DOC PREVIEW
UCSD CSE 120 - CPU Scheduling

This preview shows page 1-2-20-21 out of 21 pages.

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

Unformatted text preview:

1Lecture 3CPU SchedulingOctober 2, 2003Prof. Joe PasqualeDepartment of Computer Science and EngineeringUniversity of California, San Diego© 2003 by Joseph PasqualeCSE 120: Principles of Operating Systems2Before We Begin …Read Chapter 6 (CPU Scheduling)Programming Assignment 1• Will be available by midnight Sunday• Due in two weeks: Sunday October 19 (midnight)Midterm• Tentative date: week of October 203The CPU Scheduling ProblemWe have multiple processes/threads, but only one CPUHow much time does each process/thread get on CPU?Possibilities• Keep it till done• Each uses it a bit and passes it on• Each gets proportional to what they payWhich is the best policy?4There is No Single Best PolicyDepends on the goals of the systemDifferent for• your personal computer• large time-shared computer• computer controlling a nuclear power plantMight even have multiple (conflicting) goals5Classifying SchedulersPreemptive vs. non-preemptiveReal-time: non vs. soft vs. hardInteractive vs. non-interactive (batch)Mixture6Scheduling: An ExampleProcess Arrival Time Service Time1 0 52 0 33 0 1What order minimizes average turnaround time?Turnaround time: time between arrival and departure• arrive, wait for CPU (waiting time)• use CPU (service time), depart7Longest First vs. Shortest FirstLongest FirstShortest FirstP1P2P30 1 2 3 4 5 6 7 8 9P1P2P30 1 2 3 4 5 6 7 8 98Shortest First Is Provably Optimal• Given n processes with service times S1, S2, S3, … , Sn• Average Turnaround Time (ATT)= [S1 + (S1 + S2) + (S1 + S2 + S3) + … + (S1 + … + Sn)] / n= [(n * S1) + ((n-1) * S2) + ((n-2) * S3) + … + Sn] / n• S1 has maximum weight (n), minimize it• S2 has next-highest weight (n-1), minimize it after S1• In general: order by shortest to longest9Consider Different Arrival TimesProcess Arrival Time Service Time1 0 52 1 33 3 1P1P2P30 1 2 3 4 5 6 7 8 9waiting executing10First-Come First-ServedAllocate CPU in the order that processes arriveProcess Departure Time Turnaround Time1 5 52 8 73 9 6• Average Turnaround Time = (5 + 7 + 6)/3 = 6.0• Simple, non-preemptive, poor for short processesP1P2P30 1 2 3 4 5 6 7 8 911Round RobinTime-slice CPU: give each processes a quantum in turnProcess Departure Time Turnaround Time1 9 92 7 63 4 1• Average Turnaround Time = (9 + 6 + 1)/3 = 5.3• Simple, preemptive, more overhead than FCFSP1P2P30 1 2 3 4 5 6 7 8 912Shortest Process NextSelect process with shortest execution timeProcess Departure Time Turnaround Time1 5 52 9 83 6 3• Average Turnaround Time = (5 + 8 + 3)/3 = 5.3• Optimal for non-preemptive, must know exec timesP1P2P30 1 2 3 4 5 6 7 8 913Shortest Remaining TimeSelect process with shortest remaining timeProcess Departure Time Turnaround Time1 9 92 5 43 4 1• Average Turnaround Time = (9 + 4 + 1)/3 = 4.7• Optimal, must know execution timesP1P2P30 1 2 3 4 5 6 7 8 914Multi-Level Feedback QueuesMultiple ready queues 0, 1, …, nAlways select process in lowest-numbered queueRun selected process for 2iquantums (for queue i)If process doesn’t block, place innext higher queue (except last)…2021222n15Example using Feedback QueuesSelect process in lowest-numbered queue• preemptive: if a new process arrives, currentprocess goes back to queue it came from• Average Turnaround Time = (9 + 5 + 1)/3 = 5.0• Favors shorter processes over longer, dynamicP1P2P30 1 2 3 4 5 6 7 8 916Priority SchedulingSelect process with highest priorityExample: P1 = medium, P2 = high, P3 = low• Allows scheduling based on arbitrary criteria• External, e.g., based on who’s willing to pay most• Internal, e.g., past CPU usage (dynamic)P1P2P30 1 2 3 4 5 6 7 8 917Fair Share (Proportional Share)Processes get predetermined fraction of CPU time• Example: P1 gets 25%, P2 gets 50%, P3 gets 25%Compute ratios of fraction of time used• at time 2, P2/P1 = 100/50 = 2/1: fair shareP1P2P30 1 2 3 4 5 6 7 8 9100% 50%100%33%100% 67%25% 40%50%33% 43% 50% 56%18Computing Fraction of TimeCompute fraction Fn of CPU time used up to time nFn = a L + (1 - a) Fn-1• L: did process run during last interval? 1=yes, 0=no• a = number between 0 and 1• indicates importance of recent CPU usage relative to past• large a: give more weight to recent usage, forget quickly• small a: give more weight to past usage, forget slowly19Examples: Fn = a L + (1 - a) Fn-1a = 1 means ignore the past• Fn = La = 0.5, recent usage and past equally important• Fn = 0.5 L + 0.5 Fn-1• this is an exponential average (typically a < 0.2)a = 1/n, simple average over all intervals• Fn = (1/n) L + (1 - 1/n) Fn-1• Fn = (L + F1 + F2 + F3 + … + Fn-1)/n20Fair Share using Simple Averagea = 1/n : Fn = (L + F1 + F2 + F3 + … + Fn-1)/nExample: P1 gets 25%, P2 gets 50%, P3 gets 25%Note: n is time intervals since process startedP1P2P30 1 2 3 4 5 6 7 8 9100% 50%100%33%100% 67%25% 40%50%33% 43% 50% 56%21Fair Share using Exponential Averagea = 0.5 : Fn = 0.5 L + 0.5 Fn-1Example: P1 gets 25%, P2 gets 50%, P3 gets 25%P1P2P30 1 2 3 4 5 6 7 8 950% 25%50%13%75% 38%6% 53%19%27% 63% 82%


View Full Document

UCSD CSE 120 - CPU Scheduling

Documents in this Course
Threads

Threads

14 pages

Deadlocks

Deadlocks

19 pages

Processes

Processes

14 pages

Paging

Paging

13 pages

Processes

Processes

18 pages

Threads

Threads

29 pages

Security

Security

16 pages

Paging

Paging

13 pages

Processes

Processes

32 pages

Lecture 2

Lecture 2

13 pages

Paging

Paging

8 pages

Threads

Threads

14 pages

Paging

Paging

13 pages

Paging

Paging

26 pages

Paging

Paging

13 pages

Lecture

Lecture

13 pages

Processes

Processes

14 pages

Paging

Paging

13 pages

Security

Security

17 pages

Threads

Threads

15 pages

Processes

Processes

34 pages

Structure

Structure

10 pages

Lecture 3

Lecture 3

13 pages

Lecture 1

Lecture 1

28 pages

Threads

Threads

15 pages

Paging

Paging

30 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?