操作系统计算题总结汇编.docx
《操作系统计算题总结汇编.docx》由会员分享，可在线阅读，更多相关《操作系统计算题总结汇编.docx（35页珍藏版）》请在冰点文库上搜索。
操作系统计算题总结汇编
应用类型知识要点一：
进程同步问题
整形信号量：
未遵循“让权等待原则”
wait（S）:
whileS<=0dono-op;
S:
=S-1;
signal（S）:
S:
=S+1
记录型信号量：
执行wait操作时，信号量的值加1，信号量的值小于0时阻塞；
执行signal操作时，信号量的值减1，信号量的值小于等于0时唤醒阻塞中的进程。
typesemaphore=record
value:
integer;
L:
listofprocess;
end
procedurewait（S）
varS:
semaphore;
begin
S.value=S.value-1;
ifS.value<0thenblock（S.L）;
end
proceduresignal（S）
varS:
semaphore;
begin
S.value:
=S.value+1;
ifS.value<=0thenwakeup（S.L）;
end
Ø生产者-消费者问题
Ø读者-写者问题
Ø哲学家进餐问题
Ø理发室问题
进程同步问题求解要领
Ø认真审题、确立信号量及关键变量
Ø构建算法基本步骤及逻辑结构
Ø资源信号量申请先于互斥信号量申请
Øwait操作与signal操作配对出现
利用信号量实现互斥
主程序
子程序
Varmutex:
semaphore:
=1;
begin
parbegin
process1;
process2;
parend
end
process1
begin
repeat
wait（mutex）;
临界区
signal（mutex）;
……
untilfalse
end
process2
begin
repeat
wait（mutex）;
临界区
signal（mutex）
……
untilfalse
end
1.互斥信号量初值为1
2.互斥信号量wait和signal肯定出现在同一进程中，并出现在需要互斥访问数据（临界资源）前后
利用信号量描述前趋关系
Vara,b,c,d,e,f,g,h:
semaphore:
=0,0,0,0,0,0,0,0;
begin
parbegin
beginS1;signal（a）;signal（b）;end
beginwait（a）;S2;signal（c）;signal（d）;end
beginwait（b）;S3;signal（e）;end
beginwait（c）;S4;signal（f）;end
beginwait（d）;S5;signal（g）;end
beginwait（e）;S6;signal（h）;end
beginwait（f）;wait（g）;wait（f）;S7;end
parend
end
首先应找出所有的前趋关系。
然后，对每一种前趋关系，如Si->Sj，专门设置一初值为0的信号量，并在Si结束之后执行对该信号量的signal操作，而在Sj开始之前执行对该信号量的wait操作，这样便可保证程序段Si执行完后才执行程序段Sj。
生产者-消费者问题
主程序（n为常量）
Varbuffer:
array[0,…,n-1]ofitem;
in,out:
integer:
=0,0;
mutex,empty,full:
semaphore:
=1,n,0;
begin
parbegin
producer1;…;produceri;…;producerM;
consumer1;…consumerj;…;consumerN;
parend
end
生产者子程序
消费者子程序
produceri
Varnextp:
item;
begin
repeat
Produceaniteminnextp;
wait（empty）;wait（mutex）;
buffer[in]:
=nextp;
in=（in+1）modn;
signal（mutex）;signal（full）;
untilfalse
end
consumerj
Varnextc:
item;
begin
repeat
wait（full）;wait（mutex）;
nextc:
=buffer[out];
out:
=（out+1）modn;
signal（mutex）;signal（empty）;
Consumetheiteminnextc;
untilfalse
end
生产者子程序（基于AND信号量）
消费者子程序（基于AND信号量）
produceri
begin
repeat
Produceaniteminnextp;
Swait（empty,mutex）;
buffer[in]=nextp;
in:
=（in+1）modn;
Signal（mutex,full）;
untilfalse
end
consumerj
begin
repeat
Swait（full,mutex）;
nextc:
=buffer[out];
out:
=（out+1）modn;
Ssignal（mutex,empty）;
Consumetheiteminnextc;
untilfalse
end
读者-写者问题（读者优先）
主程序
Varreadercount:
integer:
=0;
rcmutex,wmutex:
semaphore:
=1,1;
begin
parbegin
reader1;…;readeri;…;readerM;
writer1;…;writerj;…;writerN;
parend
end
读者
readeri
begin
repeat
wait（rcmutex）;
ifreadercount=0thenwait（wmutex）;
readercount:
=readercount+1;
signal（rcmutex）;
Performreadoperation;
wait（rcmutex）;
readercount:
=readercount-1;
ifreadercount=0thensignal（wmutex）;
signal（rcmutex）;
untilfalse
end
写者
writerj
begin
repeat
wait（wmutex）;
Performwriteoperation;
signal（wmutex）;
untilfalse;
end
readercount:
读者数
rcmutex:
读者进程中用于readercount变量的互斥访问
wmutex:
用于读者与写者、写者与写者之间的互斥访问
写者与第一个读者竞争wmutex。
一旦读者获得wmutex，那么直到所有读者执行结束由最后一个读者释放，而每个写者执行结束都释放，所以读者优先写者执行。
读者-写者问题（写者优先）
主程序
Varreadercount,writercount:
integer:
=0,0;
rcmutex,wcmutex,wmutex,S:
semaphore:
=1,1,1,1;
begin
parbegin
reader1;…;readeri;…;readerM;
writer1;…;writerj;…;writerN;
parend
end
读者
readeri
begin
repeat
wait（S）;
wait（rcmutex）;
ifreadercount=0thenwait（wmutex）;
readercount:
=readercount+1;
signal（rcmutex）;
signal（S）;
Performreadoperation;
wait（rcmutex）;
readercount:
=readercount-1;
ifreadercount=0thensignal（wmutex）;
signal（rcmutex）;
untilfalse;
end
写者
writerj
begin
repeat
wait（wcmutex）;
ifwritercount=0thenwait（S）;
writercount:
=writercount+1;
signal（wcmutex）;
wait（wmutex）;
Performwriteoperation;
signal（wmutex）;
wait（wcmutex）;
writercount:
=writercount-1;
ifwritercount=0thensignal（S）;
signal（wcmutex）;
untilfalse
end
rcmutex:
读者进程中用于readercount变量的互斥访问
wcmutex:
写者进程中用于writercount变量的互斥访问
wmutex:
用于读者与写者、写者与写者之间的互斥访问
读者与第一个写者竞争S信号量。
一旦读者获得S信号量，那么直到所有读者执行结束由最后一个写者释放，而每个读者执行结束都释放，所以写者优先读者执行。
读者-写者问题（限定读者数）
主程序
VarRN:
integer:
=10;
rmax,wmutex:
semaphore:
=RN,1;
begin
parbegin
reader1;…;readeri;…;readerM;
writer1;…;writerj;…;writerN;
parend
end
读者
readeri
begin
repeat
Swait（rmax,1,1）;
Swait（wmutex,1,0）;
Performreadoperation;
Ssignal（rmax,1）;
untilfalse;
end
写者
writerj
begin
repeat
Swait（wmutex,1,1,rmax,RN,0）;
Performwriteoperation
Signal（wmutex）;
untilfalse
end
RN:
限定最多同时读的读者数
rmax:
空位置的数目，即系统还允许执行读操作的读者数，超过这个数目后读者将等待
wmutex:
用于读者与写者、写者与写者之间的互斥访问
读者执行Swait（wmutex,1,0）保证无写者（wmutex值保持不改变）
写者执行Swait（wmutex,1,1,rmax,RN,0）保证既无写者在写又无读者在读（rmax值保持不变）
哲学家进餐问题
主程序
Varchopstick:
array[0,…,4]ofsemaphore:
=1,1,1,1,1;
begin
parbegin
philosopher0;…;philosopheri;…;philosopher4;
parend
end
哲学家进餐问题子程序
基于AND信号量机制
philosopheri
begin
repeat
Think;
Swait（chopstick[（i+1）mod5],chopstick[i]）;
Eat;
Ssignal（chopstick[（i+1）mod5],chopstick[i]）;
untilfalse
end
哲学家进餐问题子程序
限制哲学家同时进餐人数
philosopheri
varpmax:
semaphore:
=4;
begin
repeat
wait（pmax）;
wait（chopstick[i]）;
wait（chopstick[（i+1）mod5]）;
Eat;
signal（chopstick[（i+1）mod5]）;
signal（chopstick[i]）;
signal（pmax）;
Think;
untilfalse
end
理发师问题描述如下：
理发店包含一间接待室和一间工作室，接待室内有n（n>=1）把椅子，而工作室只有一把椅子。
如果没有顾客，理发师就去睡觉，如果顾客来时所有的椅子都有人，那么顾客离去；如果理发师在忙且接待室有空闲的椅子，那么此顾客会坐在其中一把空闲的椅子上等待；如果理发师在睡觉，则顾客会唤醒他。
请采用信号量机制解决该理发师问题（可采用伪代码描述）。
解：
要求描述理发师和顾客的行为，因为需要两类进程Barber（）和Customer（）分别描述理发师和顾客的行为。
理发师和顾客之间是同步的关系，理发师和椅子使临界资源，所以顾客之间是互斥的关系。
引入3个信号量和一个控制变量：
Ø控制变量waiting也用于记录等候的顾客数，实际上是customers的一份拷贝。
之所以使用waiting是因为无法读取信号量的当前值，初值均为0。
Ø信号量customers用来记录等候理发的顾客数（不包括正在理发的顾客），并用作阻塞理发师进程，初值为0。
Ø信号量barbers用来记录正在等候顾客的理发师数（为0或1），并用作阻塞顾客进程，初值为0。
Ø信号量mutex用于对waiting的访问进行互斥，初值为1。
进入理发店的顾客必须先看等候的顾客数，如果少于椅子数（n），他坐下来等，否则他就离开。
PV操作代码如下:
intwaiting=0;//等候理发的顾客数（还没理发的）,0～n
semaphorecustomers=0,barbers=0,mutex=1;
barber（）{
while（TRUE）//理完一人,还有顾客吗?
{
P（customers）;//若无顾客,理发师睡眠
P（mutex）;//进程互斥
waiting:
=waiting-1;//等候顾客数少一个
V（barbers）;//理发师去为一个顾客理发
V（mutex）;//开放临界区
cut-hair（）;//正在理发（非临界区操作）
}
}
customer（）{//顾客进入理发店
P（mutex）;//进程互斥
if（waitingwaiting:
=waiting+1;//等候顾客数加1
V（customers）;//有顾客了，如果理发师在睡则唤醒
V（mutex）;//开放临界区
P（barbers）;//无理发师,顾客坐着养神
get-haircut（）;//一个顾客坐下等待理发
}else
V（mutex）;//顾客已满，离开
}
应用类型知识要点二：
分页存储地址结构及地址变换
Ø分页存储管理地址结构（由硬件机制决定）
3112110
页号
页内地址
Ø逻辑地址与页号及页内偏移地址之间的换算
PageNo=INT[Addr/PageLength]
PageOffset=AddrmodPageLength
举例：
对于1KB页面，若给定逻辑地址2170B，则PageNo=2，PageOffset=122
Ø地址变换任务
关键在于页号到物理块号之间的转变
Ø地址映射
某虚拟存储器的用户编程空间共32个页面，每页1K，主存为16K。
假定某时刻用户页表中已调入主存的页面的虚页号和物理页号对照表如图所示，则当虚地址为十六进制0A5C时，对应的物理地址是多少？
虚页号
物理页号
0
4
1
10
2
4
3
7
解：
虚拟地址（0A5C）
=（10*16
+5*16+12）
页号=INT[2652/1K]=2，其物理块号为4
页内偏移=2652mod1K=604
物理地址为4*1K+604=（4700）
=（125C）
应用类型知识要点三：
分页存储与数据访问时间
假定快表检索时间为20ns，内存访问时间为100ns，则若能在快表中找到CPU给出的页号，CPU存取一个数据将需要（100+20）=120ns，若不能在快表中找到CPU给出的页号，则为存取一个数据将需要（100+100+20）=220ns。
进一步说，若假定快表查找命中率为80%，则其有效访问时间为120*80%+220*（1-80%）=140ns。
应用类型知识要点四：
页面置换算法与缺页次数
Ø最佳置换算法OPT（向前看页面引用序列）
基本思想：
选择永不使用或是在最长时间内不再被访问（即据现在最长时间才会被访问）的页面淘汰出内存
评价：
理想化算法，具有最好性能（对于固定分配方式，本法可保证获得较低的缺页率），但实际上却难于实现，故主要用于算法评价参照
7
0
1
2
0
3
0
4
2
3
0
3
2
1
2
0
1
7
0
1
7
7
7
2
2
2
2
2
2
2
2
2
2
2
2
2
2
7
7
7
0
0
0
0
0
0
4
4
4
0
0
0
0
0
0
0
0
0
0
1
1
1
3
3
3
3
3
3
3
3
1
1
1
1
1
1
1
某进程分配获得三个物理块
采用预调页策略（区别预调页策略与请求调页策略），前3个页面预先装入
第一行为页面访问（引用）序列
第二、三、四行为内存页面分布情况，前三列页面预先装入
缺页中断次数为6次，缺页率30%[缺页率=（发生缺页次数/页面序列长度）*100%]
Ø先进先出置换算法FIFO（向回看页面分布情况）
基本思想：
选择最先进入内存即在内存中驻留时间最久的页面换出到外存。
进程已调入内存的页面按进入先后次序链接成一个队列，并设置替换指针以指向最老页面。
评价：
简单直观，但不符合进程实际运行规律，性能较差，故实际应用极少。
7
0
1
2
0
3
0
4
2
3
0
3
2
1
2
0
1
7
0
1
7
7
7
2
2
2
2
4
世界上的每一个国家和民族都有自己的饰品文化，将这些饰品汇集到一起再进行新的组合，便可以无穷繁衍下去，满足每一个人不同的个性需求。
4
500元以上1224%4
0
0
0
0
0
就算你买手工艺品来送给朋友也是一份意义非凡的绝佳礼品哦。
而这一份礼物于在工艺品店买的现成的礼品相比，就有价值意义，虽然它的成本比较低但它毕竟它是你花心血花时间去完成的。
就像现在最流行的针织围巾，为何会如此深得人心，更有人称它为温暖牌绝大部分多是因为这个原因哦。
而且还可以锻炼你的动手能力，不仅实用还有很大的装饰功用哦。
0
喜欢□一般□不喜欢□0
7
１９９６年“碧芝自制饰品店”在迪美购物中心开张，这里地理位置十分优越，交通四通八达，由于位于市中心，汇集了来自各地的游客和时尚人群，不用担心客流量的问题。
迪美有３００多家商铺，不包括柜台，现在这个商铺的位置还是比较合适的，位于中心地带，左边出口的自动扶梯直接通向地面，从正对着的旋转式楼梯阶而上就是人民广场中央，周边４、５条地下通道都交汇于此，从自家店铺门口经过的９０％的顾客会因为好奇而进去看一下。
7
7
0
附件
（二）：
调查问卷设计0
1．www。
cer。
net/artide/2004021313098897。
shtml。
0
0
一、消费者分析3
3
3
2
（1）专业知识限制2
2
2
ｂｅａｄｏｒｋｓ公司成功地创造了这样一种气氛：
商店和顾客不再是单纯的买卖关系，营业员只是起着参谋的作用，顾客成为商品或者说是作品的作参与者，营业员和顾客互相交流切磋，成为一个共同的创作体2
1
1
1
1
1
0
0
1
1
1
1
0
0
0
3
3
3
3
3
2
2
2
2
2
1
某进程分配获得三个物理块
采用预调页策略（区别预调页策略与请求调页策略），前3个页面预先装入
第一行为页面访问（引用）序列
第二、三、四行为内存页面分布情况，前三列页面预先装入
缺页中断次数为12次，缺页率68%[缺页率=（发生缺页次数/页面序列长度）*100%]
Ø最近最久未使用置换算法LRU（向回看页面引用序列）（硬件支持）
基本思想：
以“最近的过去”作为“最近的将来”的近似，选择最近一段时间最长时间未被访问的页面淘汰出内存。
评价：
适用于各种类型的程序，性能较好，但需要较多的硬件支持。
7
0
1
2
0
3
0
4
2
3
0
3
2
1
2
0
1
7
0
1
7
7
7
2
2
2
2
4
4
4
0
0
0
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
3
3
3
3
3
3
0
0
0
0
0
1
1
1
3
3
3
2
2
2
2
2
2
2
2
2
7
7
7
某进程分配获得三个物理块
采用预调页策略（区别预调页策略与请求调页策略），前3个页面预先装入
第一行为页面访问（引用）序列
第二、三、四行为内存页面分布情况，前三列页面预先装入
缺页中断次数为9次，缺页率45%[缺页率=（发生缺页次数/页面序列长度）*100%]
Ø简单CLOCK置换算法（NRU）（硬件支持）
Ø改进型CLOCK置换算法（硬件支持）
评价：
与简单CLOCK算法相比，可减少磁盘的I/O操作次数，但淘汰页的选择可能经历多次扫描（最多3轮加1次），故实现算法自身的开销增大。
Ø最少使用置换算法（硬件支持）
基本思想：
为内存各页设置一个以为寄存器用于记录对应被访问频率。
选择在最近时期使用最少的页面作为淘汰页。
评价：
鉴于仅用一位寄存器有限各位来记录页面使用会导致访问一次与访问多次的等效性，本算法并不能真实全面地反映页面适用情况。
应用类型知识要点五：
文件结构与记录检索次数
Ø索引顺序文件组织方式
检索开销
分组大小
Ø两级索引顺序文件组织方式
主文件分组大小
低级索引表分组大小
检索开销
升级会员 