计算机操作系统第三讲

2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,1,第三章 进程管理进程的互斥与同步,教学目的,掌握利用信号量解决并发进程同步的问题,掌握临界区、互斥的概念,掌握并发进程互斥执行的准则,掌握信号量和P/V原语,掌握同步的概念,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,2,第三章 进程管理进程的互斥与同步,教学内容,3.5 进程互斥,3.6 进程同步,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,3,第三章 进程管理进程的互斥与同步,资源共享所引起的制约,临界区,举例,设有计算进程Pa和Pb，共享内存MS。MS分为三个区：系统区、进程工作区和数据区。数据区被划分为大小相同的块，系统区主要是堆栈S，存放空数据的地址。,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,4,第三章 进程管理进程的互斥与同步,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,5,第三章 进程管理进程的互斥与同步,取空数据块的过程,procedure getspace() begin local g -g1语句 g-stacktop -g2语句 top-top-1 -g3语句 return (g) -g4语句 end,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,6,第三章 进程管理进程的互斥与同步,释放数据块的过程,procedure release(ad) begin top-top+1 -r1语句 stacktop-ad -r2语句 end,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,7,第三章 进程管理进程的互斥与同步,一种执行结果,设t0时刻，top=h0，进程Pa与Pb并发执行的语句序列为： r1,g2,g3,r2,执行结果,由学生自己完成！,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,8,虽然可以判断两个相邻语句是否能并发执行，但是这种方法的局限性在于将花费巨大的系统开销。,解决办法,第三章 进程管理进程的互斥与同步,产生的原因,该资源是不能被共享并发使用的。,方法一： Bernstein条件,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,9,第三章 进程管理进程的互斥与同步,不允许多个并发进程交叉执行的一段程序。,方法二：临界区（Critical region）,间接制约,类（class）,把那些不允许交叉执行的临界区按不同的公用数据划分为不同的集合。,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,10,第三章 进程管理进程的互斥与同步,公用数据栈S的临界区集合是getspace,release。,例如,临界区的程序描述,When do od,上例中的getspace和release的描述为：,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,11,第三章 进程管理进程的互斥与同步,getspace,when sp do g-stacktop top-top-1 od,release(ad),when sp do top-top+1 stacktop-ad od,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,12,第三章 进程管理进程的互斥与同步,间接制约,把这种由于共享某一个公用资源而引起的在临界区内不允许并发进程交叉执行的现象。,互斥,一组并发进程中的一个或多个程序段，因共享某一个共有资源而导致它们必须以一个不允许交叉执行的单位执行。,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,13,第三章 进程管理进程的互斥与同步,临界区调度原则,不假设各并发进程的执行速度,空闲让进,忙则等待,有限等待,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,14,第三章 进程管理进程的互斥与同步,互斥的加锁实现,通过对临界区加锁，在进入临界区时测试是否可以进入，退出临界区时对锁进行恢复。,锁的定义,keyS：表示临界区S(临界区类名)的锁定位 keyS=1：表示临界区S可用 keyS=0：表示临界区S不可用,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,15,第三章 进程管理进程的互斥与同步,加锁实现临界区的描述,lock(keyS) unlock(keyS),lock/unlock的实现,unlock的实现,procedure unlock(keys) begin keys-1 end,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,16,第三章 进程管理进程的互斥与同步,lock的实现,procedure lock(keys) begin local v repeat v-keys until v=1 keys-0 end,存在困难 如何保证lock 操作为原语？,使用机器指令实现 1、关中断 2、测试与设置,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,17,第三章 进程管理进程的互斥与同步,信号量实现互斥,信号量的引入,使用锁虽可以解决互斥问题，但是存在循环测试浪费CPU的时间；,可能出现不公平现象；,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,18,第三章 进程管理进程的互斥与同步,Pa A:lock(keyS) unlock(keyS) goto A Pb B:lock(keyS) unlock(keyS) goto B,执行结果 每个进程自己检测锁，查看自己是否可以进入临界区。这个过程，既浪费了CPU时间，也给进程进入临界区带来了不公平，因为必须调度该进程，它才能测试。,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,19,第三章 进程管理进程的互斥与同步,信号量及其操作，将交通管制中多种颜色的信号灯管理交通的方法引入操作系统，让两个或多个进程通过特殊变量展开交互。,1965年E.W.Dijkstra(荷兰人）提出信号量和P 操作（荷兰语的测试Proberen）、V操作（增量Verhogen）。,信号量（Semaphore）,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,20,第三章 进程管理进程的互斥与同步,信号量定义,sem：用一整数表示信号量,sem=0：表示可以使用的资源数,sem0：表示正在等待使用临界区的进程数,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,21,第三章 进程管理进程的互斥与同步,P/V原语,P原语的主要动作,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,22,第三章 进程管理进程的互斥与同步,V原语的主要动作,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,23,第三章 进程管理进程的互斥与同步,P/V原语的实现,P原语的实现,P(sem): begin 关中断 lock(lockbit) valsem=valsem-1 if valsem0 保护当前进程CPU现场 当前进程状态置为“等待” 将当前进程插入信号sem等待队列 转进程调度 fi unlock(lockbit) 开中断 end,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,24,第三章 进程管理进程的互斥与同步,V原语的实现,V(sem): begin 关中断 lock(lockbit) valsem=valsem+1 if valsem=0 local k 从sem等待队列中选取一等待进程，将其指针置入k中 将k插入就绪队列 进程状态置“就绪” fi unlock(lockbit) 开中断 end,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,25,第三章 进程管理进程的互斥与同步,用信号量实现互斥,信号量说明 sem=1,P0: P(sem) V(sem) ,P1: P(sem) V(sem) ,Pn: P(sem) V(sem) ,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,26,第三章 进程管理进程的互斥与同步,例1：设有三个进程A、B、C需共享一个临界资源，用信号量实现该算法。,sem=1; Pa() begin P(s); ； V(s); end,Pb() begin P(s); ； V(s); end,Pc() begin P(s); ； V(s); end,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,27,第三章 进程管理进程的互斥与同步,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,28,第三章 进程管理进程的互斥与同步,进程同步,进程间存在两种形式的制约关系：,间接制约互斥,直接制约同步,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,29,第三章 进程管理进程的互斥与同步,同步的引入,设有计算和打印两个进程Pc和Pp,共同使用同一缓冲区Buffer，Pc向Buffer中存放计算结果，Pp从Buffer取计算结果送打印机输出。如下图模型。,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,30,假设互斥已解决，这两个进程的执行是相互制约的。即Pc的执行结果是Pp的执行条件；而Pp的执行结果也是Pc的执行条件，它们是相互制约的。,第三章 进程管理进程的互斥与同步,把一组在异步环境中由于以各自的执行结果而限制其它进程的执行速度的现象称为并发进程的直接制约，解决这种直接制约的方法称为同步。模型如下。,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,31,第三章 进程管理进程的互斥与同步,repeat wait(Bufempty); 计算; Buf-计算结果; Bufempty-false; signal(Buffull); Until false,repeat wait(Buffull); 打印缓冲区中的数据； Buffull-false; signal(Bufempty); Until false,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,32,第三章 进程管理进程的互斥与同步,说明,设置了两个消息Bufempty和Buffull，分别表示buffer空和满,初始化Bufempty=true，Buffull=false,wait(消息名)：表示进程等待合作进程发来的消息,signal(消息名)：表示合作进程发送消息,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,33,第三章 进程管理进程的互斥与同步,使用信号量实现同步,私有信号量（Private Semaphore）,只与制约进程及被制约进程相关，而与整组并发进程无关。,相对实现互斥的信号量也称为公用信号量。,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,34,第三章 进程管理进程的互斥与同步,实现同步,设置私有信号量,为私有信号量赋初值,利用P/V原语规定进程的执行顺序,2019年1月28日星期一1时0分57秒,内蒙古工业大学计算机系,35,第三章 进程管理进程的互斥与同步,例如：进程Pa和进程Pb通过缓冲区队列传递数据。Pa为发送进程；Pb为接收进程。数据的接收和发送满足下