Chapter 5 - Process Synchronization producer/consumer, bounded buffer, concurrent execution (5.1: 203 - 206) The critical section problem (5.2: 206) The critical section solution (mutual exclusion, progress, bounded waiting) race conditions, preemptive kernel vs nonpreemptive kernel Peterson's Solution (5.3: 207 209) atomic instructions,TestAndSet, Swap (5.4) semaphores, counting, binary, mutex, synchronization (5.5-5.6) implementation - busy waiting, spinlock, or blocking deadlock and starvation (5.6.3) classic problems - bounded buffer, dining philosophers, sleeping barber (5.7) Chapter 7 - Deadlock Why is deadlock a problem? Four simultaneous conditions for deadlock to occur (7.2) 1. Mutual exclusion 2. No preemption 3. Hold and wait 4. Circular Wait System Resource Allocation Graph (7.2.2) Handling Deadlock (7.3): Deadlock prevention, avoidance, detection and recovery, or ignoring deadlock Deadlock Prevention (7.4) - prevent deadlock by removing one of the four essential components. 1. mutual exclusion - useful but cannot be done for all resources 2. hold and wait - (i) request only when it has none or (ii) access all resources before execution may begin 3. no preemption - (i) implicitly release all resources when a resource requested is not available or (ii) take resources from processes that have them allocated and that are also waiting 4. circular wait - (i) Impose a strict order on resources and force each process to request resources in that order. Define a function F(Ri) which returns this order Deadlock Avoidance (7.5) - Use the resource allocation graph to avoid deadlock at all times. (safe state, safe sequence) Deadlock avoidance with single instance resources (7.5.2) Add a claim edge Pi -> Rj to symbolize that Pi may request Rj in the future. A process which begins execution with no resource will add claim edges for every resource it may acquire in the future. With this addition, we avoid deadlock by allowing Rj to be allocated to Pi only if this results in a graph with no cycles. Deadlock Detection and Recovery (7.6) For single instances - uses a resource-allocation graph and find cycles For multiple instances, (when a process requests resources, run a modified safety algorithm. This modified safety algorithm will use Request[n][m] for the currently requested resources of each process in place of Need[n][m]. If at Step 4, Finish[i] == false then deadlock has been detected. In particular, the process Pi where Finish[i] == false is a deadlocked one. *Recovery from deadlock (7.7) - process termination or resource preemption *process termination: abort all deadlocked process or abort one process at a time until deadlock is eliminated *resource preemption: (i) select a victim based on number of resources held by a deadlocked process, amount of time the process has executed, and the number of times the process was already chosen as a victim, (ii) rollback the process to a safe state, (iii) ensure starvation does not occur