Prevention of deadlock (methods)

Mutual Exclusion

Understanding Mutual Exclusion: Mutual exclusion means that a resource can only be used by one process or thread at a time. If a resource is non-shareable (like a printer), only one process can use it at a time, which is a typical cause of deadlock.

Preventing Mutual Exclusion: To prevent deadlock, one strategy is to minimize or eliminate the use of mutual exclusion whenever possible. This means allowing resources to be shared by multiple processes if it is safe to do so.

Example: Sharable Resources: 

  • Read-Only Files: A read-only file is a good example of a sharable resource. Multiple processes can read from the same file simultaneously without causing any conflict, so there’s no need for mutual exclusion (locking). Since the file is not being modified, there's no risk of inconsistency, so the system doesn't need to enforce mutual exclusion.
  • Memory Spaces: Similarly, if a memory space can be safely accessed by multiple processes without causing data corruption (like shared read-only memory), then mutual exclusion is not necessary.
Hold and wait

Understanding Hold and Wait: Hold and Wait occurs when a process is holding at least one resource and is waiting to acquire additional resources that are currently being held by other processes. This can lead to deadlock if a circular chain of processes forms, each waiting for a resource held by the next in the chain.

1. Prevention Strategy 1: Allocate All Resources at Once:
  • Approach: Before starting execution, a process must request and be allocated all the resources it will need for its entire task.
  • Issue: This can lead to inefficient resource utilization. For example, if a process acquires all the resources (e.g., DVD drive, file, printer) but only needs one at a time, the other resources remain idle. This can cause other processes to wait unnecessarily, leading to resource wastage.
2. Prevention Strategy 2: Request Resources Gradually:
  • Approach: Instead of acquiring all resources at once, a process requests resources only as needed and releases them as soon as it is done using them.
  • Example: In the scenario where a process needs to copy data from a DVD drive to a file and then print the file:
  • The process first requests the DVD drive and file.
  • It completes the data copying task, then releases the DVD drive and file.
  • The process then requests the file and printer to print the copied data.
  • Benefit: This approach allows resources like the printer to be used by other processes while the current process is busy copying data. This maximizes resource utilization and reduces waiting times for other processes.
No preemption

No Preemption: This condition means that once a process has acquired a resource, it cannot be forcibly taken away by the operating system or another process. The process will hold onto the resource until it voluntarily releases it after completing its task.
 Scenario: 
  • Process P1 is holding Resource R1 and needs Resource R2 to proceed.
  • Process P2 is holding Resource R2 and needs Resource R1 to proceed.
  • In this case, a deadlock could occur if both processes hold onto their current resources and wait indefinitely for the other to release the needed resource.
1. Strategy to Prevent Deadlock under No Preemption:
  • Releasing Resources: If a process (e.g., P1) needs a resource that is currently unavailable (e.g., R2 held by P2), a strategy is to preemptively release all resources it currently holds (e.g., R1).
  • After releasing its resources, P1 waits for both R1 and R2 to become available and then requests them together.
  • Issue with Resource Locking: If P1 and P2 both try to acquire R1 and R2 simultaneously, there's a risk of colliding locks (e.g., both processes might try to lock R1 and R2 at the same time).
  • If this happens repeatedly, it could lead to livelock, where processes continually attempt to acquire locks but never succeed, wasting CPU cycles.
  • Solution: Adding Delay to Avoid Livelock:
  • Delay Strategy: To avoid livelock, a small, random delay can be introduced between the attempts to acquire locks on the resources. This reduces the chances of both processes trying to lock the resources at exactly the same time.
2. Strategy to Prevent Deadlock under No Preemption:

Process P1: Holds Resource R1. Needs Resource R2.
Process P2: Holds Resource R2. Needs Resource R3.
Strategy Description: Release and Re-acquisition: To avoid deadlock, P2 might release R2 so that P1 can acquire it. Once P1 has finished using R2, P2 can re-acquire R2 if needed.

Circular wait

Circular Wait: This occurs when a set of processes are waiting for resources in a circular chain. For instance, if P1 is holding R1 and waiting for R2, and P2 is holding R2 and waiting for R1, it forms a circular wait condition.

1. Preventing Circular Wait:
  • Resource Ordering:  Assign a unique order to resources and require processes to request resources in this predefined order.
  • Example: If R1 and R2 are assigned an order (e.g., R1 < R2), processes must request R1 before R2. If P1 holds R1, it must request R2 afterward. If P2 holds R2, it must release R2 and request R1 in the correct order.
  • Result: This eliminates circular waiting because no process will hold a resource while waiting for another resource that is in the future order.



Comments

Post a Comment

Popular posts from this blog

Indexed allocation

Image
  Indexed allocation is a file allocation method used by operating systems to manage how files are stored on disk. The core idea is simple but powerful: instead of storing a file in contiguous blocks or linking blocks one-by-one, the system uses a special index block that contains a list of all the disk block addresses where the file’s data is stored. This removes many limitations of earlier methods like contiguous and linked allocation. In indexed allocation, each file has its own index block . This index block acts like a table of contents. Every entry inside it points to a data block that belongs to that file. When a file is created, the OS allocates an index block and then fills it with pointers to the actual data blocks as the file grows. These data blocks can be located anywhere on the disk , so the file does not need contiguous space. This makes storage much more flexible and avoids external fragmentation. When the system needs to access a particular part of a file, it fir...
Read more

Thrashing

Image
Thrashing occurs in a computer system when the operating system spends a significant amount of time swapping pages in and out of memory, rather than executing actual processes. This typically happens when the system's memory is overcommitted, meaning there are too many processes competing for too little physical memory, leading to frequent page faults. How Memory is Used 1. Initial State: App1 is running, and its two pages are loaded into memory: Frame 1: App1, Page 1 Frame 2: App1, Page 2 Frame 3 and 4 are free. App3's pages are present in swap memory. 2. Switch to App2: Now, you switch to App2, which also requires 2 pages: Frame 3: App2, Page 1 Frame 4: App2, Page 2 Memory is now full with both App1 and App2’s pages. App3's pages are present in swap memory. 3. Switch to App3: You decide to switch to App3, which needs 2 pages as well. Since the memory is full, the system needs to make room: App1’s pages are moved to swap memory: Swap Memory: [App1, Page 1] [App1, Page 2] F...
Read more

Basics of paging

Image
Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory and thus helps in handling fragmentation. It involves breaking down memory into fixed-size blocks called pages and frames. The OS typically decides the page size when the system is configured or during the OS design phase. This page size is constant for the entire system and is determined based on considerations such as hardware architecture, efficiency, and the type of applications running. Common page sizes are 4 KB, 8 KB, or 16 KB. Here's a simple explanation with an example: Basic Concepts Page: A fixed-size block of logical memory (virtual memory) used by a process. Frame: A fixed-size block of physical memory (RAM) where a page is mapped. Page Table: A data structure used by the operating system to keep track of the mapping between pages and frames. The Page Table Base Register (PTBR) is a special register in the CPU that holds the starting address of the page table for ...
Read more