操作系统第4讲综述课件

操作系统Operating Systems计算机专业核心课程授课：赵俊生 副教授版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程目目 录录第3章 进程管理3.5 进程互斥进程互斥3.6 进程同步进程同步操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程教教 学学 目目 的的1.掌握临界区、互斥的概念掌握临界区、互斥的概念5.掌握利用信号量解决并发进程同步的问题掌握利用信号量解决并发进程同步的问题2.掌握并发进程互斥执行的准则掌握并发进程互斥执行的准则4.掌握同步的概念掌握同步的概念3.掌握信号量和掌握信号量和P/V原语原语操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥一、资源共享所引起的制约一、资源共享所引起的制约1、临界区（、临界区（Critical region）v举例：例：设有计算进程Pa和Pb，共享内存MS。MS分为三个区：系统区、进程工作区和数据区。数据区被划分为大小相同的块，系统区主要是堆栈S，存放空数据的地址。（如下图所示）操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥1）取空数据块的过程）取空数据块的过程procedure getspace()begin local g -g1语句 g-stacktop -g2语句 top-top-1 -g3语句 return(g)-g4语句 end空数据块的管理：通过两个过程进行管理。一是取取空数据块；二是释放释放数据块。操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥2）释放数据块的过程）释放数据块的过程procedure release(ad)begin top-top+1 -r1语句 stacktop-ad -r2语句end3）一种执行结果）一种执行结果设t0时刻，top=h0，进程Pa与Pb并发执行的语句序列为：r1,g2,g3,r2结果？操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥4）临界区（）临界区（Critical region）把不允许多个并发进程交叉执行的一段程序称为临界部分（critical section）或临界区（critical region）。5）临界区的特点）临界区的特点特点1：不同进程的程序段；特点2：共享公用数据或公用数据变量操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥2、间接制约、间接制约把由于共享某一个公用资源而引起的在临界区内不允许并发进程交叉执行的现象,称为由共享公有资源而造成的对并发进程执行速度的间接制约执行速度的间接制约，简称间接制约。操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥1）类（）类（class）把那些不允许交叉执行的临界区按不同的公用数据划分为不同的集合，这些集合称为类（class）。公用数据栈S的临界区集合是getspace,release，类名为sp。例如例如操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥2）临界区的类描述）临界区的类描述When do od上例中的上例中的getspace和release的描述为：（见下页）操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥getspacewhen sp do g-stacktop top-top-1odrelease(ad)when sp do top-top+1 stacktop-ad od操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥3、互斥、互斥一组并发进程中的一个或多个程序段，因共享某一个共有资源而导致它们必须以一个不允许交叉执行的单位执行。操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥1）临界区调度原则）临界区调度原则(1)不假设各并发进程的执行速度(2)空闲让进(3)忙则等待(4)有限等待操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥二、互斥的加锁实现二、互斥的加锁实现通过对临界区加锁，在进入临界区时测试是否可以进入，退出临界区时对锁进行恢复。1）锁的定义）锁的定义keyS：表示临界区S(临界区类名)的锁定位keyS=1：表示临界区S可用keyS=0：表示临界区S不可用操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥2）用锁实现的临界区描述）用锁实现的临界区描述lock(keyS)unlock(keyS)3）lock/unlock的实现的实现（1）unlock的实现procedure unlock(keys)begin keys-1end操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥（2）lock的实现procedure lock(keys)begin local v repeat v-keys until v=1 keys-0end存在困难存在困难如何保证lock 操作为原语？使用机器指令实现使用机器指令实现1、关中断、关中断2、测试与设置、测试与设置操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥三、信号量实现互斥三、信号量实现互斥1、信号量的引入、信号量的引入使用锁虽可以解决互斥问题，但是存在循环测试浪费CPU的时间；可能出现不公平现象；操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥Pa A:lock(keyS)unlock(keyS)goto APb B:lock(keyS)unlock(keyS)goto B执行结果 每个进程自己检测锁，查看自己是否可以进入临界区。这个过程，即浪费了CPU时间，也给进程进入临界区带来了不公平，因为必须调度该进程，它才能测试。操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥信号量及其操作，将交通管制中多种颜色的信号灯管理交通的方法引入操作系统，让两个或多个进程通过特殊变量展开交互。1965年E.W.Dijkstra(荷兰人）提出信号量和P 操作（荷兰语的测试Proberen）、V操作（增量Verhogen）。2、信号量（、信号量（Semaphore）操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥1）信号量定义）信号量定义sem：用一整数表示信号量sem=0：表示可以使用的资源数sem0：表示正在等待使用临界区的进程数操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥2）P原语原语操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥P(sem):begin 关中断 lock(lockbit)valsem=valsem-1 if valsem0 保护当前进程CPU现场 当前进程状态置为“等待”将当前进程插入信号sem等待队列 转进程调度 fi unlock(lockbit)开中断end操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥3）V原语原语操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥V(sem):begin 关中断 lock(lockbit)valsem=valsem+1 if valsem=0 local k 从sem等待队列中选取一等待进程，将其指针置入k中 将k插入就绪队列 进程状态置“就绪”fi unlock(lockbit)开中断end操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥3）用信号量实现互斥）用信号量实现互斥信号量说明sem=1P0:P(sem)V(sem)P1:P(sem)V(sem)Pn:P(sem)V(sem)（1）一般模型）一般模型操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥（2）例：设有三个进程A、B、C需共享一个临界资源，用信号量实现该算法。sem=1;Pa()begin P(s);；V(s);endPb()begin P(s);；V(s);endPc()begin P(s);；V(s);end操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.5 3.5 进程互斥进程互斥 sem Pa Pb Pc10P(sem)-1P(sem)-2-10V(sem)1P(sem)V(sem)V(sem)操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.6 3.6 进程同步进程同步进程间存在两种形式的制约关系间接制约互斥直接制约同步操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.6 3.6 进程同步进程同步一、同步的引入一、同步的引入设有计算和打印两个进程Pc和Pp,共同使用同一缓冲区Buffer，Pc向Buffer中存放计算结果，Pp从Buffer取计算结果送打印机输出。如下图模型。BufferPcPp操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.6 3.6 进程同步进程同步假设互斥已解决，这两个进程的执行是相互制约的。即Pc的执行结果是Pp的执行条件；而Pp的执行结果也是Pc的执行条件，它们是直接制约的。把一组在异步环境中由于以各自的执行结果而限制其它进程的执行速度的现象称为并发进程的直直接制约接制约，解决这种直接制约的方法称为同步同步。二、同步二、同步操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.6 3.6 进程同步进程同步1、模型PcPprepeat wait(Bufempty);计算;Buf-计算结果;Bufempty-false;signal(Buffull);Until false repeat wait(Buffull);打印缓冲区中的数据；Buffull-false;signal(Bufempty);Until false 操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.6 3.6 进程同步进程同步2、说明、说明(1)设置了两个消息Bufempty和Buffull，分别表示buffer空和满(2)初始化Bufempty=true，Buffull=false(3)wait(消息名)：表示进程等待合作进程发来的消息(4)signal(消息名)：表示合作进程发送消息操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.6 3.6 进程同步进程同步三、使用信号量实现同步三、使用信号量实现同步1、私有信号量（、私有信号量（Private Semaphore）只与制约进程及被制约进程相关，而与整组并发进程无关。相对实现互斥的信号量也称为公用信号量公用信号量。操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.6 3.6 进程同步进程同步2、同步的实现步骤、同步的实现步骤(1)定义私有信号量(2)为私有信号量赋初值(3)利用P/V原语规定进程的执行顺序操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.6 3.6 进程同步进程同步例如：进程Pa和进程Pb通过缓冲区队列传递数据。Pa为发送进程；Pb为接收进程。数据的接收和发送满足下面的条件：（1）缓冲区空时，Pb不能从中取数据；（2）Pa往缓冲区写数据时，缓冲区必须有一块为空；（3）缓冲区中的缓冲块按先进先出（FIFO）的方式排列。操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.6 3.6 进程同步进程同步解：解：（1）设置私有信号量并赋初值）设置私有信号量并赋初值Bufempty=n，Buffull=0;（2）Pa进程的发送过程的实现进程的发送过程的实现(deposit(data)操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.6 3.6 进程同步进程同步(3)Pb进程的接收过程的实现（进程的接收过程的实现（remove(data)）操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.6 3.6 进程同步进程同步四、生产者四、生产者消费者问题消费者问题1、生产者、生产者消费者问题消费者问题有m个生产者和k个消费者，连接在一个有n个单位缓冲区的有界缓冲上。其中，pi和cj都是并发进程，只要缓冲区未满，生产者pi生产的产品就可投入缓冲区；只要缓冲区不空，消费者进程cj就可从缓冲区取走并消耗产品。操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.6 3.6 进程同步进程同步m个生产者k个消费者n个单位缓冲区2、生产者、生产者消费者模型消费者模型把系统中使用某类资源的进程称为消费者；把释放同类资源的进程称为生产者。操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.6 3.6 进程同步进程同步3、信号量解决生产者、信号量解决生产者消费者问题消费者问题1)设置公有信号量mutex，以实现互斥；2)设置私有信号量empty和full，以实现同步；3)赋初值：empty=k,full=0,mutex=1;4)实现deposit(data)和remove(data)操作操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.6 3.6 进程同步进程同步deposit(data):begin P(avail)P(mutex)送数据入缓冲区某单元 V(mutex)V(full)endremove(data):begin P(full)P(mutex)取缓冲区中某单元数据 V(mutex)V(avail)endavail-nfull-0mutex-1操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程3.6 3.6 进程同步进程同步1、可以实现进程间的同步与互斥2、可读性差。要知道整个程序中共享变量和信号量的操作是否正确，必须通读整个程序。3、不利于维护和修改。因为修改一个量可能会影响整个程序。4、正确性难以保证。因为程序很大。五、信号量的性能五、信号量的性能操作系统（Operating Systems）授课：赵俊生版权所有：内蒙古工业大学信息工程学院 计算机系操作系统课程组计算机专业核心课程作作 业业习题习题 3.9，3.11思考题思考题 3.10，3.6