DOC PREVIEW
U of I CS 241 - CPU Scheduling

This preview shows page 1-2-3-18-19-37-38-39 out of 39 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 Nahrstedt2ContentWhy Scheduling?Scheduling LevelsBasic Scheduling Algorithm (FCFS)Summary01/14/19 CS 241 - System Programming,Klara Nahrstedt3AdministrativeMP1 due February 13Read: T: 2.4 (Scheduling)01/14/19 CS 241 - System Programming,Klara Nahrstedt4SchedulingDeciding 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 startsThe running process exitsThe 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 QueuesProcesses 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 queueOther 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 SchedulerCPU 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 ExampleProcess 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 TheoryModelPoisson Distribution and Random Arrival rates01/14/19 CS 241 - System Programming,Klara Nahrstedt25Problem7 Jobs arrive on average every second8 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 EventsPoisson DistributionEach event independent of other eventsMean event rate, SD is same as meanExponential distribution01/14/19 CS 241 - System Programming,Klara Nahrstedt27Queuing Theory ARRIVAL RATE ARRIVAL RATE SERVICE RATESERVICE RATEInput QueueInput QueueServerServer01/14/19 CS 241 - System Programming,Klara Nahrstedt28Queueing TheorySteady statePoisson 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 BehaviorProbability 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 TheoryWq= mean time a customer


View Full Document

U of I CS 241 - CPU Scheduling

Documents in this Course
Process

Process

28 pages

Files

Files

37 pages

File I/O

File I/O

52 pages

C Basics

C Basics

69 pages

Memory

Memory

23 pages

Threads

Threads

14 pages

Lecture

Lecture

55 pages

C Basics

C Basics

24 pages

Signals

Signals

27 pages

Memory

Memory

45 pages

Threads

Threads

47 pages

Threads

Threads

28 pages

LECTURE

LECTURE

45 pages

Threads

Threads

30 pages

Threads

Threads

55 pages

Files

Files

37 pages

SIGNALS

SIGNALS

22 pages

Files

Files

37 pages

Threads

Threads

14 pages

Threads

Threads

13 pages

Load more
Download CPU Scheduling
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CPU Scheduling and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CPU Scheduling 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?