HOME

Top 10 List of Week 07

1. Process Synchronization
   Process Synchronization is the task of coordinating the execution of process in a way that no 2 processes can have the access (at the same time) to the same shared data and resources. It is specially needed in a multi-process system (concurrency). For Example, process A changing the data in a memory location while another process B is trying to read the data from the same memory location. There is a high probability that data read by the second process will be erroneous.

2. Sections of a Program
   • Entry Section: It is part of the process which decides the entry of a particular process.
   • Critical Section: This part allows one process to enter and modify the shared variable.
   • Exit Section: Exit section allows the other process that are waiting in the Entry Section, to enter into the Critical Sections. It also checks that a process that finished its execution should be removed through this Section.
   • Remainder Section: All other parts of the Code, which is not in Critical, Entry, and Exit Section, are known as the Remainder Section.

3. Critical Section Problem
   A critical section is a segment of code which can be accessed by a signal process at a specific point of time. The section consists of shared data resources that required to be accessed by other processes. In the critical section, only a single process can be executed. Other processes, waiting to execute their critical section, need to wait until the current process completes its execution.

4. Solution to Critical Section Problem
   Solution to critical section problem must enforce all three rules:
   • Mutual Exclusion : Out of a group of cooperating processes, only one process can be in its critical section at a given point of time.
   • Progress : If no process is in its critical section, and if one or more threads want to execute their critical section then any one of these threads must be allowed to get into its critical section.
   • Bound Waiting: When a process makes a request for getting into critical section, there is a specific limit about number of processes can get into their critical section. So, when the limit is reached, the system must allow request to the process to get into its critical section.

5. Synchronization Hardware
   Some times the problems of the Critical Section are also resolved by hardware. Some operating system offers a lock functionality where a Process acquires a lock when entering the Critical section and releases the lock after leaving it. So when another process is trying to enter the critical section, it will not be able to enter as it is locked. It can only do so if it is free by acquiring the lock itself.

6. Mutex vs Semaphore
   Mutex and semaphore are kernel resources that provide synchronization services (also called as synchronization primitives).
   • Mutex (locking mechanism) : In this approach, in the entry section of code, a LOCK is obtained over the critical resources used inside the critical section. In the exit section that lock is released.
   • Semaphore (signaling mechanism) : Semaphore is simply a variable that is non-negative and shared between threads. It is another algorithm or solution to the critical section problem. It is a signaling mechanism and a thread that is waiting on a semaphore, which can be signaled by another thread. Semaphore uses two atomic operations, 1)wait, and 2) signal for the process synchronization.
7. Synchronization Problem Example
   • Bounded buffer Problem : A finite buffer pool is used to exchange messages between producer and consumer processes. Solution to this problem is, creating two counting semaphores “full” and “empty” to keep track of the current number of full and empty buffers respectively
   • Dining Philosophers Problem : Involves the allocation of limited resources to a group of processes in a deadlock-free and starvation-free manner.
   • The Readers Writers Problem : In this problem there are some processes(called readers) that only read the shared data, and never change it, and there are other processes(called writers) who may change the data in addition to reading, or instead of reading it.

8. Deadlock
   Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.
   

9. How to Avoid Deadlocks
   • Mutual Exclusion : Resources shared such as read-only files do not lead to deadlocks but resources, such as printers and tape drives, requires exclusive access by a single process.
   • Hold and Wait : In this condition processes must be prevented from holding one or more resources while simultaneously waiting for one or more others.
   • No preemption : Preemption of process resource allocations can avoid the condition of deadlocks, where ever possible.
   • Circular wait : Circular wait can be avoided if we number all resources, and require that processes request resources only in strictly increasing(or decreasing) order.
10. Handling Deadlock
    • Preemption : We can take a resource from one process and give it to other. This will resolve the deadlock situation, but sometimes it does causes problems.
    • Rollback : In situations where deadlock is a real possibility, the system can periodically make a record of the state of each process and when deadlock occurs, roll everything back to the last checkpoint, and restart, but allocating resources differently so that deadlock does not occur.
    • Kill one or more processes