Basics of Deadlock

What is a deadlock?

Consider two processes, P1 and P2, each requiring two resources, R1 and R2, to execute. Currently, P1 is holding R1, and P2 is holding R2. However, neither P1 nor P2 can continue their execution without acquiring both resources. Since P1 is waiting for R2 (held by P2), and P2 is waiting for R1 (held by P1), this creates a deadlock situation where both processes are stuck, and unable to proceed.


How does a process or thread utilize a resource?
  • Request: The process or thread first checks if the resource (e.g., R) is available. This is often done by attempting to acquire a lock or checking the status of the resource.
  1. If the resource is locked: This means another process or thread is currently using it, so the requesting process must wait. 
  2. If the resource is not locked: The process can acquire the lock, indicating that it now has control over the resource.
  • Use: Once the resource is acquired, the process or thread uses it to perform its task. During this time, the resource remains locked to prevent other processes or threads from accessing it simultaneously.
  • Release: After completing the task, the process or thread releases the resource. This typically involves unlocking the resource and making it available for other processes or threads to use.
Necessary conditions for deadlock

1. Mutual Exclusion: In the mutual exclusion condition, only one process or thread can use a resource at a time. If a resource is already being used by one process, any other process that requests it must wait until the resource is released.
2. Hold and wait:  This condition 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.
3. No Preemption: This condition means that once a resource (like R1) has been allocated to a process (like P1), it cannot be forcibly taken away by the operating system or another process. The process that holds the resource will only release it when it has completed its task with that resource.
4. Circular wait:  This condition occurs when a group of processes are each waiting for a resource that is held by the next process in the sequence. The "circle" means that the last process in the chain is waiting for a resource held by the first process, creating a loop of dependencies.

Resource allocation block


Methods to handle deadlock

1. Deadlock Prevention or Avoidance:
  • Objective: Ensure that the system never enters a deadlock state.
  • Prevention: The system uses strategies to prevent one or more of the necessary conditions for deadlock (mutual exclusion, hold and wait, no preemption, circular wait) from occurring.
2. Deadlock Detection and Recovery:
  • Objective: Allow the system to enter a deadlock state but have mechanisms to detect it and recover from it.
  • Detection: The system periodically checks for deadlocks by analyzing the resource allocation graph or using algorithms designed for detecting cycles in the graph.
3. Ostrich Algorithm:
  • Objective: Ignore the problem of deadlocks.
  • Approach: It assumes that the application programmer is responsible for ensuring that deadlocks do not occur in their code.

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