计算机操作系统考试重点习题集

计算机操作系统习题

原语：由若干多机器指令构成的完成某种特定功能的一段程序，具有不可分割性；即原语的执行必须是连续的，在执行过程中不允许被中断

死锁：是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去

进程：是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位

线程：进程内一个相对独立的、可调度的执行单元，是系统独立调度和分派CPU的基本单位指运行中的程序的调度单位

管程：管程 (英语：Monitors，也称为监视器) 是一种程序结构，结构内的多个子程序（对象或模块）形成的多个工作线程互斥访问共享资源。这些共享资源一般是硬件设备或一群变数

链接文件：在文件之间创建链接，实际上是给系统中已有的某个文件指定另外一个可用于访问它的名称

文件系统：操作系统用于明确存储设备或分区上的文件的方法和数据结构；即在存储设备上组织文件的方法 快表

虚拟存储器：作业装入的时候只装入一部分，另一部分放在磁盘上，当需要的时候再装入到主存，用户的逻辑地址空间可以比主存的绝对地址空间要大 逻辑地址：是指由程序产生的与段相关的偏移地址部分

物理地址：是指出现在CPU外部地址总线上的寻址物理内存的地址信号，是地址变换的最终结果地址

驱动程序：是一种可以使计算机和设备通信的特殊程序。相当于硬件的接口，操作系统只有通过这个接口，才能控制硬件设备的工作，假如某设备的驱动程序未能正确安装，便不能正常工作

临界区：指的是一个访问共用资源的程序片段，而这些共用资源又无法同时被多个线程访问的特性

程序控制块; 系统为了管理进程设置的一个专门的数据结构。系统用它来记录进程的外部特征，描述进程的运动变化过程。同时，系统可以利用PCB来控制和管理进程

文件控制块: 操作系统为管理文件而设置的一组具有固定格式的数据结构，存放了为管理文件所需的所有有属性信息（文件属性或元数据）

处理机: 处理机包括中央处理器，主存储器，输入-输出接口，加接外围设备就构成完整的计算机系统。处理机是处理计算机系统中存储程序和数据，并按照程序规定的步骤执行指令的部件

操作系统: 是管理和控制计算机硬件与软件资源的计算机程序，是直接运行在“裸机”上的最基本的系统软件，任何其他软件都必须在操作系统的支持下才能运行

页表: 页表是一种特殊的数据结构，放在系统空间的页表区，存放逻辑页与物理页帧的对应关系

DMA:直接存储器访问

库函数：把函数放到库里，供别人使用的一种方式。.方法是把一些常用到的函数编完放到一个文件里，供不同的人进行调用。调用的时候把它所在的文件名用#include<>加到里面就可以了

1

简答题

1. OS有哪几大特征？其最基本的特征是什么？ 并发、共享、虚拟、异步，最基本的是并发和共享

2. 什么是时分复用技术？举例说明它能提高资源利用率的根本原因是什么？

a. 时分复用技术：将资源在不同的时间片内分配给各进程以使该资源被重复利用，从而提高资源的利用率。

b. 如采用时分复用技术的虚拟处理机，能够在不同的时间片内处理多个用户的请求，从而使得用户感觉自己独占主机，而处理机在这期间也被充分的利用。

3. 为什么要引入实时操作系统？

答：实时操作系统是指系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。引入实时OS 是为了满足应用的需求，更好地满足实时控制领域和实时信息处理领域的需要

4. 在基于微内核结构的OS中，应用了哪些新技术？ 采用客户/服务器模式和面向对象的程序设计技术。

5. 何谓微内核技术？在微内核中通常提供了哪些功能？

答：把操作系统中更多的成分和功能放到更高的层次（即用户模式）中去运行，而留下一个尽量小的内核，用它来完成操作系统最基本的核心功能，称这种技术为微内核技术。在微内核中通常提供了进程（线程）管理、低级存储器管理、中断和陷入处理等功能。

6. 在操作系统中为什么要引入进程的概念？它会产生什么样的影响？

为了使程序在多道程序环境下能并发执行，并对并发执行的程序加以控制和描述，在操 作系统中引入了进程概念。

影响: 使程序的并发执行得以实行

7. PCB提供了进程管理和进程调度所需要的哪些信息?

进程标识符、处理机状态、进程调度信息、进程控制信息。

8. 何谓操作系统内核? 内核的主要功能是什么? 操作系统内核是指大多数操作系统的核心部分。它由操作系统中用于管理存储器、文件、外设和系统资源的那些部分组成。操作系统内核通常运行进程，并提供进程间的通信

9. 为什么要在OS中引入线程? 在OS中引入进程的目的，是为了使多个程序能并发执行，以提高资源利用率和系 统吞吐量。在OS中再引入线程，则是为了减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性。

10. 线程控制块TCB中包含了哪些内容?

一般TCB中的内容较少，因为有关资源分配等多数信息已经记录于所属进程的PCB中．TCB中的主要信息包括线程标识、线程状态、调度参数、现场、链接指针，其中现场信息主要包括通用寄存器、指令计数器PC以及用户栈指针．对于操作系统支持的线程，TCB中还应包含系统栈指针。

2

11. 何谓用户级线程和内核支持线程?

答： （1）用户级线程：仅存在于用户空间中的线程，无须内核支持。 调度单位：进程 （2）内核支持线程：在内核支持下运行的线程。 调度单位：线程

12. 试比较FCFS和SJF两种进程调度算法。

相同点：两种调度算法都可以用于作业调度和进程调度。

不同点：FCFS调度算法每次都从后备队列中选择一个或多个最先进入该队列的作业，将它们调入内存、分配资源、创建进程、插入到就绪队列。该算法有利于长作业/进程，不利于短作业/进程。SPF算法每次调度都从后备队列中选择一个或若干个估计运行时间最短的作业，调入内存中运行。该算法有利于短作业/进程，不利于长作业/进程。

13. 在时间片轮转法中，应如何确定时间片的大小?

答：时间片应略大于一次典型的交互需要的时间。一般应考虑三个因素：系统对相应时间的 要求、就绪队列中进程的数目和系统的处理能力。

14. 什么是最早截止时间优先调度算法? 举例说明之。 根据任务的开始截止时间确定的任务优先级调度算法。截止时间越早则优先级越高。 该算法要求在系统中保持一个实时任务就绪队列，该队列按各任务截止时间的先后排序。举 例：非抢占式调度方式用于非周期实时任务

15. 什么是最低松弛度优先调度算法? 举例说明之。

答： 该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。 任务的紧急程度愈高， 为该任务所赋予的优先级就愈高，以使之优先执行。例如，一个任务在 200 ms 时必须完成， 而它本身所需的运行时间就有 100 ms，因此，调度程序必须在 100 ms 之前调度执行，该任务 的紧急程度(松弛程度)为 100 ms。 又如， 另一任务在 400 ms 时必须完成， 它本身需要运行 150 ms，则其松弛程度为 250 ms

16. 何谓死锁? 产生死锁的原因和必要条件是什么?

答：死锁是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。

产生死锁的原因为竞争资源和进程间推进顺序非法。其必要条件是：互斥条件、请求和 保持条件、不剥夺条件、环路等待条件。

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

答：解决死锁的四种方法即预防、避免、检测和解除死锁中，预防死锁最容易实现； 解除死锁使资源的利用率最高。

18. 可采用哪几种方式将程序装入内存? 它们分别适用于何种场合? （1）绝对装入方式，只适用于单道程序环境。 （2）可重定位装入方式，适用于多道程序环境。

（3）动态运行时装入方式，用于多道程序环境；不允许程序运行时在内存中移位置。

3

19. 何谓装入时动态链接? 装入时动态链接方式有何优点? 答：

装入时动态链接是指将用户源程序编译后得到的一组目标模块，在装入内存时采用边装 入边链接的链接方式。

优点：加快程序的装入过程，且可以节省大量内存空间。

20. 何谓运行时动态链接? 运行时动态链接方式有何优点?

答：运行时动态链接是将对某些模块的链接推迟到程序执行时才进行链接， 也就是，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由 OS 去找到该模块并将之装入内存，把它链接到调用者模块上。 优点：凡是在执行过程中未被用过的目标模块，都不会被调入内存和被链 接到装入模块上，这样不仅能加快程序的装入过程，而且可节省大量的内 存空间。

21. 在采用首次适应算法回收内存时，可能出现哪几种情况? 应怎样处理这些情况? 答：在采用首次适应算法回收内存时可能出现4种情况：

（1）回收区前邻空闲区。将回收区与前邻空闲区合并，将前邻空闲区大小修改为两者之和。

（2）回收区后邻空闲区。将两区合并，改后邻空闲区始址为回收区始址，大小为两者之和。

（3）回收区前后均邻空闲区。将三个分区合并，修改前邻空闲区大小为三者之和。 （4）回收区前后均不邻空闲区。为回收区设置空闲区表项，填入回收区始址和大小并插入

空闲区队列。

22. 为什么要引入对换? 对换可分为哪几种类型?

在多道环境下，一方面，在内存中的某些进程由于某事件尚未发生而被阻塞，但 它却占用了大量的内存空间，甚至有时可能出现在内存中所有进程都被阻塞而迫 使 CPU 停止下来等待的情况；另一方面，却又有着许多作业在外存上等待，因无 内存而不能进入内存运行的情况。显然这对系统资源是一种严重的浪费，且使系 统吞吐量下降。为了解决这一问题，在操作系统中引入了对换(也称交换)技术。 可以将整个进程换入、换出，也可以将进程的一部分(页、段)换入、换出。前者 主要用于缓解目前系统中内存的不足，后者主要用于实现虚拟存储。

23. 在以进程为单位进行对换时，每次是否都将整个进程换出? 为什么? 答：在以进程为单位进行对换时，并非每次都将整个进程换出。这是因为：

(1)从结构上讲，进程由程序段、数据段和进程控制块组成的，其中进程控制块总有部分或全部常驻内存，不被换出。

(2)程序段和数据段可能正被若干进程共享，此时它们也不能换出。

24. 什么是页面? 什么是物理块? 页面的大小应如何确定?

答：页面，物理块——分页存储管理方式中的单元。 页面：分页存储管理将进程的逻辑地址空间分成若干个页，并为各页加以编号。 物理块：相应地，也将内存的物理空间分成若干个物理块，同样为它们加以编号 页面大小：既不能太小也不能太大，要起到减少内存碎片总空间的作用，也不能 使页表过长，总之要选择适中，且页面大小应

4

是 2 的幂，通常为 1KB-8KB。

25. 什么是页表? 页表的作用是什么?

答：在分页系统中，允许将进程的各个页离散地存储在内存的任一物理块中，为 保证进程仍让能够正确地运行， 即能在内存中找到每个页面所对应的物理块，系 统又为每个进程建立了一张页面映像表，简称页表。 页表的作用是实现从页号到物理块号的地址映射。

26. 具有快表时是如何实现地址变换的?

系统将有效地址(逻辑地址)中的页号与页表寄存器中的内容比较，若页号太 大，表示访问越界，于是产生越界中断；若未出现越界情况，地址变换机构自动 地将页号 P 送入高速缓存， 再确定所需要的页是否在快表(高速缓存)中。若在则 直接读出该页所对应的物理块号，并送物理地址寄存器；若在快表中未找到对应 的页表项，需再访问内存中页表，找到后，把从页表中读出的页表项存入快表中 的一个寄存器单元中， 以取代一个老的、 已被认为不再需要的页表项。 与此同时， 再将有效地址寄存器中的页内地址直接送入物理地址寄存器， 从而完成了从有效 地址(逻辑地址)到物理地址的转换

27. 虚拟存储器有哪些特征? 其中最本质的特征是什么?

虚拟存储器有多次性、对换性、虚拟性三大特征。最本质的特征是虚拟性。 28. 实现虚拟存储器需要哪几个关键技术? 答：

（1）在分页请求系统中是在分页的基础上，增加了请求调页功能和页面置换功能所形成的

页式虚拟存储系统。允许只装入少数页面的程序（及数据），便启动运行。

（2）在请求分段系统中是在分段系统的基础上，增加了请求调段及分段置换功能后形成的

段式虚拟存储系统。允许只装入少数段（而非所有段）的用户程序和数据，即可启动运行。

29. 在请求分页系统中，应从何处将所需页面调入内存? 答：请求分页系统中的缺页从何处调入内存分三种情况：

（1）系统拥有足够对换区空间时，可以全部从对换区调入所需页面，提高调页速度。在进程运行前将与该进程有关的文件从文件区拷贝到对换区。

（2）系统缺少足够对换区空间时，不被修改的文件直接从文件区调入；当换出这些页面时，未被修改的不必换出，再调入时，仍从文件区直接调入。对于可能修改的，在换出时便调到对换区，以后需要时再从对换区调入。

（3）UNIX 方式。未运行页面从文件区调入。曾经运行过但被换出页面，下次从对换区调入。UNIX 系统允许页面共享，某进程请求的页面有可能已调入内存，直接使用不再调入。

30. 试说明在请求分页系统中页面的调入过程。 31. 当前可以利用哪几种方法来防止“抖动”?

预防方法：1.采取局部置换策略。2.把工作集算法融入到处理及调度中。3.利用“L=S”准则调节缺页率。4.选择暂停的进程

5

32. 简要说明I/O软件的四个层次的基本功能。

从硬件层到用户层分为中断处理程序； 设备驱 动程序；与设备无关的 I/O 软件；用户空间的 I/O 软件等 4 层

33. 设备驱动程序通常要完成哪些工作?

答：设备驱动程序通常要完成如下工作： （1）将抽象要求转换为具体要求； （2）检查 I/O 请求的合法性； （3）读出和检查设备的状 态； （4）传送必要的参数； （5）设置工作方式； （6）启动 I/O 设备。

34. 什么是线程？它与进程有什么关系？ 答：线程是进程中执行运算的最小单位，即处理机调度的基本单位。它与进程的关系是：一个线程只能属于一个进程，而一个进程可以有多个线程；资源分配给进程，同一进程的所有线程共享该进程的所有资源；处理机分给线程，即真正在处理机上运行的是线程；线程在运行过程中，需要协作同步，不同进程的线程间要利用消息通信的办法实现同步。

特别注意的是：传统操作系统中的进程概念与现代操作系统中的进程概念不同——简单说，传统操作系统中进程具有分配资源、调度运行两大功能，而现代操作系统中进程只作为分配资源单位，线程才作为调度运行单位。

35. 假脱机系统向用户提供共享打印机的基本思想是什么

答：（1）系统不是即时执行程序输出的打印操作，而是将数据输入到缓冲区，没真实

打印但给用户系统已经在打印的错觉；

(2) 真正打印操作是在打印机空闲且打印任务在队列队首时进行； (3) 打印操作是利用CPU的一个时间片，没有使用专们的外围机。

36. 文件系统的模型可分为三层，试说明其每一层所包含的基本内容。 答：第一层：对象及其属性说明（文件、目录、硬盘或磁带存储空间）；

第二层：对对象操纵和管理的软件集合（I/O控制层即设备驱动程序、基本文件系统即物理I/O层、基本I/O管理程序或文件组织模块层、逻辑文件系统层）

第三层：文件系统接口（命令接口/图形化用户接口与程序接口）。

37. 为什么在大多数OS中都引入了“打开”这一文件系统调用? 打开的含意是什么? 当用户要求对一个文件实施多次读/写或其它操作时，每次都要从检索目录 开始，浪费时间，低效。为了避免多次重复地检索目录，在大多数OS 中都引入 了“打开”这一文件系统调用。 当用户第一次请求对某文件进行操作时，先利用“打开”系统调用将该文件 打开，磁盘索引结点被拷贝到内存中，后面的目录检索都在内存中进行

。

38. 何谓文件的逻辑结构? 何谓文件的物理结构?

文件的逻辑结构是指从用户的观点出发所观察到的文件组织形式，也就是用户可 以直接处理的数据及其结构，它独立于物理特性,；而文件的物理结构则是指文 件在外存上的存储组织形式，与存储介质的存储性能有关。

39. 目前广泛采用的目录结构形式是哪种? 它有什么优点?

答：现代操作系统都采用多级目录结构。基本特点是查询速度快、层次结构清晰、文件管理和保护易于实现。

6

40. 何谓路径名和当前目录?

文件路径名: 根目录到任何数据文件只有唯一通路，从根目录开始把目录名与数据

文件一次地用“/”连接，构成唯一路径名。

当前目录就是你现在所在的目录!

41. 进程进入临界区的调度原则是什么

①如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入。②任 何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则 其它所有试图进入临界区的进程必须等待。 ③进入临界区的进程要在有限时间内 退出， 以便其它进程能及时进入自己的临界区。④如果进程不能进入自己的临界 区，则应让出 CPU，避免进程出现“忙等”现象。

42. 什么是临界区

43. 什么是进程的同步与互斥？

答：进程的同步与互斥是指进程在推进时的相互制约关系。在多道程序系统中，由于进程合作与资源共享，这种进程间的制约称为可能。我们把前者称为进程同步，后者称为进程互斥。

进程同步是进程间共同完成一项任务时直接发生相互作用的关系。为进程之间的直接制约关系。在多道环境下，这种进程间在执行次序上的协调是必不可少的。同步进程之间的关系如同接力赛跑中的运动员，或生产流水线的每一道工序。

进程互斥是进程之间的间接制约关系。在多道系统中，每次只允许一个进程访问的资源称为临界资源，进程互斥就是保证每次只有一个进程使用临界资源。互斥进程之间的关系如同汽车在交叉路口争用车道，篮球比赛中双方争抢篮板球。

44. 用PV操作实现进程间的同步与互斥应该注意什么？

答：用PV操作实现进程间的同步与互斥，应该注意以下四个方面：

⑴ 对每一个共享资源都要设立信号量。互斥时对一个共享资源设立一个信号量；同步时对一个共享资源可能要设立两个或多个信号量，要视由几个进程来使用该共享变量而定；

⑵ 互斥时信号量的初值一般为1；同步时至少有一个信号量的初值大于等于1；

⑶ PV操作一定要成对调用。互斥时在临界区前后对同一信号量作PV操作；同步时则对不同的信号量作PV操作，PV操作的位置一定要正确。

⑷ 对互斥和同步混合问题，PV操作可能会嵌套，一般同步的PV操作在外，互斥的PV操作在内。

45. 什么是死锁？产生死锁的四个必要条件是什么？

7

46. 简述进程的几种状态和引起状态转换的典型原因，以及相关的操作原语。 答：进程的基本状态有：新、就绪，阻塞，执行、挂起和终止六种。 新到就绪：交换，创建原语， 就绪到执行：进程调度，

执行到阻塞：I/O请求，阻塞原语 阻塞到就绪：I/O完成，唤醒原语 执行到就绪：时间片完 阻塞到挂起：挂起原语 挂起到就绪：唤醒原语 执行到终止：进程执行完毕

47. 什么是请求页式管理？能满足用户哪些需要？ 答：请求页式管理的基本原理是将逻辑地址空间分成大小相同的页，将存储地址空间分块，页和块的大小相等，通过页表进行管理。页式系统的逻辑地址分为页号和页内位移量。页表包括页号和块号数据项，它们一一对应。根据逻辑空间的页号，查找页表对应项找到对应的块号，块号乘以块长，加上位移量就形成存储空间的物理地址。每个作业的逻辑地址空间是连续的，重定位到内存空间后就不一定连续了。此外，页表中还包括特征位（指示该页面是否在内存中）、外存地址、修改位（该页的内容在内存中是否修改过）等。页式存储管理在动态地址转换过程中需要确定某一页是否已经调入主存。若调入主存，则可直接将虚拟地址转换为实地址，如果该页未调入主存，则产生缺页中断，以装入所需的页。

页式存储管理将不常用的页面调出内存，使内存的利用率高；虚拟的容量大，用户不必担心内存不够；不要求作业连续存放，有效地解决了“碎片”问题。

48. 进程调度中可抢占和非抢占两种方式，哪一种系统的开销更大？为什么？ （1）可抢占式会引起系统的开销更大。

（2）可抢占式调度是严格保证任何时刻，让具有最高优先数（权）的进程占有处理机运行，因此增加了处理机调度的时机，引起为退出处理机的进程保留现场，为占有处理机的进程恢

复现场等时间开销增大。

49. 一个含五个逻辑记录的文件，系统把它以链接结构的形式组织在磁盘上，每个记录占用一个磁盘块，现要求在第一记录和第二记录之间插入一个新记录，简述它的操作过程。

从文件目录中找到该文件，按址读出第一个记录；取出第一个记录块中指针，存放到新记录的指针位置；把新记录占用的物理块号填入第一个记录的指针位置启动磁盘把第一个记录和新记录写到指字的磁盘块上。

8

50. 试比较进程调度与作业调度的不同点

（1）作业调度是宏观调度，它决定了哪一个作业能进入主存。进程调度是微观调度，它决定各作业中的哪一个进程占有中央处理机（或）作业调度是高级调度，它位于操作系统的作业管理层次。进程调度是低级调度，它位于操作系统分层结构的最内层。

（2）作业调度是选符合条件的收容态作业装入内存。进程调度是从就绪态进程中选一个占用处理机。

三、应用题

1. 在一个采用页式虚拟存储管理的系统中，有一用户作业，它依次要访问的字

地址序列是：115，228，120，88，446，102，321，432，260，167，若该作业的第 0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字，请回答下列问题： （1）按FIFO调度算法将产生次缺页中断，依次淘汰的页号为，缺页中断率为。 按FIFO调度算法将产生5次缺页中断；依次淘汰的页号为：0，1，2；缺页中断率为：5/10=50% （2）按LRU调度算法将产生次缺页中断，依次淘汰的页号为，缺页中断率为。

按LRU调度算法将产生6次缺页中断；依次淘汰的页号为：2，0，1，3； 缺页中断率为：6/10=60%

2. 设系统有三种类型的资源，数量为(4，2，2)，系统中有进程A，B，C按如下顺序请求资源：

进程A申请(3，2，1) 进程B申请(1，0，1) 进程A申请(0，1，0) 进程C申请(2，0，0)

请你给出一和防止死锁的资源剥夺分配策略，完成上述请求序列，并列出资源分配过程，指明哪些进程需要等待，哪些资源被剥夺。

3. 假设一个可移动磁头的磁盘具有200个磁道，其编号为0~199，当前它刚刚结束了125道的存取，正在处理149道的服务请求，假设系统当前磁盘请求序列为：88, 147, 95, 177, 94, 150, 102, 175, 138。试问对以下的磁盘调度算法而言，满足以上请求序列，磁头将如何移动？并计算总的磁道移动数。 （1）先来先服务策略

（2）最短寻道时间优先策略 （3）扫描策略

9

4. 已知某程序访问以下页面：0、1、4、2、0、2、6、5、1、2、3、2、1、2、6、2、1、3、6、2，如果程序有3个页框可用且使用下列替换算法，求出现缺页的次数。（1）FIFO替换算法（2）LRU替换算法

四、程序与算法题

1. 假定系统有三个并发进程read, move和print共享缓冲器B1和B2.进程read负责从输入

10

设备上读信息,每读出一个记录后把它存放到缓冲器B1中.进程move从缓冲器B1中取出一记录,加工后存入缓冲器B2.进程print将B2中的记录取出打印输出.缓冲器B1和B2每次只能存放一个记录.要求三个进程协调完成任务,使打印出来的与读入的记录的个数,次序完全一样. 请用PV操作,写出它们的并发程序.

2．系统运行有三个进程：输入进程、计算进程和打印进程，它们协同完成工作。输入进程和计算进程之间共用缓冲区buffer1,计算进程和打印进程之间共用缓冲区buffer2。

输入进程接收外部数据放入buffer1中；计算进程从buffer1中取出数据进行计算，然后将结果放入buffer2；打印进程从buffer2取出数据打印输出。

用算法描述这三个进程的工作情况，并用wait和signal原语实现其同步操作。

11

12

3. 请用信号量描述哲学家进餐问题。

4. 用信号量和P，V操作描述读者-写者问题：即允许多个读者同时读一个共享对象，但绝不允许一个写者和其它进程同时访问共享对象。

13

14

5. 设有一缓冲池P，P中含有20个可用缓冲区，一个输入进程将外部数据读入P，另有一个输出进程将P中数据取出并输出。若讲程每次操作均以一个缓冲区为单位，试用记录型信号量写出两个进程的同步算法,要求写出信号量的初值。

6. 下面是两个并发执行的进程，它们能正确运行吗？若不能请举例说明，并改正。 int x;

process_P1{ process_P2{ int y,z; int t,u; x=1; x=0; y=0; t=0; if(x>=1) if(x<=1) y=y+1; t=t+2; z=y; u=t; } } 解答：

P1和P2两个并发进程的执行结果是不确定的，它们都对同一变量X进程操作，X是一个临界资源，而没有进行保护。例如：

若先执行完P1再执行P2，结果是x=0,y=1,z=1,t=2,u=2.

若先执行P1到x=1，然后一个中断去执行完P2，再一个中断回来执行完P1，结果是x=0,y=0,z=0,t=2,u=2。

15

显然两次执行结果不同，所以这两个并发过程不能正确运行。可以将程序改为： int x;

semaphore S=1;

process_P1{ process_P2{ int y,z; int t,u; P(S) P(S); x=1; x=0; y=0; t=0; if(x>=1) if(x<=1) y=y+1; t=t+2; V(S); V(S); z=y; u=t; } }

7. 假定一个阅览室可供50个人同时阅读。读者进入和离开阅览室时都必须在阅览室入口处的一个登记表上登记，阅览室有50个座位，规定每次只允许一个人登记或注销登记。要求： （1）用PV操作描述读者进程的实现算法（可用流程图表示，登记、注销可用自然语言描述）；

（2）指出算法中所用信号量的名称、作用及初值。

五、综合应用题

1. 某银行提供1个服务窗口和20个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下： cobegin

16

{

process 顾客i {

从取号机获取一个号码； 等待叫号； 获取服务； }

process 营业员 {

while (TRUE) {

叫号；

为客户服务； } } }coend

请添加必要的信号量和P、V（或wait()、signal()）操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。 答：

Semaphore seats = 10; //表示空余座位数量的资源信号量，初值为10

Semaphore mutex = 1; //管理取号机的互斥信号量，初值为1，表示取号机空闲。 Semaphore custom = 0; //表示顾客数量的资源信号量，初值为0 Process 顾客

{ P(seats); //先找个空座位

P(mutex); //再看看取号机是否空闲 从取号机上取号； V(mutex); //放开取号机

V(custom); //取到号，告诉营业员有顾客 等待叫号； V(seats); //顾客被叫号，离开座位 接受服务； }

Process 营业员 { While(true) { P(custom); //看看有没有等待的顾客 叫号； 为顾客服务； } }

17

本文来源：https://www.bwwdw.com/article/tpqp.html