CPU SCHEDULINGCPU scheduling in UNIX is designed to benefit interactive processes. Processes are given small CPU time slices by a priority algorithm that reduces to round-robin scheduling for CPU-bound jobs.The scheduler on UNIX system belongs to the general class of operating system schedulers known as round robin with multilevel feedback which means that the kernel allocates the CPU time to a process for small time slice, preempts a process that exceeds its time slice and feed it back into one of several priority queues. A process may need much iteration through the "feedback loop" before it finishes. When kernel does a context switch and restores the context of a process. The process resumes execution from the point where it had been suspended.Each process table entry contains a priority field. There is a process table for each process which contains a priority field for process scheduling. The priority of a process is lower if they have recently used the CPU and vice versa.The more CPU time a process accumulates, the lower (more positive) its priority becomes, and vice versa, so there is negative feedback in CPU scheduling and it is difficult for a single process to take all the CPU time. Process aging is employed to prevent starvation.Older UNIX systems used a 1-second quantum for the round- robin scheduling. 4.33SD reschedules processes every 0.1 second and recomputed priorities every second. The round-robin scheduling is accomplished by the -time-out mechanism, which tells the clock interrupt driver to call a kernel subroutine after a specified interval; the subroutine to be called in this case causes the rescheduling and then resubmits a time-out to call itself again. The priority recomputation is also timed by a subroutine that resubmits a time-out for itself event. The kernel primitive used for this purpose is called sleep (not to be confused with the user-level library routine of the same name.) It takes an argument, which is by convention the address of a kernel data structure related to an event that the process wants to occur before that process is awakened. When the event occurs, the system process that knows about it calls wakeup with the address corresponding to the event, and all processes that had done a sleep on the same address are put in the ready queue to be run. |

Scheduling in the 4.2BSD UNIX OS
Short term scheduling in UNIX Is designed to benefit interactive jobs. Processes are given small CPU time slices by an algorithm that reduces to round robin for CPU-bound jobs, although there is a priority scheme. There's no preemption of one process by another when running in kernel mode. A process may relinquish the CPU because it's waiting for I/O (including I/O due to page faults) or because its time slice has expired.
Every process has a scheduling priority associated with it; the lower the numerical priority, the more likely is the process to run.
System processes doing disk I/O and other important tasks have negative priorities and cannot be interrupted. Ordinary user processes have positive priorities and thus are less likely to be run than any system process, although user processes may have precedence over one another. The nice command may be used to affect this precedence according to its numerical priority argument.
The more CPU time a process accumulates, the lower (more positive) its priority becomes. The reverse is also true (process aging is employed to prevent starvation). Thus there is negative feedback in CPU scheduling, and it’s difficult for a single process to take CPU all time.
Old UNIX systems used a 1 sec. quantum for the round-robin scheduling algorithm. Later 4.2BSD did rescheduling every 0.1 seconds, and priority re-computation every second. The round-robin scheduling is accomplished by the timeout mechanism, which tells the clock interrupt driver to call a certain system routine after a specified interval. The subroutine to be called in this case causes the rescheduling and then resubmits a timeout to call itself again 0.1 sec later. The priority re-computation is also timed by a subroutine that resubmits a timeout for itself.
When a process chooses to relinquish the CPU (voluntarily, in a user program, or because this decision is to be made in the kernel context for a process executing that program) it sleep on an even. The system call used for this is called sleep (not to be confused with the C library routine with the same name, sleep(3)). It takes an argument that is by convention the address of a kernel data structure related to an event the process wants to occur before it is awakened. When the event occurs, the system process that knows about it calls wakeup with the address corresponding to the event, and all processes that had done a sleep on the same address are put in the ready queue.
For example, a process waiting for disk I/O to complete will sleep on the address of the buffer corresponding to the data being transferred. When the interrupt routine for the disk driver notes that the transfer is complete, it calls wakeup on that buffer, causing all processes waiting for that buffer to be awakened. Which process among those actually does run is chosen by the scheduler effectively at random. Sleep, however, also takes a second argument, which is the scheduling priority to be used for this purpose.

CPU - I/O Burst Cycle
• Bursts of CPU usage alternate with periods of I/O wait – a CPU-bound process – an I/O bound process2 3 Basic Concepts • CPU–I/O Burst Cycle – Process execution consists of a cycle of CPU execution and I/O wait.
• Maximum CPU utilization obtained with multiprogramming 4 CPU Scheduler • Selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them. • CPU scheduling decisions may take place when a process:
1. Switches from running to waiting state. 2. Switches from running to ready state. 3. Switches from waiting to ready. 4. Terminates. • Scheduling under 1 and 4 is nonpreemptive. • All other scheduling is preemptive.
3 5 Scheduling Metrics • CPU utilization – keep the CPU as busy as possible
• Throughput – # of processes that complete their execution per time unit
• Turnaround/Response time – amount of time to execute a particular process • Waiting time – amount of time a process has been waiting in the ready queue 6 Scheduling Algorithm Goals4 7 Dispatcher • Dispatcher module gives control of the CPU to the process selected by the scheduler; this involves: – switching context – switching to user mode – jumping to the proper location in the user program to restart that program
• Dispatch latency – time it takes for the dispatcher to stop one process and start another running. 8 First-Come, First-Served (FCFS) Scheduling Process Burst Time P1 24 P2 3 P3 3
• Suppose that the processes arrive in the order: P1 , P2, P3 The Gantt Chart for the schedule is: • Waiting time for P1 = 0; P2 = 24; P3 = 27
• Average waiting time: (0 + 24 + 27)/3 = 17 P1 P2 P3 24 27 300 5 9 FCFS Scheduling (Cont.) Suppose that the processes arrive in the order P2 , P3 , P1 . • The Gantt chart for the schedule is: • Waiting time for P1 = 6; P2 = 0; P3 = 3
• Average waiting time: (6 + 0 + 3)/3 = 3
• Much better than previous case. • Convoy effect short process behind long process P1 P3 P2 6 3 30 0 10 Shortest-Job-First (SJF) Scheduling
• Associate with each process the length of its next CPU burst. Use these lengths to schedule the process with the shortest time. • Two schemes: – nonpreemptive – once CPU given to the process it cannot be preempted until completes its CPU burst. – preemptive – if a new process arrives with CPU burst length less than remaining time of current executing process, preempt. This scheme is know as the Shortest-Remaining-Time-First (SRTF). • SJF is optimal – gives minimum average waiting time for a given set of processes.6 11 Example of Preemptive SJF Process Arrival Time Burst Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 • SJF (preemptive) • Average waiting time = (9 + 1 + 0 +2)/4 = 3 P1 P3 P2 4 2 11 0 P4 5 7 P2 P1 16 12 Process Arrival Time Burst Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 • SJF (non-preemptive)
• Average waiting time = (0 + 6 + 3 + 7)/4 = 4 Example of Non-Preemptive SJF P1 P3 P2 7 3 16 0 P4 8 127 13 Determining Length of Next CPU Burst
• Can only estimate the length.
• Can be done by using the length of previous CPU bursts, using exponential averaging.
: Define 4. 1 0 , 3. burst CPU next for the value predicted 2. burst CPU of length actual 1. 1 ≤ ≤ = =+ α α τ n th n n t ( ) n n n t τ α α τ −+ =+ 1 1 14 Examples of Exponential Averaging
• α =0 – τn+1 = τn – Recent history does not count. • α =1 – τn+1 = tn – Only the actual last CPU burst counts.
• If we expand the formula, we get: τn+1 = α tn+(1 - α) α tn-1+ … +(1 - α )j α tn-j + … +(1 - α )n+1τ0
• Since both α and (1 - α) are less than or equal to 1, each successive term has less weight than its predecessor.8 15 Priority Scheduling • A priority number (integer) is associated with each process • The CPU is allocated to the process with the highest priority (smallest integer ≡ highest priority). – Preemptive – Non-preemptive
• SJF is a priority scheduling where priority is the predicted next CPU burst time. • Problem ≡ Starvation – low priority processes may never execute.
• Solution ≡ Aging – as time progresses increase the priority of the process. 16 Round Robin (RR) • Each process gets a small unit of CPU time (time quantum), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue. • If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n-1)q time units. • Performance – q large ⇒ FIFO – q small ⇒ q must be large with respect to context switch, otherwise overhead is too high.9 17 Example of RR with Time Quantum = 20 Process Burst Time P1 53 P2 17 P3 68 P4 24 • The Gantt chart is: Typically, higher average turnaround than SJF, but better interactive response. P1 P2 P3 P4 P1 P3 P4 P1 P3 P3 0 20 37 57 77 97 117 121 134 154 162 18 Multilevel Queue
• Ready queue is partitioned into separate queues: e.g., foreground (interactive), background (batch) • Each queue has its own scheduling algorithm, e.g., foreground – RR, background – FCFS
• Scheduling must be done between the queues. – Fixed priority scheduling; (i.e., serve all from foreground then from background). Possibility of starvation. – Time slice – each queue gets a certain amount of CPU time which it can schedule amongst its processes; e.g., 80% to foreground in RR, 20% to background in FCFS 10 19 Multi-queue priority scheduling A scheduling algorithm with four priority classes 20 Multilevel Feedback Queue • A process can move between the various queues; – aging can be implemented this way.
• Multilevel-feedback-queue scheduler defined by the following parameters: – number of queues – scheduling algorithms for each queue – method used to determine when to upgrade a process – method used to determine when to demote a process – method used to determine which queue a process will enter when that process needs service11 21 Example of Multilevel Feedback Queue • Three queues: – Q0 – time quantum 8 milliseconds – Q1 – time quantum 16 milliseconds – Q2 – FCFS • Scheduling – A new job enters queue Q0 which is served FCFS. When it gains CPU, job receives 8 milliseconds. If it does not finish in 8 milliseconds, job is moved to queue Q1. – At Q1 job is again served FCFS and receives 16 additional milliseconds. If it still does not complete, it is preempted and moved to queue Q2. 22 Multilevel Feedback Queues12 23 Multiple-Processor Scheduling • CPU scheduling more complex when multiple CPUs are available. • Homogeneous processors within a multiprocessor. • Load sharing 24 Real-Time Scheduling
• Hard real-time systems – required to complete a critical task within a guaranteed amount of time. • Soft real-time computing – requires that critical processes receive priority over less fortunate ones.13 25 Solaris 2 Scheduling 26 Windows 2000 Windows 2000 supports 32 priorities for threads14 27 Windows 2000 Priorities 28 UNIX Scheduler The UNIX scheduler is based on a multilevel queue structure