1. 操作系统绪论 (Introduction to Operating Systems)

概念（为什么很重要）

• 定义：操作系统（Operating System, OS）是管理和控制计算机硬件与软件资源的计算机程序。它位于硬件（Hardware）之上，所有应用软件（Application Software）之下，是两者之间的桥梁。
• 为什么重要（两大核心作用）：
  1. 资源管理器 (Resource Manager)：计算机系统由各种资源组成，如CPU、内存、硬盘、打印机等。OS的核心任务就是管理这些资源，决定哪个程序可以使用哪个资源、使用多久、以何种方式使用。这解决了资源分配的效率和公平性问题。没有OS，多个程序同时运行时会因争抢资源而一片混乱。
  2. 提供虚拟机 (Virtual Machine / Extended Machine)：OS向用户和应用程序隐藏了底层硬件的复杂性。它提供了一个更简单、更清晰、更方便的接口。例如，你不需要知道数据在硬盘的哪个磁道、哪个扇区，只需要调用open(), read(), write()等命令即可。OS为你创造了一个“虚拟机”的假象，让编程和使用计算机变得更容易。

难在哪里

操作系统的设计与实现之所以困难，主要在于它需要解决一系列相互冲突的目标：

• 效率 vs. 公平：如何既能让系统总吞吐量最大（效率），又能保证每个任务都有机会运行（公平）？例如，一直运行短任务对平均周转时间有利，但可能让长任务“饿死”。
• 并发性 (Concurrency)：多个任务在逻辑上同时运行，这带来了资源竞争和不确定性，极易产生难以复现的错误（如死锁、数据不一致）。
• 性能 vs. 安全：过多的安全检查会降低系统性能，但缺乏检查又会导致系统不稳定或被攻击。
• 硬件的复杂多样性：OS需要能适配各种不同的硬件，并为其提供统一的接口。

基本特征与主要功能

• 四大基本特征：

  1. 并发 (Concurrency)：指两个或多个事件在同一时间间隔内发生。在单核CPU上，通过快速切换实现宏观上的“同时”运行。这是OS最重要的特征。
  2. 共享 (Sharing)：系统中的资源（硬件、数据）可供内存中多个并发执行的进程共同使用。共享分为互斥共享（如打印机，一次只能一个进程用）和同时访问（如只读文件）。
  3. 虚拟 (Virtuality)：通过某种技术将一个物理实体变为若干个逻辑上的对应物。例如，虚拟内存让每个进程感觉自己拥有整个地址空间；虚拟CPU（通过分时）让每个进程感觉自己独占CPU。
  4. 异步 (Asynchronicity)：进程的执行不是一贯到底的，而是走走停停，因为等待I/O、时间片用完等原因被中断。进程的推进速度是不可预知的。

• 五大主要功能：

  1. 进程管理 (Process Management)：管理进程的创建、撤销、阻塞、唤醒、调度等。
  2. 存储器管理 (Memory Management)：管理内存的分配、回收、地址转换、内存保护和扩充。
  3. 文件管理 (File Management)：管理文件的创建、删除、读写、以及对文件和目录的访问控制。
  4. 设备管理 (Device Management)：管理所有外围设备，包括分配、回收、启动设备，并提供统一的I/O接口。
  5. 提供用户接口：如命令行接口（Shell）、图形用户界面（GUI）、系统调用（API）。

操作系统类型

1. 批处理系统 (Batch System)：用户将作业脱机提交，由操作员收集成批，然后由OS依次自动处理。优点：系统吞吐量大。缺点：无交互性，用户等待时间长。
2. 分时系统 (Time-Sharing System)：将CPU时间划分为很短的“时间片”，轮流分配给各个在线用户。优点：人机交互性好，响应及时。缺点：系统开销较大。
3. 实时系统 (Real-Time System)：必须在严格的时间限制内完成任务。特点：高可靠性、及时性。分为硬实时（必须在规定时间内完成，如导弹控制）和软实时（偶尔超时可以接受，如视频播放）。
4. 网络操作系统 (Network OS) 和 分布式操作系统 (Distributed OS)：
   • 网络OS：重点在于管理网络上的资源，用户明确知道资源在哪台计算机上。
   • 分布式OS：将多台计算机的资源统一管理，对用户透明。用户感觉就像在使用一台超级计算机。

并发与并行 (Concurrency & Parallelism)

• 并发 (Concurrency)：逻辑上同时发生。在单核CPU上，多个任务通过时间片轮转，在宏观上看起来像同时运行，但微观上任意时刻只有一个任务在执行。好比一个人同时在做饭、接电话、看孩子，他需要不断在任务间切换。
• 并行 (Parallelism)：物理上同时发生。在多核CPU上，多个任务可以真正地在不同核心上同时执行。好比三个人，一个做饭，一个接电话，一个看孩子。
• 时间计算举例： 假设有两个任务，T1需要2秒，T2需要3秒。
  • 串行执行：总时间 = 2 + 3 = 5秒。
  • 并行执行（双核CPU）：总时间 = max(2, 3) = 3秒。
  • 并发执行（单核CPU）：由于需要频繁切换，会产生额外的上下文切换开销（比如0.1秒/次）。总时间 > 2 + 3 = 5秒。并发并不能缩短总执行时间，但能提高系统的响应性和资源利用率（如一个任务在等I/O时，另一个任务可以使用CPU）。

CPU工作原理与中断

• CPU工作原理：CPU的核心是一个循环：取指 (Fetch) -> 译码 (Decode) -> 执行 (Execute)。它从内存的某个地址（由程序计数器PC指出）取出指令，分析指令要做什么，然后执行它。
• 特权级：用户态 (User Mode) 与 内核态 (Kernel Mode)
  • 内核态（特权态）：CPU可以执行所有指令，访问所有内存。操作系统内核运行在内核态。
  • 用户态（普通态）：CPU只能执行部分指令，访问受限的内存。应用程序运行在用户态。
  • 为什么需要区分？ 为了保护操作系统内核和硬件不被应用程序恶意或无意地破坏。
• 中断 (Interrupt)：中断是改变CPU正常执行流程的事件。它是实现OS功能的核心机制，也是从用户态切换到内核态的唯一途径。
  • 中断处理流程：
    1. 中断发生：一个事件（如I/O完成、时钟到时、程序出错）发生。
    2. 保存现场：CPU立即停止当前指令，将当前进程的上下文（PC、寄存tors等）保存到内存（通常是进程的内核栈）中。
    3. 切换到内核态。
    4. 查找中断处理程序：根据中断类型，在中断向量表中找到对应的处理程序地址。
    5. 执行中断处理程序：处理该事件。
    6. 恢复现场：将之前保存的上下文恢复到CPU寄存器中。
    7. 返回：从内核态切换回用户态，继续执行被中断的程序。
  • 中断类型：
    • 外中断 (External Interrupt)：来自CPU外部，如I/O设备完成、时钟中断。
    • 内中断 (Internal Interrupt / Exception)：来自CPU内部，如除以零、地址越界、缺页。
    • 软件中断 (Software Interrupt)：由程序执行特定指令（如int或syscall）主动引发，这就是系统调用。

系统调用 (System Call)

• 概念：系统调用是应用程序请求操作系统内核提供服务的接口。它是应用程序进入内核的唯一合法途径。
• 为什么需要？ 因为应用程序运行在用户态，无法直接执行高特权指令（如I/O操作）。它必须请求运行在内核态的OS来代为完成。
• 过程：
  1. 用户程序准备参数，并调用一个库函数（如C语言的printf）。
  2. 库函数将系统调用号和参数放入指定寄存器。
  3. 库函数执行一个特殊的陷入指令 (Trap instruction)，如syscall。
  4. CPU捕获该指令，发生软件中断，切换到内核态。
  5. 内核根据系统调用号，在系统调用表中找到对应的内核函数并执行。
  6. 内核函数执行完毕，将结果返回。
  7. 切换回用户态，用户程序继续执行。

内核重编译

• 为什么需要？
  1. 添加新功能：如支持新的文件系统或网络协议。
  2. 支持新硬件：将新硬件的驱动程序编译进内核。
  3. 系统裁剪：移除不需要的功能，减小内核体积，提高性能和安全性。
  4. 参数调优：修改内核的某些默认参数以适应特定应用场景。
• 基本步骤 (以Linux为例)：
  1. make menuconfig: 打开一个图形化菜单，选择需要编译进内核的模块和功能。
  2. make: 编译内核和模块。
  3. make modules_install: 安装内核模块。
  4. make install: 将新的内核映像和相关文件安装到/boot目录，并更新引导加载程序（如GRUB）。
  5. reboot: 重启系统，选择新内核启动。

2. 进程管理 (Process Management)

概念

• 程序 vs. 进程：
  • 程序 (Program)：是静态的，存放在磁盘上的可执行文件，是一系列指令的集合。
  • 进程 (Process)：是动态的，是程序的一次执行过程。它是系统进行资源分配和调度的基本单位。
• 进程的组成：一个进程实体包括程序段、数据段、进程控制块 (PCB)。
  • PCB (Process Control Block)：是进程存在的唯一标志。OS通过PCB来管理进程。它包含了进程的所有信息，如：进程ID、进程状态、CPU寄存器、内存指针、I/O状态等。

顺序与并发

• 顺序执行：一个程序执行完，下一个才能开始。特点：顺序性、封闭性、可再现性。
• 并发执行：多个进程在宏观上同时执行。特点：间断性、失去封闭性、不可再现性。并发执行引入了巨大的复杂性，主要是与时间相关的错误。

与时间相关的错误 (Time-Related Errors)

• 根源：并发进程对共享资源的访问顺序不确定，导致程序执行结果不可预知。
• 竞态条件 (Race Condition)：当多个进程都企图访问和操作同一个共享数据，而最终的结果取决于这些进程的执行时序时，就发生了竞态条件。
• 临界区 (Critical Section)：进程中访问共享资源的那段代码。
• 例子：两个进程同时对共享变量count（初值为5）执行count++操作。
  • count++在机器层面通常分为三步：1. load R, count；2. add R, 1；3. store R, count。
  • 可能发生的错误时序：
    1. 进程A执行load R, count (R=5)。
    2. 发生切换，进程B开始执行。
    3. 进程B执行load R, count (R=5)，add R, 1 (R=6)，store R, count (count=6)。
    4. 发生切换，进程A继续执行。
    5. 进程A执行add R, 1 (基于它之前读到的5，R=6)，store R, count (count=6)。
  • 结果：两个进程都执行了count++，但最终结果是6，而不是期望的7。这就是与时间相关的错误。

fork() 与 vfork()

这两个都是在类UNIX系统中创建新进程的系统调用。

• fork()：
  • 创建一个新的子进程，子进程是父进程的副本。
  • 内核会复制父进程的地址空间（内存数据、代码等）给子进程。现代OS使用写时复制 (Copy-On-Write, COW) 技术进行优化：一开始父子进程共享物理内存页，只有当其中一个进程试图写入时，才会真正复制该页。
  • 父进程和子进程并发执行，执行顺序不确定。
  • fork()对父进程返回子进程的PID，对子进程返回0。
• vfork()：
  • 创建一个新子进程，但不复制父进程的地址空间，而是共享它。
  • 父进程会被阻塞，直到子进程调用exec()（加载一个新程序）或_exit()（退出）。
  • 优点：非常高效，因为避免了地址空间复制。适用于创建子进程后立即执行exec()的场景。
  • 缺点：非常危险！因为子进程在exec()或_exit()之前对内存的任何修改都会影响到父进程。

进程状态及其转换

• 五状态模型：
  1. 创建态 (New)：进程正在被创建，尚未被OS接纳为可执行进程。
  2. 就绪态 (Ready)：进程已具备运行条件（分配到除CPU外的所有资源），正在等待被调度执行。
  3. 运行态 (Running)：进程正在CPU上执行。
  4. 阻塞态 (Waiting/Blocked)：进程因等待某一事件（如I/O完成、等待信号量）而暂停执行。即使给它CPU，它也无法运行。
  5. 终止态 (Terminated)：进程执行完毕或被终止，正在等待OS回收其资源。
• 状态转换图设计
  • 关键转换解释：
    • Ready -> Running：唯一转换，由进程调度程序完成。
    • Running -> Ready：通常是时间片用完或被更高优先级的进程抢占。
    • Running -> Blocked：进程主动发起的，如请求I/O。
    • Blocked -> Ready：进程等待的事件发生了（如磁盘读完数据），由中断处理程序完成。注意：不能直接从阻塞态到运行态，因为此时可能有其他进程在运行，必须先进入就绪队列等待调度。

进程调度算法

• 衡量指标：
  • 周转时间 = 完成时间 - 到达时间
  • 带权周转时间 = 周转时间 / 服务时间（实际运行时间）
  • CPU利用率、系统吞吐量、等待时间、响应时间
• 常见算法：

进程同步与互斥

• 互斥 (Mutual Exclusion)：指当一个进程进入临界区访问共享资源时，其他进程必须等待，直到该进程退出临界区。是一种特殊的同步关系。
• 同步 (Synchronization)：指多个进程在执行次序上需要进行协调，以共同完成一项任务。例如，进程A产生数据，进程B处理数据，必须先有A的产生，才有B的处理。

前驱图 (Precedence Graph)

• 用一个有向无环图（DAG）来描述进程之间的执行先后顺序。
• 例：P1 -> P2 表示P1必须在P2开始前执行完毕。如果P2和P3都依赖于P1，则图为 P1 -> P2 和 P1 -> P3。

同步的四个基本原则

为解决临界区问题，任何解决方案必须遵循以下原则：

1. 空闲让进：当临界区空闲时，允许一个等待进入的进程立即进入。
2. 忙则等待：当已有进程在临界区内时，其他试图进入的进程必须等待。
3. 有限等待：对任何一个进程的等待时间必须是有限的，不能使其“饿死”。
4. 让权等待：当进程不能进入临界区时，应立即释放CPU，防止“忙等”。

信号量 (Semaphore)

• 定义：由Dijkstra提出的同步机制。一个信号量S是一个整数，以及两个原子操作 P 和 V。

  • P(S) (荷兰语Proberen，测试)：
    1. S--
    2. 如果 S < 0，则该进程阻塞，并加入该信号量的等待队列。
  • V(S) (荷兰语Verhogen，增加)：
    1. S++
    2. 如果 S <= 0，则从该信号量的等待队列中唤醒一个进程。

• 用信号量描述同步与互斥关系：

  • 实现互斥：

    • 定义一个互斥信号量 mutex，初值为 1。
    • 伪代码：

      semaphore mutex = 1;
      
      process_i {
          ...
          P(mutex);       // 进入临界区
          // 临界区代码
          V(mutex);       // 退出临界区
          ...
      }

      解释：第一个进程执行P(mutex)后，mutex变为0，可以进入。第二个进程执行P(mutex)后，mutex变为-1，阻塞。直到第一个进程执行V(mutex)，mutex变回0，唤醒第二个进程。

  • 实现同步：

    • 定义一个同步信号量 S，初值为 0。
    • 场景：进程A执行完任务a后，进程B才能执行任务b。
    • 伪代码：

      semaphore S = 0;
      
      Process_A {
          ...
          // 执行任务a
          V(S); // 通知B，a已完成
          ...
      }
      
      Process_B {
          ...
          P(S); // 等待A的通知
          // 执行任务b
          ...
      }

      解释：如果B先执行P(S)，S变为-1，B阻塞。直到A执行完a，执行V(S)，S变为0，并唤醒B。

典型问题

• 生产者-消费者问题：

  • 关系：生产者和消费者共享一个有界缓冲区。生产者生产物品放入缓冲区，消费者从中取出。这是同步（缓冲区空/满）和互斥（访问缓冲区）的混合问题。
  • 信号量：
    • mutex = 1：用于互斥访问缓冲区。
    • empty = n（n为缓冲区大小）：表示空闲缓冲区的数量。
    • full = 0：表示已用缓冲区的数量。
  • 伪代码：

    // Producer
    P(empty);       // 等待空位
    P(mutex);       // 锁住缓冲区
    // 放入物品
    V(mutex);       // 解锁
    V(full);        // 物品数+1，通知消费者
    
    // Consumer
    P(full);        // 等待物品
    P(mutex);       // 锁住缓冲区
    // 取出物品
    V(mutex);       // 解锁
    V(empty);       // 空位数+1，通知生产者

• 哲学家就餐问题：

  • 问题描述：5个哲学家围桌而坐，每人面前一碗饭，两两之间一根筷子。哲学家需要拿到左右两边的筷子才能吃饭。
  • 核心问题：死锁。如果所有哲学家同时拿起左手边的筷子，那么他们都在等待右手边的筷子，而这个筷子永远不会被释放。
  • 解决方案（破坏死锁的四个条件之一，通常是循环等待）：
    1. 至多允许4人同时拿筷子：用一个信号量 room=4 来限制。
    2. 奇偶编号：奇数号哲学家先拿左筷再拿右筷，偶数号反之。
    3. 同时拿：用一个互斥信号量保护拿筷子的过程，使其成为原子操作。

• 读者-写者问题：

  • 关系：多个进程共享数据。读者只读，写者可读可写。
  • 要求：允许多个读者同时读；读者和写者不能同时访问；写者和写者不能同时访问。
  • 核心：如何实现读者优先或写者优先。
  • 读者优先解法：
    • rw_mutex = 1：保证写者与其他进程（读或写）互斥。
    • mutex = 1：保证对读者计数器read_count的访问互斥。
    • read_count = 0：记录当前读者数量。
  • 伪代码：

    // Writer
    P(rw_mutex);
    // 写操作
    V(rw_mutex);
    
    // Reader
    P(mutex);
    if (read_count == 0) {
        P(rw_mutex); // 第一个读者锁住，防止写者进入
    }
    read_count++;
    V(mutex);
    
    // 读操作
    
    P(mutex);
    read_count--;
    if (read_count == 0) {
        V(rw_mutex); // 最后一个读者解锁，允许写者进入
    }
    V(mutex);

• 医生与病人问题：

  • 关系：这是生产者-消费者的一个变种。病人是“产品”，医生是“消费者”。
  • 信号量：
    • patients = 0: 等待看病的病人数量，医生在此等待。
    • doctors = 1: 空闲医生的数量，病人在次等待。
    • mutex = 1: 互斥访问挂号/等待室。
  • 伪代码：

    // Patient
    P(doctors);  // 等待有空闲医生
    P(mutex);
    // 挂号
    V(mutex);
    V(patients); // 通知医生有病人来了
    // 等待看病...
    
    // Doctor
    P(patients); // 等待有病人
    P(mutex);
    // 叫号
    V(mutex);
    V(doctors);  // 医生再次空闲
    // 看病...

管程 (Monitor)

• 概念：一种比信号量更高阶的同步机制，是一种程序结构。它将共享数据和操作这些数据的过程封装在一起。
• 特点：
  1. 互斥：每次只允许一个进程在管程内执行。这是由编译器保证的，程序员无需关心。
  2. 条件变量 (Condition Variable)：管程内引入条件变量，提供wait()和signal()操作。
     • c.wait(): 调用此操作的进程阻塞，并进入该条件变量的等待队列。
     • c.signal(): 唤醒该条件变量等待队列中的一个进程。
• 优点：比信号量更易用，不易出错，因为互斥是隐式实现的。

3. 存储器管理 (Memory Management)

存储器分配与回收

基本（一次性分配）

进程运行前，必须将其全部装入内存。

• 连续分配 (Contiguous Allocation)
  • 固定分区分配：内存被预先划分为大小固定或不等的分区。
    • 优点：实现简单，无外部碎片。
    • 缺点：存在内部碎片（分配给进程的分区可能比进程实际需要的大，多余部分被浪费）。
  • 动态分区分配：根据进程的实际大小，动态地从空闲内存中划分一个分区。
    • 分配算法：
      • 首次适应 (First-Fit)：从头开始查找，找到第一个足够大的空闲分区。
      • 最佳适应 (Best-Fit)：查找所有空闲分区，选择大小与需求最接近的那个。
      • 最坏适应 (Worst-Fit)：选择最大的那个空闲分区。
    • 优点：没有内部碎片。
    • 缺点：会产生外部碎片（小空闲区散布在内存中，总和可能很大，但无法分配给任何一个需要大块内存的进程）。
  • 伙伴系统 (Buddy System)：介于固定和动态之间。内存大小为2^k，按2的幂次进行划分和合并。
    • 优点：回收和合并速度快，一定程度上减少了外部碎片。
    • 缺点：仍存在内部碎片（例如，需要20KB，但必须分配32KB）。
• 离散分配 (Non-contiguous Allocation)
  • 分页 (Paging)：
    • 思想：将逻辑地址空间划分为大小相等的页 (Page)，将物理内存划分为大小相等的帧 (Frame)。页和帧大小相同。以页为单位进行分配。
    • 优点：无外部碎片，只有少量内部碎片（在最后一个页）。分配和管理非常方便。
    • 缺点：需要硬件支持（MMU），页表本身占用内存。
  • 分段 (Segmentation)：
    • 思想：按程序的逻辑结构（如主程序段、子程序段、数据段、栈段）划分逻辑地址空间。段的长度不固定。
    • 优点：方便编程、保护和共享。
    • 缺点：会产生外部碎片。
  • 段页式 (Segmented Paging)：
    • 思想：先分段，再将每个段分页。
    • 优点：结合了分段和分页的优点，既有逻辑清晰性，又没有外部碎片。
    • 缺点：管理开销大，需要段表和页表两级映射。

逻辑地址到物理地址的映射

• 重定位：
  • 静态重定位：在程序装入时，由加载器将逻辑地址转换为物理地址。一旦装入，不能移动。
  • 动态重定位：在程序运行时，每次访问内存都由硬件（MMU, Memory Management Unit）进行地址转换。进程可以在内存中移动。这是现代OS的通用做法。
• 地址映射过程：
  • 分页：
    • 逻辑地址 = (页号 P, 页内偏移 d)
    • 1. 根据页表基址寄存器 (PTBR) 和页号 P，在内存中找到对应的页表项 (PTE)。
    • 2. 从页表项中读出物理帧号 F。
    • 3. 物理地址 = F * 帧大小 + d
  • 分段：
    • 逻辑地址 = (段号 S, 段内偏移 d)
    • 1. 根据段表基址寄存器 (STBR) 和段号 S，在内存中找到对应的段表项。
    • 2. 从段表项中读出段基址 B 和段长 L。
    • 3. 检查 d < L 是否成立（地址越界保护）。
    • 4. 物理地址 = B + d
• 页表分级：
  • 为什么？ 对于32位系统，若页大小为4KB，则一个进程的页表可能需要 2^32 / 2^12 = 2^20 个条目。若每个条目4字节，则页表本身就需要4MB。这太大了，而且需要连续存放。
  • 二级页表：将巨大的页表再进行分页。
    • 逻辑地址 = (一级页号 P1, 二级页号 P2, 页内偏移 d)
    • 1. 通过P1在外层页表中找到内层页表的地址。
    • 2. 通过P2在内层页表中找到物理帧号 F。
    • 3. 物理地址 = F * 帧大小 + d
• 访问时间与次数：
  • 无TLB：
    • 一级页表：访问一次内存（读页表项）+ 访问一次内存（读数据） = 2次内存访问。
    • 二级页表：访问外层页表 + 访问内层页表 + 访问数据 = 3次内存访问。
  • 有TLB (Translation Lookaside Buffer)：TLB是页表项的高速缓存。
    • TLB命中：直接从TLB获得帧号。总时间 = TLB访问时间 + 内存访问时间。
    • TLB未命中：需要按常规方式访问内存中的页表，并将结果存入TLB。
    • 有效访问时间 (EAT) = 命中率 * (TLB时间 + 内存时间) + (1 - 命中率) * (TLB时间 + 页表访问内存次数 * 内存时间 + 数据访问内存时间)
    • 简化公式：EAT = 命中率 * T_hit + (1 - 命中率) * T_miss

虚拟（多次分配）

进程运行时，只将部分内容装入内存。

• 概念：基于局部性原理（程序倾向于在一段时间内集中访问一小块地址空间），只把当前需要的页面/段装入内存。当访问到不在内存中的页面/段时，通过缺页/缺段中断将其从磁盘调入。
• 实现方式：请求分页、请求分段、请求段页式。
• 缺页（段）中断 (Page/Segment Fault)：
  1. CPU访问某地址，MMU发现页表项中的存在位 (Present Bit) 为0。
  2. MMU产生缺页中断，陷入内核。
  3. OS中断处理程序开始执行： a. 检查该地址是否合法。 b. 在物理内存中查找一个空闲帧。 c. 若无空闲帧，则执行置换算法，选择一个“牺牲”页。 d. 如果牺牲页是脏页 (Dirty Bit = 1)，即被修改过，则需将其写回磁盘。 e. 从磁盘读入所需的页到找到的帧中。 f. 更新页表（修改存在位、帧号等）。 g. 重新执行被中断的指令。
• 置换算法 (Replacement Algorithms)：
  • 最佳置换 (OPT)：置换未来最长时间内不会被访问的页。（理想算法，无法实现，作为衡量标准）
  • 先进先出 (FIFO)：置换最早进入内存的页。
    • 优点：实现简单。
    • 缺点：性能差，可能出现Belady异常（分配的帧数越多，缺页率反而上升）。
  • 最近最少使用 (LRU)：置换最长时间未被使用的页。
    • 优点：性能好，接近OPT。
    • 缺点：实现开销大，需要硬件支持（时间戳或维护一个栈）。
  • Clock (时钟/二次机会)算法：LRU的近似实现。
    • 机制：所有页环形成一个循环队列。每个页有一个使用位 (Use Bit)。
    • 过程：当需要置换时，指针从当前位置开始扫描。
      • 若页的Use Bit为1，则将其置为0，指针下移，给它“第二次机会”。
      • 若页的Use Bit为0，则置换该页。
• 逻辑地址到物理地址的映射：与基本分页/分段类似，但多了一个检查存在位的步骤。
• 访问时间与次数：
  • 有效访问时间 (EAT) = (1 - p) * 内存访问时间 + p * 缺页处理时间
    • p 是缺页率。
    • 缺页处理时间 非常巨大，因为它包含了磁盘I/O时间。

4. 文件系统 (File System)

文件类型、逻辑结构与物理结构

• 文件类型：普通文件、目录文件、设备文件等。
• 文件逻辑结构：用户看到的文件组织方式。
  • 流式文件：无结构，一串字符流（如C的源文件）。
  • 记录式文件：由定长或变长记录组成（如数据库文件）。
• 文件物理结构：文件在磁盘上的存放方式。
  • 连续分配 (Contiguous)：文件数据存放在连续的磁盘块中。
    • 优点：支持顺序和随机访问，速度快。
    • 缺点：外部碎片，文件大小不易扩展。
  • 链式分配 (Linked)：文件数据存放在不连续的磁盘块中，通过指针链接。
    • 优点：无外部碎片，文件易于扩展。
    • 缺点：只适合顺序访问，随机访问效率极低。指针占用额外空间，可靠性差（指针丢失则文件损坏）。
  • 索引分配 (Indexed)：为每个文件创建一个索引块，存放指向所有数据块的指针。
    • 优点：无外部碎片，支持高效的随机访问。
    • 缺点：索引块本身占用空间。文件很小时，索引块开销大。文件很大时，单个索引块可能不够用。
  • 混合索引 (UNIX/Linux inode)：结合直接和间接索引。
    • inode (索引节点)：每个文件有一个inode，包含文件的元数据（权限、大小等）和一系列指针。
    • 结构：通常包含
      • 直接块指针 (e.g., 12个)：直接指向数据块。
      • 一级间接块指针 (e.g., 1个)：指向一个存满指针的块，这些指针再指向数据块。
      • 二级间接块指针 (e.g., 1个)：指向一个间接块，该间接块再指向一批一级间接块。
      • 三级间接块指针 (e.g., 1个)：…
    • 优点：对于小文件，访问快（直接块）；对于大文件，可以支持非常大的尺寸。
• 计算文件大小和磁盘空间
  • 例题：假设磁盘块大小4KB，地址占4B。inode有10个直接指针，1个一级间接，1个二级间接。
    • 一级间接块能存多少地址？ 4KB / 4B = 1024个地址。
    • 二级间接块能索引多少数据？ 1024 * 1024 * 4KB。
    • 最大文件大小 = (10 * 4KB) + (1024 * 4KB) + (1024 * 1024 * 4KB)
  • 文件大小：指文件内容的字节数。
  • 磁盘空间：指文件内容占用的数据块 + 索引块所占用的空间。

磁盘调度算法（移臂调度）

• 目标：减少磁头臂的移动距离，从而减少寻道时间 (Seek Time)。
• 算法：(假设磁道请求序列: 98, 183, 37, 122, 14, 124, 65, 67，当前磁头在53)
  • FCFS：按请求顺序服务。移动路径: 53 -> 98 -> 183 -> 37 -> 122 -> 14 -> 124 -> 65 -> 67。移动距离大。
  • SSTF (最短寻道时间优先)：选择与当前磁头位置最近的请求。路径: 53 -> 65 -> 67 -> 37 -> 14 -> 98 -> 122 -> 124 -> 183。可能导致“饥饿”。
  • SCAN (电梯算法)：磁头在一个方向上移动，服务所有请求，到达磁盘末端后反向。假设从53向0移动：53 -> 37 -> 14 -> 0(到达末端) -> 65 -> 67 -> 98 -> 122 -> 124 -> 183。对两端的请求不公平。
  • C-SCAN (循环扫描)：磁头在一个方向上移动到末端，然后立即返回到起始端，再开始服务。路径：53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199(末端) -> 0(返回) -> 14 -> 37。等待时间更均匀。

不同物理结构对应的访问磁盘次数

假设要访问文件的第i个逻辑块，并且目录和索引块均未缓存。

• 连续文件：
  1. 读目录文件，找到文件的起始块号b。 (1次访盘)
  2. 访问第i个数据块，其地址为 b+i-1。 (1次访盘)
  • 总共：2次访盘。
• 链式文件：
  1. 读目录文件，找到文件的第一块地址。 (1次访盘)
  2. 从第一块顺序读到第i-1块，以获得第i块的指针。(i-1次访盘)
  3. 访问第i块。(1次访盘)
  • 总共：i+1次访盘。效率极低。
• 索引文件 (单级)：
  1. 读目录文件，找到索引块的地址。 (1次访盘)
  2. 读索引块，找到第i个条目，获得数据块地址。(1次访盘)
  3. 读第i个数据块。(1次访盘)
  • 总共：3次访盘。
• 索引文件 (多级，如inode)：
  • 访问直接块：读inode(1次) + 读数据块(1次) = 2次。
  • 访问一级间接块中的数据：读inode(1次) + 读一级间接块(1次) + 读数据块(1次) = 3次。
  • 访问二级间接块中的数据：读inode(1次) + 读二级间接块(1次) + 读一级间接块(1次) + 读数据块(1次) = 4次。
  • 注意：通常文件打开后，inode会被读入内存缓存。如果这样假设，上述访盘次数可以减1。考试时要看清题目条件。

5. 设备管理 (Device Management)

基本概念

• I/O设备：按信息交换单位可分为块设备（如硬盘，可寻址）和字符设备（如键盘，不可寻址）。
• 设备控制器：硬件，负责控制一个或多个设备，提供与CPU的接口。
• I/O控制方式：程序直接控制 -> 中断驱动 -> DMA -> 通道。
  • DMA (Direct Memory Access)：允许设备控制器直接与内存交换数据，不占用CPU，只在开始和结束时中断CPU。极大提高了I/O效率。

缓冲 (Buffering)

• 为什么需要？
  1. 缓和CPU与I/O设备的速度矛盾。
  2. 减少对CPU的中断频率。
  3. 解决数据粒度不匹配的问题（如块设备与字符设备间）。
• 类型和实现机制：
  • 单缓冲：在内核中设置一个缓冲区。输入时，设备数据 -> 缓冲区，然后CPU从缓冲区 -> 用户区。反之亦然。
  • 双缓冲：设置两个缓冲区。当设备向缓冲区1输入时，CPU可以从缓冲区2取数据，两者可以并行。
  • 循环缓冲：将多个缓冲区组织成环形队列，常用于生产者-消费者模式。
• 时间计算：
  • 设一个数据块从设备输入到缓冲区时间为 T，CPU处理（从缓冲区拷贝到用户区并计算）时间为 C。
  • 无缓冲：系统处理一块数据的时间 = T + C。
  • 单缓冲：系统处理一块数据的时间 = max(T, C)。因为当CPU在处理时，设备可以开始向缓冲区输入下一块数据（部分重叠）。
  • 双缓冲：CPU处理缓冲区1的数据时，设备可以完全向缓冲区2输入数据。系统处理一块数据的时间 = max(T, C)。双缓冲比单缓冲的优势在于，它能让CPU和设备更充分地并行。
  • 例：T=10s, C=8s。
    • 无缓冲：18s/块。
    • 单/双缓冲：max(10, 8) = 10s/块。
  • 例：T=8s, C=10s。
    • 无缓冲：18s/块。
    • 单/双缓冲：max(8, 10) = 10s/块。

设备驱动程序 (Device Driver)

• 概念：是I/O系统核心与设备控制器之间的通信和转换模块。
• 功能：
  1. 接收上层（设备无关软件）的抽象I/O请求（如read）。
  2. 将其转换为对设备控制器的具体操作（如向控制器寄存器写入命令）。
  3. 管理设备状态，处理设备中断。
  4. 向上层返回操作结果。
• 位置：它是操作系统内核的一部分，但通常是可加载的模块。每个设备类型都有其特定的驱动程序。它隐藏了设备的物理细节，为上层提供了统一的接口。