In this tutorial you will learn, what is a deadlock, starvation, and priority inversion in detail. Deadlock and starvation are two common problems that can occur in an operating system.
What is Deadlock in OS
Deadlock occurs when two or more processes are blocked, waiting for each other to release the resources they need to continue execution. This results in a circular wait, where each process is waiting for a resource that is held by another process. Deadlocks can occur when there are limited resources available, and processes do not release them properly after use.
There are four necessary conditions for a deadlock to occur:
- Mutual exclusion: Resources are exclusive to a process, and no other process can use them.
- Hold and wait: A process holding at least one resource is waiting to acquire additional resources held by other processes.
- No preemption: A resource cannot be forcibly removed from a process holding it.
- Circular wait: A circular chain of two or more processes exists, where each process is waiting for a resource held by the next process in the chain.
Deadlocks can be prevented by using techniques such as deadlock prevention, avoidance, and detection. Deadlock prevention involves removing one or more of the necessary conditions for a deadlock to occur. Deadlock avoidance involves predicting which resources a process may need and allocating them accordingly to avoid deadlocks. Deadlock detection involves periodically checking the system for deadlocks and taking corrective action if one is found.
What is Starvation in OS
Starvation occurs when a process is unable to access a resource it needs for an extended period because the resource is continually being allocated to other processes. In other words, a process is prevented from making progress because it is not getting the resources it needs. This can occur when resources are allocated using a first-come, first-served policy, which can result in some processes waiting indefinitely.
Starvation can be prevented by using scheduling policies that ensure every process gets a chance to access resources fairly. For example, a round-robin scheduling policy ensures that each process gets a fixed amount of time to execute before moving on to the next process. Priority-based scheduling policies can also be used to ensure that high-priority processes get access to resources before low-priority processes.
In summary, deadlocks and starvation are two common problems that can occur in an operating system. Deadlocks occur when two or more processes are blocked, waiting for each other to release resources they need to continue execution, while starvation occurs when a process is unable to access a resource it needs for an extended period. Both problems can be prevented or mitigated using various techniques and policies.
Priority Inversion
Priority inversion is a phenomenon that can occur in an operating system where a higher-priority task is blocked because it is waiting for a lower-priority task to release a resource it needs. This can happen in a system where tasks or threads have different priorities, and a lower-priority task is currently holding a resource that a higher-priority task needs to execute.
For example, consider a system with three tasks: A, B, and C. Task A has the highest priority, task B has medium priority, and task C has the lowest priority. If task B is currently holding a resource that task A needs to execute, and task C is scheduled to execute, task A may be blocked until task C completes, even though task A has a higher priority than both task B and task C. This situation is known as priority inversion.
Priority inversion can cause significant problems in real-time systems, where the timely execution of high-priority tasks is critical. If a high-priority task is blocked for an extended period due to priority inversion, it can cause delays and potentially impact the system’s overall performance.
Techniques that can be used to prevent priority inversion
There are several techniques that can be used to prevent priority inversion. One common approach is to use priority inheritance protocols, which dynamically elevate the priority of a lower-priority task to prevent priority inversion. In this approach, if a higher-priority task is blocked by a lower-priority task, the lower-priority task is temporarily assigned a higher priority, equal to that of the blocked task. This ensures that the blocked task can access the necessary resources to continue executing as soon as possible.
Another approach is to use priority ceiling protocols, which restrict the highest priority level that a resource can be accessed. This technique ensures that a higher-priority task cannot be blocked by a lower-priority task that is holding a resource it needs.
In summary, priority inversion is a problem that can occur in operating systems where a higher-priority task is blocked by a lower-priority task that is holding a resource it needs. Several techniques can be used to prevent priority inversion, including priority inheritance and priority ceiling protocols.
The issue in Mars Pathfinder due to Priority Inversion
The Mars Pathfinder mission experienced a critical issue related to priority inversion. The mission was launched in 1996 by NASA to explore the surface of Mars using a rover called Sojourner. The rover was designed to operate on a tight schedule and complete specific tasks during specific time windows.
The mission’s software used a real-time operating system that implemented a priority-based scheduler. The rover’s most critical task was to take pictures, and this task had the highest priority. However, during the mission, the rover’s communication software, which had a lower priority, needed to send data to the lander to relay it back to Earth.
The communication software used a shared buffer to transfer data to the lander, and it took longer to complete than expected, resulting in a priority inversion. The rover’s camera software was blocked from executing because it was waiting for the communication software to release the shared buffer. This delay caused the rover to miss its picture-taking window, which had significant implications for the mission’s success.
To address this issue, the mission team implemented a priority inversion avoidance protocol called priority inheritance. In this protocol, the priority of the communication software was temporarily elevated to the priority of the camera software when the camera software needed to use the shared buffer. This ensured that the critical task of taking pictures was not blocked, and the mission could continue as planned.
The Mars Pathfinder mission’s experience with priority inversion highlights the importance of using real-time operating systems and implementing priority-based scheduling protocols carefully. It also emphasizes the critical role that software plays in the success of complex missions like space exploration.
