Computer Operating System - Lecture 6: CPU Scheduling - Nguyen Thanh Son

Nội dung text: Computer Operating System - Lecture 6: CPU Scheduling - Nguyen Thanh Son

1. Chapter’s Content  Basic Concepts  Scheduling Criteria  Scheduling Algorithms  Multiple-Processor Scheduling  Real-Time Scheduling  Algorithm Evaluation BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 2
2. Alternating Sequence of CPU And I/O Bursts BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 4
3. 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. BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 6
4. 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  Response time – amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment) BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 8
5. 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: P1 P2 P3 0 24 27 30 Waiting time for P1 = 0; P2 = 24; P3 = 27  Average waiting time: (0 + 24 + 27)/3 = 17 BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 10
6. 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 BK time for a given set of processes. TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 12
7. 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) P P P P P P 1 2 3 2 4 1 0 2 4 5 7 11 16  BK Average waiting time = (9 + 1 + 0 +2)/4 - 3 TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 14
8. Prediction of the Length of the Next CPU Burst BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 16
9. 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. BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 18
10. 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  Typically, higher average turnaround than SJF, but better response. BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 20
11. Turnaround Time Varies With The Time Quantum BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 22
12. Multilevel Queue Scheduling BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 24
13. 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, BK it is preempted and moved to queue Q2. TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 26
14. Multiple-Processor Scheduling  CPU scheduling more complex when multiple CPUs are available.  Homogeneous processors within a multiprocessor.  Load sharing  Asymmetric multiprocessing – only one processor accesses the system data structures, alleviating the need for data sharing. BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 28
15. Dispatch Latency BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 30
16. Evaluation of CPU Schedulers by Simulation BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 32
17. Windows 2000 Priorities BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 34