CS241 Operating Systems CPU Scheduling (3)ContentAdministrative NotesShortest Job First (SJF)Non-preemptive SJF: ExampleComparing to FCFSSJF is not always optimalPreemptive SJFPreemptive SJF: Same ExampleA Problem with SJFInteractive Scheduling AlgorithmsMulti-Queue SchedulingMulti-Queue Scheduling: ExampleReal-Time SchedulingPriority Inversion and InheritanceUser-level Thread SchedulingKernel-level Thread SchedulingIntroduction to Signals (Ch8 pp255-283)Introduction to Signals (2)POSIX Required Signals (1)POSIX Required Signals (2)Generating SignalsProgramming a signal (1)Programming a signal (2) (A process sends a signal to itself)SummaryCS241 Operating SystemsCPU Scheduling (3)Klara NahrstedtLecture 122/15/200601/14/19 CS 241 - System Programming, Klara Nahrstedt2ContentScheduling algorithms–Batch systemsShortest job first–Interactive systemsMulti QueueReal-Time SchedulingThread Scheduling Introduction to SignalsSummary01/14/19 CS 241 - System Programming, Klara Nahrstedt3Administrative NotesMP2 on scheduling is runningQuiz 3 will be on Friday, February 17, 2006Quiz 3 will include material from Tanenbaum, 3rd edition, 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-sched01/14/19 CS 241 - System Programming, Klara Nahrstedt4Shortest Job First (SJF)Schedule the job with the shortest elapse time firstScheduling in Batch Systems Two types:–Non-preemptive–PreemptiveRequirement: the elapse time needs to be known in advanceOptimal if all jobs are available simultaneously (provable) –Gives the best possible AWT (average waiting time)01/14/19 CS 241 - System Programming, Klara Nahrstedt5Non-preemptive SJF: ExampleProcess Duration Order Arrival TimeP1 6 1 0P2 8 2 0P3 7 3 0P4 3 4 003P4 (3)P1 (6)9P3 (7)16P4 waiting time: 0P1 waiting time: 3P3 waiting time: 9P2 waiting time: 16The total time is: 24The average waiting time (AWT): (0+3+9+16)/4 = 7P2 (8)2401/14/19 CS 241 - System Programming, Klara Nahrstedt6Comparing to FCFSProcess Duration Order Arrival TimeP1 6 1 0P2 8 2 0P3 7 3 0P4 3 4 006P4 (3)P1 (6)14P3 (7)21P1 waiting time: 0P2 waiting time: 6P3 waiting time: 14P4 waiting time: 21The total time is the same.The average waiting time (AWT): (0+6+14+21)/4 = 10.25(comparing to 7)P2 (8)2401/14/19 CS 241 - System Programming, Klara Nahrstedt7SJF is not always optimalIs SJF optimal if all the jobs are not available simultaneously?Process Duration Order Arrival TimeP1 10 1 0P2 2 2 20 10P1 (10)P1 waiting time: 0P2 waiting time: 8The average waiting time (AWT): (0+8)/2 = 4P2 (2)2 (p2 arrives) 1201/14/19 CS 241 - System Programming, Klara Nahrstedt8Preemptive SJFAlso called Shortest Remaining Time First–Schedule the job with the shortest remaining time required to completeRequirement: the elapse time needs to be known in advance01/14/19 CS 241 - System Programming, Klara Nahrstedt9Preemptive SJF: Same ExampleProcess Duration Order Arrival TimeP1 10 1 0P2 2 2 2P1 waiting time: 4-2 =2P2 waiting time: 0The average waiting time (AWT): (0+2)/2 = 1No CPU waste!!!0122 P1 (8)P2 (2)4P1 (2)01/14/19 CS 241 - System Programming, Klara Nahrstedt10A Problem with SJFStarvation–In some condition, a job is waiting for ever–Example: SJFProcess A with elapse time of 1 hour arrives at time 0But ever 1 minute, a short process with elapse time of 2 minutes arriveResult of SJF: A never gets to run01/14/19 CS 241 - System Programming, Klara Nahrstedt11Interactive Scheduling AlgorithmsUsually preemptive–Time is sliced into quantum (time intervals)–Scheduling decision is also made at the beginning of each quantumPerformance Criteria–Min Response time–best proportionality Representative algorithms:–Priority-based–Round-robin–Multi Queue & Multi-level Feedback–Shortest process time–Guaranteed Scheduling–Lottery Scheduling–Fair Sharing Scheduling01/14/19 CS 241 - System Programming, Klara Nahrstedt12Multi-Queue SchedulingHybrid between priority and round-robinProcesses assigned to one queue permanently Scheduling between queues –Fixed Priorities –% CPU spent on queue Example –System processes –Interactive programs –Background Processes –Student Processes Address the starvation and infinite blocking problems01/14/19 CS 241 - System Programming, Klara Nahrstedt13Multi-Queue Scheduling: Example20%50%30%01/14/19 CS 241 - System Programming, Klara Nahrstedt14Real-Time SchedulingHard-Real Time v Soft-Real TimePeriodic vs AperiodicA set of m periodic event streams is schedulable if the condition ∑Ci/Pi ≤ 1 is satisfied, where i=1,…,m; Ci is the processing CPU time of an event stream i; Pi is the period at which the event i occursIf the set of event streams are schedulable then the real-time scheduling policy Earliest Deadline First worksImplementation of the scheduling policy: Earliest Deadline process is mapped to the highest priority01/14/19 CS 241 - System Programming, Klara Nahrstedt15Priority Inversion and InheritancePriority inversion –When a higher priority process needs to read or modify kernel data that are currently being accessed by a lower priority process. –The higher priority process must wait!– But the lower priority cannot proceed quickly due to scheduling.Solution: priority inheritance (Result of Prof. Sha, Rajkumar and Lehotzky Work)–When a lower-priority process accesses a resource, it inherits the priority level of the waiting high-priority process until it is done with the resource in question. And then its priority reverses to its natural value.01/14/19 CS 241 - System Programming, Klara Nahrstedt16User-level Thread SchedulingPossible Scheduling 50-msec process quantumrun 5 msec/CPU burst01/14/19 CS 241 - System Programming, Klara Nahrstedt17Kernel-level Thread SchedulingPossible scheduling 50-msec process quantumthreads run 5 msec/CPU burst01/14/19 CS 241 - System Programming, Klara Nahrstedt18Introduction to Signals (Ch8 pp255-283)Signal is a software notification to a process of an event.–Examples of such events Process waits on a semaphoreProcess waits to be scheduledA signal is generated when the event that causes the signal occurs. A signal is delivered when the process takes action based on the signal. The lifetime of a signal is the interval between its generation and delivery. A signal that has been
View Full Document
Unlocking...