第4章进程同步与进程通信.ppt

1、计算机操作系统 主讲: 四川大学计算机学院 刘 循,第4章 进程同步与进程通信,在多进程环境下，并发进程之间存在相互协作和相互竞争资源。 进程同步措施使得进程之间能够相互协作和有序使用资源。 进程通信是进程之间数据的相互交换和信息的相互传递，进程通信是一种高级通信机制。,第4章 进程同步与进程通信,本章的主要内容如下： 进程并发； 信号量机制； 用信号量实现经典进程同步问题； 管程； 进程通信。,4.1 进 程 并 发,4.1.1 程序的顺序执行 程序执行时，必须按照先后次序逐个进行。 如果一段程序由输入、计算、输出3部分操作构成。程序顺序执行要求首先是输入操作，然后是计算处理，最后是输出操作

2、；一段程序完成后，才能完成下一段程序 程序的顺序执行如图4.1所示。,图4.1 程序顺序执行前驱图,4.1.1 程序的顺序执行,程序的顺序性包括程序的内部顺序性和程序的外部顺序性。 程序的内部顺序性是指一个程序的操作代码在计算机处理器上按照顺序执行，一个代码结束后，后一个代码才能开始。 程序的外部顺序性是指如果一项任务由多个程序模块组成，程序模块的运行也需要按照调用顺序执行，即程序模块之间的顺序性。,程序顺序执行的特点： 顺序性：一个程序在处理器上的运行是按照顺序进行的，每个操作必须在上一个操作完成后才能开始；由多个程序模块构成的一个程序，一个程序模块执行完成后另一个程序模块才能开始。 封闭性

3、：在程序顺序执行下，运行的程序独占系统全部资源，程序执行的结果除初始条件外，由程序本身决定，不会受到任何其它程序和外界因素的干扰。 再现性：针对相同的数据集合，程序执行的结果总是相同的。在程序执行过程中允许出现中断，但是，中断对程序执行的最终结果没有影响。即，程序执行的结果会重复出现。程序执行的结果是可再现的。,4.1.1 程序的顺序执行,程序设计的顺序性、封闭性和再现性表明程序设计与程序执行是一一对应的，这给编制程序和调试程序带来了极大的方便。 程序顺序性，特别是外部顺序性，要求一个程序模块完成后另一个程序模块才能开始，这样，限制了多个程序模块的并发执行。 在多道程序并发执行环境下，如果再按

4、照程序的顺序执行,处理器的利用率低，系统性能差。 传统的程序顺序执行在多道程序环境下已不适合。,4.1.1 程序的顺序执行,4.1.2 进程的并发性,在多道程序环境下，程序是按照多个进程并发执行。 如图4.2所示，这是一个包含有输入、计算、输出多个进程并发执行的情况。,图4.2 程序并发执行前驱图,输入进程、计算进程、输出进程之间存在顺序关系：,输入进程、计算进程、输出进程之间也存在交替关系：,4.1.2 进程的并发性(续),一个输入进程还没有完成，另一个计算进程已经开始；程序的外部顺序性不再存在。 多个进程并发执行，并发进程之间可能是分别在不同的变量集合上操作。一个进程执行与其它进程的进展没

5、有关系，不会改变另一个并发进程的变量值。 并发进程之间也可能是交互的，相关的。可能在同一时间段内，多个进程执行相同的软件代码，或多个进程共享某些变量，或多个进程请求同一硬件资源，一个进程的执行可能影响到其他进程的执行结果，并发进程之间具有制约关系。,4.1.2 进程的并发性(续),例如，两个计数程序A、B，都为： N=N+1； print（N）； 其中，计数值N是共享变量。 如果N的初始值为0:,4.1.2 进程的并发性(续),（1）如果执行的次序为程序A在前，程序B在后，完成A之后再执行程序B。 程序A：N = N + 1； print（N）； /* 此时打印出的结果为1*/ 程序B：N =

6、 N + 1； print（N）； /* 此时打印出的结果为2*/ 最终程序结果为： 程序A打印出的结果为1，程序B打印出的结果为2。,4.1.2 进程的并发性(续),（2）如果执行的次序为程序B在前，程序A在后，完成B之后再执行程序A。 程序B：N = N + 1； print（N）； /* 此时打印出的结果为1*/ 程序A：N = N + 1； print（N）； /* 此时打印出的结果为2*/ 最终程序结果为： 程序A打印出的结果为2，程序B打印出的结果为1。,4.1.2 进程的并发性(续),（3）如果程序A、B以另一种方式交替执行，那么 程序A：N=N+1； 程序B：N=N+1； 程序

7、A：print（N）； /* 此时打印出的结果为2*/ 程序B：print（N）； /* 此时打印出的结果为2*/ 最终程序结果为： 程序A打印出的结果为2，程序B打印出的结果为2。 从上面可以看到，相同的程序由于并发执行的情况不同，最终得到的结果也不同，程序运行出现了不可再现性。,4.1.2 进程的并发性(续),进程并发执行的特点： 间断性 制约性 不可再现性 失去封闭性 进程并发执行充分利用了计算机资源，提高了计算机系统的效率。并发程序设计是多道程序设计的基础，是现代程序设计的主流。,4.1.2 进程的并发性(续),4.1.3 进程间的竞争和协作,在进程并发环境下，并发执行的进程以各自的速

8、度向前推进，相互之间构成了相互竞争资源和相互协作的关系。 1进程间的竞争 进程之间表面上可能无相互影响，不知道对方的存在。在实际上多道程序并发执行，进程的执行失去了封闭性。并发进程相互共处在一个系统中，一个进程的执行必然会影响到其他进程。 例如，火车票售票系统，两个终端进程表面上并无相互影响，但实质上共同访问同一数据库系统中的同一数据。如果售票系统不采取一定的同步措施则系统会发生同一张车票预定给多个用户的情况。 并发进程产生了对资源的竞争问题。,在计算机系统中，共享的资源分为： 互斥共享资源和同时共享资源。 互斥共享资源是指只有一个进程对资源访问，访问结束并释放后，另外的进程才能访问该资源。如

9、：打印机、扫描仪等硬件设备 软件资源有各种数据结构、数据库对象、服务性程序等。这些资源需要进程互斥访问。 同时共享资源是指多个进程可以并发访问，不需要一个进程访问结束，其他的进程就可访问的资源。如磁盘、光盘等外存储设备。这些资源不存在进程的互斥访问问题。 进程对互斥共享资源的竞争要求操作系统对进程操作采取同步措施，从时间上和顺序上加以限制，使得进程之间相互制约地使用这些资源，保证资源的完整性。,4.1.3 进程间的竞争和协作（续）,进程对互斥共享资源的竞争要求操作系统对进程操作采取同步措施，从时间上和顺序上加以限制，使得进程之间相互制约地使用这些资源，保证资源的完整性。,4.1.3 进程间的竞

10、争和协作（续）,2进程间的协作 并发进程之间除了以资源共享的方式相互影响外，还存在协作关系。 由于每个进程都以独立地不可知的速度向前推进，需要具有协作关系的进程需要在某些协调点上相互协调、相互等待，使得双方都能够顺利地运行直至完成。 例如，一项由输入、计算和输出构成的任务，用3个并发进程：输入进程、计算进程、输出进程完成。这3个进程之间构成的是相互协作关系。 对每一次任务过程来讲，必须先运行输入进程，再运行计算进程，最后才能运行输出进程。进程之间构成的是一种先后协作关系。,4.1.3 进程间的竞争和协作（续）,协作的进程之间存在数据或变量等的共享关系，进程的推进顺序受到一定的限制，进程推进需要

11、按照特定的顺序进行，否则会发生进程执行结果的不可再现与不确定的情况。,4.1.3 进程间的竞争和协作（续）,例4-1 并发进程P1和P2 P1 P2 S1 x: = a + 2； S3 y: = x + 4 S2 z: = 3 y； S4 w: = z+ 6 进程P2的值y、z和w依赖于进程P1的值x； 进程P1的值z依赖于进程P2中的值y。 并发进程P1和P2构成相互依赖的协作关系。 在参数a的初始值给定的情况下，进程并发需要按照S1S3S2S4的顺序执行，才能得到x、y、z和w的合理值。否则，程序结果会出现不可再现性。 因此，在并发进程之间存在相互协作关系时，系统需要采取同步措施，确保进程

12、以合理的顺序推进，确保进程运行的可再现性和结果的确定性。 并发进程协作共享资源，也是进程同步关系。,4.1.3 进程间的竞争和协作（续）,4.1.4 进程同步,例4-2 对生产者和消费者问题有如下描述。 生产者进程和消费者进程并发执行。 生产者进程将生产出的产品放入缓冲区，消费者进程从缓冲区中取出产品进行消费。 缓冲区是生产者进程和消费者进程共享的资源，缓冲区大小为n。 生产者进程需要生产出产品，并将产品放入缓冲区后，消费者进程才能进入缓冲区取走产品进行消费。如果缓冲区为空，则消费者进程不能消费；如果缓冲区满，则生产者进程不能生产。,对生产者和消费者问题分析如下： 一个进程正在访问缓冲区时，另

13、一个进程不能同时缓冲区访问，必须等待，直到进入缓冲区访问的进程结束缓冲区访问后，等待的进程才能访问,否则会发生资源的竞争。 由于缓冲区大小为n，是有限缓冲。当缓冲区已经装满了产品，生产者进程不能生产，等待消费者进程来消费；当缓冲区中没有产品，消费者不能消费，等待生产者进程放入产品。 用in表示装入缓冲区的产品个数，生产者进程每生产出一个产品，in加1； 用out表示从缓冲区取走的产品个数，消费者进程每消费一个产品，out加1；,4.1.4 进程同步（续）,当in=out时，表示生产者进程生产出的产品已经被消费者进程消费，缓冲区为空； 缓冲区采用循环缓冲，in=（in+1）mode n，out=

14、（out+1）mode n； 用count计数缓冲区中还剩下的产品数。生产者进程生产出一个产品，count加1；消费者进程取走一个产品，count减1。,4.1.4 进程同步（续）,下面是生产者和消费者问题的算法描述: 定义变量及给定初始值，创建生产者和消费者进程。 var n integer; /* 设置缓冲区数目为100 */ type item = ; var buffer:array 0,1, ,n1 of item; in,out,count:integer: = 0,0,0; f_producer; /* 创建生产者进程producer_p */ f_consumer; /* 创建

15、消费者进程consumer_p */,4.1.4 进程同步（续）,producer: repeat / * 生产者进程 */ produce an item in nextp; /* 生产出一个产品 */ while count = n then no-produce; /* 如果缓冲区已满，则停止生产 */ bufferin: = nextp; /* 如果缓冲区没有满，则送一个产品到缓冲区 */ in: = in + 1 mode n; /* 生产者生产出一个产品标志加1 */ count: = count + 1; /* 缓冲区中产品计数加1 */ until false;,4.1.4 进

16、程同步（续）,consumer: repeat /* 消费者进程 */ whlie count = 0 then no-comsumer; /* 如果缓冲区为空，则停止消费 */ nextc: = bufferout; /* 如果缓冲区有产品，则从缓冲区取走一个产品 */ out: = out + 1 mode n; /* 表示消费者已消费产品标志加1 */ count: = count - 1; /* 缓冲区中产品计数减1 */ consume the item in nextc; until false;,4.1.4 进程同步（续）,在实际进程运行中，如果系统采取控制措施，开始先让生产者进

17、程运行在先，先将产品放入缓冲区中，消费者进程运行在后。按照这样的进程顺序运行，不存在资源的竞争，也不会出现问题。 在实际进程运行中，生产者进程和消费者进程并发运行，除了可能存在生产者进程和消费者进程对缓冲区的竞争使用外，还会出现生产者进程与消费者进程之间不能协作的问题。因为当缓冲区中没有产品时，如果消费者进程竞争得到缓冲区访问权，消费者进程却不能消费，造成生产者进程与消费者进程不能同步。同样，当缓冲区中已经装满产品时，生产者进程得到缓冲区的访问权，生产者进程无法进行生产。 生产者进程与消费者进程都需要对变量count进行访问，对共享变量的访问可能造成数据不一致。,4.1.4 进程同步（续）,如

18、果当前缓冲区中有10个产品，共享变量count为10。在生产者和消费者进程中对变量count作运算的机器操作如下： A1:register1=count； B1:register2=count； A2:register1=register1+1；B2:register2=register21； A3:count=register1； B3:count=register2； 如果按照A1B1A2B2A3B3的顺序执行，则经过寄存器register1得到的count值为11，经过寄存器register2得到的count值为9，最后count的值为9。 如果按照A1A2A3B1B2B3的顺序执行，则

19、经过寄存器register1得到的count值为11，经过寄存器register2得到的count值为10，最后count的值为10。,4.1.4 进程同步（续）,如果按照A1B1A2B2B3A3的顺序执行，最后count的值为11。 进程并发环境下，对count的运算，不同的进程并发顺序执行会得到不同的结果，count的值不确定。引起这个错误关键在于两个并发进程共享访问count，如果对count的访问不采取同步措施，就会造成数据不一致。 在进程并发环境下，竞争使用的资源和共享访问的变量，如果在程序中不采取同步措施，实现互斥访问和有序访问，则会出现数据不一致等问题。 在并发进程之间存在竞争资

20、源关系和相互协作关系的环境下，系统需要采取同步机制，实现并发进程对竞争资源的有序访问和协作关系的协调推进。,4.1.4 进程同步（续）,4.2 临界区管理,4.2.1 临界资源和临界区 互斥共享的资源称为临界资源。 在生产者和消费者进程中，缓冲区和变量count都是临界资源。 在程序中对临界资源访问的代码部分称为临界区。 每个进程访问临界资源前都要判断该资源能否访问，如果进程能够访问，才能进入到临界区访问临界资源； 如果不能访问，则进程需要等待，直到该资源能够访问为止，才能进入到临界区访问临界资源。 进程对临界资源访问结束后，需要将资源归还，使其他进程能够知道临界资源已经被当前进程访问结束。,

21、4.2.1 临界资源和临界区（续）,在程序中，进入临界区代码之前，应该是对临界资源能否访问的判断，这部分代码称为进入区，进入区通常是测试语句或判断语句，如while，if等。 临界区后面的代码应该体现对临界资源访问结束后的标志，即退出区。 程序中的进入区、临界区和退出区3个部分如图4.3所示。,4.2.1 临界资源和临界区（续）,在临界区概念中，并发进程交互访问的共享变量是临界资源，并发的进程对该变量进行访问。 如生产者进程中进入区“while count = n then no-produce;”中的count变量，该变量在消费者进程的进入区“whlie count = 0 then no-

22、comsumer;”也能够访问。 需要采取同步机制，使并发进程互斥访问。,4.2.1 临界资源和临界区（续）,（1）空闲让进 当没有进程访问临界资源，临界资源为空闲时，系统允许一个请求临界资源的进程进入临界区，访问临界资源。 （2）忙则等待 当已有进程正访问临界资源，临界资源为忙时，则系统不允许当前请求临界资源的进程访问临界资源，请求进程只能等待，以保证临界资源的互斥使用。 （3）有限等待 对请求访问临界资源的进程，如果不能访问临界资源，需要等待临界资源，则应该保证进程等待临界资源的时间是有限的，使其在有限的时间内可以进入访问临界资源，不允许让进程无限等待临界资源。 （4）让权等待 当进程不能

23、访问临界资源时，进程应该立即停止运行，让出处理器，同时进程的状态从运行转换到阻塞，以免进程陷入“忙等待”。此处的“权”是指处理器的执行权。,4.2.2 进程同步准则,4.2.2 进程同步准则（续）,假设存在A、B两个并发进程访问临界资源，如图4.4所示。,4.2.2 进程同步准则（续）,在程序设计时，进入区是判别能否访问临界资源的关键。 如果进程能访问临界资源，则通过进入区，进入临界区访问临界资源；否则，进程不能进入临界区访问临界资源； 当进程访问临界资源完后，通过退出区，释放临界资源。 并行的进程需要共享整个系统资源或系统全局变量，进程并行同样存在进程之间资源的竞争和相互协调关系，在多处理器

24、环境下系统同样需要采取同步措施。,1软件方法 软件方法在共享内存的单处理机或多处理机系统中实现进程的并发。 软件方法假定基于内存访问级别的一些基本互斥，对内存同一位置的同时访问将被排序，而访问的顺序并不事先指定。 不需要硬件或操作系统或程序设计语言的任何支持。,4.2.3 早期的临界区管理方法（续）,算法1：临界区标志法 为了实现临界区的管理，采用标志来表示哪个并发进程可以进入临界区访问。 对并发进程i和进程j，首先设置标志变量turn。 如果标志变量turn = i，表示允许进程i进入临界区访问； 如果标志变量turn = j，表示允许进程j进入临界区访问。 while是一个判断语句，只要w

25、hile后面的条件满足，则while一直等待在后面的条件上，只有条件不满足时，才进入while的下一个语句执行，直到end语句结束，进程完成一轮执行。 下一轮还需要访问临界资源时，又到while处判断，如此循环往复。两个进程不断地并发执行。,4.2.3 早期的临界区管理方法（续）,对进程i和进程j，算法代码如下： turn: integer; turn: = i; f_Pi; /* 创建进程Pi */ f_Pj; /* 创建进程Pj */ cobegin,Pi: /* 对进程i */ begin while turn = j do nothing; critical section; turn

26、 = j; end;,Pj: /* 对进程j */ begin while turn = i do nothing; critical section; turn = i; end;,coend;,对进程i，首先判断turn是否为i，如果为i，表示进程i可以进入临界区访问，访问完后将标志turn置为j； 如果turn不为i，表示进程i不能进入临界区访问，在while语句处等待，do nothing表示什么操作都不作的等待，直到turn为i。 对进程j，也是首先判断turn是否为j，如果为j，表示进程j可以进入临界区访问，访问完后将标志turn置为i； 如果turn不为j，表示进程j不能进入临界

27、区访问，在while语句处停下来等待，do nothing表示什么操作都不作的等待，直到turn为j。,4.2.3 早期的临界区管理方法（续）,在程序初始化时将turn的初始值设置为i，所以，在进程i和进程j并发时，总是进程i首先进入临界区访问； 进程i访问完临界区后，将turn的值置为j，此时进程j进入临界区访问； 当进程j访问完临界区后，又将turn置为i，让进程i访问临界资源。这样相互轮流访问临界资源。,4.2.3 早期的临界区管理方法（续）,该算法存在的问题： 强制两个进程轮流进入临界区。如果进程i访问完临界区后，进程j并未要求访问该临界资源，或者进程j暂时不访问该临界资源，而进程i又

28、需要再次访问该临界资源，进程i却无法进入临界区，最终造成临界资源没有进程访问。 违背了进程同步机制中的“空闲让进”的原则。,4.2.3 早期的临界区管理方法（续）,算法2：先判断对方进程标志的进程数组标志法 采用查看标志的方法。 进程i每次访问临界资源前，首先查看其他进程访问临界资源的标志。如果其他进程标志处于正在访问，则进程i等待。 当其他进程标志处于没有访问临界资源时，进程i才能进入临界区访问。 设置数组flag为每个进程是否访问临界资源的标志。 对进程i，flagi为true，标志进程i正在临界区访问；flagi为false表示进程i没有访问临界区。,4.2.3 早期的临界区管理方法（续

29、）,turn: integer var flag: array1,2,n of Boolean; flag0 = false; /* flag初始化为false */ flag1 = false; f_Pi; /* 创建进程Pi */ f_Pj; /* 创建进程Pj */ cobegin,Pj /* 对进程j */ begin while flagi do nothing; flagj = true; critical section; /* 访问临界区 */ flagj = false; end;,coend;,Pi： /* 对进程i */ begin while flagj do noth

30、ing; flagi = true; critical section; /* 访问临界区 */ flagi = false; end;,存在问题： 当进程i和进程j都没有进入临界区时，即各自的访问标志flag都为false时，进程while语句通过，进程进入下一个语句时设置进程自己的访问标志，双方都将自己的访问标志设置成true，都要访问临界区。此时，进程i和进程j都进入临界区访问，发生冲突，违背了“忙则等待”的同步准则。 当某个进程要访问临界区已经将自己的标志置为true之后，进程又放弃了临界区的访问，从而会引起其它进程一直等待。,4.2.3 早期的临界区管理方法（续）,算法3：先设置自己

31、标志的进程数组标志法 首先设置自己的标志flag为true，先表明自己需要访问临界资源，然后再判断对方进程是否在使用临界资源。 算法代码如下。 turn: integer var flag: array1,2,n of Boolean; flag0 = false; /* flag初始化为false */ flag1 = false; f_Pi; /* 创建进程Pi */ f_Pj; /* 创建进程Pj */ cobegin,4.2.3 早期的临界区管理方法（续）,Pi：/* 对进程i */ begin flagi = true; while flagj do nothing; critica

32、l section; flagi = false; end;,Pj: /* 对进程j */ begin flagj = true; while flagi do nothing; critical section; flagj = false; end;,4.2.3 早期的临界区管理方法（续）,coend;,算法3面临的问题： 双方进程都先将自己的访问标志设置为true，表明自己要访问临界资源，再判断对方是否访问临界资源，这最终会造成进程双方在判断对方是否访问临界资源时，首先看到的是对方设置了访问标志为true，认为对方进程要访问临界资源，自己不能访问临界资源，最终导致并发进程在while语句

33、上等待，而临界资源并没有进程在访问。 该算法违背了“空闲让进”的同步准则。,4.2.3 早期的临界区管理方法（续）,算法4：双标志法 1981年，GLPerterson总结了算法1和算法3的问题后，提出了算法4。 算法4既利用了标志flag，又利用了标志turn。 标志flag用于表示每个进程是否访问临界资源。 标志turn用于表示临界资源此时是否有对方进程在访问。 只有在对方进程的访问标志flag为true并且turn也为对方进程时，才表明对方进程在访问临界资源，需要等待对方进程访问完并释放资源后才能访问；否则进程不需要等待对方进程而访问临界资源。,4.2.3 早期的临界区管理方法（续）,t

34、urn：integer: = i; var flag: array1,2,n of Boolean; flag0 = false; /* flag初始化为false */ flag1 = false; f_Pi; /* 创建进程Pi */ f_Pj; /* 创建进程Pj */ cobegin,4.2.3 早期的临界区管理方法（续）,算法代码如下：,Pi： /* 对进程i */ begin flagi = true; turn=j; while flagj and turn = j donothing; critical section; flagi = false; end;,4.2.3 早期

35、的临界区管理方法（续）,Pj： /* 对进程j */ begin flagj = true; turn = i; while flagi and turn = i do nothing; critical section; flagj = false; end;,coend;,此处语句“while flagj and turn = j do nothing;”表示只有进程j的标志flagj为进程j，并且标志turn也为进程j时，才表示进程j访问临界区，进程i需要等待。 如果进程i要访问临界资源，则首先将自己的标志flag设置为true，然后设置标志turn为对方进程j；如果此时进程j尚未申请访

36、问临界资源，则flagj为false，进程i能够进入临界区； 如果此时进程j比进程i申请临界资源稍微晚一点，进程j会设置自己的访问标志flag为true后再设置turn为i，这样进程i在等进程j将turn设置为i后，便进入临界区访问。而进程j则需要等待进程i访问完里临界区后将flagi设置为false，便可访问临界区。 此算法可以很好的实现进程对临界资源的访问，turn变量的使用非常巧妙。,4.2.3 早期的临界区管理方法（续）,算法4是一个应用性非常方便的进程同步算法，如果有多个进程并发访问临界资源，该算法也可以容易地实现。 虽然现在很少用上面的软件算法实现临界区管理问题，但是，这些算法对理

37、解同步问题还是很有益处的。,4.2.3 早期的临界区管理方法（续）,2硬件方法 在临界区访问标志算法中，出现了违背“忙则等待”或“空闲让进”准则的根本原因在于管理临界区标志要用两条指令： 一条指令是看对方的标志，一条指令是设置自己的标志。 进程并发，特别是单处理器上的并发，并发进程交替执行，可能导致一个进程在执行这两条指令时被另一个进程中断，最终产生进程对临界区的不正确访问。 要保证进程在执行这两条指令时不被中断，系统可以采取锁的方式。,4.2.3 早期的临界区管理方法（续）,如果临界区没有被访问，则锁是打开的，在进程访问临界区时，只要进程一进入临界区，则系统立即上锁，使得其他进程不能进入临界

38、区，直到访问临界区的进程离开临界区才打开锁。 只有锁打开了，等待临界区访问的进程才有机会进入临界区。 在锁的操作问题上，同样，测试锁和上锁这两个操作也是不能分开的，否则也会造成多个进程测试到锁打开而同时上锁的现象，引起冲突。 进程在执行这两个操作期间在处理器上的运行不能被中断。完全用软件方法来解决有一定局限性和难度，该方法已经很少被采用，现在一般都借助于硬件设施。,4.2.3 早期的临界区管理方法（续）,（1）禁止中断方法 最简单的方法是硬件上的关中断，即禁止中断。在进入临界区标志的两条指令之前或锁测试之前将中断关上，计算机系统在进程测试并进入临界区期间不响应中断，只有临界区访问完后系统才打开

39、中断，从而保证了对临界资源的互斥访问。,4.2.3 早期的临界区管理方法（续）,关中断会带来如下缺点： 影响计算机效率 如果对临界区的访问时间较长，关中断的时间太长，限制了处理器交叉执行程序的能力，影响计算机系统的效率。 不能及时处理重要程序 滥用关中断会引起计算机响应不及时，重要的中断程序不能及时处理，导致出现严重的后果。 在多处理器下方法失效 对于多处理器系统，要想通过关中断阻止进程在临界区执行期间不被中断，毫无任何意义。因为相同的临界区代码会被另一个进程在另一个处理器上执行。,4.2.3 早期的临界区管理方法（续）,（2）测试并建立指令 许多计算机都提供了一些特殊的硬件指令，这些硬件指令

40、在执行中不会被中断。因此，实现临界区管理可以利用硬件提供的“测试并建立(Test and Set)”指令TS。 将TS指令看成为一个函数过程，该函数有一个布尔参数x和一个返回条件码。当TS为true时则置x为false，根据测试到的x值形成条件码。 TS(x)： if x = true then x： = false； return true； else return false；,4.2.3 早期的临界区管理方法（续）,可把临界区看为与布尔变量x相连。 如果x为true，表示没有进程在临界区内，没有上锁，临界资源可被使用，并立即将x置为false，即立刻对临界区上锁。 如果x为false，则

41、表示进程在访问临界区，需要等待。,4.2.3 早期的临界区管理方法（续）,TS函数的应用为： var s: Boolean; s: = true; Pi： /* 对进程Pi，i=1， 2，3，n */ begin var Pi: Boolean; repeat Pi：= TS(s) until Pi; /* 上锁 临界区; s： = true; /* 开锁 */ end；,4.2.3 早期的临界区管理方法（续）,程序中repeat语句用于检查TS指令执行后的TS状态。 如果为true，表示临界区可以访问，上锁并进入临界区。 临界区访问完后开锁。如果为false，表示临界区不可访问，需要等待。,

42、4.2.3 早期的临界区管理方法（续）,（3）对换指令 在不被中断的硬件指令中，也可以用交换两个字内容的对换指令。 下面用对换指令实现对临界区的访问。 Swap是对换指令，用于交换两个字的内容，定义过程如下。 Swap(a, b) temp: = a; a: = b; b: = temp; ,4.2.3 早期的临界区管理方法（续）,Swap的应用为： var lock：Boolean; lock = false; Pi /* 对进程Pi，i=1，2，3，n */ begin var Pi：Boolean; Pi: = true; repeat swap(lock，Pi) until pi =

43、false; /* 上锁 临界区; Lock: = false; /* 开锁 end;,4.2.3 早期的临界区管理方法（续）,系统为每个临界区设置一个全局布尔锁变量lock， 其初值为false，表示没有进程在访问临界区， 用对换指令swap(lock，Pi)将临界区上锁，上锁成功后，进程访问临界区，临界区访问完后，开锁。 如果lock的值为true，表示有进程在访问临界区，等待开锁。 利用swap指令可以简单有效地实现互斥。,4.2.3 早期的临界区管理方法（续）,使用硬件指令实现临界区管理有如下优点： 实现简单：只需要硬件指令就可实现。 适用性强：可用于多个并发进程的单处理器系统或共享内

44、存的多处理器系统。 可支持多个临界区：每个临界区用单独的变量定义，对临界区的多少没有限制，可支持多个临界区。,4.2.3 早期的临界区管理方法（续）,用硬件指令实现临界区管理存在的缺点： 耗费处理器时间：采用忙等待，没有放弃处理器等待，使得处理器空闲时间增多。 进程产生饥饿现象：一个进程离开临界区并唤醒阻塞等待的其它进程，可能阻塞更早的进程长期得不到唤醒，产生饥饿现象。 可能产生死锁：在一个单处理器系统中，进程执行特殊指令，如testset，并进入临界区，这时拥有更高优先级的进程可能抢占正在执行的进程，而更高优先级的进程不可能得到没有释放的临界资源，于是这两个进程发生死锁。,4.2.3 早期的

45、临界区管理方法（续）,4.3 信号量机制,1965年E.W.Dijkstra在其解决并发进程的论文中提出了一种卓有成效的进程同步工具：信号量（semaphore）机制。 信号量类似于交通管理中的信号灯。 在信号量同步机制中，有“检测”和“归还”两个重要的操作。 在荷兰语中，单词“Proberen”的意思为“检测”，用P操作表示； 单词“Verhogen”的意思为“增量”，用V操作表示。“增量”即增加一个可以使用的临界资源，也就是“归还”的意思。,P操作表示同步进程发出的检测信号量操作，检测是否能够使用临界资源，如果能够使用，则检测通过，进程可以访问临界资源；如果不能使用，则等待，直到访问临界区

46、的进程将临界资源归还后，等待的进程才能够访问临界资源。 V操作表示访问完临界资源的进程通知等待进程已经完成了临界资源的访问，将临界资源释放。 信号量机制强调P操作和V操作都是原子操作。 原子操作是不可分割的操作，原语。即通常所说的“要么做，要么不做”，而不可能操作没有完成就被终止。 P操作和V操作表示为wait操作和signal操作，或up操作和down操作，或sleep操作和wakeup操作等。,4.3 信号量机制,4.3.1 整型信号量,1整型信号量定义 设s为一个需要初始化值的正整型量。对s的访问只能通过P、V操作。 s称为整型信号量，其初值可为1或0。,V操作的原语定义如下： V(s)

47、 s = s + 1; ,P操作的原语定义如下： P(s) while s0 do nothing； s = s 1; ,4.3.1 整型信号量（续）,当信号量s的值大于0时，表示临界资源可以访问，P(s)中的检测语句通过，调用P(s)的进程可以访问临界资源。 当信号量s的值小于等于0，表示有进程在访问临界资源，此时临界资源处于忙，调用P(s)的进程只能等待，直到s的值大于0，才可以访问临界资源。 在P(s)操作的定义中，检测语句通过后，后面的语句是将信号量s的值减去1，表示临界资源被调用P(s)的进程使用，此时，如果其他并发进程看见s的值时，s的值为0。当进程完成P(s)操作之后，进程访问临

48、界资源。 V(s)操作则是对临界资源进行释放，s值作加1操作。,从整型信号量定义，需要理解以下几点： 如果s的值为1，表示有1个临界资源可以使用。P(s)操作检测通过，s的值被减为0； P(s)操作后，进程访问临界资源； 对临界资源访问完后，调用V(s)操作，释放临界资源。 如果s的值为0，表示没有临界资源，P(s)操作检测不能通过，进程等待。 整型信号量s是一个全局变量，并发进程都能够访问。s需要在主程序中定义，并赋予初值。,4.3.1 整型信号量（续）,2整型信号量应用 （1）用整型信号量解决并发进程互斥使用共享资源的问题 在临界资源的应用中，系统首先需要为临界资源设置整型信号量。 整型信

49、号量主要应用在互斥访问的资源上，因此整型信号量又称为互斥信号量。,4.3.1 整型信号量（续）,例4-3 输入进程和计算进程共用缓冲区，如图4.5所示。输入进程和计算进程并发执行，缓冲区是竞争访问的临界资源，缓冲区的大小为n。用整型信号量实现进程同步。 由于输入进程和计算进程都要访问缓冲区，缓冲区是临界资源，对缓冲区的访问必须采取互斥的方式。 为缓冲区设置整型信号量mutex，并设mutex的初值为1。然后将各进程对临界区访问置于P(mutex)和V(mutex)之间。,图4.5 进程竞争访问临界资源,4.3.1 整型信号量（续）,算法描述如下： var n:integer; /* 缓冲区数目

50、 */ var mutex: semaphore = 1; /* 设置缓冲区互斥操作的信号量mutex */ Pi(); /* 创建输入进程 */ Pc(); /* 创建计算进程 */ cobegin,4.3.1 整型信号量（续）,4.3.1 整型信号量（续）,Pi: /* 输入进程 */ begin while(输入未完成) P(mutex); /* 如果缓冲区装满，则等待 */ 将一批输入数据放入缓冲区; V(mutex); end;,Pc： /* 计算进程 */ begin while(计算未完成) P(mutex); /* 如果缓冲区为空，则等待 */ 从缓冲区中拿出一批数据; V(m

51、utex); 计算; end;,coend;,对于本例，需要注意如下几点： 对于输入进程，只要缓冲区没有装满，进程就能够将数据输入到缓冲区中。至于缓冲区现在是否可以访问，还需要用P(mutex)去检测，如果P(mutex)检测通过，则进程能够访问缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。 对于计算进程，只要缓冲区不为空，则进程能够从缓冲区中取走数据。至于缓冲区现在是否能够访问，也需要用P(mutex)去检测，如果P(mutex)检测通过，进程能够访问缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。,4

52、.3.1 整型信号量（续）,对于输入进程和计算进程，如果两个进程都能够访问缓冲区，哪个进程先访问缓冲区，关键在于哪个进程先执行P(mutex)，先执行的进程先进入缓冲区访问；后执行P(mutex)的进程等待，直到先进入缓冲区访问的进程用V(mutex)释放缓冲区为止。 从应用可见，在并发进程中，信号量mutex的操作P(mutex)和V(mutex)必须成对出现。如果缺少P(mutex)和V(mutex)中的任何一个都会造成临界资源不能正常使用。,4.3.1 整型信号量（续）,（2）用整型信号量解决并发进程之间的协调问题 虽然整型信号量为互斥信号量，主要应用在对互斥资源的访问上，但是，当并发进

53、程之间需要相互协调时，需要按照一定的顺序执行时，系统也可以利用整型信号量来实现进程并发。,4.3.1 整型信号量（续）,例4-4 在例4-3的基础上，当输入进程和计算进程之间共用的缓冲区中只能装入一条数据时，用整型信号量实现输入进程和计算进程的同步。 对于输入进程和计算进程，当缓冲区中只能装入一条数据时，输入进程每次放入一条数据后，要等待计算进程取走数据才能再放入下一条数据。 因此，除了缓冲区的访问权外，还存在输入进程和计算进程之间的先后协调问题。需要用整型信号量实现输入进程和计算进程的同步。 这里需要设置两个整型信号量is和ps，这两个信号量用于输入进程和计算进程协调访问缓冲区，初值分别设置

54、为1和0。,4.3.1 整型信号量（续）,输入进程和计算进程的算法描述如下： var is,ps: semaphore = 1,0; /* 设置进程协调的信号量is, ps */ Pi(); /* 创建输入进程 */ Pc(); /* 创建计算进程 */ cobegin,4.3.1 整型信号量（续）,Pi: /* 输入进程 */ begin while(输入未完成) P(is); 将一批输入数据放入缓冲区; V(ps); end;,4.3.1 整型信号量（续）,Pc: /* 计算进程 */ begin while(计算未完成) P(ps); 从缓冲区中拿出一批数据; V(is); 计算; en

55、d;,coend;,此题的关键是将信号量is的初值设置为1，ps的初值设置为0。总是输入进程先进入缓冲区放入数据，计算进程先等待。输入进程将一条数据放入缓冲区后释放ps，计算进程才能进入缓冲区取走一条数据。 如果计算进程没有进入缓冲区取走一条数据，输入进程不能再进入缓冲区放数据，因为输入进程需要计算进程释放缓冲区is。 如果没有输入进程释放缓冲区ps，计算进程不能进入缓冲区取走数据。,4.3.1 整型信号量（续）,例4-5 有6个进程A、B、C、D、E、F，它们并发执行的关系如图4.6所示。用整型信号量实现这样的并发关系。,图4.6 用整型信号量实现进程并发,4.3.1 整型信号量（续）,设置

56、8个整型信号量s1、s2、s3、s4、s5、s6、s7、s8，将它们的初值设置为0，这里整型信号量的初值设置非常关键。,下面是实现并发进程顺序要求的算法描述。 /* 设置8个整形信号量并分别令初值为0 */ var s1，s2,s3,s4,s5,s6,s7,s8:semaphore = 0,0,0,0,0,0,0,0; A(); /* 创建进程A */ B(); /* 创建进程B */ C(); /* 创建进程C */ D(); /* 创建进程D */ E(); /* 创建进程E */ F(); /* 创建进程F */,4.3.1 整型信号量（续）,cobegin A： / * 进程A */

57、begin /* 执行进程A中的所有程序语句 */ V(s1); /* 当进程A中的语句执行完后释放信号量s1，让进程B在之后运行*/ V(s2); /* 释放信号量s2，让进程C在之后运行*/ end;,4.3.1 整型信号量（续）,B: / * 进程B */ begin P(s1); /* 进程B等待进程A完成并释放s1后，才能开始执行 */ /* 执行进程B的所有程序语句 */ V(s3); /* 当进程B中的语句执行完后释放信号量s3，让进程D在之后运行*/ V(s4); /* 释放信号量s4，让进程E在之后运行*/ end;,4.3.1 整型信号量（续）,C: / * 进程C */

58、begin P(s2); /* 进程C等待进程A完成并释放s2后，才能开始执行 */ /* 执行进程C的所有程序语句 */ V(s5); /* 当进程C中的语句执行完后释放信号量s5，让进程E在之后运行*/ end;,4.3.1 整型信号量（续）,D: / * 进程D */ begin P(s3); /* 进程D等待进程B完成并释放s3后，才能开始执行 */ /* 执行进程D的所有程序语句 */ V(s6); /* 当进程D中的语句执行完后释放信号量s6，让进程F在 之后运行*/ V(s7); /* 释放信号量s7，让进程E在之后运行*/ end;,4.3.1 整型信号量（续）,E: / *

59、进程E */ begin P(s4); /* 进程E等待进程B完成并释放s4后，才能开始执行 */ P(s5); /* 进程E等待进程C完成并释放s5后，才能开始执行 */ P(s7); /* 进程E等待进程D完成并释放s7后，才能开始执行 */ V(s8); /* 释放信号量s8，让进程F在之后运行*/ end;,4.3.1 整型信号量（续）,F: / * 进程F */ begin P(s6); /* 进程F等待进程D完成并释放s6后，才能开始执行*/ P(s8); /* 进程F等待进程E完成并释放s8后，才能开始执行*/ end; coend;,4.3.1 整型信号量（续）,用整型信号量实现并发进程之间的协调关系的关键是将整型信号量的初值设置为0，利用操作P()在信号量初