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.

• 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.