DJ2-4 Process Synchronization (Lesson 1)

Directory

2.4.1 Basic Concepts of Process Synchronization

1. Two forms of constraints

2. Critical resource

3. Producer-Consumer Problem

4. Critical section

5. Rules to be followed by the synchronization mechanism

2.4.2 Hardware synchronization mechanism

1. Disable interrupt

2. Test-and-Set command

3. Swap command

4. Summary


The asynchronous nature of the process will inevitably lead to disorderly competition for system resources by several processes, resulting in system chaos. In order to ensure that multiple processes can run in an orderly manner, a process synchronization mechanism must be introduced in a multiprogramming system.

The main task of the process synchronization system is to enable the concurrently executed processes to effectively share resources and cooperate with each other, so that the execution of the program is reproducible.

2.4.1 Basic concepts of process synchronization

1. Two forms of constraints

1) Indirect mutual restriction relationship. Due to shared system resources.

2) Direct mutual restriction relationship. Due to the mutual cooperation between processes.

2. Critical resource

A resource that only one process is allowed to access at a time is a critical resource.

3. Producer-Consumer Problem

1) Problem description

There is a group of producer processes that produce products and provide these products to consumer processes for consumption. In order to enable the producer process and the consumer process to execute concurrently, a buffer pool with n buffers is set between the two, and the producer process puts the products it produces into a buffer zone; the consumer process can take products from a buffer to consume.

2) Workaround

The variables are defined as follows:

int in = 0; //Array unit input pointer
int out = 0; //array unit output pointer
int count = 0; //Record the number of buffer pool products
item buffer[n]; //buffer pool with n buffers

Buffer pools are organized as circular buffers.

In the producer process, a local variable nextp is used to temporarily store the products just produced each time; in the consumer process, a local variable nextc is used to store the products to be consumed each time.

producer

void producer() {
    while(1) {

        //produce an item in nextp

        while(count == n); //The buffer pool is full, do no-op

        buffer[in] = nextp; //put the product
        in = (in + 1) % n; // point to the next array element
        count = count + 1; //Add one to the number of buffer pool products
    }
}

consumer

void consumer() {
    while(1) {
        while(count == 0); //The buffer pool is empty, do no-op

        nextc = buffer[out]; //take out the product
        out = (out + 1) % n; // point to the next array element
        count = count - 1; //The number of buffer pool products minus one

        //consume the item in nextc
    }
}

3) There is a problem

Although the above producer program and consumer program are correct when viewed separately, and the results of the two will be correct when they are executed sequentially, but if they are executed concurrently, errors will occur. The problem lies in the two Process shared variable count.

Suppose the initial value of count is 5 . The producer adds 1 to it, and the consumer subtracts 1 from it. When these two operations are implemented in machine language, they can be described in the following forms.

reg1 = count; |reg2 = count;
reg1 = reg1 + 1; |reg2 = reg2 - 1;
count = reg1; |count = reg2;

Ancestry chart.

In actual execution, the execution of each statement in the two programs may be interspersed due to the end of the time slice.

reg1 = count; (reg1=5)
reg1 = reg1 + 1; (reg1=6)
reg2 = count; (reg2=5)
reg2 = reg2 - 1; (reg2=4)
count = reg1; (count=6)
count = reg2; (count=4)

If you change the order of the interleaved execution of the statements in the two programs, you will see other answers. This indicates that the execution of the program has lost reproducibility. In order to prevent this kind of error, the key to solving this problem is to treat the variable count as a critical resource, that is, let the producer process and the consumer process access the variable count exclusively.

4. Critical section

The section of code that accesses critical resources in each process is called a critical section.

A cyclic process that accesses critical resources is described as follows:

while(true) {
    Entry zone: Check for process entry.
    Critical section: A process accesses critical resources.
    Exit area: Reset the access flag.
    Remaining area: the code of other parts.
}

5. Rules to be followed by synchronization mechanism

1) Idle yield

When no process is in the critical section, a process that requests to enter the critical section should be allowed to immediately enter its own critical section.

2) Wait if busy

When an existing process enters the critical section, other processes trying to enter the critical section must wait.

3) Bounded waiting

For processes that require access to critical resources, they should ensure that they can enter their own critical area within a limited time, so as not to fall into a “dead wait” state.

4) Give up the right to wait

When a process cannot enter its own critical section, the processor should be released immediately to prevent the process from falling into a “busy waiting” state.

2.4.2 Hardware synchronization mechanism

Use computer hardware instructions to solve critical section problems. When managing critical sections, think of flags as a “lock”.

  • Initially the lock is open.
  • Before entering the critical section, the process must first perform a “lock test”.
  • “Lock open” enters, “Lock off” waits.
  • “lock open” When entering, it should be locked immediately to prevent other processes from entering.
  • The “lock test” and lock-off operations must be consecutive (atomic operations).

Computer hardware provides three major instructions: close interrupt, Test-and-Set instruction, and Swap instruction.

1. Disable interrupt

Principle: Turn off the interrupt before entering the lock test, and the interrupt cannot be turned on until the lock test is completed and locked. In this way, during the execution of the process in the critical section, the computer system does not respond to interrupts and thus does not cause scheduling.

shortcoming:

  • Abuse of shutdown rights may lead to serious consequences (interrupts related to system security cannot be responded)
  • Excessive shutdown time will affect system efficiency
  • Not suitable for multi-CPU systems (this one is off and there is another one)

2. Test-and-Set directive

The general description of the TS instruction is as follows:

boolean TS(boolean * lock) {
    boolean old;
    old = *lock;
    * lock = true;
    return old;
}

The loop process structure using TS instruction to realize mutual exclusion can be described as follows:

do {
    //...

    while TS( & amp;lock); //entry section
    //... //critical section
    lock = false; //exit section
    //... //remainder section
} while(true);

do … while … Remember the semicolon at the end.

In the entry area, if there is always lock == true, it means that the critical area is locked, and other processes trying to enter the critical area must wait.

3. Swap command

The Swap instruction is also called the XCHG instruction in 8086/8088, and is used to exchange the contents of two words.

The general description of the Swap command is as follows:

void swap(boolean * a, boolean * b) {
    boolean temp;
    temp = *a;
    * a = * b;
    * b = temp;
}

Set a global boolean variable lock for each critical resource, and its initial value is false (representing no lock). Then set a local boolean variable key . The loop process structure using the Swap instruction to realize mutual exclusion can be described as follows:

do {
    key = true;
    do { //entry section
        swap( & amp; lock, & amp; key);
    } while(key != false);
    //... //critical section
    lock = false; //exit section
    //... //remainder section
} while(true);

Since the initial value of lock is false, the first in-process loop that enters the critical section exits the loop once. At this point, the lock value is true, and other processes trying to enter the critical section will always loop in the inner loop. Until the first process to enter the critical section executes to the exit section, the lock value is set to false .

4. Summary

Using the above hardware instructions can effectively realize process mutual exclusion, but when critical resources are busy, other access processes must continue to test, in a “busy waiting” state, which does not comply with the “wait for right” principle, resulting in processor time waste, and it is difficult to use them to solve complex process synchronization problems.