C/C++中的进程同步

Process synchronization is the technique to overcome the problem of concurrent access to shared data which can result in data inconsistency. A cooperating process is the one which can affect or be affected by other process which will lead to inconsistency in processes data therefore Process synchronization is required for consistency of data.

The Critical-Section Problem

Every process has a reserved segment of code which is known as Critical Section. In this section, process can change common variables, update tables, write files, etc. The key point to note about critical section is that when one process is executing in its critical section, no other process can execute in its critical section. Each process must request for permission before entering into its critical section and the section of a code implementing this request is the Entry Section, the end of the code is the Exit Section and the remaining code is the remainder section.

Given below is the structure of a critical section of a particular process P1

There are three requirements that must be satisfied for a critical section

• Mutual Exclusion − If one process let’s say P1 is executing in its critical section than any other process let’s say P2 can’t execute in its critical section.
• Progress − If there is no process executing in its critical section and there are processes who wants to enter in its critical section, then only those processes who are not executing in their remainder section can request to enter the critical section and the selection can be postponed indefinitely.
• Bounded Waiting − In bounded waiting, there are limits or bounds on the number of times a process can enter its critical section after a process has made a request to enter its critical section and before that request is granted.

There are two approaches that are commonly used in operating system to handle critical section.

Preemptive Kernel − A preemptive kernel allows a process to be preempted while it is running in kernel mode.

Non-Preemptive Kernels − A non-preemptive kernel doesn’t allow a process running in kernel mode to be preempted.

Peterson’s Solution

Peterson’s solution is a classic based software solution to the critical-section problem. It is restricted to two processes that alternate execution between their critical sections and remainder sections. Peterson’ section requires two data items to be shared between the two processes i.e.

• Int turn;
• Boolean flag[2];

Here, variable turn indicates whose turn is to enter its critical section and flag array indicated whether the process is ready to enter its critical section.

If turn == i, it means process Pi is allowed to enter in its critical section.

If flag[j] is TRUE, it means process j is ready to enter in its critical section

Given below is the structure of process P in Peterson’s solution

Peterson’s Solution preserves all three conditions −

• Mutual Exclusion − one process at a time can access the critical section.
• Progress − A process outside the critical section does not block other processes from entering the critical section.
• Bounded Waiting − Every process will get a chance to enter its critical section without waiting indefinitely.

Synchronization Hardware

It is implemented using two types of instructions −

• Test and Set()
• swap()

Test and Set () is a hardware solution to solve the problem of synchronization. In this, there is a shared variable which is shared by multiple processes known as Lock which can have one value from 0 and 1 where 1 represents Lock gained and 0 represents Lock released.

Whenever the process is trying to enter their critical sections they need to enquire about the value of lock. If the value of lock is 1 then they have to wait until the value of lock won't get changed to 0.

Given below is the mutual-exclusion implementation with TestAndSet()

Semaphores

Semaphore is a synchronization tool that is used to overcome the problems generated by TestAndSet() and Swap() instructions. A semaphore S is an integer variable that can be accessed through two standard atomic operations that are wait() and signal()

Function for wait():

wait(S) {
   While S <= 0
   ; // no operation
   S--;
}

Signal()函数的功能：

signal(S) {
   S++;
}

当一个进程正在修改信号量的值时，其他进程不能同时操作相同的信号量值。

下面给出了使用信号量的互斥实现

操作系统使用两种类型的信号量，它们是：

计数信号量 - 这种类型的信号量的值可以在无限制的域内变化

二进制信号量 - 这种类型的信号量的值可以在0和1之间变化。它们也被称为互斥锁。操作系统使用它来解决多个进程中的临界区问题。