引论1.什么是操作系统操作系统是一种运行在内核态的软件。它是应用程序和硬件之间的媒介向应用程序提供硬件的抽象以及管理硬件资源。屏蔽了硬件层的复杂性本质是个软件。2.操作系统主要有哪些功能操作系统最主要的功能• 处理器CPU管理CPU的管理和分配主要指的是进程管理。• 内存管理内存的分配和管理主要利用了虚拟内存的方式。• 外存管理外存磁盘等的分配和管理将外存以文件的形式提供出去。• I/O管理对输入/输出设备的统一管理。除此之外还有保证自身正常运行的健壮性管理防止非法操作和入侵的安全性管理。操作系统主要功能操作系统结构1.什么是内核内核是一个计算机程序它是操作系统的核心提供了操作系统最核心的能力可以控制操作系统中所有的内容。2.什么是用户态和内核态内核具有很⾼的权限可以控制 cpu、内存、硬盘等硬件出于权限控制的考虑因此⼤多数操作系统把内存分成了两个区域• 内核空间这个内存空间只有内核程序可以访问• ⽤户空间这个内存空间专⻔给应⽤程序使⽤权限比较小⽤户空间的代码只能访问⼀个局部的内存空间⽽内核空间的代码可以访问所有内存空间。因此当程序使⽤⽤户空间时我们常说该程序在⽤户态执⾏⽽当程序使用内核空间时程序则在内核态执⾏。3.用户态和内核态是如何切换的应⽤程序如果需要进⼊内核空间就需要通过系统调⽤来进入内核态用户态内核态切换内核程序执⾏在内核态⽤户程序执⾏在⽤户态。当应⽤程序使⽤系统调⽤时会产⽣⼀个中断。发⽣中断后 CPU 会中断当前在执⾏的⽤户程序转⽽跳转到中断处理程序也就是开始执⾏内核程序。内核处理完后主动触发中断把 CPU 执⾏权限交回给⽤户程序回到⽤户态继续⼯作。4.什么是系统调用我们运行的程序基本都是运行在用户态如果我们调用操作系统提供的内核态级别的子功能咋办呢那就需要系统调用了也就是说在我们运行的用户程序中凡是与系统态级别的资源有关的操作如文件管理、进程控制、内存管理等)都必须通过系统调用方式向操作系统提出服务请求并由操作系统代为完成。系统调用这些系统调用按功能大致可分为如下几类• 设备管理完成设备输入输出设备和外部存储设备等的请求或释放以及设备启动等功能。• 文件管理完成文件的读、写、创建及删除等功能。• 进程管理进程的创建、撤销、阻塞、唤醒进程间的通信等功能。• 内存管理完成内存的分配、回收以及获取作业占用内存区大小及地址等功能。系统调用和普通库函数调用非常相似只是系统调用由操作系统内核提供运行于内核态而普通的库函数调用由函数库或用户自己提供运行于用户态。总结系统调用是应用程序与操作系统之间进行交互的一种方式通过系统调用应用程序可以访问操作系统底层资源例如文件、设备、网络等。进程和线程1.并行和并发有什么区别并发就是在一段时间内多个任务都会被处理但在某一时刻只有一个任务在执行。单核处理器做到的并发其实是利用时间片的轮转例如有两个进程A和BA运行一个时间片之后切换到BB运行一个时间片之后又切换到A。因为切换速度足够快所以宏观上表现为在一段时间内能同时运行多个程序。并行就是在同一时刻有多个任务在执行。这个需要多核处理器才能完成在微观上就能同时执行多条指令不同的程序被放到不同的处理器上运行这个是物理上的多个进程同时进行。2.什么是进程上下文切换对于单核单线程 CPU 而言在某一时刻只能执行一条 CPU 指令。上下文切换 (Context Switch) 是一种将 CPU 资源从一个进程分配给另一个进程的机制。从用户角度看计算机能够并行运行多个进程这恰恰是操作系统通过快速上下文切换造成的结果。在切换的过程中操作系统需要先存储当前进程的状态 (包括内存空间的指针当前执行完的指令等等)再读入下一个进程的状态然后执行此进程。因为进程是资源分配和调度的基本单位线程是进程的一个执行路径进程中的多个线程共享进程的资源。线程是cpu分配的最小单位3.进程有哪些状态当一个进程开始运行时它可能会经历下面这几种状态上图中各个状态的意义• 运⾏状态Runing该时刻进程占⽤ CPU• 就绪状态Ready可运⾏由于其他进程处于运⾏状态⽽暂时停⽌运⾏• 阻塞状态Blocked该进程正在等待某⼀事件发⽣如等待输⼊/输出操作的完成⽽暂时停⽌运⾏这时即使给它CPU控制权它也⽆法运⾏当然进程还有另外两个基本状态• 创建状态new进程正在被创建时的状态• 结束状态Exit进程正在从系统中消失时的状态4.什么是僵尸进程僵尸进程是已完成且处于终止状态但在进程表中却仍然存在的进程。僵尸进程一般发生有父子关系的进程中一个子进程的进程描述符在子进程退出时不会释放只有当父进程通过 wait() 或 waitpid() 获取了子进程信息后才会释放。如果子进程退出而父进程并没有调用 wait() 或 waitpid()那么子进程的进程描述符仍然保存在系统中。5.什么是孤儿进程一个父进程退出而它的一个或多个子进程还在运行那么这些子进程将成为孤儿进程。孤儿进程将被 init 进程 (进程 ID 为 1 的进程) 所收养并由 init 进程对它们完成状态收集工作。因为孤儿进程会被 init 进程收养所以孤儿进程不会对系统造成危害。6.进程有哪些调度算法进程调度就是确定某一个时刻CPU运行哪个进程常见的进程调度算法有进程调度算法• 先来先服务非抢占式的调度算法按照请求的顺序进行调度。有利于长作业但不利于短作业因为短作业必须一直等待前面的长作业执行完毕才能执行而长作业又需要执行很长时间造成了短作业等待时间过长。另外对I/O密集型进程也不利因为这种进程每次进行I/O操作之后又得重新排队。这似乎很公平但是当一个长作业先运行了那么后面的短作业等待的时间就会很长不利于短作业。FCFS 对长作业有利适用于 CPU 繁忙型作业的系统而不适用于 I/O 繁忙型作业的系统。先来先服务• 短作业优先非抢占式的调度算法按估计运行时间最短的顺序进行调度。长作业有可能会饿死处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来那么长作业永远得不到调度。短作业优先• 优先级调度为每个进程分配一个优先级按优先级进行调度。为了防止低优先级的进程永远等不到调度可以随着时间的推移增加等待进程的优先级。优先级调度• 时间片轮转将所有就绪进程按 先来先服务的原则排成一个队列每次调度时把 CPU 时间分配给队首进程该进程可以执行一个时间片。当时间片用完时由计时器发出时钟中断调度程序便停止该进程的执行并将它送往就绪队列的末尾同时继续把 CPU 时间分配给队首的进程。时间片轮转算法的效率和时间片的大小有很大关系因为进程切换都要保存进程的信息并且载入新进程的信息如果时间片太小会导致进程切换得太频繁在进程切换上就会花过多时间。 而如果时间片过长那么实时性就不能得到保证。时间片轮转• 最短剩余时间优先最短作业优先的抢占式版本按剩余运行时间的顺序进行调度。 当一个新的作业到达时其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少则挂起当前进程运行新的进程。否则新的进程等待。7.进程间通信有哪些方式进程间通信方式• 管道管道可以理解成不同进程之间的对白一方发声一方接收声音的介质可是是空气或者电缆进程之间就可以通过管道所谓的管道就是内核中的一串缓存从管道的一端写入数据就是缓存在了内核里另一端读取也是从内核中读取这段数据。另外管道传输的数据是无格式的流且大小受限。管道可以分为两类匿名管道和命名管道。匿名管道是单向的只能在有亲缘关系的进程间通信命名管道是双向的可以实现本机任意两个进程通信。• 信号 信号可以理解成一种电报发送方发送内容指定接收进程然后发出特定的软件中断操作系统接到中断请求后找到接收进程通知接收进程处理信号。对于异常情况下的工作模式就需要用「信号」的方式来通知进程。比如kill -9 1050就表示给PID为1050的进程发送SIGKIL信号。Linux系统中常用信号1SIGHUP用户从终端注销所有已启动进程都将收到该进程。系统缺省状态下对该信号的处理是终止进程。2SIGINT程序终止信号。程序运行过程中按CtrlC键将产生该信号。3SIGQUIT程序退出信号。程序运行过程中按Ctrl\键将产生该信号。4SIGBUS和SIGSEGV进程访问非法地址。5SIGFPE运算中出现致命错误如除零操作、数据溢出等。6SIGKILL用户终止进程执行信号。shell下执行kill -9发送该信号。7SIGTERM结束进程信号。shell下执行kill 进程pid发送该信号。8SIGALRM定时器信号。9SIGCLD子进程退出信号。如果其父进程没有忽略该信号也没有处理该信号则子进程退出后将形成僵尸进程。• 消息队列消息队列就是保存在内核中的消息链表包括Posix消息队列和System V消息队列。有足够权限的进程可以向队列中添加消息被赋予读权限的进程则可以读走队列中的消息。消息队列克服了信号承载信息量少管道只能承载无格式字节流以及缓冲区大小受限等缺点。消息队列消息这种模型两个进程之间的通信就像平时发邮件一样你来一封我回一封可以频繁沟通了。但邮件的通信方式存在不足的地方有两点一是通信不及时二是附件也有大小限制这同样也是消息队列通信不足的点。消息队列不适合比较大数据的传输因为在内核中每个消息体都有一个最大长度的限制同时所有队列所包含的全部消息体的总长度也是有上限。在 Linux 内核中会有两个宏定义 MSGMAX 和 MSGMNB它们以字节为单位分别定义了一条消息的最大长度和一个队列的最大长度。消息队列通信过程中存在用户态与内核态之间的数据拷贝开销因为进程写入数据到内核中的消息队列时会发生从用户态拷贝数据到内核态的过程同理另一进程读取内核中的消息数据时会发生从内核态拷贝数据到用户态的过程。• 共享内存共享内存的机制就是拿出⼀块虚拟地址空间来映射到相同的物理内存中。这样这个进程写⼊的东西另外的进程⻢上就能看到。共享内存是最快的 IPC 方式它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制如信号量配合使用来实现进程间的同步和通信。共享内存• 信号量信号量我们可以理解成红绿灯红灯行绿灯停。它本质上是一个整数计数器可以用来控制多个进程对共享资源的访问。它常作为一种锁机制防止某进程正在访问共享资源时其他进程也访问该资源。因此主要作为进程间以及同一进程内不同线程之间的同步手段。信号量其实是一个整型的计数器主要用于实现进程间的互斥与同步而不是用于缓存进程间通信的数据。信号量表示资源的数量控制信号量的⽅式有两种原⼦操作◦ ⼀个是 P 操作这个操作会把信号量减去 1相减后如果信号量 0则表明资源已被占⽤进程需阻塞等待相减后如果信号量 0则表明还有资源可使⽤进程可正常继续执⾏。◦ 另⼀个是 V 操作这个操作会把信号量加上 1相加后如果信号量 0则表明当前有阻塞中的进程于是会将该进程唤醒运⾏相加后如果信号量 0则表明当前没有阻塞中的进程P 操作是⽤在进⼊共享资源之前V 操作是⽤在离开共享资源之后这两个操作是必须成对出现的。可以发现信号初始化为 1就代表着是互斥信号量它可以保证共享内存在任何时刻只有一个进程在访问这就很好的保护了共享内存。可以发现信号初始化为 0就代表着是同步信号量它可以保证进程 A 应在进程 B 之前执行。看小林coding互斥和同步的例子要能讲出来信号量• Socket与其他通信机制不同的是它可用于不同机器间的进程通信。优缺点• 管道简单效率低容量有限• 消息队列不及时写入和读取需要用户态、内核态拷贝。• 共享内存区能够很容易控制容量速度快但需要注意不同进程的同步问题。• 信号量不能传递复杂消息一般用来实现进程间的同步• 信号它是进程间通信的唯一异步机制。• Socket用于不同主机进程间的通信。8.进程和线程的联系和区别线程和进程的联系线程是进程当中的⼀条执⾏流程。9.什么是线程同⼀个进程内多个线程之间可以共享代码段、数据段、打开的⽂件等资源但每个线程各自都有⼀套独⽴的寄存器和栈这样可以确保线程的控制流是相对独⽴的。需要有一种新的实体满足以下特性• 实体之间可以并发运行• 实体之间共享相同的地址空间这个新的实体就是线程( Thread )线程之间可以并发运行且共享相同的地址空间。多线程-来源参考[3]线程与进程的⽐较如下• 调度进程是资源包括内存、打开的⽂件等分配的单位线程是 CPU 调度的单位• 资源进程拥有⼀个完整的资源平台⽽线程只独享必不可少的资源如寄存器和栈• 拥有资源线程同样具有就绪、阻塞、执⾏三种基本状态同样具有状态之间的转换关系• 系统开销线程能减少并发执⾏的时间和空间开销——创建或撤销进程时系统都要为之分配或回收系统资源如内存空间I/O设备等OS所付出的开销显著大于在创建或撤销线程时的开销进程切换的开销也远大于线程切换的开销。为甚使用线程参考小林coding线程的优点• 一个进程中可以同时存在多个线程• 各个线程之间可以并发执行• 各个线程之间可以共享地址空间和文件等资源线程的缺点• 当进程中的一个线程崩溃时会导致其所属进程的所有线程崩溃这里是针对 C/C 语言Java语言中的线程奔溃不会造成进程崩溃具体分析原因可以看这篇线程崩溃了进程也会崩溃吗 (opens new window)。举个例子对于游戏的用户设计则不应该使用多线程的方式否则一个用户挂了会影响其他同个进程的线程。10.线程上下文切换了解吗这还得看线程是不是属于同⼀个进程• 当两个线程不是属于同⼀个进程则切换的过程就跟进程上下⽂切换⼀样• 当两个线程是属于同⼀个进程因为虚拟内存是共享的所以在切换时虚拟内存这些资源就保持不动只需要切换线程的私有数据、寄存器等不共享的数据所以线程的上下⽂切换相⽐进程开销要⼩很多11.线程间如何同步解决线程间的冲突在进程/线程并发执行的过程中进程/线程之间存在协作的关系例如有互斥、同步的关系。为了实现进程/线程间正确的协作操作系统必须提供实现进程协作的措施和方法主要的方法有两种• 锁加锁、解锁操作• 信号量P、V 操作这两个都可以方便地实现进程/线程互斥而信号量比锁的功能更强一些它还可以方便地实现进程/线程同步。同步解决的是多线程操作共享资源的问题目的是不管线程之间的执行如何穿插最后的结果都是正确的。我们前面知道线程和进程的关系线程是进程当中的⼀条执⾏流程。所以说下面的一些同步机制不止针对线程同样也可以针对进程。临界区我们把对共享资源访问的程序片段称为临界区我们希望这段代码是互斥的保证在某时刻只能被一个线程执行也就是说一个线程在临界区执行时其它线程应该被阻止进入临界区。临界区互斥-来源参考[3]临界区不仅针对线程同样针对进程。临界区同步的一些实现方式1、锁使⽤加锁操作和解锁操作可以解决并发线程/进程的互斥问题。任何想进⼊临界区的线程必须先执⾏加锁操作。若加锁操作顺利通过则线程可进⼊临界区在完成对临界资源的访问后再执⾏解锁操作以释放该临界资源。加锁和解锁锁住的是什么呢可以是临界区对象也可以只是一个简单的互斥量例如互斥量是0无锁1表示加锁。根据锁的实现不同可以分为忙等待锁和和⽆忙等待锁。忙等待锁和就是加锁失败的线程会不断尝试获取锁也被称为自旋锁它会一直占用CPU。⽆忙等待锁就是加锁失败的线程会进入阻塞状态放弃CPU等待被调度。既然不想自旋那当没获取到锁的时候就把当前线程放入到锁的等待队列然后执行调度程序把 CPU 让给其他线程执行。c线程中的几种锁_牛客网 (nowcoder.com)好好看一下2、信号量信号量是操作系统提供的⼀种协调共享资源访问的⽅法。通常信号量表示资源的数量对应的变量是⼀个整型 sem 变量。另外还有两个原⼦操作的系统调⽤函数来控制信号量的分别是• P 操作将 sem 减 1 相减后如果 sem 0 则进程/线程进⼊阻塞等待否则继续表明 P操作可能会阻塞• V 操作将 sem 加 1 相加后如果 sem 0 唤醒⼀个等待中的进程/线程表明 V 操作不会阻塞• ⼀个是 P 操作这个操作会把信号量减去 1相减后如果信号量 0则表明资源已被占⽤进程需阻塞等待相减后如果信号量 0则表明还有资源可使⽤进程可正常继续执⾏。• 另⼀个是 V 操作这个操作会把信号量加上 1相加后如果信号量 0则表明当前有阻塞中的进程于是会将该进程唤醒运⾏相加后如果信号量 0则表明当前没有阻塞中的进程P 操作是⽤在进⼊临界区之前V 操作是⽤在离开临界区之后这两个操作是必须成对出现的。12.什么是死锁在两个或者多个并发线程中如果每个线程持有某种资源而又等待其它线程释放它或它们现在保持着的资源在未改变这种状态之前都不能向前推进称这一组线程产生了死锁。通俗的讲就是两个或多个线程无限期的阻塞、相互等待的一种状态。13.死锁产生有哪些条件死锁产生需要同时满足四个条件• 互斥条件指线程对己经获取到的资源进行它性使用即该资源同时只由一个线程占用。如果此时还有其它线程请求获取获取该资源则请求者只能等待直至占有资源的线程释放该资源。• 请求并持有条件指一个线程己经持有了至少一个资源但又提出了新的资源请求而新资源己被其它线程占有所以当前线程会被阻塞但阻塞 的同时并不释放自己已经获取的资源。• 不可剥夺条件指线程获取到的资源在自己使用完之前不能被其它线程抢占只有在自己使用完毕后才由自己释放该资源。• 环路等待条件指在发生死锁时必然存在一个线程——资源的环形链即线程集合 {T0T1T2,…… Tn} 中 T0 正在等待一 T1 占用的资源Tl1正在等待 T2用的资源…… Tn 在等待己被 T0占用的资源。线程A占有M1请求M2线程B占有M2请求M1 互斥 占有等待 非抢占条件 循环等待解决按顺序加锁RAII锁管理14.如何避免死锁呢产⽣死锁的有四个必要条件互斥条件、持有并等待条件、不可剥夺条件、环路等待条件。避免死锁破坏其中的一个就可以。消除互斥条件这个是没法实现因为很多资源就是只能被一个线程占用例如锁。消除请求并持有条件消除这个条件的办法很简单就是一个线程一次请求其所需要的所有资源。消除不可剥夺条件占用部分资源的线程进一步申请其他资源时如果申请不到可以主动释放它占有的资源这样不可剥夺这个条件就破坏掉了。消除环路等待条件可以靠按序申请资源来预防。所谓按序申请是指资源是有线性顺序的申请的时候可以先申请资源序号小的再申请资源序号大的这样线性化后就不存在环路了。15.活锁和饥饿锁了解吗饥饿锁饥饿锁这个饥饿指的是资源饥饿某个线程一直等不到它所需要的资源从而无法向前推进就像一个人因为饥饿无法成长。活锁在活锁状态下处于活锁线程组里的线程状态可以改变但是整个活锁组的线程无法推进。活锁可以用两个人过一条很窄的小桥来比喻为了让对方先过两个人都往旁边让但两个人总是让到同一边。这样虽然两个人的状态一直在变化但却都无法往前推进。内存管理1.什么是虚拟内存我们实际的物理内存主要是主存但是物理主存空间有限所以一般现代操作系统都会想办法把一部分内存块放到磁盘中用到的时候再装入主存手机上常见的内存融合将一部分存储当作存放内存内容的地方需要的时候再从存储中调回到内存中方便cpu调度但是对用户程序而言是不需要注意实际的物理内存的为什么呢因为有虚拟内存的机制。如果都使用绝对物理地址在这种情况下要想在内存中同时运行两个程序是不可能的。如果第一个程序在 2000 的位置写入一个新的值将会擦掉第二个程序存放在相同位置上的所有内容所以同时运行两个程序是根本行不通的这两个程序会立刻崩溃。简单说虚拟内存是操作系统提供的⼀种机制将不同进程的虚拟地址和不同内存的物理地址映射起来。每个进程都有自己独立的地址空间再由操作系统映射到到实际的物理内存。于是这⾥就引出了两种地址的概念程序所使⽤的内存地址叫做虚拟内存地址Virtual Memory Address实际存在硬件⾥⾯的空间地址叫物理内存地址Physical Memory Address2.什么是内存分段程序是由若⼲个逻辑分段组成的如可由代码分段、数据分段、栈段、堆段组成。不同的段是有不同的属性的所以就⽤分段Segmentation的形式把这些段分离出来。分段机制下的虚拟地址由两部分组成段号和段内偏移量。虚拟地址和物理地址通过段表映射段表主要包括段号、段的界限。虚拟地址、段表、物理地址我们来看一个映射虚拟地址段3、段偏移量500 ---- 段基地址7000段偏移量500 ---- 物理地址7500。内存分段产生的问题具体要看下小林coding• 第一个就是内存碎片的问题。• 第二个就是内存交换的效率低的问题。3.什么是内存分页分⻚是把整个虚拟和物理内存空间切成⼀段段固定尺⼨的⼤⼩。这样⼀个连续并且尺⼨固定的内存空间我们叫⻚Page。在 Linux 下每⼀⻚的⼤⼩为 4KB 。访问分页系统中内存数据需要两次的内存访问 一次是从内存中访问页表从中找到指定的物理页号加上页内偏移得到实际物理地址第二次就是根据第一次得到的物理地址访问内存取出数据。总结一下对于一个内存地址转换其实就是这样三个步骤• 把虚拟内存地址切分成页号和偏移量• 根据页号从页表里面查询对应的物理页号• 直接拿物理页号加上前面的偏移量就得到了物理内存地址。内存分页4.多级页表知道吗操作系统可能会有非常多进程如果只是使用简单分页可能导致的后果就是页表变得非常庞大。所以引入了多级页表的解决方案。所谓的多级页表就是把我们原来的单级页表再次分页这里利用了局部性原理除了顶级页表其它级别的页表一来可以在需要的时候才被创建二来内存紧张的时候还可以被置换到磁盘中。多级页表示意图5.什么是快表TLB同样利用了局部性原理即在⼀段时间内整个程序的执⾏仅限于程序中的某⼀部分。相应地执⾏所访问的存储空间也局限于某个内存区域。利⽤这⼀特性把最常访问的⼏个⻚表项存储到访问速度更快的硬件于是计算机科学家们就在 CPU 芯⽚中加⼊了⼀个专⻔存放程序最常访问的⻚表项的 Cache这个 Cache 就是 TLBTranslation Lookaside Buffer 通常称为⻚表缓存、转址旁路缓存、快表等。TLB示意图-来源参考[3]6.分页和分段有什么区别• 段是信息的逻辑单位它是根据用户的需要划分的因此段对用户是可见的 页是信息的物理单位是为了管理主存的方便而划分的对用户是透明的。• 段的大小不固定由它所完成的功能决定页的大小固定由系统决定。• 段向用户提供二维地址空间页向用户提供的是一维地址空间。这里其实不太理解• 段是信息的逻辑单位便于存储保护和信息的共享页的保护和共享受到限制。7.什么是交换空间操作系统把物理内存(Physical RAM)分成一块一块的小内存每一块内存被称为页(page)。当内存资源不足时Linux把某些页的内容转移至磁盘上的一块空间上以释放内存空间。磁盘上的那块空间叫做交换空间(swap space),而这一过程被称为交换(swapping)。物理内存和交换空间的总容量就是虚拟内存的可用容量。用途• 物理内存不足时一些不常用的页可以被交换出去腾给系统。• 程序启动时很多内存页被用来初始化之后便不再需要可以交换出去。8.页面置换算法有哪些在分页系统里一个虚拟的页面可能在主存里也可能在磁盘中如果CPU发现虚拟地址对应的物理页不在主存里就会产生一个缺页中断然后从磁盘中把该页调入主存中。如果内存里没有空间就需要从主存里选择一个页面来置换。常见的页面置换算法常见页面置换算法• 最佳⻚⾯置换算法OPT最佳⻚⾯置换算法是一个理想的算法基本思路是置换在未来最⻓时间不访问的⻚⾯。所以该算法实现需要计算内存中每个逻辑⻚⾯的下⼀次访问时间然后⽐较选择未来最⻓时间不访问的⻚⾯。但这个算法是无法实现的因为当缺页中断发生时操作系统无法知道各个页面下一次将在什么时候被访问。• 先进先出置换算法FIFO既然我们⽆法预知⻚⾯在下⼀次访问前所需的等待时间那可以选择在内存驻留时间很⻓的⻚⾯进⾏中置换这个就是「先进先出置换」算法的思想。FIFO的实现机制是使用链表将所有在内存的页面按照进入时间的早晚链接起来然后每次置换链表头上的页面就行了新加进来的页面则挂在链表的末端。按照进入内存早晚构建的页面链表• 最近最久未使⽤的置换算法LRU最近最久未使⽤LRU的置换算法的基本思路是发⽣缺⻚时选择最⻓时间没有被访问的⻚⾯进⾏置换也就是说该算法假设已经很久没有使⽤的⻚⾯很有可能在未来较⻓的⼀段时间内仍然不会被使⽤。这种算法近似最优置换算法最优置换算法是通过「未来」的使⽤情况来推测要淘汰的⻚⾯⽽ LRU 则是通过历史的使⽤情况来推测要淘汰的⻚⾯。LRU 在理论上是可以实现的但代价很⾼。为了完全实现 LRU需要在内存中维护⼀个所有⻚⾯的链表最近最多使⽤的⻚⾯在表头最近最少使⽤的⻚⾯在表尾。LRU实现困难的是在每次访问内存时都必须要更新整个链表。在链表中找到⼀个⻚⾯删除它然后把它移动到表头是⼀个⾮常费时的操作。所以LRU 虽然看上去不错但是由于开销⽐较⼤实际应⽤中⽐较少使⽤。• 时钟页面置换算法这个算法的思路是把所有的⻚⾯都保存在⼀个类似钟⾯的环形链表中⼀个表针指向最⽼的⻚⾯。时钟页面置换算法当发⽣缺⻚中断时算法⾸先检查表针指向的⻚⾯如果它的访问位位是 0 就淘汰该⻚⾯并把新的⻚⾯插⼊这个位置然后把表针前移⼀个位置如果访问位是 1 就清除访问位并把表针前移⼀个位置重复这个过程直到找到了⼀个访问位为 0 的⻚⾯为⽌• 最不常⽤置换算法最不常用算法LFU当发⽣缺⻚中断时选择访问次数最少的那个⻚⾯将其置换。它的实现⽅式是对每个⻚⾯设置⼀个「访问计数器」每当⼀个⻚⾯被访问时该⻚⾯的访问计数器就累加 1。在发⽣缺⻚中断时淘汰计数器值最⼩的那个⻚⾯。pdf完整版下载https://upload.csdn.net/creation/uploadResources?spm1001.2014.3001.5355