Deadlock Characteristics

Deadlock Characterization

In a deadlock, processes never finish executing, and system resources are tied up, preventing other jobs from starting. Before we discuss the various methods for dealing with the deadlock problem, we look more closely at features that characterize deadlocks.

Necessary Conditions

A deadlock situation can arise if the following four conditions hold simultaneously in a system:

1. Mutual exclusion

At least one resource must be held in a nonsharable mode; that is, only one process at a time can use the resource. If another process requests that resource, the requesting process must be delayed until the resource has been released.


Let's see how deadlock can :occur in a multithreaded Pthread program using mutex locks. The pthread_mutex_init() function initializes an unlocked mutex. Mutex locks are  acquired ;and released using pthread_mutex_lock() and pthread_mutex_unlock() respectively. If a thread attempts to acquire a locked niutex the call to X pthread_mutex_lock() blocks the thready until the owner of the rnutex lock invokes pthread_mutex_unlock().

Two mutex lock are created uaing following code example.

/* create and initialize mutex locks */

pthread_mutex_t   first_mutex

pthread_mutex_t   second_mutex



Next, two threads—thread-one and thread-two are created, and both tliese threads have access to both mutex locks,thread-one and thread-two run in the functions do_work_one() and do_work_two(), respectively as shown in Figure


Deadlock Characteristics

     In this example, thread one attempts to acquire the mutex locks in the order (1) first_mutex (2) second_mutex, while thread_two attempts to acquire the mutex locks: in the order (1) second _mutex (2) first_mutex. Deadlock is possible, If thread_one 


2. Hold and wait.

A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.

3. No preemption.

Resources cannot be preempted.; that is, a resource can be released only voluntarily by the process holding it, after that process has completed its task.

4. Circular wait.

A set {P0, P1, ..., Pn} of waiting processes must exist such that P0 is waiting for a resource held by P1, P1 is waiting for a resource held by Pi,……., P(i-1) is waiting for a resource held by Pn. We emphasize that all four conditions must hold for a deadlock to occur. The circular-wait condition implies the hold-and-wait condition, so the four conditions are not completely independent.

Resource-Allocation Graph

Deadlocks can be described more precisely in terms of a directed graph called a system resource-allocation graph. This graph consists of a set of vertices V and a set of edges E. The set of vertices V is partitioned into two different types of nodes: P - {Pi, Pi,,.., P,,\, the set consisting of all the active processes in the system, and R = {R[, R?, •••/ Rm}, the set consisting of all resource types in the system. A directed edge from process P- to resource type Rj is denoted by P; -> R ,•; it signifies that process P, has requested an instance of resource type R, and is currently waiting for that resource. A directed edge from resource type Rj to process P- is denoted by Rj -»• P,; it signifies that an instance of resource type Rj has been allocated to process P;. A directed edge P, —> Rj is called a request edge; a directed edge Rj -* P; is called an assignment edge. Pictorially, we represent each process P, as a circle and each resource type Ri as a rectangle. Since resource type Rj may have more than one instance, we represent each such instance as a dot within the rectangle. Note that a request edge points to only the rectangle R;, whereas an assignment edge must also designate one of the dots in the rectangle. When process P, requests an instance of resource type Rj, a request edge is inserted in the resource-allocation graph. When this request can be fulfilled, the request edge is instantaneously transformed to an assignment edge. When the process no longer needs access to the resource, it releases the resource; as a result, the assignment edge is deleted. The resource-allocation graph shown in Figure 7.2 depicts the following situation.

Resource instances:

  • One instance of resource type R1
  • Two instances of resource type R2
  • One instance of resource type R3
  • Three instances of resource type Ri

Deadlock Characteristics

The graph contains no cycles, then no process in the system is deadlocked. If the graph does contain a cycle, then a deadlock may exist. If each resource type has exactly one instance, then a cycle implies that a deadlock has occurred. If the cycle involves only a set of resource types, each of which has only a single instance, then a deadlock has occurred. Each process involved in the cycle is deadlocked. In this case, a cycle in the graph is both a necessary and a sufficient condition for the existence of deadlock. If each resource type has several instances, then a cycle does not necessarily imply that a deadlock has occurred. In this case, a cycle in the graph is a necessary but not a sufficient condition for the existence of deadlock. To illustrate this concept, we return to the resource-allocation graph depicted in Figure 7.2.

Suppose that process P3 requests an instance of resource type RT. Since no resource instance is currently available, a request edge P3 —>• R2 is added to the graph (Figure 7.3). At this point, two minimal cycles exist in the svstem:

Deadlock Characteristics

Processes P\, P2, and P3 are deadlocked. Process P2 is waiting for the resource R3, which is held by process P3. Process P3 is waiting for either process P\ or

Deadlock CharacteristicsDeadlock Characteristics

Frequently Asked Questions

Ans: 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. Memory space, CPU cycles, files, and I/O devices (such as printers and DVD drives) are examples of resource types. If a system has two CPUs, then the resource type CPU has two instances. Similarly, the resource type printer may have five instances. If a process requests an instance of a resource type, the allocation of any instance of the type will satisfy the request. If it will not, then the instances are not identical, and the resource type classes have not been defined properly. view more..
Ans: Synchronization Hardware We have just described one software-based solution to the critical-section problem. In general, we can state that any solution to the critical-section problem requires a simple tool—a lock. Race conditions are prevented by requiring that critical regions be protected by locks. That is, a process must acquire a lock before entering a critical section; it releases the lock when it exits the critical section. view more..
Ans: we illustrate a classic software-based solution to the critical-section problem known as Peterson's solution. Because of the way modern computer architectures perform basic machine-language instructions, such as load and store, there are no guarantees that Peterson's solution will work correctly on such architectures. However, we present the solution because it provides a good algorithmic description of solving the critical-section problem and illustrates some of the complexities involved in designing software that addresses the requirements of mutual exclusion, progress, and bounded waiting requirements. Peterson's solution is restricted to two processes that alternate execution between their critical sections and remainder sections. The processes are numbered Po and Pi. view more..
Ans: Deadlock Characterization In a deadlock, processes never finish executing, and system resources are tied up, preventing other jobs from starting. Before we discuss the various methods for dealing with the deadlock problem, we look more closely at features that characterize deadlocks. view more..
Ans: Atomicity We introduced the concept of an atomic transaction, which is a program unit that must be executed atomically. That is, either all the operations associated with it are executed to completion, or none are performed. When we are dealing with a distributed system, ensuring the atomicity of a transaction becomes much more complicated than in a centralized system. This difficulty occurs because several sites may be participating in the execution of a single transaction. The failure of one of these sites, or the failure of a communication link connecting the sites, may result in erroneous computations. Ensuring that the execution of transactions in the distributed system preserves atomicity is the function of the transaction coordinator. Each site has its own local transaction coordinator, which is responsible for coordinating the execution of all the transactions initiated at that site. view more..
Ans: Kernel Modules The Linux kernel has the ability to load and unload arbitrary sections of kernel code on demand. These loadable kernel modules run in privileged kernel mode and as a consequence have full access to all the hardware capabilities of the machine on which they run. In theory, there is no restriction on what a kernel module is allowed to do; typically, a module might implement a device driver, a file system, or a networking protocol. Kernel modules are convenient for several reasons. Linux's source code is free, so anybody wanting to write kernel code is able to compile a modified kernel and to reboot to load that new functionality; however, recompiling, relinking, and reloading the entire kernel is a cumbersome cycle to undertake when you are developing a new driver. If you use kernel modules, you do not have to make a new kernel to test a new driver—the driver can be compiled on its own and loaded into the already-running kernel. view more..
Ans: Disk Attachment Computers access disk storage in two ways. One way is via I/O ports (or host-attached storage); this is common on small systems. The other way is via a remote host in a distributed file system; this is referred to as network-attached storage. view more..
Ans: Memory-Mapped Files Consider a sequential read of a file on disk using the standard system calls openQ, readO, and writeQ. Each file access requires a system call and disk access. Alternatively, we can use the virtual memory techniques discussed so far to treat file I/O as routine memory accesses. This approach, known as memory mapping a file, allows a part of the virtual address space to be logically associated with the file. view more..
Ans: Efficiency and Performance Now that we have discussed various block-allocation and directorymanagement options, we can further consider their effect on performance and efficient disk use. Disks tend to represent a major bottleneck in system performance, since they are the slowest main computer component. In this section, we discuss a variety of techniques used to improve the efficiency and performance of secondary storage. view more..
Ans: Recovery Files and directories are kept both in main memory and on disk, and care must taken to ensure that system failure does not result in loss of data or in data inconsistency. view more..
Ans: Log-Structured File Systems Computer scientists often find that algorithms and technologies originally used in one area are equally useful in other areas. Such is the case with the database log-based recovery algorithms described in Section 6.9.2. These logging algorithms have been applied successfully to the problem of consistency checking. The resulting implementations are known as log-based transaction-oriented (or journaling) file systems. view more..
Ans: Example: The WAFL File System Disk I/O has a huge impact on system performance. As a result, file-system design and implementation command quite a lot of attention from system designers. Some file systems are general purpose, in that they can provide reasonable performance and functionality for a wide variety of file sizes, file types, and I/O loads. Others are optimized for specific tasks in an attempt to provide better performance in those areas than general-purpose file systems. view more..
Ans: Network Structure There are basically two types of networks: local-area networks (LAN) and wide-area networks (WAN). The main difference between the two is the way in which they are geographically distributed. Local-area networks are composed of processors distributed over small areas (such as a single building? or a number of adjacent buildings), whereas wide-area networks are composed of a number of autonomous processors distributed over a large area (such as the United States). These differences imply major variations in the speed and reliability of the communications network, and they are reflected in the distributed operating-system design. view more..
Ans: Network Topology The sites in a distributed system can be connected physically in a variety of ways. Each configuration has advantages and disadvantages. We can compare the configurations by using the following criteria: • Installation cost. The cost of physically linking the sites in the system • Communication cost. The cost in time and money to send a message from site A to site B 16.4 Network Topology 621 • Availability. The extent to which data can be accessed despite the failure of some links or sites view more..
Ans: Revocation of Access Rights In a dynamic protection system, we may sometimes need to revoke access rights to objects shared by different users view more..
Ans: We survey two capability-based protection systems. These systems vary in their complexity and in the types of policies that can be implemented on them. Neither system is widely used, but they are interesting proving grounds for protection theories view more..
Ans: Robustness A distributed system may suffer from various types of hardware failure. The failure of a link, the failure of a site, and the loss of a message are the most common types. To ensure that the system is robust, we must detect any of these failures, reconfigure the system so that computation can continue, and recover when a site or a link is repaired. view more..
Ans: Design Issues Making the multiplicity of processors and storage devices transparent to the users has been a key challenge to many designers. Ideally, a distributed system should look to its users like a conventional, centralized system. The1 user interface of a transparent distributed system should not distinguish between local and remote resources. That is, users should be able to access remote resources as though these resources were local, and the distributed system should be responsible for locating the resources and for arranging for the appropriate interaction. view more..

Rating - 3/5