Celery's Blog

0%

semaphore

发表于 Valine：

信号量编程(模板)

  • 试解释为什么在单处理器系统的用户进程中通过屏蔽中断来实现同步是不合理的？

    如果用户进程具有屏蔽中断的功能，那么它可以同样屏蔽计时器，没有时钟中断则分派程序无法进行，进程会无限执行

  • 试解释为什么在多处理器系统中无法通过屏蔽中断来实现同步

    屏蔽中断仅仅阻止其他进程在被屏蔽了中断的处理器上运行，其他进程可能在其他处理器上运行。

先记住wait()和signal()的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
wait(semaphore *S) {
	S->value--;
	if(S->value < 0) {
        add this process to S->list;
        block();
    }	
}

signal(semaphore *S) {
    S->value++;
    if(S->value <= 0) {
        remove a process P from S->list;
        wakeup(P);
    }
}

经典同步问题

有限缓冲区——生产者、消费者问题

  • 进程互斥中的生产者-消费者问题可以通过三个信号量解决
    • 二进制信号量mutex保证了对缓冲区访问的互斥
    • 计数信号量empty和full表示缓冲区中空余数量和已有数据数量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// procuder
do {
    // produce an item
    wait(empty);
    wait(mutex);
    // put item into buffer
    signal(mutex);
    signal(empty);
} while(true);

// customer 
do {
    wait(full);
    wait(mutex);
    // remove an item from buffer
    signal(mutex);
    signal(empty);
} while(true);

读者-写者问题

  • 读者优先，如果当前获得数据库权限的是读者进程，则其他读者进程无需等待，读者进程只有在当前操作数据库的进程是写者的情况下才需要阻塞
  • 写者有限，任何在等待获取数据库权限的写者进程都将比其他正在等待的读者进程先获得权限
  • 前两种策略回到这写者或者读者饿死的情况，第三种策略保证没有任何进程会被无限阻塞
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
// 读者优先
semaphore mutex, wrt;
int readcount;
// 读者进程
do {
    wait(mutex);
    readcount++;
    if(readcount == 1) {
        wait(wrt);
    }
    signal(mutex);
    // 读者访问
    wait(mutex);
    readcount--;
    if(readcount == 0) {
        signal(wrt);
    }
    signal(mutex);
} while(true);
// 写者
do {
    wait(wrt);
    // 执行写操作
    signal(wrt);
} while(true);

读写公平

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
int count = 0;			// 用于记录当前的读者数量
semaphore mutex = 1;	// 用于保护更新count变量时的互斥
semaphore rw = 1;		// 用于保证读者和写者互斥地访问文件
semaphore w = 1;		// 用于实现"写优先" 
// 读者
wait(w)
wait(mutex);
count++;
if(count == 0) {
  	wait(rw); 
}
signal(mutex);
signal(w);
reading;
wait(mutex);
count--;
if(count == 0) {
    signal(rw);
}
signal(mutex);
// 写者
wait(w);
wait(rw);
writing;
signal(rw);
signal(w);
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
// 写者有限
int readcount = 0, writecount = 0;	// readcount记录当前正在等待读对象的读者数量，writecount记录当前正在等待写对象的写者数量，均初始化为0
semaphore rmutex = 1, wmutex = 1;	// 确保更新变量readcount和writecount时的互斥，均初始化为1
semaphore readTry;	// readTry信号量用于声明有读者加入等待队列，确保读者和写者之间的互斥
remaphore resource; //	resource信号量用于确保写者和写者之间的互斥
// 读者
do {
    wait(readTry);
    wait(rmutex);
    readcount++;
    if(readcount == 1) {
        wait(resource);	// 第一个读者需要获取资源权限
    }
    signal(rmutex);
    signal(readTry);
    // 临界区
    wait(rmutex);
    readcount--;
    if(readcount == 0) {
        signal(resource);
    }
    signal(rmutex);
} while(true);

// 写者
do {
    wait(wmutex);
    writecount++;
    if(writecount == 1) {	// 第一个写者需要与读者竞争资源
        wait(readTry);
    }
    signal(wmutex);
    // 进入临界区
    wait(resource);
    // 写操作
    signal(resource);
    // 离开临界区
    wait(wmutex);
    writecount--;
    if(writecount == 0) {
        signal(readTry);
    }
    signal(wmutex);
} while(true);

哲学家就餐问题

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
enum {thinking, hungry, eating} state[5];	// 记录每个人的状态
semaphore mutex = 1;	// 临界区互斥，保证每个时刻最多只能有一个人执行从餐桌上取或者放两把叉子的动作
semaphore self[5] = {0};	// 哲学家信号量，表明i是否已经获得2把刀叉并可以开始进餐

void philosophere(int i) {
    while(true) {
        thinking();	// 剩余段，思考
        pickup(i);	// 进入段，同时获取两把叉子或阻塞
        eating();	// 临界段：进餐
        putdown(i);	// 退出段，放下两把叉子   
    }
}

void pickup(int i) {
    wait(mutex);	// 申请访问餐桌，进入临界区
    state[i] = hungry;
    test[i];
    signal(mutex);
    wait(self[i]);
}

void test(int i) {
    if((state[(i + 4) % 5] != eating) && (state[i] == hungry) && (state[(i + 1) % 5] != eating)) {
        state[i] = eating;
        signal(self[i]);
    }
}

void putdown(int i) {
    wait(mutex);
    state[i] = thinking;
    test[(i + 1) % 5];
    test[(i + 4) % 5];
    signal(mutex);
}

另一种解法：

1
2
3
4
5
6
7
8
9
10
11
semaphore chopisticks[5] = {1, 1, 1, 1, 1};	// 初始化信号量
semaphore mutex = 1;
P(int i) {	// 第i个哲学家的进程
    wait(mutex);
    wait(chopisticks[i]);
    wait(chopisticks[(i + 1) % 5]);
    signal(mutex);
    eat;
    signal(chopisticks[i]);
    signal(chopisticks[(i + 1) % 5]);
}

睡眠理发师问题

理发店有一位理发师，一把理发椅和n把供等待理发的顾客坐的椅子。如果没有顾客，理发师便在理发椅上睡觉，一个顾客到来时，顾客必须叫醒理发师，如果理发师正在理发时又有顾客到来，则如果有空椅子可坐，就坐下来等待，否则就离开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int chairs = N;
int waitings = 0;
semaphore mutex;	// 对等待理发的人数的互斥修改
semaphore customer;
semaphore barber;
// 顾客
wait(mutex);
if(waiting < chairs) {
    waitings++;
    signal(customer);
    signal(mutex);
    wait(barber);
    理发;
} else {
    signal(mutex);
}
// 理发师
wait(customer);
wait(mutex);
waitings--;
signal(mutex);
signal(barber);	// 开放临界区
理发;

考研题详解

1. 单向行驶问题

有桥如图所示，车辆方向如箭头所示，回答如下问题
(1) 假设该桥上每次只能有一辆车行驶，试用信号灯的wait(), signal()操作实现交通管理
(2) 假设该桥上不允许辆车交会，但允许同方向多个车一次通过(即桥上可由多个同方向行驶的车)。试用信号灯的wait(), signal()操作实现交通管理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
semaphore bridge = 1; // 对桥的控制权
semaphore north_mutex = 1;	// 北边的控制权
semaphore south_mutex = 1;	// 南边的控制权
int count1 = 0;	// 记录从北边来的车辆的数量
int count2 = 0;	// 记录从南边来的车辆的数量
void car_from_north() {
    wait(north_mutex);
    count1++;
    if(count1 == 1) {
        wait(bridge);
    }
    signal(north_mutex);
    // 过桥
    wait(north_mutex);
    count1--;
    if(count1 == 0) {
        signal(bridge);
    }
    signal(north_mutex);
}
// 南边与北边对称

2.士兵过桥问题

独木桥的左右两端各停留一队士兵，左侧有 m 个，右侧有 n 个。两侧士兵均可上桥，但一旦有一侧士兵上桥，另一侧士兵必须等待已上桥一侧的士兵全部通过后才可上桥。试使用信号量描述此过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int left = 0, right = 0;	// 记录左右两侧已经通过的士兵数目
semaphore left_mutex = right_mutex = 1;	// 控制两队士兵数量的读写互斥
semophore bridge = 1;	// 控制桥的资源
// 左侧士兵
do {
    wait(left_mutex);
    left++;
    if(left == 1) {
        wait(bridge);
    }
    signal(left_mutex);
    // 过桥
    if(left == m) {
        signal(bridge);
    }
} while(true)

3. 双向有限行驶问题

在南开大学和天津大学之间有一条小路 S -> T，小路中间有一个安全岛 M，安全岛能够同时容纳两辆自行车，可供两个已经从两端进入小路的自行车错车用。整个地图如下图，S 到 K 段的小路和 T 到 L 段的小路同时都只能允许一辆自行车通过。试设计一个算法，使来往的自行车都能顺利通过。

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
semaphore S = T = 1;	// 两端最多允许进入一辆
semaphore SK = LT = 1;	// 两段小路最多允许进入一辆
// 从S口进入的自行车
do {
    wait(S);
    wait(Sk);
    // 通过S-K一段小路
    signal(SK);
    // 进入安全岛
    wait(LT);
    // 通过L-T一段小路
    signal(LT);
    signal(S);
} while(true);
// T口进入的自行车与S口进入的自行车对称

4. 理发店问题

一个理发店配有一个有 10 个椅子的休息室和一个有理发椅的理发室。如果没有顾客则理发师睡觉；如果顾客来了而休息室、理发椅都没有空则离开；如果理发师在忙而有空的椅子，则顾客选择一个坐下等待；如果理发师在睡觉则顾客摇醒他。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int count = 11;	// 空闲的椅子数量
semaphore mutex = 1;	// 对椅子数量的修改互斥
semaphore barber_chair = 1;	// 理发师的互斥，同时只能给一个人理发
semaphore customers = 0;	// 顾客人数
// 顾客
do {
    wait(mutex);
    if(count == 0) {
        signal(mutex);
        return ;
    }
    if(count == 11) {
        signal(customer);
        // 唤醒barber
    }
} while(true)

5. 上机实习问题

某高校计算机系安排学生上机实习，机房共 30 台机器，有超过 60 名学生选课。规定每两个学生一组，一组占一台机器，协同完成实习。只有凑够两个学生且机房仍有空闲机器的情况下，门卫才允许该组学生进入机房。每组上机实习结束时需要由一名固定的老师检查完毕后，该组学生才可离开。

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
int count = 0;	// 开始时在机房等候的学生人数
semaphore mutex = 1;	// 修改学生人数的互斥信号量
semaphore teacher = 1;	// 验收的老师
semaphore machine = 30;	// 30台机器

// 学生进程
do {
    wait(mutex);
    count++;
    int id = count;	// 记录自己的序号
    if(count % 2 == 0) {	// 偶数号的学生
        wait(machine);
    }
    signal(mutex);
    // 上机
    // 上机完成，等待验收
    wait(teacher);
    // 验收
    if(temp % 2 == 0) {
        signal(machine);	// 由偶数号的学生释放机器
        wait(mutex);
        count -= 2;		// 一组学生离开
        signal(mutex);
    }
} while(true)

6. 吸烟者问题

假设一个系统有 3 个吸烟者进程和一个供应商进程，制造一根香烟需要三种材料各一份。三个吸烟者分别无限量的拥有三种材料中的一种。供应商进程可以无限量的供应这三种材料，一旦一个吸烟者想吸烟，则他向供应商发出请求，供应商会为这个吸烟者提供另外两种材料。供货商同时只能为一个吸烟者提供服务，多个吸烟者同时发出请求时按固定顺序服务。如此循环往复，请用信号量编写程序控制四个进程同步执行。

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
bool smoker1, smoker2, smoker3;	// 分别表示1、2、3这三个吸烟者
semaphore a = b = c = 0;	// 初始供应的三种材料数量，1、2、3分别持有a、b、c类型的材料
semaphore smoker_request = 1;	// 吸烟者发出请求的权限

// 供应商
do {
    if(smoker1 == true) {
        signal(b);
        signal(c);
    }
    if(smoker2 == true) {
        signal(a);
        signal(c);
    }
    if(smoker3 == true) {
        signal(b);
        signal(c);
    }
} while(true);

// 吸烟者1
do {
    wait(smoker_request);
    smoker1 = true;
    wait(b);
    wait(c);
    signal(smoker_request);
} while(true);

7. 苹果-句子或老虎与猪

有一个笼子可以容纳一只老虎或者两只猪，如果笼子中已经有猪，则老虎不能被放入。猎人 A 每次向笼子中放入一只老虎，猎人 B 每次向笼子中放入一只猪。饲养员每次会从笼子中取出一只老虎，厨师每次会从笼子中取出一只猪。对笼子的操作是互斥的。试用信号量描述此过程。

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
semaphore pig = 0, tiger = 0;	//  对猪和老虎的互斥访问
semaphore coop = 1;	// 对笼子的互斥读写
semaphore pig_space = 2;	// 用于限制可以放置猪的剩余空间
semaphore pig_count_mutex = 1;	// 用于限制对pig_count的互斥读写
int pig_count = 0;	// 记录当前在笼子中的猪的数量

// 猎人A
do {
    // 抓到一只老虎
    wait(coop);
    // 将老虎放入笼子
    signal(tiger);
} while(true);
// 饲养员
do {
    wait(tiger);
    // 从笼子中取出老虎
    signal(coop);
} while(true);
// 猎人B
do {
    // 抓到一只猪
 	wait(pig_space);
    wait(pig_count_mutex);
    pig_count++;
    if(pig_count == 1) {
        wait(coop);
    }
    // 将猪放进笼子
    signal(pig);
    signal(pig_count_mutex);
} while(true);
// 厨师
do {
    wait(pig);
    wait(pig_count_mutex);
    // 从笼子中取出一只猪
    pig_count--;
    if(pig_count == 0) {
        signal(coop);
    }
    signal(pig_count_mutex);
    signal(pig_space);
} while(true);

8.

三个进程P1、P2、P3互斥使用一个包含N（N>0）个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元。P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数。P3每次用geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明定义的信号量的含义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
semaphore mutex;	// 用于对缓冲区的互斥读写
semaphore odd, even;	// 计数和偶数的计数信号量
semaphore empty = N;	// 空余的缓冲区的数量
// P1进程
wait(empty);
x = produce();
wait(mutex);
put();
signal(mutex);
if(x % 2 == 0) {
    signal(odd);
} else {
    signal(even);
}
// P2进程
wait(odd);
wait(mutex);
getodd();
signal(mutex);
signal(empty);
countodd();
// P3进程与P2同理

9.

在一个仓库可以存放A和B两种产品，要求：

  • 每次只能存入一种产品
  • A产品数量 - B产品数量 < M
  • B产品数量 - A产品数量 < N

描述产品A与产品B的入库过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
semaphore mutex;	// 商品入库过程的互斥
semaphore Sa = M - 1, Sb = N - 1;
int countA = 0, countB = 0;

// A产品进仓库过程
wait(Sa);
wait(mutex);
A产品入库;
signal(mutex);
signal(Sb);
// B产品入库
wait(Sb);
wait(mutex);
B产品入库;
signal(mutex);
signal(Sa);

10.

面包师有很多面包，由n个销售人员推销，每个顾客进店后取一个号，并且等待叫号，当一个销售人员空闲下来时，就叫下一个号，试设计一个使销售人员和顾客同步的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int i = 0, j = 0;	// i表示取号值，j表示叫号值
semaphore mutex_i, mutex_j;
// 顾客进程
wait(mutex_i);
取号;
i++;
signal(mutex_i);
等待叫号i并购买面包;
// 销售员进程
wait(mutex_j);
if(j < i) {
    叫号;
    j++;
    signal(mutex_j);
    销售面包;
} else {
    signal(mutex_j);
    休息片刻;
}

11.

设自行车生产线上有一只箱子，其中有N个位置（N>=3），每个位置可存放一个车架或一个车轮；又设有3个工人，其活动分别为：

  • 工人1：加工一个车架，车架放入箱中
  • 工人2：加工一个车轮，车轮放入箱中
  • 工人3：箱中取一个车架，取一个车轮，组装为一台车
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
semaphore empty = N;
semaphore wheel = 0;	// 车轮
semaphore frame = 0;	// 车架
semaphore s1 = N - 1;	// 车架最大数
semaphore s2 = N - 2;	// 车轮最大数
// 工人1活动
加工一个车架;
wait(s1);	// 检查车架数是否已经达到最大值
wait(empty);
车架放入箱中;
signal(frame);
// 工人2活动
加工一个车轮;
wait(s2);
wait(empty);
车轮放入箱中;
signal(wheel);
// 工人3活动
wait(frame);
箱中取一个车轮;
signal(empty);
signal(s1);
wait(wheel);
wait(wheel);
箱中取两个车轮;
signal(empty);
signal(empty);
signal(s2);
signal(s2);
组装为一台车;

12.

系统中有多个生产者进程和多个消费者进程，共享一个能存放1000件产品的环形缓冲区（初始为空），当缓冲区未满时，生产者进程可以放入其生产的一个产品，否则等待；当缓冲区未空时，消费者进程可以从缓冲区取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取出10间产品后，其他消费者才可以取产品。

这道题的解答感觉有问题，当产品的剩余数量不足10个的时候，消费者还控制着mutex1，但是有没有产品，生产者因为得不到mutex1，也不能生产，因此会造成死锁的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
semophere mutex1 = 1, mutex2 = 1;
semophere empty = n, full = 0;
int count = 0;
// 生产者
wait(empty);
wait(mutex1);
放入一件产品;
signal(mutex1);
signal(full);
// 消费者
wait(mutex1);
for(int i = 0;i < 10;i++) {
    wait(full);
    wait(mutex2);
    把产品放入缓冲区;
    signal(mutex2);
    signal(empty);
    消费这件产品;
}
signal(mutex1);

13. 生产者-消费者问题扩展

桌子上有一只盘子，每次只能向其中放入一个水果，爸爸专向盘子中放苹果，妈妈专向盘子中放橘子， 儿子专吃盘子中的橘子，女儿专吃盘子中的苹果，只有盘子为空时，爸爸或妈妈就可以向盘子中放一个水果，仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
semaphore plate = 1;
semaphore apple = 0, orange = 0;
// 爸爸
wait(plate);
put the apple;
signal(apple);
// 妈妈
wait(plate);
put the orange;
signal(orange);
// 女儿
wait(apple);
take an apple from the plate;
signal(plate);
// 儿子
wait(orange);
take an orange from the plate;
signal(plate);

1572779448179

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
semaphore emptyA = 10, fullA = 0;
semaphore emptyB = 10, fullB = 0;
semaphore mutexA, mutexB;
// 生产A车间
wait(emptyA);
wait(mutexA);
把A放入生产车间;
signal(mutexA);
signal(fullA);
// 生产B车间
wait(emptyB);
wait(mutexB);
把B放入生产车间;
signal(mutexB);
signal(fullB);
// 装配车间
wait(fullA);
wait(mutexA);
从车间取一个A;
signal(mutexA);
signal(emptyA);

wait(fullB);
wait(mutexB);
从车间取一个B;
signal(mutexB);
signal(emptyB);

1572779434654

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
semaphore mutex1, mutex2;	// 分别表示互斥从井中取水和从水缸取水
semaphore count = 3;	// 表示水桶
semaphore empty = 10, full = 0;	// 表示水缸中的剩余容量

// 小和尚
wait(empty);
wait(count);
wait(mutex1);
取水;
signal(mutex1);

wait(mutex2);
往水井倒水;
signal(mutex2);
signal(count);	// 放弃桶
signal(full);
// 老和尚
wait(full);
wait(count);
wait(mutex2);
取水;
signal(mutex2);
signal(empty);
signal(count);

1572779424549

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
semaphore mutex;	// 取号的互斥访问
semaphore empty = 10, full = 0;
semaphore keeper = 1;
// 顾客
wait(empty);
wait(mutex);
取号;
signal(mutex);
signal(full);
等待叫号;
wait(keeper);
获取服务;
// 营业员
wait(full);
叫号;
signal(empty);
为客户服务;
signal(keeper);

1572779408974

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
semaphore bridge;
semaphore mutexN, mutexS;
int northcount = 0, southcount = 0;
// 从北到南
wait(mutexN);
northcount++;
if(northcount == 1) {
    wait(bridge);
}
signal(mutexN);
过桥;
wait(mutexN);
northcount--;
if(northcount == 0) {
    signal(bridge);
}
signal(mutexN); = 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
semaphore movie1 = 0, movie2 = 0, movie3 = 0;
semaphore mutex1, mutex2, mutex3;
int count1 = 0, count2 = 0, count3 = 0;
// 选择观看电影1的观众
wait(movie1);
wait(mutex1);
count1++;
signal(mutex1);
观看电影;
wait(mutex1);
count1--;
if(count1 == 0) {
    signal(movie1);
}
signal(mutex1);
// 选择观看电影2的观众
wait(movie2);
... 同理;
最后signal(movie3);

1572779372327

1
2
3
4
5
6
7
8
9
10
11
12
// 驾驶员
wait(mutex1);
...
signal(mutex2);

// 售票员
wait(mutex2);
开车门;
...
关车门;
signal(mutex1);
...

1572779358412

1
2
3
4
5
6
7
8
9
10
11
12
13
semophere emptyA, fullA, emptyB, fullB;
semophere mutexA, mutexB;
wait(fullA);
wait(mutexA);
取邮件;
signal(mutexA);
signla(emptyA);
回答&提出问题;
wait(emptyB);
wait(mutexB);
放入B的邮箱中;
signal(mutexB);
signal(fullB);