Definitions of Sync Problems

Deadlock, livelock, and starvation are synchronization problems that can occur in computer systems when multiple processes compete for the same shared resources.

Deadlock refers to a situation where two or more processes are blocked, waiting for each other to release resources they need, leading to a permanent standstill.

Example:

• Two processes, A and B, need to access two resources, X and Y, to complete their tasks. If process A has acquired resource X and is waiting for resource Y, and process B has acquired resource Y and is waiting for resource X, then a deadlock has occurred. Neither process can complete its task without releasing the resource it has acquired, but neither will release it because they are waiting for the other to release the resource they need.
• Another analogy, two trains are approaching each other on a single track railway. Train A wants to go in the direction of train B, and train B wants to go in the direction of train A. If both trains stop and wait for the other to pass, they are in a deadlock situation. Neither train can move forward without the other train moving out of the way, and neither train will move out of the way because they are both waiting for the other to move.

Livelock occurs when two or more processes continuously change their state in response to the state of others, without making progress.

Example:

• Imagine two philosophers sitting at a table and sharing chopsticks to eat. Philosopher A picks up their chopsticks and sees that philosopher B has their chopsticks, so philosopher A puts down their chopsticks. Philosopher B sees philosopher A put down their chopsticks, so they put down their chopsticks. This continues indefinitely, with neither philosopher making progress. This is an example of a livelock.
• Imagine a situation where two cars are stopped at a 4-way stop sign and neither driver wants to go first. If driver A moves a little bit forward, but then stops to let driver B go, and driver B moves a little bit forward but then stops to let driver A go, this could lead to a livelock situation where neither driver makes progress.

Starvation refers to a situation where a process is unable to acquire the resources it needs because they are being held by other processes, leading to an indefinite delay.

Example:

• Consider a system with multiple processes and a single printer. If a process with high priority constantly prints documents, it can prevent other processes from accessing the printer, leading to starvation for the lower priority processes. They may never be able to complete their tasks because the resources they need are always being held by the higher priority process.
• In a busy restaurant, a group of customers arrive and are told that they need to wait for a table to become available. However, other customers who arrive after them are given priority and are seated before the first group. This could lead to starvation for the first group, who may never get a table because the resources (the tables) are always being taken by others.