CPU Scheduling PDF

CPU Scheduling Basic Concepts Scheduling Criteria Scheduling Algorithms 1  CPU Scheduler: OS Selects among processes in memory that are ready to be executed, and allocates CPU to one of them. CPU scheduling decisions may take place when a pr...

CPU Scheduling Basic Concepts Scheduling Criteria Scheduling Algorithms 1  CPU Scheduler: OS Selects among processes in memory that are ready to be executed, and allocates 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. 2  CPU Scheduling Criteria CPU utilization – keep the CPU as busy as possible Throughput – # of processes that complete their execution per unit time Turnaround time – total time required to execute a particular process Waiting time – amount of time a process waits in the ready queue Response time – amount of time it takes from when a request was submitted until the first response is produced. 3  CPU Optimization Criteria Maximize throughput - run as many jobs as possible in a given amount of time. – This could be accomplished easily by running only short jobs or by running jobs without interruptions. Minimize response time - quickly turn around interactive requests. – This could be done by running only interactive jobs and letting the batch jobs wait until the interactive load ceases. Minimize turnaround time - move entire jobs in and out of the system quickly. – This could be done by running all batch jobs first (because batch jobs can be grouped to run more efficiently than interactive jobs). 4  CPU Optimization Criteria… Minimize waiting time - move jobs out of the READY queue as quickly as possible. – This could only be done by reducing the number of users allowed on the system so the CPU would be available immediately whenever a job entered the READY queue. Maximize CPU efficiency - keep the CPU busy 100 percent of the time. – This could be done by running only CPU-bound jobs (and not I/O- bound jobs). Ensure fairness for all jobs - give everyone an equal amount of CPU and I/O time. – This could be done by not giving special treatment to any job, 5 regardless of its processing characteristics or priority.  Process Scheduling Algorithms Part of the operating system that makes scheduling decision is called scheduler and the algorithm it uses is called scheduling algorithm The Process Scheduler relies on a process scheduling algorithm, – based on a specific policy, to allocate the CPU and move jobs through the system. There are six process scheduling algorithms that have been 6 used extensively. First-Come, First-Served (FCFS) Scheduling Basic Concept is a non preemptive scheduling algorithm that handles jobs according to their arrival time: the earlier they arrive, the sooner they're served. It's a very simple algorithm to implement because it uses a FIFO queue. In a strictly FCFS system there are no WAIT queues (each job is run to completion). 7 First-Come, First-Served (FCFS) Scheduling Process Burst Time (msec) P1 2 4 P2 3 P3 3 Suppose that the processes arrive in the order: P1 , P2 , P3 The Gantt Chart for the schedule is: P1 P2 P3 0 24 27 30 Waiting time for P1 = 0; P2 = 24; P3 = 27 Average waiting time: (0 + 24 + 27)/3 = 17 Turnaround time for P1=24, P2=27, P3=30 Avg turnaround time: (24+27+30)/3= 27  FCFS Scheduling (Cont.) Suppose that the processes arrive in the order P2 , P3 , P1. The Gantt chart for the schedule is: P2 P3 P1 0 3 6 30 Waiting time for P1 = 6; P2 = 0; P3 = 3 Average waiting time: (6 + 0 + 3)/3 = 3 Turnaround time for P1 =30, P2 =3, P3 =6 Avg turnaround time: (30+3+6)/3= 13 Much better than previous case. 6 6  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 1 processes. 0  Example of Non-Preemptive SJF Process Arrival Time Burst Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 SJF (non-preemptive) P1 P3 P2 P4 0 3 7 8 12 16 Waiting time P1=0-0=0, P2=8-2=6, P3=7-4=3, P4=12-5=7 Average waiting time = (0 + 6 + 3 + 7)/4 = 4 Turnaround time: P1= 7-0=7, P2=12-2=10, P3=8-4=4, P4=16-5=11 Avg. turnaround time: (7+10+4+11)/4= 8  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) P1 P2 P3 P2 P4 P1 0 2 4 5 7 11 16 Average waiting time = (9 + 1 + 0 +2)/4 = 3 Turnaround time:P1=16-0=16, P2=7-2=5, P3=5-4=1, P4=11-5=6 Avg. turnaround time= (16+5+1+6)/4=7 70 1 3 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 ▪ nonpreemptive 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.  Example of Priority Scheduling Let's assume we have 4 processes with the following details: Process Burst Time Priority P1 10 2 P2 1 1 P3 2 4 P4 1 3 Scheduling Order: Based on the table above, the order is: 1.P2 (priority 1) 2.P1 (priority 2) 3.P4 (priority 3) 4.P3 (priority 4) Calculation of Waiting Time and Turnaround Time: Step-by-step Calculations: 1.P2 runs first (highest priority). 1. Waiting Time (WT) for P2 = 0 (it starts immediately) 2. Turnaround Time (TT) for P2 = 1 (WT + Burst Time) 2.P1 runs next. 1. Waiting Time for P1 = 1 (P2's burst time) 2. Turnaround Time for P1 = 1 + 10 = 11 3.P4 runs third. 1. Waiting Time for P4 = 1 + 10 = 11 2. Turnaround Time for P4 = 11 + 1 = 12 4.P3 runs last. 1. Waiting Time for P3 = 1 + 10 + 1 = 12 2. Turnaround Time for P3 = 12 + 2 = 14 Average Times: Average Waiting Time = (0 + 1 + 11 + 12) / 4 = 6 Average Turnaround Time = (1 + 11 + 12 + 14) / 4 = 9.5  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. 1 6  Example of RR with Time Quantum = 20 Process Burst Time P1 53 P2 17 P3 68 P4 24 The Gantt chart is: P1 P2 P3 P4 P1 P3 P4 P1 P3 P3 0 20 37 57 77 97 117 121 134 154 162 Avg turnaround time = (134+37+162+121)/4 = 113.5 Average Waiting Time = (81 + 20 + 94 + 97) / 4 = 73 73 Typically, higher average turnaround than SJF, but better response.