《22进程及进程通信XXXX.pdf》由会员分享,可在线阅读,更多相关《22进程及进程通信XXXX.pdf(63页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、内容 目录概要 总结练习 操作系统与进程通信-2.2进程及进程通信 B U PT 漆渊第2章目录概要 2.1 操作系统概述 2.2 进程及进程通信 2.3 线程 2.4 文件 2.5 操作系统网络服务 2.6 操作系统接口 B U PT 漆渊2.2节目录概要 2.2.1 进程的引入 进程概念及特点、进程与程序、进程控制块及进程映像、进程状态及状态变化 2.2.2 进程描述、进程状态及进程控制 创建原语、撤销原语、阻塞原语、唤醒原语 2.2.3 进程控制 互斥、同步概念与同步问题 2.2.4 并发进程的相互制约同步与互斥 整型信号量、记录型信号量 利用信号量实现进程互斥、同步 2.2.5 信号量
2、机制 生产者-消费者问题 读者-写者问题 2.2.6经典的进程同步问题 共享内存模式 消息传递模式 2.2.7进程通信 B U PT 漆渊2.2.1进程的引入 批处理-作业 分时系统-用户程序或任务 程序 如何描述所有这些CPU的活动?单道程序 只允许一次执行一个程序 程序对系统有完全的控制权,能访问所有的系统资源 多道程序 多个程序可以同时存在于内存 共享系统的所有资源 B U PT 漆渊2.2.1进程的引入 单道程序 顺序性:处理机的操作严格按照程序所规定的顺序执行 封闭性:程序运行的环境资源只能由程序本身访问和修改 可再现性:只要它的运行条件(初始数据)相同,其运行结果一定相同 多道程序
3、 间断性:各程序在执行时间上是重叠的,相互制约 失去封闭性:一个程序的环境可能会受其它程序影响 不可再现性:并发程序的运行结果不确定 B U PT 漆渊2.2.1进程的引入 不确定性的示例 假设一个火车订票系统程序,其中读取某车次车票余额并售出车票的程序片段为ticketP,现在两个窗口T1和T2并发执行这段程序,两个并发程序必须共享某车次的剩余车票数的变量tNum ticketP /从共享文件中读取车票数tNum Read(tNum);/如果还有余票,则售出,票数减1,假设每次只能售一张,否则票数不变,返回 if tNum=1 then tNum-;else return(-1);/车票数据
4、写回共享文件 Write(tNum);B U PT 漆渊2.2.1进程的引入 0 运行环境的非封闭性、结果不可再现性、间断性 B U PT 漆渊2.2节目录概要 2.2.1 进程的引入 进程概念及特点、进程与程序、进程控制块及进程映像、进程状态及状态变化 2.2.2 进程描述、进程状态及进程控制 创建原语、撤销原语、阻塞原语、唤醒原语 2.2.3 进程控制 互斥、同步概念与同步问题 2.2.4 并发进程的相互制约同步与互斥 整型信号量、记录型信号量 利用信号量实现进程互斥、同步 2.2.5 信号量机制 生产者-消费者问题 读者-写者问题 2.2.6经典的进程同步问题 共享内存模式 消息传递模式
5、 2.2.7进程通信 B U PT 漆渊2.2.2进程描述、进程状态及进程控制 进程概念及特点 CPU的并发活动 通过CPU在多个程序执行之间切换,伪并行多道程序设计 比较多处理机系统,真正硬件并行 进程 一个正在执行程序的实例,包括数据、程序计数器、寄存器和变量的当前值 进程 B U PT 漆渊2.2.2进程描述、进程状态及进程控制 进程概念及特点 不同的定义 进程是程序的一次执行 进程是一个程序及其数据在处理机上顺序执行时所发生的活动 进程是程序在一个数据集合上的运行过程,它是系统进行资源分配和调度的一个独立单位 可以与其它程序并行执行的程序的一次执行 允许将多个程序调入内存并发执行 要求
6、对各种程序提供更严格的控制和划分 现代计算机系统 一次执行一个程序;程序对系统有完全的控制,能访问所有的系统资源 早期计算机系统 进程 执行中的程序 现代分时系统的工作单元 B U PT 漆渊2.2.2进程描述、进程状态及进程控制 进程与程序 动态的 有生命过程,存在是暂时的 包括程序和数据、状态,可以顺序的执行多个程序 进程 静态的 存在是永久的 可以对应多个进程 程序 B U PT 漆渊2.2.2进程描述、进程状态及进程控制 进程概念及特点 进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位 进程实体:进程映像,由程序、数据以及描述进程状态的数据结构组成的 进程的特征 动态性
7、 并发性 独立性 异步性 进程控制块 B U PT 漆渊2.2.2进程描述、进程状态及进程控制 进程控制块及进程映像 进程控制块PCB(Process Control Block)描述活动状态,包含内容:包含了进程的描述信息和控制信息 唯一标识进程存在的数据结构 使一个在多道程序环境下不能独立运行的程序(含数据),成为一个能独立运行的基本单位,一个能与其他进程并发执行的进程 进程标识符 进程状态信息 进程执行现场信息 进程调度信息 进程控制信息 B U PT 漆渊2.2.2进程描述、进程状态及进程控制 进程映像 进程的实体即进程映像,是由程序、数据和进程控制块组成的 进程 程序 数据 进程控制
8、块 描述了进程所要完成的功能 进程在执行时的操作对象 进程存在的物理标志和体现 B U PT 漆渊2.2.2进程描述、进程状态及进程控制 进程状态及状态变化 运行状态(Running):一个进程已获得处理机,正在执行。就绪状态(Ready):一个进程得到了除CPU以外的所有必要资源,一旦得到处理机就可以运行,又称为逻辑可运行状态。阻塞状态(Blocked):一个进程因等待某事件发生(如申请打印机,打印机忙)而暂时无法继续执行,从而放弃处理机,使进程执行处于暂停状态,又称为逻辑不可运行状态 e.g:计算进程|打印进程 注意:就绪、阻塞的区别!B U PT 漆渊2.2.2进程描述、进程状态及进程控
9、制 进程状态及状态变化 B U PT 漆渊2.2.2进程描述、进程状态及进程控制 进程实现 OS是根据PCB来对并发执行的进程进行控制和管理的 B U PT 漆渊2.2.2进程描述、进程状态及进程控制 进程实现 进程调度选择一个可用的进程到CPU上执行 进程在不同的队列之间移动 驻留在内存中就绪的、等待运行的进程保存在就绪队列中 等待特定I/O设备的进程列表称为设备队列 B U PT 漆渊2.2节目录概要 2.2.1 进程的引入 进程概念及特点、进程与程序、进程控制块及进程映像、进程状态及状态变化 2.2.2 进程描述、进程状态及进程控制 创建原语、撤销原语、阻塞原语、唤醒原语 2.2.3 进
10、程控制 互斥、同步概念与同步问题 2.2.4 并发进程的相互制约同步与互斥 整型信号量、记录型信号量 利用信号量实现进程互斥、同步 2.2.5 信号量机制 生产者-消费者问题 读者-写者问题 2.2.6经典的进程同步问题 共享内存模式 消息传递模式 2.2.7进程通信 B U PT 漆渊2.2.3进程控制 进程控制机构 进程的状态变化是由系统的进程控制机构完成的 具有创建进程、撤销进程和实施进程间同步、通信等功能 包含在操作系统的内核里 原语 OS内核中由若干条指令构成,用于完成特定功能的一个过程,该过程在执行时是不可中断的 控制进程的原语:创建原语、撤销原语、阻塞原语、唤醒原语等 现代OS广
11、泛采用层次式结构,通常将一些与硬件密切相关的模块,以及运行频率较高的模块安排在紧靠硬件的软件层次中,并将它们常驻内存,以提高OS的运行效率,并对它们加以特殊的保护 B U PT 漆渊2.2.3进程控制 创建原语 创建一个新进程 有四类事件会导致创建一个进程 进程树 系统初始化 正在运行的进程创建 用户请求创建 批处理作业初始化 根进程 子进程 父进程 B U PT 漆渊2.2.3进程控制 创建原语 主要工作:为被创建进程建立一个进程控制块PCB,分配进程标识符,形成PCB 申请空白PCB 为新进程分配资源 初始化进程控制块 将新进程插入就绪队列 B U PT 漆渊2.2.3进程控制 撤销原语
12、撤销或终止一个进程 系统可以按照进程标识符撤销一个进程,也可以按照优先级撤销多个进程 撤销进程一般由父进程或祖先进程发出,给出的参数是进程标识符或优先级。如果一个进程被撤销,那么它的子孙进程必须先行撤销。正常退出(自愿)出错退出(自愿)严重错误(非自愿)被其他进程杀死(非自愿)B U PT 漆渊2.2.3进程控制 撤销原语 主要工作:将被撤销进程及其子孙进程的所有资源(主存、外设、PCB)全部收回,归还系统 根据被终止进程的标识符,从PCB集合中检索出该进程的PCB,从中读出该进程的状态 若被终止进程正处于执行状态,应立即终止该进程的执行,并置调度标志为真,用于指示该进程被终止后应重新进行调度
13、 若该进程还有子进程,还应将其所有子进程予以终止,以防他们成为不可控的进程 将被终止进程所拥有的全部资源,或者归还给其父进程,或者归还给系统 将被终止进程(它的PCB)从所在队列(或链表)中移出,等待其他程序来搜集信息 B U PT 漆渊2.2.3进程控制 阻塞原语 当一个进程期待某一事件(如请求系统服务、启动某种操作、数据尚未到达、无新工作可做等)出现时,该进程就调用阻塞原语将自己置为阻塞(等待)状态 主要工作是保存阻塞进程的现场,让出处理机 调用阻塞原语把自己阻塞 停止进程的执行,修改PCB中的状态信息,并将其插入相应的阻塞队列 转处理机调度程序,选择一个进程运行 B U PT 漆渊2.2
14、.3进程控制 唤醒原语 当处于阻塞状态的进程所等待的事件出现时,由发现者进程调用唤醒原语唤醒该阻塞进程 引起唤醒的事件与引起阻塞的事件是相对应的 唤醒原语的主要工作是将阻塞进程从阻塞队列移到就绪队列 将该阻塞进程的进程控制块PCB从阻塞队列中移出 修改PCB中的状态信息 再将其插入到就绪进程队列 B U PT 漆渊2.2节目录概要 2.2.1 进程的引入 进程概念及特点、进程与程序、进程控制块及进程映像、进程状态及状态变化 2.2.2 进程描述、进程状态及进程控制 创建原语、撤销原语、阻塞原语、唤醒原语 2.2.3 进程控制 互斥、同步概念与同步问题 2.2.4 并发进程的相互制约同步与互斥
15、整型信号量、记录型信号量 利用信号量实现进程互斥、同步 2.2.5 信号量机制 生产者-消费者问题 读者-写者问题 2.2.6经典的进程同步问题 共享内存模式 消息传递模式 2.2.7进程通信 B U PT 漆渊2.2.4 同步与互斥 并发的进程 独立性:各进程都可以独立向前推进 制约性:进程之间有时会相互制约 直接制约 源于进程间的合作 异步环境下的并发进程,各自的执行结果互为对方的执行条件,从而限制各进程的执行速度的过程 同步 间接制约 源于进程对资源的共享和争用 由共享公有资源而造成的对并发进程执行速度的制约 一旦将这个竞争资源分配给一个进程,其它进程就必须等待,直到前者完成任务释放资源
16、为止 互斥 B U PT 漆渊2.2.4 同步与互斥 并发的进程 间接制约示例 设想假脱机目录中有许多槽位,编号依次为1,2,每个槽位存放一个文件名 假设有两个共享变量:out,指向下一个要打印的文件;In,指向目录中下一个空闲槽位 操作系统要有进程间的同步与互斥措施控制 局部变量 next_free_slot t0 A nfs_A=7 t1 B nfs_B=7 t2 B 加入队列,in=8 t3 A 加入队列,in=8 B要打印的被覆盖!B U PT 漆渊2.2.4 同步与互斥 互斥 竞争资源的进程首先面临的是互斥的要求 某些资源由于其物理特性,一次只允许一个进程使用,不能多进程同时共享,我
17、们称其为临界资源 打印机、磁带机 物理设备 变量、数据、队列 软临界资源 避免与时间有关的错误 共享了变量 同时使用了这个变量 多个进程之间需要互斥使用临界资源 指在一个进程开始使用但尚未结束使用的期间,另一个进程也开始了使用 B U PT 漆渊2.2.4 同步与互斥 互斥 访问临界资源的程序段称为临界区CS(Critical Section)其它程序段统称为非临界区non_CS 把与同一个临界资源相关联的临界区称为同类临界区 互斥使用临界资源的问题 控制不允许进程同时进入各自的同类临界区 B U PT 漆渊2.2.4 同步与互斥 互斥 使用临界区的基本要求 互斥进入:只允许一个进程访问该临界
18、资源 不互相阻塞:如果有若干进程都要求进入临界区,必须在有限时间内允许一个进程进入,不应互相阻塞,以至于哪个进程都无法进入 公平性:进入临界区的进程要在有限时间内退出,不让等待者无限等待 Repeat Non_CS;临界区入口控制代码CS-inCode;CS;临界区出口控制代码CS-outCode;Until false B U PT 漆渊2.2.4 同步与互斥 同步概念与同步问题 同步(synchronism)是指有协作关系的进程之间需要调整它们之间的相对速度 计算进程 当上一次计算结果还在缓冲区未被打印时,Computing进程不能向其中送入新的计算结果,计算进程必须等待 单缓冲区 打印进
19、程 当计算结果未出来前,Printer进程必须等待 互斥也是一种特殊的同步,而同步时共享的资源(缓冲区)也是临界资源,因此有时我们将同步和互斥面临的问题统称为同步问题 B U PT 漆渊2.2.4 同步与互斥 同步机制都应遵循下述四条准则 空闲让进:当无进程进入临界区,应允许一个请求进入临界区的进程立即进入临界区 忙则等待:当已有进程进入临界区,其它请求进入临界区的进程必须等待,以保证对临界资源的互斥访问 有限等待:对请求进入临界区的进程,应保证在有限时间内能够进入临界区,避免“死等”让权等待:当进程不能进入自己的临界区时,应立即释放已占用资源,以免产生死锁 B U PT 漆渊2.2节目录概要
20、 2.2.1 进程的引入 进程概念及特点、进程与程序、进程控制块及进程映像、进程状态及状态变化 2.2.2 进程描述、进程状态及进程控制 创建原语、撤销原语、阻塞原语、唤醒原语 2.2.3 进程控制 互斥、同步概念与同步问题 2.2.4 并发进程的相互制约同步与互斥 整型信号量、记录型信号量 利用信号量实现进程互斥、同步 2.2.5 信号量机制 生产者-消费者问题 读者-写者问题 2.2.6经典的进程同步问题 共享内存模式 消息传递模式 2.2.7进程通信 B U PT 漆渊2.2.5 信号量机制 信号量机制 1965年荷兰学者Dijkstra 是现代操作系统在进程之间实现互斥与同步的基本工具
21、 基本原理是:两个或多个进程可以通过简单的信号进行合作,一个进程可以被迫在某一位置停止,直到它接收到一个特定的信号 信号量 为了发信号,需要使用一个特殊变量,即信号量。是一个数据结构,它由一个信号量变量以及对该变量进行的原语操作组成 操作系统利用信号量实现进程同步与互斥的机制称为信号量机制 B U PT 漆渊2.2.5 信号量机制 整型信号量 信号量变量定义为整数值变量 定义三个操作 一个信号量可以初始化成非负整数 原语操作P(P操作):判断信号量值,如果为0,忙等待(判断等待),否则将信号量值减1;原语操作V(V操作):将信号量值加1 P、V操作的算法描述如下:P(S):While S=0
22、do no-op;S:=S-1;V(S):S:=S+1;出口控制代码 进入临界区的入口控制代码 临界区入口:P操作 临界区 临界区出口:V操作 B U PT 漆渊2.2.5 信号量机制 整型信号量 两个进程P1、P2共享临界资源CR,同类临界区为CS1、CS2 使用P、V操作作为CS1、CS2的入口和出口控制码,二者共享信号量mutex P(S):While S=0 do no-op;S:=S-1;V(S):S:=S+1;B U PT 漆渊2.2.5 信号量机制 整型信号量 t0 t1 t2 t3 t4 t5 t5 进程P1执行 P操作:判 断 mutex值为1;mutex-;进入临界区 临
23、界 区 工作,访 问临界资源 退 出 临 界区;执行V操作mutex+;进程P2执行 P操作:判断 mutex值为0;在P操作中等待 P操作:判断 mutex值为1;mutex-进 入 临 界区 临 界 区 工作,访 问临界资源 退 出 临 界区;执 行 V 操作:mutex+;P、V操作的算法描述如下:P(S):While S=0 do no-op;S:=S-1;V(S):S:=S+1;先执行P操作的进程将信号量减1,进入临界区;后执行P操作的进程判断信号量时已经为0,只能不断检查信号量值,等待在P操作中,直到进入临界区的进程,退出临界区,执行V操作,将信号量值加1,等待的进程此时判断信号量
24、值为1,将其减1,进入临界区 B U PT 漆渊2.2.5 信号量机制 记录型信号量 避免执行语句while浪费处理机资源记录型信号量机制 除了一个整数变量外,还加了一个指针队列,用以记录阻塞进程 Struct Semaphore int value;List_of_process L;S;Wait(S)S.value-;if S.value0 then block(S,L);Signal(S)S.value+;if S.value0 then wakeup(S,L);阻塞原语,调用此原语的进程挂在(阻塞在)L队列中,等待资源为S的信号量 唤醒原语,wakeup(S,L)是将因等待S信号量的、
25、挂在(阻塞在)L队列中的进程唤醒 临界区入口:wait操作 临界区 临界区出口:signal操作 B U PT 漆渊2.2.5 信号量机制 记录型信号量的几点说明 设置的信号量初值,一定是一个非负的整数进程状态转移相关 定义在信号量上的P(wait)操作和V(signal)操作,都由两个不可分割的动作组成 调用wait的进程 如果对信号量当前值减1后,信号量值大于等于0,则该进程继续运行下去 否则它就被阻塞,直到有别的进程通过做signal(S)来唤醒它 调用signal的进程 状态不会改变 Wait(S)S.value-;if S.value0 then block(S,L);Signal(
26、S)S.value+;if S.value0 then wakeup(S,L);B U PT 漆渊2.2.5 信号量机制 利用信号量实现进程互斥 使用信号量互斥访问临界资源,需要设置一个互斥信号量,其初值必须为1 以Wait操作作为临界区入口控制码,Signal操作作为临界区出口控制码 Wait(S)S.value-;if S.value0 then block(S,L);Signal(S)S.value+;if S.value0 then wakeup(S,L);B U PT 漆渊2.2.5 信号量机制 利用信号量实现进程互斥 t0 t1 t2 t3 t4 t5 进程P1 执行 wait操作
27、:判 断 mutex 值为1;mutex-;进入临界区 临界区工作CS1,访 问临界资源 退出临界区执 行 signal操作:mutex+mutex=0 唤醒 进程P2 执行 wait操作:判 断 mutex值为0;mutex-;阻塞 临界区工作CS2,访问临界资源 退出临界区执 行 signal操作:mutex+Wait(S)S.value-;if S.value0 then block(S,L);mutex初值为1 Signal(S)S.value+;if S.value0 then wakeup(S,L);B U PT 漆渊2.2.5 信号量机制 利用信号量实现进程同步 设计一个同步方案
28、解决计算进程与打印进程的同步 计算进程 单缓冲区 打印进程 二者的同步关系是,计算进程先执行,有了计算结果才可以打印 计算进程为C,计算语句为c1 打印进程为P,打印语句为p1 B U PT 漆渊2.2.5 信号量机制 利用信号量实现进程同步 如何实现?一旦打印进程先于计算进程获得处理机,会发生什么?值得注意的是,Wait操作和Signal操作使用不当,仍然会出现与时间有关的错误 同步信号量sm初值设置为0 Wait(S)S.value-;if S.value0 then block(S,L);Signal(S)S.value+;if S.value0 then wakeup(S,L);B U
29、 PT 漆渊2.2节目录概要 2.2.1 进程的引入 进程概念及特点、进程与程序、进程控制块及进程映像、进程状态及状态变化 2.2.2 进程描述、进程状态及进程控制 创建原语、撤销原语、阻塞原语、唤醒原语 2.2.3 进程控制 互斥、同步概念与同步问题 2.2.4 并发进程的相互制约同步与互斥 整型信号量、记录型信号量 利用信号量实现进程互斥、同步 2.2.5 信号量机制 生产者-消费者问题 读者-写者问题 2.2.6经典的进程同步问题 共享内存模式 消息传递模式 2.2.7进程通信 B U PT 漆渊2.2.6经典的进程同步问题 生产者-消费者问题 代表两类对象共享资源,间接制约的关系 问题
30、描述与分析 一组生产者和一组消费者,通过一个有界的缓冲池进行通信 生产者不断(循环)将产品送入缓冲池,消费者不断(循环)从中取用产品 互斥问题:存在于所有进程之间 同步问题:存在于两类进程之间 若缓冲池满(供过于求),则生产者不能将产品送入,必须等待消费者取出产品;若缓冲池已空(供不应求),则消费者不能取得产品,必须等待生产者送入产品。B U PT 漆渊2.2.6经典的进程同步问题 生产者-消费者问题 设计信号量 同步问题 产品多少(货)缓冲池大小(坑)生产、消费者执行顺序 同步信号量 满缓冲数量:full(0)空缓冲数量:empty(n)互斥问题 缓冲池 只有一种临界资源 互斥信号量 mut
31、ex 初值一定为1 设置信号量的关键:找到使进程状态变化的量 初始:没货,full=0,消费者状态阻塞 初始有n个坑,直到没坑,empty=0,生产者状态阻塞 B U PT 漆渊消费者进程临界区出口 消费者进程临界区 消费者进程临界区入口 2.2.6经典的进程同步问题 生产者-消费者问题 并发进程的行为 生产者进程临界区出口 生产者进程临界区 生产者进程临界区入口 判断缓冲是否满 判断缓冲是否被用 标记退出缓冲(唤醒使用缓冲的进程)标记存放(唤醒取产品的进程)阻塞(等待有坑)阻塞(等待挪地)判断缓冲是否空 阻塞(等待有货)判断缓冲是否被用 阻塞(等待挪地)标记退出缓冲(唤醒使用缓冲的进程)标记
32、取走(唤醒生产的进程)Yes Yes Yes Yes 取产品 存产品 B U PT 漆渊2.2.6经典的进程同步问题 生产者-消费者问题 入口出口控制代码设计 生产者 消费者 判断 是否有坑 是否有人占坑 是否有货 是否有人占坑 尝试信号量 empty mutex full mutex 阻塞原因 等待有坑、取货事件(消费者)等待挪地儿(占坑者)等待有货、送货事件(生产者)等待挪地儿(占坑者)阻塞位置 empty的阻塞队列上 Mutex的阻塞队列上 Full的阻塞队列上 Mutex的阻塞队列上 唤醒 消费者取货,操作empty 占坑者出来操作mutex 生产者送货,操作full 占坑者出来操作m
33、utex 谁导致了进程状态变化?B U PT 漆渊2.2.6经典的进程同步问题 生产者-消费者问题 producer:begin repeat /非临界区 生产产品;Wait(empty);Wait(mutex);/临界区,存放产品 buffer(in):=nextp;in:=(in+1)mod n;Signal(mutex);Signal(full);until false;end 生产者进程临界区入口 生产者进程临界区出口 想看看有坑没?有坑,那么有人在用缓冲池吗?不用缓冲池了,要用的醒醒!已存货,坑又少了一个,取货的醒醒!临界资源 缓冲池 Wait(S)S.value-;if S.val
34、ue0 then block(S,L);Signal(S)S.value+;if S.value0 then wakeup(S,L);B U PT 漆渊2.2.6经典的进程同步问题 生产者-消费者问题 consumer:begin repeat Wait(full);Wait(mutex);/临界区,取产品 nextc:=buffer(out);out:=(out+1)mod n;Signal(mutex);Signal(empty);/非临界区 消费产品;until false;end 消费者进程临界区入口 消费者进程临界区出口 想看看有货没?有货,那么有人在用缓冲池吗?不用缓冲池了,要用的
35、醒醒!已取货,货又少了一个,存货的醒醒!Wait(S)S.value-;if S.value0 then block(S,L);Signal(S)S.value+;if S.value0 then wakeup(S,L);B U PT 漆渊2.2.6经典的进程同步问题 生产者-消费者问题 设producer为生产者,consumer为消费者,数组buffer表示一个环形缓冲池,in为缓冲池存放产品的指针,out为缓冲池取产品的指针,nextp代表生产的产品,nextc代表消费的产品 Wait(mutex);Wait(empty);Wait(mutex);Wait(full);B U PT 漆渊
36、2.2.6经典的进程同步问题 读者-写者问题 多个并发进程共享一个数据对象(如数据库或文件),这些进程中有的只想读共享数据,而其它一些进程可能要更新(即读和写)共享数据 问题描述与分析:保证一个Writer进程必须与其它进程互斥地访问共享对象的问题 允许多个进程同时读一个共享对象 不允许一个Writer进程和其它Reader进程或Writer进程同时访问共享对象 互斥问题 B U PT 漆渊2.2.6经典的进程同步问题 读者-写者问题 设计信号量 互斥问题 访问的数据对象 多个读进程计数 读写进程的互斥 两种种临界资源 互斥信号量wmutex 初值为1 整数变量ReaderCount 初值为0
37、 变化由Reader进程进出临界区时加1或减1 互斥信号量Rcmutex 初值为1 注意引起进程状态变化的量 读写进程共享 读进程共享 不允许一个Writer进程和其它Reader进程或Writer进程同时访问共享对象 允许多个读进程共享对象 B U PT 漆渊2.2.6经典的进程同步问题 读者-写者问题 并发进程的行为 Reader进程临界区出口 Reader进程临界区 Reader进程临界区入口 判断是否有Reader进程在访问数据对象 判断是否有Writer进程在访问数据对象,与Writer进程互斥访问数据对象 判断是否还有Reader进程在访问数据对象 Writer进程临界区出口 Wr
38、iter进程临界区 Writer进程临界区入口 退出临界区 No(可能有Writer进程)Yes No(唤醒Writer进程)Yes wmutex RCmutex B U PT 漆渊2.2.6经典的进程同步问题 读者-写者问题 设计入口出口 读者 写者 判断 是否有人访问RC 读RC,判断是否有人读(是否能读数据),如果没有,是否有人写 是否有人访问共享数据 尝试信号量 RCmutex wmutex wmutex 阻塞原因 等待修改RC事件(读者)等待写完(写者)等待写完(写者)阻塞位置 RCmutex 的阻塞队列上 wmutex的阻塞队列上 wmutex的阻塞队列上 唤醒 读者更新RC,操作
39、RCmutex 写者出来操作wmutex 写者出来操作wmutex B U PT 漆渊2.2.6经典的进程同步问题 Reader:begin repeat /非临界区 ;Wait(RCmutex);/访问ReaderCount临界区 if ReaderCount=0 then Wait(wmutex);ReaderCount+;Signal(RCmutex);读数据对象;Wait(RCmutex);/访问ReaderCount临界区 ReaderCount-;if ReaderCount=0 then Signal(wmutex);Signal(RCmutex);until false;end
40、 Reader进程临界区入口(嵌套临界区)Reader进程临界区出口(嵌套临界区)想看看有多少人看,想加我一个 没人看?小心有人写 有人看?我也去看,加上我 我知道有多少人看了,还包括我哦 临界资源 现在有*个人在看数据 数据*看完了,还有多少人啊,把我删了吧 除了我没人了?看看要写的家伙睡醒没?我知道还有多少人在看,不包括我 Wait(S)S.value-;if S.value0 then block(S,L);Signal(S)S.value+;if S.value0 then wakeup(S,L);B U PT 漆渊2.2.6经典的进程同步问题 读者-写者问题 B U PT 漆渊2.2
41、节目录概要 2.2.1 进程的引入 进程概念及特点、进程与程序、进程控制块及进程映像、进程状态及状态变化 2.2.2 进程描述、进程状态及进程控制 创建原语、撤销原语、阻塞原语、唤醒原语 2.2.3 进程控制 互斥、同步概念与同步问题 2.2.4 并发进程的相互制约同步与互斥 整型信号量、记录型信号量 利用信号量实现进程互斥、同步 2.2.5 信号量机制 生产者-消费者问题 读者-写者问题 2.2.6经典的进程同步问题 共享内存模式 消息传递模式 2.2.7进程通信 B U PT 漆渊2.2.7进程通信 进程通信 并发进程之间相互交换信息 进程的同步和互斥就是一种进程通信 两种基本模式 速度比消息传递要快 用于进程间交换数据较少的情况 B U PT 漆渊2.2.7进程通信 共享内存模式 需要通信进程建立共享内存区域 协作进程通过在共享区域内读或写来交换数据,在使用共享区域读操作或写操作时必须互斥 操作系统只提供共享存储空间,对共享区域的使用和进程间的互斥关系都由程序员来控制 生产者-消费者的协作问题可以利用共享内存模式来解决 消息传递模式 提供一种机制,使协作进程不必通过共享地址空间来进行信息交换 至少两种操作:发送消息和接收消息,都是原语操作 B U PT 漆渊练习&思考 选作题:哲学家就餐问题 建模对于互斥访问有限资源的竞争问题 哲学家:吃饭+思考 B U PT 漆渊
限制150内