第三章

3.1 调度的作用和级别

1.调度的作用

• 处理机调度的主要目的就是分配处理机；
• 进程调度：
  • 调度的功能是组织和维护就绪进程队列。
  • 分配的功能是指当处理机空闲时，从就绪队列队首中移出一个PCB，并将该进程投入运行；

2.调度级别：

• 1. 高级调度：作业调度，长期调度；
• 2. 中级调度：中期调度；
• 3. 低级调度：进程调度或短期调度；

3.2 作业调度(高级调度)

1. 作业状态：

• 1. 提交状态：系统向用户提交一个作业；
• 2. 后备状态：作业送入输入井中存放，等待进入内存；
• 3. 执行状态：作业被调入内存，并在CPU上执行；
• 4. 完成状态：完成计算任务，由系统回收资源，准备退出系统；

2.作业管理和调度

• 1. 作业控制块JCB
  • 1. 系统为每个作业设置了一个作业控制块（JCB）
  • 2. 记录该作业的有关信息；
  • 3. JCB时作业在系统中存在的标志；
• 2. 作业调度的功能
  • 记录系统中各个作业的情况
  • 按照某种调度算法从后备作业队列中挑选作业；
  • 为选中的作业分配内存和外设等资源；
  • 为选中的作业建立相应的进程，并把该进程放入就绪队列中
  • 作业结束后进行善后工作
• 主要功能：完成作业从后备状态到执行状态，以及从执行状态到完成状态的转换；

  3.3进程调度(低级调度)

• 1. 进程调度的主要功能：
  • 保存现场；
  • 挑选进程；
  • 恢复现场；
• 2. 进程调度的时机
  • 1. 任务完成；
  • 2. 等待资源；
  • 3. 运行到时；
  • 4. 发现重新调度的标志

3.4.两级调度模型

• 1. 作业调度是宏观调度；
• 2. 进程调度是微观调度；
• 队列图：

• 根本区别：两者执行的频率不同

3.5.三级调度模型图：

性能评价标准

1. 周转时间：从作业提交到作业完成的时间间隔

   • Ti= tci – tsi(tsi表示作业i的提交时间，亦即作业i到达系统的时间；tci表示作业i的完成时间 )

2. 平均周转时间：（主要）
   

3. 带权周转时间W：
   

4. 平均带权周转时间：(主要)
   

3.6常用调度算法

1. 先来先服务FCFS

• 特点：
  • 1. 比较适合长作业，不利于短作业；
  • 2. 容易实现，但效率较低；

2. 短作业优先(SJF)

• 分配CPU资源时，优先分配给运行时间短的作业；
• 特点：
  • 能有效的降低作业的平均等待时间；
  • 提高系统的吞吐量；
  • 对长作业不利，同时不能保证紧迫性作业会被及hi处理；

3. 优先级法

• 从就绪队列中选出优先级最高的进程，让他在CPU上运行；
• 1. 非抢占式优先级法
• 2. 抢占式优先级法；
  • 优先级确定：可有系统内部定义或外部指定 ；
• 确定进程优先级的方式——静态与动态
  • 静态方式
    • 静态优先级：是在创建进程时就确定下来了，并且不变；
    • 优先数——标示优先级的整数；优先数小，优先级高
  • 动态方式
    • 优先级随着进程的推进而不断改变；

4. 时间片轮转法

• 主要用于分时系统；
• 时间片以一种很小的时间单位， 通常为10~100ms数量级
  • 时间片的长短通常由以下四个因素确定：
    • 1. 系统的响应时间；
    • 2. 就绪队列进程的数目；
    • 3. 进程的转换时间；
    • 4. CPU运行指令速度；

3.7实时调度

1.实施任务类型

1. 根据对截止时间的要求：

• 硬实时任务： 任务必须满足任务对截止时间的要求；
• 软实时任务： 任务与预期的截止时间相关联，但不是绝对严格的；

2. 按照任务执行的是否呈现周期性规律

• 周期性任务：以固定的时间间隔出现的事件；
• 非周期性任务：事件的出现无法预计；

3. 可调度测试公式

2. 实时调度算法

• 分为静态和动态两种方式：
• 1.优先级随速率单调的调度算法
  • 每个周期性进程必须在其周期内完成；
  • 进程间彼此互不依存；
  • 每个进程在每次运行时需要相同的CPU时间；
  • 非周期性进程都没有截止时间限制；
  • 进程抢占瞬间完成，开销不计；
• 2. 最早截止时间优先调度算法
  • 角度程序把所有可以运行的进程按照其截止时间先后顺序妨碍一个表格上，执行调度时，就选择该表中的第一个进程——截止时间最近；

3.8 中断处理和系统调用

中断： 指CPU对系统发生的某一个事件做出的一种反应，它使CPU暂停正在执行的程序，保留现场后自动执行相关处理程序，处理完事件之后，如果被打断的事件的优先级最高，则返回断点继续执行被打断的程序；

中断的一些基本概念：

• 中断源：引发中断的事件或者发出中断请求的来源；
• 中断请求：中断源向CPU提出处理请求；
• 断点：发生中断时，被打断程序的暂停点；

中断类型：

• 中断：它有CPU以外的事件引起的，同时它也是异步的，中断的产生与正在执行的进程无关；
• 异常exception:它是来自CPU内部事件或者程序正在执行引发的事件的过程，具有同步性；

中断处理的过程

• 1. 中断响应——由硬件实施
  • 中止当前程序的运行；
  • 保存原程序的断点信息；
  • 转到相应的处理程序；
• 2. 中断处理 ——由软件实施
  • 保存被中断程序的现场：
    • 1. 集中式保存
    • 2. 分散式保存
  • 分析中断原因；
  • 转入相应的处理程序进行处理；
  • 恢复被中断的程序现场；
    • 1. 选取可以立即执行的进程；
    • 2. 恢复工作现场；

中断优先级和中断屏蔽

• 1. 中断优先级
  • 中断级：硬件设计时，一般把紧迫程度相似的中断源归并为一组；
  • 中断优先级：与某种中断相关的优先权；
• 2. 中断屏蔽
  • 1. 中断屏蔽：再提出中断请求之后，CPU不理睬；
  • 2. 中断禁止：在可引起中断的事件发生时系统不接受该中断的信号，因而就不可以提出中断请求而引起中断；
  • 3. 中断屏蔽的作用：
    • 延迟或者中断对某些中断的响应；
    • 协调中断响应和中断处理的关系；
    • 防止同类中断的相互干扰
• 3.多重中断
  • 多个中断同时发生，处理该终端的方法有两种：
    • 1. 顺序处理方式；
      • 当一个中断正在被处理期间，屏蔽其他中断，处理完当前中断之后再开放该中断，然后去处理其他未被处理过的中断；
    • 2. 嵌套处理方式；
      • 对每类中断赋予不同的优先级，允许优先级高的中断程序打断优先级低的中断的处理程序；

系统调用的处理

• 1. 陷入事件的处理方式
  • 在unix /linux 系统中，对异常处理称为陷入
    • 自陷——自愿进入陷入，如使用系统调用或者断点跟踪；
    • 捕俘——由程序执行过程中，出现软、硬件故障或错误—— 如：转换无效、访问违章、非法指令；
  • 陷入处理的基本过程与中断处理基本相同，即：
    • 中断响应——进入系统核心——进入陷入处理子程序(trap)——分别处理
    • trap子程序对所有陷入事件按如下四种方式分别进行处理：
      • 1. 请求系统管理人员干预；
      • 2. 按用户规定方式进行处理；
      • 3. 用户栈自动扩充；
      • 4. 系统调用处理；