|
|
计算机考研科目包括数据结构、计算机组成原理、操作系统以及计算机网络几部分。其中操作系统是重要考点，希望考生认真复习。下面新东方在线小编分享2015年计算机考研：操作系统试题希望通过这些题目大家能够更深刻的记忆知识点，更通透的理解每一个考点。
下面请看2015年计算机考研：操作系统试题（十三）
6、某段表内容如下：
段号段首地址段长度
0120K40K
1760K30K
2480K20K
3370K20K
一逻辑地址为(2，154)的实际物理地址为多少?
答：逻辑地址(2154)表示段号为2，即段首地址为480K，154为单元号，则实际物理地址为480K+154。
7、设系统中有三种类型的资源(A，B，C)和五个进程(P1，P2，P3，P4，P5)，A资源的数量为17，B资源的数量为5，C资源的数量为20。在T0时刻系统状态如表1和表2所示。(共10分)
系统采用银行家算法实施死锁避免策略。
① T0时刻是否为安全状态?若是，请给出安全序列。
② 在T0时刻若进程P2请求资源(0，3，4)，是否能实施资源分配?为什么?
③ 在②的基础上，若进程P4请求资源(2，0，1)，是否能实施资源分配?为什么?
④ 在③的基础上，若进程P1请求资源(0，2，0)，是否能实施资源分配?为什么?
表1 T0时刻系统状态
最大资源需求量已分配资源数量
ABCABC
P1559212
P2536402
P34011405
P4425204
P5424314
表2 T0时刻系统状态
ABC
剩余资源数233
8.系统中有五个进程P1、P2、P3、P4、P5，有三种类型的资源：R1、R2、和R3。在T0时刻系统状态如表所示。若采用银行家算法实施死锁避免策略，回答下列问题：
(共9分，每小题3分)
1. T0时刻是否为安全状态?为什么?
2. 若这时P4请求资源(1，2，0)，是否能实施资源分配?为什么?
3. 在上面的基础上，若进程P3请求资源(0，1，0)，是否能实施资源分配?为什么?
T0时刻系统状态
已分配资源数量最大资源需求量
R1R2R3R1R2R3
P1001001
P2200275
P3003665
P4115435
P5033065
R1R2R3
剩余资源数330
解：(共9分，每小题3分)
1. T0时刻是安全的，安全序列为：P1，P4，P5，P2，P3
2. P4请求资源(1，2，0)，根据银行家算法，预分配后系统是安全的，安全序列为：P1，P4，P5，P2，P3
3. P3请求资源(1，1，0)，根据银行家算法，预分配后系统不安全，所以不能实施资源分配。
9.一个进程的大小占5个页面，每页的大小为1K，系统为它分配了3个物理块。当前进程的页表如图所示：(共8分)
块号 存在位P 访问位R 修改位M
0x1C110
0x3F111
-000
0x5D100
-000
1. 有那些页面不在内存?(2分)
2. 请分别计算进程中虚地址为0x3B7、0x12A5、0x1432单元的物理地址(用十六进制表示)，并说明理由。 (6分)
解：(共8分)
不在内存的是第2和4页(按页号)，或第3和5页(按序号)。 (2分)
0x3B7的物理地址=0x 73 B7 (2分)
0x12 A5的物理地址=0x 176 A5，缺页，换出第三页。 (2分)
0x1432地址越界，出错。 (2分)
10.系统运行有三个进程：输入进程、计算进程和打印进程，它们协同完成工作。输入进程和计算进程之间共用缓冲区buffer1,计算进程和打印进程之间共用缓冲区buffer2。输入进程接收外部数据放入buffer1中;计算进程从buffer1中取出数据进行计算，然后将结果放入buffer2;打印进程从buffer2取出数据打印输出。
用算法描述这三个进程的工作情况，并用wait和signal原语实现其同步操作。(共8分)
解：(共8分)
解答：输入进程、计算进程和打印进程之间的同步问题描述如下：
var：mutex1，mutex2，empty1，empty2，full1，full2：=1，1，1，1，0，0;
InP:begin
repeat
wait(empty1);
wait(mutex1);
input a data from keyboard;
Add to buffer1;
signal(mutex1);
signal(full1);
until false
end
CalP:begin
repeat
wait(full1);
wait(mutex1);
Take a data form buffer1;
Add to ch1;
signal(mutex1);
signal(empty1);
calculate ch1;
wait (empty2);
wait(mutex2);
Take a data form ch1;
Add to buffer2;
signal (mutex2);
signal (full2);
until false
end
OutP:begin
repeat
wait(full2);
wait(mutex2);
Take a data from buffer2;
Add to printer controler;
signal(mutex2);
signal(empty2);
start printer;
until false
end
(评分标准：信号量设置2分，输入进程、计算进程、打印进程各2分)
11.在一个请求分页系统中，有一个长度为 5 页的进程，假如系统为它分配 3 个物理块 ，并且此进程的页面走向为
2，3，2，1，5，2，4，5，3，2，5，2。试用 FIFO 和 LRU 两种算法分别计算出程序访问过程中所发生的缺页次数。(10分)
解：FIFO：
2 3 2 1 5 2 4 5 3 2 5 2
第1页 2 2 2 5 5 5 3 3 3
第2页 3 3 3 2 2 2 5 5
第3页 1 1 1 4 4 4 2
缺页中断次数 = 6
LUR：
2 3 2 1 5 2 4 5 3 2 5 2
第1页 2 2 2 2 5 5 5 3
第2页 3 3 5 2 3 3 5
第3页 1 1 4 4 2 2
缺页中断次数 = 5
12. 进程 A1，A2，…，An 通过 K 个缓冲区向进程 B1，B2，…，Bm 不断地发送消息。发送和接收工作遵循如下规则：
1. 每个发送进程一次发送一个消息，写入缓冲区，缓冲区大小与消息长度一致;
2. 对每个消息，B1，B2，…，Bm 都需接收一次，读入各自的数据区内;
3. K 个缓冲区都满时，发送进程等待，没有可读的消息时，接收进程等待。
试用 wait 和 signal 原语操作组织正确的发送和接收操作。(10分)
解：
BEGIN
Integer Mutex, Avail[n], Full[m];
Integer I;
Mutex:=1;
FOR i:=1 TO m DO
BEGIN
Avail[I] := k;
Full[I] := 0;
END
PROCEDURE Send(K)
Integer I;
BEGIN
13.一个进程的大小为5个页面，为它分配了四个物理块。当前每个块的情况如下表所示(都为十进制数，且从0开始计数。)。当虚页4发生缺页时，使用下列的页面置换算法，哪一个物理块将被换出?并解释原因.(10分)
页号 块号 加载时间 访问时间 访问位R 修改位M
2 0 60 161 0 1
1 1 130 160 0 0
0 2 26 162 1 0
3 3 20 163 1 1
1. IFO算法
2. LRU算法
3. CLOCK算法
4.当页面的访问串为：“4，0，0，0，2，4，2，1，0，3，2”的OPT算法
解：1.换出第3号虚页，因为它加载的时间最早;
2.换出第1号虚页，因为它最近最久没被访问;
3.换出第1号虚页，因为它最近既没被访问，又没被修改;
4.换出第3号虚页，因为它离访问点最远。
14. 用整型信号量描述在哲学家进餐问题中，至多允许4个哲学家同时进餐的算法。(10分)
解：public class diningphilosophers {
semaphore [] fork = new semaphore [5] (1);
semaphore room = new semaphore (4);
int i;
void philosopher (int i) {
while (true)
think();
wait (room);
wait (fork);
wait (fork [(i+1) % 5]);
eat();
signal (fork [(i+1) % 5]);
signal (fork);
signal (room); }
void main() {
parbegin (philosopher (0), philosopher (1), philosopher (2),
philosopher (3), philosopher (4)); } }
15.考虑一个有150个存储器单元的系统，如下分配给三个进程：
进程 最大 占有
————————————————————
1 70 45
2 60 40
3 60 15
使用银行家算法，以确定下面的任何一个请求是否安全：
a.第4个进程到达，最多需要60个存储单元，最初需要25个单元;
b.第4个进程到达，最多需要60个存储单元，最初需要35个单元;
如果安全给出安全序列;若不安全给出结果分配简表。(10分)
解：进程 最大 占有 尚需 可用
————————————————————————
1 70 45 25 25
2 60 40 20
3 60 15 45
4 60 25 35
安全序列为：1、2、3、4
所以系统是安全的，可以进行分配。
b.
进程 最大 占有 尚需 可用
————————————————————————
1 70 45 25 15
2 60 40 20
3 60 15 45
4 60 35 25
当前可用的资源不够任何一个进程运行完毕，所以不安全。
16. Jruassic
公园有一个恐龙博物馆和一个公园.有m个旅客和n辆车,每辆车只能容纳一个旅客。旅客在博物馆逛了一会儿，然后排队乘坐旅行车。当一辆车可用时，它载入一个旅客，然后绕公园行驶任意长的时间。如果n辆车都已被旅客乘坐游玩，则想坐车的旅客需要等待;如果一辆车已经就绪，但没有旅客等待，那么这辆车等待。使用信号量同步m个旅客和n辆车的进程。(10分)
解：
visitors=m; cars=n; mutex=1;
Pvi() Pci()
{ repeat { repeat
wait(cars); wait(visitors);
wait(mutex); wait(mutex);
get on; start;
travell; run;
get off; stop;
signal(cars); signal(visitors);
wait(mutex); wait(mutex);
until false; until false;
} }
17.读者与写者问题 (reader -- writer problems ) (10分)
在计算机体系中，对一个共享文件进行操作的进程可分为两类：读操作和写操作，它们分别被称为读者和写者。访问该文件时读者和写者，写者和写者间必须实现互斥。只有在没有读者访问文件时，写者才允许修改文件。或者写者在修改文件时不允许读者去读，否则会造成读出的文件内容不正确。试写出算法描述读者和写者的问题。
解： 为了实现读者与写者的同步和互斥，我们设置一个信号量S，用于读者与写者之间或写者与读者之间的互斥，初值为“1”。用一个变量rc
表示当前正在读的读者个数，当进程可以去读或读结束后都要改变rc 的值，因此rc
又成为若干读进程的共享变量，它们必须互斥地修改rc。故必须定义另一个用于互斥的信号量Sr，初值也是“1”。读者--写者问题可描述如下：
S, Sr：semaphore; int rc = 0; S=Sr=1;
process Reader I (i=1,2,...,m) process Writer j (j=1,2,...,k)
begin begin
P(Sr); rc = rc+1; P(S);
if (rc==1) P(S); Write file F;
V(Sr); V(S);
read file F; end
P(Sr); rc = tc-1;
if (rc==0) V(S);
V(Sr);
end
18、若干个等待访问磁盘者依次要访问的磁道为20，44，40，4，80，12，76，假设每移动一个磁道需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别写出访问序列并计算为完成上述各次访问总共花费的寻道时间。
(1)先来先服务算法;
(2)最短寻道时间优先算法。
(3)扫描算法(当前磁头移动的方向为磁道递增)(10分)
解：
(1)磁道访问顺序为：20，44，40，4，80，12，76
寻道时间=(20+24+4+36+76+68+64)*3=292*3=876
(2)磁道访问顺序为：40，44，20，12，4，76，80
寻道时间=(0+4+24+8+8+72+4)*3=120*3=360
(3)磁道访问顺序为：40，44，76，80，20，12，4
寻道时间=(0+4+32+4+60+8+8)*3=116*3=348
19、生产者和消费者问题 (10分)
有一组生产者P1，P2，……，PM和一组消费者C1，C2，……，CK，他们通过由n个环形缓冲区构成的缓冲池进行通信，生产者把产品放入缓冲区，消费者从缓冲区取产品来消费。请用wait和signal原语实现他们的同步操作。
解：生产者和消费者问题
begin
Var mutex,empty,full:semaphore:=1,n,0;
buffer:array[0,…,n-1] of item;
in,out:integer := 0,0;
parbegin
producer: begin
repeat
produce next product ;
wait (empty);
wait (mutex);
buffer(in):=nextp ;
in := (in+1) mod n ;
signal (full);
signal (mutex);
until false ;
end
consumer: begin
repeat
wait (full);
wait (mutex);
nextc := buffer(out);
out := (out+1) mod n;
signal (empty);
signal (mutex);
consume the item in nextc;
until false ;
end
parend end
20、请用信号量描述哲学家进餐问题。(15分)
解：哲学家进餐问题(15分)
public void philosopher (int i) {
while (true) {
think();
wait (fork);
wait (fork [(i+1) % 5]);
eat();
signal(fork [(i+1) % 5]);
signal(fork);
} }
21.今有三个并发进程R，M，P，它们共享了一个可循环使用的缓冲区B，缓冲区B共有N个单元。进程R负责从输入设备读信息，每读一个字符后，把它存放在缓冲区B的一个单元中;进程M负责处理读入的字符，若发现读入的字符中有空格符，则把它改成“，”;进程P负责把处理后的字符取出并打印输出。当缓冲区单元中的字符被进程P取出后，则又可用来存放下一次读入的字符。请用PV操作为同步机制写出它们能正确并发执行的程序。
(10分)
解：(10分)
begin
Var mutex,input,calculate,output:semaphore:=1,n,0,0;
buffer:array[0,…,n-1] of item;
in,mid,out:integer := 0,0,0;
proR() { do {
wait (input);
wait (mutex);
buffer(in):=input data;
in := (in+1) mod n ;
signal (calculate);
signal (mutex);
while true ; }
proM() { do {
wait (calculate);
wait (mutex);
buffer(middle):=calculate data ;
mid := (mid+1) mod n ;
signal (output);
signal (mutex);
} while true ; }
proP() { do {
wait (output);
wait (mutex);
buffer(out):=calculate data ;
out := (out+1) mod n ;
signal (input);
signal (mutex);
} while true ; }
22.理发店里有一位理发师、一把理发椅子和五把供等候理发的顾客坐的椅子。如果没有顾客，理发师便在理发椅上睡觉。当一个顾客到来时，他必须先叫醒理发师，如果理发师正在理发时又有顾客来到，而如果有空椅子可坐，他们就坐下来等，如果没有空椅子，他就离开。这里的问题是为理发师和顾客各编写一段程序来描述他们行为，并用wait和signal原语操作实现其同步。(10分)
解：理发师问题
#define CHAIRS 5 /*为等候的顾客准备椅子数*/
typedef int semaphore; /* 运用你的想像力*/
semphore customers=0; /*等候服务的顾客数*/
semaphore barbers=0 /*等候服务的理发师数*/
semaphore mutex=1; /*用于互斥*/
int waiting=0; /*还没理发的等候顾客*/
void barber (void) {
while(TRUE) {
wait(customers); /*如果顾客数是0，则睡觉*/
wait(mutex); /*要求进程等候*/
waiting=waiting-1; /*等候顾客数减1*/
signal(barbers); /*一个理发师现在开始理发*/
signal(mutex); /*释放等候*/
cut_hair(); /*理发(非临界区操作)*/
}
void customers (void) {
wait(mutex);
if (waiting
waiting=waiting+1;
signal(customers);
signal(mutex);
wait(barbers);
} else {
signal(mutex);
} }
23、根据如下的前趋图写出可并发执行的程序：(10分)
1
2
3
4
5
6
7
解：(10)
评分：变量、进程、程序主体每项一分。
var a,b,c,d,e,f,g,h,i:semaphore := 0,0,0,0,0,0,0,0;
begin parbegin
begin S1;signal(a); signal(b); end
begin wait(a); S2; signal(c);signal(d); end
begin wait(c); S3; signal(e);signal(f); end
begin wait(b); S4; signal(g); end
begin wait(d);wait(e) S5; signal(h); end
begin wait(f); wait(g); S6 ; signal(i); end
begin wait(h); wait(i); S7; end
parend
end
24、在公共汽车上，乘客上完后，售票员关门，驾驶员开车，售票员售票，到站汽车停稳后，售票员开门，乘客上下车，售票员和驾驶员之间密切配合，直到下班。请用信号量描述公共汽车上售票员与驾驶员的工作过程。(10分)
解：建立驾驶员和售票员两进程，驾驶员进程执行过程如下：
(1) 判售票员关门没有
(2) 开车
(3) 到站后停车
(4) 重复(1)-(3)
售票员执行过程如下：
(1) 判断乘客上完没有
(2) 关门
(3) 售票
(4) 判车停稳没有
(5) 开门
(6) 重复(1)-(5)
评分标准：执行过程完善3分，
驾驶员与售票员合作消息正确3分
售票员与驾驶员合作消息正确3分
书写格式1分
25、设某作业占有7个页面，如果在主存中只允许装入4个工作页面(即工作集为4)，作业运行时，实际访问页面的顺序是：1， 2， 3， 6， 4， 7，
3， 2， 1， 4， 7， 5， 6， 5， 2， 1。试用FIFO、LRU和CLOCK页面置换算法，列出各自的页面淘汰顺序和页面置换次数。
(10分)
解：FIFO：
1， 2， 3， 6， 4， 7， 3， 2， 1， 4， 7， 5， 6， 5， 2， 1
1 1 1 1 4 4 4 4 5 5
2 2 2 2 7 7 7 7 6
3 3 3 3 2 2 2 2
6 6 6 6 1 1 1
页面置换次数为：6次
LRU：
1， 2， 3， 6， 4， 7， 3， 2， 1， 4， 7， 5， 6， 5， 2， 1
1 1 1 1 4 4 4 1 1 1 1 6 6 6
2 2 2 2 7 7 7 4 4 4 4 2 2
3 3 3 3 3 3 3 7 7 7 7 1
6 6 6 2 2 2 2 5 5 5 5
页面置换次数为：10次
CLOCK：
1， 2， 3， 6， 4， 7， 3， 2， 1， 4， 7， 5， 6， 5， 2， 1
1 1 1 1 4 4 4 1 1 1 1 6 6 6
2 2 2 2 7 7 7 4 4 4 4 2 2
3 3 3 3 3 3 3 7 7 7 7 1
6 6 6 2 2 2 2 5 5 5 5
页面置换次数为：10次
26、某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：
(1)用wait和signal操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。
(2)根据所定义的信号量，加上wait和signal原语，写出购票者进程的算法，以保证进程能够正确地并发执行。
(3)若欲购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值)。
解：(1)定义一信号量S，初始值为20。
意义：
S>0 S的值表示可继续进入售 票厅的人数
S=0 表示售票厅中已有20名顾 客(购票者)
S<0 |S|的值为等待进入售票 厅的人数
(2) int S=20;
COBEGIN PROCESS PI(I=1，2，……)
begin
进入售票厅;
wait(S);
购票;
signal(S);
退出;
end;
COEND
(3)S的最大值为20
S的最小值为20-n
27.设正在处理器上执行的一个进程的页表如下表所示，表中的虚页号和物理块号是十进制数，起始页号(块号)均为0。所有的地址均是存储器字节地址。页的大小为1024字节。(10分)
① 详述在设有快表的请求分页存储管理系统中，一个虚地址转换成物理内存地址的过程。
② 下列虚地址对应于什么物理地址：5499，2221。
进程的页表
虚页号状态位访问位修改位物理块号
01104
11117
2000-
31002
4000-
51010
解：
5499的物理地址为：379
2221的物理地址为 ：3*1024+173=3245
28、假定系统有三个并发进程read,
move和print共享缓冲器B1和B2。进程read负责从输入设备上读信息，每读出一个记录后把它存放到缓冲器B1中。进程move从缓冲器B1中取出一记录，加工后存入缓冲器B2。进程print将B2中的记录取出打印输出。缓冲器B1和B2每次只能存放一个记录。要求三个进程协调完成任务，使打印出来的与读入的记录的个数，次序完全一样。请用wait和signal原语写出它们的并发程序。(10分)
解：begin SR,SM1,SM2,SP:semaphore;
B1,B2:record;
SR:=1;SM1:=0;SM2:=1;SP:=0
Cobegin
process read
X:record;
begin R: (接收来自输入设备上一个记录)
X:=接收的一个记录;
waiut(SR);
B1:=X;
signal(SM1);
goto R;
end;
Process move
Y:record;
Begin
M:wait(SM1);
Y:=B1;
signal(SR)
加工 Y
wait(SM2);
B2:=Y;
signal(SP);
goto M;
end;
Process print
Z:record;
Begin
P:wait(SP);
Z:=B2;
signal(SM2)
打印Z
goto P;
end;
coend;
end;
29、考虑下述页面走向：
12，3，42，1，56，2，12，3，76，3，21，2，36
当内存块数量分别为3时，试问FIFO、LRU、OPT
答：所有内存块最初都是空的，所以第一次用到的页面都产生一次缺页。
3时：
FIFO 1，23，4，21，5，6，2，12，3，76，3，21，2，36
1 1 1 4 4 4 6 6 6 3 3 3 2 2 2 6
2 2 2 1 1 1 2 2 2 7 7 7 1 1 1
3 3 3 5 5 5 1 1 1 6 6 6 3 3
发生缺页中断的次数为16在FIFO64、1、56之前调入的页面，分别为5、1、24，可见4为最先进入内存的，本次应换出，然后把页6 LRU
1，23，4，21，5，6，2，12，3，76，3，21，2，36
1 1 1 4 4 5 5 5 1 1 7 7 2 2 2
2 2 2 2 2 6 6 6 3 3 3 3 3 3
3 3 1 1 1 2 2 2 2 6 6 1 6
发生缺页中断的次数为15在LRU65、2、16之前调入的页面，分别为5、1、22为最近一段时间内使用最少的，本次应换出，然后把页6调入内存。
OPT 1，23，4，21，5，6，2，12，3，76，3，21，2，36
1 1 1 1 1 1 3 3 3 3 6
2 2 2 2 2 2 7 2 2 2
3 4 5 6 6 6 6 1 1
发生缺页中断的次数为11在OPT61、2、56后面要调入的页面，分别为2、1、2…，可见5为最近一段时间内使用最少的，本次应换出，然后把页64、答：引入缓冲技术的主要目的是：(123)使得一次输入的信息能多次使用。
30.若干个等待访问磁盘的进程依次要访问的磁道为27，63，57，24，107，35，106当前磁头的位置为57号磁道，根据下面的磁盘调度算法，请给出调度的顺序，并计算平均寻道长度。(10分)
1. 先来先服务算法
2. 最短寻道时间优先
3. 扫描算法(当前磁头移动的方向为磁道递增)
4. 循环扫描算法(当前磁头移动的方向为磁道递增)
解：一系统中具有S类资源150个，在T0时刻按下表所示分配给3个进程：
进程Maximum demandCurrent allocation
P17025
P26040
P36045
对下列请求应用银行家算法逐步分别分析判定是否安全, 如果是安全的，请给出一个可能的进程安全执行序列;如果不是安全的，请说明原因。(10分)
1. 第4个进程P4到达，对资源S的最大需求为60个，当前请求分配25个;
2.第4个进程P4到达，对资源S的最大需求50个，当前请求分配35个。
31.一个采用请求式存储管理的计算机系统，其主存(实存)容量为256M字节，虚存容量(给用户的最大地址空间)为4G字节，页面大小为4K字节，试问：(10分)
1. 主存物理地址应设为多少位?
2. 主存中有多少物理块?
3. 虚拟地址应该设多少位?
4. 虚拟地址空间最多可以有多少页?
5. 页内最大和最小偏移量是多少?
温馨提示：考研复习是一个长期的过程，需要恒心和耐力才能够取得，希望每一位考生都能够坚持到底，赢得最后的胜利，加油！ |
|
发表于 2017-8-6 14:43:27