22进程及进程通信XXXX.pdf

内容 目录概要 总结练习 操作系统与进程通信-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.6经典的进程同步问题 共享内存模式 消息传递模式 2.2.7进程通信 B U PT 漆渊2.2.1进程的引入 批处理-作业 分时系统-用户程序或任务 程序 如何描述所有这些CPU的活动？单道程序 只允许一次执行一个程序 程序对系统有完全的控制权，能访问所有的系统资源 多道程序 多个程序可以同时存在于内存 共享系统的所有资源 B U PT 漆渊2.2.1进程的引入 单道程序 顺序性：处理机的操作严格按照程序所规定的顺序执行 封闭性：程序运行的环境资源只能由程序本身访问和修改 可再现性：只要它的运行条件（初始数据）相同，其运行结果一定相同 多道程序 间断性：各程序在执行时间上是重叠的，相互制约 失去封闭性：一个程序的环境可能会受其它程序影响 不可再现性：并发程序的运行结果不确定 B U PT 漆渊2.2.1进程的引入 不确定性的示例 假设一个火车订票系统程序，其中读取某车次车票余额并售出车票的程序片段为ticketP，现在两个窗口T1和T2并发执行这段程序，两个并发程序必须共享某车次的剩余车票数的变量tNum ticketP /从共享文件中读取车票数tNum Read(tNum);/如果还有余票，则售出，票数减1，假设每次只能售一张，否则票数不变，返回 if tNum=1 then tNum-;else return(-1);/车票数据写回共享文件 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经典的进程同步问题 共享内存模式 消息传递模式 2.2.7进程通信 B U PT 漆渊2.2.2进程描述、进程状态及进程控制 进程概念及特点 CPU的并发活动 通过CPU在多个程序执行之间切换，伪并行多道程序设计 比较多处理机系统，真正硬件并行 进程 一个正在执行程序的实例，包括数据、程序计数器、寄存器和变量的当前值 进程 B U PT 漆渊2.2.2进程描述、进程状态及进程控制 进程概念及特点 不同的定义 进程是程序的一次执行 进程是一个程序及其数据在处理机上顺序执行时所发生的活动 进程是程序在一个数据集合上的运行过程，它是系统进行资源分配和调度的一个独立单位 可以与其它程序并行执行的程序的一次执行 允许将多个程序调入内存并发执行 要求对各种程序提供更严格的控制和划分 现代计算机系统 一次执行一个程序；程序对系统有完全的控制，能访问所有的系统资源 早期计算机系统 进程 执行中的程序 现代分时系统的工作单元 B U PT 漆渊2.2.2进程描述、进程状态及进程控制 进程与程序 动态的 有生命过程，存在是暂时的 包括程序和数据、状态，可以顺序的执行多个程序 进程 静态的 存在是永久的 可以对应多个进程 程序 B U PT 漆渊2.2.2进程描述、进程状态及进程控制 进程概念及特点 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位 进程实体：进程映像，由程序、数据以及描述进程状态的数据结构组成的 进程的特征 动态性 并发性 独立性 异步性 进程控制块 B U PT 漆渊2.2.2进程描述、进程状态及进程控制 进程控制块及进程映像 进程控制块PCB（Process Control Block）描述活动状态，包含内容：包含了进程的描述信息和控制信息 唯一标识进程存在的数据结构 使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程 进程标识符 进程状态信息 进程执行现场信息 进程调度信息 进程控制信息 B U PT 漆渊2.2.2进程描述、进程状态及进程控制 进程映像 进程的实体即进程映像，是由程序、数据和进程控制块组成的 进程 程序 数据 进程控制块 描述了进程所要完成的功能 进程在执行时的操作对象 进程存在的物理标志和体现 B U PT 漆渊2.2.2进程描述、进程状态及进程控制 进程状态及状态变化 运行状态（Running）：一个进程已获得处理机，正在执行。就绪状态（Ready）：一个进程得到了除CPU以外的所有必要资源，一旦得到处理机就可以运行，又称为逻辑可运行状态。阻塞状态（Blocked）：一个进程因等待某事件发生（如申请打印机，打印机忙）而暂时无法继续执行，从而放弃处理机，使进程执行处于暂停状态，又称为逻辑不可运行状态 e.g：计算进程|打印进程 注意：就绪、阻塞的区别！B U PT 漆渊2.2.2进程描述、进程状态及进程控制 进程状态及状态变化 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 进程控制 互斥、同步概念与同步问题 2.2.4 并发进程的相互制约同步与互斥 整型信号量、记录型信号量 利用信号量实现进程互斥、同步 2.2.5 信号量机制 生产者-消费者问题 读者-写者问题 2.2.6经典的进程同步问题 共享内存模式 消息传递模式 2.2.7进程通信 B U PT 漆渊2.2.3进程控制 进程控制机构 进程的状态变化是由系统的进程控制机构完成的 具有创建进程、撤销进程和实施进程间同步、通信等功能 包含在操作系统的内核里 原语 OS内核中由若干条指令构成，用于完成特定功能的一个过程，该过程在执行时是不可中断的 控制进程的原语：创建原语、撤销原语、阻塞原语、唤醒原语等 现代OS广泛采用层次式结构，通常将一些与硬件密切相关的模块，以及运行频率较高的模块安排在紧靠硬件的软件层次中，并将它们常驻内存，以提高OS的运行效率，并对它们加以特殊的保护 B U PT 漆渊2.2.3进程控制 创建原语 创建一个新进程 有四类事件会导致创建一个进程 进程树 系统初始化 正在运行的进程创建 用户请求创建 批处理作业初始化 根进程 子进程 父进程 B U PT 漆渊2.2.3进程控制 创建原语 主要工作：为被创建进程建立一个进程控制块PCB，分配进程标识符，形成PCB 申请空白PCB 为新进程分配资源 初始化进程控制块 将新进程插入就绪队列 B U PT 漆渊2.2.3进程控制 撤销原语 撤销或终止一个进程 系统可以按照进程标识符撤销一个进程，也可以按照优先级撤销多个进程 撤销进程一般由父进程或祖先进程发出，给出的参数是进程标识符或优先级。如果一个进程被撤销，那么它的子孙进程必须先行撤销。正常退出（自愿）出错退出（自愿）严重错误（非自愿）被其他进程杀死（非自愿）B U PT 漆渊2.2.3进程控制 撤销原语 主要工作：将被撤销进程及其子孙进程的所有资源（主存、外设、PCB）全部收回，归还系统 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度 若该进程还有子进程，还应将其所有子进程予以终止，以防他们成为不可控的进程 将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统 将被终止进程(它的PCB)从所在队列(或链表)中移出，等待其他程序来搜集信息 B U PT 漆渊2.2.3进程控制 阻塞原语 当一个进程期待某一事件（如请求系统服务、启动某种操作、数据尚未到达、无新工作可做等）出现时，该进程就调用阻塞原语将自己置为阻塞（等待）状态 主要工作是保存阻塞进程的现场，让出处理机 调用阻塞原语把自己阻塞 停止进程的执行，修改PCB中的状态信息，并将其插入相应的阻塞队列 转处理机调度程序，选择一个进程运行 B U PT 漆渊2.2.3进程控制 唤醒原语 当处于阻塞状态的进程所等待的事件出现时，由发现者进程调用唤醒原语唤醒该阻塞进程 引起唤醒的事件与引起阻塞的事件是相对应的 唤醒原语的主要工作是将阻塞进程从阻塞队列移到就绪队列 将该阻塞进程的进程控制块PCB从阻塞队列中移出 修改PCB中的状态信息 再将其插入到就绪进程队列 B U 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.4 同步与互斥 并发的进程 独立性：各进程都可以独立向前推进 制约性：进程之间有时会相互制约 直接制约 源于进程间的合作 异步环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程 同步 间接制约 源于进程对资源的共享和争用 由共享公有资源而造成的对并发进程执行速度的制约 一旦将这个竞争资源分配给一个进程，其它进程就必须等待，直到前者完成任务释放资源为止 互斥 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 同步与互斥 互斥 竞争资源的进程首先面临的是互斥的要求 某些资源由于其物理特性，一次只允许一个进程使用，不能多进程同时共享，我们称其为临界资源 打印机、磁带机 物理设备 变量、数据、队列 软临界资源 避免与时间有关的错误 共享了变量 同时使用了这个变量 多个进程之间需要互斥使用临界资源 指在一个进程开始使用但尚未结束使用的期间，另一个进程也开始了使用 B U PT 漆渊2.2.4 同步与互斥 互斥 访问临界资源的程序段称为临界区CS（Critical Section）其它程序段统称为非临界区non_CS 把与同一个临界资源相关联的临界区称为同类临界区 互斥使用临界资源的问题 控制不允许进程同时进入各自的同类临界区 B U PT 漆渊2.2.4 同步与互斥 互斥 使用临界区的基本要求 互斥进入：只允许一个进程访问该临界资源 不互相阻塞：如果有若干进程都要求进入临界区，必须在有限时间内允许一个进程进入，不应互相阻塞，以至于哪个进程都无法进入 公平性：进入临界区的进程要在有限时间内退出，不让等待者无限等待 Repeat Non_CS;临界区入口控制代码CS-inCode；CS；临界区出口控制代码CS-outCode；Until false B U PT 漆渊2.2.4 同步与互斥 同步概念与同步问题 同步(synchronism)是指有协作关系的进程之间需要调整它们之间的相对速度 计算进程 当上一次计算结果还在缓冲区未被打印时，Computing进程不能向其中送入新的计算结果，计算进程必须等待 单缓冲区 打印进程 当计算结果未出来前，Printer进程必须等待 互斥也是一种特殊的同步，而同步时共享的资源（缓冲区）也是临界资源，因此有时我们将同步和互斥面临的问题统称为同步问题 B U PT 漆渊2.2.4 同步与互斥 同步机制都应遵循下述四条准则 空闲让进：当无进程进入临界区，应允许一个请求进入临界区的进程立即进入临界区 忙则等待：当已有进程进入临界区，其它请求进入临界区的进程必须等待，以保证对临界资源的互斥访问 有限等待：对请求进入临界区的进程，应保证在有限时间内能够进入临界区，避免“死等”让权等待：当进程不能进入自己的临界区时，应立即释放已占用资源，以免产生死锁 B U 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.5 信号量机制 信号量机制 1965年荷兰学者Dijkstra 是现代操作系统在进程之间实现互斥与同步的基本工具 基本原理是：两个或多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一位置停止，直到它接收到一个特定的信号 信号量 为了发信号，需要使用一个特殊变量，即信号量。是一个数据结构，它由一个信号量变量以及对该变量进行的原语操作组成 操作系统利用信号量实现进程同步与互斥的机制称为信号量机制 B U PT 漆渊2.2.5 信号量机制 整型信号量 信号量变量定义为整数值变量 定义三个操作 一个信号量可以初始化成非负整数 原语操作P（P操作）：判断信号量值，如果为0，忙等待（判断等待），否则将信号量值减1；原语操作V（V操作）：将信号量值加1 P、V操作的算法描述如下：P(S):While S=0 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-；进入临界区 临 界 区 工作，访 问临界资源 退 出 临 界区；执行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，等待的进程此时判断信号量值为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信号量的、挂在（阻塞在）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(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操作：判 断 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 信号量机制 利用信号量实现进程同步 设计一个同步方案解决计算进程与打印进程的同步 计算进程 单缓冲区 打印进程 二者的同步关系是，计算进程先执行，有了计算结果才可以打印 计算进程为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 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经典的进程同步问题 生产者-消费者问题 代表两类对象共享资源，间接制约的关系 问题描述与分析 一组生产者和一组消费者，通过一个有界的缓冲池进行通信 生产者不断（循环）将产品送入缓冲池，消费者不断（循环）从中取用产品 互斥问题:存在于所有进程之间 同步问题：存在于两类进程之间 若缓冲池满（供过于求），则生产者不能将产品送入，必须等待消费者取出产品；若缓冲池已空（供不应求），则消费者不能取得产品，必须等待生产者送入产品。B U PT 漆渊2.2.6经典的进程同步问题 生产者-消费者问题 设计信号量 同步问题 产品多少（货）缓冲池大小（坑）生产、消费者执行顺序 同步信号量 满缓冲数量：full（0）空缓冲数量：empty（n）互斥问题 缓冲池 只有一种临界资源 互斥信号量 mutex 初值一定为1 设置信号量的关键：找到使进程状态变化的量 初始：没货，full=0，消费者状态阻塞 初始有n个坑，直到没坑，empty=0，生产者状态阻塞 B U PT 漆渊消费者进程临界区出口 消费者进程临界区 消费者进程临界区入口 2.2.6经典的进程同步问题 生产者-消费者问题 并发进程的行为 生产者进程临界区出口 生产者进程临界区 生产者进程临界区入口 判断缓冲是否满 判断缓冲是否被用 标记退出缓冲（唤醒使用缓冲的进程）标记存放（唤醒取产品的进程）阻塞（等待有坑）阻塞（等待挪地）判断缓冲是否空 阻塞（等待有货）判断缓冲是否被用 阻塞（等待挪地）标记退出缓冲（唤醒使用缓冲的进程）标记取走（唤醒生产的进程）Yes Yes Yes Yes 取产品 存产品 B U PT 漆渊2.2.6经典的进程同步问题 生产者-消费者问题 入口出口控制代码设计 生产者 消费者 判断 是否有坑 是否有人占坑 是否有货 是否有人占坑 尝试信号量 empty mutex full mutex 阻塞原因 等待有坑、取货事件（消费者）等待挪地儿（占坑者）等待有货、送货事件（生产者）等待挪地儿（占坑者）阻塞位置 empty的阻塞队列上 Mutex的阻塞队列上 Full的阻塞队列上 Mutex的阻塞队列上 唤醒 消费者取货，操作empty 占坑者出来操作mutex 生产者送货，操作full 占坑者出来操作mutex 谁导致了进程状态变化？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.value0 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 消费者进程临界区入口 消费者进程临界区出口 想看看有货没？有货，那么有人在用缓冲池吗？不用缓冲池了，要用的醒醒！已取货，货又少了一个，存货的醒醒！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 漆渊2.2.6经典的进程同步问题 读者-写者问题 多个并发进程共享一个数据对象（如数据库或文件），这些进程中有的只想读共享数据，而其它一些进程可能要更新（即读和写）共享数据 问题描述与分析：保证一个Writer进程必须与其它进程互斥地访问共享对象的问题 允许多个进程同时读一个共享对象 不允许一个Writer进程和其它Reader进程或Writer进程同时访问共享对象 互斥问题 B U PT 漆渊2.2.6经典的进程同步问题 读者-写者问题 设计信号量 互斥问题 访问的数据对象 多个读进程计数 读写进程的互斥 两种种临界资源 互斥信号量wmutex 初值为1 整数变量ReaderCount 初值为0 变化由Reader进程进出临界区时加1或减1 互斥信号量Rcmutex 初值为1 注意引起进程状态变化的量 读写进程共享 读进程共享 不允许一个Writer进程和其它Reader进程或Writer进程同时访问共享对象 允许多个读进程共享对象 B U PT 漆渊2.2.6经典的进程同步问题 读者-写者问题 并发进程的行为 Reader进程临界区出口 Reader进程临界区 Reader进程临界区入口 判断是否有Reader进程在访问数据对象 判断是否有Writer进程在访问数据对象，与Writer进程互斥访问数据对象 判断是否还有Reader进程在访问数据对象 Writer进程临界区出口 Writer进程临界区 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，操作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 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节目录概要 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 漆渊