Handling DeadlockJonathan GeislerMarch 2, 2007Jonathan Geisler Handling DeadlockConditions necessary for deadlock1Mutual exclusion2Hold resources & wait3No preemption of resources4Circular waitJonathan Geisler Handling DeadlockOptions for dealing with deadlock1Steer clearAvoidancePrevention2Detect3OstrichDo nothingMost frequentJonathan Geisler Handling DeadlockPreventionThis technique works by making one of the necessary conditionsimpossible to reach.1Can we remove Mutual Exclusion?2Hold & WaitAsk for resources at process startupAsk for resources when none are held3No PreemptionRelease on waitTake resources from waiting process4Circular WaitAcquire resources in specified orderFreeBSD provides checker (witness) to help debug thisconditionJonathan Geisler Handling DeadlockPreventionThis technique works by making one of the necessary conditionsimpossible to reach.1Can we remove Mutual Exclusion?2Hold & WaitAsk for resources at process startupAsk for resources when none are held3No PreemptionRelease on waitTake resources from waiting process4Circular WaitAcquire resources in specified orderFreeBSD provides checker (witness) to help debug thisconditionJonathan Geisler Handling DeadlockPreventionThis technique works by making one of the necessary conditionsimpossible to reach.1Can we remove Mutual Exclusion?2Hold & WaitAsk for resources at process startupAsk for resources when none are held3No PreemptionRelease on waitTake resources from waiting process4Circular WaitAcquire resources in specified orderFreeBSD provides checker (witness) to help debug thisconditionJonathan Geisler Handling DeadlockPreventionThis technique works by making one of the necessary conditionsimpossible to reach.1Can we remove Mutual Exclusion?2Hold & WaitAsk for resources at process startupAsk for resources when none are held3No PreemptionRelease on waitTake resources from waiting process4Circular WaitAcquire resources in specified orderFreeBSD provides checker (witness) to help debug thisconditionJonathan Geisler Handling DeadlockPreventionThis technique works by making one of the necessary conditionsimpossible to reach.1Can we remove Mutual Exclusion?2Hold & WaitAsk for resources at process startupAsk for resources when none are held3No PreemptionRelease on waitTake resources from waiting process4Circular WaitAcquire resources in specified orderFreeBSD provides checker (witness) to help debug thisconditionJonathan Geisler Handling DeadlockPreventionThis technique works by making one of the necessary conditionsimpossible to reach.1Can we remove Mutual Exclusion?2Hold & WaitAsk for resources at process startupAsk for resources when none are held3No PreemptionRelease on waitTake resources from waiting process4Circular WaitAcquire resources in specified orderFreeBSD provides checker (witness) to help debug thisconditionJonathan Geisler Handling DeadlockPreventionThis technique works by making one of the necessary conditionsimpossible to reach.1Can we remove Mutual Exclusion?2Hold & WaitAsk for resources at process startupAsk for resources when none are held3No PreemptionRelease on waitTake resources from waiting process4Circular WaitAcquire resources in specified orderFreeBSD provides checker (witness) to help debug thisconditionJonathan Geisler Handling DeadlockPreventionThis technique works by making one of the necessary conditionsimpossible to reach.1Can we remove Mutual Exclusion?2Hold & WaitAsk for resources at process startupAsk for resources when none are held3No PreemptionRelease on waitTake resources from waiting process4Circular WaitAcquire resources in specified orderFreeBSD provides checker (witness) to help debug thisconditionJonathan Geisler Handling DeadlockPreventionThis technique works by making one of the necessary conditionsimpossible to reach.1Can we remove Mutual Exclusion?2Hold & WaitAsk for resources at process startupAsk for resources when none are held3No PreemptionRelease on waitTake resources from waiting process4Circular WaitAcquire resources in specified orderFreeBSD provides checker (witness) to help debug thisconditionJonathan Geisler Handling DeadlockPreventionThis technique works by making one of the necessary conditionsimpossible to reach.1Can we remove Mutual Exclusion?2Hold & WaitAsk for resources at process startupAsk for resources when none are held3No PreemptionRelease on waitTake resources from waiting process4Circular WaitAcquire resources in specified orderFreeBSD provides checker (witness) to help debug thisconditionJonathan Geisler Handling DeadlockAvoidanceThis technique works by ensuring the processes always remain in a“safe state.” It may be possible that the four necessary conditionsare held, but they will never cause a problem because we haveensured that we will never reach a deadlocked state.1Resource allocation graphAdd claim edgesCycle detection whenever a process requests a change fromclaim to use2Bankers algorithmPretend allocation is successfulFind if still in a safe stateJonathan Geisler Handling DeadlockDetectionPeriodically check for cycles in wait-for graphModified bankers algorithmWhen should we check?Jonathan Geisler Handling DeadlockRecovery1Process te rminationKill one (which one?)Kill all2Resource preemptionWhich resources?Which process?How do we recover?Can we prevent starvation?Jonathan Geisler Handling