CS241 System Programming CPU SchedulingContentAdministrativeSchedulingWhen to schedule?Scheduling QueuesQueuing Diagram for ProcessesCPU SchedulerCPU Scheduler ExampleSlide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Queueing TheoryProblemRandom EventsQueuing TheorySlide 28Analysis of Queueing BehaviorUseful Facts From Queuing TheorySlide 31Analysis of Single Server QueueExampleSlide 34Slide 35Slide 36Slide 37Slide 38SummaryCS241 System ProgrammingCPU SchedulingKlara NahrstedtLecture 102/10/200601/14/19 CS 241 - System Programming,Klara Nahrstedt2ContentWhy Scheduling?Scheduling LevelsBasic Scheduling Algorithm (FCFS)Summary01/14/19 CS 241 - System Programming,Klara Nahrstedt3AdministrativeMP1 due February 13Read: T: 2.4 (Scheduling)01/14/19 CS 241 - System Programming,Klara Nahrstedt4SchedulingDeciding which process/thread should occupy the resource (CPU, disk, etc)(CPU (horsepower))Process 1Process 2 Process 3I want to ride itWhose turn is it?01/14/19 CS 241 - System Programming,Klara Nahrstedt5When to schedule?A new process startsThe running process exitsThe running process is blocked I/O interrupt (some processes will be ready)Clock interrupt (every 10 milliseconds)01/14/19 CS 241 - System Programming,Klara Nahrstedt6Scheduling QueuesProcesses in ready state enter READY QUEUE–This queue is generally stored as a linked list–Ready-queue header contains pointers to the first and last PCBs in the list–Each PCB has a pointer field that points to the next process in he ready queueOther Queues–I/O Queue01/14/19 CS 241 - System Programming,Klara Nahrstedt7Queuing Diagram for ProcessesReady QueueReady QueueI/O request inI/O request inDevice QueueDevice QueueTime SliceTime SliceExpiredExpiredFork a ChildFork a ChildWait for an Wait for an InterruptInterruptInterrupt Interrupt OccursOccursCreate Create Child Child CPUCPUI/OI/OUpdateUpdateAccountingAccountingCreate JobCreate Job01/14/19 CS 241 - System Programming,Klara Nahrstedt8CPU SchedulerCPU scheduler selects one of the processes from the ready queue and allocates CPU to one of them;Ready queue:= FIFO queue, tree queue, or unordered linked list, or priority queue;Elements in the ready queue are PCBs (Process Control Block) of processes01/14/19 CS 241 - System Programming,Klara Nahrstedt9CPU Scheduler ExampleProcess 1 burst computes for 14 time units Process 2 burst computes for 8 time units Process 3 burst computes for 8 time units01/14/19 CS 241 - System Programming,Klara Nahrstedt10Queuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPU01/14/19 CS 241 - System Programming,Klara Nahrstedt11Queuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPU01/14/19 CS 241 - System Programming,Klara Nahrstedt12Queuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPU01/14/19 CS 241 - System Programming,Klara Nahrstedt13Queuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPU01/14/19 CS 241 - System Programming,Klara Nahrstedt14Queuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPU01/14/19 CS 241 - System Programming,Klara Nahrstedt15Queuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPU01/14/19 CS 241 - System Programming,Klara Nahrstedt16Queuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPU01/14/19 CS 241 - System Programming,Klara Nahrstedt17Queuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPU01/14/19 CS 241 - System Programming,Klara Nahrstedt18Queuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPU01/14/19 CS 241 - System Programming,Klara Nahrstedt19Queuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPU01/14/19 CS 241 - System Programming,Klara Nahrstedt20Queuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPU01/14/19 CS 241 - System Programming,Klara Nahrstedt21Queuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPU01/14/19 CS 241 - System Programming,Klara Nahrstedt22Queuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPU01/14/19 CS 241 - System Programming,Klara Nahrstedt23Queuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPU01/14/19 CS 241 - System Programming,Klara Nahrstedt24Queueing TheoryModelPoisson Distribution and Random Arrival rates01/14/19 CS 241 - System Programming,Klara Nahrstedt25Problem7 Jobs arrive on average every second8 Jobs are processed by system on average every second1) How long does it take for a job to be serviced?2) How many jobs are waiting in queue to be serviced?01/14/19 CS 241 - System Programming,Klara Nahrstedt26Random EventsPoisson DistributionEach event independent of other eventsMean event rate, SD is same as meanExponential distribution01/14/19 CS 241 - System Programming,Klara Nahrstedt27Queuing Theory ARRIVAL RATE ARRIVAL RATE SERVICE RATESERVICE RATEInput QueueInput QueueServerServer01/14/19 CS 241 - System Programming,Klara Nahrstedt28Queueing TheorySteady statePoisson arrival with constant arrival rate (customers per unit time) each arrival is independent. P( t ) = 1- e–t01/14/19 CS 241 - System Programming,Klara Nahrstedt29Analysis of Queueing BehaviorProbability n customers arrive in time interval t is: e–t t n/ n!Assume random service times (also Poisson): constant service rate (customers per unit time)01/14/19 CS 241 - System Programming,Klara Nahrstedt30Useful Facts From Queuing TheoryWq= mean time a customer
View Full Document