Process Synchronization

Process Synchronization

• Logical control flows are concurrent if they overlap in time. This general phenomenon is known as concurrency. Concurrency refers to any form of  interaction among processes or threads. The familiar examples are hardware exception handlers, processes and UNIX signal handlers.

• Modern operating systems can handle more than one process at a time. System scheduler manages processes and their competition for the CPU. The role of memory manager is to manage sharing of main memory between active processes in the system. Look at how processes coexist and communicate with each other on modern computer.

• Concurrency is good for users because working on the same problem, simultaneous execution of programs, background execution.

• Concurrency creates problems also because of access to shared data structures, deadlock due to resource contention and enabling process interaction.

• Applications that use application-level concurrency are known as concurrent Bish programs. Modern operating systems provide three basic approaches for building concurrent programs: Processes, I/O multiplexing and threads.

• Concurrency means that two or more calculations happen within the same time oil frame and there is usually some sort of dependency between them. Parallelism means that two or more calculations happen simultaneously.

• But concurrency describes a problem, while parallelism describes a solution. Parallelism is one way to implement concurrency, but it is not the only one. Another popular solution is interleaved processing.

Principle of Concurrency

• Concurrent access to shared data may result in data inconsistency. Maintaining data consistency requires mechanisms to ensure the orderly execution of Scooperating processes.ug or ai asges

•Concurrency arises in the same way at different levels of execution streams. Following are the example of concurrency in different types of operating systems: 

1. Concurrency in multiprogramming: An interaction between multiple processes running on one CPU.

2. Concurrency in multithreading: An interaction between multiple threads running in one process.

3. Concurrency in multiprocessors: An interaction between multiple CPUs running multiple processes or threads.

4. Concurrency in multi-computers: An interaction between multiple computers running distributed processes or threads.

• Java is a concurrent programming language.

• Process synchronization is required in uni-processor system, multiprocessor system and network. If more than one thread exists in a system at the same time, then the threads are said to be concurrent. Synchronization problems can occur whenever two or more concurrent processes use any shared resource.

• Cooperating process share the logical address space.

Is concurrency is possible without parallelism?

• Yes, concurrency is possible without parallelism.

Concurrency means that more than one process or thread is progressing at the same time. However, it does not imply that the processes are running simultaneously. The scheduling of tasks allows for concurrency, but parallelism is supported only on systems with more than one processing core.

Race Condition

• Race condition occurs when two or more operations occur in an undefined manner. When two or more processes are reading or writing some shared data and the final result depends on who runs precisely when,are called race condition.

• There is a "race condition" if the outcome depends on the order of the execution. The outcome depends on the CPU scheduling or "interleaving" of the threads.

• Race condition should be avoided because they can cause fine errors in applications and are difficult to debug.

• In banking system balance is a shared variable. After depositing the amount, it update by bank employee balance = balance + amount. At the same time, some amount is transfer then it becomes balance balance amount. These two tasks gain are in a race to write variable balance. In this the process that updates last determines the final value of balance.

• The concurrent execution of two processes is not guaranteed to be determinate, since different executions of the same program on the same data may not produce the same result.

Operating system concerns

• Design and management issue for concurrency are as follows:

1. Track of various processes is kept by operating system.

2. Operating systems allocates and deallocate software and hardware resources to active process.

3. Operating system must protect user data and physical resources from un-authorized process.

4. Process execution speed do not depends upon other process

Critical Section Problem

• A critical section is a block of code that only one process at a time can execute; so, when one process is in its critical section, no other process may be in its critical section. The critical section problem is to ensure that only one process at a time is allowed to be operating in its critical section.

• Critical section means, process may change some common variable, writing files, updating memory location, updating a process table etc. When is accessing shared modifiable data, it is said to be in a critical section.

• Each process takes permission from operating system to enter into the critical section. Structure of process is as follows:

1. Entry section

2. Remainder section

3. Exit section

• Entry section: It is block of code executed in preparation for entering critical section.

• Exit section: The code executed upon leaving the critical section.

• Remainder section: Rest of the code is remainder section.

• Each process cycles through remainder, entry, critical, exit sections in this order. 

• Consider the following example:

• Problem: Design a protocol to solve this problem.

Process 1                    Process 2

Count = count + 1      Count = count - 1

Output: count = ?        (6 or 5)

• General framework: Every solution will have the following layout: 

• To prevent critical section problem, the system on should ensure that only one process at a time can execute the instruction in its critical section for a particular resource. If one process attempts to enter its critical section while another is in its own critical section, the first process should wait until the executing process exits the critical section.

• If a process in a critical section terminates by any reasons, then the operating system must release mutual exclusion so that other process may enter their critical sections.

Solution of critical section

• Solution to critical section problem must satisfy the mutual exclusion, progress and bounded waiting parameters.

• Software and hardware solution to critical section problem is available.

• Process using Kernel is active in the system at any given time. Race condition is with implementing a Kernel code. Kernel data structure maintains a list of all open files in the system. System always modifies this list depending upon the process open files and closed files.

• Operating system handles critical section problem by using Kernel. Kernel is classified as preemptive Kernel and non-preemptive Kernel.

Preemptive Kernel: If process running in kernel mode then also it is preempted.

• Non-preemptive Kernel: It does not allow process to preempt.

Critical Region

• Writing set of data into a section of memory or reading it out, generally take some time and is performed through execution of a series of primitives operation.

• Critical region is an area of a process which is sensitive to inter-process complications. To guarantee mutual exclusion only one process is allowed to enter its critical region at a time.

• OS need a system to ensure process cannot enter critical region if another process is in it's.

• A process must be allowed to finish work on a critical part of the program before other processes can have access to it. It is called a critical region because it is a

critical section and its execution must be handled as a unit. Other processes must wait before accessing critical region resources.

• Each conditional critical region is a "resource" that has a name and a set of variables that can only be accessed in that region. All variables can only be accessed within a conditional critical region.

Mutual Exclusion

• The need for mutual exclusion comes with concurrency. There are several kinds of In concurrent execution:

1. Interrupt handlers

2. Interleaved preemptively scheduled processes/threads

3. Multiprocessor clusters, with shared memory

4. Distributed systems

• Mutual exclusion methods are used in concurrent programming to avoid the ob simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections

• Requirement of mutual exclusion is that, when process P1 is accessing a shared resource R1 then on other process should be able to access resource R1 until process P1 has finished its operation with resource R1.

• Examples of such resources include files, I/O devices such as printers and shared data structures.

Approaches to implementing mutual exclusion:

1. Software method: Leave the responsibility with the processes themselves. These methods are usually highly error-prone and carry high overheads.

 2. Hardware method: Special-purpose machine instructions are used for accessing shared resources. This method is faster but cannot provide complete solution. Hardware solution cannot give guarantee the absence of deadlock and starvation

3. Programming language method: Provide support through the operating system or through the programming language.

Requirements of mutual exclusion

1. At any time, only one process is allowed to enter in its critical section.

2. Solution is implemented purely in software on a machine.

3. A process remains inside its critical section for a bounded time only.

4. No assumption can be made about relative speeds of asynchronous concurrent processes.

5. A process cannot prevent any other process for entering into critical section. 

6. A process must not be indefinitely postponed from entering its critical section.

Lock

• Lock is a shared variable. Software mutual exclusion required that a process read a variable to determine that no other process is executing a critical section,then set a variable known as lock. It indicates that the process is executing its critical section.

• Initially lock variable is initialized with zero. The process set it to 1 and enters its critical section.

Lock = 0       no process in the critical section

Lock = 1       process in the critical section

• Using simple lock variable, process synchronization problem is not solved. To avoid this, spinlock is used. A lock that uses busy waiting is called a spin lock.

Mutex

Mutex is used to ensure only one thread at a time can access the resource Bets protected by the mutex. The process that locks the mutex must be the one that unlocks it. Mutex is good only for managing mutual exclusion to some shared resource.

• Mutex is easy and efficient for implement.

• Mutex can be in one of two states: locked or unlocked

• Mutex is represented by one bit. Zero (0) means unlock andsteig represents locked. It uses two procedures.

• When a process needs access to a critical section, it checks the condition of mutex_locks. If the mutex is currently unlocked then calling process enters into critical section.

• If the mutex is locked, the calling process is enters into blocked state and wait until the process in the critical section finishes its execution.

• Mutex variables have only two states so they are simple to implement. Their use is limited to guarding entries to critical regions.

• A segment of code in which a thread may be accessing some shared variable is called a critical region.

• Mutex variable is like a binary semaphore. But both are not same.

University Questions

1. What is a race condition? Explain how a critical section avoids this condition. What are the properties which a data item should possess to implement a critical section? Describe a solution to the Dining philosopher problem so that no races arise.    AU May-17, Marks 13

2. Describe critical section problem with a suitable example.