信号量和管程

$$信号量和管程$$

$信号量$

$抽象数据类型$

1. 一个整形，附加着两个原子操作。
2. $P$操作：$sem-1$，如果$sem<0$，则进入线程睡眠，开始等待，否则继续。
3. $V$操作：如果$sem<=0$，唤醒一个正在睡眠等待的$P$。

$便于理解的解释：$
1.最开始的时候两条铁轨上，没有没有火车，铁轨数量相当于信号量，当一辆火车进入铁轨的时候，执行$P$操作，这个时候铁轨数量$-1$($信号量数量-1$)。
2. 当所有的铁轨都被占满的时候($信号量数量<=0$)，如果又来了火车，此时执行$P$操作会因为$信号量数量<=0$而进入等待状态。

3. 当铁轨中有的火车运行完毕之后，从分叉铁轨出来的时候，执行$V$操作，可使用铁轨数量$+1$($信号量数量+1$)，并且向一个正在等待的火车传递信息($睡眠线程的唤醒$)。然后该等待的火车进入铁轨。

$信号量的使用$

①.$信号量特征：$

1. 信号量是$正数$。
2. 信号量是一个$被保护$的变量。
   $被保护$：信号量只要初始化了之后，$只能通过P与V两个操作进行改变|$
3. $P$操作会阻塞，而$V$操作不会。

②.$信号量种类：$

1. $二进制信号量$：$0$或$1$($Lock$)
2. $一般信号量$：可以取得任何值($多线程适用$)

③.$信号量作用：$

1. 线程互斥
2. 条件同步

$有界缓冲区的生产者——消费者问题$

$正确性要求：$

1. $互斥$：同一时间只能够有一个线程操作缓冲区。
2. $调度/同步约束$：
   缓冲区空，那么消费者必须等待生产者。
   缓冲区满，那么生产者必须等待消费者。

$信号量:$

1. 二进制信号量(互斥)
2. 计数信号量$FullBuffers$和$EmptyBuffers$。

$伪代码描述：$

Class BoundedBuffer{				//缓冲区类型
	mutex = new Semaphore(1);			//互斥信号量
	FullBuffers = new Semaphore(0);		//缓冲区满信号量
	EmptyBuffers = new Semaphore(n);	//缓冲区空信号量
}

BoundedBuffer::Deposit(e) {			//生产者的Deposit存储资源操作
	EmptyBuffers -> P();
	mutex -> P();
	Add c to the buffer;
	mutex -> V();
	FullBuffers -> V();
}

BoundedBuffer::Remove(e) {			//消费者的Remove取用资源操作
	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

$整体流程：$
$Deposit：$
生产者首先对于$EmptyBuffers$信号量执行$P$操作希望能够获得向缓冲区存储数据的权利($EmptyBuffers信号量的值代表缓冲区同时可以进入多少个生产者$)，之后对于$mutex$信号量执行$P$操作开启线程互斥($mutex=1\to mutex=0$)，意为当前临界区已经被使用了，拒绝其他线程的访问。存储完数据之后，首先使用$mutex$的$V$操作打开临界区的访问权限($mutex=1\to mutex=0$)，之后调用$FullBuffers$的$V$操作告知消费者现在缓冲区里面的已经有了数据了($FullBuffers信号量的值代表缓冲区中存储的数据个数$)。
$Remove：$
消费者首先对于$FullBuffers$执行$P$操作，意为从缓冲区中读出数据($FullBuffers信号量初始化的值是0，如果一开始没有数据，那么消费者会会被直接挡在这一步，等待消费者添加数据$)。之后进行线程互斥操作，对$mutex$信号量执行$P$操作，然后取出数据。之后放开对于临界区的访问管控($mutex$ = 0 → $mutex$ = 1)。最后对于$EmptyBuffers$信号量执行$V$操作，这时可以将睡眠的生产者进程唤醒。

$信号量基本操作的实现$($P$和$V$操作)

class Semaphore{
	int sem;
	WaitQueue q;
}

Semaphore::P(){			//P操作实现基本原理
	sem--;
	if(sem < 0){
		Add this thread to q:
		block(p);
	}
}

Semaphore::V(){			//V操作实现基本原理
	sem++;
	if(sem <= 0){
		Remove a thread t from q;
		wakeup(t);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

$Sem++和Sem--的理解：$可以理解为，当$sem<0$的时候开始，对线程进行入队(等待队列)。$Sem--$就是对线程进行入队，$Sem++$就是对等待队列中的等待线程进行出队，然后调用$Wakeup(出队线程)$函数进行唤醒。

$管程(Monitor)$

$管程定义$

包含了一系列的共享变量以及操作这些共享变量的函数的集合。

$管程构成：$

1. $Lock：$指定临界区。
2. $0或多个条件变量：$等待/通知信号量用于管理和并发访问共享数据。

$条件变量Wait和Signal操作实现：$

Class Condition {
	int numWaiting = 0;			//等待的线程数
	WaitQueue q;				//线程的等待队列
}

Condition::Wait(lock) {	//将一个线程加入到等待队列中
	numWaiting++;
	Add this thread t to q;
	release(lock);
	schedule();
	require(lock);
}

Condition::Signal() {		//唤醒一个在等待队列中等待的线程
	if(numWaiting > 0) {
		Remove a thread t from q;
		wakeup(t);
		numWaiting--;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

classBoundedBuffer {				//字节缓冲区类构成
	...
	Lock lock;						//共享锁变量
	int count = 0;					//线程中的数据数
	Condition notFull , notEmpty;			//条件变量
}

BoundedBuffer::Deposit(e) {			//存储操作
	lock -> Acquire();			//索要lock变量，锁住临界区
	while(count == n)			//如果数据已经满了，当前生产者的存放进程进入等待状态
		notFull.Wait(&lock);
	Add c to the buffer;			//存放数据
	count++；
	notEmpty.Signal();			//Signal操作通知消费者可以进行取出数据了
	lock -> Release();			//释放其他线程访问临界区的资格
}

BoundedBuffer::Remove(c) {				//消费者取出资源操作
	lock -> Acquire();						//索要访问临界区资源的权限
	while(count == 0)			//临界区没有资源了，当前消费者取出资源的操作进入等待状态
		notEmpty.Wait(&lock);			
	Remove c from buffer;
	count--;
	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
26

$线程同步经典问题$

①. $哲学家用餐问题：$
$思路：$

1. 将每个哲学家的当前状态表示为临界区的临界资源。

2. 每个哲学家访问临界资源的时候，应该是互斥的($进程互斥$)。
   

3. 一个哲学家吃饱之后，可能会唤醒它的左邻右舍，两者之间存在着同步关系($进程同步$)。
   

$伪代码实现：$
1. $take\_forks$函数：
2. $testt\_take\_left\_right\_forks$函数
3. $put\_forks$函数