2016-2017学年上学期月考

2016-2017学年上学期月考试卷（含答案）

说明

• 日期：2016.10
• 原卷标题：华东师范大学软件学院月考试卷（2016—2017学年第一学期）

一、判断题（15 分，每小题 3 分）

判断下列每句话是否正确，如错误请说明理由。

1. 线程都保存有各自的栈信息、CPU 状态（寄存器、指令计数器等）、堆信息，以及打开文件列表等。

   答案：

   错。线程保存栈信息、CPU 状态；而堆信息，以及打开文件列表等是进程保存的。

   （线程实现了资源和调度单位相分离）

   ---

2. 向操作系统传递参数只能通过寄存器实现。

   答案：

   错。还可以通过堆栈传递等

   ---

3. 在微内核结构的操作系统中，进程间通讯可以不在微内核内。

   答案：

   错。进程通讯是内核的核心功能，对微内核系统，也在微内核内实现。

   ---

4. 对于内核支持的线程，当该线程执行系统调用被阻塞时，不仅该线程被阻塞，而且同一进程内的所有线程都会被阻塞。

   答案：

   错。只有当前进程被阻塞，其它进程可以继续执行。

   ---

5. 当前运行进程发生缺页中断，进程将进入 Ready 队列

   答案：

   错。进入 waiting 队列。

---

二、不定项选择题（15 分，每小题 3 分）

每题有一个或多个答案，答错、少选、多选均不给分。

1. 以下哪些（个）操作会使得一个进程从运行（running）状态转换为就绪（ready）状态（ ）

   A. 在可占先（preemptive）系统中，高优先级进程被创建

   B. 分时系统中，时间片到

   C. 当前运行进程发生缺页中断

   D. 当前运行进程调用 yield( )，主动放弃使用 CPU

   答案：

   ABD

   ---

2. 当从“新建（new）”状态进入“就绪（ready）”状态的进程增多时，下面哪种情况不会发生（ ）

   A. I/O 操作的频度升高；

   B. CPU 利用率下降

   C. CPU 利用率上升

   D. 进程的平均响应时间减少

   答案：

   D

   ---

3. 以下描述正确的是（ ）

   A. 中断处理程序（interrupt handler）是进程的一部分，在进程的地址空间运行

   B. 中断处理程序（interrupt handler）必须运行在内核态

   C. 微内核体系结构下，进程间通讯（inter-processing communication）必须在微内核内

   D. 分时（time sharing）的目的是提高 CPU 和 I/O 的并行度

   答案：

   BC

   ---

4. 以下哪些（个）对于微内核操作系统的描述是正确的？（ ）

   A. Microsoft Windows 是微内核操作系统，但 Linux 不是；

   B. 进程间通信必须在微内核内实现；

   C. 因为用户进程不应访问页表，因此虚存应该在微内核内实现；

   D. 操作系统设计时采用微内核结构可以提高操作系统执行的效率。

   答案：

   B

   宏内核（模块化内核）结构的例子：传统的 UNIX 内核，BSD 伯克利大学发行的版本；Linux 内核；MS-DOS，Windows 9x（Windows 95，98，Me）；

   混合内核：Windows NT、Windows 2000、Windows XP、Windows Server 2003 以及 Windows Vista 和 Windows 7 等基于 NT 技术的微软视窗操作系统。

   ---

5. 以下对于线程的描述哪些（个）是错误的（ ）

   A. 一个用户态线程的阻塞（block）会引起它所属的整个进程（包括其中的其它线程）的阻塞；

   B. 同一个进程的不同线程可以共享地址空间中的堆；

   C. 线程间通信必须通过内核态系统调用进行；

   D. 同一个进程的不同线程必须维护各自的调用栈和 CPU 状态。

   答案：

   C

---

三、辨析题（30 分，每小题 6 分）

分别解释以下每组的两个名词，并列举他们的区别。

1. 分时（time-sharing）与多道程序（multi-programming）

   答案：

   分时：将时间划分成时间片，进程按时间片轮流执行

   多道：系统中存在多个程序同时执行

   区别：分时主要针对提高系统的响应速度，改善用户体验；多道主要针对增加系统的利用率。

   ---

2. 长程调度（long-term scheduling）与中程调度（mid-term scheduling）

   答案：

   长程调度：操作系统决定到底有多少进程能够从“new”状态进入就绪状态的调度

   中程调度：操作系统决定哪些进程的地址空间能够保留在内存中，哪些进程的地址空间需要被交换到外存的调度

   区别：长程调度被用于平衡系统资源利用率与并发进程个数；中程调度被用于控制运行与就绪进程有足够的内存、较低的缺页率能够运行。

   ---

3. 网络操作系统和分布式操作系统

   答案：

   网络操作系统：支持网络的操作系统

   分布式操作系统：可管理分布式系统的操作系统

   区别：采用分布式操作系统，分布的计算机对于用户是透明的。

   ---

4. 微内核和模块化内核

   答案：

   微内核：操作系统内核只包含最基本的功能（进程调度和进程间通讯）

   模块化内核：操作系统内核的一些功能可以作为模块挂载

   区别：微内核中内核和其它操作系统的功能模块（如虚存管理）在不同的地址空间运行，模块化内核中它们在一个地址空间。

   ---

5. 核心态和用户态

   答案：

   核心态：操作系统内核执行的受保护的状态

   用户态：用户进程执行所在的状态

   区别：处于用户态只能访问进程的地址空间，用户态需要通过中断或系统调用才能进入核心态。

---

四、综合题（40 分）

1. 请简要说明你对以下图的理解。（5 分）

   

   答案：

   操作系统工作过程是被中断驱动的，An operating system is interrupt driven。

   CPU 在用户程序处理过程中，遇到中断请求后，要进行中断处理。

   进程从用户程序执行状态转换到中断处理状态之间要进行上下文的保护。因此在 Transfer done 以后，CPU 保护上下文的信息后对中断进行响应。

   I/O 设备和 CPU 并行工作。在 I/O 请求后，设备进行数据 Transfer 时，CPU 在同时工作。

   ---

2. 调度队列有哪几种？请简单说明（5 分）

   答案：

   Ready 队列。已经调入内存在 Ready 状态等待执行的进程队列。

   I/O 队列。在特定的 I/O 设备资源上等待资源的出现的队列。每个 I/O 设备都有一个相应的队列。

   job 队列。Job queue -- set of all processes in the system

   ---

3. 进程创建时（如在类 UNIX 操作系统中，连续执行 fork() 和 exec() 系统调用），操作系统所需要进行那些工作，它们的代价如何（大，中，小）。为什么线程创建比进程快，它主要节省了以上哪个步骤的代价？（10 分）

   答案：

   a. 构造 PCB，代价小

   b. 设置地址空间映射，代价中

   c. 复制父进程地址空间内容，代价大

   d. 复制 I/O 状态，代价中

   （2）为什么线程创建比进程快，它主要节省了以上哪个步骤的代价？（4 分）

   答：同一进程的不同线程共享资源，因此以上 b, c, d 三项代价几乎都可节省

   ---

4. 请详细描述一个用户态线程调用 sleep() 系统调用后，操作系统所执行的任务。（8 分）

   答案：

   1. 系统调用过程：mode-switch, 查表（syscall handling）, 执行系统调用代码。

   2. sleep() 将当前进程放入 waiting 队列（设置 alarm）

   3. CPU 调度（context switch）

   4. 系统调用结束，返回，mode-switch

   ---

5. 请给出以下图中操作系统进程状态的概念和状态之间转换的一个例子（12 分）。

   

   答案：

   参考答案：（进程状态的概念略）

   (1): new-->ready：从 shell 启动程序或者 fork 进程

   (2): running->ready：高优先级程序运行，时间片到，...

   (3): ready-->running：时间片到，前一进程结束／等待...

   (4): running-->terminated：exit

   (5): running-->waiting：等待 i/o、信号量 P 操作...

   (6): waiting-->ready：i/o 结束、获得信号量，...

   (7): waiting-->suspended：虚存时，内存不够

   (8): suspended-->ready：得到 i/o 结束、获得信号量，...

---

2016-2017学年上学期月考试卷（三）（含答案）

说明

• 日期：2016.12
• 原卷标题：华东师范大学软件学院月考试卷（三）（2014—2015学年第二学期），但卷内老师的批注为16年11月，因此标题为误标

一、判断题（15 分，每小题 3 分）

判断下列每句话是否正确，如错误请说明理由。

1. 发生缺页中断的进程将从运行态转换为等待态。

   答案：

   对。

   ---

2. 段页式内存分配方案可以同时避免产生外部碎片和内部碎片。

   答案：

   错，段页式分配仍然也可能会产生内部碎片。

   ---

3. Belady 异常是指过多缺页导致 Swap in,swap out 增多，即 I/O 操作增多，从而引起 CPU 利用率下降，导致操作系统增加更多的用户进程进入系统，反过来导致更多缺页的现象。

   答案：

   错，以上是 Thrashing（颠簸，抖动）；Belady 异常是指“分配页框越多，缺页率反而越高”。

   ---

4. 虚拟内存的容量只受计算机系统地址位数的限制。

   答案：

   错，还受限于物理内存和磁盘的大小。

   ---

5. 基于转换表缓冲区（TLB）的数据访问最多只需要两次内存访问。

   答案：

   错，最多几次内存访问取决于分页策略，段页式、散列页表或者多级页表可能需要多于两次内存访问。

---

二、单项选择题（15 分，每小题 3 分）

1. 虚拟存储的基础是程序局部性理论，它的基本含义是（ ）。

   A. 代码的顺序执行

   B. 程序执行时对内存访问的不均匀性

   C. 变量的连续访问

   D. 指令的局部性

   答案：

   B

   ---

2. 采用分段式存储管理的系统中，若地址用 32 位表示，其中 12 位表示段号，则允许每段的最大长度是:

   A. 12

   B. 20

   C. $2^{12}$

   D. $2^{20}$

   答案：

   D

   ---

3. 使用段页式内存管理，段表和页表都存放在主存中，所有要访问的页面都在主存中。页表项可以缓存在转换表缓冲区（TLB）中。一次内存访问的代价为 $100\ \text{ns}$，一次 TLB 访问代价为 $10\ \text{ns}$。假设 TLB 的命中率为 50%，请问进程对内存的有效访问时间（effective access time）是：

   A. $110\ \text{ns}$

   B. $210\ \text{ns}$

   C. $160\ \text{ns}$

   D. $320\ \text{ns}$

   答案：

   B

   ---

4. 某作业访问页面的顺序为 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2，分配给该作业三个框，则采用 LRU 页面置换算法会产生几次缺页中断？

   A. 5

   B. 6

   C. 7

   D. 8

   答案：

   C

   ---

5. 以下对于按需调页的页面替换算法的描述，正确的是：

   A. 在缺页率上，最优调页必然优于（或相当于）LRU 算法；

   B. 先进先出（FIFO）算法必然会导致页框越多，缺页率越高；

   C. LRU 算法在替换页面查找效率上优于 FIFO 算法；

   D. 以上皆错。

   答案：

   A

---

三、辨析题（30 分，每小题 6 分）

分别解释以下每组的两个名词，并列举他们的区别。

1. 逻辑地址与物理地址

   答案：

   逻辑地址：又称为虚拟地址，由程序产生的与段相关的偏移地址部分；

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

   区别：物理地址通常是唯一的，而逻辑地址与物理地址可以是多对一的关系；而且用户程序通常只能操作逻辑地址，通过操作系统提供的保护机制，物理地址对用户程序是透明的。

   ---

2. Valid/invalid bit 与 dirty bit.

   ---

3. 动态加载 vs 动态链接

   答案：

   动态加载：P280. 例程仅在被调用时加载。未被使用的例程不会被加载。

   动态链接：P281. 程序仅在被调用时链接。被链接的程序一般是系统库函数。

   区别。P282

   ---

4. 页表和转换表缓冲区（TLB）

   答案：

   页表：在分页的内存管理策略中，页表实现了逻辑地址向物理地址的转换，通常保持在内存中；

   转换表缓冲区：它是一段小且专用的快速硬件缓冲，其中保持了页表中的一部分条目。

   区别：转换表缓冲区的访问速度远快于内存访问，因此比页表访问具有更高的时间效率，但是由于缓冲区通常是很小的一部分空间，因此只能容纳页表中很少的一部分。

   ---

5. 最优置换策略和 LRU 置换策略

   答案：

   最优置换策略：按需调页时，置换最长时间不会使用的页。

   LRU 置换策略：按需调页时，置换最长时间没有使用的页。

   区别：由于我们未知进程运行需要的页，最优置换算法难以实现，可以使用最长时间没有使用的页来近似最长时间不会使用的页。

---

四、综合题（40 分）

1. 五个内存块大小依次为 $100\ \text{KB}$, $500\ \text{KB}$, $200\ \text{KB}$, $300\ \text{KB}$, $600\ \text{KB}$。分别用 first-fit, best-fit, 以及 worst-fit 算法处理 $212\ \text{KB}$, $417\ \text{KB}$, $112\ \text{KB}$, and $426\ \text{KB}$ (按序)的内存请求，请说明各算法的分配情况。对于当前情况，那种算法比较好？

   答案：

   Answer:

   (a) First-fit:

   212K is put in 500K partition

   417K is put in 600K partition

   112K is put in 288K partition (new partition 288K = 500K − 212K)

   426K must wait

   (b) Best-fit:

   212K is put in 300K partition

   417K is put in 500K partition

   112K is put in 200K partition

   426K is put in 600K partition

   (c) Worst-fit:

   212K is put in 600K partition

   417K is put in 500K partition

   112K is put in 388K partition

   426K must wait

   In this example, best-fit turns out to be the best

   ---

2. （1）某系统段表如下,求以下逻辑地址的物理地址。（5 分）。

   (a) 0, 0x430000；(b) 1, 0x10000；(c) 2, 0x500000；

   (d) 3,0x400000； (e) 4, 0x112000

   段号	基地址	长度
   0	0x219000	0x600000
   1	0x2300000	0x14000
   2	0x90000	0x100000
   3	0x1327000	0x580000
   4	0x1952000	0x96000

   答案：

   a. 0x219000 + 0x430000 = 0x649000

   b. 0x2300000 + 0x10000 = 0x2310000

   c. illegal reference, trap to operating system

   d. 0x1327000 + 0x400000 = 0x1727

   e. illegal reference, trap to operating system

   （2）某 32 位系统采用分页技术进行内存分配，页大小为 $4\ \text{KB}$。某进程的页表如下，请在内存中定位下列虚拟地址的物理地址：0x0c73, 0x1e41, 0x2b4c, 0x37bb, 0x580b（5 分）。

   页号	框号	i/v
   0	4	v
   1	2	v
   2	5	v
   3	3	v
   4	8	i

   答案：

   0x0c73 --> 0x4c73

   0x1e41 --> 0x2e41

   0x2b4c --> 0x5b4c

   0x37bb --> 0x37bb

   0x480b --> 超出了页表长度，非法内存访问

   ---

3. 请解释多级页表、反向页表、散列页表（或叫“哈希”页表）的概念（可画图表示），并从地址翻译的效率、内存空间占用这连个角度，详细分析对于 64 位 CPU 的计算机，这三种技术各自的优缺点。（10 分）

   答案：

   略

   ---

4. （10 分）现有两个进程 P1 和 P2，当前的页面访问序列分别为：

   P1: 1, 2, 3, 4, 1, 2, 5

   P2: 6, 7, 8, 6, 7, 6, 7

   这两个进程总共可有 5 个页框可供使用。假设使用 LRU 替换策略，页框分配采用固定分配（即分配后不可修改），请问如何在两个进程间分配页框可以达到缺页率最低？请写出替换序列，和缺页率计算过程（4 分）；并证明该分配对于给出的序列是最优的（6 分）。

   答案：

   2, 3 （10 次缺页）

   1, 1, 3, 4, 1, 2, 5

      2, 2, 3, 4, 1, 2

   
   

   6, 6, 6, 6, 6, 6, 6

      7, 7, 7, 7, 7, 7

         8, 8, 8, 8, 8

   证明：

   1. 给 P2 更多页面不会减少 P2 的缺页率；
   2. 给 P1 3 个页面不会减少 P1 的缺页率，但是会增加 P2 的缺页率；
   3. 给 P1 4 个页面，P1 的缺页次数为 5，但是 P2 的缺页次数为 7。