高频知识汇总 | 【操作系统】面试题汇总（万字长博通俗易懂）

前言

这篇我亲手整理的【操作系统】资料，融入了我个人的理解。当初我在研习八股文时，深感复习时的困扰，网上资料虽多，却过于繁杂，有的甚至冗余。例如，文件管理这部分，在实际面试中很少涉及，因此我仅深入探究了磁盘、缓存和内存的读写速度差异，未再深究其他内容。

此文是我精心筛选的结晶，囊括了操作系统中最为核心、常被提及的知识点。我建议你首先掌握这些内容，再进一步探索更高级、全面的知识。

为方便你学习，我在关键知识点下方附上了补充链接，轻点即可查阅。如果你想逐一攻克每个知识点，这篇文章绝对是你的得力助手。关注和收藏一下，以便未来查看。计算机网、数据库的知识我会陆续整理发布。

不再赘述，让我们开始深入探索操作系统的奥秘吧。

1. 操作系统概述

1.1 系统调用 / 用户态和内核态

根据进程访问资源的特点，我们可以把进程在系统上的运行分为两个级别：

用户态(user mode) : 用户态运行的进程可以直接读取用户程序的数据。
系统态(kernel mode):可以简单的理解系统态运行的进程或程序几乎可以访问计算机的任何资源，不受限制。

1.2 说了用户态和系统态之后，那么什么是系统调用呢？

我们运行的程序基本都是运行在用户态，如果我们调用操作系统提供的系统态级别的子功能咋办呢？那就需要系统调用了！
也就是说在我们运行的用户程序中，凡是与系统态级别的资源有关的操作（如文件管理、进程控制、内存管理等)，都必须通过系统调用方式向操作系统提出服务请求，并由操作系统代为完成。

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

设备管理。完成设备的请求或释放，以及设备启动等功能。
文件管理。完成文件的读、写、创建及删除等功能。
进程控制。完成进程的创建、撤销、阻塞及唤醒等功能。
进程通信。完成进程之间的消息传递或信号传递等功能。
内存管理。完成内存的分配、回收以及获取作业占用内存区大小及地址等功能。

1.3 那么如何从用户态切换到内核态呢？（仅需知道是这哪三种就可以了，其实一般只会问到举几个系统调用的例子）

系统调用
这是用户态进程主动要求切换到内核态的一种方式，用户态进程通过系统调用申请使用操作系统提供的服务程序完成工作，比如 read 操作，比如前例中 fork() 实际上就是执行了一个创建新进程的系统调用。而系统调用的机制其核心还是使用了操作系统为用户特别开放的一个中断来实现，例如Linux的int 80h中断。
异常
当CPU在执行运行在用户态下的程序时，发生了某些事先不可知的异常，这时会触发由当前运行进程切换到处理此异常的内核相关程序中，也就转到了内核态，比如缺页异常。
外围设备的中断
当外围设备完成用户请求的操作后，会向CPU发出相应的中断信号，这时CPU会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序，如果先前执行的指令是用户态下的程序，那么这个转换的过程自然也就发生了由用户态到内核态的切换。比如硬盘读写操作完成，系统会切换到硬盘读写的中断处理程序中执行后续操作等。

这3种方式是系统在运行时由用户态转到内核态的最主要方式，其中系统调用可以认为是用户进程主动发起的，异常和外围设备中断则是被动的。

1.4 其他必会知识

并行与并发
并发：在操作系统中，某一时间段，几个程序在同一个CPU上运行，但在任意一个时间点上，只有一个程序在CPU上运行。
并行：两个程序在某一时刻同时运行，强调同时发生。
阻塞与非阻塞
阻塞是指调用线程或者进程被操作系统挂起。
非阻塞是指调用线程或者进程不会被操作系统挂起。
同步与异步
同步与异步同步是阻塞模式，异步是非阻塞模式。
同步就是指一个进程在执行某个请求的时候，若该请求需要一段时间才能返回信息，那么这个进程将会一直等待下去，知道收到返回信息才继续执行下去；
异步是指进程不需要一直等下去，而是继续执行下面的操作，不管其他进程的状态。当有消息返回式系统会通知进程进行处理，这样可以提高执行的效率。

2. 进程管理

2.1 线程、进程、协程的区别

答：

进程是资源分配的最基本的单位，运行一个程序会创建一个或多个进程，进程就是运行起来的可执行程序。
线程是程序执行的最基本的单位，是轻量级的进程，每个进程里都有一个主线程，且只能有一个，和进程是相互依存的关系，生命周期和进程一样。
协程是用户态的轻量级线程，是线程内部的基本单位。无需线程上下文切换的开销、无需原子操作锁定及同步的开销、方便切换控制流，简化编程模型。

进程和线程的区别的话

首先从资源来说，进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。
然后从调度来说，线程是独立调度的基本单位，在同一进程中线程切换的话不会引起进程的切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程的切换。
从系统开销来讲，由于创建或撤销进程，系统都要分配回收资源，所付出的开销远大于创建或撤销线程时的开销。类似的，在进行进程切换的时候，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境设置，而线程切换只需保存和设置少量寄存器的内容，开销很小。
通信方面来说，线程间可以通过直接读写同一进程的数据进行通信，但是进程通信需要借助一些复杂的方法。

2.2 PCB是什么？

PCB主要包含下面几部分的内容：
- 进程的描述信息，比如进程的名称，标识符，
- 处理机的状态信息，当程序中断是保留此时的信息，以便 CPU 返回时能从断点执行
- 进程调度信息，比如阻塞原因，状态，优先级等等
- 进程控制和资源占用，同步通信机制，链接指针（指向队列中下一个进程的 PCB 地址）
PCB 的作用
- PCB是进程实体的一部分，是操作系统中最重要的数据结构
- 由于它的存在，使得多道程序环境下，不能独立运行的程序成为一个能独立运行的基本单位，使得程序可以并发执行
- 系统通过 PCB 来感知进程的存在。（换句话说，PCB 是进程存在的唯一标识）
- 进程的组成可以用下图来表示，PCB 就是他唯一标识符。

2.3 进程和线程创建和撤销的过程中发生了什么事情？（问的不多，我被问到过一次）

进程允许创建和控制另一个进程，前者称为父进程，后者称为子进程，子进程又可以创建孙进程，如此下去进而形成一个进程的家族树，这样子进程就可以从父进程那里继承所有的资源，当子进程撤销时，便将从父进程处获得的所有资源归还，此外，撤销父进程，则必须撤销所有的子进程。（撤销的过程实际上就是对这棵家族树进行后序遍历的过程）
在应用中创建一个子进程的过程如下：

申请空白的PCB
初始化进程描述信息
为进程分配资源以及地址空间
将其插入就绪队列中

当进程完成后，系统会回收占用的资源，撤销进程，而引发进程撤销的情况有：进程正常结束或者异常结束，外界的干预（比如我们在任务管理器中强制停止某个进程的运行）。

查找需要撤销的进程的 PCB
如果进程处于运行状态，终止进程并进行调度
终止子孙进程 - 归还资源
将它从所在的队列中移除

2.4 进程的五种状态

面试在答的时候这么答：有创建状态、就绪状态、运行状态、阻塞状态、结束状态。

其中只有就绪状态和运行状态能互相转化，当进程为就绪态时，等待 CPU 分配时间片，得到时间片后就进入运行状态
运行状态在使用完 CPU 时间片后，又重回就绪态。
阻塞状态是进程在运行状态时，需要等待某个资源比如打印机资源，而进入一个挂起的状态，等资源拿到后会回到就绪状态，等待 CPU 时间片。

2.5 进程调度算法（面试高频知识点）

这个看cyc大佬总结的，按批处理系统和交互式系统去记忆比较容易记住。点这里：cycBook

2.6 进程同步的方式

临界区
首先对临界资源的访问那段代码被称为临界区，为了互斥的访问临界区，每个进程在进入临界区时，都需要先进行检查，也就是查看锁。
同步与互斥
同步：多个进程因为合作产生的直接制约关系，使得进程有一定的先后顺序。
互斥：多个进程在同一时刻只有一个进程能进入临界区。
信号量
信号量是一个整型变量，可以对其执行 P 和 V 操作。
P：如果信号量大于零，就对其进行减 1 操作；如果信号量等于 0，进程进入 waiting 状态，等待信号量大于零。
V：对信号量执行加 1 操作，并唤醒正在 waiting 的进程
如果信号量只能取 0 或者 1，那么就变成了互斥量，其实也可以理解成加锁解锁操作，0 表示已经加锁，1 表示解锁。
管程
使用信号量机制实现的生产者消费者问题需要客户端代码做很多控制，而管程把控制的代码独立出来，不仅不容易出错，也使得客户端代码调用更容易。
管程有一个重要特性：在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。
管程引入了条件变量以及相关的操作：wait() 和 signal() 来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞，把管程让出来给另一个进程持有。signal() 操作用于唤醒被阻塞的进程。

2.7 进程间通信的方式（重要！）

建议把BiliBili王道考研的这一节课给看了
进程通信和进程同步很容易混淆，其实可以把进程通信当成一种手段，进程同步是一种目的，为了实现进程同步，可传输一些进程同步所需要的信息。

管道
- 匿名管道：举个例子：linux 里的竖线，就是管道的意思，比如 ps -aux|grep mysql 这句话的意思是把前一个进程查询的结果作为 grep mysql 的输入，如果两个进程要进行通信的话，就可以用这种管道来进行通信。
  这种通信的方式是半双工通信的，只能单向交替传输
  并且只能在具有亲属关系的进程之间通信使用。
  可以看成是一种特殊的文件，但是这种文件只能存在于内存之中。
- 命名管道：可以用 mkfifo 命令创建一个命名管道，可以用一个进程向管道里写数据，然后可以让另一个进程把里面的数据读出来。命名管道的优点是去除了只能在父子进程中使用的限制，并且命名管道有路径名和它相关联，是以一种特殊设备文件形式存在于文件系统中的。

消息队列

消息队列的通信模式是这样的：a 进程要给 b 进程发消息，只需要把消息挂在消息队列（可以是中介邮局，也可以是进程自己的信箱）里就行了，b 进程需要的时候再去取消息队列里的消息。
消息队列可以独立于读写进程存在，就算进程终止时，消息队列的内容也不会被删除。
读进程可以根据消息类型有选择的接收消息，而不像 FIFO 那样只能默认接收。

如果进程发送的数据较大，并且两个进程通信非常频繁的话，消息队列模型就不太合适了，因为如果发送的数据很大的话，意味着发送消息（拷贝）这个过程就需要很多时间来读写内存。

共享内存
- 共享内存的方式就可以解决拷贝耗时很长的问题了。
- 共享内存是最快的一种进程通信的方式，因为进程是直接对内存进行存取的。因为可以多个进程对共享内存同时操作，所以对共享空间的访问必须要求进程对共享内存的访问是互斥的。所以我们经常把信号量和共享内存一起使用来实现进程通信。
- （这里补个知识！！！系统加载一个进程的时候，分配给进程的内存并不是实际的物理内存，而是虚拟内存空间。那么我们可以让两个进程各自拿出一块儿虚拟地址空间来，映射到同一个物理内存中。这样两个进程虽然有独立的虚拟内存空间，但有一部分是映射到相同的物理内存，这样就完成共享机制了。）
信号量
- 共享内存最大的问题就是多进程竞争内存的问题，就像平时所说的线程安全的问题，那么就需要靠信号量来保证进程间的操作的同步与互斥。
- 信号量其实就是个计数器，例如信号量的初始值是 1，然后 a 进程访问临界资源的时候，把信号量设置为 0，然后进程 b 也要访问临界资源的时候，发现信号量是 0，就知道已有进程在访问临界资源了，这时进程 b 就访问不了了，所以说信号量也是进程间的一种通信方式。

套接字
套接字可以实现两个不同的机器之间的进程通信，比如 socket 使用。

2.8 生产者消费者模型（要会写伪代码）

生产者和消费者模型，期间就需要线程之间进行通信来实现互斥和同步。

需求是这样的：

生产者每生成一个产品，就消耗一个缓冲区，只有当缓冲区不满的时候才能放入；
消费者每消费一个产品，就消耗一个产品，只有当缓冲区不空的时候才能消费。

做法：

因为缓冲区是临界资源，所以需要定义一个互斥信号量，为 mutex 来实现两者对临界资源的互斥访问。
为了同步生产者和消费者的操作，需要记录缓冲区的剩余大小 empty 和产品的个数 full。当缓冲区大小不为 0 时，生产者才能放入产品；当产品个数不为 0 时，消费者才能拿走产品。
注意！不可对临界区先加锁，设想这样一个情况：当 empty = 0 时，生产者此时先对临界区加锁，然后发现缓冲区的数量为 0，则开始进入阻塞等待消费者消费的状态，而此时一个消费者开始进入消耗一个产品，但发现临界区被加锁，所以生产者在等待消费者消费产品，而消费者在等待生产者释放临界区锁，进入了一个死锁状态。

伪代码如下

mutex = 1;
empty = N;
full = 0;void Producer() {P(empty); // 生产者生产一个产品，消耗一个缓冲区 P(mutex);....      // 临界区V(mutex);V(full); // 产品数量加1
}void Consumer() {P(full); // 消费者消耗一个产品，释放一个缓冲区P(mutex); // 临界区上锁....V(mutex); // 临界区锁释放V(empty); // 增加一个缓冲区
}void P(S){S--;if(S < 0) block();  // 如果小于0，代表资源没了
}void V(S){S++;if(S <= 0) wakeUp(); // 如果小于等于0，代表有进程仍然在等待，通知他们ok了
}

2. 死锁

2.1 讲讲死锁发生的条件是什么？

互斥条件：是资源分配是互斥的，资源要么处于被分配给一个进程的状态，要么就是可用状态。
等待和占有条件：进程在请求资源得不到满足的时候，进入阻塞等待状态，且不释放已占有的资源。
不剥夺条件：已经分配给一个进程的资源不能强制性地被抢占，只能等待占有他的进程释放。
环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程释放所占有的资源。

2.2 如何避免死锁的发生？

预防策略：从形成死锁的条件入手，基本思想就是打破形成死锁的四个条件中的一个或多个，保证系统不会进入死锁状态。
- 破坏互斥条件：比如只读文件、磁盘等软硬件资源可采用这种办法处理。
- 破坏占有和等待条件：在进程开始执行之前，就把其要申请的所有资源全部分配给他，直到所有资源都满足，才开始执行。
- 破坏不剥夺条件：允许进程强行从资源占有者那里夺取某些资源
- 破坏环路等待条件：给系统的所有资源编号，规定进程请求所需资源的顺序必须按照资源的编号依次执行。

2.3 如果发生死锁了怎么办？

死锁检测：发生死锁之前总归需要先检测到死锁吧，不然怎么进行接下来的操作？可以通过检测有向图中是否存在环来检测，从一个节点出发进行 dfs，对访问过的节点进行标记，如果访问到了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。
死锁恢复：从下到上逐渐变态。。。
- 撤销进程法：
  - 1) 撤消陷于死锁的全部进程；
  - 2) 逐个撤消陷于死锁的进程，直到死锁不存在；
- 资源剥夺法：
  - 3) 从陷于死锁的进程中逐个强迫放弃所占用的资源，直至死锁消失；
  - 4) 从另外的进程那里强行剥夺足够数量的资源分配给死锁进程，以解除死锁状态。
- 鸵鸟算法，直接不管！

2.4 你能举出一个死锁的例子吗？

要举就直接举刚才的生产者消费者模型，可以知识复用。

对临界区的上锁如果放在了检测缓冲区是否已经满之前，就有可能发生死锁。比如生产者此时要产生一个产品，如果先对临界区上锁，然后检测缓冲区已满，这时就进入等待消费者消耗产品的状态，而消费者想消费产品时，必须先检测临界区是否上锁，此时临界区已经被生产者占有，这样就形成了死锁。

3. 内存管理（重中之重）

3.1 内存管理到底是干什么的？

内存分配
内存回收
地址转换
内存保护功能

3.2 内存管理分页的基础知识主要包括以下几点：

分页思想：将内存分为一个个相等的小分区，称为页框（或页帧、内存块、物理块），对应页框号（从0开始）。然后再按照分区大小把进程拆分成一个个小部分，称为页（或页面），对应页号（从0开始）。进程的各个页面可离散地存放到各个的内存块中，进程的页面与内存的页框有一一对应的关系。各个页面不必连续存放，也不必按先后顺序来，可以放到不相邻的各个页框中。
逻辑地址结构：为了方便计算页号、页内偏移量，页面大小一般设为2的整数幂。
地址转换：虚拟地址与物理地址之间通过页表来映射，页表是存储在内存里的，CPU中的内存管理单元（MMU，Memory Management Unit）将虚拟地址转换成物理地址。
内存碎片：由于页的大小是固定的，就不会产生外部内存碎片问题，只有少量的内部碎片。
内存分配与回收：如果内存空间不够，操作系统会把其他正在运行的进程中的最近没被使用的内存页面给释放掉，也就是暂时写在硬盘上，一旦需要，再加载进来。

3.3 讲讲内存管理的几种机制

分块管理
是连续管理的一种，把内存分为几个大小相等且固定的块，每个进程占用其中一个，如果进程很小的话，会浪费大量的空间。已经淘汰。
分页管理
把内存分为若干个很小的页面，相对比分块的划分力度更大一些。提高内存利用率。减少碎片，页式管理通过页表对应逻辑地址和物理地址。
分段管理
把内存分为几个大小不定的有实际意义的段，比如 main 函数段，局部变量段，通过管理段表来把逻辑地址转为物理地址。
段页式管理
结合了段式管理和页面管理的优点，把主存先分为若干个段，每个段又分为若干个页，也就是说段页式管理的段与段以及段的内部都是离散的。

3.4 分页和分段有什么区别呢？

共同点的话：
- 首先都是离散分配的，单每个页和每个段的内存是连续的。
- 都是为了提高内存利用率，减少内存碎片。
不同点：
- 分页式管理的页面大小是固定的，由操作系统决定；分段式管理的页面是由用户程序所决定的。
- 分页是为了满足操作系统内存管理的需求，每一页是没有实际的意义的；而段是有逻辑意义的，在程序中可认为是代码段、数据段。
- 分页的内存利用率高，不会产生外部碎片；而分段如果单段长度过大，为其分配很大的连续空间不方便，会产生外部碎片。

3.5 讲讲分页管理的快表和多级页表（按照why how的方式来回答，即为什么出现快表，是如何解决痛点的）

3.5.1. 快表

why? 首先快表的引入是为了加快逻辑地址到物理地址的访问速度的，在引入快表之前，由逻辑地址访问到内存的过程是这样的：
a) 首先根据逻辑地址的高位拿到页号
b) 根据页号访问内存中页表，根据页表的映射拿到实际的内存块儿号。（一次访问）
c) 把内存块儿号和逻辑地址的低位拼接，得到物理地址
d) 访问对应的内存物理地址。（二次访问）
这样是需要有两次直接访问内存的过程的，所以为了加快这个速度，引入了快表，快表可以认为是一个 Cache，内容是页表的一部分或者全部内容。和页表的功能是一样的，只不过比在内存中的页表的访问速度要快很多。
how? 根据局部性原理，被访问后的内存块儿很可能在短时间内再次被访问，可能程序在一段时间内会多次访问同一个页表项。所以在每次访问页表项时，先在快表里查询是否有该页表项，如果没有再去页表中查询，并把查到的页表项放入快表。如果快表满了，就根据一些策略把里面的页表项淘汰掉，再把新查询的页表加入进去。

3.5.2 多级页表

why? 多级页表主要是为了解决页表在内存中占用空间太大的问题的，典型的时间换空间。
how？讲个例子即可：在引入多级页表之前，我们使用单级页表来进行存储页表项，假如虚拟内存为 4GB，每个页大小为 4KB，那么需要的页表项就为 4GB / 4KB = 1M 个！每个页表项一般为 4B，那么就需要 4MB 的空间，大概需要占用 1000 个页来存页表项。
所以如果引入两级页表，让一级页表的每个页表项不再映射 4KB，而是映射 4MB，那么需要的一级页表项的个数为 4GB / 4MB = 1K 个，再让每个一级的页表项映射 1K 个二级页表项。当一级页表的某个页表项被用到时，再把该一级页表项对应的所有 1K 个二级页表项加载到内存中，这样可以节省大量的空间！

3.6 讲讲虚拟地址和物理地址？为什么要有虚拟地址空间？

我们在写程序的时候打交道的都是虚拟地址，比如 C 语言的指针，这个虚拟地址由操作系统决定，而物理地址指的是真实内存地址寄存器的地址。现代处理器通常使用虚拟寻址，用 MMU 把虚拟地址翻译成物理地址才能访问到真正的物理地址。

那么为什么要有虚拟地址呢？

如果没有虚拟地址空间的话，我们操作的都是直接的物理地址，这样用户程序可以直接访问到底层的物理地址，很容易破坏操作系统，造成操作系统崩溃。
想要同时运行多个程序特别困难，多个程序可能对同一个寄存器进行操作，会发生崩溃。

通过虚拟地址就会得到如下优势（记不住也无所谓这一段）

程序可以使用一系列相邻的虚拟地址来访问物理内存中不相邻的内存缓冲区。
程序可以使用一系列虚拟地址访问大于可用物理内存的内存缓冲区。当物理内存的供应量变小的时候，内存管理器会将物理页面保存到磁盘里。数据或代码页会根据需要在物理内存和磁盘之间移动。
不同进程使用的虚拟地址彼此隔离。一个进程中的代码无法更改正在由另一个进程使用的物理内存。

3.7 讲讲虚拟内存？

按照 why and how 来回答！

why? 传统的内存管理必须把作业一次性的 load 到内存中，并且一直驻留到其作业运行结束，当作业很大时，是没有办法一次性装入内存的。
how? 而在一段时间内，只需要访问小部分数据就可以保证程序的正常运行。所以基于局部性原理，在程序加载的时候，把很快就会用到的部分放入内存中，暂时用不到的部分留在磁盘上。在程序执行的过程中，当信息不在内存时，再从外存把信息加载到内存里。当内存不够的时候，根据一些策略把用不到的内存换出到外存中，从而腾出空间给要调入内存的信息。而在 os 的管理下，让应用程序认为自己拥有一连续可用的内存，产生独享主存的错觉，这就是虚拟内存。

其实虚拟内存的基础是局部性原理，也正是因为有局部性原理，程序运行时才可以做到只装入部分到内存就可以运行。

3.8 虚拟内存的三种实现技术

请求分页式存储管理
建立在分页管理的基础之上，为了支持虚拟内存实现了请求调页和页面置换功能。其具体流程是这样的：
首先作业运行时，仅装入当前要执行的部分页面即可。
假如在运行的过程中，发现要请求的页面不在内存中，那么处理器通知操作系统按照对应的页面置换算法把相应的页面调入到内存中。
如果发现在把页面调入内存时，内存已满，同时也可以把不用的页面置换出去，以便腾出空间装入新的页面。
请求分段式存储管理
和分页是一样的，把页换成段即可。
请求段页式存储管理
总结
需要一定量的内存和外存，在刚开始运行的时候，只把部分要执行的页面加载到内存，就可以运行了。
缺页中断，如果指令或数据不在内存，则处理器通知操作系统把页面段调入到内存。
虚拟地址空间，都需要把虚拟地址转换为物理地址。

这和内存管理的机制有什么不同呢？
请求分页式存储管理建立在分页管理之上，他们的根本区别是用不用把程序所需的全部地址空间 load 到内存里。请求分页式不需要全部 load 到内存中，而分页式管理需要，前者能够提供虚拟内存，后者不可以！

3.9 讲讲页面置换算法

答：当使用请求分页存储来管理内存时，发生缺页中断，就是要访问的页面不在内存中，这时就需要操作系统把其调入主存后再进行访问。

而在发生缺页中断时，内存中没有空闲的页面，就必须在内存中根据一定的策略挪出一些不用的页面，可以把页面置换算法看成是淘汰机制。

OPT 页面置换法，最佳页面置换：不可实现，不可预测哪个是不用的。
FIFO 先到先出算法，把在内存中停留时间最长的页面置换出去
LRU 最近最久未使用页面置换算法：LRU 算法赋予每一个页面一个访问字段，来记录一个页面最近一次访问到现在所经历的时间 T，需要淘汰一个页面时，把最久没有使用的页面淘汰掉就可以了。
LFU 最少使用算法：把使用最少的页面淘汰掉。