[operating system] Chapter 2 -- process description and control -- in depth and explanation

Before further explanation, you can read the corresponding notes to understand → [operating system] Chapter 2 - process description and control - notes and understanding (2)

Chapter II – process description and control – in depth and explanation (2)

Synchronization code of three classic cases

Producer consumer
  • Single producer single consumer single buffer
// Core code
void *producer(void *p) {
    while(1) {
        sem_wait(&space);
        printf("Put a product\n");
        sem_post(&prod);
    }
    return NULL;
}
void *consumer(void *p) {
    while(1) {
        sem_wait(&prod);
        printf("Get a product\n");
        sem_post(&space);
    }
    return NULL;
}

// Full code
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>
sem_t space,prod;

void *producer(void *p) {
    while(1) {
        sem_wait(&space);
        printf("Put a product\n");
        sem_post(&prod);
    }
    return NULL;
}
void *consumer(void *p) {
    while(1) {
        sem_wait(&prod);
        printf("Get a product\n");
        sem_post(&space);
    }
    return NULL;
}

int main(void) {

    sem_init(&space,0,1);
    sem_init(&prod,0,0);
    pthread_t tid[2];
    pthread_create(&tid[0],NULL,producer,NULL);
    pthread_create(&tid[1],NULL,consumer,NULL);
    sem_destroy(&space);
    sem_destroy(&prod);
    pthread_join(tid[0],NULL);
    
    return 0;
}


  • Single producer single consumer multiple buffers
// Core code
void *producer(void *p) {
    while(1) {
        sem_wait(&space);
        printf("Put a product into Buffer[%d]\n",in);
        in = (in+1)%N;
        sem_post(&prod);
    }
    return NULL;
}
void *consumer(void *p) {
    while(1) {
        sem_wait(&prod);
        printf("Get a product from Buffer[%d]\n",out);
        out = (out+1)%N;
        sem_post(&space);
    }
    return NULL;
}

// Full code
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>
#define N 10
sem_t space,prod;
int BUffer[N];
int in=0,out=0;

void *producer(void *p) {
    while(1) {
        sem_wait(&space);
        printf("Put a product into Buffer[%d]\n",in);
        in = (in+1)%N;
        sem_post(&prod);
    }
    return NULL;
}
void *consumer(void *p) {
    while(1) {
        sem_wait(&prod);
        printf("Get a product from Buffer[%d]\n",out);
        out = (out+1)%N;
        sem_post(&space);
    }
    return NULL;
}

int main(void) {

    sem_init(&space,0,N);
    sem_init(&prod,0,0);
    pthread_t tid[2];
    pthread_create(&tid[0],NULL,producer,NULL);
    pthread_create(&tid[1],NULL,consumer,NULL);
    sem_destroy(&space);
    sem_destroy(&prod);
    pthread_join(tid[0],NULL);

    return 0;
}


  • Multi producer multi consumer
// Core code
void *producer(void *p) {
    while(1) {
        sem_wait(&space);
        sem_wait(&buf);
        printf("Put a product into Buffer[%d]\n",in);
        in = (in+1)%N;
        sem_post(&prod);
        sem_post(&buf);
    }
    return NULL;
}
void *consumer(void *p) {
    while(1) {
        sem_wait(&prod);
        sem_wait(&buf);
        printf("Get a product from Buffer[%d]\n",out);
        out = (out+1)%N;
        sem_post(&space);
        sem_post(&buf);
    }
    return NULL;
}

// Full code
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>
#define M 8
#define N 10
sem_t space,prod,buf;
int Buffer[N];
int in = 0, out = 0;

void *producer(void *p) {
    while(1) {
        sem_wait(&space);
        sem_wait(&buf);
        printf("Put a product into Buffer[%d]\n",in);
        in = (in+1)%N;
        sem_post(&prod);
        sem_post(&buf);
    }
    return NULL;
}
void *consumer(void *p) {
    while(1) {
        sem_wait(&prod);
        sem_wait(&buf);
        printf("Get a product from Buffer[%d]\n",out);
        out = (out+1)%N;
        sem_post(&space);
        sem_post(&buf);
    }
    return NULL;
}

int main(void) {
    
    sem_init(&space,0,N);
    sem_init(&prod,0,0);
    sem_init(&buf,0,1);
    pthread_t tid[M],tid2[M];
    for(int i = 0; i < M; i ++) {
        pthread_create(&tid[i],NULL,producer,NULL);
    }
    for(int i = 0; i < M; i ++) {
        pthread_create(&tid2[i],NULL,consumer,NULL);
    }
    sem_destroy(&space);
    sem_destroy(&prod);
    sem_destroy(&buf);
    pthread_join(tid[0],NULL);

    return 0;

}

Reader writer
  • Reader writer reader first
// Core code
void *reader(void *p) {
    sem_wait(&srcount);
    readcount++;
    if(readcount == 1) {
        sem_wait(&sdata);
    }
    sem_post(&srcount);
    printf("Reading..\n");
    sem_wait(&srcount);
    readcount--;
    if(readcount == 0) {
        sem_post(&sdata);
    }
    sem_post(&srcount);
    return NULL;
}
void *writer(void *p) {
    sem_wait(&sdata);
    printf("Writing..\n");
    sem_post(&sdata);
    return NULL;
}

// Full code
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>
#define M 10
sem_t sdata,srcount;
int readcount = 0;

void *reader(void *p) {
    sem_wait(&srcount);
    readcount++;
    if(readcount == 1) {
        sem_wait(&sdata);
    }
    sem_post(&srcount);
    printf("Reading..\n");
    sem_wait(&srcount);
    readcount--;
    if(readcount == 0) {
        sem_post(&sdata);
    }
    sem_post(&srcount);
    return NULL;
}
void *writer(void *p) {
    sem_wait(&sdata);
    printf("Writing..\n");
    sem_post(&sdata);
    return NULL;
}

int main(void) {

    sem_init(&sdata,0,1);
    sem_init(&srcount,0,1);
    pthread_t tid[M],tid2[M];
    for(int i = 0; i < M; i ++) {
        pthread_create(&tid[i],NULL,writer,NULL);
    }
    for(int i = 0; i < M; i ++) {
        pthread_create(&tid2[i],NULL,reader,NULL);
    }
    sem_destroy(&sdata);
    sem_destroy(&srcount);
    pthread_join(tid[0],NULL);

    return 0;
}


  • Reader writer writer first
// Core code
void *reader(void *p) {
    sem_wait(&sdata);
    sem_wait(&srcount);
    sem_post(&sdata);
    printf("Reading..\n");    
    sem_post(&srcount);
    return NULL;
}
void *writer(void *p) {
    sem_wait(&sdata);
    for(int i = 0; i < N; i++) {
        sem_wait(&srcount);
    }
    printf("Writing..\n");
    for(int i = 0; i < N; i++) {
        sem_post(&srcount);
    }
    sem_post(&sdata);
    return NULL;
} 

// Full code
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>
#define M 10
sem_t sdata,srcount;
int readcount = 0;

void *reader(void *p) {
    sem_wait(&srcount);
    readcount++;
    if(readcount == 1) {
        sem_wait(&sdata);
    }
    sem_post(&srcount);
    printf("Reading..\n");
    sem_wait(&srcount);
    readcount--;
    if(readcount == 0) {
        sem_post(&sdata);
    }
    sem_post(&srcount);
    return NULL;
}
void *writer(void *p) {
    sem_wait(&sdata);
    printf("Writing..\n");
    sem_post(&sdata);
    return NULL;
}

int main(void) {

    sem_init(&sdata,0,1);
    sem_init(&srcount,0,1);
    pthread_t tid[M],tid2[M];
    for(int i = 0; i < M; i ++) {
        pthread_create(&tid[i],NULL,writer,NULL);
    }
    for(int i = 0; i < M; i ++) {
        pthread_create(&tid2[i],NULL,reader,NULL);
    }
    sem_destroy(&sdata);
    sem_destroy(&srcount);
    pthread_join(tid[0],NULL);

    return 0;
}


Dining for philosophers
  • Basic scheme
#include<stdio.h>
#include<semaphore.h>
#include<pthread.h>
sem_t sfork[5];
void *philosopher(void*p) {
    int id=(int)p;
    while(1){
        printf("Thinking...\n");
        sem_wait(&sfork[id]);
        sem_wait(&sfork[(id+1)%5]);
        printf("Eating...\n");
        sem_post(&sfork[id]);
        sem_post(&sfork[(id+1)%5]);
    }
    return NULL;
}
int main() {
    for(int i=0;i<5;i++)
        sem_init(&sfork[i],0,1);
    pthread_t tid[5]];
    for(int i=0;i<5;i++)
        pthread_create(&tid[i],NULL,philosopher,(void*)i);
    for(int i=0;i<5;i++)
        sem_destroy(&sfork);
    pthread_join(tid[0],NULL);
}
  • Solution 1
#include<stdio.h>
#include<semaphore.h>
#include<pthread.h>
sem_t sfork[5];
void *philosopher(void*p) {
    int id=(int)p;
    while(1){
        printf("Thinking...\n");
        if(id%2==0){
            sem_wait(&sfork[id]);
            sem_wait(&sfork[(id+1)%5]);
        }
        else{
            sem_wait(&sfork[(id+1)%5]);
            sem_wait(&sfork[id]);
        }
        printf("Eating...\n");
        sem_post(&sfork[id]);
        sem_post(&sfork[(id+1)%5]);
    }
    return NULL;
}
int main() {
    for(int i=0;i<5;i++)
    sem_init(&sfork[i],0,1);
    pthread_t tid[5]];
    for(inti=0;i<5;i++)
        pthread_create(&tid[i],NULL,philosopher,(void*)i);
    for(inti=0;i<5;i++)
        sem_destroy(&sfork);
    pthread_join(tid[0],NULL);
}
  • Solution 2
#include<stdio.h>
#include<semaphore.h>
#include<pthread.h>
sem_t sfork[5];
void *philosopher(void*p) {
    int id=(int)p;
    while(1){
        printf("Thinking...\n");
        if(id%==4){
            sem_wait(&sfork[0]);
            sem_wait(&sfork[4]);
        }
        else{
            sem_wait(&sfork[id]);
            sem_wait(&sfork[id+1]);
        }
        printf("Eating...\n");
        sem_post(&sfork[id]);
        sem_post(&sfork[(id+1)%5]);
    }
    return NULL;
}
int main() {
    for(int i=0;i<5;i++)
        sem_init(&sfork[i],0,1);
    pthread_ttid[5]];
    for(int i=0;i<5;i++)
        pthread_create(&tid[i],NULL,philosopher,(void*)i);  
    for(int i=0;i<5;i++)
        sem_destroy(&sfork);
    pthread_join(tid[0],NULL);
}

Understand three cases

Design benefits embodied in the producer consumer model
  1. Decoupling: Conceptually speaking, coupling refers to the phenomenon that two or more systems or two motion forms interact with each other so as to unite. Decoupling is actually to use mathematical methods to decompose the two motions to deal with the problem. How does the producer consumer model reflect the idea of decoupling? For a simple example, if we want to change our eating taste, we will think of ordering takeout. Before there are no takeout platforms, the street will not be full of takeout brothers. If we want to order a takeout, we often call the store and order a meal directly. And the boss who receives a meal order call often receives the call, cooks and delivers meals to customers. Then we will find that it is not easy for the boss at this time. First of all, he has to wash, cut and cook his own vegetables, pack them after they are ready, then ride a bicycle or an electric car to deliver his own meals, and be very familiar with the roads in the city to ensure speed and accuracy; It's really hard for a boss to contract all things. Moreover, if this order takes a long time, it will directly affect the time of the next order. If you hurt yourself when cooking, you may not be able to cook for the day. The two things of cooking and delivering meals are interrelated and affect each other, and they are all coupled together; However, it is different with the delivery brother. The boss only needs to focus on the dishes. The delivery problem can be left to the delivery brother. The functions are clear and the efficiency is naturally higher; Here, we can take the boss as a producer and the takeout brother as a consumer to solve this coupling problem;
  2. Balancing the capabilities of consumers and producers: the same is the case of takeout. If the boss cooks quickly, but the takeout brother takes a long time to deliver the meal, then we will wait a long time to get the takeout. In addition, what we finally wait for is not what the boss really wants to present. Then we may have a bad feeling about the dishes; Similarly, if the boss is slow in cooking and the delivery boy has been waiting in the store, it will affect the dining time of the customers who order this meal, and other orders will also be delayed. This is also a problem. Because the producer consumer model has more clearly separated its only problems, it can be solved quickly; As for the problem that the first type of consumer consumption (delivery brother) can not keep up with the production capacity of the producer (boss), we can only focus on the consumer, and we can send more delivery brothers. Each of us is in charge of one of our most familiar areas, which is not only fast, but also high accuracy; As for the second problem that the production capacity of producers (bosses) can not keep up with that of consumers (takeout boys), we only focus on improving the production capacity of producers. We can solve the production capacity problem by hiring more chefs and opening more branches; This will solve the problem of capacity imbalance between producers and consumers.
The application of reader writer model in life
  • In fact, the reader writer model should follow three important points: reading and writing are mutually exclusive, writing is mutually exclusive, and reading is not mutually exclusive;
  • Take a very simple example. In ordinary class, teachers in class often use computers and projectors to assist in class. For the content cast on the screen, students in the classroom can see and receive new knowledge at the same time. This shows that reading is not mutually exclusive. I read mine and you read yours. We do not change the content, so there is no problem of mutual exclusion; During the flipped class, many students copied their PPT to the classroom computer. When it was their turn, they explained their ppt. During this period, the right to use the computer was handed over to each student who was lecturing. It is impossible to say that two students went up to operate the computer at the same time. There is only one pair of keyboard and mouse, and two people are not allowed to operate at the same time. This corresponds to the mutual exclusion of writing in the reader writer model; In the process of PPT presentation, an error is suddenly found and needs to be modified on the spot. Of course, it cannot be directly modified in the PPT being demonstrated. First, switch to the PPT editing mode, edit and save it again. When you open the PPT again for presentation, the content that appears is the correct content after modification. Here, it reflects the mutual exclusion of reading and writing;
In the producer consumer problem, there are two wait() operations and two signal() operations in producer() and consumer(). Can you change the order of adjacent operations and what impact will the change bring?
  • In producer():
    1. Record wait(empty) as operation ①
    2. wait(mutex) is recorded as operation ②
  • In consumer():
    1. Record wait(full) as operation ③
    2. wait(mutex) is recorded as operation ④
  • In producer():
    1. Record signal(mutex) as operation ⑤
    2. signal(full) is recorded as operation ⑥
  • In consumer():
    1. Record signal(mutex) as operation ⑦
    2. signal(empty) is recorded as operation ⑧.
  1. wait(): exchange ③ and ④. As soon as the process starts, execute ① first. If wait(empty) is true, continue to execute; Then execute ④. If wait(mutex) is true, continue to execute; Then execute ②, the wait(mutex) is false, and the producer process is blocked; Then execute ③ wait(full) as false, and the consumer process is blocked, so it cannot be replaced.
  2. signal(): it can be exchanged, but it will bring overhead. Exchange ⑤ ⑥, then ⑥ signal(full) will wake up the process waiting for the consumable buffer, execute the wait(full) operation in the consumer as true, and continue to execute the wait(mutex) as false, blocking; But ⑤ signal(mutex) will wake up the process waiting to enter the critical zone. So it can be exchanged, but the cost is relatively large.
In the producer consumer problem, if the buffer is full, what will be the impact of exchanging the producer's wait() operation and the consumer's wait() operation?
  • If the buffer is full at this time, then empty=0,full=n. the producer executes wait(mutex) to make mutex 0, and then executes wait(empty). Since there is no free buffer, the producer will be blocked. Because the producer is blocked, it switches back to the consumer process. The consumer process executes wait(mutex). Since mutex is 0, that is, the producer has not released the lock on critical resources, the consumer is also blocked. This leads to the situation that the producer waits for the consumer to release the free buffer, while the consumer waits for the producer to release the critical zone. The producer and the consumer wait for each other to wake up, causing a "deadlock"
The difference and relation between synchronization and mutual exclusion
  • The so-called mutual exclusion refers to three program fragments between different processes. When a process runs one of the program fragments, other processes cannot run any of them. They can only run after the process runs the program fragment. The so-called synchronization refers to a number of program fragments walking between different processes. Their operation must be carried out in strict accordance with a specified sequence, which depends on the specific tasks to be completed. Synchronization is a more complex mutex, and mutex is a special synchronization. In other words, mutual exclusion means that two threads cannot run at the same time. They will be mutually exclusive. One thread must wait for the other to run. Synchronization cannot run at the same time, but it must run the corresponding threads in a certain order (also a kind of mutual exclusion)

Tags: Linux Operating System kernel

Posted by Flying Sagittarius on Mon, 30 May 2022 20:48:02 +0530