tulipsys.htm

生产者与消费者问题

                  href="http://www.tulipsys.com/OSC/Chapter7.htm#Top"><IMG 
                  height=25 alt=#Top src="TULIPSYS.files/Return.jpg" width=29 
                  border=0></A><BR>　　7.2节所描述的解决互斥问题的方法以及在此给出的信号量定义的主要缺点在与于它们需要繁忙等待（busy 
                  waiting）。当一个进程处于临界区时，其它试图进入临界区的进程必须在进入区代码中持续循环运行。在多道程序系统（多个进程共享一个单独的CPU）中，这种持续循环显然是个问题。繁忙等待浪费了CPU周期，而其它进程可以有效利用这些时间。这种类型的信号量也被称为自旋锁（因为进程在等待锁时“自旋”）。自旋锁（spinlock）在多处理机系统中非常有用。自旋锁的优点是当进程必须等待锁时没有上下文转换，而上下文转换（context 
                  switch）需要一定的时间。这样，当期望短时间持有锁时，自旋锁很有用。（注：这儿我不明白，甚至自旋锁名称的来源也不理解，外国人的想法给我们不太一样。意思是，进程在等待进入临界区时不要利用一个循环来等待，而是阻塞自己，或者说进入阻塞队列，那么这一定需要上下文转换的？！但是上下文转换的时间应该比循环少）<BR>　　为了克服对繁忙等待的需求，我们修改wait和signal信号量操作的定义。当一个进程执行wait操作且信号量不为正时，它必须等待。然而，进程可以阻塞（block）自身，而不是繁忙等待。block操作将一个进程置入与该信号量关联的等待队列中并将进程状态设为等待。那么，CPU调度程序获得控制，就可以选择另一个进程执行。<BR>　　一个被阻塞而等待信号量S的进程应该能够在其它进程执行signal操作后被重新开始。wakeup操作重新开始进程，它把进程的状态从等待状态转为就绪状态。于是进程被置入就绪队列。（CPU可能会从正在运行的进程转向新的就绪进程，也可能不会，这与CPU调度算法有关）<BR>　　为了在这个定义下实现信号量，我们以“C”结构定义一个信号量：<BR>　　typedef 
                  struct {<BR>　　　int value;<BR>　　　struct process *L;<BR>　　} 
                  semaphore;<BR>　　每个信号量有一个整形数和一个进程列表。当一个进程必须等待一个信号量时，它就被添加到进程列表中。signal操作将进程从等待进程列表中移除并唤醒该进程。<BR>　　wait操作定义如下：<BR>　　void 
                  wait(semaphore S) {<BR>　　　S.value--;<BR>　　　if (S.value &lt; 0) 
                  {<BR>　　　　add this process to S. L;<BR>　　　　block( 
                  );<BR>　　　}<BR>　　}<BR>　　signal操作定义如下：<BR>　　void 
                  signal(semaphore S) {<BR>　　　S.value++;<BR>　　　if (S.value &lt;= 
                  0) {<BR>　　　　remove a process P from S. L;<BR>　　　　wakeup 
                  (P);<BR>　　　}<BR>　　}<BR>　　block操作将挂起调用它的进程。wakeup(P)操作恢复执行一个被阻塞的进程。这两个操作由操作系统作为基本的系统调用提供。<BR>　　注意，虽然在传统的需要繁忙等待的信号量定义下的信号量不会为负，但是这个实现中信号量可能为负。如果信号量为负，那么它的大小也就是等待该信号量的进程数目。这是因为我们交换了wait操作中减一和测试语句的顺序。使用一个链接每个进程控制块（PCB）的链表可以很容易的实现等待进程列表。One 
                  way to add and remove processes from the list, that ensures 
                  bounded waiting would be to use a FIFO queue, where the 
                  semaphore contains both head and tail pointers to the queue. 
                  通常，然而，列表可以采用任何排队策略（queueing 
                  strategy）。对信号量的正确使用不应该依赖于特定的对信号量列表的排队策略。<BR>　　信号量的关键特征是执行的原子性。我们必须确保没有两个进程可以同时对同一个信号量执行wait和signal操作。这是临界区问题，有两种方法可以解决。<BR>　　在单处理机环境中（更确切的说就是只存在一个CPU），我们可以简单的在wait和signal操作执行的过程中禁止中断。这种方案在单处理机环境中可行，因为一旦中断被禁止，那么就不可以执行别的进程的指令。在中断重新启用且调度程序重新获得控制之前只有当前运行的进程执行。<BR>在多处理机环境中不可以禁止中断。不同进程的指令（运行在不同的处理器上）可能会以任意的顺序交叉执行。如果硬件没有提供特殊的指令，我们可以采用某些针对临界区问题（临界区由wait和signal过程组成）的软件解决方案（7.2节）。<BR>　　必须承认不可能凭借对wait和signal的定义完全消除繁忙等待。相反，我们把繁忙等待从进入应用程序临界区的过程中移除了。更进一步讲，我们仅仅限制了对wait和signal操作的临界区的繁忙等待，而这些区又非常短（如果编码合适，应该不多于10条语句）。这样，临界区几乎不会被占用，繁忙等待也很少发生，即使发生也只有很短的时间。一个完全不同的情况是，应用程序的临界区可能会很长（数分钟或数小时）或可能几乎总被占据。在这种情况下，繁忙等待相当的低效。<BR>　　<STRONG><A 
                  name=死锁和饥饿></A>7.4.3 死锁和饥饿</STRONG><A 
                  href="http://www.tulipsys.com/OSC/Chapter7.htm#Top"><IMG 
                  height=25 alt=#Top src="TULIPSYS.files/Return.jpg" width=29 
                  border=0></A><BR>　　具备一个等待队列的信号量实现可能会导致这样的一个情况：两个或多个进程无休止的等待发生一个事件，而这个事件只能由等待中的某个进程引发。问题中的这个事件是指signal操作的执行。当达到这样的一个状态时，我们称这些进程被死锁（deadlock）。<BR>　　考虑由两个进程P0和P1组成的系统，这两个进程都要访问S和Q这两个信号量，将其值设为1：<BR>　　　　　　　　　　　　　　　P0　　　　 
                  P1<BR>　　　　　　　　　　　　　　wait(S);　 
                  wait(Q);<BR>　　　　　　　　　　　　　　wait(Q); 
                  　wait(S);<BR>　　　　　　　　　　　　　　signal(S); 
                  signal(Q);<BR>　　　　　　　　　　　　　　signal(Q); 
                  signal(S);<BR>　　假设P0执行wait(S)，然后P1执行wait(Q)。当P0执行wait(Q)时，它必须等待P1执行完signal(Q)。 
                  类似的，当P1执行wait(S)时，它必须等待执P0行完signal(S)。因为这些signal操作是不可能被执行的，所以P0和P1被死锁。<BR>　　在一组进程中，当每个进程都在等待其它进程发生的事件时，我们说这组进程处于死锁状态。我们在此主要涉及的事件是资源的获取和释放。然而，其它类型的事件可能引发死锁，如第八章所示。在第八章中，我们将讨论用于处理死锁问题的各种机制。<BR>　　涉及死锁的另一个问题是无限阻塞（indefinite 
                  blocking）或饥饿，此时进程在信号量中无休止的等待。（Another problem related to 
                  deadlocks is indefinite blocking or starvation, a situation 
                  where processes wait indefinitely within the 
                  semaphore.）如果我们以LIFO顺序在与一个信号量关联的列表中添加和删除进程，就有可能发生无限等待。<BR>　　<A 
                  name=二元信号量></A><STRONG>7.4.4 二元信号量</STRONG><A 
                  href="http://www.tulipsys.com/OSC/Chapter7.htm#Top"><IMG 
                  height=25 alt=#Top src="TULIPSYS.files/Return.jpg" width=29 
                  border=0></A><BR>　　上一节所描述的信号量一般被称为计数信号量，因为它的整数值在一个无限制的范围内。而二元信号量的整数范围在0到1之间（也就是说不是1就是0）。实现二元信号量要比实现计数信号量简单，这取决于底层硬件结构。现在我们说明怎样利用二元信号量来实现一个计数信号量。<BR>设计数信号量S。为了以二元信号量的方法来实现，我们需要定义如下的数据结构：<BR>　　binary-semaphore 
                  S1, S2;<BR>　　int C;<BR>　　初始S1 = 1，S2 = 
                  0且令整形数C的值于计数信号量S的初始值相等。<BR>　　计数信号量S的wait操作的实现如下：<BR>　　wait(S1);<BR>　　C--;<BR>　　if(C 
                  &lt; 0) 
                  {<BR>　　　signal(S1);<BR>　　　wait(S2);<BR>　　}<BR>　　signal(S1);<BR>　　计数信号量S的signal操作的实现如下：<BR>　　wait(S1);<BR>　　C++;<BR>　　if(C 
                  &lt;= O)<BR>　　　signal(S2);<BR>　　else<BR>　　　signal(S1);<BR>　　<A 
                  name=经典的同步问题></A><STRONG>7.5 经典的同步问题</STRONG><A 
                  href="http://www.tulipsys.com/OSC/Chapter7.htm#Top"><IMG 
                  height=25 alt=#Top src="TULIPSYS.files/Return.jpg" width=29 
                  border=0></A><BR>　　我们将在本节描述一些不同的同步问题，把这些问题作为并行控制问题这一大类的例子。这些问题用于测试几乎所有新提出的同步问题解决方案。我们在方案中使用信号量。<BR>　　<A 
                  name=有限缓冲区问题></A><STRONG>7.5.1 有限缓冲区问题</STRONG><A 
                  href="http://www.tulipsys.com/OSC/Chapter7.htm#Top"><IMG 
                  height=25 alt=#Top src="TULIPSYS.files/Return.jpg" width=29 
                  border=0></A><BR>　　7.1节介绍了有限缓冲区问题；这个问题通常用来阐明同步原语的作用。在此，我们只是表示这个机制的一般结构而不涉及具体实现。假设缓冲池由n个缓冲区构成，每个缓冲区可以容纳一个条目。信号量mutex提供对缓冲池的互斥访问，初始值为1。信号量empty和full分别记录空缓冲区和满缓冲区的数量。信号量empty的初始值为n；信号量full的初始值为0。<BR>　　图7.12描述了生产者进程的代码；图7.13描述了消费者进程的代码。请注意生产者和消费者之间的对称关系。可以这么解释这些代码：生产者为消费者生产满缓冲区，而消费者为生产者生产空缓冲区。</P>
                  <P>　　　　　　<IMG height=253 src="TULIPSYS.files/7.12.jpg" 
                  width=380></P>
                  <P>　　　　　　<IMG height=240 src="TULIPSYS.files/7.13.jpg" 
                  width=390><BR>　　<A name=读者写者问题></A><STRONG>7.5.2 
                  读者－写者问题</STRONG><A 
                  href="http://www.tulipsys.com/OSC/Chapter7.htm#Top"><IMG 
                  height=25 alt=#Top src="TULIPSYS.files/Return.jpg" width=29 
                  border=0></A><BR>　　多个并发进程共享一个数据对象（如一个文件或记录）。其中有些进程只是读取这些共享数据的内容，而其它进程可能想要更新共享对象（更确切的说，是读和写）。我们称只是要读取共享对象的进程为读者，其余为写者，以此来区别对待这两种进程类型。显然，如果有两个读者同时访问共享对象，那么不会造成任何不利的影响。然而，如果一个写者和其它一些进程（一个读者或一个写者）同时访问共享对象，就有可能造成混乱局面。<BR>　　为了确保避免产生这些问题，我们要求写者互斥访问共享对象。这个同步问题被称为读者－写者问题（readers-writers 
                  problem）。自最初提出以来，它被用于测试几乎所有的新同步原语。读者－写者问题有多个变种，都包含了优先权机制。最简单的一种被称为第一读者－写者问题（first 
                  readers-writers 
                  problem），它要求没有读者保持等待，除非是有一个写者已经获取了使用共享对象的许可。换句话说，读者不应该等待其它读者结束。（In 
                  other words, no reader should wait for other readers to finish 
                  simply because a writer is 
                  waiting.）第二读者－写者问题要求写者就绪后尽可能迅速的执行它的写工作。换句话说，如果一个写者等待访问对象，那么不会再有新的读者开始读取。</P>
                  <P>　　　　　　<IMG height=165 src="TULIPSYS.files/7.14.jpg" 
                  width=360><BR>　　这两个问题的解决方案都可能造成饥饿。在第一种情况下，写者可能会饥饿；在第二种情况下，读者可能会饥饿；为此，提出了该问题的其它的变种。（in 
                  the second case, readers may starve. For this reason, other 
                  variants of the problem have been 
                  proposed.）在本节，我们描述一种解决第一读者－写者问题的方案。查阅本章后面的注记来获取关于读者－写者问题的饥饿解除方法的参考材料。<BR>　　在对第一读者－写者问题的解决方案中，读者进程共享如下的数据结构：<BR>　　semaphore 
                  mutex, wrt;<BR>　　int 
                  readcount;<BR>　　信号量mutex和wrt被初始化为1；readcount被初始化为0。信号量wrt为读者和写者所共用。mutex用于确保对变量readcount更新的互斥性。变量readcount保存了当前读取对象的进程数量。信号量wrt的功能与用于写者的互斥信号量如出一辙。（The 
                  semaphore wrt functions as a mutual-exclusion semaphore for 
                  the 
                  writers.）进入或退出临界区的第一个或最后一个读者也会调用它。当有读者处于临界区时，其它的读者在进入或退出临界区时不会调用它。<BR>　　写者进程的代码如图7.14所示；图7.15描述了读者进程的代码。注意到，如果有一个写者在临界区中，n个读者等待，那么一个读者关于wrt排队，n-1个读者关于mutex排队。可以看到，当一个写者执行signal(wrt)时，我们可能恢复执行另外多个等待的读者或一个单独等待的写者。调度程序做出这个选择。</P>
                  <P>　　　　　　<IMG height=286 src="TULIPSYS.files/7.15.jpg" 
                  width=380><BR>　　<STRONG><A name=哲学家进餐问题></A>7.5.3 
                  哲学家进餐问题</STRONG><A 
                  href="http://www.tulipsys.com/OSC/Chapter7.htm#Top"><IMG 
                  height=25 alt=#Top src="TULIPSYS.files/Return.jpg" width=29 
                  border=0></A><BR>　　考虑五个一起思考和进餐的哲学家。他们使用一个圆桌，圆桌周围有五个椅子，每个哲学家一把。桌子的中央有一碗米饭，而且桌子上放置着5只筷子（图7.16）。哲学家在思考的时候并不与其它哲学家交流。哲学家有时会感到饥饿并设法拿到最近的两个筷子（她左右两边的筷子）。哲学家一次只能够拿起一支筷子。显然，她不能够拿到邻居手中的筷子。当哲学家同时拿到了两支筷子时才可以吃饭。吃饱后，她放下这两支筷子继续思考。</P>
                  <P>　　　　　　<IMG height=281 src="TULIPSYS.files/7.16.jpg" 
                  width=400><BR>　　哲学家进餐问题被认为是一个经典的同步问题，并不是因为它具有实际意义上的重要性，也不是因为计算机科学家不太喜欢哲学家，而是因为它是并行控制这类问题的一个例子。它简单的描述了以死锁和饥饿解除方式在多个进程之间分配多个资源的方法。（It 
                  is a simple representation of the need to allocate several 
                  resources among several processes in a deadlock- and 
                  starvation- free 
                  manner.）<BR>　　一个简单的方案是利用信号量来表示每个筷子。哲学家通过执行一个信号量上的wait操作来获取筷子；通过执行相应信号量上的signal操作来释放筷子。如此，共享数据是：<BR>　　　　　　　　　　　　semaphore 
                  chopstick[5];<BR>　　数组元素chopstick都被初始化为1。哲学家i的结构如图7.17所示。</P>
                  <P>　　　　　　<IMG height=267 src="TULIPSYS.files/7.17.jpg" 
                  width=380><BR>　　虽然这种解决方案保证了相邻的哲学家不能同时进餐，但是仍然不够，因为它可能会造成死锁。假设五个哲学家同时饥饿，而且每个哲学家都得到了其左侧的筷子。现在所有的chopstick等于0。当每个哲学家试图获取她右侧的筷子时，她将永远等下去。<BR>　　稍后列举了几种可能的纠正死锁问题的方法。在7.7节，我们描述一种解决哲学家进餐问题的方案，它可以确保从死锁中解除。<BR>　　同时最多允许四个哲学家围坐在桌子周围。<BR>　　只有在哲学家两侧的筷子都可用时才允许她捡起筷子（为此，她必须在临界区中操作）。<BR>　　应用不对称机制；也就是说，奇数哲学家先捡起左侧的筷子再捡起右侧的筷子，而偶数哲学家先捡起右侧的筷子再捡起左侧的筷子。<BR>　　最后，任何令人满意的哲学家进餐问题的解决方案必须要确保哲学家不会被饿死。死锁解除方案并不能消除饿死的可能性。<BR>　　<A 
                  name=临界区域></A><STRONG>7.6 临界区域</STRONG><A 
                  href="http://www.tulipsys.com/OSC/Chapter7.htm#Top"><IMG 
                  height=25 alt=#Top src="TULIPSYS.files/Return.jpg" width=29 
                  border=0></A><BR>　　虽然信号量提供了一个方便有效的进程同步机制，但是对它们的不正确使用仍能导致难以察觉的同步错误（timing 
                  error）。这些错误之所以难以被发现是因为它们只会发生在一些特定执行序列中，而且这些执行序列并不总会出现。<BR>　　我们已经在生产者－消费者问题（7.1节）的解决方案里对计时器的使用中看到了这种错误类型的例子。在那个例子里，很少会发生同步问题，即使在发生时计数器的值也比较合理——偏差只有1。否则，这种方法显然就不可行。因此，信号量才第一次被提出。<BR>　　然而，在使用信号量时仍有可能发生这样的同步错误。为了说明这一点，我们回顾一下利用信号量解决临界区问题的方法。所有的进程共享一个信号量变量mutex，它的初始值为1。每个进程进入临界区之前必须执行wait(mutex)，退出临界区之后执行signal(mutex)。如果不遵守这个顺序，那么可能同时会有两个进程在各自的临界区内。<BR>　　让我们分析一下可能会出现什么样的问题。要注意，即使是单独的一个进程，如果它的行为不恰当，那么也会出现这些问题。（Note 
                  that these difficulties will arise if even a single process is 
                  not well behaved.）一个真正的程序错误或一个不合作的程序员（uncooperative 
                  programmer）都有可能导致这样的情况出现。<BR>　　假如一个进程交换了对信号量mutex的wait和signal 
                  操作的位置，如下：<BR>　　signal(mutex);<BR>　　　...<BR>　　critical 
                  section<BR>　　　...<BR>　　wait(mutex);<BR>　　这样，可能会有多个进程同时在临界区中执行，这就破坏了互斥条件。只有在多个进程同时在它们的临界区中执行时才有可能发现这个错误。要注意，这种情况并不总是可以出现。<BR>　　假如一个进程的signal(mutex)操作为wait(mutex)操作所取代。也就是说，它执行<BR>　　wait(mutex);<BR>　　　...<BR>　　critical 
                  section<BR>　　　...<BR>　　wait(mutex);<BR>这样，将发生死锁。<BR>　　假如一个进程遗漏了wait(mutex)或signal(mutex)，或二者。这样，或者破坏了互斥条件或者将发生死锁。<BR>　　这些例子阐明：在利用信号量解决临界区问题时很容易产生各种类型的错误。类似的错误也会发生在7.5节讨论的其它同步模型中。<BR>　　为了解决我们所描述的错误类型，引入了许多高级语言结构。在本节，我们描述一种基本的高级同步结构——临界区域（有条件临界区域）。在7.7节，我们描述另一种基本同步结构——管程（monitor）。在我们对这两个结构的描述里，假设一个进程由一些本地数据和一个能够操作数据的顺序程序（sequential 
                  program）构成。局部数据只能由封装在同一个进程里的顺序程序访问。更确切的说，一个进程不能直接访问另一个进程的本地数据。然而进程可以共享全局数据。<BR>　　临界区域高级语言同步结构需要一个由多个进程共享的T类型的变量v，定义如下：<BR>　　　　　　　　　　　　　v: 
                  shared T;<BR>　　对变量v的访问只能通过如下形式的区域内部的语句进行：<BR>　　　　　　　　　　　region 
                  v when(B) do 
                  S;<BR>　　这个结构意味着，当语句S执行时，其它的进程不可以访问变量v。表达式B是一个布尔表达式，它管理对临界区域的访问。当一个进程试图进入临界区区域（critical-section 
                  region）时，就会计算表达式B。如果表达式是true，那么执行语句S。如果是false，那么进程放弃并延迟，直到B变为true且无其它进程在区域内与v有关联。如此，如果如下两个语句同时被各自的进程执行，那么其结果将等同于执行序列“先执行S1，再执行S2”或“先执行S2，再执行S1”。<BR>　　　　　　　　　　　region 
                  v when(true) S1;<BR>　　　　　　　　　　　region v when(true) 
                  S2;<BR>　　临界区域结构确保不会发生临界区问题的信号量方案中可能由程序员造成的某些简单错误。注意，它不能消除所有的同步错误；相反，它减少了错误的数量。如果在程序的逻辑上发生错误，那么重新构造一个执行序列并不是那么简单。<BR>　　可以有效地利用临界区域构造解决某些通常的同步问题。为了说明这一点，我们对有限缓冲区机制进行编码。缓冲区和它的指针被封装在buffer结构中：<BR>　　　　　　　　　　struct 
                  buffer{<BR>　　　　　　　　　　　item pool[n];<BR>　　　　　　　　　　　int count, 
                  in, 
                  out;<BR>　　　　　　　　　　};<BR>　　消费者进程向共享缓冲区中插入新条目nextp代码如下：<BR>　　　　　　　　　region 
                  buffer when(count &lt; n)<BR>　　　　　　　　　　pool[in] = 
                  nextp;<BR>　　　　　　　　　　in = (in + i) % 
                  n;<BR>　　　　　　　　　　count++;<BR>　　　　　　　　　}<BR>　　消费者进程从共享缓冲区中移除一个条目并将其置入nextc中的代码如下：<BR>　　　　　　　　　region 
                  buffer when(count &gt; 0)<BR>　　　　　　　　　　nextc = 
                  pool[out];<BR>　　　　　　　　　　out = (out + l) % 
                  n;<BR>　　　　　　　　　　count--;<BR>　　　　　　　　　}<BR>　　让我们说明编译器实现有条件临界区域的方法。对于每个共享变量，有如下的变量与之关联：<BR>　　semaphore 
                  mutex, first_delay, second_delay;<BR>　　int first_count, 
                  second_count;<BR>　　信号量mutex初始化为1；信号量first_delay和second_delay初始化为0。整形数first_count和second_count初始化为0。<BR>　　通过mutex提供对临界区的互斥访问。如果一个进程因为布尔条件B