计算机操作系统汤小丹ppt课件.ppt

湘潭大学 第2章进程的描述与控制 在多道程序批处理系统和分时系统中 程序并不能独立运行 资源分配和独立运行的基本单位是进程 操作系统所具有的四大特征 并发 共享 虚拟 异步 也都是基于进程而形成的 并可从进程的观点来研究操作系统而形成所谓的进程观点 在操作系统中 进程是一个极其重要的概念 2 1前趋图和程序执行 前趋图前趋图 ProcedenceGraph 是一个有向无循环图DAG DirectedAcyclicGraph 用于描述进程之间执行的先后顺序 图中的结点可表示一条语句 一个程序段或进程 结点间的有向边表示在两结点之间存在的偏序或前趋关系 Pi Pj PimustcompletebeforePjmaystart 若 Pi Pj 则可以写成Pi Pj 称Pi是Pj的前趋 Pj是Pi的直接后继 没有前趋的结点称为初始结点 没有后继的结点称为终止结点 此外 每个结点有一权重 Weight 可用该结点所含的程序量或结点的执行时间来计量 该图的前趋关系为 P1 P2 P1 P3 P1 P4P2 P5 P3 P5 P4 P6P5 P7 P6 P7其中 P1是初始结点 P7是终止结点 程序顺序执行通常一个应用程序都由若干个程序段组成 每个程序段完成特定功能 程序执行时 必须按照某种先后次序逐个执行 仅当前一个程序段执行完毕后 才能执行后继程序段 例如 在进行计算时 总是先输入数据后 才能计算 计算完成后再打印结果 用结点代表各程序段的操作 结点I表输入操作 C表计算操作 P表打印操作 则上述各程序段的执行可用以下前趋图来表示 I1 C1 P1 I2 C2 P2 对于一个程序段中的多条语句来说 也有一个执行顺序问题 如下述的程序段 S1 a x yS2 b a 5S3 c b 1其中S2必须在a被赋值后才能执行 S3也只能在b被赋值后才能执行 S1 S2 S3 程序顺序执行时的特征顺序性 处理机的操作 严格按照程序所规定的顺序执行 即只有前一个操作结束后 才能执行后继操作 封闭性 程序是在封闭的环境下运行的 即程序在运行时 独占全机资源 因而机内各资源的状态 初试态除外 只有本程序才能改变 程序一旦运行 其执行结果不受外界因素影响 可再现性 只要程序执行时的环境和初始条件相同 当程序多次重复执行时 不论是从头到尾不停顿地执行 还是 停停走走 地执行 获得的结果是相同的 程序并发执行对一批程序进行处理时 可使它们并发执行 设结点Ii表输入程序 Ci表计算程序 Pi表打印程序 则下图描述了程序并发执行时的情况 其中的Ii 1 Ci Pi 1是重叠的 即它们可并发执行 程序段中语句并发执行 对于具有下述4条语句的程序段 S1 a x 2S2 b y 4S3 c a bS4 d c 6可以看出 S3必须在a和b被赋值后方能执行 S4须在S3之后执行 但S1和S2可以并发执行 因它们彼此互不依赖 S1 S2 S3 S4 程序并发执行时的特征 间断性 程序在并发执行时 因它们共享资源或为完成同一任务而相互合作 致使并发程序之间形成了相互制约的关系 这种关系导致并发程序具有执行 暂停执行 执行这种间断性的活动规律 失去封闭性 程序并发执行时 多个程序共享系统的各种资源 因而资源的状态将由多个程序来改变 使程序的运行失去了封闭性 不可再现性 由于失去封闭性 从而导致可再现性的失去 不可再现性的例子 设有2个循环程序A和B 它们共享一个变量N 程序A每执行一次时 做都N N 1操作 程序B则每执行一次时 都要执行print N 操作 然后再将N置0 A和B以不同的速度运行 这样 可能出现三种情况 设某时刻N的值为n 1 N N 1beforeprint N andN 0 sotheNisn 1 n 1 0 2 N N 1afterprint N andN 0 sotheNisn 0 1 N N 1betweenprint N andN 0 sotheNisn n 1 0 这说明程序并发执行时由于失去了封闭性 从而失去了可再现性 即程序经过多次执行后 虽然其执行时的环境和初始条件都相同 但得到的结果却各不相同 2 2进程描述 程序并发执行时 产生了一些新特征 致使一般的程序不能并发执行 例如 程序在执行中一旦受阻而停下来 系统无法保留该程序的现场 因而也就无法再恢复该程序的现场以继续执行 为使程序在多道程序环境下能并发执行 并能对并发执行的程序加以控制和描述 而专门配置了一个称之为 进程控制块 的数据结构 其中 存放了进程标识符 进程运行的当前状态 程序和数据的地址 以及能保存该程序运行时的CPU的环境信息 由程序段 数据段和进程控制块三部分构成了一个进程的实体 进程映像 一般情况下 进程实体简称为进程 2 2 1进程的定义和特征 进程的定义定义 进程是进程实体的运行过程 进程是系统进行资源分配和调度的一个独立单位 或者说进程是可并发执行的程序在一个数据集合上的运行过程 进程和程序是两个截然不同的概念 二者之间既着密切的联系 又相互区别 下面分析进程的特征 并与程序作一些对比 以动态的观点来理解进程是最基本的 注意区别进程 进程实体 程序这三个概念 进程的特征动态性 动态性表现为 进程由创建而产生 由调度而执行 因得不到资源而暂停执行 以及由撤消而消亡 可见 进程有一定的生命周期 而程序是一组有序指令的集合 并存放在某种介质上 本身无运动的含义 是一个静态实体 并发性 指多个进程实体同存于内存中 能在一段时间内同时运行 引入进程的目的正是为了使其程序能和其它进程的程序并发执行 而程序是不能并发执行的 是OS的重要特征 独立性 指进程实体是一个能独立运行的基本单位 同时也是系统中独立获得资源和独立调度的基本单位 凡未建立进程的程序 都不能作为一个独立的单位参加运行 异步性 指进程按各自独立的 不可预知的速度向前推进 这一特征导致了程序执行的不可再现性 OS必须管制和协调 2 2 2进程的基本状态及转换 1 进程的三种基本状态就绪状态 当进程已分配到除CPU之外的所需资源后 只要再获得处理机 便可立即执行 这时的进程状态称为就绪态 多个进程可同时处于就绪态 执行状态 指进程已获得处理机 其程序正在执行 阻塞状态 进程因某事件 如请求I O 申请缓冲空间等 的发生而暂停执行时的状态 有时也称为 等待 或 睡眠 状态 处于阻塞态的进程将排入阻塞队列 三种基本状态的转换 创建状态和终止状态创建状态 进程刚建立 尚未进入就绪队列时的状态 终止状态 进程已正常或异常结束 已从就绪队列中移出但未撤消时的状态 创建 终止 许可 释放 2 2 3挂起操作和进程状态的转换 不少系统中 进程只有上述五种基本状态 而有一些系统 基于某种需要又增加了一些新的进程状态 其中最重要的是挂起状态 所谓挂起状态 是指活动的进程暂时停止活动而处于静止的状态 引入挂起态可能是因下述的需要 终端用户的需要 父进程的需要 OS的需要 对换的需要 负荷调节的需要 活动阻塞 活动就绪 静止就绪 静止阻塞 执行 挂起 释放 激活 挂起 请求I O 释放 激活 挂起 调度 2 2 4进程管理中的数据结构 操作系统中用于管理控制的数据结构对于每个资源和进程都设置一个数据结构 用于表征其实体 称为资源信息表和进程信息表 内存 设备 文件 进程 内存表 设备表 文件表 进程1 进程2 进程n 进程1 进程2 进程n 进程实体及所用资源列表 进程控制块 PCB 的作用PCB是进程实体的一部分 是OS中最重要的记录型数据结构 记录了OS所需的 用于描述进程情况及控制进程运行所需的全部信息 PCB的作用是使一个在多道程序环境下不能独立运行的程序 成为一个能独立运行的基本单位 一个能与其他进程并发执行的进程 或者说 OS是根据PCB来对并发执行的进程进行控制和管理的 PCB是进程存在的唯一标志 PCB常驻内存 系统将所有的PCB组织成若干个链表 或队列 存放在OS中专门开辟的PCB区内 PCB的具体作用 作为独立运行基本单位的标志 能实现间断性运行方式 提供进程管理所需要的信息 提供进程调度所需要的信息 实现与其他进程的同步与通信 进程控制块中的信息进程标识符 进程的唯一标识 分为两种 1 外部标识符 由创建者提供 供用户 进程 访问该进程时使用 2 内部标识符 为方便系统而设置 处理机状态信息 处理机在运行时 许多信息都放在寄存器中 当前进程被中断时 这些信息必须保存在被中断进程的PCB中 以便该进程重新执行时 能从断点继续 这组寄存器包括 1 通用寄存器 2 指令计数器 3 程序状态字PSW 4 用户栈指针 进程调度信息 包括与进程调度和进程对换有关的信息 1 进程状态 2 进程优先级 3 进程调度所需的其他信息 4 事件 指进程由执行态转变为阻塞态所等待发生的事件 即阻塞原因 进程控制信息 1 程序和数据的地址 内 外存地址 2 进程同步和通信机制 信号量等 3 资源清单 4 链接指针 下一个进程的PCB首地址 进程控制块的组织方式线性方式 把系统中所有PCB组织在一张线性表上 链接方式 把具有相同状态的PCB 用其中的链接字链接成一个队列 索引方式 系统根据所有进程的状态 建立几张索引表 2 3进程控制 操作系统内核现代OS的结构采用层次式结构 通常将一些与硬件紧密相关的模块诸如中断处理程序等和运行频率较高的模块如时钟管理 进程调度等都安排在紧靠硬件的软件层次中 使他们常驻内存 并加以特殊保护 通常把这一部分模块称为OS内核 为防止OS和关键数据受到用户程序的破坏 常将处理机的执行状态分为系统态 管态 内核态 和用户态 目态 系统态 具有较高的特权 能执行一切指令 访问所有寄存器和存储区 用户态 具有较低特权的执行状态 只能执行规定的指令 访问指定寄存器和存储区 通常 用户程序运行在用户态 OS内核运行在系统态 进程控制是由OS内核实现的 OS的层次模型 低级处理机管理 进程调度 PV管理 存储管理 分配 释放 高级处理机管理 进程创建 撤消 通讯等 设备管理 I O调度等 裸机 信息管理 建立 撤消文件打开 关闭文件 读 写文件 用户程序 内核 OS内核包含如下功能 支撑功能 是提供给OS其他许多模块所需的一些基本功能 以支持这些模块工作 介绍三种最基本的支撑功能 1 中断处理 通常 内核只对中断进行 有限的处理 然后便转有关进程继续处理 2 时钟管理 OS的许多活动都依赖于时钟 3 原语操作 内核对某些操作的执行 采用原语实现 原语操作不可分割 资源管理功能1 进程管理 管理进程的功能模块的运行频率高 2 存储器管理 管理存储器功能模块运行频率高 3 设备管理 与硬件密切相关 进程的创建 1 进程的层次结构子进程由父进程创建 子进程可以继承父进程所拥有的资源 子进程被撤消时 应归还从父进程处获得的资源 撤消父进程时 也同时撤消其所有子进程 在PCB中都设有家族关系表项 以标明自己的父进程和所有的子进程 UNIX按分层来组织进程 WINDOWS没有进程层次结构的概念 使用句柄实现进程控制 2 进程图 ProcessGraph 进程图是用于描述进程家族关系的有向树 3 引起创建进程的事件为使程序能运行就必须为它创建进程 导致一个进程创建另一个进程的典型事件有以下四类 1 用户登录 在分时系统中 2 作业调度 在批处理系统中 3 提供服务 当运行中的用户提出某种服务请求后 系统将专门创建一个进程来提供服务 4 应用请求 该类事件是基于应用进程的需要 由它自己创建一个新进程 以便使新进程以并发方式完成特定任务 4 进程的创建 CreationofProcess 当OS发现要求创建新进程的事件后 便调用进程创建原语Creat 创建一新进程 其过程如下 1 申请空白PCB 2 为新进程分配资源 3 初始化PCB 4 将新进程插入就绪队列 进程的终止 1 引起进程终止 TerminationofProcess 的事件1 正常结束2 异常结束3 外界干预操作员或OS干预 父进程请求 父进程终止 2 进程的终止过程根据被终止进程的标识符 从PCB读出该进程的状态 若被终止进程正处于执行态 则立即终止执行 并置重新调度标志 将处理机分配给一新进程 若该进程有子孙进程 则一并终止 将该进程拥有的全部资源 归还其父进程或系统 将被终止进程的PCB从所在队列中移出 进程阻塞和唤醒 1 引起进程阻塞和唤醒的事件向系统请求共享资源失败 等待某种操作的完成 新数据尚未到达 等待新任务的到达 2 进程阻塞过程进程的阻塞是进程自身的一种主动行为 通过调用阻塞原语block 将自己阻塞 执行态 阻塞态 阻塞队列 Px Px Px Pz Py 就绪队列 调度程序 执行态 Py 阻塞事件 3 进程唤醒过程当被阻塞进程所期待的事件出现时 则有关进程调用唤醒原语wakeup 将等待该事件的进程唤醒 阻塞队列 Px Pz 将PCB由现行的阻塞态改为就绪态 就绪队列 Px Px Pa Pb 值得注意的是 block和wakeup是一对作用刚好相反的原语 必须成对使用 若在某进程调用了阻塞原语把自己阻塞 则必须在与之合作的另一个进程或其他相关进程中 调用唤醒原语来唤醒进程 否则 被阻塞进程将会因不能被唤醒而长久地处于阻塞状态 从而再无机会运行 进程的挂起与激活 1 进程的挂起过程 当出现引起进程挂起的事件时 系统将用挂起原语suspend 将指定进程或处于阻塞状态的进程挂起 即由活动状态转为静止状态 2 进程的激活过程 当发生激活进程的事件时 系统利用激活原语active 将指定进程激活 激活原语将先把进程从外存调入内存并转为活动状态 在采用抢占式调度方式中 若被激活进程的优先级比当前运行的进程高 则立即剥夺当前进程的运行 把处理机分配给被激活的进程 2 4线程的基本概念 20世纪60年代中期 在设计多道程序OS时引入了进程概念 解决了单处理机环境下程序并发执行的问题 20世纪80年代中期 提出线程 Threads 概念 改善单处理机环境下程序并发的程度 在多处理机环境下提高程序并行执行的程度 2 4 1线程的引入 进程的两个基本属性进程是一个可拥有资源的独立单位 进程是一个可以独立调度和分派的基本单位 程序并发执行所付出的时空开销创建进程时分配资源 撤销进程时回收资源 进程切换时要保留或设置CPU环境 这限制了并发程度的进一步提高 线程 作为调度和分派的基本单位将进程的两个属性分开 即作为调度和分派的基本单位就不作为独立分配资源的单位 而对拥有资源的基本单位 则使之切换不频繁 这样 产生了线程的概念 即线程作为调度和分派的基本单位 线程是进程中的一个实体 是被系统独立调度和分派的基本单位 2 4 2线程与进程的比较 线程具有许多传统进程的特征 故又称为轻型进程或进程元 而把传统进程称为重型进程 相当于只有一个线程的任务 在引入线程的OS中 进程都有若干个线程 至少也有一个线程 调度的基本单位线程是调度和分派的基本单位 而进程是资源拥有的基本单位 因而线程是能独立运行的基本单位 线程切换的代价远低于进程切换的代价 在同一进程中 线程的切换不会引起进程的切换 但由一个进程中的线程切换到另一进程中的线程时 将会引起进程切换 并发性进程之间可以并发执行 一个进程中的多个线程之间 也可以并发执行 拥有资源进程拥有自己的资源 线程本身基本上不拥有系统资源 多个线程可共享同一进程的资源 独立性每个进程拥有一个独立的地址空间和其他资源 同一进程中的不同线程共享进程的地址空间和资源 系统开销OS为进程所付出的开销要远大于线程 支持多处理机系统 2 4 3线程的状态和线程控制块 线程运行的三个状态执行态 线程已获得处理机正在运行 就绪态 线程已具备执行条件 只需获得CPU便可执行 阻塞态 线程在执行中受阻 而处于暂停状态 线程控制块 TCB 系统为每个线程配置一个线程控制块 记录在TCB中的信息有 线程标识符一组寄存器线程运行状态优先级线程专有存储区信号屏蔽堆栈指针 多线程OS中进程属性进程是一个可拥有资源的基本单位 多个线程可并发执行 进程已不是可执行的实体 2 4 4线程的类型和多线程模型 线程的类型 用户级线程 ULT 内核支持线程 KST 很多系统都提供了对ULT和KST的支持 但由于连接方式不同 形成了不同类型的多线程模型 多对一模型一对一模型多对多模型 2 5线程的实现 2 5 1线程的实现方式线程已在许多系统中实现 有的系统实现的是用户级线程 有的是内核支持线程 有的则同时实现UL和KST 内核支持线程KST是在内核支持性运行的 其创建 阻塞 撤销和切换等 也是在内核空间实现的 在内核空间为每个内核线程设置一个线程控制块 内核根据该控制块感知线程的存在 并对线程进行控制 用户级线程用户级线程是在用户空间实现的 线程的创建 撤销 同步与通信等功能都无须内核的支持 即用户级线程与内核无关 在设置用户级线程的系统中 调度仍是以进程为单位进行的 组合方式线程有些OS提供了组合方式ULT KST线程 在该系统中 内核支持多个KST的建立 调度和管理 同时也允许用户应用程序建立 调度和管理 一些KST对应多个ULT 这是ULT多路复用KST来实现的 即将ULT对部分或全部KST进行多路复用 程序员可按应用需要和机器配置 对KST数目进行调整 以达到较好效果 2 5 2线程的实现 内核支持线程的实现在仅设置了内核支持线程的OS中 一种线程控制方案是 系统在创建一个新进程时 便为它分配一个任务数据区 PTDA 其中包括若干个TCB空间 TCB保持在内核空间 当进程要创建一个