操作系统121948

第二章进程管理 进程的基本概念进程与程序的区别进程控制进程同步进程通信线程 进程的基本概念 程序在并发环境中的执行过程资源分配和独立运行的基本单位 程序的顺序执行 一个有四条语句的程序段 S1 a x 2 S2 b y 4 S3 c a b S4 d c b 程序的顺序执行 s1 s2 s3 s4 程序顺序执行的特征 顺序性封闭性可再现性 顺序性 处理机的操作严格按照程序所规定的顺序执行 即每一个操作必须在下一操作之前结束 封闭性 程序在封闭环境下执行 结果不受外界因素影响 可再现性 只要环境和初始条件相同 程序重复执行时总得到相同结果 程序并发执行 一个有四条语句的程序段 S1 a x 2 S2 b y 4 S3 c a b S4 d c b 程序的并发执行 s1 s2 s3 s4 程序并发执行的特征 间断性共享 合作 制约导致 执行 暂停 执行失去封闭性资源状态由多程序改变不可再现性相同环境和初始条件 重复执行结果不同 程序AL1 N N 1gotoL1 程序BL2 PRINT N N 0 gotoL2 设共享变量N初值为5 则会产生3中执行结果 6 6 05 0 15 6 0 进程的特征 结构特征动态性并发性独立性异步性 结构特征 进程结构 PCB进程控制块 程序段 数据段 动态特征的集中反映 描述要完成的功能 操作对象及工作区 动态性 进程最基本的特征是动态性进程的生命周期 进程由创建而产生 由调度而执行 由撤销而消亡的过程 并发性 多个进程同在内存中 且能在一段时间内同时运行 独立性 进程是一个能独立运行 独立分配资源 独立接受调度的基本单位 异步性 进程按各自独立的 不可预知的速度向前推进 进程定义 进程是进程实体的运行过程 是系统进行资源分配和调度的基本单位 进程和程序的关系 1 进程是一个动态概念 程序是一个静态概念 2 进程具有并行特征 程序没有 3 进程是竞争资源的基本单位 4 一个程序对应多个进程 一个进程为多个程序服务 进程的三种基本状态 就绪状态执行状态阻塞状态 就绪状态 进程已经分配了除处理机以外的所有必要资源 只要再获得处理机就能够执行的状态 这样的进程可能有多个 通常排成一个队列 称就绪队列 执行状态 已经获得CPU 正在运行 在单处理机系统只有一个进程处于执行状态 多处理机系统则有多个处于执行状态 阻塞状态 正在执行的进程由于发生某事件而暂时无法继续执行时 放弃处理机而进入的状态 又称等待状态 引起阻塞的事件 请求I O 申请缓存 进程的基本状态转换 就绪 阻塞 执行 I O请求 I O完成 时间片完 进程调度 挂起状态 引入原因 1 终端用户请求 2 父进程请求 3 负荷调节需要 4 操作系统的需要 挂起引起的状态转换 静止状态 活动状态 挂起状态 非挂起状态 有挂起状态的进程状态图 静止就绪 活动阻塞 执行 I O请求 活动就绪 静止阻塞 挂起 挂起 激活 挂起 激活 调度 释放 释放 进程控制块 进程结构 PCB进程控制块 程序段 数据段 ProcessControlBlock 进程控制块 PCB是OS中最重要的记录型结构 OS用PCB对并发进程进行管理和控制 PCB是进程存在的唯一标志 PCB常驻内存 OS专门开辟PCB区将所有的PCB组织成若干个链表或队列 结构体 structure forexample 一个学生的自然信息 结构体 structure 定义一个结构 structStudent charname 20 charsex 12 DATEbirthday charspeciality 20 charclass 10 typedefstructStudentSTUDENT PCB中的信息 1 进程标识符 2 处理机状态 3 进程调度信息 4 进程控制信息 进程标识符 1 内部标识符进程唯一的数字编号 给OS使用 2 外部标识符由字母 数字组成 给用户使用 处理机状态 处理机中主要的寄存器 1 通用寄存器8 32个 暂存信息用 2 指令计数器要访问的下一条指令地址 3 程序状态字PSW条件码 执行方式 中断屏蔽标志 4 用户栈指针用户进程拥有的系统栈 存放过程和系统调用参数及调用地址 进程调度信息 进程状态进程优先级与调度算法有关信息事件如 阻塞原因 进程控制信息 程序和数据地址进程同步和通信机制资源清单 除CPU之外的所需资源与已经分配资源清单链接指针 本进程PCB所在队列的下一个地址 PCB的组织方式 1 链接方式把统一状态的PCB 用其中的链接字链接成一个队列 如 就绪队列 阻塞队列 根据不同阻塞原因 空白队列 2 索引方式建立就绪索引表 阻塞索引表等 把索引表在内存的首地址放在内存的专用单元中 链接方式 执行指针 就绪队列指针 阻塞队列指针 空闲队列指针 索引方式 执行指针 就绪表指针 阻塞表指针 进程管理中最基本功能是进程控制进程控制任务 进程的创建 终止 进程状态的转变等进程控制一般由OS内核来实现 2 2进程控制 进程图 D B C A E F G H 引起创建进程的事件 1 用户登录 2 作业调度 3 提供服务 4 应用请求 由系统内核创建 由自己创建 进程的创建 原语CREAT 按下述步骤创建一个新进程 1 申请空白PCB 2 为新进程分配资源 3 初始化进程控制块 4 将新进程插入就绪队列 PCB的初始化 初始化标识信息 初始化处理机状态信息 初始化处理机控制信息 引起进程终止的事件 正常结束 异常结束 外界干预 越界错误 保护错 非法指令 特权指令错 运行超时 等待超时 算术运算错 I O故障 操作员或os干预 被父进程终止 父进程终止 进程的终止过程 从PCB集合中检索出该进程的PCB 从中读出该进程的状态 若处于执行状态 终止该进程的执行 并置调度标志为真 重新调度 若有子孙进程 将所有子孙进程终止 将进程全部资源归还其父进程或系统 将其PCB从所在队列 或链表 中移出 引起阻塞和唤醒的事件 请求系统服务 启动某种操作 新数据尚未到 无新工作可做 进程阻塞过程 入口 保存当前进程的CPU现场 置该进程状态 进入等待队列 转进程调度 由阻塞原语BLOCK完成 进程唤醒过程 入口 从等待队列中摘下被唤醒进程 置该进程为就绪态 进入就绪队列 转进程调度或返回 由唤醒原语WAKEUP完成 注意 BLOCK和WAKEUP是一队作用相反的原语 如果在某进程中调用了阻塞原语 则必须在与之相合作的另一进程中或其他相关的进程中 安排唤醒原语 以能唤醒阻塞进程 否则 被阻塞进程将会因不能被唤醒而长久地处于阻塞状态 从而再无机会继续运行 进程的挂起 挂起原语 SUSPEND 挂起原语的执行过程 检查被挂起进程的状态 若处于活动就绪状态 改为静止就绪 若处于活动阻塞状态 则改为静止阻塞 若正在执行 则转向调度程序重新调度 有挂起状态的进程状态图 静止就绪 活动阻塞 执行 活动就绪 静止阻塞 挂起 挂起 挂起 进程的激活状态图 静止就绪 活动阻塞 执行 活动就绪 静止阻塞 激活 激活 调度 有挂起状态的进程状态图 静止就绪 活动阻塞 执行 I O请求 活动就绪 静止阻塞 挂起 挂起 激活 挂起 激活 调度 释放 释放 2 3进程同步 进程的两种制约关系 间接制约 进程间由于共享某种系统资源 而形成的相互制约 直接制约 进程间由于合作而形成的相互制约 进程B 资源 进程A 进程A 进程B 2 3进程同步 进程的两大关系 互斥同步 互斥 互斥是并发执行的多个进程由于竞争同一资源而产生的相互排斥的关系 同步 同步是进程间共同完成一项任务时直接发生相互作用的关系 同步进程间具有合作关系 在执行时间上必须按一定的顺序协调进行 临界资源 一次仅允许一个进程使用的共享资源如 打印机 磁带机 表格 临界区 在每个进程中访问临界资源的那段程序进程必须互斥进入临界区 访问临界区的循环进程描述 repeat 检查临界资源是否能访问 将临界区标志设为未访问 untilfalse 同步机制遵循的原则 空闲让进忙则等待有限等待让权等待 信号量机制 中心街道 楼宇1 小区A 小区B 城市公路 进程 信号量 信号量是一种数据结构信号量的值与相应资源的使用情况有关信号量的值仅由P V操作改变 整型信号量 整型数 S P操作 wait 原语V操作 signal 原语 Wait S whileS 0dono opS S 1 Signal S S S 1 wait s 和signal S 是原子操作 只要信号量S 0就不断测试 不满足让权等待 记录型信号量 记录型结构 包含两个数据项 typesemaphore recordvalue integer L listofprocess end Value L S S value为资源信号量其初值 某类资源的数目wait操作 申请一个单位资源 Procedurewait s VarS semaphore beginS value S value 1 IfS value 0thenblock s L end signal操作 释放一个单位资源 Proceduresignal s VarS semaphore beginS value S value 1 IfS value 0thenwakeup s L end S value 0 表示系统中可用的资源数量S value 0 其绝对值表示已阻塞的进程数量S Value初值为1时 只允许一个进程访问临界资源 是互斥信号量 Pa wait Dmutex wait Emutex Pb wait Emutex wait Dmutex 会造成死锁的僵持状态 AND型信号量 基本思想 将进程在整个运行中需要的所有资源 一次性全部分配给进程 待进程使用完后一起释放 在wait中加入AND条件 又称AND同步或同时wait操作 SwaitSwait S1 S2 Sn IfS1 1andSn 1thenfori 1tondoSi Si 1 endforelse当发现第一个Si 1就把该进程放入等待队列并将其程序计数器置于Swait操作的开始位置endif Ssignal S1 S2 Sn fori 1tondoSi Si 1 将所有等待Si的进程由等待队列取出放入到就绪队列Endfor 用信号量实现互斥 Varmutex semaphore 1 BeginParbeginProcess1 beginrepeatwait mutex criticalsectionsignal mutex remaindersectionuntilfalse end Process2 beginrepeatwait mutex criticalsectionsignal mutex remaindersectionuntilfalse end parend 在实现互斥时应注意wait mutex 和signal mutex 必须成对地出现 缺wait mutex 将会引起系统混乱 不能保证对临界资源的互斥访问缺signal mutex 将会使该临界资源永久不被释放 初始状态 mutex 1 没有并发进程使用临界区 临界区 互斥的进程 一个进程申请临界区 mutex 1 没有并发进程使用临界区 mutex 申请成功 进程使用临界区 0 mutex 0 另一个进程也申请临界区 mutex 1 申请失败 阻塞队列 mutex 0 释放资源 阻塞队列 mutex 0 释放资源 阻塞队列 2 4经典的同步问题 生产者一消费者问题读者一写者问题哲学家进餐问题 生产者一消费者问题 一组生产者进程生产产品给一组消费者进程消费 为使他们并发执行 设一个有n个缓冲区的缓冲池 生产者一次向一个缓冲区中投入消息 消费者从一个缓冲区中取得消息 生产者一消费者问题实际上是相互合作进程关系的一种抽象 制约关系 不允许消费者进程到一个空缓冲区中取产品不允许生产者进程到一个已满且还没被取走的缓冲区中投放产品 例如 在输入时 输入进程是生产者 计算进程是消费者 在输出时 计算进程是生产者 打印进程是消费者 用记录型信号量解决生产者一消费者问题 设有n个缓冲区 每个缓冲区存放一个消息 用互斥信号量mutex对缓冲池实现互斥访问 利用资源信号量empty和full分别表示缓冲池中空缓冲区及满缓冲区的数量 又假定这些生产者和消费者相互等效 只要缓冲池未满 生产者便可将消息送入缓冲池 只要缓冲池未空 消费者便可从缓冲池取走一个消息 Varmutex semaphore 1 empty semaphore n full semaphore 0 buffer array 0 n 1 ofitem in out integer 0 0 Procedure beginrepeat procedureanitemnextp wait empty wait mutex Buffer in nextp in in 1 modn signal mutex signal full untilfalse end consumer beginrepeatwait full wait mutex nextc Buffer out out out 1 modn signal mutex signal empty Consumertheiteminnextc untilfalse end 注意 每个程序中互斥的wait mutex 和signal mutex 必须成对出现 对资源信号量empty和full的P v操作成对出现 但它们分别处于不同的程序中例如P在计算进程中 而v则在打印进程中 计算进程若因执行P而阻塞 则以后将由打印进程将它唤醒 每个程序中的P操作顺序不能颠倒 应先执行对资源信号量的P操作 然后再执行对互斥信号量的P操作 否则可能引起进程死锁 哲学家进餐问题 有五个哲学家 他们的生活方式是交替地进行思考和进餐 哲学家们共用一张圆桌 分别坐在周围的五张椅子上 在圆桌上有五个碗和五支筷子 平时一个哲学家进行思考 饥饿时便试图取用其左 右最靠近他的筷子 只有在他拿到两支筷子时才能进餐 进餐毕 放下筷子又继续思考 分析 筷子是临界资源 在一段时间内只允许一个哲学家使用用一个信号量表示一支筷子 由这五个信号量构成信号量组 varchopstick array 0 4 ofsemaphore所有信号量被初始化为1 用记录型信号量解决哲学家进餐问题 第i个哲学家的活动可描述为repeatwait chopstick i wait chopstick i 1 mod5 eat signal chopstick i signal chopstick i 1 mod5 think untilfalse 问题 假如五个哲学家同时饥饿而各自拿起左边的筷子 会使五个信号量均为0 当他们再试图拿起右边筷子时 都将无限期地等待 解决方法 1 至多四个人同时拿左边的筷子 保证至少有一个人可以进餐 最终释放筷子使更多的人进餐 2 仅当哲学家的左右两支筷子均可用时 才允许他拿起筷子进餐 3 规定奇数号哲学家先拿起其左边的筷子 再拿右边的 偶数号哲学家则相反 即 l 2号人竞争1号筷子 3 4号人竞争3号筷子 即五个人都先竞争奇数号筷子 获得后 再去竞争偶数号筷子 最后总会有某一人进餐 用AND型信号量解决哲学家进餐问题 varchopstick array 0 4 ofsemaphore 1 1 1 1 1 第i个哲学家的活动 repeatthink Swait chopstick i 1 mod5 chopstick i eatSsignal chopstick i 1 mod5 chopstick i think untilfalse 读者一写者问题 一个数据文件或记录可被多个进程共享 其中 有些进程要求读 而另一些进程要求行写或修改 只要求读的进程称为 Reader进程 其它进程称为 Writer进程 允许多个Reader进程同时读一个共享对象 不允许一个Writer进程和其它Reader进程或Writer进程同时访问共享对象 所谓读者一写者问题是指保证一个Writer进程必须与其它进程互斥地访问共享对象的同步问题 信号量设置 为解决一个Writer进程和其它Reader进程互斥 设互斥信号量Wmutex设置整型变量Readercount表示正在读的进程数目 Readercount是一个可被多个Reader进程访问的临界资源 为它设置互斥信号量Rmutex 仅当Readercount 0表示无Reader进程在读时 Reader进程才需要执行p操作 若p操作成功 Reader进程便可去读 使Readercount 1 原因是 Readercount 0 说明已有Reader进程在安全的读数据 2 5进程通信 进程通信是指进程之间的信息交换交换的信息量一个状态或数值上千个字节 进程通信分类 低级通信 进程的互斥和同步高级通信 指用户可直接利用os提供的一组通信命令 高效地传送大量数据的一种通信方式 对用户透明 高级通信分类 共享存储器系统消息传递系统管道通信 共享存储器系统 1 共享数据结构的通信方式进程之间通过某种数据结构 如缓冲池进行通信属于低级通信方式 2 共享存储区通信方式为了传送大量信息 在存储器中划出一块共享存储区 进程可通过对共享存储区进行读或写来实现通信 属于高级通信方式 消息传递系统 信息交换的单位是消息或报文 分成两种 1 直接通信方式2 间接通信方式计算机网络中将消息称为报文 直接通信方式 发送进程直接把消息发送给目标进程发送进程和接收进程都以显式方式分别提供对方的标识符 系统提供两条通信原语Send Receiver message Receive Send message 例如 Send P2 m1 Receive P1 m1 解决生产者一消费者问题 repeat produceaniteminnextp Send consumer nextp untilfalse repeatReceive producer nextp Consumertheiteminnextc untilfalse 间接通信方式 进程之间的通信需要通过某种中间实体 该实体用来暂存发送进程发送给目标进程的消息 接收进程则从该实体中取出对方发送给自己的消息 这种中间实体称为信箱 消息在信箱中可以安全地保存 只允许核准的目标用户随时读取 故可实现非实时通信 信箱的创建和撤消 进程用信箱创建原语来建立一个新信箱 创建者进程应给出信箱名字 信箱属性 公用 私用或共享 对于共享信箱 还应给出共享者的名字 用信箱撤消原语来撤消 消息的发送与接收 Send mailbox message 将一个消息发送到指定信箱 Receive mailbox message 从指定信箱中接收一个消息 信箱分类 私用信箱 公用信箱 共享信箱 私用信箱 用户进程建立 作为该进程的一部分 拥有者有权读消息 其他用户只能发送 采用单向通信链路 进程结束时信箱也消失 公用信箱 它由OS创建 提供给系统中的所有核准进程使用 进程既发送也可取出 采用双向通信链路的信箱来实现 系统运行期间始终存在 共享信箱 由某进程创建 创建时提供共享进程 用户 的名字 信箱的拥有者和共享者 都有权从信箱中取走发送给自己的消息 信箱通信时发送进程和接收进程的关系 一对一关系 建立一条专用的通信链路 多对一关系 服务进程与多个用户进程之间进行交互 又称客户 服务器交互 一对多关系 一个发送进程与多个接进程进行交互 使发送进程可用广播形式 向接收者发送消息 多对多关系 建立一个公用信箱 多个进程投递并取走自己的消息 管道通信 管道通信方式建立在文件系统的基础上 利用共享文件来连接两个相互通信的进程 此共享文件称为管道 Pipe 管道是指用于连接一个读进程和一个写进程 以实现它们之间通信的共享文件 写进程 读进程 管道 管道通信必需的协调能力 1 互斥当一个进程正在对管道进行读 写操作时 另一进程必须等待 2 同步当写 输入 进程把一定量的数据 如4K 写入管道后 便去睡眠等待 直到读 输出 进程取走数据后再把它唤醒 当读进程发现管道空时也应睡眠等待 直至写进程将消息写入管道后 才将它唤醒 3 判别对方是否存在 只有确定了对方存在时方能进行通信 2 6线程 进程 使多个程序能并发执行 以提高资源利用率和系统吞吐量引入线程 是为了减少程序在并发执行时所付出的时空开销 使OS具有更好的并发性 引入线程目的 进程是可拥有资源的独立单位和可独立调度和分派的基本单位 创建 撤消和切换中 系统必须为之付出较大的时空开销 故进程 其数目不宜过多 进程切换的频率也不宜过高 进程不应同时作为拥有资源的单位和可独立调度和分派的基本单位 应该 轻装上阵 线程的属性 1 轻型实体 线程中的实体基本上不拥有系统资源 2 独立调度和分派的基本单位 线程的切换非常迅速 开销小 3 可并发执行 4 共享进程资源 课堂练习1 操作系统是控制和管理计算机系统内各种硬件和软件资源 有效地组织多道程序运行的系统软件 或程序集合 是用户与计算机之间的接口 操作系统的基本职能是 A 控制和管理系统内各种资源 有效地组织多道程序的运行B 提供用户界面 方便用户使用C 提供方便的可视化编辑程序D 提供功能强大的网络管理工具 A 操作系统的基本特征是 和 并发 共享 异步性 虚拟 操作系统中引入 进程 概念的主要目的是 A 改善用户编程环境B 描述程序动态执行过程的性质C 使程序与计算过程一一对应D 提高程序的运行速度 B 某进程由于需要从磁盘上读入数据而处于阻塞状态 当系统完成了所需的读盘操作后 此时该进程的状态将 A 从就绪变为运行B 从运行变为就绪C 从运行变为阻塞D 从阻塞变为就绪 D 进程控制块 PCB 是专为用户进程设置的私有数据结构 每个进程仅有一个PCB 判断对错并改正 所有 简单地说 进程是程序的执行过程 因而 进程和程序是一一对应的 判断对错并改正 不是 进程间相互合作的关系是 关系 而对资源争用的关系是 关系 若干进程