Linux with Operating System Concepts

mutually exclusive
. This means that if 
a process has access to a resource, any other process that wants to also access that resource 
is forced to wait.
In the above example, this will be handled by forcing P1 to wait before accessing file 
F0. Therefore, before step 4, P1 is forced to wait. With P1 waiting, the operating system 
will move on to another process (perhaps P0 again). The operating system is in charge 
of enforcing mutually exclusive access to resources by granting access to a process upon 
request but only if no other process is currently holding onto the resource.
This leads to another situation that we need to resolve. Let us go back to our prior exam-
ple with P0 and P1 but slightly modify it. There are two files that both processes are going 
to access, F0 and F1. We have the following pattern:
1. P0 begins executing
2. P0 requests access to F0

---

586
◾
Linux with Operating System Concepts
3. As no other process is using F0, the operating system grants P0 access
4. A context switch forces the CPU to switch to P1
5. P1 begins executing
6. P1 requests access to F1
7. As no other process is using F1, the operating system grants P1 access
8. A context switch forces the CPU to switch to P0
9. P0 resumes executing
10. While holding onto F0, P0 requests access to F1
11. The operating system denies access to P0 as P1 is holding onto F1. P0 enters a waiting 
state and the CPU performs a context switch to P1
12. P1 resumes executing
13. While holding onto F1, P1 requests access to F0
14. The operating system denies access to P1 as P0 is holding onto F0. P1 enters a wait-
ing state
In our example, we have P0 waiting for F1 to become available and P1 waiting for F0 
to become available. As P0 is holding onto F0, F0 will not become available for P1 until 
P0 resumes. P0 itself cannot resume until F1 becomes available but F1 is being held by P1 
and P1 is also waiting. P0 and P1 are in a state of 
deadlock
. Neither process can continue 
but because each process needs the resource it is holding onto, neither resource can be 
used. Neither P0 nor P1 are making progress toward completion; so, they are both starv-
ing. Even worse though is that any other process that might need F0 or F1 also becomes 
deadlocked.
Operating systems handle deadlock in differing ways. Some aggressively prevent 
deadlock from arising by keeping processes that might cause a deadlock waiting before 
they can be executed. Others prevent deadlock by not allocating a resource to a process if 
the action might result in a deadlock. Others ignore the possibility of causing a deadlock 
but look for deadlocks on occasion (such as every few minutes). If a deadlock is detected, 
the deadlock is resolved by arbitrarily killing off some of the processes. Yet other operat-
ing systems ignore deadlock entirely, leaving it up to the user (or administrator) to detect 
and handle.
Linux handles deadlock in two ways. First, for kernel processes, deadlocks are avoided 
because kernel processes are granted access to resources in a specific order. A particular 
resource will only be granted to a kernel process when it is that process’ turn to access any 
or all resources. Second, for user processes, Linux implements the Ostrich algorithm. This 
is a sarcastic response meaning that Linux buries its head in the sand to ignore deadlocks. 
So, deadlocks are free to arise for any nonkernel set of processes!

---

Maintaining and Troubleshooting Linux
◾
587
14.4.2 Fairness
Related to liveness and starvation is another concept known as