操作系统原理5章节(1297KB).ppt

* 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) Average waiting time = (0 + 6 + 3 + 7)/4 = 4 Operating System Concepts P1 P3 P2 7 3 16 0 P4 8 12 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 Operating System Concepts P1 P3 P2 4 2 11 0 P4 5 7 P2 P1 16 How do we know the Next CPU Burst? Without a good answer to this question, SJF cannot be used for CPU scheduling. We try to predict the next CPU burst! Can be done by using the length of previous CPU bursts, using exponential averaging. Operating System Concepts Operating System Concepts Examples of Exponential Averaging ? =0 ?n+1 = ?n Recent history does not count. ? =1 ?n+1 = tn Only the actual last CPU burst counts. Operating System Concepts Prediction of the Length of the Next CPU Burst Operating System Concepts Examples of Exponential Averaging (Cont.) 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. Operating System Concepts SJF Problems It is difficult to estimate the next burst time value accurately. SJF is in favor of short jobs. As a result, some long jobs may not have a chance to run at all. This is starvation. Operating System Concepts Priority Scheduling Each process has a priority. Priority may be determined internally or externally: internal priority: determined by time limits,memory requirement, # of files, and so on. external priority: not controlled by the OS (e.g., importance of the process) The scheduler always picks the process (in ready queue) with the highest priority to run. FCFS and SJF are special cases of priority scheduling. (Why?) Operating System Concepts Priority Scheduling (Cont.) Prior