内容回顾内容回顾•操作系统的基本特征？操作系统的基本特征？•什么是微内核操作系统，它使用了哪些什么是微内核操作系统，它使用了哪些技术？技术？1 第二章 进程管理 （ ）学习目标：理解进程的概念以及 与程序的异同掌握进程的实体、状态及状态的演变熟练掌握进程的控制与调度掌握进程之间的关系协调（同步与互斥 ）掌握进程的通信熟练掌握用信号量描述进程的同步2 第二章 进程管理1 进程的基本概念2 进程控制3 进程同步4 经典进程的同步问题5 管程机制6 进程通信7 线程3 第二章 进程管理2.1 进程的基本概念在传统的操作系统中，程序并不能独立运行，作为资源分配和独立运行的基本单位都是进程在未配置OS的系统中，程序是顺序执行的在多道运行环境下，允许程序的并发执行 4 2.1.1 程序的顺序执行及其特征(图2-1)1 程序的顺序执行：2 特征：顺序性：程序段中的操作和指令按顺序执行封闭性：程序独占资源，结果不受外界因素影响可再现性：只要程序的运行环境和初始条件相同，无论什么时间执行都能得到相同的结果5 2.1.2 前趋图（图2-2）前趋图（Procedure Graph）是一个有向无循环图DAG（Directed Acyclic Graph），用于描述进程之间执行的前后关系。
图中的每一个结点可以用来表示一条语句、一个程序段或进程；结点间的有向边则表示在两结点之间存在的偏序或前趋关系6 2.1.3 程序的并发执行及其特征程序的并发执行：图2-3特征：•间断性:并发性引起资源的共享或相互合作，因此形成了相互制约的关系，因而导致并发程序的“执行－暂停－执行”的间断过程•失去封闭性:并发性引起资源的共享，资源的状态由多个进程改变，这样进程的运行就失去了封闭性7 •不可再现性：并发性使程序的运行失去了封闭性，程序的计算结果与程序的速度有关，从而失去了结果的可再现性•例如两个循环程序A和B,他们共享一个变量N，A执行一次N:=N+1，B执行一次都完成Print(N),然后执行N:=0.则会出现：•N:=N+1;Print(N);N:=0;•Print(N);N:=0;N:=N+1;•Print(N);N:=N+1;N=0;8 2.1.4 2.1.4 进程的特征与状态进程的特征与状态为什么要引入进程？并发程序执行的不可再现性，使程序的并发执行失去了意义，为了程序能并发执行，且能够对并发执行的程序进行控制和描述9 进程的定义：进程是进程实体（程序段、数据段、进程控制块）的运行过程，是系统进行资源分配和调度的独立单位10 1)结构特征：程序段，数据段，PCB（进程控制块）为了使程序能够独立运行而存放程序控制信息的数据结构。
2)动态性：进程的实质是进程实体的一次执行过程，由创建而生，由调度而执行，由撤销而消亡3)并发性：多个进程同驻内存，在一段时间内同时运行4)独立性：独立运行、资源分配、调度的单位5)异步性：独立的，不可预知的速度向前推进进程的特征进程的特征：11 思考题•程序与进程的联系与区别？程序与进程的联系与区别？12 进程基本状态及其转换：•进程的动态性表明进程在其生存期内会经历一系列的离散状态，运行中的进程可以处于一下三种状态之一 图2-5•就绪态：万事具备，只欠CPU•执行态：进程获得CPU,正在运行•阻塞态：发生事件无法继续13 状态转换：就绪—进程调度分配CPU—执行执行—时间片用完—就绪执行—因某事件（I/O请求）—阻塞阻塞—资源满足（I/O完成）—就绪例题14 3.3.具有挂起功能的进程状态及其转换具有挂起功能的进程状态及其转换•由于进程的不断创建，系统的资源特别由于进程的不断创建，系统的资源特别是内存资源不能满足进程运行的需要，是内存资源不能满足进程运行的需要，这时必须把某个进程对换到磁盘中，释这时必须把某个进程对换到磁盘中，释放该进程占有的资源，暂时不参与进程放该进程占有的资源，暂时不参与进程调度，起到平滑系统操作负荷的目的。
调度，起到平滑系统操作负荷的目的15 •这种对换到磁盘，暂时不进行调度的进程状态这种对换到磁盘，暂时不进行调度的进程状态叫做挂起状态（静止状态），分为静止就绪和叫做挂起状态（静止状态），分为静止就绪和静止阻塞静止阻塞•将进程换出的过程叫挂起将进程换出的过程叫挂起•将静止的进程换入的过程叫做释放将静止的进程换入的过程叫做释放•静止就绪：进程具备运行条件，但处于辅存静止就绪：进程具备运行条件，但处于辅存•静止阻塞：进程正在等待某事件且在辅存中静止阻塞：进程正在等待某事件且在辅存中16 •系统中的进程均处于阻塞状态，处理机空闲，此系统中的进程均处于阻塞状态，处理机空闲，此时需要腾出内存空间，将资源分配给某个等待进时需要腾出内存空间，将资源分配给某个等待进程，然后执行程，然后执行•竞争资源，导致资源不足，负荷过重，此时需要竞争资源，导致资源不足，负荷过重，此时需要将一些进程挂起，释放资源将一些进程挂起，释放资源•用户要求挂起的自己的进程，以便对中间结果进用户要求挂起的自己的进程，以便对中间结果进行核查，修改行核查，修改•父进程要求修改子进程时，需要将子进程挂起父进程要求修改子进程时，需要将子进程挂起。
• 17 状态转换：如图2-61.活动阻塞－静止阻塞：活动阻塞进程由其活动阻塞－静止阻塞：活动阻塞进程由其自身调用或其他进程调用挂起原语自身调用或其他进程调用挂起原语（（suspend)在其挂起期间并不影响其在其挂起期间并不影响其等待事件的发生等待事件的发生2.活动就绪－静止就绪：活动就绪进程由其活动就绪－静止就绪：活动就绪进程由其自身或其他进程调用挂起原语而进入的一自身或其他进程调用挂起原语而进入的一种状态在其挂起期间没有资格竞争种状态在其挂起期间没有资格竞争cpu18 创建状态和终止状态创建状态和终止状态•创建一个进程需要：创建PCB,并填写必要的管理信息；分配内存资源，转入就绪状态•终止一个进程需要：首先等待OS进行善后处理；然后将PCB清零，将PCB空间返还系统19 创建就绪执行阻塞终止许可时间片完进程调度I/O完成I/O请求释放图图2-7进程的五种基本状态及转换进程的五种基本状态及转换20 1.5 1.5 进程控制块（进程控制块（图示图示）：）：•记录了操作系统所需要的,用于描述进程 的当前状态、本身特性、对资源的占有以及控制进程运行的全部信息•记录了这些信息的数据结构就是进程控制块（（PCB)PCB) , ,是进程存在的唯一标志，常驻内存。
是进程存在的唯一标志，常驻内存21 2 进程控制块中信息：进程标识符：•外部标识符-名字、用户使用;•内部标识符-数字、系统使用 处理机状态：由处理机各种寄存器中的内容组成处理机运行时状态信息放在寄存器中，处理机中断时放在PCB中•通用寄存器、指令计数器、程序状态字(PSW)、用户栈指针22 进程调度信息（进程状态、进程优先级、进程调度需要的其它信息、事件） 进程控制信息（程序和数据地址、进程同步和通信机制、资源清单和链接指针）23 3 PCB的的组织方式组织方式系统中通常会由多个PCB，这些PCB通常会用某种方式组织起来，才能有效的管理•链接方式（图2-7）•索引方式（图2-8）24 2.2 进程控制 进程控制是进程管理的最基本的功能，用于创建新进程，终止进程，进程的状态转换进程控制由OS内核中的原语实现原语：由若干指令组成的，用于完成一定功能的过程，这些过程是原子操作原子操作：是一个不可分的基本单位，操作中的动作或者全做或者全不做 25 •在操作系统中，通常把进程控制用程序段在操作系统中，通常把进程控制用程序段做成原语用于进程控制的原语有：创建做成原语用于进程控制的原语有：创建原语原语(creat)、撤销原语、撤销原语(destory)、阻塞原、阻塞原语语(block)、唤醒原语、唤醒原语(wakeup)等。
等26 2.2.1 进程创建•进程在执行过程中可以通过系统调用创建多个子进进程在执行过程中可以通过系统调用创建多个子进程，将正在执行的进程叫做父进程，新创建的进程程，将正在执行的进程叫做父进程，新创建的进程叫做子进程叫做子进程1 1 进程图进程图：描述进程的家族关系的有向树（图2-9） 父进程、子进程、祖先进程 进程图由结点和有向边构成27 •子进程可以继承父进程拥有的资源子进程可以继承父进程拥有的资源•子进程撤销时要归还父进程的资源子进程撤销时要归还父进程的资源•父进程撤销时必须同时撤销所有的子进程父进程撤销时必须同时撤销所有的子进程•在在PCB设置了家族关系表项，标明进程的父进设置了家族关系表项，标明进程的父进程和所有子进程程和所有子进程28 请同学们想一下：请同学们想一下：•使用进程图是为了描述什么？使用进程图是为了描述什么？•进程图与前趋图的比较，有什么异同？进程图与前趋图的比较，有什么异同？29 2 引起进程创建的事件：•用户登录•作业调度•提供服务•应用请求 系统创建进程父进程创建进程30 3 进程的创建调用creat()原语•申请空白PCB和唯一的数字标识符•为新进程分配资源（内存空间）•初始化PCB—标识信息，处理机状态信息，处理机控制信息•将进程插入就绪队列。
建立PCB，分配内存，加载程序，入就绪链31 入口入口查查PCB链表链表有空有空PCB？？PCB（（I））入进程家族或进程链入进程家族或进程链PCB( 1)入就绪队列入就绪队列将有关参数填入将有关参数填入PCB（（1））相应项相应项取空表取空表PCB(1)返回返回创建失败创建失败无创建原语流程图创建原语流程图有32 • Creat(s0,m0,pi)•{•p=Get-New-PCB(); 分配新的PCB•pid= Get-New-PID(); 分配进程ID•p->ID=pid; 设置进程ID•p->CPU-State=so; CPU的状态•p->Memory=m0;•p->Priority=pi;•p->Status. Type=‘ready’;•p->Status. List=RL;•Insert(RL,p);•Scheduler(); 调度程序•}33 2.2.2 进程终止 引起进程终止的事件：1 1 正常结束：计算机系统中，都有一个表示进程已正常结束：计算机系统中，都有一个表示进程已经运行完成的指示如：批处理经运行完成的指示。
如：批处理(Holt)(Holt)，分时系，分时系统中统中(Logs Off(Logs Off））2 2 异常结束异常结束 越界错误、保护错、特权指令错、非法指令错、越界错误、保护错、特权指令错、非法指令错、 运行超时、等待超时、算术运算错、运行超时、等待超时、算术运算错、 I/O I/O故障故障3 3 外界干预外界干预 操作员或操作系统干预操作员或操作系统干预 父进程请求父进程请求 父进程终止父进程终止34 入口返回查进程链表或进程家族有此PCB吗？该PCB有子进程吗？释放该进程所占有的资源释放该PCB结构本身出错处理有无有35 2 终止过程:调用进程终止原语1.根据进程标识符，从PCB集合中检索出该 进程的PCB，读出该进程的状态；2.若正处于执行态，立即停止该进程的执行，并设置调度标志为真，把处理机分配给新进程；3. 终止所有子进程；4. 全部资源归还给其父进程或系统；5.将被终止进程的PCB从所在队列（或链表）中移出归还资源，撤销归还资源，撤销PCB，通知父进程，通知父进程36 •Destroy(pid)•{• p=Get-PCB(pid);•Kill-Tree(p);•Scheduler();•}Kill-Tree(p){For(each q in p->creation.tree.child) Kill-tree(q);If(p->status.type=‘runing’{p1=p->processor-ID;Interrupt(p1);}Remove(p->status.list,p);release-all(p->memory);Releas-all(p->other-resources);Close-all(p->open-files);Delete-PCB(P);}37 2.2.3 进程的阻塞和唤醒1 进程阻塞一个进程经常要和其他进程通信。
这一个进程经常要和其他进程通信这在运行的进程因为提出服务请求在运行的进程因为提出服务请求（（I/O)I/O)操作，未得到操作系统的立即操作，未得到操作系统的立即满足，或者所需数据尚未到达等原因，满足，或者所需数据尚未到达等原因，将转变为阻塞状态将转变为阻塞状态38 2 阻塞过程：调用阻塞原语block()，是主动行为•停止进程的执行•将PCB中的执行态改为阻塞态•将PCB插入阻塞队列•将处理机分配给另一个就绪进程 39 入口保存当前进程的CPU现场置该进程的状态被阻塞进程入等待队列转进程调度阻塞原语阻塞原语40 •Block( )•{• p=Get-PCB();• s=p->Status.Type;•Cpu=p->processor-ID;• P->CPU-State=interrupt(cpu);• p->status.type=‘blocked’;•Insert(BL,p);•Scheduler( );•}41 3 唤醒过程唤醒原语wakeup()，将等待该事件的进程唤醒•把阻塞的进程从阻塞队列中移出•将PCB的状态由阻塞改为就绪•将PCB插入就绪队列42 入口从等待队列中摘下被唤醒进程将被唤醒进程置为就绪状态将被唤醒进程送入就绪队列进程调度返回唤醒原语唤醒原语43 •Wakeup(pid)•{•P=Get-PCB(pid);•Remove(p->status.list,p);•P->status.type=‘ready’;•Insert(RL,p);•Scheduler();•}44 2.2.4 进程的挂起和激活•当出现了引起进程挂起的事件时，用户请求将当出现了引起进程挂起的事件时，用户请求将自己挂起，或者父进程请求挂起自己的子进程，自己挂起，或者父进程请求挂起自己的子进程，应该利用挂起原语应该利用挂起原语suspend()•挂起原语的执行过程：检查被挂起进程的状态；挂起原语的执行过程：检查被挂起进程的状态；如果处于活动就绪状态，就将它改为静止就绪；如果处于活动就绪状态，就将它改为静止就绪；如果处于活动阻塞，则改为静止阻塞。
如果处于活动阻塞，则改为静止阻塞•进程的激活过程：当发生激活事件后，系统利进程的激活过程：当发生激活事件后，系统利用激活原语用激活原语Active()将指定进程激活激活原将指定进程激活激活原语先将进程从外存调入内存，然后检查进程的语先将进程从外存调入内存，然后检查进程的状态45 填空题•为使进程由活动就绪转变为静止就绪，应利用为使进程由活动就绪转变为静止就绪，应利用__⑴⑴__原语；为使进程由执行状态变为阻塞状态，原语；为使进程由执行状态变为阻塞状态，应利用应利用__⑵⑵__原语；为使进程由静止就绪变为活原语；为使进程由静止就绪变为活动就绪，应利用动就绪，应利用__⑶⑶__原语；从阻塞状态变为就原语；从阻塞状态变为就绪状态应利用绪状态应利用__⑷⑷__原语•⑴-⑷： suspend() block() active () wakeup()46 知识回顾知识回顾•什么是进程什么是进程?•进程的三种基本状态及转换条件及其关进程的三种基本状态及转换条件及其关系？系？•什么是进程控制块什么是进程控制块PCB?47 2.3 进程同步•在多道程序运行环境下，并发执行的进程共享在多道程序运行环境下，并发执行的进程共享计算机资源，从而导致进程之间存在着一定的计算机资源，从而导致进程之间存在着一定的制约关系。
制约关系•为了保证执行结果的正确性和资源的充分利用，为了保证执行结果的正确性和资源的充分利用，系统必须提供相应的并发控制机制（进程同步系统必须提供相应的并发控制机制（进程同步机制）机制）•并发进程之间为了完成某个任务而相互等待的并发进程之间为了完成某个任务而相互等待的关系就是进程同步关系关系就是进程同步关系48 进程同步的任务：对多个相关进程在执行次序上进行协调，使并发进程之间有效的共享资源和相互合作，使执行结果可再现2.3.1 进程同步的基本概念1 两种形式的制约关系：•直接相互制约（源于相互合作）•间接相互制约(源于资源共享）49 1). 1). 直接相互制约：发生在相关进程之间直接相互制约：发生在相关进程之间直接相互制约：发生在相关进程之间直接相互制约：发生在相关进程之间sendreceiveP1:P2:2). 2). 间接相互制约：发生在任何进程之间间接相互制约：发生在任何进程之间间接相互制约：发生在任何进程之间间接相互制约：发生在任何进程之间RP2P1holdwait50 2 临界资源临界资源临界资源：临界资源：一段时间内只允许一个进程访问的资源一段时间内只允许一个进程访问的资源要求要求：各进程必须互斥访问临界资源。
各进程必须互斥访问临界资源原因：原因：例如例如 生产者－消费者进程生产者－消费者进程生产者进程（生产者进程（producer) 消费者进程（消费者进程（consumer){ … { … 放产品放产品 取产品取产品 counter:=counter+1; counter:=counter-1; … …} }51 机器语言形式为：生产者进程机器语言形式为：生产者进程 counter:=counter+1;1 register1:=counter;2 register1:=register1+1;3 counter:=register1消费者消费者进程counter:=counter-1;4 register2:=counter;5 register2:=register2-1;6 counter:=register2由于生产者和消费者并发运行，且共享变量由于生产者和消费者并发运行，且共享变量counter，造成：，造成：可能性可能性ABCD其他其他CPU执行顺序执行顺序123456456123124536451263…Counter初初值值55546…正确正确正确正确不正确不正确不正确不正确不正确不正确52 3 临界区临界区•临界区：每个进程中访问临界资源的代码称为 临界区。
•进入区：检查临界资源是否正在被使用•退出区：将临界资源使用标志恢复，释放临界 资源•剩余区：保证进程互斥的进入临界区，从而保证互斥访问临界资源53 临界区临界区(CS)：每个进程中访问临界资源的那段代码：每个进程中访问临界资源的那段代码生产者进程（生产者进程（producer) 消费者进程（消费者进程（consumer){ … { … 放产品放产品 取产品取产品counter:=counter+1;－－(CS) counter:=counter-1;-(CS) … …} }为了实现对临界资源的互斥访问，应保证各进程互斥为了实现对临界资源的互斥访问，应保证各进程互斥的进入临界区的进入临界区54 4 4 同步机制应遵循的规则：同步机制应遵循的规则： •空闲让进，•忙则等待，•有限等待，•让权等待。
55 •P操作相当于申请资源，而操作相当于申请资源，而V操作相当于操作相当于释放资源所以要记住以下几个关键字：释放资源所以要记住以下几个关键字：•P操作操作----申请资源申请资源•V操作操作----释放资源释放资源2.3.2 信号量机制信号量机制56 •PV操作的含义：操作的含义：PV操作是由操作是由P操作原语和操作原语和V操作操作原语组成（原语是不可中断的过程），对信号量原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下：进行操作，具体定义如下：•P（（S）：）：①①将信号量将信号量S的值减的值减1，即，即S=S 1；；• ②②如果如果S 0，则该进程继续执行；否，则该进程继续执行；否则该进程置为等待状态，排入等待队列则该进程置为等待状态，排入等待队列•V（（S）：）：①①将信号量将信号量S的值加的值加1，即，即S=S+1；；• ②②如果如果S>0，则该进程继续执行；否，则该进程继续执行；否则释放队列中第一个等待信号量的进程则释放队列中第一个等待信号量的进程57 一个生产者，一个消费者，公用一个缓冲区一个生产者，一个消费者，公用一个缓冲区好好又又多多一一分分 店店伊伊利利牛牛奶奶生生产产厂家件厂家件生产一个产品生产一个产品取出一个产品取出一个产品58 •empty——表示缓冲区是否为空，初值为表示缓冲区是否为空，初值为1。
•full——表示缓冲区中是否为满，初值为表示缓冲区中是否为满，初值为0生产者进程生产者进程while(TRUE){生产一个产品生产一个产品; P(empty); 产品送往产品送往Buffer; V(full);}消费者进程消费者进程while(TRUE) { P(full); 从从Buffer取出一个产品取出一个产品; V(empty); 消费该产品消费该产品; }59 •信号量机制信号量机制是一种卓有成效的进程同步进程同步工具，被广泛应用于单处理机和多处理机系统，以及计 算机网络中 信号量机制信号量机制60 （１）（１） 信号量的含义信号量的含义信号量是一个用来实现进程同信号量是一个用来实现进程同步的整型或记录型变量，除了初始化外，对它只能步的整型或记录型变量，除了初始化外，对它只能执行执行 wait和和signal这两种原子操作这两种原子操作 在学习时，应了解对信号量的在学习时，应了解对信号量的wait和和signal操作分别操作分别是如何实现的，整型信号量存在着什么不足之处，是如何实现的，整型信号量存在着什么不足之处，记录型信号量是如何解决整型信号量的不足的。
记录型信号量是如何解决整型信号量的不足的 61 （２）２） 信号量的物理意义信号量的物理意义一个信号量一个信号量 S通通常对应于一类临界资源常对应于一类临界资源 在学习时，必须理解在学习时，必须理解S.value的值在物理上的值在物理上有什么特殊的含义，而每次有什么特殊的含义，而每次wait和和signal操操作又分别意味着什么，故必须分别对作又分别意味着什么，故必须分别对S.value进行什么操作进行什么操作 62 （３）（３） 用信号量实现互斥用信号量实现互斥为了实现进程对临为了实现进程对临界资源的互斥访问，需为每类临界资源设置一界资源的互斥访问，需为每类临界资源设置一初值为初值为 1的互斥信号量的互斥信号量mutex 在学习时，应清楚在进入临界区前或退出临界在学习时，应清楚在进入临界区前或退出临界区后应对区后应对mutex分别执行什么操作，为什么对分别执行什么操作，为什么对mutex的的wait和和signal操作必须成对出现，如操作必须成对出现，如少了其中的少了其中的wait操作或操作或signal操作，会对互斥操作，会对互斥算法产生什么样的影响算法产生什么样的影响 63 （４）（４） 用信号量实现前趋关系。
用信号量实现前趋关系为实现前为实现前趋关系趋关系 Pi→Pj，可为它们设置一个初值为，可为它们设置一个初值为0的信号量的信号量S 在学习时，应清楚对在学习时，应清楚对S的的wait操作和操作和signal操作应分别安排在什么位置，同时必须注操作应分别安排在什么位置，同时必须注意意wait(S)操作和操作和signal(S)操作也必须成对操作也必须成对出现64 信号量的分类：信号量的分类：整型信号量整型信号量（（integer semaphore)：信号：信号量是整数量是整数记录型信号量记录型信号量（（record semaphore)：每：每个信号量个信号量s除一个整数值除一个整数值s.value（计数）（计数）外，还有一个进程等待队列外，还有一个进程等待队列s.L，其中是阻，其中是阻塞在该信号量的各个进程的标识塞在该信号量的各个进程的标识65 1、整型信号量、整型信号量 •最初由最初由Dijkstra把整型信号量定义为一个整型量，把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作除初始化外，仅能通过两个标准的原子操作wait(s)和和signal(s)来访问，分别称为来访问，分别称为P和和V操作。
操作•wait(s): while s<=0 do no_op;• s:=s-1;• •signal(s): s:=s+1 • if s<=0 then wakeup(P1);• 66 2、记录型信号量、记录型信号量• 在整型信号量中的在整型信号量中的wait(s)，只要，只要s<=0则会不停地测试，该机制不遵循则会不停地测试，该机制不遵循“让权让权等待等待”的准则，记录型的信号量描述如的准则，记录型的信号量描述如下：下：• type semaphore = record• Value :integer;• L: list of process;• end67 相应的相应的wait(s)和和signal(s)操作描述如下：操作描述如下：procedure wait(s) var s:semaphore; begin s.Value := s.Value-1; if s.Value <0 then block(s,L); end;procedure signal(s) var s:semaphore; begin s.Value := s.Value+1; if s.Value <=0 then wakeup(s.L); end;• 当当s.Value初值为初值为1时表示互斥信号量。
时表示互斥信号量68 3、、AND型信号量型信号量 •上述的进程互斥问题是针对进程之间要共享一上述的进程互斥问题是针对进程之间要共享一个临界资源，在某些场合下，一个进程要先获个临界资源，在某些场合下，一个进程要先获得两类或更多的共享资源方能执行任务得两类或更多的共享资源方能执行任务•例：有例：有A、、B进程，它们共享进程，它们共享D和和E两个临界资源，两个临界资源，对这两个数据分别用信号量对这两个数据分别用信号量S1和和S2，且，且S1=S2=1，则在这两个进程中必然会有：，则在这两个进程中必然会有：•process A process B wait(S1); wait(S2); wait(S2); wait(S1)；； 69 如按如下调度方式，则如按如下调度方式，则A、、B进程进入了死锁进程进入了死锁 时刻时刻ABS1S2(1)Wait(s1)S1=0(2)Wait(s2)S2=0(3)Wait(s2)S2=-1(4)等待等待(5)Wait(s1)S1=-1(6)等待等待70 •AND同步机制的基本思想：将进程在整同步机制的基本思想：将进程在整个运行过程中所需要的所有临界资源一个运行过程中所需要的所有临界资源一次性分配给进程，使用完后一起释放，次性分配给进程，使用完后一起释放，只要一个资源没有分配到则其它可能分只要一个资源没有分配到则其它可能分配到的资源也不分配，已经分配的全部配到的资源也不分配，已经分配的全部释放，释放，AND原语对资源的分配是原子的，原语对资源的分配是原子的，其操作定义如下：其操作定义如下： 71 •swait(s1,s2,...sn) if s1>=1 and s2>=1 and ... sn>=1 then for i=1 to n do si := si-1; endfor else将调用将调用swait的进程置入所有的对应于的进程置入所有的对应于si的等待的等待该信号的进程队列中。
该信号的进程队列中 endif; •ssignal(s1,s2,...ssignal(s1,s2,...snsn) ) for i=1 to n do for i=1 to n do sisi:=si+1;:=si+1; 将与将与sisi有关的进程插入到就绪队列有关的进程插入到就绪队列中 endforendfor 72 4、信号量集、信号量集•在记录型信号量中，在记录型信号量中，P和和V仅执行减仅执行减1和和增增1操作，当一次需要操作，当一次需要N个某类资源时则个某类资源时则要进行要进行N次次P操作，其效率低下，此外在操作，其效率低下，此外在某些情况下当资源数低于某一下限值便某些情况下当资源数低于某一下限值便不分配，在每次分配之前，必须测试该不分配，在每次分配之前，必须测试该资源总数是否大于下限值，下面是对资源总数是否大于下限值，下面是对AND信号量机制的改写：信号量机制的改写：73 •si：资源总数，：资源总数， t ti: 下限值，下限值， di: 所需的资源所需的资源数数 •swait(s1,t1,d1swait(s1,t1,d1;...sn,t tn,dn)if s1>=t t1 and ... sn>=t tn t then for i=1 to n do si=si-di; endfor;else 将调用将调用swaitswait的进程插入到相应的的进程插入到相应的si的等待队列的等待队列中中;74 •ssignalsignal(s1,d1;...sn,dn)for i=1 to n do si=si+di; 将对应于将对应于si的所有进程唤醒到就绪队列的所有进程唤醒到就绪队列中中;endfor; 75 •swait(s,d,d)：此时信号量集中仅有一：此时信号量集中仅有一个信号量，允许每次申请个信号量，允许每次申请d个资源，当少个资源，当少于于d时不分配。
时不分配•swait(s,1,1)：为一般的记录型信号量：为一般的记录型信号量或互斥信号量或互斥信号量(s=1)•swait(s,1,0)：： 当当s>=1时允许多个进程时允许多个进程进入，当进入，当s=0时阻止任何进程进入时阻止任何进程进入76 2.3.3信号量的应用信号量的应用1 ) 利用信号量实现进程互斥利用信号量实现进程互斥设有设有2个并发进程个并发进程P0和和P1互斥共享互斥共享counter变量77 •begin count :integer := 0; s :semaphore := 1;• process Pin process Pout r1 :integer r2 :integer; begin begin p(s); p(s); r1 :=count; r2 :=count; r1 :=r1+1; r2 :=r2-1; count :=r1; count :=r2; v(s); v(s) end; end;coend;end;78 2））PV操作实现前趋图操作实现前趋图79 •定义：定义：• var a,b,c,d,e,f,g :signal :=0,0,0,0,0,0,0•process s1 process s2 process s3 s1; P(a); P(b); V(a); s2; s3; V(b); V(c); V(e); end; V(d); end; end;process s4 process s5 process s6 P(c); P(d); P(e); s4; s5; P(f); V(f); V(g); P(g); end; end; s6 end80 •【【例例1】】桌上有一空盘，允许存放一只水桌上有一空盘，允许存放一只水果。
爸爸可向盘中放苹果，也可向盘中果爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果规定当盘空时一次专等吃盘中的苹果规定当盘空时一次只能放一只水果供吃者取用，请用只能放一只水果供吃者取用，请用P、、V原语实现爸爸、儿子、女儿三个并发进原语实现爸爸、儿子、女儿三个并发进程的同步程的同步81 •解：在本题中，应设置三个信号量解：在本题中，应设置三个信号量S、、So、、Sa，信号量，信号量S表示盘子是否为空，表示盘子是否为空，其初值为其初值为l；信号量；信号量So表示盘中是否有桔表示盘中是否有桔子，其初值为子，其初值为0；信号量；信号量Sa表示盘中是表示盘中是否有苹果，其初值为否有苹果，其初值为0同步描述如下：同步描述如下： 82 •int S＝＝1;•int Sa＝＝0;•int So＝＝0;• main()• {• cobegin• father(); /*父亲进程父亲进程*/• son(); /*儿子进程儿子进程*/• daughter(); /*女儿进程女儿进程*/• coend• ｝｝83 •father()• {• while(1)• {• P(S);• 将水果放入盘中将水果放入盘中;• if（放入的是桔子）（放入的是桔子）V(So);• else V(Sa);• }• }84 • son()• {• while(1)• {• P(So);• 从盘中取出桔子从盘中取出桔子;• V(S);• 吃桔子吃桔子;• ｝｝• }85 • daughter()• {• while(1)• {• P(Sa);• 从盘中取出苹果从盘中取出苹果;• V(S);• 吃苹果吃苹果;• ｝｝•｝｝86 •三个进程P1、P2、P3互斥使用一个包含N（N>0)个单元的缓冲区。
P1每次使用produce()生成一个正整数，并用put()送入缓冲区的某一个单元中；P2每次用getodd()从该缓冲区中取走一个奇数，并用countodd()统计奇数的个数；P3每次用geteven()从该缓冲区中取走一个偶数，并用counteven()统计偶数的个数请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义，要求用伪代码描述思考题思考题187 88 思考题思考题2•四个进程四个进程A、、B、、C、、D都要读一个共享文件都要读一个共享文件F，系统允许多个进程同时读文件，系统允许多个进程同时读文件F但限制是但限制是进程进程A和进程和进程C不能同时读文件不能同时读文件F，进程，进程B和进和进程程D也不能同时读文件也不能同时读文件F为了使这四个进程为了使这四个进程并发执行时能按系统要求使用文件，现用并发执行时能按系统要求使用文件，现用PV操作进行管理，请回答下面的问题：操作进行管理，请回答下面的问题：89 •1）应定义的信号量及初值：）应定义的信号量及初值： •2）在下列的程序中填上适当的）在下列的程序中填上适当的P、、V操作，以保证操作，以保证它们能正确并发工作：它们能正确并发工作：• A() B() C() D()• { { { {• [1]; [3]; [5]; [7];• read F; read F; read F; read F;• [2]; [4]; [6]; [8];• } } } } 90 思考题解答：• （（1）定义二个信号量）定义二个信号量S1、、S2，初值均为，初值均为1，即：，即：S1=1，，S2=1。
其中进程其中进程A和和C使使用信号量用信号量S1，进程，进程B和和D使用信号量使用信号量S2•（（2）从）从[1]到到[8]分别为：分别为：P(S1) V(S1) P(S2) V(S2) P(S1) V(S1) P(S2) V(S2) 91 内容回顾内容回顾•什么是进程同步？什么是进程同步？•什么是临界资源和临界区？什么是临界资源和临界区？•进程同步遵循的规则？进程同步遵循的规则？•几种常见的信号量机制？几种常见的信号量机制？92 2.3.4 管程管理管程管理•对于信号量机制，每个访问临界资源的进程自对于信号量机制，每个访问临界资源的进程自备备PV操作，给系统管理带来了麻烦，而且容操作，给系统管理带来了麻烦，而且容易出现死锁易出现死锁•共享变量分部到各程序中，使程序易读性差共享变量分部到各程序中，使程序易读性差•正确性难以保证正确性难以保证93 1 管程的基本概念管程的基本概念•为了更易于编写正确的程序，为了更易于编写正确的程序，Hoare和和Brinch Hansan提出了一种高级的同步提出了一种高级的同步原语，称为原语，称为管程管程(monitor) 94 •基本思想：将共享资源用共享数据结构表示，用基本思想：将共享资源用共享数据结构表示，用对数据结构操作的一组过程表示资源管理程序，对数据结构操作的一组过程表示资源管理程序， 将共享数据结构和对它们的操作集中在一个模块将共享数据结构和对它们的操作集中在一个模块中形成管程。
中形成管程•一个管程定义了一个数据结构和能为并发进程所一个管程定义了一个数据结构和能为并发进程所执行在该数据结构上的一组操作，这组操作能同执行在该数据结构上的一组操作，这组操作能同步进程和改变管程中的数据步进程和改变管程中的数据95 •管程由四部分组成：管程由四部分组成：Ø①①管程名称管程名称Ø②②局部于管程内部的共享数据结构的说明；局部于管程内部的共享数据结构的说明；Ø③③对该数据结构进行操作的一组过程；对该数据结构进行操作的一组过程；Ø④④对局部于管程内部的数据设置初始值的语句对局部于管程内部的数据设置初始值的语句96 •管程作为一个模块，它的定义如下：管程作为一个模块，它的定义如下： Ømonitor_name = MoNITOR; Ø共享变量说明共享变量说明; Ø可调用的函数名表可调用的函数名表; Ø 内部定义的函数说明和函数体内部定义的函数说明和函数体 { 共享变量初始化语句共享变量初始化语句; } 97 2 管程的语法如下：管程的语法如下：• type monitor-name=monitor• variable declarations；；• procedure entry P1(…);• begin … end;• procedure entry P2(…);• begin … end;• …• procedure entry Pn(…);• begin … end;• begin• initialization code;• end 98 99 •在管程入口有一个等待队列，称为入口在管程入口有一个等待队列，称为入口等待队列（条件不忙队列）等待队列（条件不忙队列） •在管程内部，由于执行唤醒操作，可能在管程内部，由于执行唤醒操作，可能存在多个等待进程（等待使用管程），存在多个等待进程（等待使用管程），称为紧急等待队列（进入队列），它的称为紧急等待队列（进入队列），它的优先级高于入口等待队列。
优先级高于入口等待队列 100 101 3 管程主要有以下特性：管程主要有以下特性：（（1）模块化2）抽象数据类型抽象数据类型3）信息掩蔽信息掩蔽4）互斥使用互斥使用5）有进程等待队列和相应的等待和唤醒操作）有进程等待队列和相应的等待和唤醒操作 102 4 管程的使用过程管程的使用过程•一个进程进入管程之前要先申请，一般一个进程进入管程之前要先申请，一般由管程提供一个由管程提供一个enter过程；离开时释放过程；离开时释放使用权，如果紧急等待队列不空，则唤使用权，如果紧急等待队列不空，则唤醒第一个等待者，一般也由管程提供外醒第一个等待者，一般也由管程提供外部过程部过程leave 103 实现管程的三个关键问题实现管程的三个关键问题•（（1）互斥：）互斥：•（（2）同步：）同步：•（（3）条件变量：当调用管程的进程无法运）条件变量：当调用管程的进程无法运行时，用于阻塞进程的一种信号量在管行时，用于阻塞进程的一种信号量在管程内可执行程内可执行wait和和signal操作104 思考题思考题•管程与进程的不同？管程与进程的不同？105 例题：在一个分时操作系统中，进程可能出现如图所示的变化，请将每一种变化的具体原因写出来。
运 行等待数据资源就绪队列等待I/O传输（1）（5）（2）（4）（3）（6）106 107 108 t109 110 111 112 执执 行行活动就绪活动就绪活动阻塞活动阻塞静止就绪静止就绪静止阻塞静止阻塞进程调度进程调度时间片完时间片完请求请求I/OI/O完成完成挂起挂起激激 活活挂起挂起激激 活活某事件完成某事件完成.如如I/O113 114 115 116 117 118 119 。