Lecture 8:Lecture 8:Scheduling & DeadlockScheduling & DeadlockCSE 120: Principles of Operating SystemsAlex C. SnoerenHW 2 Due NOWCSE 120 – Lecture 8: Scheduling and Deadlock 2SchedulingScheduling The scheduler (aka dispatcher) is the module thatmanipulates the queues, moving jobs to and fro The scheduling algorithm determines which jobs arechosen to run next and what queues they wait on In general, the scheduler runs:◆ When a job switches states (running, waiting, etc.)◆ When an interrupt occurs◆ When a job is created or terminated We’ll discuss scheduling algorithms in two contexts◆ A preemptive scheduler can interrupt a running job◆ A non-preemptive scheduler waits for running job to blockCSE 120 – Lecture 8: Scheduling and Deadlock 3Priority SchedulingPriority Scheduling Priority Scheduling◆ Choose next job based on priority» Airline checkin for first class passengers◆ Can implement SJF, priority = 1/(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 consumptionCSE 120 – Lecture 8: Scheduling and Deadlock 4Combining AlgorithmsCombining Algorithms 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 interactive to CPU-bound behaviorCSE 120 – Lecture 8: Scheduling and Deadlock 5Unix SchedulerUnix Scheduler The canonical Unix scheduler uses a MLFQ◆ 3-4 classes spanning ~170 priority levels» Timesharing: first 60 priorities» System: next 40 priorities» Real-time: next 60 priorities» Interrupt: next 10 (Solaris) Priority scheduling across queues, RR within a queue◆ 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 quantumCSE 120 – Lecture 8: Scheduling and Deadlock 6Motivation of Unix SchedulerMotivation of Unix Scheduler The idea behind the Unix scheduler is to rewardinteractive processes over CPU hogs Interactive processes (shell, editor, etc.) typically runusing short CPU bursts◆ They do not finish quantum before waiting for more input Want to minimize response time◆ Time from keystroke (putting process on ready queue) toexecuting keystroke handler (process running)◆ Don’t want editor to wait until CPU hog finishes quantum This policy delays execution of CPU-bound jobs◆ But that’s okCSE 120 – Lecture 8: Scheduling and Deadlock 7Scheduling SummaryScheduling Summary Scheduler (dispatcher) is the module that gets invokedwhen a context switch needs to happen Scheduling algorithm determines which process runs,where processes are placed on queues Many potential goals of scheduling algorithms◆ Utilization, throughput, wait time, response time, etc. Various algorithms to meet these goals◆ FCFS/FIFO, SJF, Priority, RR Can combine algorithms◆ Multiple-level feedback queues◆ Unix exampleCSE 120 – Lecture 8: Scheduling and Deadlock 8DeadlockDeadlock Processes that acquire multiple resources aredependent on those resources◆ E.g., locks, semaphores, monitors, etc. What if one process tries to allocate a resource that asecond process holds, and vice-versa?◆ Neither can ever make progress!◆ Dining philosphers problem from Homework 2 We call this situation deadlock, and we’ll look at:◆ Definition and conditions necessary for deadlock◆ Representation of deadlock conditions◆ Approaches to dealing with deadlockCSE 120 – Lecture 8: Scheduling and Deadlock 9Deadlock DefinitionDeadlock Definition Deadlock is a problem that can arise:◆ When processes compete for access to limited resources◆ When processes are incorrectly synchronized Definition:◆ Deadlock exists among a set of processes if every process iswaiting for an event that can be caused only by anotherprocess in the set.lockA->Acquire();…lockB->Acquire();lockB->Acquire();…lockA->Acquire();Process 1 Process 2CSE 120 – Lecture 8: Scheduling and Deadlock 10Conditions for DeadlockConditions for DeadlockDeadlock can exist if and only if four conditions hold:1. Mutual exclusion – At least one resource must be heldin a non-sharable mode. (I.e., only one instance)2. Hold and wait – There must be one process holdingone resource and waiting for another resource3. No preemption – Resources cannot be preempted(I.e., critical sections cannot be aborted externally)4. Circular wait – There must exist a set of processes{P1, P2, P3,…,Pn} such that P1 is waiting for a resourceheld by P2, P2 is waiting for P3, … , and Pn for P1CSE 120 – Lecture 8: Scheduling and Deadlock 11Resource Allocation GraphResource Allocation Graph Deadlock can be described using a resource allocationgraph (RAG) The RAG consists of sets of vertices P = {P1, P2, …,Pn} of processes and R = {R1, R2, …, Rm} resources◆ A directed edge from a process to a resource, Pi→Ri, impliesthat Pi has requested Rj◆ A directed edge from a resource to a process, Ri→Pi, impliesthat Rj has been acquired by Pi◆ Each resource has a fixed number of units If the graph has no cycles, deadlock cannot exist If the graph has a cycle, deadlock may existCSE 120 – Lecture 8: Scheduling and Deadlock 12RAG ExampleRAG ExampleA cycle…anddeadlock!Same cycle…but nodeadlock. Why?CSE 120 – Lecture 8: Scheduling and Deadlock 13Dealing With DeadlockDealing With DeadlockThere are four ways to deal with deadlock: Ignore it◆ How lucky do you feel? Prevention◆ Make it impossible for deadlock to happen Avoidance◆ Control allocation of resources Detection and recovery◆ Look for a cycle in dependenciesCSE 120 – Lecture 8: Scheduling and Deadlock 14Deadlock PreventionDeadlock PreventionPrevent at least one condition from happening: Mutual exclusion◆ Make resources sharable
View Full Document