在多道程序系统中,调度的实质是一种资源分配,处理机调度是对处理机资源进行分配。处理机调度算法是指根据处理机分配策略所规定的处理机分配算法。
在多道程序系统中,进程的数量远远多于处理机的个数,因此进程争用处理机的情况在所难免。处理机调度是对处理机进行分配,即从就绪队列中按照一定的算法(公平、高效)选择一个进程并将处理机分配给它运行,以实现进程的并发执行。
高级调度又称 长程调度 或 作业调度 ,它调度的对象是 作业 。其主要功能是根据某种算法,决定将外存上处于后备队列中的哪几个作业调入内存,为它们创建进程、分配必要的资源,并将其放入就绪队列。
高级调度主要用于多道批处理系统中,在分时系统和实时系统中不设置高级调度。高级调度的执行频率较低,通常为几分钟一次。
低级调度又称为 进程调度 或 短程调度 ,其所调度的对象是 进程 或 内核级线程 。其主要功能是根据某种算法决定就绪队列中哪个进程应获得处理机,并由分派程序将处理机分配给被选中的进程。
进程调度是最基本的一种调度,在多道批处理、分时系统和实时系统三种类型的OS中都必须设置这种调度。进程调度的频率很高,一般几十毫秒一次。
中级调度又称 内存调度 。引入中级调度的目的主要是提高内存的吞吐率和系统吞吐量。为此应把那些暂时不能运行的进程调至外存等待,此时进程的状态称为 就绪驻外存状态(或挂起状态) 。当它们已具备运行条件且内存又稍有空闲时,由中级调度来决定把外存上那些已具备运行条件的就绪进程再重新调入内存,并修改其状态为就绪状态,挂在就绪队列上等待。中级调度实际上就是存储器管理中的对换功能。
为了管理和调度作业,在多道批处理系统中,为每个作业设置一个作业控制块JCB,它是作业在系统中存在的标志,其中保存了系统对作业进行管理和调度所需的全部信息,例如 作业标识 、 用户名称 、 用户账号 、 作业类型(CPU繁忙型、I/O繁忙型、批量型、终端型) 、 作业状态 、 调度信息(优先级、作业运行时间) 、 资源需求(预计运行时间、要求内存大小等) 、 资源使用情况 等。
每当一个作业进入系统时,由“作业注册”程序为该作业建立一个JCB,再根据作业类型放到相应的后备队列中等待调度。调度程序根据一定的调度算法来调度它们,被调度的作业将被装入内存。在作业运行期间,系统根据JCB中的信息和作业说明书对作业进行控制。当一个作业执行完毕后,系统负责回收分配给它的资源,并撤销该JCB。
作业调度的主要任务是 根据JCB中的信息,检查系统中的资源是否满足作业对资源的需求,以及按照一定的调度算法,从外存的后备队列中选取某些作业调入内存,并为它们创建进程、分配必要的资源,然后将新创建的进程排在就绪队列上等待调度 。因此也把作业调度称为“接纳调度”。在每次执行作业调度时,都需要决定 接纳多少个作业 和 接纳哪些作业 。
进程调度和切换的程序是操作系统的内核程序。请求调度的事件发生后,才可能运行进程调度程序,调度了新的就绪进程后,才会进行进程间的切换。在实际设计中,操作系统的内核程序运行时,若发生了引起进程调度的因素,也不一定能够马上进行进程调度与切换。
不能进行进程调度与切换的原因有:
若上述过程中发生了引起调度的条件,不能马上进行进程的调度与切换,应置系统的请求调度标志,直到上述过程结束后再进行相应的调度与切换。
应该进行进程的调度与切换的情况如下:
进程切换往往在调度完成后立刻发生。
进程调度方式是指 某个进程正在处理机上执行时,若有某个更为重要或紧迫的进程需要处理,即有更高优先权的进程进入就绪队列,此时应该如何分配处理机。
进程调度通常有 非剥夺调度方式 和 剥夺调度方式 两种方式。
又称 非抢占方式 ,是指当一个进程正在处理机上执行时,即使有某个更为重要或紧迫的进程进入就绪队列,仍然让正在执行的进程继续执行,直到该进程完成或发生某种事件而进入阻塞状态时,才把处理机分配给更为重要或紧迫的进程。在非剥夺调度方式下,一旦把CPU分配给一个进程,该进程就会保持CPU直到终止或转换到等待态。
非剥夺调度方式适合大多数的批处理系统,但不能用于分时系统和大多数的实时系统。
又称 抢占方式 ,是指当一个进程在处理机上执行时,若有某个更为重要或紧迫的进程需要使用处理机,则立即暂停正在执行的进程,将处理机分配给这个更为重要或紧迫的进程。
采用剥夺调度方式,对提高系统吞吐率和响应效率都有明显的好处,但“剥夺”必须遵循一定的原则,主要有优先权、短进程优先、时间片原则等。
FCFS调度算法既可以用于作业调度,又可以用于进程调度。在作业调度中, 算法每次从后备队列中选择最先进入该队列的一个或几个作业,将它们调入内存,分配必要的资源,创建进程并放入就绪队列。
在进程调度中,FCFS调度算法每次从就绪队列中选择最先进入该队列的进程,将处理机分配给它,直到进程完成或因某种原因而阻塞才释放处理机。
FCFS调度算法属于不可剥夺算法。若一个长作业先到达系统,就会使后面许多短作业等待很长时间,因此它不能作为分时系统和实时系统的主要调度策略。但它常被结合在其它调度策略中使用,如在使用优先级作为调度策略的系统中,往往对多个具有相同优先级的进程按FCFS处理。
特点:
短作业优先调度算法是对短作业优先调度的算法。短作业优先算法从后备队列中选择一个或若干估计运行时间最短的进程,将它们调入内存执行;短进程优先算法从就绪队列中选择一个估计运行时间最短的进程,将处理机分配给它,直到完成或发生某事件而阻塞时,才释放处理机。
特点:
优先级调度算法又可称为优先权调度算法,既可以用于作业调度,又可以用于进程调度。该算法中的优先级用于描述作业的紧迫程度。在作业调度中,优先级调度算法每次从后备作业队列中选择优先级最高的一个或几个作业,将它们调入内存,分配必要的资源,创建进程并放入就绪队列。在进程调度中,优先级调度算法每次从就绪队列中选择优先级最高的进程,将处理机分配给它。
该算法按照更高优先级的进程是否抢占正在执行的进程可分为两种:
根据进程的优先级是否改变,可将进程的优先级分为以下两种:
一般来说,进程优先级的设置可以参照以下原则:
高响应比优先调度算法主要用于作业调度,是对FCFS调度算法和SJF调度算法的一种综合平衡,同时考虑了每个作业的等待事件和估计的运行时间。在每次进行作业调度时,先计算后备队列中每个作业的响应比,从中选出响应比最高的作业投入运行。
响应比的计算公式为: 响应比Rp = (等待时间 + 要求服务时间)/ 要求服务时间
特征:
时间片轮转调度算法主要用于分时系统。系统将所有就绪进程按到达时间的先后次序排成一个队列,进程调度程序总是选择就绪队列中的第一个进程执行,即先来先服务原则,但仅能运行一个时间片(如100ms)。在使用完一个时间片后,即使进程未完成其运行,它也必须释放处理机给下一个就绪的进程,而被剥夺处理机的进程返回就绪队列的末尾重新排队,等候再次运行。
时间片的大小对性能影响很大。若时间片足够大以至于所有进程都能在一个时间片内执行完毕,则该算法就退化为先来先服务调度算法;若时间片很小,则处理机将在进程间过于频繁地切换,使处理机的开销增大,而真正用于运行用户进程的时间将减少。
时间片的长短通常由以下因素确定:
多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合与发展。多级反馈队列调度算法可以兼顾多方面的系统目标,如为提高系统吞吐量和缩短平均周转时间而照顾短进程;为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程;不必事先估计进程的执行时间。
该算法的实现思想如下:
优点:
死锁是指多个进程因竞争资源而造成的一种僵局(互相等待),若无外力作用,这些进程都将无法向前推进。
为使系统不发生死锁,必须破坏死锁的四个必要条件之一,或允许死锁产生,但当死锁发生时能检测出死锁,并有能力实现恢复。
设置某些限制条件,破坏产生死锁的四个必要条件中的一个或几个,以防止发生死锁。
在资源的动态分配过程中,用某种方法防止系统进入不安全状态,从而避免死锁。
无需采取任何限制性措施,允许进程在运行的过程中发生死锁,通过系统的检测机构及时地检测出死锁的发生,然后采取某种措施解除死锁。
死锁的预防和避免都属于事先预防策略,预防死锁的限制条件比较严格,实现起来较为简单,但往往导致系统的效率低,资源利用率低;避免死锁的限制条件比较宽松,资源分配后需要通过算法来判断是否进入不安全状态,实现起来比较复杂。
死锁的几种处理策略如下:
防止死锁的发生只需要破坏死锁产生的4个必要条件的其中之一即可。
特点:把只能互斥使用的资源改造成允许共享使用,则系统就不会进入死锁状态。如操作系统使用SPOOLing技术把独占设备在逻辑上改造成共享设备。
缺点:并不是所有的资源都可以改造成可以共享使用的资源,并且为了系统安全,很多地方还必须保持这种互斥性。因此,很多时候都无法破坏这种互斥条件。
特点:
缺点:
特点:可采用静态分配方法,即进程运行之前一次申请完它所需要的全部资源,在它的资源尚未得到满足前,不把它投入运行。一旦投入运行,这些资源就一直归它所有,不再提出申请其他资源的请求。这种方法实现起来简单。
缺点:有些资源可能只需要使用很短的时间,因此如果进程的整个运行期间都一直保持着所有资源,就会造成严重的资源浪费,资源利用率极低。另外,该策略也有可能导致某些进程饥饿。
特点:采用顺序资源分配法,首先给系统中的资源编号,规定每个进程都必须按照编号递增的顺序请求资源,同类资源一次申请完。也就是说,只要进程提出申请分配资源Ri,则该进程在以后的资源申请中就只能申请编号大于Ri的资源(一个进程只有已占有我号的资源时,才有资格申请更大编号的资源)。按此规则,已持有更大编号资源的进程不可能逆向地申请我号的资源,从而就不会产生循环等待现象。
缺点:
所谓安全序列,就是指如果系统按照这种序列分配资源,则每个进程都能顺利完成。只要找出一个安全序列,系统就是安全状态。安全序列可能有多个。
如果分配了资源之后,系统找不到安全序列,则系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利执行下去。当然,如果有进程提前归还了一些资源,那系统也有可能提前回到安全状态。
如果系统处于安全状态,那么就一定不会发生死锁;如果系统进入不安全状态,就可能发生死锁(处于不安全状态未必就发生了死锁,但发生死锁时系统一定处于不安全状态)。因此可以在资源分配前预先判断这次分配是否会导致系统进入不安全状态,以此决定是否答应资源分配请求。
设Requesti是进程Pi的请求向量,Requesti[j] = K表示进程Pi需要j类资源K个。当Pi发出资源请求后,系统按照如下步骤进行检查:
安全性算法描述如下:
若系统在为进程分配资源时不采取任何措施,则应该提供死锁检测与解除的手段。
系统死锁可用资源分配图描述。如下图所示,圆圈代表一个进程,框代表一类资源,由于一种资源可能有多个,所以用框中的一个圆代表一类资源中的一个资源。从进程到资源的有向边称为请求边,表示该进程申请一个单位的该类资源;从资源到进程的边称为分配边,表示该类资源已经有一个资源分配给了该进程。
通过简化资源分配图可以检测系统状态S是否为死锁状态。简化方法如下: