Operating Systems 2017F Lecture 13

Video

Video from the lecture given on October 19, 2017 is now available.

Code

Files from the lecture are available.

Note

Questions:

Mutex and semaphore?

Mutex is a binary semaphore, it is a semaphore that take a value that is zero or one, a classic semaphore can count.

Mutex stands for ‘mutual exclusion’: I am exclusive access, no one else does.

More general semaphore is used when you need to keep track of numbers.

Most classic semaphore: read write semaphore. which will be seen in the kernel. The idea is multiple reader and only one writer.

Most of the time we use mutex.

dinner philosopher problem

Wiki page: https://en.wikipedia.org/wiki/Dining_philosophers_problem

You have five philosophers sitting around the table, these philosophers will talk, and they will talk so much, they don’t really want to focus on eating. And for some reason there is not enough of forks at the table. There is one fork at every position between the plates. In order to eat anything, you need two forks.(Maybe better to think about using chopsticks instead of forks). There are five people there and only five forks.

Important notes, 3000 Lecture 13 //can be represented with chopsticks which makes more sense. Illustration of the dining philosophers problems: an example the professor represented, in which philosophers need 2 forks to have dinner but they only have 1 so they will share at random timing but will end up in a mess and an error . This error illustrates deadlock. We can have them to have a delay then pick it up but then they will never eat, we can also have them to do that at randomization which will work but then end up in an error which I explained earlier. Code used in class is tutorial 4 code and the professor is modifying it to explain. Shared state: when they get both of locks (2 chopsticks) they get a message. Modify the code. The message will state “eat it” in the code. In the code presented in class: 5 philosopher and 5 chopsticks. Initilized each semaphore, each Copstick has a lock. Create a processes for each philosopher by forking each one and each will have an ID. Exit the for loop so each child will continue to fork Wait time : they are concurrent , the real time is 1 sec. Philosophers are running concurrently

 Dead lock: the computation cant proceed any further, since the concurrent processes can’t access the other resources. Enough resources you never have to share, deadlock won’t happen. But if you have shared sources you may occur with a deadlock. > Release the locks: ( put a chopstick down) using post in the code Does is matter which one will be released first?  Running the code: someone only has one chopstick and someone did not get it. The code got stuck o How so we solve this? :  Man Sem_wait() to see if it is available to solve this problem. Put sem_wait() and sem_trywait() to check out the problem.  Create a new function called get chopstick , and it failed so thr prof added a sleep()  There is no chopstick 5 = have a bug, #1 failed and no one else is eating except #1. They tried to eat 50 times  No deadlock since we have enough sources, since they exit.  If one exits there is enough chopsticks  The prof tried while (1) which is an infinite loop.  Our code never locks, no dead lock now. Why is that? Nvm some of them are deadlocked such as 4.  Why don’t we access the CHPstick in a fixed order? (Ask what he means) • Which one do we get first?  Solution : If you get 1 only and not 2, you must let go of it and then try to get both.  Release in the opposite order you acquire them  Practice on semaphores, and creating processes  After the midterm : kernel hacking  Linux cross reference : source code into file system (fs) data_sem and others are semaphores  Have to enforce mutual exclusion and that why we use semaphores down = lock, up = release.  Have to release the semaphores so someone accesses the inode To ask : Why is there more chopsticks than philosophers

• Senario 1: they all pick the left one at the same time, they all now have one fork.- can any of them eat? no, they suppose to use two forks to eat.
• Senario 2: Immediately put a fork down, wait for five seconds, and pick a fork. (have a delay, and pick it up) -they will never eat, because they always get one fork.
• Senario 3: randomize it? When they get one fork and couldn’t get the other one, they put it back down, wait a random amount of time and get the next one. -Yes this will work on average, except sometime randomly they will pick up a fork at the same time and starve to death. (unless you have a timeout)

This illustrate the concept of deadlock: you get to the point where the computation cannot proceed any further. Because the concurrence processes cannot get all the resource. Some of them can access the resources and some of them do not have the resources, so everyone stuck.

Wiki page: https://en.wikipedia.org/wiki/Deadlock

When your computer logs up, a lot of time it is because of the deadlock. Something get locked and never get unlocked at the driver.

One way to avoid deadlock: if you have enough resources you never have to share, deadlock never happen. If you have shared resources, you can’t have deadlock.

After the midterm we will do more kernel hacking.