2016-2017-1_计算机操作系统课后题

第一章：

   一、3、15、19、23

   二、2、5

2、答：画出两道程序并发执行图如下：

(1)两道程序运行期间，CPU存在空闲等待，时间为100至150ms之间(见图中有色部分)。

(2)程序A无等待现象，但程序B有等待。程序B有等待时间段为180ms至200ms间(见图中有色部分)。

5、答：画出三个作业并行工作图如下(图中着色部分为作业等待时间)：

(1)Job1从投入到运行完成需80ms，Job2从投入到运行完成需90ms，Job3从投入到运行完成需90ms。

(2)CPU空闲时间段为：60ms至70ms，80ms至90ms。所以CPU利用率为(90-20)/90=77.78%。

(3)设备I1空闲时间段为：20ms至40ms，故I1的利用率为(90-20)/90=77.78%。设备I2空闲时间段为：30ms至50ms，故I2的利用率为(90-20)/90=77.78%。

第二章：

   一、18、20、26、38、48

   二、5、12、16、20、25、28

5、答：采用短作业优先算法调度时，三个作业的总周转时间为：

           T1=a+(a+b)+(a+b+c)=3a+2b+c               ①

若不按短作业优先算法调度，不失一般性，设调度次序为：J2、J1、J3。则三个作业的总周转时间为：

T2=b+(b+a)+(b+a+c)=3b+2a+c                ②

令②-①式得到：

T2-T1=b-a>0

可见，采用短作业优先算法调度才能获得最小平均作业周转时间。

12、答：

(1)FCFS调度算法

(2)优先级调度算法

(3)时间片轮转法(每个作业获得相同的2分钟长的时间片)

按次序A B C D E A B D E A B E A E A轮转执行。

16、

答：

20、答：

执行次序  提交时间  执行时间  开始时间   完成时间   周转时间

  J1        8:00       60       8:00        9:00        60

  J5         8:35        5        9:00        9:05         30

  J6         8:40       10        9:05        9:15         35

  J3         8:25       20        9:15        9:35         70 

  J4         8:30       25        9:35        10:00        90

  J2         8:20       35        10:00       10:35        135

作业平均周转时间T=(60+30+35+70+90+135)/6=70

注意，J1被调度运行后，直到它执行结束，才会引出作业调度程序工作。所以，J2至J6虽在J1执行期间进入，但未被调度，均在等待。当J1撤离后，作业调度程序工作，按SJF算法，显然有执行次序：J5、J6、J3、J4、和J2。

25、答：

每个作业运行将经过两个阶段：作业调度(SJF算法)和进程调度(优先数抢占式)。另外，批处理最多容纳2道作业，更多的作业将在后备队列等待。

CPU

(1)10:00，作业A到达并投入运行。

(2)10:20，作业B到达且优先权高于作业A，故作业B投入运行而作业A在就绪队列等待。

(3)10:30，作业C到达，因内存中已有两道作业，故作业C进入作业后备队列等待。

(4)10:50，作业B运行结束，作业D到达，按SJF短作业优先算法，作业D被装入内存进入就绪队列。而由于作业A的优先级高于作业D，故作业A投入运行。

(5)11:10，作业A运行结束，作业C被调入内存，且作业C的优先级高于作业D，故作业C投入运行。

(6)12:00，作业C运行结束，作业D投入运行。

(7)12:20，作业D运行结束。

各作业周转时间为：作业A  70，作业B  30，作业C  90，作业D  90。平均作业周转时间为70分钟。

28、答：

(1) FIFO算法选中作业执行的次序为：A、B、D、C和E。作业平均周转时间为63分钟。

(2) SJF算法选中作业执行的次序为：A、B、D、E和C。作业平均周转时间为58分钟。

第三章：

   一、3、9、24、25、32

3、解释并发性与并行性

答：计算机操作系统中把并行性和并发性明显区分开，主要是从微观的角度来说的，具体是指进程的并行性（多处理机的情况下，多个进程同时运行）和并发性（单处理机的情况下，多个进程在同一时间间隔运行的）。

并行性是指硬件的并行性，两个或多个事件在同一时刻发生。

并发性是指进程的并发性，两个或多个事件在同一时间段内发生。

24、

死锁：所谓死锁是指在多道程序系统中，一组进程中的每一个进程都无限期等待被该组进程中的另一个进程所占有且永远不会释放的资源。如：假如双方都拥有部分资源（P1拥有A，P2拥有B，且A，B均只有一个），但这时P1还需要B，P2还需要A，于是P1与P2都会处在无限等待状态，发生了死锁。

饥饿：操作系统在一个分配资源时，当多个进程同时申请某类资源时，由分配策略确定资源分配给进程的次序。当资源分配策略是不公平的(unfair)的情况下，即不能保证等待时间上界的存在，即使系统没有发生死锁，某些进程也可能会长时间等待。当等待时间给进程推进和响应带来明显影响时，称发生了进程饥饿(starvation)。如：考虑一台打印机分配的例子，当有多个进程需要打印文件时，系统按照短文件优先的策略排序，该策略具有平均等待时间短的优点，似乎非常合理，但当短文件打印任务源源不断时，长文件的打印任务将被无限期地推迟，导致饥饿

32、

当N取不大于3的正整数时，系统没有死锁的危险。因为当N=1或2时，最多需要6台磁带机，系统不会发生死锁。当N=3时，最坏情况是3个进程都需要3个磁带机，且每个进程都已拥有2个磁带机，但此时系统还有2台未分配的磁带，能满足其中两个进程的资源请求，使进程顺利推进后再释放资源，此时另外1个进程因为得到被释放的磁带机而能够获得足够的磁带机，也可以顺利执行，不会发生死锁。

   二、5、6、16、23、36

5、答：1) 使用信号量和P、V操作：

var  name: array[1..100] of A;

A=record

  number:integer;

  name:string;

end

for i:=1 to 100 do {A[i].number:=i; A[i].name:=null;}

mutex,seatcount:semaphore;

i:integer;mutex:=1;seatcount:=100;

cobegin

{

process  readeri(var readername:string)(i=1,2,…)

    {

      P(seatcount);

      P(mutex);

for i:=1 to 100 do i++

      if A[i].name=null then A[i].name:=readername;

      reader get the seat number =i;            /*A[i].number

      V(mutex)

      进入阅览室，座位号i，座下读书;

P(mutex);

      A[i] name:=null;

      V(mutex);

      V(seatcount);

      离开阅览室;

     }

}

coend.

6、答：实质上是两个进程的同步问题，设信号量S1和S2分别表示可拣白子和黑子，不失一般性，若令先拣白子。

var  S1,S2:semaphore;

S1:=1;S2:=0; 

cobegin

{ 

process P1

  begin

    repeat

     P(S1);

     拣白子

     V(S2);

     until false;

  end

process P2

  begin

    repeat

     P(S2);

     拣黑子

     V(S1);

     until false;

  end

}

coend.

16、答：(1)用信号量和P、V操作。

var S,S1,S2,S3;semaphore;

   S:=1;S1:=S2:=S3:=0;

   flag1,flag2,flag3:Boolean;

   flag1:=flag2:=flag3:=true;

cobegin

{

 process 供应者

begin

    repeat

     P(S);

     取两样香烟原料放桌上，由flagi标记; /*flage1、flage2、flage3代表烟草、纸、火柴

     if  flag2&flag3  then V(S1);           /*供纸和火柴

      else  if  flag1&flag3  then V(S2);     /*供烟草和火柴

          else  V(S3);                    /*供烟草和纸

     untile false; 

end

 process 吸烟者1

begin

    repeat

      P(S1);

      取原料;

      做香烟;

      V(S);

      吸香烟;

    untile false;

process 吸烟者2

begin

    repeat

      P(S2);

      取原料;

      做香烟;

      V(S);

      吸香烟;

    untile false;

process 吸烟者3

begin

    repeat

      P(S3);

      取原料;

      做香烟;

      V(S);

      吸香烟;

    untile false;

}

coend.

23、

答：(1) P1，P2，P3，P4的Cki-Aki分别为：(2，2，2)、(1，0，2)、(1，0，3)、(4，2，0)

(1)系统处于安全状态，存在安全序：P2，P1，P3，P4

(2)可以分配，存在安全序列：P2，P1，P3，P4。

(3)不可以分配。

36、

答：当两个进程都执行完第一步(都占用R1) 时，系统进入不安全状态。这时无论哪个进程执行完第二步，死锁都会发生。可能到达的死锁点：进程P1占有一个R1和一个R2，而进程P2占有一个R1。或者相反。这时己形成死锁。进程---资源图为：

第四章：

   一、1、4、5、9、10、11、18

18、答：

虚拟存储器是指在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比物理内存容量大得多的、可寻址的“内存储器”。是一种具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。

虚拟存储器的实现方式有两种：请求分页系统和请求分段系统。请求分页系统允许只装入少数页面的程序(及数据)，便启动运行，以后，再通过调页功能及页面置换功能，陆续地把即将要运行的页面调入内存，同时把暂不运行的页面换出到外存上；请求分段系统允许只装入少数段(而非所有的段)的用户程序和数据，即可启动运行。以后再通过调段功能和段的置换功能将暂不运行的段调出，同时调入即将运行的段。

   二、3、6、13、15、20、29、30

3、答：(1) 作业的物理块数为3块，使用FIFO为9次，9/12=75%。使用LRU为7次，7/12=58%。使用OPT为6次，6/12=50%。

作业的物理块数为4块，使用FIFO为6次，6/12=50%。使用LRU为6次，6/12=50%。使用OPT为5次，5/12=42%。

    (2) 作业的物理块数为3块，使用FIFO为9次，9/12=75%。使用LRU为10次，10/12=83%。使用OPT为7次，7/12=58%。

作业的物理块数为4块，使用FIFO为10次，10/12=83%。使用LRU为8次，8/12=66%。使用OPT为6次，6/12=50%。

其中，出现了Belady现象，增加分给作业的内存块数，反使缺页中断率上升。

6、答：由于32-9-11=12，所以，页面大小为4KB，页面的个数为220 个。

13、答：首次适应、最坏适应算法处理这个作业序列可以满足分配，最佳适应算法不行。因为后者会分割出无法使用的碎片，浪费内存，从而，不能满足所有作业的内存需求。

15、答：因为逻辑地址长度为16位，而页面大小为4096字节，所以，前面的4位表示页号。把2F6AH转换成二进制为：0010 1111 0110 1010，可知页号为2。故放在14号物理块中，写成十六进制为：EF6AH。

20、答：虚地址0AC5H对应的物理地址为：12C5H。而执行虚地址1AC5H会发现页表中尚未有分配的页框而发生缺页中断，由系统另行分配页框。

29、

答：1)680   2)915  3)904  4)越界  5)1750  6) 越界。

30、

答：1) 1) 页面访问序列为0，0，1，1，0，3，1，2，2，4，4，3。

    2)FIFO为5次，缺页中断率为5/12=41.6%。LRU为6次，缺页中断率为6/12=50%。

LRU反比FIFO缺页中断率高。

第五章：

   一、2、12、21、26、28

2、

（1）轮询方式：

（2）中断驱动I/O方式

（3）DMA方式：

（4）通道方式

12、答P265

21、答：虚拟设备：为了提高独占设备的利用率，采用SPOOLING技术，用可共享的设备模拟独占设备，使独占设备成为共享设备，使每个作业感到自己分到了速度极高的独占设备。这种模拟的独占设备称为虚拟设备。

26 答：在联机的条件下，进行两个方向的操作，在数据输入时，将数据从输入设备传送到磁盘或磁带（块设备），然后把这些块设备与主机相连；反过来，在数据输出时，将输出数据传送到磁盘或磁带上，再从磁盘或磁带传送到输出设备。这样，可以将一占的物理设备虚拟为并行使用的多台逻辑设备，从而使该物理设备被多个进程共享。

28、答：设备性：用户不指定物理设备，而是指定逻辑设备，使得用户作业和物理设备之间分离开来，再通过其他途径建立逻辑设备和物理设备之间的映射，设备的这种特性就是“设备无关性”。  

好处：应用程序与具体物理设备无关，系统增减或变更设备时对源程序不必加以修改；易于应对I/O设备故障，提高系统可靠性；增加设备分配的灵活性，更有效地利用逻辑设备资源，实现多道程序设计。

   二、1、2、7、16

1、答：定位第1个记录需10ms。读出第1个记录，处理花2ms，这时已到了第4个记录，再转过18个记录(花18ms)才能找到记录2，所以，读出并处理20个记录的总时间：

10+3+(1+2+18)×19=13+21×19=412ms

        如果给出优先分布20个记录的方案为：1，8，15，2，9，16，3，10，17，4，11，18，5，12，19，6，13，20，7，14。当读出第1个记录，花2ms处理后，恰好就可以处理记录2，省去了寻找下一个记录的时间，读出并处理20个记录的总时间：

               10+3+3×19=13+247=260ms

2、答：处理次序为：100-110-129-147-186-78--41-27-18-12-10-8。移动的总柱面数：2。

7、答：(1)先来先服务算法FCFS为565，依次为143-86-147-91-177-94-150-102-175-130。

(2)最短查找时间优先算法SSTF为162，依次为143-147-150-130-102-94-91-86-175-177。

(3)扫描算法SCAN为169，依次为143-147-150-175-177-199-130-102-94-91-86。

(4)电梯调度为125(先向地址大的方向)，依次为143-147-150-175-177-102-94-91-86。为148(先向地址小的方向) 依次为143-130-102-94-91-86-147-150-175-177。

16答： 

第六章：

   一、4、5、16

5、答：

文件的物理结构和组织是指逻辑文件在物理存储空间中的存放方法和组织关系。

组织方式

（1）顺序文件 

（2）连接文件

（3）直接文件

（4）索引文件 

16、答：文件共享是指不同进程共同使用同一个文件，文件共享不仅为不同进程完成共同任务所必需，而且还节省大量外存空间，减少因文件复制而增加的I/O操作次数。文件共享有三种形式：静态共享、动态共享、符号链接共享。

   二、3、8、16、18

3、

答：    (1) 位示图占用字数为500/32=16(向上取整)个字。

    (2) 第i字第j位对应的块号N=32×i+j。

(3)申请时自上至下、自左至有扫描位示图跳过为1的位，找到第一个迁到的0位，根据它是第i字第j位算出对应块号，并分配出去。归还时已知块号，块号/32算出第i字第j位并把位示图相应位清0。

8、

答：1569/512得到商为：3，余数为：33。所以，访问的是80磁盘块的第33个字节。

16、

由于索引节点为128B，而状态信息占用68B，故索引节点中用于磁盘指针的空间大小为：128-68=60字节。

一次间接、二次间接和三次间接指针占用三个指针项，因而直接指针项数为：60/4-3=12个。每块大小为8KB。所以，直接指针时：12×8192=98304B。

一次间接指针时：8192/4=2048，即一个磁盘块可装2048个盘块指针，2048×8192=16MB。

二次间接指针时：2048×2048=4M，即二次间接可装4M个盘块指针，4M×8192=32GB。

三次间接指针时：2048×2048×2048=8G，即三次间接可装8G个盘块指针，8G×8192=TB。

18、答：