Week 5: Semaphores and Deadlocks Flashcards
Semaphore
Semaphore is a system where the processes get “trapped” in a while loop until the condition becomes false.
The element changing the condition is a “key”.
The first process to enter the system will be able to pass through the while loop and will “lock” it by making the condition true for the following processes.
When process one finished using the resources, the “key” changes and sets the condition to false, allowing another process to pass and blocking again the while loop.
Name 3 practical uses of semaphores
- Buffers
- Shared files/variables
- Limited resources with many processes
Notice:
Semaphores are also a great solution for Process Manager design
Describe how you would implement a file read/write system using semaphores.
When a process used fopen(), a semaphore would let the process pass, copy part of the file into a buffer and then let the process out and another one in. This keeps only one process while ensuring that no one is writing.
Finally, fscan() would act locally, while pointing to the buffer. Once the buffer is empty, the semaphore would kick in again, to copy the rest of the file in the buffer.
Bounded-Buffer Problem
When only one process at the time can use a resource. Also, no other process can access the resource until the first process is done.
When there is synchronization in one direction.
Ex: Sending data to a printer.
In your words, how would you solve this problem with semaphores?
Producer
Here we would need 3 semaphores: mutex, full, empty where mutex is the one that guards the critical section, empty is the one that keeps track of how empty the buffer is, and full the one that keeps track of how full the buffer is. Then, the producer would first check if there is space in the buffer and signal empty, then the first process would enter the Critical Section and finally would signal mutex and full.
Consumer
Same semaphores. First, it will check if there is something in the buffer and signal full with full-1 since the consumer is taking from the buffer, then wait(mutex) since we can’t read and write to the buffer at the same time.
Notice: mutes, empty and full are share between consumer and producer.
Readers-writers Problem
- The resource is shared
- We can have many processes reading at the same time
- We cannot have many processes writing at the same time
How would you solve the Readers-writers problem with semaphores?
In this case we have 2 semaphores: wrt and mutex.
Mutex: allows access to Critical Section
wrt: keeps track is someone is writing
Writer
wait(wrt) ensures that only ONE process can write at the time
Reader
wait(mutex) protects the Critical Section which is the increase/decrease of readersCount (keeps track of the number of readers). Then, wait(wrt) checks if someone is writing and if not, keeps other processes from writing as the process reads.
How would you solve the Dining-Philosophers Problem with semaphores (not with monitors)?
TODO
Explain how the following image is a deadlock based on resources
Notice that the arrows are important.
An arrow coming from a process means “I want” whereas an arrow pointing to a process means “I am using”.
Notice that Process A wants resource 2 but Process B is using resource 2 and it will not finish using it until it gets resource 1. BUT Process A is using resource 1. So Process A and Process B will never end.
Request of resources
If a process needs a given resource it has to wait until it is available.
Use of resources
A process has dedicated access to a resource until it finishes.
True or False
In a deadlock, it is possible that a process in a set of processes will finish executing.
False
By definition, deadlock means that all the processes in a given set of processes can’t finish executing.
Name 4 necessary conditions to get a deadlock
- Mutual exclusion
- Hold and wait
- No pre-emption
- Circular wait
1) Is there a deadlock?
No,
P3 finishes, then P2, then P1
2) Is there a deadlock?
Yes
P3, P2 make a cycle
3) Is there a deadlock?
No,
P2 finishes, then P1 in R1 and finishes, P3 in R2 and finishes and P4 finishes
