缺页否 Y Y Y Y Y Y Y Y Y Y Y Y 缺页次数为12
FIFO算法的情况如下表： 页面走向 物理页0 物理页1 物理页2 缺页否 1 1 Y 2 1 2 Y 3 1 2 3 Y 4 4 2 3 Y 2 1 4 1 3 Y 5 4 1 5 Y 6 6 1 5 Y 2 6 2 5 Y 1 6 2 1 Y 2 3 3 2 1 Y 7 3 7 1 Y 6 3 7 6 Y 3 缺页次数为12
Optimal算法的情况如下表： 页面走向 物理页0 物理页1 物理页2 缺页否 1 1 Y 2 1 2 Y 3 1 2 3 Y 4 1 2 4 Y 2 1 5 1 2 5 Y 6 1 2 6 Y 2 1 2 3 3 2 6 Y 7 3 7 6 Y 6 3 缺页次数为8
假设某系统中有三种资源（R1、R2、R3），在某时刻系统中共有四个进程。进程P1,P2，P3，P4的最大资源需求数向量和此时已分配的资源数向量分别是：
进程 P1 P2 P3 P4 当前已分配到的资源 （1，0，0） （5，1，1） （2，1，1） （0，0，2） 最大资源需求 （3，2，2） （6，1，3） （3，1，4） （4，2，2） 系统中当前可用资源向量为（1，1，2）。问： （1） 如果进程P1发出资源请求向量（1，0，1），系统能否将资源分配给它？ （2） 如果进程P2发出请求向量（1，0，1）呢？
答（1）不可以分配，因为分配后不存在安全序列。分析如下：
P2 P1 P3 P4 P2 P1 P3 WORK 1，1，2 0，1，1 WORK 1，1，2 0，1，1 6，2，3 7，2，3 NEED 1，0，2 1，2，1 1，0，3 4，2，0 NEED 0，0，1 2，2，2 1，0，3 ALLOCATION 5，1，1 2，0，1 2，1，1 0，0，2 ALLOCATION 6，1，2 1，0，0 2，1，1 新WORK 0，1，1 新WORK 0，1，1 6，2，3 7，2，3 9，3，4 FINISH False False False False FINISH True True True 分配给P1：（1，0，1） （2）可以分配，因为存在安全序列，分析如下： 分配给P2：（1，0，1） P4 9，3，4 4，2，0 0，0，2 9，3，6 True 1
3、 在一个多道程序系统中，采用非抢占的最短作业优先算法管理作业。今有如下所示的作
业序列，请列出各个作业开始执行时间、完成时间和周转时间，并填写在下表的适当位置。（注：忽略系统开销，时间为秒。） 作业 P1 P2 P3 P4 到达时间 1 4 5 7 需执行时间 6 6 8 7 1 7 20 13 开始时间 7 13 28 20 完成时间 6 11 23 13 周转时间 （1）T0时刻为安全状态。其中的一个安全序列为（P4，P5，P1，P3，P2） （其他可能的安全序列有：（P4，P5，P1，P2，P3），（P4，P1，X，X，X））
（2）可以为P2分配资源，因为分配后的状态还是安全的，其安全序列的分析如下表：
P4 P5 P1 P2 P3 WORK 1，0，2，0 1，0，1，0 2，1，1，1 2，1，1，1 5，1，2，2 5，2，3，2 NEED 0，0，1，0 2，1，1，0 1，1，0，0 0，1，0，2 3，1，0，0 ALLOCATION 1，1，0，1 0，0，0，0 3，0，1，1 0，1，1，0 1，1，1，0 新WORK 1，0，1，0 2，1，1，1 2，1，1，1 5，1，2，2 5，2，3，2 6，3，4，2 FINISH True True True True True 分配给P2：（0，0，1，0） （3）进程P5再请求资源（0，0，1，0），则不能为之分配资源。因为分配资源后，不存在
安全序列，其分析如下表：
P1 P2 P3 P4 P5 WORK 1，0，1，0 NEED ALLOCATION 新WORK 1，0，0，0 FINISH False False False False False 分配给P5：（0，0，1，0） 1，1，0，0 此时，WORK不能满足任何一个0，1，0，2 进程的请求使之运行结束，即进入了不安全状态。 3，1，0，0 0，0，1，0 2，1，0，0 1、考虑下面的页访问串：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3。假定物理块数为3，若应用下面的页面替换算法，分别会出现多少次缺页？ （1）LRU替换法算法 （2）FIFO替换算法 （3）Optimal替换算法
答：LRU算法的情况如下表： 页面走向 物理页0 物理页1 物理页2 缺页否 1 1 Y 2 1 2 Y 3 1 2 3 Y 4 4 2 3 Y 2 1 4 2 1 Y 5 5 2 1 Y 6 5 6 1 Y 2 5 6 2 Y 1 1 6 2 Y 2 3 1 3 2 Y 7 7 3 2 Y 6 7 3 6 Y 3 缺页次数为12 （4分）
FIFO算法的情况如下表： 页面走向 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 物理页0 物理页1 物理页2 缺页否 1 Y 1 2 Y 1 2 3 Y 4 2 3 Y 4 1 3 Y 4 1 5 Y 6 1 5 Y 6 2 5 Y 6 2 1 Y 3 2 1 Y 3 7 1 Y 3 7 6 Y 缺页次数为12 （4分）
Optimal算法的情况如下表： 页面走向 物理页0 物理页1 物理页2 缺页否 1 1 Y 2 1 2 Y 3 1 2 3 Y 4 1 2 4 Y 2 1 5 1 2 5 Y 6 1 2 6 Y 2 1 2 3 3 2 6 Y 7 3 7 6 Y 6 3 缺页次数为8
2、假设某系统中有三种资源（R1、R2、R3），在某时刻系统中共有四个进程。进程P1,P2，P3，P4的最大资源需求数向量和此时已分配的资源数向量分别是：
进程 P1 P2 P3 P4 当前已分配到的资源 （1，0，0） （5，1，1） （2，1，1） （0，0，2） 最大资源需求 （3，2，2） （6，1，3） （3，1，4） （4，2，2） 系统中当前可用资源向量为（1，1，2）。问： 1如果进程P1发出资源请求向量（1，0，1），系统能否将资源分配给它？ 2如果进程P2发出请求向量（1，0，1）呢？
（1）不可以分配，因为分配后不存在安全序列。分析如下：
P2 P1 P3 P4 WORK 1，1，2 0，1，1 NEED 1，0，2 1，2，1 1，0，3 4，2，0 ALLOCATION 5，1，1 2，0，1 2，1，1 0，0，2 新WORK 0，1，1 FINISH False False False False 分配给P1：（1，0，1） （6分） （2）可以分配，因为存在安全序列，分析如下： P2 P1 P3 P4 （6分）
WORK 1，1，2 0，1，1 6，2，3 7，2，3 9，3，4 NEED 0，0，1 2，2，2 1，0，3 4，2，0 ALLOCATION 6，1，2 1，0，0 2，1，1 0，0，2 新WORK 0，1，1 6，2，3 7，2，3 9，3，4 9，3，6 FINISH True True True True 分配给P2：（1，0，1） 3、若干个等待访问磁盘者依次要访问的柱面为20，44，40，4，80，12，76，假设每移动一个柱面需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。
（1）先来先服务算法； （2）最短寻找时间优先算法。(写出过程) （1）先来先服务算法:3毫秒×292=876毫秒（3分）
使移动臂的移动次序和移动的柱面数(3分): 40 → 20 → 44 → 40 → 4 → 80 → 12 → 76 （20） （24） (4） （36） （76） （68） （64）
共移动292柱面
（2）最短寻找时间优先算法: 3毫秒×120=360毫秒（3分）
使移动臂的移动次序和移动的柱面数(3分): 40 → 44 → 20 → 12 → 4 → 76 → 80 （4） （24） （8） （8） （72） （4） 共移动120柱面
南昌大学 2007～2008学年第二学期期末考试试卷B
1、 某系统中有10台打印机，有三个进程P1，P2，P3分别需要8台，7台和4台。 P1，P2，P3已申请到4台，2台和2台。若此时P3提出还需要使用2台打印机的请求，试问：按银行家算法能分配给P3吗？
答：系统能为进程P3分配二台打印机。因为尽管此时10台打印机已分配给进程P1 4台，P22台和P34台，全部分配完，但P3已分配到所需要的全部4台打印机，它不会对打印机再提出申请，所以它能顺利运行下去，能释放占用的4台打印机，使进程P1，P2均可能获得乘余的要求4台和5台，按银行家算法是安全的。 有一个仓库，可以存放A和B两种产品，但要求： （1）每次只能存放一种产品（A或B）； （2）－N
其中N和M是正整数。试用p、v操作描述产品A和产品B的入库过程。 答：
信号量的定义如下：
Var mutex，SA，SB：semphore＝1,M-1,N-1；（M，N为题目中给出的整数值）。 这里mutex用来做为互斥的信号量，保证每次只能存放一种产品（A或B）；SA用来保证
的值就加1；，每当放入一个B产品，SA的值就加1，SB的值就减1；当然这些操作都是由pv操作来完成的。
具体程序如下：(用C或者类C来写都可以) Begin Prabegin
PA: (表示A产品放置动作对应的进程) Begin Repeat P(SA) P(mutex) 放入一个A产品； V(mutex); V(SB); Until false; End
PB: (表示B产品放置动作对应的进程) Begin Repeat P(SB) P(mutex) 放入一个B产品； V(mutex); V(SA); Until false;
2、 End假设一个系统中有5个进程，到达时间和服务时间见下表，请按照先来
先服务、非抢占及抢占式的短作业优先、响应比高者优先、时间片轮转（q=1）、多级反馈队列（第i级队列的时间片=2i-1）进行调度，算出各种方法得到的完成时间、周转时间、带权周转时间、平均周转时间及平均带权周转时间。
进程 A B C 到达时间 0 2 4 服务时间 3 6 4