Operating Systems Design & Construction
Operating Systems Design & Construction CMPSC 473
Popular in Course
Popular in ComputerScienence
verified elite notetaker
This 0 page Class Notes was uploaded by Isabel Eichmann on Sunday November 1, 2015. The Class Notes belongs to CMPSC 473 at Pennsylvania State University taught by Staff in Fall. Since its upload, it has received 19 views. For similar materials see /class/233061/cmpsc-473-pennsylvania-state-university in ComputerScienence at Pennsylvania State University.
Reviews for Operating Systems Design & Construction
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: 11/01/15
4 Operating Systems CMPSC 473 CPU Scheduling February 14 2008 Lecture 9 y Instructor Trent Jaeger Last Class CPU Scheduling Today CPU Scheduling Algorithms and Systems Scheduling Algorithms First come First serve FCFS Non preemptive Does not account for waiting time or much else Convoy problem Shortestjob First May be preemptive Optimal for minimizing waiting time Giow Lots more And What do real systems use Priority Scheduling Each process is given a certain priority value Always schedule the process with the highest priority Durations Priority P1 10 3 P2 1 1 P3 2 4 P4 1 5 P5 5 2 Gan r r Chart for Priority Scheduling Priorities 39 Note that FCFS and SJF are specialized versions of Priority Scheduling ie there is a way of assigning priorities to the processes so that Priority Scheduling would result in FCFSSJF Wmz WWId excl72pm of 9036 129720729 fmcz z om be Round Robin RR Each process gets a small unit of CPU time lime g dIZ M Usually 10 100 milliseconds After this time has elapsed the process is preempted and added to the end of the ready queue Approach If there are n processes in the ready queue and the time quantum is g Then each process gets 172 of the CPU time In chunks of at most q time units at once No process waits more than 72 1q time units An example of Round Robin 523 Job length 5 P1 0 24 P2 0 P3 0 Time Quantum 4 s P mmmw 15 18 22 26 30 34 11 RR Time Quantum Round robin is Virtually sharing the CPU between the processes giving each process the illusion that it is running in isolation at 1 n th the CPU speed Smaller the time quantum the more realistic the illusion note that when time quantum is of the order of job size it degenerates to FCFS But what is the drawback when time quantum gets smaller RR Time Quantum 39 For the considered example if time quantum size drops to 2s from 4s the number of context switches increases to 39 But context switches are not free Saving restoring registers Switching address spaces Indirect costs cache pollution Scheduling Desirables SJF Minimize waiting time Requires estimate of CPU bursts Round robin Share CPU Via time quanta If burst turns out to be too long Priorities Some processes are more important Priorities enable composition of importance factors No single best approach now What Round Robin with Priority 39 Have a ready queue for each priority level 39 Always service the non null queue at the highest priority level 39 Within each queue you perform round robin scheduling between those processes Round Robin with Priority I Priori39l39y Levels What is the problem With xed priorities processes lower in the priority level can get awed 0qu In general you employ a mechanism to age the priority of processes Multilevel Feedback Queue A process can move between the various queues aging can be implemented this way Multilevel feedback queue scheduler de ned by the following parameters number of queues scheduling algorithms for each queue method used to determine when to upgrade a process method used to determine when to demote a process method used to determine which queue a process will enter when that process needs service Example of Multilevel Feedback Queue Three queues Q0 RR with time quantum 8 milliseconds Q1 RR time quantum 16 milliseconds Q2 FCFS Scheduling A new job enters queue Q0 which is served FCFS When it gains CPU job receives 8 milliseconds If it does not finish in 8 milliseconds job is moved to queue Q1 At Q1 job is again served FCFS and receives 16 additional milliseconds If it still does not complete it is preempted and moved to queue Q2 Multilevel Feedback Queues quantum 16 gt FCFS g Scheduling in Systems Solaris 2 Scheduling class lobal scheduling s eciiic scheduler run priority order priorities classes queue highesi first real time kernel 0 ihreatis oi real time LWPs 0 SYS em kernel 0 service threads 0 interactive amp kernel time sharing 0 threads oi interactive amp iimesharing O lowest Iasi Solaris Dispatch Table time return time quantum from priority quantum expired sleep 0 200 0 5O 5 200 0 5O 10 160 O 51 15 160 5 51 20 120 10 52 25 120 15 52 30 80 20 53 35 80 25 54 4O 4O 30 55 45 4O 35 56 5O 40 4O 58 55 4O 45 58 59 20 49 59 LinuX Scheduling Two algorithms time sharing and real time Time sharing still abstracted Two queues mine and expired In active until you use your entire time slice quantum then expired Once in expired Wait for all others to nish fairness Priority recalculation based on waiting vs running time From 0 10 milliseconds Add waiting time to value subtract running time Adjust the static priority Real time Soft real time Posix1b compliant two classes FCFS and RR Highest priority process always runs rst The Relationship Between Priorities and Time Slice length numeric relative time priority priority quantum 0 highest 200 ms realtime tasks 99 100 39 other tasks lowest 10 ms List of Tasks Indexed According to Priorities active expired array array priority task lists priority task lists 0 0 0 0 0 0 0 1 0 0 0 1 O 140 O 140 0 0 Summary CPU Scheduling Algorithms Combination of algorithms Multi level Feedback Queues Scheduling Systems Solaris Linux 39 Next time Review
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'