操作系统0x05-处理机调度
2.2 处理机调度
2.2.1 调度的概念
调度的基本概念
在多道程序系统中,进程的数量往往多于处理机的个数,因此进程争用处理机的情况在所难免。处理机调度是对于处理机进行分配,即从就绪队列中按照一定的算法选择一个进程,并将处理机分配给它运行,以实现进程并发地执行。
处理机调度是多道操作系统的基础,是操作系统设计的核心问题。
调度的层次
一个作业从提交到完成,要经历三级调度。
(1)作业调度(高级调度)
其主要任务是按照一定的原则,从外存上处于后备状态的作业中挑选一个或多个作业,给它们们分配内存、输入/输出设备等必要的资源,并建立相应的进程,以使它们获得竞争处理机的权利。简言之,作业调度就是内存与辅存之间的调度。
(2)内存调度(中级调度)
其作用是提高内存利用率和系统吞吐量。将那些暂时不能运行的进程调至外存等待,把此时的进程状态称为挂起态;当他们已具备运行条件且内存有空闲时,再由中级调度重新调入内存并修改其状态为就绪态,挂在就绪队列上等待。
(3)进程调度(低级调度)
主要任务是按照某种方法和策略从就绪队列中选取一个进程,将处理机分配给它。是操作系统中最基本的一种调度。
三级调度的联系
如上图。作业调度从外存的后备队列中选择一批作业进入内存,为它们建立进程,这些进程就被送入就绪队列;进程调度从就绪队列中选择一个进程,并把其状态改为运行态,把CPU分配给他;中级调度是为了提高内存利用率,系统将那些暂时不能运行的进程挂起来,当内存空间宽松时,通过中级调度选择具备运行条件的进程将其唤醒。
1>作业调度为进程活动做准备,进程调度使进程正常活动起来,中级调度将暂时不能运行的进程挂起,中级调度处于作业调度和进程调度之间。
2>作业调度次数少,中级调度次数略多,进程调度频率最高。
3>进程调度是最基本的,不可或缺。
2.2.2 进程调度方式
当某个进程正在处理机上执行时,若有某个更为重要或紧迫的进程需要处理,即有优先权更高的进程进入就绪队列,此时应该如何分配处理机?
非剥夺调度方式(非抢占方式) | 剥夺调度方式(抢占方式) |
---|---|
当一个进程正在处理机上执行时,即使有某个更为重要和紧迫的进程进入就绪队列,仍然让正在执行的进程继续执行,直到该进程执行玩或发生某种事件而进入阻塞态时,才把处理机分配给更为重要的进程。 | 当一个进程正在处理机上执行时,若有某个更为重要和紧迫的进程需要使用处理机,则立即暂停正在执行的进程,将处理机分配给这个更为重要的进程。 |
优点是实现简单系统开销小,适用于大多数的批处理系统。但不能用于分时系统和大多数的实时系统。 | 对提高系统吞吐率和响应速率都有明显的好处。 |
2.2.3 调度的基本准则
选择调度算法时,需要考虑的算法特性:
- CPU利用率
- 系统吞吐量:单位时间内CPU完成的作业数量。
- 周转时间=作业完成时间-作业提交时间
带权周转时间=作业周转时间/作业实际运行时间 - 等待时间:进程等待处理机的时间。
- 响应时间:从用户提交请求到系统产生响应的时间。
2.2.4 典型的调度算法
先来先服务(FCFS)调度算法
每次从就绪队列中选择最先进入该队列的进程。将处理机分配给它,使之投入运行,直至完成,或因某种原因而注册时才释放处理机。属于不可剥夺算法。
算法简单,但效率低,对长作业比较有利,但对短作业不利。有利于cpu繁忙型。作业而不利于IO繁忙型作业。
假设系统中有四个作业,他们的提交时间分别是8,8.4,8.8,9。运行时间依次是2,1,0.5,0.2。系统采用FCFS调度算法:
作业号 | 提交时间 | 运行时间 | 开始时间 | 等待时间 | 完成时间 | 周转时间 | 带权周转时间 |
---|---|---|---|---|---|---|---|
1 | 8 | 2 | 8 | 0 | 10 | 2 | 1 |
2 | 8.4 | 1 | 10 | 1.6 | 11 | 2.6 | 2.6 |
3 | 8.8 | 0.5 | 11 | 2.2 | 11.5 | 2.7 | 5.4 |
4 | 9 | 0.2 | 11.5 | 2.5 | 11.7 | 2.7 | 13.5 |
- 平均等待时间:1.575
- 平均周转时间:2.5
- 平均带权周转时间:5.625
短作业优先(SJF)调度算法
短作业优先(SJF)调度算法从后备队列中选择一个或若干个估计运行时间最短的作业,将它们调入内存运行。短进程优先(SPF)调度算法从就绪队列中选择一个估计运行时间最短的进程。将处理机分配给他,使之立即执行,直至完成或发生某事件而阻塞时,才释放处理机。
对长作业不利;未完全考虑作业的紧迫程度;SJF调度算法的平均等待时间和平均周转时间最少。
假设系统中有四个作业,他们的提交时间分别是8,8.4,8.8,9。运行时间依次是2,1,0.5,0.2。系统采用SJF调度算法:
作业号 | 提交时间 | 运行时间 | 开始时间 | 等待时间 | 完成时间 | 周转时间 | 带权周转时间 |
---|---|---|---|---|---|---|---|
1 | 8 | 2 | 8 | 0 | 10 | 2 | 1 |
2 | 8.4 | 1 | 10.7 | 2.3 | 11.7 | 3.3 | 3.3 |
3 | 8.8 | 0.5 | 10.2 | 1.4 | 10.7 | 1.9 | 3.8 |
4 | 9 | 0.2 | 10 | 1 | 10.2 | 1.2 | 6 |
- 平均等待时间:1.175
- 平均周转时间:2.1
- 平均带权周转时间:3.525
优先级调度算法
根据新的更高优先级进程能否抢占正在执行的进程,可分为:非剥夺式优先级调度算法、剥夺式优先级调度算法。
根据进程创建后优先级能否改变,可分为:静态优先级、动态优先级。
优先级设置的参照原则:系统进程>用户进程、交互型进程>非交互型进程、I/O型进程>计算型进程。
高响应比优先调度算法
主要用于作业调度,同时考虑了每个作业的等待时间和估计运行时间,是对FCFS和SJF的权衡。在每次作业调度中,选择响应比.最高的作业投入运行。
响应比Rp=(等待时间+要求服务时间)/ 要求服务时间
时间片轮转调度算法
主要适用于分时系统。系统将所有就绪进程按到达时间的先后次序排成一个队列,选择就绪队列中的第一个进程执行,但仅能执行一个时间片,在使用完一个时间片后,即使进程并未完成其运行,也必须释放出处理机给下一个就绪的进程,而被剥夺的进程发挥到就绪队列的末尾,重新排队,等候再次运行。
应选择适当的时间片大小。时间片过大:退化为FDFS。时间片过小:频繁切换进程,开销增大。
多级反馈队列调度算法
是时间片轮转调度算法和优先级调度算法的综合与发展。融合了前几种算法的优点。