OS 同步与互斥.ppt

第四讲 进程同步与互斥 为什么要引入进程？ 为了描述 程序在并发执行时对系统资源的共享 需要一个描述程序执行时动态特征的概念 并发 有效地提高了系统资源的利用率 但也带来了一些问题 内 容 一、进程间的联系 二、P、V操作 三、经典问题 四、进程间通信 一、进程间的联系 直接作用和间接作用 直接作用（同步）： 进程间的相互联系是有意识的安排的，直接作用只发生在相交进程间 间接作用（互斥，更重要些）： 进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间 有时需要同时使用二者！ 进程的同步（直接作用） 进程的同步 指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态 司机 P1 售票员 P2 while (true){ while (true){  启动车辆； 关门； 正常运行； 售票； 到站停车； 开门；} } 一个例子： 同步的例子非常多：网络视频播放、文件更新 进程的互斥（间接作用） 由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥 临界资源：critical resource 系统中某些资源一次只允许一个进程使用 这样的资源是临界资源或互斥资源或共享变量 互斥的例子也很多：共享打印机、火车票售票系统 临界区（互斥区） 一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作 临界区:在进程中涉及到临界资源的程序段 相关临界区:多个进程的临界区 a := a -1 print (a) a := a +1 print (a) P1 互斥 P2 互斥 If a 0 then a := a +1 else a:= a-1 P3 互斥 进程的互斥 （间接作用） 使用临界资源的原则 有空让进：当无进程在互斥区时，任何有权使用 互斥区的进程可进入 无空等待：不允许两个以上的进程同时进入互斥区 多中择一：当没有进程在临界区，而同时有多个进 程要求进入临界区，只能让其中之一进 入临界区，其他进程必须等待 有限等待：任何进入互斥区的要求应在有限的时间 内得到满足 让权等待：处于等待状态的进程应放弃占用CPU， 以使其他进程有机会得到CPU的使用权 前提：任何进程无权停止其它进程的运行 进程之间的相对运行速度无硬性规定 进程互斥的解决有两种做法: 由竞争各方平等协商（主动锁资源） 引入进程管理者，由管理者来协调竞争各方对互斥资源的使用（P、V操作） 软件解法 (1) Busy: 表示临界区当前状态的标志 true: 有进程在临界区 false:无进程在临界区(Busy的初值为 false)  …… while (Busy); Busy = true; 临界区 Busy = false; …… 软件解法 (2) turn: true P进入临界区 false Q进入临界区 P: …… while (turn); 临界区 turn = true; //? ……. Q: …… while (not turn); 临界区 turn = false; //? …… 前面介绍的各种算法都 提供了互斥的解决方式 是平等进程间的一种协商机制 但存在一些不足：应用程序显式控制临界资源的状态 编程复杂（代码乱） 检测开销大（每个进程不断检测） 需要一个地位高于进程的管理者来解决资源使用问题 操作系统可从进程管理者的角度来处理互斥的问题 信号量就是操作系统提供的管理公有资源的有效手段 二、P、V操作 P、V操作 1965年，由荷兰学者Dijkstra提出 P、V分别是荷兰语的 Test( Proberen)和Increment( Verhogen) P、V操作一种卓有成效的进程互斥/同步机制 最初提出的是二元信号量 推广到一般信号量（多值） 信号量：semaphore 是一个数据结构