第3章 处理器管理

第三章处理器管理 处理器管理的地位 主要内容 3 1进程的引入3 2进程的概念3 3进程控制3 4线程3 5处理器调度3 6调度算法3 7处理器调度和实时调度 3 1 1程序的执行方式 顺序 顺序执行特征 顺序性 封闭性 可再现性 3 1 2程序的执行方式 并发 并发执行 3 1 1程序的执行方式 并发 与并发有关的错误 3 2进程的概念 问题引入程序这个静态概念已不能如实反映程序并发执行过程的特征 为了深刻描述程序动态执行过程的性质 人们引入 进程 Process 概念 3 2进程的概念 程序在处理机上执行时所发生的活动 Dijkstra 是一个容器 该容器用以聚集相关资源 A S Tanenbaum 进程是一个具有独立功能的程序关于某个数据集合的一次运行活动 是系统进行资源分配和调度的单位 3 2进程的概念 操作级 图形窗口界面 一个窗口就是一个进程打开窗口 建立一个进程关闭窗口 一个进程结束字符命令界面 一条命令一般就是一个进程命令行尾回车 一个进程开始命令执行结束 下一命令提示符出现 一个进程结束编程级 进程建立 建立进程 函数或系统调用进程结束 撤消进程 函数或系统调用 或者程序的正常或非正常结束 进程和程序的区别 程序静态的 进程是动态的 程序和进程的组成不同 进程 程序 数据 PCB程序的存在是永久的 程序的存在是暂时的 一个程序可以对应多个进程 一个进程可包含多个程序 进程的特征 动态性 进程是个动态的概念 有一定的生命周期 要经历创建 执行 撤销过程 结构性 它由进程控制块 程序段和数据段组成 并发性 在一个系统内可以同时存在多个进程 它们通过交替使用处理器 从而实现并发执行 异步性 指进程之间在交替使用计算机资源时没有强制的顺序 按各自独立的 不可预知的速度向前推进 独立性 进程是系统分配资源和进行调度的独立单位 3 2 2进程的状态 进程从创建而产生至撤销而消亡的整个生命周期 可用一组状态加以刻画 按进程在执行过程中的状况至少定义三种不同的进程状态 运行态 Running 就绪状态 Ready 阻塞状态 Blocked 当前进程已经分配到CPU 它的程序正在处理机上执行的状态 已具备运行条件 但因为其他进程正在占用CPU 使它暂时不能运行而处于等待分配CPU的状态 进程因等待某种事件发生 例如等待I O操作完成 等待其他进程发来的信号 而暂时不能运行的状态 也就是说 处于阻塞状态的进程尚不具备运行条件 即使CPU空闲它也无法使用 3 2 2进程的状态 引起进程状态转换原因就绪 运行时间一到 调度程序选择一个新的进程运行运行 就绪运行进程用完了时间片 运行进程被中断 因为一高优先级进程处于就绪状态 3 2 2进程的状态 引起进程状态转换原因运行 阻塞当一进程所需的东西必须等待时对一资源的访问尚不能进行初始化I O且必须等待结果等待某一进程提供输入阻塞 就绪当所等待的事件发生时 3 2 2进程的状态 进程三种状态的转换 3 2 2进程的状态 有一个计算机科学家 有一天女儿过生日 想亲手给女儿做一个生日蛋糕 所以他就找了一本有关做蛋糕的食谱 买了一些原料 面粉 鸡蛋 糖 香料等 然后边看边学边做 食谱 程序 科学家 CPU 原料 数据 做蛋糕 进程 这时小儿子哭着跑进来 说手被蜜蜂蛰了 教授只好把蛋糕先放在一边 他在食谱上做了个标记 把状态信息记录了起来 然后又去找了一本医疗手册 查到了相关的内容 按照上面的指令一步步地执行 当伤口处理完之后 又回到厨房继续做蛋糕 CPU从一个进程 做蛋糕 切换到另一个进程 医疗救护 3 2 2进程的状态 五状态模型 新建态 就绪态 允许进入运行态 完成态 执行完 3 2 2进程的状态 问题出现进程挂起 suspend 进程不断创建 系统资源已不满足进程运行的要求 系统就必须把某些进程挂起 即将进程对换到磁盘中 暂时不参与进程调度 已达到平衡操作系统负荷的目的 引起进程挂起原因 P45 46 1 4 挂起 Suspend 把一个进程从内存转到外存 激活 Activate 把一个进程从外存转到内存 引入挂起状态后的七状态模型 Linux进程的状态 DUninterruptiblesleep usuallyIO RRunningorrunnable onrunqueue SInterruptiblesleep waitingforaneventtocomplete TStopped eitherbyajobcontrolsignalorbecauseitisbeingtraced Xdead shouldneverbeseen ZDefunct zombie process terminatedbutnotreapedbyitsparent high priority notnicetootherusers Nlow priority nicetootherusers Lhaspageslockedintomemory forreal timeandcustomIO sisasessionleaderlismulti threaded usingCLONE THREAD likeNPTLpthreadsdo isintheforegroundprocessgroup 例题 1 如果系统中有N个进程 运行的进程最多几个 最少几个 就绪进程最多几个最少几个 等待进程最多几个 最少几个 解答 在单处理机系统中 处于运行状态的进程最多为1个 最少为0个 处于就绪进程最多为N 1个 最少为0个 处于阻塞的进程最多为N个 最少为0个 2 有没有这样的状态转换 为什么 1 等待 运行 2 就绪 等待 3 2 3进程控制块 进程描述 进程控制块程序和数据组成了进程的实体 静态文本 需要一个数据结构来描述进程当前状态 本身特性 对资源的占用以及调度信息等 即进程控制块 ProcessControlBlock PCB 进程 程序 数据 PCB 3 2 3进程控制块 3 2 3进程控制块 PCB是进程存在的唯一标志 PCB常驻内存 CPU在进程之间的切换 PCB的组织 链表 同一状态的进程其PCB组成一链表 多个状态对应多个不同的链表 各状态的进程形成不同的链表 就绪链表 阻塞链表 链表 PCB的组织 PCB的组织 索引表 同一状态的进程归入一个index表 由index指向PCB 多个状态对应多个不同的index表各状态的进行形成不同的索引表 就绪索引表 阻塞索引表 3 2 3进程控制块 PCB的组织索引表 补充 PCB和进程的代码数据放在一起吗 系统态和用户态系统空间和用户空间 3 3进程控制 OS如何管理和控制进程必须知道进程的位置 依赖于所使用的存储管理方案 必须知道进程的属性 PCB 必须能够创建 撤销进程必须能够改变进程的状态 进程控制的职责 进程的创建进程的撤消进程的阻塞与唤醒进程控制是通过执行各种原语来实现的 3 3进程控制 原语是由若干条机器指令构成的 用于完成特定功能的一段程序 原语在执行过程中是不可分割的 P47 3 3进程控制 3 3 3进程的创建 进程图 引起创建进程的事件 进程的创建过程 1 2 3 3 3 3进程的创建 A B C D E I J F H L M K G 入口 PCB i 入就绪队列 返回 Y N 进程创建 include includepid tfork void 功能 创建一个新的进程 返回值 在子进程中为0 在父进程中为子进程ID 出错为 1 进程创建 该函数被调用一次 但返回两次 两次返回的区别是子进程的返回值是0 而父进程的返回值则是子进程的进程ID一般来说 在fork之后是父进程先执行还是子进程先执行是不确定的 这取决于内核所使用的调度算法 新创建的子进程是父进程的完全克隆 会复制父进程的数据段 堆 栈空间 共享代码段 进程相关术语 init进程领养 当父进程在子进程结束前结束 子进程变成了孤儿进程 孤儿进程被init进程收养 子进程的父进程就变成了init进程 僵尸进程当子进程在父进程结束前结束 如果父进程没有释放子进程的资源 默认 那么子进程就变成了一个僵尸进程 进程创建 3 3 4引起进程终止的事件 寿终 进程运行完自行退出 自杀 进程因错误而自行退出 3 3 2引起进程终止的事件 他杀 进程被其它进程强行杀死或由用户杀死 处决 进程因异常而强行终结 检索相应的PCB 读其状态若处于执行状态 则终止执行若有子孙进程则终止子孙进程释放终止进程的全部资源将PCB从队列中移出 3 3 4进程的终止过程 3 3 3进程的阻塞与唤醒 1 引起进程阻塞的事件 2 进程阻塞的过程 3 进程唤醒的过程 4 唤醒原语的执行过程 引起进程阻塞的事件 启动某种操作 请求系统服务 新数据尚未到达 无新工作可做 执行状态的进程调用阻塞原语进程变为阻塞状态PCB进入阻塞队列转进程调度程序 进行切换 进程阻塞的过程 被阻塞进程期待的事件发生 由发现者进程调用唤醒原语唤醒阻塞进程 阻塞进程进入就绪状态 进程唤醒的过程 3 3进程控制 Linux进程控制原语 进程创建fork进程监控ps进程终止kill 3 4线程 线程的引入进程 资源分配单位和CPU调度单位缺点 时间空间开销大 限制并发度的提高将程序块的执行从进程中分离出来程序块执行需要单独的 执行状态 寄存器内容 栈 局部内存程序块执行不需要单独的 进程资源 如文件 页表内容等多线程 将一个程序分成多个并发的活动 程序块 3 4线程 进程 线程 资源集进程作为拥有资源的基本单位 线程是系统调度的基本单位 3 4线程 进程和线程资源所有权 Process 调度的实体 Thread 3 4线程 线程描述线程状态 运行 就绪 等待 一个执行栈未运行时保存的线程上下文 静态存储局部变量对内存和其他进程资源的访问与该进程中其他线程共享资源 3 4线程 用户级线程由应用程序 线程库 实现线程管理 POSIXPthreads Win32threads 内核感觉不到线程的存在优点共享一个进程用户空间中 线程管理不需要内核模式的切换可运行任何OS上 内核无需修改 缺点全阻塞不能运用多处理技术 3 4线程 用户级线程 内核级线程 在处理机上被调度和执行的对象 由内核实现线程管理克服了用户级线程的缺点线程切换需要到内核的模式切换 3 4线程 内核级线程 3 4线程 3 4线程 程序 进程 线程的比较程序 一组有序指令的集合进程 系统分配资源的基本单位线程 处理机调度的基本单位 3 4线程 3 4线程 多线程编程优点 响应程度高资源共享经济多处理器体系结构利用 3 5处理器调度 请思考 我们是如何确定在任意时刻到底哪个进程执行 哪个不执行呢 进程管理的一个主要任务就是选择下一个要运行的进程 要解决的问题WHAT 按什么原则分配CPU 进程调度算法WHEN 何时分配CPU 进程调度时机HOW 如何分配CPU 进程调度方式 3 5处理器调度 WHAT 选择进程调度算法的标准 CPU利用率用户程序响应时间系统吞吐量公平合理设备利用率 WHEN 进程调度时机 时间片过期进程退出进程阻塞I O中断发生 HOW 进程调度方式 1 非抢占方式 简单 实时性差2 抢占方式 1 时间片原则 2 优先权原则 3 短作业优先原则 处理器调度的层次 1 CPU利用率CPU利用率 CPU有效工作时间 CPU总运行时间 CPU有效工作时间 CPU有效工作时间 CPU空闲等待时间 2 吞吐量 特别用于批处理 使得单位时间内处理的作业数尽可能多 选择调度算法的原则 面向系统 3 周转时间从作业提交给系统开始 到作业完成为止的时间间隔称作作业周转时间 作业周转时间 ti tf ts实际上 ti是作业在系统里等待时间和运行时间之和 平均作业周转时间 选择调度算法的原则 面向用户 4 响应时间交互式进程从提交一个请求到接收到响应之间的时间间隔 5 公平性确保每个用户每个进程获得合理的CPU份额和其它资源份额 不会出现饿死的情况 选择调度算法的原则 面向用户 调度算法一 FCFS 1 先来先服务 First come first served FCFS 最先进入就绪进程首先分配到CPU FCFS策略可用FIFO队列实现缺点 只顾及到等候时间 没有考虑要求服务时间长短 不利于短作业 例 如下一组进程P1 P2 P3 到达系统的先后顺序分别如下面三图所示 计算各种顺序的平均周转时间 P1 P2 P3T 28 36 38 3 34P2 P1 P3T 9 36 38 3 27 6P3 P2 P1T 3 11 38 3 17 3可见 FCFS算法的平均作业周转时间与作业提交及调度的顺序有关 调度算法二 SJF 2 短作业优先 shortest job first SJF 以进入系统的作业所要求的CPU时间长短为标准 总是选取估计计算时间最短的作业投入运行 采用SJF调度 P4 P1 P3 P2T 13ms采用FCFS调度 P1 P2 P3 P4T 16 25ms SJF 缺点 难以精确估计作业所需CPU时间 如程序员估计过低 系统可能提前终止该作业 忽视作业等待时间 由于系统不断接受新作业 而调度算法又总选计算时间短的作业投入运行 因此 使进入系统时间早但计算时间长的作业等待时间长 会出现饥饿现象 可抢占式SJF算法 SRTF 当一个新作业到达就绪队列 如果新作业需要的CPU时间短 则强行赶走当前作业 这种算法也叫最短剩余时间优先算法 shortestremainingtimefirst SRTF SRTF P1 P2 P4 P1 P3T 13msSJF P1 P2 P4 P3T 14 25ms 调度算法三 HRRF 3 高响应比优先调度 HighestResponseRatioFirst HRRF FCFS和SJF都是比较片面和调度算法 FCFS只考虑作业等候时间而忽视了作业计算时间 SJF正好相反 本算法是一种折衷算法 既考虑作业等待时间 又考虑作业运行时间 这样既照顾了短作业又不使长作业等待时间过长 改进了调度性能 HRRF 响应比 响应时间 要求服务时间 等待时间 运行时间 运行时间 1 等待时间 运行时间缺点 每次计算各道作业的响应比会有一定时间开销 性能比SJF略差 SJF P1 P3 P4 P2T 25msFCFS P1 P2 P3 P4T 28 75msHRRF P1 P3 P2 P4T 26 25ms 调度算法四优先级调度算法 优先级可以通过内部或外部方式来定义 内部优先级使用一些可测量数据以计算进程优先级 外部优先级是通过操作系统之外的准则来设置的 优先级调度可以是可抢占的或者非抢占的 静态优先级 创建进程时就确定 直到进程终止前都不改变 通常是一个整数 依据 进程类型 系统进程优先级较高 对资源的需求 对CPU和内存需求少的优先级较高 用户要求 紧迫程度和付费多少 动态优先级 在创建进程时赋予优先级 在进程运行过程中可以自动改变 以后便获得更好的调度性能 如 在就绪队列中等待时间延长则优先级提高 使优先级较低的进程在等待足够了的时间后 其优先级提高到可被调度执行 进程每执行一个时间片 就降低其优先级 优先级调度算法P2 P5 P1 P3 P4T 12 优先级调度算法 缺点 无穷阻塞 indefiniteblocking 或饥饿 starvation 解决方案之一 老化 在1973年关闭MIT的IBM7094时 发现有一个低优先级进程是于1967年提交但是一直未运行 调度算法五 RR 4 轮转法调度 Round robin RR 系统将所有的进程按先进先出的原则排成一个队列 将新来的进程加到就绪队列的末尾 每当执行调度时 调度程序从就绪队列中选第一个进程 分配一个时间片 将CPU分配给进程 时间片一般为10ms 100ms RR 进程需要CPU的时间小于一个时间片的时间 进程本身会释放CPU 进程调度程序接着处理就绪队列的下一个进程 进程所需CPU的时间大于一个时间片的时间 定时器会切断当前进程 进行上下文切换 该进程被加到队列尾部 接着进程调度程序选择就绪队列中的下一下进程 RR 注 时间片为4ms P1 P2 P3 P1 P1 P1 P1 P1T 15 67ms RR 如果时间片太小 以至于大多数进程都不可能在一个时间片内运行完毕 切换就会频繁 系统开销显著增大 所以 从系统效率来看 时间片取大一点好 如果时间片较大 那么 随着就绪队列里进程数目的增加 轮转一次的总时间增大 亦即对每个进程的响应速度放慢了 所以 时间片大小