1、对于本章内的基本调度算法:算法思想、就绪队列的组织、是抢占还是非抢占
FCFS先来先服务调度算法 算法思想:
当在作业调度中采用该算法时,每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业,将它们调入内存,为它们分配资源、创建进程,然后放入就绪队列。在进程调度中采用FCFS算法时,则每次调度是从就绪队列中选择一个最先进入该队列的进程,为之分配处理机,使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。
FCFS是非抢占式的调度算法。
短作业(进程)优先调度算法 算法思想:
短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业,将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选择一个估计运行时间最短的进程,将处理机分配给它,使它立即执行并一直执行到完成,或发生某事件而被阻塞放弃处理机时再重新调度。
短作业调度算法是非抢占式的调度算法。
非抢占式优先权调度算法和抢占式优先权调度算法 算法思想:
非抢占式优先权调度算法:系统一旦把处理机分配给就绪队列中优先权最高的进程后,该进程便一直执行下去,直至完成,或因发生某事件使该进程放弃处理机时,系统方可再将处理机重新分配给另一个优先权最高的进程。
抢占式优先权调度算法:系统同样是把处理机分配给优先权最高的进程,使之执行。但在其执行期间,只要又出现了另一个其优先权更高的进程,进程调度就立即停止当前进程的执行,重新将处理机分配给新到的优先权最高的进程。
静态优先权和动态优先权 算法思想:
静态优先权是在创建进程时确定的,且在进程的整个运行期间保持不变。动态优先权是指在创建进程时所赋予的优先权,是可以随进程的推进或随其等待时间的增加而改变的。
高响应比优先调度算法 算法思想:
为每个作业引入动态优先权,并使作业的优先级随着等待时间的增加而以速率a提高,则长作业在等待一定的时间后,必然后寄回分配到处理机。该优先权的变化规律可描述为:
优先权=(等待时间+要求服务时间)/ 要求服务事件
基于时间片的轮转调度算法 算法思想:
系统将所有的就绪进程按先来先服务的原则排成一个队列,每次调度时,把CPU分配给队首进程,并令其执行一个时间片。
多级反馈队列调度算法 算法思想:
设置多个就绪队列,并为各个队列赋予不同的优先级。第一个队列的优先级最高,第二个队列次之。
当一个新进程进入内存后,首先将它放入第一个队列的末尾,按FCFS原则排队等待调度。如果一个时间片后进程尚未完成,调度程序便将该进程转入第二个队列的末尾,再同样地按FCFS原则等待调度执行。当一个长作业从第一个队列一次降到第n个队列后,在第n队列中便采取按时间片轮转的方式运行。
仅当第一队列空闲时,调度程序才调度第二队列中的进程运行。
2、典型的动态优先权调度调度算法:高响应比优先度调度算法;典型的实时调度算法:最低松弛度优先调度算法;时间片轮转法中,时间片取值的影响,如何确定时间片的大小
时间片取值的影响:
如果选择很小的时间片将有利于短作业,因为它能较快地完成,但会频繁地发生中断、进程上下文的切换,从而增加系统的开销;反之,如果选择太长的时间片,使得每个进程都能在一个时间片内完成,时间片轮转算法便退化为FCFS算法,无法满足交互式用户的需求。
如何确定时间片的大小:
时间片应略大于一次典型的交互需要的时间。这样可使大多数进程在一个时间片内完成。一般应考虑三个因素:系统对相应时间的要求、就绪队列中进程的数目和系统的处理能力。
3、什么是死锁,死锁产生的原因及必要条件
所谓死锁,是指多个进程在运行过程中因争夺资源而造成的一种僵局,当进程处于这种僵持状态时,若无外力作用,它们都将无法再向前推进。
产生死锁的原因:可归结为如下两点:(1)竞争资源。(2)进程间推进顺序非法。
产生死锁的必要条件:互斥条件,请求和保持条件,不剥夺条件和环路等待条件。
4、死锁的避免----避免死锁的银行家算法,数据结构,算法思想
银行家算法中的数据结构:
① 可利用资源向量 Available ② 最大需求矩阵Max ③ 分配矩阵 Allocation ④ 需求矩阵 Need
三个矩阵间存在下述关系:
Need[i,j] = Max[i,j] –Allocation[i,j]
算法思想: (1)如果Request i[j] <= Need[i,j],便转向步骤(2);否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。 (2)如果Request i[j] <= Available[j],便转向步骤(3);否则,表示尚无足够资源,Pi须等待。 (3)系统试探着把资源分配给进程Pi,并修改下面数据结构中的值:
Available[j]:=Available[j] – Request i[j]; Allocation[i,j]:=Allocation[i,j] + Request i[j]; Need[i,j]:=Need[i,j] – Request i[j];
(4)系统执行安全性算法,减产此次算法分配后系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。 安全性算法: (1)设置两个向量:
① 工作向量Work,表示系统可提供给进程继续运行所需的各类资源数目,它含有m个元素,在执行安全算法开始时,Work:=Available。 ② Finish,表示系统是否有足够的资源分配给进程,使之运行完成。开始时限做Finish[i]:=false;当有足够资源分配给进程时,再令Finish[i]:=true。
(2)从进程集合中找到一个能满足下述条件的进程:
① Finish[i] = false; ② Need[i,j] <= Work[j];
若找到,执行步骤(3),否则,执行步骤(4)
(3)当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:
Work[j]:=Work[j] + Allocation[i,j]; Finish[i]:=true; go to step 2;
(4)如果所有进程的Finish[i] = true都满足,则表示系统处于安全状态;否则,系统处于不安全状态。
5、死锁的检测和解除----资源分配图,检测方法、解除方法
资源分配图:
系统死锁可利用资源分配图来描述。该图是由一组节点N和一组边E所组成的一个对偶G=(N1E)。用圆圈代表一个进程,用方框代表一类资源。
检查方法:
我们可以利用把资源分配图加以简化的方法,来检查当系统处于S状态时是否为死锁状态。简化方法如下:
① 在资源分配图中,找出一个既不阻塞又非独立的进程结点Pi。分配资源使Pi运行再释放全部资源,相当于消去Pi所求的请求边和分配边,使之成为孤立的结点。 ② Pi释放资源后,使其他进程获取资源运行。这样不断减缓资源分配图 ③ 在进程一系列的简化后,若能消去图中所有的边,使所有的进程结点都成为孤立结点,则成该图是可完全简化的。
有关文件已经证明,所有的简化顺序,都将得到相同的不可简化图。S为死锁的充分条件是:当且仅当S状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理。
解除方法:
常用解除死锁的两种方法是:① 剥夺资源; ② 撤销进程。
6、在银行家算法中,若出现下述资源分配情况:
Process
Allocation
Need
Available
P0
0 0 3 2
0 0 1 2
1 6 2 2
P1
1 0 0 0
1 7 5 0
P2
1 3 5 4
2 3 5 6
P3
0 3 3 2
0 6 5 2
P4
0 0 1 4
0 6 5 6
试问: ⑴ 该状态是否安全? ⑵ 若进程P2提出请求Request(1,2,2,2)后,系统能否将资源分配给它?
⑴该状态是安全的,因为存在一个安全序列< P0P3P4P1P2>。下表为该时刻的安全序列表。
资源情况 进程
Work
Need
Allocation
Work+Allocation
Finish
P0 P3 P4 P1 P2
1 6 2 2 1 6 5 4 1 9 8 6 1 9 9 10 2 9 9 10
0 0 1 2 0 6 5 2 0 6 5 6 1 7 5 0 2 3 5 6
0 0 3 2 0 3 3 2 0 0 1 4 1 0 0 0 1 3 5 4
1 6 5 4 1 9 8 6 1 9 9 10 2 9 9 10 3 12 14 16
true true true true true
⑵若进程P2提出上述请求,系统不能将资源分配给它,因为分配之后系统将进入不安全状态。
P2请求资源:P2发出请求向量Request2(1,2,2,2),系统按银行家算法进行检查: ①Request2(1,2,2,2)≤Need2(2,3,5,6); ②Request2(1,2,2,2)≤Available(1,6,2,2); ③系统暂时先假定可为P2分配资源,并修改P2的有关数据,如下表:
Allocation
Need
Available
2 5 7 6
1 1 3 4
0 4 0 0
可用资源Available(0,4,0,0)已不能满足任何进程的需要。
7、在什么情况下需要使用作业控制块JCB?其中包含了哪些内容?
为了管理和调度作业,在多道批处理系统中为每个作业设置了一个作业控制块。
在JCB 中所包含的内容因系统而异,通常应包含的内容有:作业标识、用户名称、用户帐户、作业类型(CPU 繁忙型、I/O 繁忙型、批量型、终端型)、作业状态、调度信息(优先级、作业已运行时间)、资源需求(预计运行时间、要求内存大小、要求I/O设备的类型和数量等)、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。
8、在抢占调度方式中,抢占的原则是什么?
抢占的原则有:优先权原则;短作业(进程)优先原则;时间片原则。
9、为什么说多级反馈队列调度算法能较好满足各方面用户的需要?
(1) 所有类型的作业都会在很短的时间内启动,用户会获得响应; (2) 终端型用户作业、短批处理作业用户,能在较短的时间内完成; (3) 系统吞吐率高; (4) 长批处理作业,能够最终得到处理。
10、在解决死锁问题的几个方法中,哪种方法最易于实现?哪种方法资源利用率最高?
“预防死锁”最容易实现;“避免死锁”资源利用率最高。