DJ2-4 Process Synchronization (Lesson 2)

Directory

2.4.3 Semaphore mechanism

1. Integer semaphore

2. Recorded semaphore

3. AND type semaphore

4. Semaphore set

three special cases

2.4.4 Application of semaphore

1. Using semaphores to realize process mutual exclusion

2. Use semaphore to realize predecessor relationship

2.4.5 Monitor Mechanism

1. The composition of the tube process

2. Main features of the tube process


2.4.3 Semaphore Mechanism

Semaphore (Semaphores) mechanism: It is an effective process synchronization tool.

1. Integer semaphore

Define an integer semaphore as an integer S used to represent the number of resources, which can only be accessed through two standard atomic operations wait(S) and signal(S). These two atomic operations are also called P and V operations respectively. Note that uppercase must be used.

wait(S) {
    while(S <= 0); //do no-op, CPU idle
    S--; //Access resources, resource minus one
}

signal(S) {
    S + + ; //Release resources, add one to resources
}

In wait(S), both the test of the value of S and the operation of S=S-1 are uninterruptible.

2. Recorded semaphore

The problem with the integer semaphore: busy waiting, that is, when the semaphore S<=0 in wait(S), the test will be carried out continuously, so the principle of giving the right to wait is not followed. The record-type semaphore mechanism is a process synchronization mechanism that does not have a "busy wait" phenomenon.

The data structure of record semaphore can be described as follows:

typedef struct {
    int value;
    struct process_control_block * list;
} semaphore;

The atomic operations wait(S) and signal(S) can be described as follows:

wait(semaphore * S) {
    S->value--;
    if(S->value < 0) block(S->list);
    //S->value == 0 means that the last resource has just been taken
}

signal(semaphore * S) {
    S->value + + ;
    if(S->value <= 0) wakeup(S->list);
    //S->value == 0 means that there is just one process blocked
}

Problems with integer semaphores and record semaphores:

  • It can only effectively solve the situation where multiple processes share a critical resource
  • That is, only one critical section needs to be set

Let’s look at the situation where multiple processes need to access multiple critical resources. Assuming that processes A and B need to access shared data D and E, set mutually exclusive semaphores Dmutex and Emutex, both of which have an initial value of 1, and the access operations of processes A and B are as follows:

process A: |process B:
wait(Dmutex); |wait(Emutex);
wait(Emutex); |wait(Dmutex);
signal(Emutex); |signal(Dmutex);
signal(Dmutex); |signal(Emutex);

If processes A and B alternately perform wait operations in the following order:

process A: wait(Dmutex); //Dmutex=0
process B: wait(Emutex); //Emutex=0
process A: wait(Emutex); //Emutex=-1, A blocked
process B: wait(Dmutex); //Dmutex=-1, B blocked

After the process is blocked, it cannot release the resources it has held. Eventually, processes A and B will be in a deadlock. In the absence of external force, neither will be able to escape from the stalemate. We say that processes A and B have entered a deadlock state at this time.

3. AND type semaphore

The basic idea of the AND synchronization mechanism: allocate all the resources needed by the process during the entire running process to the process at one time, and release them together after the process is used up. As long as there is still a resource that cannot be allocated to the process, all other resources that may be allocated to it are also not allocated to it.

An atomic operation is adopted for the allocation of several critical resources: either all the requested resources are allocated to the process, or none are allocated. The specific method is to add an “AND” condition in the wait operation, so it is called AND synchronization, or simultaneous wait operation (simultaneous wait).

The Swait operation is defined as follows:

Swait(S1, S2, ... , Sn) {
    while(true) {
        if(S1 >= 1 & amp; & amp; S2 >= 1 & amp; & amp; ... & amp; & amp; Sn >= 1) {
            for(i = 1; i <= n; + + i) Si = Si - 1;
            break; //After allocating resources, exit the while loop directly
        } else {
            /*place the process in the waiting queue associated with
            the first Si found with Si<1, and set the program count
            of this process to the beginning of Swait operation*/
        }
    }
}

The Ssignal operation is defined as follows:

Ssignal(S1, S2, ... , Sn) {
    for(i = 1; i <= n; + + i) Si = Si + 1;
    
    /*remove all the process waiting in the queue
    associated with Si into the ready queue*/
}

4. Semaphore set

In each allocation, a semaphore set is used to control, and multiple resources can be allocated.

The Swait operation is defined as follows:

Swait(S1, t1, d1, ... , Sn, tn, dn) {
    while(true) {
        if(S1 >= t1 & amp; & amp; ... & amp; & amp; Sn >= t1) {
            for(i = 1; i <= n; + + i) Si = Si - di;
            break; //After allocating resources, exit the while loop directly
        } else {
            /*place the process in the waiting queue associated with
            the first Si found with Si<ti, and set the program count
            of this process to the beginning of Swait operation*/
        }
    }
}

The Ssignal operation is defined as follows:

Ssignal(S1, d1, ... , Sn, dn) {
    for(i = 1; i <= n; + + i) Si = Si + di;

    /*remove all the process waiting in the queue
    associated with Si into the ready queue*/
}

Three special cases

1) Swait(S, d, d): There is only one kind of semaphore S, which allows a process to apply for d resources each time. When the existing resources are less than d, they will not be allocated.

2) Swait(S, 1, 1): There is only one kind of semaphore S, which allows the process to apply for 1 resource at a time. When the existing resource is less than 1, it will not be allocated. When S = 1, it means that the total amount of resources is 1, so that the semaphore set degenerates into a mutual exclusion semaphore; when S > 1, it means that the total amount of resources is greater than 1, so that the semaphore set degenerates into a record-type semaphore.

3) Swait(S, 1, 0): Controllable switch. When S >= 1, multiple processes are allowed to enter a particular zone; when S = 0, any process is prevented from entering a particular zone.

Example of reading and writing files: multiple reading processes are allowed to enter the critical section, but once a writing process enters the critical section, any process will be prevented from entering the critical section.

P0: Swait(S, 1, 0) //S>=1 holds true, and does not change the semaphore
P1: Swait(S, 1, 0) //S>=1 holds true, and does not change the semaphore
Pw: Swait(S, 1, 1) //S>=1 is established, and S-1=0
P2: Swait(S, 1, 0) //S>=1 is not true

2.4.4 Application of Semaphore

1. Use semaphore to realize process mutual exclusion

In order to allow multiple processes to mutually exclusive access to a critical resource, it is only necessary to set a mutually exclusive semaphore mutex for the resource, and set its initial value to 1, and then set the critical section CS for each process to access the resource to wait( between mutex) and signal(mutex) operations.

  1. Set a mutual exclusion semaphore mutex
  2. Set its initial value to 1
  3. place critical section CS between wait(mutex) and signal(mutex)

The description of using semaphore to realize mutual exclusion between two processes is as follows:

  • mutex mutually exclusive
  • semaphore semaphore
  • The teacher wrote it in Pascal, I can’t guarantee that my grammar is correct
var mutex:semaphore:=1; //Define mutex as semaphore type, and assign initial value to 1
begin
parbegin

    process1: begin
        repeat
            wait(mutex);
            //critical section
            signal(mutex);
            //remainder section
        until false
    end

    process2: begin
        repeat
            wait(mutex);
            //critical section
            signal(mutex);
            //remainder section
        until false
    end

parend
end

Notice:

  • For mutex semaphores, wait(mutex) and signal(mutex) must appear in pairs;
  • The lack of wait(mutex) leads to system chaos, and mutual exclusion access to critical resources cannot be guaranteed;
  • The lack of a signal(mutex) will cause the critical resource to never be released, and the process waiting for the resource cannot be woken up.

2. Use semaphore to realize predecessor relationship

Use semaphores to describe the predecessor relationship between programs or statements.

Where, Si is the statement that needs to be executed.

p1(){ S1; signal(a); signal(b); }
p2(){ wait(a); S2; signal(c); signal(d);
p3(){ wait(b); S3; signal(e); }
p4(){ wait(c); S4; signal(f); }
p5(){ wait(d); S5; signal(g); }
p6(){ wait(e); wait(f); wait(g); S6; }

void main() {
    semaphore a, b, c, d, e, f, g;

    //Set the initial value of the semaphore to 0, if the subsequent process tries to execute, it must be blocked
    a.value = b.value = c.value = 0;
    d.value = e.value = f.value = g.value = 0;

    cobegin // use parallel execution
         p1(); p2(); p3(); p4(); p5(); p6();
    coend;
}

2.4.5 Monitor Mechanism

When a shared resource is represented by a shared data structure, the resource management program can be represented by a set of processes that operate on the data structure (for example, the resource request process request and the release process release), we combine such a set of related data structures with The processes are collectively called monitors.
Hansan’s definition of a monitor is: “A monitor defines a data structure and a set of operations (on the data structure) that can be performed by concurrent processes. data”.

1. The composition of the monitor

  • monitor name
  • Description of shared variables local to the monitor
  • A set of procedures that operate on the data structure
  • Statements that set initial values for data local to the monitor

Monitor – object-oriented approach

2. Main features of the monitor

Local data variables can only be accessed by the monitor’s process, and cannot be accessed by any external process.

A process enters a monitor by calling a procedure of the monitor.

Only one process can be executing in a monitor at any time, and any other process that invokes the monitor is suspended waiting for the monitor to become available.