Process Synchronization and Process Exclusion for Learning Notes in operating system

First of all, let’s look at this picture to make a position for the place we are currently studying:

The last note covered the concept of process and process control. This note covers process synchronization and process exclusion.

1. Process synchronization and process synchronization are mutually exclusive

1.1 Process Synchronization

Question:

In a multichannel batch system, multiple processes are executed concurrently, and concurrent processes are asynchronous, that is, each process moves forward at an independent and unpredictable rate. What’s the problem with that? If two processes a and B are reading and writing data, the write should occur before the read data. In fact, due to the asynchronous nature, the read data may occur before the write data, and the read data process will be blocked because the buffer is empty.

Solution:

Therefore, we need to solve this problem through process synchronization.

Related to process synchronization are direct constraints, where multiple processes work together to complete a task and have constraints that result from cooperation and the need to coordinate their work order at certain locations.

1.2 Processes are mutually exclusive

Question:

In a multichannel batch system, multiple processes execute concurrently, and concurrent processes inevitably need to share some system resources (such as memory, printers, cameras, and so on). What’s the problem with that? In fact, there are resources that can only be used by one process at a time, such as various physical devices, variables, data, memory buffers, etc. These are called critical resources — that is, on the one hand, concurrently executing processes need to share resources; On the other hand, access to critical resources must be mutually exclusive (not shared at the same time), which obviously leads to conflicting access to resources.

Solution:

Therefore, we solve this problem through process exclusion.

The indirect restriction relationship is related to process exclusivity, which means that when process A accesses A critical resource, another process B that also wants to access the resource must wait until process A finishes accessing and releases the resource.

Basic implementation logic:

In order to achieve mutually exclusive access to critical resources, the access process of a process to critical resources can be logically divided into four parts:

do {
    extry section;       / / into the area
    critical section;    / / critical region
    exit section;        / / exit area
    remainder section;   / / rest area
} while(true)
Copy the code

• Entry area: if process A wants to access critical resources, it will first check whether it can enter the entry area. Since no other process occupies critical resources at this time, the check passes. At the same time, it sets A Flag indicating that it is currently accessing critical resources.
• Critical section: the piece of code that actually accesses the critical resource
• Exit area: is responsible for removing the previous Flag
• Remaining area: other processing

For process B, if it also wants to access the resource at this point, it will also do A check in the entry area. It knows that process A is accessing the resource, so it cannot access it. This makes resource access mutually exclusive.

Four principles:

To be more specific, we need to constrain this mutually exclusive process with four principles:

• Idle Let in: When a critical section is idle, it indicates that no process is using the critical resource. In this case, the process that wants to enter the critical section should be allowed to enter immediately
• Busy waiting: If a process has already entered a critical section, other processes that want to enter will have to wait
• Finite wait: do not let the process wait forever, ensure that it can enter the critical section in a limited time
• Let wait: when process A enters A critical section and process B cannot enter its own critical section, the processor should be released immediately to prevent the process from falling into A “busy waiting” state.

2. How to implement mutually exclusive processes

2.1 How to Achieve Mutually Exclusive Processes on the Software Level

① Single sign method:

The core of the single Flag method is to use a Flag to mark which process can enter the critical region. When a Flag is given initially, it must be ensured that the process corresponding to the Flag can enter the critical region. After the process successfully enters and completes its task, it changes its Flag to another process. Let’s use an example to illustrate:

int turn = 0; Process P0: process P1:while(turn ! =0);              while(turn ! =1);
critical section;               critical section;
turn = 1;                       turn = 0;
remainder section;              remainder section;
Copy the code

At the beginning we set Flag to point to process 0. Suppose that there are two possibilities: one is that P0 process on the processor first, then the while condition is not satisfied, then smoothly enter its own critical region; In the other case, P1 runs on the processor first. However, because it satisfies the while condition, it falls into an infinite loop and cannot enter the critical region until it runs out of its time slice and turns to P0. P0 enters the critical region smoothly because it does not satisfy the cyclic condition. It is important to note that in this process, even if the processor rights are transferred to P1 as A result of P0 running out of time slices, P1 does not actually enter the critical section, but circulates over and over again — this ensures that only P0 is using the critical resource throughout the process, even though the process is constantly switching back and forth. That is, we have achieved the “mutually exclusive access to resources”.

The problem is that when you look at the whole process, P0 passes Flag to P1 when it’s done, and P1 passes Flag to P0 when it’s done, so it’s always P0 — > P1 — > P0 — > P1……….. This alternates, meaning that even after P0 has run and wants to run again, it has to wait for P1 to finish.

Another problem is that if P0 does not access the critical section, then P1 cannot access the critical section even if the critical section is idle and P1 wants to access the critical resource. This is a clear violation of the “spare room” principle mentioned above.

② Double mark first inspection method:

Instead of using a Flag to indicate which process can enter the critical section, each process has a Flag that can be switched on and off. At its core, all processes start with a false Flag, indicating that none of them want to enter the critical section for the time being. Inscribed with a special process to enter, he will first check whether there are other processes are currently occupy, so just forget about it, their slowly, etc., if not enters oneself, open the Flag immediately entered the switch to true, equivalent to a “lock”, during which only own possession, other processes are not. After completing the task, set Flag to false to release possession (unlock). Let’s use an example to illustrate:

bool flag[2];
flag[0] = false;
flag[1] = false; Process P0: process P1:while (flag[1]);                while (flag[0]);
flag[0] = true;                 flag[1] = true;
critical section;               critical section;
flag[0] = false;                flag[1] = false;
remainder section;              remainder section;
Copy the code

The process is the same as before, and even if other processes are scheduled, they fall into an infinite loop and run out of time, so it looks like mutual exclusion is possible.

Also, notice how individual processes release “permissions” differently here. Single flag method release “permission”, is to give “permission” to a specified process, which indicates that another process to get “permission”, must pass through the process consent (so there is the problem of alternate running); But due to the double mark method can be set with the function of switch Flag, so the release of “authority” is just let go of his own permissions, other processes to enter the critical section into the can, and don’t have to specify the process, so, this method does not have alternate, the operation of his to a certain extent, achieve the decoupling.

The problem is that checking and locking are not an atomic operation and can be interrupted — which means that if A process suddenly switches to PROCESS B after checking but before locking, process B will skip the loop it should have fallen into before process A “locks”. Later, regardless of whether the process switches back or not, both processes A and B skip the loop, which means they can both enter the critical section and use the critical resources at the same time. In other words, double-flag-first checking does not guarantee mutually exclusive access to resources, and it violates the “busy, wait” principle.

③ Check method after double sign

The difference between the double-marked post-inspection method and the pre-inspection method is that it is first “locked” and then “checked”. In other words, the problem with pre-check is that it locks up too slowly, allowing other processes to take advantage, so post-check decides to lock up first anyway. Look at this example:

bool flag[2];
flag[0] = false;
flag[1] = false; P0 process: P1 process: flag[0] = true;                 flag[1] = true;
while (flag[1]);                while (flag[0]);
critical section;               critical section;
flag[0] = false;                flag[1] = false;
remainder section;              remainder section;
Copy the code

The post-check method solves the problem of “busy, wait”, but violates the principles of “spare advance” and “finite wait” — the root problem caused by non-atomic operations is not solved, so it is very likely that neither process can enter the critical region.

For example, if P0 wants to enter the critical section, it will “lock” first, and since there is a gap between “lock” and “check”, if process P0 switches to P1 during this gap, then P1 will also be “locked”. After that, regardless of whether the process switches back or not, both parties are stuck in an endless loop (because both parties have the opportunity to “lock up”, locking others and themselves), which results in no one being able to enter the critical zone and “starvation” occurs.

(4) Peterson algorithm

Peterson algorithm, in fact, at the same time combines the single sign method and double sign after checking method, its core is: in the first place or after the test, first to “lock”, but will turn again after the locked threads for each other, although said he wanted to enter the critical section, but you don’t mind “will be the opportunity to each other. However, since the condition of the while is increased and the turn is common, it is guaranteed that only one while will satisfy the condition in the end. Both the mutually exclusive access to resources and the failure of both parties to access resources are avoided.

Here’s another example:

bool flag[2];  flag[0] = false;  flag[1] = false;
int turn = 0; P0 process: P1 process: flag[0] = true;                 flag[1] = true;
turn = 1;                       turn = 0;
while (flag[1] && turn == 1);   while (flag[0] && turn == 0);
critical section;               critical section;
flag[0] = false;                flag[1] = false;
remainder section;              remainder section;
Copy the code

In the post-check case, P0 first indicates that it wants to enter the critical region, so its Flag is true. Then the process switches to P1, and P1 also indicates that it wants to enter the critical region, so its Flag is also true.

In the case of post-examination, this situation is doomed to a loop in which both parties are unable to enter. But Peterson’s algorithm is different.

In this algorithm, the last process that the other process wants to enter and that “concedes” will not be able to enter the critical section. ** Continuing with the above example, it is possible to:

• While (flag[0] && turn == 0) P0, while (flag[1] && turn == 1) P0, turn = 1, while (flag[1] && turn == 1) Note that for P1, its while condition is not satisfied, so it successfully enters the critical region. Until the “permission” is released, P0 has a chance to break out of its dead loop.

  In this case, since P0 is the last one to yield, it is P1 that enters the critical region

• Or, switch to P0 and execute turn = 1 while (flag[1] && turn == 1), thus entering an infinite loop, and then P1 and execute turn = 0 while (flag[0] && turn == 0), It’s also in an infinite loop, so when the time slice runs out, you end up at P0, and for P0, the while condition is no longer satisfied, so THAT P0 can successfully enter the critical region.

  In this case, since P1 is the last one to yield, it is P0 that enters the critical zone

• And others ……

Considering the asynchronous nature of process concurrency, there are many permutations and combinations, but in either case, one thing is certain: even if both parties want to enter the critical section, since there is only one TURN, one party will be able to successfully break out of the loop and enter the critical section. This prevents starvation; At the same time, the “permission” will never be released as long as its own process does not complete the execution of the critical section, which means that the other process will not seize the opportunity to enter the critical section, which ensures the “mutual exclusion”.

It might be better to use a life example:

A and B go to the library at the same time to borrow a book. A says: “I really want to read this book, but if you want to read it, I don’t mind letting you read it first”, and B also says: “I also want to read this book, but you are so humble I feel embarrassed, you’d better read it first”, so they go back and forth to each other. To the end a also tired, so in hear b again said “let you read” after, a patted b’s shoulder, at the same time took the book over, say: “ok, that I read first, I read, you read again. “

Peterson algorithm solved the problem of idle let in, busy wait, limited wait, but still did not solve the problem of let wait. That is, even though P1 cannot enter the critical section, it still does a meaningless loop when the time slice is its turn, occupying the processor that could have been used by P0.

2.2 How to Implement Mutually Exclusive Processes on Hardware

① Interrupt shielding method

In the dual-flag method, it is possible for two processes to enter the critical region at the same time, but the interrupt masking method can avoid this situation well.

It works in much the same way as the primitives, by using “on/off interrupt instructions” to perform atomic operations. Specifically, is to make the process before you enter the critical section off interrupt instruction execution “locked”, guarantee the thereafter will not be interrupted by the entire execution process, also won’t happen naturally process switching, two processes access to critical resources at the same time, after visiting a critical region, through open interrupt instruction “unlocked”, so that other processes to have the opportunity to access to the critical section.

The advantage of interrupt masking method is simple and efficient, but it is not suitable for multiprocessors, and because it involves the use of the two privilege instructions of open/close interrupt, so in fact this method is only suitable for the kernel process, not for the user process.

(2) TestandSetLock instruction

The TestAndSetLock /TestAndSet instruction is also called the TSL/TS instruction. Double labelling method the fundamental problem lies in a “locked” and “check” is atomic operations, leading to a process can make use of the two operations, while the TSL instruction two operations to the atomic operation (with one, leaving no space), and it also did like interrupt mask instructions, once in the critical section, execution cannot be interrupted.

Although this is a hardware operation, let’s use pseudo code to understand it for the moment:

bool TestAndSet (bool *lock){
    bool old;
    old = *lock;
    *lock = true;
    return old;
}
P0:                                        P1:
while (TestAndSet(&lock));                 while (TestAndSet(&lock));
critical section;                          critical section;
lock = false;                              lock = false;
remainder section;                         remainder section;
Copy the code

Where, lock is the global variable that records whether the critical section is currently “locked”.

First, process P0 wants to access the critical section, so it goes to the while loop, where it does the lock and check in one go — the TSL function executes, on the one hand, sets the global lock to true, Return the old lock with the value false to yourself. So, for itself, by returning false, it can skip the loop and enter the critical section; For P1, every time it tries to “lock” and “check” in the while, it gets stuck in an infinite loop because the global lock has been set to true.

Thus, the whole process ensures that P0’s “locking” and “checking” are atomic operations in one go, and that P0’s execution is never switched. After P0 completes, global lock is set to false again, and so on.

The method of TSL instruction is simple to implement and does not need to strictly check the logic. It is also suitable for multi-processor environment, but it still does not meet the principle of “let the weight wait” — it can be seen from the pseudo-code that P1 may still occupy the processor for nothing after failing to enter the critical area as desired, resulting in “busy and so on”.

(3) Wrap instructions

The Swap directive, or Exchange/XCHG, is similar to the TSL directive:

P0:                             P1:
bool old = true;                bool old = true;  
while (old == true)             while (old == true)
	Swap(&lock,&old)  ;        	    Swap(&lock,&old)  ;  
critical section;               critical section;
lock = false;                   lock = false;
remainder section;              remainder section;
Copy the code

When P0 wants to enter the critical section, it sets old to true and swaps to the critical section. For P1 process, because it shares global lock, global lock = itself old = true, so it falls into an infinite loop and cannot enter the critical region.

Like the TSL instruction, the Swap instruction does not solve the “let wait” problem.

So, is there a more perfect way to solve this problem?