An example of Process Scheduling?
Scheduling: FCFS [60]* assume processes arrive in this order: P1, P2, P3 * nonpreemptive scheduling * average waiting time: (0+24+27)/3=17 ms PIDBurstP124P23P33 Gantt chart 0242730* assume processes arrive in this order: P2, P3, P1 * average waiting time: (6+0+3)/3=3 msPIDBurstP23P33P124 Gantt chart 03630* in general, FCFS average waiting time is not minimal * in general, better to process shortest jobs firstScheduling: Round Robin (RR) [61]* similar to FCFS, but preemption to switch between processes * time quantum (time slice) is a small unit of time (10 to 100 ms) * process is executed on the CPU for at most one time quantum * implemented by using the ready queue as a circular queue * head process gets the CPU * uses less than a time quantum IMPLIES gives up the CPU voluntarily * uses full time quantum IMPLIES timer will cause an interrupt * context switch will be executed * process will be put at the tail of queue[III.B] Scheduling: RR [62]* assume processes arrive in this order: P1, P2, P3 * preemptive scheduling * time quantum: 4 ms * P1 uses a full time quantum; P2, P3 use only a part of a quantum * P1 waits 0+6=6; P2 waits 4; P3 waits 7 * average waiting time: (6+4+7)/3=5.66 msPIDBurstP124P23P33 Gantt chart 047101418222630* very large time quantum IMPLIES RR = FCFS * very small time quantum IMPLIES context switch is too much overhead * quantum approximately CPU burst IMPLIES better turnaround * rule of thumb: 80% should finish burst in 1 quantumScheduling: Shortest-Job-First (SJF) [63]* assume the next burst time of each process is known * SJF selects process which has the shortest burst time * optimal algorithm because it has the shortest average waiting time * impossible to know in advance * OS knows the past burst times - make a prediction using an average * nonpreemptive * or preemptive: * shortest-remaining-time-first * interrupts running process if a new process enters the queue * new process must have shorter burst than remaining timeScheduling: SJF [64]* assume all processes arrive at the same time: P1, P2, P3, P4 * nonpreemptive scheduling * average waiting time: (3+16+9+0)/4=7 msPIDBurstP16P28P37P43 Gantt chart 0391624* SJF is optimal: shortest average waiting time * but burst times are not known in advance * next_predicted burst time by (weighted) average of past burst times * * next_predict = last_observed + last_predict * next_predict = initialized value (usually 0) * next_predict = last_observedSJF: Weighted Average Burst [65]: : : recent and past history the same time 0 1 2 3 4 5 6 7 Burst ()6 4 6 4 13 13 13 Guess () 10 8 6 6 5 9 11 12Scheduling: SJF [66]* assume processes arrive at 1 ms intervals: P1, P2, P3, P4 * preemptive scheduling: shortest-remaining-time-first* P1 waits 0+(10-1)=9; P2 waits 1-1=0 * P3 waits 17-2=15; P4 waits 5-3=2 * average waiting time: (9+0+15+2)/4=6.5 msPIDBurstArrivalP180P241P392P453 Gantt chart 015101726* nonpremptive SJF: 7.75 msScheduling: Priority (PRIO) [67]* assume a priority is associated with each process * select highest priority process from the ready queue * let be the (predicted) next CPU burst of a process * SJF is a special case of priority scheduling * assume: high numbers IMPLY high priority * then priority is * assume: low numbers IMPLY high priority * then priority is * equal-priority processes are scheduled in FCFS order * PRIO can be preemptive or nonpreemptive * priorities can be defined internally* memory requirements, number of open files, burst times * priorities can be defined externally * user, department, companyScheduling: PRIO [68]* assume all processes arrive at the same time: P1, P2, P3, P4, P5 * nonpreemptive scheduling * high priority: low number * some OS use a high number!!! See VOS. * average waiting time is: (6+0+16+18+1)/5=8.2 msPIDBurstPriorityP1103P211P323P414P552 Gantt chart 0161618 19* indefinite blocking (starvation): low priority process never runs * aging: low priorities increase with waiting time, will eventually runVOS Scheduling: PRIO, FCFS, SJF [69]for (i=1; i> SUMMARY (READY) >>>>>>>>> SUMMARY (RUNNING)
