计算机操作系统第三讲

1、2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系1第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步q教学目的教学目的掌握利用信号量解决并发进程同步的问题掌握利用信号量解决并发进程同步的问题掌握临界区、互斥的概念掌握临界区、互斥的概念掌握并发进程互斥执行的准则掌握并发进程互斥执行的准则掌握信号量和掌握信号量和P/V原语原语掌握同步的概念掌握同步的概念2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系2第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步q教学内容教学内容3.5 进程互斥进程互斥3.6 进程同步进程同步2022年3月22日星

2、期二16时35分50秒内蒙古工业大学计算机系3第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步q资源共享所引起的制约资源共享所引起的制约临界区临界区v举例举例设有计算进程设有计算进程Pa和和Pb，共享内存，共享内存MS。MS分为三个区：系统区、进程工作区和分为三个区：系统区、进程工作区和数据区。数据区被划分为大小相同的块，数据区。数据区被划分为大小相同的块，系统区主要是堆栈系统区主要是堆栈S，存放空数据的地址。，存放空数据的地址。2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系4第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步2022年3月22日星

3、期二16时35分50秒内蒙古工业大学计算机系5第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步取空数据块的过程取空数据块的过程procedure getspace()begin local g -g1语句语句 g-stacktop -g2语句语句 top-top-1 -g3语句语句 return (g) -g4语句语句 end2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系6第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步释放数据块的过程释放数据块的过程procedure release(ad)begin top-top+1 -r1语句语句 sta

4、cktop-ad -r2语句语句end2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系7第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步一种执行结果一种执行结果设设t0时刻，时刻，top=h0，进程，进程Pa与与Pb并发执行并发执行的语句序列为：的语句序列为： r1,g2,g3,r2执行结果执行结果由学生自己完成！2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系8虽然可以判断两个相邻语句是否能并发执行，虽然可以判断两个相邻语句是否能并发执行，但是这种方法的局限性在于将花费巨大的系但是这种方法的局限性在于将花费巨大的系统开销。统开销。v解决办法解

5、决办法第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步v产生的原因产生的原因该资源是不能被共享并发使用的。该资源是不能被共享并发使用的。方法一：方法一： Bernstein条件2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系9第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步不允许多个并发进程交叉执行的一段程序。不允许多个并发进程交叉执行的一段程序。方法二：临界区（方法二：临界区（Critical region）间接制约间接制约v类（类（class）把那些不允许交叉执行的临界区按不同的把那些不允许交叉执行的临界区按不同的公用数据划分为不同的集合。公用

6、数据划分为不同的集合。2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系10第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步公用数据栈公用数据栈S的临界区集合是的临界区集合是getspace,release。例如例如v临界区的程序描述临界区的程序描述When do od上例中的上例中的getspace和release的描述为：2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系11第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步getspacewhen sp do g-stacktop top-top-1odrelease(ad) wh

7、en sp do top-top+1 stacktop-ad od2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系12第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步v间接制约间接制约把这种由于共享某一个公用资源而引起的把这种由于共享某一个公用资源而引起的在临界区内不允许并发进程交叉执行的现在临界区内不允许并发进程交叉执行的现象。象。互斥互斥一组并发进程中的一个或多个程序段，因共一组并发进程中的一个或多个程序段，因共享某一个共有资源而导致它们必须以一个不享某一个共有资源而导致它们必须以一个不允许交叉执行的单位执行。允许交叉执行的单位执行。2022年3月22日星期

8、二16时35分50秒内蒙古工业大学计算机系13第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步v临界区调度原则临界区调度原则不假设各并发进程的执行速度不假设各并发进程的执行速度空闲让进空闲让进忙则等待忙则等待有限等待有限等待2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系14第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步q互斥的加锁实现互斥的加锁实现 通过对临界区加锁，在进入临界区时测试是通过对临界区加锁，在进入临界区时测试是否可以进入，退出临界区时对锁进行恢复。否可以进入，退出临界区时对锁进行恢复。锁的定义锁的定义keyS：表示临界区：表示临界

9、区S(临界区类名临界区类名)的锁定位的锁定位keyS=1：表示临界区：表示临界区S可用可用keyS=0：表示临界区：表示临界区S不可用不可用2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系15第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步加锁实现临界区的描述加锁实现临界区的描述lock(keyS)unlock(keyS)lock/unlock的实现的实现vunlock的实现的实现procedure unlock(keys)begin keys-1end2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系16第三章第三章 进程管理进程管理进程的互斥

10、与同步进程的互斥与同步vlock的实现的实现procedure lock(keys)begin local v repeat v-keys until v=1 keys-0end存在困难存在困难如何保证lock 操作为原语？使用机器指令实现使用机器指令实现1、关中断、关中断2、测试与设置、测试与设置2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系17第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步q信号量实现互斥信号量实现互斥信号量的引入信号量的引入使用锁虽可以解决互斥问题，但是存在使用锁虽可以解决互斥问题，但是存在循环测试浪费循环测试浪费CPU的时间；的时间；

11、可能出现不公平现象；可能出现不公平现象；2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系18第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步Pa A:lock(keyS) unlock(keyS) goto APb B:lock(keyS) unlock(keyS) goto B执行结果 每个进程自己检测锁，查看自己是否可以进入临界区。这个过程，既浪费了CPU时间，也给进程进入临界区带来了不公平，因为必须调度该进程，它才能测试。2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系19第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步信号

12、量及其操作，将交通管制中多种颜色的信号量及其操作，将交通管制中多种颜色的信号灯管理交通的方法引入操作系统，让两信号灯管理交通的方法引入操作系统，让两个或多个进程通过特殊变量展开交互。个或多个进程通过特殊变量展开交互。1965年年E.W.Dijkstra(荷兰人）提出荷兰人）提出信信号量和号量和P 操作（荷兰语的测试操作（荷兰语的测试Proberen）、）、V操作（增量操作（增量Verhogen）。）。信号量（信号量（Semaphore）2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系20第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步v信号量定义信号量定义sem

13、：用一整数表示信号量：用一整数表示信号量sem=0：表示可以使用的资源数：表示可以使用的资源数sem0：表示正在等待使用临界区的进程数：表示正在等待使用临界区的进程数2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系21第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步vP/V原语原语P原语的主要动作原语的主要动作2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系22第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步V原语的主要动作原语的主要动作2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系23第三章第三章 进程管理进

14、程管理进程的互斥与同步进程的互斥与同步vP/V原语的实现原语的实现P原语的实现原语的实现P(sem):begin 关中断关中断 lock(lockbit) valsem=valsem-1 if valsem0 保护当前进程保护当前进程CPU现场现场 当前进程状态置为当前进程状态置为“等待等待” 将当前进程插入信号将当前进程插入信号sem等待队列等待队列 转进程调度转进程调度 fi unlock(lockbit) 开中断开中断end2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系24第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步V原语的实现原语的实现V(sem)

15、:begin 关中断关中断 lock(lockbit) valsem=valsem+1 if valsem=0 local k 从从sem等待队列中选取一等待进程，将其指针置入等待队列中选取一等待进程，将其指针置入k中中 将将k插入就绪队列插入就绪队列 进程状态置进程状态置“就绪就绪” fi unlock(lockbit) 开中断开中断end2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系25第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步用信号量实现互斥用信号量实现互斥信号量说明sem=1P0:P(sem)V(sem)P1:P(sem)V(sem)Pn:P(s

16、em)V(sem)2022年3月22日星期二16时35分50秒内蒙古工业大学计算机系26第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步例例1：设有三个进程：设有三个进程A、B、C需共享一个临界资源，需共享一个临界资源，用信号量实现该算法。用信号量实现该算法。sem=1;Pa()begin P(s); ； V(s);endPb()begin P(s); ； V(s);endPc()begin P(s); ； V(s);end2022年3月22日星期二16时35分51秒内蒙古工业大学计算机系27第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步 sem Pa Pb Pc

17、10P(sem)-1P(sem)-2-10V(sem)1P(sem)V(sem) V(sem)2022年3月22日星期二16时35分51秒内蒙古工业大学计算机系28第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步q进程同步进程同步进程间存在两种形式的制约关系：进程间存在两种形式的制约关系：间接制约间接制约互斥互斥直接制约直接制约同步同步2022年3月22日星期二16时35分51秒内蒙古工业大学计算机系29第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步同步的引入同步的引入设有计算和打印两个进程设有计算和打印两个进程PcPc和和Pp,Pp,共同使用共同使用同一缓冲区同

18、一缓冲区BufferBuffer，PcPc向向BufferBuffer中存放计算中存放计算结果，结果，PpPp从从BufferBuffer取计算结果送打印机输出。取计算结果送打印机输出。如下图模型。如下图模型。BufferPcPp2022年3月22日星期二16时35分51秒内蒙古工业大学计算机系30 假设互斥已解决，这两个进程的执行是相假设互斥已解决，这两个进程的执行是相互制约的。即互制约的。即PcPc的执行结果是的执行结果是PpPp的执行条件；的执行条件；而而PpPp的执行结果也是的执行结果也是PcPc的执行条件，它们是相的执行条件，它们是相互制约的。互制约的。第三章第三章 进程管理进程管理

19、进程的互斥与同步进程的互斥与同步 把一组在异步环境中由于以各自的执行把一组在异步环境中由于以各自的执行结果而限制其它进程的执行速度的现象称为结果而限制其它进程的执行速度的现象称为并发进程的直接制约，解决这种直接制约的并发进程的直接制约，解决这种直接制约的方法称为同步。模型如下。方法称为同步。模型如下。2022年3月22日星期二16时35分51秒内蒙古工业大学计算机系31PcPp第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步repeat wait(Bufempty); 计算; Buf-计算结果; Bufempty-false; signal(Buffull);Until fals

20、e repeat wait(Buffull); 打印缓冲区中的数据； Buffull-false; signal(Bufempty);Until false 2022年3月22日星期二16时35分51秒内蒙古工业大学计算机系32第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步v说明说明设置了两个消息设置了两个消息Bufempty和和Buffull，分别表，分别表示示buffer空和满空和满初始化初始化Bufempty=true，Buffull=falsewait(消息名消息名)：表示进程等待合作进程发来：表示进程等待合作进程发来的消息的消息signal(消息名消息名)：表示合作进

21、程发送消息：表示合作进程发送消息2022年3月22日星期二16时35分51秒内蒙古工业大学计算机系33第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步使用信号量实现同步使用信号量实现同步v私有信号量（私有信号量（Private Semaphore）只与制约进程及被制约进程相关，而与整组只与制约进程及被制约进程相关，而与整组并发进程无关。并发进程无关。相对实现互斥的信号量也称为公用信号量。相对实现互斥的信号量也称为公用信号量。2022年3月22日星期二16时35分51秒内蒙古工业大学计算机系34第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步v实现同步实现同步设置私有

22、信号量设置私有信号量为私有信号量赋初值为私有信号量赋初值利用利用P/V原语规定进程的执行顺序原语规定进程的执行顺序2022年3月22日星期二16时35分51秒内蒙古工业大学计算机系35第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步例如：进程例如：进程Pa和进程和进程Pb通过缓冲区队列传递数据。通过缓冲区队列传递数据。Pa为发送进程；为发送进程；Pb为接收进程。数据的接收和发为接收进程。数据的接收和发送满足下面的条件：送满足下面的条件：（1）缓冲区空时，）缓冲区空时，Pb不能从不能从中取数据；（中取数据；（2）Pa往缓冲区写数据时，缓冲区必往缓冲区写数据时，缓冲区必须有一块为空；

23、（须有一块为空；（3）缓冲区中的缓冲块按先进先）缓冲区中的缓冲块按先进先出（出（FIFO）的方式排列。）的方式排列。2022年3月22日星期二16时35分51秒内蒙古工业大学计算机系36第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步设置私有信号量并赋初值设置私有信号量并赋初值Bufempty=n，Buffull=0;Pa进程的发送过程的实现进程的发送过程的实现(deposit(data)2022年3月22日星期二16时35分51秒内蒙古工业大学计算机系37第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步Pb进程的接收过程的实现（进程的接收过程的实现（remove(

24、data)）2022年3月22日星期二16时35分51秒内蒙古工业大学计算机系38第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步生产者生产者消费者问题消费者问题v生产者生产者消费者问题消费者问题有有m m个生产者和个生产者和k k个消费者，连接在一个有个消费者，连接在一个有n n个单位缓冲区的有界缓冲上。其中，个单位缓冲区的有界缓冲上。其中，pipi和和cjcj都是并发进程，只要缓冲区未满，生都是并发进程，只要缓冲区未满，生产者产者pipi生产的产品就可投入缓冲区；只要生产的产品就可投入缓冲区；只要缓冲区不空，消费者进程缓冲区不空，消费者进程cjcj就可从缓冲区就可从缓冲区取走并消耗产品。取走并消耗产品。2022年3月22日星期二16时35分51秒内蒙古工业大学计算机系39m个生产者k个消费者n个单位缓冲区第三章第三章 进程管理进程管理进程的互斥与同步进程的互斥与同步生产者生产者消费者模型消费者模型把系统中使用某类资源的进程称为消费者；把系统中使用某类资源的进程称为消费者；把释放同类资源的进程称为生产者