操作系统算法题

2．设在一个页面大小为 1K的系统中，正在处理器上执行的一个进程的页表如图所示：

页号     状态位   访问位   修改位   物理块号

0     1     1     0     4

1     1     1     1     7

2     0     0     0     -

3     1     0     0     2

4     0     0     0     -

5     1     0     1     0

起始页号和块号均为0。

2．下列虚地址（十进制）对应与什么物理地址：5449，2221。  

解：（10分）5449的物理地址为：329      2221的物理地址为：2221

4．设公共汽车上，司机和售票员的活动分别是：

   司机：   启动车辆      售票员：  上乘客

      正常行车         关车门

      到站停车         售票

                    开车门

                    `下乘客

在汽车不断地到站，停车，行使过程中，这两个活动有什么同步关系？并用 wait和signal 原语操作实现它们的同步。

解：BEGIN 

integer stop,run;

Stop:=0;

Run:=0;

COBEGIN

Driver: BEGIN

               L1: wait(run);

                启动车辆；

正常行车；

到站停车；

             signal(stop);

                Goto L1;

      END

Conductor: BEGIN

        L2：  上乘客；

           关车门；

           signal(run);

           售票；

wait(stop);

开车门；

下乘客；

Goto  L2;

END

COEND

END

6、某段表内容如下：

   一逻辑地址为（2，154）的实际物理地址为多少？

答：逻辑地址（2154）表示段号为2，即段首地址为480K，154为单元号，则实际物理地址为480K+154。

8．系统中有五个进程P₁、P₂、P₃、P₄、P₅，有三种类型的资源：R1、R2、和R3。在T₀时刻系统状态如表所示。若采用银行家算法实施死锁避免策略，回答下列问题：    （共9分，每小题3分）

1． T₀时刻是否为安全状态？为什么？

2． 若这时P₄请求资源（1，2，0），是否能实施资源分配？为什么？

3． 在上面的基础上，若进程P₃请求资源（0，1，0），是否能实施资源分配？为什么？ 

T₀时刻系统状态

解：（共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

1．有那些页面不在内存？（2分）

2．   请分别计算进程中虚地址为0x3B7、0x12A5、0x1432单元的物理地址（用十六进制表示），并说明理由。    （6分）

解：（共8分）不在内存的是第2和4页（按页号），或第3和5页（按序号）。（2分）  0x3B7的物理地址=0x 73 B7  （2分）0x12 A5的物理地址=0x176 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 fromkeyboard;

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分）

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号虚页，因为它离访问点最远。

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);                       Writefile 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) modn ;

           signal (full);

           signal (mutex);

        until false ;

        end

consumer: begin

            repeat

        wait (full);

        wait (mutex);

        nextc :=buffer(out);

        out := (out+1) modn;

        signal (empty);

        signal (mutex);

        consume the item innextc;

        until false ;

      end

   parend     end

20、请用信号量描述哲学家进餐问题。（15分）

解：哲学家进餐问题（15分）

public void philosopher (inti) {

      while (true) {

        think();

        wait (fork[i]);

        wait (fork [(i+1) %5]);

        eat();

        signal(fork [(i+1) %5]);

        signal(fork[i]);

        }     }

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<CHAIRS)  {

waiting=waiting+1;

signal(customers);

signal(mutex);

wait(barbers);

} else  {

   signal(mutex);

}   }

24、在公共汽车上，乘客上完后，售票员关门，驾驶员开车，售票员售票，到站汽车停稳后，售票员开门，乘客上下车，售票员和驾驶员之间密切配合，直到下班。请用信号量描述公共汽车上售票员与驾驶员的工作过程。（10分）解：建立驾驶员和售票员两进程，驾驶员进程执行过程如下：

判售票员关门没有

（1）  开车

（2）  到站后停车

（3）  重复（1）－（3）

售票员执行过程如下：

（1）  判断乘客上完没有

（2）  关门

（3）  售票

（4）  判车停稳没有

（5）  开门

（6）  重复（1）－（5）

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