《操作系统》期末总复习

一. 选择题

1. (单选题)操作系统的基本功能是( )。

A. 提供功能强大的网络管理工具

B. 提供用户界面，方便用户使用

C. 提供方便的可视化编辑程序

D. 控制和管理系统的各种资源，有效地组织多道程序的运行

2. (单选题)从用户的观点看，操作系统是( )。

A. 用户与计算机之间的接口

B. 控制和管理计算机资源的软件

C. 合理地组织计算机工作流程的软件

D. 由若干层次的程序按一定的结构组成的有机体

3. (单选题)同一个进程的所有线程不会共享( )。

A. 代码

B. 文件

C. 栈

D. 优先级

4. (单选题)在操作系统中，一般不实现进程从( )状态的转换。

A. 就绪→等待

B. 运行→就绪

C. 就绪→运行

D. 等待→就绪

5. (单选题)在下列同步机制中，可以实现让权等待的是( )。

A. Peterson 方法

B. swap 指令

C. 信号量方法

D. TestAndSet 指令

6. (单选题)下列关于线程的描述中，错误的是( )。

A. 内核级线程的调度由操作系统完成

B. 操作系统为每个用户级线程建立一个线程控制块

C. 用户级线程间的切换比内核级线程间的切换效率高

D. 用户级线程可以在不支持内核级线程的操作系统上实现

7. (单选题)下列关于死锁的叙述中，正确的是( )。

I、可以通过剥夺进程资源解除死锁
II、死锁的预防方法能确保系统不发生死锁
III、银行家算法可以判断系统是否处于死锁状态
IV、当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态

A. 仅II、III

B. 仅I、II、IV

C. 仅I、II、III

D. 仅I、III、IV

8. (单选题)在可变分区存储管理方案中需要一对界限地址寄存器，其中( )作为地址映射使用。

A. 逻辑地址寄存器

B. 长度寄存器

C. 物理地址寄存器

D. 基址寄存器

9. (单选题)下列措施中，能加快虚实地址转换的是( )

I、增大快表的容量
II、让页表常驻内存
III、增大交换区

A. 仅I

B. 仅II

C. 仅II、III

D. 仅I、II

10. (单选题)在请求分页系统中有多种页面置换算法，选择最先进入内存的页面予以淘汰的算法称为( )。

A. FIFO置换算法

B. OPT置换算法

C. LRU置换算法

D. NRU置换算法

11. (单选题)下列选项中，操作系统提供给应用程序的接口是( )。

A. 系统调用

B. 中断

C. 库函数

D. 原语

12. (单选题)下列选项中，在用户态执行的是( )。

A. 命令解释程序

B. 缺页处理程序

C. 进程调度程序

D. 时钟中断处理程序

13. (单选题)进程与程序的主要区别是( )。

A. 进程是静态的，而程序是动态的

B. 进程不能并发执行而程序能并发执行

C. 程序异步执行，会相互制约，而进程不具备此特征

D. 进程是动态的，而程序是静态的

14. (单选题)进程和线程是两个既相关又有区别的概念，下面描述中，不正确的是( )。

A. 线程是申请资源和调度的独立单位

B. 每个进程有自己的虚存空间，同一进程中的各线程共享该进程虚存空间

C. 进程中所有线程共享进程的代码段

D. 不同的线程可以对应相同的程序

15. (单选题)要实现两个进程互斥，设一个互斥信号量mutex，当mutex为0时，表示( )。

A. 没有进程进入临界区

B. 有一个进程进入临界区

C. 有一个进程进入临界区，另外一个进程在等候

D. 两个进程都进入临界区

16. (单选题)下面有关选择进程调度算法的准则，错误的是( )。

A. 尽量提高处理器利用率

B. 尽可能提高系统吞吐量

C. 适当增长进程在就绪队列中的等待时间

D. 尽快响应交互式用户的要求

17. (单选题)若系统S1采用死锁避免方法，S2采用死锁检测方法，下列叙述中正确的是( )。

I、S1会限制用户申请资源的顺序
II、S1需要进行所需资源总量信息，而S2不需要
III、S1不会给可能导致死锁的进程分配资源，S2会

A. 仅I、II

B. 仅I、III

C. 仅II、III

D. 仅I、II、III

18. (单选题)在分段存储管理系统中，用共享段表描述所有被共享的段。若进程P1和P2共享段S，下列叙述中，错误的是( )。

A. 在物理内存中仅保存一份段S的内容。

B. 段S在进程P1和P2中应该具有相同的段号。

C. 进程P1和P2共享段S在共享段表中的段表项。

D. 进程P1和P2都不再使用段S时才回收段S所占的内存空间

19. (单选题)下列关于虚拟存储器的叙述中，正确的是( )。

A. 虚拟存储只能基于连续分配技术。

B. 虚拟存储只能基于非连续分配技术。

C. 虚拟存储容量只受外存容量的限制。

D. 虚拟存储容量只受内存容量的限制。

20. (单选题)在请求分页系统中有多种页面置换算法，选择以后不再使用的页面予以淘汰的算法称为( )。

A. FIFO置换算法

B. OPT置换算法

C. LRU置换算法

D. NRU置换算法

二. 填空题

本小题共有10个空，1空1分，总分在10分。此题是拉开差距的一道，范围在全书

三. 简答题

1.进程的特征是什么？

答：①动态性；②并发性；③独立性；④异步性；⑤结构性。

2.简述程序、进程、线程、作业的关系和区别。

答：关系：程序是静态的代码，进程是程序的动态执行实例，线程是进程的执行单元，而作业是对执行任务的一种高级抽象。一个程序可以启动多个进程，一个进程可以包含多个线程，而作业则可以包含一个或多个进程。

区别：程序是静态的，进程是动态的；进程是资源分配的单位，线程是调度的单位；作业是一个更高层次的概念，通常涉及多个进程和用户交互。

3.进程控制块的作用是什么？其主要内容有什么？

答：作用：进程控制块记录了进程情况和控制进程运行的全部信息，操作系统控制了进程控制块，就掌握了进程的全部信息。进程控制块在进程创建、调度、切换和终止等操作中起着至关重要的作用。

主要内容：进程控制块包含四类信息：标识信息、说明信息、现场信息、控制信息。

4.什么是临界资源？什么是临界区？

答：临界资源是指在多进程或多线程环境中共享的有限资源，这些资源在同一时间只能被一个进程或线程使用。临界区是指进程内访问临界资源的代码段。

5.什么是管程？它有哪些特性？

答：管程是一种特殊的程序设计结构，任何一个时刻，管程只能由一个进程使用。特性：①模块化；②抽象数据类型；③信息隐藏；④使用的互斥性。

6.试述进程进入临界区，解决互斥问题应遵守的原则。

答：①空闲让进；②互斥使用；③忙则等待；④有限等待；⑤让权等待。

7.什么叫进程通信？进程通信的作用是什么？

答：各并发进程在执行过程中经常要交换一些信息，通过专门的通信机制实现进程间交换大量信息的通信方式称为“进程通信”。作用：①数据共享；②协作处理；③资源管理；④任务分解与负载均衡；⑤事件通知；⑥同步控制。

8.什么是死锁？

答：若系统中只存在两个资源，资源A和资源B，此时有两个进程分别为P1和P2，进程P1占有资源A并未释放又申请资源B，而此时资源B正在被进程P2占用，进程P2未释放资源B又申请资源A，则两个进程会互相无休止的等待下去，此时P1、P2陷入死锁态。

9.死锁产生的原因是什么？

答：①资源的竞争；②请求和释放资源的顺序不当。

10.产生死锁的必要条件是什么？

答：①互斥条件；②请求和保持条件；③不可剥夺条件；④循环等待条件。

11.死锁的处理方法。

答：①忽略死锁；②预防或避免死锁；③检测和解除死锁。

12.页式存储与段式存储的区别。

答：①页是信息的物理单位，分页是为了实现离散分配方式，以减少内存碎片，提高内存的利用率；段是信息的逻辑单位，是一组具有完整意义的信息段。②页的大小是固定的，由系统决定；而段的长度却不固定，由用户所编写的程序决定。③分页系统中进程的地址空间是唯一的，页间的逻辑地址是连续的；而段式系统中段的地址空间是二维的，段的分类是一维的，段内位移是二维的，段间的逻辑地址是不连续的。④段式存储方便共享段的使用，而页式存储不方便共享。⑤页式存储会产生少量的内部碎片，段式存储会产生外部碎片。

13.存储管理的主要功能。

答：①地址转换；②存储分配与去配；③存储共享；④存储保护；⑤存储扩充。

14.什么叫重定位？

答：通常，把在装入模块的逻辑地址变换为内存的物理地址的过程，称为重定位。

15.重定位的几种类型。

答：静态重定位和动态重定位。

16.采用内存分区管理时，如何实现程序运行时的动态重定位？

答：动态运行时的装入程序在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。这种延迟转换通过硬件基址寄存器（或MMU）实时完成，操作系统仅需在程序调入内存时设置正确的基址值。

17.试述设备管理的基本功能。

答：①外围设备的分配和去配；②外围设备的启动；③磁盘的驱动调度；④设备处理；⑤虚拟设备管理。

18.试说明各种I/O控制方式及其主要优缺点。

答：I/O设备的控制方式分为4类：直接程序控制方式、中断驱动控制方式、直接存储器访问（DMA）控制方式和通道控制方式。

直接程序控制方式优点：实现简单，无需额外硬件支持；适用于低速、简单的I/O设备。缺点：CPU利用率低；实时性差；不适合高速设备。

中断驱动控制方式优点：提高CPU利用率；实时性较好。缺点：中断处理开销大；不适合高速设备。

DMA控制方式优点：大幅减少CPU负担；适合高速设备（如磁盘、网卡）。缺点：硬件成本较高；总线竞争。

通道控制方式优点：CPU完全解放；支持多设备并行；适用于高性能计算。缺点：硬件成本高；系统复杂度高。

19.试说明DMA的工作流程（要求掌握流程图及基本描述性文字）。

答：在DMA控制器的控制下，采用窃取或挪用总线控制权，占用CPU的一个工作周期把数据缓冲器中的数据直接送到主存地址寄存器所指向的主存区域中，在设备和主存之间开辟直接数据交换通道，成批地交换数据，而不必受CPU的干预。DMA方式的工作流程如下图所示。

20.简述采用通道技术时，I/O操作的全过程。

答：①当进程要求设备输入数据时，CPU发出启动指令，并指明要进行的I/O操作、使用的设备的设备号和对应的通道。

②通道接收到CPU发来的启动指令后，把存放在内存的通道处理程序取出，开始执行通道指令。

③执行一条通道指令，设置对应设备控制器中的控制/状态寄存器。

④设备根据通道指令的要求把数据送往内存指定区域。如果本指令不是通道处理程序的最后一条指令，取下一条通道指令，并转③继续执行；否则执行⑤。

⑤通道处理程序执行结束，通道向CPU发出中断信号请求CPU做中断处理。

⑥CPU接到中断处理信号后进行善后处理，然后返回被中断处继续执行。

四. 计算综合题

1.有A、B两个程序，程序A按如下顺序使用系统中资源，CPU 10 s、使用设备甲 5 s、使用CPU 5 s、使用设备乙 10 s、最后使用CPU 10 s；程序B按如下使用顺序使用系统中资源，设备甲 10 s、使用CPU 10 s、使用设备乙 10 s、使用CPU 5 s、使用设备乙 10 s。试问：

（1）在单道批处理环境下执行程序A和程序B，CPU利用率是多少？

（2）在多道批处理环境下，CPU的利用率是多少？请画出A、B程序的执行过程。

（3）在多道批处理中，系统中并发的进程越多，资源利用率越好吗？

结论：（1）在单道批处理环境下CPU利用率=A程序和B程序使用CPU时间/两个程序顺序执行完成的时间总和，即：

\color{red}{ \begin{aligned} CPU的利用率 & =\frac{(10+5+10)+(10+5)}{(10+5+5+10+10)+(10+10+10+5+10)}\times 100 \%\\ & =47.1 \% \end{aligned} }

（2）在多道环境下，A、B程序执行过程如下图所示。

ddp.drawio-pwop.svg

根据题图4-1可以看出，在多道批处理环境下，CPU的利用率=40/50×100%=80%.

（3）不是，因为在系统实际运行中并发执行的程序是交替使用系统资源的，而在发生运行程序与运行程序的切换时需要操作系统管理，这样就会产生系统开销，若程序间切换次数较多，反而会造成系统性能的下降。

2.假设有以下程序段：

S₁:a=x-3
S₂:b=3*a
S₃:c=5+a

（1）Bernstein条件是什么？

（2）试画出前驱图表示它们执行时的先后次序。

（3）利用Bernstein条件证明S₁、S₂和S₃中哪两个可以并发执行，哪两个不能并发执行。

答：（1）Bernstein条件：当且仅当满足以下条件，两个程序S₁、S₂并发执行：

\begin{aligned} R(S_1)\cap W(S_2) \cup R(S_2) \cap W(S_1) \cup W(S_1) \cap W(S_2)=\{ \} \end{aligned}

（2）前驱图表示：

qqt.drawio-csjg.svg

（3）R(S₁)={x}，W(S₁)={a}；R(S₂)={a}，W(S₂)={b}；R(S₃)={a}，W(S₃)={c}；

①.R(S_1)∩W(S_2)∪R(S_2)∩W(S_1)∪W(S_1)∩W(S_2)=\{a\}，则S₁与S₂不能并发执行；

②.R(S_1)∩W(S_3)∪R(S_3)∩W(S_1)∪W(S_1)∩W(S_3)=\{a\}，则S₁与S₃不能并发执行;

③.R(S_2)∩W(S_3)∪R(S_3)∩W(S_2)∪W(S_2)∩W(S_3)=\{ \ \ \}，则S₂与S₃能够并发执行。

3.如表4-3所示，设有A、B、C、D、E五个进程，其到达时间分别为0、1、2、3、4，要求运行时间以此为3、6、4、5、2，采用最高响应比优先调度算法，试计算其平均周转时间和平均带权周转时间。

进程	提交时间	运行时间	开始时间	完成时间	周转时间（T_完-T_到）	带权周转时间（T_周/T_运行）
A	0	3	0	3	3	1
B	1	6	3	9	8	1.33
C	2	4	11	15	13	3.25
D	3	5	15	20	17	3.4
E	4	2	9	11	7	3.5

解：用R表示响应比，则不同时刻的运行过程为：

0':A运行，BCD依次到达；

3':R_B=1+WT/BT=1+2/6≈1.3，R_C=1+WT/BT=1+1/4=1.25，R_D=1+WT/BT=1；B先运行。

9':R_C=1+WT/BT=1+7/4=2.75，R_D=1+WT/BT=1+6/5=2.2，R_E=1+WT/BT=1+5/2=3.5；E先运行。

11':R_C=1+WT/BT=1+9/4=3.25，R_D=1+WT/BT=1+8/5=2.6；C先运行。

由此可知作业的运行顺序为A、B、E、C、D。

平均周转时间T=(3+8+13+17+7)/5=9.6

平均带权周转时间W=(1+1.33+3.25+3.4+3.5)/5=2.496

4.设有一组进程，它们需要占用CPU的事件及优先级如表4-4所示。

进程	需要占用CPU的时间	优先级
P₁	10	3
P₂	1	1
P₃	2	3
P₄	1	4
P₅	5	2

假设各进程在时刻0按P₁、P₂、P₃、P₄和P₅的顺序到达。

（1）画出分别采用调度算法先来先服务（FCFS）、短进程优先（SPF）、非抢占式优先级（NPP，数值小的优先级大）及时间片轮转（RR，时间片为1）时的调度顺序甘特（Gantt）图。

（2）计算各种调度算法下每个进程的周转时间和平均周转时间。

（3）计算各种调度算法下每个进程的等待时间和平均等待时间。

（4）哪个调度算法可以获得最小的平均等待时间？

答：此为参考答案，小题(2)SJP的平均周转时间有误，正确应为7，请注意甄别。

5.假设系统中有5个进程P₀、P₁、P₂、P₃、P₄，有3类资源{A、B、C}，A资源的数量为7，B资源的数量为3，C资源的数量为6。在T₀时刻，资源分配与申请情况如下表4-5所示。

ssjc.drawio (1).svg

试问：（1）在T₀时刻，用死锁检测算法判断系统是否死锁。

（2）假定现在进程P2发出请求Request₁（0,0,1），此时系统是否发生死锁？

解答：（1）根据死锁检测算法可以得到一个安全序列<P0、P2、P3、P1、P4>，所以系统在T₀时刻不会发生死锁。

aqxljcb.drawio.svg

（2）假定现在进程P2发出请求Request₁（0,0,1），资源分配与申请情况发生变换，如表所示。

p2fcqq.drawio.svg

此时Available只能分配给进程P₀，回收资源，Work=Work+Allocation₀=(0,2,0)，所以系统处于死锁状态，参与死锁的进程构成的集合为<P1、P2、P3、P4>。

解答：

7.假定存在如下页面访问序列：5，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，4，5，0，1，内存为该进程分配 3 个物理块，采用最近最久未使用页面置换算法（LRU），写出页面置换过程，缺页次数是多少？缺页率是多少？

答：根据算法原理，最近最久未使用页面置换算法置换过程如下图：

zjzj.drawio.svg

一共发生缺页中断12次，缺页率为12/20=60%。

8.在某请求分页管理系统中，一个进程共5页，进程执行时依次访问如下页面：1，4，3，1，2，5，1，4，2，1，4，5，若分配给该进程的物理块为3，分别采用FIFO、LRU、简单的CLOCK页面置换算法，试求出缺页中断的次数及缺页率。

答：

五. 程序综合题

1.读者-写者问题（公平情况算法）：一个文件可以被读和被写，多个进程操作这一个共享对象。因为读操作不会引起文件混乱，所以可以同时有多个进程被读。写操作会引起文件混乱，所以写操作不允许和其他读操作或者写操作同时访问对象。

semaphore mutex = 1; //初始化mutex,用于控制互斥访问数据区
semaphore rmutex = 1; //初始化rmutex,用于读者互斥访问readcount
semaphore wmutex = 1; //初始化wmutex,用于存在写者时禁止新读者进入
int readcount = 0; //用于记录读者数量，初值为0
void reader(){
  while(true){
    wait(wmutex);
    wait(rmutex);
    if(readcount == 0)
      wait(mutex);
    readcount ++ ;
    signal(rmutex);
    signal(wmutex);
    进行读操作
    wait(rmutex);
    readcount -- ;
    if(readcount == 0)
      signal(mutex);
    signal(rmutex);
  }
}
void writer(){
  while(true){
    wait(wmutex);
    wait(mutex);
    进行写操作
    signal(mutex);
    signal(wmutex);
  }
}
void main(){
  cobegin
    reader();
    writer();
  coend;
}

2.生产者-消费者问题：系统中有两个进程，一个进程用于生产资源，一个进程用于消费资源。这两个进程共享一块大小确定的存放资源的区域（缓冲池）。当区域内的资源没有装满时，生产进程可以往里面放资源；当区域内的资源装满时，生产进程需等待；当区域内的资源不为空时，消费进程可以从里面取出资源；当区域内的资源为空时，消费进程需等待。

semaphore mutex = 1; //对有界缓冲区进行操作的互斥信号量
semaphore empty = n; //空缓冲区数目
semaphore full = 0; //满缓冲区数目
void producer(){
  while(true){
    prodece an item put in nextp; //nextp为临时缓冲区
      wait(empty); //申请一个空缓冲区
      wait(mutex); //申请使用缓冲池
      将产品放入缓冲池
      signal(mutex); //缓冲池使用完毕，释放互斥信号量
      signal(full); //增加一个满缓冲区
  }
}
void consumer(){
  while(true){
    wait(full); //申请一个满缓冲区
    wait(mutex); //申请使用缓冲池
    取出产品
    signal(mutex); //缓冲池使用完毕，释放互斥信号量
    signal(empty); //增加一个空缓冲区
    consumer the item in nextc; //消耗掉产品
  }
}
void main(){
  cobegin
    producer();
    consumer();
  coend;
}

3.（考研真题）某寺庙有小和尚和老和尚若干，有一个水缸，由小和尚提水入缸供老和尚饮用。水缸可以容纳10桶水，水取自同一口井中，由于水井口窄，每次只能容纳一个水桶取水。水桶总数为3个（老和尚和小和尚共同使用）。每次入水、取水仅为一桶，且不可同时进行。试给出有关取水、入水的算法描述。

答：本题需要设置5个信号量：

semaphore empty = 10;
semaphore full = 0;
semaphore buckets = 3;
semaphore mutex_well = 1;
semaphore mutex_bigjar = 1;
yong_monk(){
  While(true){
    P(empty);
      P(buckets);
      去井边；
      P(mutex_well);
      取水；
      V(mutex_well);
      回寺庙；
      P(mutex_bigjar);
      pure the water into the big jar;
      V(mutex_bigjar);
      V(buckets);
      V(full);
  }
}
old_monk(){
  While(true){
    P(full);
      P(buckets);
    P(mutex_bigjar);
      取水；
    V(mutex_bigjar);
      喝水；
        V(buckets);
      V(enpty);
  }
}

4.（考研真题）桌上有一空盘，允许存放一个水果。爸爸可向盘中放苹果，也可向盘中放橘子，儿子专等吃盘中的橘子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一个水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿3个并发进程的同步。

答：在本题中，应设置3个信号量S、So、Sa。

Semaphore S = 1;
Semaphore Sa = 0;
Semaphore So = 0;
  Procedure father{
    While(true){
      P(S);
        将水果放入盘中;
      if(放入的是橘子)
        V(So);
      else
        V(Sa);
    }
  }
Procedure son{
  While(true){
    P(So);
      从盘中取出橘子;
    V(S);
      吃橘子;
  }
}
Procedure daughter{
  While(true){
    P(Sa);
      从盘中取出苹果;
    V(S);
      吃苹果;
  }
}

5.（考研真题）有桥如图5-5所示。车流如箭头所示。桥上不允许有两车交汇，但允许同方向车依次通行（即桥上可以有多个同方向的车）。用 P、V 操作实现交通管理以防桥上堵塞。

答：由南往北过桥的车辆描述如下：

行驶到桥头;
P(SA);
If(countA == 0)
  P(mutex);
countA ++ ;
V(SA);
  过桥;
P(SA);

由北往南过桥的车辆描述如下：

行驶到桥头;
P(SB);
If(countB == 0)
  P(mutex);
countB ++ ;
V(SB);
  过桥;
P(SB);
countB -- ;
If(countB == 0)
  V(mutex);
V(SB);