第四组 线程的同步与互斥

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. 利用用户空间计数变量 countA、countB、numEmpty，配合信号量 mutexA、mutexB、mutexEmpty，统计工作台中零件 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 实验算法

我采用的是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，取得numEmpty和countA的值,不仅需要空工位数>=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;
}