Operating Systems 2014F Lecture 11

Dining Philosophers problem

When can you have deadlock?

4 conditions must apply

- mutual exclusion

- hold and wait - you can grab a lock and wait for the next one, you can spin / go to sleep or something. You dont' just do things like try the lock if you are successful, and then continue with the computation.

- no pre-emption (pre-emption is taking the resource by force.) you can only have deadlock when people are polite.

- circular wait that's why the dining philosopher's problem has a circular table - have to have something that a) is waiting on one another - that's what gets it into the problem.

you break any of these, you can't have deadlock.

When people talk about deadlock, they talk about strategies for avoiding it (for removing the problem) in terms of these strategies:

1 prevention - construct your system so that deadlock can never happen. (Make it impossible) Design your system such that one of these or more go away. 

let's say one thread has three locks to continue - whenever one goes to sleep, I'll take their chopstick and give it back to them ebfore they wake up and they'll never know the difference.

2 avoidance - prevention means you are making it impossible for this to happen. All four conditions are there in principle, but you can watch the unfolding of the computation, and you can notice when you are getting into a situation that can lead to deadlock, I can avoid it. Allocating resources such that you know that it's never going to happen. It's not necessarily prediction, where you lay a schedule for how everything operates. For example, let's say we are talking about car accidents - complete prevention - don't get into the car. Avoidance - you see something coming, you steer around it, or you have strategies like, stay within the lanes, don't go off the road.