Worker4： begin repeat
P (Afull) ; //在货架A上取1个车架
P (Bfull) ; P (Bfull) ; //在货架B上取2个车轮 取1个车架；取2个车轮；
V (Aempty) ; //货架A上的空位数增1(通知工人1)
V (Bempty) ; V (Bempty) ; //货架B上的空位数增2(通知工人2、3) 组装一辆自行车; until false end PAREND END
第三章
例3-1：有如下三道作业。系统为它们服务的顺序是：1、2、3.求平均周转时间和平均带权周转时间。
作业 提交时间/时 运行时间/h 1 2 3
作业 提交时运行时开始时完成时间 周转时带权周转间 间 间 间 时间 1 2 3 10.00 2 10.10 1 10 12 12.00 13.00 13.25 2 2/2 10.00 10.10 10.25 2 1 0.25 2．9 2.9/1 3 3/0.25 10.25 0.25 13 例3-2：假定在单CPU条件下有下列要执行的作业。作业到来的时间是按作业编号顺序进行
的（即后面作业依次比前一个作业迟到一个时间单位）。
（1）用一个执行时间图描述在采用抢占方式优先算法时执行这些作业的情况。
（2）对于上述算法，各作业的周转时间、平均周转时间、带权周转时间及平均带权周转时间分别是多少？ 作业 1 2 3
运行时间/h 10 4 3 优先级 2 3 5
【例3-3】 设在单道系统中用FCFS算法调度如下作业，请完成下表。
FCFS算法比较有利于长作业（进程），不利于短作业（进程）。 有利于CPU繁忙型作业（进程），不利于I/O繁忙型作业（进程）——因非抢占式 【例3-4】 设在单道系统中用SJF算法调度如下作业，请完成下表。 进程名 A B 9:10 C 9:30 D 10:00 E 10:15 平 均 到达时间 9:00 服务时间 30分钟 1小时 完成时间 9：30 10：40 周转时间 30min 90min 1.5 10分钟 50分钟 20分钟 9：40 10min 1 11：50 110min 2.2 11：00 45min 2.25 61min 1.99 带权周转时 1 间
例3-5：有一个内存中只能装入2道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。有如下表所示的作业序列，表中所列的优先数是指进程调度的优先数，且优先数越小优先级越高。 （1）列出所有作业进入内存的时刻及结束的时刻。 （2）计算作业的平均周转时间。 作业名 A B C D
到达时间 10:00 10:20 10:30 10:50 估计运行时间 40分 30分 50分 20分 优先数 5 3 4 6 作业名 到达时间 估计运行时间 A B C D 10:00 10:20 10:30 10:50 40分 30分 50分 20分 优先数 进入内存时间 5 3 4 6 结束时间
A、B、C、D的周转时间分别为：70分、30分、90分、90分，则平均周转时间为70分钟。
练习题
1．下列各项中，不是进程调度时机的是 C 。 现运行的进程正常结束或异常结束 B. 现运行的进程从运行态进入就绪态 C. 现运行的进程从运行态进入等待态 D. 现运行的进程从等待态进入就绪态
2．采用时间片轮转调度算法主要是为了 A 。 A.多个终端都能得到系统的及时响应 B.先来先服务
C.优先权高的进程及时得到调度 D.需要CPU时间最短的进程先做 3．在单处理器的多进程系统中，进程什么时候占用处理器和能占用多长时间，取决于__C__ 。 A.进程相应的程序段的长度 B.进程总共需要运行时间多少 C.进程自身和进程调度策略 D.进程完成什么功能
4．一种既利于短小作业又兼顾到长作业的作业调度算法是__C_____。 A.先来先服务 B. 轮转 C.最高响应比 D.均衡调度
5．下列因素中， C 不一定是引起进程调度的因素。 A．一个进程运行完毕 B．运行进程被阻塞
C．一个高优先级进程被创建
D．实时调度中，一个紧迫的任务到来
6．若进程P一旦被唤醒就能投入运行，则系统可能是 D 。 A．分时系统，进程P的优先级最高
B．抢占式调度方式，就绪队列上的所有进程的优先级皆比P低 C．就绪队列为空队列
D．抢占式调度方式，P的优先级高于当前运行的进程
7．在分时系统中，若当前运行的进程连续获得了两个时间片，原因可能是 B 。 A．该进程的优先级最高 B．就绪队列为空
C．该进程最早进入就绪队列 D．该进程是一个短进程
8．下列进程调度算法中，_A____可能会出现进程长期得不到调度的情况。 A．静态优先权法
B．抢占式调度中采用动态优先权算法 C．分时处理中的时间片轮转调度算法 D．非抢占式调度中采用FIFO算法
9．在采用动态优先权的调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和_A___调度算法相同。 A．先来先服务 B．短作业优先 C．时间片轮转 D．长作业优先
10.设在内存中有P1，P2两道程序，并按照P1，P2的次序运行，其内部计算和I/O操作的时间分别如下：
P1:先计算60ms，然后I/O80ms，最后再计算20ms P2:先计算120ms，然后I/O40ms，最后再计算40ms 调度程序的执行时间不计，在多道批处理系统中，完成这两道程序比单道批处理系统节约的时间是_A____.
A. 100ms B. 120ms C.160ms D. 200ms 银行家算法之例
设系统中有5个进程{P0，P1，P2，P3，P4}和3类资源{A，B，C}，各类资源总数分别为10、5、7，在T0时刻的资源分配情况如下表所示： P0 P1 P2 P3 P4 Max A B C 7 5 3 3 2 2 9 0 2 2 2 2 4 3 3 Allocation A B C 0 1 0 2 0 0 3 0 2 2 1 1 0 0 2 Need A B C 7 4 3 1 2 2 6 0 0 0 1 1 4 3 1 Available A B C 3 3 2
（1）T0时刻系统是否安全，为什么？
（2）P1发出请求向量Request1（1，0，2），分析系统是否可同意请求。 （3）P4发出请求向量Request4（3，3，0），分析系统是否可同意请求。 （4）P0发出请求向量Request0（0，2，0），分析系统是否可同意请求。 （5）在（4）中，若P0发出请求向量Request0（0，1，0），系统是否可同意请求。
回答问题
T0时刻系统是否安全，为什么？ P0 P1 P2 P3 P4
Max A B C 7 5 3 3 2 2 9 0 2 2 2 2 4 3 3 Allocation A B C 0 1 0 2 0 0 3 0 2 2 1 1 0 0 2 Need A B C 7 4 3 1 2 2 6 0 0 0 1 1 4 3 1 Available A B C 3 3 2 P1 P3 P4 P0 P2 Work Work+Allocation A B C A B C 3 3 2 5 3 2 7 4 3 7 4 5 7 5 5 5 3 2 7 4 3 7 4 5 7 5 5 10 5 7 Finish true true true true true
（2）P1发出请求向量Request1（1，0，2），按银行家算法，系统是否同意请求？ Request1(1,0,2)≤Need1(1,2,2) Request1(1,0,2)≤Available(3,3,2)
系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量，由此形成资源变化情况如图 P0 P1 P2 P3 P4 Max A B C 7 5 3 3 2 2 9 0 2 2 2 2 4 3 3 Allocation A B C Need A B C Available A B C 0 1 0 7 4 3 3 3 2 2 0 0 1 2 2 （2 3 0） （3 0 2） （0 2 0） 3 0 2 6 0 0 2 1 1 0 1 1 0 0 2 4 3 1
再利用安全性算法检查此时系统是否安全。
即存在安全序列{P1,P3,P4,P0,P2}，故系统是安全的，可以立即将P1所申请的资源分配给它。
实际上，(1)中的安全序列中的第一个进程就是P1，当然对P1的请求可以满足。
（3）P4发出请求向量Request4(3,3,0)，按银行家算法，分析系统是否可同意请求。 Request4(3,3,0)≤Need4(4,3,1)
Request4(3,3,0)≤Available(2,3,0)，让P4等待。 （4）P0发出请求向量Request0（0，2，0），按银行家算法，分析系统是否可同意请求。 Request0(0,2,0)≤Need0(7,4,3) Request0(0,2,0)≤Available(2,3,0)
系统暂时先假定可为P0分配资源，并修改有关数据 Max A B C Allocation A B C Need A B C Available A B C