Unformatted text preview:

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

UCSD CSE 120 - Scheduling & Deadlock

Documents in this Course
Threads

Threads

14 pages

Deadlocks

Deadlocks

19 pages

Processes

Processes

14 pages

Paging

Paging

13 pages

Processes

Processes

18 pages

Threads

Threads

29 pages

Security

Security

16 pages

Paging

Paging

13 pages

Processes

Processes

32 pages

Lecture 2

Lecture 2

13 pages

Paging

Paging

8 pages

Threads

Threads

14 pages

Paging

Paging

13 pages

Paging

Paging

26 pages

Paging

Paging

13 pages

Lecture

Lecture

13 pages

Processes

Processes

14 pages

Paging

Paging

13 pages

Security

Security

17 pages

Threads

Threads

15 pages

Processes

Processes

34 pages

Structure

Structure

10 pages

Lecture 3

Lecture 3

13 pages

Lecture 1

Lecture 1

28 pages

Threads

Threads

15 pages

Paging

Paging

30 pages

Load more
Download Scheduling & Deadlock
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Scheduling & Deadlock and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Scheduling & Deadlock 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?