【北邮大三上操作系统】第四组 线程的同步与互斥

发布于 2023-07-21  1404 次阅读


第四组 线程的同步与互斥

1 题目

An assembly line is to produce a product C with n1=4 part As, and n2=3 part Bs. The worker of machining A and worker of machining B produce m1=2 part As and m2=1 part B independentlyeach time. Then the m1 part As or m2 part B will be moved to a station, which can hold at most N=12 of part As and part Bs altogether. The produced m1 part As must be put onto the station simultaneously. The workers must exclusively put a part on the station or get it from the station.

In addition, the worker to make C must get all part of As and Bs, i.e. n1 part As and n2 part Bs, for one product C once. Using semaphores to coordinate the three workers who are machining part A, part B and manufacturing the product C without deadlock.

It is required that

(1) definition and initial value of each semaphore, and
(2) the algorithm to coordinate the production process for the three workers should be given.

2 实验目的

通过编写程序实现进程同步和互斥,使学生掌握有关进程(线程)同步与互斥的原理,以及解决进程(线程)同步和互斥的算法,从而进一步巩固进程(线程)同步和互斥

3 实验内容

Pthread/POSIX 提供了两种线程同步互斥机制:互斥锁和信号量,互斥锁相当于教科书中的 binary semphore,取值为 0、1;信号量则是教科书中的 counting semaphore,取值为整数。
信号量为教科书中所述的 counting semaphore,即计数信号量,即可用于进程/线程间互斥、也可以应用于进程间同步。

进程/线程通过 wait()、signal 操作(或、PV 操作),改变信号量的值,获取共享资源的访问权限,实现进程/线程同步互斥。经典的同步互斥问题有:生产者-消费者问题,读写者问题,哲学家就餐问题。
Pthread 线程库提供的信号量访问操作有:

  • sem_init(),创建一个信号量,并初始化它的值;
  • sem_wait()sem_trywait(),相当于 wait/P 操作,在信号量>0 时,它们能将信号量的值减 1。两者的区别在于信号量<0 时,sem_wait() 将会阻塞进程/线程,而sem_trywait 则会立即返回。
  • sem_post(),相当于 signal/V 操作,它将信号量的值加 1,同时发出信号来唤醒等待的进程/线程。
  • sem_getvalue(),得到信号量的值。
  • sem_destroy(),删除信号量。

4 实验设计原理

4.1 实验思路

  1. 利用用户空间计数变量 countAcountBnumEmpty,配合信号量 mutexAmutexBmutexEmpty,统计工作台中零件 A、零件 B、空单元的数目,当有足够多的零件 A、B和工作台空位时,再一次性申请/获取多个所需的零件 A、零件 B、工作台空位,即将 workerA 所需的 2个工作台空位作为一个整体一次性地申请,worker C 所需的工作台中的 4个 A和3个 B 作为一个整体一次性地申请;
  2. 当所需工作台空位不满足时,worker A 和 worker B 应主动阻塞自身(suspend/block),防止忙等待。当 worker C 所需的工作台中 A 和 B 不满足时,也应主动阻塞自身;
  3. 当 worker A、worker B 分别生产并放入新的零件 A、B 后,考虑唤醒由于所需零件不足而处于阻塞态的 worker C;同样地,当 worker C 从工作台取出零件 A、零件 B 后,考虑唤醒因没有足够空位而处于阻塞态的 worker A、worker B。

4.2 实验算法

6884b128c1946751ae94849fe0d1c206.png

我采用的是PTHREAD信号量来实现线程的同步与互斥。

信号量,初始值均为1

sem_t mutexA;
sem_t mutexB;
sem_t mutexEmpty;

全局变量

int countA = 0;//已完成A的数量
int countB = 0;//B
int numEmpty = 12;//空工位数

workerA/B/C需要申请修改NUMEMPTY的权限,一次只能由一个人修改,workerA想要一次性生产两个零件,首先需要被允许进入缓冲区A,取得numEmptycountA的值,不仅需要空工位数>=2同时也要满足countA<=6,剩下的位置无法再将A元件和B元件组装起来。workerB和workerA基本同理。

workerC则需要一次得到4个A零件和3个B零件,获得修改Numepty的权限后,同样需要被允许进入缓冲区A和缓冲区B,如果A零件个数>=4,B>=3,则取出零件并组装,释放空位。

5 实验步骤

打开vim文本编辑器,编写代码

编译

执行命令gcc worker.c -o worker -lpthread

运行结果

6 实验结果及分析


分析:程序可以稳定运行一段时间,输出符合问题结果。

7 程序代码

#include <stdlib.h>
#include <stdio.h>
#include <semaphore.h>
#include <pthread.h>
#include <errno.h>

/* 全局变量 */
int countA = 0;//已完成A的数量
int countB = 0;//B
int numEmpty = 12;/*空工位数*/

/*信号量 */
sem_t mutexA;
sem_t mutexB;
sem_t mutexEmpty;

/* 声明线程运行服务程序. */
void* workerA(void) {
    while (1) {
        sem_wait(&mutexEmpty);
        sem_wait(&mutexA);
        if (numEmpty >= 2 && countA <= 6) {//对countA进行限制,否则B没有空间生产,会造成死锁
            countA += 2;
            numEmpty -= 2;
            printf("====workerA====\n");
            printf("countA:%d empty=%d\n", countA, numEmpty);
        }
        sem_post(&mutexA);
        sem_post(&mutexEmpty);
    }
}
void* workerB(void) {
    while (1) {
        sem_wait(&mutexEmpty);
        sem_wait(&mutexB);
        if (numEmpty >= 1 && countB <= 7) {
            countB++;
            numEmpty--;
            printf("====workerB====\n");
            printf("countB:%d empty=%d\n", countB, numEmpty);

        }
        sem_post(&mutexB);
        sem_post(&mutexEmpty);
    }
}
void* workerC(void) {
    while (1) {
        sem_wait(&mutexEmpty);
        sem_wait(&mutexA);
        sem_wait(&mutexB);
        if (countA >= 4 && countB >= 3) {
            countA -= 4;
            countB -= 3;
            numEmpty += 7;
            printf("====workerC====\n");
            printf("countA:%d countB:%d empty=%d\n", countA, countB, numEmpty);
        }
        sem_post(&mutexA);
        sem_post(&mutexB);
        sem_post(&mutexEmpty);
    }
}
int main(void)
{
    /*线程的标识符*/
    pthread_t A, B, C;
    int ret = 0;

    /* 初始化信号量 */
    sem_init(&mutexA, 0, 1);  //信号量初始化
    sem_init(&mutexB, 0, 1);
    sem_init(&mutexEmpty, 0, 1);
    /*分别创建线程ABC*/
    ret = pthread_create(&A, NULL, (void*)workerA, NULL);
    if (ret != 0)
    {
        perror("workerA_create");
    }
    ret = pthread_create(&B, NULL, (void*)workerB, NULL);
    if (ret != 0)
    {
        perror("workerB_create");
    }
    ret = pthread_create(&C, NULL, (void*)workerC, NULL);
    if (ret != 0)
    {
        perror("workerB_create");
    }
    sleep(3);
    /*等待线程ABC的结束*/
    pthread_join(A, NULL);
    pthread_join(B, NULL);
    pthread_join(C, NULL);

    return 0;
}