浅聊操作系统

操作系统简要

操作系统（Operating System，简称 OS）是管理计算机硬件与软件资源的程序，是计算机的基石。
操作系统本质上是一个运行在计算机上的软件程序，它屏蔽了硬件层的复杂性，像是硬件使用的管理员，统筹管理计算机硬件和软件资源。
操作系统的 内核（Kernel） 是操作系统的核心部分，它负责系统的内存管理，硬件设备的管理，文件系统的管理以及应用程序的管理。内核是连接应用程序和硬件的桥梁，决定着系统的性能和稳定性。

操作系统功能

进程和线程的管理 ：进程的创建、撤销、阻塞、唤醒，进程间的通信等。
存储管理 ：内存的分配和管理、外存（磁盘等）的分配和管理等。
文件管理 ：文件的读、写、创建及删除等。
设备管理 ：完成设备（输入输出设备和外部存储设备等）的请求或释放，以及设备启动等功能。
网络管理 ：操作系统负责管理计算机网络的使用。网络是计算机系统中连接不同计算机的方式，操作系统需要管理计算机网络的配置、连接、通信和安全等，以提供高效可靠的网络服务。
安全管理 ：用户的身份认证、访问控制、文件加密等，以防止非法用户对系统资源的访问和操作。

用户态和内核态

用户态(User Mode) : 用户态运行的进程可以直接读取用户程序的数据，拥有较低的权限。当应用程序需要执行某些需要特殊权限的操作，例如读写磁盘、网络通信等，就需要向操作系统发起系统调用请求，进入内核态。
内核态(Kernel Mode) ：内核态运行的进程几乎可以访问计算机的任何资源包括系统的内存空间、设备、驱动程序等，不受限制，拥有非常高的权限。当操作系统接收到进程的系统调用请求时，就会从用户态切换到内核态，执行相应的系统调用，并将结果返回给进程，最后再从内核态切换回用户态。

用户态切换到内核态的方式

系统调用（Trap） ：用户态进程主动要求切换到内核态的一种方式，主要是为了使用内核态才能做的事情比如读取磁盘资源。系统调用的机制其核心还是使用了操作系统为用户特别开放的一个中断来实现。
中断（Interrupt） ：当外围设备完成用户请求的操作后，会向 CPU 发出相应的中断信号，这时 CPU 会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序，如果先前执行的指令是用户态下的程序，那么这个转换的过程自然也就发生了由用户态到内核态的切换。比如硬盘读写操作完成，系统会切换到硬盘读写的中断处理程序中执行后续操作等。
异常（Exception）：当 CPU 在执行运行在用户态下的程序时，发生了某些事先不可知的异常，这时会触发由当前运行进程切换到处理此异常的内核相关程序中，也就转到了内核态，比如缺页异常。

进程和线程

进程（Process） 是指计算机中正在运行的一个程序实例。PCB（Process Control Block） 为进程控制块，是操作系统中用来管理和跟踪进程的数据结构，每个进程都对应着一个独立的 PCB。
线程（Thread） 也被称为轻量级进程，更加轻量。多个线程可以在同一个进程中同时执行，并且共享进程的资源比如内存空间、文件句柄、网络连接等。

一个进程内可能有多个线程，它们的区别在于进程往往是相互独立的，而线程之间可能会相互影响，需要进行通信。并且，线程的执行开销相对要小一些。

线程的优点

多个线程可以并发处理不同的任务，更有效地利用了多处理器和多核计算机。
同一进程内的线程共享内存和文件，因此它们之间相互通信无须调用内核。

线程之间的同步方式

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

进程的状态

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

进程的通信方式

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

进程调度算法

先到先服务调度算法(FCFS，First Come, First Served) : 从就绪队列中选择一个最先进入该队列的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。
短作业优先的调度算法(SJF，Shortest Job First) : 从就绪队列中选出一个估计运行时间最短的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。
时间片轮转调度算法（RR，Round-Robin） : 时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。
多级反馈队列调度算法（MFQ，Multi-level Feedback Queue） ：前面介绍的几种进程调度的算法都有一定的局限性。如短进程优先的调度算法，仅照顾了短进程而忽略了长进程 。多级反馈队列调度算法既能使高优先级的作业得到响应又能使短作业（进程）迅速完成。，因而它是目前被公认的一种较好的进程调度算法，UNIX 操作系统采取的便是这种调度算法。
优先级调度算法（Priority） ：为每个流程分配优先级，首先执行具有最高优先级的进程，依此类推。具有相同优先级的进程以 FCFS 方式执行。可以根据内存要求，时间要求或任何其他资源要求来确定优先级。

僵尸进程和孤儿进程

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

死锁

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

产生死锁的必要条件

互斥：资源必须处于非共享模式，即一次只有一个进程可以使用。如果另一进程申请该资源，那么必须等待直到该资源被释放为止。
占有并等待：一个进程至少应该占有一个资源，并等待另一资源，而该资源被其他进程所占有。
非抢占：资源不能被抢占。只能在持有资源的进程完成任务后，该资源才会被释放。
循环等待：有一组等待进程 {P0, P1,..., Pn}， P0 等待的资源被 P1 占有，P1 等待的资源被 P2 占有，……，Pn-1 等待的资源被 Pn 占有，Pn 等待的资源被 P0 占有。

解决死锁的方法

预防是采用某种策略，限制并发进程对资源的请求，从而使得死锁的必要条件在系统执行的任何时间上都不满足。
避免则是系统在分配资源时，根据资源的使用情况提前做出预测，从而避免死锁的发生。
检测是指系统设有专门的机构，当死锁发生时，该机构能够检测死锁的发生，并精确地确定与死锁有关的进程和资源。
解除是与检测相配套的一种措施，用于将进程从死锁状态下解脱出来。

死锁的预防

死锁的预防主要是通过破坏产生死锁的四个必要条件来实现的：

静态分配策略：指一个进程必须在执行前就申请到它所需要的全部资源，并且知道它所要的资源都得到满足之后才开始执行，它破坏了占有并等待的要求。
层次分配策略：将所有的资源分成多个层次，一个进程得到某一次的一个资源后，它只能再申请较高一层的资源；当一个进程要释放某层的一个资源时，必须先释放所占用的较高层的资源，它破坏了循环等待的要求。

死锁的避免

死锁的避免允许产生死锁的四个必要条件存在，它根据并发进程中与每个进程有关的资源动态申请情况做出进程的调度。

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

如果操作系统能够保证所有的进程在有限的时间内得到需要的全部资源，则称系统处于安全状态，否则说系统是不安全的。很显然，系统处于安全状态则不会发生死锁，系统若处于不安全状态则可能发生死锁。

银行家算法：先试探分配给该进程资源，然后通过 安全性算法 判断分配后系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待，若能够进入到安全的状态，则就 真的分配资源给该进程。

问题：（1）该状态是否安全？（2）若进程 P2 提出请求 Request（1，2，2，2）后，系统能否分配给它？

Process	Allocation	Need	Avaliable
P0	0 0 3 2	0 0 1 2	1 6 2 2
P1	1 0 0 0	1 7 5 0
P2	1 3 5 4	2 3 5 6
P3	0 3 3 2	0 6 5 2
P4	0 0 1 4	0 6 5 6

死锁的检测

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

乐观锁和悲观锁

乐观锁和悲观锁是两种用于解决并发场景下数据竞争问题的思想.

乐观锁：

乐观锁对应于生活中乐观的人，总是认为事情会往好的方向发展。

在操作数据时，乐观锁非常乐观，认为别人不会同时修改数据。

乐观锁不会上锁，只是在执行更新时判断一下在此期间别人是否修改了数据：如果别人修改了数据则放弃操作，否则执行操作。

性能较好，大部分情况下不会阻塞其他事务的读操作。

悲观锁：

悲观锁对应于生活中悲观的人，总是认为事情会往坏的方向发展。

在操作数据时，悲观锁比较悲观，认为别人会同时修改数据。

悲观锁在操作数据时直接将数据锁住，直到操作完成后才会释放锁；上锁期间其他人不能修改数据。

性能较差，可能会阻塞其他事务的读写操作。

死锁的解除

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

进程-资源分配图

在资源分配图中，进程由圆表示，资源由矩形表示。这个图可以帮助我们了解哪些进程在多使用系统资源，并且指出可能存在的瓶颈

化简资源分配图的方法步骤如下：

首先，查看系统还剩下多少资源未分配，然后确定哪些进程是不阻塞的（即系统有足够的空闲资源分配给它们）。
将不阻塞的进程的所有边都去掉，形成一个孤立的点，并将系统分配给这些进程的资源回收回来。
接着，查看剩下的进程中哪些是不阻塞的，然后逐个将它们变成孤立的点。
最后，所有的资源和进程都变成孤立的点。这样的图被称为“可完全简化”。如果一个图可完全简化，那么不会产生死锁；如果一个图不可完全简化（即图中还有“边”存在），则会产生死锁。

我们看到图 a，发现左边的进程资源有三个箭头是往外的，这表示它分配了三个资源，所以它没有空闲的资源。再看到右边的进程资源，有一个箭头往外，则表示它分配了一个资源，所以它有一个空闲资源。
进程看完了后，我们看进程，发现 $P_2$ 进程请求一个左边资源，但是左边的资源都分配了，所以 $P_2$ 被阻塞了。在看到 $P_1$ 它请求了一个右边的资源，恰好有空闲的资源分配，所以 $P_1$ 正常运行。
紧接着，在 $P_1$ 执行完毕后，资源释放。我们看到图 b，现在左边有两个空闲资源，右边有一个空闲资源。我们的 $P_2$ 也获得了它的需要的所有资源，所以 $P_2$ 也正常运行了。

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

内存管理

操作系统的内存管理非常重要，主要负责下面这些事情：

内存的分配与回收 ：对进程所需的内存进行分配和释放，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分配器 来解决。它将内存划分为固定大小的块，每个块就是一个 SLAB，一个 SLAB 由连续的物理页组成。如果本地高速缓存中有可用的对象，直接从本地高速缓存中分配一个SLAB。否则，执行重新填充操作，从伙伴系统的空闲内存中获取一个 SLAB 并填充到本地高速缓存中。虽然如此，但是在某些情况下它无法提供最优性能。

SLOB 分配器：

围绕一个简单的内存块链展开，在分配内存时使用了同样简单的最先适配算法。

主要针对嵌入式系统，特别适用于内存非常有限的系统，例如只有 32MB 以下的内存。

SLOB 的目标是使用较少的内存来实现和管理内存分配。

然而，SLOB 分配器的主要限制在于容易产生外部碎片。

SLUB 分配器：

SLUB 是 SLAB 分配器 的进化版，旨在改进 SLAB 分配器的一些问题。

为了配合大规模并行系统，通过将页帧打包为组，并用struct page中未使用的字段来管理这些组。

SLUB 分配器与 SLAB 分配器的一些不同之处在于：

每个 CPU 结构中保存的是一个 SLAB 缓冲区，而不是空闲对象链表。

对于每个 CPU，SLUB 不再使用共享的空闲对象链表，而是直接使用单个 SLAB，并且每个 CPU 都维护有自己的部分空链表。

结构对比：

SLAB 分配器的每个节点有三个链表：空闲 SLAB 链表、部分空 SLAB 链表和已满 SLAB 链表。

SLUB 分配器将这三个链表精简为一个链表，只保留了部分空 SLAB 链表。

SLUB 分配器的 SLAB 缓冲区结构与 SLAB 分配器的不同，它没有对象描述符数组，而是使用指针来管理空闲对象。

非连续内存管理

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

虚拟内存

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

虚拟内存的好处

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

虚拟内存的缺点

性能下降：当物理内存严重不足时，系统会频繁地进行内存和磁盘的交换（swap），这会降低系统性能。特别是在处理超大文件时，这种性能下降更为明显。
切换开销：在多个应用程序之间切换时，虚拟内存会增加一定的时间开销。因为数据需要从磁盘加载到内存，这会影响应用程序的响应速度。
磁盘空间占用：虚拟内存实际上是将一部分硬盘空间划分为内存使用，同时在硬盘上生成一个 PageFile.Sys文件。尽管这样可以弥补物理内存不足，但也会占用一定的磁盘空间，导致实际可用的磁盘空间变小。
对固态硬盘的影响：虚拟内存的读写操作会对固态硬盘的寿命产生一定影响。如果虚拟内存设置不当，可能会加速固态硬盘的磨损。

虚拟地址和物理地址

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

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

MMU（Memory Management Unit，内存管理单元）是一种硬件模块，用于在CPU和内存之间实现虚拟内存管理。其主要功能包括：

虚实地址翻译：当用户访问内存时，将用户访问的虚拟地址翻译为实际的物理地址，以便CPU对实际的物理地址进行访问。

访问权限控制：MMU可以对一些虚拟地址进行访问权限控制，以便于对用户程序的访问权限和范围进行管理。例如，代码段一般设置为只读，如果有用户程序对代码段进行写操作，系统会触发异常。

引申的物理内存管理：MMU负责对系统的物理内存资源进行管理，为用户程序提供物理内存的申请、释放等操作接口。

分段机制

目的：分段机制旨在将虚拟地址空间划分为不同的段，每个段对应一个连续的内存区域。

工作原理：

分段管理通过 段表（Segment Table） 映射虚拟地址和物理地址。
每个逻辑段都有一对基址寄存器和界限寄存器。
基址寄存器存储段的起始物理地址，界限寄存器定义了段的大小。

优点：

灵活性：不同的段可以放置在不同的物理内存地址处，避免了虚拟地址空间中未使用部分占用内存。
共享：支持共享代码段等，确保多个进程共享某些段而不会出现问题。

缺点：

外部碎片：段的大小不一，可能导致物理内存被分割成奇怪的大小，难以分配连续的内存。
内存分配请求复杂：需要解决外部碎片问题。

分段机制下的虚拟地址组成：

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

段表中每个段的参数：

段基地址：段在线性地址空间中的开始地址。
段限长：段内最大可用偏移地址，定义了段的长度。
段属性：指定段的特性，如可读、可写、可执行等。

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

程序执行时，从进程控制块（PCB）中取出段表始址和段表长度，装入段表寄存器；
MMU 解析得到虚拟地址中的段号和段内偏移量；
通过段号去该应用程序的段表中取出对应的段信息（找到对应的段表项）；
检查段内位移量是否超出该段的长度，若超过，产生越界中断；
从段信息中取出该段的起始地址（物理地址）加上虚拟地址中的段内偏移量得到最终的物理地址。

分页机制

目的：将用户程序的地址空间划分为固定大小的页，并将内存空间分成相应大小的物理块。

工作原理：

分页管理通过 页表（Page Table） 映射虚拟地址和物理地址。

用户程序的地址空间被划分成若干固定大小的区域，称为“页”。（虚拟页）
内存空间也分成若干个物理块，页和块的大小相等。（物理页）
可将用户程序的任一页放在内存的任一块中，实现了离散分配。

优点：

内存利用率高：分页将内存划分为大小相等的页框，可以更有效地利用内存空间。
减少外部碎片：由于页的大小固定，不会产生外部碎片。
用户不可见：分页对用户是透明的，用户无需关心页的分配。

缺点：

设计复杂：实现分页需要复杂的管理机制。
信息共享受限：页的大小由页框决定，一个页中可能包含多个逻辑模块，共享同一块内存不太合理。

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

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

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

程序执行时，从进程控制块（PCB）中取出页表始址和页表长度，装入页表寄存器；
MMU 解析得到虚拟地址中的虚拟页号和页内偏移量；
通过页号去该应用程序的页表中取出对应的物理页号（找到对应的页表项）；
检查页号是否超出页表长度，若超过，产生越界中断。
用该物理页号对应的物理页起始地址（物理地址）加上虚拟地址中的页内偏移量得到最终的物理地址。

多级别页表

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

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

为了解决这个问题，操作系统引入了 多级页表（Multi-Level Page Table） ，多级页表对应多个页表，每个页表也前一个页表相关联。32 位系统一般为二级页表，64 位系统一般为四级页表。多级页表属于时间换空间的典型场景，利用增加页表查询的次数减少页表占用的空间。

我们看一下这个四级页表的例子，它的虚拟地址有 4级索引、3级索引、2级索引、1级索引和偏移量。

每个进程会有一个 4级页表。检索的时候，我们先通过4级页表索引得到一个3级页表的位置，然后再根据3级页表索引找到该表中的条目，也就是一个2级页表，然后再根据2级页表索引获得一个1级页表，最后再根据该1级页表来获得最终的物理地址。

所以根据上图，我们明白4级索引中可能会有很多种 1级页表、2级页表，甚至是 3 级页表。

事实上，多级页表就像一个多叉树的数据结构，所以我们常常称它为页表树。因为虚拟内存地址分布的连续性，树的第一层节点的指针，很多就是空的，也就是不需要有对应的子树了。所谓不需要子树，其实就是不需要对应的 2 级、3 级的页表。找到最终的物理页号，就好像通过一个特定的访问路径，走到树最底层的叶子节点。

最后，我们可以知道的是：如果用单级表进行存储，则需要将虚拟空间对物理空间的映射占满，这样不论是多大的进程都会分配到一样大的映射表；而用多级表进行存储，则可以只使用进程占用空间的映射，这样映射表的空间就每那么大，从而达到省下空间的效果。

段页机制

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

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

段式地址映射。

页式地址映射。

快表

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

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

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

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

页缺失

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

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

页面置换

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

用来选择淘汰哪一个物理页的规则叫做 页面置换算法 ，我们可以把页面置换算法看成是淘汰物物理页的规则。

最佳页面置换算法（OPT，Optimal） ：优先选择淘汰的页面是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若干页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现，只是理论最优的页面置换算法，可以作为衡量其他置换算法优劣的标准。
先进先出页面置换算法（FIFO，First In First Out） : 最简单的一种页面置换算法，总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面进行淘汰。该算法易于实现和理解，一般只需要通过一个 FIFO 队列即可需求。不过，它的性能并不是很好。
最近最久未使用页面置换算法（LRU ，Least Recently Used） ：LRU 算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 T，当须淘汰一个页面时，选择现有页面中其 T 值最大的，即最近最久未使用的页面予以淘汰。LRU 算法是根据各页之前的访问情况来实现，因此是易于实现的。OPT 算法是根据各页未来的访问情况来实现，因此是不可实现的。
最少使用页面置换算法（LFU，Least Frequently Used） : 和 LRU 算法比较像，不过该置换算法选择的是之前一段时间内使用最少的页面作为淘汰页。
时钟页面置换算法（Clock） ：可以认为是一种最近未使用算法，即逐出的页面都是最近没有使用的那个。

文件系统

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

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

软链接和硬链接

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

1、硬链接（Hard Link）

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

2、软链接（Symbolic Link 或 Symlink）

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

磁盘调度算法

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

附录

死锁产生代码实例

（1）互斥条件：资源一次只能被一个线程占用。

import threading

lock = threading.Lock()

def task():
    with lock:
        print(f"{threading.current_thread().name} acquired the lock")
        # 模拟长时间操作
        threading.Event().wait(1)
        print(f"{threading.current_thread().name} released the lock")

threads = [threading.Thread(target=task) for _ in range(2)]
for t in threads:
    t.start()
for t in threads:
    t.join()

（2）请求和保持条件：线程已经持有一个资源，在等待另一个资源时不释放已持有的资源。

import threading

lock1 = threading.Lock()
lock2 = threading.Lock()

def task1():
    with lock1:
        print("Task 1 acquired lock1")
        threading.Event().wait(1)
        with lock2:
            print("Task 1 acquired lock2")

def task2():
    with lock2:
        print("Task 2 acquired lock2")
        threading.Event().wait(1)
        with lock1:
            print("Task 2 acquired lock1")

t1 = threading.Thread(target=task1)
t2 = threading.Thread(target=task2)
t1.start()
t2.start()
t1.join()
t2.join()

（3）不可剥夺条件：资源不能被强制剥夺，只能由线程主动释放。

import threading

lock1 = threading.Lock()
lock2 = threading.Lock()

def task1():
    lock1.acquire()
    print("Task 1 acquired lock1")
    threading.Event().wait(1)
    lock2.acquire()
    print("Task 1 acquired lock2")
    lock2.release()
    lock1.release()

def task2():
    lock2.acquire()
    print("Task 2 acquired lock2")
    threading.Event().wait(1)
    lock1.acquire()
    print("Task 2 acquired lock1")
    lock1.release()
    lock2.release()

t1 = threading.Thread(target=task1)
t2 = threading.Thread(target=task2)
t1.start()
t2.start()
t1.join()
t2.join()

（4）循环等待条件：存在一个线程等待队列，队列中的每个线程都在等待下一个线程所持有的资源。

import threading

lock1 = threading.Lock()
lock2 = threading.Lock()

def task1():
    lock1.acquire()
    print("Task 1 acquired lock1")
    threading.Event().wait(1)
    lock2.acquire()
    print("Task 1 acquired lock2")
    lock2.release()
    lock1.release()

def task2():
    lock2.acquire()
    print("Task 2 acquired lock2")
    threading.Event().wait(1)
    lock1.acquire()
    print("Task 2 acquired lock1")
    lock1.release()
    lock2.release()

t1 = threading.Thread(target=task1)
t2 = threading.Thread(target=task2)
t1.start()
t2.start()
t1.join()
t2.join()

页面置换算法实现

# FIFO（先进先出）算法
def FIFO(pages, capacity):
    memory = []
    page_faults = 0

    for page in pages:
        if page not in memory:
            if len(memory) == capacity:
                memory.pop(0)
            memory.append(page)
            page_faults += 1
        print(f"Memory: {memory}")

    print(f"Total page faults: {page_faults}")

# LRU（最近最少使用）算法   
def LRU(pages, capacity):
    memory = []
    page_faults = 0

    for page in pages:
        if page not in memory:
            if len(memory) == capacity:
                memory.pop(0)
            memory.append(page)
            page_faults += 1
        else:
            memory.remove(page)
            memory.append(page)
        print(f"Memory: {memory}")

    print(f"Total page faults: {page_faults}")
    
# OPT（最佳置换）算法
def OPT(pages, capacity):
    memory = []
    page_faults = 0

    for i in range(len(pages)):
        if pages[i] not in memory:
            if len(memory) < capacity:
                memory.append(pages[i])
            else:
                future_uses = [pages[i:].index(page) if page in pages[i:] else float('inf') for page in memory]
                memory.pop(future_uses.index(max(future_uses)))
                memory.append(pages[i])
            page_faults += 1
        print(f"Memory: {memory}")

    print(f"Total page faults: {page_faults}")
    
# 示例
pages = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
capacity = 3
FIFO(pages, capacity)
LRU(pages, capacity)
OPT(pages, capacity)

磁盘调度算法实现

# FCFS（先来先服务）算法
def FCFS(requests, start):
    seek_sequence = [start] + requests
    total_seek = sum(abs(seek_sequence[i] - seek_sequence[i-1]) for i in range(1, len(seek_sequence)))
    return seek_sequence, total_seek

# SSTF（最短寻道时间优先）算法
def SSTF(requests, start):
    seek_sequence = [start]
    total_seek = 0
    while requests:
        closest = min(requests, key=lambda x: abs(x - start))
        total_seek += abs(closest - start)
        start = closest
        seek_sequence.append(closest)
        requests.remove(closest)
    return seek_sequence, total_seek

# SCAN（扫描）算法
def SCAN(requests, start, direction='up'):
    requests.sort()
    seek_sequence = []
    total_seek = 0
    if direction == 'up':
        for request in requests:
            if request >= start:
                seek_sequence.append(request)
        for request in reversed(requests):
            if request < start:
                seek_sequence.append(request)
    else:
        for request in reversed(requests):
            if request <= start:
                seek_sequence.append(request)
        for request in requests:
            if request > start:
                seek_sequence.append(request)
    seek_sequence.insert(0, start)
    total_seek = sum(abs(seek_sequence[i] - seek_sequence[i-1]) for i in range(1, len(seek_sequence)))
    return seek_sequence, total_seek

# 示例
requests = [98, 183, 37, 122, 14, 124, 65, 67]
start = 53

sequence, total_seek = FCFS(requests, start)	
print(f"Seek Sequence: {sequence}")
print(f"Total Seek Operations: {total_seek}")

参考

操作系统常见面试题总结

2020届秋招面试题总结-操作系统篇

2.5w字 + 36 张图爆肝操作系统面试题，太牛逼了