Deadlock avoidance, its detection and recovery

Difference between deadlock prevention and deadlock avoidance

Deadlock Avoidance:

  • What it does: It’s like driving a car and always checking the road ahead to make sure you never get stuck in traffic. Before giving a resource to a process, the system checks if doing so could lead to a deadlock in the future. If it’s safe, the process gets the resource. If not, the process has to wait.
  • How it works: The system carefully manages resources by constantly keeping track of what’s available, what’s being used, and what each process might need in the future. This way, it can avoid any situation where processes might get stuck waiting for each other.

Deadlock Prevention:

  • What it does: Instead of constantly checking like in avoidance, deadlock prevention sets up rules from the beginning to make sure a deadlock can never happen. It’s like setting up traffic lights and one-way streets to ensure cars never get stuck in a loop.
  • How it works: The system makes sure that at least one of the conditions needed for a deadlock never happens. For example, it might make sure that processes request all their needed resources at once, or that they release resources if they can’t get everything they need right away.
What exactly is deadlock avoidance?

In deadlock avoidance, the primary goal is to ensure that the system never enters a deadlock state. This approach relies on knowing the current state of the system and carefully managing the allocation of resources to processes to maintain a safe state.

1. System State:
  • The current state of the system includes:
  • The number of processes.
  • The total number of resources available in the system.
  • The number of resources currently allocated to each process.
  • The maximum need of each process (i.e., the maximum number of resources each process may request).
2. Safe State:
  • Now we aim to schedule processes and resources so that our system is safe. A state is considered safe if there exists a sequence of process execution where each process can complete its execution without causing a deadlock.
  • Resources are allocated only if they will keep the system in a safe state. If allocating a resource might lead to an unsafe state (and potentially a deadlock), the system will delay the resource allocation.
Bankers' algorithm

It is a classic example where the system simulates the allocation of resources and checks if the resulting state would be safe. If it’s safe, the allocation proceeds; otherwise, the process must wait.
In the image above, we see that the first process needs 7 units of resource A, but since only 3 units of A are currently available, we can't allocate resources to this process right now. So, we move on to the next process. For the second process, the number of required resources is available, so we allocate the remaining resources to it. Once process 2 completes its execution, it will release all the resources it's holding. We then repeat this procedure for the remaining processes, checking if they can be allocated the resources they need. this way we can find the safe state for the system.

Deadlock detection

In systems that do not use deadlock avoidance or deadlock prevention, we rely on deadlock detection to find out if a deadlock has occurred.
  • How Deadlock Detection Works (Detection Algorithm): The system periodically runs an algorithm to check if any deadlocks exist. This algorithm examines the state of resource allocation and processes to see if there's a circular dependency, which is a sign of a deadlock. Here we can also use the Bankers algorithm to figure out if the system is in a safe state or not. If it isn't in a safe state, then it is in deadlock and vice-versa.
  • If Deadlock is Detected: If the algorithm finds that the system is in a deadlock, it triggers a recovery process. Recovery might involve actions like forcibly terminating some processes or all processes dealing with a deadlock or preempting resources from some processes to break the deadlock.
  • If No Deadlock is Found: If the system is not in a deadlock, the detection algorithm will be run again after a certain time interval to continuously monitor the system.




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