OS课后思考题Word文档下载推荐.docx
《OS课后思考题Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《OS课后思考题Word文档下载推荐.docx（21页珍藏版）》请在冰点文库上搜索。
wait（chopstick[（i+1）mod5]）；
eat；
signal（chopstick[i]）；
signal（chopstick[（i+1）mod5]）；
signal（sum）；
//退出进餐
think；
2.2仅当两支筷子都可用时才允许拿起筷子
方法1：
利用AND型信号量机制实现：
定义信号量chopstick[i]表示一只筷子，初值为1。
Swait（chopstick[i],chopstick[（i+1）mod5]）；
//拿左边和右边的筷子
Ssignal（chopstick[i],chopstick[（i+1）mod5]）；
方法2：
通过信号量mutex对eat之前的取左侧和右侧筷子的操作进行保护，使之成为一个原子操作，这样可以防止死锁的出现。
设置一个信号量mutex使取左侧和右侧筷子的操作成为一个原子操作，初值为1。
wait（mutex）；
signal（mutex）；
2.3让奇数号的哲学家先取左手边的筷子，偶数号的哲学家先取右手边的筷子。
为每一把叉子设置对应的公用信号量chopstick[i]，（i=0,1,2,3,4），表示一只筷子，初值为1。
think;
ifimod2==0then//偶数号哲学家
{P（chopstick[（i+1）mod5]）;
//拿右手边的叉子
P（chopstick[i]）;
//拿左手边的叉子
eat;
V（chopstick[（i+1）mod5]）;
//放下右手边的叉子
V（chopstick[i]）;
//放下左手边的叉子
}
else//奇数号哲学家
{P（chopstick[i]）;
P（chopstick[（i+1）mod5]）;
}
3.读者-写者问题（写者优先）
有一组并发进程：
Reader与Writer进程，共享一组数据区
Ø
要求：
允许多个Reader进程同时执行读操作
不允许多个Writer进程同时操作
不允许Reader与Writer进程同时操作
一旦有Writer进程到达，后续的Reader进程必须等待。
而且无论是否有读者在读文件。
答案：
使用Readcount对Reader进程计数，初值为0；
rmutex是对变量Readcount进行互斥操作的信号量，初值设为1；
Wmutex是写信号量，初值设为1。
增加一个信号量S，用于在写进程到达后封锁后续的读者，初值为1。
Varrmutex，wmutex，s:
semaphore:
=1,1,1；
Readcount:
integer:
=0；
Reader进程：
Begin
repeat
wait（s）;
wait（rmutex）;
ifReadcount:
=0thenwait（wmutex）;
/*读进程把写进程阻塞*/
Readcount:
=Readcount+1;
signal（rmutex）;
signal（s）;
performreadoperation;
Readcount:
=Readcount-1;
IfReadcount:
=0thensignal（wmutex）;
/*最后一个读进程结束退出*/
signal（rmutex）
end
wait（wmutex）;
/*实现Writer进程间的互斥*/
performwriteoperation;
signal（wmutex）;
untilfalse；
补充题：
桌上有一只盘子，只能容纳一个水果，每次只能放入或取出一只水果。
爸爸专向盘子中放苹果（apple），妈妈专向盘子中放桔子（orange），一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子中的苹果。
试用信号量机制实现爸爸、妈妈、儿子和女儿之间的同步与互斥关系。
解：
设信号量sp控制盘子里只能放一个水果；
初值为1。
设信号量orange表示盘子里有桔子，初值为0。
设信号量apple表示盘子里有苹果，初值为0。
实现爸爸、妈妈、儿子和女儿之间正确同步工作的算法如下：
Var
Plate:
（apple,orange）
sp:
semaphore;
orange:
apple:
=1;
=0;
Cobegin
Processfather
Begin
L1：
削一个苹果；
wait（sp）;
把苹果放入plate;
signal（apple）;
GotoL1;
End;
Processmather
L2：
剥一个桔子；
wait（sp）;
把桔子放入plate;
signal（orange）;
GotoL2;
Processson
L3：
wait（orange）;
从plate中取桔子;
signal（sp）;
吃桔子；
GotoL3;
Processdaughter
L4：
wait（apple）;
从plate中取苹果;
吃苹果；
GotoL4;
Coend。
四：
3个进程P1、P2、P3互斥使用一个包含N（n>
0）个单元的缓冲区。
P1每次用produce（）生成一个正整数并用put（）送入缓冲区某一空单元中；
P2每次用getodd（）从该缓冲区中取出一个奇数并用countodd（）统计奇数个数；
P3每次用geteven（）从该缓冲区中取出一个偶数并用counteven（）统计偶数个数。
请用信号量机制实现者三个进程的同步与互斥活动，并说明所定义的信号量的含义。
要求用伪代码描述。
第三章有关作业和进程调度算法及死锁的习题
1.有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用抢占式的优先级调度算法，在下表的作业序列，作业优先数即为进程优先数，优先数越小优先级越高。
作业名
到达时间
估计运行时间
优先数
A
8:
00
40分钟
4
B
20
30分钟
2
C
30
50分钟
3
D
50
20分钟
5
（1）列出所有作业进入内存时间及结束时间。
（2）计算这批作业的平均周转时间及平均带权周转时间。
作业执行过程如下：
00A到达，内存空，A进入内存，无竞争开始运行；
20B到达，进入内存，优先数为2，由于A的优先数为4，相比B优先级低，被剥夺处理器，B开始运行；
30C到达，内存满，不可进入内存；
50B运行结束，同时D到达，同C争夺内存，由于D运行时间短，按照短作业优先的调度算法，D被调入内存；
D与A的优先数相比，A的优先级别高，获得处理器继续运行；
9:
10A运行结束，C进入内存，C的优先级别高于D，C开始运行；
10:
00C运行结束，D开始运行；
20D运行结束。
1）所有作业进入内存时间及结束时间如下表所示：
作业
进入内存时间
结束时间
执行时间（分钟）
周转时间
（分钟）
带权周转时间（分钟）
10
40
70
7/4
30
1
50
90
9/5
20
9/2
2）作业周转时间=作业结束时间-作业到达时间
这批作业的平均周转时间=（70+30+90+90）/4=70分钟
这批作业的平均带权周转时间=（7/4+1+9/5+9/2）/4=2.26
2.有一个四道作业的操作系统，若在一段时间内先后到达6个作业，它们的提交和估计运行时间由下表给出：
提交时间
估计运行时间（分钟）
J1
60
J2
35
J3
25
J4
J5
35
J6
40
采用短作业优先调度算法，作业被调入系统后中途不会退出，但作业运行时可被更短作业抢占。
（1）分别给出6个作业的开始执行时间、作业完成时间、作业周转时间。
（2）计算这批作业的平均周转时间。
解答：
00J1到达，内存空，无竞争,进入内存开始运行；
20J1运行20分钟，剩余40分钟；
J2到达，运行时间为35分钟，小于J1，取代J1开始运行。
25J1剩40分钟，J2剩30分钟；
J3到达，运行时间为20分钟，小于J2，取代J2开始运行。
30J1剩40分钟，J2剩30分钟；
J3剩15分钟；
J4到达，运行时间为25分钟，大于J3，J3继续运行。
35J3剩10分钟；
J5到达，运行时间为5分钟，尽管时间最短，但是内存中已有四道作业，因此，J5，不可进入内存，J3继续运行。
40J3剩5分钟；
J6到达，同理不可进入内存，J3继续运行。
45J3运行结束；
J5最短，进入内存并开始执行。
50J5运行结束；
J6进入内存，运行时间10分钟，为最短，开始执行。
00J6运行结束，J1剩40分钟，J2剩30分钟；
J4剩25分钟；
J4最短，开始运行。
25J4运行结束，J2最短，开始运行。
55J2运行结束，J1开始运行。
35J1运行结束。
1）所有作业的开始执行时间、作业完成时间、作业周转时间，如下表所示：
运行时间（分钟）
开始执行时间
完成时间
周转时间（分钟）
平均周转时间（分钟）
155
155/60
55
95
95/35
45
11/5
15
这批作业的平均周转时间=（155+95+20+55+15+20）/6=60分钟
这批作业的平均带权周转时间=（155/60+195/35+1+11/5+3+2）/4=4.01
1.某系统有11台打印机，N个并发进程共享打印机资源，每个进程需要3台，但N的取值不超过（）时，系统不会发生死锁。
A.4B.5C.6D.7
2．在分时操作系统中，进程调度经常采用（）算法。
A.先来先服务B.最高优先权C.时间片轮转D.随机
3．在的多道程序设计的操作系统的运行过程中，不断地选择新进程进行来实现CPU的共享，但其中（）不是引起操作系统选择新进程的直接原因。
A.运行进程的时间片用完B.运行进程出错
C.有新进程进入就绪队列D.运行进程要等待某一事件发生
4．在（）情况下，系统出现死锁。
A.计算机系统发生重大故障
B.有多个封闭的进程同时存在
C.若干进程因竞争资源而无休止地相互等待他方释放已占有的资源
D．资源数远远小于进程数或进程同时申请的资源数远远超过资源总数
5．资源的按序分配策略可以破坏（）条件
A.互斥B.请求与保持C.不剥夺D.环路等待
第四章存储器管理
1.在一分页存储管理系统，页面大小为4KB。
已知某进程的第0、1、2、3、4页依次存在内存中的6、8、10、14、16物理块号中，现有逻辑地址为12138B,3A5CH，分别求其所在的页号、页内相对地址、对应的物理块号以及相应的物理地址。
（1）已知页面大小4KB=4096D
页号p=INT[12138/4096]=2,页内位移d=12138MOD4096=3946D
查页表可知页号2对应物理块号为10。
由地址转换原理可得：
块内位移等于页内位移。
故物理地址=10*4096+3946=44906B
（2）解法一：
已知页面大小4KB=212B，占12位，逻辑地址长度为16位，故高4位为页号，低12位为页内位移。
逻辑地址为：
3A5CH=11101001011100B。
则页号为：
3。
查页表可知页号3对应物理块号为14。
块内位移等于页内位移，物理地址高4位为物理块号，低12位为块内位移。
故物理地址为：
1110101001011100B=EA5CH=59996D
解法二：
已知页面大小4KB=4096D，逻辑地址3A5CH=14940D。
页号p=INT[14940/4096]=3,页内位移d=14940MOD4096=2652D
故物理地址=14*4096+2652=59996D=EA5CH
4.26在一个请求分页系统中，采用FIFO、最近最久未使用、最佳页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数M分别为3和4时，试计算在访问过程中所发生的缺页次数和缺页率。
并比较所得结果。
（1）分配给该作业3个物理块时，采用FIFO页面替换算法，进程执行过程中页面置换如下表:
4
f（4）
f（3）
f
（2）
f
（1）
上表中，第一行为进程执行时要访问的页面次序，第二行为最先调入主存的页面，最后一行为发生缺页中断时替换的页面。
缺页次数为9，缺页中断率为：
9/12。
分配给该作业4个物理块时，采用FIFO页面替换算法，进程执行过程中页面置换如下表:
f（5）
缺页次数为10，缺页中断率为：
10/12。
结果分析：
多分配一个物理块没有减少缺页次数。
（3）分配给该作业3个物理块时，采用LRU页面替换算法，进程执行过程中页面置换如下表:
1
2
3
分配给该作业4个物理块时，采用LRU页面替换算法，进程执行过程中页面置换如下表:
5
缺页次数为8，缺页中断率为：
8/12。
多分配一个物理块可有效减少缺页次数。
（3）分配给该作业3个物理块时，采用最佳页面替换算法，进程执行过程中页面置换如下表:
缺页次数为7，缺页中断率为：
7/12。
分配给该作业4个物理块时，采用最佳页面替换算法，进程执行过程中页面置换如下表:
缺页次数为6，缺页中断率为：
6/12。
多分配一个物理块可减少缺页次数。
（2009年考研题）46.（8分）请求分页管理系统中，假设某进程的页表内容如下表所示。
页表内容
页号
页框（PageFrame）号
有效位（存在位）
101H
—
254H
页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为108ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法（LRU）和局部淘汰策略。
假设①TLB初始为空；
②地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；
③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。
设有虚地址访问序列2362H、1565H、25A5H，请问：
（1）依次访问上述三个虚地址，各需多少时间？
给出计算过程。
（2）基于上述访问序列，虚地址1565H的物理地址是多少？
请说明理由。
（1）根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。
页面大小为4KB，即212，则得到页内位移占虚地址的低12位，页号占剩余高位。
可得三个虚地址的页号P如下（十六进制的一位数字转换成4位二进制，因此，十六进制的低三位正好为页内位移，最高位为页号）：
2362H：
P=2，访问快表10ns，因初始为空，访问页表100ns得到页框号，合成物理地址后访问主存100ns，共计10ns+100ns+100ns=210ns。
1565H：
P=1，访问快表10ns，落空，访问页表100ns落空，进行缺页中断处理108ns，合成物理地址后访问主存100ns，共计10ns+100ns+108ns+100ns≈318ns。
25A5H：
P=2，访问快表，因第一次访问已将该页号放入快表，因此花费10ns便可合成物理地址，访问主存100ns，共计10ns+100ns=110ns
（2）当访问虚地址1565H时，产生缺页中断，合法驻留集为2，必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H的对应页框号为101
升级会员 