Operating System Process Scheduling | OS Tutorials

In Operating System Process Scheduling is the activity of selecting the next request to be serviced by a server. A scheduling policy determines the quality of service provided to users. It also influences the performance of a computer system. Scheduling policies use the fundamental techniques of preemption, reordering of requests and variation of time slice to achieve their goals.

Process Scheduling

An operating system uses a combination of three schedulers to perform its functions; those are:

1. Long-term Scheduler
2. Medium-term Scheduler
3. Short-term Scheduler

• When more than one process is in the ready state, and there is only one CPU available, the operating system must decide which process to run first.
• The part of the operating system that makes the choice is called the Scheduler; the algorithm it uses is called the scheduling algorithm.

Process Scheduling Concepts

In a single-processor system, only one process can run at a time; any others must wait until the CPU is free and can be rescheduled. Figure 1 shows a schematic of scheduling.

• All requests waiting to be serviced are kept in a list of pending requests. An arriving request is added to this list.
• Whenever scheduling is to be performed, the scheduler examines the pending request and selects one for servicing (shown by a dashed line in Figure 1).
• This request is handed over to the server. A request leaves the server when it completes or when it is preempted by the scheduler; in this case it is put back into the list of pending requests.
• In either situation, the scheduler performs scheduling to select the next request to be serviced.
• Thus, four events related to scheduling are Arrival, Scheduling, Preemption and Completion.

Objectives of Scheduling

There could be many objectives that must be considered in the design of scheduling discipline. In general, it should have the following standards followed:

1. Fairness – Fairness can be reflected by treating all the processes the same, and no process should suffer indefinite postponement.
2. Throughput – It must attempt to service the largest possible number of processes per unit time.
3. Predictable – A given job should run in about the same amount of time and at the same cost irrespective of the load on the system.
4. Overhead – A certain portion of system resources invested as overhead can greatly improve overall performance of the system.
5. Resources – Scheduling mechanisms should keep the resources of the system busy.
6. Indefinite Postponement – This could be as bad as the deadlock. Avoiding indefinite postponement can best be accomplished by ageing.
7. Priorities – Scheduling mechanisms should favour higher-priority processes.

Classification of Scheduling Algorithm

We know that, in different environments, different scheduling algorithms are needed. This situation arises because different application areas have different goals. In other words, what the scheduler should optimise for is not the same in all systems. Three environments worth distinguishing are:

• In batch systems, there are users impatiently waiting at their terminals for a quick response to a short request.
• Nonpreemptive algorithms or preemptive algorithms with long time periods for each process are often acceptable.
• In an environment with interactive users, preemption is essential to keep one process from hogging the CPU and denying service to the others.
• In a system with real-time constraints, preemption is enough; they may not run for long periods of time.
• The difference with interactive systems is that real time system run only programs that are intended to further the application at hand.
• Interactive systems are general purpose and may run arbitrary programs that are not cooperative or even malicious.

Terms Associated with Scheduling

Request Related

• Arrival time – time when a user submits a job/process.
• Admission time – time when the system starts considering a job/process for scheduling.
• Completion time – time when a job/process must be completed to meet the response requirement of a real-time application.
• Service Time – The total of CPU time and I/O time required by a job/ process or subrequest to complete its operation.
• Preemption – Forced deallocation of CPU from a job/process.
• Priority – It is a tie-breaking rule used to select a request when many requests await service.

User Service Related

• Fair Share – A specified share of CPU time that should be devoted to execution of a process or a group of processes.
• Response Time – Time between the submission of a sub-request for processing to the time its result becomes available. This concept applies to interactive processes.
• Response Ratio – is the ratio of $\space\frac{Time\space since\space arrival + Service\space time \space of\space the\space process}{Service\space time\space of\space the\space process}$
• Turn-Around Time – time between the submission of a job/process and its completion by the system.
• Weighted Turn-around – Ratio of the turn-around time of a job/process to its own service time.

User Service Related: Average Service

• Mean Response Time (rt) – Average of the response times of all sub-requests serviced by the system.
• Mean Turn-Around Time (ta) – Average of the turn-around times of all jobs/processes serviced by the system.

Scheduling Related

• Scheduling length – Time taken to complete a specific set of jobs/proceses.
• Throughput – The average number of jobs/process or sub-requests completed by a system in one unit of time.