Operating Systems 2014F Lecture 11
The audio from the lecture given on October 10, 2014 is now available.
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.
Symbolic link - treat it as a password file, you replace it quickly and have it point to the real password file. If I win the race, in between the time it checks and the time it modifies the file, I can get in there, and do my damage. Particular problem at the filesystem level. All the stuff we talked about with locks, can't apply to files. It's harder to do atomic operations on files.
If you are programming a system and you are messing with temp files, make sure you use their mechanisms for doing secure temporary file allocation. One of the ways to do this, is it creates a very hard name to guess for your temporary files, it's hard for them to mess with it. Is it perfect no? but it protects you against these types of attacks. A lot of the built in programs to create temporary files claim they are secure, but they are not.
You know that a privileged program is going to mess with the file, it's doing a check for something, it's going to do it, and then it's going to modify it. You setup your race so that you wait for it to do it's check, once that check is done, make sure it passes, and then swap it around. How can I win that? I can potentially do a fork bomb, slow the system down. To win the race.
Switch gears, start thinking about TLBs. TLBs is the probably the most annoying term in operating systems - Translation Lookaside Buffer. When you are going from virtual to physical addresses. We do this on not a per address basis, but a per page basis. It's not actually a table, it's a tree with a couple of levels. But the important thing to realize, is that it's a big complex data structure that you can't access on every data access. It's too slow, why is it too slow? In order to access a big data structure, you have to access multiple locations in memory. The thing you are trying to do quickly, you are having to do many operations that are much slower in order to do the fast operation. The TLB is a cache of virtual to physical mappings. The smallest cache on the chip. question is why is it small? It's really weird. What's the operation I want to do on this cache. I want to give it a virtual address,a nd I want it to give me the corresponding physical address. how can you do a really fast table lookup?
1 have the table sorted, you go through and see where in the table it is and you find it, is a binary search of the table faster 2 what's a data structure that is a key value mapping - hash map - constant time - a hash table isn't fast enough for this so instead of that, the fastest way to do a key value resolution - a content addressable memory. how our brains work - when you want to find something in memory, what's your way of accessing ram? It's by the address - RAM address accessible - ok I want whataver the value is at location 2000, you get that value. do you find anything else in memory, no you find out that particular thing. A TLB instead has all these entries. (each is a page table entry)
