tulipsys.htm

生产者与消费者问题

                  href="http://www.tulipsys.com/OSC/Chapter7.htm#Solaris2中的同步机制">7.8.1 
                  Solaris 2中的同步机制</A></SPAN></SPAN></TD></TR>
              <TR>
                <TD borderColor=#009900><SPAN class=style35><SPAN 
                  class=style31>　<A 
                  href="http://www.tulipsys.com/OSC/Chapter7.htm#Windows2000中的同步机制">7.8.2 
                  Windows 2000中的同步机制</A></SPAN></SPAN></TD></TR>
              <TR>
                <TD borderColor=#009900><SPAN class=style35><SPAN 
                  class=style31><A 
                  href="http://www.tulipsys.com/OSC/Chapter7.htm#原子事务">7.9 
                  原子事务</A></SPAN></SPAN></TD></TR>
              <TR>
                <TD borderColor=#009900><SPAN class=style35><SPAN 
                  class=style31>　<A 
                  href="http://www.tulipsys.com/OSC/Chapter7.htm#系统模型">7.9.1 
                  系统模型</A></SPAN></SPAN></TD></TR>
              <TR>
                <TD borderColor=#009900><SPAN class=style35><SPAN 
                  class=style31>　<A 
                  href="http://www.tulipsys.com/OSC/Chapter7.htm#基于日志的数据恢复">7.9.2 
                  基于日志的数据恢复</A></SPAN></SPAN></TD></TR>
              <TR>
                <TD borderColor=#009900><SPAN class=style35><SPAN 
                  class=style31>　<A 
                  href="http://www.tulipsys.com/OSC/Chapter7.htm#检查点">7.9.3 
                  检查点</A></SPAN></SPAN></TD></TR>
              <TR>
                <TD borderColor=#009900><SPAN class=style35><SPAN 
                  class=style31>　<A 
                  href="http://www.tulipsys.com/OSC/Chapter7.htm#并发原子事务">7.9.4 
                  并发原子事务</A></SPAN></SPAN></TD></TR>
              <TR>
                <TD borderColor=#009900><SPAN class=style35><SPAN 
                  class=style31>　　<A 
                  href="http://www.tulipsys.com/OSC/Chapter7.htm#可串行性">7.9.4.1 
                  可串行性</A></SPAN></SPAN></TD></TR>
              <TR>
                <TD borderColor=#009900><SPAN class=style35><SPAN 
                  class=style31>　<A 
                  href="http://www.tulipsys.com/OSC/Chapter7.htm#封锁协议">　7.9.4.2 
                  封锁协议</A></SPAN></SPAN></TD></TR>
              <TR>
                <TD borderColor=#009900><SPAN class=style35><SPAN 
                  class=style31>　　<A 
                  href="http://www.tulipsys.com/OSC/Chapter7.htm#基于时间戳的协议">7.9.4.3 
                  基于时间戳的协议</A></SPAN></SPAN></TD></TR>
              <TR>
                <TD borderColor=#009900><SPAN class=style35><SPAN 
                  class=style31><A 
                  href="http://www.tulipsys.com/OSC/Chapter7.htm#摘要">7.10 
                  摘要</A></SPAN></SPAN></TD></TR>
              <TR>
                <TD borderColor=#009900><SPAN class=style35><SPAN 
                  class=style31><A 
                  href="http://www.tulipsys.com/OSC/Chapter7.htm#词汇">词汇</A></SPAN></SPAN></TD></TR>
              <TR>
                <TD borderColor=#009900>&nbsp;</TD></TR></TBODY></TABLE></TD>
          <TD vAlign=top align=left width=618>
            <TABLE height=155 width=618 border=0>
              <TBODY>
              <TR>
                <TD height=16>更新日期：2004-11-30 　　　　　　　　　　　　　　　　　　　　　　　　　　　<A 
                  href="http://www.tulipsys.com/OSC/Download/第七章%20进程同步.pdf" 
                  target=_blank>下载</A>　<A 
                  href="http://blog.csdn.net/tulipsys/archive/2004/12/01/200087.aspx" 
                  target=_blank>讨论</A></TD></TR>
              <TR>
                <TD vAlign=top align=left>　　协作进程（cooperating 
                  process）不但影响系统中其它的进程，也受它们影响。协作进程之间可以直接共享一个逻辑地址空间（确切的说是代码和数据），也可以通过文件实现数据共享。前者通过轻量级进程或线程实现，我们在第5节讨论。对共享数据的并发访问可能会导致数据的不一致。在本章，我们要讨论各种确保共享逻辑地址空间的协作进程有序执行的机制，以此来维护数据的一致性。<BR>　　<A 
                  name=背景知识></A><STRONG>7.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>　　我们在第四章中讨论了由许多协作顺序进程（cooperating sequential 
                  process）组成的系统的模型，这些进程异步执行，并可能会共享数据。我们利用有限缓冲区来阐明这种模型，它代表操作系统。<BR>　　让我们重新看一下4.4节在有限长度缓冲区问题中所描述的共享存储器方案。正如我们所指出的，在这个解决方案中最多允许同时有BUFFER_SIZE 
                  – 
                  1个条目在缓冲区中。让我们修改这个算法以矫正这个缺陷。可以添加一个整形变量counter，初始化为0。每向缓冲区中添加一个新条目counter就加1，每移除一个就减1。生产者进程代码修改如下：<BR>　　　　while 
                  (1) {<BR>　　　　　/* produce an item in nextProduced 
                  */<BR>　　　　　while (counter = = BUFFER_SIZE)<BR>　　　　　; /* do 
                  nothing */<BR>　　　　　buffer[in] = nextProduced;<BR>　　　　　in = (in 
                  + 1) % 
                  BUFFER_SIZE;<BR>　　　　　counter++;<BR>　　　　}<BR>　　消费者进程代码修改如下：<BR>　　　　while 
                  (1) {<BR>　　　　　while (counter = = 0)<BR>　　　　　; /* do nothing 
                  */<BR>　　　　　nextConsumed = buffer[out];<BR>　　　　　out = (out + 1) 
                  % BUFFER_SIZE;<BR>　　　　　counter--;<BR>　　　　　/* consume the item 
                  in nextConsumed 
                  */<BR>　　　　}<BR>　　虽然生产者和消费者程序可以独立正确执行，但是当他们并发执行时就有可能出问题。假设当前counter的值为5，生产者和消费者进程同时执行“counter++”和“counter--”。那么在这两个语句执行之后，变量counter的值可能是4、5或6！唯一正确的结果是counter 
                  = = 
                  5，如果生产者和消费者独立执行可以正确的产生这个结果。<BR>我们可以说明为什么counter的值可能出错。以机器语言实现语句“counter++”可能如下（在一个典型的机器上）：<BR>　　register1 
                  = counter<BR>　　register1 = register1 + 1<BR>　　counter = 
                  register1<BR>　　register1是一个CPU本地寄存器。类似的，语句“counter--”实现如下：<BR>　　register2 
                  = counter<BR>　　register2 = register2 - 1<BR>　　counter = 
                  register2<BR>　　register2 
                  是一个CPU本地寄存器。即使register1和register2可能是同一个物理寄存器（比如一个累加器），但是要注意，中断处理程序会保存并恢复这个寄存器的内容（2.1节）。<BR>“counter++”和“counter--”并行执行等同于前述的低级语言语句以某些随机的顺序交叉执行（但是高级语言的执行顺序是保留的）。这是一种：<BR>　　T0: 
                  producer execute register1 = counter { register1 = 5}<BR>　　T1: 
                  producer execute register1 = register1 + 1 { register1 = 
                  6}<BR>　　T2: consumer execute register2 = counter { register2 = 
                  5}<BR>　　T3: consumer execute register2 = register2 - 1 { 
                  register2 = 4}<BR>　　T4: producer execute counter = register1 
                  {counter = 6}<BR>　　T5: consumer execute counter = register2 
                  {counter = 4}<BR>　　我们得到了一个错误的结果“counter = = 
                  4”，这指明有四个满缓冲区，而事实上有五个。如果我们颠倒语句T4和T5的顺序，那么我们得到“counter = = 
                  6”。<BR>　　之所以得到这个错误的结果是因为我们允许两个进程并行操作变量counter。像这样的情形，多个进程并行访问和操作同样的数据，其执行结果取决于具体的执行顺序，我们称之为竞争条件（race 
                  condition）。为了预防上述的竞争条件，我们要确保一次只有一个进程能够操作变量counter。为此，我们需要某些形式的进程同步。在操作系统中会频繁发生这样的情况，因为系统中的各个不同部分都要操作资源，而且我们不希望一处的变动会影响到另一处。本章的一个主要部分涉及到进程同步（process 
                  synchronization）和协调（coordination）。<BR>　　<STRONG><A 
                  name=临界区问题></A>7.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>　　考虑由n个进程{P0, P1, ..., 
                  Pn-l}构成的系统。每个进程有一个代码段，被称作临界区（critical 
                  section），进程在临界区内可能会修改公有变量、更新一个表、写一个文件等等。该系统的一个重要的特征是当一个进程在其临界区内执行时就不允许其它进程在它的临界区内执行。这样，进程对临界区的执行在时间上是互斥的。（Thus, 
                  the execution of critical sections by the processes is 
                  mutually exclusive in 
                  time.）临界区问题是设计一个用于协作进程执行的协议。每个进程必须请求许可进入其临界区。实现这个请求的代码为进入区（entry 
                  section）。临界区随后可能会有一个退出区（exit section）。其余代码为剩余区（remainder 
                  section）。 
                  <P>　　　　　<IMG height=266 src="TULIPSYS.files/7.1.jpg" 
                  width=457><BR>　　临界区问题的解决方案必须要满足如下的三个要求：<BR>　　1. 互斥（Mutual 
                  Exclusion）：如果进程Pi正在其临界区中执行，那么就不允许有其它进程在临界区中执行。<BR>　　2.