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.

3 - detect and recover - you had an accident - sorry , call the police, call the bodyshop - fix it up.

in practice we mostly do detect and recover. you don't do all of them perfectly. Where watchdog timers come in? it's something that watches the system and then detects, an easy way of doing this ... let's say you have to call in to, a guard is going around, and when they are checking the perimeter, they have to check in periodically and say, ok that's fine, if someone was to attack the base, what would they do? they take out the guard. Then the signal wouldn't come in. Then you take steps to deal with it.

A watchdog timer, is a separate processor, that is periodically sending it messages - normal interrupts to the system, if the OS is working properly and keeping sending messages back to the interrupt. but if you don't respond to the watchdog timer's request, it goes uh-oh and restarts the system. spontaneous reboot is performed to ensure the system keeps running. The assumption being that when you reboot, you come back to a working state.