CPU Scheduling Notes PDF

System Software and Computing Concepts CT123-3-1Ver: VDE CPU Scheduling  Learning Outcomes At the end of this section, YOU should be able to: Define Processes and Threads Draw and explain; the process state diagram, the process scheduli...

System Software and Computing Concepts CT123-3-1Ver: VDE CPU Scheduling  Learning Outcomes At the end of this section, YOU should be able to: Define Processes and Threads Draw and explain; the process state diagram, the process scheduling diagram and PCB State the Aims of CPU Scheduling Perform calculations using the various scheduling Algorithms available CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 2  Topics we will cover Process and Thread Concepts Process States Process Scheduling CPU scheduling Preemptive Scheduling Algorithms Non-preemptive Scheduling Algorithms Calculation using Preemptive and Non-preemptive Scheduling Algorithms CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 3  Process What is a process? – it is a program in execution which progresses in a sequential manner. – it is a unit of work with a unique process identification. – requires resources like memory, CPU time and files to complete its task. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 4  Process What is a process? – resources are allocated when a process is created or while in execution – the operating system creates and deletes user and system processes – a process is active while a program is passive – the operating system keeps track of processes using a process table CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 5  Process State Diagram new new terminated terminated admitted exi t Interrupt / time out ready ready running running scheduler I/O or event dispatcher I/O or event wait completion blocked blocked CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 6  Process States As a program executes, it changes states New – A process has just been created – Reasons for process creation new batch job interactive logon – Upon creation, a New process becomes Ready Ready – the process is waiting to be assigned to a processor CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 7  Process States (cont.) Ready - Running – instructions are being executed – a process is using the CPU – the number of running processes will depend on the number of processors the computer has A running process can possibly become Blocked, Ready or Terminated A Running process becomes Blocked when:- – the process itself cannot execute because it is waiting for an I/O operation to complete – waiting for some external event to happen CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 8  Process States (cont.) From the Blocked state a process moves to the Ready state when the event which the process was waiting for occurs. A Running process moves to the Ready state when:- – a process has reached its maximum allowable time for uninterrupted execution. – a process needs a resource that is not immediately available. – a process needs an I/O operation before continuation. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 9  Process States (cont.) From the Running state a process moves into the Terminated state when:- – the process has completed – the process has been aborted Reasons for process termination:- – normal completion – invalid instruction – memory unavailable Upon termination, control is then returned to the operating system. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 10  Quick Review Questions 1. For each of the following transitions between process states, indicate whether the transition is possible or not possible? ready → running ready → new blocked → ready 2. On a system with n number of CPU’s what is the minimum number of processes that can be in the ready, running and blocked state? CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 11  Process Control Block (PCB) Each process is represented in the operating system as a process control block. A Process Control Block (PCB):- – keeps track of each process. – contains information associated with a specific process. – serves as a repository of any information that may vary from process to process. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 12  Process Control Block Diagram Pointer to parent process Pointer area to child process Process state Program counter Register save area Memory limits Priority information Accounting information Pointer to files and otherCPU Scheduling CT123-3-1-System Software and Computing Concepts SLIDE 13  Process Control Block Diagram Process state – the process state; ready, running, blocked, terminated. Program counter – indicates the location for the next instruction. CPU scheduling information – process priority, pointers to scheduling queues. Accounting information – statistics on CPU time, job and process numbers. I/O status – list of I/O devices which are allocated to processes. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 14  Process Scheduling As processes enter the system, they are put on the job queue. A new process is put on the ready queue. The process waits until it is selected for execution (or dispatched) and given CPU resources. Once the CPU is allocated and the process is running:- – the process could issue an I/O request and be placed on a device queue. – the process could create a new sub-process. – the process could be forcibly removed. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 15  Process Scheduling Diagram readyqueue ready queue CPU CPU I/O I/O I/OQueue I/O Queue I/ORequest I/O Request timeslice time slice expired expired child child childexecute child execute forkaachild fork child terminates terminates interrupt interrupt waitfor wait foran an occurs occurs interrupt interrupt CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 16  Concurrent Processes Concurrent processes can be independent or cooperating processes. Independent processes are processes that do not need to interact with other processes. Cooperating processes are processes that work with each other, can affect or be affected by another process. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 17  Concurrent Processes (cont.) Why should an operating system allow for cooperating processes? – information sharing and to allow access to resources using the PCB. – increase computation speed. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 18  Thread A mini lightweight process that can execute independently of other parts of the process Two types of threads:- – user processes – system processes Creation of a new process (child) from the older one (parent) is called spawning or forking. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 19  Quick Review Questions 1. What is a process control block? 2. Draw and briefly explain the process scheduling diagram. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 20  Follow Up Assignment 1. What are the differences and similarities between a process and a thread? 2. Draw and explain the process state diagram. 3. What does a process table store? CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 21  CPU Scheduling A CPU scheduler is tasked with choosing which process to run first from the ready queue. A scheduling algorithm is used to choose the next process. Scheduling is a fundamental function of an operating system. Scheduling is done to ensure that the CPU is not idle. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 22  Aims of Scheduling fairness – to make sure all processes get a fair share of the CPU time. – avoid starvation. efficiency – maximise CPU utilisation and keep the CPU busy close to 100% of the time. response time – consistent response time. – minimise response time. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 23  Aims of Scheduling turnaround time – minimise time between submission and job completion. – minimise output time. throughput – maximise number of job completed within a given time period. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 24  Preemptive Scheduling Allows for running processes to be temporarily suspended. Processes releases CPU upon receiving a command. Preemptive scheduling algorithms:- – round robin – multilevel queue – multilevel feedback queue CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 25  Non-preemptive Scheduling Processes release the CPU only after completion. Processes releases CPU voluntarily. Non-preemptive scheduling algorithms:- – first come first serve (FCFS) or first in first out (FIFO) – shortest job first (SJF) – priority CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 26  Quick Review Questions 1. Why is CPU scheduling important? 2. What is the difference between preemptive and non-preemptive algorithms? 3. Give 2 examples each for a preemptive and non-preemptive algorithms. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 27  Calculation Keywords CPU utilisation Throughput Turnaround time – Average turnaround time Waiting time – Average waiting time Response time Burst time CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 28  Round Robin Oldest, simplest, fairest and most widely used. Designed for time-sharing systems. Time quantum/time slice is defined for each process. The ready queue is treated as a circular queue. To implement round robin, the ready queue is kept as a first in first out queue. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 29  Round-robin Step 1:- Draw a Gantt Chart to represent timing for all processes P1 P2 P3 P4 P5 P1 P5 P1 P5 P1 P1 0 2 3 5 6 8 10 12 14 15 17 19 Step 2:- Calculate waiting times and average waiting time Time Slice = 2 TW(P1) = (0+6+2+1)=9 Milliseconds TW(P2) = 2 Burst Time Process (Milliseconds) TW(P3) = 3 TW(P4) = 5 P1 10 TW(P5) = (6+2+2)=10 P2 1 TW(average)=(9+2+3+5+10)/5 P3 2 P4 1 =5.8 Milliseconds CT123-3-1-System Software and Computing Concepts P5 CPU Scheduling 5 SLIDE 30  Round-robin Step 3:- Calculate turnaround times and average turnaround time TT = Tw+TB P1 P2 P3 P4 P5 P1 P5 P1 P5 P1 P1 0 2 3 5 6 8 10 12 14 15 17 19 TT(P1)=(9+10)=19 Time Slice = 2 Milliseconds TT(P2)=(2+1) = 3 Burst Time TT(P3)=(3+2) = 5 Process (Milliseconds ) TT(P4)=(5+1) = 6 P1 10 TT(P5)=(10+5)=15 P2 1 Average turnaround time is (19+3+5+6+15)/5 = P3 2 (48/5)=9.6 Milliseconds P4 1 P5 5 CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 31  Round Robin Average waiting time is usually long. Performance depends on the size of the time quantum (10 – 100 milliseconds). Process switch requires time, while the time quantum clock is already running. Time quantum which is set too short would result in too many process switches and this reduces CPU efficiency. Time quantum which is too long would cause poor response to short interactive request. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 32  Multilevel Queue Classifies processes into different groups. The ready queue is separated into several separate queues. Each process is permanently assigned to one queue based on process priority, size or process type. Each queue would have its own scheduling algorithm. Each queue has priority over lower level queues. Time slices can be allocated to queues. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 33  Multilevel Queue highest priority System Processes Interactive Processes Interactive Editing Processes Batch Processes Student Processes lowest priority CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 34  Multilevel Feedback Queue Processes are allowed to move between queues. Processes are separated by CPU burst time. If a process utilises too much CPU time it will be moved to a lower priority queue. If a process is starved of CPU time it will be moved to a higher level priority queue. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 35  Multilevel Feedback Queue quantum=8 quantum=16 FCFS CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 36  Quick Review Questions 1. How does the round robin algorithm work? 2. What is the difference between the multilevel queue and multilevel feedback queue? CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 37  Follow Up Assignment 1. List down some features of the round robin scheduling algorithm 2. What is turnaround time? 3. Why are priorities used? CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 38  FIFO / FCFS The simplest CPU scheduling algorithm. The process that requests the CPU first is allocated the CPU first. The implementation of the FIFO policy is easily managed with a FIFO queue. Average waiting time for FIFO is quite long. Once the CPU has been allocated the process, the process keeps the CPU until termination or by requesting for I/O. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 39  FIFO / FCFS Step 1:- Draw Gantt Chart to represent timing for all processes P1 P2 P3 P4 P5 0 10 11 1314 19 Step 2:- Calculate waiting times and average waiting time Burst Time TW(P1) = 0 Process (Millisecond TW(P2) = 10 s) TW(P3) = 11 P1 10 TW(P4) = 13 TW(P5) = 14 P2 1 TW(average) = (0+10+11+13+14)/5 P3 2 = 9.6 Milliseconds P4 1 P5 5 CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 40  FIFO / FCFS Step 3:- Calculate turnaround times and average turnaround time TT = Tw+TB P1 P2 P3 P4 P5 0 10 11 1314 19 TT(P1) = (0+10) = 10 TT(P2) = (10+1) = 11 Burst Time Process TT(P3) = (11+2) = 13 (Milliseconds) TT(P4) = (13+1) = 14 P1 10 P2 1 TT(P5) = (14+5) = 19 Average turnaround time is P3 2 (10+11+13+14+19)/5 = (67/5) P4 1 =13.4 Milliseconds P5 5 CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 41  Shortest Job First (SJF) Scheduling is done by examining the length of the next CPU burst of a process. If the CPU is free, the next process with the smallest next CPU burst is assigned. If two processes have the same CPU burst, FIFO is used to break the tie. The difficulty with SJF is to determine the length of the next process. The advantage of this algorithm is that it is optimal by providing the minimum average waiting time. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 42  Shortest Job First (SJF) Step 1:- Draw Gantt Chart to represent the timing for all processes P2 P4 P3 P5 P1 0 1 2 4 9 19 Step 2:- Calculate waiting times and average waiting time TW(P1) = 9 Burst Time TW(P2) = 0 Process (Milliseconds) TW(P3) = 2 TW(P4) = 1 P1 10 TW(P5) = 4 P2 1 TW(average) = (9+0+2+1+4)/5 P3 2 = 3.2 Milliseconds P4 1 P5 5 CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 43  Shortest Job First (SJF) Step 3: Calculate turnaround times and average turnaround time TT = Tw+TB P2 P4 P3 P5 P1 0 1 2 4 9 19 TT(P1) = (9+10) = 19 Burst Time Process TT(P2) = (0+1) = 1 (Milliseconds) TT(P3) = (2+2) = 4 P1 10 TT(P4) = (1+1) = 2 P2 1 TT(P5) = (4+5) = 9 P3 2 Average turnaround time is P4 1 (19+1+4+2+9)/5 = (35/5) P5 5 =7 Milliseconds CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 44  Priority Priority is associated with each process. The CPU is allocated the job with highest priority. Equal priority processes are scheduled using FIFO. Priority can be high or low; however 0 can mean high priority. Can be preemptive or non-preemptive. A problem with priority algorithm is starvation. Aging is a technique to gradually increase a processes priority. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 45  Priority Step 1:- Draw Gantt Chart to represent timing for all processes P4 P1 P3 P5 P2 0 1 11 13 18 19 Step 2:- Calculate waiting time and average waiting time TW(P1) = 1 TW(P2) = 18 Burst Time TW(P3) = 11 Process (ms) Priority TW(P4) = 0 P1 10 3 TW(P5) = 13 P2 1 1 TW(average) = (1+18+11+0+13)/5 P3 2 3 = 8.6 Milliseconds P4 1 4 P5 5 2 CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 46  Priority Step 3:- Calculate turnaround times and average turnaround time TT = Tw+TB P4 P1 P3 P5 P2 0 1 11 13 18 19 TT(P1) = (1+10) = 11 TT(P2) = (18+1) = 19 Burst Time Process Priority TT(P3) = (11+2) = 13 (ms) TT(P4) = (0+1) = 1 P1 10 3 P2 1 1 TT(P5) = (13+5) = 18 P3 2 3 Average turn around time is P4 1 4 (11+19+13+1+18)/5 = (62/5) P5 5 2 =12.4 Milliseconds CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 47  Quick Review Questions 1. Name three preemptive scheduling algorithms. 2. Which of the three is the easiest to implement? CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 48  Follow Up Assignment 1. FIFO on its own is a scheduling algorithm, however FIFO is also used in other scheduling algorithms. Name these algorithms. 2. Which non-preemptive algorithm is optimal and why? CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 49  Summary of Main Teaching Points A process is a unit of work in execution which requires resources. The state of a processes changes as it executes. A process control block represents a process in the operating system. Processes can execute concurrently or independently from each other. A thread is a basic unit of CPU utilisation. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 50  Summary of Main Teaching Points CPU scheduling is used to select a process from the ready queue and allocate this process CPU time. Scheduling algorithms can be pre-emptive or non-pre- emptive. Scheduling algorithms aim to achieve fairness, efficiency, maximising throughput and minimising turnaround time. Round robin, multilevel queues and multilevel feedback queues are examples of pre-emptive algorithms. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 51  Summary of Main Teaching Points Non-preemptive algorithms are FIFO, SJF and priority. SJF algorithm has a shorter average waiting time. Using priority scheduling may result in some processes experiencing starvation; aging is a method used to overcome this. CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 52  END Q&A CT123-3-1-System Software and Computing Concepts CPU Scheduling SLIDE 53