利用线程和信号量模拟冰淇淋商店运营情况

发表于 更新于 分类于
斯坦福公开课《编程范式》中利用线程和信号量模拟了一个冰淇淋店运行情况，通过这个训练可以更深刻地理解如何通过信号量去同步线程

本文源于Stanford大学公开课《编程范式》第18讲中讲解的一个通过线程和信号量去模拟一个冰淇淋店的运营情况，我觉得很有意思，所以就着重的摘录实现了一下。

模型的角色分类

维持这个冰淇淋店运营模型的角色分为四类：

  • 管理员：负责检验操作员制作的冰淇淋是否合格，并给操作员一反馈，如果检验合格操作员把冰淇淋交给顾客；如果不合格操作员重新制作冰淇淋然后再找管理员检验，直到合格为止。假如：3个顾客没人请求了2个冰淇淋，管理员必须检验合格6个冰淇淋才算完成了自己的目标。假设：管理员只有一位，所以操作员们请求检验时存在竞争关系。
  • 操作员：负责接受顾客的请求，然后去制作冰淇淋然后找管理员去检验制作的冰淇淋是否合格，如果合格则将冰淇淋交给顾客；如果不合格则重新制作冰淇淋再次去找管理员检验，直到制作出合格的冰淇淋为止。假设：操作员的数量跟顾客请求的冰淇淋数量相同，在请求检验的时候操作员之间会竞争一个管理员。
  • 顾客：通过一个随机函数得到每个顾客需要的冰淇淋的数量，然后分派给几个操作员去制作这些冰淇淋，然后等待这几个操作员制作出合格的冰淇淋后，最后再去收银员那里去付款。假设：顾客的数量是固定的，顾客负责分派任务给操作员，需要几个冰淇淋就要起几个操作员线程去制作冰淇淋，等到这几个操作员给出合格的冰淇淋后，最后顾客拿着冰淇淋去找收银员付款，付款的过程顾客之间需要排队，先找到收银员的先结账，保持先进先出的原则。
  • 收银员：负责按照顺序给顾客结账。假设：收银员只有一个，所以顾客在付款的时候需要先竞争到收银员，先来的先结账后来的后结账。

关系图如下：

分析角色竞争关系建立数据结构

通过上面的描述我们知道了管理员与收银员只有一位，操作员会竞争管理员拿到进行检验的资格；顾客需要竞争收银员进行付款，但是顾客之间是先到先付款的关系，所以需要维持一个信号量数组来维持这个队列。

为了维持操作员对管理员的竞争关系，建立如下结构体以及其初始化函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 同步管理员检查的结构体
typedef struct {
    bool     passed;    // 操作员制作的冰淇淋是否合格的反馈标识
    signal_t request;   // 操作员发起检验信号量
    signal_t finish;    // 管理员检验完成信号量
    signal_t lock;      // 管理员资源竞争信号量
}inspect_s, *inspect_p;

void inspectNew(inspect_p inspect)
{
    inspect->passed = false;
    inspect->request = malloc(sizeof(signal_s));
    inspect->finish = malloc(sizeof(signal_s));
    inspect->lock = malloc(sizeof(signal_s));
}

为了维持顾客对收银员的竞争关系，并保证顾客先到先付款的队列关系，建立如下结构体以及其初始化函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 同步收银员收银的结构体
typedef struct{
    int      number;    // 当前结账顾客的队列编号
    signal_t request;   // 顾客发起结账信号量
    signal_t customers[kCountOfCustomers]; // 每一个顾客维持一个信号量保证顺序
    signal_t lock;      // 收银员竞争信号量
}payment_s, *payment_p;

void paymentNew(payment_p payment)
{
    payment->number = 0;
    payment->request = malloc(sizeof(signal_s));
    payment->lock = malloc(sizeof(signal_s));
    for (int i = 0; i < kCountOfCustomers; i++) {
        payment->customers[i] = malloc(sizeof(signal_s));
    }
}

为了使得输出信息后台输出更加完善易懂，我们定义了一下结构体，传递给顾客线程：

1
2
3
4
5
// 传递给customer线程的参数
typedef struct {
    int customerIndex;          // 顾客编号
    int numberOfRequestCreams;  // 该顾客请求冰淇淋数量
}customer_s, *customer_p;

为了使得信号量调试方便我们对信号量进行了简单的封装：

1
2
3
4
5
6
7
8
9
typedef struct{
    sem_t *sem;     // 信号量
    char *name;     // 名称标识
    int value;      // 当前信号量的值
}signal_s, *signal_t;

void initSignal(signal_t signal, char *name, int value); // open_sem
void waitSignal(signal_t signal);   // wait_sem
void postSignal(signal_t signal);   // post_sem

分析角色职责建立任务线程

  • 根据上面描述创建管理员线程：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 管理员线程
void *managerTask(void *creams)
{
    int totalCreams = (*(int *)creams); // 冰淇淋总数
    printf("管理员需要检验合格%d个冰淇淋\n" ,totalCreams);
    int numRefused = 0;     // 不合格的数量
    int numApproved = 0;    // 合格的数量
    int numInspect = 0;     // 检验的总次数
    
    while (numApproved < totalCreams) {
        waitSignal(inspect.request);    // 等待操作员发起检验请求
        numInspect++;
        printf("管理员正在检验第%d个冰淇淋\n" ,numInspect);
        inspect.passed = x_random(1);   // 0-1随机数决定是否合格
        
        if (inspect.passed){
            numApproved++;
            printf("%d个冰淇淋通过了检验\n", numApproved);
        }else{
            numRefused ++;
            printf("%d个冰淇淋未通过检验\n", numRefused);
        }
        postSignal(inspect.finish);     // 告诉操作员检验完成
    }
    
    return NULL;
}
  • 根据上面描述创建操作员任务线程：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 操作员线程
void *clerkTask(void *sem)
{
    bool passed = false;    // 检验是否合格的标识
    while (!passed) {       // 知道合格为止
        makeCream();
        waitSignal(inspect.lock);   // 竞争管理员资源

        postSignal(inspect.request);// 发起检验请求
        waitSignal(inspect.finish); // 等待检验结束
        passed = inspect.passed;    // 记录检验结果
        
        postSignal(inspect.lock);   // 释放管理员资源
    }
    
    postSignal(sem);                // 将合格的冰淇淋交给顾客
    
    return NULL;
}
  • 根据以上描述创建顾客任务线程：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 顾客线程
void *customerTask(void *customer)
{
    customer_s customerInfo = *(customer_p)customer;// 接受管理员信息
    int numberOfNeedCreams = customerInfo.numberOfRequestCreams;
    signal_s    clerkDone[numberOfNeedCreams];      // 创建信号量数组等待合格的冰淇淋
    pthread_t   clerk[numberOfNeedCreams];          // 创建操作员线程数组去制作冰淇淋
    for (int i = 0; i < numberOfNeedCreams; i ++) {
        char *name = malloc(sizeof(char *));        // 信号量命名
        sprintf(name, "clerk_done_%d", i);
        initSignal(&clerkDone[i], name, 0);
        
        // 执行操作员线程并将信号量传递过去 等操作员获取到合格的冰淇淋后 通过该信号量通知顾客
        pthread_create(&clerk[i], NULL, clerkTask, &clerkDone[i]);
        free(name);
    }
   
    // 等待所有的操作员都拿到合格的冰淇淋
    for (int i = 0; i < numberOfNeedCreams; i ++) {
        waitSignal(&clerkDone[i]);
    }
    
    walkToCashier(customerInfo);    // 去排队付款
    waitSignal(payment.lock);       // 竞争收银员资源
    int place = payment.number ++;  // 记录当前正在付款的顾客队列好
    
    postSignal(payment.request);    // 请求付款
    waitSignal(payment.customers[place]); // 等待收银员找钱
    
    postSignal(payment.lock);       // 释放收银员资源
    
    // 释放内存
    free(customer);
    for (int i = 0; i < numberOfNeedCreams; i ++) {
        pthread_join(clerk[i], NULL);
    }
    
    return NULL;
}
  • 根据以上描述创建收银员任务线程：
1
2
3
4
5
6
7
8
9
10
11
// 收银员线程
void *cashierTask()
{
    for (int i = 0; i < kCountOfCustomers; i ++) {
        waitSignal(payment.request);      // 等待付款请求
        collectMoney(i);                  // 找钱
        postSignal(payment.customers[i]); // 结账结束通知顾客
    }
    
    return NULL;
}
  • 最后在main函数中我们要启动管理员线程、收银员线程和顾客线程：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
int main(int argc, const char * argv[])
{
    srand((unsigned) time(0));  // 随机因子
    
    // 初始化全局数据
    inspectNew(&inspect);
    initSignal(inspect.request, "clerk_request", 0);
    initSignal(inspect.finish, "clerk_finish", 0);
    initSignal(inspect.lock, "clerk_lock", 1);
    paymentNew(&payment);
    initSignal(payment.request, "customer_request", 0);
    for (int i = 0; i < kCountOfCustomers; i ++) {
        char *name = malloc(sizeof(char *));
        sprintf(name, "customer_%d", i);
        initSignal(payment.customers[i] ,name, 0);
        free(name);
    }
    initSignal(payment.lock ,"customer_lock", 1);
    
    // 调起顾客线程
    int totalCreams = 0;
    pthread_t customer[kCountOfCustomers];
    
    for (int i = 0; i < kCountOfCustomers; i ++) {
        customer_p customerInfo = malloc(sizeof(customer_s));
        customerInfo->customerIndex = i;
        customerInfo->numberOfRequestCreams = x_random(kMaxCreamsPerCustomer) + 1;
        
        printf("第%d号顾客请求了%d个冰淇淋\n", i, customerInfo->numberOfRequestCreams);
        pthread_create(&customer[i], NULL, customerTask, customerInfo);
        
        totalCreams += customerInfo->numberOfRequestCreams;
    }
    
    // 调起管理员和收银员线程
    pthread_t manager;
    pthread_t cashier;
    
    pthread_create(&manager, NULL, managerTask, &totalCreams);
    pthread_create(&cashier, NULL, cashierTask, NULL);
    
    // 等待线程结束回收内存
    for (int i = 0; i < kCountOfCustomers; i ++) {
        pthread_join(customer[i], NULL);
    }
    pthread_join(manager, NULL);
    pthread_join(cashier, NULL);
    
    return 0;
}

编译运行输出结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
第0号顾客请求了1个冰淇淋
操作员正在制作第1冰淇淋
第1号顾客请求了1个冰淇淋
操作员正在制作第2冰淇淋
第2号顾客请求了3个冰淇淋
管理员需要检验合格5个冰淇淋
管理员正在检验第1个冰淇淋
操作员正在制作第3冰淇淋
操作员正在制作第4冰淇淋
操作员正在制作第5冰淇淋
1个冰淇淋通过了检验
第0号顾客的1个冰淇淋已经做好了,可以去找收银员付款了
管理员正在检验第2个冰淇淋
第0号顾客付款完毕
1个冰淇淋未通过检验
操作员正在制作第6冰淇淋
管理员正在检验第3个冰淇淋
2个冰淇淋未通过检验
操作员正在制作第7冰淇淋
管理员正在检验第4个冰淇淋
3个冰淇淋未通过检验
操作员正在制作第8冰淇淋
管理员正在检验第5个冰淇淋
2个冰淇淋通过了检验
管理员正在检验第6个冰淇淋
3个冰淇淋通过了检验
第1号顾客的1个冰淇淋已经做好了,可以去找收银员付款了
管理员正在检验第7个冰淇淋
第1号顾客付款完毕
4个冰淇淋通过了检验
管理员正在检验第8个冰淇淋
5个冰淇淋通过了检验
第2号顾客的3个冰淇淋已经做好了,可以去找收银员付款了
第2号顾客付款完毕

写在后面：
程序中可能还存在需要完善的地方，比如：我们可以给操作员多传一个参数，明确这是第几号顾客的冰淇淋；还有就是为了控制顾客排队结账而在struct payment结构体中为每一个顾客声明了一个信号量signal_t customers[...]，但是在收银员线程中却是用for循环去依次发信号的；我们还可以在每个角色任务线程中加入的函数(如makeCream()，walkToCasher()…)中通过绘图代码去绘制一些图画或动画，这样能够更加直观的展现冰淇淋店的运营情况，这些待完善的部分就交给大家去完成吧。

项目地址

0%