Chapter 6 - Concurrency: Deadlock and starvation. This chapter examines two problems that plague all efforts to support concurrent processing: deadlock and starvation. We begin with a discussion of the underlying principles of deadlock and the related problem of starvation. Then we examine the three common approaches to dealing with deadlock: prevention, detection, and avoidance. | Chapter 6 Concurrency: Deadlock and Starvation Operating Systems: Internals and Design Principles, 6/E William Stallings Patricia Roy Manatee Community College, Venice, FL ©2008, Prentice Hall 1 Deadlock Permanent blocking of a set of processes that either compete for system resources or communicate with each other No efficient solution Involve conflicting needs for resources by two or more processes 2 Deadlock 3 Deadlock 4 Deadlock 5 Reusable Resources Used by only one process at a time and not depleted by that use Processes obtain resources that they later release for reuse by other processes 6 Reusable Resources Processors, I/O channels, main and secondary memory, devices, and data structures such as files, databases, and semaphores Deadlock occurs if each process holds one resource and requests the other 7 Reusable Resources 8 Reusable Resources Space is available for allocation of 200Kbytes, and the following sequence of events occur Deadlock occurs if both processes progress to | Chapter 6 Concurrency: Deadlock and Starvation Operating Systems: Internals and Design Principles, 6/E William Stallings Patricia Roy Manatee Community College, Venice, FL ©2008, Prentice Hall 1 Deadlock Permanent blocking of a set of processes that either compete for system resources or communicate with each other No efficient solution Involve conflicting needs for resources by two or more processes 2 Deadlock 3 Deadlock 4 Deadlock 5 Reusable Resources Used by only one process at a time and not depleted by that use Processes obtain resources that they later release for reuse by other processes 6 Reusable Resources Processors, I/O channels, main and secondary memory, devices, and data structures such as files, databases, and semaphores Deadlock occurs if each process holds one resource and requests the other 7 Reusable Resources 8 Reusable Resources Space is available for allocation of 200Kbytes, and the following sequence of events occur Deadlock occurs if both processes progress to their second request P1 . . . . . . Request 80 Kbytes; Request 60 Kbytes; P2 . . . . . . Request 70 Kbytes; Request 80 Kbytes; 9 Consumable Resources Created (produced) and destroyed (consumed) Interrupts, signals, messages, and information in I/O buffers Deadlock may occur if a Receive message is blocking May take a rare combination of events to cause deadlock 10 Example of Deadlock Deadlock occurs if receives blocking P1 . . . . . . Receive(P2); Send(P2, M1); P2 . . . . . . Receive(P1); Send(P1, M2); 11 Resource Allocation Graphs Directed graph that depicts a state of the system of resources and processes 12 Conditions for Deadlock Mutual exclusion Only one process may use a resource at a time Hold-and-wait A process may hold allocated resources while awaiting assignment of others 13 Conditions for Deadlock No preemption No resource can be forcibly removed form a process holding it Circular wait A closed chain of processes exists, such that each process holds at least one resource .
