操作系统学习笔记-精简复习版

操作系统

概述

1、操作系统

• 操作系统（Operating System，简称 OS）是管理计算机硬件与软件资源的程序，是计算机的基石。

• 操作系统本质上是一个运行在计算机上的软件程序，是最底层的系统软件。

• 操作系统存在屏蔽了硬件层的复杂性。

• 操作系统的内核（Kernel）是操作系统的核心部分，内核是连接软件和硬件的桥梁，决定着系统的性能和稳定性，内核功能一般包括进程管理、内存管理、设备管理、文件管理、网络管理等。

2、主要功能

进程和线程的管理：进程的创建、撤销、阻塞、唤醒，进程间的通信等。

存储管理：内存的分配和管理、外存（磁盘等）的分配和管理等。

文件管理：文件的读、写、创建及删除等。

设备管理：完成设备（输入输出设备和外部存储设备等）的请求或释放，以及设备启动等功能。

网络管理：操作系统需要管理计算机网络的配置、连接、通信和安全等，以提供高效可靠的网络服务。

安全管理：系统用户的身份认证、访问控制、文件加密等，以防止非法用户对系统资源的访问和操作。

3、用户态和内核态

用户态和内核态的概念

• 用户态(User Mode) : 用户态运行的进程可以直接读取用户程序的数据，拥有较低的权限。当应用程序需要执行某些需要特殊权限的操作，例如读写磁盘、网络通信等，就需要向操作系统发起系统调用请求，进入内核态。

• 内核态(Kernel Mode)：内核态运行的进程几乎可以访问计算机的任何资源包括系统的内存空间、设备、驱动程序等，不受限制，拥有非常高的权限。当操作系统接收到进程的系统调用请求时，就会从用户态切换到内核态，执行相应的系统调用，并将结果返回给进程，最后再从内核态切换回用户态。

用户态与内核态的切换需要付出较高的开销（需要进行一系列的上下文切换和权限检查），应该尽量减少进入内核态的次数，以提高系统的性能和稳定性。

用户态和内核态的切换

• 系统调用（Trap）：用户态进程 主动 要求切换到内核态的一种方式，主要是为了使用内核态才能做的事情比如读取磁盘资源。系统调用的机制其核心还是使用了操作系统为用户特别开放的一个中断来实现。

• 中断（Interrupt）：当外围设备完成用户请求的操作后，会向 CPU 发出相应的中断信号，这时 CPU 会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序，如果先前执行的指令是用户态下的程序，那么这个转换的过程自然也就发生了由用户态到内核态的切换。比如硬盘读写操作完成，系统会切换到硬盘读写的中断处理程序中执行后续操作等。

• 异常（Exception）：当 CPU 在执行运行在用户态下的程序时，发生了某些事先不可知的异常，这时会触发由当前运行进程切换到处理此异常的内核相关程序中，也就转到了内核态，比如缺页异常。

4、系统调用

我们运行的用户程序中，凡是与系统态级别的资源有关的操作（如文件管理、进程控制、内存管理等)，都必须通过系统调用方式向操作系统提出服务请求，并由操作系统代为完成。

这些系统调用按功能大致可分为如下几类：

• 设备管理：完成设备（输入输出设备和外部存储设备等）的请求或释放，以及设备启动等功能。
• 文件管理：完成文件的读、写、创建及删除等功能。
• 进程管理：进程的创建、撤销、阻塞、唤醒，进程间的通信等功能。
• 内存管理：完成内存的分配、回收以及获取作业占用内存区大小及地址等功能。

系统调用和普通库函数调用非常相似，只是系统调用由操作系统内核提供，运行于内核态，而普通的库函数调用由函数库或用户自己提供，运行于用户态。

系统调用的过程可以简单分为以下几个步骤

1. 用户态的程序发起系统调用，因为系统调用中涉及一些特权指令（只能由操作系统内核态执行的指令），用户态程序权限不足，因此会中断执行，也就是 Trap（Trap 是一种中断）。
2. 发生中断后，当前 CPU 执行的程序会中断，跳转到中断处理程序。内核程序开始执行，也就是开始处理系统调用。
3. 内核处理完成后，主动触发 Trap，这样会再次发生中断，切换回用户态工作。

为什么系统调用耗时？

在用户态和内核态切换时，需要先保存现场，即保存用户态的寄存器等，然后去执行系统调用，最后恢复现场。

进程管理

1、进程和线程

进程（Process） 是指计算机中正在运行的一个程序实例。举例：你打开的微信就是一个进程。

线程（Thread） 也被称为轻量级进程，更加轻量。多个线程可以在同一个进程中同时执行，并且共享进程的资源比如内存空间、文件句柄、网络连接等。举例：你打开的微信里就有一个线程专门用来拉取别人发你的最新的消息。

以JVM的内存区域为视角，看一下进程和线程的区别

从上图可以看出：一个进程中可以有多个线程，多个线程共享进程的堆和方法区 (JDK1.8 之后的元空间)资源，但是每个线程有自己的程序计数器、虚拟机栈和本地方法栈。

总结：

• 进程是资源分配的基本单位，线程是处理机调度执行的基本单位
• 进程有独立的地址空间和程序代码等资源，切换开销较大；线程共享同一进程的地址空间和程序代码等资源，切换开销小（进程虚拟地址空间切换后导致页表也要切换，进而导致Cache失效，命中率降低，虚拟地址转换为物理地址就会变慢，而线程无需切换地址空间）
• 进程可以包含多个线程，但是一个线程只能属于一个进程

2、引入线程的好处

• 进程切换是一个开销很大的操作，线程切换的成本较低。
• 线程更轻量，一个进程可以创建多个线程。
• 多个线程可以并发处理不同的任务，更有效地利用了多处理器和多核计算机。而进程只能在一个时间干一件事，如果在执行过程中遇到阻塞问题比如 IO 阻塞就会挂起直到结果返回。
• 同一进程内的线程共享内存和文件，因此它们之间相互通信无须调用内核。

3、线程间同步

线程同步是两个或多个共享关键资源的线程的并发执行。应该同步线程以避免关键的资源使用冲突。

常见线程同步方式有：

• 互斥锁(Mutex)：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。比如 Java 中的 synchronized 关键词和各种 Lock 都是这种机制。

• 读写锁（Read-Write Lock）：允许多个线程同时读取共享资源，但只有一个线程可以对共享资源进行写操作。

• 信号量(Semaphore)：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量。

• 屏障（Barrier）：屏障是一种同步原语，用于等待多个线程到达某个点再一起继续执行。当一个线程到达屏障时，它会停止执行并等待其他线程到达屏障，直到所有线程都到达屏障后，它们才会一起继续执行。比如 Java 中的 CyclicBarrier 是这种机制。

• 事件(Event) :Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作。

4、进程控制块 PCB

PCB，Process Control Block 进程控制块，是操作系统用来管理和跟踪进程的数据结构，每个进程都有一个独立的 PCB。

包含了进程的各种信息，比如

• 进程的描述信息，名称、标识符等
• 进程的调度信息，包括进程的状态，优先级，阻塞原因等
• 进程对资源的需求情况，包括CPU时间，内存空间，IO设备等
• 进程打开的文件信息，包括文件描述符、文件类型、打开模式等
• 处理机的状态信息（由处理机的各种寄存器中的内容组成的），包括通用寄存器、指令计数器、程序状态字 PSW、用户栈指针

5、进程的状态

创建状态(new)：进程正在被创建，尚未到就绪状态。

就绪状态(ready)：进程已处于准备运行状态，即进程获得了除了处理器之外的一切所需资源，一旦得到处理器资源(处理器分配的时间片)即可运行。

运行状态(running)：进程正在处理器上运行(单核 CPU 下任意时刻只有一个进程处于运行状态)。

阻塞状态(waiting)：又称为等待状态，进程正在等待某一事件而暂停运行如等待某资源为可用或等待 IO 操作完成。即使处理器空闲，该进程也不能运行。

结束状态(terminated)：进程正在从系统中消失。可能是进程正常结束或其他原因中断退出运行。

6、进程的通信方式

1、管道/匿名管道(Pipes)：用于具有亲缘关系的父子进程间或者兄弟进程之间的通信。

2、有名管道(Named Pipes) : 匿名管道由于没有名字，只能用于亲缘关系的进程间通信。为了克服这个缺点，提出了有名管道。有名管道严格遵循 先进先出(First In First Out) 。有名管道以磁盘文件的方式存在，可以实现本机任意两个进程通信。

3、信号(Signal)：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生；

4、消息队列(Message Queuing)：消息队列是消息的链表,具有特定的格式,存放在内存中并由消息队列标识符标识。管道和消息队列的通信数据都是先进先出的原则。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点

5、信号量(Semaphores)：信号量是一个计数器，用于多进程对共享数据的访问，信号量的意图在于进程间同步。这种通信方式主要用于解决与同步相关的问题并避免竞争条件。

6、共享内存(Shared memory)：使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据的更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等。可以说这是最有用的进程间通信方式。

7、套接字(Sockets): 此方法主要用于在客户端和服务器之间通过网络进行通信。套接字是支持 TCP/IP 的网络通信的基本操作单元，可以看做是不同主机之间的进程进行双向通信的端点，简单的说就是通信的两方的一种约定，用套接字中的相关函数来完成通信过程。

7、进程的调度算法

先到先服务调度算法(FCFS，First Come, First Served) : 从就绪队列中选择一个最先进入该队列的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。

短作业优先的调度算法(SJF，Shortest Job First) : 从就绪队列中选出一个估计运行时间最短的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。

时间片轮转调度算法（RR，Round-Robin） : 时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。

多级反馈队列调度算法（MFQ，Multi-level Feedback Queue）：前面介绍的几种进程调度的算法都有一定的局限性。如短进程优先的调度算法，仅照顾了短进程而忽略了长进程 。多级反馈队列调度算法既能使高优先级的作业得到响应又能使短作业（进程）迅速完成。，因而它是目前被公认的一种较好的进程调度算法，UNIX 操作系统采取的便是这种调度算法。

优先级调度算法（Priority）：为每个进程分配优先级，首先执行具有最高优先级的进程，依此类推。具有相同优先级的进程以 FCFS 方式执行。可以根据内存要求，时间要求或任何其他资源要求来确定优先级。

8、僵尸进程&孤儿进程

在 Unix/Linux 系统中，子进程通常是通过 fork()系统调用创建的，该调用会创建一个新的进程，该进程是原有进程的一个副本。子进程和父进程的运行是相互独立的，它们各自拥有自己的 PCB，即使父进程结束了，子进程仍然可以继续运行。当一个进程调用 exit()系统调用结束自己的生命时，内核会释放该进程的所有资源，包括打开的文件、占用的内存等，但是该进程对应的 PCB 依然存在于系统中。这些信息只有在父进程调用 wait()或 waitpid()系统调用时才会被释放，以便让父进程得到子进程的状态信息。

僵尸进程：子进程已经终止，但是其父进程仍在运行，且父进程没有调用 wait()或 waitpid()等系统调用来获取子进程的状态信息，释放子进程占用的资源，导致子进程的 PCB 依然存在于系统中，但无法被进一步使用。这种情况下，子进程被称为“僵尸进程”。避免僵尸进程的产生，父进程需要及时调用 wait()或 waitpid()系统调用来回收子进程。

孤儿进程：一个进程的父进程已经终止或者不存在，但是该进程仍在运行。这种情况下，该进程就是孤儿进程。孤儿进程通常是由于父进程意外终止或未及时调用 wait()或 waitpid()等系统调用来回收子进程导致的。为了避免孤儿进程占用系统资源，操作系统会将孤儿进程的父进程设置为 init 进程（进程号为 1），由 init 进程来回收孤儿进程的资源。

9、死锁

DeadLock：多个进程/线程同时被阻塞，其中的一个或者全部都在等待某个资源被释放，由于被无限期阻塞，导致程序不能正常终止。

产生死锁的必要条件

• 互斥：资源必须为互斥模式，即一次只有一个进程可以使用。如果另一进程申请该资源，那么必须等待直到该资源被释放为止
• 占有并等待：一个进程至少应该占有一个资源， 并等待另一个资源，而该资源被其他进程所占有
• 不可抢占：资源不能被抢占，只能在持有资源的进程完成任务后，该资源才会被释放
• 循环等待：有一组等待的进程{P0、P1、、、Pn}，P0等待的资源被P1占有，P1等待的资源被P2占有，，Pn等待的资源被P0占有。

最简单的代码示例

package fengluo.idea;/*** @Author: fengluo* @Date: 2023/9/17 1:02*/
public class Test {private static final Object resource1 = new Object();private static final Object resource2 = new Object();public static void main(String[] args) {new Thread(() -> {synchronized (resource1) {System.out.println(Thread.currentThread().getName() + "拿到资源1");try {Thread.sleep(1000);System.out.println(Thread.currentThread().getName() + "想拿到资源2，等待中");synchronized (resource2) {System.out.println(Thread.currentThread().getName() + "拿到资源2");}} catch (InterruptedException e) {throw new RuntimeException(e);}}}, "线程A").start();new Thread(() -> {synchronized (resource2) {System.out.println(Thread.currentThread().getName() + "拿到资源2");try {Thread.sleep(1000);System.out.println(Thread.currentThread().getName() + "想拿到资源1，等待中");synchronized (resource1) {System.out.println(Thread.currentThread().getName() + "拿到资源1");}} catch (InterruptedException e) {throw new RuntimeException(e);}}}, "线程B").start();}}

死锁的预防

想要预防死锁，只需要破坏某一个必要条件，使之不成立即可。

• 破坏互斥条件，是最简单的方法，但是很多资源往往必须是互斥的
• 破环占有并等待，通过静态分配策略，在进程执行之前就申请到他所需要的全部资源，并且需要其所有的资源都得到满足之后才开始执行，不会出现占有某个资源并等待另一个资源的情况，会导致资源利用率下降。
• 破坏不可抢占，采用剥夺式调度算法，只适合主存资源和CPU资源的分配，并不适用与所有资源，会导致资源利用率下降。
• 破坏循环等待条件，通过层次分配策略，所有的资源都被分成了多个层次，一个进程得到某一次的一个资源后，它只能再申请较高一层的资源；当一个进程要释放某层的一个资源时，必须先释放所占用的较高层的资源，按这种策略，是不可能出现循环等待链的，因为那样的话，就出现了已经申请了较高层的资源，反而去申请了较低层的资源，不符合层次分配策略，也降低了资源利用率

死锁的避免

银行家算法：当一个进程申请使用资源的时候，银行家算法 通过先 试探 分配给该进程资源，然后通过 安全性算法 判断分配后系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待，若能够进入到安全的状态，则就 真的分配资源给该进程。改善了 资源使用率低的问题 ，但是它要不断地检测每个进程对各类资源的占用和申请情况，以及做 安全性检查 ，需要花费较多的时间。

死锁的检测

通过进程资源分配图，是描述了进程和资源申请及分配关系的一种有向图，用于检测系统是否处于死锁状态。

死锁的解除

当死锁检测程序检测到存在死锁发生时，应设法让其解除，让系统从死锁状态中恢复过来，常用的解除死锁的方法有以下四种：

• 立即结束所有进程的执行，重新启动操作系统：这种方法简单，但以前所在的工作全部作废，损失很大。

• 撤销涉及死锁的所有进程，解除死锁后继续运行：这种方法能彻底打破死锁的循环等待条件，但将付出很大代价，例如有些进程可能已经计算了行时还要再次进行计算。

• 逐个撤销涉及死锁的进程，回收其资源直至死锁解除。

• 抢占资源：从涉及死锁的一个或几个进程中抢占资源，把夺得的资源再分配给涉及死锁的进程直至死锁解除。

内存管理

内存管理包含了内存的分配与回收、地址转换、内存扩充、内存映射、内存优化、内存安全等

1、内存碎片

内存碎片是由内存的申请和释放产生的，通常分为下面两种：

内部内存碎片(Internal Memory Fragmentation，简称为内部碎片)：已经分配给进程使用但未被使用的内存。

外部内存碎片(External Memory Fragmentation，简称为外部碎片)：部内存碎片指的是那些并未分配给进程但又不能使用的内存。

2、内存管理

• 连续内存管理：为一个用户程序分配一个连续的内存空间，内存利用率一般不高。
• 非连续内存管理：允许一个程序使用的内存分布在离散或者说不相邻的内存中，相对更加灵活一些。

3、虚拟内存

虚拟内存(Virtual Memory) 是计算机系统内存管理非常重要的一个技术，本质上来说它只是逻辑存在的，是一个假想出来的内存空间，主要作用是作为进程访问主存（物理内存）的桥梁并简化内存管理。

• 隔离进程：进程之间彼此隔离，每个进程对应各自独立的虚拟地址空间，对于进程来说都认为自己拥有了独立的物理内存，提供了系统的安全性
• 提升物理内存利用率：通过虚拟地址空间，操作系统只需要将进程当前正在使用的部分数据或指令加载到物理内存
• 简化内存管理：程序员不用和物理内存打交道，而是通过虚拟地址空间访问物理内存，从而简化了内存管理
• 多个进程共享物理内存：进程在运行过程中，会加载许多操作系统的动态库，这些库对于每个进程来说都是公用的，在内存中实际只会加载一份，这部分称之为共享内存
• 提供更大的内存空间：可以让程序拥有超过系统物理内存大小的可用内存空间，当物理内存不够用时，利用磁盘充当，将物理内存页（通常为4KB）保存到磁盘文件，可以根据需要在物理内存与磁盘之间移动

4、分段机制

分段机制（Segmentation） 以段(—段 连续 的物理内存)的形式管理/分配物理内存。应用程序的虚拟地址空间被分为大小不等的段，段是有实际意义的，每个段定义了一组逻辑信息，例如有主程序段 MAIN、子程序段 X、数据段 D 及栈段 S 等。

分段管理通过 段表（Segment Table） 映射虚拟地址和物理地址。

分段机制下的虚拟地址由两部分组成：

• 段号：标识着该虚拟地址属于整个虚拟地址空间中的哪一个段。
• 段内偏移量：相对于该段起始地址的偏移量。

地址转换过程如下：

1. MMU 首先解析得到虚拟地址中的段号；
2. 通过段号去该应用程序的段表中取出对应的段信息（找到对应的段表项）；
3. 从段信息中取出该段的起始地址（物理地址）加上虚拟地址中的段内偏移量得到最终的物理地址。

分段机制容易出现外部内存碎片，即在段与段之间留下碎片空间(不足以映射给虚拟地址空间中的段)。从而造成物理内存资源利用率的降低。

5、分页机制

分页机制（Paging） 把主存（物理内存）分为连续等长的物理页，应用程序的虚拟地址空间划也被分为连续等长的虚拟页。现代操作系统广泛采用分页机制。页是连续等长的，不同于分段机制下不同长度的段。

在分页机制下，应用程序虚拟地址空间中的任意虚拟页可以被映射到物理内存中的任意物理页上，因此可以实现物理内存资源的离散分配。分页机制按照固定页大小分配物理内存，使得物理内存资源易于管理，可有效避免分段机制中外部内存碎片的问题。

每个应用程序都有一个对应的页表

分页机制下的虚拟地址由两个部分组成

• 页号：通过虚拟页号可以从页表中取出对应的物理页号
• 页内偏移量：物理页起始地址 + 页内偏移量 = 物理内存地址

地址转换过程如下：

1. MMU 首先解析得到虚拟地址中的虚拟页号；
2. 通过虚拟页号去该应用程序的页表中取出对应的物理页号（找到对应的页表项）；
3. 用该物理页号对应的物理页起始地址（物理地址）加上虚拟地址中的页内偏移量得到最终的物理地址。

多级页表：属于时间换空间的典型场景，利用增加页表查询的次数减少页表占用的空间。

TLB：快表，相当于一个缓存

页面置换算法

• 最佳页面置换算法（OPT，Optimal）：优先选择淘汰的页面是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若干页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现，只是理论最优的页面置换算法，可以作为衡量其他置换算法优劣的标准。

• 先进先出页面置换算法（FIFO，First In First Out） : 最简单的一种页面置换算法，总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面进行淘汰。该算法易于实现和理解，一般只需要通过一个 FIFO 队列即可需求。不过，它的性能并不是很好。

• 最近最久未使用页面置换算法（LRU ，Least Recently Used）：LRU 算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 T，当须淘汰一个页面时，选择现有页面中其 T 值最大的，即最近最久未使用的页面予以淘汰。LRU 算法是根据各页之前的访问情况来实现，因此是易于实现的。OPT 算法是根据各页未来的访问情况来实现，因此是不可实现的。

• 最少使用页面置换算法（LFU，Least Frequently Used） : 和 LRU 算法比较像，不过该置换算法选择的是之前一段时间内使用最少的页面作为淘汰页。

• 时钟页面置换算法（Clock）：可以认为是一种最近未使用算法，即逐出的页面都是最近没有使用的那个。

6、段页式机制

结合了段式管理和页式管理的一种内存管理机制，把物理内存先分成若干段，每个段又继续分成若干大小相等的页。

在段页式机制下，地址翻译的过程分为两个步骤：

1. 段式地址映射。
2. 页式地址映射。

7、局部性原理

局部性原理是指在程序执行过程中，数据和指令的访问存在一定的空间和时间上的局部性特点。

• 时间局部性是指一个数据项或指令在一段时间内被反复使用的特点
• 空间局部性是指一个数据项或指令在一段时间内与其相邻的数据项或指令被反复使用的特点。

文件管理

文件管理包括：存储管理、文件管理、目录管理、文件访问控制

1、硬链接和软链接

硬链接：在 Linux/类 Unix 文件系统中，每个文件和目录都有一个唯一的索引节点（inode）号，用来标识该文件或目录。硬链接通过 inode 节点号建立连接，硬链接和源文件的 inode 节点号相同，两者对文件系统来说是完全平等的（可以看作是互为硬链接，源头是同一份文件），删除其中任何一个对另外一个没有影响，可以通过给文件设置硬链接文件来防止重要文件被误删。也就是一个文件的备份

软链接：软链接和源文件的 inode 节点号不同，而是指向一个文件路径。源文件删除后，软链接依然存在，但是指向的是一个无效的文件路径。也就是Windows下的快捷方式

2、磁盘调度算法

机械硬盘的一次磁盘读写操作的时间由磁盘寻道/寻找时间、延迟时间和传输时间决定。磁盘调度算法可以通过改变到达磁盘请求的处理顺序，减少磁盘寻道时间和延迟时间。

1、先来先服务算法（First-Come First-Served，FCFS）：按照请求到达磁盘调度器的顺序进行处理，先到达的请求的先被服务。FCFS 算法实现起来比较简单，不存在算法开销。不过，由于没有考虑磁头移动的路径和方向，平均寻道时间较长。同时，该算法容易出现饥饿问题，即一些后到的磁盘请求可能需要等待很长时间才能得到服务。

2、最短寻道时间优先算法（Shortest Seek Time First，SSTF）：也被称为最佳服务优先（Shortest Service Time First，SSTF）算法，优先选择距离当前磁头位置最近的请求进行服务。SSTF 算法能够最小化磁头的寻道时间，但容易出现饥饿问题，即磁头附近的请求不断被服务，远离磁头的请求长时间得不到响应。实际应用中，需要优化一下该算法的实现，避免出现饥饿问题。

3、扫描算法（SCAN）：也被称为电梯（Elevator）算法，基本思想和电梯非常类似。磁头沿着一个方向扫描磁盘，如果经过的磁道有请求就处理，直到到达磁盘的边界，然后改变移动方向，依此往复。SCAN 算法能够保证所有的请求得到服务，解决了饥饿问题。但是，如果磁头从一个方向刚扫描完，请求才到的话。这个请求就需要等到磁头从相反方向过来之后才能得到处理。

4、循环扫描算法（Circular Scan，C-SCAN）：SCAN 算法的变体，只在磁盘的一侧进行扫描，并且只按照一个方向扫描，直到到达磁盘边界，然后回到磁盘起点，重新开始循环。

5、边扫描边观察算法（LOOK）：SCAN 算法中磁头到了磁盘的边界才改变移动方向，这样可能会做很多无用功，因为磁头移动方向上可能已经没有请求需要处理了。LOOK 算法对 SCAN 算法进行了改进，如果磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向，依此往复。也就是边扫描边观察指定方向上还有无请求，因此叫 LOOK。

6、均衡循环扫描算法（C-LOOK）：C-SCAN 只有到达磁盘边界时才能改变磁头移动方向，并且磁头返回时也需要返回到磁盘起点，这样可能会做很多无用功。C-LOOK 算法对 C-SCAN 算法进行了改进，如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。

SSD 固态硬盘没有扇区、磁道等这些概念，是通过闪存颗粒的特性（FTL:闪存转换层算法），内部维护了一张映射表，记录了逻辑到物理的映射。

参考文章&推荐阅读

《现代操作系统》

操作系统常见面试题总结(上) | JavaGuide(Java面试 + 学习指南)

操作系统常见面试题总结(下) | JavaGuide(Java面试 + 学习指南)