操作系统大题

第⼀章：

1-1设有三道程序A,B,C ，它们共同使⽤⼀个设备进⾏I/O 操作，并按照A,B,C 的优先次序执⾏，这三个程序的计算和I/O 操作时间表如下表所⽰，假设调度时间可忽略不计，分别画出单道程序环境和多道程序环境下，它们的运⾏的时间关系图。并⽐较运⾏时间。（抢占和⾮抢占）。（单位ms ）

A B C 计算 30 60 20 I/O 40 30 40 计算101020程 序操作

1-2.⼀个计算机系统，有⼀台输⼊机和⼀台打印机，现有两道程序投⼊运⾏，且程序A先开始做，程序B后开始做。程序A的运⾏轨迹是：计算50ms，打印100ms，再计算50ms，打印100ms，结束。程序B的运⾏轨迹是：计算50ms,输⼊80ms，再计算100ms，结束。试说明：

1.两道程序运⾏时，CPU有⽆空等待？若有，在哪段时间内等待？2.程序A,B有⽆等待CPU的情况？若有，指出发⽣等待的时间解：

解：1.有100ms---150ms

2.程序A没有，程序B有，在180ms---200ms时程序B等待，由于此时程序A已经占⽤CPU。第⼆章：

2-1 试画出下⾯四条语句的前驱图： S1: a ∶=x+2 S2: b ∶=a+4 S3: c ∶=a+bS4: d ∶=x+b

解：前趋关系：S1-->S2,S1-->S3,S2-->S3,S2-->S4,S3-->S4。（PS ：前趋图的线不能交叉。） 前趋图：

1. 设有8个程序段P1，P2，…,P8，它们在并发执⾏时有如下图所⽰的制约关系，试⽤信号量实现这些程序段之间的同步。

解：将上图转换为前趋关系S1S2 S3S4

Var a,b,c,d,e,f,g,h,i,j,k;

Semaphore:=0,0,0,0,0,0,0,0,0,0,0;BeginParbegin

Begin P1; signal(a); signal(b); signal(c); end;Begin P2;signal(d);signal(e);signal(f);end;Begin wait(a);wait(d);P3;signal(g);end;Begin wait(b);wait(e);P4;signal(h);end;Begin wait(c);wait(f);P5;signal(i);end;Begin wait(g);P6;signal(j);end;Begin wait(i);P7;signal(k);end;Begin wait(h);wait(j);wait(k);P8;end;Parendend

2-3以下为记录型信号量两个原⼦操作：Wait(s) //申请资源s.count:=s.count - 1;if s.count<0then begin进程阻塞；

进程进⼊s.quene队列；End; Signal(s) //释放资源S.count:=s.count +1;

If s.count<=0 //表⽰有阻塞队列Then begin

唤醒队⾸进程；

将该进程从s.quene队列中移出；End;

2.⼀个⽣产者，⼀个消费者，公⽤n 个环形缓冲区（可能考⼩题）

伊利⽜奶⼚⽣产很多⽜奶，放在永辉超市多个分店销售，⼩明可以从任⼀间超市买到⽜奶，同样，只有当⼚商把⽜奶放在某⼀分店时，⼩明才可以从分店中买到⽜奶。

分析：与情况⼀不同，情况⼆有N 个分店（即N 个缓冲区形成⼀个环形缓冲区），所以要利⽤指针，要求⼚商必须按⼀定的顺序将商品依次放到每⼀个分店中。 缓冲区对的指向则通过模运算得到。解：定义两个同步信号量

Empty ：表⽰缓冲区是否为空，初值为n(缓冲区的数量). Full:表⽰缓冲区是否为满，初值为0.设缓冲区编号0--（n-1），定义两个指针in 和out 。

In ：指⽰下⼀个可投放产品的缓冲区，每为⽣产者⽣产并投放⼀个产品，指针+1， in=（in+1）mod n. ----取模运算Out ：指⽰下⼀个可获取产品的缓冲区，每当消费者取⾛⼀个产品，指针+1， out=（out+1）mod n. ----取模运算3.⼀组⽣产者，⼀组消费者，公⽤N 个环形缓冲区（可能考⼩题）

有伊利、蒙⽜、光明等多家⽣产⼚家，消费者也不只⼩明⼀⼈，有很多消费者，不同⼚家把产品放在永辉超市不同分店中销售，不同的消费者可以去不同⼤的分店中购买。当某⼀个分店已放满某个⼚家的商品时，下⼀个⼚家只能把商品放在下⼀家分店中。分析：

⽣产者和消费者之间是同步关系。

各个⽣产者之间、各个消费者之间是互斥关系，互斥访问缓冲区。解：定义4个信号量：

Empty ：表⽰缓冲区是否为空，初值为n(缓冲区的数量). Full:表⽰缓冲区是否为满，初值为0. Mutex1:⽣产者之间的互斥信号量，初值为1 Mutex2:消费者之间的互斥信号量，初值为1.设缓冲区编号0--（n-1），定义两个指针in 和out 。

In ：指⽰下⼀个可投放产品的缓冲区，每为⽣产者⽣产并投放⼀个产品，指针+1， in=（in+1）mod n. ----取模运算Out ：指⽰下⼀个可获取产品的缓冲区，每当消费者取⾛⼀个产品，指针+1，⽣产者进程While(true){⽣产⼀个产品；P （empty ）；

产品送往缓冲区（Buffer ）；in=（in+1）mod n.V(full);} 消费者进程While(true){P(full);

从缓冲区中取产品；

out=（out+1）mod n.V （empty ）；消费产品；

out=（out+1）mod n. ----取模运算⽣产者进程While(true){⽣产⼀个产品；P（empty）；

P（mutex1); /*其他⼚家不能再放产品*/产品送往缓冲区（Buffer）；in=（in+1）mod n;V(mutex1);V(full);} 消费者进程While(true){P(full);

P(mutex2);/*其他消费者不能再取产品*/从缓冲区中取产品；out=（out+1）mod n.V(mutex2);V（empty）；消费产品；}

第四章：（三选⼀吧） 4-1

已知某分页系统，主存容量为64KB ，页⾯⼤⼩为1KB 。对于⼀个4页⼤的作业，将0、1、2、3页分别装⼊主存的2、4、6、7块中。

（1）将⼗进制的逻辑地址1023,2500,3500,4500转换成物理地址。 （2）以⼗进制的逻辑地址1023为例画出地址变换过程。需注意：页号<页表长度（越界中断）

物理地址=物理块号*页⾯⼤⼩（块⼤⼩）+页内地址

需要先计算出来它们的页号和页内地址（页号为逻辑地址除以页⾯⼤⼩的商，余数为页内地址），然后再转换。

（1）逻辑地址1023,1023/1K ，商（页号）为0，余数（页内地址）为1023，0<4（页数），页号合法，查页表找到对应的物理块号为2，所以物理地址为：2*1K+1023=3071 （2）物理地址为：6*1K+452=6596 （3）物理地址为：7*1K+428=7596（4）页号为4，因为页号不⼩于页表长度，越界中断。 逻辑地址1023的地址变换过程：PS ：图上的>要改成>=）页表始址 页表长度4页表寄存器 0 1023

逻辑地址1023 2 1023 物理地址3071内存块号 页号 0 0 0 0

2 4 6 7>越界+N4-2

对于⼀个将页表存放在内存中的分页系统：

（1）如果访问内存需要0.2ms,有效访问时间是多少？

（2）如果加⼀快表，且假定在快表中找到页表项的⼏率⾼达90%，则有效访问时间⼜是多少？（假定查快表需花的时间为0） 。（1）2*0.2

有效访问时间表⽰从逻辑地址到物理地址的时间。分页系统需要两次访问内存，所以需要2*0.2=0.4ms（2）0.9*0.2+（1-0.9）*2*0.2 4-3

对于表所⽰的段表，请将逻辑地址（0,137），（1,4000），（2,3600），（5,230）转换成物0 1 2 3

页⾯号需注意：

（1）段号<段表长度（越界中断） （2）段内地址<段长（越界中断）（3）物理地址=基址（内存始址）+段内地址（位移量）

在分段系统中进⾏地址转换时，地址变换机构⾸先将逻辑地址中的段号与段表长度做⽐较，如果段号超长，则产⽣越界中断；否则便以段号为索引去检索段表，从中得到段在内存中的始址和段长；然后再将逻辑地址中的段内地址与段表项中的段长做⽐较，若不越界，则由段的始址与段内地址相加，形成物理地址。（1）段号0⼩于段表长5，所以段号合法；由于段表的第

0项可获得段的内存起始地址为50K ，段长为10KB ；由于段内地址为137，⼩于段长10KB ，故段内地址也是合法的，因此物理地址为：50KB+137=51337（2

）越界中断（段内地址超过段长） （3）70K+3600=75280（4

）越界中断（段号不合法）

4-4（可能三选⼀吧。。。）最佳置换算法（

OPT ）：所选择的被淘汰页⾯，将是以后永不使⽤的，或许是在最长（未来）时间内不再被访问的页⾯。

这种算法本⾝不是⼀种实际的⽅法，因为页⾯访问的顺序是很难预知的。但是，可把它作为⼀种评价标准，⽐较其他实⽤⽅法的优劣。所以，最优算法只具有理论上的意义。7

0120304230321201701770701201203243

203201701

70120304230321201701

采⽤最佳置换算法发⽣了6次页⾯置换。 缺页的次数为9次。缺页率= 缺页的次数 / 总的访问次数 = 9/20. 4-5

先进先出（FIFO ）页⾯置换算法：该算法总是淘汰最先进⼊内存的页⾯，即选择在内存中页⾯号

驻留时间最久的页⾯予以淘汰。

该算法与进程实际运⾏的规律不相适应，因为在进程中，有些页⾯经常被访问，⽐如，含有全局变量、常⽤函数、例程等的页⾯，FIFO 算法并不能保证这些页⾯不被淘汰。

70120304230321201701770701201231230430420423023013012712702701

70120304230321201701

采⽤FIFO 算法时进⾏了12次页⾯置换，其缺页次数为15次。 缺页率= 缺页的次数 / 总的访问次数 = 15/20. 4-6最近最久未使⽤（LRU ）算法：

FIFO 置换算法性能之所以较差，是因为它所依据的条件是各个页⾯调⼊内存的时间，⽽页⾯调⼊的先后并不能反映页⾯的使⽤情况。 最近最久未使⽤的页⾯置换算法，是根据页⾯调⼊内存后的使⽤情况进⾏决策。由于⽆法预测各页⾯将来的使⽤情况，只能利⽤“最近的过去”作为“最近的将来”的近似。 LRU 置换算法是选择最近最久未使⽤的页⾯予以淘汰。

7012030423032121701

770701201203 403402432032 132 102107 701203042303212017010102100211

02210

301012120201012103210021130201012120201012770701201

20340340243203213210210770120304230321201701

采⽤最近最久未使⽤置换算法，页⾯置换次数为9次，缺页的次数为12次。 缺页率= 缺页的次数 / 总的访问次数 = 12/20.