操作系统第三章处理机调度与死锁题目
A。FCFS B.RR C.优先级 D.多级反馈队列
【答案】C
【解析】优先级低的可能长时间得不到服务，产生饿死现象。
2.以下情况不可能引起进程调度的是（）
A、一个进程完成工作后被撤销
B、一个进程从就绪状态变成了运行状态
C、一个进程从等待状态变成了就绪状态
D、一个进程从运行状态变成了等待状态或就绪状态
【答案】B
【解析】
可能引起进程调度:
(1)正在执行的进程执行完毕。
(2)执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等状态。(3)执行中进程调用了P原语操作，从而因资源不足而被阻塞；或调用了v原语操作激活了等待资源的进程队列。
(4)执行中进程提出I/O请求后被阻塞。
(5)在分时系统中时间片已经用完。
(6)在执行完系统调用等系统程序后返回用户进程时，这时可看作系统进程执行完毕，从而可调度选择一新的用户进程执行。
以上都是在不可剥夺方式下的引起进程调度的原因。在CPU执行方式是可剥夺时．还有
(7)就绪队列中的某进程的优先级变得高于当前执行进程的优先级，从而也将引发进程调度。
2-1．在一般操作系统中必不可少的调度是（）。 （武汉科技学院2008）
A．高级调度 B．中级调度 C．作业调度 D．进程调度
【答案】D
2-2．进程的调度方式有两种，一种是 ① ，另一种是 ② 。
【答案】① 剥夺方式 ② 非剥夺方式。
2-3．确定作业调度算法时应注意系统资源的均衡使用，使 作业和 作业搭配运行。 （武汉理工大学2006）
【答案】CPU繁忙，I/O繁忙
2-4．不影响分时系统响应时间的是（）。 （武汉理工大学2008）
A．进程调度和对换的时间 B.分时用户的数目
C.分时用户所运行程序的特性 D.时间片的大小
【答案】C
【解析】影响响应时间的几个因素是：用户数目，时间片及程序切换时内、外存需对换的信息量。
2-5．某进程被唤醒后立即投入运行，我们就说这个系统采用的是剥夺调度方法，对吗？为什么？
【答案】不对。因为，若当前就绪队列为空，则被唤醒进程是就绪队列中惟一的一个进程，无论系统是否采用剥夺调度方法，调度程序都会立即将该进程投入运行。
2-6 ．下列选项中，降低进程优先权级的合理时机是（） （2010全国考研）
A、进程的时间片用完
B、进程刚完成I/O，进入就绪列队
C、进程长期处于就绪列队
D、进程从就绪状态转为运行状态
【答案】A
【解析】降低进程优先级一般是降低刚刚执行过的，刚得到CPU的，像B，C情况应该提高其优先级，再降低反而更是没有机会得到CPU。
2-7、下列进程调度算法中，综合考虑进程等待时间和执行时间的是（2009全国考研）
A．时间片轮转调度算法 B．短进程优先调度算法
C．先来先服务调度算法 D．高响应比优先调度算法
【答案】D
【解析】本题考查进程调度算法的基本概念。时间片轮转调度算法是保证用户的响应时间，每个进程分配一个时间片，所以在一给定的很短时间内进程都可以获得执行，等待时间都比较短，但没有考虑进程执行时间长短问题；先来先服务调度算法只考虑了进程的等待时间，等待时间长的进程优先处理；短进程优先调度算法只考虑了执行时间，执行时间短的进程优先处理。高响应比优先调度算法中如果进程等待时间相同，执行时间短的优先，进程执行时间相同的等待时间短的优先，所以综合考虑了进程等待时间和执行时间。
2-8、某系统中预计有50个用户同时上机，为使每个用户能在2秒内得到响应，时间片最大限度为（）。 （武汉理工大学2008）
A．20ms B.30ms C.40ms D.50ms
【答案】C
【解析】50个用户同时上机，2秒内得到响应即2秒钟内50个用户应都运行一次，所以时间片最大为2s/50=2000ms/50=40ms。
2-9、在分时操作系统中，进程调度经常采用 _____ 算法。
A. 先来先服务 B. 最高优先权 C. 时间片轮转 D. 随机
【答案】C
【解析】在分时系统中，处理机的时间被分成很短的时间片，系统按时间片轮流将处理机分配给各联机用户使用。
2-10_____ 优先权是在创建进程时确定的，确定之后在整个进程运行期间不再改变。
A. 先来先服务 B. 静态
C. 动态 D. 短作业
【答案】B
【解析】静态优先权是在创建进程时确定的，确定之后在整个进程运行期间不再改变。
2-11若要使当前运行进程总是优先级最高的进程，应选择 _____ 进程调度算法。
【答案】可抢占式最高优先级优先
【解析】可抢占式最高优先级优先调度算法总是将处理机分配给优先级最高的进程。
2-12、进程调度算法采用等时间片轮转法时，时间片过大，就会使轮转法转化为_____ 调度算法。
【答案】先来先服务
【解析】当时间片过大（大到每个进程都能在一个时间片内完成）时，就会使轮转法转化为先来先服务调度算法。
2-13在单道批处理系统中，有下列 4个作业采用响应比高者优先调度算法，则它们的执行先后次序为（）。 （武汉科技学院2008）
作业 | 提交时间 | 运行时间 |
1 | 8.00 | 2.00 |
2 | 8.50 | 0.50 |
3 | 9.00 | 0.10 |
4 | 9.50 | 0.20 |
【答案】1，3，2，4
进程 | 作业1 | 作业2 | 作业3 | 作业4 |
到达时间 | 8.00 | 8.50 | 9.00 | 9.50 |
服务时间 | 2.00 | 0.50 | 0.10 | 0.20 |
开始运行时间 | 8.00 | 10.10 | 10.00 | 11.00 |
完成时间 | 10.00 | 11.00 | 10.10 | 11.20 |
10.00响应比 | （70+50）/50=2.4 | （60+10）/10=7 | （10+20）/20=1.5 | |
10.10响应比 | (80+50)/50=2.6 | (20+20)/20=2 |
2-14系统中有5个进程P1，P2，P3，P4，P5如表。规定进程的优先数越小优先级越高。试描述在采用下述各种调度算法时，各个进程运行过程，并计算采用每种算法的进程平均周转时间。假设忽略进程的调度时间。（1）先来先服务调度算法；（2）短进程优先调度算法；（3）剥夺式优先级调度算法。
进程 | 到达时刻 | 运行时间/ms | 优先数 |
P1 | 0 | 3 | 3 |
P2 | 2 | 6 | 5 |
P3 | 4 | 4 | 1 |
P4 | 6 | 5 | 2 |
P5 | 8 | 2 | 4 |
（1）先来先服务调度算法运行过程如下：按到达先后P1，P2，P3，P4，P5
进程 | 到达时刻 | 运行时间/ms | 开始时间 | 完成时间 | 周转时间 |
P1 | 0 | 3 | 0 | 3 | 3 |
P2 | 2 | 6 | 3 | 9 | 7 |
P3 | 4 | 4 | 9 | 13 | 9 |
P4 | 6 | 5 | 13 | 18 | 12 |
P5 | 8 | 2 | 18 | 20 | 12 |
所以此算法进程的平均周转时间为：（3+7+9+12+12）/5=43/5=8.6
(2) 短进程优先调度算法运行过程如下：
0时刻只有P1，所以先执行P1，3时刻只有P2，所以再执行P2，P2执行完，9时刻时，P3，P4，P5都已到达，按短进程优先，所以先执行P5，再执行P3，最后执行P4
进程 | 到达时刻 | 运行时间/ms | 开始时间 | 完成时间 | 周转时间 |
P1 | 0 | 3 | 0 | 3 | 3 |
P2 | 2 | 6 | 3 | 9 | 7 |
P3 | 4 | 4 | 11 | 15 | 11 |
P4 | 6 | 5 | 15 | 20 | 14 |
P5 | 8 | 2 | 9 | 11 | 3 |
所以此算法进程的平均周转时间为：（3+7+11+14+3）/5=38/5=7.6
（3）剥夺式优先级调度算法运行过程如下：
在0时刻只有P1，所以先执行P1，2时刻P2到达，但P2的优先级没有P1高，所以继续执行P1，3时刻P1执行完，只有P2，所以执行P2，4时刻P3到达，P3的优先级高于P2，所以执行P3，P3执行完，8时刻，P4，P5都到达，P2，P4，P5中P4的优先级最高，所以先执行P4，再执行P5，最后执行P2剩余的。
所以此算法进程的平均周转时间为：（3+18+4+7+7）/5=39/5=7.8
进程 | 到达时刻 | 运行时间/ms | 开始时间 | 完成时间 | 周转时间 |
P1 | 0 | 3 | 0 | 3 | 3 |
P2 | 2 | 6 | 3 | 20 | 18 |
P3 | 4 | 4 | 4 | 8 | 4 |
P4 | 6 | 5 | 8 | 13 | 7 |
P5 | 8 | 2 | 13 | 15 | 7 |
2-15、假设有6个作业正在等待运行，它们所需的运行时间分别是：10，8，6，4，2 和X。不考虑并行、基于X、在追求最小平均响应时间（Minimal average response time）的前提下，请给出它们的运行顺序。（提示：共有六种顺序，先确定运行方法）（北京航空航天大学2007）
【答案】本题中，不考虑并行，即单道，没有给出到达时间，假定为同时到达，那么应该是最短作业优先的调度算法会得到最小的平均响应时间。响应时间是作业到达时间到系统开始服务的时间，在单道中即可看为等待时间。
假设此6个作业为别为，A，B，C，D，E，F。A-E的运行时间依次为10，8，6，4，2，F的运行时间为X
当x<2时，运行顺序为：F，E，D，C，B，A
当2<x<4时，运行顺序为：E，F，D，C，B，A
当4<x<6时，运行顺序为：E，D，F，C，B，A
当6<x<8时，运行顺序为：E，D，C，F，B，A
当8<x<10时，运行顺序为：E，D，C，B，F，A
当x>10时，运行顺序为：E，D，C，B，A，F
2-16 、有5个进程如下表。时间从0开始，单位为1，最高优先级为0。
绘图说明以下进程调度过程：（1 CPU 系统，所有进程只使用CPU）。
请使用时间为横向坐标轴，并请在图中表明每个进程的“等待”和“运行”两种状态。
1．先来先服务（FCFS）。
2．轮转调度（Round-Robin）时间片=2。
3．优先级轮转法（Priority Round-Robin）时间片=2。
4．最短进程轮转法（Shortest Process Next）。
【答案】
1．FCFS:
【解析】在进程调度中，先来先服务算法是按照进程到达的时间顺序调度进程。
2．轮转调度，时间片=2：
【解析】在轮转调度中，时间片为2，按照先来先服务顺序依次调度进程，每个进程一次允许运行一个时间片，如果在一个时间片没用完的情况下运行完成，则提前进行调度。
3．优先级轮转法
【解析】在优先级轮转调度中，基本思想与轮转调度一致，每个时间片为2 ，每个进程一次允许运行一个时间片，如果在一个时间片没用完的情况下运行完成，则提前进行调度，但调度次序按照优先级最高的优先调度。
4．最短进程轮转法
【解析】在最短进程轮转调度中，基本思想与轮转调度一致，每个时间片为2 ，每个进程一次允许运行一个时间片，如果在一个时间片没用完的情况下运行完成，则提前进行调度，但调度次序按照每次所需运行时间最短的进程的优先调度。
2-17、在一个单处理器的计算机系统中，有四个进程P1，P2，P3，P4的到达时间和所需要的运行时间如下表所示（时间单位：小时，以十进制计算），请问 （武汉理工大学2006）
（1）分别写出采用“先来先服务”调度算法、“短进程优先”和“响应比高者优先”调度算法选中进程运行的次序。
（2）分别计算上述三种算法使各进程在就绪队列中的平均等待时间以及三种算法下的平均周转时间。
（3）是否存在缩短平均周转时间的调度策略，如果存在，请提出来，写出选中进程运行的次序，并计算在就绪队列中的平均等待时间以及平均周转时间？
进程 | 到达时间 | 运行时间 |
P1 P2 P3 P4 | 0.0 0.4 1.0 4.0 | 8.0 4.0 1.0 3.0 |
【解析】先来先服务就是按照到达的次序依次执行。到达次序为P1，P2，P3，P4，所以调度次序也为P1，P2，P3，P4
【答案】短进程优先,调度次序为P1，P3，P4，P2。
【解析】开始只有P1所以执行P1，P1执行完时，P2，P3，P4都已经到达，服务时间短的优先，所以是P3，P4，P2。
进程 | P1 | P2 | P3 | P4 |
到达时间 | 0.0 | 0.4 | 1.0 | 4.0 |
服务时间 | 8.0 | 4.0 | 1.0 | 3.0 |
开始运行时间 | 0.0 | 12.0 | 8.0 | 9.0 |
完成时间 | 8.0 | 16.0 | 9.0 | 12.0 |
周转时间 | 8.0 | 15.6 | 8.0 | 8.0 |
等待时间 | 0.0 | 11.6 | 7.0 | 5.0 |
【解析】开始只有P1所以执行P1，P1执行完时，P2，P3，P4都已经到达，响应比等于（等待时间+服务时间）/服务时间，则P2的响应比为(7.6+4)/4=2.9，P3的响应比为(7+1)/1=8，P4的响应比为（4+3）/3=2.3,P3的响应比最高，所以第二个执行P3，P3完成时，时间为9.0，此时P2的响应比为(8.6+4)/4=3.15，P4的响应比为（5+3）/3=2.6, P2的响应比最高，所以第三个执行P2，最后执行P4
进程 | P1 | P2 | P3 | P4 |
到达时间 | 0.0 | 0.4 | 1.0 | 4.0 |
服务时间 | 8.0 | 4.0 | 1.0 | 3.0 |
开始运行时间 | 0.0 | 9.0 | 8.0 | 13.0 |
完成时间 | 8.0 | 13.0 | 9.0 | 16.0 |
周转时间 | 8.0 | 12.6 | 8.0 | 12.0 |
等待时间 | 0.0 | 8.6 | 7.0 | 9.0 |
先来先服务算法的平均等待时间为：(0+7.6+11+9)/4=6.9
平均周转时间为：（8+11.6+12+12）/4=10.9
短进程优先算法的平均等待时间为：（0+11.6+7+5）/4=5.9
平均周转时间为：(8+15.6+8+8)/4=9.9
高响应比者优先算法的平均等待时间为：（0+8.6+7+9）/4=6.15
平均周转时间为：(8+12.6+8+12)/4=10.15
【解析】周转时间等于进程到达到服务完成的这段时间，平均周转时间就是每个进程的周转时间相加取平均。
等待时间是进程处于就绪队列中的时间，在前面三个非抢占式调度算法中等于开始运行时间减去到达时间这一段时间。平均等待时间就是每个进程的等待时间相加取平均。
（3）【答案】可采用抢占式短作业优先算法。执行过程如图：
其平均周转时间为6.6，平均等待时间为2.6。
【解析】可抢占式短作业优先，遇到短作业立即抢占CPU，所以使短作业无需等待立即得到执行，从而降低了平均周转时间。其中在0.0时刻，只有P1进程，所以执行P1，0.4时刻P2到达，由于P2的服务时间比P1短，抢占CPU执行，在1.0时刻P3到达，P3的服务时间更短，则P3抢占CPU执行，2.0时刻P3完成，此时内存中有P1和P2，因为P2的服务时间短于P1，则执行P2，当4.0时刻P4到达时，这时P2所剩服务时间为1.4短于P4，所以仍执行P2，5.4时刻P2执行完，系统中剩P1与P4，P4的服务时间短，所以先执行P4，P4执行完再执行P1。由结果可以看出，此种算法可以缩短平均周转时间，也大大降低了平均等待时间。
2-18、有一个具有两道作业的批处理系统，作业调度采用短作业优先调度算法，进程调度采用抢占式优先级调度算法，作业的运行情况见下表。其中作业的优先数即为进程的优先数，优先数越小优先级越高。
作业名 | 到达时间 | 运行时间 | 优先数 |
1 | 8:00 | 40min | 5 |
2 | 8:20 | 30min | 3 |
3 | 8:30 | 50min | 4 |
4 | 8:50 | 20min | 6 |
（1）列出所有作业进入内存的时间和结束的时间（以分钟为单位）
（2）计算平均周转时间
假设有三个进程P1 P2 P3,P1有一个线程T11，P2有3个线程T21 T22 T23 ，P3有2个线程T31 T32。这些线程的CPU运行时间如下表所示
进程 | 线程 | 运行时间 |
P1 | T11 | 7 |
P2 | T21 | 4 |
T22 | 2 | |
T23 | 4 | |
P3 | T31 | 6 |
T327 | 3 |
（1）如果这些线程是用户级线程
（2）如果这些线程是内核级线程
【答案】
（1）
P1 T11 | P2 T21 | P2 T22 | P3 T31 | P1 T11 | P2 T22 | P2 T23 | P3 T31 | P3 T32 |
P1 T11 | P2 T21 | P2 T22 | P3 T31 | P1 T11 | P2 T22 | P2 T23 | P3 T31 | P3 T32 |
（2）
P1 T11 | P2 T21 | P2 T22 | P3 T31 | P1 T11 | P2 T22 | P2 T23 | P3 T31 | P3 T32 |
