Operating system chapter 6

Operating system chapter 6

اسلاید 1: 1Concurrency: Deadlock and StarvationChapter 6

اسلاید 2: 2DeadlockPermanent blocking of a set of processes that either compete for system resources or communicate with each otherNo efficient solutionInvolve conflicting needs for resources by two or more processes

اسلاید 3: 3

اسلاید 4: 4

اسلاید 5: 5

اسلاید 6: 6Reusable ResourcesUsed by only one process at a time and not depleted by that useProcesses obtain resources that they later release for reuse by other processesProcessors, I/O channels, main and secondary memory, devices, and data structures such as files, databases, and semaphoresDeadlock occurs if each process holds one resource and requests the other

اسلاید 7: 7Example of Deadlock

اسلاید 8: 8Another Example of DeadlockSpace is available for allocation of 200Kbytes, and the following sequence of events occurDeadlock occurs if both processes progress to their second requestP1. . .. . .Request 80 Kbytes;Request 60 Kbytes;P2. . .. . .Request 70 Kbytes;Request 80 Kbytes;

اسلاید 9: 9Consumable ResourcesCreated (produced) and destroyed (consumed)Interrupts, signals, messages, and information in I/O buffersDeadlock may occur if a Receive message is blockingMay take a rare combination of events to cause deadlock

اسلاید 10: 10Example of DeadlockDeadlock occurs if receive is blockingP1. . .. . .Receive(P2);Send(P2, M1);P2. . .. . .Receive(P1);Send(P1, M2);

اسلاید 11: 11Resource Allocation GraphsDirected graph that depicts a state of the system of resources and processes

اسلاید 12: 12Resource Allocation Graphs

اسلاید 13: 13Conditions for DeadlockMutual exclusionOnly one process may use a resource at a timeHold-and-waitA process may hold allocated resources while awaiting assignment of othersNo preemptionNo resource can be forcibly removed form a process holding it

اسلاید 14: 14Conditions for DeadlockCircular waitA closed chain of processes exists, such that each process holds at least one resource needed by the next process in the chain

اسلاید 15: 15

اسلاید 16: 16Possibility of DeadlockMutual ExclusionNo preemptionHold and wait

اسلاید 17: 17Existence of DeadlockMutual ExclusionNo preemptionHold and waitCircular wait

اسلاید 18: 18Deadlock PreventionMutual ExclusionMust be supported by the operating systemHold and WaitRequire a process request all of its required resources at one time

اسلاید 19: 19Deadlock PreventionNo PreemptionProcess must release resource and request againOperating system may preempt a process to require it releases its resourcesCircular WaitDefine a linear ordering of resource types

اسلاید 20: 20Deadlock AvoidanceA decision is made dynamically whether the current resource allocation request will, if granted, potentially lead to a deadlockRequires knowledge of future process request

اسلاید 21: 21Two Approaches to Deadlock AvoidanceDo not start a process if its demands might lead to deadlockDo not grant an incremental resource request to a process if this allocation might lead to deadlock

اسلاید 22: 22Resource Allocation DenialReferred to as the banker’s algorithmState of the system is the current allocation of resources to processSafe state is where there is at least one sequence that does not result in deadlockUnsafe state is a state that is not safe

اسلاید 23: 23Determination of a Safe State Initial State

اسلاید 24: 24Determination of a Safe State P2 Runs to Completion

اسلاید 25: 25Determination of a Safe State P1 Runs to Completion

اسلاید 26: 26Determination of a Safe State P3 Runs to Completion

اسلاید 27: 27Determination of an Unsafe State

اسلاید 28: 28Determination of an Unsafe State

اسلاید 29: 29Deadlock Avoidance Logic

اسلاید 30: 30Deadlock Avoidance Logic

اسلاید 31: 31Deadlock AvoidanceMaximum resource requirement must be stated in advanceProcesses under consideration must be independent; no synchronization requirementsThere must be a fixed number of resources to allocateNo process may exit while holding resources

اسلاید 32: 32Deadlock Detection

اسلاید 33: 33Strategies once Deadlock DetectedAbort all deadlocked processesBack up each deadlocked process to some previously defined checkpoint, and restart all processOriginal deadlock may occurSuccessively abort deadlocked processes until deadlock no longer existsSuccessively preempt resources until deadlock no longer exists

اسلاید 34: 34Selection Criteria Deadlocked ProcessesLeast amount of processor time consumed so farLeast number of lines of output produced so farMost estimated time remainingLeast total resources allocated so farLowest priority

اسلاید 35: 35Strengths and Weaknesses of the Strategies

اسلاید 36: 36Dining Philosophers Problem

اسلاید 37: 37Dining Philosophers Problem

اسلاید 38: 38Dining Philosophers Problem

اسلاید 39: 39Dining Philosophers Problem

اسلاید 40: 40Dining Philosophers Problem

اسلاید 41: 41UNIX Concurrency MechanismsPipesMessagesShared memorySemaphoresSignals

اسلاید 42: 42

اسلاید 43: 43Linux Kernel Concurrency MechanismsIncludes all the mechanisms found in UNIXAtomic operations execute without interruption and without interference

اسلاید 44: 44Linux Atomic Operations

اسلاید 45: 45Linux Atomic Operations

اسلاید 46: 46Linux Kernel Concurrency MechanismsSpinlocksUsed for protecting a critical section

اسلاید 47: 47

اسلاید 48: 48Linux Kernel Concurrency Mechanisms

اسلاید 49: 49Solaris Thread Synchronization PrimitivesMutual exclusion (mutex) locksSemaphoresMultiple readers, single writer (readers/writer) locksCondition variables

اسلاید 50: 50

اسلاید 51: 51