本文共 7051 字，大约阅读时间需要 23 分钟。
目录
处理器调度算法计算题
1.设有按P1、P2、P3、P4次序到达的4个进程，CPU阵法时间如表所示，采用先到先得服务算法和最短作业优先算法，画出甘特图，并计算各自的平均等待时间。
| 进程 | CPU阵法时间/ms |
| P1 | 20 |
| P2 | 8 |
| P3 | 5 |
| P4 | 18 |
（1）采用先到先得服务算法，甘特图如下：
| P1 | P2 | P3 | P4 |
0 20 28 33 51
平均等待时间=(0 ＋20+28 +33 )/4 ms = 20.25 ms。
（2）采用最短作业优先算法，甘特图如下：
| P3 | P2 | P4 | P1 |
0 5 13 31 51
平均等待时间=(0+5+ 13 +31)/4 ms = 12.25 ms。
2.设有周期性实时任务集如下表所示，用EDF算法和RMS算法是否可以调度？画出相应的Gantt图。
| 任务 | 发生周期Ti | 处理时间Ci |
| A | 30 | 10 |
| B | 40 | 15 |
| C | 50 | 5 |
答：由于
因而采用EDF算法一定可以调度，其Gantt图为：
由于
因而采用RMS算法不可调度。
3.设有4个作业J1、J2、J3、J4，其提交时刻与运行时间如下。试采用先到先服务、最短作业优先、最高响应比优先算法,分别求出各个作业的周转时间，带权周转时间,以及所有作业的平均周转时间，平均带权周转时间。
1. 执行时间顺序为J1-J2-J3-J4
作业的平均周转时间=（120+160+160+188）/4=157 min 约为2.62h
平均带权周转时间=(120/120+160//60+160/30+188/48)/4=3.23
2. SJB执行时间顺序为J1-J3-J4-J2，如图所示。
作业的平均周转时间=（120+238+100+128）/4=146.5min约为2.44h
平均带权周转时间=(120/120+238/60+100/30+128/48)/4=2.74
3. HRN执行时间顺序为J1-J3-J2-J4，如图所示。
作业的平均周转时间=（120+190+100+188）/4=149.5min约为2.49h
平均带权周转时间=(120/12/+190/60+100/30+188/48)/4=2.85
PV操作
4.关于读者/写者问题,有人给出如下改进解法: 由于s以及读者和写者对s的操作，读者和写者都不会无限等待，因而算法不会出现饿死现象，是一个公平的解法
semaphore r_w_w, mutex, s; (初值均为1)
int count; (初值为0)
| 读者活动： P(s); P(mutex); count++; if (count= =1) P(r_w_w); V(mutex); V(s); {读操作} P(mutex); count--; If (count= =0) V(r_w_w); V(mutex); | 写者活动： P(s); P(r_w_w); {写操作} V(r_w_w); V(s); |
PV互斥信号量
5.用P、v操作解决读者和写者之间的同步问题，且写者优先。
这里仍需设置 readcount 记录读者数，rmutex是读者互斥访问 readcount 的信号量，rwmutex是读者与写者互斥访问文件的信号量。另外再设 writecount 记录写者数，wmutex是写者互斥访问 writecount 的信号量。为了使写者优先，需要再设置两个信号量z和x,z控制所有读者按照FCFS策略排队。x使一个读者和一个写者竞争访问文件。只要在x上等待的写者能继续执行，其他写者便可以直接竞争写者之间文件的互斥访问权，从而实现写者优先。
int readcount, writecount;
semaphore rmutex =1, wmutex = 1, rwmutex = 1, z = 1 ,x = 1 ;
void reader( ){
while(1){
p(z); //所有读进程在z上排队
p(x); //—个读进程与一个写进程在x上竞争
p(mutex); //读进程互斥访问readcount
++readcount;
if(readcount= = 1) p(rwmutex ) ;
v(mutex);
v(z);
v(x);
read data; //临界区
p(rmutex);
}
}
void writer( ){
while(1){
p(wmutex); //写进程互斥访问writecount
++ writecount;
if(writecount==1) p(x); //一个写进程在x上排队
v(wmutex);
p(rwmutex); //其他写进程在rwmutex上排队
write data;
v(rwmutex);
p(wmutex);
--writecount;
if(writecount==0) v(x); //写进程都写完时,通过v(x)允许读进程读
v(wmutex);
}
}
互斥信号量
6.某单位为节省开支,决定建造男女共用的单性洗浴间。为满足社会风化要求,洗浴间在任何时刻均不允许不同性别的人同时进入。编写一个管程,实现对洗浴间的管理。假定洗浴e中同性别人数没有限制。该管程中包括如下外部函数:
woman_wants_to_enter;
man_wants_to_enter;
woman_leave;
man_leave。
银行家算法
7．在银行家算法中，若出现如下资源分配情况：
Allocation Need Available
A B C D A B C D A B C D
P0: 0 0 3 2 0 0 1 2 1 6 2 3
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
试问：
(1)当前状态是否安全？
(2)如果进程P2提出安全请求Request[2]=(1,2,2,2),系统能否将资源分配给它？说明原因．
解：
（1）当前状态是安全状态。可以找到一个安全进程序列<p0,p3，p4，p1,p2>，它使Finish[i]=true，因而可以断言系统当前处于安全状态．
（2）系统不能将资源分配给它。运行银行家算法，由于Request[2]=（1, 2, 2, 2）<Need[2]=（2, 3, 5, 6），因而请求合法。进一步，Request[2]=（1, 2, 2, 2）<Available=（1, 6, 2, 3），故该请求是可以满足的。假设将资源分配给p2，则系统状态变为:
Allocation Need Available
A B C D A B C D A B C D
P0: 0 0 3 2 0 0 1 2 0 4 0 1
P1: 1 0 0 0 1 7 5 0
P2: 2 5 7 6 1 1 3 4
P3: 0 3 3 2 0 6 5 2
P4: 0 0 1 4 0 6 5 6
运行安全性检测算法，Work=Available=（0, 4, 0, 1），Finish[i]=false，此时所有Need[i]￡Work[i]均不成立，结果Finish[i]均为false，不存在安全进程序列，系统处于不安全状态。系统将取消资源分配并恢复原来状态，进程p2等待。
死锁检查算法
8.某系统采用死锁检测手段发现死锁，设系统中资源类集合为{A，B，C}，资源类A中共有8个实例，资源类B中共有6个实例，资源类C中共有5个实例．又设系统中进程集合为{p1,p2,p3,p4,p5,p6}，某时刻系统状态如下：
Allocation Need Available
A B C A B C A B C
p1: 1 0 0 0 0 0 2 2 1
p2: 3 2 1 0 0 0
p3: 0 1 2 2 0 2
p4: 0 0 0 0 0 0
p5: 2 1 0 0 3 1
p6: 0 0 1 0 0 0
- 在上述状态下系统依次接受如下请求：Request[1]=(1,0,0)；Request[2]=(2,1,0)；Request[4]=(0,0,2)。给出系统状态变化情况，并说明没有死锁。
- 在由(1)所确定的状态下系统接收如下请求：Request[1]=(0,3,1)，说明此时已发生死锁，并找出参与死锁的进程。
解：
（1）①系统接受请求：Request[1]=(1,0,0)，Request[1]< Available,可以执行分配，那么系统状态变为：
Allocation Need Available
A B C A B C A B C
p1: 2 0 0 0 0 0 1 2 1
p2: 3 2 1 0 0 0
p3: 0 1 2 2 0 2
p4: 0 0 0 0 0 0
p5: 2 1 0 0 3 1
p6: 0 0 1 0 0 0
在该状态下运行死锁检测算法，可以找到一个进程序列<p4,p1,p2,p3,p5,p6>，它使Finish[i]=true，对于所有1≤i≤6，因而可以断言系统当前没有进入死锁状态。
②系统接受请求：Request[2]=(2,1,0)，Request[2]>Available,系统只接受请求，无法实现资源分配，那么系统状态变为：
Allocation Need Available
A B C A B C A B C
p1: 2 0 0 0 0 0 1 2 1
p2: 3 2 1 2 1 0
p3: 0 1 2 2 0 2
p4: 0 0 0 0 0 0
p5: 2 1 0 0 3 1
p6: 0 0 1 0 0 0
在该状态下运行死锁检测算法，可以找到一个进程序列<p4,p1,p2,p3,p5,p6>，它使Finish[i]=true，对于所有1≤i≤6，因而可以断言系统当前没有进入死锁状态。
③系统接受请求：Request[4]=(0,0,2)，Request[4]>Available,系统只接受请求，无法实现资源分配，那么系统状态变为：
Allocation Need Available
A B C A B C A B C
p1: 2 0 0 0 0 0 1 2 1
p2: 3 2 1 2 1 0
p3: 0 1 2 2 0 2
p4: 0 0 0 0 0 2
p5: 2 1 0 0 3 1
p6: 0 0 1 0 0 0
在该状态下运行死锁检测算法，可以找到一个进程序列< p1,p2,p3, p4,p5,p6>，它使Finish[i]=true，对于所有1≤i≤6，因而可以断言系统当前没有进入死锁状态。
(2)在（1）状态下系统接收如下请求：Request[1]=(0,3,1)，Request[1]>Available,系统只接受请求，无法实现资源分配，则系统状态变为：
Allocation Need Available
A B C A B C A B C
p1: 2 0 0 0 3 1 1 2 1
p2: 3 2 1 2 1 0
p3: 0 1 2 2 0 2
p4: 0 0 0 0 0 2
p5: 2 1 0 0 3 1
p6: 0 0 1 0 0 0
在该状态下运行死锁检测算法，找不到一个进程序列使Finish[i]=true，对于所有1≤i≤6，因为存在i∈{1，2，3，5}，使Finish[i]=false，因而可以断言系统已经进入死锁状态，进程p1,p2,p3,p5卷入死锁．
缺页置换算法
9.设某进程页面的访问序列为4,3,2,1,4,3,5,4,3，2,1,5，当分配给该进程的内存页框数分别为3和4时，对于先进先出，最近最少使用，最佳页面置换算法，分别发生多少次缺页中断？
答：
分配的页框数为3时：
FIFO:
| 4 | 3 | 2 | 1 | 4 | 3 | 5 | 4 | 3 | 2 | 1 | 5 |
| 4 | 4 | 4 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 5 | 5 |
| 3 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 2 | 2 | 2 | |
| 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 1 | 1 | ||
| × | × | × | × | × | × | × | √ | √ | × | × | √ |
共缺页9次
LRU:
| 4 | 3 | 2 | 1 | 4 | 3 | 5 | 4 | 3 | 2 | 1 | 5 |
| 4 | 4 | 4 | 1 | 1 | 1 | 5 | 5 | 5 | 2 | 2 | 2 |
| 3 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 4 | 1 | 1 | |
| 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 5 | ||
| × | × | × | × | × | × | × | √ | √ | × | × | × |
共缺页10次
OPT:
| 4 | 3 | 2 | 1 | 4 | 3 | 5 | 4 | 3 | 2 | 1 | 5 |
| 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 2 | 2 | 2 |
| 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 1 | 1 | |
| 2 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 5 | 5 | ||
| × | × | × | × | √ | √ | × | √ | √ | × | × | √ |
共缺页7次
分配的页框数为4时：
FIFO:
| 4 | 3 | 2 | 1 | 4 | 3 | 5 | 4 | 3 | 2 | 1 | 5 |
| 4 | 4 | 4 | 4 | 4 | 4 | 5 | 5 | 5 | 5 | 1 | 1 |
| 3 | 3 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 5 | |
| 2 | 2 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | ||
| 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | |||
| × | × | × | × | √ | √ | × | × | × | × | × | × |
共缺页10次
LRU:
| 4 | 3 | 2 | 1 | 4 | 3 | 5 | 4 | 3 | 2 | 1 | 5 |
| 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 5 |
| 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | |
| 2 | 2 | 2 | 2 | 5 | 5 | 5 | 5 | 1 | 1 | ||
| 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | |||
| × | × | × | × | √ | √ | × | √ | √ | × | × | × |
共缺页8次
OPT：
| 4 | 3 | 2 | 1 | 4 | 3 | 5 | 4 | 3 | 2 | 1 | 5 |
| 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 1 | 1 |
| 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | |
| 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | ||
| 1 | 1 | 1 | 5 | 5 | 5 | 5 | 5 | 5 | |||
| × | × | × | × | √ | √ | × | √ | √ | √ | × | √ |
共缺页6次
分页管理
10.请求分页管理系统中，假设某进程的页表内容如下表所示。
页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为108ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法（LRU）和局部淘汰策略。假设：
①TLB初始为空；
②地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；
③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列137H 、565H、15A5H，请问：
| 页号 | 页框号 | 有效位（存在位） |
| 0 | 101H | 1 |
| 1 | -- | 0 |
| 2 | 254H | 1 |
（1） 依次访问上述三个虚地址，各需多少时间？给出计算过程。
（2） 基于上述访问序列，虚地址258H的物理地址是多少？请说明理由。
（1）根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。页面大小为4KB，即212，则得到页内位移占虚地址的低12位，页号占剩余高位。可得三个虚地址的页号P如下（十六进制的一位数字转换成4位二进制，因此，十六进制的低三位正好为页内位移，最高位为页号）：
137H：P=0，访问快表10ns，因初始为空，访问页表100ns得到页框号，合成物理地址后访问主存100ns，共计10ns+100ns+100ns=210ns。
565H：P=0，访问快表，因第一次访问已将该页号放入快表，因此花费10ns便可合成物理地址，访问主存100ns，共计10ns+100ns=110ns。
15A5H：P=1，访问快表10ns，落空，访问页表100ns落空，进行缺页中断处理108ns，合成物理地址后访问主存100ns，共计10ns+100ns+108ns+100ns≈108ns。
（2）访问1565H时,1号页面在内存中,页框号与15A5H相同。前面当访问虚地址15A5H时，访问页表发现1号页不在内存中，产生缺页中断，合法驻留集为2，必须从页表中淘汰一个页面，根据题目的置换算法，最近访问的都是0号页的内容，0号页不应被淘汰。应淘汰2号页面，因此1号页面装入时对应的页框号为254H。由此可得1565H的物理地址为254565H。
段式存储管理
11.在某个段式存储管理系统中，进程P的段表如下表，求表中各逻辑地址对应的物理地址
| 段号 | 段内位移 |
| 0 | 430 |
| 1 | 15 |
| 2 | 500 |
| 3 | 400 |
| 4 | 112 |
解：
| 段号 | 段内位移 | 物理地址 |
| 0 | 430 | 680 |
| 1 | 15 | 2365 |
| 2 | 500 | 越界 |
| 3 | 400 | 1750 |
| 4 | 112 | 越界 |
页式管理
12.在某页式管理系统，某进程页表如下，已知页面大小为1024B，试将逻辑地址1012、2248、3010、4020、5018转化为相应的物理地址。
| 页号 | 页框号 |
| 0 | 5 |
| 2 | 8 |
| 2 | 8 |
| 3 | 1 |
| 4 | 6 |
解：
| 逻辑地址 | 页号 | 页内地址 | 页框号 | 物理地址 |
| 1012 | 0 | 1012 | 5 | 5*1024+1012=6132 |
| 2248 | 2 | 200 | 8 | 8*1024+200=8392 |
| 3010 | 2 | 962 | 8 | 8*1024+962=9154 |
| 4020 | 3 | 948 | 1 | 1*1024+948=1972 |
| 5018 | 4 | 922 | 6 | 6*1024+922=7066 |
转载地址：http://whdef.baihongyu.com/