1. 操作系统

1. 概念：是控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配，以提供给用户和其它软件接口和环境，它是计算机系统中最基本的系统软件。
   

2. 功能和目标：
   （1）资源的管理者：处理机管理、存储器管理、文件管理、设备管理
   （2）向用户提供服务：命令接口、程序接口（由一组系统调用组成）、GUI用户图形界面
   （3）对硬件机器的扩展：扩展机器

3. 特征
   （1）并发：多个事件之间微观上交替执行，宏观上同时执行 。 需要注意：并行：多个事件宏观上微观上同时执行
   （2）共享：互斥共享 和 同时共享。互斥共享举例：同一时间段摄像头只能分配给其中一个进程。同时共享举例：一个进程发送文件A和发送文件B，微观上交替访问系统资源，宏观同时发送
   （3）虚拟：把一个物理上的实体变为若干个逻辑上的对应物。
   （4）异步：多个进程并发执行，但由于系统资源有限，各进程以不可预知速度的向前推进（因为某个进程可能受系统资源有限的影响）

4. 发展与分类（未复习）

5. 操作系统的内核：
   （1）不同操作系统的内核划分不同（操作系统的体系结构）：分为 微内核（只包含图中下层部分） 和 大内核（包含图中上下层部分）。
   
   （2）操作系统的运行机制：包括以下几个部分：
       两种指令：特权指令 和 非特权指令
       两种处理机状态：核心态 和 用户态
       两种程序：内核程序 和 应用程序
   （3）思路：
      1. 实现操作系统内核功能的那些程序就是内核程序
      2. 需要执行进程管理、存储器管理等功能（需要执行特权指令），即处理机需要从用户态切换为核心态，这也引出了 大内核的优点 是它包括了操作系统的主要功能，运行在核心态，无需切换（缺点：内核代码庞大，难以维护）。微内核的缺点 是需要频繁地切换在核心态和用户态之间切换，性能低（优点：内核功能少，方便维护）。

6. 中断和异常
   （1）中断：分为 内中断 和 外中断。如下：
      内中断：进程当遇到 需要系统资源 或者 需要其它进程配合 或者 该进程时间片已到 等时候，会发生内中断，处理机收到计时部件发出的中断信号，切换为核心态，此时需要操作系统介入，把处理机使用权限给操作系统，操作系统内核开始对中断信号进行处理，管理工作完成之后，把处理机使用权限还给用户进程。
      外中断：当外部I/O设备任务完成之后，设备向处理机发出中断信号，处理机收到后，切换为核心态，此时需要操作系统介入，把处理机使用权限给操作系统，操作系统内核开始对中断信号进行处理，管理工作完成之后，把处理机使用权限还给用户进程。
   （2）系统调用：
      库函数： 库函数可以看作是对系统调用的封装和扩展，提供更加方便和高级的编程接口。

2. 进程

1. 单核和多核：单核只允许同一时刻一个进程被处理机服务。多核允许多个处理机服务多个进程

2. 进程概念：进程就是一个程序在计算机中的执行过程，它可以独立运行，也可以与其他进程进行通信和协作，同时需要访问和操作数据集合。它是系统进行资源分配和调度的一个独立单位。（强调 动态）

3. 进程实体概念：PCB（管理进程所需信息）、数据段（变量等）、程序段（程序代码）。一般情况下，进程实体简称为进程。（强调 静态）

4. 进程的特征：

5. 进程的状态与转换
   （1）状态
     运行态：占有CPU，并在CPU上运行
     就绪态：具备资源等所有运行条件，等待CPU调度
     阻塞态：因等待某一事件（如打印机系统资源）暂时不能运行
     创建态：未进入就绪态，操作系统为它分配所需内存等系统资源，并为其创建PCB
     终止态：数组越界等报错，该进程终止，操作系统撤销系统资源和PCB等工作
   （2）状态转换：

6. 进程控制
   （1）概念：实现进程状态转换，使转换过程操作具有原子性
   （2）实现：原语（关中断指令 和 开中断指令），处理机需要切换到核心态
   
   （3）进程控制（状态转换），怎么做：

7. 进程通信
   概念：进程通信就是指进程之间的信息交换。进程是分配系统资源的单位，因此各进程拥有的内存地址空间相互独立，为了保证安全，一个进程不能直接访问另一个进程的地址空间。
   通信方式：
    （1）共享存储：分为
         1. 基于数据结构的共享（限制多，低级通信）
         2. 基于存储区的共享 （数据形式、存放位置由进程控制而不是操作系统。高级通信）
   注意：两个进程对共享空间的访问必须是互斥的，互斥工具由操作系统提供。
    （2）管道通信：
         1. 管道只能采用半双工通信，某一时间段内只能实现单向的传输。
         2. 各进程要互斥地访问管道。
         3. 当管道写满时，写进程的write()系统调用将被阻塞；当管道为空时，读进程的read()系统调用将被阻塞
    （3）消息传递：分为直接通信 和 间接通信。一个进程通过发送原语发送给另一个进程，另一个进程通过接受原语接受。二者区别：有无中间者。例如 “电子邮件系统”

8. 线程
   （1）概念：线程是一个进程内部的一个控制序列，或者说是执行流（轻量级的进程）。（一个进程中，多个线程并发执行，例如qq可以聊天和发文件）
   （2）引入线程之后：
       1. 线程是一个基本的CPU调度单位，进程内的各线程之间并发，进一步提高并发度。
       2. 进程只作为出CPU资源之外的系统资源的分配单位。
       3. 并发带来的系统开销减小。进程间并发需要切换进程的运行环境，同一进程间的线程并发，不需要切换进程环境，开销减小。
   （3）线程的实现方式：多线程模型，未复习

9. 处理机调度的层次
   （1）高级调度（作业调度）：按照一定的原则从外存上处于后备队列的作业中挑选一个或者多个作业，给它们分配内存等必要资源，并建立相应的进程（PCB），使它们等待被处理机调度。
   （2）中级调度：由于内存有限，将暂时不能运行的进程调至外存等待（进程状态变为挂起状态），等它重新具备了运行条件且内存稍有空闲时，再重新调入内存。注意：PCB不会调到外存，它常驻内存，操作系统通过内存中的PCB保持对进程管理。被挂起的进程对应PCB会被放到挂起队列中。
   七状态模型：
   （3）低级调度（进程调度）：按照某种方法和策略（调度算法）从就绪队列中选取一个进程，将处理机分配给它。是最基本的一种调度。
   （4）对比：

10. 处理机调度的时机
    （1）当前运行进程主动放弃：
       1. 进程正常终止
       2. 发生异常终止
       3. 主动请求阻塞（如 I/O等待）
    （2）当前运行进程被动放弃：
       1. 时间片用完
       2. 有更紧急的事情要处理（如 I/O中断）
       3. 有更高优先级进程进入就绪队列
    注意：不能进行进程调度与切换的情况：
       1. 在处理中断的过程中
       2. 进程在操作系统内核程序临界区
       3. 原语
    临界区：访问临界资源的那段代码。
    临界资源：一个时间段内只允许一个进程使用的资源。
    当一个进程处于操作系统内核程序临界区，并且这个临界区要访问就绪队列，并且访问时候，会给就绪队列上锁，如果进程还没有退出内核程序临界区，则就绪队列不会解锁，处理机调度就不能从就绪队列中挑选进程。

11. 处理机调度算法
    （1）先来先服务（非抢占式）
        对象：用于进程或者作业调度
        规则：按照进程或者作业到达时间从小到大进行服务。
        造成饥饿：不会。
        优点：公平、实现简单
        缺点：对排在长作业后面的短作业需要等待很长时间。
    （2）短作业(进程)优先（抢占式和非抢占式）
        对象：用于进程或者作业调度
        规则：最短的作业或者进程优先得到服务
        造成饥饿：会。（源源不断的短作业或者短进程到来）
        抢占式版本：最短剩余时间优先算法
        优点：平均等待时间、平均周转时间短
        缺点：不公平。对短作业有利，对长作业不利。运行时间不真实。
    （3）高响应比优先（非抢占式）
        对象：用于进程或者作业调度
        规则：每次调度时候计算各个作业或者进程的响应比，优先服务响应比高的
        造成饥饿：不会。
        优点：综合考虑了等待时间和运行时间
        响应比：（等待时间+要求服务时间）/ 要求服务时间
    （4）时间片轮转
        对象：用于进程调度
        规则：按照就绪队列中进程的先后到达顺序，轮流让各进程执行一个时间片
        抢占式：当一个时间片过了，进程还未执行完，会剥夺处理机使用权
        优点：公平；响应快，适用于分时操作系统
        缺点：进程切换频率高，系统开销大；不区分任务的紧急程度
    （5）优先级调度算法
        对象：用于进程或者作业调度
        规则：每个作业或者进程有各自的优先级，调度时选优先级高的
        是否可抢占：都有。当就绪队列改变时候，优先级较高的会抢占当前运行的进程的处理机使用权
        优点：用优先级区分紧急程度，适用于实时操作系统。
        缺点：若远远不断有高优先级进程到来，可能出现饥饿
        饥饿：会
    （6）多级反馈队列
    

12. 进程同步和进程互斥
    （1）进程同步：并发性带来了异步性，需要进程同步解决异步问题。有的进程之间需要相互配合地完成工作，各进程的工作推进需要遵循一定的先后顺序。
    （2）进程互斥：对临界资源的访问，需要互斥的进行，即同一时间段只能允许一个进程访问该资源。
         进程互斥是什么？
         四个部分：进入区、临界区、退出区、剩余区
         四个原则：空闲让进、忙则等待、有限等待、让权等待
         如图：

13. 死锁
    （1）概念：各进程互相等待对方手里的资源，导致各进程阻塞，无法向前推进的现象。
    （2）产生死锁满足四个条件：
        1. 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁
        2. 不剥夺条件：进程所获得的资源在未使用完之前，不能由其它进程强行夺走，只能主动释放。
        3. 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。
        4. 请求和保持条件：进程已经获得了至少一个资源，但又提出新的资源请求，而该资源又被其它请求占有，此时请求进程被阻塞，同时对自己所持资源保持不放。
        注意：发生死锁时必有循环等待，循环等待未必死锁。
    （2）预防死锁：破坏一个或多个死锁产生的四个必要条件（具体方案先略过）
        1. 破坏互斥条件
        2. 破坏不剥夺条件
        3. 破坏请求和保持条件
        4. 破坏循环等待条件
    （4）避免死锁：
        1. 什么是安全序列？指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要找出一个安全序列，系统就是安全状态。（安全序列可能有多个），如果系统找不到任何一个安全序列，则系统进入不安全状态。此后，若有进程提前归还了资源，系统也有可能进入安全状态。所以，如果系统处于安全状态，就一定不会发生死锁，否则就可能发生死锁。
        2. 银行家算法：
          核心思想：在进程提出资源申请时候，先预判此次分配是否会导致系统进入不安全状态。如果进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。
          步骤：
            1. 检查此次申请是否超过了之前声明的最大需求数。
            2. 检查此时系统剩余的资源是否能满足此次请求。
            3. 试探着分配，更改数据（例如修改剩余各资源数量），并用安全性算法检查此次分配是否会导致系统进入不安全状态。
            安全性算法的步骤：检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。
          优点：避免 死锁和资源浪费。
          缺点：需要预先知道每种资源的总量和当前可用的数量，可能会导致一些限制。此外，安全性算法会增加系统的开销
    （5）死锁的检测和解除。
        1. 死锁的检测：用某种数据结构（资源分配图）来保存资源的请求和分配信息。提供一种算法（消除边），判断系统是否已进入死锁状态。
    如果按照系统中剩余资源可以满足进程需求，那么该进程可以执行下去，等该进程结束后，归还资源使某些阻塞进程得到资源也能够执行，如此循环下去，若能够消除资源分配图的所有边，此时系统就一定没有发生死锁，如果最终不能消除所有边，那么此时就是发生了死锁，最终还连着边的是处于死锁中的进程。
        2. 死锁的解除：
          1. 资源剥夺法：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其它的进程。
          2. 撤销进程法：强制撤销部分、深圳全部死锁进程，并剥夺这些进程的资源。（这种方式实现简单，付出代价可能会很大，例如一个运行了很久的进程将要运行完但是被撤销了，这就造成了很大的资源浪费）
          3. 进程回退法：让一个或多个进程回退到足以避免死锁的地步。
          对谁（进程）下手呢？
            进程优先级。（优先级低的）
            已执行多长时间。（执行时间少的）
            还要多久能完成。（还要很久完成的）
            进程已经使用了多少资源。（占有资源多的）
            进程是交互式还是批处理式。（用户体验，批处理式的）

3. 内存管理

1. 内存介绍
   程序执行前需要先放到内存中才能被CPU处理
2. 连续分配管理
   （1）连续分配的概念：为用户进程分配的必须是一个连续的内存空间
   （2）单一连续分配
   （3）固定分区分配****产生大量的内部碎片
   

（4）动态分区分配 产生大量外部碎片，“紧凑”技术时间代价高

以下为非连续分配的管理方式（基本分页，基本分段，段页式）

3. 基本分页存储管理（将进程内存分页放入不连续的分区）
   （1）引出：连续分配方式有产生（内部、外部）碎片的缺点，并且解决其会花费代价高。
   （2）基本分页存储概念：每个分区是一个页框。页框的编号为页框号。 进程内存的分区，每个分区为一个页。页的编号为页号。
   

4. 基本分段存储管理（进程的地址空间会按照程序的自身逻辑关系划分为若干个段，每段从0开始编址）
   （1）分段：进程的地址空间会按照程序的自身逻辑关系划分为若干个段，每**段从0开始编址
   
   （2）内存分配规则：以段为单位进行分配，每个段在内存中占连续空间，但各段之间可以不相邻
   
   (3) 段表
     概念：从物理内存中找到各个逻辑段的存放位置（段号可省略）
   注意：1. 每个段对应段表中的一个项，其中记录了该段在内存中的起始位置和段的长度。
      2. 各个段表项的长度是相同的，因此段号可以隐含。

5. 段页式管理
   （1）引出：结合分页管理和分段管理。
   （2）概念：将进程按自身逻辑分段，再将各段分页，再将内存空间分为大小相同的内存块。
   （3）段表和页表在其中作用
   （4）段页式地址变换中要得到物理地址须经过三次内存访问
       1. 第一次访问段表，得到页表起始地址；
       2. 第二次访问页表，得到物理页号；
       3. 第三次将物理页号与页内位移组合，得到物理地址。

6. 虚拟内存（两张图片就可理解）

第一张

第二张

7.栈和堆的区别

1. 分别由谁分配和释放？
   栈：由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
   堆：一般由程序员分配释放
2. 怎么申请栈和堆空间？
   栈：只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。
   堆：操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，会 遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序
3. 申请栈和堆空间谁大？
   栈：一块连续的内存的区域（栈顶的地址和栈的最大容量是系统预先规定好的），从栈获得的空间较小。
   堆：系统是用链表来存储的空闲内存地址的，自然是不连续的。堆获得的空间比较灵活，也比较大。

操作系统八股：

1. 操作系统的四个特性？
   并发：同一段时间内多个程序执行（与并行区分，并行指的是同一时刻有多个事件，多处理器系统可以使程序并行执行）
   共享：系统中的资源可以被内存中多个并发执行的进线程共同使用
   虚拟：通过分时复用（如分时系统）以及空分复用（如虚拟内存）技术把一个物理实体虚拟为多个
   异步：系统进程用一种走走停停的方式执行，（并不是一下子走完），进程什么时候以怎样的速度向前推进是不可预知的
2. 什么是操作系统？请简要概述一下
   操作系统是管理计算机硬件和软件资源的计算机程序，提供一个计算机用户与计算机硬件系统之间的接口。
   向上对用户程序提供接口，向下接管硬件资源。
   操作系统本质上也是一个软件，作为最接近硬件的系统软件，负责处理器管理、存储器管理、设备管理、文件管理和提供用户接口。
3. 操作系统有哪些分类？
   操作系统常规可分为批处理操作系统、分时操作系统、实时操作系统。
   若一个操作系统兼顾批操作和分时的功能，则称该系统为通用操作系统。
   常见的通用操作系统有：Windows、Linux、MacOS等。
4. 什么是内核态和用户态？
   内核态是操作系统管理程序执行时所处的状态，能够执行包含特权指令在内的一切指令，能够访问系统内所有的存储空间。
   用户态是用户程序执行时处理器所处的状态，不能执行特权指令，只能访问用户地址空间。
   用户程序运行在用户态,操作系统内核运行在内核态。
5. 并发和并行的区别
   并发 ：指宏观上看起来两个程序在同时运行，比如说在单核cpu上的多任务。但是从微观上看两个程序的指令是交织着运行的，指令之间交错执行，在单个周期内只运行了一个指令。这种并发并不能提高计算机的性能，只能提高效率（如降低某个进程的相应时间）。
   并行 ：指严格物理意义上的同时运行，比如多核cpu，两个程序分别运行在两个核上，两者之间互不影响，单个周期内每个程序都运行了自己的指令，也就是运行了两条指令。这样说来并行的确提高了计算机的效率。所以现在的cpu都是往多核方面发展。
6. 什么是进程？
   进程一般由以下的部分组成：
   （1）进程控制块PCB，是进程存在的唯一标志，包含进程标识符PID，进程当前状态，程序和数据地址，进程优先级、CPU现场保护区（用于进程切换），占有的资源清单等。
   （2）程序段
   （3）数据段
7. 简述进程间通信方法
   （1）管道：管道是一种半双工的通信方式，只能在具有亲缘关系的进程之间使用。一个进程向管道中写入数据，另一个进程从管道中读取数据。管道可以是匿名管道或命名管道。
   （2）共享内存：共享内存是一种高效的进程间通信方式，可以在多个进程之间共享同一块物理内存。多个进程可以同时读写共享内存中的数据，因此需要进行同步和互斥操作。
   （3）信号量：信号量是一种计数器，用于控制多个进程对共享资源的访问。当一个进程访问共享资源时，它需要获取信号量，如果信号量的值为0，则进程被阻塞，直到另一个进程释放了信号量。
   （4）消息队列：消息队列是一种进程间通信方式，可以在不同进程之间传递数据。一个进程向消息队列中发送消息，另一个进程从消息队列中接收消息。消息队列可以是有名队列或匿名队列。
   （5）套接字：套接字是一种网络通信方式，可以在不同主机之间进行进程间通信。套接字可以用于TCP/IP协议或UDP协议的通信。
   （6）文件映射：文件映射是一种将文件映射到进程地址空间的方式，可以在多个进程之间共享同一文件。多个进程可以同时读写文件映射中的数据，因此需要进行同步和互斥操作。
8. 进程如何通过管道进行通信？
   （1）其本质是一个伪文件(实为内核缓冲区)
   （2）由两个文件描述符引用，一个表示读端，一个表示写端。
   （3）规定数据从管道的写端流入管道，从读端流出。
    局限性：
   （1）数据自己读不能自己写。
   （2）数据一旦被读走，便不在管道中存在，不可反复读取。
   （3）由于管道采用半双工通信方式。因此，数据只能在一个方向上流动。
   （4）只能在有公共祖先的进程间使用管道。
9. 进程调度的时机
   （1）当前运行的进程运行结束。
   （2）当前运行的进程由于某种原因阻塞。
   （3）执行完系统调用等系统程序后返回用户进程。
   （4）在使用抢占调度的系统中，具有更高优先级的进程就绪时。
   （5）分时系统中，分给当前进程的时间片用完。
10. 不能进行进程调度的情况
    （1）在中断处理程序执行时。
    （2）在操作系统的内核程序临界区内。
    （3）其它需要完全屏蔽中断的原子操作过程中。
11. 进程的调度算法
    （1）先到先服务调度算法
    （2）短作业优先调度算法
    （3）优先级调度算法
    （4）时间片轮转调度算法
    （5）高响应比优先调度算法
    （6）多级队列调度算法
    （7）多级反馈队列调度算法
12. 进程调度算法的基本设计指标
    （1）CPU利用率
    （2）系统吞吐率，即单位时间内CPU完成的作业的数量。
    （3）响应时间。
    （4）周转时间。是指作业从提交到完成的时间间隔。从每个作业的角度看，完成每个作业的时间也是很关键（平均周转时间、带权周转时间、平均带权周转时间）
13. 什么是孤儿进程？僵尸进程?
    孤儿进程：父进程退出，子进程还在运行的这些子进程都是孤儿进程，孤儿进程将被init进程（1号进程）所收养，并由init进程对他们完成状态收集工作。
    僵尸进程：进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait 获waitpid 获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中的这些进程是僵尸进程。
14. 什么是线程？
    （1）是进程划分的任务，是一个进程内可调度的实体，是CPU调度的基本单位，用于保证程序的实时性，实现进程内部的并发。
    （2）线程是操作系统可识别的最小执行和调度单位。每个线程都独自占用一个虚拟处理器：独自的寄存器组，指令计数器和处理器状态。
    （3）每个线程完成不同的任务，但是属于同一个进程的不同线程之间共享同一地址空间（也就是同样的动态内存，映射文件，目标代码等等），打开的文件队列和其他内核资源。
15. 简述线程和进程的区别和联系
    （1）一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。线程依赖于进程而存在。
    （2）进程在执行过程中拥有独立的地址空间，而多个线程共享进程的地址空间。（资源分配给进程，同一进程的所有线程共享该进程的所有资源。同一进程中的多个线程共享代码段（代码和常量），数据段（全局变量和静态变量），扩展段（堆存储）。但是每个线程拥有自己的栈段，栈段又叫运行时段，用来存放所有局部变量和临时变量。）
    （3）进程是资源分配的最小单位，线程是CPU调度的最小单位。
    （4）通信：由于同一进程中的多个线程具有相同的地址空间，使它们之间的同步和通信的实现，也变得比较容易。进程间通信，线程间可以直接读写进程数据段（如全局变量）来进行通信（需要一些同步方法，以保证数据的一致性）。
    （5）进程编程调试简单可靠性高，但是创建销毁开销大；线程正相反，开销小，切换速度快，但是编程调试相对复杂。
    （6）进程间不会相互影响；一个进程内某个线程挂掉将导致整个进程挂掉。
    （7）进程适应于多核、多机分布；线程适用于多核。
16. 多线程模型
    （1）多对一模型。将多个用户级线程映射到一个内核级线程上。该模型下，线程在用户空间进行管理，效率较高。缺点就是一个线程阻塞，整个进程内的所有线程都会阻塞。几乎没有系统继续使用这个模型。
    （2）一对一模型。将内核线程与用户线程一一对应。优点是一个线程阻塞时，不会影响到其它线程的执行。该模型具有更好的并发性。缺点是内核线程数量一般有上限，会限制用户线程的数量。更多的内核线程数目也给线程切换带来额外的负担。linux和Windows操作系统家族都是使用一对一模型。
    （3）多对多模型。将多个用户级线程映射到多个内核级线程上。结合了多对一模型和一对一模型的特点。
17. 什么是虚拟内存？
    （1）它将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在磁盘和主存之间来回传送数据，通过这种方式，它高效地使用了主存。
    （2）它为每个进程提供了一致的地址空间，从而简化了内存管理。
    （3）它保护了每个进程的地址空间不被其他进程破坏。
18. 常见的页面置换算法？
    （1）先进先出算法
    思路：置换最先调入内存的页面，即置换在内存中驻留时间最久的页面。
    实现：按照进入内存的先后次序排列成队列，从队尾进入，从队首删除。
    特点：实现简单；性能较差，调出的页面可能是经常访问的
    （2）最近最少使用算法
    思路：置换最近一段时间以来最长时间未访问过的页面。根据程序局部性原理，刚被访问的页面，可能马上又要被访问；而较长时间内没有被访问的页面，可能最近不会被访问。
    实现：缺页时，计算内存中每个逻辑页面的上一次访问时间，选择上一次使用到当前时间最长的页面
    特点：可能达到最优的效果，维护这样的访问链表开销比较大
    （3）最不常用算法
    思路：缺页时，置换访问次数最少的页面
    实现：每个页面设置一个访问计数，访问页面时，访问计数加1，缺页时，置换计数最小的页面
    特点：算法开销大，开始时频繁使用，但以后不使用的页面很难置换