tulipsys.htm

生产者与消费者问题

                  有空让进（Progress）：如果没有进程处于临界区而此时有进程希望进入临界区，那么只可以从这些不在剩余区执行的进程中挑选出下一个进入临界区的进程，而且这个选择不可以长时间的延缓。<BR>　　3. 
                  有限等待（Bounded 
                  Waiting）：在一个进程请求进入临界区之后和获准之前，允许其它进程在有限的时间内进入临界区。<BR>假设每个进程的执行速度大于零。然而，我们没有关于n个进程的相对速度（relative 
                  speed）的假设。<BR>　　在7.2.1和7.2.2节，我们逐步建立满足这三个要求的临界区问题的解决方案。这些方案并不依赖于任何关于硬件指令或硬件所支持的处理器数量的假设。但是，我们要假设基本的机器语言（基本的指令，如：load、store和test）指令被原子的执行。也就是说，如果有两个这样的指令并行执行，那么其结果等同于二者以任意未知的顺序执行。如此，如果同时执行一个load和一个store，那么load将获得一个旧的数据或一个新的数据，而不是这两者之间的什么。<BR>　　表示一个算法时，我们只定义用于同步并只描述一个典型的进程Pi（图7.1表述了它的通常的结构）的变量。把它的进入区和退出区用方框围绕起来是为了突出这些代码的重要性。</P>
                  <P>　　　　　　<IMG height=234 src="TULIPSYS.files/7.2.jpg" 
                  width=420><BR>　　<A name=两个进程的方案></A><STRONG>7.2.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>　　我们在这一节只考虑同时只有两个进程的情况。进程编号为P0和P1。为了方便起见，用Pi表示一个进程，Pj表示另一个；于是j 
                  = = 1 - i。<BR>　　<A name=算法1></A><STRONG>7.2.1.1 算法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>　　第一个方法是使进程共享一个公有整形变量turn，它被初始化为0（或1）。如果turn 
                  = = 
                  i，那么进程Pi被允许在其临界区内执行。进程Pi的结构如图7.2。<BR>　　这种方案确保了一次只有一个进程可以在临界区执行。然而它不能满足有空让进条件，因为在临界区的执行上它需要严格的进程交替。例如，如果turn 
                  = = 0并且P1准备进入临界区，但是P1却做不到，即使P0可能此时处于剩余区。<BR>　　<A 
                  name=算法2></A><STRONG>7.2.1.2 算法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>　　算法1的问题在于它不能够为每个进程维护足够的状态信息；它只是记住了哪个进程被允许进入临界区。为了改善这一点，我们使用如下的数组来代替变量turn：<BR>　　　　　　　　　　　　　　　　　boolean 
                  flag[2];<BR>　　数组中的元素被初始化为false。如果flag[i]是true，那么这个值指明Pi就绪（ready）（进入临界区）。图7.3表示了进程Pi的结构。<BR>　　在这个算法中，进程Pi首先设置flag[i]为true，说明它就绪（进入临界区）。然后，Pi检查核实进程Pj没有就绪。如果Pj 
                  就绪，那么Pi将等待，直到Pj声明自己不再需要处于临界区中（就是直到flag[j]为false）。此时，Pi将进入临界区。在退出临界区时，Pi将flag[i]设为false，以允许其它进程（如果它正在等待）进入临界区。</P>
                  <P>　　　　　<IMG height=273 src="TULIPSYS.files/7.3.jpg" 
                  width=450><BR>　　在这种方案中，互斥需求得到了满足。但是没有满足有限等待条件。为了阐明这个问题，考虑如下的执行序列：<BR>　　T0: 
                  P0 sets flag[0] = true<BR>　　T1: P1 sets flag[1] = 
                  true<BR>　　现在P0和P1在各自的while语句中无限循环。<BR>　　这个算法对两个进程同步的精确性依赖严重。The 
                  sequence could have been derived in an environment where there 
                  are several processors executing concurrently, or where an 
                  interrupt (such as a timer interrupt) occurs immediately after 
                  step T0 is executed, and the CPU is switched from one process 
                  to 
                  another.<BR>　　注意，交换设置指令flag[i]和测试flag[j]并不能解决问题。相反，可能会出现两个进程同时处于临界区的情况，这样违背了互斥准则。<BR>　　<A 
                  name=算法3></A><STRONG>7.2.1.3 算法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>　　结合算法1和算法2的思想，我们得到了一个解决临界区问题的正确方案，可以满足三个条件。进程共享两个变量：<BR>　　boolean 
                  flag[2];<BR>　　int turn;<BR>　　初始化flag[0] = flag[1] = 
                  false，turn的值无关紧要（但是0或者是1）。进程Pi的结构如图7.4所示。<BR>　　为了进入临界区，进程Pi首先设定flag[i]为true，turn为j，从而声明：如果其它进程想要进入临界区，请便。如果两个进程同时试图进入临界区，那么turn的值大约同时是i和j。最终只会实现一个赋值；其它的也要发生，但是立即被覆盖。turn最终的值决定哪个进程被允许首先进入临界区。<BR>　　现在证明这个算法的正确性。我们需要证明：<BR>　　1. 
                  确保了互斥原则<BR>　　2. 满足了有空让进原则<BR>　　3. 
                  符合有限等待原则<BR>　　为了证明性质1，我们看到只有flag[j] = = false或turn = = 
                  i时Pi才能够进入临界区。而且，如果两个进程能够同时在临界区中执行，那么flag[0] = = flag[l] = = 
                  true。这两点意味着P0和P1不可能大约在同时执行它们的while语句，因为turn要么是0要么是1，不会二者都是。因此，一个进程，比如Pj，会成功完成while语句，而Pi至少会执行另一条语句（“turn 
                  = = j”）。因为那时flag[j] = = true且turn = = 
                  j，而且只要Pj处于临界区中该条件就会保持下去，如此：满足了互斥原则。</P>
                  <P>　　　　　<IMG height=296 src="TULIPSYS.files/7.4.jpg" 
                  width=450><BR>　　为了证明性质2和3， 注意到进程只有以循环条件flag[j] = = true and 
                  turn = = j执行while语句时才会被阻止进入临界区；这是唯一的一种情况。如果Pj没有就绪，那么flag[j] = 
                  = false，Pi可以进入临界区。如果Pj设置flag[j]为true且正在执行while语句，那么turn = = 
                  i或turn = = j。如果turn = = 
                  j，那么Pj将进入临界区。然而，一旦Pj退出临界区，它必须设置set为i，允许Pi进入临界区。如果Pj重新设置flag[j]为true，也必须将turn设置为i。这样，因为Pi在执行while语句时不能够改变变量turn的值，所以Pi最多在Pj进入一次（有限等待）之后将进入临界区（有空让进）。<BR>　　<A 
                  name=多个进程的临界区问题></A><STRONG>7.2.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>　　算法3解决了两个进程的临界区问题。现在让我们研究解决n个进程的临界区问题的算法。这个算法被称为面包房算法（bakery 
                  algorithm），它基于通常用在面包店、冰激淋店、熟食店、车辆登记处（motor-vehicle 
                  registry）等必须维护好工作顺序的地方。这个算法设计用于分布式环境（distributed 
                  environment），但是这里我们只考虑该算法适用于集中式环境（centralized 
                  environment）的几点特征。<BR>　　进入商店后，每个消费者得到一个数字。下一个得到服务的消费者是持有最小数字的消费者。可是面包房算法不能够确保两个进程（消费者）不会获得同一个数字。在这种情况下（两个进程拥有同样的数字），名称最小的进程首先得到服务。也就是说，如果Pi和Pj接收到了同样的数字，而且如果i 
                  &lt; 
                  j，那么Pi先得到服务。因为进程的名称是唯一的而且总体上是安排好的，所以这个算法完全可行。<BR>　　通常的数据结构如下：<BR>　　boolean 
                  choosing[n];<BR>　　int 
                  number[n];<BR>　　最初，分别初始化这些数据结构为false和0。为了简便，我们定义如下的表示法：<BR>?　(a, 
                  b) &lt; (c, d) if a &lt; c or if a = = c and b &lt; 
                  d.<BR>?　max(a0, ...., an-1) is a number, k, such that k &gt;= 
                  ai for i = 0, ..., n - 
                  1.<BR>　　图7.5列出了用在面包房算法中的进程Pi的结构。<BR>　　现在证明面包房算法的正确性，首先看到：如果Pi处于临界区且Pk 
                  (k != i)已经获得了它的数字k != 0，那么(number[i], i) &lt; (number[k] 
                  ,k)。该算法的证明作为练习7.3。</P>
                  <P>　　　　<IMG height=391 src="TULIPSYS.files/7.5.jpg" 
                  width=550><BR>　　给定这个结果，现在可以很容易证明面包房算法满足了互斥原则。确实，考虑Pi处于临界区而Pk试图进入临界区的情况。当进程Pk执行第二个while语句时，因为当进程Pk执行第二个while语句（j 
                  = = i）时，它会发现：<BR>?　number[i] != 0<BR>?　(number[i] , i) &lt; 
                  (number[k] , 
                  k).<BR>　　这样，它继续在while语句中循环直到Pi离开临界区。<BR>　　如果我们想要证明该算法能够满足有空让进和有限等待条件，而且能够确保公平，那么采用先来先服务算法允许进程进入临界区就足以。<BR>　　<A 
                  name=同步的硬件实现></A><STRONG>7.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>　　硬件可以简化程序设计工作并提高系统效能。（As with other aspects 
                  of software, hardware features can make the programming task 
                  easier and improve system 
                  efficiency.）在本节，我们要讨论许多系统中都有的一些简单的硬件指令，并介绍在临界区问题中如何有效地利用这些指令。<BR>　　如果在对共享变量进行修改期间禁止中断，那么在单处理机环境中就可以轻而易举解决临界区问题。以这种方式，我们可以确保当前的指令序列有序执行而不会被抢占。因为没有其它的指令可以执行，所以不会对共享变量有意外的修改。<BR>　　然而这种解决方案不适于多处理机环境。在多处理机中禁止中断会消耗大量的时间，因为需要把消息传送给所有的处理器。消息传送延迟会影响到每个临界区，而且会降低系统效率。另外，还要考虑对系统时钟的影响，如果系统时钟是靠中断来更新的，那会怎样？<BR>　　有些机器提供了专门的硬件指令，允许我们原子地（atomically）测试或修改一个字（word）或交换两个字的内容——也就是说，把这些操作作为一个不可中断的单元。利用这些专门的指令，我们可以以一种相对简单的方式来解决临界区问题。在此，我们并不讨论具体某个机器的具体指令，而是要抽象出这些指令类型的主要概念。<BR>　　图7.6展示了TestAndSet指令的定义。该指令最大的特点是它执行的原子性。这样，如果两个TestAndSet指令同时执行（在不同的CPU上），那么它们的顺序可以是以任意的。</P>
                  <P>　　　　　<IMG height=125 src="TULIPSYS.files/7.6.jpg" 
                  width=400><BR>　　如果机器支持TestAndSet指令，我们就可以通过声明一个布尔变量lock（初始化为false）来实现互斥。图7.7表示了进程Pi的结构。</P>
                  <P>　　　　<IMG height=222 src="TULIPSYS.files/7.7.jpg" 
                  width=460><BR>Swap指令（图7.8）操作两个字；如同TestAndSet指令，它也是原子执行的。</P>
                  <P>　　　　　<IMG height=153 src="TULIPSYS.files/7.8.jpg" 
                  width=400><BR>如果机器支持Swap指令，那么可以通过如下的方法实现互斥。声明一个全局布尔变量lock（初始化为false）来实现互斥。另外，为每个进程设置一个局部布尔变量key。图7.9表示了进程Pi的结构。</P>
                  <P><IMG height=317 src="TULIPSYS.files/7.9.jpg" 
                  width=600><BR>这些算法并不能满足有空让进原则。图7.10中描述了一个利用TestAndSet指令的算法。该算法满足了所有的临界区需求。通常的数据结构如下：<BR>　　boolean 
                  waiting[n];<BR>　　boolean lock;<BR>　　这些数据结构初始化为false。进程Pi 
                  只有在waiting[i] = = false或key = = 
                  false时才可以进入临界区。只有在TestAndSet执行时key的值可以为false。第一个进程执行TestAndSet时会发现key 
                  = = 
                  false；其它进程都必须等待。只有在其它的进程离开临界区之后，变量waiting[i]才可以变为false；只有一个waiting[i]被设为false（注：数组waiting中同时只能有一项为false），这样维护了互斥原则。</P>
                  <P>　　　　　<IMG height=433 src="TULIPSYS.files/7.10.jpg" 
                  width=500><BR>　　为了证明符合有限等待原则，我们注意到：用于表示互斥的参数在这儿也会用到，因为进程在退出临界区时或者设定lock为false或者设定waiting[j]为false。这都允许等待进入临界区的进程继续运行。<BR>　　为了证明符合有空让进原则，我们注意到：当一个进程离开它的临界区时，它以循环顺序（cyclic 
                  ordering）（i + 1, i + 2, ..., n - 1, 0, ..., i - 
                  1）扫描数组waiting。它指明：以这个顺序，第一个处于进入区的进程（waiting[j] = = 
                  true）接下来进入临界区。任何等待进入临界区的进程在n – 
                  1次之内都有机会进入临界区。但是，对于硬件设计者来说，实现原子TestAndSet指令绝非轻而易举。在计算机体系结构的教材中有对这种实现的讨论。<BR>　　<STRONG><A 
                  name=信号量></A>7.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>　　7.3节讨论的临界区问题的解决方案难以适用于更为复杂的问题。为此，我们可以使用一种被称为信号量的同步工具。信号量S是一个整形数，除初始化以外，对它的访问只能通过两个标准原子操作：wait和signal。最初，这被称为P操作(for 
                  wait; from the Dutch proberen, to test)和V操作(for signal; from 
                  verhogen, to increment)。典型的wait定义用伪代码表示如下：<BR>　　wait (S) 
                  {<BR>　　while (S &lt;= 0)<BR>　　; //no-op<BR>　　S--;<BR>　　) 
                  <BR>　　典型的signal定义用伪代码表示如下：<BR>　　signal (S) 
                  {<BR>　　S++;<BR>　　}<BR>　　在wait操作和signal操作中对信号量的修改必须是不可分割的。这样，当一个进程修改信号量时，其它进程不可以同时修改这个信号量。另外，就wait(S)来说，它测试S的值（S 
                  &lt;= 
                  0）并可能对其进行修改（S--），这些操作在执行时也必须不受中断的干扰。我们将在7.4.2节看到如何实现这些操作；首先让我们看一下如何使用信号量。<BR>　　<STRONG><A 
                  name=用法></A>7.4.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>　　使用信号量可以处理n个进程的临界区问题。这n个进程共享一个信号量mutex（代表互斥条件），将其初始化为1。进程Pi的组织方式如图7.11。<BR>　　也可以利用信号量来解决多种同步问题。例如，考虑两个同时运行的进程：P1有个语句S1，P2有个语句S2。假如我们需要只有在S1完成之后S2才能执行。那么可以使和共享一个信号量synch（初始化为0），并在P1中插入语句：<BR>　　S1;<BR>　　signal 
                  (synch);<BR>　　在P2中插入语句：<BR>　　wait 
                  (synch);<BR>　　S2;<BR>　　因为synch被初始化为0，P2只有在P1调用之后才会执行S2，也就是S2在S1执行后执行。</P>
                  <P>　　　　<IMG height=260 src="TULIPSYS.files/7.11.jpg" 
                  width=500><BR>　　<STRONG><A name=实现></A>7.4.2 实现</STRONG><A