Deadlock AvoidanceDeadlock AvoidanceProcess TrajectoriesProblemsAvoiding DeadlockAlternate Process TrajectorySafe and Unsafe StatesThe Banker's Algorithm (Dijkstra, 1965)ExampleThe Banker's Algorithm for Multiple ResourcesWhy Isn't This Useful?Example: File Binding TimeDeadlock PreventionPreventing DeadlocksAttacking Mutual ExclusionAttacking Holding and WaitA Variant is UsefulAttacking Circular WaitMainframe ResourcesTwo-Phase LockingWhat's Really Done About Deadlocks?What About Linux?SchedulingSchedulingEnvironmentsProcess BehaviorWhen to Make Scheduling DecisionsPreemptive vs. Nonpreemptive SchedulersCategories of Scheduling AlgorithmsGoalsGoals: Batch SystemsInteractive SystemsReal-Time SystemsBatch SchedulersBatch SchedulersFirst-Come, First-ServedFirst-Come, First-ServedShortest FirstOptimality Requires Simultaneous AvailabilityShortest Remaining Time NextThree-Level SchedulerUser RequirementsDeadlock Avoidance 1 / 38Deadlock Avoidance■ If we can detect deadlocks, can we avoid them?■ Yes, but. . .■ We can avoid deadlocks if certain information is available in advance1 / 38Process TrajectoriesY4Y3Process BProcess APrinterPlotterP QRSTX1 X2 X3 X4Y1Y2A needs the printer from X1to X3; it needs the plotter from X2to X4.B needs the plotter from Y1to Y3; it needs the printer from Y2to Y4.2 / 381Problems■ Warning sign: A and B are asking for resources in a different order■ Green region: both A and B have the printer — impossible■ Yellow region: both have the plotter■ Blue — both have both devices. . .■ The colored regions represent impossible states and cannot be entered3 / 38Avoiding Deadlock■ If the system ever enters the red-bordered state, it will deadlock■ At time t, cannot schedule B■ If we do, system will enter deadlock state■ Must run A until X44 / 382Alternate Process TrajectoryY4Process BProcess APrinterPlotterP QRSTX1 X2 X3 X4Y1Y2Y3If A and B ask for the plotter first, there’s no danger. B will clearly block if it’sscheduled, so A will proceed. The dangerous state was where a process entered aclear box that would deadlock.5 / 38Safe and Unsafe States■ A state is safe if not deadlocked and there is a scheduling order in which allprocesses can complete, even if they all ask for all of their resources at once■ An unsafe state is not deadlocked, but no such scheduling order exists■ It may even work, if a process releases resources at the right time6 / 383The Banker’s Algorithm (Dijkstra, 1965)■ Assume we’re dealing with a single resource — perhaps dollars■ Every customer has a “line of credit” — a maximum possible resourceallocation”■ The banker only has a certain amount of cash on hand■ Not everyone will need all of their credit at once■ Solution: only grant requests if they leave us in a safe state7 / 38ExampleHas MaxA 0 6B 0 5C 0 4D 0 7Free: 10Has MaxA 1 6B 1 5C 2 4D 4 7Free: 2Has MaxA 1 6B 2 5C 2 4D 4 7Free: 1The first state is safe; we can grant the requests sequentially. The second state issafe; we can grant C’s maximum request, let it run to completion, and then have$4 to give to B or D.If, after the second state, we give $1 to B, we enter an unsafe state — there isn’tenough money left to satisfy all possible requests.8 / 384The Banker’s Algorithm for Multiple Resources■ Build matrices C (currently assigned) and R (and still needed), just as weused for deadlock detection■ Build vectors E (existing resources) and A (available), again as before■ To see if a state is safe:1. Find a row R whose unmet needs are ≤ A2. Mark that row; add its resources to A3. Repeat until either all rows are marked, in which case the state is safe, orsome are unmarked , in which case it’s u nsafe■ Run this algorithm any time a resource request is made9 / 38Why Isn’t This Useful?■ Every process must state its resource requirements at startup■ This is rarely possible today■ Processes come and go■ Resources vanish as hardware breaks■ Not really used these days. . .10 / 385Example: File Binding Time■ Old mainframes: all file name binding is done immediately prior to execution.Also makes it easy to move files around■ Classic Unix: file names on command line (but not clearly identifiable as such)or compiled-in to commands. Occasional overrides via environment variables oroptions.■ GUIs: many files selected via menusEarly versus late binding is a major issuse in system design. Both choices herehave their advantages and disadvantages11 / 38Deadlock Prevention 12 / 38Preventing Deadlocks■ Practically speaking, we can’t avoid deadlocks■ Can we prevent them in the real world?■ Let’s go back to the four conditions:1. Mutual exclusion2. Hold and Wait3. No preemption4. Circular wait12 / 386Attacking Mutual Exclusion■ Much less of an issue today — fewer single-user resources■ Many of the existing ones are dedicated to single machines used by singleindividuals, i.e., CD drives■ Printers are generally spooled⇒ No contention; only the printer daemon requests it■ Not a general solution, but useful nevertheless13 / 38Attacking Holding and Wait■ Could require processes to state their requirements up front■ Still done sometimes in the mainframe world■ Of course, if we could do that, we could use the Banker’s Algorithm14 / 387A Variant is Useful■ Before requesting a resource, release all currently-held resources■ Request all new ones at once■ Doesn’t work if some resources must be held15 / 38Attacking Circular Wait■ Number each possible resource:1. Scanner2. Printer3. Tape drive4. . . .■ Resources must be requested in numerical order■ Can’t deadlock — prevents the out-of-order scenario we saw earlier■ Used on old mainframes■ Can combine this with release-and-rerequest16 / 388Mainframe Resources■ Wait until enough tape drives are available■ Wait until memory region is available■ Wait for all disk files to be freeOrder based on typical wait time — disk files freed up quickly, while tape driveswaited for operators to find and mount tape reels17 / 38Two-Phase Locking■ Frequ ently used in d atabases■ Processes need to lock several records then update them all■ Phase 1: try locking each record, one at a time■ On failure, release them all and restart■ When they’re all locked, do the updates and then the release■ Effectively the same as “request everything up front”18 / 389What’s Really Done About Deadlocks?■ In the OS, nothing. . .■