6 3ULQFLSOHV RI 2SHUDWLQJ 6 VWHPV DOO Lecture 8 Scheduling and Deadlock Geoffrey M Voelker 6FKHGXOLQJ 2YHUYLHZ In discussing process management and synchronization we talked about context switching among processes threads on the ready queue But we have glossed over the details of exactly which thread is chosen from the ready queue Making this decision is called scheduling We ll look at The goals of scheduling Starvation Various well known scheduling algorithms Standard Unix scheduling algorithm October 19 2000 CSE 120 Lecture 8 Scheduling and Deadlock 2 1 0XOWLSURJUDPPLQJ In a multiprogramming system we try to increase CPU utilization and job throughput by overlapping I O and CPU activities We have covered the mechanisms Context switching how and when it happens Process queues and process states Now we ll look at the policies Doing this requires a combination of mechanisms and policy Which process thread to run for how long etc We ll refer to schedulable entities as jobs standard usage could be processes threads people etc October 19 2000 CSE 120 Lecture 8 Scheduling and Deadlock 3 6FKHGXOLQJ RDOV Scheduling works at two levels in an operating system To determine the multiprogramming level the number of jobs loaded into primary memory Moving jobs to from memory is often called swapping To decide what job to run next to guarantee good service Good service could be one of many different criteria These decisions are known as long term and shortterm scheduling decisions respectively Long term scheduling happens relatively infrequently Short term scheduling happens relatively frequently Significant overhead in swapping a process out to disk Want to minimize the overhead of scheduling October 19 2000 Fast context switches fast queue manipulation CSE 120 Lecture 8 Scheduling and Deadlock 4 2 6FKHGXOLQJ The scheduler dispatcher is the module that manipulates the queues moving jobs to and fro The scheduling algorithm determines which jobs are chosen to run next and what queues they wait on In general the scheduler runs When a job switches from running to waiting When an interrupt occurs When a job is created or terminated We ll discuss scheduling algorithms in two contexts In preemptive systems the scheduler can interrupt a running job involuntary context switch In non preemptive systems the scheduler waits for a running job to explicitly block voluntary context switch October 19 2000 CSE 120 Lecture 8 Scheduling and Deadlock 5 6FKHGXOLQJ RDOV Scheduling algorithms can have many different goals Batch systems CPU utilization Job throughput jobs unit time Turnaround time Tfinish Tstart Waiting time Avg Twait avg time spent on wait queues Response time Avg Tready avg time spent on ready queue Strive for job throughput turnaround time supercomputers Interactive systems Strive to minimize response time for interactive jobs PC October 19 2000 CSE 120 Lecture 8 Scheduling and Deadlock 6 3 6WDUYDWLRQ Starvation is a scheduling non goal Starvation is a situation where a process is prevented from making progress because some other process has the resource it requires Starvation usually a side effect of the sched algorithm Resource could be the CPU or a lock recall readers writers A high priority process always prevents a low priority process from running on the CPU One thread always beats another when acquiring a lock Starvation can be a side effect of synchronization Constant supply of readers always blocks out writers October 19 2000 CSE 120 Lecture 8 Scheduling and Deadlock 7 6 2 First come first served FCFS first in first out FIFO Jobs are scheduled in order of arrival to ready Q Real world scheduling of people in lines e g supermarket Typically non preemptive no context switching at market Jobs treated equally no starvation Problem Average waiting time can be large if small jobs wait behind long ones high turnaround time You have a basket but you re stuck behind someone with a cart October 19 2000 CSE 120 Lecture 8 Scheduling and Deadlock 8 4 6KRUWHVW RE LUVW 6 Shortest Job First SJF Choose the job with the smallest expected CPU burst Person with smallest number of items to buy Provably optimal minimum average waiting time Problem Impossible to know size of CPU burst How can you make a reasonable guess Can potentially starve Like choosing person in line without looking at number of items Flavors Can be either preemptive or non preemptive Preemptive SJF is called shortest remaining time first SRTF October 19 2000 CSE 120 Lecture 8 Scheduling and Deadlock 9 3ULRULW 6FKHGXOLQJ Priority Scheduling Choose next job based on priority Airline checkin for first class passengers Problem Can implement SJF priority expected CPU burst Also can be either preemptive or non preemptive This is what you re implementing in Nachos in Project 1 Starvation low priority jobs can wait indefinitely Solution Age processes Increase priority as a function of waiting time Decrease priority as a function of CPU consumption October 19 2000 CSE 120 Lecture 8 Scheduling and Deadlock 10 5 5RXQG 5RELQ 55 Round Robin Excellent for timesharing Ready queue is treated as a circular queue FIFO Each job is given a time slice called a quantum A job executes for the duration of the quantum or until it blocks or is interrupted No starvation Can be preemptive or non preemptive Problem Context switches are frequent and need to be very fast October 19 2000 CSE 120 Lecture 8 Scheduling and Deadlock 11 RPELQLQJ OJRULWKPV Scheduling algorithms can be combined Have multiple queues Use a different algorithm for each queue Move processes among queues Example Multiple level feedback queues MLFQ Multiple queues representing different job types Queues have priorities jobs on same queue scheduled RR Jobs can move among queues based upon execution history Interactive CPU bound batch system etc Feedback Switch from interactive to CPU bound behavior October 19 2000 CSE 120 Lecture 8 Scheduling and Deadlock 12 6 8QL 6FKHGXOHU The canonical Unix scheduler uses a MLFQ 3 4 classes spanning 170 priority levels Priority scheduling across queues RR within a queue Timesharing first 60 priorities System next 40 priorities Real time next 60 priorities Interrupt next 10 Solaris The process with the highest priority always runs Processes with the same priority are scheduled RR Processes dynamically change priority Increases over time if process blocks before end of quantum Decreases over time if process uses entire quantum October 19 2000 CSE 120 Lecture 8
View Full Document
Unlocking...