操作系统笔记清华大学陈渝

程序员文章站 2022-06-22 09:54:31

...

课程概要

基本概念及原理
操作系统介绍
中断及系统调用
内存管理
进程及线程
调度
同步
文件系统
I/O子系统

1. 基本概念

操作系统是控制软件，管理应用程序，为应用程序提供服务，杀死应用程序，分配资源，管理外设
抽象：CPU - 进程，内存 - 地址空间，磁盘 - 文件
OS分为Shell（界面）和Kernel（内核）
并发（concurrent，交替运行） vs 并行（parallel，同时运行）
实例：UNIX BSD，LINUX，WIN

2. 启动、系统调用、异常、中断

启动过程：BIOS检测外设，加载BootLoader，再由BootLoader加载OS
系统调用：应用程序向OS发出请求
异常：应用程序发生异常，需要OS处理
中断：外设发出请求
系统调用之上有API供应用程序调用：Win32 API，POSIX API（UNIX LINUX Mac OS）
CPU不同状态：用户态内核态

3. 内存管理

CPU：运算器、控制器、Register、Cache、MMU
内存管理能够实现：物理存储抽象为逻辑地址空间，保护各程序各自内存空间，程序间共享内存，虚拟化 - 暂时不用的数据移动到磁盘
程序经过编译、汇编、链接、载入对应到逻辑地址
连续内存分配、内存碎片（外碎片 - 程序之间、内碎片 - 程序之内）
首次适配、最优适配、最差适配
内存碎片整理：压缩式（移动空闲内存）、交换式（暂时不用的数据移动到磁盘）

4. 非连续内存分配

解决碎片问题，提高内存利用率
分段segment：内存块大小可变
- 内存地址表示为(segment number, offset)
- 段表：段号 - 基址，长度
分页page：内存块大小固定（帧）
- 物理地址：(frame number, offset)
- 逻辑地址：(page number, offset)
- 页表：page - frame
解决页表过大：
- TLB（Translation Lookaside Buffer）用于缓存常用地址
- 多级页表
- 反向页表：frame - page
- 反向页表的实现：页寄存器、关联内存、hash table

5. 虚拟内存

缓解内存不足
覆盖技术（overlay），常用程序模块独占常驻内存，不常用程序模块分时共享内存，但需要程序员设计覆盖关系，增加了程序设计复杂度，并且有从硬盘读写模块的开销，粒度是程序模块
交换技术（swapping），由OS执行换入换出，以程序为单位，内存可能不足时进行内存和硬盘间数据交换，粒度是程序
虚拟内存，由OS执行，程序设计需要有局部性（指令和数据访问在时间和空间上较为集中），低粒度，以页为单位，按需从硬盘调入程序和数据
有效存储访问时间（effective memory access time, EAT）
数据结构，通过页表实现：
- 驻留位（resident bit, 1表示在内存中，0表示在硬盘中）
- 保护位（设置权限，包括只读、读写、可执行等）
- 修改位（dirty bit, 数据是否被修改过，换出时是否需要写回硬盘）
- 访问位（access/used bit, 是否被访问，长时间未访问的数据在内存不足时优先被换出）
- 锁定位（lock bit, 标记需要常驻内存的数据，如OS进程和对时间敏感的进程）
算法，在页表中查找所需数据的物理地址，如存在则直接读取；如不存在，先判断是否有空余内存，如无，先换出内存上的数据（未被修改直接free，被修改过则写回硬盘），再从硬盘读取数据

6. 页面置换算法

物理内存不足时，需要换出内存中的数据
置换算法选择将哪些数据换出，目标是尽可能减少换入换出
最优页面置换算法，换出未来等待最长时间才会被访问的数据，是一种理想情况，作为其他评价其他算法的标杆
先进先出算法（FIFO），换出在内存中存在时间最长的数据，但存在时间久的数据有可能会被频繁访问，导致缺页较多，造成Belady现象
最近最久未使用算法（Least Recently Used, LRU），换出距离上一次被访问间隔时间最久的数据，缺页较少，但需要记录每个数据的访问时间，开销较大
时钟算法（Clock），在环形链表中记录frame的access bit，数据被访问时bit置为1，所有bit定期归零。发生缺页时，在环形链表中寻找access bit为0的frame，若为1则置为0，若为0则换出。相当于近似的LRU，缺页次数稍大，但节省空间
二次机会算法，改进clock，(access bit, dirty bit) :
- (1, 1) -> (0, 1) -> (0, 0)
- (1, 0) -> (0, 0)
- 换出(0, 0)，被修改过的frame换出开销大，指针经过两次才变为(0, 0)
最不常用算法（Least Frequently Used, LFU），将访问次数最少的数据换出
Belady现象，分配更多物理内存，缺页反而更多的现象，如FIFO
全局页面置换算法
- 实现全局动态分配各个程序的内存，保持平衡，效果好于局部算法
- 工作集模型，W(t, Δ)，t时刻往前Δ时间段（窗口）内，page的集合，集合size越小，程序局部性越好
- 工作集页置换算法，固定窗口大小，随着时间窗口移动，换出窗口外的页，换出最久未访问的页，限制每个程序的可用内存
- 缺页率页置换算法（Page Fault Frequency, PFF），用缺页发生的时间间隔评价缺页率，间隔短说明内存不足，加载页，间隔长说明内存过多，换出未访问的页
抖动（thrashing）,内存严重不足时，大量时间耗费在换入换出操作上，程序运行效率大大降低的现象

7. 进程

进程（Process）
- 定义：程序的一次执行过程
- 为了支持运行多个程序、多个实例而生
- 记录程序的所有状态信息，包含代码、数据、程序计数器和寄存器中存储的值、其他系统资源（文件、网络）等
- 描述进程的数据结构：进程控制块（Process Control Block， PCB），与进程一一对应
- PCB保存：
  - 进程标识（进程ID、父进程ID、用户ID）
  - 状态信息（寄存器，主要有程序计数器PC、栈指针SP）
  - 控制信息（调度、通信、存储、IO、树形结构）
- PCB实现方式：链表、索引表
- 生命周期管理：
  - 创建（源自系统、用户、进程）
  - 运行（OS调度）
  - 等待（阻塞，等待数据就绪、其他进程完成）
  - 唤醒（由OS或其他进程完成，回到就绪态）
  - 结束
- 进程（线程）状态：new、ready、running、blocked、exit
- OS对各状态分别维护队列，并按优先级区分多个队列
- 各就绪态进程分时占用CPU，OS管理时钟
- 进程挂起（suspend）：将内存中的数据换出到磁盘中；就绪或阻塞时可挂起，优先挂起阻塞进程；相反的过程：进程解挂/**（activate）
线程（Thread）
- 进程中的更小的运行单位
- 进程分配资源，实现代码、数据、文件的共享；线程将执行过程独立出来，是CPU调度单位，各线程有各自的寄存器、堆栈
- 描述线程的数据结构：线程控制块（Thread Control Block，TCB）
- 线程机制提高并发性能，但数据共享导致线程间容易发生互相干扰，安全性差。需要性能时使用线程（如科学计算），需要安全时使用进程（如浏览器）
线程实现方式：
- 用户线程，由用户线程库管理调度，自定义调度算法，OS只管理进程层面；
- 内核线程，由OS管理，粒度小，但产生用户态到内核态切换的开销，如Windows；轻量级进程，每个进程拥有多个轻量级进程，各自对应一个内核线程，如Solaris/Linux
上下文切换：停止当前进程/线程，开始其他进程/线程时，需要在PCB/TCB中保存当前线程的信息，读取下一个线程的信息，这些信息称为上下文
- 上下文具体包括：寄存器信息（程序计数器PC：程序执行阶段，栈指针SP：调用关系和局部变量位置），CPU状态
进程控制
- 创建、加载和执行进程： Windows - CreateProcess(); Linux - fork()复制进程，exec()加载新程序，取代当前进程。优化方式：vfork() 轻量级fork()，Copy On Write只复制元数据，其他数据只在写操作时进行复制
- 等待和终止进程：父进程的wait()和子进程的exit()配合完成子进程资源的回收；子进程调用exit()后，资源完成回收前的状态称为Zombie态；root进程也会定期进行资源回收

8. CPU调度

调度（Schedule），进程、线程切换
抢占，线程运行完成前被打断，OS发展：不可抢占 -> 只支持用户态抢占 -> 用户态和内核态都可抢占
CPU忙与闲（I/O操作）
调度原则：选择哪一个线程来执行？
评价指标：CPU忙时百分比、吞吐量、完成时间（从初始化到结束的时间）、等待时间（处于就绪态的总时间）、响应时间（从发起请求到第一次响应的时间）
目标：低响应时间、高吞吐量，两者很难兼顾
公平，每个进程占用同等的CPU时间，但会牺牲效率
调度算法：
- 基本调度算法
  - FCFS，First Come First Served，先来先服务，简单，等待时间波动大
  - SPN，Shortest Process Next，短进程优先 == SJF，Shortest Job First，短作业优先，不可抢占
  - SRT，Shortest Remaining Time，短剩余时间优先，可抢占；增加长进程等待时间（饥饿）；需要根据历史执行时间估算未来执行时间
  - HRRN，Highest Response Ratio Next，最高响应比优先，R=(waiting time+service time)/service time，R最高者优先；防止无限期推迟，也需要预估执行时间
  - Round Robin，轮循，按时间片轮流执行，提高公平，增加了上下文切换开销，时间片大小很重要，过大则变成FCFS，过小则切换开销太大，一般根据经验决定，使得上下文切换开销<1%
  - Multilevel Feedback Queues，多级反馈队列，将进程放置在多个队列中，高优先级队列时间片小，低优先级队列时间片大，等待时间长的任务提高优先级（I/O密集型，即前台交互任务，保证公平性），服务时间长的任务降低优先级（CPU密集型，即后台运算任务，提高效率）
  - Fair Share Scheduling，公平共享调度，用户层面的公平，适用于多用户共享服务器的场景
- 实时调度算法（嵌入式）
  - 实时系统：强调deadline，平均性能相对不重要
  - 强实时系统：重要任务在规定时间必须完成
  - 弱实时系统：重要任务优先级更高，尽量完成
  - RM，Rate Monotonic，速率单调调度，静态优先级，周期越短优先级越高
  - EDF，Earliest Deadline First，最早期限调度，动态优先级，deadline越早优先级越高
- 多处理器调度算法（多核）
  - 追求负载平衡（load balance）
- 优先级反转
  - 低优先级任务占用了某共享资源，高优先级任务不能及时执行
  - 解决优先级反转
    - 优先级继承，与高优先级任务共享资源的低优先级任务，优先级被提升
    - 优先级天花板，将资源的优先级设置为可以锁定该资源的任务的最高优先级，任务的优先级取决于所占用资源的优先级

9. 同步

解决进程间的交互产生的各种问题
为什么需要合作：共享资源、并行提高效率、模块化
如果没有同步互斥机制，则一系列指令执行中被打断，会导致结果不符合预期
需要保证任何交替执行方式都能得到正确结果，反之，则形成Race Condition 竞态条件：结果依赖于执行顺序
一些概念：
- Atomic Operation 原子操作，不可被打断的操作，要么完整执行，要么不执行，不会发生部分执行
- Critical Section 临界区，访问共享资源的代码区域
- Mutual Exclusion 互斥，保证只有一个进程处于临界区，不允许多个进程访问同一共享资源
- Dead Lock 死锁，进程之间互相等待，无法执行的情况
- Starvation 饥饿，一个进程被调度器忽略，无限期等待，无法执行
- Lock 锁，获得锁，获得控制权，释放锁，失去控制权
- Busy-waiting 忙等待，进程在等待进入临界区时，循环执行无意义操作，浪费系统资源
- Progress，希望进入临界区的进程总是能够进入临界区
互斥实现方式
- 硬件方式，禁用中断，进入临界区后禁用中断，离开后开启中断，临界区代码无法被停止，适用于临界区较小的情况，只适用于单处理器
- 软件方式，开销较大
  - 两个进程互斥，Peterson算法，解决进程 i 和进程 j 之间的互斥
    - 进入临界区
```
flag[i] = true; 
turn = j; 
while (flag[j] && turn == j);
```
      - 1
      - 2
      - 3
    - 离开临界区
```
flag[i] = false;
```
      - 1
  - 多个进程互斥，Eisenberg and McGuire算法（循环），Bakery算法（排队取号，同号比ID）
  - 需要共享数据（flag、turn），存在忙等待，需要硬件支持（原子性LOAD、STORE）
- 更高级的抽象，主流方式
  - 硬件提供原子操作指令，通过特殊的内存访问电路实现
    - Test-and-Set指令，从内存读取值，返回该值，并将内存值设为1
    - Exchange指令，交换内存中的两个值
  - 锁的实现
```
class Lock {
	int lock = 0;
}
Lock::Acquire() {
	// test-and-set
	while (test-and-set(lock));
	// exchange
	key = 1;
	while (key == 1) exchange(lock, key);
}
Lock::Release() {
	lock = 0;
}
```
    - 1
    - 2
    - 3
    - 4
    - 5
    - 6
    - 7
    - 8
    - 9
    - 10
    - 11
    - 12
    - 13
    以上是忙等版本，适用于临界区较小的情况；如果临界区较大，则加入阻塞和唤醒语句，会产生上下文切换开销
  - 优点：适用于多处理器，多进程，多临界区，简单
  - 需要考虑：忙等待，随机进入临界区导致饥饿，优先级反转

10. 信号量

信号量和管程是比锁更高级的抽象，也是同步互斥的解决方式
锁只解决了互斥，为了让多个线程进入临界区（比如只在临界区进行读操作，不必要求互斥），需要解决同步
信号量 Semaphore，Dijkstra提出
- 用一个整形（sem）表示，提供两个原子操作，P()和V()
- P()，表示有线程需要进入临界区，sem--; if (sem < 0) wait; else progress;
- V()，表示有线程离开临界区，sem++; if (sem <= 0) wakeup a thread in waiting list // sem <= 0意味着有线程在等待进入临界区，唤醒常用FIFO方式
- sem初值设为1，就相当于锁了；初值设为更大的值，可以实现条件同步
调度约束，sem初值设为0，Thread A在某处P()，Thread B在某处V()，确保Thread A在P()之后的语句一定在Thread B的V()执行之后才会开始执行
Producer - Buffer - Consumer：buffer用于存放产品，buffer大小为n；生产者向buffer中放入产品，消费者从buffer中取走产品；mutex控制同一时间只有一个生产者或消费者可以对buffer操作，fullBuffers和emptyBuffers实现buffer满时阻塞生产者、空时阻塞消费者
信号量的实现，P()和V()的实现使用禁用中断、test-and-set等原子指令，需要等待时将线程放入等待队列使之挂起
信号量的一些问题：开发难度较大，忘记释放信号量，语句顺序错误导致死锁
管程 Monitor
- 比信号量抽象程度更高的机制
- 作为编程语言的特性而诞生，用来简化并发编程，而非为OS设计
- 包含了一系列变量（锁和条件变量）和方法的模块
  - 条件变量 Condition，numWaiting表示等待队列中的线程数量，wait()使线程等待，signal()唤醒线程
- 用管程实现生产者-消费者模型
  - count表示buffer中产品的数量
  - 条件变量notFull、notEmpty表示是否为满或空的状态，notFull可以理解为okToProduce
- Hansen vs. Hoare
  - Hansen方式，signal()之后继续执行完release()再切换线程，易于实现，实际OS采用此方式
  - Hoare方式，signal()之后立刻切换线程，直观，但实现困难，教科书一般按此方式
一些经典同步问题：
- 读者 - 写者问题（读者优先，信号量实现）：
  - 读者读取数据，写者修改数据
  - 同一时间允许多个读者，或者一个写者
  - 读者优先：同时有读者和写者需要操作时，读者优先操作
  - Rcount初值为0，表示读者个数
  - 信号量CountMutex初值为1，用于对count修改的互斥
  - 信号量WriteMutex初值为1，用于读者和写者、写者之间的互斥
  - sem_wait()为P()，sem_post()为V()
- 读者 - 写者问题（写者优先，管程实现）：
  - 写者优先：只有在没有写者等待时，读者才能操作
  - signal() 只唤醒一个线程
  - broadcast() 唤醒所有线程

操作系统笔记清华大学陈渝

哲学家就餐问题
- 圆桌，5个哲学家，5个叉子，每个叉子放在两人之间，哲学家吃饭需要拿起自己左右两个叉子，吃完后放下叉子
- 基于信号量的解决方式：
  - 对每个哲学家设置状态state[5]，THINKING、HUNGRY or EATING
  - 信号量mutex，确保对state的访问是互斥的，初值为1
  - 信号量s[5]，吃完饭后唤醒邻居，进行同步，初值为0
  - 实现如下：

void philosopher(int i) { // i为哲学家编号，0-4
    while (true) {
        think();
        take_forks(i);
        eat();
        put_forks(i);
    }
}

void take_forks(int i) {
P(mutex); // 进入临界区
state[i] = HUNGRY; // 自身状态设置为饥饿
test_take_left_right_forks(i); // 试图拿叉子
V(mutex); // 退出临界区
P(s[i]); // 拿到叉子后会进行V()，这里就不会阻塞；如果没拿到叉子，就会阻塞
}

void test_take_left_right_forks(int i) {
if (state[i] == HUNGRY && // 自己饥饿，且邻居都没有在吃饭时，即有叉子可用，自己才可以吃饭
state[LEFT] != EATING &&
state[RIGHT] != EATING ) {
state[i] == EATING; // 拿到了叉子
V(s[i]); // 通知第i人可以吃饭
}
}

void put_forks(int i) {
state[i] = THINKING; // 表示放下叉子
test_take_left_right_forks(LEFT); // 看邻居能否吃饭
test_take_left_right_forks(RIGHT);
}

11. 死锁

死锁一般是由于双方各占用了资源，又需要对方占用的资源，但都不释放资源
可以用一个系统模型来描述死锁问题
资源的特征
- 某一时刻只能有一个进程使用，且不可被删除
- 一个进程获取资源，然后释放资源，以供其他进程使用
- 资源既可以是物理资源（CPU、内存、I/O通道），也可以是虚拟资源（数据结构、文件、信号量）
资源分配图 Resource Allocation Graph，一组顶点V和边E的集合
- 顶点包括进程P和资源R
- 边，请求P -> R，分配R -> P
- 例子如下，黑点表示资源个数；形成了环路，存在死锁
- 形成环路，但没有死锁
死锁出现的必要条件
- 互斥：一个资源同时只能有一个进程使用
- 持有并等待：进程持有资源，并在等待其他进程持有的资源
- 无抢占：资源只能被进程使用完后主动释放
- 循环等待：存在一个环，每个进程在等待下一个进程持有的资源
死锁解决方法，约束力度逐渐减弱；实际OS中往往选择忽略死锁问题，因为解决开销过大，影响了性能
- 死锁预防 Deadlock Prevention，改变资源申请方式，确保不出现死锁，比如对资源类型排序，进程只能按顺序申请资源，防止出现循环等待；资源利用率低，容易饥饿
- 死锁避免 Deadlock Avoidance，在进程申请资源时，判断是否会出现死锁，如果是则拒绝分配资源；要求进程声明所需资源最大数量，如果超过该数量则拒绝；还通过算法检测申请资源后是否会形成环形等待
  - 银行家算法 Banker’s Algorithm，类比客户申请贷款
  - 数据结构：
    - Max（总需求量）：n x m矩阵，n为进程数量，m为资源种类数量，Max[i, j] = k表示进程Pi最多请求k个Rj资源
    - Allocation（已分配量）：n x m矩阵，表示进程已分配的资源数量
    - Need（未来需要量）：n x m矩阵，表示进程还需要的资源数量
    - Need[i, j] = Max[i, j] - Allocation[i, j]
    - Available（剩余空闲量）：长度为m的向量，表示每种资源可用数量
  - 算法
    - 当某个进程发出对资源的请求时，假设将资源分配给它，并更新以上变量，然后进行下一步寻找安全序列
    - 找出线程执行的序列：找到一个未结束的进程，并且其Need ≤ Available，然后将其资源全部回收，更新Available，并将该进程标记为已结束；继续找下一个进程，直至所有进程都能正常结束，说明能够找出安全序列，则允许请求；如果找不到安全序列，则拒绝资源请求
- 死锁检测 Deadlock Detection，允许死锁出现，通过检测算法发现死锁并恢复
  - 等待图 wait-for graph，表示进程等待关系，判断是否存在环
  - 定期执行类似银行家算法的死锁检测，检测到死锁后执行死锁恢复
  - 开销很大，O(m x n2)，“所需资源最大数量”这一信息难以获取，所以实际很少使用，多用于OS调试
- 死锁恢复 Recovery from Deadlock
  - reboot，终止所有死锁进程，逐个终止死锁进程（先终止优先级低的、运行时间短的、占用资源多的进程）
进程间通信 Inter-Process Communication, IPC
- 概述
  - 通信模型，建立通信链路，进行操作send(message)，receive(message)
  - 直接及间接通信：直接，通过共享区域，进程间直接收发消息；间接，通过内核kernel转发，进程与消息队列之间收发消息
  - 阻塞与非阻塞：阻塞方式，同步，收发消息开始后让进程阻塞，直至通信完成；非阻塞方式，异步
  - 通信链路缓冲：收发速度不一致时提高效率，有限容量缓冲
- 信号 Signal，短小的bit，不能用于传递数据；不同的信号对应有handler，kernel发送消息给进程，并跳转到handler的stack
- 管道 Pipe，用于传递字节流，使得多个程序组合起来实现更负责的功能；shell对其子进程的输入输出重定向，串联成管道，kernel中的一个buffer
- 消息队列 Message queue，无继承关系的进程间，结构化的数据结构
- 共享内存 Shared memory，两个进程的共享区域，直接通信，快速，需要设置同步互斥；通过将同一块物理内存分别映射到两个进程的page中
- Socket机制，详见网络原理课程

12. 文件系统

文件系统：持久性存储的系统抽象
需要解决数据的组织、控制、导航、访问和检索
文件：一个单元的相关数据的在文件系统中的抽象
文件系统提供的功能：
- OS视角：管理文件块（一块数据归属于哪一个文件）、管理空闲空间、分配算法
- 用户视角：如何定位一个文件、文件名关联到文件、分层目录
- 保护，文件的“互斥”
文件元数据信息（名称、大小、修改时间等等）保存在文件头中
文件描述符，open(filename)返回的一个int值，表示已打开文件表的一个index，对应到一个文件
打开的文件需要的元数据：文件指针表示读写位置，打开计数表示打开一个文件的进程数量，为0时从文件表中移除文件，文件磁盘位置，访问权限
块（逻辑单元，比如4KB大小）< - > 扇区（物理单元），读写是以一个扇区为单位的，即使只读写一个字节
顺序访问、随机访问、基于内容访问（数据库）
OS不关心复杂的文件结构，只看做字节流
对不同用户（owner、同组用户、所有用户）设置访问权限，读、写、执行
对文件共享（多个程序都可以访问同一个文件）的支持，互斥，不同粒度的锁
目录是一张表<filename, pointer to file header> ，构成目录和文件的树形结构，hash表实现
通过路径逐级解析找到文件，通过缓存当前工作目录来加快这一过程
挂载，跨越不同的文件系统进行访问，一个目录对应一个文件系统，UNIX
文件别名，多个文件名指向同一个文件，硬链接（多个文件项，删除时减少计数，为0时才真正删除），软链接（快捷方式）
避免形成路径的循环（你中有我，我中有你）
文件系统类别，for Windows - FAT、NTFS，for UNIX - ext2/3
- 日志文件系统，用于断电后快速恢复，避免读写操作意外中断
- 分布式文件系统，基于网络，延迟 - Google，高吞吐、高容错的访问文件
- 虚拟文件系统，用文件的方式管理内核，UNIX - proc
虚拟文件系统层，屏蔽掉底层文件系统，为应用提供统一API
- 卷控制块 superblock，每个文件系统只有一个，记录文件系统信息，块、块大小、空余块
- 文件控制块 vnode，每个文件一个，文件的元数据
- 目录 dentry，每个目录一个，树形数据结构
常用数据会缓存到内存中，预先读取，延迟写入，以页为粒度缓存，减少对硬盘的读写次数
打开文件的数据结构，将被打开文件的文件控制块读入内存，放入表中，偏移量offset表示需要读写文件的何处，查找到文件对应的磁盘位置后将数据返回给程序；对文件的锁，强制或建议
对存储空间的分配，时间空间效率，类似于内存分配，页表
- 连续存储，类比数组，高效的顺序和随机访问，碎片、增长不方便，适合只读
- 链式存储，类比链表，容易增大缩小，没有碎片，不能随机访问，缺失一环会丢失信息
- 索引存储，建立索引表，容易增大缩小，没有碎片，可以随机访问，小文件冗余信息多，大文件需要扩展索引块，链式、多级
空闲空间管理，用bitmap表示，先将硬盘上的bit置为1，再分配空间，以保证一致性；也可以通过链表实现
多磁盘管理 RAID，冗余磁盘阵列，通过多磁盘提高速度、可靠性；OS实现或硬件实现
- RAID 0，将数据均匀防止在多个硬盘上，并行访问，成倍提高速度
- RAID 1，镜像硬盘，提高可靠性
- disk 1 - 4并行，disk 5 作为parity disk，存储disk 1 - 4的奇偶校验数据，1 - 4任何一个磁盘故障，可以据此恢复；将parity disk平均放置在disk 1 - 5上，平衡了读写负载，即为RAID 5
磁盘调度，在OS层面组织请求顺序，减少磁盘读写
- 在磁盘上定位数据时，先确定在哪个磁道（同心圆）上，再确定扇区，读取数据；找磁道的时间为寻道时间，占大头；目标是减少寻道时间，尽量按顺序寻道，避免磁头往复移动，
- 电梯算法，磁头走到头再回头，如此往复，类比电梯；变种C-Scan，只单方向扫描
- N-Step算法，解决“磁头粘着”（磁头在小区域内往复运动），将请求队列分成N个子队列，子队列内Scan；N为2，FSCAN，当前队列，和下一次队列

（完）

操作系统笔记 清华大学陈渝

课程概要

1. 基本概念

2. 启动、系统调用、异常、中断

3. 内存管理

4. 非连续内存分配

5. 虚拟内存

6. 页面置换算法

7. 进程

8. CPU调度

9. 同步

10. 信号量

11. 死锁

12. 文件系统