DOC PREVIEW
U of I CS 241 - System Programming CPU Scheduling (2)

This preview shows page 1-2-24-25 out of 25 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 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 25 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 25 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 25 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS241 System Programming CPU Scheduling (2)ContentAdministrativePreemptive vs. Non-preemptiveWhat are the scheduling objectives?Scheduling ObjectivesPerformance CriteriaDifferent Systems, Different FocusesProcess ProfilesProgram Behaviors Considered in SchedulingCPU SchedulerDispatcherSingle Processor Scheduling AlgorithmsFirst Come First Serve (FCFS)(Batch Scheduling Policy)FCFS ExampleProblems with FCFSFCFS PerformanceConvoy EffectsPriority Scheduling(Interactive Scheduling Policy)Set PriorityPriority Scheduling: ExampleRound-robin (Interactive Scheduling Policy)Round-robin: ExampleTime QuantumSummaryCS241 System Programming CPU Scheduling (2)Klara NahrstedtLecture 112/13/20062/12/2006CS 241 - System Programming,Klara Nahrstedt2Contentz Basic Scheduling Algorithm (FCFS)z Round Robinz Priority Schedulingz Summary2/12/2006CS 241 - System Programming,Klara Nahrstedt3AdministrativezMP2 posted today, due February 27zMP1 due today, February 13zRead T: 2.4zQuiz 3 will be on Friday, February 17, 2006zQuiz 3 will include material from Tanenbaum, 3rdedition, section 2.2, 2.3, 2.4 AND LECTURE NOTES (see lecture note files)–lec6-syn1–lec7-syn2–lec8-syn3–lec8-syn4–lec10-sched–lec11-sched2/12/2006CS 241 - System Programming,Klara Nahrstedt4Preemptive vs. Non-preemptivezNon-preemptive scheduling:–The running process keeps the CPU until it voluntarily gives up the CPU zprocess exitszswitches to blocked statez1and 4 only (no 3)z Preemptive scheduling:–The running process can be interrupted and must release the CPU (can be forced to give up CPU)RunningTerminatedReady Blocked1432/12/2006CS 241 - System Programming,Klara Nahrstedt5What are the scheduling objectives?(CPU (horsepower))Process 1Process 2 Process 3I want to ride itWhose turn is it?2/12/2006CS 241 - System Programming,Klara Nahrstedt6Scheduling ObjectiveszFair (nobody cries)z Priority (lady first)z Efficiency (make best use of equipment)z Encourage good behavior (good boy/girl)z Support heavy loads (degrade gracefully)z Adapt to different environments (interactive, real-time, multi-media)2/12/2006CS 241 - System Programming,Klara Nahrstedt7Performance CriteriazFairnesszEfficiency: keep resources as busy as possiblezThroughput: # of processes that completes in unit timezTurnaround Time (also called elapse time)–amount of time to execute a particular process from the time its entered zWaiting Time–amount of time process has been waiting in ready queue zResponse Time–amount of time from when a request was first submitted until first response is produced. –predictability and variance zPolicy Enforcement:–seeing that stated policy is carried out zProportionality: –meet users' expectation zMeeting Deadlines: avoid losing data2/12/2006CS 241 - System Programming,Klara Nahrstedt8Different Systems, Different FocuseszFor all–Fairness, policy enforcement, resource balancezBatch Systems–Max throughput, min turnaround time, max CPU utilization zInteractive Systems–Min Response time, best proportionality zReal-Time Systems–predictability, meeting deadlines2/12/2006CS 241 - System Programming,Klara Nahrstedt9Process ProfileszI/O – Bound –Does too much I/O to keep CPU busyzCPU – Bound–Does too much computation to keep I/O busyzProcess Mix–Scheduling should load balance between I/O bound and CPU-bound processes–Ideal would be to run all equipment at 100% utilization but that would not necessarily be good for response time2/12/2006CS 241 - System Programming,Klara Nahrstedt10Program Behaviors Considered in SchedulingzIs it I/O bound? Example?zIs it CPU bound? Example?zBatch or interactive environment zUrgency zPriority zFrequency of page faults zFrequency of preemption zHow much execution time it has already received zHow much execution time it needs to complete I/O I/Ocompute computeI/O2/12/2006CS 241 - System Programming,Klara Nahrstedt11CPU SchedulerzProc 1: 14 time unitsz Proc2: 8 time unitsz Proc3: 8 time unitsz Dispatcherz Preemptive vs.non-preemptiveCPUDispatcherProc 1Proc 2Proc 3Proc 10Proc 11Proc 12Ready queueblocked queue2/12/2006CS 241 - System Programming,Klara Nahrstedt12DispatcherzGives the control of the CPU to the process, scheduled by the short-term scheduler. z Functions: –switching context–switching to user mode–jumping to the proper location in the user program. zDispatch Latency :time to stop process and start another one. –Pure overhead–Needs to be fast2/12/2006CS 241 - System Programming,Klara Nahrstedt13Single Processor Scheduling AlgorithmszBatch systems–First Come First Serve (FCFS)–Short Job FirstzInteractive Systems–Round Robin–Priority Scheduling–Multi Queue & Multi-level Feedback–Shortest process time–Guaranteed Scheduling–Lottery Scheduling–Fair Sharing Scheduling2/12/2006CS 241 - System Programming,Klara Nahrstedt14First Come First Serve (FCFS)(Batch Scheduling Policy)zProcess that requests the CPU FIRST is allocated the CPU FIRST. zAlso called FIFOzNon-preemptivezUsed in Batch Systems zReal life analogy: Fast food restaurantzImplementation: FIFO queues–A new process enters the tail of the queue–The schedule selects from the head of the queue. zPerformance Metric: Average Waiting Time. zGiven Parameters: –Burst Time (in ms), Arrival Time and Order2/12/2006CS 241 - System Programming,Klara Nahrstedt15FCFS ExampleProcess Duration Order Arrival TimeP1 24 1230P2 3 0P3 4 0The final schedule:P1 (24)024 27P2 (3) P3 (4)P1 waiting time: 0P2 waiting time: 24P3 waiting time: 27The average waiting time: (0+24+27)/3 = 172/12/2006CS 241 - System Programming,Klara Nahrstedt16Problems with FCFSzNon-preemptivez Not optimal AWTz Cannot utilize resources in parallel:–Assume 1 process CPU bounded and many I/O bounded processes –result: Convoy effect, low CPU and I/O Device utilization –Why?2/12/2006CS 241 - System Programming,Klara Nahrstedt17FCFS PerformancezWhat is the impact of convey effect?a)Slows down CPU bound processes?b)Slows down I/O bound processes?c)Low CPU utilization? d)Low I/O device utilization?e)All of the above?2/12/2006CS 241 - System Programming,Klara Nahrstedt18Convoy EffectszConsider n-1 jobs in system that are I/O bound and 1 job that is CPU bound. zI/O bound jobs pass quickly through the ready queue and suspend themselves waiting for I/O. zCPU bound job arrives at head of queue and executes until complete. zI/O bound jobs rejoin ready queue and wait for CPU bound job to complete. zI/O devices idle until CPU bound job


View Full Document

U of I CS 241 - System Programming CPU Scheduling (2)

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 System Programming CPU Scheduling (2)
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 System Programming CPU Scheduling (2) 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 System Programming CPU Scheduling (2) 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?