操作系统（408考研）

进程与线程

一个进程（Process）是计算机中正在运行的程序的实例，它由以下核心组成部分构成：

PCB（Process Control Block，进程控制块）

进程ID（PID）、父进程ID（PPID）
进程状态（运行、就绪、阻塞等）

代码段（Text Segment）
数据段（Data Segment）

程序执行的实体。没有代码，进程无法运行；没有数据，代码无法处理信息。

PCB内主要有什么

进程标识信息：PID
进程状态信息：运行（Running）、就绪（Ready）、阻塞（Blocked）等
CPU上下文信息（状态）：（进程被切换时，保存当前CPU状态以便恢复）PC、SP
等

进程的状态转换

区分就绪态与阻塞态
主动/被动的转换

进程的创建

分配PID与PCB
- 操作系统为新进程分配唯一的进程ID（PID）和空的进程控制块（PCB）。
- 例子：在终端输入 ls 命令时，Shell（父进程）调用 fork() 创建子进程，内核为其分配PCB。
分配资源
- 子进程继承父进程的资源（如文件描述符、内存映射），或从操作系统申请新资源。
- 例子：子进程通过 exec() 加载 ls 程序时，需申请内存存储代码和数据。
初始化PCB
- 设置进程状态（就绪）、程序计数器（PC）、堆栈指针等。
加入就绪队列
- 新进程被放入调度队列等待CPU分配。

进程终止

终止原因：

正常终止：进程执行完毕（如 main() 返回）。
异常终止：段错误（访问非法内存）、除零错误、被 kill 命令杀死。

终止步骤：

触发终止：exit()、信号、父进程终止
释放资源：内存、文件、锁、设备等
更新 PCB：状态改为 Zombie，记录退出状态
通知父进程：父进程 wait() 或由 init 接管
删除 PCB

进程阻塞与唤醒

1. 阻塞（主动行为）

触发条件：进程主动调用阻塞操作（如 read() 等待I/O）。
过程：
1. 进程从运行态转为阻塞态，PCB加入等待队列。
2. CPU调度其他就绪进程。

2. 唤醒（被动行为）

触发条件：外部事件发生（如I/O完成、信号量释放）。
过程：
1. 内核将对应PCB从阻塞队列移到就绪队列。
2. 进程重新等待调度。

例子：

当磁盘I/O完成时，硬件触发中断，操作系统唤醒等待该I/O的进程。

易错点

阻塞是主动的，唤醒是被动的：
- 阻塞是进程主动请求等待（如调用 sleep()），而唤醒依赖外部事件（如定时器中断）。
资源泄漏：
- 终止进程时若未释放资源（如内存泄漏），会导致系统资源耗尽。
进程调度负责分配CPU资源，而非进程创建
进程调度（Process Scheduling）是操作系统内核的核心功能之一，负责从多个就绪（Ready）的进程中选择一个进程分配CPU资源，并控制进程状态的切换。其本质是解决CPU资源的分配问题，确保系统高效、公平地运行多个程序。

进程之间的通信

共享存储：原理：多个进程访问同一块内存区域，直接读写数据，速度最快（无需内核介入）。
消息传递：原理：进程通过发送/接收消息（数据包（HTTP））通信，由内核中转。
管道通信：管道是一种特殊的文件：又称pipe文件。管道不满即可发、管道不空即可收

如何理解“进程获得处理器运行是通过调度得到的”？

这句话的核心含义是：在操作系统中，进程不能直接占用 CPU，而是必须由操作系统的调度程序（Scheduler）决定哪个进程可以运行、何时运行以及运行多久。

并发程序的执行速度与调度策略的关系

并发程序的执行速度并非单纯由CPU性能决定，调度策略的合理配置（如时间片（短时间片提高响应速度，长时间片提高吞吐量。）、算法选择（FCFS适合长任务，RR适合交互式任务。））同样关键

高级调度

高级调度的核心功能是将作业从磁盘加载到内存并创建进程，因此一定会导致新进程创建

为什么分时操作系统中，就绪态的任务最多？

分时操作系统的主要目标是：公平共享CPU时间（每个任务轮流执行一小段时间）。

实时操作系统阻塞态任务最多

因为：

任务多为事件/周期驱动，大部分时间在等待触发条件。
高优先级任务抢占CPU，低优先级任务长期阻塞。
资源同步机制（如锁、信号量）强制任务阻塞等待。

线程

404
进程-资源分配的基本单位
线程-现代OS中CPU调度和分派的最小单位

系统线程 vs 用户线程

404

用系统线程：
需要真并发（如视频编码、科学计算）。
线程可能频繁阻塞（如网络服务）。
用用户线程：
轻量级任务（如快速切换的小任务）。
语言或环境限制（如Python的GIL）。

多级反馈队列调度算法

MLFQ的核心三点：

优先级队列：高优先级处理短任务，低优先级处理长任务。
动态降级：霸占CPU的任务会被“惩罚”到低优先级。
奖励交互：频繁让出CPU的任务（如I/O）保持高优先级。// 以下举例

第一轮调度：X用了5ms后发起I/O请求（如加载图片）→ 保持Q0（因为主动释放了CPU）。
第二轮调度：X从I/O返回后，仍在 Q0，继续优先执行

利用信号量实现互斥

404

利用信号量实现同步

404
通过信号量，原本异步的进程可以像齿轮一样精准咬合，实现复杂的协作逻辑！

利用信号量实现前驱关系

404

生产者-消费者问题：为什么 PV 操作顺序很重要？

（1）生产者顺序：P(empty) → P(mutex)

如果先 P(mutex) 再 P(empty)：
- 生产者拿到锁后，发现缓冲区满，会阻塞在 P(empty)。
- 但锁未释放，消费者无法消费，导致死锁。

（2）消费者顺序：P(full) → P(mutex)

如果先 P(mutex) 再 P(full)：
- 消费者拿到锁后，发现缓冲区空，会阻塞在 P(full)。
- 但锁未释放，生产者无法生产，导致死锁。

结论：同步信号量（empty/full）必须先于互斥信号量（mutex）申请，否则可能死锁。

读者-写者

为什么这是“相对”写者优先？

阻塞队列的公平性：

若读者A和写者B同时请求：读者A先执行 P(w)，成功进入。写者B执行 P(w)，被阻塞。读者A完成 V(w) 后，唤醒的是阻塞队列的队首进程（可能是另一个读者C，而非写者B）。
结果：写者B可能仍需等待多个读者完成后才能执行，因此是相对优先而非绝对优先。

管程

管程（Monitor）详解

管程（Monitor）是一种高级进程同步工具，由编程语言或操作系统提供，用于解决信号量（Semaphore）在复杂同步问题中存在的死锁风险高、代码分散等问题。其核心思想是：
将共享资源及其操作封装为一个模块，自动实现互斥访问，并通过条件变量（Condition Variables）实现灵活的进程同步。

为什么需要管程？

信号量的缺陷

PV操作分散：每个进程需自行编写PV代码，容易遗漏或顺序错误。
死锁风险高：如错误嵌套PV操作（如先 P(mutex) 再 P(empty)）。
可维护性差：同步逻辑与业务逻辑混杂，代码难以理解。

管程的优势

内置互斥：管程的过程（函数）自动保证互斥执行（同一时间仅一个进程进入管程）。
条件变量：通过 wait() 和 signal() 实现进程阻塞与唤醒，避免忙等待。
代码模块化：同步逻辑集中在管程内，业务逻辑更清晰。

管程的组成

管程的定义包含以下4部分：

组成部分	说明
① 管程名称	例如 `monitor Demo`。
② 共享数据结构	描述资源的抽象数据（如缓冲区、计数器等）。
③ 操作共享数据的函数	提供对资源的访问接口（如 `take_away()`、`give_back()`）。
④ 同步工具	如条件变量、互斥锁

示例代码

monitor Demo                  // ① 管程名称
    shared int S;             // ② 共享数据结构（资源计数器）
    condition not_empty;      // 条件变量（用于同步）

    procedure take_away() {   // ③ 操作过程1：申请资源
        if (S <= 0) wait(not_empty);  // 资源不足时阻塞
        S--;                  // 占用资源
    }

    procedure give_back() {   // ③ 操作过程2：释放资源
        S++;                  // 释放资源
        signal(not_empty);    // 唤醒等待的进程
    }

    init_code() { S = 5; }    // ④ 初始化资源数为5
end monitor

管程的核心机制

（1）互斥访问

管程的过程（如 take_away()）自动互斥执行：
当一个进程进入管程时，其他进程必须等待其退出后才能进入。

（2）条件变量（Condition Variables）

操作	作用
`wait(c)`	当前进程阻塞在条件变量 `c` 上，并释放管程的互斥锁。
`signal(c)`	唤醒一个在条件变量 `c` 上等待的进程（若无等待进程，则不产生效果）。

关键区别：

信号量机制中的 V 操作：唤醒一个因等待该信号量而阻塞的进程，若没有阻塞进程，则信号量值加 1。
管程中的 signal 操作：若当前有进程在条件变量上阻塞，唤醒其中一个进程；若没有阻塞进程，该 signal 操作直接失效（不积累效果），而不像信号量的 V 操作那样会累积信号量值。
因此，两者的作用并不完全相同。

管程 vs. 信号量

特性	管程（Monitor）	信号量（Semaphore）
互斥实现	自动（由管程保证）	手动（显式调用 `P()`/`V()`）
同步机制	条件变量（`wait`/`signal`）	PV操作（`P()`/`V()`）
死锁风险	低（内置互斥，逻辑集中）	高（PV顺序错误易导致死锁）
代码复杂度	低（同步逻辑封装在管程内）	高（分散在各进程中）
适用场景	高级语言（如Java的`synchronized`）	底层系统编程（如操作系统内核）

经典问题：用管程实现生产者-消费者

monitor ProducerConsumer {
    int buffer[N], count = 0;
    condition not_full, not_empty;  // 两个条件变量

    procedure produce(item) {
        if (count == N) wait(not_full);  // 缓冲区满则等待
        buffer[count] = item;
        count++;
        signal(not_empty);  // 唤醒消费者
    }

    procedure consume() {
        if (count == 0) wait(not_empty);  // 缓冲区空则等待
        item = buffer[count-1];
        count--;
        signal(not_full);  // 唤醒生产者
        return item;
    }
}

优势：

生产者和消费者只需调用 produce() 和 consume()，无需关心互斥细节。
条件变量直接表达“缓冲区非空”和“缓冲区非满”的同步逻辑。

管程的局限性

语言依赖：需编程语言原生支持（如Java的 synchronized，Pascal的 monitor）。
性能开销：管程的互斥和条件变量可能比信号量更耗时。
灵活性不足：某些复杂场景（如嵌套同步）仍需结合其他机制。

管程是被进程调用的，管程是语法范围，无法创建和撤销

管程代码是固定的代码段，无法创建 / 撤销：进程只能调用管程的现有过程，而不能像创建进程一样 “生成新的管程” 或 “删除已有的管程”。

循环等待与死锁的关系解析

循环等待的定义

循环等待是指存在一组进程 ({P_1, P_2, \cdots, P_n})，其中：

(P_i) 持有的资源被 (P_{i+1}) 请求（(i=1, 2, \cdots, n-1)）。
(P_n) 持有的资源被 (P_1) 请求，形成一个闭环等待链（如图2.13）。

循环等待 ≠ 死锁

虽然循环等待是死锁的必要条件，但并非充分条件。关键区别在于：

死锁的严格条件：
所有 (P_i) 必须且只能从 (P_{i+1}) 获取资源（闭环内自给自足，无法被外部打破）。
循环等待的宽松条件：
进程可能从闭环外的其他进程获取资源（如图2.14中的 (P_K)），从而避免死锁。

举例说明

场景1：严格死锁（循环等待导致死锁）

(P_0) 持有 R1，请求 R2；
(P_1) 持有 R2，请求 R1。
结果：闭环内无外部资源可依赖，死锁必然发生。

场景2：循环等待但无死锁

(P_0) 持有 R1，请求 R2；
(P_1) 持有 R2，请求 R1 或 R3（R3被闭环外的 (P_K) 持有）。
结果：若 (P_1) 选择请求 R3，且 (P_K) 释放 R3，则 (P_1) 可继续运行，闭环被打破，无死锁。

图解对比

图2.13（死锁）	图2.14（无死锁）
闭环内资源完全自循环，无外部依赖	闭环内进程可依赖外部资源（如 (P_K)）
必然死锁	可能避免死锁

核心结论

循环等待是死锁的必要条件：所有死锁一定存在循环等待链。
但循环等待不必然导致死锁：若闭环内进程能通过外部资源解除等待，则系统仍可正常运行。
死锁的充分条件：循环等待 + 资源完全闭环分配（无外部依赖）。

实际意义

死锁检测：仅发现循环等待链时，需进一步检查资源是否全部闭环。
死锁预防：允许进程从多来源申请资源（如银行家算法），可减少死锁概率。

简单说：
循环等待就像一群人围成一圈互相讨债，但如果有人能从圈外借到钱还债，圈子就能解开；若所有人只能靠圈内人还钱，就会僵持到底（死锁）。

死锁处理三大策略详解

死锁的应对方法可分为三类，分别作用于死锁发生的不同阶段：

1. 死锁预防（Prevention）

核心思想：破坏死锁的四个必要条件中的至少一个，确保系统永远不会进入死锁状态。
实现方式：

破坏条件	方法	缺点
互斥条件	允许资源共享（如只读文件），但多数资源无法避免互斥。	适用性有限。
请求并保持	进程必须一次性申请所有资源，否则不分配（静态分配）。	资源利用率低，可能饥饿。
不可剥脱条件	若进程申请资源失败，则释放已占有的资源（回滚）。	实现复杂，开销大。
循环等待条件（所有进程都在互相等待，谁都无法继续执行，形成“循环等待”。）	强制资源按线性顺序申请（如所有进程必须先申请R1再申请R2）。	限制灵活性，可能浪费资源。

特点：严格但保守，可能降低系统吞吐量。

2. 死锁避免（Avoidance）

核心思想：动态检查资源分配状态，确保系统始终处于安全状态（即存在至少一个进程执行序列不会导致死锁）。
关键算法：

银行家算法（Banker’s Algorithm）：
1. 进程声明最大资源需求。
2. 分配资源前，模拟检查分配后系统是否仍安全。
3. 仅当安全时才分配资源。

安全状态示例：
假设系统有10个内存块：

进程A已占4，最多需7；
进程B已占2，最多需4；
剩余4块。
安全序列：B可先完成（需再2块），释放后A可完成（需再3块）。

特点：需预知进程最大需求，运行时开销大，适合资源类型少的场景。

3. 死锁检测与恢复（Detection & Recovery）

核心思想：允许死锁发生，但定期检测并解除。

（1）死锁检测

资源分配图（RAG）算法：
构建有向图（进程→资源：申请边；资源→进程：分配边），检测图中是否存在环。
时间复杂度：(O(n^2))（n为进程数）。

（2）死锁恢复

方法	操作	缺点
进程终止	终止所有死锁进程，或逐个终止直至死锁解除。	代价高，可能丢失工作。
资源抢占	强制剥夺某进程资源分配给其他进程（需解决饥饿和回滚问题）。	实现复杂，可能引发级联终止。

特点：适合对死锁容忍度高的系统（如通用操作系统）。

对比总结

策略	时机	开销	资源利用率	适用场景
预防	事前	低	低	嵌入式系统、实时系统
避免	事中（动态）	高	高	已知最大需求的批处理系统
检测与恢复	事后	中	最高	通用操作系统（如Linux、Windows）

如何选择策略？

严格实时系统：优先预防（如航空控制系统）。
高资源利用率需求：采用避免或检测（如数据库管理系统）。
通用系统：通常结合预防（部分条件）和检测（如Unix/Linux默认不预防，仅定期检测）。

关键trade-off：安全性与性能的平衡！

资源分配图（Resource Allocation Graph, RAG）判断系统是否处于死锁状态

死锁的判断是通过简化资源分配图来完成的。方法如下：

找出“可以执行完”的进程：

找出满足可立即完成条件的进程 P：它请求的资源数量小于等于系统中可用的资源数 + 已分配给某些即将完成进程的资源数。

删除满足条件的进程及其边（资源请求边和占有边）：
死锁的判断条件总结

若图最终能被完全简化（所有节点和边都消除）→ 无死锁。
若图中还有剩余节点和边，即至少存在一个环路 → 死锁发生。

循环等待条件的预防：资源有序分配法示例

核心思想

通过强制所有进程按照统一的线性顺序申请资源，破坏循环等待条件。例如，规定资源类型为R1、R2、R3时，所有进程必须按 R1 → R2 → R3 的顺序申请，禁止反向或跳跃申请。

具体示例

假设系统中有三种资源：

打印机（R1）
扫描仪（R2）
磁盘（R3）

规则：

所有进程必须按 R1 → R2 → R3 的顺序申请资源，不可逆序。

场景1：遵守顺序（无死锁）

进程A：
1. 申请打印机（R1）→ 成功。
2. 申请扫描仪（R2）→ 成功。
3. 申请磁盘（R3）→ 成功。
进程B：
1. 申请打印机（R1）→ 阻塞（因被进程A占用）。

结果：进程A完成后释放资源，进程B继续，不会形成循环等待。

场景2：违反顺序（可能死锁）

若允许无序申请：

进程X：
1. 先申请扫描仪（R2）→ 成功。
2. 再申请打印机（R1）→ 阻塞（假设被进程Y占用）。
进程Y：
1. 先申请打印机（R1）→ 成功。
2. 再申请扫描仪（R2）→ 阻塞（被进程X占用）。

结果：

进程X持有R2，等待R1；
进程Y持有R1，等待R2；
循环等待 → 死锁。

为什么有序分配能预防死锁？

打破闭环：强制线性顺序后，进程只能单向等待资源（如R1→R2→R3），无法形成“A等B，B等A”的环路。
数学证明：若有环存在，则至少有一个进程违反了申请顺序，与规则矛盾。

实际应用

数据库系统：按固定顺序锁表（如先锁表A再锁表B）。
操作系统：文件系统按层级顺序加锁。

缺点：

可能降低灵活性（如进程必须提前申请所有高序资源，即使暂时不需要）。
可能导致资源浪费（如进程A占用了R1但长时间不用，阻塞其他进程）。

总结：资源有序分配是简单有效的死锁预防手段，但需权衡效率与灵活性。

临界资源（Critical Resource）

不属于临界资源的选项：

磁盘存储介质（Disk Storage Medium）

虽然多个进程可以同时访问磁盘，但现代文件系统通常通过缓存、锁机制等方式管理并发访问，磁盘本身并非典型的临界资源。

可重入的程序代码（Reentrant Code）

可重入代码（Reentrant Code）是指可以被多个线程或进程同时调用而不会导致数据不一致或错误的代码，可以被同时访问，但不能被修改。
例如：

// 可重入函数示例（仅使用局部变量）
int add(int a, int b) {
    return a + b;  // 不依赖任何全局状态
}

共享数据段必须用可重入编码编写

PV操作的实质

P即wait操作表示等待某种资源直到可用
V即signal(S)释放资源（S++），并唤醒等待该信号量的阻塞进程。

PV 操作与系统调用的关系

PV 操作是原语（Primitive）：
原语是操作系统内核中执行时不可被中断的原子操作，属于底层机制，其实现依赖硬件支持（如测试并设置指令）。
不直接等同于系统调用：
系统调用是用户态程序请求内核服务的接口（如fork()、open()），而 PV 操作是内核用于实现进程同步的内部机制。用户程序无法直接调用 PV 操作，而是通过操作系统提供的高层同步接口（如 POSIX 信号量sem_wait()/sem_post()）间接使用。

内存管理

物理地址与逻辑地址

1. 基本概念

逻辑地址（Logical Address）
- 又称虚拟地址（Virtual Address），是程序在编译、链接后生成的地址，从进程的视角看到的地址空间。
- 特点：
  - 每个进程拥有独立的逻辑地址空间（32位系统范围：0 ~ 2³²-1）。
  - 不同进程的逻辑地址可以相同，但实际映射到不同的物理内存位置。
  - 程序员只需关注逻辑地址，无需关心物理内存如何分配。
物理地址（Physical Address）
- 是内存中实际存储单元的地址，CPU通过物理地址访问主存（RAM）。
- 特点：
  - 由操作系统和硬件（MMU）管理，对用户透明。
  - 逻辑地址必须转换为物理地址后才能访问真实数据。

2. 实例说明

场景：两个进程同时运行，均访问逻辑地址0x4000。
- 进程1的0x4000 → 物理地址0x8000（存储数据A）。
- 进程2的0x4000 → 物理地址0x12000（存储数据B）。
结果：
- 进程间完全隔离，互不影响。
- 物理内存的实际分配由操作系统管理。

6. 总结

特性	逻辑地址（虚拟地址）	物理地址
生成阶段	编译、链接时生成	运行时由MMU转换
可见性	进程可见	对进程透明
唯一性	进程内唯一，进程间可重复	全局唯一
映射机制	通过页表映射到物理内存	直接访问RAM

逻辑地址是操作系统实现多进程、虚拟内存的核心机制，而物理地址是硬件执行的真实内存访问基础。两者通过MMU和页表协同工作，既保证了安全性，又提升了灵活性。

内存保护

内存保护是操作系统的核心功能之一，通过硬件支持（如基址寄存器和限长寄存器）和操作系统协作，可以实现进程内存空间的隔离和保护。重定位寄存器用于地址转换，界地址寄存器用于越界检查，两者结合既能实现动态地址映射，又能确保内存访问的安全性。特权指令的使用进一步保证了内存保护机制不会被用户程序破坏。

内存保护的必要性

保护操作系统：防止用户进程意外或恶意地修改操作系统的代码或数据。
保护用户进程：防止一个用户进程访问或修改另一个用户进程的内存空间。
系统稳定性：避免因非法内存访问导致的程序崩溃或系统错误。

内存保护的实现方法

题目中提到了两种常见的内存保护方法：

方法1：上、下限寄存器

原理：
- 设置一对寄存器：下限寄存器和上限寄存器。
- 下限寄存器存放进程在主存中的起始物理地址（下限地址）。
- 上限寄存器存放进程在主存中的结束物理地址（上限地址）。
工作流程：
- CPU每次访问内存时，会检查访问的地址是否在下限和上限之间。
- 如果地址低于下限或高于上限，则触发越界异常，阻止访问。
优点：
- 实现简单，硬件开销小。
缺点：
- 需要为每个进程维护两个寄存器，且不支持动态地址变换（逻辑地址到物理地址的映射）。

方法2：重定位寄存器（基址寄存器）和界地址寄存器（限长寄存器）

原理：
- 重定位寄存器（基址寄存器）：存放进程的起始物理地址。
- 界地址寄存器（限长寄存器）：存放进程的最大逻辑地址（即进程的逻辑地址空间大小）。
工作流程：
1. CPU生成一个逻辑地址。
2. 硬件比较逻辑地址和界地址寄存器的值：
  - 如果逻辑地址 ≥ 界地址寄存器的值，说明越界，触发异常。
  - 如果未越界，则将逻辑地址与重定位寄存器的值相加，得到物理地址。
3. 物理地址被送交内存单元进行访问。
优点：
- 支持动态地址变换（逻辑地址到物理地址的映射）。
- 可以灵活地实现进程的内存隔离和保护。
缺点：
- 需要额外的硬件支持（基址寄存器和限长寄存器）。

特权指令与安全性

重定位寄存器和界地址寄存器的加载必须通过特权指令完成。
- 特权指令只能由操作系统内核执行，用户程序无法直接修改这些寄存器。
- 这样可以防止用户程序恶意修改内存保护机制，确保系统的安全性。
操作系统在切换进程时：
1. 保存当前进程的基址和限长寄存器值。
2. 加载新进程的基址和限长寄存器值。
3. 确保新进程只能访问自己的内存空间。

示例

假设：

进程A的逻辑地址空间为0~1000。
进程A的物理内存起始地址为2000。
基址寄存器 = 2000，限长寄存器 = 1000。

访问逻辑地址500：

比较500 < 1000，未越界。
物理地址 = 500 + 2000 = 2500。
访问物理地址2500。

访问逻辑地址1500：

比较1500 ≥ 1000，越界。
触发异常，阻止访问。

内存回收

情况1：回收区与前面的空闲分区相邻（向前合并）
特点：回收区的起始地址 = 前一个空闲分区的结束地址
操作：将回收区合并到前一个空闲分区，只修改前一分区的大小（始址不变）。

示例：

1 2	空闲分区链： [0K-100K], [150K-200K] 进程释放内存块：[100K-150K]（回收区）

回收区（100K-150K）紧邻前面的空闲分区（0K-100K）。
合并后：
[0K-150K], [150K-200K]（前一个分区大小从100K→150K）

情况2：回收区与后面的空闲分区相邻（向后合并）
特点：回收区的结束地址 = 后一个空闲分区的起始地址
操作：将回收区合并到后一个空闲分区，修改后一分区的始址和大小。

示例：

1 2	空闲分区链： [0K-100K], [200K-300K] 进程释放内存块：[150K-200K]（回收区）

回收区（150K-200K）紧邻后面的空闲分区（200K-300K）。
合并后：
[0K-100K], [150K-300K]（后一个分区始址从200K→150K，大小从100K→150K）

情况3：回收区同时与前后两个空闲分区相邻（三块合并）
特点：回收区正好填补了前后两个空闲分区之间的空隙
操作：将三个分区合并成一个，修改前一分区的大小，并删除后一分区。

示例：

1 2	空闲分区链： [0K-100K], [200K-300K] 进程释放内存块：[100K-200K]（回收区）

回收区（100K-200K）同时紧邻前面的（0K-100K）和后面的（200K-300K）空闲分区。
合并后：
[0K-300K]（前一个分区大小从100K→300K，后一个分区被删除）

情况4：回收区不与任何空闲分区相邻（独立插入）
特点：回收区既不与前一个分区相邻，也不与后一个分区相邻
操作：在空闲分区链中新建一个表项，插入到合适位置（通常按地址排序）。

示例：

1 2	空闲分区链： [0K-100K], [200K-300K] 进程释放内存块：[150K-160K]（回收区）

回收区（150K-160K）不与任何空闲块相邻。
插入后：
[0K-100K], [150K-160K], [200K-300K]（新增一个表项）

搜索-分配算法

1. 首次适应算法（First Fit）
规则：空闲分区按地址递增排列，分配时从头开始查找，选择第一个满足大小的空闲分区。

示例：

1 2	空闲分区链（按地址排序）： [0K-50K], [60K-100K], [150K-300K]

进程A请求40K：
- 检查第一个分区 [0K-50K]（大小50K ≥ 40K）→ 分配。
- 剩余 [40K-50K]（10K，假设不分割）。
进程B请求80K：
- 跳过 [40K-50K]（太小）。
- 检查 [60K-100K]（40K ≥ 80K？不满足）。
- 检查 [150K-300K]（150K ≥ 80K）→ 分配。

优点：

简单高效，查找速度快（只需找到第一个满足的）。
高地址部分保留大块内存，适合后续大作业。

缺点：

低地址容易堆积小碎片（每次分配都从低地址开始）。
分配大作业时可能需要多次遍历。

2. 邻近适应算法（Next Fit / 循环首次适应）
规则：空闲分区按地址递增排列，但从上一次分配结束的位置开始查找（类似循环队列）。

示例：

1 2	空闲分区链： [0K-50K], [60K-100K], [150K-300K]

空闲分区按地址递增排列。
分配时从上一次分配结束的位置开始查找（类似循环队列）。
如果查找到链表末尾仍未找到合适分区，则回到链表头部继续查找。

初始空闲分区链：

1	[0K-50K], [60K-100K], [150K-300K]

假设初始指针指向链表的开头（[0K-50K]）。

步骤1：进程A请求40K

从指针当前位置（[0K-50K]）开始查找：
- [0K-50K] 大小 = 50K ≥ 40K → 满足。
- 分配 [0K-40K] 给进程A，剩余 [40K-50K]（10K，假设不分割）。
- 指针移动到下一个分区 [60K-100K]（因为分配是从 [0K-50K] 完成的，下一次从它的下一个开始）。

更新后的空闲分区链：

1	[40K-50K], [60K-100K], [150K-300K]

指针位置：指向 [60K-100K]。

步骤2：进程B请求30K

从指针当前位置（[60K-100K]）开始查找：
- [60K-100K] 大小 = 40K ≥ 30K → 满足。
- 分配 [60K-90K] 给进程B，剩余 [90K-100K]（10K）。
- 指针移动到下一个分区 [150K-300K]。

更新后的空闲分区链：

1	[40K-50K], [90K-100K], [150K-300K]

指针位置：指向 [150K-300K]。

步骤3：进程C请求20K

从指针当前位置（[150K-300K]）开始查找：
- [150K-300K] 大小 = 150K ≥ 20K → 满足。
- 分配 [150K-170K] 给进程C，剩余 [170K-300K]（130K）。
- 指针移动到下一个分区，但已经是链表末尾，所以回到头部 [40K-50K]。

更新后的空闲分区链：

1	[40K-50K], [90K-100K], [170K-300K]

指针位置：指向 [40K-50K]。

3. 最佳适应算法（Best Fit）
规则：空闲分区按大小递增排列，分配时选择最小的能满足需求的分区（避免浪费大块内存）。

示例：

1 2	空闲分区链（按大小排序）： [10K-20K], [60K-100K], [150K-300K]

进程A请求15K：
- 检查 [10K-20K]（10K < 15K？不满足）。
- 检查 [60K-100K]（40K ≥ 15K）→ 分配。
- 剩余 [75K-100K]（25K）。
进程B请求10K：
- 检查 [10K-20K]（10K ≥ 10K）→ 分配。

优点：

减少大分区的浪费（尽量保留大块内存）。

缺点：

产生大量小碎片（每次分配后可能留下极小剩余块）。
查找速度慢（需要遍历所有小分区）。

4. 最坏适应算法（Worst Fit）
规则：空闲分区按大小递减排列，分配时选择最大的分区（尽量少留碎片）。

示例：

1 2	空闲分区链（按大小排序）： [150K-300K], [60K-100K], [10K-20K]

进程A请求50K：
- 检查 [150K-300K]（150K ≥ 50K）→ 分配。
- 剩余 [200K-300K]（100K）。
进程B请求20K：
- 检查 [200K-300K]（100K ≥ 20K）→ 分配。
- 剩余 [220K-300K]（80K）。

优点：

减少小碎片（尽量使用大块，剩余部分仍然较大）。

缺点：

快速消耗大分区（可能导致大作业无法分配）。
性能较差（实验证明不如首次适应）。

四种算法对比总结

算法	排序方式	分配策略	优点	缺点
首次适应	地址递增	第一个满足的分区	简单高效，保留大块内存	低地址碎片多
邻近适应	地址递增	从上次结束位置继续查找	分配更均匀	可能破坏大分区，性能较差
最佳适应	大小递增	最小的能满足的分区	减少大分区浪费	产生大量小碎片，查找慢
最坏适应	大小递减	最大的能满足的分区	减少小碎片	快速消耗大分区，性能较差

索引-分配算法

基于索引搜索的动态分区分配算法详解

在大型系统中，空闲分区链可能非常长，使用顺序搜索（如首次适应、最佳适应等）效率较低。因此，引入了 基于索引搜索的分配算法，通过 分类管理空闲分区 提高分配速度。主要包括以下三种算法：

1. 快速适应算法（Quick Fit）
核心思想

按 进程常用内存大小 预先划分多个空闲分区链（如4KB、8KB、16KB等）。
使用 索引表 记录每个大小类别的空闲链头指针。

分配过程

根据进程请求的内存大小，在索引表中找到 能容纳它的最小分区链。
从该链表中取出 第一个空闲块 分配给进程。

示例

索引表：
| 大小  | 空闲链头指针 |
|-------|-------------|
| 4KB   | → [4KB块1] → [4KB块2] |
| 8KB   | → [8KB块1] → [8KB块2] |
| 16KB  | → [16KB块1]           |

进程请求5KB：
- 查找索引表，选择 8KB链（最小能满足的）。
- 分配 [8KB块1]，剩余3KB（若系统允许分割）。

特点

优点：
- 查找速度极快（直接通过索引定位）。
- 无外部碎片（分区按固定大小分类）。
缺点：
- 回收合并复杂：需合并相邻分区，可能需重组索引表。
- 内部碎片：若进程请求大小略小于分区大小（如7KB用8KB块）。

2. 伙伴系统（Buddy System）
核心思想

所有分区大小必须是 2的幂次方（如1KB、2KB、4KB等）。
通过 分裂与合并 管理空闲块，始终保持分区对齐。

分配过程

计算满足请求的最小2^k分区（如请求5KB → 选择8KB）。
若8KB链为空，则查找更大的链（如16KB）：
- 将16KB块 分裂为两个8KB伙伴块，一个分配，另一个加入8KB链。
若16KB链仍为空，继续向上查找（如32KB）。

示例

空闲链：
| 大小 | 空闲块          |
|------|----------------|
| 8KB  | → [8KB块1]      |
| 16KB | → [16KB块1]     |

进程请求5KB：
- 选择8KB链，分配 [8KB块1]。
若8KB链为空：
- 从16KB链取出 [16KB块1]，分裂为两个8KB伙伴块：
  - 分配其中一个8KB，另一个加入8KB链。

回收过程

检查回收块的 伙伴块（相邻且大小相同）是否空闲。
- 若空闲，则合并为更大的块（如两个8KB合并为16KB），并递归检查能否继续合并。

特点

优点：
- 合并高效（仅需检查伙伴块）。
- 减少外部碎片（分区对齐）。
缺点：
- 内部碎片：请求非2^k大小时需向上取整（如5KB→8KB）。
- 分裂与合并增加开销。

3. 哈希算法（Hash Fit）
核心思想

使用 哈希表 管理空闲分区链，以分区大小为关键字。
通过哈希函数快速定位合适的分区链。

分配过程

根据请求大小计算哈希值（如hash(5KB)=链2）。
在对应哈希桶的空闲链中查找满足大小的分区。

示例

哈希表：
| 哈希桶 | 分区链                     |
|--------|---------------------------|
| 链1    | → [4KB块1] → [4KB块2]     |
| 链2    | → [8KB块1] → [8KB块2]     |
| 链3    | → [16KB块1]               |

进程请求5KB：
- hash(5KB) 指向链2（8KB），分配 [8KB块1]。

特点

优点：
- 查找速度快（接近O(1)）。
- 灵活支持非固定大小分区。
缺点：
- 哈希冲突可能降低效率。
- 合并碎片较复杂（需额外策略）。

对比总结

算法	适用场景	优点	缺点
快速适应	固定大小请求频繁	无外部碎片，分配极快	回收合并复杂，内部碎片
伙伴系统	需要高效合并的场景	外部碎片少，合并简单	内部碎片多，仅支持2^k大小
哈希算法	大小分布不均匀的系统	灵活，查找快	哈希冲突可能影响性能

连续分配 vs 非连续分配

连续分配（如上述算法）：
- 要求作业占用 连续物理内存。
- 问题：即使总空闲足够，也可能因无连续空间导致分配失败。
  
  例如：内存有1GB碎片，但无连续的1GB块，大作业无法运行。
非连续分配（分页/分段）：
- 允许作业分散存储在物理内存中。
- 优点：解决连续分配的空间浪费问题。
- 缺点：需要额外空间存储映射表（如页表），存储密度较低。

关键点

索引搜索算法 的核心是通过 分类或哈希 加速查找，适合大型系统。
伙伴系统 是折中方案，兼顾分配速度和碎片管理，但限制分区大小。
非连续分配（如分页）是解决外部碎片的终极方案，但需硬件支持。

分页内存管理

页面（Page）：进程的逻辑地址空间被划分为固定大小的块，称为页面，编号从0开始（页号）。
页框（Page Frame）：物理内存被划分为与页面大小相同的块，称为页框（或物理块），编号从0开始（页框号）。

文件管理

读取文件的过程

打开文件：把目录项（元信息）读入内存，返回文件描述符。
根据目录项里的 “存储位置”（如磁盘块号、簇号），找到文件数据在磁盘的位置；
通过文件系统缓存 / 磁盘 IO，把文件数据读入内存（按需读，不是一次性全读）；
进程通过read/write操作内存中的数据，或直接读写磁盘（取决于缓存策略）。

文件系统层次结构

以用户双击打开“工作报告.docx”文件为例，逐层拆解各层工作流程：

应用程序层（用户交互入口）

角色：用户操作的“接口”，比如 Windows 的资源管理器、Linux 的文件管理器，或者办公软件（如 WPS）。
举例：你在桌面双击“工作报告.docx”，应用程序（如 WPS）先捕获操作，识别这是“打开文件”需求，然后向“逻辑文件系统”发起请求：“我要访问名为‘工作报告.docx’的文件，获取它的内容显示给用户”。

逻辑文件系统层（需求解析与权限判断）

角色：负责“翻译”应用程序的需求，处理文件逻辑（如路径解析、权限检查），决定文件实际在哪里、能不能访问。
举例：逻辑文件系统收到请求后，先解析文件路径（比如 D:\工作文件夹\工作报告.docx），然后检查你的用户权限（是否有权限读取这个文件）。如果权限没问题，它会告诉“文件组织模块”：“需要打开 D 盘工作文件夹里的‘工作报告.docx’，按文件系统规则找到它的存储位置”。

文件组织模块层（确定物理存储方式）

角色：决定文件在硬盘上的物理组织形式（比如连续存储、索引存储、链式存储），并找到文件数据的具体位置。
举例：假设“工作报告.docx”用索引分配（类似数据库索引）存储，文件组织模块会查询“文件索引表”，找到该文件数据块在硬盘中的位置（比如硬盘的第 100 - 200 扇区），然后告诉“基本文件系统”：“数据在这些物理位置，需要读取”。

基本文件系统层（元数据与存储交互）

角色：处理文件的元数据（比如文件大小、创建时间、存储位置映射），把“物理位置”转化为硬件能理解的指令，准备和 I/O 控制交互。
举例：基本文件系统拿到“第 100 - 200 扇区”的信息后，会封装成硬盘能识别的“读取指令”（比如告诉硬盘控制器：“从 LBA 地址 100 开始，读取 100 个扇区的数据” ），然后把指令传递给“I/O 控制层”。