计算机操作系统课件(第四版)第二章.ppt

第二章进程管理 2 1前驱图和程序执行2 2进程的描述2 3进程控制2 4进程同步2 5经典进程同步问题2 6进程通信2 7线程的基本概念 2 1前驱图和程序执行 程序的顺序执行前趋图与前趋关系程序的并发执行 1 程序顺序执行的特征 1 程序的顺序执行 语句1 语句2 语句3 语句4 语句5 I2 C2 P2 程序1 程序2 2 特征 顺序性 封闭性 可再现性 2 前趋图与前趋关系 前趋图 PrecedenceGraph 一个有向无循环图描述程序或程序段之间执行的前后关系前趋关系 如果 Pi Pj 也可以写成 Pi Pj则称 Pi是Pj的直接前趋 Pj是Pi的直接后继初始结点 没有前趋终止结点 没有后继 观察下图 初始结点是哪个 终止结点是哪个 有哪些前驱关系 思考 下图是否为前趋图 S1 S2 S3 3 程序的并发执行 输入程序 计算程序 打印程序 并发执行时的特征间断性 停停走走 失去封闭性 原因 多个程序共享资源不可再现性 程序A n n 1 程序B print n n 0 例如 有两个循环程序A和B 共享一个变量n 程序A和B以不同的速度运行 可能出现的情况如下 1 A快B慢 得到的n值为 n 1 n 1 0 2 B快A慢 得到的n值为 n 0 1 3 n n 1在print n 和n 0之间 如图 得到的n值为n n 1 0 2 2进程的描述 进程的定义和特征进程的基本状态和转换挂起操作和状态转换进程管理中的数据结构 2 2 1 进程的定义和特征 进程的定义进程的特征 进程的定义 进程 进程是进程实体的运行过程 是系统进行资源分配和调度的一个独立单位 进程实体 程序段 相关的数据段 PCB Linux的进程实体组成 Linux进程是由三部分组成 正文段 用户数据段和系统数据段 1 正文段 text 程序段正文段是只能读不能修改的指令代码 它允许系统中多个进程共享这一代码段 2 用户数据段 usersegment 数据段用户数据段是进程执行时直接操作的所有数据 包括全部变量在内 这些信息是可以被修改的 3 系统数据段 systemsegment PCB系统数据段存放着进程的控制信息 即进程控制块 PCB 它存放了程序的运行环境 进程的结构图示 进程控制块 动态特征的集中反映 描述要完成的功能 操作对象及工作区 进程的其他定义 进程是一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程 进程是并发程序的一次执行过程 是系统进行资源分配和调度的独立单位 进程是可以和别的计算并发执行的计算 进程与程序的区别 进程是动态的 程序是静态的 程序是有序代码的集合 进程是程序的执行 进程是暂时的 程序的永久的 进程是一个状态变化的过程 程序可长久保存 进程与程序的组成不同 进程的组成包括程序 数据和进程控制块 即进程状态信息 进程与程序的对应关系 通过多次执行 一个程序可对应多个进程 通过调用关系 一个进程可包括多个程序 进程的特征 动态性 它由创建而产生 由调度而执行 由撤销而消亡 进程具有动态的地址空间 数量和内容 地址空间上包括 代码 指令执行和CPU状态的改变 数据 变量的生成和赋值 系统控制信息 进程控制块PCB的生成和删除 独立性 进程是一个能独立运行 独立分配资源和独立调度的基本单位 各进程的地址空间相互独立 并发性 引入进程的目的正是为了使其程序能和其他进程的程序并发执行 异步性 进程按各自独立的 不可预知的速度向前推进结构性 进程由程序段 数据段及PCB三部分组成 在Linux中称为 进程映像 2 2 2进程的基本状态及转换 就绪状态 Ready 得到了除CPU以外的所有必要资源执行状态 Running 已获得处理机 程序正在被执行阻塞状态 Blocked 因等待某事件发生而暂时无法继续执行 从而放弃处理机 使程序执行处于暂停状态 1 进程的三种基本状态 进程基本状态转换图 创建状态为新进程创建PCB 填写信息 该进程转入就绪状态并插入就绪队列中 引入创建状态可保证进程的调度在创建工作完成后 确保对PCB操作的完整性 终止状态等待OS进行善后处理将PCB清零 将PCB空间返还系统 终止态的进程不能再执行 但需等待其它进程完成对它的信息提取后 OS再将它删除 进程的挂起状态 静止状态 引入父进程考查和修改 协调子进程间的活动操作系统协调资源使用或进行记账终端用户的请求 希望自己的程序暂时静止下来负荷调节的需要 如实时紧急任务 由系统把一些不重要的进程挂起 活动 静止 进程的挂起状态 挂起就绪 挂起阻塞 活动就绪 执行 活动阻塞 1 操作系统中用于管理控制的数据结构资源信息表 进程信息表 数据结构表征其实体 包含了资源或进程的标识 描述 状态等信息及一批指针 2 2 4 进程管理中的数据结构 内存表 设备表 文件表 进程表1 进程表n 进程1 进程n 进程实体及所用资源列表 2 PCB ProcessControlBlock PCB中记录了操作系统所需的 用于描述进程的当前情况以及控制进程运行的全部信息 OS是根据PCB来对并发执行的进程进行控制和管理的 是进程存在的唯一标志 PCB可被操作系统中的多个模块读或修改 如被调度程序 资源分配程序 中断处理程序以及监督和分析程序读或修改 PCB经常被系统访问 故应常驻内存 2 2 4 进程管理中的数据结构 Linux的PCB结构 3 PCB中的信息进程标识符 唯一的标识一个进程内部标识 OS 外部标识 由创建者提供 由字母数字组成 处理机状态 由CPU的各种寄存器中的内容组成 通用R指令计数器PC程序状态字PSW用户栈指针 进程调度信息 进程状态进程优先级其它信息等待事件 阻塞原因 进程控制信息 程序和数据的地址同步和通信机制资源清单链接指针 4 进程控制块的组织方式 PCB数目一个系统中的PCB数目可为数十个 数百个甚至数千个线性方式把所有的PCB都组织在一张线性表中 将表的首地址放在内存的专用区中 链接方式把具有同一状态的PCB 用其链接字链接成一个队列就绪队列 若干个阻塞队列 空队列索引方式系统根据所有进程的状态建立相应的索引表就绪索引表 阻塞索引表等 索引表在内存的首地址记录在内存的一些专用单元中 PCB线性表示示意图 PCBn PCB链接队列示意图 按索引方式组织PCB 第三节进程的控制 系统内核进程创建进程撤消进程阻塞进程唤醒进程挂起与激活 进程管理中最基本功能是进程控制 进程控制的作用 创建新进程 终止已完成进程 并负责进程的状态转换 进程控制是由OS内核中的原语实现的 OS内核 把一些与硬件紧密相关的模块 如中断 各种常用设备的驱动程序 运行频率较高的模块 时钟管理 进程调度等 以及为许多模块公用的一些基本操作 安排在靠近硬件的软件层次中 以提高OS的运行效率 OS内核是常驻内存的程序和数据 2 3 1操作系统内核 原语 是由若干条指令组成的 用于完成一定功能的一个过程 具有不可分割性 具有原子性 即 原语的执行必须是连续的 在执行的过程中不允许被中断 处理机的执行状态具有两种状态 核心态 系统态 管态 OS的管理程序执行时处理机所处状态 具有较高的特权 能执行一切指令 访问所有寄存器和存储区 OS运行在系统态 用户态 目态 用户程序执行时处理机所处状态 具有较低特权的执行状态 仅能执行规定的指令访问制定的寄存器和存储区 应用程序一般运行在用户态 1 进程创建 Creat 进程之间的关系 父 子进程与祖先进程 PCB中标识继承归还资源 父 创建 子 父撤子消 引起创建进程的事件用户登录 作业调度 提供服务 应用请求进程创建的过程申请空白PCB 为新进程分配资源 初始化PCB 插入就绪进程队列 RAM程序 数据 PCB80 PCB68 2 进程撤消 Terminat 引起进程终止 Termination 的事件正常结束 执行到最后的结束指令 中断异常结束 出现错误或因故障而被迫终止外界干扰 进程应外界的请求而终止运行进程撤消的过程检索进程状态 结束并置调度标志 撤销其所有的子进程 归还资源 移出队列一个进程可以向其父进程申请撤消自己 也可以因父进程的被撤销而被同时撤消 3 进程阻塞 Block 引起阻塞的事件请求系统服务 启动某种操作 数据尚未到达 无新工作可做进程阻塞的过程发现上述事件 调用阻塞原语把自己阻塞停止进程的执行 修改PCB中的状态信息 并将其插入相应的阻塞队列转调度程序进行重新调度 4 进程唤醒 Wakeup 引起唤醒的事件与引起阻塞的事件相对应进程唤醒的过程阻塞进程所期待的事件出现 有关的进程调用唤醒原语 将等待该事件的进程唤醒将PCB从阻塞队列中移出 修改PCB中的状态信息 再将其插入到就绪进程队列中阻塞与唤醒要匹配使用 以免造成 永久阻塞 5 进程挂起与激活 Suspend Active 进程挂起检查被挂进程的状态 改为相应的挂起状态 把进程的PCB复制到指定的区域 最后 转向调度程序重新调度 进程激活先将进程从外存调入内存 检查该进程的现行状态 改为相应的活动状态 根据优先级确定是否需要重新调度 第四节进程同步 进程同步的主要任务是使并发执行的诸进程之间有效地共享资源和相互合作 从而使程序的执行具有可再现性 基本概念硬件同步机制信号量机制信号量的应用 进程互斥 一个进程正在访问临界资源 另一个要访问该资源的进程必须等待 并发执行可产生与时间有关的错误 2 4 1基本概念 两种形式的制约关系直接相互制约 源于进程间的合作间接相互制约 源于进程对资源的共享进程同步 合作完成同一个任务的多个进程 在执行速度或某些时序点上必须相互协调的合作关系 互斥现象 火车到站的调度火车1火车2火车3 站台轨道 例1 两个同学做抢椅子的游戏 同学甲 if有空椅子then坐下 同学乙 if有空椅子then搬走 例2 民航售票系统 主机 A窗口 B窗口 C窗口 D窗口 每个进程执行的操作 设x表示某航班的票数 ifx 0thenx x 1 在某时刻x 1 有a b两人分别去A窗口 B窗口买票 分析售票情况 a人 b人 例3 交通流量统计 统计在一定的时间段之内在路面上通过的车辆数量 利用计算机计数车辆数 S表示车辆数 S 0 Delay 600 Write S 中断处理程序 S S 1 例4 存储管理 分配进程 B ifx Bthen等待elsex x B 回收进程 B x x B 唤醒 x为可用内存空间 例5 哲学家就餐问题 五个哲学家围着桌子坐 工作方式 思考 if饿了 拿左叉子 拿右叉子 吃饭 放左叉子 放右叉子 只能拿靠近自己左右两边的叉子 临界区 临界段 临界资源 一段时间内只允许一个进程访问的资源临界区 每个进程中访问临界资源的代码段临界区的使用原则 各进程互斥地进入临界区 可实现互斥访问临界资源 同步应遵循的规则空闲让进 忙则等待 有限等待 让权等待 2 4 2 硬件同步机制 关中断利用Test and Set指令实现互斥利用Swap指令实现进程互斥 计算机提供一些特殊的硬件指令 允许对一个字中的内容进行检测和修正 或者是对两个字的内容进行交换 利用这些特殊指令解决临界区问题 临界区的标志可以看做一个锁 锁开 锁关两种状态 关中断 关中断是实现互斥的最简单的方法之一 进入锁测试之前关闭中断 直至完成锁测试 并上锁之后才能打开中断 进程在临界区中执行期间 计算机系统不响应中断 也不会引发进程调度 缺点 滥用关中断权利关中断时间过长 会影响系统效率不适用于多CPU系统 利用Test and Set指令实现互斥 是一种借助TS 测试建立 硬件指令实现互斥TS指令的一般性描述 booleanTS boolean lock booleanold old lock lock TRUE returnold do whileTS while TRUE 利用Swap指令实现进程互斥 对换指令 用于交换两个字的内容 booleanswap boolean a b booleantemp temp a a b b temp do key TRUE do swap while TRUE 3 信号量 灯 机制 1965年 荷兰人Dijkstra首先提出信号量机制信号量 Semaphores 用于表示资源数目或请求使用某一资源的进程个数的数据结构 信号量是一个被保护的变量 它的值只能通过初始化和两个wait signal原语来操作 作为OS核心代码执行 wait操作 P原语 进程申请使用资源的操作 或申请进入临界区的操作 类似于进入区的功能 P是荷兰语的test proberen signal操作 V原语 进程用此释放临界资源 类似于退出区的功能 V是荷兰语的increment verhogen Dijkstra 迪杰斯特拉 信号量的类型 整型 S为初值非负的整型变量 通常描述资源的状态或可用资源的数量 记录型 二元组 S Q Q初始状态为空的队列 AND型 一次需要多个共享资源 改进wait signal操作 信号量集 一次需要N个多类资源 改进wait signal操作 整型信号量intS Semaphorewait S whileS 0dono op S signal S S wait s 和signal s 是原子操作只要信号量S 0就不断测试 不满足让权等待 是一个记录型的数据结构 包含两个数据项 一是记数值域 另一是等待该信号量的进程队列首指针域 描述如下 记录型信号量 typedefStructSemaphore intvalue 整型变量List of processL 进程等待队列 S S value L wait S S value ifS value 0thenblock S L 将该进程状态置为等待状态 并将该进程的PCB插入相应的等待队列S L末尾 wait S 原语描述如下 执行一次wait操作意味着请求分配一个单位的资源 因此描述为 s value s value 1 减1后 若s value 0 则进程继续进行 若s value 0 表示已无资源可用 因此请求该资源的进程将被阻塞 要把它排在信号量s的等待队列中 此时 s value的绝对值等于该信号量等待队列上的进程数目 s value的物理含义 信号量的物理意义 S 0 S表示可用资源的个数S 0 S表示无资源 无等待进程S 0 S 表示等待队列中进程的个数 signal S S value ifS value 0thenwakeup S L 唤醒相应等待队列中等待的第一个进程 改变其状态为就绪态 并将其插入到就绪队列 signal S 原语描述如下 执行一次signal操作意味着释放一个单位的资源 故s value s value 1 加1后 若s value 0 则进程继续 若s value 0 表示信号量请求队列中仍有因请求该资源而被阻塞的进程 因此应把队列中的一个或几个进程唤醒 使之转至就绪队列中 举例 已知系统中有两台打印机 又有A B C D四个进程都要使用打印机 分析其wait signal操作和信号量变化 设打印机资源信号量为s 初值为2 A wait s 使用打印机 signal s B wait s 使用打印机 signal s C wait s 使用打印机 signal s D wait s 使用打印机 signal s s 1 s 0 s 1 s 2 s 1 s 0 s 1 s 2 4 信号量的应用 实现进程互斥例如 两个进程都使用一台打印机实现进程同步例如 矩阵运算A B利用信号量实现前驱关系 1 实现进程互斥 mutex 1 wait mutex 临界区代码signal mutex SAVE m1 amountm1 m1 10amount m1 TAKE m2 amountm2 m2 10amount m2 如何用wait signal操作实现两并发进程的互斥执行 例2兄弟俩共用一个账号 每次仅限存取十元钱 存钱和取钱的进程分别如下所示 amount 0parbeginSAVE TAKEparend 解决方法 设信号量mutex 初值为1 控制进程对变量amount的互斥使用 amount 0parbeginSAVE TAKEparend SAVE wait mutex m1 amountm1 m1 10amount m1signal mutex TAKE wait mutex m2 amountm2 m2 10amount m2signal mutex 2 实现进程同步 例3 矩阵A B运算 3 实现前趋关系 前趋关系 并发执行的进程P1和P2中 分别有代码C1和C2 要求C1在C2开始前完成 为该前趋关系设置一个同步信号量S12 其初值为0 C1Signal S12 P1 Wait S12 C2 P2 例4 利用信号量来描述前趋图关系 该前趋图具有8个结点 共有有向边10条 可设10个信号量 初值均为0 有8个结点 可设计成8个并发进程 具体描述如下 smaphorea b c d e f g h I j 0 0 0 0 0 0 0 0 0 0 parbegin S1 signal a signal b signal c wait a S2 signal d wait b S3 signal e signal f wait c S4 signal g wait d wait e S5 signal h wait f wait g S6 signal i wait h wait i S7 signal j wait j S8 parend 用信号量解题的关键 步骤 信号量的设置 给信号量赋初值 常用的互斥和同步信号量值的大小 wait signal操作安排适当的位置注意 1 互斥信号量 互斥时使用的信号量 二元信号量 其初值为1或n 表示临界资源的数目 用作互斥 它wait signal操作在同一个进程中 2 同步信号量 它联系着一组并行进程 但其初值为 或为某个正整数 主要用于进程同步 wait signal操作在两个进程中配对出现 信号量小结 信号量必须置初值 且只能置一次初值 初值可为非负整数信号量分类 互斥的信号量 它的P V在同一个进程中同步的信号量 它的P V在不同的进程中信号量的物理意义 S 0 S表示可用资源的个数S 0 S表示无资源 无等待进程S 0 S 表示等待队列中进程的个数 第五节经典进程同步问题 生产者 消费者问题生产者与消费者互斥访问公用数据缓冲区生产 数据 消费 数据 读者 写者问题数据文件或记录被多个进程共享并互斥访问的问题允许多个Reader同时访问 但不允许一个Writer和其它Reader或任何两个以上的Writer同时访问哲学家就餐问题多资源共享及互斥访问五个哲学家的思考与互斥共享五根筷子就餐的问题 生产者 消费者问题 仓库 放 取 生产者 消费者问题分类 第一类 一个生产者 一个消费者 单一资源第二类 一个生产者 一个消费者 多个资源第三类 多个生产者 多个消费者 多个资源 情况一 单一资源的Producer Consumer问题 同步问题 分析进程间的同步关系 设置信号量 设进程P的同步信号量 buffer empty 初值为1 表示缓冲区个数 空缓冲区的个数 设进程C的同步信号量 product full 初值为0 表示产品个数 满缓冲区的个数 P while true 生产一产品 P buffer 送产品到缓冲区 C while true P product 从缓冲区取一产品 消费产品 V product V buffer 初值buffer 1 product 0 情况二 多个资源的P C问题 有限资源 1 设置信号量 buffer 进程P的私用信号量 初始值为n 缓冲区的个数 product 进程C的私用信号量 初始值为0 2 算法描述Main smaphorebuffer n product 0 intin 0 out 0 parbeginP C parend P while true 生产一产品 P buffer 往Buffer i 放产品 V product in in 1 n 环形缓冲区 C while true P product 从Buffer j 取产品 V buffer 消费产品 out out 1 n 初值buffer n product 0 情况三 n个缓冲区 m个生产者 k个消费者 要求 任何时刻只能有一个进程可对共享缓冲池进行操作 1 分析进程的同步关系 2 设置信号量a 互斥信号量mutex 表示缓冲池是否可用 初值为1 b 生产者的同步信号量buffer empty 表示缓冲区个数 空单元数 初值为n c 消费者的同步信号量product full 表示产品个数 满单元个数 初值为0 Producer while true 生产一产品 wait buffer 往Buffer in 放产品 in in 1 n signal product Consumer while true wait product 从Buffer out 取产品 out out 1 n signal buffer 消费一产品 wait mutex signal mutex wait mutex signal mutex 初值buffer n product 0 mutex 1 该问题中的两个wait操作的顺序不能颠倒 否则容易导致死锁 例如 消费者进程的两个wait操作顺序如下 Consumer while true wait mutex wait product 从Buffer out 取产品 out out 1 n signal mutex signal buffer 消费一产品 Producer while true 生产一产品 wait buffer wait mutex 往Buffer in 放产品 in in 1 n signal mutex signal product 问题 其实生产者和消费者间是不用互斥的 为了提高效率 为生产者和消费者分别设置互斥信号量 解决方法 为所有生产者设置一互斥信号量 mutex1 为所有消费者设置一互斥信号量 mutex2 初值均为1 代码如下 Producer while true 生产一产品 wait buffer 往Buffer in 放产品 in in 1 n signal product Consumer while true wait product 从Buffer out 取产品 out out 1 n signal buffer 消费一产品 初值buffer n product 0 mutex1 1 mutex2 1 wait mutex1 signal mutex1 wait mutex2 signal mutex2 小结 P S 表示申请 请求 使用 一个资源V S 表示释放 归还 一个资源信号量的初值应该 0P V必须成对出现 但不一定一一对应 当互斥操作时 处于同一进程当同步操作时 则在不同进程如果P S1 和P S2 两个操作在一起 那么P操作的顺序至关重要 一个同步P操作与一个互斥P操作在一起时 同步P操作应在互斥P操作前 而两个V操作无关紧要 思考 有一个充分大的池子 两个人分别向池中扔球 甲扔红球 乙扔兰球 一次扔一个 开始时池中有红球 兰球各一个 要求池中球满足条件 1 红球数 兰球数 2试用P V描述两个过程 AND型信号量集 AND型信号量集是指同时需要多种资源 且每种占用一个时的信号量操作 基本思想 在一个原语中申请整段代码需要的多个临界资源 要么全分配给它要么一个都不分配 AND型信号量集P原语 Swait SimultaneousWait AND型信号量集V原语 Ssignal Swait S1 S2 Sn P操作 while true if S1 1阻塞调用进程 Ssignal S1 S2 Sn V操作 for i 1 i n i Si 释放占用的资源 for 在Si L中等待的每个进程P 检查每种资源的等待队列的所有进程 从等待队列Si L中取出进程P if 判断进程P是否通过Swait中的测试 进程P进入就绪队列 通过检查时的处理else 进程P进入某等待队列 未通过检查时的处理 哲学家就餐问题 信号量定义 varchopstick 0 4 ofsemaphore 所有信号均量初始化为1第i位哲学家的活动描述 while true P chopstick i P chopstick i 1 5 eating V chopstick i V chopstick i 1 5 thinking Swait chopstick i chopstick i 1 5 Ssignal chopstick i chopstick i 1 5 1 至多只允许四位哲学家同时坐在桌旁 2 仅当哲学家左右两边的筷子均可用时才允许他拿起筷子 3 规定奇数号哲学家先拿起他左边的筷子 再拿右边的筷子 而偶数号哲学家先拿起他右边的筷子再拿左边的筷子 死锁的解决办法如下 第1种解决解决方法 Semaphorechopstick 5 1 1 1 1 1 Semaphoresm 4 while true wait sm wait chopstick i wait chopstick i 1 5 eating signal chopstick i signal chopstick i 1 5 signal sm thinking 第2种解决解决方法 用AND型信号量解决信号量定义 semaphorechopstick 5 所有信号均量初始化为1第i位哲学家的活动描述 while true wait chopstick i wait chopstick i 1 5 eating signal chopstick i signal chopstick i 1 5 thinking Swait chopstick i chopstick i 1 5 Ssignal chopstick i chopstick i 1 5 while true ifi 2 0then wait chopstick i wait chopstick i 1 5 eating signal chopstick i signal chopstick i 1 5 thinking else wait chopstick i 1 5 wait chopstick i eating signal chopstick i 1 5 signal chopstick i thinking 第3种解决解决方法 则第i位哲学家的活动描述 Semaphorechopstick 5 1 1 1 1 1 一般信号量集 一般信号量集是指同时需要多种资源 每种占用的数目不同 且可分配的资源还存在一个临界值时的信号量处理 基本思路 在AND型信号量集的基础上进程扩充 在一次原语操作中完成所有的资源申请 对应的PV原语格式为 Swait S1 t1 d1 Sn tn dn Ssignal S1 d1 Sn dn 进程对信号量Si的下限值 测试值 为ti 表示信号量的判断条件 要求Si ti 即当资源数量低于ti时 便不予分配 需求值 占用值 为di 表示资源的申请量 即Si Si di Swait S d d Swait S 1 1 Swait S 1 0 只测试 不占用 可控开关 一般信号量集的几种情况 读者 写者问题 有两组并发进程 读者 写者 共享一组数据区要求 允许多个读者同时执行读操作不允许读者 写者同时操作 读写互斥 不允许多个写者同时操作 只能一人写 第一类 读者优先如果读者来 无读者 写者 新读者可以读有写者在等待 但有其他读者在读 则新读者也可以读有写者在写 新读者等待 如果写者来 无读者 新写者可以写有读者 新写者等待有其他写者 新写者等待 例如 教室 共享文件上自习 读者 多个人使用教室 练歌 写者 1个人使用教室 策略 1 唱歌的人进来后 把门关上 其他任何人等待2 自习的人进来后 把前门关上 后门开 其他自习的人从后门进 唱歌的人等待 关键 1 第一个读者进入后把前门关 后门开2 最户一个读者离开时 把后门关 从前门出 读者 while true if readcount 0 P wmutex readcount 读 readcount if readcount 0 V wmutex 写者 while true P wmutex 写V wmutex 初值wmutex 1rmutex 1 用一般信号量集表示 只允许至多RN个人同时读 写者 Swait mx 1 1 rcount RN 0 既无写者也无读者才可 写 操作写Ssignal mx 1 读者 Swait rcount 1 1 mx 1 0 读 Ssignal rcount 1 初值mx 1rcount RN 控制读者人数 管程机制 管程的基本概念管程应用分析 1 管程的基本概念 管程的提出 采用P V同步机制来编写并发程序 对于共享变变量及信号量变量的操作将被分散于各个进程中 缺点 易读性差 不利于修改和维护 正确性难以保证管程的产生 Dijkstra 1971 秘书 进程Hansen和Hoare 1973 管程概念 管程 Monitor 定义了一个数据结构和能为并发进程所执行 在该数据结构上 的一组操作 这组操作能同步进程和改变管程中的数据 管程的形式 构成部分名字局部于管程的数据结构说明 共享变量 局部于管程的对该数据结构进行操作的一组过程 函数对局部于管程的数据的初始化语句 typemonitor name monitorvariabledeclarationsprocedureentryp1 begin end prcedureentryPn begin end begininitializationcode end 管程的特点 1 封装性 管程内的共享变量在管程外不可见 2 管程必须互斥进入3 管程通常是用来管理资源的 因而在管程中应当设有进程等待队列以及相应的等待和唤醒操作 问题 多个进程出现在管程中 当一个进入管程的进程Q执行等待操作时 它应当释放管程的互斥权 当另一个进入管程的进程P执行唤醒操作时 如P唤醒Q 管程中便存在两个同时处于活动状态的进程 这是管程所不允许的 处理方法有三种 前提 P唤醒Q 1 P等待 Q继续 直到Q退出或等待2 Q等待 P继续 直到P退出或等待3 规定唤醒操作为管程中最后一个可执行的操作 入口等待队列 等待进入管程紧急等待队列 在管程内部由于执行唤醒操作 可能会出现多个等待进程注 紧急等待队列优先级高于入口等待队列 条件变量condition 当进入管程的进程因资源被占用等原因不能继续运行时要使其等待 为此在管程内部可以说明和使用一种特殊类型的变量 称为条件变量 Varcconditon 对于条件变量可以执行wait和signal操作 c wait 如果紧急等待队列非空 则唤醒第一个等待者 否则 释放管程的互斥权 执行此操作的进程的PCB入C链尾部 c signal 如果C链为空 则相当于空操作 执行此操作的进程继续 否则 唤醒第一个等待者 执行此操作的进程的PCB入紧急等待队列的尾部 2 管程应用分析 生产者 消费者问题put item 产品放入缓冲区中get item 从缓冲区中取出一产品producer consumer 简称p c typep c monitorVarin out count integer buffer array 0 n 1 ofitem notfull notempty condition procedureentryput Varpro item beginifcount nthennotfull wait buffer in pro in in 1 modn count count 1 ifnotempty queue notempty signal endprocedureentryget Varpro item beginifcount 0thennotempty wait pro buffer out out out 1 modn count count 1 ifnotfull queuethennotfull signal end beginin out 0 count 0 end 第六节进程通信 进程通信的概念进程通信的类型消息传递通信的实现方法消息传递系统实现中的若干问题消息缓冲队列通信机制 1 进程通信的概念 进程通信 是指进程之间的信息交换 低级通信 互斥 同步 利用信号量机制实现进程间的数据传递 缺点 效率低 对用户不透明 高级通信 进程通信 进程之间利用OS提供的一组通信命令 高效地传送大量数据的信息交换方式 优点 高效 方便 简化了通信程序的设计 2 进程通信的类型 高级通信机制可分为 共享存储器系统 消息传递系统 管道通信系统三种 共享存储器系统基于共享数据结构的通信方式基于共享存储区的通信方式消息传递系统进程之间的数据交换 是以格式化的消息为单位消息 Message报文 及相关的一组命令直接通信方式和间接通信方式 管道通信系统 首创于UNIX系统 管道 Pipe文件 用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件 管道通信 发送进程和接收进程利用管道进程通信 双方进程的协调 互斥 同步 确定对方存在 3 消息传递通信的实现方法 直接通信方式发送进程利用OS提供的发送命令原语 直接把消息发送给目标进程 Send Receiver message Receive Sender message 利用直接通信原语 解决生产者 消费者问题 生产者消费者 repeat produceaniteminnextp send consumer nextp untilfalse repeat receive producer nextc consumeraniteminnextc untilfalse 间接通信方式进程之间通过一个作为共享数据结构的中间实体 信箱 以消息暂存方式实现的通信 操作原语 信箱的创建 撤消 消息的发送接收Send mailbox message Receive mailbox message 信箱的创建和拥有者 OS或用户 通信 进程 信箱的种类 私用信箱 公用信箱 共享信箱利用信箱通信时 发送和接收进程之间的关系 一对一 多对一 一对多 多对多 4 消息传递系统实现中的问题 通信链路网络中 显式调用 建立 拆除连结原语 单机中 系统自动建立 拆除连结 只需调用发送原语消息格式消息头 单机简单 消息正文定长 变长消息格式 通常系统同时支持两种格式 进程同步发送进程阻塞 接收进程阻塞发送进程不阻塞 接收进程阻塞发送进程和接收进程均不阻塞 选讲 5 消息缓冲队列通信机制 Hansen教授首先提出的消息缓冲队列通信机制是通过内存中公用的消息缓冲区进行进程通信 属直接通信方式 发送原语send receiver a a 发送区的地址接收原语receive b b 接收区的地址数据结构消息缓冲区PCB中有关通信的数据项 通信过程 构成消息 发送进程在工作区设置发送区a 将消息正文和有关控制信息填入其中 发送消息 将消息从发送区a复制到消息缓冲区 并把它插入到目标进程的消息队列中 接收消息 由目标进程从自己的消息队列中找到第一个消息缓冲区 并将其中的消息复制到自己的接收区b中 1 消息缓冲区 typemessagebuffer recordsender 发送区进程标识符size 消息长度text 消息正文next 指向下一个消息缓冲区的指针end 发送原语 接收原语 procedurereceive b beginj internalname j为接收进程的内部标识符wait j sm wait j mutex remove j mq i 将消息队列中第一个消息移出signal j mutex b sender i sender b size i size b text i text releasei 将消息缓冲区i归还系统end 将消息缓冲区i的信息复制到接收区b 消息缓冲通信 第七节线程的基本概念 线程的引入线程和进程的比较线程的属性线程的状态多线程OS中的进程 1 线程的引入 进程 60年代 目的 使多个程序并发执行 提高资源利用率和系统吞吐量定义 在OS中能拥有资源和独立运行的基本单位进程的创建 撤消与切换存在较大的时空开销 限制了并发程度的提高 线程 80年代 目的 减少程序在并发执行时所付出的时空开销 思想 轻装上阵 将进程的两个属性分离 定义 线程是系统独立调度和分派 即可独立运行 的基本单位 进程 拥有资源的单位 调度线程是调度和分派的基本单位 进程是拥有资源的基本单位并发性同族 非同族线程均可并发 拥有资源线程几乎不占资源系统开销线程的切换 同步 通信无须内核干预 开销小 2 线程和进程的特点 轻型实体 线程几乎不占资源 TCB 程序计数器 寄存器 堆栈 独立运行的基本单位 切换迅速且开销小可并发执行 同族 非同族的线程皆可并发共享进程的资源 同族的线程共享进程的资源可以创建 撤销另一个线程 3 线程的属性 每个线程都利用TCB和一组状态参数进行描述 1 状态参数 寄存器状态 堆栈 运行状态 优先级 专用存储器 信号屏蔽 2 运行状态 就绪态 执行态 阻塞态 4 线程的状态 进程作为系统资源分配的单位进程不是一个可执行的实体进程可包括一个或多个线程单进程单线程 各种UNIX版本 单进程多线程 WindowsNT Solaris OS 2 5 多线程OS中的进程 地址空间和其他资源 如打开文件 同一进程的各线程间共享资源 进程间相互独立通信进程间通信IPC 线程间可以直接读写进程数据段 如全局变量 来进行通信 需要线程间同步和通信手段的辅助 以保证数据的一致性调度不论是系统进程还是用户进程 进程的创建 撤销等都是利用系统调用进入内核 由内核的相应处理程序来完成 而线程的创建 撤销则有可能由内核来实现 也有可能无须内核的支持 线程上下文切换比进程上下文切换要快得多 6 线程和进程的比较 线程间同步和通信 互斥锁 mutex 数据结构 多线程访问关键共享数据和程序段 开锁 unlock 和关锁 lock trylock条件变量 条件变量通常都与一个互斥锁一起使用 互斥锁用于短期锁定 主要是用来保证对临界区的互斥进入 而条件变量则用于线程的长期等待 直至所等待的资源成为可用的 信号量机制私有信号量 同一进程中各线程之间的同步公有信号量 系统信号量 不同进程间或不同进程中各线程之间的同步 内核线程 kernel levelthread 依赖于OS核心 由内核的内部需求进行创建和撤销 用来执行一个指定的函数 Windo