Ch4 CPU Scheduling PDF - Princess Nora University

Princess Nora University Computer Sciences Department Operating Systems CS 340 1 Term 1 - 1446  Chapter-4 CPU Scheduling (covered in chapter 6 of textbook) Chapter 4: CPU Scheduling 1. Basic Concepts 2. Scheduling Criteria 3. Scheduling Algorithms...

Princess Nora University Computer Sciences Department Operating Systems CS 340 1 Term 1 - 1446  Chapter-4 CPU Scheduling (covered in chapter 6 of textbook) Chapter 4: CPU Scheduling 1. Basic Concepts 2. Scheduling Criteria 3. Scheduling Algorithms 3 OBJECTIVES:  To introduce CPU scheduling, which is the basis for multiprogrammed operating systems  To describe various CPU-scheduling algorithms 4 Basic Concepts 5 Basic Concepts CPU–I/O Burst Cycle : o Process execution consists of a cycle of CPU execution and I/O wait  The process alternates between these two states o Process execution begins with a CPU burst…That is followed by an I/O burst, which is followed by another CPU burst, then another I/O burst, and so on. o Eventually, the final CPU burst ends with a system request to terminate execution 6 Histogram of CPU-burst Times The durations of CPU bursts vary greatly from process to process. There is large number of short CPU bursts and a small number of long CPU bursts. An I/O-bound program >>>> has many short CPU bursts. A CPU-bound program >>>> has a few long CPU bursts 7  CPU Scheduler  CPU Scheduler (/ short-term scheduler): o Whenever the CPU becomes idle, the short-term scheduler must select one process from among multiple ready processes in memory (ready queue) and allocates the CPU to one of them to be executed. o The ready queue is NOT necessarily a first-in, first-out (FIFO) queue. It can be implemented as a FIFO queue, a priority queue, a tree, or an unordered linked list. 8 Preemptive Scheduling 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 case(1) and (4) is non-preemptive (/cooperative).  scheduling under case (2) and (3) is preemptive 9 Preemptive Scheduling (cont..)  What is non-preemptive scheduling? Once the CPU has been allocated to a process, the process keeps the CPU until it releases the CPU either by terminating or by switching to the waiting state.  What is preemptive scheduling? The process can be removed forcibly from the CPU before finish executing because a better process arrives to the ready queue. 10 Dispatcher  Dispatcher : is an OS module gives control of the CPU to the process selected by the short-term scheduler.  The dispatcher should be as fast as possible, since it is invoked during every process switch.  Dispatch latency: is amount of time it takes for the dispatcher to stop one process and start another running. ( i.e. context switch time) 11 Scheduling Criteria 12 Scheduling Criteria 1. CPU utilization 2. Throughput 3. Turnaround time 4. Waiting time 5. Response time 13  Scheduling Criteria  CPU utilization: the time percentage that the CPU is busy (/not idle).  Throughput : number of processes that complete their execution per time unit (e.g. 10 processes /sec)  Turnaround time: time interval from the time of submission of a process to the time of completion. (i.e. how long it takes to execute a process?) Turnaround time = waiting time to get into RAM + waiting time in RAM (ready queue) + CPU execution time+ I/O time Turnaround time = Termination time- creation time 14 Scheduling Criteria (cont.)  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. (i.e. is the time it takes to start responding, not the time it takes to output the response)  In an interactive system, response time is very important. 15 Scheduling Criteria (cont.)  It is desirable to:  Max CPU utilization  Max throughput  Min turnaround time  Min waiting time  Min response time 16 Useful Notes: Key Concepts in CPU Scheduling:  Arrival Time (AT):  Refers to the moment in time when a process enters the ready queue and is awaiting execution by the CPU.  Burst Time (BT) (execution time):  Refers to the amount of CPU time the process requires to complete its execution  Completion Time (CT):  Is when a process finishes execution and is no longer being processed by the CPU.  Turnaround Time (TAT):  Turnaround Time = Completion Time – Arrival Time  Waiting Time (WT):  Waiting Time = Turnaround Time – Burst Time.  Response Time (RT):  Response Time = Time it Started Executing – Arrival Time. 17 Scheduling Algorithms 18 Scheduling Algorithms 1. First-Come, First-Served Scheduling (FCFS) 2. Shortest-Job-First Scheduling (SJF) 3. Priority Scheduling 4. Round-Robin Scheduling (RR) 5. Multilevel Queue Scheduling. 6. Multilevel Feedback Queue. 19 (1) First-Come, First-Served (FCFS)  FCFS is the simplest CPU-scheduling algorithm Basic Methodology:  The process that requests the CPU first is allocated first.  FCFS algorithm is always non-preemptive 20 (1) First-Come, First-Served (FCFS)  FCFS can be implemented using FIFO queue:  When a process enters the ready queue, its PCB is linked onto the tail of the queue. When the CPU is free, it is allocated to the process at the head of the queue. The running process is then removed from the queue.  Gantt chart: is a bar chart that illustrates a particular schedule, including the start and finish times of each of the processes. 21  (1) First-Come, First-Served (FCFS) -cont..  Example(1): Consider the following set of processes that arrive at time 0, with the length of the CPU burst given in milliseconds Suppose that the processes arrive in the order: P1 , P2 , P3 Draw the Gantt chart using (FCFS) algorithm and find the average WT. Process Burst time (ms)  The Gantt Chart for the schedule is: P1 24 P1 P2 P3 P2 3 P3 3 0 24 27 30  WT for P1 = 0; P2 = 24; P3 = 27  Average WT: (0 + 24 + 27)/3 = 17 22 (1) First-Come, First-Served (FCFS) -cont..  Example(1)- cont.: Waiting time for P1= W(P1) = (0-0)=0 ms W(P2) = (24-0)=24 ms W(P3) = (27-0)=27 ms Average waiting time = (0+24+27)/3 = 17ms  Waiting time = Σ waiting intervals time in to CPU- arrival time (if it is the FIRST interval)  waiting interval= time in to CPU- last time out of CPU (if it is the NOT the first interval) 23 (1) First-Come, First-Served (FCFS) -cont.. Example(2): Consider the same previous set of processes arrive at time 0,with the length of the CPU burst in milliseconds Suppose that the processes arrive in the order: P2 , P3 , P1 Draw the Gantt chart using (FCFS) algorithm and find the average WT. Process Burst time (ms) P1 24 P2 3 P3 3  The Gantt chart for the schedule is: P2 P3 P1 0 3 6 30  W(P1) = 6 ms ; W(P2) = 0 ms ; W(P3) = 3 ms  Average WT: (6 + 0 + 3)/3 = 3 ms >>Much better than example (1)..WHY?? 24 (1) First-Come, First-Served (FCFS) -cont..  Convoy effect :  It is problem appears in FCFS algorithm where short processes wait for the one big process to get off the CPU.  This effect results in lower CPU and device utilization 25 (1) First-Come, First-Served (FCFS) -cont..  FCFS Pros. (++):  Simplest algorithm  FCFS Cons. (--):  The average waiting time is generally not minimal (quite long) and affected by processes’ order.  Lower CPU and device utilization because of convoy effect  The average response time is generally bad (i.e. Not suitable for time-shared systems) 26 (2) Shortest-Job-First (SJF) Scheduling Basic Methodology:  Associate with each process the length of its next CPU burst.  Use these lengths to select the process with the shortest time  If the next CPU bursts of two processes are the same, FCFS scheduling is used to select the next process.  Two schemes: Non-preemptive & Preemptive 27 (2) Shortest-Job-First (SJF) -cont.. Two schemes: Non-preemptive SJF Preemptive SJF once CPU given to the process it If a new process arrives with CPU burst cannot be preempted until length less than remaining time of completes its CPU burst current executing process, preempt. This is also known as Shortest-remaining Time First scheduling. 28 (2) Shortest-Job-First (SJF) -cont..  Example(3): Consider the following set of processes. Draw the Gantt chart using (Non-preemptive SJF) algorithm and find the average waiting time. Process Arrival time Burst time (ms) P1 0 7 P2 2 4 P3 4 1 P4 5 4 P1 P3 P2 P4 0 3 7 8 12 16  W(P1) = 0 ms ; W(P2) = 6 ms ; W(P3) = 3 ms ; W(P4) = 7 ms  Average waiting time=(0 + 6 + 3 + 7)/4 = 4 ms 29 (2) Shortest-Job-First (SJF) -cont..  Example(4): Consider the following set of processes. Draw the Gantt chart using (preemptive SJF) algorithm and find the average WT and TAT of each process. Process Arrival time Burst time (ms) P1 0 7 P2 2 4 P3 4 1 P4 5 4 P1 P2 P3 P2 P4 P1 0 2 4 5 7 11 16  WT:  WT(P1) =9ms ; WT(P2) = 1ms ; WT(P3) = 0ms ; WT(P4) = 2ms  Average WT= (9 + 1 + 0 +2)/4 = 3ms.  TAT:  TAT(P1) =16ms ; TAT(P2) =5ms ; TAT(P3) = 1ms ; TAT(P4) = 6ms. 30 (2) Shortest-Job-First Scheduling-(cont..)  SJF Pros. (++): SJF is optimal – gives minimum average waiting time for a given set of processes  SJF Cons. (--): The difficulty is knowing the length of the next CPU request (sometimes this time is predicted).  This type of scheduling is more appropriate for long-term scheduling and NOT for short-term scheduling.  Because the next CPU burst length is difficult to predict.  Try to predict the length from previous lengths. 31 (3) Priority Scheduling Basic Methodology:  A priority number (integer) is associated with each process. The CPU is allocated to the process with the highest priority.  Equal-priority processes are scheduled in FCFS order.  The priority can be defined:  Internally: use measurable quantities such as number of open files.  Externally: set criteria outside the OS such as the importance of a process department.  Textbook assumes (smallest integer  highest priority)  Two schemes: Non-preemptive & Preemptive 32 (3) Priority Scheduling (cont..)  Two schemes: Non-preemptive priority algorithm Preemptive priority algorithm Once CPU is given to the process If a new process arrives with it cannot be preempted until it priority higher of current completes its CPU burst. executing process, preempt. Newly arrived process with the highest priority will be at the head of the ready queue. 33 (3) Priority Scheduling (cont..)  Example(5): Consider the following set of processes. Draw the Gantt chart using (Non-preemptive priority) algorithm and find the average WT and TAT of each process where higher priority in the system is (1). Process Arrival time Burst time (ms) Priority P1 3 6 5 P2 5 2 3 P3 6 1 2 P1 P3 P2 3 9 10 12  WT:  WT(P1) =0ms ; WT(P2) = 5ms ; WT(P3) = 3ms  Average WT= (0 + 5 + 3)/3 = 2.7ms  TAT:  TAT(P1) =6ms ; TAT(P2) = 7ms ; TAT(P3) = 4ms 34 (3) Priority Scheduling (cont..)  Example(6): Consider the following set of processes. Draw the Gantt chart using (preemptive priority) algorithm and find the average WT and TAT of each process, where higher priority in the system is (1). Process Arrival time Burst time Priority P1 5 6 8 P2 7 2 1 P3 9 3 8 P4 11 4 9 P5 25 1 3 P1 P2 P1 P3 P4 idle P5 5 7 9 13 16 20 25 26  WT(P1) =2ms; WT(P2)=0ms ; WT(P3) = 4ms; W(P4) = 5ms; W(P5) = 0ms.  Average WT = (2 + 0 + 4 +5 + 0)/5 = 2.2 ms.  TAT  exercise.. 35 (3) Priority Scheduling (cont..)  Priority scheduling Pros. (++):  Simple algorithm  Priority scheduling Cons. (--):  Main Problem : Starvation ( /indefinite blocking) where low priority processes may never execute.  A process that is ready to run but waiting for the CPU can be considered as blocked.  Solution : Aging >>as time progresses, system increase the priority of the process. 36 (4) Round Robin Scheduling (RR) Basic Methodology:  Each process gets a small unit of CPU time (time quantum).  After this time has elapsed, the process is preempted and added to the end of the ready queue.  The ready queue is treated as a circular queue and implemented as FIFO queue  RR algorithm is always preemptive.  Similar to FCFS but with preemption to enable the system to switch between processes.  (RR) algorithm is designed especially for time-sharing systems (to improve response time ).  Time quantum (/ time slice ) (q)>> usually 10-100 ms. 37 (4) Round Robin Scheduling (cont..)  Example(7): Consider the following set of processes. Draw the Gantt chart using (RR) algorithm and find the average waiting time where time quantum (q=5ms) Process Arrival time Burst time (ms) P1 3 18 P2 5 2 P3 9 1 P1 P2 P1 P3 P1 P1 3 8 10 15 16 21 24  WT(P1) =3 ms ; WT(P2) = 3 ms ; WT(P3) = 6 ms  Average WT= (3 + 3 + 6 )/3 = 4 ms 38 (4) Round Robin Scheduling (cont..)  If there are n processes in the ready queue and the time quantum is q, then :  Each process gets [(1/n) *CPU time] in chunks of at most (q) time units at once.  Maximum waiting time for any process= (n-1) *q time units.  Performance depends on the size of the time quantum (q)  If q is very large  RR is same as FCFS  If q is very small  decrease the performance because of context switch time and increase system overhead Switching the CPU to another process requires performing a state save of the current process and a state restore of a different process. 39 (4) Round Robin Scheduling (cont..)  Turnaround time depends on the size of the time quantum:  The average turnaround time can be improved if most processes finish their next CPU burst in a single time quantum. 40 (4) Round Robin Scheduling (cont..)  RR Scheduling Pros. (++):  Suitable to time-shared system (better response time)  RR Scheduling Cons. (--):  The average waiting time is often long.  Context switch overhead is higher 41 (5) Multilevel Queue Scheduling Basic Methodology:  Processes are classified into different groups (/queues)  Ready queue is partitioned into separate queues  Each queue has its own scheduling algorithm.  Scheduling must be done between the queues (usually priority scheduling is used)  The processes are permanently assigned to one queue.  Example: classify the processes to (2) queues: o Q1: Foreground (interactive) processes >> scheduled by RR, (high priority) o Q2: Background (batch) processes >> scheduled by FCFS, (low priority) o Scheduling between the queues >> Non-preemptive priority 42 (5) Multilevel Queue Scheduling(cont..) Example (8): (Q1)  A multilevel queue scheduling algorithm with (5)queues  Scheduling between queues is preemptive (Q2) priority & each queue has a priority over lower queues. (Q3) No process in (Q4) could run unless the (Q4) queues for Q1, Q2, and Q3 were all empty. If an interactive editing process entered the (Q5) ready queue (Q3) while a batch process was running, the batch process would be preempted. 43 (5) Multilevel Queue Scheduling(cont..)  Example(9): Consider a system using (Multilevel Queue Scheduling) algorithm. It classify the processes to (2) groups (/queues): o Q1: interactive processes >> scheduled by RR algorithm & (q=4ms) o Q2: batch processes >> scheduled by FCFS algorithm o Scheduling between the queues >> Non-preemptive priority o Q1 has the highest priority. Draw the Gantt chart for the following set of processes and find the average WT and TAT of each process. Process Process type Arrival time Burst time (ms) P1 Interactive 0 7 P2 batch 2 5 P3 Interactive 10 2 P4 batch 11 4 44  Multilevel Queue Scheduling(cont..) Example(9): Cont. Q1 P1 P1 busy P3 0 4 7 12 14 Q2 P2 busy P4 7 12 14 18 CPU Gantt chart: P1 P2 P3 P4 0 7 12 14 18 WT(P1) =0 ms ; WT(P2) = 5 ms ; WT(P3) = 2 ms ; WT(P4) = 3 ms Average WT= (0 + 5 + 2 +3)/4 = 2.5 ms. TAT  exercise.. 45 (5) Multilevel Queue Scheduling (cont..)  Multilevel Queue Scheduling Pros. (++):  Consider different process prosperities & requirements  Multilevel Queue Scheduling Cons. (--):  Inflexible: a process can’t change it’s queue  If priority scheduling is used between queues, starvation is possible and NO solution for it. 46 (6) Multilevel Feedback Queue Basic Methodology:  Processes are classified into different groups (/queues)  Ready queue is partitioned into separate queues  Each queue has its own scheduling algorithm.  Scheduling must be done between the queues (usually priority scheduling is used)  The processes can be moved between the various queues. The main deference to previous algorithm 47 (6) Multilevel Feedback Queue (cont..) Example:  Consider a system separates processes according to the characteristics of their CPU bursts to (2) groups: o Q1: I/O-bound processes >> scheduled by RR , (high priority) o Q2: CPU-bound processes >> scheduled by FCFS, (low priority) o Scheduling between the queues >> priority scheduling  A process that waits too long in low-priority queue (Q2) ,the system will move it to a higher-priority queue (Q1).  This form of aging prevents starvation. 48 (6) Multilevel Feedback Queue (cont..)  Example(10): consider a multilevel feedback queue scheduler with three queues:  Q0 >> RR , (q=8 ms) ,(high priority)  Q1 >> RR , (q=16 ms) ,(medium priority) Q0 ( high priority)  Q2 >> FCFS ,(low priority)  Initially, all arrived processes assigned to Q0.  Processes in lower priority queue is selected if the higher queues are empty  A new job enters queue Q0 which is served RR. When it gains CPU, job receives 8 milliseconds. If it does not Q1 (medium priority) finish in 8 milliseconds, job is moved to queue Q1.  If Q0 is empty, process at Q1 job is again served RR and receives 16 additional milliseconds. If it still does not complete, it is preempted and moved to queue Q2. This example approximates the performance of SJF Q2 (low priority) algorithm without the need to predict the length of the next CPU bust…(less overhead) 49 Multilevel Feedback Queue (cont..)  Example(11): Consider the following set of processes Where the system have (3) queues: Q1: RR, q=2 ms……….. (highest priority) Process Arrival Burst Q2: RR, q=4 ms time time Q3: Non preemptive-SJF.. (lowest priority) P1 3 82 Scheduling between queues is Non-preemptive P2 4 71 priority Initially, all arrived processes assigned to Q1. P3 8 71 In Q1 & Q2 : If the process doesn’t finish in it’s time P4 12 1 slice, it will be moved to the next lower-priority queue. If a process waiting time ≥ 13 ms , it must be upgraded to the next higher queue Perform the following: a) Draw the CPU Gantt chart & find the Average waiting. b) Find when a process will be demoted. c) Is there any process will be upgraded ? Which one? When? 50  Multilevel Feedback Queue (cont..) Example(11): Cont. Q1 P1 P2 busy P3 P4 3 5 7 11 13 14 Q2 P1 busy P2 P3 P1 P2 7 11 14 18 22 24 25 Q3 P3 25 26 (a) CPU Gantt chart: P1 P2 P1 P3 P4 P2 P3 P1 P2 P3 3 5 7 11 13 14 18 22 24 25 26 51 Multilevel Feedback Queue (cont..)  Example(11): Cont. (a) Average WT= TIME WT(p1) WT(p2) WT(p3) WT(p4) (13+14+11+1)/4 =9.75 ms 5 0 1 -- -- 7 2 1 -- -- (b) The process will be demoted according the following conditions: 11 2 5 3 -- Q1  Q2 : If Process burst 13 4 7 3 1 time >2 14 5 8 4 -- Q2  Q3 : If Process burst 18 9 8 8 -- time >6 22 13 12 8 -- (c) P1 has been upgraded at 24 -- 14 10 -- time(22) from Q3 to Q2 25 -- -- 11 -- 26 -- -- -- -- P2 has been upgraded at time(24) from Q3 to Q2 52 (6) Multilevel Feedback Queue (cont..)  Multilevel Feedback Queue Scheduling Pros. (++):  Consider different process prosperities & requirements  Very flexible >>>it is the most general CPU-scheduling algorithm.  Can be configured to prevent starvation.  Multilevel Feedback Queue Scheduling Cons. (--):  Most complex algorithm 53 Multiple-Processor Scheduling 54 Multiple-Processor Scheduling  CPU scheduling is more complex when multiple CPUs are available.  In multiple-Processor System, load sharing is possible. keep the workload balanced among all processors to fully utilize the benefits of having more than one processor. 55 Multiple-Processor Scheduling (cont..)  Approaches to Multiple-Processor Scheduling Asymmetric multiprocessing Symmetric multiprocessing (ASMP) (SMP) Only master processor executes Each processor can run system code & system code & slave processors user code execute user code Only the master processor has all scheduling decisions, I/O processing, Each processor is self-scheduling, and other system activities Simple Complex 56 Multiple-Processor Scheduling (cont..)  Approaches to Multiple-Processor Scheduling (cont..) Asymmetric multiprocessing Symmetric multiprocessing (ASMP) (SMP) only master processor Each processor has its own private queue accesses the ready queue, reducing of ready processes. the need for data sharing. OR All processors take processes from one common ready queue , So: The scheduler must be programmed carefully. It must ensure that two separate processors do not choose to schedule the same process. It must ensure that processes are not lost from the queue. 57 Thank you End of Chapter 4