|
1
|
制造商-消费者问题 |
也叫缓存绑定问题（bounded- buffer），是一个经典的、多进程同步问题。即有两个进程：制造商和消费者，共享一个固定大小的缓存。制造商的工作是制造一段数据，放进缓存，如此反复。同时，消费者则一次消费一段数据（即将其从缓存中移出）。问题的核心就是要保证不让制造商在缓存还是满的时候仍然要向内写数据，不让消费者试图从空的缓存中取出数据。
制造商的方案是：如果缓存是满的就去睡觉。消费者从缓存中取走数据后就叫醒制造商，让它再次将缓存填满。这样，消费者发现缓存是空的，它就去睡觉了。下一轮中制造商将数据写入后就叫醒消费者。通过使用“进程间通信”就可以解决这个问题，人们一般使用“信号标”（semaphore）。不完善的解决方案会造成“死锁”，即两个进程都在“睡觉”等着对方来“唤醒”。
信号标解决方案
信号标可以解决唤醒的问题。在下面的方案中，我们使用了两个信号标：fillCount和emptyCount来解决问题。新的数据添加到缓存中后，fillCount在增加，而emptyCount则减少。如果制造商试图在emptyCount为0减少其值，制造商就会被“催眠”。下一轮中有数据被消费掉时，emptyCount就会增加，制造商就会被“唤醒”。可示意如下：
semaphore fillCount = 0
semaphore emptyCount = BUFFER_SIZE
procedure producer() {
while (true) {
item = produceItem()
down(emptyCount)
putItemIntoBuffer(item)
up(fillCount)
}
}
procedure consumer() {
while (true) {
down(fillCount)
item = removeItemFromBuffer()
up(emptyCount)
consumeItem(item)
}
}
如果只有一个制造商和一个消费者时，这个方案运行正常。不巧的是，在多个制造商和多个消费者出现的情况下就会造成拥护不堪的情况，会导致两个或多个进程同时向一个磁道写入或读出数据。要理解这种情况是如何出现的，我们可以借助于putItemIntoBuffer()函数。它包含两个动作：一个来判断是否有可用磁道，另一个则用来向其写入数据。如果进程可以由多个制造商并发执行，下面的情况则会出现：
1、 两个制造商为emptyCount减值；
2、 一个制造商判断缓存中有可用磁道；
3、 第二个制造商与第一个制造商一样判断缓存中有可用磁道；
4、 两个制造商同时向同一个磁道写入数据。
为了克服这个问题，我们需要一个方法，以确保一次只有一个制造商在执行putItemIntoBuffer()函数。换个说法来讲，我们需要一个有“互斥信号标”（mutal exclusion）的“关键扇区”（critical section）。为了实现这一点，我们使用一个叫mutex二位信号标。因为一个二位信号标的值只能是1或0，只有一个进程能执行down(mutex)或up(mutex)。多个制造商和消费者的解决方案如下：
semaphore mutex = 1
semaphore fillCount = 0
semaphore emptyCount = BUFFER_SIZE
procedure producer() {
while (true) {
item = produceItem()
down(emptyCount)
down(mutex)
putItemIntoBuffer(item)
up(mutex)
up(fillCount)
}
up(fillCount) //the consumer may not finish before the producer.
}
procedure consumer() {
while (true) {
down(fillCount)
down(mutex)
item = removeItemFromBuffer()
up(mutex)
up(emptyCount)
consumeItem(item)
}
}
使用监控法
下面的伪代码演示了如何使用监控法来解决制造商-消费者问题。因为使用互斥信号标没有保护关键区，所以监控法更优。代码如下：
monitor ProducerConsumer {
int itemCount
condition full
condition empty
procedure add(item) {
while (itemCount == BUFFER_SIZE) {
wait(full)
}
putItemIntoBuffer(item)
itemCount = itemCount + 1
if (itemCount == 1) {
notify(empty)
}
}
procedure remove() {
while (itemCount == 0) {
wait(empty)
}
item = removeItemFromBuffer()
itemCount = itemCount - 1
if (itemCount == BUFFER_SIZE - 1) {
notify(full)
}
return item;
}
}
procedure producer() {
while (true) {
item = produceItem()
ProducerConsumer.add(item)
}
}
procedure consumer() {
while (true) {
item = ProducerConsumer.remove()
consumeItem()
}
}
|
2
|
哲学家就餐问题 |
哲学家就餐问题是在计算机科学中的一个经典问题，用来演示在并行计算中多线程同步时产生的问题。
在1971年，著名的计算机科学家艾兹格·迪科斯彻（Edsger Wybe Dijkstra）提出了一个同步问题，即假设有五台计算机都试图访问五份共享的磁带驱动器。稍后，这个问题被托尼·霍尔重新表述为哲学家就餐问题。这个问题可以用来解释死锁和资源耗尽。
问题描述
哲学家就餐问题可以这样表述，假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭，或者思考。吃东西的时候，他们就停止思考，思考的时候也停止吃东西。餐桌中间有一大碗意大利面，每两个哲学家之间有一只餐叉。因为用一只餐叉很难吃到意大利面，所以假设哲学家必须用两只餐叉吃东西。他们只能使用自己左右手边的那两只餐叉。哲学家就餐问题有时也用米饭和筷子而不是意大利面和餐叉来描述，因为很明显，吃米饭必须用两根筷子。
哲学家就餐问题的演示哲学家从来不交谈，这就很危险，可能产生死锁，每个哲学家都拿着左手的餐叉，永远都在等右边的餐叉（或者相反）。
即使没有死锁，也有可能发生资源耗尽。例如，假设规定当哲学家等待另一只餐叉超过五分钟后就放下自己手里的那一只餐叉，并且再等五分钟后进行下一次尝试。这个策略消除了死锁（系统总会进入到下一个状态），但仍然有可能发生“活锁”。如果五位哲学家在完全相同的时刻进入餐厅，并同时拿起左边的餐叉，那么这些哲学家就会等待五分钟，同时放下手中的餐叉，再等五分钟，又同时拿起这些餐叉。
在实际的计算机问题中，缺乏餐叉可以类比为缺乏共享资源。一种常用的计算机技术是资源加锁，用来保证在某个时刻资源只能被一个程序或一段代码访问。当一个程序想要使用的资源已经被另一个程序锁定，它就等待资源解锁。当多个程序涉及到加锁的资源时，在某些情况下就有可能发生死锁。例如，某个程序需要访问两个文件，当两个这样的程序各锁了一个文件，那它们都在等待对方解锁另一个文件，而这永远不会发生。
解法
[编辑] 服务生解法
一个简单的解法是引入一个餐厅服务生，哲学家必须经过他的允许才能拿起餐叉。因为服务生知道哪只餐叉正在使用，所以他能够作出判断避免死锁。
为了演示这种解法，假设哲学家依次标号为A至E。如果A和C在吃东西，则有四只餐叉在使用中。B坐在A和C之间，所以两只餐叉都无法使用，而D和E之间有一只空余的餐叉。假设这时D想要吃东西。如果他拿起了第五只餐叉，就有可能发生死锁。相反，如果他征求服务生同意，服务生会让他等待。这样，我们就能保证下次当两把餐叉空余出来时，一定有一位哲学家可以成功的得到一对餐叉，从而避免了死锁。
[编辑] 资源分级解法
另一个简单的解法是为资源（这里是餐叉）分配一个偏序或者分级的关系，并约定所有资源都按照这种顺序获取，按相反顺序释放，而且保证不会有两个无关资源同时被同一项工作所需要。在哲学家就餐问题中，资源（餐叉）按照某种规则编号为1至5，每一个工作单元（哲学家）总是先拿起左右两边编号较低的餐叉，再拿编号较高的。用完餐叉后，他总是先放下编号较高的餐叉，再放下编号较低的。在这种情况下，当四位哲学家同时拿起他们手边编号较低的餐叉时，只有编号最高的餐叉留在桌上，从而第五位哲学家就不能使用任何一只餐叉了。而且，只有一位哲学家能使用最高编号的餐叉，所以他能使用两只餐叉用餐。当他吃完后，他会先放下编号最高的餐叉，再放下编号较低的餐叉，从而让另一位哲学家拿起后边的这只开始吃东西。
尽管资源分级能避免死锁，但这种策略并不总是实用的，特别是当所需资源的列表并不是事先知道的时候。例如，假设一个工作单元拿着资源3和5，并决定需要资源2，则必须先要释放5，之后释放3，才能得到2，之后必须重新按顺序获取3和5。对需要访问大量数据库记录的计算机程序来说，如果需要先释放高编号的记录才能访问新的记录，那么运行效率就不会高，因此这种方法在这里并不实用。
这种方法经常是实际计算机科学问题中最实用的解法，通过为分级锁指定常量，强制获得锁的顺序，就可以解决这个问题。
[编辑] Chandy/Misra解法
1984年，K. Mani Chandy和J. Misra提出了哲学家就餐问题的另一个解法，允许任意的用户（编号P1, ..., Pn）争用任意数量的资源。与迪科斯彻的解法不同的是，这里编号可以是任意的。
对每一对竞争一个资源的哲学家，新拿一个餐叉，给编号较低的哲学家。每只餐叉都是“干净的”或者“脏的”。最初，所有的餐叉都是脏的。
当一位哲学家要使用资源（也就是要吃东西）时，他必须从与他竞争的邻居那里得到。对每只他当前没有的餐叉，他都发送一个请求。
当拥有餐叉的哲学家收到请求时，如果餐叉是干净的，那么他继续留着，否则就擦干净并交出餐叉。
当某个哲学家吃饭东西后，他的餐叉就变脏了。如果另一个哲学家之前请求过其中的餐叉，那他就擦干净并交出餐叉。
这个解法允许很大的并行性，适用于任意大的问题。
|
3
|
熟睡的理发师问题 | | 0天 |
在计算机科学中，“熟睡的理发师问题”是用来描述多个操作系统进程之间的，一个经典的进程之间的通信及同步问题。该问题模拟的描述是有顾客时，让理发师理发；没顾客时，让理发师睡觉。理发师与顾客就代表系统进程。
问题说明
假设有一个理发店只有一个理发师，一张理发时坐的椅子，若干张普通椅子顾客供等候时坐。没有顾客时，理发师就坐在理发的椅子上睡觉。顾客一到，他不是叫醒理发师，就是离开。如果理发师没有睡觉，而在为别人理发，他就会坐下来等候。如果所有的枯木都坐满了人，最后来的顾客就会离开。
在出现竞争的情况下问题就来了，这和其它的排队问题是一样的。实际上，与哲学家就餐问题是一样的。如果没有适当的解决方案，就会导致进程之间的“饿肚子”和“死锁”。
如理发师在等一位顾客，顾客在等理发师，进而造成死锁。另外，有的顾客可能也不愿按顺序等候，会让一些在等待的顾客永远都不能理发。
解决方案
最常见的解决方案就是使用三个信号标（Semaphore）：一个给顾客信号标，一个理发师信号标（看他自己是不是闲着），第三个是互斥信号标（Mutual exclusion，缩写成mutex）。一位顾客来了，他想拿到互斥信号标，他就等着直到拿到为止。顾客拿到互斥信号标后，会去查看是否有空着的椅子（可能是等候的椅子，也可能是理发时坐的那张椅子）。
如果没有一张是空着的，他就走了。如果他找到了一张椅子，就会让空椅子的数量减少一张（）标。这位顾客接下来就使用自己的信号标叫醒理发师。这样，互斥信号标就释放出来供其他顾客或理发师使用。如果理发师在忙，这位顾客就会等。理发师就会进入了一个永久的等候循环，等着被在等候的顾客唤醒。一旦他醒过来，他会给所有在等候的顾客发信号，让他们依次理发。
这个问题中只有一个理发师，所以也叫“一个熟睡的理发师问题”。尽管多个理发师的情况会遇到相同的问题，不过解决起来问题要复杂得多。
模拟
下面的伪代码可以保证理发师与顾客之间不会发生死锁，但可能会让某位顾客“饿肚子”。P和V是信号标的函数。
+顾客信号标 = 0
+理发师信号标=0
+互斥信号标=1
+int 空椅子数量=N //所有的椅子数量
理发师（线程/进程）
While(true){ //持续不断地循环
P（顾客） //试图为一位顾客服务，如果没有他就睡觉
P（互斥信号标） //这时他被叫醒，要修改空椅子的数量
空椅子数量++ //一张椅子空了出来
V（理发师） //理发师准备理发
V（互斥信号标） //我们不想再死锁在椅子上
//这时理发师在理发
｝
顾客（线程/进程）
while(true) ｛ //持续不断地循环
P（互斥信号标） //想坐到一张椅子上
if (空椅子数量>0) { //如果还有空着的椅子的话
空椅子数量-- //顾客坐到一张椅子上了
V（顾客） //通知理发师，有一位顾客来了
V（互斥信号标） //不会死锁到椅子上
P（理发师） //该这位顾客理发了，如果他还在忙，那么他就等着
//这时顾客在理发
}else ｛ //没有空着的椅子
//不好彩
V（互斥信号标） //不要忘记释放被锁定的椅子
//顾客没有理发就走了
｝
｝
|
4
|
三个烟鬼的问题 |
这也是计算机领域的并发问题，最早是1971年S.S.Patil讲述的。
问题描述
假设一支香烟需要：1、烟草；2、卷烟纸；3、一根火柴。
假设一张圆桌上围座着三烟鬼。他们每个人都能提供无穷多的材料：一个有无穷多的烟草；一个有无穷多的卷烟纸；一个有无穷多的火柴。
假设还有一个不吸烟的协调人。他每次都会公正地要求两个人取出一份材料放到桌，然后通知第三个人。第三个人从桌上拿走另外两个人的材料，再加上自己的一份，卷一枝烟就会抽起来。这时，协调人看到桌上空了，就会再次随机叫两人向桌上贡献自己的材料。这个过程会无限地进行下去。
不会有人把桌上的东西藏起来。只有当他抽完一枝烟后，才会再卷另一枝。如果协调人将烟草和卷烟纸放到桌上，而那个有火柴的人仍在吸烟，那么烟草、卷烟纸就会原封不动地放在桌上，走到有火柴的人抽完烟取走桌上的材料。
这个问题是想模拟一个软件程序中的四个角色，只使用了一部分同步前提条件。在PATIL的讲解中，只有一个同步前提条件是：信号标（semaphore），四个程序都不允许有条件地“跳转”，只能有一种由信号标操作提供的有条件的“等待”。
观点
PATIL的观点是Edsger Dijstra的信号标方法作用有限。他用“三个烟鬼的问题”来证明这一点，即这种情况下信号标不能解决问题。但是，PATIL为自己的辩解添加了两个限制条件：
1、 代码不能修改。
2、 解决方案不能使用有条件的语句或使用信号标数组。
如果加上这两个限制条件，三个烟鬼的问题没有办法解决了。Downey曾其撰写的《信号标的小册子》里表示，第一个限制条件是有意义的。因为如果代码代表的是一个操作系统，每来一个新的应用程序都要修改它不但不合理，也是不可能的。但是，就像David Parnas指出的那样，第二个限制条件让重大的问题无法解决。
解决方案
如果我们取消第二个限制条件，使用二位信号标就可以解决“三个烟鬼的问题”。我们可以定义一个二位信号标数组A，每个烟鬼一个，桌子也有一个对应的二进制信号标T。将烟鬼的信号标初始化为0，桌子的初始化为1。于是，协调人的代码为：
While true {
Wait (T);
公正地随机地选择烟鬼i和j，第三个为k；
Signal(A[k]);
}
烟鬼的代码为：
While true {
Wait (A[i]); 卷一枝烟
Signal (T); 抽一枝烟
}
|
5
|
读者-作者问题 |
读者-作者问题
第一和第二读者-作者问题是并行计算的模拟。这两个问题描述的是有许多线程必须同时访问共享的内存地址，有的要读，有的要写。在通常的限制条件下，在一个进程正在写入的时候，其它的进程不能读，也不能写那个共享的内存块。特别要说的是，两个或多个读者可以同时访问同一内存地址。一般来说，会使用一种叫“读-写锁”（readers-writer lock）的数据结构来解决这类问题。
第一读者-作者问题
假设我们有一个共享内存区，使用了以上提到的限制技术。使用一个互斥信号标（mutex）来保护共享的数据是可能的，这时很显然当一个过程在写入时其它进程不能访问。但是这个方案不是很经济。因为如果一个读者R1拿到了“锁”，而另一个读者R2应该也可以要求访问。如果R2非得等到R1完成了才能去操作是不是很傻？所以，R2就直接去读了。这就是第一读者-作者问题的动机。限制条件变成了“如果共享内存正在被读，其它的读者不应该苦等”。这就是读者优先法则。
第二读者-作者问题
假如我们有一个受到互斥信号标（Mutex）保护的共享内存区。上面那个方案也是不经济的。因为很可能会发生当读者R1锁住了内存，而作者W必须等着拿到那个锁后才能写入。然后又有一个读者R2要求访问。于是R2挤到W前面去了。如果这情况一直继续下去，我们会把W“饿死”。实际上，W应该马上动手操作。这就是第二读者-作者问题的动机。限制条件变成了“如果一个作者在排队，就不应该让它等得太久”。这就是作者优先法则。
这个问题的解决方案示意如下：
int readcount, writecount; (initial value = 0)
semaphore mutex 1, mutex 2, mutex 3, w, r ; (initial value = 1)
READER
P(mutex 3)
P(r);
P(mutex 1);
readcount := readcount + 1;
if readcount = 1 then P(w);
V(mutex 1);
V(r);
V(mutex 3)
reading is done
P(mutex 1);
readcount := readcount - 1;
if readcount = 0 then V(w);
V(mutex 1);
WRITER
P(mutex 3);
P(mutex 2);
writecount := writecount + 1;
if writecount = 1 then P(r);
V(mutex 2);
V(mutex 3);
P(w);
writing is performed
V(w);
P(mutex 2);
writecount := writecount - 1;
if writecount = 0 then V(r);
V(mutex 2);
第三读者-作者问题
实际上，以上两个方案都会导致“饿死”的情况发生。第一读者-作者问题的方法可能会“饿死”队列中的作者；第二读者-作者问题的方法可能会“饿死”读者。所以，人们提出了第三读者-作者问题的解决方案，即“不能允许有线程被饿死”。即取得一个共享内存区的锁定权的操作要在一个限定的时间内结束。这个解决方案会在共享内存区可以读的时候让读者等待，或者让作者等更长一段时间。