System Model

• A system consists of a finite number of resources to be distributed among a number of competing processes.
• The resources are partitioned into several types, each consisting of some number of identical instances.
• Reusable: something that can be safely used by one process at a time and is not consumed by that use. Processes obtain resources that they later release for reuse by others (processors, memory, files, devices, databases, and semaphores).
• Consumable: these can be created and destroyed. When a resource is acquired by a process, the resource ceases to exist (interrupts, signals, messages, and information in I/O buffers).
• A preemptable resource is one that can be taken away from the process owning it with no ill effects. Memory (also CPU) is an example of a preemptable resource.
• A nonpreemptable resource, in contrast, is one that cannot be taken away from its current owner without causing the computation to fail (printer, CD-R(W)floppy disk).
• In general, deadlocks occur when sharing reusable and nonpreemptable resources. Potential deadlocks that involve preemptable resources can usually be resolved by reallocating resources from one process to another.
• A process must request a resource before using it and must release the resource after using it.
  • A process may request as many resources as it requires to carry out its designated task.
  • Obviously, the number of resources requested may not exceed the total number of resources available in the system.
• Under the normal mode of operation, a process may utilize a resource in only the following sequence:
  1. Request. If the request cannot be granted immediately, then the requesting process must wait until it can acquire the resource.
  2. Use. The process can operate on the resource.
  3. Release. The process releases the resource.
• The request and release of resources are system calls. Examples are the $request()$ and $release()$ device, $open()$ and $close()$ file, and $allocate()$ and $free()$ memory system calls.
• Request and release of resources that are not managed by the OS can be accomplished through the $wait()$ and $signal()$ operations on semaphores or through acquisition and release of a mutex lock.
• A system table records whether each resource is free or allocated; for each resource that is allocated, the table also records the process to which it is allocated.
• If a process requests a resource that is currently allocated to another process, it can be added to a queue of processes waiting for this resource.
• A process whose resource request has just been denied will normally sit in a tight loop requesting the resource, then sleeping, then trying again.
• One possible way of allowing user management of resources is to associate a semaphore with each resource. Mutexes can be used equally well.
• The three steps listed above are then implemented as a down on the semaphore to acquire the resource, using the resource, and finally an up on the resource to release it. These steps are shown in Fig. 1.

  Figure 1: Using a semaphore to protect resources. (a) One resource. (b) Two resources.

  
• A set of processes is in a deadlock state when every process in the set is waiting for an event that can be caused only by another process in the set.
  • Because all the processes are waiting, none of them will ever cause any of the events that could wake up any of the other members of the set, and all the processes continue to wait forever.
  • None of the processes can run, none of them can release any resources, and none of them can be awakened.
  • This result holds for any kind of resource, including both hardware and software.
• To illustrate a deadlock state, consider a system with three CD RW drives.
  • Suppose each of three processes holds one of these CD RW drives.
  • If each process now requests another drive, the three processes will be in a deadlock state.
  • Each is waiting for the event "CD RW is released," which can be caused only by one of the other waiting processes.
• Deadlocks can occur in a variety of situations besides requesting dedicated I/O devices. In a database system, for example, a program may have to lock several records it is using, to avoid race conditions.
  • If process $A$ locks record $R1$ and process $B$ locks record $R2$, and then each process tries to lock the other one's record, we also have a deadlock (see Fig. 2).

  Figure 2: (a) Deadlock-free code. (b) Code with a potential deadlock.

  
• Deadlocks can occur on hardware resources or on software resources.
• Unlike other problems in multiprogramming systems, there is no efficient solution to the deadlock problem in the general case.
• A programmer who is developing multithreaded applications must pay particular attention to this problem. Multithreaded programs are good candidates for deadlock because multiple threads can compete for shared resources.