操作系统

大二下学期操作系统的复习笔记，目前已完结。

一、进程管理

1.1 基本概念

1. 进程状态：就绪、运行、阻塞（挂起）
2. 写时复制：fork 后父子进程共享物理内存，某一方修改内存后再复制
3. Jacketing：ULT 调用可能触发阻塞的系统调用前先检查资源是否准备好

1.2 进程调度

1. 调度指标：CPU利用率、吞吐量、周转/等待/响应时间（提交到完成、队列等待、提交到首次）
2. 调度算法：先来先服务 FCFS、短作业优先 SJF 指数平均预测、时间片轮转 RR、优先级调度 Aging
3. 多级反馈队列 MLFQ：从最高耗尽时间片降级，定时提升
4. 高响应比优先 HRRN：(等待 + 服务) / 服务
5. 比例公平：彩票调度、步长调度（步长 = 常数 / 票数，每次选择累计步值最小并加步长）
6. 实时调度：截止时间最近优先 EDF、短周期优先 RMS（定时触发事件）

1.3 进程互斥

1. 自旋锁：while(lock==1);
2. Peterson 算法：想进时先让对方进，对方不想进或轮到自己时再进

flag[i] = true;
turn = j;

while (flag[j] && turn == j) {
    // 等待
}

// 临界区

3. Dekker 算法：没轮到自己时撤回意愿，轮到自己再表达

flag[i] = true;

while (flag[j]) {
    if (turn == j) {
        flag[i] = false;

        while (turn == j) {
            // 等待轮到自己
        }

        flag[i] = true;
    }
}

// 临界区

turn = j;
flag[i] = false;

4. 信号量：P操作减一，若＜0则置为等待态；V操作加一，若≤0则唤醒一个等待进程
5. 生产者-消费者问题：设置产品（初值0）和缓冲区（初值1）信号量
6. 哲学家就餐问题：拿左右两个叉子，都拿左边会死锁，相邻两个不能同时就餐

二、存储管理

2.1 基本概念

1. 分区管理：首次适应、最佳适应、最坏适应（最大）、下次适应
2. 驻留集：进程实际驻留在内存中的逻辑页面集合，小于工作集时抖动 thrashing
3. 反置页表：根据进程号页号通过 Hash 加速查询系统中唯一的反置页表
4. 多级页表：分段，用第 i 段查询第 i 级页表，最后一级页表是物理页框
5. 段式管理：独立逻辑地址，内存中多段连续物理地址
6. 段页式管理：段表记录每段页表地址

2.2 页面调度

1. 最佳 Opt：不再访问、距下次访问最久
2. 最近较久未用 LRU：移位寄存器，每周期右移，选最小
3. 最不常用 LFU：次数链表
4. 先进先出 FIFO：有 Belady 异常，增加页框数反而增加缺页率
5. 一次机会 Clock：循环链表，淘汰时把扫描到的1置零，淘汰第一个0
6. 两次机会 EClock：访问和修改位，10或01置为00，11置为01

三、设备管理

3.1 基本概念

1. 编址方式：独立编址、内存映像编址、混合编址（设备控制器寄存器独立，缓存区内存映像）
2. 控制方式：轮询、中断驱动、直接内存访问 DMA（从设备直接传输至内存）
3. 通道（直接读通道程序）：字节多路（字符类，字节交叉）、选择（块）、数组多路（块，轮流）
4. I/O 软件层次：硬件、中断处理程序、设备驱动程序、独立于设备的 I/O 软件、用户程序

3.2 磁盘结构

1. 盘片、盘面、磁道，不同盘面的同一磁道组成柱面，每个磁道分为多个扇区，相邻扇区组成簇
2. 物理块地址：柱面号、磁头号（盘面号）、扇区号
3. 存取时间：柱面定位、旋转延迟、数据传送
4. 移臂调度：先来先服务 FCFS、最短定位时间优先 SSTF；单向/双向/电梯扫描
5. 旋转调度：交替排序，交叉因子为 n:1 表示相邻编号间隔 n−1 个扇区

四、文件管理

1. 卷/块：介质的物理单位；介质上连续信息所组成的一个区域（物理记录），有间隙
2. 块因子：每块中的逻辑记录数，系统缓冲区用于成组/分解
3. 文件控制块 FCB/索引节点 inode：第一个物理块 X1 地址，记录在目录中
4. 文件分配表 FAT：第 X1 项中记录第二个物理块编号 X2，表项个数等于物理块个数
5. 系统调用：进程打开文件表指向系统打开文件表项，系统打开文件表项复制目录项
6. 辅存空间管理：空闲块成组索引法，用物理块记录空闲物理块编号，头指向上一组

五、Petri 网

5.1 基本概念

1. 简单网：不存在前后集相同的不同节点
2. 单纯网：没有自环
3. 连通网：无向图连通
4. 对偶网：交换库所和变迁
5. 互逆网：流关系调转方向

5.2 基本网系统 EN

1. 定义：$(B,E;F,c_{\text{in}})$，库所、变迁、流关系、初始情态，$c_{\text{in}}$ 是库所的子集
2. 可达集 $C_{\Sigma}$：从 $c_{\text{in}}$ 开始的所有后继丛（情态）集合
3. FR($\cdot$)/RC($\cdot$)：对后继丛封闭/可达集
4. 顺序：$c[e_1\rangle c^\prime,c^\prime[e_2\rangle $，但不满足 $c[e_2\rangle $
5. 并发：情态 $c$ 同时满足 $e_1,e_2$，且 $e_1,e_2$ 外延（前后集的并）不相交，反之冲突
6. 情态 $c$ 在变迁 $b$ 有冲撞：$b$ 满足但 $b$ 的后集已有 token
7. 结构互补条件：一方前集、后集为另一方后集、前集，token 互补
8. 条件/事件系统 C/E：没有初态，所有可能状态构成完全可达情态集

5.3 库所/变迁系统 P/T

1. 定义：$(S,T;F,K,W,M_0)$，库所、变迁、流关系、库所容量函数、流关系权函数、库所初始标识，$M\leq K$ 称为标识
2. 广义权函数：不在 $S\times T$ 中的流关系权值为 0
3. 可达标识集：$[M_0\rangle$
4. 变迁序列：$\sigma=\tau_1\cdots\tau_n$，$M_n$ 称为 $\sigma$ 的后继标识，记作$M_0[\sigma\rangle M_n$
5. 活性：对任意可达集中的标识，若干步后都能满足某变迁；所有变迁都是活的则称系统 $\Sigma$ 是活的
6. 有界性：任意可达集中的标识在所有库所都不超过某常数
7. 公平性：不存在无穷变迁序列使得某变迁发生无穷次但某变迁只发生有限次
8. 出现网：库所单入单出且整个系统无环
9. 补库所：$M(s)+M(s^\prime)=K(s)$

5.4 Colored Petri Nets

1. 基本思想：结构折叠、token 编号（颜色）
2. 发生规则：变迁含有变量，变迁在某个绑定（变量赋值）下发生
3. 哲学家用餐问题