【10. 信号量和管程】

🎉作者简介:👓$博主在读机器人研究生，目前研一。对计算机后端感兴趣，喜欢c++,go,python,目前熟悉c++，go语言，数据库，网络编程，了解分布式等相关内容$
📃$个人主页：$ 小呆鸟_coding
🔎$支持:$$如果觉得博主的文章还不错或者您用得到的话，可以免费的关注一下博主，如果三连收藏支持就更好啦$👍$就是给予我最大的支持！$🎁
💛本文摘要💛

本专栏主要是讲解操作系统的相关知识 本文主要讲解 信号量和管程

文章目录

• 🎶信号量和管程
• • ❓0. 上次概念
  • ❓1. 信号量
  • ❓2. 信号量的使用
  • • ❗️2.1 生产者与消费者模型（第一个经典问题）
  • ❓3. 信号量的实现
  • ❓4. 管程
  • ❓5. 经典同步问题
  • • ❗️5.1 读者-写者问题（第二个经典问题）
    • • 💤5.1.1 利用管程实现写者优先的，读者—写者问题（前面使用信号量方式实现读者优先的，读者—写者问题）
      • • ⭐️5.1.1.1 代码
    • ❗️5.2 哲学家就餐问题（第三个经典问题）
    • • 💤5.2.1 代码（信号量实现,也可以用管程+条件变量实现）

清华操作系统系列文章：可面试可复习
1. 操作系统—概述
2. 操作系统—中断、异常、系统调用
3. 操作系统—物理内存管理
4. 操作系统—非连续内存分配
5. 虚拟内存管理
6. 操作系统—虚拟内存管理技术页面置换算法
7. 进程管理
8. 调度算法
9. 同步与互斥
10. 信号量和管程
11. 死锁和进程通信
12. 文件系统管理

🎶信号量和管程

• 背景
• 信号量
• 信号量实现
• 管程
• 经典同步问题

用信号量和管程解决同步互斥的问题

❓0. 上次概念

• 并发问题：竞争条件（竞态条件）
  • 多程序并发存在大的问题
• 同步
  • 多线程共享公共数据的协调执行
  • 包括互斥与条件同步
  • 互斥：在同一时间只有一个线程可以执行临界区
• 确保同步正确很难？
  • 需要高层的编程抽象（如：锁）
  • 从底层硬件支持编译

• 同步：一种合作关系，为完成某个任务而建立的多个进程或者线程之间的协调调用，次序等待，传递消息告知资源（进程切换，互相前进）
• 互斥：制约关系，当一个进程或多个进程进入临界区后会进行加锁操作，此时其他进程（线程）无法进入临界区，只有当该进程（线程）使用后进行解锁，其他人才可以进入临界区。

❓1. 信号量

• 进入临界区后，不一定做一些操作，还需要做读操作，读操作可以有多个进程一起进入临界区执行（不需要限制一个进程）。

• P() < 0，执行P操作的进程需要睡眠，当P >= 0,可以继续执行，进入临界区（类似于lock锁操作）
• V() 就是把信号量的值加1，如果sem <= 0,当前一些进程等待着P操作。他就会唤醒等待的P（执行位操作的进程，会唤醒挂载信号量上的等待的进程，一般可以唤醒一个或者多个）

❓2. 信号量的使用

一般最开始把信号量设置为整数，而且是大于0的整数，这样在进程进入临界区的时候才不会阻塞

• 信号量是整数

• 信号量是被保护的变量

  • 初始化完成后,唯一改变一个信号量的值的办法是通过P()和V()
  • 操作必须是原子

• P()能够阻塞,V()不会阻塞

• 我们假定信号量是公平的

  • 没有线程被阻塞在P()仍然堵塞如果V()被无限频繁调用(在同一个信号量)
  • 在实践中,FIFO经常被使用

问题：信号量可以通过FIFO队列实现唤醒进程，而锁在进行忙等待时能否通过FIFO队列实现唤醒进程吗

信号量的设置

• 两个类型信号量
  • 二进制信号量: 可以是0或1（模拟锁lock）
  • 计数信号量: 可以取任何非负数（设置为大于0的整数，可以使得多个进程一起进入临界区执行。而lock锁是临界区只有一个进程，这就是区别）
  • 两者相互表现(给定一个可以实现另一个)
• 信号量可以用在2个方面
  • 互斥
  • 条件同步(调度约束——一个线程等待另一个线程的事情发生)

二进制信号量可以实现互斥操作

二进制信号量可以实现同步操作

• 同步操作信号量赋值为0。
• 线程A必须等待线程B执行完之后才执行。

先执行进程A，当进程A执行后O操作会减1，此时信号量变为-1，进程A挂起，然后执行进程B，当执行完进程B，V操作会+1，此时信号量为0，唤醒进程A

计数信号量

• 单纯使用二进制信号量，可能对于复杂的进程没办法解决，此时需要条件同步机制完成

• 一个线程等待另一个线程处理事情

  • 比如生产东西或消费东西(生产者消费者模式),
  • 互斥(锁机制)是不够的

• 例如有界缓冲区的生产者-消费者问题

  • 一个或者多个生产者产生数据将数据放在一个缓冲区里
  • 单个消费者每次从缓冲区取出数据
  • 在任何一个时间只有一个生产者或消费者可以访问该缓冲区

• 正确性要求

  • 在任何一个时间只能有一个线程操作缓冲区(互斥)
  • 当缓冲区为空时,消费者必须等待生产者(调度,同步约束)
  • 当缓存区满,生产者必须等待消费者(调度,同步约束)

• 每个约束用一个单独的信号量

  • 二进制信号量互斥（二进制信号量用于互斥）
  • 一般信号量 fullBuffers（计数信号量用于同步）
  • 一般信号了 emptyBuffers

❗️2.1 生产者与消费者模型（第一个经典问题）

• 需要满足使得buffer互斥，使用mutex->P()和mutex->V()(使用信号量的P,V操作使得往缓冲区添加数据时为互斥操作，使得对buffer操作是只有一个进程对其操作)
• 生产者：
  • buffer没有满，可以执行，用emptyBuffer判断buffer有没有满，而且emptybuffer初始值设置为n，也就是可以执行n次操作（也就是可以用有n个生产者进程进入buffer中）
  • fullbuffer->V操作,可以通知消费者，buffer缓冲区有数据，你可以来取（一开始消费者想取数据，取不到因为初始值为0，只有在生产者执行fullbuffer->V才可以）
• 消费者
  • 如果一开始生产者先执行，那么fullbuffer为1，此时消费者执行fullbuffer->P()操作时，可以从缓冲区取数据
  • 如果一开始消费者先执行，由于fullbufferW为空，则会阻塞，消费者会睡眠，同时会唤醒生产者，知道缓冲区有数据。

如果生产者很快，把buffer塞满了，此时执行emptybuffer->P(),操作是阻塞，此时需要消费者执行emptybuffer->V()操作，使得buffer的值+1，当buffer不满时，通知睡眠的生产者

class BoundedBuffer{
		mutex = new Semaphore(1);         //互斥操作，初始值设置为1（当第一个执行时，值-1，为0.此时第二个需要等待第一个锁释放）
		fullBuffers = new Semaphore(0);   //说明缓冲区初始为空
 		emptyBuffers = new Semaphore(n);  //生产者可以往缓冲区填充n个数据
};

BoundedBuffer::Deposit(c){
		emptyBuffers->P();
		mutex->P();
		Add c to the buffer;
		mutex->V();
		fullBuffers->V();
}

BoundedBuffer::Remove(c){
		fullBuffers->P();
		mutex->P();
		Remove c from buffer;
		mutex->V();
		emptyBuffers->V();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

P、V操作的顺序有影响吗？

• 对于互换生生产者最后的V操作，对程序没有影响
  • 不会影响，因为V操作只会加1，和通知机制（唤醒），本身不会阻塞
• 对于互换生生产者开头的P操作，对程序有影响
  • 当buffer满时，此时生产者会进入mutex->P(),在执行到emptybuffer->P()操作会阻塞（因为buffer已满，在执行就变成-1，需要睡眠），此时需要唤醒消费者。
  • 对于消费者，buffer已满，此时fullbuffer->P();可以执行，但是执行到mutex->P()就会产生错误，因为生产者虽然buffer满无法执行但是它占用mutex信号量。使得消费者执行mutex失败——死锁

❓3. 信号量的实现

• 做P操作可能有信号处于等待状态，等操作就是等待队列（进程当得不到相应的资源，就会睡眠），也就是执行P操作时，这个值<0，此时进程会睡眠，需要等待队列。等待信号量执行V操作后会唤醒
• P操作执行–，当信号量<0,此时会将信号量放到等待队列中去，并且自身睡眠
• V操作执行++，判断是否等待队列中有睡眠的信号量，将它从等待队列移除，并将其唤醒（FIFO取出唤醒等待队列中的信号量）
  
• 信号量的双用途
  • 互斥和条件同步
  • 但等待条件是独立的互斥
• 读,开发代码比较困难
  • 程序员必须非常精通信号量
• 容易出错
  • 使用的信号量已经被另一个线程占用
  • 忘记释放信号量
• 不能够处理死锁问题

与lock区别：

• lock有俩种等待：忙等和等待队列（可以做sleep操作）
• 信号量全部都是使用等待队列实现sleep，在通过v操作唤醒

❓4. 管程

管程最开始是用于语言，来完成同步互斥的操作（针对语言的并发操作），后来用于操作系统上

• 目的: 分离互斥和条件同步的关注
• 什么是管程
  • 一个锁: 指定临界区（所有要访问管程管理的函数只能有一个线程，需要确保互斥性）
  • 0或者多个条件变量: 等待,通知信号量用于管程并发访问共享数据（访问大量共享资源，在访问中可能得不到满足，需要把等待的，得不到资源的线程挂起，挂在条件变量上面）
  • 管程管理着一系列函数。可以供线程访问
• 一般方法
  • 收集在对象,模块中的相关共享数据
  • 定义方法来访问共享数据

图例

1. entry queue进入管程是互斥的，首先要去的lock，获得lock才能进入管程，取不到lock就要在这个队列中
2. 进入lock管理的临界区后，线程可以执行管程维护的一系列函数，操作函数，这些函数有许多共享变量，可以对共享变量操作，针可能对某个共享资源的共享变量得不到满足，则需要等待，需要把自身挂载到条件变量上，同时把lock释放掉，让等待在lock上的其他线程执行
3. 自身挂到条件变量上，条件变量的等待队列挂载所有线程，有条件x和y，当条件满足就会唤相应进程

wait:线程等在条件变量中
signal:唤醒条件变量使得，使得挂载到条件变量上的线程可以继续执行

• Lock
  • Lock::Acquire() 等待直到锁可用,然后抢占锁
  • Lock::Release() 释放锁,唤醒等待者如果有
• Condition Variable
  • 允许等待状态进入临界区
    • 允许处于等待(睡眠)的线程进入临界区
    • 某个时刻原子释放锁进入睡眠
  • Wait() operation
    • 释放锁,睡眠,重新获得锁放回
  • Signal() operation(or broadcast() operation)
    • 唤醒等待者(或者所有等待者),如果有

实现

• 需要维持每个条件队列
• 线程等待的条件等待signal()

class Condition{
		int numWaiting = 0;
		WaitQueue q;
};

Condition::Wait(lock){
		numWaiting++;             //执行wait操作就是睡眠了，表明多了一个睡在条件变量上的进程。
		Add this thread t to q;
		release(lock);    //让生产者释放锁，让其他的进程进入管程执行
		schedule(); //need mutex,选择下一个线程执行，本身这个进程已经属于睡眠状态了
		require(lock);
}

Condition::Signal(){
		if(numWaiting > 0){   //说明有进程处于等待状态，如果有的活从等待队列唤醒进程
				Remove a thread t from q;
				wakeup(t); //need mutex
				numWaiting--;
		}
}
wake up与 schedule对应，schedule是进程睡眠了，他会取一个就绪态进程继续执行，完成线程切换，wake up 将睡眠进程重新置成就绪态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

值得注意，如果这个等待队列里没有进程，则这个操作什么也不做
信号里面是信号量的个数为0，（他的P和V操作一定会进行加和减操作的）而这里是num waiting等待进程的数量为0（在Wait会做加操作，而signal不一定会减操作）.

管程解决生产者—消费者问题

• 管程最重要的俩个：lock(锁)和条件变量
• 对于之前的生产者和消费者问题，条件变量有俩种：buffer满和buffer空
• 管程的生产者和消费者模型，不仅需要设置buffer空和buffer满，还要设置count(记录buffer当前的空闲情况，count =0,buffer空，count=n,buffer满)

注意：与信号量互斥不一样，信号量的互斥是仅仅靠近这个buffer,而管程的互斥是放到程序的头和尾（由管程的定义决定，线程进入到管程的时候，只有一个线程能进去，才能使用管程管理的所有函数，所以一进入管程的时候就需要互斥）

class BoundedBuffer{
		Lock lock;
		int count = 0;  //buffer 为空
		Condition notFull, notEmpty;
};

BoundedBuffer::Deposit(c){
		lock->Acquire();    //管程的定义:只有一个线程能够进入管程
		while(count == n)
				notFull.Wait(&lock); //与信号量不一样，notfull是条件变量，不需要初始化，表示当前已经满了，需要睡眠，释放前面的锁（释放管程的lock，因为睡眠了，释放锁后，可以让其他的进程进入管程执行，睡眠之前一定要释放锁， 不然会导致所有后面等待的进程都无法进入管程）
		Add c to the buffer;
		count++;
		notEmpty.Signal();  //buffer空与buffer满是一样的
		lock->Release();
}

BoundedBuffer::Remove(c){
		lock->Acquire();
		while(count == 0)
				notEmpty.Wait(&lock);
		Remove c from buffer;
		count--;
		notFull.Signal();    //对应生产者的notfull Wait，notfull.Signal是唤醒机制，如果notfill Signal中有等待的线程，那么就会唤醒（首先count --, buffer满，经过-- 后，会不满，此时可以使用notfull Signal操作唤醒，它里面等待的进程）
		lock->Release();
}
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

问题：

• 当线程在管程里面执行的时候，如果某个线程，执行某个条件变量的> Signal（唤醒）操作时，是不是马上唤醒等待在条件变量上的线程。
  • 执行Signal操作时，管程里面是有俩个线程，signal之后，就是要把等>待的进程唤醒（唤醒进程的本身也可以执行），这就会产生冲突。

俩种解决办法

1. 一旦发出signal操作后，让等待的线程执行，它自身去睡眠，直到等待的线程执行完release之后，发出signal的线程才能继续执行。
2. 当发出signal操作是，不是立刻放弃CPU，让等待的线程执行，而是等到发出signal的线程执行完release后，才把控制权交给等待的线程执行。

• 开发,调试并行程序很难
  • 非确定性的交叉指令
• 同步结构
  • 锁: 互斥
  • 条件变量: 有条件的同步
  • 其他原语: 信号量
• 怎么样有效地使用这些结构
  制定并遵循严格的程序设计风格,策略

❓5. 经典同步问题

❗️5.1 读者-写者问题（第二个经典问题）

• 动机：
  • 共享数据的访问
• 两种类型的使用者：
  • 读者 — 不修改数据（读者优先）
  • 写者 — 读取和修改数据
• 问题的约束：
  • 允许同一时间有多个读者,但在任何时候只有一个写者
  • 当没有写者时,读者才能访问数据
  • 当没有读者和写者时,写者才能访问数据
  • 在任何时候只能有一个线程可以操作共享变量

当读者读的过程中，有写者进入，那么等待读者读完，同样当写者执行时，不管读者和写者都要等待。等待当前写者写完。

• 多个并发进程的数据集共享
  • 读者 — 只读数据集;他们不执行任何更新
  • 写者 — 可以读取和写入
• 共享数据
  • 数据集
  • 信号量CountMutex初始化为1（读Rcounter保证读是互斥的）
  • 信号量WriteMutex初始化为1（写也要互斥）
  • 整数Rcount初始化为0(当前读者个数,写者就一个，读者有很多)

• WriteMutex确保写者的互斥性，以及只有一个读者的互斥性
• 通过Rcounter实现对读者个数的记录,使得多个读者可以同时数据里面进行读操作
• Rcounter通过CounterMutex来进行保护（互斥），使得Rcounter可以互斥的+，-

读者优先与写者优先

💤5.1.1 利用管程实现写者优先的，读者—写者问题（前面使用信号量方式实现读者优先的，读者—写者问题）

• 读者需要等待的写者的有俩类：
  1. 当前正在做写操作的写者
  2. 当前正在等待做写操作的写者

⭐️5.1.1.1 代码

初始化

读者代码

写者代码

总代码

//writer
Database::Write(){
		Wait until readers/writers;
		write database;
		check out - wake up waiting readers/writers;
}
//reader
Database::Read(){
		Wait until no writers;
		read database;
		check out - wake up waiting writers;
}

//管程实现
AR = 0; // # of active readers
AW = 0; // # of active writers
WR = 0; // # of waiting readers
WW = 0; // # of waiting writers
Condition okToRead;
Condition okToWrite;
Lock lock;
//writer
Public Database::Write(){
		//Wait until no readers/writers;
		StartWrite();
		write database;
		//check out - wake up waiting readers/writers;
		DoneWrite();
}

Private Database::StartWrite(){
		lock.Acquire();
		while((AW + AR) > 0){    //如果临界区里面的读者或者写者正在进行操作，那么写者等待(体现写者优先)
				WW++;
				okToWrite.wait(&lock);
				WW--;		
		}
		AW++;
		lock.Release();
}

Private Database::DoneWrite(){
		lock.Acquire();
		AW--;
		if(WW > 0){
				okToWrite.signal();
		}
		else if(WR > 0){
				okToRead.broadcast(); //唤醒所有reader,可能等待的没有写者，只有读者，就把读者全部唤醒，提高效率
		}
		lock.Release();
}

//reader
Public Database::Read(){
		//Wait until no writers;
		StartRead();
		read database;
		//check out - wake up waiting writers;
		DoneRead();
}

Private Database::StartRead(){
		lock.Acquire();
		while(AW + WW > 0){    //关注等待的writer,体现出写者优先
				WR++;
				okToRead.wait(&lock);
				WR--;
		}
		AR++;
		lock.Release();
}

private Database::DoneRead(){
		lock.Acquire();
		AR--;
		if(AR == 0 && WW > 0){  //只有读者全部没有了,才需要唤醒
				okToWrite.signal();
		}
		lock.Release();
}
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

❗️5.2 哲学家就餐问题（第三个经典问题）

思路1：

思路2：

思路3：

💤5.2.1 代码（信号量实现,也可以用管程+条件变量实现）

• V(s[i])操作一般是通知其他进程（唤醒其他进程）
• 状态都属于互斥，需要保护起来

'用数据结构，来描述每个哲学家的当前状态'
#define N 5                  //哲学家个数
#define LEFT (i + N - 1) % N //第i个哲学家的左邻居
#define RIGHT (i + 1) % N    //第i个哲学家的右邻居
#define THINKING 0           //思考状态
#define HUNGRY   1           //饥饿状态
#define EATING   2           //进餐状态
typedef int semaphore;  
int state[N];                // 跟踪每个哲学家的状态

'该状态是一个临界资源，对它的访问应该互斥地进行'
semaphore mutex = 1;         // 临界区的互斥，临界区是 state 数组，对其修改需要互斥

'一个哲学家吃饱后，唤醒临界，存在同步关系'
semaphore s[N];              // 每个哲学家一个信号量(哲学家进行通信，看是否阻塞还是运行)

void philosopher(int i) {    //i的取指：0到N-1
    while(TRUE) {
        think(i);            //S1
        take_forks(i);       //S2-S4（拿到俩把叉子或被阻塞）
        eat(i);              //S5（吃面条）
        put_forks(i);        //S6-S7（把俩把叉子放回到原处）
    }
}

'要么拿到俩把叉子，要么被阻塞起来'
void take_forks(int i) {
    P(mutex);                  //hunger是需要保护的，这是写操作
    state[i] = HUNGRY;         //第i个哲学家，饿了！
    test_take_left_right_forks(i);//试图拿俩把叉子
    V(mutex);
    P(s[i]); // 只有收到通知之后才可以开始吃，否则会一直等下去（没有叉子便阻塞）
}

'把俩把叉子放回原处，并在需要的时候，去唤醒左邻右舍'
void put_forks(i) {
    P(mutex);                         //进入临界区
    state[i] = THINKING;              //思考状态，意味着把俩把叉子放回去
    test_take_left_right_forks(LEFT); // 尝试通知左右邻居，自己吃完了，你们可以开始吃了——看左邻居能否进餐
    test_take_left_right_forks(RIGHT); //看右邻居能否进餐（之前参数i是指的自身，看自身能不能进餐）
    V(mutex);                        //与take_forks的P[s[i]]是一对的，当这里执行了V操作后，P操作才不会阻塞（我先判断左/右邻居能不能拿到俩把叉子进餐，如果可以的话，执行V操作，在执行P操作就不会阻塞，如果不执行V操作，说明它拿不到叉子此时P操作需要一直等等待）
}
void think(int i){
	P(&mutex);
    state[i] = THINKING;
    V(&mutex);
}
void eat(int i) {
    P(&mutex);
    state[i] = EATING;
    V(&mutex);
}

// 检查两个邻居是否都没有用餐，如果是的话，就 V(s[i])，使得 P(s[i]) 能够得到通知并继续执行
void  test_take_left_right_forks(int i) {         
    if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) {
        state[i] = EATING;         //俩把叉子到手(只要处于eat状态，证明俩把叉子到手)

'拿到俩把叉子，且通知自己可以吃饭了'
        V(s[i]);                   //通知第i人可以吃饭了,s[i]的初值为0（V操作后s[i]的值变为1），我自己可以吃饭（对自身状态做了设置），使得后面做P操作的时候不会阻塞。
    }
}
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
51
52
53
54
55
56
57
58
59
60
61
62

**总结**：

• 读者—写者问题（细分读者优先和写者优先，使用了管程的方法）
• 哲学家问题（使用了了信号量，也可以使用管程+条件变量）