2011-12操作系统复习题及答案

(一)进程同步

●进程同步1

进程P1和进程P2并发执行时满足一定的时序关系，P1的代码段S1执行完后，才能执行P2的代码段S2.为描述这种同步关系，：试设计相应的信号量，：给出信号量的初始值，：给出进程P1和P2的结构

●进程同步2

问题描述：(理发店问题)一个理发店有一间配有n个椅子的等待室和一个有理发椅的理发室。如果没有顾客，理发师就睡觉；如果顾客来了二所有的椅子都有人，顾客就离去；如果理发师在忙而有空的椅子，顾客就会坐在其中一个椅子；如果理发师在睡觉，顾客会摇醒他。

1给出同步关系

2设计描述同步关系的信号量；

3给出满足同步关系的进程结构(请完成满足同步关系的进程结构)。

●进程同步2

       设公共汽车上，司机和售票员的活动分别为：司机的活动为启动车辆，正常行车，到站停车；售票员的活动为关车门，售票，开车门。

给出在汽车不断地到站、停车、行驶过程中，司机和售票员的活动的同步关系。

用信号量和wait, signal操作实现他们间的协调操作。

●进程同步3：某高校计算机系开设网络课并安排上机实习，假设机房共有2m台机器，有2n名学生选该课，规定：

(1)每两个学生组成一组，各占一台机器，协同完成上机实习；

(2)只有凑够两个学生，并且此时机房有空闲机器，门卫才允许该组学生进入机房；

(3)上机实习由一名教师检查，检查完毕，一组学生才可以离开机房。

   试用信号量机制实现它们的同步关系。

●进程同步4：多个进程对信号量S进行了5次 wait操作，2次signal操作后，现在信号量的值是-3，与信号量S相关的处于阻塞状态的进程有几个？信号量的初值是多少？

●进程同步5：使用两个进程计算Y=F1(X)+F2 (X). 在这个问题中，F1(X)和F2 (X)的计算是可以并行处理的，因此F1(X)和F2 (X)可以分别出现在两个进程中。在F1(X)+F2 (X)中，必须在F1(X)和F2(X)计算完毕，才能进行加法运算，因此本问题是同步问题。

(1)确定并发和顺序操作

(2)确定互斥或同步的规则

(3)同步的操作流程

(4)确定信号量的个数和含义

(5)确定进程的程序结构

●进程同步6：如下图所示，有多个PUT操作同时向BUFF1放数据，有一个MOVE操作不断地将BUFF1的数据移到Buff2，有多个GET操作不断地从Buff2中将数据取走。BUFF1的容量为m，BUFF2的容量是n, PUT、 MOVE、 GET每次操作一个数据，在操作的过程中要保证数据不丢失。试用wait、signal原语协调PUT、 MOVE的操作，并说明每个信号量的含义和初值。

(1)确定并发操作的规则

(2)设计信号量、初始值及用途含义

(3)给出进程的程序结构

●进程同步7：一售票厅只能容纳300人，当少于300人时，可以进入；否则，需在外等候。若将每一个购票者作为一个进程，请用wait、signal操作给出进程程序结构，并写出信号量及初值。

●进程同步8：针对如下所示的优先图，使用信号量给出正确的程序结构。

(二)进程调度与死锁

●进程调度与死锁1 ：5个进程，3种资源，某个时刻，资源分配情况如下：

         Allocation                  Max                    Available

         A     B    C               A    B    C             A     B     C

P0     0      1     0               7    5    3              ,3      3      2

P1     2      0     0               3    2    2              

P2     3      0     2               9    0    2

P3     2      1     1               2    2    2

P4     0      0     2               4    3    3

问：系统是否处于安全状态？如果P1再提出请求1个A类，2个C类资源，是否该批准？

●进程调度与死锁2：假设一个系统有某类资源m个，被n个进程共享，进程每次只请求和释放一个资源，证明只要系统满足下面两个条件，就不会发生死锁：

(1)每个进程需求资源的最大值在1到m之间；

(2)所有进程需要资源的最大值的和小于m+n。

证明：

设每个进程最多申请资源x个（1≤x≤m），

最坏情况下，为进程分配资源数为n（x-1） 。系统剩余资源为m- n（x-1） 。

只要 m- n（x-1）≥1；则系统不会出现死锁。整理得：

 nx ≤m+n-1，所以nx ≤m+n时，不会引起死锁

●进程调度与死锁3：和死锁1相同，系统的资源数量为：（10，5，7）。经过一段时间的分配后，资源分配与占用情况见下表所示。

●进程调度与死锁4：假设系统有4个相容类型的资源被3个进程共享，每个进程最多需要2个资源，证明这个系统不会死锁。

     假设每个进程都需要2个资源，3个进程先每个进程分一个资源，共需3个资源，这时候只需要再有一个资源就能保证至少有一个进程能够执行，系统即不会死锁

●进程调度与死锁5：有三个进程P1、P2和P3并发工作。进程P1需要资源S3和S1；进程P2需用资源S1和S2；进程P3需用资源S2和S3，回答：

(1)若对资源分配不加，会发生什么情况？为什么？

(2)为保证进程正确地工作，应采用怎样的资源分配策略？为什么？

  1) 若对进程间的资源分配不加，可能会发生死锁。若进程P1、P2和P3分别获得资源S3、S1和S2，后再继续申请资源时会导致进程间的“循环等待”，并且这种状态将永远持续下去。 

(2) 为保证系统处于安全状态，应采用下面列举3种资源分配策略：

     1) 采用静态资源分配：由于执行前已获得所需全部资源，故不会出现占有资源又等待资源的现象，从而避免资源的循环等待。

     2)  采用资源按序分配，避免出现循环等待资源的现象。

     3)  采用银行家算法进行分配资源前的检测。

●进程调度与死锁6：有5个任务A，B，C，D，E，它们几乎同时到达，预计它们的运行时间为10，6，2，4，8min。其优先级分别为3，5，2，1和4，这里5为最高优先级。对于下列每一种调度算法，计算其平均进程周转时间（进程切换开销可不考虑）。

(1)先来先服务（按A，B，C，D，E）算法。

(2)优先级调度算法。

(3)时间片轮转算法。  

●进程调度与死锁7：设某系统进程的状态有创建状态、运行状态、阻塞状态、延迟状态和完成状态。试画出系统的进程状态变迁图，并说明状态变迁可能的原因。

●进程调度与死锁8：一个计算机系统中拥有6台打印机，现有N个进程竞争使用，每个进程要求两台，试问，N的值如何选取时系统中绝对不会出现死锁？为什么？

(三)内存管理

●内存管理1：在分页存储管理系统中，存取一次内存的时间是8us，查询一次快表的时间是1us，缺页中断的时间是20us，假设页表的查询与快表的查询同时进行 。当查询页表时，如果该页在内存但快表中没有页表项，系统将自动把该页页表项送入快表。

(1)求对某一数据进行一次次存取可能需要的时间？

(2)现连续对同一页面上的数据进行4次连续读取，求每次读取数据可能需要的时间?

●内存管理2：若在一分页存储管理系统中，某作业的页表如下所示。已知页帧大小为1024字节，试将逻辑地址1011，2148，3000，5012转化为相应的物理地址（注：此处块号即为页帧号）。

●内存管理3：假设一个请求分页系统具有一个平均访问和传输时间为20ms的分页磁盘。地址转换时通过在主存中的页表来进行的，每次内存访问时间为1s。为了提供性能，加入一个快表，当页表项在快表中，可以减少内存的访问次数。假设80%的访问发生在快表汇总，而且剩下中的10%会导致页错误，内存的有效访问时间是多少？（假设快表的查找时间可以忽略）

●内存管理4：假设有下面也引用序列1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6. LRU页面置换算法会导致多少次页错误？假设内存帧数分别为2,3,4

●内存管理5：有一计算机系统，内存容量为512K，辅存容量为2G，逻辑地址形式如下：

求其虚拟存储器的实际容量？

●内存管理6：有这样一种页面置换算法，它给每一个内存块(块与页大小相等)设置一个计数器，以计数曾经装入过该块的页面数。当需要置换一个页面时，该算法总是将其计数值最小的那个块内的页面换掉，当有多个最小值时，按FIFO执行。若某进程分得4个内存块，现对1、2、3、4、5、3、4、1、6、7、8、7、8、9、7、8、9、5、4、5、4、2，页面引用串，解答如下问题：

(1)求在上述算法下的页面错误数；

(2)求在最优置换算法下的页面错误数。

(四)文件系统

●文件系统1：设想一个在磁盘上的文件系统的块大小为512B，假设每个文件的信息已经在内存中。对三种分配方法：连续分配、链接分配(假设链接指针占1个字节)和索引分配，假设文件的线性逻辑地址从0开始线性增长，分别回答下面的问题：

(1)逻辑地址到物理盘块地址的映射是怎样进行的？(对于索引分配，假设文件总是小于512Blocks)

(2)假设现在处于盘块10，现在想访问盘块4，那么必须从磁盘上读多少个物理块？

●文件系统2：在有些系统中，一个子目录可以被一个授权用户读和写，就像一个普通文件一样。

(1)描述可能产生的文件保护问题。

(2)给出你认为的保护处理方案。

●文件系统3：假定一个盘组共有100个柱面，每个柱面上有16个磁道，每个盘面分成4 个扇区，问：

(1)整个磁盘空间共有多少个存储块？

(2)如果用字长为32位的单元来构造位示图，共需要多少个字？

(3)位示图中第18个字的第16位对应的块号是多少？

.   （1） 4*16*100＝00

    （2） 00/32＝200

（3） 18*32+16＝592

●文件系统4：假设一个系统支持连续分配、连接分配和索引分配，应依据什么标准决定哪个方法最适合一个特定的文件？

●文件系统5：假定有一个磁盘组共有100个柱面，每个柱面有8个磁道，每个盘面划分成8个扇区。现有一个5000个逻辑记录的文件，逻辑记录的大小与扇区大小相等，该文件以顺序结构被存放在磁盘组上，柱面、磁道、扇区均从0开始编址，逻辑记录的编号从0开始，文件信息从0柱面、0磁道、0扇区开始存放。请问：

(1)该文件的3468个逻辑记录应存放在哪个柱面的第几个磁道的第几个扇区上。

(2)第56柱面上的第8磁道的第5扇区中存放的是该文件的第几个逻辑记录。

      （1） 柱面号：3468/＝54

          磁道号：（3468%）/8＝1

          扇区号：（3468%）％8＝4

（2）56*+8*8+5＝3652

(五)I/O系统

●I/O系统1：假定在某移动臂磁盘上，刚刚处理了访问60号柱面的请求，目前正在73号柱面上读信息，并有下列请求序列等待访问磁盘：请求序列欲访问的柱面号：150、50、178、167、87、43、23、160、85。

试用最短任务优先算法和电梯调度算法，分别排出实际上处理上述请求的次序。

●I/O系统2：I/O软件一般分为4个层次，用户层I/O软件、I/O内核子系统、设备驱动程序以及中断处理程序。请说明以下各工作是在哪一层完成的？

(1)向设备寄存器写命令；

(2)检查用户是否有权使用设备；

(3)将二进制整数转换成ASCII码以便打印。

●I/O系统3：内核I/O子系统的功能职责是什么？系统采用什么方法来协调内核I/O组件的活动，它们各有什么优劣？

●I/O系统4：RAID的哪个级别使用奇偶校验来实现冗余？它们是如何恢复破坏的数据的？

(六)概念复习

1.当时引入多道程序的目的在于（  C   ）。 

A.有利于代码共享，减少主、辅存信息交换量   B．充分利用存储器

C.充分利用CPU，减少CPU等待时间          D．提高实时响应速度 

2.在单处理机计算机系统中，（   B   ）是并行操作的。

A.程序与程序

B.处理机的操作与通道的操作

C.主程序与子程序

D.用户程序与操作系统程序

3.当线程处于阻塞状态时，线程( B    )。

    A. 正在占用处理机        B.没有占用处理机

C. 将进入执行状态        D.将进入结束状态

4.当多道程序系统中发生死锁时，（   C    ）。

1.计算机系统不能处理任何事情

2.某个进程不能够执行

3.一组进程相互等待，并进入阻塞状态

4.不能进行输入和输出

5.下面哪一个不是程序在并发系统内执行的特点（B      ）。

A.产生死锁的必然性          B.资源分配的动态性

C.程序执行的间断性          D.相互通信的可能性

6.进程和程序的一个本质区别是(    D  )。

A. 进程分时使用CPU，程序独占CPU

B．进程存储在内存，程序存储在外存

C. 进程在一个文件中，程序在多个文件中

D．进程为动态的，程序为静态的

7.在文件系统中，采用位图主要是实现（B  ）。

A. 磁盘的驱动调度   B. 磁盘空间的分配和回收

C. 文件目录的查找   D. 页面置换

8.进程调度的基本功能是选择(    A  ).

       A.就绪的进程   B.后备的作业  C.空闲内存  D.空闲设备

9.对于普通用户而言，OS的（    B   ）是最重要。

      A.开放性      B.方便性    C.有效性     D.可扩充性

10.计算机的普通用户通常通过（    B    ）使用OS所提供的服务。

A.中断键盘           B.控制接口

C.指令           D.系统调用

11.（       B  ）进程调度算法适合分时系统.

A.先来先服务      B.轮转   

C.短作业优先      D.最高优先级

12.进程的控制信息和描述信息存放在（     B    ）。

A.JCB        B.PCB        C.AFT         D.SFT

13.下列有可能导致一进程从运行变为就绪的事件是（ D   ）。

A.一次I/O操作结束     

B.运行进程需作I/O操作

C.运行进程结束     

D.出现了比现运行进程优先权更高的进程

15.与计算机硬件关系最密切的软件是（    D   ）.

A.编译程序        B.数据库管理系统  

C.游戏程序        D.OS

16.与设备控制器关系最密切的软件是（   B  ）。

A.编译程序      B.设备驱动程序   C.存储管理程序    D.处理机管理

17.(    C  )进程调度算法适合紧急事件的处理。

    A.先来先服务    B.轮转    C.可抢占优先级   D.优先级

18.若进程P一旦被唤醒就能够投入运行，系统可能（     D  ）。

A.在抢占调度方式中，P的优先级高于当前运行的进程 

B.进程P的优先级最高 

C.就绪队列为空队列 

D.在抢占调度方式中，P的优先级高于就绪队列中所有的进程

19.进程依靠什么从阻塞状态过渡到就绪状态（      D   ）。

    A.操作人员的命令            B.系统服务

C.等待下一个时间片到来      D.由"合作"进程唤醒

20.在下面的I/O控制方式中，需要CPU干预最少的方式是（   C）。

A. 程序I/O方式                   B. 中断驱动I/O控制方式  

C. 直接存储器访问DMA控制方式   D. I/O通道控制方式

21.新创立的进程首先进入(   A   )状态。

A.就绪          B.执行        C.阻塞        D.挂起

22.在OS中，文件的存取控制可以使（       A    ）。

A. 用户间不能相互删除文件

B. 内存中的多道程序间不相互破坏 

    C. 内存中的程序不破坏OS 

    D. 防止黑客攻击

23.页的逻辑地址形式是:页号24位，页内地址10位,内存128M,辅存10G，那么虚拟存储器最大实际容量可能是(   C   ) 。

    A.1024K           B.16G        C.10G     D.10G+128M

24.分页存储管理的存储保护是通过(    A  )完成的。

A.页表      B.快表    C.存储键     D.索引

25.用户使用（   D   ）形式的文件。

    A.链接       B.连续   C.物理   D.逻辑

26.能够装入内存任何位置并能执行的程序代码必须是可(    B  )。

A.动态链接        B.重定位 

C.可重入的        D.静态链接   

27.. 若系统中只有用户级线程，则处理机调度单位是（   A  ）。

A.线程   B.进程   C.程序   D.作业

28.如果要使装入内存的程序，在内存中移动后仍能正常运行，必须要有(      B  )的支持。

A. 静态重定位     B.动态重定位    C. 动态链接    D.静态链接

29.采用（ B ）不会产生内部碎片。

A.分页式存储管理         B.分段式存储管理

C.固定分区式存储管理     D.段页式存储管理

30.假脱机技术中，对打印机的操作实际上是用对磁盘存储实现的，用以替代打印机的部分是指（  C ）。

A.共享设备                    B.独占设备  

C.虚拟设备                    D.物理设备

31.UNIX系统中的文件分配有以下哪些特征：

A.基于非连续块的动态索引分配。B.基于连续块的动态分配

C.基于非连续块的预分配。   D.以上都不是

32.最短进程优先技术的一个困难在于＿＿

A.需要估算每个进程的处理时间。B.长进程的饥饿

C.缺乏抢占。                  D.以上都是

33.分时系统中的当前运行进程连续获得了两个时间片，原因可能是（      ）。

A．该进程的优先级最高        B．就绪队列为空

C．该进程最早进入就绪队列    D．该进程是一个短进程

34.. 进程依靠（     ）从阻塞状态过渡到就绪状态。

A.程序员的命令              B.系统服务

C.等待下一个时间片到来      D.“合作”进程的唤醒

简答题：

1.为什么要区分系统态和用户态？

2.进程和线程的主要区别是什么？

解：线程可定义为进程内的一个执行单位，或者定义为进程内的一个可调度实体。

在具有多线程机制的操作系统中，处理机调度的基本单位不是进程而是线程。一个进程可以有多个线程，而且至少有一个可执行线程。

进程和线程的区别是：

(1)线程是进程的一个组成部分；

(2)进程的多个线程都在进程的地址空间活动；

(3)资源是分给进程的，而不是分给线程的，线程在执行中需要资源时，系统从进程的资源配额中扣除并分配给它；

(4)处理机调度的基本单位是线程，线程之间竞争处理机，真正在处理机上运行的是线程；

(5)同一进程中的线程在执行过程中，可能需要同步。

3.进程能自己将自己唤醒吗？进程能自己将自己撤消吗？

解：唤醒进程和撤消进程都是要通过在CPU上运行程序来实现的。一个进程入睡了，它就不可能被调度到CPU上运行；一个进程在撤消前必须先进入终止状态，而处于终止状态的进程不可能被调度到CPU上运行。因此，进程被唤醒、被撤消都不能由自己来完成，只能由别的进程实现。

4.程序并发执行的主要特性是什么？

解：可分割性(即可中断性)、失去封闭性、失去可再现性。

5.何为死锁？产生死锁的原因和必要条件是什么？

解：死锁是指多个进程因竞争资源而造成的一种僵持状态。若无外力作用，这些进程都将永远处于阻塞状态，不能再运行下去。

产生死锁的原因有：资源不足资源、进程推进次序不当。

产生死锁的必要条件有：互斥条件、请求和保持条件、不可剥夺条件、环路等待条件

6.在解决死锁问题的几个方法中，哪种方法最容易实现？哪种方法使资源的利用率最高？

解：预防死锁方法，主要是破坏产生死锁的必要条件。该方法是最容易实现的，但系统资源利用率较低。

避免死锁方法，比较实用的有银行家算法（Banker Algorithm）。该算法需要较多的数据结构，实现起来比较困难，但资源利用率最高。

检测死锁方法是基于死锁定理设计的，定期运行该算法对系统的状态进行检测，发现死锁便予以解除。其中，需要比较一下各种死锁解除方案的代价，找到代价最小的方案。该方法最难实现，资源利用率较高。

7.分页存储管理存在的局限性是什么?

8.为什么说分段系统较之分页系统更易于实现信息共享和保护？如何实现。

解

a)在分页和分段存储管理系统中，多个进程并发运行，共享同一内存块里的程序或数据是可行的。为了实现共享，必须在各共享者的段表或页表中分别有指向共享内存块的表目。

b)对分段式系统，被共享的程序或数据可作为单独的一段。在物理上它是一段，在不同的进程中，可以对应不同的逻辑段，相对来说比较易于实现。

c)对分页管理，则要困难的多。首先，必须保证被共享的程序或数据占有整数块，以便与非共享部分分开。其次，由于共享程序或数据被多个进程访问，所以每个进程对共享程序或数据的访问都应该是有条件的。

d)因此，从共享和保护的实现上来看，须共享的程序段或数据段是一个逻辑单位，而分段存储管理中被共享的程序或数据作为一个整体（一段）,实现共享和保护就要方便得多。

e)分段系统的共享是通过两个（或多个）进程的段表之相应表目都指向同一个物理段，并设置共享计数来实现的。每段设置访问方式，就可以实现段的保护。

9.多道程序系统为什么能提高CPU的利用率？

10.文件的逻辑结构有哪些？ 

11.什么是设备性？

12.为什么要引入线程，解释一下线程与进程之间的相互关系。

13.死锁的必要条件是什么？

14.什么是虚拟内存？

解 虚拟存储器通过把主、辅存统一起来管理，给用户造成一种仿佛系统内有巨大主存供用户使用的假象。例如页式存储管理，一道作业被划分成若干页，其中较活跃的几页放在内存，而其余不活跃的页被放在辅存，当需要访问辅存内的页时，就可通过页面调度将其调入内存运行；但用户感觉不到这种变化，他会以为作业的所有部分都存在于主存。这样可以让更多的作业进入主存，提高系统的效率。

15.说明静态重定位和动态重定位的区别。

解 “重定位”，在实际上指的是这样相互联系的两件事情：一是确定一个待执行程序在内存中的位置；二是将程序中的逻辑地址转换成物理地址。说它们是相互联系的，是因为后一件事情是由前一件事情决定的。

静态重定位，指的是在程序装入时实现的重定位。具体的讲，就是将程序装入内存后，立即根据其装入位置将程序中需重定位的逻辑地址转换成物理地址，包括指令地址、数据地址、子程序入口地址等。这种“定位”的特点是“定位”之后，内存中的代码发生了变化，程序不能在内存移动，CPU按物理地址运行程序。

动态重定位，是在程序执行的过程中，根据执行的需要动态地装入、链接和定位。它不是根据程序在内存的位置立即将指令和数据的逻辑地址转换成物理地址，而是把这种位置信息送入一个称之为“地址映射机构”的硬件中，然后，CPU按逻辑地址执行程序。在执行中，由“映射机构”将逻辑地址及时地转换成正确的访存物理地址。这种定位方法的主要特点是重定位后，内存中的代码没有发生了变化，允许程序在执行的过程中在内存移动位置，这只要更换“映射机构”中的启址信息就可将同一程序映射到内存不同的地方。这种位置移动对提高内存空间的利用率是有好处的。

16.假脱机技术是什么？

解：SPOOLing系统，把独享设备分割为若干台逻辑上的独占的设备，使用户感受到系统有出若干独占设备在运行。当然，系统中至少一台拥有物理设备，这是虚拟设备技术的基础。

SPOOLing系统又称“假脱机I/O系统”，其中心思想是，让共享的、高速的、大容量外存储器（比如，磁盘）来模拟若干占设备，使系统中的一台或少数几占设备变成多台可并行使用的虚拟设备。

SPOOLing系统主要管理外存上的输入井和输出井，以及内存中的输入缓冲区和输出缓冲区。其管理进程主要有输入和输出进程，负责将输入数据装入到输入井，或者将输出井的数据送出。它的特点是：提高了 I/O操作的速度；将独占设备改造为共享设备；实现了虚拟设备功能。

17.为什么在分页和分段管理下取一条指令或一个操作数通常需两次访存？如何解决这一问题？

解 这是因为用于地址变换的页表或段表也是存放在内存的，为了将CPU给出的逻辑地址变成物理地址，首先就要访问内存的页表和段表，然后，根据形成的物理地址再取指令或数据，这就要两次访存。解决这一问题的办法是提供一个称之为“快表”的硬件，用以存放当前运行进程的页表或段表的部分内容，“快表”的访问时间很快，因此可以节约访问页表和段表的时间。 存储器访问具有时间和空间的“局部性”，因此快表的命中率一般可达70%到90%；页表和段表是在系统执行过程中，每时每刻都需要访问的，因此，访问时间的微小缩短，其累计节约的时间却可以达到很大。

18.为什么要引入设备性？如何实现设备性？

19.对目录管理的主要要求是什么？

   实现“按名存取”；提高对目录的检索速度；文件共享；允许文件重名。