Deadlock/Dining Philosophers

Question 1

Dining Philosophers Problem

Answer 1

There are n philosophers around a table, which each one flipping between eating and thinking. They don’t need resources to think, but need them to eat (chopsticks etc).
There are only n chopsticks, so if a philosopher needs to eat, they must wait for both neighbours to stop eating. We can think of the chopsticks either side of a philosopher as K and (K+1) % 5 (if there are 5 philosophers).

Question 2

Deadlock

Answer 2

Lets say that each philosopher picks up one chopstick each. This results in something called deadlock; each philosopher is waiting for the others to finish, but none will since everyone is waiting.

Question 3

Solution One / Blocking

Answer 3

We can have it where when a philosopher wants to eat, they check both chopsticks to see if there are available, and if they are, proceed to eat. If not, the philosopher is blocked from eating until both are free. However, this does not get rid of deadlock.
This solution also can lead to starvation, where a philosopher can be waiting a very long time.

Question 4

Deadlock Solution

Answer 4

We could add some rules, where only N-1 philosophers can dine at the same time. We could also say that picking up both chopsticks is atomic and cannot be interrupted.

Question 5

Deadlock OS Reactions

Answer 5

The operating system has four days of dealing with deadlock:
- prevent
- detect
- avoid
- ignore

Question 6

Deadlock Prevention

Answer 6

• We could force processes to claim all resources in one atomic operation.
• We could number each resource and force processes to claim them in a specific order
• We could force processes to use only one resource at a time
  This can be shown on a resource allocation graph, which indicates that if there are no loops between processes and resources, it is deadlock free.

Question 7

Deadlock Detection

Answer 7

We can monitor this resource allocation graph with the OS, detecting a cycle and taking one of the following options:
- Remove a resource
- Kill a process
- Roll back to a previously saved state

Question 8

Deadlock Avoidance

Answer 8

Very similar to prevention, in which we:
- Never grant access to a resource that would lead to deadlock
- Make sure that processes declare which resource they will be using
- Makes sure that processes are forced to wait.
The banker’s algorithm is a type of approach, which follows from these rules.

Question 9

Deadlock Ignorance

Answer 9

It is very hard to stop deadlock in an efficient way in terms of things like memory, theory etc.
So we can implement an “algorithm” called the ostrich algorithm, that essentially just states that deadlock is so rare that it is not worth the money, memory nor time to try to implement a prevention for it.

Question 10

Applications in CS

Answer 10

Philosophers are the processes, and chopsticks are the resources.