处理机调度基本概念

2019-07-14 12:33发布

处理机调度:

多道程序环境下,动态的把处理机分配给就绪队列中的一个进程使之执行。 提高处理机的利用率、改善系统性能,很大程度上取决于处理机调度的性能。 处理机调度便成为OS设计的中心问题之一。分配的任务由处理机调度程序完成。

一、处理机调度的基本概念

作业进入系统驻留在外存的后备队列上,再至调入内存运行完毕,可能要经历下述三级调度。
  • 高级调度(High Scheduling)
  • 中级调度(Intermediate-Level Scheduling)
  • 低级调度(Low Level Scheduling)

1、高级调度(High Scheduling)

又称作业调度长程调度(Long-Term Scheduling),接纳调度(Admission Scheduling)          主要在早期批处理阶段,处理在外存上的作业。 决定外存后备队列中的哪些作业调入内存; 为它们创建进程、分配必要的资源; 将新创建的进程排在就绪队列上,准备执行。 作业调度决定的细节 在每次执行作业调度时,都须作出两个决定:
  • 接纳多少作业——取决于多道程序度。应根据系统的规模和运行速度等情况综合考虑。
  • 接纳哪些作业——取决于采用的调度算法。如先来先服务,短作业优先等
系统运行并不一定存在高级调度
  • 批处理系统:作业进入系统后先驻留外存,故需要有作业调度。
  • 分时系统:为及时响应,作业由终端直接送入内存,故不需作业调度。
  • 实时系统中,通常也不需作业调度。

2、低级调度(Low Level Scheduling)

也称为进程调度微观调度短程调度(Short-Term Scheduling)         决定内存就绪队列中的哪个进程获得处理机,进行分配工作。是最基本的一种调度,在三种基本OS中都有进程调度方式 1)非抢占方式(Non-preemptive Mode)          一旦处理机分配给某进程,该进程一直执行。决不允许其他进程抢占已分配运行进程的处理机。 2)抢占方式(Preemptive Mode)          允许调度程序根据某种原则,暂停某个正在执行的进程,将处理机重新分配给另一进程。   调度程序的任务职能:调度和分派。 (1) 记录系统中所有进程的有关情况 (PCB) (2) 确定分配处理机的原则 (算法) (3) 分配处理机给进程 (保存、更新cpu现场 (4) 从进程收回处理机     进场队列处理)

3、中级调度(Intermediate-Level Scheduling)

又称交换调度或中程调度(Medium-Term Scheduling)          引入目的:提高内存利用率和系统吞吐量。根据条件将一些进程调出或再调入内存。  

三种调度的频率和复杂度

  • 进程调度:运行频率最高,算法不能太复杂,以免占用太多的CPU时间。分时系统通常10~100ms便进行一次。
  • 作业调度:一个作业运行完毕退出系统时即触发重新调度一个新作业入内存,周期较长,大约几分钟一次。因而也允许作业调度算法花费较多的时间。
  • 中级调度:运行频率基本上介于上述两种调度之间。
三级调度比较  

4、调度队列模型

不论高级、中级或者低级调度,都涉及到进程队列,由此形成了三类调度队列模型。从这三种方式中体验调度的过程。
  • 仅有进程调度的调度队列模型
  • 具有高级和低级调度的调度队列模型
  • 同时具有三级调度的调度队列模型

1)仅有进程调度的调度队列模型

常见情况 分时系统。 通常仅设置进程调度,用户键入的命令和数据,都直接送入内存。 调度对象 处于就绪状态的进程。 组织形式 栈、树或一个无序链表 用何种形式取决于OS类型和采用的调度算法。如:分时系统中把就绪进程组织成FIFO队列形式:按时间片轮转方式运行。 每个进程在执行时按规定的时间片算法,在给定时间片内任务有三种执行情况:
  • 完成工作,释放处理机进入完成状态
  • 未完成,将该任务再放入就绪队列末尾
  • 因某事件而被阻塞,被OS放入阻塞队列
进程调度什么时候发生?或者说什么时候需要进程调度程序执行去给CPU做选择?
  • 正在执行的进程结束
  • 正在执行的进程阻塞
  • 正在执行的进程未完成转就绪(时间片到)
  • 新就绪了更高优先级的进程(抢占式)

2)具有高级和低级调度的调度队列模型

批处理系统中,还需要作业调度

3)同时具有三级调度的调度队列模型

引入中级调度后,进程的状态变化:
  • 就绪状态:分为内存就绪和外存就绪。
  • 阻塞状态:分为内存阻塞和外存阻塞。
        中级调度使进程在上述状态间变化,并使数据在内外存间互换。  

5. 选择调度方式和调度算法的若干准则

什么算法是好算法? :不同的情况和对象需求不同,适用的方式和算法也不同。
  • 1)面向用户的准则     
  • 2)面向系统的准则

1)面向用户的准则

周转时间短:         针对批处理系统的性能指标。作业从提交到完成所经历的时间。 CPU执行用时Ts 总的等待时间Tw = 在后备队列中等待 + 就绪队列上等待 + 阻塞队列中等待(等待I/O操作用时) 周转时间T=Ts+Tw 带权周转时间W= T/Ts 平均周转时间 平均带权周转时间
  • 响应时间快:针对分时系统。用户输入一个请求(如击键)到系统给出首次响应(如屏幕显示)的时间
  • 均衡性:系统响应时间的快慢与用户所请求的复杂性相适应。
  • 截止时间的保证:针对实时系统的性能指标。开始截止时间和完成截止时间。任务必须按规定的时间开始或完成,调度方式和算法必须能保证该要求。
  • 优先权准则:三大基本OS在调度算法的选择时都可遵循。可以使关键任务达到更好的指标。

2)面向系统的准则

  • 系统吞吐量高:批处理系统的重要指标
         单位时间内所完成的作业数,跟作业本身(与作业平均长度密切相关)和调度算法都有关系;
  • 处理机利用率好(主要针对大中型主机)
  • 各类资源的平衡利用(主要针对大中型主机)
不同系统需求各有侧重 批处理系统
  • 平均周转时间短
  • 系统吞吐量高
  • 处理机利用率好
分时系统
  • 响应时间快
  • 均衡
实时系统
  • 截至时间的保证
  • 可预测性
  处理机调度相关基本概念完