操作系统

1 基础概念

1.1 操作系统功能

  • **进程和线程管理：**进程的创建、撤销、阻塞、唤醒，进程间的通信。
  • **存储管理：**内存的分配和管理、外存（磁盘）的分配和管理。
  • **文件管理：**文件的读写、创建及删除。
  • **设备管理：**完成设备的请求或释放，以及设备的启动等功能。
  • **网络管理：**操作系统负责管理计算机网络的使用，管理网络的配置、连接、通信、安全等。
  • **安全管理：**用户身份认证，访问控制、文件加密等。

1.2 用户态和内核态

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

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

内核态相比用户态拥有更高的特权级别，因此能够执行更底层、更敏感的操作。不过，由于进入内核态需要付出较高的开销（需要进行一系列的上下文切换和权限检查），应该尽量减少进入内核态的次数，以提高系统的性能和稳定性。

用户态和内核态的切换：

  • 系统调用：用户态进程主动切换
  • 中断：当外围设备完成用户请求的操作后，会向 CPU 发出相应的中断信号，这时 CPU 会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序，如果先前执行的指令是用户态下的程序，那么这个转换的过程自然也就发生了由用户态到内核态的切换。比如硬盘读写操作完成，系统会切换到硬盘读写的中断处理程序中执行后续操作等。
  • 异常：当 CPU 在执行运行在用户态下的程序时，发生了某些事先不可知的异常，这时会触发由当前运行进程切换到处理此异常的内核相关程序中，也就转到了内核态，比如缺页异常。

在系统的处理上，中断和异常类似，都是通过中断向量表来找到相应的处理程序进行处理。区别在于，中断来自处理器外部，不是由任何一条专门的指令造成，而异常是执行当前指令的结果。

1.3 系统调用

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

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

系统调用过程：

  1. 用户态发起系统调用，用户态权限不足，中断执行（Trap）
  2. CPU执行的程序终端，跳转到终端处理程序，内核程序开始执行。
  3. 内核处理后，主动出发Trap，再次发生中断，切换回用户态工作。

2 进程和线程

2.1 进程

进程（Process） 是指计算机中正在运行的一个程序实例。资源分配的基本单位。

PCB是什么？

PCB（Process Control Block） 即进程控制块，是操作系统中用来管理和跟踪进程的数据结构，每个进程都对应着一个独立的 PCB。你可以将 PCB 视为进程的大脑。

当操作系统创建一个新进程时，会为该进程分配一个唯一的进程 ID，并且为该进程创建一个对应的进程控制块。当进程执行时，PCB 中的信息会不断变化，操作系统会根据这些信息来管理和调度进程。

PCB 主要包含下面几部分的内容：

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

进程有哪些状态？（生命周期）

image.png

  • 创建状态(new)：进程正在被创建，尚未到就绪状态。
  • 就绪状态(ready)：进程已处于准备运行状态，即进程获得了除了处理器之外的一切所需资源，一旦得到处理器资源(处理器分配的时间片)即可运行。
  • 运行状态(running)：进程正在处理器上运行(单核 CPU 下任意时刻只有一个进程处于运行状态)。
  • 阻塞状态(waiting)：又称为等待状态，进程正在等待某一事件而暂停运行如等待某资源为可用或等待 IO 操作完成。即使处理器空闲，该进程也不能运行。
  • 结束状态(terminated)：进程正在从系统中消失。可能是进程正常结束或其他原因中断退出运行。

进程之间的通信

  1. 管道/匿名管道(Pipes)：用于具有亲缘关系的父子进程间或者兄弟进程之间的通信。
  2. 有名管道(Named Pipes) : 匿名管道由于没有名字，只能用于亲缘关系的进程间通信。为了克服这个缺点，提出了有名管道。有名管道严格遵循 先进先出(First In First Out) 。有名管道以磁盘文件的方式存在，可以实现本机任意两个进程通信。
  3. 信号(Signal)：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生；
  4. 消息队列(Message Queuing)：消息队列是消息的链表,具有特定的格式,存放在内存中并由消息队列标识符标识。管道和消息队列的通信数据都是先进先出的原则。与管道（无名管道：只存在于内存中的文件；命名管道：存在于实际的磁盘介质或者文件系统）不同的是消息队列存放在内核中，只有在内核重启(即，操作系统重启)或者显式地删除一个消息队列时，该消息队列才会被真正的删除。消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取.比 FIFO 更有优势。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。
  5. 信号量(Semaphores)：信号量是一个计数器，用于多进程对共享数据的访问，信号量的意图在于进程间同步。这种通信方式主要用于解决与同步相关的问题并避免竞争条件。
  6. 共享内存(Shared memory)：使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据的更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等。可以说这是最有用的进程间通信方式。
  7. 套接字(Sockets) : 此方法主要用于在客户端和服务器之间通过网络进行通信。套接字是支持 TCP/IP 的网络通信的基本操作单元，可以看做是不同主机之间的进程进行双向通信的端点，简单的说就是通信的两方的一种约定，用套接字中的相关函数来完成通信过程。

进程调度算法

  1. 先到先服务
  2. 短作业优先
  3. 时间片轮转调度
  4. 优先级调度
  5. 多级反馈队列调度

僵尸进程和孤儿进程

Linux中：子进程通常通过fork()系统调用创建，该进程时原有进程的一个副本，子进程和父进程之间相互独立，各自拥有各自的PCB，即使父进程结束了，子进程也可以继续运行。

当一个进程调用exit()结束自己生命时，内核会释放该进程所有资源，包括打开的文件、占用的内存，但是进程对应的PCB仍然存在与系统中。这些信息只有在父进程调用wait()或者waitpid()系统调用时才会被释放，以便让父进程得到子进程的系统状态。

这样设计可以让父进程在子进程结束时得到子进程的状态信息，并且可以防止出现“僵尸进程”。

  • **僵尸进程：**子进程终止，父进程仍在运行，父进程没有调用wait()或者waitpid()等系统调用来回去子进程状态信息，释放子进程占用的资源，导致子进程的PCB仍然存在与系统中，但是无法被进一步使用。为了避免，父进程需要及时调用wait()或waitpid()来回收子进程。
  • **孤儿进程：**一个进程的父进程已经终止或者不存在，但是该进程仍在运行。这就是孤儿进程。孤儿进程是由于父进程意外终止或未即使调用wait()或waitpid()系统调用来回收子进程呆滞的。为了避免孤儿进程占用系统资源，操作系统会将孤儿进程的附近下设置为init进程（进程号为1），由init进程来回收孤儿进程的资源。

Linux下可以用TOP查找僵尸进程，进程状态为Z即为僵尸进程，zombie表示僵尸进程数量。

2.2 线程

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

为什么需要线程？

  • 进程切换开销大
  • 线程轻量，一个进程可以有多个线程
  • 多个线程可以并发处理不同任务，更有效的利用了多处理器和多核计算机
  • 同一进程之内线程共享内存和文件，相互通信无需调用内核

为什么要使用多线程？

  • 线程切换开销小，减少了上下文切换的开销
  • 多线程可以提高并发能力和性能

线程之间同步的方法

  1. 互斥锁（Mutex）：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。比如 Java 中的 synchronized 关键词和各种 Lock 都是这种机制。
  2. 读写锁（Read-Write Lock）：允许多个线程同时读取共享资源，但只有一个线程可以对共享资源进行写操作。
  3. 信号量(Semaphore)：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量。
  4. 屏障（Barrier）：屏障是一种同步原语，用于等待多个线程到达某个点再一起继续执行。当一个线程到达屏障时，它会停止执行并等待其他线程到达屏障，直到所有线程都到达屏障后，它们才会一起继续执行。比如 Java 中的 CyclicBarrier 是这种机制。
  5. 事件(Event) :Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作。

::线程状态::

2.3 进程和线程的区别

  • 线程是进程划分成的更小的运行单位,一个进程在其执行的过程中可以产生多个线程。
  • 线程和进程最大的不同在于基本上各进程是独立的，而各线程则不一定，因为同一进程中的线程极有可能会相互影响。
  • 线程执行开销小，但不利于资源的管理和保护；而进程正相反。

3 死锁

死锁（Deadlock）描述的是这样一种情况：多个进程/线程同时被阻塞，它们中的一个或者全部都在等待某个资源被释放。由于进程/线程被无限期地阻塞，因此程序不可能正常终止。

3.1 产生死锁的四个条件

  1. 互斥：资源非共享，只能同时被一个进程占有
  2. 占有且等待：一个进程至少占有一个资源，并等待另一个资源，等待的资源被其他进程占有
  3. 非抢占：资源不能抢占
  4. 循环等待：有一组等待进程，循环等待

3.2 解决死锁的方法

  1. 预防：限制并发进程对资源的请求
  2. 避免：分配资源是提前做出预测
  3. 检测：发生死锁后，检测思索发生，并确定与死锁相关的进程和资源
  4. 解除：与检测搭配，将进程从死锁状态下解脱。

3.3 死锁预防

  1. 破坏互斥：使资源可以同时访问，能解决的情况有限
  2. 破坏非抢占：剥夺式调度算法，适用与主存资源和处理器资源分配
  3. 破坏占有且等待：静态分配，执行前申请到所有资源，降低了资源利用率
  4. 破坏循环等待：层次分配策略，在层次分配策略下，所有的资源被分成了多个层次，一个进程得到某一次的一个资源后，它只能再申请较高一层的资源；当一个进程要释放某层的一个资源时，必须先释放所占用的较高层的资源，按这种策略，是不可能出现循环等待链的，因为那样的话，就出现了已经申请了较高层的资源，反而去申请了较低层的资源，不符合层次分配策略。

3.4 死锁避免

我们将系统的状态分为 安全状态 和 不安全状态 ，每当在为申请者分配资源前先测试系统状态，若把系统资源分配给申请者会产生死锁，则拒绝分配，否则接受申请，并为它分配资源。

  • 银行家算法：死锁的避免(银行家算法)改善了 资源使用率低的问题 ，但是它要不断地检测每个进程对各类资源的占用和申请情况，以及做 安全性检查 ，需要花费较多的时间。

3.5 死锁检测

解决死锁问题的另一条途径是 死锁检测和解除 (这里突然联想到了乐观锁和悲观锁，感觉死锁的检测和解除就像是 乐观锁 ，分配资源时不去提前管会不会发生死锁了，等到真的死锁出现了再来解决嘛，而 死锁的预防和避免 更像是悲观锁，总是觉得死锁会出现，所以在分配资源的时候就很谨慎)。

这种方法对资源的分配不加以任何限制，也不采取死锁避免措施，但系统 定时地运行一个 “死锁检测” 的程序，判断系统内是否出现死锁，如果检测到系统发生了死锁，再采取措施去解除它。

检测步骤：

  1. 如果进程-资源分配图中无环路，则此时系统没有发生死锁
  2. 如果进程-资源分配图中有环路，且每个资源类仅有一个资源，则系统中已经发生了死锁。
  3. 如果进程-资源分配图中有环路，且涉及到的资源类有多个资源，此时系统未必会发生死锁。如果能在进程-资源分配图中找出一个 既不阻塞又非独立的进程 ，该进程能够在有限的时间内归还占有的资源，也就是把边给消除掉了，重复此过程，直到能在有限的时间内 消除所有的边 ，则不会发生死锁，否则会发生死锁。(消除边的过程类似于 拓扑排序)

3.6 死锁解除

  1. 立即结束所有进程的执行，重新启动操作系统：这种方法简单，但以前所在的工作全部作废，损失很大。
  2. 撤销涉及死锁的所有进程，解除死锁后继续运行：这种方法能彻底打破死锁的循环等待条件，但将付出很大代价，例如有些进程可能已经计算了很长时间，由于被撤销而使产生的部分结果也被消除了，再重新执行时还要再次进行计算。
  3. 逐个撤销涉及死锁的进程，回收其资源直至死锁解除。
  4. 抢占资源：从涉及死锁的一个或几个进程中抢占资源，把夺得的资源再分配给涉及死锁的进程直至死锁解除。

4 内存管理

内存的分配与回收：对进程所需的内存进行分配和释放，malloc 函数：申请内存，free 函数：释放内存。

地址转换：将程序中的虚拟地址转换成内存中的物理地址。

内存扩充：当系统没有足够的内存时，利用虚拟内存技术或自动覆盖技术，从逻辑上扩充内存。

内存映射：将一个文件直接映射到进程的进程空间中，这样可以通过内存指针用读写内存的办法直接存取文件内容，速度更快。

内存优化：通过调整内存分配策略和回收算法来优化内存使用效率。

内存安全：保证进程之间使用内存互不干扰，避免一些恶意程序通过修改内存来破坏系统的安全性。

4.1 内存碎片

内部内存碎片(Internal Memory Fragmentation，简称为内存碎片)：已经分配给进程使用但未被使用的内存。导致内部内存碎片的主要原因是，当采用固定比例比如 2 的幂次方进行内存分配时，进程所分配的内存可能会比其实际所需要的大。举个例子，一个进程只需要 65 字节的内存，但为其分配了 128（2^7） 大小的内存，那 63 字节的内存就成为了内部内存碎片。

外部内存碎片(External Memory Fragmentation，简称为外部碎片)：由于未分配的连续内存区域太小，以至于不能满足任意进程所需要的内存分配请求，这些小片段且不连续的内存空间被称为外部碎片。也就是说，外部内存碎片指的是那些并未分配给进程但又不能使用的内存。我们后面介绍的分段机制就会导致外部内存碎片。

4.2 内存管理方式

  • 连续内存管理：为一个用户程序分配一个连续的内存空间，内存利用率一般不高。
    • 块式管理 是早期计算机操作系统的一种连续内存管理方式，存在严重的内存碎片问题。块式管理会将内存分为几个固定大小的块，每个块中只包含一个进程。如果程序运行需要内存的话，操作系统就分配给它一块，如果程序运行只需要很小的空间的话，分配的这块内存很大一部分几乎被浪费了。这些在每个块中未被利用的空间，我们称之为内部内存碎片。除了内部内存碎片之外，由于两个内存块之间可能还会有外部内存碎片，这些不连续的外部内存碎片由于太小了无法再进行分配。
  • 非连续内存管理：允许一个程序使用的内存分布在离散或者说不相邻的内存中，相对更加灵活一些。
    • 段式管理：以段(—段连续的物理内存)的形式管理/分配物理内存。应用程序的虚拟地址空间被分为大小不等的段，段是有实际意义的，每个段定义了一组逻辑信息，例如有主程序段 MAIN、子程序段 X、数据段 D 及栈段 S 等。
    • 页式管理：把物理内存分为连续等长的物理页，应用程序的虚拟地址空间也被划分为连续等长的虚拟页，是现代操作系统广泛使用的一种内存管理方式。
    • 段页式管理机制：结合了段式管理和页式管理的一种内存管理机制，把物理内存先分成若干段，每个段又继续分成若干大小相等的页。

4.3 虚拟内存

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

1. 虚拟内存主要提供了下面这些能力：

  • 隔离进程：物理内存通过虚拟地址空间访问，虚拟地址空间与进程一一对应。每个进程都认为自己拥有了整个物理内存，进程之间彼此隔离，一个进程中的代码无法更改正在由另一进程或操作系统使用的物理内存。
  • 提升物理内存利用率：有了虚拟地址空间后，操作系统只需要将进程当前正在使用的部分数据或指令加载入物理内存。
  • 简化内存管理：进程都有一个一致且私有的虚拟地址空间，程序员不用和真正的物理内存打交道，而是借助虚拟地址空间访问物理内存，从而简化了内存管理。
  • 多个进程共享物理内存：进程在运行过程中，会加载许多操作系统的动态库。这些库对于每个进程而言都是公用的，它们在内存中实际只会加载一份，这部分称为共享内存。
  • 提高内存使用安全性：控制进程对物理内存的访问，隔离不同进程的访问权限，提高系统的安全性。
  • 提供更大的可使用内存空间：可以让程序拥有超过系统物理内存大小的可用内存空间。这是因为当物理内存不够用时，可以利用磁盘充当，将物理内存页（通常大小为 4 KB）保存到磁盘文件（会影响读写速度），数据或代码页会根据需要在物理内存与磁盘之间移动。

2. 没有虚拟内存会发生什么事情？

用户程序可以访问任意物理内存，可能会不小心操作到系统运行必需的内存，进而造成操作系统崩溃，严重影响系统的安全。

同时运行多个程序容易崩溃。比如你想同时运行一个微信和一个 QQ 音乐，微信在运行的时候给内存地址 1xxx 赋值后，QQ 音乐也同样给内存地址 1xxx 赋值，那么 QQ 音乐对内存的赋值就会覆盖微信之前所赋的值，这就可能会造成微信这个程序会崩溃。

程序运行过程中使用的所有数据或指令都要载入物理内存，根据局部性原理，其中很大一部分可能都不会用到，白白占用了宝贵的物理内存资源。

3. 物理地址和虚拟地址

  • 物理地址（Physical Address） 是真正的物理内存中地址，更具体点来说是内存地址寄存器中的地址。程序中访问的内存地址不是物理地址，而是 虚拟地址（Virtual Address） 。
  • 操作系统一般通过 CPU 芯片中的一个重要组件 MMU(Memory Management Unit，内存管理单元) 将虚拟地址转换为物理地址，这个过程被称为 地址翻译/地址转换（Address Translation） 。
  • 通过 MMU 将虚拟地址转换为物理地址后，再通过总线传到物理内存设备，进而完成相应的物理内存读写请求。
  • MMU 将虚拟地址翻译为物理地址的主要机制有两种: 分段机制 和 分页机制 。

4. 什么是虚拟地址空间和物理地址空间

  • 虚拟地址空间是虚拟地址的集合，是虚拟内存的范围。每一个进程都有一个一致且私有的虚拟地址空间。
  • 物理地址空间是物理地址的集合，是物理内存的范围。

5. 虚拟地址和物理地址之间如何进行映射

MMU 将虚拟地址翻译为物理地址的主要机制有 3 种:

  1. 分段机制
  2. 分页机制
  3. 段页机制

其中，现代操作系统广泛采用分页机制，需要重点关注！

4.4 分段机制

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

image.png

1. 具体的地址翻译过程如下：

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

段表中还存有诸如段长(可用于检查虚拟地址是否超出合法范围)、段类型（该段的类型，例如代码段、数据段等）等信息。

2. 通过段号一定要找到对应的段表项吗？得到最终的物理地址后对应的物理内存一定存在吗？

不一定。段表项可能并不存在：

  • 段表项被删除：软件错误、软件恶意行为等情况可能会导致段表项被删除。
  • 段表项还未创建：如果系统内存不足或者无法分配到连续的物理内存块就会导致段表项无法被创建。

3. 分段机制为什么会导致内存外部碎片？

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

4.5 分页机制

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

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

image.png

在分页机制下，每个应用程序都会有一个对应的页表。

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

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

具体的地址翻译过程如下：

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

2. 通过虚拟页号一定要找到对应的物理页号吗？找到了物理页号得到最终的物理地址后对应的物理页一定存在吗？

不一定！可能会存在 页缺失 。也就是说，物理内存中没有对应的物理页或者物理内存中有对应的物理页但虚拟页还未和物理页建立映射（对应的页表项不存在）。

  • 硬性页缺失（Hard Page Fault）：物理内存中没有对应的物理页。于是，Page Fault Handler 会指示 CPU 从已经打开的磁盘文件中读取相应的内容到物理内存，而后交由 MMU 建立相应的虚拟页和物理页的映射关系。
  • 软性页缺失（Soft Page Fault）：物理内存中有对应的物理页，但虚拟页还未和物理页建立映射。于是，Page Fault Handler 会指示 MMU 建立相应的虚拟页和物理页的映射关系。

发生上面这两种缺页错误的时候，应用程序访问的是有效的物理内存，只是出现了物理页缺失或者虚拟页和物理页的映射关系未建立的问题。如果应用程序访问的是无效的物理内存的话，还会出现 无效缺页错误（Invalid Page Fault） 。

3. 单级页表有什么问题，为什么需要多级页表？

以 32 位的环境为例，虚拟地址空间范围共有 2^32（4G）。假设 一个页的大小是 2^12（4KB），那页表项共有 4G / 4K = 2^20 个。每个页表项为一个地址，占用 4 字节，2^20 * 2^2 / 1024 * 1024= 4MB。也就是说一个程序啥都不干，页表大小就得占用 4M。

系统运行的应用程序多起来的话，页表的开销还是非常大的。而且，绝大部分应用程序可能只能用到页表中的几项，其他的白白浪费了。

为了解决这个问题，操作系统引入了 多级页表 ，多级页表对应多个页表，每个页表也前一个页表相关联。32 位系统一般为二级页表，64 位系统一般为四级页表。

image.png

以二级页表为例进行介绍：二级列表分为一级页表和二级页表。一级页表共有 1024 个页表项，一级页表又关联二级页表，二级页表同样共有 1024 个页表项。二级页表中的一级页表项是一对多的关系，二级页表按需加载（只会用到很少一部分二级页表），进而节省空间占用。

假设只需要 2 个二级页表，那两级页表的内存占用情况为: 4KB（一级页表占用） + 4KB * 2（二级页表占用） = 12 KB。

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

TLB有什么用？使用TLB之后的地址翻译流程是怎样的？

为了提高虚拟地址到物理地址的转换速度，操作系统在 页表方案 基础之上引入了 转址旁路缓存(Translation Lookaside Buffer，TLB，也被称为快表) 。

image.png

在主流的 AArch64 和 x86-64 体系结构下，TLB 属于 (Memory Management Unit，内存管理单元) 内部的单元，本质上就是一块高速缓存（Cache），缓存了虚拟页号到物理页号的映射关系，你可以将其简单看作是存储着键（虚拟页号）值（物理页号）对的哈希表。

使用 TLB 之后的地址翻译流程是这样的：

  1. 用虚拟地址中的虚拟页号作为 key 去 TLB 中查询；
  2. 如果能查到对应的物理页的话，就不用再查询页表了，这种情况称为 TLB 命中（TLB hit)。
  3. 如果不能查到对应的物理页的话，还是需要去查询主存中的页表，同时将页表中的该映射表项添加到 TLB 中，这种情况称为 TLB 未命中（TLB miss)。
  4. 当 TLB 填满后，又要登记新页时，就按照一定的淘汰策略淘汰掉快表中的一个页。

换页机制有什么用

换页机制的思想是当物理内存不够用的时候，操作系统选择将一些物理页的内容放到磁盘上去，等要用到的时候再将它们读取到物理内存中。也就是说，换页机制利用磁盘这种较低廉的存储设备扩展的物理内存。

这也就解释了一个日常使用电脑常见的问题：为什么操作系统中所有进程运行所需的物理内存即使比真实的物理内存要大一些，这些进程也是可以正常运行的，只是运行速度会变慢。

这同样是一种时间换空间的策略，你用 CPU 的计算时间，页的调入调出花费的时间，换来了一个虚拟的更大的物理内存空间来支持程序的运行。

常见的页面置换算法

  1. 最佳页面置换算法：优先选择淘汰的页面是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。只是理论最优的页面置换算法，可以作为衡量其他置换算法优劣的标准。
  2. 先进先出页面置换算法（FIFO）
  3. 最近最久未使用页面置换算法（LRU）
  4. 最少使用页面置换算法（LFU）
  5. 时钟页面置换算法（Clock）

FIFO 页面置换算法性能为何不好？

主要原因主要有二：

  1. 经常访问或者需要长期存在的页面会被频繁调入调出：较早调入的页往往是经常被访问或者需要长期存在的页，这些页会被反复调入和调出。
  2. 存在 Belady 现象：被置换的页面并不是进程不会访问的，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。出现该异常的原因是因为 FIFO 算法只考虑了页面进入内存的顺序，而没有考虑页面访问的频率和紧迫性。

哪一种页面置换算法实际用的比较多？

LRU 算法是实际使用中应用的比较多，也被认为是最接近 OPT 的页面置换算法。

不过，需要注意的是，实际应用中这些算法会被做一些改进，就比如 InnoDB Buffer Pool（ InnoDB 缓冲池，MySQL 数据库中用于管理缓存页面的机制）就改进了传统的 LRU 算法，使用了一种称为"Adaptive LRU"的算法（同时结合了 LRU 和 LFU 算法的思想）。

分页机制和分段机制的共同点和区别

共同点：

  • 都是非连续内存管理的方式。
  • 都采用了地址映射的方法，将虚拟地址映射到物理地址，以实现对内存的管理和保护。

区别：

  • 分页机制以页面为单位进行内存管理，而分段机制以段为单位进行内存管理。页的大小是固定的，由操作系统决定，通常为 2 的幂次方。而段的大小不固定，取决于我们当前运行的程序。
  • 页是物理单位，即操作系统将物理内存划分成固定大小的页面，每个页面的大小通常是 2 的幂次方，例如 4KB、8KB 等等。而段则是逻辑单位，是为了满足程序对内存空间的逻辑需求而设计的，通常根据程序中数据和代码的逻辑结构来划分。
  • 分段机制容易出现外部内存碎片，即在段与段之间留下碎片空间(不足以映射给虚拟地址空间中的段)。分页机制解决了外部内存碎片的问题，但仍然可能会出现内部内存碎片。
  • 分页机制采用了页表来完成虚拟地址到物理地址的映射，页表通过一级页表和二级页表来实现多级映射；而分段机制则采用了段表来完成虚拟地址到物理地址的映射，每个段表项中记录了该段的起始地址和长度信息。
  • 分页机制对程序没有任何要求，程序只需要按照虚拟地址进行访问即可；而分段机制需要程序员将程序分为多个段，并且显式地使用段寄存器来访问不同的段。

4.6 段页机制

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

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

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

5 文件系统

文件系统主要负责管理和组织计算机存储设备上的文件和目录，其功能包括以下几个方面：

  1. 存储管理：将文件数据存储到物理存储介质中，并且管理空间分配，以确保每个文件都有足够的空间存储，并避免文件之间发生冲突。
  2. 文件管理：文件的创建、删除、移动、重命名、压缩、加密、共享等等。
  3. 目录管理：目录的创建、删除、移动、重命名等等。
  4. 文件访问控制：管理不同用户或进程对文件的访问权限，以确保用户只能访问其被授权访问的文件，以保证文件的安全性和保密性。

5.1 软链接和硬链接的区别

在 Linux/类 Unix 系统上，文件链接（File Link）是一种特殊的文件类型，可以在文件系统中指向另一个文件。常见的文件链接类型有两种：

1、硬链接（Hard Link）

  • 在 Linux/类 Unix 文件系统中，每个文件和目录都有一个唯一的索引节点（inode）号，用来标识该文件或目录。硬链接通过 inode 节点号建立连接，硬链接和源文件的 inode 节点号相同，两者对文件系统来说是完全平等的（可以看作是互为硬链接，源头是同一份文件），删除其中任何一个对另外一个没有影响，可以通过给文件设置硬链接文件来防止重要文件被误删。
  • 只有删除了源文件和所有对应的硬链接文件，该文件才会被真正删除。
  • 硬链接具有一些限制，不能对目录以及不存在的文件创建硬链接，并且，硬链接也不能跨越文件系统。
  • ln 命令用于创建硬链接。

2、软链接（Symbolic Link 或 Symlink）

  • 软链接和源文件的 inode 节点号不同，而是指向一个文件路径。
  • 源文件删除后，软链接依然存在，但是指向的是一个无效的文件路径。
  • 软连接类似于 Windows 系统中的快捷方式。
  • 不同于硬链接，可以对目录或者不存在的文件创建软链接，并且，软链接可以跨越文件系统。
  • ln -s 命令用于创建软链接。

硬链接为什么不能跨文件系统？

我们之前提到过，硬链接是通过 inode 节点号建立连接的，而硬链接和源文件共享相同的 inode 节点号。

然而，每个文件系统都有自己的独立 inode 表，且每个 inode 表只维护该文件系统内的 inode。如果在不同的文件系统之间创建硬链接，可能会导致 inode 节点号冲突的问题，即目标文件的 inode 节点号已经在该文件系统中被使用。

5.2 提高文件系统性能的方式有哪些？

优化硬件：使用高速硬件设备（如 SSD、NVMe）替代传统的机械硬盘，使用 RAID（Redundant Array of Inexpensive Disks）等技术提高磁盘性能。

选择合适的文件系统选型：不同的文件系统具有不同的特性，对于不同的应用场景选择合适的文件系统可以提高系统性能。

运用缓存：访问磁盘的效率比较低，可以运用缓存来减少磁盘的访问次数。不过，需要注意缓存命中率，缓存命中率过低的话，效果太差。

避免磁盘过度使用：注意磁盘的使用率，避免将磁盘用满，尽量留一些剩余空间，以免对文件系统的性能产生负面影响。

对磁盘进行合理的分区：合理的磁盘分区方案，能够使文件系统在不同的区域存储文件，从而减少文件碎片，提高文件读写性能。

5.3 常见磁盘调度算法

磁盘调度算法是操作系统中对磁盘访问请求进行排序和调度的算法，其目的是提高磁盘的访问效率。

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

  1. 先来先服务算法（FCFS）：按照请求到达磁盘调度器的顺序进行处理，先到达的请求的先被服务。FCFS 算法实现起来比较简单，不存在算法开销。不过，由于没有考虑磁头移动的路径和方向，平均寻道时间较长。同时，该算法容易出现饥饿问题，即一些后到的磁盘请求可能需要等待很长时间才能得到服务。
  2. 最短寻道优先算法（SSTF）：也被称为最佳服务优先（Shortest Service Time First，SSTF）算法，优先选择距离当前磁头位置最近的请求进行服务。SSTF 算法能够最小化磁头的寻道时间，但容易出现饥饿问题，即磁头附近的请求不断被服务，远离磁头的请求长时间得不到响应。实际应用中，需要优化一下该算法的实现，避免出现饥饿问题。
  3. 扫描算法（SCAN）：也被称为电梯（Elevator）算法，基本思想和电梯非常类似。磁头沿着一个方向扫描磁盘，如果经过的磁道有请求就处理，直到到达磁盘的边界，然后改变移动方向，依此往复。SCAN 算法能够保证所有的请求得到服务，解决了饥饿问题。但是，如果磁头从一个方向刚扫描完，请求才到的话。这个请求就需要等到磁头从相反方向过来之后才能得到处理。
  4. 循环扫描算法（C-SCAN）：SCAN 算法的变体，只在磁盘的一侧进行扫描，并且只按照一个方向扫描，直到到达磁盘边界，然后回到磁盘起点，重新开始循环。
  5. 边扫描边观察算法（LOOK）：SCAN 算法中磁头到了磁盘的边界才改变移动方向，这样可能会做很多无用功，因为磁头移动方向上可能已经没有请求需要处理了。LOOK 算法对 SCAN 算法进行了改进，如果磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向，依此往复。也就是边扫描边观察指定方向上还有无请求，因此叫 LOOK。
  6. 均衡循环扫描算法（C-LOOK）：C-SCAN 只有到达磁盘边界时才能改变磁头移动方向，并且磁头返回时也需要返回到磁盘起点，这样可能会做很多无用功。C-LOOK 算法对 C-SCAN 算法进行了改进，如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。