第6章进程间的制约关系 本章讲述内容： 6.1进程间的制约关系； 6.2信号量与P、V操作： 6.3死锁、高级进程通信
第6章 进程间的制约关系 6.1 6.2 6.3 本章讲述内容： 进程间的制约关系 ； 信号量与P、V操作 ； 死锁、高级进程通信
6. 1进程间的制约关系 ● 6.1.1与时间有关的错误 1.与时间有关的错误 进程的并发，使一个进程何时占有处理机、占有多长时间、执行速度的快慢、以及 外界对进程产生作用等都带有随机性。因此，一个进程对其他进程的影响无法预测。在 操作系统里，把这种由于时间因素的影响而产生的错误，称为“与时间有关的错误”。 输入井文件目录表 2.例：对输入井文件目录的管理 为输出井设置一张“输出井文件目录表”，它由若干目 out 录项组成。每个目录项记录一个要打印输出的文件名以及该 44 test.c 文件在磁盘的存放地址。 5 group.p ·为管理该目录表，系统安排两个 井管理写”程序 指针：out和in。“缓输出程序”根据out 6 robit.txt 的指点进行打印，out总是指向下一个被 7 读的当前内容 打印的文件；井管理写程序根据n的指 根据指点，存入打印文件名 点存放要求输出的文件目录信息，in总 n的值加1 是指向下一个可用的目录项位置
为输出井设置一张 “输出井文件目录表”，它由若干目 录项组成。每个目录项记录一个要打印输出的文件名以及该 文件在磁盘的存放地址。 6.1 进程间的制约关系 • 6.1.1与时间有关的错误 1. 与时间有关的错误 进程的并发，使一个进程何时占有处理机、占有多长时间、执行速度的快慢、以及 外界对进程产生作用等都带有随机性。因此，一个进程对其他进程的影响无法预测。在 操作系统里，把这种由于时间因素的影响而产生的错误，称为“与时间有关的错误”。 2. 例：对输入井文件目录的管理 读in的当前内容 ; 根据指点，存入打印文件名 ; in的值加1 ; test . c group . p robit . txt 4 5 6 7 4 out 7 in 输入井文件目录表 “井管理写” 程序 . 为管理该目录表，系统安排两个 指针：out和in。“缓输出程序”根据out 的指点进行打印，out总是指向下一个被 打印的文件；井管理写程序根据in的指 点存放要求输出的文件目录信息，in总 是指向下一个可用的目录项位置。
.若现在进程A要求打印名为“games'的文件。为此调用“井管理写”程序。在做 了准备工作后，读出i中当前的内容为7。恰在此时，系统分配给进程A的时间片到，调 度进程B运行。假定现在进程B要求打印文件“mail”,于是也去调用“井管理写”程序。 在做了准备工作后，它读取中的内容。此时，n中的值没改变，得到的仍为7。于是把 它的文件“mai存入输出井文件目录表中的第7个表目，并把in改为8，然后做其他的操 作。.再次调度进程A运行，从断点往下做。由于它已做读in的操作，就把文件“games” 存入输出井文件目录表中的第7个表目，把原来里面进程B的文件名删去，并且把i更新 为9（因为进程B已把in改为8了），然后做其他的操作。 。这样一来，进程B要输出的文件信息全无，永远也得不到任何打印输出。另外， 输出井文件目录表的表目8被跳过去了，它里面没有记录下任何要输出 输入井文件目录表 的文件信息。从而产生了“与时间有关的错误”。 3.例：通过双缓冲区复制文件 out ·编写复制个记录的程序，它把文件F中的记录依次读到输入缓钟感 ,再头拷贝 到输出缓冲区工，最后写到文件G中。假定R和T督率放序个记录。写下面上伞子程宇 作为进程来完成整个工作： 6 robit.txt (④)GET:从文件F按照顺序读出一个记录，然后送入输入缓，7 (②COPY:把输入缓冲区R里的记录转霞理 (③)PUT:从输出缓冲区T里读出一个记然后依照顺序写入文件G
. 再次调度进程A运行，从断点往下做。由于它已做读in的操作，就把文件“games” 存入输出井文件目录表中的第7个表目，把原来里面进程B的文件名删去，并且把in更新 为9（因为进程B已把in改为8了），然后做其他的操作。 若现在进程A要求打印名为“games”的文件。为此调用“井管理写”程序。在做 了准备工作后，读出in中当前的内容为7。恰在此时，系统分配给进程A的时间片到，调 度进程B运行。假定现在进程B要求打印文件“mail”，于是也去调用“井管理写”程序。 在做了准备工作后，它读取in中的内容。此时，in中的值没改变，得到的仍为7。于是把 它的文件“mail”存入输出井文件目录表中的第7个表目，并把in改为8，然后做其他的操 作。. 这样一来，进程B要输出的文件信息全无，永远也得不到任何打印输出。另外， 输出井文件目录表的表目8被跳过去了，它里面没有记录下任何要输出 的文件信息。从而产生了“与时间有关的错误”。 . 3. 例：通过双缓冲区复制文件 . 编写复制n个记录的程序，它把文件F中的记录依次读到输入缓冲区R，再从R拷贝 到输出缓冲区T，最后写到文件G中。假定R和T正好存放一个记录。写下面三个子程序 作为进程来完成整个工作： (1) GET：从文件F按照顺序读出一个记录，然后送入输入缓冲区R； (2) COPY：把输入缓冲区R里的记录拷贝到输出缓冲区T里； (3) PUT：从输出缓冲区T里读出一个记录，然后依照顺序写入文件G。 读in的当前内容 ; 根据指点，存入打印文件名 ; in的值加1 ; test . c group . p robit . txt 4 5 6 7 4 out 7 in 输入井文件目录表 “井管理写” 程序
,复制时，若COPY已把R里的记录 文件F 文件G 拷贝到了T中，那GET和PUT就可并发 记录1 记录 执行了。即GET从F里读下一个记录送 记录2 记录2 到R中的操作，与PUT从T中取出内容 GET COPY PUT 写入G的操作，谁先谁后都没有关系， 不会影响到复制结果的正确性。由于 输入缓冲区R 输出缓冲区T 利用并发性，工作效率就会提高。 。假定现在处于如图所示的状态， 记录 记录 文件F的第1个记录已顺利地复制到了 文件G,文件F的第2个记录也已由GET读到了输入缓冲区R中。 。若不顾及这三者间执行顺序的内在 制约关系，随意让GET、COPY、PUT 文件F 文件G 并发执行，那么就会产生“与时间有关的 记绿1 错误”。 .不管GET、COPY、PUT的执行关系， 记录3 有六种可能的执行顺序： 记录4 记录2 记录1 1)COPY→PUT→GET; 2)COPY→GET→PUT: 记录知 3)PUI→COPY→GET: 4)PUT→GET→COPY;5)GET→COPY→PUT;6)GET-→PUT→COPY
复制时，若COPY已把R里的记录 拷贝到了T中，那GET和PUT就可并发 执行了。即GET从F里读下一个记录送 到R中的操作，与PUT从T中取出内容 写入G的操作，谁先谁后都没有关系， 不会影响到复制结果的正确性。由于 利用并发性，工作效率就会提高。 记录1 记录2 记录n GET COPY PUT 文件F 记录1 记录2 记录n 文件G 输入缓冲区R 输出缓冲区T . 若不顾及这三者间执行顺序的内在 制约关系，随意让GET、COPY、PUT 并发执行，那么就会产生“与时间有关的 错误”。 . 不管GET、COPY、PUT的执行关系， 有六种可能的执行顺序： 1）COPY→PUT→GET； 2）COPY→GET→PUT； 3）PUT→COPY→GET； 4）PUT→GET→COPY；5）GET→COPY→PUT；6）GET→PUT→COPY . 假定现在处于如图所示的状态， 文件F的第1个记录已顺利地复制到了 文件G，文件F的第2个记录也已由GET读到了输入缓冲区R中。 记录3 记录4 记录n 文件F 记录2 记录1 文件G R T 记录1
.比如在前图基础上，来看第6种可能“GET→PUT→COPY”时导致的错误结果。 。这时先执行GET,把文件F中的第3个记录读入缓冲区R,致使原来R中的记录2被删 去，由记录3代替，如图(a)所示。 。然后，执行PUT,把现在还在输出缓 文件F 文件G 冲区中的记录1写入到文件G中，成为它的 记录1 第2个记录，如图(b)所示。 ,最后做COPY,把记录3从R拷贝到T 中，如图(c)所示。 记录4 GET 记录3 记录1 。由于没有遵循三个程序在执行顺序 R T 上的限制，复制过程中，丢失了第2个记 记录n 录，第1个记录在文件G里重复复制了两 (a) 次。导致了“与时间有关的错误”的发 生文件F 文件G 文件F 文件G 记录1 记录1 记录1 记录1 记录4 PUT 记绿3 记录 记录4 COPY 记录3 记录3 R 人 记录n 记录n b
GET PUT 记录1 记录1 文件G R T 记录 记录3 4 记录n 文件F 记录1 记录4 记录n 文件F 记录3 记录1 文件G R T 记录1 COPY 记录1 记录4 记录n 文件F 记录3 记录3 文件G R T 记录1 1 2 3 . 比如在前图基础上，来看第6种可能“GET→PUT→COPY”时导致的错误结果。 . 这时先执行GET，把文件F中的第3个记录读入缓冲区R，致使原来R中的记录2被删 去，由记录3代替，如图(a)所示。 (a) . 然后，执行PUT，把现在还在输出缓 冲区中的记录1写入到文件G中，成为它的 第2个记录，如图(b)所示。 . (b) (c) 最后做COPY，把记录3从R拷贝到T 中，如图(c)所示。 . 由于没有遵循三个程序在执行顺序 上的限制，复制过程中，丢失了第2个记 录，第1个记录在文件G里重复复制了两 次。导致了“与时间有关的错误”的发 生
。6.1.2竞争资源 一互 1.输入井文件目录管理导致“与时间有关的错误”的分 杨子里进程A和B没有任何直接的关系，各做各的事情。不过，当它们要输出时， 都要访问变量n。也就是说，n是它们的共享变量。 .若在进程A用完变量in(即取出in的值，把文件按其指点存入输出井目录表，把in 的值加1)后，进程B才去用，那是不会发生“与时间有关的错误”的。同样地，若在 进程B用完变量后，进程A才去用，那么也不会发生“与时间有关的错误”。 .现在是在A取出变量in的值、还没按其指点往目录表中存放文件信息、没对n实 行加1操作的情况下，B就去用了变量，从而导致了“与时间有关的错误”输入井文件相录表 。很明显，A和B谁先做或谁先用in都没关系，重要的是它们不能同时 用in。“不能同时”的含义是：在一个进程已开始用in、且还没有用完时， 不允许另一个进程也用n,即它们对in的使用必须“互斥” 4+4 test.c ·在操作系统中，凡牵扯到数据、队列、缓冲区、表格和变量等任何形式的共享资 源时，都容易出现这种“与时间有关的错误”。为避细错蝴发生，关键是要找到卫种 途径，来阻止多于一个进程同时使用它们。 robit.txt 2.互斥与临界区 +7 。称可以共享的资源（文件、队列、变量滂单学驴营辜变量或临界资源。为深亚与 个共享变量交往的多个进程各自运行的正确性，审入避霜正在对该变量进行操华 时，绝不允许其他进程同时对它进行操作。进程间的这种制约关系被称为“互厅”：
• 6.1.2 竞争资源——互斥 若在进程A用完变量in（即取出in的值，把文件按其指点存入输出井目录表，把in 的值加1）后，进程B才去用in ，那是不会发生“与时间有关的错误”的。同样地，若在 进程B用完变量in后，进程A才去用，那么也不会发生“与时间有关的错误”。 1. 输入井文件目录管理导致“与时间有关的错误”的分 . 析例子里进程A和B没有任何直接的关系，各做各的事情。不过，当它们要输出时， 都要访问变量in。也就是说，in是它们的共享变量。 . 现在是在A取出变量in的值、还没按其指点往目录表中存放文件信息、没对in实 行加1操作的情况下，B就去用了变量in，从而导致了“与时间有关的错误”。 . . 很明显，A和B谁先做或谁先用in都没关系，重要的是它们不能同时 用in。“不能同时”的含义是：在一个进程已开始用in、且还没有用完时， 不允许另一个进程也用in，即它们对in的使用必须“互斥”。 在操作系统中，凡牵扯到数据、队列、缓冲区、表格和变量等任何形式的共享资 源时，都容易出现这种“与时间有关的错误”。为避免错误的发生，关键是要找到一种 途径，来阻止多于一个进程同时使用它们。 . 称可以共享的资源（文件、队列、变量等）为共享变量或临界资源。为保证与一 个共享变量交往的多个进程各自运行的正确性，当其中一个进程正在对该变量进行操作 时，绝不允许其他进程同时对它进行操作。进程间的这种制约关系被称为“互斥”。 2. 互斥与临界区 . 读in的当前内容 ; 根据指点，存入打印文件名 ; in的值加1 ; test . c group . p robit . txt 4 5 6 7 4 out 7 in 输入井文件目录表 “井管理写” 程序
。在进程程序中，涉及到共享变量的那一部分程序，才真正需要保证互斥地执行。 在操作系统中，把进程程序中“真正需要保证互斥执行”的那一段程序，称为该进程的 “临界区（或临界段）” 3.设计互斥进程的注意事项 。具有互斥关系的进程，它的一部分程序可能用于内部的计算，用于内部的数据处理 等。只有涉及共享变量的那一部分程序，才真正需要保证互斥地执行。 。有互斥关系的进程，并不关心对方的存在性。即使对方不存在，自己也能够正确的 运行，不会受到它存在与否的影响。 。有互斥关系的那些进程程序中的临界区，虽然都是针对同一个共享变量的程序段， 但在其上的操作可以相同也可以不相同。 。进程的临界区是相对于某个共享变量而言的，不同共享变量的临界区之间，不存在 互斥关系。 4.设计进程临界区时必须遵循的准则 。如果有若干个进程要求进入自己的临界区，那么它们不应互相排斥，致使谁也进 不了临界区。 。每次只允许一个进程进入临界区。 一个进程在临界区内逗留有限时间后，就应该退出，以便给其他进程创造进入临 界区的机会
一个进程在临界区内逗留有限时间后，就应该退出，以便给其他进程创造进入临 界区的机会。 如果有若干个进程要求进入自己的临界区，那么它们不应互相排斥，致使谁也进 不了临界区。 . 在进程程序中，涉及到共享变量的那一部分程序，才真正需要保证互斥地执行。 在操作系统中，把进程程序中“真正需要保证互斥执行”的那一段程序，称为该进程的 “临界区（或临界段）”。 3. 设计互斥进程的注意事项 . . 每次只允许一个进程进入临界区。 具有互斥关系的进程，它的一部分程序可能用于内部的计算，用于内部的数据处理 等。只有涉及共享变量的那一部分程序，才真正需要保证互斥地执行。 . 有互斥关系的进程，并不关心对方的存在性。即使对方不存在，自己也能够正确的 运行，不会受到它存在与否的影响。 . 有互斥关系的那些进程程序中的临界区，虽然都是针对同一个共享变量的程序段， 但在其上的操作可以相同也可以不相同。 . 进程的临界区是相对于某个共享变量而言的，不同共享变量的临界区之间，不存在 互斥关系。 4. 设计进程临界区时必须遵循的准则 .
。6.1.3协同工作一同步 1.用双缓冲区复制文件导致“与时间有关的错误”的分 握GET设把记录从F读到R前，COPY不能把R中的内容拷贝到T中去：在COPY没 把R中的内容拷贝到T之前，GET不得把下一个记录从F读到R中。即只有GET先于COPY 工作，COPY的工作才正确；只有COPY取走了R中的内容，GET做下一步工作才正确。 COPY与PUT之间也有这种关系，这是进程之间由于协同工作而产生的一种直接关系。 正是由于例中的GET、COPY、PUT之间没有保持这种关系，因此产生了所谓的 “与时间有关的错误”。 2.保证GET和COPY间协调一致的作法 COPY 件F 文件G 。GET读记录到R后，给COPY发消 记逯 记录 息，告诉它R中已有记录，然后暂停， 记专》文件F取田斗个记 等待GET发来“可 等待COPY发来“拷贝结束”的消息。 篆送至输入编中区R 以拷贝”按滑稳 只有接到这个消息，GET才能往下做。 向OPY发送可乎 里的录： .COpY一直等待。只有接到GET 发来“可以拷贝”的消息才能工作，将 以烤贝时消息输入缓冲区R 3 R里的记录拷到T里，然后向GET发“拷 等待COPY发来的 向GET发送"拷 贝结束”的消息，随之又等待GET发消 记录拷贝结束”的消息 贝结束” 息
• 6.1.3 协同工作——同步 1. 用双缓冲区复制文件导致“与时间有关的错误”的分 . 析在GET没把记录从F读到R前，COPY不能把R中的内容拷贝到T中去；在COPY没 把R中的内容拷贝到T之前，GET不得把下一个记录从F读到R中。即只有GET先于COPY 工作，COPY的工作才正确；只有COPY取走了R中的内容，GET做下一步工作才正确。 COPY与PUT之间也有这种关系，这是进程之间由于协同工作而产生的一种直接关系。 2. 保证GET和COPY间协调一致的作法 从文件F取出一个记 录送至输入缓冲区R 向COPY发送“可 以拷贝” 的消息 等待COPY发来的 “拷贝结束”的消息 等待GET发来“可 以拷贝” 的消息 将输入缓冲区R里的记录 拷贝到输出缓冲区T里 向GET发送“拷 贝结束”的消息 GET COPY 1. 1. 2. 2. 3. 3. GET读记录到R后，给COPY发消 息，告诉它R中已有记录，然后暂停， 等待COPY发来 “拷贝结束”的消息。 只有接到这个消息，GET才能往下做。 . COPY一直等待。只有接到GET 发来 “可以拷贝”的消息才能工作，将 R里的记录拷到T里，然后向GET发“拷 贝结束”的消息，随之又等待GET发消 息。 . . 正是由于例中的GET、COPY、PUT之间没有保持这种关系，因此产生了所谓的 “与时间有关的错误”。 记录1 记录2 记录n GET COPY PUT 文件F 记录1 记录2 记录n 文件G 输入缓冲区R 输出缓冲区T
3.设计有直接制约关系进程时应注意的问题 。具有这种关系的进程，需要在某些点上协调相互的动作，谁先到达谁后到达是有 顺序要求的。比如，GET应先在R中为COPY准备好记录，并向COPY发送“可拷贝”的 消息。这样，当COPY运行时就有数据可用了。如果COPY先于GET到达等待GET发来 “可拷贝”消息的地方，那么由于GET还没有为它准备好数据，它就只能等待。 ·这些进程都应了解对方的工作，对方如果不存在，或任何一方单独运行，就会出 现差错。比如，GET应知道COPY只有得到自己给它的数据后，才能往下运行。COPY 应该知道GET只有在得到它发出的“拷贝结束”消息后，才能继续做。只有这样配合， 才能保证它们处于正常的工作状态。 。一方或双方的运行会直接地依赖于对方所产生的信息或发出的消息。比如，GET 和COPY之间是双方都依赖于对方发来的消息，接收不到对方的消息，自己就一直保持 等待。 4.同步、同步点、同步条件 。一个进程运行到某点时，除非合作进程已经完成了某种操作或发来了信息，否则 就必须暂时等待那些操作的完成或信息的到来。进程间的这种关系被称为“同步”。 。暂停等待以取得同步的那一点，称为“同步点”。 。一个进程需要等待另一个进程完成的操作或发送的信息，称为“同步条件
一个进程需要等待另一个进程完成的操作或发送的信息，称为“同步条件”。 一个进程运行到某点时，除非合作进程已经完成了某种操作或发来了信息，否则 就必须暂时等待那些操作的完成或信息的到来。进程间的这种关系被称为“同步”。 . 4. 同步、同步点、同步条件 . 暂停等待以取得同步的那一点，称为“同步点”。 . 3. 设计有直接制约关系进程时应注意的问题 . 具有这种关系的进程，需要在某些点上协调相互的动作，谁先到达谁后到达是有 顺序要求的。比如，GET应先在R中为COPY准备好记录，并向COPY发送“可拷贝”的 消息。这样，当COPY运行时就有数据可用了。如果COPY先于GET到达等待GET发来 “可拷贝” 消息的地方，那么由于GET还没有为它准备好数据，它就只能等待。 . . 这些进程都应了解对方的工作，对方如果不存在，或任何一方单独运行，就会出 现差错。比如，GET应知道COPY只有得到自己给它的数据后，才能往下运行。COPY 应该知道GET只有在得到它发出的“拷贝结束”消息后，才能继续做。只有这样配合， 才能保证它们处于正常的工作状态。 一方或双方的运行会直接地依赖于对方所产生的信息或发出的消息。比如，GET 和COPY之间是双方都依赖于对方发来的消息，接收不到对方的消息，自己就一直保持 等待
6.2信号量与P、V操作 ● 6.2.1信号量与P、V操作的定义 1.信号量的定义 所谓“信号量”，是一个具有非负初值的整型变量，并有一个队列与它关联。因此， 定义一个信号量S时，要给出它的初值Vs,给出与它相关的队列指针Vq。在一个信号 量S上，只能做规定的两种操作：P操作，记为P(S):和V操作，记为V(S。 2.信号量$上的P操作定义 当一个进程调用P(S)时，应该顺序做下面两个不可分割的动作： ()Vs=Vs-1,即把当前信号量S的取值减1： (2)若Vs>0,则调用进程继续运行；若Vs0,则调用进程继续运行；若Vs<=O,则先从与该信号量有关的队列Vg上摘 下一个等待进程，让它从阻塞态变为就绪态，到就绪队列排队，然后调用进程继续运 行
• 6.2.1 信号量与P、V操作的定义 1. 信号量的定义 所谓“信号量”，是一个具有非负初值的整型变量，并有一个队列与它关联。因此， 定义一个信号量S时，要给出它的初值Vs，给出与它相关的队列指针Vq。在一个信号 量S上，只能做规定的两种操作：P操作，记为P(S)；和V操作，记为V(S)。 2. 信号量S上的P操作定义 6.2 信号量与P、V操作 3. 信号量S上的V操作定义 当一个进程调用P（S）时，应该顺序做下面两个不可分割的动作： (1) Vs=Vs-1，即把当前信号量S的取值减1； (2) 若Vs>=0，则调用进程继续运行；若Vs0，则调用进程继续运行；若Vs<=0，则先从与该信号量有关的队列Vq上摘 下一个等待进程，让它从阻塞态变为就绪态，到就绪队列排队，然后调用进程继续运 行