Operating System – Process Management 2(Synchronization and Mutual exclusion of processes)

  1. Process synchronization and mutual exclusion

  • Resources that cannot be used by two or more processes at the same time are called critical resources. The existence of critical resources creates the problem of mutually exclusive access between processes.

  • Mutually exclusive: Two logically independent, unrelated processes that are mutually restricted because they compete for the same resource are called mutually exclusive.

  • Process synchronization: Collaborative processes constantly adjust their relative speed or execution to ensure proper utilization of critical resources and smooth process execution. Generally by intermediate media to achieve: such as semaphore operation, lock operation. Rules for synchronization:

    • Free let into
    • Busy, wait
    • Finite wait: A process must wait for a finite amount of time to enter a critical section to avoid a busy state
    • Grant wait: when a process cannot enter its own critical section, the processor should be released immediately.

  • Locking mechanism

    • Locking and unlocking

      Locking mechanism uses lock variable W to indicate whether the critical region is locked. W =1 indicates that the device is locked

      Efficient locking and unlocking primitives are:

      // Lock primitives
Lock w(a)
{
    while (w == 1) { // Indicates that the current process cannot enter the critical sectionProtect the CPU field of the current process. Puts the current process into the wait queue of W, and puts the process in"Wait"State; Transfer process scheduling; }}// Unlock primitive
Unlock() {
    if(w wait queue is not empty) {remove the first element of wait queue; Put the process in the ready state and put it on the ready queue; } w =0;
}
Copy the code

      All processes that want to access the critical region must first execute the locking primitive. If the locking primitive passes smoothly, the process can enter the critical region. After the critical section is accessed, the unlock primitive is executed to release the critical resource.

  • Semaphore mechanism

    The primitive operations for applying and releasing critical resources in the semaphore mechanism are wait operations and signal operations, also known as P operations and V operations. Semaphore: An effective data structure used in the semaphore synchronization mechanism for synchronization and mutual exclusion of processes. The common ones are integer semaphore, recording semaphore, AND semaphore AND semaphore set.

    • Integer semaphore

      The integer semaphore S represents the number of such critical resources currently available:

      S > 0: indicates the number of idle critical resources in the system

      S = 0: The number of critical resources in the system is 0, and no process is waiting

      S < 0: The absolute value of S represents the number of waiting processes in the system

      wait(s):
	while (s <= 0) {the process waits; s--; } signal(s): s++;Copy the code

    • Recording semaphore

      The data structure of the recording semaphore is:

      struct semaphore{
    int value;
    struct PCB *queue;
};
Copy the code

      The value of value represents the number of critical resources available to the system, and queue is a process linked list pointer to the PCB queue waiting for this resource.

      The primitive operations for recording semaphores are:

      semaphore S;

/ / wait operation
wait(S) {
    S.value--;
    if (S.value >= 0) {this process receives a resource and continues execution; }else{call the block primitive, put the process into the blocking queue, protect the CPU field, release the processor resources; Transfer process scheduling; }}/ / signal operations
signal(S) {
    S.value++;
    if (S.value <= 0) {// Indicates that another process is waiting on the PCB queue
        在queueWake up a blocked process. } Release the critical resource occupied by this process and continue execution; }Copy the code
  1. Example of process synchronization

  • Example 7.1 Synchronizing printer Use

    semaphore s;
s.value = 1;
void main(a){ parbegin(p1,p2,p3,.. ,pn); } pi(){/ / I = 1, 2, 3,... ,nwait(s); Print; signal(s); }Copy the code

  • Example 7.2 has a cache shared by multiple processes, including read and write processes. Write a program that synchronizes multiple processes using the same cache.

    semaphore empty,full;
empty.value = 1; //empty is used to indicate whether the cache has been written
full.value = 0; // Full indicates whether the cache has been read.

reader() {
    while (true) {
        wait(full); // Set full to value 0 before reading to prevent other processes from readingRead cache; signal(empty);// Set the value of empty after reading to 0, indicating that the data in the cache has been read and can be continued.
    }
}

writer() {
    while (true) { wait(empty); Write cache; signal(full); }}// Implement writer and reader alternately by setting two semaphores
void main(a) {
    prebegin(writer,reader);
}
Copy the code

  • Example 7.3 Producer-consumer problem: The producer process produces products and puts them into a cache of capacity N for consumers to take away. Consumers can’t empty the cache and producers can’t put things in the full cache. This is similar to the previous file reading and writing example.

    /* An array represents a cache pool with n buffers. The input pointer in points to a cache where products can be stored and the output pointer OUT points to a cache where products can be obtained. Since arrays can be placed in a loop, when the input or output is incremented by one, it can be expressed as: in = (in + 1) % n, out = (out + 1) % n. If (in + 1) % n = out, the cache pool is full. If (in + 1) % n = out, the cache pool is empty. The integer counter represents the number of full buffers in the cache pool. Mutex: uses the mutex pool semaphore. The initial value mutex = 1 empty: the empty cache semaphore. Full: The full cache semaphore */
semaphore mutex, empty, full;
mutex.value = 1;
empty.value = n;
full.value = 0;

product buffer[n];
int in = 0,out = 0;

void main(a) {
    prebegin(producer, consumer);
}
void producer(a) {
    while (true) {produce a product; wait(empty); wait(mutex); Put the product into the cache; counter++; in = (in +1) % n; signal(mutex); signal(full); }}void consumer(a) {
    while (true) { wait(full); wait(mutex); Take away a product; counter--; out = (out +1) % n; signal(mutex); signal(empty); }}/ / note: In these two processes, the order of wait() semaphores cannot be changed. To apply for mutex resources, full or empty resources must be applied first. Otherwise, mutex resources may not be applied for full or Empty resources, and the process will enter the wait state. Signal (mutex) cannot be executed, causing the cache pool to lock up.
Copy the code

    Typically, processes in the system that use the same resource are called consumers of the resource, and processes that release the resource are called producers.

  • Example 7.4 Reader-writer problem: File F can be shared by multiple processes. Those that write to F are called writing processes, and those that read F are called reading processes. Use Wait and Signal to solve synchronization problems between processes.

    //F can be read by multiple processes at the same time, but cannot be written by multiple processes at the same time. Otherwise, data will be confused. Or one write process can exclude all other processes.
semaphore wmutex,rmutex;
wmutex.value = 1;
rmutex.value = 1; 
int readcount = 0; Readcount is a resource that can be accessed by multiple reader processes, so rmutex is used to control access.
void main(a) {
    prebegin(writer,reader);
}
void writer(a) {
    while (true) { wait(wmutex); Write operations; signal(wmutex); }}void reader(a) {
    while (true) {
        wait(rmutex); // To access readcount, you must first apply for a resource.
        if (readcount == 0) { // If no process of the same type is accessing the resource, you need to apply for itwait(wmutex); } readcount++; signal(rmutex); Read operation; wait(rmutex); readcount--;if (readcount == 0) signal(wmutex); signal(rmutex); }}Copy the code

    This problem is also typical of a class of problems that, unlike producer-consumer problems, allow entry of any number of processes with specific behavior, but not of other types. That is, there is no mutual exclusion between processes of the same type. The key to this problem is that when at least one process of the same type is accessing the resource, the process can directly access the resource without applying for it.

  • Example 7.5 Philosopher eating Problem: Five philosophers eat at a table with five chopsticks placed between each of them. A philosopher can eat only if he gets two chopsticks, or if he doesn’t, he can eat only when others have finished. Every philosopher does not put down his chopsticks until he has eaten. Describe the process of a philosopher eating.

    Suppose every philosopher holds a chopstick first on the left and then on the right. Then philosopher I’s chopstick holding process can be described as:

    // Each chopstick is a critical resource, so create a chopstick semaphore array
semaphore chopstick[5];
// The initial value of each chopstick is 1, and the indexes of adjacent chopstick I are (n+i-1)%n and (I +1)%n. Let philosopher I be to the right of chopstick I
void main(a) {
    prebegin(p1(),p2(),p3(),p4(),p5());
}
void pi(a) {	//p is the philosopher's eating process
	while (true) {
        wait(chopstick[i]);
        wait(chopstick[(i + 1) % n]); Have a meal; signal(chopstick[(i +1) % n]); signal(chopstick[i]); }}Copy the code

    The problem with this approach is that all philosophers pick up the left chopsticks at the same time, so that no philosopher can reach the right chopsticks. Cause a deadlock.

    There are several ways to resolve deadlocks, such as:

    1). Chopsticks are allowed to be picked up only when both the philosopher’s left and right hands are available

    2). At most n-1 philosophers are allowed to take the chopsticks on the left at the same time, so that one philosopher can always get a pair of chopsticks.