【操作系统】操作系统原理复习_一座小桥横跨南北两岸

综合应用题实例：

一、已知主存512K，OS占用低位40K，现有一作业序列如下：

   J1要求 160K，J2要求 42K，J3要求 70K，J1完成,J4要求 130K，J5要求 140K，J3完成,J6要求 20K，J7要求 42K，J2完成，J8要求 62K。

试用最佳适应法为上述作业分配主存，画出主存分配情况和自由主存队列。（分配时，高地址处作为已分配区）（’）

答：

 

 

二、一文件系统中，盘块大小为1KB=1024B(字节),盘块编号长4B,文件说明中可存放14个盘块编号。关于文件大小有如下统计结果：

文件大小≤4KB       占50%

4KB＜文件大小≤9KB       占20%

9KB＜文件大小≤256KB     占14%

256KB＜文件大小≤768KB   占8%

768KB＜文件大小≤64MB    占6%

64MB＜文件大小≤16GB    占2%

试为该文件系统设计文件的物理结构，使访问文件时具有尽可能小的平均访问磁盘次数，并计算其平均访问磁盘次数。（11’）

解：此文件系统应采用多级索引。先将文件大小转化为盘块个数

关于文件大小有如下统计结果：

文件大小≤4个盘块          占50%

4个盘块＜文件大小≤9个盘块       占20%

9个盘块＜文件大小≤256个盘块     占14%

256个盘块＜文件大小≤768个盘块   占8%

768个盘块＜文件大小≤64K个盘块   占6%

64K个盘块＜文件大小≤16M个盘块   占2%

考虑到一个索引块可索引1024/4=256个盘块。因此文件说明中可用编号a0-a8共9个标号索引9个盘块。用编号a9-a11共3个标号索引3个二级块,共3*256=768个盘块。用编号a12可索引1个三级块,共1*256*256=64K个盘块。

用编号a13可索引1个四级块,共256*256*256=16M个盘块。

其平均访问磁盘次数=(50%+20%)*1+(14%+8%)*2+6%*3+2%*4=1.40

 

三、设某单面磁盘共有28000个扇区，采用CSCAN(循环扫描)磁盘调度策略，磁盘的旋转速度为每分钟6000转，每个磁道有100个扇区，相临磁道间的移动时间为1ms.若在某时刻，磁头位于100号磁道处，并沿着磁道号增大的方向移动,磁道号的请求队列为150，40，230，120，78，28，90，190，对请求队列中的每个磁道需读取1个随机分布的扇区，则读完这些扇区点共需要多少时间?需要给出计算过程。（8’）

解：每分钟6000转，转一圈需10ms,通过一扇区需要0.1ms;

访问时间=寻道时间+旋转时间平均5ms+通过扇区0.1ms;

按CSCAN则访问磁道的顺序为(当前100）-120-150-190-230-max-0-28-40-78-90 其中max=279

总的访问时间=（max-100+max+90)*1ms+5.1ms*8=588.8ms

 

四、设一系统中有三类资源，所有可用资源个数为（9，8，9）。某时刻系统中资源状态如下：Allocation  Need   1)若P2提出请求Request（1,1,2），试问系统

P1:   2  1  1    3  2  4       能否将资源分配给它？为什么？

P2:   1  1  2    4  2  3     2)此后，P4提出请求Request（0,1,1），

P3:   1  2  1    2  1  1      试问系统能否将资源分配给它？为什么？（13’）

P4:   2  1  2    3  3  4     

解：依题意可得Available（3，3，3） 

  1）若进程P2请求资源Req（1，1，2），按银行家算法判断如下：

1）判断Req(1,1,2)<=Need2(4,2,3),表示Req为合法请求；

2）判断Req(1,1,2)<=Available（3，3，3），表示Req为可满足的请求；

3）试探性分配

       Available-=Req; 变为（2，2，1）

       Alloc2+=Req;    变为（2，2，4）

       Need2-=Req;     变为（3，1，1）

4）判断新状态的安全性

     新状态是安全的，可找到安全序列P3,P2,P1,P4（具体过程在此略去）,因此可分配资源；

 

2）此后若进程P4请求资源Req（0，1，1），按银行家算法判断如下：

1）判断Req(0,1,1)<=Need4(3,3,4),表示Req为合法请求；

2）判断Req(0,1,1)<=Available（2，2，1），表示Req为可满足的请求；

3）试探性分配

       Available-=Req; 变为（2，1，0）

       Alloc4+=Req;    变为（2，2，3）

       Need4-=Req;     变为（3，2，3）

4）判断新状态的安全性

     此时可利用的资源不能满足任何进程的需求，新状态是不安全的，因此不可分配资源，进程P4阻塞，并取消试探性分配。

 

五、一请求分页系统中，页面大小为2K，一作业共有7个页面，页面访问序列如下：

时刻25时页面0，1，2，3分别装入到物理页框2，4，1，3中。(13分)

（1）若采用LRU页面置换算法，试计算缺页中断次数；假设时刻70时执行指令MOV  AX，[2600]（AX为寄存器，2600为十进制），给出在执行过程中的地址变换过程。

（2）若采用FIFO页面置换算法，试计算缺页中断次数。

解：1）页块数为4，页面0 1 2 3 已装入内存，采用LRU算法，下面给出缺页中断时软件栈的变化情况（栈底打X号的为被淘汰的页面）：

共产生缺页中断4次。

LA=2600=1*2K+552  p=1   w=552  访问页表，产生缺页中断；

按上图 时刻70时访问页面1，缺页中断会淘汰页面5，而页面5是淘汰页面0而使用页框2的 所以页框号b=2

PA=2*2K+552=4648

2）采用FIFO算法，需写出队列的变化：

 

共产生缺页中断5次。

 

六、一座小桥横跨南北两岸，分南段、中段和北段三部分，南段较窄仅允许单向通行（即当有北向行人依次通过时，南向行人无法通过；同样，当有南向行人依次通过时，北向行人无法通过）；中段宽敞，允许多人通过或歇息；北段较短，仅允许两人同时通过，整座桥梁最多承重30人，试用信号量及PV操作实现南、北两岸行人过桥的同步，并列出信号量的含义和初值。

GO_Northi()

{

P(empty);

P(nmutex);

if（ncount==0）P(south);

ncount++;

V(nmutex)；

过南段;

P(nmutex);

ncount--;

if（ncount==0）V(south);

V(nmutex)；

过中段或歇息;

P(north);

过北段;

V(north);

到达北岸;

V(empty);

}

 

GO_Southj()

{

P(empty);

P(north);

过北段;

V(north);

过中段或歇息;

P(smutex);

if（scount==0）P(south);

scount++;

V(smutex)；

过南段;

P(smutex);

scount--;

if（scount==0）V(south);

V(smutex)；

到达南岸;

V(empty);

}

 

七、有一仓库，可存放A和B两种产品，每次入库时只能存入A或B一种产品，每次出库时只能取出A或B一种产品。现要求

(1)-30<A产品数量-B产品数量<40

         (2) A产品数量+B产品数量<200

试用P、V操作描述产品的入库过程和出库过程。（14分）

解：Main(){

Semaphore empty=199;         //A+B<200

Semaphore fullA=0, fullB=0;

Semaphore mutex=1;

Semaphore AB=39;                 //A-B<40

Semaphore BA=29;                 //B-A<30

Cobegin

   InLib();

        OutLib();

Coend

}

入库过程    InLib()                         出库过程OutLib()

while(有产品入库)                while(有产品须出库)

{                                                      {

  if(产品为A)                              if(产品为A)

{ P(empty);                                 {      P(fullA)

   P(AB)                                    P(BA)

   P(mutex)                                     P(mutex)

     A产品入库                              A产品出库

   V(mutex)                                     V(mutex)

   V(BA)                                    V(AB)

   V(fullA);                                      V(empty)

}else{                                                 }else{

P(empty);                                    P(fullB)

   P(BA)                                    P(AB)

   P(mutex)                                     P(mutex)

     B产品入库                             B产品出库

   V(mutex)                                     V(mutex)

   V(AB)                                    V(BA)

   V(fullB);                                      V(empty)

}                                                 }

}                                                      }