第16章

操作系统

操作系统面试例题主要包括进程、线程、内存管理、垃圾回收，以及缓存等诸多方面。

16.1　进程

面试例题1：试解释操作系统原理中的作业、进程、线程、管程各自的定义。［中国著名通讯公司Z2009年10月笔试题］

答案：作业：用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合。它包括用户程序、所需要的数据及控制命令等。作业是由一系列有序的步骤组成的。

进程：一个程序在一个数据集合上的一次运行过程。所以一个程序在不同数据集合上运行，乃至一个程序在同样数据集合上的多次运行都是不同的进程。

线程：线程是进程中的一个实体，是被系统独立调度和执行的基本单位。

管程：管程实际上是定义了一个数据结构和在该数据结构上的能为并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据。

面试例题2：进程间的通信如何实现？［日本某著名家电／通信／IT企业面试题］

答案：现在最常用的进程间通信的方式有信号、信号量、消息队列、共享内存。所谓进程通信，就是不同进程之间进行一些“接触”。这种接触有简单，也有复杂。机制不同，复杂度也不一样。通信是一个广义上的意义，不仅仅指传递一些message。它们的使用方法是基本相同的，所以只要掌握了一种使用方法，然后记住其他的使用方法就可以了。信号和信号量是不同的，它们虽然都可用来实现同步和互斥，但前者是使用信号处理器来进行的，后者是使用P、V操作来实现的。消息队列是比较高级的一种进程间通信方法，因为它真的可以在进程间传送message，连传送一个“I seek you”都可以。

一个消息队列可以被多个进程所共享（IPC就是在这个基础上进行的）；如果一个进程的消息太多，一个消息队列放不下，也可以用多于一个的消息队列（不过可能管理会比较复杂）。共享消息队列的进程所发送的消息中除了message本身外还有一个标志，这个标志可以指明该消息将由哪个进程或者是哪类进程接受。每一个共享消息队列的进程针对这个队列也有自己的标志，可以用来声明自己的身份。

面试例题3：在Windows编程中互斥器（mutex）的作用和临界区（critical section）类似，请说一下二者间的主要区别。［中国台湾某著名杀毒软件公司2005年面试题］

解析：多线程编程问题。

答案：两者的区别是mutex可以用于进程之间互斥，critical section是线程之间的互斥。

面试例题4：At time 0, process A has arrived in the system, in that order; at time 30, both progress B and C have just arrived; at time 90, both progress D and E have also arrived.The quantum or timeslice is 10 units.（在0时刻，进程A进入系统，按照这个顺序，在30时刻，进程B和进程C也抵达；在90时刻，进程D和进程E也抵达。一个时间片是10个单元）

Process A requires 50 units of time in the CPU; Process B requires 40 units of time in the CPU; Process C requires 30 units of time in the CPU; Process D requires 20 units of time in the CPU; Process E requires 10 units of time in the CPU。

（进程A需要占用CPU50个单元；进程B需要占用CPU40个单元；进程C需要占用CPU30个单元；进程D需要占用CPU20个单元；进程E需要占用CPU10个单元。）

Which of the process will be the LAST to complete, if scheduling policy is preemptive SJF(Short Job First)?（如果按照短作业优先级的方法，哪个进程最后结束？）［美国著名软件公司M2009年10月笔试题］

解析：牢记“短作业优先”=“最短剩余时间作业优先”。本题考的是可剥夺式处理机的调度问题。时间图如下所示。

答案：如果按短作业优先级的方法，进程B最后结束。

扩展知识

读者试着扩展思维，想想如果本题是不可剥夺式处理机的调度方法，哪个进程最后结束。

面试例题5：For a multiple-processing OS, the way to deal with dead-lock is whether to prevent it from happening, or break it happens. Which of the following approaches belong to the way to prevent dead-lock from happening?(M)（多选：在多重处理系统中，处理死锁的办法有两种：一是防止其发生；二是发生后进行处理。下面的办法中属于防止其发生的是哪一个？）［中国台湾著名杀毒软件公司Q2009年1月笔试题］

A．Destroy mutual condition（破坏互斥条件）

B．Destroy non-preemptive condition（破坏不可剥夺条件）

C．Destroy iterative waiting condition（破坏循环等待条件）

D．To kill one process which involves in dead-lock（杀死某个激活死锁的进程）

解析：所谓deadlocks（死锁）是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁。

产生死锁的4个必要条件如下。

●　互斥条件：一个资源每次只能被一个进程使用。

●　请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。

●　不剥夺条件：进程已获得的资源，在末使用完之前，不能强行剥夺。

●　循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。

这4个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。

死锁的解除与预防方法如下：

理解了死锁的原因，尤其是产生死锁的4个必要条件，就可以最大可能地避免、预防和解除死锁。所以，在系统设计、进程调度等方面注意如何不让这4个必要条件成立，如何确定资源的合理分配算法，避免进程永久占据系统资源。此外，也要防止进程在处于等待状态的情况下占用资源，在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。因此，对资源的分配要给予合理的规划。

根据产生死锁的4个必要条件，只要使其中之一不能成立，死锁就不会出现。为此，可以采取下列3种预防措施：

●　采用资源静态分配策略，破坏“部分分配”条件。

●　允许进程剥夺使用其他进程占有的资源，从而破坏“不可剥夺”条件。

●　采用资源有序分配法，破坏“环路”条件。

这里注意一点：互斥条件无法被破坏。

死锁的避免不严格地限制死锁的必要条件的存在，而是系统在系统运行过程中小心地避免死锁的最终发生。避免死锁算法中最有代表性的算法是Dijkstra E.W于1968年提出的银行家算法，该算法需要检查申请者对资源的最大需求量，如果系统现存的各类资源可以满足申请者的请求，就满足申请者的请求。这样申请者就可很快完成其计算，然后释放它占用的资源，从而保证了系统中的所有进程都能完成，所以可避免死锁的发生。

在本题中选项A破坏互斥条件是无法做到的，B、C正确，D选项属于死锁事后处理操作，与题意不符。

答案：B，C。

面试例题6：在Linux平台下运行C程序。如果fork()函数不失败，下面哪个描述是正确的

A．The output will include number "1" exactly two times;

B．The output will include number "2" exactly two times;

C．Number "3" will always be last outputted;

D．It is possible that no number "3" in output, because "i++" is not an atomic operation.

解析：fork英文是叉的意思。在这里的意思是进程从这里开始分叉，分成了两个进程：一个是父进程，一个子进程。子进程拷贝了父进程的绝大部分：栈、缓冲区等等。系统为子进程创建一个新的进程表项，其中进程id与父进程是不相同的，这也就是说父子进程是两个独立的进程，虽然父子进程共享代码空间，但是在涉及写数据时子进程有自己的数据空间，在有数据修改时，系统会为子进程申请新的页面。

在本题中，由于if(!fork()) i++;所以只有子进程才会执行i++。执行顺序如下：

选项B不正确，2会输出3次；选项C不一定，因为父子进程谁先运行不一定；选项D也不对，3会出现。

答案：A

扩展知识：想一下，如下代码的输出结果是什么？

面试例题7：请描述进程的三种基本状态。［中国某互联网软件公司T2013年面试题］

答案：进程在运行中不断地改变其运行状态。通常，一个运行进程必须具有以下三种基本状态。1>就绪(Ready)状态：当进程已分配到除CPU以外的所有必要的资源，只要获得处理机便可立即执行，这时的进程状态称为就绪状态。2>执行（Running）状态：当进程已获得处理机，其程序正在处理机上执行，此时的进程状态称为执行状态。3>阻塞(Blocked)状态：正在执行的进程，由于等待某个事件发生而无法执行时，便放弃处理机而处于阻塞状态。引起进程阻塞的事件可以有多种，例如，等待I/O完成、申请缓冲区不能满足、等待信件(信号)等。

面试例题8：若系统中有五台绘图仪，有多个进程均需要使用两台，规定每个进程一次仅允许申请一台，则至多允许（　　）个进程参于竞争，而不会发生死锁。［中国台湾某IT公司C2013年2月笔试题］

A．2

B．3

C．4

D．5

解析：哲学家就餐问题：资源（餐叉）按照某种规则编号为1至5，每一个工作单元（哲学家）总是先拿起左右两边编号较低的餐叉，再拿编号较高的。用完餐叉后，他总是先放下编号较高的餐叉，再放下编号较低的。在这种情况下，当4位哲学家同时拿起他们手边编号较低的餐叉时，只有编号最高的餐叉留在桌上，从而第5位哲学家就不能使用任何一只餐叉了。

答案：C

16.2　线程

面试例题1：请描述进程和线程的差别。［美国某著名软件公司2005年面试题］

答案：进程是程序的一次执行。线程可以理解为进程中执行的一段程序片段。在一个多任务环境中下面的概念可以帮助我们理解两者间的差别。

进程间是独立的，这表现在内存空间、上下文环境上；线程运行在进程空间内。一般来讲（不使用特殊技术），进程无法突破进程边界存取其他进程内的存储空间；而线程由于处于进程空间内，所以同一进程所产生的线程共享同一内存空间。

同一进程中的两段代码不能够同时执行，除非引入线程。

线程是属于进程的，当进程退出时该进程所产生的线程都会被强制退出并清除。线程占用的资源要少于进程所占用的资源。进程和线程都可以有优先级。

进程间可以通过IPC通信，但线程不可以。

面试例题2：下面哪个选项不是PE文件？

A．EXE

B．DLL

C．COM

D．DOC

解析：PE文件被称为可移植的执行体是Portable Execute的全称，常见的EXE、DLL、OCX、SYS、COM都是PE文件，PE文件是微软Windows操作系统上的程序文件（可能是间接被执行，如DLL）

答案：D

面试例题3：Windows将遵循下面的哪种搜索来定位DLL？

1　进程的当前工作目录

2　包含EXE文件的目录

3　列在Path环境变量中的一系列目录

4　Windows系统目录

5　Windows目录

A．12453

B．12543

C．21453

D．21345

解析：Windows平台的大多数程序都使用各种动态链接库（DLL）来避免重复实现功能。操作系统为每个程序加载若干个DLL，具体由程序的类型决定。当程序不指定DLL的绝对位置时，将使用默认的搜索顺序来找到它。默认情况下，操作系统所使用的搜索顺序为：（1）内存；（2）KnownDLLs；（3）清单与.local；（4）应用程序目录；（5）当前工作目录；（6）系统目录；（7）路径变量。

答案：A

面试例题4：In user mode application development, sometimes we choose to use dynamic linked library instead of static linked library. That is because（动态链接库相对静态连接库的优点主要是）

A．The dynamic link library can be upgraded without requiring applications to be re-linked or re-compiled.

B．Runtime loading dynamic library will be faster than static library.

C．Calling functions in dynamic library will be faster than static library.

D．Dynamic library enable lots of memory sharing when mutiple apps are using the same libraries at the same time. This is also true for saving disk space.

E．Dynamic link library can be explicitly loaded/unloaded at runtime, this helps application provide optional features.

解析：目前以lib为后缀的库有两种，一种为静态链接库(Static Libary)，另一种为动态链接库(DLL)的导入库（Import Libary，以下简称“导入库”）。虽然静态链接库和动态库的导入库都是.lib文件，但是区别很大，它们实质是不一样的东西。静态库本身就包含了实际执行代码、地址符号表等等，而对于导入库而言，其实际的执行代码位于动态库中，导入库只包含了地址符号表等，确保程序找到对应函数的一些基本地址信息。

静态链接库是一个或者多个obj文件的打包，所以有人干脆把从obj文件生成lib的过程称为Archive，即合并到一起。比如你链接一个静态库，如果其中有错，它会准确地找到是哪个obj有错，即静态lib只是壳子。当我们的应用工程在使用静态链接库的时候，静态链接库要参与编译，在生成执行文件之前的链接过程中，将静态链接库的全部指令直接链接入可执行文件中，故而，在可执行文件生成以后，静态链接库.lib文件即可以弃之不用。

动态链接库(dll)是作为共享函数库的可执行文件。动态链接提供了一种方法，使进程可以调用不属于其可执行代码的函数。函数的可执行代码位于一个.dll文件中，该dll包含一个或多个已被编译、链接并与使用它们的进程分开存储的函数。dll还有助于共享数据和资源。多个应用程序可同时访问内存中单个dll副本的内容。使用动态链接代替静态链接有若干优点。dll节省内存，减少交换操作，节省磁盘空间，更易于升级(不需要重链接和重编译)，提供售后支持，提供扩展MFC库类的机制，支持多语言程序。

静态链接库与动态链接库都是共享代码的方式，如果采用静态链接库，lib中的指令都全部被直接包含在最终生成的exe文件中了。但是若使用dll（即动态链接库），该dll不必被包含在最终exe文件中，exe文件执行时可以“动态”地引用和卸载这个与exe独立的dll文件。静态链接库和动态链接库的另外一个区别在于静态链接库中不能再包含其他的动态链接库或者静态库，而在动态链接库中还可以再包含其他的动态或静态链接库。动态链接库与静态链接库的使用不同之处在于它允许可执行模块（.dll文件或.exe文件）仅包含在运行时定位dll函数的可执行代码所需的信息。在静态链接库的使用中，链接器从静态链接库获取所有被引用的函数，并将库同代码一起放到可执行文件中。

选项B和C不正确，静态链接库可能比动态链接库更快。

答案：A，D，E。

面试例题5：假定我们有三个程序，每个程序花费80％的时间进行I/O，20％的时间使用CPU，每个程序的启动时间和其需要使用CPU进行计算机的分钟数如表所示。请问在多线程／进程环境下，系统总响应时间为多少？［中国某著名即时通讯软件公司T2013年面试题］

A．22.5

B．23.5

C．24.5

D．25.5

解析：0～10分钟，100.8=8 100.2=2 A还剩下3.5-2=1.5分钟CPU需要跑。

10～15分钟，有两个进程，CPU利用率为1-0.80.8=0.36。所以(15-10)0.36=1.8分钟；1.8/2=0.9（两个进程均分CPU时间）这样A剩下1.5-0.9=0.6分钟，B剩下2-0.9=1.1分钟。

15分钟开始时，有三个进程CPU利用率为1-0.80.80.8=0.488，所以A在0.63/0.488=3.69后也就是15+3.69=18.69分完成，之后CPU利用率又为0.36，此时B剩下1.1-0.6=0.5分钟，C剩下1.5-0.6=0.9分钟之后，B在0.52/0.36=2.78也就是2.78+18.69=21.46分钟的时候B进程结束，之后C开始单跑0.9-0.5=0.4分钟；0.4/0.2=2分钟，即2分钟之后C结束，也就是21.46+2=23.46≈23.5分钟之后，CPU跑完三个程序。

答案：A

面试例题6：创建两个线程模拟火车站两个窗口售票程序，窗口售票时间为1秒，两个窗口不能同时售票。［美国某著名软件公司I2013年面试题］

解析：进程是由两个部分构成的，一个是进程内核对象，另一个是地址空间。同样，线程也是由两个部分组成的：一个是线程的内核对象，操作系统用它来对线程实施管理。内核对象也是系统用来存放线程统计信息的地方。另一个是线程堆栈，它用于维护线程在执行代码时需要的所有函数参数和局部变量。

进程是不活泼的。进程从来不执行任何东西，它只是线程的容器。线程总是在某个进程环境中创建的，而且它的整个寿命期都在该进程中。这意味着线程在它的进程地址空间中执行代码，并且在进程的地址空间中对数据进行操作。因此，如果在单进程环境中，你有两个或多个线程正在运行，那么这两个线程将共享单个地址空间。这些线程能够执行相同的代码，对相同的数据进行操作。这些线程还能共享内核对象句柄，因为句柄表依赖于每个进程而不是每个线程的存在。

进程使用的系统资源比线程多得多，原因是它需要更多的地址空间。为进程创建一个虚拟地址空间需要许多系统资源。系统中要保留大量的记录，这要占用大量的内存。由于线程需要的开销比进程少，因此一般用增加线程来解决编程问题，而要避免创建新的进程。

每当进程被初始化时，系统就要创建一个主线程。该线程与C / C++运行期库的启动代码一道开始运行，启动代码则调用进入点函数，并且继续运行直到进入点函数返回并且C/ C++运行期库的启动代码调用退出为止。对于许多应用程序来说，这个主线程是应用程序需要的唯一线程。不过，进程能够创建更多的线程来帮助执行它们的操作。

每个线程必须拥有一个进入点函数，线程从这个进入点开始运行。即main、wmain、Win Main或wWin Main。如果想要在你的进程中创建一个辅助线程，它必定也是一个进入点函数，类似下面的样子：

线程函数可以执行你想要它做的任何任务。最终，线程函数到达它的结尾处并且返回。这时，线程终止运行，该堆栈的内存被释放，同时，线程的内核对象的使用计数被递减。如果使用计数降为0，线程的内核对象就被撤销。与进程内核对象的情况相同，线程内核对象的寿命至少可以达到它们相关联的线程那样长，不过，该对象的寿命可以远远超过线程本身的寿命。

答案：

16.3　内存管理

面试例题1：简述Windows内存管理的几种方式和优缺点。［中国某著名互联网公司B面试题］

答案：Windows内存管理方式主要分为：页式管理、段式管理、段页式管理。

页式管理的基本原理是将各进程的虚拟空间划分成若干个长度相等的页(page)；页式管理把内存空间按页的大小划分成片或者页面，然后把页式虚拟地址与内存地址建立一一对应的页表；并用相应的硬件地址变换机构来解决离散地址变换问题。页式管理采用请求调页或预调页技术来实现内外存存储器的统一管理。其优点是没有外碎片，每个内碎片不超过页的大小。缺点：程序全部装入内存，要求有相应的硬件支持。例如地址变换机构缺页中断的产生和选择淘汰页面等都要求有相应的硬件支持。这增加了机器成本，增加了系统开销。

段式管理的基本思想就是把程序按内容或过程函数关系分成段，每段有自己的名字。一个用户作业或进程所包含的段对应一个二维线形虚拟空间，也就是一个二维虚拟存储器。段式管理程序以段为单位分配内存　然后通过地址影射机构把段式虚拟地址转换为实际内存物理地址。其优点是可以分别编写和编译，可以针对不同类型的段采取不同的保护，可以按段为单位来进行共享，包括通过动态链接进行代码共享。缺点是会产生碎片。

段页式管理：为了实现段页式管理，系统必须为每个作业或进程建立一张段表以管理内存分配与释放、缺段处理等。另外由于一个段又被划分成了若干页。每个段又必须建立一张页表以把段中的虚页变换成内存中的实际页面。显然与页式管理时相同，页表中也要有相应的实现缺页中断处理和页面保护等功能的表项。段页式管理是段式管理与页式管理方案结合而成的　所以具有它们两者的优点。但反过来说，由于管理软件的增加，复杂性和开销也就随之增加了。另外需要的硬件以及占用的内存也有所增加。使得执行速度下降。

面试例题2：X64和X86有何区别？

答案：Intel曾用8086、80286、80386等作为其PC用CPU的型号表示法，x86指Intel制造的普通CPU（提出x86这个表示法时，个人电脑上以32位Intel的CPU为主），x64是x86_64的缩写，指x86基础上的改进版（加入64位地址扩展等性能），而纯64位计算机架构用IA64表示，32位兼容的64位架构用amd64表示（AMD是这一架构的主要生产商）。由于Intel起步较早，影响较大，有时也把amd64架构的CPU称为x86_64架构。

面试例题3：Belady's Anomaly出现在哪？

A．内存管理算法

B．内存换页算法

C．预防死锁算法

D．磁盘调度算法

解析：所谓Belady现象是指：采用FIFO算法时，如果对—个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。Belady现象的原因是FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。这些页在FIFO算法下被反复调入和调出，并且有Belady现象。

答案：B

面试例题4：什么是Thrashing？

A．非常频繁的换页活动

B．非常高的CPU执行活动

C．一个极长的执行过程

D．一个极大的虚拟内存法

解析：内存抖动(Thrashing)一般是内存分配算法不好，内存太小或者程序的算法不佳引起的页面频繁地从内存调入／调出的行为。

答案：A

面试例题5：避免死锁的一个著名算法是？

A．先入先出发

B．银行家算法

C．优先级算法

D．资源有序分配法

解析：银行家算法是用来避免死锁的，该方法将系统的状态分为安全状态和不安全状态，只要使系统处于安全状态，便可避免死锁的发生。

答案：B

面试例题6：某主机安装了2GB内存，在其上运行的某支持MMU的32位Linux发行版中，一共运行了X，Y，Z三个进程，下面关于三个内存使用程序的方式，哪个是可行的？

A．X，Y，Z的虚拟地址空间都映射到0～4G虚拟地址上

B．X在堆上分配总大小为1GB的空间，Y在堆上分配200MB，Z在堆上分配500MB，并且内存映射访问一个1GB的磁盘文件。

C．X在堆上分配1GB，Y在堆上分配800MB，Z在堆上分配400MB

D．以上的访问方式都是可行的

解析：虚拟存储器的基本思想是程序、数据、堆栈的总的大小可以超过物理存储器的大小，操作系统把当前使用的部分保留在内存中，而把其他未被使用的部分保存在磁盘上。

答案：D

面试例题7：某虚拟内存系统采用页式内存管理，使用LRU页面管理算法。考虑下面的页面访问地址流（每次访问在一个时间单位内完成）中一共有几次页面失败：

1，8，1，7，8，2，7，2，1，8，3，8，2，1，3，1，7，1，3，7？

A．4

B．5

C．6

D．7

解析：LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面，很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面，很可能在未来较长的一段时间内不会被用到。算法如下。

答案：C