Process Scheduling B Ramamurthy Page 1 01 13 19 Introduction An important aspect of multiprogramming is scheduling The resources that are scheduled are IO and processors The goal is to achieve High processor utilization High throughput number of processes completed per unit time Low response time time elapse from the submission of a request to the beginning of the response Page 2 01 13 19 Topics for discussion Motivation Types of scheduling Short term scheduling Various scheduling criteria Various algorithms Priority queues First come first served Round robin Shortest process first Shortest remaining time and others Realtime scheduling Page 3 01 13 19 The CPU I O Cycle We observe that processes require alternate use of processor and I O in a repetitive fashion Each cycle consist of a CPU burst typically of 5 ms followed by a usually longer I O burst A process terminates on a CPU burst CPU bound processes have longer CPU bursts than I O bound processes Page 4 01 13 19 CPU IO Bursts Bursts of CPU usage alternate with periods of I O wait a CPU bound process an I O bound process Page 5 01 13 19 Motivation Consider these programs with processing component and IO component indicated by upper case and lower case letters respectively A1 a1 A2 a2 A3 0 30 50 80 120 130 JOB A B1 b1 B2 0 20 40 60 JOB B C1 c1 C2 c2 C3 c3 C4 c4 C5 0 10 20 60 80 100 110 130 140 150 JOB C Page 6 01 13 19 Motivation The starting and ending time of each component are indicated beneath the symbolic references A1 b1 etc Now lets consider three different ways for scheduling no overlap round robin simple overlap Compare utilization U time CPU busy total run time Page 7 01 13 19 Scheduling Criteria CPU utilization keep the CPU as busy as possible Throughput of processes that complete their execution per time unit Turnaround time amount of time to execute a particular process Waiting time amount of time a process has been waiting in the ready queue and blocked queue Response time amount of time it takes from when a request was submitted until the first response is produced not output for timesharing environment Page 8 01 13 19 Optimization Criteria Max CPU utilization Max throughput Min turnaround time Min waiting time Min response time Page 9 01 13 19 Types of scheduling Long term To add to the pool of processes to be executed Medium term To add to the number of processes that are in the main memory Short term Which of the available processes will be executed by a processor IO scheduling To decide which process s pending IO request shall be handled by an available IO device Page 10 01 13 19 Classification of Scheduling Activity Long term which process to admit Medium term which process to swap in or out Short term which ready process to execute next Page 11 01 13 19 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 P1 P P Average waiting time 0 24 27 32 17 3 0 Page 12 24 27 30 01 13 19 FCFS Scheduling Cont Suppose that the processes arrive in the order P2 P3 P 1 The Gantt chart for the schedule is P2 P3 P1 Waiting time for P1 6 P2 0 P3 3 Average waiting time 6 0 3 3 3 0 3 6 30 Much better than previous case Convoy effect short process behind long process Page 13 01 13 19 Shortest Job First SJR 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 Page 14 01 13 19 Example of NonPreemptive SJF Process Arrival TimeBurst Time P1 0 0 7 P2 2 0 4 P3 4 0 1 P4 5 0 4 P1 0 3 P3 7 P2 8 P4 12 16 Average waiting time 0 6 3 7 4 4 Page 15 01 13 19 Example of Preemptive SJF Process Arrival TimeBurst Time P1 0 0 7 P2 2 0 4 P3 4 0 1 P4 5 0 4 P1 P2 P3 P2 P4 P1 11 16 0 2 4 5 time 7 9 Average waiting 1 0 2 4 3 Page 16 01 13 19 Shortest job first critique Possibility of starvation for longer processes as long as there is a steady supply of shorter processes Lack of preemption is not suited in a time sharing environment CPU bound process gets lower priority as it should but a process doing no I O could still monopolize the CPU if he is the first one to enter the system SJF implicitly incorporates priorities shortest jobs are given preferences The next preemptive algorithm penalizes directly longer jobs Page 17 01 13 19 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 1 tn actual lenght of nthCPU burst 2 n 1 predicted value for the next CPU burst 3 0 1 4 Define n 1 tn 1 n Page 18 01 13 19 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 t n 1 1 j t n j 1 n 1 1 Since both and 1 are less than or equal to 1 each successive term has less weight than its predecessor Page 19 01 13 19 More on Exponential Averaging S n 1 next burst s n current burst S n 1 T n 1 S n 0 1 more weight is put on recent instances whenever 1 n By expanding this eqn we see that weights of past instances are decreasing exponentially S n 1 T n 1 T n 1 1 i T n i 1 nS 1 predicted value of 1st instance S 1 is not calculated usually set to 0 to give priority to to new processes Page 20 01 13 19 Exponentially Decreasing Coefficients Page 21 01 13 19 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 Page 22 01 13 19 Round Robin RR Each …
View Full Document
Unlocking...