乐趣区

关于操作系统:21万字30张图详解操作系统常见面试题收藏版

jiezi

本文曾经收录进 JavaGuide（「Java 学习 + 面试指南」一份涵盖大部分 Java 程序员所须要把握的外围常识。）

耗时两周，新版的操作系统常见知识点 / 问题总结总算搞完了，手绘了 30 多张图。大家能够用来温习操作系统或者筹备操作系统面试。对于大部分公司的面试来说根本够用了，不过，像腾讯、字节这种大厂的面试还是要适当深刻一些。

这篇文章总结了一些我感觉比拟重要的操作系统相干的问题比方 用户态和内核态、零碎调用、过程和线程、死锁、内存治理、虚拟内存、文件系统 等等。另外，这篇文章只是对一些操作系统比拟重要概念的一个概览，深刻学习的话，倡议大家还是老老实实地去看书。

操作系统根底

什么是操作系统？

通过以下四点能够概括操作系统到底是什么：

  1. 操作系统（Operating System，简称 OS）是治理计算机硬件与软件资源的程序，是计算机的基石。
  2. 操作系统实质上是一个运行在计算机上的软件程序，次要用于治理计算机硬件和软件资源。举例：运行在你电脑上的所有应用程序都通过操作系统来调用零碎内存以及磁盘等等硬件。
  3. 操作系统存在屏蔽了硬件层的复杂性。操作系统就像是硬件应用的负责人，兼顾着各种相干事项。
  4. 操作系统的内核（Kernel）是操作系统的外围局部，它负责零碎的内存治理，硬件设施的治理，文件系统的治理以及应用程序的治理。内核是连贯应用程序和硬件的桥梁，决定着零碎的性能和稳定性。

很多人容易把操作系统的内核（Kernel）和中央处理器（CPU，Central Processing Unit）弄混。你能够简略从上面两点来区别：

  1. 操作系统的内核（Kernel）属于操作系统层面，而 CPU 属于硬件。
  2. CPU 次要提供运算，解决各种指令的能力。内核（Kernel）次要负责系统管理比方内存治理，它屏蔽了对硬件的操作。

下图清晰阐明了应用程序、内核、CPU 这三者的关系。

操作系统次要有哪些性能？

从资源管理的角度来看，操作系统有 6 大性能：

  1. 过程和线程的治理：过程的创立、撤销、阻塞、唤醒，过程间的通信等。
  2. 存储管理：内存的调配和治理、外存（磁盘等）的调配和治理等。
  3. 文件治理：文件的读、写、创立及删除等。
  4. 设施治理：实现设施（输入输出设施和内部存储设备等）的申请或开释，以及设施启动等性能。
  5. 网络管理：操作系统负责管理计算机网络的应用。网络是计算机系统中连贯不同计算机的形式，操作系统须要治理计算机网络的配置、连贯、通信和平安等，以提供高效牢靠的网络服务。
  6. 平安治理：用户的身份认证、访问控制、文件加密等，以避免非法用户对系统资源的拜访和操作。

常见的操作系统有哪些？

Windows

目前最风行的集体桌面操作系统，不做多的介绍，大家都分明。界面简略易操作，软件生态十分好。

玩玩电脑游戏还是必须要有 Windows 的，所以我当初是一台 Windows 用于玩游戏，一台 Mac 用于平时日常开发和学习应用。

Unix

最早的多用户、多任务操作系统。前面崛起的 Linux 在很多方面都参考了 Unix。

目前这款操作系统曾经逐步逐步退出操作系统的舞台。

Linux

Linux 是一套收费应用、开源的类 Unix 操作系统。 Linux 存在着许多不同的发行版本，但它们都应用了 Linux 内核。

严格来讲，Linux 这个词自身只示意 Linux 内核，在 GNU/Linux 零碎中，Linux 理论就是 Linux 内核，而该零碎的其余部分次要是由 GNU 工程编写和提供的程序组成。独自的 Linux 内核并不能成为一个能够失常工作的操作系统。

很多人更偏向应用“GNU/Linux”一词来表白人们通常所说的“Linux”。

Mac OS

苹果自家的操作系统，编程体验和 Linux 相当，然而界面、软件生态以及用户体验各方面都要比 Linux 操作系统更好。

用户态和内核态

什么是用户态和内核态？

依据过程拜访资源的特点，咱们能够把过程在零碎上的运行分为两个级别：

  • 用户态(User Mode) : 用户态运行的过程能够间接读取用户程序的数据，领有较低的权限。当应用程序须要执行某些须要非凡权限的操作，例如读写磁盘、网络通信等，就须要向操作系统发动零碎调用申请，进入内核态。
  • 内核态(Kernel Mode)：内核态运行的过程简直能够拜访计算机的任何资源包含零碎的内存空间、设施、驱动程序等，不受限制，领有十分高的权限。当操作系统接管到过程的零碎调用申请时，就会从用户态切换到内核态，执行相应的零碎调用，并将后果返回给过程，最初再从内核态切换回用户态。

内核态相比用户态领有更高的特权级别，因而可能执行更底层、更敏感的操作。不过，因为进入内核态须要付出较高的开销（须要进行一系列的上下文切换和权限查看），应该尽量减少进入内核态的次数，以进步零碎的性能和稳定性。

为什么要有用户态和内核态？只有一个内核态不行么？

  • 在 CPU 的所有指令中，有一些指令是比拟危险的比方内存调配、设置时钟、IO 解决等，如果所有的程序都能应用这些指令的话，会对系统的失常运行造成灾难性地影响。因而，咱们须要限度这些危险指令只能内核态运行。这些只能由操作系统内核态执行的指令也被叫做 特权指令。
  • 如果计算机系统中只有一个内核态，那么所有程序或过程都必须共享系统资源，例如内存、CPU、硬盘等，这将导致系统资源的竞争和抵触，从而影响零碎性能和效率。并且，这样也会让零碎的安全性升高，毕竟所有程序或过程都具备雷同的特权级别和拜访权限。

因而，同时具备用户态和内核态次要是为了保障计算机系统的安全性、稳定性和性能。

用户态和内核态是如何切换的？

用户态切换到内核态的 3 种形式：

  1. 零碎调用（Trap）：用户态过程 被动 要求切换到内核态的一种形式，次要是为了应用内核态能力做的事件比方读取磁盘资源。零碎调用的机制其外围还是应用了操作系统为用户特地凋谢的一个中断来实现。
  2. 中断（Interrupt）：当外围设备实现用户申请的操作后，会向 CPU 收回相应的中断信号，这时 CPU 会暂停执行下一条行将要执行的指令转而去执行与中断信号对应的处理程序，如果先前执行的指令是用户态下的程序，那么这个转换的过程天然也就产生了由用户态到内核态的切换。比方硬盘读写操作实现，零碎会切换到硬盘读写的中断处理程序中执行后续操作等。
  3. 异样（Exception）：当 CPU 在执行运行在用户态下的程序时，产生了某些当时不可知的异样，这时会触发由以后运行过程切换到解决此异样的内核相干程序中，也就转到了内核态，比方缺页异样。

在零碎的解决上，中断和异样相似，都是通过中断向量表来找到相应的处理程序进行解决。区别在于，中断来自处理器内部，不是由任何一条专门的指令造成，而异样是执行以后指令的后果。

零碎调用

什么是零碎调用？

咱们运行的程序根本都是运行在用户态，如果咱们调用操作系统提供的内核态级别的子性能咋办呢？那就须要零碎调用了！

也就是说在咱们运行的用户程序中，但凡与零碎态级别的资源无关的操作（如文件治理、过程管制、内存治理等)，都必须通过零碎调用形式向操作系统提出服务申请，并由操作系统代为实现。

这些零碎调用按性能大抵可分为如下几类：

  • 设施治理：实现设施（输入输出设施和内部存储设备等）的申请或开释，以及设施启动等性能。
  • 文件治理：实现文件的读、写、创立及删除等性能。
  • 过程治理：过程的创立、撤销、阻塞、唤醒，过程间的通信等性能。
  • 内存治理：实现内存的调配、回收以及获取作业占用内存区大小及地址等性能。

零碎调用和一般库函数调用十分类似，只是零碎调用由操作系统内核提供，运行于内核态，而一般的库函数调用由函数库或用户本人提供，运行于用户态。

总结：零碎调用是应用程序与操作系统之间进行交互的一种形式，通过零碎调用，应用程序能够拜访操作系统底层资源例如文件、设施、网络等。

零碎调用的过程理解吗？

零碎调用的过程能够简略分为以下几个步骤：

  1. 用户态的程序发动零碎调用，因为零碎调用中波及一些特权指令（只能由操作系统内核态执行的指令），用户态程序权限有余，因而会中断执行，也就是 Trap（Trap 是一种中断）。
  2. 产生中断后，以后 CPU 执行的程序会中断，跳转到中断处理程序。内核程序开始执行，也就是开始解决零碎调用。
  3. 内核解决实现后，被动触发 Trap，这样会再次发生中断，切换回用户态工作。

过程和线程

什么是过程和线程？

  • 过程（Process） 是指计算机中正在运行的一个程序实例。举例：你关上的微信就是一个过程。
  • 线程（Thread） 也被称为轻量级过程，更加轻量。多个线程能够在同一个过程中同时执行，并且共享过程的资源比方内存空间、文件句柄、网络连接等。举例：你关上的微信里就有一个线程专门用来拉取他人发你的最新的音讯。

过程和线程的区别是什么？

下图是 Java 内存区域，咱们从 JVM 的角度来说一下线程和过程之间的关系吧！

从上图能够看出：一个过程中能够有多个线程，多个线程共享过程的 堆和 办法区 (JDK1.8 之后的元空间)资源，然而每个线程有本人的 程序计数器 、 虚拟机栈 和 本地办法栈。

总结：

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

有了过程为什么还须要线程?

  • 过程切换是一个开销很大的操作，线程切换的老本较低。
  • 线程更轻量，一个过程能够创立多个线程。
  • 多个线程能够并发解决不同的工作，更无效地利用了多处理器和多核计算机。而过程只能在一个工夫干一件事，如果在执行过程中遇到阻塞问题比方 IO 阻塞就会挂起直到后果返回。
  • 同一过程内的线程共享内存和文件，因而它们之间互相通信毋庸调用内核。

为什么要应用多线程?

先从总体上来说：

  • 从计算机底层来说： 线程能够比作是轻量级的过程，是程序执行的最小单位, 线程间的切换和调度的老本远远小于过程。另外，多核 CPU 时代意味着多个线程能够同时运行，这缩小了线程上下文切换的开销。
  • 从当代互联网发展趋势来说： 当初的零碎动不动就要求百万级甚至千万级的并发量，而多线程并发编程正是开发高并发零碎的根底，利用好多线程机制能够大大提高零碎整体的并发能力以及性能。

再深刻到计算机底层来探讨：

  • 单核时代：在单核时代多线程次要是为了进步单过程利用 CPU 和 IO 零碎的效率。假如只运行了一个 Java 过程的状况，当咱们申请 IO 的时候，如果 Java 过程中只有一个线程，此线程被 IO 阻塞则整个过程被阻塞。CPU 和 IO 设施只有一个在运行，那么能够简略地说零碎整体效率只有 50%。当应用多线程的时候，一个线程被 IO 阻塞，其余线程还能够持续应用 CPU。从而进步了 Java 过程利用系统资源的整体效率。
  • 多核时代: 多核时代多线程次要是为了进步过程利用多核 CPU 的能力。举个例子：如果咱们要计算一个简单的工作，咱们只用一个线程的话，不管零碎有几个 CPU 外围，都只会有一个 CPU 外围被利用到。而创立多个线程，这些线程能够被映射到底层多个 CPU 上执行，在工作中的多个线程没有资源竞争的状况下，工作执行的效率会有显著性的进步，约等于（单核时执行工夫 /CPU 外围数）。

线程间的同步的形式有哪些？

线程同步是两个或多个共享要害资源的线程的并发执行。应该同步线程以防止要害的资源应用抵触。

上面是几种常见的线程同步的形式：

  1. 互斥锁(Mutex)：采纳互斥对象机制，只有领有互斥对象的线程才有拜访公共资源的权限。因为互斥对象只有一个，所以能够保障公共资源不会被多个线程同时拜访。比方 Java 中的 synchronized 关键词和各种 Lock 都是这种机制。
  2. 读写锁（Read-Write Lock）：容许多个线程同时读取共享资源，但只有一个线程能够对共享资源进行写操作。
  3. 信号量(Semaphore)：它容许同一时刻多个线程拜访同一资源，然而须要管制同一时刻拜访此资源的最大线程数量。
  4. 屏障（Barrier）：屏障是一种同步原语，用于期待多个线程达到某个点再一起继续执行。当一个线程达到屏障时，它会进行执行并期待其余线程达到屏障，直到所有线程都达到屏障后，它们才会一起继续执行。比方 Java 中的 CyclicBarrier 是这种机制。
  5. 事件(Event) :Wait/Notify：通过告诉操作的形式来放弃多线程同步，还能够不便的实现多线程优先级的比拟操作。

PCB 是什么？蕴含哪些信息？

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

当操作系统创立一个新过程时，会为该过程调配一个惟一的过程 ID，并且为该过程创立一个对应的过程管制块。当过程执行时，PCB 中的信息会一直变动，操作系统会依据这些信息来治理和调度过程。

PCB 次要蕴含上面几局部的内容：

  • 过程的形容信息，包含过程的名称、标识符等等；
  • 过程的调度信息，包含过程阻塞起因、过程状态（就绪、运行、阻塞等）、过程优先级（标识过程的重要水平）等等；
  • 过程对资源的需要状况，包含 CPU 工夫、内存空间、I/O 设施等等。
  • 过程关上的文件信息，包含文件描述符、文件类型、关上模式等等。
  • 处理机的状态信息（由处理机的各种寄存器中的内容组成的），包含通用寄存器、指令计数器、程序状态字 PSW、用户栈指针。
  • ……

过程有哪几种状态?

咱们个别把过程大抵分为 5 种状态，这一点和线程很像！

  • 创立状态(new)：过程正在被创立，尚未到就绪状态。
  • 就绪状态 (ready)：过程已处于筹备运行状态，即过程取得了除了处理器之外的所有所需资源，一旦失去处理器资源(处理器调配的工夫片) 即可运行。
  • 运行状态(running)：过程正在处理器上运行(单核 CPU 下任意时刻只有一个过程处于运行状态)。
  • 阻塞状态(waiting)：又称为期待状态，过程正在期待某一事件而暂停运行如期待某资源为可用或期待 IO 操作实现。即便处理器闲暇，该过程也不能运行。
  • 完结状态(terminated)：过程正在从零碎中隐没。可能是过程失常完结或其余起因中断退出运行。

过程间的通信形式有哪些？

上面这部分总结参考了:《过程间通信 IPC (InterProcess Communication)》这篇文章，举荐浏览，总结的十分不错。

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

过程的调度算法有哪些?

这是一个很重要的知识点！为了确定首先执行哪个过程以及最初执行哪个过程以实现最大 CPU 利用率，计算机科学家曾经定义了一些算法，它们是：

  • 先到先服务调度算法(FCFS，First Come, First Served) : 从就绪队列中抉择一个最先进入该队列的过程为之分配资源，使它立刻执行并始终执行到实现或产生某事件而被阻塞放弃占用 CPU 时再从新调度。
  • 短作业优先的调度算法(SJF，Shortest Job First) : 从就绪队列中选出一个预计运行工夫最短的过程为之分配资源，使它立刻执行并始终执行到实现或产生某事件而被阻塞放弃占用 CPU 时再从新调度。
  • 工夫片轮转调度算法（RR，Round-Robin） : 工夫片轮转调度是一种最古老，最简略，最偏心且应用最广的算法。每个过程被调配一个时间段，称作它的工夫片，即该过程容许运行的工夫。
  • 多级反馈队列调度算法（MFQ，Multi-level Feedback Queue）：后面介绍的几种过程调度的算法都有肯定的局限性。如 短过程优先的调度算法，仅关照了短过程而疏忽了长过程 。多级反馈队列调度算法既能使高优先级的作业失去响应又能使短作业（过程）迅速实现。，因此它是目前 被公认的一种较好的过程调度算法，UNIX 操作系统采取的便是这种调度算法。
  • 优先级调度算法（Priority）：为每个流程调配优先级，首先执行具备最高优先级的过程，依此类推。具备雷同优先级的过程以 FCFS 形式执行。能够依据内存要求，工夫要求或任何其余资源要求来确定优先级。

什么是僵尸过程和孤儿过程？

在 Unix/Linux 零碎中，子过程通常是通过 fork()零碎调用创立的，该调用会创立一个新的过程，该过程是原有过程的一个正本。子过程和父过程的运行是互相独立的，它们各自领有本人的 PCB，即便父过程完结了，子过程依然能够持续运行。

当一个过程调用 exit()零碎调用完结本人的生命时，内核会开释该过程的所有资源，包含关上的文件、占用的内存等，然而该过程对应的 PCB 仍然存在于零碎中。这些信息只有在父过程调用 wait()或 waitpid()零碎调用时才会被开释，以便让父过程失去子过程的状态信息。

这样的设计能够让父过程在子过程完结时失去子过程的状态信息，并且能够防止出现“僵尸过程”（即子过程完结后 PCB 依然存在但父过程无奈失去状态信息的状况）。

  • 僵尸过程 ：子过程曾经终止，然而其父过程仍在运行，且父过程没有调用 wait() 或 waitpid()等零碎调用来获取子过程的状态信息，开释子过程占用的资源，导致子过程的 PCB 仍然存在于零碎中，但无奈被进一步应用。这种状况下，子过程被称为“僵尸过程”。防止僵尸过程的产生，父过程须要及时调用 wait()或 waitpid()零碎调用来回收子过程。
  • 孤儿过程 ：一个过程的父过程曾经终止或者不存在，然而该过程仍在运行。这种状况下，该过程就是孤儿过程。孤儿过程通常是因为父过程意外终止或未及时调用 wait() 或 waitpid()等零碎调用来回收子过程导致的。为了防止孤儿过程占用系统资源，操作系统会将孤儿过程的父过程设置为 init 过程（过程号为 1），由 init 过程来回收孤儿过程的资源。

如何查看是否有僵尸过程？

Linux 下能够应用 Top 命令查找，zombie 值示意僵尸过程的数量，为 0 则代表没有僵尸过程。

上面这个命令能够定位僵尸过程以及该僵尸过程的父过程：

ps -A -ostat,ppid,pid,cmd |grep -e '^[Zz]'

死锁

什么是死锁？

死锁（Deadlock）形容的是这样一种状况：多个过程 / 线程同时被阻塞，它们中的一个或者全副都在期待某个资源被开释。因为过程 / 线程被无限期地阻塞，因而程序不可能失常终止。

能列举一个操作系统产生死锁的例子吗？

假如有两个过程 A 和 B，以及两个资源 X 和 Y，它们的分配情况如下：

过程 占用资源 需要资源
A X Y
B Y X

此时，过程 A 占用资源 X 并且申请资源 Y，而过程 B 曾经占用了资源 Y 并申请资源 X。两个过程都在期待对方开释资源，无奈继续执行，陷入了死锁状态。

产生死锁的四个必要条件是什么?

  1. 互斥：资源必须处于非共享模式，即一次只有一个过程能够应用。如果另一过程申请该资源，那么必须期待直到该资源被开释为止。
  2. 占有并期待：一个过程至多应该占有一个资源，并期待另一资源，而该资源被其余过程所占有。
  3. 非抢占：资源不能被抢占。只能在持有资源的过程实现工作后，该资源才会被开释。
  4. 循环期待：有一组期待过程 {P0, P1,..., Pn}，P0 期待的资源被 P1 占有，P1 期待的资源被 P2 占有，……，Pn-1 期待的资源被 Pn 占有，Pn 期待的资源被 P0 占有。

留神 ⚠️：这四个条件是产生死锁的 必要条件，也就是说只有零碎产生死锁，这些条件必然成立，而只有上述条件之一不满足，就不会产生死锁。

上面是百度百科对必要条件的解释：

如果没有事物状况 A，则必然没有事物状况 B，也就是说如果有事物状况 B 则肯定有事物状况 A，那么 A 就是 B 的必要条件。从逻辑学上看，B 能推导出 A，A 就是 B 的必要条件，等价于 B 是 A 的充分条件。

能写一个模仿产生死锁的代码吗？

上面通过一个理论的例子来模仿下图展现的线程死锁：

public class DeadLockDemo {private static Object resource1 = new Object();// 资源 1
    private static Object resource2 = new Object();// 资源 2

    public static void main(String[] args) {new Thread(() -> {synchronized (resource1) {System.out.println(Thread.currentThread() + "get resource1");
                try {Thread.sleep(1000);
                } catch (InterruptedException e) {e.printStackTrace();
                }
                System.out.println(Thread.currentThread() + "waiting get resource2");
                synchronized (resource2) {System.out.println(Thread.currentThread() + "get resource2");
                }
            }
        }, "线程 1").start();

        new Thread(() -> {synchronized (resource2) {System.out.println(Thread.currentThread() + "get resource2");
                try {Thread.sleep(1000);
                } catch (InterruptedException e) {e.printStackTrace();
                }
                System.out.println(Thread.currentThread() + "waiting get resource1");
                synchronized (resource1) {System.out.println(Thread.currentThread() + "get resource1");
                }
            }
        }, "线程 2").start();}
}

Output

Thread[线程 1,5,main]get resource1
Thread[线程 2,5,main]get resource2
Thread[线程 1,5,main]waiting get resource2
Thread[线程 2,5,main]waiting get resource1

线程 A 通过 synchronized (resource1) 取得 resource1 的监视器锁，而后通过 Thread.sleep(1000); 让线程 A 休眠 1s 为的是让线程 B 失去执行而后获取到 resource2 的监视器锁。线程 A 和线程 B 休眠完结了都开始希图申请获取对方的资源，而后这两个线程就会陷入相互期待的状态，这也就产生了死锁。

解决死锁的办法

解决死锁的办法能够从多个角度去剖析，个别的状况下，有 预防，防止，检测和解除四种。

  • 预防 是采纳某种策略， 限度并发过程对资源的申请，从而使得死锁的必要条件在零碎执行的任何工夫上都不满足。
  • 防止 则是零碎在分配资源时，依据资源的应用状况 提前做出预测 ，从而 防止死锁的产生
  • 检测 是指零碎设有 专门的机构，当死锁产生时，该机构可能检测死锁的产生，并准确地确定与死锁无关的过程和资源。
  • 解除 是与检测相配套的一种措施，用于 将过程从死锁状态下解脱进去。

死锁的预防

死锁四大必要条件下面都曾经列出来了，很显然，只有毁坏四个必要条件中的任何一个就可能预防死锁的产生。

毁坏第一个条件 互斥条件 ：使得资源是能够同时拜访的，这是种简略的办法，磁盘就能够用这种办法治理，然而咱们要晓得，有很多资源 往往是不能同时拜访的，所以这种做法在大多数的场合是行不通的。

毁坏第三个条件 非抢占 ：也就是说能够采纳 剥夺式调度算法 ，但剥夺式调度办法目前个别仅实用于 主存资源 和 处理器资源 的调配，并不适用于所有的资源，会导致 资源利用率降落。

所以个别比拟实用的 预防死锁的办法，是通过思考毁坏第二个条件和第四个条件。

1、动态调配策略

动态调配策略能够毁坏死锁产生的第二个条件（占有并期待）。所谓动态调配策略，就是指一个过程必须在执行前就申请到它所须要的全副资源，并且晓得它所要的资源都失去满足之后才开始执行。过程要么占有所有的资源而后开始执行，要么不占有资源，不会呈现占有一些资源期待一些资源的状况。

动态调配策略逻辑简略，实现也很容易，但这种策略 重大地升高了资源利用率 ，因为在每个过程所占有的资源中，有些资源是在比拟靠后的执行工夫里采纳的，甚至有些资源是在额定的状况下才应用的，这样就可能造成一个过程占有了一些 简直不必的资源而使其余须要该资源的过程产生期待 的状况。

2、档次调配策略

档次调配策略毁坏了产生死锁的第四个条件(循环期待)。在档次调配策略下，所有的资源被分成了多个档次，一个过程失去某一次的一个资源后，它只能再申请较高一层的资源；当一个过程要开释某层的一个资源时，必须先开释所占用的较高层的资源，按这种策略，是不可能呈现循环期待链的，因为那样的话，就呈现了曾经申请了较高层的资源，反而去申请了较低层的资源，不合乎档次调配策略，证实略。

死锁的防止

下面提到的 毁坏 死锁产生的四个必要条件之一就能够胜利 预防零碎产生死锁 ，然而会导致 低效的过程运行 和 资源使用率 。而死锁的防止相同，它的角度是容许零碎中 同时存在四个必要条件 ，只有把握并发过程中与每个过程无关的资源动静申请状况，做出 理智和正当的抉择，依然能够防止死锁，因为四大条件仅仅是产生死锁的必要条件。

咱们将零碎的状态分为 平安状态 和 不平安状态，每当在未申请者分配资源前先测试零碎状态，若把零碎资源分配给申请者会产生死锁，则回绝调配，否则承受申请，并为它分配资源。

如果操作系统可能保障所有的过程在无限的工夫内失去须要的全副资源，则称零碎处于平安状态，否则说零碎是不平安的。很显然，零碎处于平安状态则不会产生死锁，零碎若处于不平安状态则可能产生死锁。

那么如何保证系统放弃在平安状态呢？通过算法，其中最具备代表性的 防止死锁算法 就是 Dijkstra 的银行家算法，银行家算法用一句话表白就是：当一个过程申请应用资源的时候， 银行家算法 通过先 试探 调配给该过程资源，而后通过 安全性算法 判断调配后零碎是否处于平安状态，若不平安则试探调配作废，让该过程持续期待，若可能进入到平安的状态，则就 真的分配资源给该过程。

银行家算法详情可见：《一句话 + 一张图说分明——银行家算法》。

操作系统教程书中讲述的银行家算法也比拟清晰，能够一看.

死锁的防止 (银行家算法) 改善了 资源使用率低的问题 ，然而它要一直地检测每个过程对各类资源的占用和申请状况，以及做 安全性查看，须要破费较多的工夫。

死锁的检测

对资源的调配加以限度能够 预防和防止 死锁的产生，然而都不利于各过程对系统资源的 充沛共享 。解决死锁问题的另一条路径是 死锁检测和解除 (这里忽然联想到了乐观锁和乐观锁，感觉死锁的检测和解除就像是 乐观锁 ，分配资源时不去提前管会不会产生死锁了，等到真的死锁呈现了再来解决嘛，而 死锁的预防和防止 更像是乐观锁，总是感觉死锁会呈现，所以在分配资源的时候就很审慎)。

这种办法对资源的调配不加以任何限度，也不采取死锁防止措施，但零碎 定时地运行一个“死锁检测” 的程序，判断零碎内是否呈现死锁，如果检测到零碎产生了死锁，再采取措施去解除它。

过程 - 资源分配图

操作系统中的每一刻时刻的 零碎状态 都能够用 过程 - 资源分配图 来示意，过程 - 资源分配图是形容过程和资源申请及分配关系的一种有向图，可用于 检测零碎是否处于死锁状态。

用一个方框示意每一个资源类，方框中的黑点示意该资源类中的各个资源，每个键过程用一个圆圈示意，用 有向边 来示意 过程申请资源和资源被调配的状况。

图中 2-21 是 过程 - 资源分配图 的一个例子，其中共有三个资源类，每个过程的资源占有和申请状况已分明地示意在图中。在这个例子中，因为存在 占有和期待资源的环路 ，导致一组过程永远处于期待资源的状态，产生了 死锁。

过程 - 资源分配图中存在环路并不一定是产生了死锁。因为循环期待资源仅仅是死锁产生的必要条件，而不是充分条件。图 2-22 便是一个有环路而无死锁的例子。尽管过程 P1 和过程 P3 别离占用了一个资源 R1 和一个资源 R2，并且因为期待另一个资源 R2 和另一个资源 R1 造成了环路，但过程 P2 和过程 P4 别离占有了一个资源 R1 和一个资源 R2，它们申请的资源失去了满足，在无限的工夫里会偿还资源，于是过程 P1 或 P3 都能取得另一个所需的资源，环路主动解除，零碎也就不存在死锁状态了。

死锁检测步骤

晓得了死锁检测的原理，咱们能够利用下列步骤编写一个 死锁检测 程序，检测零碎是否产生了死锁。

  1. 如果过程 - 资源分配图中无环路，则此时零碎没有产生死锁
  2. 如果过程 - 资源分配图中有环路，且每个资源类仅有一个资源，则零碎中曾经产生了死锁。
  3. 如果过程 - 资源分配图中有环路，且波及到的资源类有多个资源，此时零碎未必会产生死锁。如果能在过程 - 资源分配图中找出一个 既不阻塞又非独立的过程 ，该过程可能在无限的工夫内偿还占有的资源，也就是把边给打消掉了，反复此过程，直到能在无限的工夫内 打消所有的边 ，则不会产生死锁，否则会产生死锁。(打消边的过程相似于 拓扑排序)

死锁的解除

当死锁检测程序检测到存在死锁产生时，应设法让其解除，让零碎从死锁状态中恢复过来，罕用的解除死锁的办法有以下四种：

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

内存治理

内存治理次要做了什么？

操作系统的内存治理十分重要，次要负责上面这些事件：

  • 内存的调配与回收：对过程所需的内存进行调配和开释，malloc 函数：申请内存，free 函数：开释内存。
  • 地址转换：将程序中的虚拟地址转换成内存中的物理地址。
  • 内存裁减：当零碎没有足够的内存时，利用虚拟内存技术或主动笼罩技术，从逻辑上裁减内存。
  • 内存映射：将一个文件间接映射到过程的过程空间中，这样能够通过内存指针用读写内存的方法直接存取文件内容，速度更快。
  • 内存优化：通过调整内存调配策略和回收算法来优化内存应用效率。
  • 内存平安：保障过程之间应用内存互不烦扰，防止一些恶意程序通过批改内存来毁坏零碎的安全性。
  • ……

什么是内存碎片？

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

  • 外部内存碎片(Internal Memory Fragmentation，简称为内存碎片)：曾经调配给过程应用但未被应用的内存。导致外部内存碎片的次要起因是，当采纳固定比例比方 2 的幂次方进行内存调配时，过程所调配的内存可能会比其理论所须要的大。举个例子，一个过程只须要 65 字节的内存，但为其调配了 128（2^7）大小的内存，那 63 字节的内存就成为了外部内存碎片。
  • 内部内存碎片(External Memory Fragmentation，简称为内部碎片)：因为未调配的间断内存区域太小，以至于不能满足任意过程所须要的内存调配申请，这些小片段且不间断的内存空间被称为内部碎片。也就是说，内部内存碎片指的是那些并为调配给过程但又不能应用的内存。咱们前面介绍的分段机制就会导致内部内存碎片。

内存碎片会导致内存利用率降落，如何缩小内存碎片是内存治理要非常重视的一件事件。

常见的内存治理形式有哪些？

内存治理形式能够简略分为上面两种：

  • 间断内存治理：为一个用户程序调配一个间断的内存空间，内存利用率个别不高。
  • 非间断内存治理：容许一个程序应用的内存散布在离散或者说不相邻的内存中，绝对更加灵便一些。

间断内存治理

块式治理 是晚期计算机操作系统的一种间断内存治理形式，存在重大的内存碎片问题。块式治理会将内存分为几个固定大小的块，每个块中只蕴含一个过程。如果程序运行须要内存的话，操作系统就调配给它一块，如果程序运行只须要很小的空间的话，调配的这块内存很大一部分简直被节约了。这些在每个块中未被利用的空间，咱们称之为外部内存碎片。除了外部内存碎片之外，因为两个内存块之间可能还会有内部内存碎片，这些不间断的内部内存碎片因为太小了无奈再进行调配。

在 Linux 零碎中，间断内存治理采纳了 搭档零碎（Buddy System）算法 来实现，这是一种经典的间断内存调配算法，能够无效解决内部内存碎片的问题。搭档零碎的次要思维是将内存按 2 的幂次划分（每一块内存大小都是 2 的幂次比方 2^6=64 KB），并将相邻的内存块组合成一对搭档（留神： 必须是相邻的才是搭档）。

当进行内存调配时，搭档零碎会尝试找到大小最合适的内存块。如果找到的内存块过大，就将其一分为二，分成两个大小相等的搭档块。如果还是大的话，就持续切分，直到达到适合的大小为止。

假如两块相邻的内存块都被开释，零碎会将这两个内存块合并，进而造成一个更大的内存块，以便后续的内存调配。这样就能够缩小内存碎片的问题，进步内存利用率。

尽管解决了内部内存碎片的问题，但搭档零碎依然存在内存利用率不高的问题（外部内存碎片）。这次要是因为搭档零碎只能调配大小为 2^n 的内存块，因而当须要调配的内存大小不是 2^n 的整数倍时，会节约肯定的内存空间。举个例子：如果要调配 65 大小的内存快，仍然须要调配 2^7=128 大小的内存块。

对于外部内存碎片的问题，Linux 采纳 SLAB 进行解决。因为这部分内容不是本篇文章的重点，这里就不具体介绍了。

非间断内存治理

非间断内存治理存在上面 3 种形式：

  • 段式治理 ：以段(—段间断的物理内存) 的模式治理 / 调配物理内存。应用程序的虚拟地址空间被分为大小不等的段，段是有实际意义的，每个段定义了一组逻辑信息，例如有主程序段 MAIN、子程序段 X、数据段 D 及栈段 S 等。
  • 页式治理：把物理内存分为间断等长的物理页，应用程序的虚拟地址空间划也被分为间断等长的虚构页，古代操作系统宽泛应用的一种内存治理形式。
  • 段页式管理机制：联合了段式治理和页式治理的一种内存管理机制，把物理内存先分成若干段，每个段又持续分成若干大小相等的页。

虚拟内存

什么是虚拟内存? 有什么用？

虚拟内存(Virtual Memory) 是计算机系统内存治理十分重要的一个技术，实质上来说它只是逻辑存在的，是一个假想进去的内存空间，次要作用是作为过程拜访主存（物理内存）的桥梁并简化内存治理。

总结来说，虚拟内存次要提供了上面这些能力：

  • 隔离过程：物理内存通过虚拟地址空间拜访，虚拟地址空间与过程一一对应。每个过程都认为本人领有了整个物理内存，过程之间彼此隔离，一个过程中的代码无奈更改正在由另一过程或操作系统应用的物理内存。
  • 晋升物理内存利用率：有了虚拟地址空间后，操作系统只须要将过程以后正在应用的局部数据或指令加载入物理内存。
  • 简化内存治理：过程都有一个统一且公有的虚拟地址空间，程序员不必和真正的物理内存打交道，而是借助虚拟地址空间拜访物理内存，从而简化了内存治理。
  • 多个过程共享物理内存：过程在运行过程中，会加载许多操作系统的动静库。这些库对于每个过程而言都是专用的，它们在内存中理论只会加载一份，这部分称为共享内存。
  • 进步内存应用安全性：管制过程对物理内存的拜访，隔离不同过程的拜访权限，进步零碎的安全性。
  • 提供更大的可应用内存空间：能够让程序领有超过零碎物理内存大小的可用内存空间。这是因为当物理内存不够用时，能够利用磁盘充当，将物理内存页（通常大小为 4 KB）保留到磁盘文件（会影响读写速度），数据或代码页会依据须要在物理内存与磁盘之间挪动。

没有虚拟内存有什么问题？

如果没有虚拟内存的话，程序间接拜访和操作的都是物理内存，看似少了一层中介，但多了很多问题。

具体有什么问题呢？ 这里举几个例子阐明(参考虚拟内存提供的能力答复这个问题)：

  1. 用户程序能够拜访任意物理内存，可能会不小心操作到零碎运行必须的内存，进而造成操作系统解体，重大影响零碎的平安。
  2. 同时运行多个程序容易解体。比方你想同时运行一个微信和一个 QQ 音乐，微信在运行的时候给内存地址 1xxx 赋值后，QQ 音乐也同样给内存地址 1xxx 赋值，那么 QQ 音乐对内存的赋值就会笼罩微信之前所赋的值，这就可能会造成微信这个程序会解体。
  3. 程序运行过程中应用的所有数据或指令都要载入物理内存，依据局部性原理，其中很大一部分可能都不会用到，白白占用了贵重的物理内存资源。
  4. ……

什么是虚拟地址和物理地址？

物理地址（Physical Address） 是真正的物理内存中地址，更具体点来说是内存地址寄存器中的地址。程序中拜访的内存地址不是物理地址，而是 虚拟地址（Virtual Address）。

也就是说，咱们编程开发的时候理论就是在和虚拟地址打交道。比方在 C 语言中，指针外面存储的数值就能够了解成为内存里的一个地址，这个地址也就是咱们说的虚拟地址。

操作系统个别通过 CPU 芯片中的一个重要组件 MMU(Memory Management Unit，内存治理单元) 将虚拟地址转换为物理地址，这个过程被称为 地址翻译 / 地址转换（Address Translation）。

通过 MMU 将虚拟地址转换为物理地址后，再通过总线传到物理内存设施，进而实现相应的物理内存读写申请。

MMU 将虚拟地址翻译为物理地址的次要机制有两种: 分段机制 和 分页机制。

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

  • 虚拟地址空间是虚拟地址的汇合，是虚拟内存的范畴。每一个过程都有一个统一且公有的虚拟地址空间。
  • 物理地址空间是物理地址的汇合，是物理内存的范畴。

虚拟地址与物理内存地址是如何映射的？

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

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

其中，古代操作系统宽泛采纳分页机制，须要重点关注！

分段机制

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

段表有什么用？地址翻译过程是怎么的？

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

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

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

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

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

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

通过段号肯定要找到对应的段表项吗？失去最终的物理地址后对应的物理内存肯定存在吗？

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

  • 段表项被删除：软件谬误、软件歹意行为等状况可能会导致段表项被删除。
  • 段表项还未创立：如果零碎内存不足或者无奈调配到间断的物理内存块就会导致段表项无奈被创立。

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

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

举个例子：假如可用物理内存为 5G 的零碎应用分段机制分配内存。当初有 4 个过程，每个过程的内存占用状况如下：

  • 过程 1：0~1G（第 1 段）
  • 过程 2：1~3G（第 2 段）
  • 过程 3：3~4.5G（第 3 段）
  • 过程 4：4.5~5G（第 4 段）

此时，咱们敞开了过程 1 和过程 4，则第 1 段和第 4 段的内存会被开释，闲暇物理内存还有 1.5G。因为这 1.5G 物理内存并不是间断的，导致没方法将闲暇的物理内存调配给一个须要 1.5G 物理内存的过程。

分页机制

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

留神：这里的页是间断等长的，不同于分段机制下不同长度的段。

在分页机制下，应用程序虚拟地址空间中的任意虚构页能够被映射到物理内存中的任意物理页上，因而能够实现物理内存资源的离散调配。分页机制依照固定页大小调配物理内存，使得物理内存资源易于治理，可无效防止分段机制中内部内存碎片的问题。

页表有什么用？地址翻译过程是怎么的？

分页治理通过 页表（Page Table） 映射虚拟地址和物理地址。我这里画了一张基于单级页表进行地址翻译的示意图。

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

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

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

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

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

页表中还存有诸如拜访标记（标识该页面有没有被拜访过）、页类型（该段的类型，例如代码段、数据段等）等信息。

通过虚构页号肯定要找到对应的物理页号吗？找到了物理页号失去最终的物理地址后对应的物理页肯定存在吗？

不肯定！可能会存在 页缺失。也就是说，物理内存中没有对应的物理页或者物理内存中有对应的物理页但虚构页还未和物理页建设映射（对应的页表项不存在）。对于页缺失的内容，前面会具体介绍到。

单级页表有什么问题？为什么须要多级页表？

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

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

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

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

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

多级页表属于工夫换空间的典型场景，利用减少页表查问的次数缩小页表占用的空间。

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

为了进步虚拟地址到物理地址的转换速度，操作系统在 页表计划 根底之上引入了 ** 转址旁路缓存(Translation Lookasjde Buffer，TLB，也被称为快表) **。

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

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

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

因为页表也在主存中，因而在没有 TLB 之前，每次读写内存数据时 CPU 要拜访两次主存。有了 TLB 之后，对于存在于 TLB 中的页表数据只须要拜访一次主存即可。

TLB 的设计思维非常简单，但命中率往往十分高，成果很好。这就是因为被频繁拜访的页就是其中的很小一部分。

看完了之后你会发现快表和咱们平时常常在开发零碎中应用的缓存（比方 Redis）很像，确实是这样的，操作系统中的很多思维、很多经典的算法，你都能够在咱们日常开发应用的各种工具或者框架中找到它们的影子。

换页机制有什么用？

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

这也就解释了一个日常应用电脑常见的问题：为什么操作系统中所有过程运行所需的物理内存即便比实在的物理内存要大一些，这些过程也是能够失常运行的，只是运行速度会变慢。

这同样是一种工夫换空间的策略，你用 CPU 的计算工夫，页的调入调出破费的工夫，换来了一个虚构的更大的物理内存空间来反对程序的运行。

什么是页缺失？

依据维基百科:

页缺失（Page Fault，又名硬错误、硬中断、分页谬误、寻页缺失、缺页中断、页故障等）指的是当软件试图拜访已映射在虚拟地址空间中，然而目前并未被加载在物理内存中的一个分页时，由 MMU 所收回的中断。

常见的页缺失有上面这两种：

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

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

常见的页面置换算法有哪些?

当产生硬性页缺失时，如果物理内存中没有闲暇的物理页面可用的话。操作系统就必须将物理内存中的一个物理页淘汰进来，这样就能够腾出空间来加载新的页面了。

用来抉择淘汰哪一个物理页的规定叫做 页面置换算法，咱们能够把页面置换算法看成是淘汰物物理页的规定。

页缺失太频繁的产生会十分影响性能，一个好的页面置换算法应该是能够缩小页缺失呈现的次数。

常见的页面置换算法有上面这 5 种（其余还有很多页面置换算法都是基于这些算法改良得来的）：

  1. 最佳页面置换算法（OPT，Optimal）：优先选择淘汰的页面是当前永不应用的，或者是在最长工夫内不再被拜访的页面，这样能够保障取得最低的缺页率。但因为人们目前无奈预知过程在内存下的若干页面中哪个是将来最长工夫内不再被拜访的，因此该算法无奈实现，只是实践最优的页面置换算法，能够作为掂量其余置换算法优劣的规范。
  2. 先进先出页面置换算法（FIFO，First In First Out） : 最简略的一种页面置换算法，总是淘汰最先进入内存的页面，即抉择在内存中驻留工夫最久的页面进行淘汰。该算法易于实现和了解，个别只须要通过一个 FIFO 队列即可需要。不过，它的性能并不是很好。
  3. 最近最久未应用页面置换算法（LRU，Least Recently Used）：LRU 算法赋予每个页面一个拜访字段，用来记录一个页面自上次被拜访以来所经验的工夫 T，当须淘汰一个页面时，抉择现有页面中其 T 值最大的，即最近最久未应用的页面予以淘汰。LRU 算法是依据各页之前的拜访状况来实现，因而是易于实现的。OPT 算法是依据各页将来的拜访状况来实现，因而是不可实现的。
  4. 起码应用页面置换算法（LFU，Least Frequently Used） : 和 LRU 算法比拟像，不过该置换算法抉择的是之前一段时间内应用起码的页面作为淘汰页。
  5. 时钟页面置换算法（Clock）：能够认为是一种最近未应用算法，即逐出的页面都是最近没有应用的那个。

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

次要起因次要有二：

  1. 常常拜访或者须要长期存在的页面会被频繁调入调出：较早调入的页往往是常常被拜访或者须要长期存在的页，这些页会被重复调入和调出。
  2. 存在 Belady 景象：被置换的页面并不是过程不会拜访的，有时就会呈现调配的页面数增多但缺页率反而进步的异常现象。呈现该异样的起因是因为 FIFO 算法只思考了页面进入内存的程序，而没有思考页面拜访的频率和紧迫性。

哪一种页面置换算法理论用的比拟多？

LRU 算法是理论应用中利用的比拟多，也被认为是最靠近 OPT 的页面置换算法。

不过，须要留神的是，理论利用中这些算法会被做一些改良，就比方 InnoDB Buffer Pool（InnoDB 缓冲池，MySQL 数据库中用于治理缓存页面的机制）就改良了传统的 LRU 算法，应用了一种称为 ”Adaptive LRU” 的算法（同时联合了 LRU 和 LFU 算法的思维）。

分页机制和分段机制有哪些共同点和区别？

共同点：

  • 都是非间断内存治理的形式。
  • 都采纳了地址映射的办法，将虚构地址映射到物理地址，以实现对内存的治理和爱护。

区别：

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

段页机制

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

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

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

局部性原理

要想更好地了解虚拟内存技术，必须要晓得计算机中驰名的 局部性原理（Locality Principle）。另外，局部性原理既实用于程序结构，也实用于数据结构，是十分重要的一个概念。

局部性原理是指在程序执行过程中，数据和指令的拜访存在肯定的空间和工夫上的局部性特点。其中，工夫局部性是指一个数据项或指令在一段时间内被重复应用的特点，空间局部性是指一个数据项或指令在一段时间内与其相邻的数据项或指令被重复应用的特点。

在分页机制中，页表的作用是将虚拟地址转换为物理地址，从而实现内存拜访。在这个过程中，局部性原理的作用体现在两个方面：

  • 工夫局部性：因为程序中存在肯定的循环或者反复操作，因而会重复拜访同一个页或一些特定的页，这就体现了工夫局部性的特点。为了利用工夫局部性，分页机制中通常采纳缓存机制来进步页面的命中率，行将最近拜访过的一些页放入缓存中，如果下一次拜访的页曾经在缓存中，就不须要再次拜访内存，而是间接从缓存中读取。
  • 空间局部性：因为程序中数据和指令的拜访通常是具备肯定的空间连续性的，因而当拜访某个页时，往往会顺带拜访其相邻的一些页。为了利用空间局部性，分页机制中通常采纳预取技术来事后将相邻的一些页读入内存缓存中，以便在将来拜访时可能间接应用，从而进步访问速度。

总之，局部性原理是计算机体系结构设计的重要准则之一，也是许多优化算法的根底。在分页机制中，利用工夫局部性和空间局部性，采纳缓存和预取技术，能够进步页面的命中率，从而进步内存拜访效率

文件系统

文件系统次要做了什么？

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

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

硬链接和软链接有什么区别？

在 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 节点号曾经在该文件系统中被应用。

进步文件系统性能的形式有哪些？

  • 优化硬件：应用高速硬件设施（如 SSD、NVMe）代替传统的机械硬盘，应用 RAID（Redundant Array of Inexpensive Disks）等技术进步磁盘性能。
  • 抉择适合的文件系统选型：不同的文件系统具备不同的个性，对于不同的利用场景抉择适合的文件系统能够进步零碎性能。
  • 使用缓存：拜访磁盘的效率比拟低，能够使用缓存来缩小磁盘的拜访次数。不过，须要留神缓存命中率，缓存命中率过低的话，成果太差。
  • 防止磁盘适度应用：留神磁盘的使用率，防止将磁盘用满，尽量留一些残余空间，免得对文件系统的性能产生负面影响。
  • 对磁盘进行正当的分区：正当的磁盘分区计划，可能使文件系统在不同的区域存储文件，从而缩小文件碎片，进步文件读写性能。

常见的磁盘调度算法有哪些？

磁盘调度算法是操作系统中对磁盘拜访申请进行排序和调度的算法，其目标是进步磁盘的拜访效率。

一次磁盘读写操作的工夫由磁盘寻道 / 寻找工夫、延迟时间和传输工夫决定。磁盘调度算法能够通过扭转达到磁盘申请的解决程序，缩小磁盘寻道工夫和延迟时间。

常见的磁盘调度算法有上面这 6 种（其余还有很多磁盘调度算法都是基于这些算法改良得来的）：

  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 算法进行了改良，如果磁头挪动的方向上曾经没有磁道拜访申请了，就能够立刻让磁头返回，并且磁头只须要返回到有磁道拜访申请的地位即可。

参考

  • 《计算机操作系统—汤小丹》第四版
  • 《深刻了解计算机系统》
  • 《重学操作系统》
  • 《古代操作系统原理与实现》
  • 王道考研操作系统知识点整顿：https://wizardforcel.gitbooks.io/wangdaokaoyan-os/content/13….
  • 操作系统为什么要分用户态和内核态：https://blog.csdn.net/chen134225/article/details/81783980
  • 从根上了解用户态与内核态：https://juejin.cn/post/6923863670132850701
  • 什么是僵尸过程与孤儿过程：https://blog.csdn.net/a745233700/article/details/120715371
  • 内存治理之搭档零碎与 SLAB：https://blog.csdn.net/qq\_44272681/article/details/124199068
  • 为什么 Linux 须要虚拟内存：https://draveness.me/whys-the-design-os-virtual-memory/
  • 程序员的自我涵养（七）：内存缺页谬误：https://liam.page/2017/09/01/page-fault/
  • 虚拟内存的那点事儿：https://juejin.cn/post/6844903507594575886
退出移动版