What is process synchronization?
Process synchronization involves managing processes that share the same memory space. It maintains consistency of data by allowing only one process to make changes to the shared memory at one time.
What is the race condition?
A race condition is where multiple processes access and manipulate the same data simultaneously and the outcome of the execution depends on the order in which the access takes place.
What is the critical section problem?
The critical section problem is to make sure that only one process should be in a critical section at a time.
The critical section problem is to design a protocol that processes can use to synchronize their activity so as to cooperatively share data.
What is the critical section in a process?
The critical section is a segment of code in a process where the process may be accessing and updating data that is shared with at least one other process. When one process is executing its critical section, no other process is allowed to execute it’s critical section.
What is the structure of a process?
- Entry Section - Requests permission to enter critical section
- Critical Section - The segment of code where the process may be accessing and updating shared data
- Exit Section - Exits critical section
- Remainder Section - Contains all remaining code
What are the three requirements a solution to the critical section problem must satisfy?
- Mutual Exclusion - If a process is executing in it’s critical section, then no other process can be executing in their critical sections
- Progress - If no process is executing in its critical section and some process wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in deciding which will enter its critical section next, and this selection cannot be postponed indefinitely.
- Bounded waiting - There exists a bound, or limit, on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted.
What Peterson’s solution?
Peterson’s solution is a solution to the critical section problem. It is restricted to two processes that alternate execution between their critical sections and remainder sections. It requires that both processes share two properties which are a Boolean flag and int Turn. When a process is executing in a critical section, then the other process executes the rest of the code.
What are the limitations to Peterson’s solution?
The limitations to Peterson’s solution are:
1. It involves busy waiting (process is waiting for condition to be satisfied in a tight loop)
2. Not guaranteed to work on modern architectures
3. May give inconsistent or unexpected results for multithreaded applications
What is the mutex lock?
The mutex lock is a software tool which solves the critical section problem. The mutex lock is used to protect critical sections and thus prevent race conditions. A process must acquire the lock before entering a critical section using the acquire() function, and release the lock when it exits the critical section using the release() function
What is a semaphore?
Semaphore is an integer variable S, that is initialized with the number of resources present in the system and is used for process synchronization. It uses two functions to change the value of S those being wait() and signal(). Only one process can change the value of S at a particular time.
What are the two types of Sempahore?
- Counting Semaphore - Counting semaphores are set to the maximum amount of processes that can access the resource at one time. The counting semaphore indicates that a process can access the resource if it has a value greater than 0.
- Binary Semaphore - When the semaphore is set to 1, it means that some process is working on its critical section, and if it is set to 0 that means that any process can enter the critical section.
What is a deadlock?
A deadlock is a situation where two or more processes are waiting for each other.
What are the four conditions that when held simultaneously can lead to a deadlock?
- Mutual exclusion: only one process can use a resource at a time.
- Hold and wait: A process holding at least one resource is waiting to acquire additional resources held by other processes
- No pre-emption: A resource cannot be pre-empted (acquired) by another process forcefully. Need to wait.
- Circular wait: P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, and P2 is waiting for a resource held by P0.
What are the 3 methods of handling deadlocks?
- Ignore the problem and pretend that deadlocks never occur in the system: used by most operating systems, including UNIX
- Allow the system to enter a deadlock state and then recover
- Ensure that the system will never enter a deadlock state through either:
- Deadlock prevention
- Deadlock avoidance
What are the methods of deadlock prevention?
- Hold and Wait - ensuring that whenever a process requests a resource, it does not hold any other resources.
- No pre-emption - forcefully pre-empt that resource from the process that is holding that resource. By doing so, we can remove the deadlock
- Circular wait - Impose a total ordering of all resource types to require that each thread requests resources in an increasing order of enumeration
What are the 3 methods of deadlock avoidance?
- Each process declares the maximum number of resources of each type that it may need.
- Deadlock avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular wait condition.
- Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the process.
