第1章 操作系统概论

1.Linux中硬件资源

中央处理器、内存、外存、输入/输出设备

2.操作系统五大功能

• 处理器管理：进程控制、进程调度、同步互斥、进程通信
• 存储器管理：内存分配、地址映射、内存保护、虚拟存储
• 设备管理：I/O 控制、设备分配、缓冲管理、虚拟设备
• 文件管理：存储空间管理、目录管理、读写控制、共享与保护
• 用户接口：程序接口（系统调用）、操作接口（命令 / 图形界面）

3.操作系统四大核心特性

• 并发性：同一时间间隔内多个程序交替执行，是操作系统最基本的特征。
• 共享性：系统资源可被多个并发进程共同使用，分为互斥共享、同时共享。
• 虚拟性：把一个物理实体虚拟为多个逻辑实体，分为时分复用（CPU 虚拟化）、空分复用（内存虚拟化）。
• 异步性：进程推进速度不可预知，但只要运行环境相同，执行结果就可再现

4. 内核、进程、线程 基础概念

• 内核：操作系统最核心的部分，运行在核心态，负责管理内存、进程、设备等核心资源，向上提供系统调用。
• 进程：程序在数据集合上的一次运行过程，是资源分配的独立单位。
• 线程：进程内部的执行单元，是CPU 调度的基本单位，共享进程的地址空间与资源，切换开销远小于进程。

5. Linux 常用命令（实验高频）

• 目录 / 文件：cd、ls、pwd、mkdir、rm、cp、mv、cat、chmod
• 进程管理：ps、kill、top
• 编译调试：gcc、make、gdb
• 系统查询：uname、man、df

第2章 处理器管理

1.中断机制

（1）中断概念

CPU 暂停当前程序，转去处理突发的硬件 / 软件事件，处理完成后返回原程序继续执行的机制，是操作系统并发的基础。

（对CPU来讲中断是改变CPU原来固有的执行顺序）

（2）中断分类

• 外中断（硬件中断）：CPU 外部设备触发，如 I/O 中断、时钟中断。分为可屏蔽中断、不可屏蔽中断。
• 内中断（异常）：CPU 内部指令执行出错触发，如缺页、地址越界、系统调用、算术溢出。

（3）中断处理完整过程

中断请求 → 中断判优 → 中断响应（关中断、保存断点） → 中断处理 → 中断返回（恢复现场、开中断）

2. 特权指令与非特权指令

• 特权指令：只能在核心态执行的指令，如 I/O 指令、内存管理指令、关中断指令。普通用户态不能直接执行。
• 非特权指令：用户态可安全执行的指令，如算术运算、普通访存指令。
• 注：用户态执行特权指令会触发异常，陷入内核态，由操作系统代为执行。

3.寄存器分类

• 通用寄存器：存放运算数据与中间结果
• 程序计数器（PC）：存放下一条指令的内存地址
• 指令寄存器（IR）：存放当前正在执行的指令
• 程序状态字寄存器（PSW）：存放程序运行状态（中断允许位、条件码、特权模式位）
• 地址寄存器：如内存地址寄存器 MAR、数据寄存器 MDR

4. 处理器状态及转换

两种状态

• 用户态（目态）：只能执行非特权指令，访问受限资源
• 核心态（管态）：可执行全部指令，访问所有硬件与内存

状态转换

• 用户态 → 核心态：唯一途径是中断 / 异常 / 系统调用（访管指令），由硬件自动完成
• 核心态 → 用户态：执行中断返回指令，或提供一条特权指令称为加载程序状态字指令，用来实现由管理状态向用户状态或原状态的转换

5. 进程的 6 点属性

1. 动态性：有从创建到消亡的生命周期，是最基本特征
2. 并发性：多个进程可同时驻留内存并发执行
3. 独立性：是资源分配和调度的独立单位
4. 异步性：推进速度不可预知，但结果可再现
5. 结构性：由程序段、数据段、PCB 三部分组成
6. 制约性：因资源竞争和同步关系产生运行制约

6. 进程三态模型 + 进程上下文

三态模型

• 就绪态：获得除 CPU 外的所有资源，等待调度
• 运行态：占有 CPU 正在执行
• 阻塞态（等待态）：等待某事件发生，暂时无法运行
• 

状态转换：

• 就绪 → 运行：调度程序选中，分配 CPU
• 运行 → 就绪：时间片用完、或高优先级进程抢占
• 运行 → 阻塞：等待 I/O、等待信号（主动进入）
• 阻塞 → 就绪：等待的事件发生（被动唤醒）

进程上下文

指：进程物理实体和支持进程运行的环境

进程执行时的全部环境信息，包括 CPU 寄存器值、地址空间内容、内核栈、PCB 状态信息。进程切换时必须保存旧进程上下文、加载新进程上下文。

7. 模式切换流程

1. 触发中断 / 异常 / 系统调用，CPU 自动关中断
2. 硬件保存用户态的 PC、PSW 到内核栈
3. 切换为核心态，加载内核栈指针
4. 保存通用寄存器等现场到内核栈
5. 执行内核中断服务程序
6. 处理完成后，恢复用户态寄存器现场
7. 执行中断返回指令，恢复用户态 PC、PSW

8. 进程与线程的区别

1. 进程是“容器”（资源分配的最小单位），线程是“工人”（CPU 调度的最小单位）。

2. 进程拥有独立的资源（安全但切换慢），线程共享进程的资源（不安全但切换快、通信方便）。

9. 三级调度

1. 高级调度（作业调度）：从外存选作业调入内存、创建进程。频率最低，批处理系统才有。
2. 中级调度（对换调度）：将暂时不运行的进程换出外存（挂起），内存空闲时再换入。用于缓解内存压力。
3. 低级调度（进程调度）：从就绪队列选进程分配 CPU。频率最高，所有操作系统都有。

10. 调度算法（计算 + 画图）

1. 周转时间 = 完成时间 - 到达时间（衡量一个任务从提交到结束的总耗时）

2. 带权周转时间 = 周转时间 / 运行时间（这个值越大，说明它在系统里“磨蹭”得越久）

3. 等待时间 = 开始运行时间 - 到达时间（不包含运行时间，只算排队的时间）

4. 响应时间：从提交请求到首次产生响应的时间（交互系统最看重这个）

非剥夺式（非抢占）:

一个进程占用CPU后，除非它自己运行结束或主动放弃（如等待I/O），否则谁也别想把它赶下来。（包含FCFS，非抢占式SJF，HRRN）

剥夺式（抢占）：

个进程正在运行，如果来了个更紧急（或时间片到了）的进程，操作系统强行暂停当前进程，把CPU让给新来的。（包含时间片轮转（RR），抢占式SJF（SRTN），抢占式优先级）

FCFS算法画图：

解;

第3章 并发进程的同步、互斥与死锁

1. 并发的概念

并发：同一时间间隔内，多个程序在单 CPU 上交替执行，宏观上同时运行，微观上分时推进。 区分：并行是同一时刻在多核 CPU 上真正同时运行。

2. 同步与互斥的概念

• 互斥：多个进程竞争临界资源时，同一时间只能有一个进程进入临界区。
• 同步：多个协作进程按指定的先后顺序执行，如生产者生产完成后消费者才能消费。

3. Peterson 算法（软件实现互斥）

算法思想

双进程互斥，用两个标志位表示进程是否想进入临界区，用turn变量表示当前轮到谁。满足空闲让进、忙则等待、有限等待，存在忙等。

// 全局共享变量
boolean flag[2] = {false, false};  // flag[i]=true 表示进程i想进入临界区
int turn = 0;                       // 表示当前轮到哪个进程

// 进程 Pi (i=0或1, j为另一个进程)
do {
    flag[i] = true;      // 标记自己想进入临界区
    turn = j;            // 谦让，让对方先
    // 对方想进入 且 轮到对方，则循环等待
    while (flag[j] && turn == j) ;
    
    /* ===== 临界区 ===== */
    
    flag[i] = false;     // 退出临界区，取消标记
    
    /* ===== 剩余区 ===== */
} while (true);

4. TS 指令（Test-and-Set，硬件实现互斥）

算法思想

硬件原子指令，不可中断，测试并设置锁变量。实现简单，单 / 多处理器均适用，存在忙等。

// 硬件原子指令，执行全程不可中断
boolean TS(boolean *lock) {
    boolean old = *lock;
    *lock = true;
    return old;
}

// 进程使用TS实现互斥
do {
    while (TS(&lock)) ;  // 锁为true则循环等待
    
    /* ===== 临界区 ===== */
    
    lock = false;        // 退出临界区，释放锁
    
    /* ===== 剩余区 ===== */
} while (true);

5. PV 操作（信号量机制）

信号量定义

信号量是一个整型变量，只能通过P、V 两个原子原语操作。

• P 操作（wait）：S 值减 1，若结果 < 0，当前进程阻塞并加入等待队列。
• V 操作（signal）：S 值加 1，若结果≤0，唤醒等待队列中的一个进程。

// P操作原语
void P(semaphore S) {
    S.value--;
    if (S.value < 0) {
        block(S.queue);  // 当前进程阻塞，加入等待队列
    }
}

// V操作原语
void V(semaphore S) {
    S.value++;
    if (S.value <= 0) {
        wakeup(S.queue); // 从等待队列唤醒一个进程
    }
}

6. 生产者 - 消费者问题

问题描述

n 个生产者往大小为 k 的缓冲区放产品，m 个消费者从缓冲区取产品；缓冲区满不能生产，缓冲区空不能消费。

semaphore mutex = 1;    // 缓冲区互斥访问
semaphore empty = k;    // 空缓冲区数量，初值为缓冲区大小
semaphore full = 0;     // 满缓冲区数量，初值为0

// 生产者进程
void producer() {
    while (true) {
        生产一个产品;
        P(empty);       // 申请空缓冲区
        P(mutex);       // 进入临界区
        
        将产品放入缓冲区;
        
        V(mutex);       // 退出临界区
        V(full);        // 满缓冲区数量+1
    }
}

// 消费者进程
void consumer() {
    while (true) {
        P(full);        // 申请满缓冲区
        P(mutex);       // 进入临界区
        
        从缓冲区取出产品;
        
        V(mutex);       // 退出临界区
        V(empty);       // 空缓冲区数量+1
        消费产品;
    }
}

7. 哲学家进餐问题

问题描述

5 位哲学家围坐圆桌，每人左右各一根筷子。哲学家思考，饿了拿左右两根筷子吃饭，吃完放下继续思考。若所有人同时拿左筷子会发生死锁。

semaphore chopstick[5] = {1,1,1,1,1};  // 5根筷子
semaphore count = 4;                    // 最多4人同时尝试拿筷

void philosopher(int i) {
    while (true) {
        思考;
        P(count);              // 申请就餐名额
        P(chopstick[i]);       // 拿左筷子
        P(chopstick[(i+1)%5]); // 拿右筷子
        
        吃饭;
        
        V(chopstick[i]);       // 放左筷子
        V(chopstick[(i+1)%5]); // 放右筷子
        V(count);              // 释放名额
    }
}

8. 管程的概念与属性

概念

管程是高级同步机制，将共享数据和操作封装在一起，自动实现入口互斥，进程只能通过管程的过程访问共享资源。

属性

1. 封装性：内部数据外部不可见，只能通过管程过程访问
2. 互斥性：同一时间只能有一个进程进入管程
3. 条件变量：提供wait/signal操作，条件不满足时进程等待
4. 安全性：同步逻辑由管程保证，避免用户编程错误

9. 进程通信

概念

进程之间的信息交换称为进程通信（IPC）。

通信机制分类

• 直接通信：进程直接指定对方，如send(P, msg)、receive(Q, msg)
• 间接通信：通过共享信箱 / 消息队列收发，不需要知道对方身份

Linux 常见通信方式

低级通信：信号量、信号 高级通信：管道、共享内存、消息队列、套接字

10. 死锁

概念

多个进程因竞争资源形成互相等待的僵局，若无外力作用，都无法向前推进。

四个必要条件

1. 互斥条件：资源一次只能被一个进程使用
2. 请求与保持：进程持有资源，同时申请新资源
3. 不剥夺条件：进程持有的资源不能被强行夺走
4. 循环等待：进程间形成资源等待的循环链

死锁预防（防止死锁）

破坏四个必要条件之一：

• 破坏请求与保持：进程一次性申请全部资源
• 破坏不剥夺：申请资源失败时释放已占资源
• 破坏循环等待：资源按序号有序分配

第 4 章 存储管理

1. 地址重定位

将程序的逻辑地址转换为内存物理地址的过程。

• 静态重定位：程序装入时一次性完成转换，运行中不再改变。无需硬件支持，但程序不能移动。
• 动态重定位：程序执行时才转换，靠地址变换机构实现。支持程序移动、虚拟存储，需要硬件支持。

2. 分页存储管理

基本结构

• 内存划分为大小相等的物理块（页框），程序逻辑地址划分为大小相等的页。
• 逻辑地址结构：页号 + 页内偏移量
• 页表：每个进程一张，记录「页号 → 物理块号」的映射。

地址变换过程伪代码

输入：逻辑地址 addr，页面大小 size，页表基址 base
1. 页号 P = addr / size   （整数除法）
2. 页内偏移 d = addr % size
3. 若 P 超过页表长度 → 触发地址越界中断
4. 物理块号 F = 页表[base + P]
5. 物理地址 = F * size + d

3. 快表（TLB，联想寄存器）

• 概念：高速缓存中存放最近访问的页表项，利用局部性原理加速地址变换。
• 流程：先查快表，命中则直接得到物理块号；未命中再查内存页表，并更新快表。
• 作用：大幅减少访存次数，提升地址变换速度。

4. 分段存储管理

基本结构

按程序逻辑功能划分段（代码段、数据段、栈段等），段长不固定。

• 逻辑地址结构：段号 + 段内偏移量
• 段表：每个进程一张，记录段号、段基址、段长。

地址变换过程

1. 拆分逻辑地址得到段号 S 和段内偏移 d
2. 查段表得到段基址和段长
3. 若 d > 段长 → 触发越界中断
4. 物理地址 = 段基址 + d

5. 分页与分段的对比

分页 = 机器强行把程序切成等大的“块”（解决内存利用率）

分段 = 按程序逻辑切成不同功能的“段”（解决编程需求）

1. 分页有内碎片，无外碎片；分段有外碎片，无内碎片。

2. 分页地址是一维的，分段地址是二维的。

3. 分段比分页更容易实现代码共享和保护。