处理机调度目标

共同目标: * 资源利用率 * 公平性 * 平衡性 * 策略强制执行

批处理系统目标: * 平均周转时间短 * 系统吞吐率高 * 处理机利用率高

分时系统目标 * 相应时间快 * 均衡性

实时系统目标 * 截止时间的保证 * 可预测性

进程调度

进程调度也是对系统性能影响最大的一种处理机调度 进程调度的步骤(任务)主要有: 1. 保存处理机的现场信息 2. 按某种算法选取进程 3. 把处理器分配给进程

进程调度方式 非抢占式:一旦将处理机分配个某进程,无论运行多长时间,决不同意由于时钟中断而抢占处理机,也不同意其它进程抢占已经分配给他的处理机 抢占式:同意调度程序基于某种原则而暂停当前正在占用处理机的进程,而将处理机分配给其它的进程

调度算法 轮转调度算法(RR) 在轮转(RR)法中,系统将所有的就绪进程按FCFS策略排成一个就绪队列. 系统可设置每隔一定时间(如30 ms)便产生一次中断,去激活进程调度程序来进行调度,把CPU分配给就绪队列的队首进程,并令其执行一个时间片。 当进程运行完毕后,又把处理机分配给就绪队列中新的队首进程,也让它执行一个时间片。 这样,就可以保证就绪队列中的所有进程在确定的时间段内,都能获得一个时间片的处理机时间

优先级调度算法 优先级进程调度算法,是把处理机分配给就绪队列中优先级最高的进程 算法分为抢占式和非抢占式 优先级分为静态优先级和动态优先级

多队列调度算法 低级调度算法是固定的、单一的,无法满足系统中不同用户对进程调度策略的不同要求,在多处理机系统中,这种单一调度策略实现机制的缺点更显突出,由此,多级队列调度算法能够在一定程度上弥补这一缺点

多级反馈队列调度算法 1. 设置多个就绪队列 2. 每个队列中都采用FCFS算法 3. 按队列优先级调度

如果规定第一个队列的时间片略大于多数人机交互所需之处理时间时,便能较好地满足各种类型用户的需要

基于公平原则的调度算法

实时调度

实现实时调度的基本条件 1. 提供必要的信息 2. 系统处理能力足够强 3. 采用抢占式调度机制 4. 具有快速切换机制

分类: 硬实时和软实时 抢占式 1. 基于时钟中断的抢占式优先级调度算法 2. 立即抢占的优先级调度算法

非抢占式 1. 非抢占式采用轮转调度算法 2. 非抢占式采用优先级调度算法

最早截止时间优先EDF(Earliest Deadline First)算法 非抢占式调度方式用于非周期实时任务 抢占式调度方式用于周期性实时任务

最低松弛度优先LLF(Least Laxity First)算法 主要用于可抢占调度方式

死锁

产生死锁的必要条件 1. 互斥条件 2. 请求和保持条件 3. 不可抢占条件 4. 循环等待条件

预防死锁 1. 破坏请求和保持条件 可通过如下两个不同的协议实现: (1) 该协议规定,所有进程在开始运行之前,必须一次性地申请其在整个运行过程中所需的全部资源。 (2) 该协议是对第一种协议的改进,它允许一个进程只获得运行初期所需的资源后,便开始运行。

  1. 破坏“不可抢占”条件 当一个已经保持了某些不可被抢占资源的进程,提出新的资源请求而不能得到满足时,它必须释放已经保持的所有资源,待以后需要时再重新申请

  2. 破坏“循环等待”条件 对系统所有资源类型进行线性排序,并赋予不同的序号

避免死锁 把系统的状态分为安全状态和不安全状态,当系统处于安全状态时,可避免发生死锁。反之,当系统处于不安全状态时,则可能进入到死锁状态. 利用银行家算法避免死锁

死锁的检测 系统死锁,可利用资源分配图来描述

死锁的解除 1. 终止所以死锁进程(代价较大) 2. 逐个终止进程 3. 付出代价最小的死锁解除算法




注:

  1. 内容仅供参考
  2. 参考教材:《计算机操作系统》(汤小丹)(第四版)
  3. 考试前匆忙整理,比较粗糙,请多担待
  4. 如有错误,请联系我