DOC PREVIEW
Princeton COS 318 - CPU Scheduling

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

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

Unformatted text preview:

COS 318: Operating Systems CPU Scheduling (http://www.cs.princeton.edu/courses/cos318/)2 Today’s Topics  CPU scheduling basics  CPU Scheduling algorithmsWhen to Schedule?  Process/thread creation  Process/thread exit  Blocking on I/O or synchronization  I/O interrupt  Clock interrupt (pre-emptive scheduling) 34 Preemptive vs. Non-Preemptive Scheduling  Preemptive scheduling  Running ⇒ ready  Blocked ⇒ ready  Running ⇒ blocked  Terminate  Non-preemptive scheduling  Running ⇒ blocked  Terminate  Batch vs interactive vs real-time Running Blocked Ready Resource free, I/O completion interrupt (move to ready queue) Create Terminate (call scheduler) Yield, Interrupt (call scheduler) Block for resource (call scheduler) Scheduler dispatch ExitedScheduling Criteria  Assumptions  One program per user and one thread per program  Programs are independent  Goals for batch and interactive systems  Provide fairness  Everyone makes some progress; no one starves  Maximize CPU utilization • Not including idle process  Maximize throughput • Operations/second (min overhead, max resource utilization)  Minimize turnaround time • Batch jobs: time to execute (from submission to completion)  Shorten response time • Interactive jobs: time response (e.g. typing on a keyboard)  Proportionality • Meets user’s expectationsScheduling Criteria  Questions:  What are the goals for PCs versus servers?  Average response time vs. throughput  Average response time vs. fairness7 Problem Cases  Completely blind about job types  No CPU and I/O overlap.  Optimization involves favoring jobs of type “A” over “B”  Lots of A’s? B’s starve.  Interactive process trapped behind others  Response time bad for no good reason.  Priorities: A depends on B and A’s priority > B’s  B never runs.Scheduling Algorithms  Simplified view of scheduling:  Save process state (to PCB)  Pick which process to run next  Dispatch process 8First-Come-First-Serve (FCFS) Policy  What does it mean?  Run to completion (old days)  Run until blocked or yields  Example 1  P1 = 24sec, P2 = 3sec, and P3 = 3sec, submitted together  Average response time = (24 + 27 + 30) / 3 = 27  Example 2  Same jobs but come in different order: P2, P3 and P1  Average response time = (3 + 6 + 30) / 3 = 13 P1 P2 P3 P2 P3 P1 (Gantt Graph)STCF and SRTCF  Shortest Time to Completion First  Non-preemptive  Shortest Remaining Time to Completion First  Preemptive version  Example  P1 = 6sec, P2 = 8sec, P3 = 7sec, P4 = 3sec  All arrive at the same time  Can you do better than SRTCF in terms of average response time?  Issues with this approach? P1 P2 P3 P4Round Robin  Similar to FCFS, but add a time slice for timer interrupt  FCFS for preemptive scheduling  Real systems also have I/O interrupts in the mix  How do you choose time slice? Current processFCFS vs. Round Robin  Example  10 jobs and each takes 100 seconds  FCFS (non-preemptive scheduling)  job 1: 100s, job2: 200s, ... , job10: 1000s  Round Robin (preemptive scheduling)  time slice 1sec and no overhead  job1: 991s, job2: 992s, ... , job10: 1000s  Comparisons  Round robin is much worse (turnaround time) for jobs about the same length  Round robin is better for short jobsResource Utilization Example  A, B, and C run forever (in this order)  A and B each uses 100% CPU forever  C is a CPU plus I/O job (1ms CPU + 10ms disk I/O)  Time slice 100ms  A (100ms CPU), B (100ms CPU), C (1ms CPU + 10ms I/O), …  Time slice 1ms  A (1ms CPU), B (1ms CPU), C (1ms CPU), A (1ms CPU), B (1ms CPU), C(10ms I/O) || A, B, …, A, B  What do we learn from this example?14 Virtual Round Robin  Aux queue is FIFO  I/O bound processes go to aux queue (instead of ready queue) to get scheduled  Aux queue has preference over ready queue CPU Admit Timeout Dispatch I/O wait I/O wait I/O wait Aux queue I/O completion15 Priority Scheduling  Obvious  Not all processes are equal, so rank them  The method  Assign each process a priority  Run the process with highest priority in the ready queue first  Adjust priority dynamically (I/O wait raises the priority, reduce priority as process runs)  Why adjusting priorities dynamically  T1 at priority 4, T2 at priority 1 and T2 holds lock L  Scenario • T1 tries to acquire L, fails, blocks. • T3 enters system at priority 3. • T2 never gets to run!Multiple Queues  Jobs start at highest priority queue  If timeout expires, drop one level  If timeout doesn’t expires, stay or pushup one level  What does this method do? Priority 4 3 2 1 Time slices 1 2 4 8Lottery Scheduling  Motivations  SRTCF does well with average response time, but unfair  Lottery method  Give each job a number of tickets  Randomly pick a winning tickets  To approximate SRTCF, give short jobs more tickets  To avoid starvation, give each job at least one ticket  Cooperative processes can exchange tickets  Question  How do you compare this method with priority scheduling?18 Multiprocessor and Cluster Multiprocessor architecture  Cache coherence  Single OS Cluster or multicomputer  Distributed memory  An OS in each box … CPU L1 $ L2 $ CPU L1 $ L2 $ … Memory Network19 Multiprocessor/Cluster Scheduling  Design issue  Process/thread to processor assignment  Gang scheduling (co-scheduling)  Threads of the same process will run together  Processes of the same application run together  Dedicated processor assignment  Threads will be running on specific processors to completion  Is this a good idea?20 Real-Time Scheduling  Two types of real-time  Hard deadline • Must meet, otherwise can cause fatal error  Soft Deadline • Meet most of the time, but not mandatory  Admission control  Take a real-time process only if the system can


View Full Document

Princeton COS 318 - CPU Scheduling

Documents in this Course
Overview

Overview

25 pages

Deadlocks

Deadlocks

25 pages

lectute 2

lectute 2

28 pages

Lecturel

Lecturel

24 pages

Real mode

Real mode

49 pages

Lecture 2

Lecture 2

54 pages

lecture 5

lecture 5

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