4.3,4.4 与书同步课件

《4.3,4.4 与书同步课件》由会员分享，可在线阅读，更多相关《4.3,4.4 与书同步课件（74页珍藏版）》请在金锄头文库上搜索。

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

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

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

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

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

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

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

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

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

10、计算进程协调访问缓冲区，初值分 别设置为1和0。4.3.1 整型信号量（续）输入进程和计算进程的算法描述如下： var is,ps: semaphore = 1,0; /* 设置进程协调的信号量is, ps */Pi(); /* 创建输入进程 */Pc(); /* 创建计算进程 */ cobegin4.3.1 整型信号量（续）Pi: /* 输入进程 */beginwhile(输入未完成)P(is);将一批输入数据放入缓冲区;V(ps);end;4.3.1 整型信号量（续）Pc: /* 计算进程 */beginwhile(计算未完成)P(ps);从缓冲区中拿出一批数据;V(is);计算;end;

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

12、设置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 整型信号量（续）cobeginA： / * 进程A */begin /

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

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

15、成并释放s4后，才能开始执行 */P(s5); /* 进程E等待进程C完成并释放s5后，才能开始执行 */P(s7); /* 进程E等待进程D完成并释放s7后，才能开始执行 */V(s8); /* 释放信号量s8，让进程F在之后运行*/end;4.3.1 整型信号量（续）F: / * 进程F */beginP(s6); /* 进程F等待进程D完成并释放s6后，才能开始执行*/P(s8); /* 进程F等待进程E完成并释放s8后，才能开始执行*/end; coend;4.3.1 整型信号量（续）l用整型信号量实现并发进程之间的协调关系的关键 是将整型信号量的初值设置为0，利用操作P()在信 号量初值为0时进程不能向下执行，只能测试等待 ；操作V()是加1，释放信号量的特点，使得进程关 系得到保证。 l因此，这样的P、V操作协调了并发进程相互之间的 执行顺序。4.3.1 整型信号量（续）4.3.2 记录型信号量l在整型信号量中，P操作开始需要测试临界资源是 否能够访问，即判断s0是否满足。如果满足， 表示进程不能进入临界区访问，进程此时“do nothing”，即什么都不做而等待。这时的等待没 有放弃CPU执行权。这违背了“让权等待”的同步 准则，造成处理器资源的浪费。 l记录型信号量在整型信号量的基础上进行了改进 ，让不能进入临界区的进程“让权等待”，即进 程状态由运行转换为阻塞状