OS

OS-同步互斥lab

Posted by 慕念 on November 17, 2021

实验1 复旦理发师问题

现在在复旦南区有一家理发店，由于经营不善，店里只剩老板一个人，以及一把理发椅和 k 把供顾客等待坐的椅子，若店里无顾客，店里的理发师即在店里休息，当有第一个顾客到来时必须叫醒理发师，若顾客到来时理发师正在理发且有空椅子可以休息则坐下来等待， 否则就离开。

Question 1: 关系分析。请写出题目中存在的互斥和同步的关系。

Question 2: 上述关系可以抽象为几个进程？ 并写出 C 或 C++代码。

A：

理发师和每一位顾客都是一个进程。（由于顾客之间需要竞争理发师资源，所以每一个顾客都要单独看作一个进程）

【关系分析】

理发师进程：由于理发师一直在等待/理发，所以在while(1)循环中。理发师只有当第一个顾客到来时才会开始工作，如果当前没有顾客，则阻塞（所以这里需要一个顾客信号量）；如果有顾客，则顾客等待人数-1，空椅子数量+1。

顾客进程：当顾客进理发店时，如果没有空椅子，直接离开（结束进程）；如果有空椅子，则通知理发师一位顾客来了，并进行等待，等待人数+1，空椅子数量-1，等待到了理发师理完发就离开了。（所以不需要while循环）

由于理发师是一个被顾客抢占的资源，所以需要设置为一个信号量。未避免多个顾客同时到达，导致空椅子数量变化出错，需要一个互斥信号量进行保护。

根据上述分析，一共需要2个同步信号量：

  • ①barbers，用来记录理发师的资源是否可用，初值为0，即没有顾客时理发师处于休息状态；

  • ②customers，用来记录等待理发的顾客数，初值为0，阻塞理发师进程。

需要1个互斥信号量mutex，保护全局变量空椅子数量free_chair。

【伪代码】

#define CHAIRS k

semaphore barbers = 0;
semaphore customers = 0;
semaphore mutex = 1;

int free_chair = CHAIRS;

//理发师进程
process barber{
    while(1){
        wait(customers);//没有顾客，阻塞
        //有顾客即将得到服务，离开等待区，free_chair++，用mutex保护
        wait(mutex);
        free_chair++;
        //通知在等理发师的顾客进程，一个理发师资源被释放
        signal(barbers);
        signal(mutex);
        work();//理发师工作
	}	
}
//顾客进程
process customer{
	wait(mutex);//一次只能有一个顾客进程访问椅子，用mutex保护空椅子
	if(free_chair>0){//还有空椅子，进店等待，空椅子数量--
        free_chair--;
        signal(customers);//等待的顾客数量+1，如果是第一名顾客，则解除了理发师进程的阻塞
        signal(mutex);
        wait(barbers);//等待理发师，如果理发师正在忙碌，则阻塞
        consume();
	}else{//没有空椅子，直接离开
		signal(mutex);
	}	
}

【C】

#include <stdio.h>

#include <stdlib.h>

#include <unistd.h>

#include <pthread.h>

#include <sys/ipc.h>

#include <semaphore.h>

#include <fcntl.h>

//在semaphore.h中，sem_wait相当于wait，sem_post相当于signal

#define CHAIRS 5 //等待区椅子的数量

#define total_consumer 25 //顾客的总数（方便创建线程）

sem_t mutex, customers, barbers;
int free_chair = CHAIRS;
void barber();
void customer();

int main()
{
    //初始化信号量
    sem_init(&mutex, 0, 1);
    sem_init(&customers, 0, 0);
    sem_init(&barbers, 0, 0);

    int ret = 0;

    //初始化barber线程
    pthread_t barber_th;
    ret = pthread_create(&barber_th, NULL, (void *)barber, NULL);
    if (ret != 0)
        printf("barber线程创建失败\n");

    //初始化consumer线程
    int num = total_consumer; 
    pthread_t *tid;
    tid = malloc(num * sizeof *tid);
    for (int i = 0; i < num; i++){
        ret = pthread_create(&tid[i], NULL, (void *)customer, i);
        if (ret)
            printf("consumer[%d]号线程创建失败\n", i);
    }

    //先回收consumer，再回收barber
    for (int i = 0; i < num; i++)
        pthread_join(tid[i], NULL);
    
    pthread_join(barber_th, NULL);
    
    free(tid);
    return 0;
}

void barber()
{
    while (1)
    {
        sem_wait(&customers);
        sem_wait(&mutex);
        free_chair++;
        printf("[理发师理发]，顾客数量:%d，空椅子数量：%d\n", ((CHAIRS)-free_chair), free_chair);
        sem_post(&barbers);
        sem_post(&mutex);
        sleep(rand() % 2); //理发师工作
    }
}

void customer(int i)
{
    sleep(rand() % 5);
    sem_wait(&mutex);
    if (free_chair > 0)
    {
        free_chair--;
        printf("[顾客%d号等待]，顾客数量:%d，空椅子数量：%d\n", i, ((CHAIRS)-free_chair), free_chair);
        sem_post(&customers);
        sem_post(&mutex);
        sem_wait(&barbers);
    }
    else
    {
        printf("[没有空椅子，顾客%d号离开]\n", i);
        sem_post(&mutex);
    }
}

运行截图：

image-20211026220516529

实验2 直播间问题

假设旦旦的阿 B 直播间有 1,2,3 三部不同时代的校史纪录片可根据各位 b 站用户的选择来播放，播放规则如下：

1）任一时刻最多只能直播一部纪录片，正在直播的纪录片是自动循环播放的。为了省网费， 如果最后一名 b 站用户也退出了直播间，那么结束当前纪录片的放映。

2）选择了当前正在直播的纪录片的 b 站用户可立即进入，允许同时有多位选择同一纪录片的观众同时观看。阿 B 服务器很强，同时观看的观众数量不受限制。

3）等待观看其他纪录片的 b 站用户按到达顺序排队，当一部新的纪录片开始直播时，所有等待观看该纪录片的 b 站用户可依次序进入直播间同时观看。

用一个进程代表一个 b 站用户，要求：用信号量 PV 操作实现，并给出信号量定义和初始值。

Question 1: 关系分析。请写出题目中存在的互斥和同步的关系。

Question 2: 上述关系可以抽象为几个进程？ 并写出 C 或 C++代码。

A：

【关系分析】

对于三部纪录片而言，他们都是可以被观众进程抢占的资源，且彼此之间互斥（在放纪录片a时无法播放纪录片b、c，除非没有纪录片a的观众了），所以需要设置一个同步信号量live_room，在每一部纪录片播放之前需要阻塞该信号量，阻止另外两部纪录片播放。

接下来看直播间的具体行为：

①一开始没有观众的时候，三部纪录片都没有播放，信号量live_room初始化为1；

②当第一个观众进直播间时，根据该观众的意愿播放对应纪录片，释放对应直播间的信号量。这里观众进程类似于读者写者中的读优先，比如说：由第一个A观众代表A观众群体去竞争临界资源。所以还需要一个全局变量viewer_cnt_a记录A观众数量，并用互斥信号量mutex_a保持对其的访问是原子操作。（同理观众B、C）

③当第一个A观众竞争到资源时，所有阻塞在wait(mutex_a);的A观众进程都可以顺利执行，直到最后一位A观众离开。在此期间B、C观众都阻塞在wait(live_room);。

④当最后一位A观众离开时，释放live_room信号量，B、C观众竞争直播间资源。

根据上述分析，一共需要1个同步信号量live_room，当一部纪录片播放时，阻塞另外两部纪录片。

需要3个互斥信号量mutex_a,mutex_b,mutex_c，保护三个记录观众数量的全局变量：viewer_cnt_a,viewer_cnt_b,viewer_cnt_c。

可抽象为三个观众进程。

【伪代码】

/*其中wait()操作相当于P()，signal()相当于V()*/
int viewer_cnt_a=0;
int viewer_cnt_b=0;
int viewer_cnt_c=0;

semaphore live_room = 1;

semaphore mutex_a = 1;
semaphore mutex_b = 1;
semaphore mutex_c = 1;

//想看纪录片A的观众
process Viewer_A{
    while(1){
        wait(mutex_a);
        viewer_cnt_a++;
        if(viewer_cnt_a==1){//第一个参与竞争，去排队
            //阻塞直播间使用权
            wait(live_room);
            //纪录片A播放，此时由于直播间使用权在A手中，所以B、C无法播放
            Film_A_start();
        }
        signal(mutex_a);
        
        sleep();//随机观看一段时间后离开
        
        wait(mutex_a);
        viewer_cnt_a--;
        if(viewer_cnt_a==0){//最后一位离开，纪录片A停止播放，释放直播间使用权
            Film_A_end();
            signal(live_room);
        }
        signal(mutex_a);
	}	
}

//想看纪录片B的观众
process Viewer_B{
    while(1){
        wait(mutex_b);
        viewer_cnt_b++;
        if(viewer_cnt_b==1){//第一个参与竞争，去排队
            //阻塞直播间使用权
            wait(live_room);
            //纪录片B播放，此时由于直播间使用权在B手中，所以A、C无法播放
            Film_B_start();
        }
        signal(mutex_b);
        
        sleep();//随机观看一段时间后离开
        
        wait(mutex_b);
        viewer_cnt_b--;
        if(viewer_cnt_b==0){//最后一位离开，纪录片B停止播放，释放直播间使用权
            Film_B_end();
            signal(live_room);
        }
	}	
}

//想看纪录片C的观众
process Viewer_C{
    while(1){
        wait(mutex_c);
        viewer_cnt_c++;
        if(viewer_cnt_c==1){//第一个参与竞争，去排队
            //阻塞直播间使用权
            wait(live_room);
            //纪录片C播放，此时由于直播间使用权在C手中，所以A、B无法播放
            Film_C_start();
        }
        signal(mutex_c);
        
        sleep();//随机观看一段时间后离开
        
        wait(mutex_c);
        viewer_cnt_c--;
        if(viewer_cnt_c==0){//最后一位离开，纪录片B停止播放，释放直播间使用权
            Film_C_end();
            signal(live_room);
        }
	}	
}

【C】

实际上的代码对伪代码进行了一些改进，注释里有详细写出来。

#include <stdio.h>

#include <stdlib.h>

#include <unistd.h>

#include <pthread.h>

#include <sys/ipc.h>

#include <semaphore.h>

#include <fcntl.h>


int viewer_cnt_a = 0;
int viewer_cnt_b = 0;
int viewer_cnt_c = 0;

sem_t live_room, mutex_a, mutex_b, mutex_c;

void Viewer_A();
void Viewer_B();
void Viewer_C();

int main()
{
    //初始化信号量
    sem_init(&live_room, 0, 1);

    sem_init(&mutex_a, 0, 1);
    sem_init(&mutex_b, 0, 1);
    sem_init(&mutex_c, 0, 1);

    printf("------------直播间开启------------\n");
        
	// 如果三类观众分别都只创建一个线程，执行结果比较有规律
    // 基本上不发生当A纪录片播放时仍有A观众进入直播间的情况
    // 所以这里每类观众都创建了2个线程，以求让状况“混乱”一点贴近现实
    int ret = 0;
    int num = 2;
    pthread_t *tid_a, *tid_b, *tid_c;

    tid_a = malloc(num * sizeof *tid_a);
    tid_b = malloc(num * sizeof *tid_b);
    tid_c = malloc(num * sizeof *tid_c);
    
    for (int i = 0; i < num; i++)
    {
        ret = pthread_create(&tid_a[i], NULL, (void *)Viewer_A, NULL);
        if (ret)
            printf("Viewer_A[%d]号线程创建失败\n", i);
        ret = pthread_create(&tid_b[i], NULL, (void *)Viewer_B, NULL);
        if (ret)
            printf("Viewer_B[%d]号线程创建失败\n", i);
        ret = pthread_create(&tid_c[i], NULL, (void *)Viewer_C, NULL);
        if (ret)
            printf("Viewer_C[%d]号线程创建失败\n", i);
    }

    for (int i = 0; i < num; i++)
    {
        pthread_join(tid_a[i], NULL);
        pthread_join(tid_b[i], NULL);
        pthread_join(tid_c[i], NULL);
    }

    return 0;
}
//想看纪录片A的观众
void Viewer_A()
{
    int i;
    while (1)
    {
        sleep(rand() % 3);
        i = 1 + rand() % (4 - 1); //随机来1-3位观众
        sem_wait(&mutex_a);
        viewer_cnt_a += i;
        printf("%d位A观众进入直播间,当前有%d位A观众。\n", i, viewer_cnt_a);
        if (viewer_cnt_a == i)
        { //表明是第一批来的，参与竞争，去排队
            //阻塞直播间使用权
            sem_wait(&live_room);
            //纪录片A播放，此时由于直播间使用权在A手中，所以B、C无法播放
            printf("---------纪录片A开始播放----------\n");
        }
        sem_post(&mutex_a);

        sleep(rand() % 3); //随机观看一段时间后离开

        sem_wait(&mutex_a);
        viewer_cnt_a -= i;
        printf("%d位A观众离开直播间,当前有%d位A观众。\n", i, viewer_cnt_a);
        if (viewer_cnt_a == 0)
        { //最后一位离开，纪录片A停止播放，释放直播间使用权
            printf("---------纪录片A结束播放----------\n");
            sem_post(&live_room);
        }
        sem_post(&mutex_a);
    }
}

void Viewer_B()
{
    int i;
    while (1)
    {
        sleep(rand() % 3);
        i = 1 + rand() % (4 - 1); //随机来0-2位观众
        sem_wait(&mutex_b);
        viewer_cnt_b += i;
        printf("%d位B观众进入直播间,当前有%d位B观众。\n", i, viewer_cnt_b);
        if (viewer_cnt_b == i)
        { //第一批参与竞争，去排队
            //阻塞直播间使用权
            sem_wait(&live_room);
            //纪录片B播放，此时由于直播间使用权在B手中，所以A、C无法播放
            printf("---------纪录片B开始播放----------\n");
        }
        sem_post(&mutex_b);

        sleep(rand() % 3); //随机观看一段时间后离开

        sem_wait(&mutex_b);
        viewer_cnt_b -= i;
        printf("%d位B观众离开直播间,当前有%d位B观众。\n", i, viewer_cnt_b);
        if (viewer_cnt_b == 0)
        { //最后一位离开，纪录片B停止播放，释放直播间使用权
            printf("---------纪录片B结束播放----------\n");
            sem_post(&live_room);
        }
        sem_post(&mutex_b);
    }
}

void Viewer_C()
{
    int i;
    while (1)
    {
        sleep(rand() % 3);
        i = 1 + rand() % (4 - 1);
        sem_wait(&mutex_c);
        viewer_cnt_c += i;
        printf("%d位C观众进入直播间,当前有%d位C观众。\n", i, viewer_cnt_c);
        if (viewer_cnt_c == i)
        { //第一个参与竞争，去排队
            //阻塞直播间使用权
            sem_wait(&live_room);
            //纪录片C播放，此时由于直播间使用权在C手中，所以A、B无法播放
            printf("---------纪录片C开始播放----------\n");
        }
        sem_post(&mutex_c);

        sleep(rand() % 3); //随机观看一段时间后离开

        sem_wait(&mutex_c);
        viewer_cnt_c -= i;
        printf("%d位C观众离开直播间,当前有%d位C观众。\n", i, viewer_cnt_c);
        if (viewer_cnt_c == 0)
        { //最后一位离开，纪录片C停止播放，释放直播间使用权
            printf("---------纪录片C结束播放----------\n");
            sem_post(&live_room);
        }
        sem_post(&mutex_c);
    }
}

运行截图：

image-20211103171316503

实验3 哲学家就餐问题(半开放编程)

补充完整 lab3_synchronization 中 philosopher、pickup、putdown 函数的代码， 模拟哲学家就餐问题，让程序正确运行并同时注意同步与互斥的问题。（可参考链接：https://blog.csdn.net/thelostlamb/article/details/80741319）。在报告中言简意赅地介绍你使用的方法及代码实现思路，并附上成功运行地截图。

如果需要，可以在 philosopher.h 与 philosopher.c 中定义变量与函数。本程序可以在linux 环境中运行，如果缺少依赖，请大家自行安装。

A：

哲学家就餐问题中：发生死锁只可能由于五位哲学家同时拿起了一边的筷子，只要避免这种状况的发生就能解决死锁。

【Plan A】

核心思路：最多只允许4位哲学家同时拿起一边的筷子。这样至少有1位哲学家可以拿到两根筷子完成进食并释放资源。所以不会造成死锁/活锁。

代码实现：需要一个信号量leftchop初始化为4，当4位哲学家拿起左边的筷子后，信号量已经减为0，如果第5位哲学家想要拿起左边的筷子，信号量减为-1，阻塞，即无法拿起左边的筷子，避免了死锁。每当一个哲学家放下左边的筷子，则信号量leftchop++。

/*philosopher.h*/
#include <semaphore.h>

sem_t leftchop; //声明leftchop信号量

/*main.c*/
sem_init(&leftchop, 0, 4); //leftchop初始化为4

/*philosopher_planA.c*/
void pickUp(int philosopherNumber)
{
	/*Your code here*/
	// 哲学家拿起左边的筷子时，P(leftchop)
	// 保证了最多只能4位哲学家同时拿起左边的筷子
	// 并且对于筷子这五个临界资源，分别用pthread_mutex_lock()加互斥锁
	// sem_wait(&leftchop)写在这里或者philosopher()中都可以
	sem_wait(&leftchop);
	pthread_mutex_lock(&chopsticks[philosopherNumber]);
	pthread_mutex_lock(&chopsticks[(philosopherNumber + 1) % NUMBER_OF_PHILOSOPHERS]);
}

void putDown(int philosopherNumber)
{
	/*Your code here*/
	// 当哲学家用餐完毕放下筷子时，给临界资源筷子解锁
	// 当放下左边的筷子时就可以释放信号量，V(leftchop)
	pthread_mutex_unlock(&chopsticks[philosopherNumber]);
	sem_post(&leftchop);
	pthread_mutex_unlock(&chopsticks[(philosopherNumber + 1) % NUMBER_OF_PHILOSOPHERS]);
}

运行截图：

image-20211028103411504

经过多次测试，没有发生死锁。

【Plan B】

核心思路：仅当哲学家的左右两支筷子都可用时，才允许他拿起筷子进餐。即如果想给某个哲学家筷子，就将他需要的所有资源都给他，否则就一个都不给他。

代码实现：增加一个互斥信号量mutex对拿起左筷子和右筷子进行保护，使这两个动作变成原子操作。

/*philosopher.h*/
sem_t mutex;; //声明mutex信号量

/*main.c*/
sem_init(&mutex, 0, 1); //mutex初始化为4

/*philosopher_planB.c*/
void pickUp(int philosopherNumber)
{
	/*Your code here*/
	// 用mutex对拿左右筷子进行保护
	printf("Philosopher %d wait...\n", philosopherNumber);
	sem_wait(&mutex);
	printf("Philosopher %d lock all chopsticks, and then pick\n", philosopherNumber);
	pthread_mutex_lock(&chopsticks[philosopherNumber]);
	pthread_mutex_lock(&chopsticks[(philosopherNumber + 1) % NUMBER_OF_PHILOSOPHERS]);
	sem_post(&mutex);
	printf("Philosopher %d unlock chopsticks\n", philosopherNumber);
}


void putDown(int philosopherNumber)
{
	/*Your code here*/
	// 放下筷子则不需要额外信号量保护
	pthread_mutex_unlock(&chopsticks[philosopherNumber]);
	pthread_mutex_unlock(&chopsticks[(philosopherNumber + 1) % NUMBER_OF_PHILOSOPHERS]);
	printf("Philosopher %d put down chopsticks\n", philosopherNumber);
}

运行截图：

image-20211028164752985

【Plan C】

核心思路：规定奇数号哲学家先拿起左边的筷子，再拿右边的筷子；而偶数号哲学家相反，先拿起右边的筷子，再拿左边的筷子（放下筷子时，顺序同理）。这样，假设0号、1号哲学家同时思考完毕，他们都将竞争1号筷子，必然有一位没有竞争到，无法用餐。避免了五位哲学家同时拿起一边的筷子的死锁情况，总会有一个哲学家能获得两支筷子，完成进餐。

image-20211028193521021

代码实现：

这种做法不需要增加额外的信号量，只需要用pthread_mutex_lock()保护5支筷子（5个临界资源）。

/*philosopher.c*/
void pickUp(int philosopherNumber)
{
	/*Your code here*/
	int i = philosopherNumber;
	int left = i;
	int right = (i + 1) % NUMBER_OF_PHILOSOPHERS;
	if (i % 2 != 0)
	{ //奇数哲学家，先左后右拿起筷子
		pthread_mutex_lock(&chopsticks[left]);
		pthread_mutex_lock(&chopsticks[right]);
		printf("[ODD]Philosopher %d pick up chopsticks\n", i);
	}
	else
	{ //偶数哲学家，先右后左拿起筷子
		pthread_mutex_lock(&chopsticks[right]);
		pthread_mutex_lock(&chopsticks[left]);
		printf("[EVEN]Philosopher %d pick up chopsticks\n", i);
	}
}


void putDown(int philosopherNumber)
{
	/*Your code here*/
	int i = philosopherNumber;
	int left = i;
	int right = (i + 1) % NUMBER_OF_PHILOSOPHERS;
	if (i % 2 != 0)
	{ //奇数哲学家，先左后右放下筷子
		pthread_mutex_unlock(&chopsticks[left]);
		pthread_mutex_unlock(&chopsticks[right]);
		printf("[ODD]Philosopher %d put down chopsticks\n", i);
	}
	else
	{ //偶数哲学家，先右后左放下筷子
		pthread_mutex_unlock(&chopsticks[right]);
		pthread_mutex_unlock(&chopsticks[left]);
		printf("[EVEN]Philosopher %d put down chopsticks\n", i);
	}
}

运行截图：

image-20211028202201883

CATALOG
    FEATURED TAGS
    安全攻防综合实验 OS 信息系统安全 SeedLab watermark Coding