Class Note for CMPSCI 377 at UMass(43)
Class Note for CMPSCI 377 at UMass(43)
Popular in Course
Popular in Department
This 2 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 16 views.
Reviews for Class Note for CMPSCI 377 at UMass(43)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CMPSCI 377 Operating Systems Fall 2005 Lecture 6 October 4 Lecturer Emery Berger Scribe Dennis Gave Ivan Ordzmez Today 0 Scheduling 61 Scheduling 611 Last Time 0 There is no perfect scheduling algorithm 0 We would like to minimize response time maximize throughput and optimize fairness o FIFO FCFS is a basic rstin rstout scheduler that works just like a queue rst job in runs till completion then next job etc 612 Round Robin RR 0 RR works by picking the rst item on the ready queue running for a quantum moving item to back of queue then repeating 7 A varient of this is used in most systems 0 This algorithm is totally dependent on the quantum length 7 Large quantum leads to a larger response time 96 As quantum goes toward in nity RR looks more like FCFS 7 Small quantum leads to a decresed throughput As quantum goes toward 0 context switch overhead dominates 613 Shortest Job First SJF 0 Great algorithm if the amount of time a job requires is known 0 The job with the shortest completion time is run rst 0 Wait times are as small as possible minimizing the starvation of other jobs 0 Advantages 7 Minimizes completion time 7 Optimal with respect to wait time minimal average 61 62 Lecture 6 October 4 7 Works for both pre emptive and nonpre emptive schedulers Preemptive SJF SRTF Shortest Remaining Time Left 7 10 bound jobs get priority over CPU bound jobs 96 IO bound jobs theoretically have a lower completion time if you think about before and after 10 as seperate jobs 0 Disadvantages 7 Impossible to predict CPU usage time a job has left in general 7 Long running CPU bound jobs can starve 614 Multi Level Feedback Queues 0 Uses past job behavior as predictor for future behavior 7 If the job stopped on 10 once then it will most likely stop on 10 again 7 If the job ran until quantum completion then it will most likely run until quantum completion again 0 The scheduler will favor jobs which use less CPU time 7 Jobs using 10 will get higher priority than jobs using CPU 7 Scheduler is adaptive because a change in job behavior leads to a change in scheduling decisions 0 Structure 1 Multiple priority queues where 10 has highest priority 7 10 jobs priority 1 7 mixture heavily IO priority 2 7 mixture heavily CPU priority 3 7 CPU jobspriority 4 2 Run highest priority queue rst priority 1 7 While in queue7 use round robin 3 Change the quantum length for each priority level priority 1 gets quantum 1 unit7 priority 4 gets quantum 4 units 4 Move jobs from queue to queue based on their behavior 7 If quantum time expires then CPU bound so move job to lower priority queue 7 If quantum time does not expire then 10 bound so move job to higher priority queue 615 Lottery Scheduling o Nonhack7 ellegant way of solving some of the issues associated with schedulers 0 Structure 1 Every job gets a lottery ticket high priority jobs could get multiple tickets7 but each job gets at least one 7 The algorithm degrades gracefully as load gets higher 2 At each quantum7 pick a random winner and run its job for one quantum repeat 0 Example on slides 38 44 httpwwwcsumassedu emerycmpsci377cmpsci377 06ppt
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'