OS课后思考题.docx
《OS课后思考题.docx》由会员分享,可在线阅读,更多相关《OS课后思考题.docx(21页珍藏版)》请在冰点文库上搜索。
OS课后思考题
1.一个消费者和一个生产者共用一个缓冲区放置和取出产品。
用信号量机制求解消费者和生产者之间的同步关系
求解过程:
设置:
empty为生产者进程的私用信号量,表示缓冲池中空缓冲区的个数,初值为1。
full为消费者进程的私用信号量,表示缓冲池中满缓冲区的个数,初值为0。
parbegin
proceducer:
begin
repeat
produceaproduct;
wait(empty);
buffer←product;//(putaproductinbuffer)
signal(full);
untilfalse;
end
consumer:
begin
repeat
wait(full);
product←Buffer;//(takeoutaproductfrombuffer)
signal(empty);
consumetheproduct;
untilfalse;
end
parend
2.用信号量机制解决哲学家就餐问题死锁的措施:
(1)把哲学家看做是进程,进程之间是互斥关系。
每一把叉子是相邻两个哲学家共享的公用资源。
(2)规定每个哲学家左右的叉子和哲学家的编号相同。
2.1至多只允许4个哲学家同时进餐,以保证最少有一个哲学家可以进餐,最终才可能由他释放其所用过的两只筷子,从而使更多的哲学家可以进餐。
求解过程:
设置一个信号量sum限制同时进餐的哲学家数目,初值为4。
信号量chopstick[i]表示一只筷子,初值为1。
第i位哲学家的活动用算法描述如下:
ProcessZi(i=0,1,2,3,4)
repeat
wait(sum);//请求进餐
wait(chopstick[i]);//拿左边的筷子
wait(chopstick[(i+1)mod5]);
eat;
signal(chopstick[i]);
signal(chopstick[(i+1)mod5]);
signal(sum);//退出进餐
think;
untilfalse;
2.2仅当两支筷子都可用时才允许拿起筷子
方法1:
利用AND型信号量机制实现:
定义信号量chopstick[i]表示一只筷子,初值为1。
第i位哲学家的活动用算法描述如下:
ProcessZi(i=0,1,2,3,4)
repeat
Swait(chopstick[i],chopstick[(i+1)mod5]);//拿左边和右边的筷子
eat;Ssignal(chopstick[i],chopstick[(i+1)mod5]);think;untilfalse;
方法2:
通过信号量mutex对eat之前的取左侧和右侧筷子的操作进行保护,使之成为一个原子操作,这样可以防止死锁的出现。
定义信号量chopstick[i]表示一只筷子,初值为1。
设置一个信号量mutex使取左侧和右侧筷子的操作成为一个原子操作,初值为1。
第i位哲学家的活动用算法描述如下:
ProcessZi(i=0,1,2,3,4)
repeat
wait(mutex);
wait(chopstick[i]);//拿左边的筷子
wait(chopstick[(i+1)mod5]);
signal(mutex);
eat;
signal(chopstick[i]);
signal(chopstick[(i+1)mod5]);
think;
untilfalse;
2.3让奇数号的哲学家先取左手边的筷子,偶数号的哲学家先取右手边的筷子。
求解过程:
为每一把叉子设置对应的公用信号量chopstick[i],(i=0,1,2,3,4),表示一只筷子,初值为1。
第i位哲学家的活动用算法描述如下:
ProcessZi(i=0,1,2,3,4)
begin
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]);//拿右手边的叉子
eat;
V(chopstick[i]);//放下左手边的叉子
V(chopstick[(i+1)mod5]);//放下右手边的叉子
}
end
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;
wait(rmutex);
Readcount:
=Readcount-1;
IfReadcount:
=0thensignal(wmutex);/*最后一个读进程结束退出*/
signal(rmutex)
untilfalse;
end
begin
repeat
wait(s);
wait(wmutex);/*实现Writer进程间的互斥*/
performwriteoperation;
signal(wmutex);
signal(s);
untilfalse;
end
补充题:
桌上有一只盘子,只能容纳一个水果,每次只能放入或取出一只水果。
爸爸专向盘子中放苹果(apple),妈妈专向盘子中放桔子(orange),一个儿子专等吃盘子中的桔子,一个女儿专等吃盘子中的苹果。
试用信号量机制实现爸爸、妈妈、儿子和女儿之间的同步与互斥关系。
解:
设信号量sp控制盘子里只能放一个水果;初值为1。
设信号量orange表示盘子里有桔子,初值为0。
设信号量apple表示盘子里有苹果,初值为0。
实现爸爸、妈妈、儿子和女儿之间正确同步工作的算法如下:
Var
Plate:
(apple,orange)
sp:
semaphore;
orange:
semaphore;
apple:
semaphore;
sp:
=1;
orange:
=0;
apple:
=0;
Cobegin
Processfather
Begin
L1:
削一个苹果;
wait(sp);
把苹果放入plate;
signal(apple);
GotoL1;
End;
Processmather
Begin
L2:
剥一个桔子;
wait(sp);
把桔子放入plate;
signal(orange);
GotoL2;
End;
Processson
Begin
L3:
wait(orange);
从plate中取桔子;
signal(sp);
吃桔子;
GotoL3;
End;
Processdaughter
Begin
L4:
wait(apple);
从plate中取苹果;
signal(sp);
吃苹果;
GotoL4;
End;
Coend。
四:
3个进程P1、P2、P3互斥使用一个包含N(n>0)个单元的缓冲区。
P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。
请用信号量机制实现者三个进程的同步与互斥活动,并说明所定义的信号量的含义。
要求用伪代码描述。
第三章有关作业和进程调度算法及死锁的习题
1.有一个具有两道作业的批处理系统,作业调度采用短作业优先的调度算法,进程调度采用抢占式的优先级调度算法,在下表的作业序列,作业优先数即为进程优先数,优先数越小优先级越高。
作业名
到达时间
估计运行时间
优先数
A
8:
00
40分钟
4
B
8:
20
30分钟
2
C
8:
30
50分钟
3
D
8:
50
20分钟
5
(1)列出所有作业进入内存时间及结束时间。
(2)计算这批作业的平均周转时间及平均带权周转时间。
解:
作业执行过程如下:
8:
00A到达,内存空,A进入内存,无竞争开始运行;
8:
20B到达,进入内存,优先数为2,由于A的优先数为4,相比B优先级低,被剥夺处理器,B开始运行;
8:
30C到达,内存满,不可进入内存;
8:
50B运行结束,同时D到达,同C争夺内存,由于D运行时间短,按照短作业优先的调度算法,D被调入内存;D与A的优先数相比,A的优先级别高,获得处理器继续运行;
9:
10A运行结束,C进入内存,C的优先级别高于D,C开始运行;
10:
00C运行结束,D开始运行;
10:
20D运行结束。
1)所有作业进入内存时间及结束时间如下表所示:
作业
到达时间
进入内存时间
结束时间
执行时间(分钟)
周转时间
(分钟)
带权周转时间(分钟)
A
8:
00
8:
00
9:
10
40
70
7/4
B
8:
20
8:
20
8:
50
30
30
1
C
8:
30
9:
10
10:
00
50
90
9/5
D
8:
50
8:
50
10:
20
20
90
9/2
2)作业周转时间=作业结束时间-作业到达时间
这批作业的平均周转时间=(70+30+90+90)/4=70分钟
这批作业的平均带权周转时间=(7/4+1+9/5+9/2)/4=2.26
2.有一个四道作业的操作系统,若在一段时间内先后到达6个作业,它们的提交和估计运行时间由下表给出:
作业
提交时间
估计运行时间(分钟)
J1
8:
00
60
J2
8:
20
35
J3
8:
25
20
J4
8:
30
25
J5
8:
35
5
J6
8:
40
10
采用短作业优先调度算法,作业被调入系统后中途不会退出,但作业运行时可被更短作业抢占。
(1)分别给出6个作业的开始执行时间、作业完成时间、作业周转时间。
(2)计算这批作业的平均周转时间。
解答:
作业执行过程如下:
8:
00J1到达,内存空,无竞争,进入内存开始运行;
8:
20J1运行20分钟,剩余40分钟;
J2到达,运行时间为35分钟,小于J1,取代J1开始运行。
8:
25J1剩40分钟,J2剩30分钟;
J3到达,运行时间为20分钟,小于J2,取代J2开始运行。
8:
30J1剩40分钟,J2剩30分钟;J3剩15分钟;
J4到达,运行时间为25分钟,大于J3,J3继续运行。
8:
35J3剩10分钟;
J5到达,运行时间为5分钟,尽管时间最短,但是内存中已有四道作业,因此,J5,不可进入内存,J3继续运行。
8:
40J3剩5分钟;J6到达,同理不可进入内存,J3继续运行。
8:
45J3运行结束;J5最短,进入内存并开始执行。
8:
50J5运行结束;J6进入内存,运行时间10分钟,为最短,开始执行。
9:
00J6运行结束,J1剩40分钟,J2剩30分钟;J4剩25分钟;J4最短,开始运行。
9:
25J4运行结束,J2最短,开始运行。
9:
55J2运行结束,J1开始运行。
10:
35J1运行结束。
1)所有作业的开始执行时间、作业完成时间、作业周转时间,如下表所示:
作业
提交时间
运行时间(分钟)
开始执行时间
完成时间
周转时间(分钟)
平均周转时间(分钟)
J1
8:
00
60
8:
00
10:
35
155
155/60
J2
8:
20
35
8:
20
9:
55
95
95/35
J3
8:
25
20
8:
25
8:
45
20
1
J4
8:
30
25
9:
00
9:
25
55
11/5
J5
8:
35
5
8:
45
8:
50
15
3
J6
8:
40
10
8:
50
9:
00
20
2
2)作业周转时间=作业结束时间-作业到达时间
这批作业的平均周转时间=(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
查页表可知页号3对应物理块号为14。
由地址转换原理可得:
块内位移等于页内位移。
故物理地址=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
3
2
1
4
3
5
4
3
2
1
5
4
4
4
1
1
1
5
5
5
3
3
3
4
4
4
2
2
2
2
2
3
3
3
1
f(4)
f(3)
f
(2)
f
(1)
f(4)
f(3)
上表中,第一行为进程执行时要访问的页面次序,第二行为最先调入主存的页面,最后一行为发生缺页中断时替换的页面。
缺页次数为9,缺页中断率为:
9/12。
分配给该作业4个物理块时,采用FIFO页面替换算法,进程执行过程中页面置换如下表:
4
3
2
1
4
3
5
4
3
2
1
5
4
4
4
4
5
5
5
5
1
1
3
3
3
3
4
4
4
4
5
2
2
2
2
3
3
3
3
1
1
1
1
2
2
2
f(4)
f(3)
f
(2)
f
(1)
f(5)
f(4)
上表中,第一行为进程执行时要访问的页面次序,第二行为最先调入主存的页面,最后一行为发生缺页中断时替换的页面。
缺页次数为10,缺页中断率为:
10/12。
结果分析:
多分配一个物理块没有减少缺页次数。
(3)分配给该作业3个物理块时,采用LRU页面替换算法,进程执行过程中页面置换如下表:
4
3
2
1
4
3
5
4
3
2
1
5
4
4
4
1
1
1
5
2
2
2
3
3
3
4
4
4
4
1
1
2
2
2
3
3
3
3
5
f(4)
f(3)
f
(2)
f
(1)
f(5)
f(4)
f(3)
缺页次数为10,缺页中断率为:
10/12。
分配给该作业4个物理块时,采用LRU页面替换算法,进程执行过程中页面置换如下表:
4
3
2
1
4
3
5
4
3
2
1
5
4
4
4
4
4
4
4
5
3
3
3
3
3
3
3
2
2
5
5
1
1
1
1
2
2
2
f
(2)
f
(1)
f(5)
f(4)
缺页次数为8,缺页中断率为:
8/12。
结果分析:
多分配一个物理块可有效减少缺页次数。
(3)分配给该作业3个物理块时,采用最佳页面替换算法,进程执行过程中页面置换如下表:
4
3
2
1
4
3
5
4
3
2
1
5
4
4
4
4
4
2
1
3
3
3
3
3
3
2
1
5
5
5
f
(2)
f
(1)
f(4)
f
(2)
缺页次数为7,缺页中断率为:
7/12。
分配给该作业4个物理块时,采用最佳页面替换算法,进程执行过程中页面置换如下表:
4
3
2
1
4
3
5
4
3
2
1
5
4
4
4
4
4
1
3
3
3
3
3
2
2
2
2
1
5
5
f(5)
f(4)
缺页次数为6,缺页中断率为:
6/12。
结果分析:
多分配一个物理块可减少缺页次数。
(2009年考研题)46.(8分)请求分页管理系统中,假设某进程的页表内容如下表所示。
页表内容
页号
页框(PageFrame)号
有效位(存在位)
0
101H
1
1
—
0
2
254H
1
页面大小为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