Preface

报名了2022年下半年浙江省软考，科目是系统架构设计师（高级），由于工作、学校各方面的原因，拖到现在才开始复习……不过奋起直追，犹未晚也。

操作系统（Operating System）概述

操作系统是计算机系统中的核心系统软件，负责管理和控制计算机系统中的硬件和软件资源，合理组织计算机工作流程和有效利用资源，是计算机和用户之间的接口。任何操作系统均提供如下基本功能：

  • 处理机管理
  • 存储管理
  • 设备管理
  • 文件管理
  • 作业管理

根据使用环境和作业处理方式，可以简单将操作系统分为：

  • 批处理操作系统：用户脱机使用，成批处理，多道程序运行；
  • 分时操作系统：交互性，多用户同时性，独立性；
  • 实时操作系统：即时响应，高可靠性；
  • 网络操作系统：互操作性，协作处理；
  • 分布式操作系统

从结构上，可分为：

  • 无序结构： 系统开发周期短，但是模块关系复杂，分析、移植和维护较困难；
  • 层次结构：简化接口设计，易保证可靠性，易于移植和维护；
  • 面向对象结构：适用于网络操作系统和分布式操作系统；
  • 对称多处理结构：所有处理机运行且共享同一内存；
  • 微内核结构：核心态（内核态）和用户态的区别，把系统公共部分抽象出来，形成一个底层核心，提供基本服务，其他功能以服务器形式运行在微内核之上；它的主要优点：
    • 接口统一
    • 可伸缩性、可移植性、实时性、安全可靠性好
    • 支持分布式系统
    • 真正面向对象的操作系统

处理机管理

操作系统必须能够处理和管理并行的程序，使之对资源的利用按照良性的顺序执行。操作系统中调度和管理的最小单位是进程，而处理器分配资源的最小单位是线程。 进程是由程序、数据和进程控制块（Process Control Block, PCB）构成的，是计算机状态的有序集合；其中PCB是进程存在的唯一标志。

进程的三态/五态模型

这里讨论的三态/五态模型不考虑新建态以及终止态。

image.png

三态模型总是假设所有进程都处于系统内存中——这样的系统是理想的，实际上总会出现进程挂起的情况，于是下图所示的模型能更好的展示进程的状态。

image.png

注意：

  1. 只有就绪态可以直接切换到运行态；
  2. 挂起状态和对应的非挂起状态可以相互切换，但是不能跨状态切换；
  3. 等待态切换到就绪态是单向的，即便在挂起状态下也是如此；
  4. 等待事件一般指等待系统分配资源或者人工干预；

信号量(Samphore)和PV操作

信号量是一种特殊的变量，表现形式是一个整形S和一个队列。若S > 0，表示系统中可用的临界资源的数量；若S < 0，其绝对值表示等待使用临界资源的进程数，即等待队列中的进程的数量。

P操作表示申请一个资源，其中S = S - 1，若S < 0则执行P操作的进程暂停，并进入等待队列；V操作表示释放一个资源，其中S = S + 1，若S <= 0则唤醒队列中一个等待的程序[1][2]。

常见的使用PV操作的场景有三个，分别是互斥控制，同步控制和生产者-消费者问题。任何PV操作的题目，均可以从简单互斥、简单同步以及生产者-消费者模型的角度分析解答。

互斥(mutex)控制

互斥控制的目的是保护共享资源，阻止多个进程同时访问同一个共享资源。由于只允许一个进程进入临界区，因此S的初值为1.

同步控制

同步控制中S的初值应为0。

为使进程A等待进程B执行到相应位置后再继续执行，A在等待点执行P操作，此时S = -1 < 0，进程A进入等待队列；当进程B执行到相应位置后，执行V操作，此时S = 0 <= 0，于是进程A被唤醒，继续执行。

生产者-消费者问题

生产者-消费者模型面临两个重要问题：

  1. 生产者进程和消费者进程的同步问题，
  2. 缓冲区的互斥关系

为解决这个问题，一般需要引入三个信号量：

Samphore Operation 说明
empty 同步 空闲的缓冲区数量，初值为缓冲区的总数
full 同步 已填充的缓冲区数量，初值为0
mutex 互斥 保证只有一个进程在写缓冲区，初值为1

死锁问题

死锁问题的必要条件：

  1. 互斥条件： 一个资源只能被一个进程占用；
  2. 保持与等待条件：一个进程持有部分所需资源，但请求其他资源被阻塞，不释放已持有的资源；
  3. 不可抢占条件：某些系统资源是不可抢占的，只能等待进程执行完毕释放；
  4. 循环等待条件：若干进程形成循环链，每个都占用对方要申请的下一个资源。

打破任意一个必要条件，都不会产生死锁。因此解决死锁问题的策略主要是：

  • 死锁预防：提前破坏死锁条件，代价是降低系统效率；
  • 死锁避免：每次申请资源时判断是否会造成死锁，增加系统开销；
  • 死锁检测：检测系统是否处于死锁状态，如果是，则执行死锁解除策略；
  • 死锁解除：强制剥夺进程持有的资源并分配给其他进程。
银行家算法

银行家算法是一种死锁避免策略的实现，主要原则是:

  1. 进程对资源的需求不大于系统资源总数时，可以被系统接纳；
  2. 进程可以分批申请资源，但是请求的总数不能超过其最大需求量；
  3. 资源不足时，系统可以推迟资源的分配，但是总能在有限的时间内使进程获得资源；
  4. 分配前测试系统现存资源是否满足进程尚需的最大资源数，以决定是否要延迟分配。

管程与线程

同一进程的线程共享该进程的地址空间。

文件管理

文件的逻辑组织是用户角度看到的文件组织形式，常用的结构有连续结构、多重结构、转置结构和顺序结构等。

文件的物理组织是文件在存储设备上的存储方法，常用的文件物理结构如下：

  1. 连续文件：只需知道文件起始位置和长度即可进行存取，适用于顺序存取，但是长度不能动态增长；
  2. 串联文件：使用非连续的物理块，每个物理块都存储指向下一个物理块的指针，适用于顺序访问，提高了设备空间利用率并解决了碎片问题，不适用于随机存取；
  3. 索引文件：为每个文件建立索引表，记录逻辑块号和对应的物理块号。会增大存储空间的开销但是适用于顺序访问和随机访问。

树形目录结构（略）

存储空间管理

文件存储设备常被分为许多大小相同的物理块，且以块为单位交换信息。存储空间的管理的本质就是对空闲块的组织和管理问题。

  1. 空闲表法（空白文件目录法）：为所有的空闲区建立一张空闲表，记录序号，第一空闲块号和空闲块的数量；
  2. 空闲链表法：
    • 空闲盘块链
    • 空闲盘区链
  3. 位图法：用二进制位表示物理块的使用情况，0表示空闲。所有盘块都与一个二进制位对应；
  4. 成组链接法。

存储管理（虚拟存储器）

虚拟地址组成的地址空间成为虚拟存储器，由虚拟地址映射到物理地址的方法主要是静态重定位/动态重定位。常用的虚存组织主要是分段技术、分页技术和段页式技术三种。

三种存储技术的虚实地址转换见[[https://blog.csdn.net/m0_54158068/article/details/124206301]]。

策略

虚存管理的策略主要涉及调入策略、放置策略和置换策略。

  1. 调入策略：决定何时将一页或者一段从外存调入内存，可以按请求调入或者先行调入；
  2. 放置策略：决定调入后，目标内存的位置；
  3. 置换策略：决定如何淘汰内存中页。

常见的置换策略的实现有：

  • 最优算法：淘汰不再使用或者将来才会使用的页，理想算法，难以实现；
  • 随机算法：随机淘汰一些页，可能会淘汰立即就要使用的页，开销小；
  • FIFO算法：淘汰在内存中驻留时间最长的页，也可能会淘汰要立即使用的页，可能会产生Belady现象；
  • LRU算法：淘汰离当前时刻之前一段时间内使用最少的页。

局部性原理：进程往往会不均匀地高度局部化（时间/空间）地访问内存。

作业管理

作业的状态：

  1. 提交状态：由输入设备进入外存的过程；
  2. 后备状态：作业全部进入外存后，系统为其建立作业控制块；
  3. 执行状态：分配了必须资源且进入内存，进程建立；
  4. 完成状态：正常结束，资源被回收。

作业的调度：

  • 高级调度：从后备状态的作业中选择部分，分配资源，建立进程；
  • 中级调度：决定进程在内存、外存之间的调入和调出；
  • 低级调度：确定处理器在就绪进程之间的分配。

调度算法

  1. 先来先调度(FCFS)：按照作业到达的先后顺序调度，不利于短作业；
  2. 短作业优先(SJF)：估计运行时间较短的作业优先调度，不利于长作业；
  3. 响应比高者优先(HRN)：FCFS和SJF的综合；
  4. 优先级调度。

响应比RR的定义如下:

R=W+TT=1+WT(1)R = \frac {W + T} T = 1 + \frac W T \tag{1}

其中，WW是等待时间，TT是执行时间，从RR的定义可以看出，等待时间越长的作业越有可能被调度。

设备管理

  1. 提供和进程管理系统的接口；
  2. 进行设备分配；
  3. 实现设备和设备、设备和CPU之间的并行操作；
  4. 缓冲区管理

数据传输控制方式：

  • 程序控制
  • 程序中断
  • DMA
  • 通道方式
  • 输入输出处理机

磁盘调度：

  • FCFS
  • 最短寻道时间优先算法(SSTF)
  • 电梯算法(SCAN)
  • N-SCAN/C-SCAN

虚设备和SPOOLing技术

构成：

  1. 输入井、输出井：位于磁盘上，模拟脱机磁盘，保存用户输入输出的数据；
  2. 输入缓冲区、输出缓冲区：位于内存中，暂存输入设备（输出井）的数据，并传输到输入井（输出设备）中；
  3. 输入进程和输出进程：模拟外围控制机。

优点：
提高了I/O速度；避免分配设备给进程；实现了虚拟设备功能（可共享给多个进程）。

  1. 若S > 0，则证明没有进程在等待资源，无需唤醒。 ↩︎

  2. 阻塞的进程唤醒后将会直接进入临界区，而不是重新执行P操作，因为已经执行过了。 ↩︎