Top 10 List of Week 07

Race Condition
Do you know what a race condition is? It happens when multiple entities access or modify shared resources in a system. This “race” happens because this type of failure is dependent on which entity gains access to the shared resource first. A singlen line in a high-level programming language could translate to multiple assembly instructions and therefore the executing process can get interrupted anywhere along this sequence of assembly instructions.
Peterson’s Algorithm
We need three requirements to solve a critical section problem, whice are mutual exclusion, bounded writing, and progress. Peterson’s algorithm is able to fulfill these requirements. When both processes are attempted to enter at the same time, the ‘turn’ value will be set to both i and j at roughly the same time. The process which has to be entered its critical section first will be decided by the value of ‘turn ‘.
Semaphores
When we hear the word ‘semaphore’, we often think about the flags that scouts use to communicate their message. But in operating systems, it is used as a variable that can hold only a non-negative Integer value, shared between all the threads, with operations wait and signal. It is valuable since it’s simple and works with many processes. There are two types of semaphore, binary and counting.
Bounded Buffer Problem
Bounded buffer problem or producer consumer problem is when a ‘producer’ tries to insert data into an empty slot of the buffer, and then a ‘consumer’ tries to remove data from a filled slot in the buffer. One of the solutions of this problem is to actually use the aforementioned semaphores.
Reader-Writer Problem
Now we’re going to another problem of synchronization. If a process is writing something on a file and another process also starts writing on the same file at the same time, then the system will go into the inconsistent state. Check this site to see what will happen if this happens and how to solve it.
Dining Philosopher’s Problem in C
Imagine five people sitting in a table, with one chopstick on each person’s left and right. They need a pair of chopsticks of course, but they can’t because they can only have one! This is called dining philosopher’s problem and it is similar with deadlock problem in OS resource sharing. Check this Medium article to see how the author explains this problem clearly.
Resource Allocation Graph
Resource allocation graph is the pictorial representation of the state of a system. As its name suggests, the resource allocation graph is the complete information about all the processes which are holding some resources or waiting for some resources. Each process is represented by a circle while the resource is represented by a rectangle. Check this video to see how to make this graph!
What is a deadlock?
When one process is holding some resources for making their execution but same resources are hold by another process, it’s called a ‘deadlock’. There are four Coffman conditions than can cause a deadlock, which are mutual exclusion, hold and wait, no preemption, and circular wait. Read more to see the examples and prevention of a deadlock!
Banker’s Algorithm
To avoid a deadlock, what do we have to do? We can use banker’s algorithm! What? I’m not a banker though! Well, you don’t have to be a banker. This algorithm tells that if any system can go into a deadlock or not by analyzing the currently allocated resources and the resources required by it in the future. Check this site to try to make banker’s algorithm! (not to be a banker)
How to avoid deadlocks?
It is a blessing that C++ standard library has some cure for deadlocks. We can use std::lock as a function that can lock two or more mutexes at once without risk of deadlock. Though std::lock can help us avoid deadlock in those cases where we need to acquire two or more locks together, it doesn’t help if they are acquired separatelyin that case we have to rely on our discipline as developers to ensure we don’t get deadlock. Check this article to see how to implement deadlock avoidance with C++ standard library!