复习日志：操作系统

基本概念

• 在图形用户接口中，用于查看和操纵应用程序或文档的是对话框。对话框是人机交流的一种方式，用户对对话框进行设置，计算机就会执行相应的命令。
• 操作系统中用得最多的数据结构是树。
• 通道技术是一种硬件机制，用于管理 I/O 设备与内存之间的数据传输。通道是一种专用的处理器，可以独立于 CPU 执行 I/O 操作，从而提高系统的效率。
• 覆盖技术是一种软件机制，用于在内存有限的情况下，将程序的多个模块分批加载到内存中执行。
• 联机命令接口（Interactive Command Interface）是一种用户与操作系统交互的方式，用户可以通过输入命令来控制系统。这种接口通常用于分时系统（Time-Sharing System），因为分时系统支持多用户同时在线操作，每个用户都可以通过终端输入命令与系统交互。
• 在交互控制方式下，用户可以采用命令语言和会话语言来控制作业的执行。
• 作业可分成若干个作业步执行，作业步可由 BAT 文件、用户、作业控制说明书指定。
• 要求以作业的形式将要处理的内容提交到系统的有批处理系统和分时系统。
• 设计实时操作系统必须首先考虑系统的实时性和可靠性。
• 操作系统对终端作业采用的控制方式有联机控制和交互控制。

虚拟化

进程

• 进程有四个方面的特性，即动态性、并发性、独立性、异步性。
  • 动态性：进程的实质是进程实体的一次执行过程，进程是动态产生、动态消亡的。
  • 并发性：多个进程实体存在于同一内存中，且能在一段时间内同时运行。
  • 独立性：传统的操作系统中，进程是一个能独立运行的基本单位，同时也是系统资源分配和调度的独立单位。
  • 异步性：进程按各自独立的、不可预知的速度向前推进。
• 进程控制块
  • 进程控制块是进程实体的一部分，是操作系统中最重要的记录型数据结构。它记录了操作系统所需的、用于描述进程当前情况及控制进程运行所需的全部信息。
  • 进程控制块的作用是使一个在多道程序环境下不能独立运行的程序（含数据）成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。系统是根据进程的进程控制块感知该进程的存在的，所以进程控制块是进程存在于系统中的唯一标志。
  • 进程控制块是为系统中所有进程设置的私有数据结构，每个进程仅有一个进程控制块。

调度

• 高级调度是指作业调度，中级调度是指内存调度，低级调度是指进程调度。
• 作业：用户在一次计算过程，或者一次事务处理中，要求计算机完成所做的工作的集合.
• 作业调度（也称为高级调度或长程调度）的主要任务是按照一定的策略从后备作业队列中选择作业，将其调入内存并分配必要的资源，以便使系统中的资源得到均衡利用。作业调度会考虑作业的资源需求（如 CPU 时间、内存、I/O 设备等），并合理搭配不同类型的作业，以提高系统资源的利用率和整体性能。
  • 为了使系统中各部分资源得到均衡使用，就必须选择对资源需求不同的作业进行合理搭配，这项工作是由作业调度完成的。
• 当作业需要的所有资源都得到满足后，是从后备状态进入就绪状态。
• 中级调度：主要负责内存和外存之间的进程交换（挂起和激活），与资源均衡搭配关系不大。
• 进程调度：负责分配 CPU 时间，管理进程的执行顺序。
• 原语：原语（Primitive）是操作系统中的一种特殊操作，通常用于实现进程同步、互斥等关键功能。原语的特点是：
  • 原子性：原语操作在执行过程中不可被中断，要么全部执行完成，要么完全不执行。
  • 由若干条机器指令组成：原语通常是由多条机器指令组合而成的，这些指令共同完成一个不可分割的操作。
  • 不可中断：原语操作在执行过程中不能被其他操作打断。
• Spooling（Simultaneous Peripheral Operations On-Line，即外围设备联机操作）
  • Spooling 是一种用来提高计算机系统效率的技术，主要用于缓解慢速外设与快速处理器之间的速度差异。通过引入缓冲区和排队机制，实现设备之间的异步操作，提高资源利用率和系统吞吐量。
  • Spooling 与 Buffering 的区别：
    • Buffering（缓冲）：在设备与设备之间引入一个缓冲区，主要用于临时存储，通常是单任务环境。
    • Spooling：在缓冲区的基础上引入了队列机制，允许多个任务共享外围设备，适用于多任务环境。
  • Spooling 技术是在外存中划出一块固定区域模仿脱机 I/O，实际上是为了提高 CPU 读取外设数据的速度，减少等待时间，因此属于以空间换取时间的技术。
• 作业管理
  • 一个作业的执行过程可能会产生多个进程。
  • 批处理作业是在输入进程中等待处理的。
  • 系统现有空闲资源能满足被选作业的资源要求是选择作业进入内存的一个必要条件。
  • 在兼有批处理和分时的计算机系统中，往往把终端作业作为前台作业，把批处理作业作为后台作业。

空闲空间管理

• 在分区分配管理中采用首次适应算法时，应把空闲分区按地址递增的次序进行管理。
  • 首次适应算法（First Fit）从内存的低地址开始查找，找到第一个能满足请求的空闲分区进行分配。因此，空闲分区应按地址递增的顺序排列，以便快速找到合适的空闲分区。
• 在分区存储管理中，最佳适应算法（Best Fit）要求把空闲分区按照容量递增的次序登记在空闲分区链中。
  • 最佳适应算法的核心思想是：从所有空闲分区中找到能满足作业需求的最小空闲分区。为了实现这一目标，空闲分区需要按照容量从小到大的顺序排列（容量递增），这样在分配时可以快速找到满足条件的最小分区。
  • 优点：可以更有效地利用内存，减少大分区的浪费。
  • 缺点：可能会产生大量难以利用的小碎片。
• FIFO（First In First Out）页面置换算法是一种简单的页面置换策略，它总是淘汰最先进入内存的页面。然而，FIFO 算法存在 Belady 异常现象，即当分配的页面数（物理块数）增加时，缺页中断的次数可能会增加，而不是减少。
  • 通常情况下，增加分配的页面数会减少缺页中断的次数，因为更多的页面可以驻留在内存中，减少了页面置换的需求。
  • 但在某些情况下（如 Belady 异常），增加页面数可能会导致缺页中断次数增加，这与页面访问模式有关。
• 在分页存储管理中，页表的始址是存放在寄存器中。
  • 在分页存储管理中，页表用于记录虚拟页与物理页的映射关系。为了快速访问页表，操作系统会将页表始址存放在一个特殊的寄存器中，通常称为页表基址寄存器（Page Table Base Register，PTBR）。
• 在分段存储管理中，分配给用户的地址空间大小由用户程序的逻辑结构决定，而不是由系统或硬件决定。分段存储管理将用户程序的地址空间划分为若干个逻辑段（如代码段、数据段、堆栈段等），每个段的大小由程序的需求决定。
• 在 Linux 系统中，通常采用位图法或成组链接法来管理存储空间的分配与回收，而不是单空闲块链接法。单空闲块链接法虽然简单，但在大规模文件系统中效率较低，因此 Linux 系统并未采用这种方法。
• 在分页存储管理中，逻辑地址由页号（p）和页内地址（d）两部分组成，但这并不意味着逻辑地址空间是二维的。逻辑地址空间仍然是一维的，页号和页内地址只是逻辑地址的划分方式，用于将逻辑地址映射到物理地址。
• 在分段存储管理中，逻辑地址是二维的。分段存储管理将程序的逻辑地址空间划分为若干个段（如代码段、数据段、堆栈段等），每个段是独立的逻辑单位。逻辑地址由两部分组成：
  1. 段号（Segment Number）：表示逻辑地址属于哪个段。
  2. 段内偏移量（Offset）：表示逻辑地址在段内的具体位置。

并发

• 在多道程序环境下，并发性是指在一段时间内，宏观上有多个程序在同时执行。多道程序设计是指有多个程序同时进入内存并发运行。
• 设计多道批处理系统时，首先要考虑的是资源利用率和系统吞吐量。
• 批处理操作系统是成批地处理作业，工作效率很高，但用户一旦把作业提交给系统后，直至作业完成，用户都不能直接干预，无交互能力。
• 响应比的定义：$\text{响应比} = \frac{\text{等待时间} + \text{运行时间}}{\text{运行时间}}$。其中：
  • 等待时间：作业从到达系统到开始执行的时间。
  • 运行时间：作业的估计运行时间。
  • 一个作业 9 点到达系统，估计运行时间为 2 小时。若从 11 点开始执行该作业，其响应比为 2。
• 目态和管态
  • 中央处理器有两种工作状态：管态和目态。
  • 当中央处理器处于管态时，可执行包括特权指令在内的一切机器指令。当中央处理器处于目态时，不允许执行特权指令。
  • 操作系统程序占用中央处理器时，应让中央处理器在管态下工作，而用户程序占用中央处理器时，应让中央处理器在目态下工作。当用户程序执行访管指令时，中断装置将使中央处理器从目态转换到管态。

线程

• 在引入线程的操作系统中，线程是调度和分派的基本单位，而进程仍是资源分配的基本单位。线程本身并不拥有系统资源，而是仅有一点必不可少的、能保证独立运行的资源。

信号量

• 信号量是一种用于进程同步和互斥的低级机制，而不是进程间的通信方式。
• P 操作（Wait 操作）：当进程执行 P 操作时，信号量减一。如果信号量的值小于或等于 0，进程会被阻塞并进入阻塞状态，直到资源可用。
• V 操作（Signal 操作）：当进程执行 V 操作时，信号量加一。V 操作用于释放资源并唤醒等待该资源的进程。
• P、V 操作是两条低级的进程通信原语。
• 信号量 S<0 时，S 的绝对值表示阻塞队列中等待该资源的进程数。
• 一个正在运行的进程调用 P(S) 后，若 $S\geq 0$，说明当前的资源能满足进程的调度需求，则该进程可继续运行。
• 对于两个并发进程，设互斥信号量为 S，其初始值通常为 1，表示临界区空闲。信号量的操作规则如下：
  • 当 S > 0 时，表示临界区空闲，进程可以进入临界区，同时 S 减 1。
  • 当 S = 0 时，表示有一个进程正在临界区运行，其他进程尝试进入临界区时会被阻塞，并加入信号量的等待队列。
  • 当 S < 0 时，其绝对值表示等待队列中的进程数量。
• 生产者 - 消费者问题
  • 生产者 - 消费者问题是经典的同步问题，需要使用信号量来解决缓冲区的互斥访问和同步操作。通常需要以下 3 个信号量：
    • 互斥信号量（mutex）：
      • 用于保证生产者和消费者对缓冲区的互斥访问。
      • 初始值为 1。
    • 空闲缓冲区信号量（empty）：
      • 表示空闲缓冲区的数量。
      • 初始值为缓冲区的总大小（N）。
    • 满缓冲区信号量（full）：
      • 表示已占用缓冲区的数量。
      • 初始值为 0。 通过这 3 个信号量，可以实现生产者和消费者之间的同步和互斥：
  • 生产者在写入数据前需要获取空闲缓冲区（P(empty)）和互斥信号量（P(mutex)）。
  • 消费者在读取数据前需要获取满缓冲区（P(full)）和互斥信号量（P(mutex)）。

中断

• 处理外部中断时，程序计数器的内容由中断隐指令自动保存，操作系统保存的是通用寄存器的内容。
• 应在每一条指令执行后检测是否有中断事件。
• 中断事件是由硬件发现的，中断事件是由软件处理的。
• 缺页中断被处理后，返回到中断前产生缺页中断的指令处继续执行。

死锁

• 死锁是指因相互竞争资源并且各进程推进顺序不当，使得系统中有多个阻塞进程相互等待的现象。
• 死锁的四个必要条件是：
  • 互斥条件：资源一次只能被一个进程占用。
  • 占有并等待（请求和保持）：进程持有至少一个资源，并等待获取其他被占用的资源。
  • 不可抢占：已分配给进程的资源不能被强制剥夺，必须由进程自行释放。
  • 循环等待：存在一个进程等待的循环链，每个进程都在等待下一个进程所占用的资源。 破坏这些条件可以预防死锁，但破坏互斥条件是不现实的，因为某些资源（如打印机、文件等）本身具有独占性，无法同时被多个进程共享。如果破坏互斥条件，可能会导致资源使用冲突或数据不一致。
  • 破坏其他条件示例：
    • 请求和保持：可以通过要求进程一次性申请所有资源来破坏该条件。
    • 不可抢占：可以通过允许系统强制回收资源来破坏该条件。
    • 循环等待：可以通过资源排序等方法破坏循环等待条件。
• 在操作系统中，安全状态和死锁状态是资源分配和进程调度中的重要概念：
  • 安全状态：系统能够按照某种顺序为所有进程分配资源，并确保所有进程都能顺利完成。如果系统处于安全状态，则不会发生死锁。
  • 不安全状态：系统无法找到一种资源分配顺序，确保所有进程都能顺利完成。不安全状态可能导致死锁，但并非一定会发生死锁。
  • 死锁状态：系统已经发生死锁，进程之间相互等待资源，无法继续执行。 死锁状态与安全状态的关系：
  • 死锁状态一定是不安全状态：因为死锁发生时，系统已经无法找到一种资源分配顺序使所有进程完成。
  • 不安全状态不一定是死锁状态：不安全状态只是可能导致死锁，但通过合理的资源分配和调度，仍然可以避免死锁。
• 常见算法
  • 银行家算法：银行家算法是一种死锁避免算法，用于在资源分配时判断系统是否处于安全状态，从而避免死锁的发生。它并不能直接检测死锁，而是通过预防来避免死锁。
  • 资源分配图简化法：资源分配图是一种有向图，用于表示进程和资源之间的分配和请求关系。通过简化资源分配图（逐步移除不阻塞的进程和资源），可以检测系统中是否存在环路。如果图中存在环路，则说明系统发生了死锁。
  • 撤消进程法：撤消进程法是一种死锁解除方法，通过终止进程来解除死锁，而不是检测死锁。
  • 资源静态分配法：资源静态分配法是一种死锁预防方法，要求进程在运行前一次性申请所有资源，从而避免死锁的发生。
• 例题：若系统中有 n 个进程，则阻塞队列中的进程数最多为 n 个。
  • 如果系统处于死锁状态，则所有的进程都将进入阻塞队列，因此阻塞队列中的进程数最多为 n 个。
• 临界区（Critical Section）是指进程中访问共享资源（临界资源）的那段代码。多个进程或线程在访问临界资源时，可能会引发竞争条件（Race Condition），因此需要通过同步机制（如信号量、互斥锁等）来保证同一时刻只有一个进程或线程进入临界区。

持久性

• 虚拟存储器
  • 虚拟存储器由主存储器和联机工作的辅助存储器（通常为磁盘存储器）共同组成，这两个存储器在硬件和系统软件的共同管理下工作。
  • 虚拟存储器的实现需要程序的动态重定位技术、覆盖技术和交换技术的支持，但实现虚拟存储器应用的最主要技术是部分交换技术。
  • 虚拟存储器的容量不是无限的，最大容量受内存和外存可利用的总容量限制。
• 动态重定位技术允许目标程序不经任何改动直接装入物理内存。程序在装入内存时，其逻辑地址与物理地址的映射关系由硬件（如基址寄存器）动态维护。程序运行时，硬件会自动将逻辑地址转换为物理地址，因此目标程序无需修改即可运行。
• 逻辑地址转换物理地址
  • 页内地址 $=$ 逻辑地址 $\text{mod}$ 页面大小
  • 页号 $=$ 逻辑地址 $/$ 页面大小
  • 物理地址 $=$ 块号 $\times$ 页面大小 $+$ 页内地址
• 共享设备是可寻址和可随机访问的。常见的 I/O 设备中，典型的共享设备是磁盘。打印机、磁带机、鼠标、键盘等都是独占设备。
• 目录
  • 对于文件系统来说，文件名及属性通常可以集中在目录中，以便查询。
  • 文件系统中的目录（Directory）是一种数据结构，用于存储文件名及其对应的文件属性（如文件大小、创建时间、权限等）。目录的主要功能是：
    • 按名存取：文件目录通过将文件名与文件存储位置关联，使用户可以通过文件名快速找到并访问文件。
    • 组织文件：通过目录结构对文件进行分类和管理。
    • 快速查询：用户或程序可以通过文件名在目录中查找文件的属性和位置。
    • 管理文件属性：文件目录存储文件的元数据（如文件大小、创建时间、权限等）。
  • 例题：文件目录的主要作用是按名存取。
• 文件的顺序存储是指按照文件的逻辑顺序依次存取文件内容。文件的逻辑号是指文件中记录或数据块的逻辑顺序编号，而不是物理存储位置或其他属性。
• 文件系统分配磁盘空间时，通常以簇（Cluster）为单位进行分配。簇是文件系统管理磁盘空间的最小单位，即使文件大小小于一个簇，系统也会分配一个完整的簇。
  • 例题：某文件系统的簇和磁盘扇区大小分别为 1KB 和 512B，若一个文件的大小为 1026B，则系统分配给该文件的磁盘空间大小为 2048。
• 磁盘高速缓存（Disk Cache）是一种用于提高磁盘 I/O 性能的技术，它将磁盘中频繁访问的数据缓存到内存中，从而减少对磁盘的直接访问。磁盘高速缓存通常设置在内存中，因为内存的访问速度远高于磁盘。
• Cache：Cache 是 CPU 和内存之间的高速缓存，用于加速 CPU 对内存的访问。
• 管道（Pipe）是一种进程间通信（IPC）机制，它基于文件系统实现。管道本质上是一个特殊的文件，进程可以通过读写该文件来进行数据交换。管道的实现依赖于文件系统的支持，因此它是借助于文件系统实现的通信方式。
• 索引文件和索引顺序文件都建立了文件索引表，因此实现了随机存取。
• 磁盘驱动调度算法
  • 扫描（SCAN）算法：扫描算法（电梯算法）按照磁头的当前移动方向依次处理请求，直到到达磁盘的一端，然后反向移动。磁头移动方向不会随时改变。
  • 最短寻道时间优先（SSTF）算法：最短寻道时间优先算法总是选择离当前磁头位置最近的请求进行处理。磁头移动方向可能会随时改变。
  • 电梯调度（LOOK）算法：电梯调度算法是扫描算法的改进版本，磁头移动到最远的请求后立即反向，而不是到达磁盘的一端。磁头移动方向不会随时改变。
  • 先来先服务（FCFS）算法：先来先服务算法按照请求到达的顺序依次处理。磁头移动方向可能会随时改变。