软件设计师 上午题 操作系统知识

操作系统(Operating System, OS)是为裸机配置的一种系统软件，用于填补人与机器之间的鸿沟。操作系统在计算机系统中的地位如下图所示：

不难发现，操作系统是裸机上的第一层软件，是对硬件系统功能的首次扩充，是用户与计算机之间的接口。有了操作系统，系统软件和应用软件等大量其它软件才有了使用基础，因此，操作系统已成为现代计算机系统中必不可少的最重要的系统软件。
操作系统的核心功能模块分为进程管理、存储管理、设备管理、文件管理和作业管理五个部分，它们共同构成了操作系统对计算机硬件和软件资源的管理体系。

一、进程管理

进程管理也称之为处理机管理，为了描述系统中程序执行时的动态变化，操作系统中引入了进程的概念。所谓进程管理即管理计算机中正在运行的程序，其管理重点是研究诸进程之间的并发特性，以及进程之间相互合作与资源竞争产生的问题，进而确保CPU资源被合理分配。

Ⅰ 基本概念

1. 程序与进程

程序的执行方式大致可以分为顺序执行和并发执行两类：

1）程序顺序执行的特征：

顺序执行是指程序严格按照代码编写的顺序依次执行，前一条语句执行完毕才会执行下一句。程序顺序执行时的主要特征包括顺序性、封闭性和可再现性。
此外，有一种有向无环图叫做前驱图，它可以用来描述程序中各个任务之间的依赖关系。因此顺序执行的任务就可以转换为一条线性前驱图，如下图所示：

其中，输入结束之后才能进行计算，计算结束之后才能进行输出。

2）程序并发执行的特征：

若在计算机系统当中采用多道程序设计技术，则主存中的多道程序可处于并发执行状态。虽然每个作业中有前驱关系的各程序段不能并行执行，但是每个作业中没有前驱关系的程序段或者不同作业的程序段可以并行执行。

若每个程序有三个程序段：输入$I_i$、计算$C_i$和输出$P_i$。如图4-2所示，$I_2$就可以和$C_1$并行执行，$I_3$、$C_2$和$P_1$也可以并行执行等等。
同时，程序并发执行时有以下特征：

• 失去了程序的封闭性：在顺序执行时，程序独占所有资源，其执行过程不受外界干扰，结果完全由程序自身决定，这也就是所谓的封闭性。而在并发执行的过程中，多个程序共享资源就会打破这一封闭性。
• 程序和机器的执行程序的活动不再一一对应：在顺序执行中，程序指令严格按照代码顺序执行，程序行为是可预测的。但是在并发执行当中因CPU调度、中断、抢占等问题，指令的执行顺序可能被打乱。
• 并发程序间的相互制约性：并发程序由于共享资源或者协作关系，会彼此制约和影响。其中又分为直接制约和间接制约。前者是指程序间进行显式通信，而后者指的是竞争同一资源导致阻塞。

---

首先需要了解的是什么是信号量和PV操作。信号量本质上是一个计数器+等待队列+原子操作(即PV操作)。其中计数器中的整型变量，也就是题目中所谓的S1，S2，S3，S4，是用来表示当前可用的“通行许可证”数量，可以用来衡量当前系统中剩余的资源数量。而P操作（Proberen，荷兰语“通过”）是申请资源，操作结果是计数器S-=1，V操作（Verhogen，荷兰语“释放”）是释放资源，作结果是计数器S+=1。另外，信号量是针对于进程转换这个过程而言的，也就是图中的每一个“箭头”，而非针对进程本身。在每一个箭头当中应该先完成一次V操作再完成一次P操作。
那么对于本题来说，S1是指P1P2之间的箭头，其余以此类推。那么P1进行时，应该先分别完成一次V(S1)和一次V(S2)；然后为了使P2准备就绪，就应该再完成一次P(S1)。重复执行这个思路就能得到最终答案。

---

BAC，捋顺$I_i$->$C_i$->$P_i$的关系即可。

2. 进程的状态及其状态间的切换

进程一般有3种基本状态：运行、就绪和阻塞：

• 运行：当一个进程在处理机上运行时，则称该进程处于运行状态。
• 就绪：一个进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行，则称此进程处于就绪状态。
• 阻塞：阻塞也称等待或者睡眠状态，当一个进程正在等待某一事件发生而暂停运行（即使把处理机分配给进程也无法运行），此时该进程处于阻塞状态。

当在这三种基本状态中捋顺了转换关系，就构成了三态模型：

Ⅱ 进程间的通信

显而易见，在一个多道程序环境的系统当中，进程间必然存在资源共享和相互合作的问题，而进程通信就是指各个进程之间交换信息的过程。

1. 同步与互斥

同步是合作进程间的直接制约问题，互斥是申请临界资源进程间的间接制约问题。^[1]

用人话说就是，同步是多个进程需要按照特定的顺序协作完成任务，互斥是多个进程竞争同一资源，需要保证同一时间仅一个进程访问。

1）进程间的同步

在计算机系统当中，多个进程可以并发执行，每个进程都以各自独立的、不可预知的速度向前推进，但是需要在某些确定点上协调相互合作进程间的工作。例如进程A煮米，进程B炒米，那显然必须是进程A完成了之后才能进行进程B，否则进程B就要停下来等待进程A。

2）进程间的互斥

在多道程序系统环境当中，有一种资源一次只能供一个进程使用，这种资源我们称其为临界资源，比如打印机。那么进程之间的互斥就是系统中多个进程因争用临界资源而发生的互斥执行。

3）临界区管理的原则

临界区即进程中对临界资源实施操作的那段程序，对互斥临界区的管理有以下几条原则：

• 有空即进。
• 无空则等。
• 有限等待：应该保证进程在有限的时间内能够进入临界区，以免其陷入“饥饿”状态。
• 让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等待（如果暂时轮不到你的时候就先去忙别的事情）。

2. 信号量机制

在本文的前边我们已经了解过信号量和PV操作相关的内容，这里我们主要探讨如何使用PV操作实现进程间的同步和互斥：

1）利用PV操作实现进程间的同步

要实现进程的同步可以用一个信号量与消息联系起来，当信号量的值为0时表示希望的消息未产生，当信号量的值为非0的时候表示希望的消息已经存在。那么进程就可以通过调用P操作测试消息是否到达，通过调用V操作通知消息已经准备好。

semaphore sync = 0; // 初始值为0的同步信号量

Process A() 
{
    // 执行操作A
    V(sync);    // 通知进程B操作A已完成
}

Process B() 
{
    P(sync);    // 等待操作A完成
    // 执行操作B
}

2）利用PV操作实现进程间的互斥

令信号量S的初值为1，当进入临界区时执行P操作，退出临界区时执行V操作。这样一来，每当有程序段调用临界资源时S就能减1，防止共用一个临界资源的情况产生。

semaphore mutex = 1; // 初始值为1的互斥信号量

Process P1() 
{
    P(mutex);    // 进入临界区前申请锁
    // 临界区代码
    V(mutex);    // 离开临界区后释放锁
}

Process P2() 
{
    P(mutex);
    // 临界区代码
    V(mutex);
}

---

D。系统内有两台打印机，那么说明起始的可用资源总数应为2，即S的最大值应为2。当第一个进程想要调用打印机时，它就需要进行一次P(S)操作，S变为1。随后依次类推，每个进程逐次进行P(S)操作，最后就得到了S的最小值为-(n-2)。

---

BA，不难发现，生产者甲和生产者乙两者之间需要保持一种同步关系，而生产者甲和生产者乙自身所处的过程则需要保持一种互斥关系。在之前的学习中我们了解到，如果要保持同步关系，需要先执行一次V操作通知资源已经准备好，而如果要保持互斥关系，需要先执行一次P操作来占用资源。据此分析，S1是一个互斥信号量，在存放前减一，在取出后加一，用来表示的应该是半成品箱中被占用的资源，因此其初值应该为n；而S2是一个同步信号量，用来表示生产者甲通知生产者乙已经完成了一个半成品，因此其初值应该为0。此外，根据题目，S也是一个互斥信号量，鉴于它在每一个临界区中都会出现，它表示的应该是半成品箱是否正在被占用以存取物品，因此其初值应该为1。

---

CD， 信号量S应该与一个互斥的进程有关，即当前还有几个购票终端可以使用，那么这个信号量的初值就应该为n-1。  用户在选定具体的终端$P_i$之后需要占用这个终端，因此需要一个互斥信号量S，其初始值应该为1；(a)处应该为P(S)，因为当一个乘客想要买票时会占用一个终端；(b)处和©处都应该是V(S)，因为此时已经完成了购票流程，可以释放终端了。

Ⅲ 死锁

死锁现象的一般表现为：多个进程/线程均无法继续执行，系统整体或部分功能停滞（如程序无响应、任务无法完成），在本小节中我们仅了解同类资源分配不当引起的死锁。
当系统中有n个进程，每个进程所需要的资源数为k，系统中的资源总数为m，且系统采用的分配策略是轮流地为每个进程分配资源时，若m < n*（k-1）+1，则会发生死锁。

1. 进程资源图

进程资源图是一种​​有向图​​，用于描述操作系统中的​​进程与资源之间的分配和请求关系​​，是分析和检测死锁的重要工具，其一般形式如下图所示：

其中，一个圆圈代表一个进程，一个矩形代表一个资源，其中的圆圈个数是其资源的数量。

不同数字代表的箭头含义不同：

1. 表示P1向R申请一个资源
2. 表示R向P1分配一个资源
3. 表示R先分配给P1一个资源，P1再向R申请一个资源
4. R已经向三个进程分配了自己全部的三个资源，此时P1再向R申请资源就会进入等待态，即堵塞状态。

此外，进程资源图是可化简的，其步骤如下所述：

1. 把不阻塞的进程的所有边都去掉，形成一个孤立的点，再把系统分配给这个进程的资源回收回来。
2. 看剩下的进程有哪些是不阻塞的，然后又把它们逐个变成孤立的点。
3. 最后，所有的资源和进程都变成孤立的点。这样的图就叫做“可完全简化”。

如果一个图可完全简化，该系统就不会产生死锁，反之就会产生死锁。

---

BC，在图(a)中，R1中两个资源已经分配完毕但依旧有P2的申请，因此P2是一个堵塞结点，P1同理，图(b)同理。

---

2. 死锁的避免策略

银行家算法​​是一种经典的​​死锁避免算法​​，由Dijkstra提出，用于确保操作系统在分配资源时不会进入死锁状态。它的核心思想是​​模拟资源分配​​，仅当分配后系统仍处于​​安全状态​​时才批准请求，否则让进程等待。

银行家（操作系统）需要确保手头的现金（资源）能满足所有客户（进程）的贷款需求，同时避免资金链断裂（死锁）。

以此题为例，通过对已分配资源数的加和计算，不难发现R1，R2和R3的剩余资源数分别为1、1、0。
那么显然此时不能再继续执行还需要R3分配资源的进程了，观察后发现只有P4符合这一条件，因此执行序列的第一个应该为P4，排除①②。
下面可以讨论序列③能否完成，可以借助下图分析：

如果一个进程最终能够执行完毕，我们就给它打上一个True的标志。而检查其是否能够执行完毕的条件即为可用能否覆盖需求。同时，一个进程完成之后会释放所有已经占用的资源，即可用+已分部分的内容。据此分析，P1是无法完成的，因此排除序列③。

Ⅳ 线程

传统的进程有两个基本属性:可拥有资源的独立单位;可独立调度和分配的基本单位。引入线程的原因是进程在创建、撤销和切换中，系统必须为之付出较大的时空开销，故在系统中设置的进程数目不宜过多，进程切换的频率不宜太高，这就限制了并发程度的提高。引入线程后，将传统进程的两个基本属性分开，线程作为调度和分配的基本单位，进程作为独立分配资源的单位。用户可以通过创建线程来完成任务，以减少程序并发执行时付出的时空开销。^[1]

对比维度	进程（Process）	线程（Thread）
定义	操作系统资源分配的基本单位，拥有独立的内存空间。	进程内的执行单元，共享进程资源，是CPU调度的基本单位。
资源占用	独立的内存、文件句柄、CPU时间等。	共享进程的内存和资源，仅私有栈和寄存器。
创建/销毁开销	高（需分配独立资源）。	低（共享进程资源，仅需少量初始化）。
切换成本	高（需切换内存空间、更新页表等）。	低（仅切换寄存器、栈等线程私有数据）。
独立性	崩溃后不影响其他进程。	崩溃可能导致整个进程终止（共享地址空间）。
并发性	多进程依赖进程间切换（上下文切换成本高）。	多线程可真正并行（同一进程内线程切换成本低）。
适用场景	需要隔离性、安全性的任务（如不同用户的程序）。	需要高并发、低延迟的任务（如Web服务器处理请求）。
类比	独立的“工厂”，拥有自己的设备和资源。	工厂中的“工人”，共享设备但独立执行任务。

此外，同一个进程中的不同线程都可以共享这个进程中的资源。

二、存储管理

存储器管理的对象是主存存储器简称主存或内存。存储器是计算机系统中的关键性资源，是存放各种信息的主要场所。尽管近年来内存越来越便宜、容量越来越大，但系统软件、应用软件在功能及其所需存储空间等方面都在急剧膨胀，如何对存储器实施有效的管理，不仅直接影响到存储器的利用率，而且还对系统性能有很大的影响。存储器管理的主要功能包括主存空间的分配和回收、提高主存的利用率、扩充主存、对主存信息实现有效保护。^[1]

前置知识：局部性原理

局部性原理是计算机系统的一个重要行为特征，它描述了程序在执行过程中对内存访问的规律性，即程序更倾向于在短时间内集中访问某些特定的内存区域，而不是均匀地访问整个地址空间：

• 时间局部性：如果一个数据或指令被访问过，那么它在不久的将来很可能再次被访问。
• 空间局部性：如果一个数据被访问，那么它附近的数据（如相邻的内存地址）也可能很快被访问。

Ⅰ 分页存储管理

进行分页管理的原理即为将一个进程的地址空间划分成若干个大小相等的区域，称为页，同时将主存空间划分成与页相等大小的若干个物理块，称为块。在实际运行时会将若干个页分别装入多个不相邻接的块中。

分页系统的地址结构如上图所示，由页号和偏移量（即页内地址）两部分组成。其中页号是高位部分，用于索引页表，而页内偏移是低位部分，直接对应物理页内的位置。

---

AC，根据题意不难发现，页面0、页面2和页面4在内存当中，若需淘汰应在在三个页面当中淘汰。而根据程序的局部性原理，页面0最近被访问过，页面2、页面4既被访问过又被修改过，因此最有可能淘汰的是页面0。此外，由于页面大小为4KB，即4×2^10字节，亦即2^12字节，说明该系统中页有12位。也就是说只有当页面偏移量为12时才能覆盖所有位，如此一来便确定了页面偏移量。而题目中给出的2C25H等同于0x2C25（H用来表明该数采用十六进制表示），也就是一共有4个数，即4×4=16位。那么在后12位为页面偏移量的情况下，剩余的前4位，即第1个数就是页号了，为2。随后再根据页表内的信息将页号转换为页帧号（即物理块号），就得到了物理地址为4C25H。

Ⅱ 段页式存储管理

段页式存储管理是一种对段式存储和页式存储“各取所长”的存储管理方式，它先将整个主存划分成大小相等的存储块，随后将用户程序按程序的逻辑关系分为若干个段，再将一个段划分成若干个页。据此就形成了由段号、段内页号和业内地址三部分组成的段页式管理的地址：

---

B，简单的分段计算，唯一需要注意的是页号所在段的长度描述的是每个段最大允许有多少多少个页。

三、设备管理

Ⅰ 缓冲技术

缓冲技术是一种通过临时存储数据来协调不同速度设备或组件之间数据传输的方法，旨在解决速度不匹配问题，提高系统效率和性能。其核心原理是在数据生产者（如CPU、磁盘）与消费者（如打印机、网络）之间设立一个中间存储区（缓冲区），允许两者以各自最佳速率运行，减少等待时间。此外，亦有单缓冲区和双缓冲区的差别：

特性	单缓冲区	双缓冲区
结构	仅一个缓冲区	两个缓冲区交替使用（Buffer A/B）
工作流程	生产者填满→消费者读取→生产者等待	生产者填满A时，可立即填充B，消费者同时读取A
阻塞情况	生产/消费过程可能相互阻塞	生产与消费可并行，减少阻塞
效率	较低	较高
适用场景	低速或非实时场景	高速或实时需求

---

CB，

单缓冲工作的过程图和并行工作的示意图如下图所示：

不难发现当单缓冲区并行工作时，上一个任务的处理过程和下一个任务的输入过程是并行的，因此每个任务的实际工作时长可以看作10+5=15μs，再加上最后一个任务多余的处理时间，总时间即为15×10+2=152μs。

双缓冲工作的过程图和并行工作的示意图如下图所示：

双缓冲区和单缓冲区的不同就在于其输入过程是持续不断的，因此只需要计算10次输入过程的时长，并再加上最后一个任务的传送以及处理时间即可，答案为107μs。

Ⅱ 磁盘调度

计算机从一个磁盘中读取数据的基本过程为：读/写头移动到目标柱面上，这一过程称之为寻道时间；而存储数据的目标扇区会一刻不停旋转，想要读取数据就需要等待扇区旋转到读/写头的位置，这一过程称之为旋转延迟。

而磁盘调度算法分为移臂调度和旋转调度两类，并且是先进行移臂调度，然后进行旋转调度。需要注意的是，在访问磁盘的过程中最耗时的是寻道时间。

1. 移臂调度算法

1） 先来先服务算法（FCFS）

2） 最短寻道时间优先算法（SSTF）

这种算法要求访问的磁道与当前磁头所在的磁道距离最近。

3） 扫描算法（SCAN）

SCAN算法较于SSTF算法的区别在于其只考虑当前移动方向内的距离最近的磁道，在当前移动方向上没有磁道需要访问了磁头才会转向。

4） 单向扫描调度算法（CSCAN）

CSCAN算法和SCAN算法的区别在于前者是一种单向扫描算法，这意味着该算法在折返过程中不会停留，将保持循环往复保持同一起点进行单向扫描。

2. 旋转调度算法

当读写头到达指定位置之后，会有多个进程等待访问该柱面，那么该如何决定这些进程的访问顺序？就需要考虑以下几种情况：

• 进程请求访问的是同一磁道上不同编号的扇区
• 进程请求访问的是不同磁道上不同编号的扇区
• 进程请求访问的是不同磁道上相同编号的扇区

对于前两种情况，旋转调度总是让首先到达读/写头位置的扇区进行操作，而后一种情况下则是任选一个扇区进行传送操作。

旋转调度算法中常常涉及到在磁盘中对信息存储进行优化分布，鉴于在这里不便展开，详情请参见2010年上半年第27、28题。

四、文件管理

Ⅰ 文件目录

为了实现文件的“按名存取”，操作系统中势必存在一种来管理文件的数据结构，我们称其为文件控制块（FCB），而FCB的有序集合就是文件目录，故而文件控制块也可以被称作目录项。

1. 文件控制块

FCB中包含以下三类信息：

• 基本信息类：存储文件名、文件的物理地址、文件长度等。
• 存取控制信息类：存储文件的存取权限。
• 使用信息类：存储文件建立日期、最后一次修改日期、当前使用的信息等。

2. 目录结构

如何组织目录结构显然是一个重要的议题，它将直接影响文件的存取速度。常见的目录结构有以下三种:

• 一级目录结构：整个目录结构是一个线性结构，即在整个系统中只需要建立一张目录表，系统为每一个文件分配一个目录项。
• 二级目录结构：一级目录结构的一个缺点就是不同用户的文件容易重名且缺乏隔离性，因此我们可以引入二级目录结构的概念。二级目录结构由用户目录和主目录组成，主目录是系统唯一的顶层目录，包含所有用户的子目录，而用户目录则用来管理用户自己的独立文件。
• 多级目录结构：但是二级目录结构过强的隔离性又影响了多个用户之间的协作，比如一个用户难以直接访问另一个用户的文件，因此我们又引入了多级目录结构。多级目录结构类似于一棵树，从树根向下，每一个结点是一个目录，叶子节点即为文件，现代操作系统一般都采用了这种目录结构。

特性	单级目录	二级目录	多级目录
结构复杂度	最简单（所有文件同级存储）	中等（用户目录+主目录）	最复杂（树形嵌套，但灵活性最高）
命名冲突	极易发生（文件名必须唯一）	用户间隔离（同用户仍冲突）	路径唯一性彻底解决（如/a/1.txt和/b/1.txt可共存）
扩展性	无法扩展	有限扩展（仅两级）	无限嵌套子目录（如/a/b/c/...）
权限控制	全局统一权限	用户目录独立权限	每个目录可单独设权限（chmod）
典型系统	早期DOS	早期Unix	现代Linux/Windows/macOS
路径示例	file.txt	/home/user1/file.txt	/home/user1/docs/project1.txt

Ⅱ 存储空间的管理

位示图

位示图是一种常见的空闲空间的管理方法，它通过在外存上建立一张位示图来记录文件存储器的使用情况。

其中，每一个字对应的是文件存储器中的连续的物理块。假如当前的计算机系统的字长为32位，那么第0字就代表了0~31号物理块，第1字就代表了32~63号物理块，以此类推。而物理块上填写的0、1即为其空闲与否的状态。

---

B，简单计算，不再赘述。

1. 软件设计师教程（第五版）. (2018). ↩