在多道程序环境下,主存中有着多个进程,其数目往往多于处理机数目。这就要求系统能按某种算法,动态地把处理机分配给就绪队列中的一个进程,使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源,提高处理机的利
用率及改善系统性能(吞吐量、响应时间),在很大程度上取决于处理机调度性能的好坏,因而,处理机调度便成为操作系统设计的中心问题之一。
1 处理机调度的层次
在多道程序系统中,一个作业被提交后必须经过处理机调度后,方能获得处理机执行。对于批量型作业而言,通常需要经历作业调度(又称高级调度或长程调度)和进程调度(又称低级调度或短程调度)两个过程后方能获得处理机;对于终端型作业,则通常只需经过进程调度即可获得处理机。在较完善的操作系统中,为提高内存的利用率,往往还设置了中级调度(又称中程调度)。对于上述的每一级调度,又都可采用不同的调度方式和调度算法。对于一个批处理型作业,从进入系统并驻留在外存的后备队列开始,直至作业运行完毕,可能要经历上述的三级调度。
1.1 高级调度
高级调度(High Level Scheduling)又称为作业调度或长程调度(LongTerm Scheduling),其主要功能是根据某种算法,把外存上处于后备队列中的那些作业调入内存,也就是说,它的调度对象是作业。
1.2 低级调度
通常也把低级调度(Low Level Scheduling) 称为 进程调度或短程调度(ShortTermScheduling),它所调度的对象是进程(或内核级线程)。进程调度是最基本的一种调度,在多道批处理、分时和实时三种类型的 OS 中,都必须配置这级调度。
低级调度的主要功能如下:
(1) 保存处理机的现场信息。在进程调度进行调度时,首先需要保存当前进程的处理机的现场信息,如程序计数器、多个通用寄存器中的内容等,将它们送入该进程的进程控制块(PCB)中的相应单元。
(2) 按某种算法选取进程。低级调度程序按某种算法如优先数算法、轮转法等,从就绪队列中选取一个进程,把它的状态改为运行状态,并准备把处理机分配给它。
(3) 把处理器分配给进程。由分派程序(Dispatcher)把处理器分配给进程。此时需为选中的进程恢复处理机现场,即把选中进程的进程控制块内有关处理机现场的信息装入处理器相应的各个寄存器中,把处理器的控制权交给该进程,让它从取出的断点处开始继续运行。
进程调度中的三个基本机制:
(1) 排队器。为了提高进程调度的效率,应事先将系统中所有的就绪进程按照一定的方式排成一个或多个队列,以便调度程序能最快地找到它。
(2) 分派器(分派程序)。分派器把由进程调度程序所选定的进程,从就绪队列中取出该进程,然后进行上下文切换,将处理机分配给它。
(3) 上下文切换机制。当对处理机进行切换时,会发生两对上下文切换操作。在第一对上下文切换时,操作系统将保存当前进程的上下文,而装入分派程序的上下文,以便分派程序运行;在第二对上下文切换时,将移出分派程序,而把新选进程的 CPU 现场信息装入到处理机的各个相应寄存器中。
进程调度方式:
1) 非抢占方式(Nonpreemptive Mode)
2) 抢占方式(Preemptive Mode)
1.3 中级调度
中级调度(Intermediate Level Scheduling)又称中程调度(Medium-Term Scheduling)。引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。为此,应使那些暂时不能运行的进程不再占用宝贵的内存资源,而将它们调至外存上去等待,把此时的进程状态称为就绪驻外存状态或挂起状态。
2 调度队列模型和调度准则
2.1 调度队列模型
- 1.仅有进程调度的调度队列模型
- 2.具有高级和低级调度的调度队列模型
- 3.同时具有三级调度的调度队列模型
2.2 选择调度方式和调度算法的若干准则
在一个操作系统的设计中,应如何选择调度方式和算法,在很大程度上取决于操作系统的类型及其目标。
- 面向用户的准则
- 面向系统的准则
3 调度算法
调度算法是指:根据系统的资源分配策略所规定的资源分配算法。对于不同的系统和系统目标,通常采用不同的调度算法,例如,在
批处理系统中,为了照顾为数众多的短作业,应采用短作业优先的调度算法;又如在分时系统中,为了保证系统具有合理的响应时间,应采用轮转法进行调度。目前存在的多种调度算法中,有的算法适用于作业调度,有的算法适用于进程调度;但也有些调度算法既可用于作业调度,也可用于进程调度。
3.1 先来先服务和短作业(进程)优先调度算法
3.2 高优先权优先调度算法
3.3 基于时间片的轮转调度算法
4 实时调度
4.1 实现实时调度的基本条件
4.2 实时调度算法的分类
4.3 常用的几种实时调度算法
5 产生死锁的原因和必要条件
在多道程序系统中,虽可借助于多个进程的并发执行来改善系统的资源利用率,提高系统的吞吐量,但可能发生一种危险——死锁。
死锁(Deadlock),是指多个进程在运行过程中因争夺资源而造成的一种僵局(DeadlyEmbrace),当进程处于这种僵持状态时,若无外力作用,它们都将无法再向前推进。在前面介绍把信号量作为同步工具时已提及到,若多个 wait 和 signal 操作顺序不当,会产生进程死锁。
5.1 产生死锁的原因
产生死锁的原因可归结为如下两点:
-
竞争资源。当系统中供多个进程共享的资源如打印机、公用队列等,其数目不足以满足诸进程的需要时,会引起诸进程对资源的竞争而产生死锁。
-
进程间推进顺序非法。进程在运行过程中,请求和释放资源的顺序不当,也同样会导致产生进程死锁。
5.2 产生死锁的必要条件
虽然进程在运行过程中可能发生死锁,但死锁的发生也必须具备一定的条件。综上所述不难看出,死锁的发生必须具备下列四个必要条件。
- 互斥条件:指进程对所分配到的资源进行排它性使用,即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求该资源,则请求者只能等待,直至占有该资源的进程用毕释放。
- 请求和保持条件:指进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源又已被其它进程占有,此时请求进程阻塞,但又对自己已获得的其它资源保持不放。
- 不剥夺条件:指进程已获得的资源,在未使用完之前,不能被剥夺,只能在使用完时由自己释放。
- 环路等待条件:指在发生死锁时,必然存在一个进程——资源的环形链,即进程集合{P0,P1,P2,…,Pn}中的 P0正在等待一个 P1占用的资源;P1正在等待 P2占用的资源,……,Pn正在等待已被 P0占用的资源。
5.3 处理死锁的基本方法
为保证系统中诸进程的正常运行,应事先采取必要的措施,来预防发生死锁。在系统中已经出现死锁后,则应及时检测到死锁的发生,并采取适当措施来解除死锁。目前,处理死锁的方法可归结为以下四种:
(1) 预防死锁。这是一种较简单和直观的事先预防的方法。该方法是通过设置某些限制条件,去破坏产生死锁的四个必要条件中的一个或几个条件,来预防发生死锁。预防死锁是一种较易实现的方法,已被广泛使用。但由于所施加的限制条件往往太严格,因而可能会导致系统资源利用率和系统吞吐量降低。
(2) 避免死锁。该方法同样是属于事先预防的策略,但它并不须事先采取各种限制措施去破坏产生死锁的四个必要条件,而是在资源的动态分配过程中,用某种方法去防止系统进入不安全状态,从而避免发生死锁。这种方法只需事先施加较弱的限制条件,便可获得较高的资源利用率及系统吞吐量,但在实现上有一定的难度。目前在较完善的系统中常用此方法来避免发生死锁。
(3) 检测死锁。这种方法并不须事先采取任何限制性措施,也不必检查系统是否已经进入不安全区,而是允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构,及时地检测出死锁的发生,并精确地确定与死锁有关的进程和资源; 然后,采取适当措施,从系统中将已发生的死锁清除掉。
(4) 解除死锁。这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时,须将进程从死锁状态中解脱出来。常用的实施方法是撤消或挂起一些进程,以便回收一些资源,再将这些资源分配给已处于阻塞状态的进程,使之转为就绪状态,以继续运行。死锁的检测和解除措施有可能使系统获得较好的资源利用率和吞吐量,但在实现上难度也最大。
6 预防死锁的方法
可以参考:死锁的四个必要条件?如何避免与预防死锁?