1&6(3ULQFLSOHVRI2SHUDWLQJ6\VWHPV)DOOLecture 8: Scheduling and DeadlockGeoffrey M. VoelkerOctober 19, 2000 CSE 120 -- Lecture 8 – Scheduling and Deadlock 26FKHGXOLQJ2YHUYLHZ● 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 algorithm2October 19, 2000 CSE 120 -- Lecture 8 – Scheduling and Deadlock 30XOWLSURJUDPPLQJ● In a multiprogramming system, we try to increase CPU utilization and job throughput by overlapping I/O and CPU activities◆ Doing this requires a combination of mechanisms and policy● We have covered the mechanisms◆ Context switching, how and when it happens◆ Process queues and process states● Now we’ll look at the policies◆ 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 46FKHGXOLQJ*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 short-term scheduling decisions, respectively◆ Long-term scheduling happens relatively infrequently» Significant overhead in swapping a process out to disk◆ Short-term scheduling happens relatively frequently» Want to minimize the overhead of scheduling■ Fast context switches, fast queue manipulation3October 19, 2000 CSE 120 -- Lecture 8 – Scheduling and Deadlock 56FKHGXOLQJ● 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 66FKHGXOLQJ*RDOV● Scheduling algorithms can have many different goals:◆ 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)● Batch systems◆ Strive for job throughput, turnaround time (supercomputers)● Interactive systems◆ Strive to minimize response time for interactive jobs (PC)4October 19, 2000 CSE 120 -- Lecture 8 – Scheduling and Deadlock 76WDUYDWLRQStarvation 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◆ Resource could be the CPU, or a lock (recall readers/writers)● Starvation usually a side effect of the sched. algorithm◆ 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 writersOctober 19, 2000 CSE 120 -- Lecture 8 – Scheduling and Deadlock 8)&)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 cart5October 19, 2000 CSE 120 -- Lecture 8 – Scheduling and Deadlock 96KRUWHVW-RE)LUVW6-)● 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» Like choosing person in line without looking at number of items ◆ How can you make a reasonable guess?◆ Can potentially starve● 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 103ULRULW\6FKHGXOLQJ● Priority Scheduling◆ Choose next job based on priority» Airline checkin for first class passengers◆ 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● Problem◆ 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 consumption6October 19, 2000 CSE 120 -- Lecture 8 – Scheduling and Deadlock 115RXQG5RELQ55● 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 fastOctober 19, 2000 CSE 120 -- Lecture 8 – Scheduling and Deadlock 12&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» Interactive, CPU-bound, batch, system, etc.◆ Queues have priorities, jobs on same queue scheduled RR◆ Jobs can move among queues based upon execution history» Feedback: Switch from
View Full Document
Unlocking...