进程的描述及处理器调度.ppt

第二讲进程的描述处理器调度 教学目标 了解进程的基本概念熟悉进程的几种状态及转换原因掌握处理器调度的各种算法 2 1进程2 1 1前趋图和程序执行1 前趋图有向无循环图每个结点表示一条语句 一段程序或一个进程结点间的有向边表示两结点的前趋关系 即进程执行的先后顺序 1为初始结点 4为终止结点例 1表示输入进程 2 3分别表示乘法 加法运算 4表示输出进程 并发程序设计 顺序程序设计使一个程序分成若干个可同时执行的程序模块的程序设计方法称为并发程序设计 相应 串行运行程序方法称为顺序程序设计 特点间断性 共享资源导致程序 执行 暂停 执行 失去封闭性 并发执行以及共享资源可能导致结果变化不可再现性 不同次执行结果可能不一致 程序并发执行的条件两段程序间无共享变量或对共享变量仅有读操作 2 1 2进程的描述与特点进程的定义一个具有一定独立功能的程序在一个数据集上的一次执行一段程序和它执行时处理的数据可与其它程序并发执行的程序的一次执行 例如 某一算题为将一千个字符输入到缓冲区 处理后输出到磁带 按并发程序设计思路将该算题分成 模块1 循环执行 读入1000个字符到输入缓冲区 模块2 循环执行 处理输入缓冲区中1000个字符 然后将1000个字符送输出缓冲区 模块3 循环执行 取出输出缓冲区中1000个字符写到磁带 让这三个模块同时并发进行 2 进程的形成例如 P为一编译程序 同时为甲 乙两程序服务 假定编译程序P从a点开始工作 现在正在编译源程序甲 当工作到b点时程序P等待磁盘传输信息 这时利用处理器让编译程序P为源程序乙进行编译 编译程序仍从a点开始 虽然编译程序P只有一个 但是加工对象有甲 乙两个源程序 如果把编译程序P与服务对象联系起来 则程序P为甲服务就说构成了进程P甲 程序P为乙服务就说构成了进程P乙 3 进程的属性结构 同一程序运行在不同数据集上时 构成不同的进程 它包含了数据集和运行在其上的程序及进程控制块 PCB 并发性 多个进程可以并发执行 交替执行 走走停停 即一个进程已开始工作但尚未结束之前 另一个进程可以开始工作 交往性 若干个进程间可以相互交往制约 表现为内部逻辑上协调关系及共享资源的间接关系 动态性 进程是动态的 有 个生命期 由创建而产生 由调度而执行 由撤销而消亡 异步性 各进程按独立 未知的速度发展 导致不可再现性 同一程序运行在不同数据集上时 构成不同的进程 4 进程的基本状态在单处理器系统中 并发进程轮流占用处理器 由于发生事件引起状态变化 进程的三种基本状态 等待 阻塞态 因某事件发生而暂停 等待该事件完成 就绪态 所需资源均已备齐 等待系统分配中央处理器 以便运行 运行态 占有中央处理器正在运行 进程的状态变化运行态 等待态等待态 就绪态就绪态 运行态注意 只有处于就绪态的进程 才有可能转换为运行态 处于等待态的进程在等待结束后只能进入就绪态 不能直接进入运行态 处于就绪态的进程只能转换为运行态 而不能再进入等待态 2 1 3进程控制块PCB每一个进程都设置一个 进程控制块 操作系统通过进程控制块来描述各进程的运行情况 并以此为依据决定如何管理和控制进程运行 进程控制块是一个进程存在的唯一标志 最基本的进程控制块如图所示 PCB1 4 PCB2 PCB8 PCB7 PCB6 PCB5 PCB4 PCB3 3 0 1 0 9 7 8 PCB9 运行态队列 等待态队列 就绪态队列 空闲队列 索引方式各种状态建立独自的索引表 每个表目记录相应PCB在PCB表中地址 2 1 4进程的控制进程的创建每一个进程都有生命期 即从创建到消亡 当一个程序模块获得一个数据块和一个进程控制块后就说创建了一个进程 进程的创建过程申请PCB为新进程分配内存初始化PCB将新进程插入就绪队列 进程的终止当一个进程完成了特定的工作后 收回它所占的数据块和一个进程控制块 即撤销了一个进程 终止过程选择新进程占用处理机将子孙进程终止将所有占用资源归还给父进程或系统将该进程从所在队列移出 等待过程从运行态转为等待态 加入等待队列唤醒过程使用唤醒原语从等待队列中移出 将PCB中状态改为就绪 插入就绪队列 进程的激活从静止阻塞态变为活动阻塞态 等待转为就绪态 从静止就绪态转为活动就绪态 等待CPU调度选中 进程状态转换图 3 1处理机调度的基本概念3 1 1调度类型一 高级调度即作业调度或长程调度 接纳调度 从外存调度选中若干个作业进入内存 并建立进程 插入到就绪队列中分时系统与实时系统无需作业调度所做工作包括 根据多道程度确定选中作业的道数 根据调度算法确定选中哪些作业 二 低级调度即进程调度或短程调度 处理器调度调度方式有 抢占方式抢占原则有 非抢占方式 时间片原则 短作业优先 优先权原则 三 中级调度又称中程调度 即存储管理中的对换将暂时不运行的进程先调至外存置为挂起 等内存空闲再把它们从外存调入改为就绪态 3 1 2选择调度方式与调度算法的若干准则一 面向用户准则1 周转时间带权周转时间W 周转时间T 系统服务时间Ts2 响应时间 3 截止时间 最迟开始时间 4 优先权二 面向系统的准则1 系统吞吐量2 处理机利用率3 各类资源的平衡利用 3 2调度算法一 先来先服务法 FCFS 按照进程进入就绪队列的先后次序来选择进程从后备队列选中作业进入内存利于CPU繁忙的作业对长作业进程有利 对短作业不利周转时间 完成时间 到达时间带权周转时间 周转时间 服务时间 二 时间片轮转法 规定一个时间片 如10毫秒 每个进程轮流地运行一个这样的时间片 当这个时间片结束时 就强迫当前运行的进程退出处理器 让其他进程运行 实现方法是使用内部间隔时钟保证所有进程均能获得时间片时间片的确定系统对时间的要求就绪进程的数目系统处理能力 三 最高优先权法每一个进程给出一个优先数 处理器调度每次选择就绪进程中优先数最小者 让它占用处理器运行 该调度算法又分两种 非抢占式适用于批处理系统或要求不严的实时系统 抢占式适合紧迫作业需求及要求较高的实时 分时系统 优先权的确定 静态优先数法进程创建时确定 在运行期间不变例如 系统进程 运行时间短或内存需求小的进程优先权高通常优先数越高优先权越低 动态优先法创建时的优先数可随进程运行发生变化 四 短作业 进程 优先法用于作业调度与进程调度降低作业平均等待时间 提高系