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.

Two non-deadlock concurrency bugs: - atomicity violations - you were supposed to lock it and you didn't, you were supposed to grab a lock and you didn't. - order violation - you attempt to use something that hasn't been initialized, use before initialize

TOCTTOU

Time Of Check To Time Of Use

race conditions - a particular class of them, in talking about memory accesses to a variable, we check the value of the variable, and we try to make a change to it

temporary files - you have a program running, in the middle of running, it's potentially useful to generate temporary files, (dump data in the middle of running) where do they often go? in a shared directory (/tmp), your own files

when you run programs that are somehow priviledged (setuid / setgid programs) - when you normally runa program on a unix like system, it runs as you, ls - ls is running as a program. which means they can access any files that you own, they have the privileges that you have. When you need to run programs that need more access. Classic situations include: lpr or passwd

passwd program allows you to change your password - a secure hash of your password is stored in a file called: /etc/passwd /etc/shadow

These files, do you want any one else to be able to change these files? No sometimes regular users want to change their password, so I have this file that I need to keep protected, sometimes I have to allow access to it. This is not an OO system. These are files. So how do I make sure that only certain code can modify that file. You would have some programs that when they ran, they didnt' run with the privileges of the person who ran it, but with the privileges of the person who owns it. This password program we want to run it with extra privileges, we want to run it as root - to change those files. How do I denote this - there is a bit in the protections, there is also the setuid and setgid bit.If these bits are set, then the program runs with the user or group of how the file is own. The password program when you run it, it has the setuid bit set, and it's owned by root. When you run it, it's run by root. Since it is owned by root, it is run as root. you hope passwd doesn't have any bugs, otherwise it could corrupt your passwd file.

Why am I talking about this now? Because these sort of programs, setuid programs, are particularly vulnerable to these TOCTTOU vulnerabilities. It will want to access a file, and if you are not careful, it will access the file with the wrong privileges.

With what privileges does /bin/passwd - it runs w/ root privileges - but it has this command line option that lets it modify any file. So if you aren't careful you could use this to modify arbitrary files on the system. Well we should place some restrictions, what do you place on it ? you have it check the owner and group of the file, and the owner and group of the person who invoked the program. It will only let me modify files that are owned by that user. Standard check, but how does it know a file is owned by that user, it has to check (a system call to ask for the inode). It has to query the filesystem and ask what's that file, who is it owned by? What if I change the file after it's done the check but before it's modified the file.