9.操作系统

一、操作系统基础

1.1 什么是操作系统？

1. 操作系统是管理计算机硬件与软件资源的软件程序，是计算机的基石。
2. 操作系统的内核（Kernel）是操作系统的核心部分，负责系统的内存管理、硬件设备管理、文件系统管理和应用程序管理。内核是连接应用程序和硬件的桥梁，决定着系统的性能和稳定性。

1.2 操作系统的内核和CPU有什么区别？

1. 操作系统的内核属于操作系统层面，而CPU属于硬件。
2. CPU主要提供运算，处理各种指令的能力。内核主要负责系统的管理。

下图是程序、内核、CPU三者的关系：

Kernel_Layout

1.3 操作系统主要有哪些功能？

1. 进程和线程的管理，进程的创建、撤销、阻塞、唤醒，进程间的通信等。；
2. 存储管理，内存的分配和管理、外存（磁盘等）的分配和管理等；
3. 文件管理，文件的读、写、创建及删除等；
4. 设备管理，完成设备（输入输出设备和外部存储设备等）的请求或释放，以及设备启动等功能；
5. 网络管理，操作系统负责管理计算机网络的使用。；
6. 安全管理，用户的身份认证、访问控制、文件加密等，以防止非法用户对系统资源的访问和操作；

1.4 什么是用户态和内核态？

根据进程访问资源的特点，可以把进程在系统上的运行分为用户态和内核态：

• 用户态：用户态运行的进程可以直接读取用户程序的数据，拥有较低的权限。当应用程序需要执行某些需要特殊权限的操作，例如读写磁盘、网络通信等，就需要向操作系统发起系统调用请求，进入内核态。
• 内核态：内核态运行的进程几乎可以访问计算机的任何资源，包括系统的内存空间、设备、驱动程序等，不受限制，拥有非常高的权限。

用户态和内核态

总结：内核态相比用户态拥有更高的特权级别，因此能够执行更底层、更敏感的操作。不过，由于进入内核态需要付出较高的开销，应该尽量减少进入内核态的次数，以提高系统的性能和稳定性。

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

• 在 CPU 的所有指令中，有一些指令是比较危险的比如内存分配、设置时钟、IO 处理等，如果所有的程序都能使用这些指令的话，会对系统的正常运行造成灾难性地影响。因此，我们需要限制这些危险指令只能内核态运行。这些只能由操作系统内核态执行的指令也被叫做 特权指令 。

• 如果计算机系统中只有一个内核态，那么所有程序或进程都必须共享系统资源，例如内存、CPU、硬盘等，这将导致系统资源的竞争和冲突，从而影响系统性能和效率。并且，这样也会让系统的安全性降低，毕竟所有程序或进程都具有相同的特权级别和访问权限。

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

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

1. 系统调用：用户态进程主动要求切换到内核态；
2. 中断：当设备完成用户请求的操作后，会向CPU发出相应的中断信号。
3. 异常：当CPU在执行运行在用户态的程序时，发生了某些事先不可知的异常，就会触发切换。

住：中断和异常类似，都是通过中断向量表来找到相应的处理程序进行处理。区别在于，中断来自处理器内部，异常是执行当前指令的结果。

1.7 系统调用的过程了解吗？

1. 用户态的程序发起系统调用，因为系统调用中涉及一些特权指令，用户态程序权限不足，就会中断执行。
2. 发生中断后，当前CPU执行的程序就会中断，调转到中断处理程序。内核程序开始执行，也即开始处理系统调用。
3. 内核处理完成后，主动触发Trap，再次发生中断，切换回用户态工作。

系统调用的过程

1.8 系统调用和库函数调用的区别？

• 系统调用通常不可替换，而库函数通常可替换。
• 系统调用通常提供最小接口，而库函数通常提供较复杂功能。
• 系统调用运行在内核空间，而库函数运行在用户空间。
• 内核调用都返回一个整数值，而库函数并非一定如此。
• 系统调用开销相对库函数来说更大。

二、进程和线程

2.1 什么是进程、线程和协程？

• 进程：指计算机中正在运行的程序实例。比如，打开浏览器，就是一个进程。
• 线程：也被称为轻量级进程。多个线程可以在同一个进程中同时执行，并且共享进程的资源。比如内存空间、网络连接等。
• 协程：也被称为微线程，是一种用户态的轻量级线程，一个线程可以拥有多个协程，协程完全由程序所控制，能提升性能，不会像线程切换那样消耗资源。

2.2 进程和线程的区别是什么？

从JVM的角度来说一说两者区别，

一个进程可以有多个线程，多个线程共享进程的堆和元空间的资源，但是每个线程有自己的程序计数器、虚拟机栈和本地方法栈。

• 线程是进程划分成的最小的运行单位，一个进程在其执行的过程中可以产生多个线程。
• 线程和进程最大的不同在于，各个进程是独立的，而各个线程则不一定，因为同一个进程中的线程极有可能会互相影响。
• 线程执行开销小，不利于资源的管理和保护；而进程则相反。

2.3 为什么要使用多线程？

• 线程可以比作轻量化的进程，是执行程序的最小单位，线程间的切换和调度的成本远远小于进程。
• 现在的系统要求百万级甚至千万级并发量，而多线程并发编程正式开发高并发系统的基础，使用多线程能够大大提高系统整体的并发能力和性能。

2.4 线程间同步的方式有哪些？

• 互斥锁：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。比如 Java 中的 synchronized 关键词和各种 Lock 都是这种机制。
• 读写锁：允许多个线程读取共享资源，但是只有一个线程可以对共享资源进行写操作。
• 信号量：允许同一时刻多个线程访问同一资源，但是控制同一时刻可访问的最大线程数量。
• 屏障：用于等待多个线程到达某个点再一起继续执行。
• 事件：通过通知操作的方式保持多线程同步。

2.5 什么是PCB？

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

PCB包括以下信息：

• 进程的描述信息；
• 进程的调度信息；
• 进程对资源的需求情况；
• 进程打开的文件信息；

2.6 进程有哪几种状态？

进程状态图转换图

• 创建：进程正在被创建，尚未达到就绪状态。
• 就绪：进程处于准备运行状态，此时进程获得了除处理器之外的一切资源，一旦得到CPU分配的时间片即可运行。
• 运行：进程正在处理器上运行。
• 阻塞：又称等待，进程正在等待某一事件而暂停运行，比如等待某资源或等待IO操作完成。哪怕此时CPU空闲，该线程也不能运行。
• 结束：进程正在从系统中消失，退出运行。

2.7 进程间通信方式有哪些？

1. 管道/匿名管道：仅用于具有亲缘关系的父子进程间、或兄弟进程间通信。
2. 有名管道：遵循先进先出，以磁盘文件的方式存在，可以实现本机中任意两个进程通信。
3. 信号：用于通知接收进程某个事件已经发生。
4. 消息队列：是消息的链表，存放在内核中，可以实现消息的随机查询。克服了信号承载信息量少、管道只能承载无格式字节流以及缓冲区受限的缺点。
5. 信号量：相当于一个计数器，用于多进程对共享数据的访问，主要用于进程间同步。
6. 共享内存：使得多个进程可以访问同一块内存空间，不同进程之间可以及时看到其他进程对共享内存中数据的更新。
7. 套接字：主要用于客户端和服务器之间通过网络进行通信。

2.7.1 管道有了解过吗？说一说

管道主要用于实现两个或多个进程间的数据传输。可以将一个进程的输出连接到另一个进程的输入，从而实现数据的流动和共享。

管道主要分为两种类型：匿名管道和有名管道。

2.7.2 那分别说说匿名管道和有名管道

1. 匿名管道：匿名管道是一种最简单的管道形式，只能用于父进程与其直接创建的子进程之间的通信。匿名管道是单向的，数据只能在一个方向上流动。它通过操作系统提供的缓冲区将数据从一个进程传递给另一个进程。
2. 命名管道：命名管道是一种更通用的管道形式，可以用于不相关的进程之间的通信。命名管道是有名字的，可以被多个进程打开和使用。命名管道可以在不同的进程之间实现双向数据传输。

2.8 进程的调度算法有哪些？

常见进程调度算法

• 先来先服务：从就绪队列中选择一个最先进入队列的进程分配资源。
• 短作业优先：从就绪队列中选择运行时间最短的进程分配资源。
• 时间片轮转：是一种最古老、最简单、最公平、使用最广的算法。每个进程被分配一个时间片。
• 优先级调度：给每个进程分配优先级，按优先级顺序执行进程。
• 多级反馈队列：既能使高优先级的作业得到响应，又能使短作业迅速完成，是一种公认的较好的进程调度算法。

2.9 什么是僵尸进程和孤儿进程？

• 僵尸进程：子进程已经终止，但是父进程仍在运行，且父进程没有调用wait()系统调用来获取子进程的状态信息，释放子进程占用的资源，导致子进程的PCB仍然存在于系统中，但无法被进一步使用。
• 孤儿进程：一个进程的父进程已经终止或不存在，但该进程仍然在运行。

三、死锁

3.1 什么是死锁

多个进程或线程同时被阻塞，他们中的一个或全部都在等待某个资源被释放。由于进程或线程被无限期的阻塞，因此程序不可能正常终止。

比如，现在有两个进程A和B，以及两个资源X和Y，进程A占用X资源，现在需要Y资源，但是进程B此时占用Y资源，需要X资源。两个进程都在等对方释放各自的资源，无法继续往下执行，所以陷入了死锁状态。

3.2 产生死锁的必要条件是什么？

1. 互斥：资源必须处于非共享模式，即一次只有一个进程可以使用该资源。
2. 占有并等待：一个进程至少应该占有一个资源，并等待另一个资源，而需要的资源被其他进程占有。
3. 非抢占：进程所占有的资源不能被抢占，只有能进程执行完毕后才会释放。
4. 循环等待：有一组进程P1、P2。。。Pn，P1所需的资源被P2占有，P2所需的资源被P3占有。。。Pn的所需资源被P1占有。

注：这四个条件是必要条件。也即只要发生死锁，这些条件必然成立，但是这些条件有一个不满足，就不会发生死锁。

3.3 写一个模拟产生死锁的代码

线程死锁示意图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public class Main{
    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() + "获取资源1");
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println(Thread.currentThread() + "等待资源2");
                synchronized (resource2){
                    System.out.println(Thread.currentThread() + "获取资源2");
                }
            }
        }, "线程1").start();

        new Thread(() -> {
            synchronized (resource2){
                System.out.println(Thread.currentThread() + "获取资源2");
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println(Thread.currentThread() + "等待资源1");
                synchronized (resource1){
                    System.out.println(Thread.currentThread() +"获取资源1");
                }
            }
        }, "线程2").start();
    }
}

运行结果：

1
2
3
4

Thread[线程1,5,main]获取资源1
Thread[线程2,5,main]获取资源2
Thread[线程1,5,main]等待资源2
Thread[线程2,5,main]等待资源1

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

3.4 解决死锁的方法

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

3.4.1 死锁的预防

1. 静态分配策略。可以破坏产生死锁的第二个条件，指一个进程必须在执行前就申请到它所需要的全部资源，得到所有资源后，才能开始执行。这种策略的逻辑很简单，但是缺点是严重降低了资源利用率。
2. 层次分配策略。可以破坏产生死锁的第四个条件，所有资源被分成多个层次，一个进程得到某一层的一个资源后，只能再申请较高一层的资源；当一个进程要释放某一层的资源时，必须先释放所占用的较高层的资源，这样就避免了循环等待。

3.4.2 死锁的避免

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

最具有代表性的算法就是银行家算法，用一句话描述就是：当一个进程申请使用资源的时候，银行家算法通过先试探分配给该进程资源，然后通过安全性算法判断分配后系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待，若安全，则给该进程分配资源。

银行家算法改善了死锁预防中的资源利用率低的问题，但是缺点是需要不断地检测每个进程对各类资源的占用和申请，并进行安全性检查，需要花费较多时间。

3.4.3 死锁的检测

操作系统中每个时刻的系统状态都可以用进程-资源分配图来表示，可以用于检测系统是否处于死锁状态。

用方框表示资源类，方框中的黑点表示资源类中的各个资源，圆圈表示进程，用有向边表示进程申请资源和资源被分配的情况。

进程-资源分配图

图2-21中共有三个资源类，每个进程的资源占有和申请情况已经可以清楚看到。在这个图中，由于存在占有和等待资源的环路，导致一组进程永远处于等待资源的状态，所以产生了死锁。

但是存在环路并不一定是发生了死锁。比如图2-22中，也存在环路，虽然进程 P1 和进程 P3 分别占用了一个资源 R1 和一个资源 R2，并且因为等待另一个资源 R2 和另一个资源 R1 形成了环路，但进程 P2 和进程 P4 分别占有了一个资源 R1 和一个资源 R2，它们申请的资源得到了满足，在有限的时间里会归还资源，于是进程 P1 或 P3 都能获得另一个所需的资源，环路自动解除，系统也就不存在死锁状态了。

所以可以通过以下步骤检测是否产生了死锁：

1. 如果进程-资源分配图中无环路，则此时系统没有发生死锁。
2. 如果进程-资源分配图中有环路，且每个资源类仅有一个资源，则系统中已经发生了死锁。
3. 如果进程-资源分配图中有环路，且涉及到的每个资源类由多个资源，此时系统未必会发生死锁。

3.4.4 死锁的解除

1. 立即结束所有进程的执行，重新启动操作系统。这种方法简单，但是之前的所有工作全部作废，损失很大。
2. 撤销涉及死锁的所有进程，解除死锁后继续运行。这种方法能彻底打破死锁的循环等待条件，但是付出的代价也很大。
3. 逐个撤销涉及死锁的进程，回收其资源直至死锁解除。
4. 抢占资源。从涉及死锁的几个进程中抢占资源，把获得的资源再分配给涉及死锁的进程，直至死锁解除。

四、内存管理

4.1 内存管理主要是做什么？

内存管理主要做的事情

• 内存分配与回收：对进程所需的内存进行分配和释放。
• 地址转换：将程序中的虚拟地址转换成为内存中的物理地址。
• 内存扩充：当没有足够的内存时，利用虚拟内存的技术或自动覆盖技术，从逻辑上扩充内存。
• 内存映射：将一个文件直接映射到进程的进程空间中，这样可以通过内存指针直接存取文件内容。
• 内存优化：通过调整内存分配策略和回收算法来优化内存使用效率。
• 内存安全：保证进程间使用内存互不干扰，避免恶意程序破坏系统安全性。

4.2 什么是内存碎片？

内存碎片是内存的申请和释放产生的，通常分为以下两种：

• 内部内存碎片：已经分配给内存使用，但是还未使用的内存。
• 外部内存碎片：由于未分配的连续内存区域太小，以至于不能满足任何进程所需的内存需求，这些小片段且不连续的内存空间。

内存碎片

4.3 常见的内存管理方式有哪些？

• 连续内存管理：为一个用户程序分配一个连续的内存空间，内存利用率一般不高。
• 非连续内存管理：允许一个程序使用的内存分布在离散或者说不连续的内存中，比较灵活。

4.3.1 连续内存管理

• 块式管理：将内存分为几个固定大小的块，每个块中只包含一个进程。但是这种方法存在严重的内存碎片问题。
• 伙伴系统算法：Linux系统中连续内存分配算法，将内存按2的幂次划分，并将相邻的内存块组合成为一堆伙伴。当进行内存分配时，伙伴系统会尝试找到大小最合适的内存块。如果找到的内存块过大，就将其一分为二，分成两个大小相等的伙伴块。如果还是大的话，就继续切分，直到到达合适的大小为止。假设两块相邻的内存块都被释放，系统会将这两个内存块合并，进而形成一个更大的内存块，以便后续的内存分配。这样就可以减少内存碎片的问题，提高内存利用率

伙伴系统（Buddy System）内存管理

4.3.2 非连续内存管理

• 段式管理：以段的形式管理和分配内存。
• 页式管理：把物理内存分为连续等长的物理页，应用程序的虚拟地址空间也被分为连续等长的虚拟页。
• 段页式管理：结合了段式和页式管理的一种内存管理机制，把物理内存先分为若干段，每个段又继续分为若干大小的页。

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

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

• 隔离进程：使进程间彼此隔离，一个进程无法更改另一个进程的物理内存。
• 提升物理内存的利用率。
• 简化内存管理。
• 多个进程共享物理内存。
• 提高内存使用安全性。
• 提供更大的可使用内存空间。

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

物理地址是物理内存中的地址，也即内存地址寄存器中的地址。

虚拟地址是程序中访问的内存地址，也即开发时访问的地址。

操作系统中一般通过内存管理单元将虚拟地址转化为物理地址，这个过程被称为地址转换。

4.4.2 虚拟地址和物理地址之间是怎么映射的？

主要有三种方式：

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

现代操作系统中更多采用分页机制。

4.4.3 为什么虚拟地址切换空间会比较费时？

进程都有自己的虚拟地址空间，把虚拟地址转换为物理地址需要查找页表，页表查找是一个很慢的过程，因此通常使用 Cache 来缓存常用的地址映射，这样可以加速页表查找。 这个 Cache 就是 TLB（translation Lookaside Buffer）， TLB 本质上就是一个 Cache，是用来加速页表查找的)。

由于每个进程都有自己的虚拟地址空间，每个进程都有自己的页表记录虚拟地址与物理地址的转换关系， 那么当进程切换后页表也要进行切换，页表切换后 TLB 就失效了，Cache 失效导致命中率降低，那么虚拟地址转换为物理地址就会变慢，表现出来的就是程序运行会变慢。而线程切换则不会导致 TLB 失效，因为线程无需切换地址空间，因此我们通常说线程切换要比较进程切换块，原因就在这里。

4.5 分段机制

分段机制以段的形式管理、分配物理内存。

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

分段机制通过段表映射虚拟地址和物理地址。虚拟地址由两部分组成：

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

分段机制下的地址翻译过程

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

1. 内存管理单元首先解析得到虚拟地址中的段号；
2. 通过段号去段表中取出对应的段信息；
3. 从段信息中取出该段的起始地址加上段内偏移量，最终得到物理地址。

4.5.2 通过段号一定能找到对应的段表项吗？

不一定。段表项可能不存在：

• 段表项被删除。
• 段表项还未创建。如果内存不足或无法分配连续的物理内存块就会导致段表项无法被创建。

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

在分段机制中，每个段的大小可以不同，因此在分配内存时会留下不同大小的空闲空间，这些空闲空间可能无法被合并使用，从而导致外部碎片的产生。当内存分配器需要寻找一块足够大的连续内存块时，它可能会因为这些零散的空闲空间而无法找到合适的内存块，从而导致内存分配失败。

分段机制导致外部内存碎片

4.6 分页机制

分页机制把物理内存分成连续等长的物理页。

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

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

每个应用程序都会有一个对应的页表。

分页机制下的地址翻译过程

虚拟地址由两部分组成：

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

具体翻译过程如下：

1. 内存管理单元首先解析得到虚拟地址中的虚拟页号；
2. 通过虚拟页号找到页表，取出对应的物理页号；
3. 通过物理页号对应的起始地址加上页内偏移量得到最终的物理地址。

4.6.2 通过页号一定能找到对应的物理页号吗？

不一定！可能会存在页缺失。也即物理内存中没有对应的物理页，或者物理页与虚拟页之间未建立映射。

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

以32位操作系统为例，一个程序啥也不干，光页表大小就得占4MB。应用程序一旦多起来，页表的开销非常大。而且绝大多数应用程序可能只能用到页表中的几项，其他只能浪费。

所以为了解决这个问题，引入了多级页表，多级页表对应多个页表，每个页表与前一个页表相关联，可以极大节省空间占用。

多级页表

多级页表属于时间换空间的典型，利用增加页表查询次数减少页表占用的空间。

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

TLB也称为快表，目的是提高虚拟地址到物理地址的转换速度。

加入 TLB 之后的地址翻译

TLB本质上属于内存管理单元，其实是一块高速缓存，缓存了虚拟页号到物理页号之间的映射关系。可以简单看作是哈希表，key是虚拟页号，value是物理页号。

使用了快表后翻译流程：

1. 用虚拟地址中的虚拟页号作为key去快表中查询；
2. 如果能查到对应的物理页，就不用去查询页表，这种情况被称为TLB命中；
3. 如果查不到，再去也飙中查询，同时将页表中查到的项加入到快表中。
4. 当快表被填满时，又要重新登记新页时，按淘汰策略淘汰掉一个页。

其实本质上相当于Redis缓存。

4.6.5 什么是页缺失？

当软件试图访问已映射在虚拟空间中，但是未被加载在物理内存中的一个分页时，由内存管理单元发出的中断。

常见的页缺失有以下两种：

• 硬性页缺失：物理内存中没有对应的物理页。
• 软性页缺失：物理内存中有对应的物理页，但是虚拟页还未和物理页建立映射。

4.7 页面置换算法

4.7.1 页面置换算法的作用

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

4.7.2 常见的页面置换算法

常见的页面置换算法

• 最佳页面置换算法：优先选择淘汰的页面是以后永不使用的，或者长时间不再访问的页面，这样可以获取最低的缺页率。只存在于理论中，无法实现。
• 先进先出页面置换算法：总是淘汰先进入内存的页面，也即选择在内存中驻留时间最久的页面淘汰。
• 最近最久未使用页面置换算法：该算法赋予每个页面一个访问字段，用来记录该页面自上次访问以来经历的时间，淘汰最近最久未使用的页面。
• 最少使用页面置换算法：和最近最久未使用算法类似，不过该算法选择的是一段时间内使用最少的页面作为淘汰页。
• 时钟页面置换算法：也可以认为是最近未使用算法，也即淘汰的页面都是最近没有使用的。

4.7.3 先进先出页面置换算法性能为什么不好？

1. 经常访问或需要长期存在的页面会被频繁调入调出。
2. 无法识别访问页面的频率和重要性，只考了页面进入的顺序。

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

4.8.1 共同点

1. 都是非连续内存管理的方法；
2. 都采用了地址映射的方法，将虚拟地址映射到物理地址。

4.8.2 区别

• 分页机制以页为单位，分段机制以段为单位。页的大小是固定的，通常为2的幂次方，而段的大小是不确定的，通常由运行的程序决定。
• 页是物理单位，段式逻辑单位。
• 分段机制容易出现外部内存碎片。分页机制解决了外部内存碎片的问题，但是可能会出现内部内存碎片问题。
• 分页机制采用了页表来完成虚拟地址到物理地址的映射，其中页表通过多级页表来实现多级映射。而分段机制则采用段表来完成，没有多级段表。
• 分页机制对程序没有任何要求，程序只需要按照虚拟地址进行访问即可。分段机制需要程序员主动将程序分为多个段，并显式的使用段寄存器来访问不同段。

4.9 局部性原理了解吗？

在程序执行过程中，数据和指令的访问存在一定的空间和时间上的局部特点。

• 时间局部性：由于程序中存在一定的循环或者重复操作，因此会反复访问同一个页或一些特定的页，这就体现了时间局部性特点。为了利用时间局部性，分页机制中通常采用缓存机制来提高页面的命中率。
• 空间局部性：由于程序中数据和指令的访问通常是具有一定的空间连续性，因此访问某个页时，会顺带访问相邻的一些页。为了利用空间局部性，分页机制中通常采用预取技术来预先将相邻的一些页存入内存缓存中，以便未来能直接使用。

总之，局部性原理是计算机体系结构设计的重要原则之一，也是许多优化算法的基础。采用缓存和预取技术，可以提高页面的命中率，从而提高内存访问效率。

五、文件系统

5.1 文件系统的功能？

1. 存储管理；
2. 文件管理；
3. 目录管理；
4. 文件访问控制。

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

1. 硬链接：是一个指向文件物理地址的链接，多个硬链接共享同一个物理文件。硬链接只有在同一个文件系统中才能使用，因为它们使用相同的索引节点标识文件。在删除一个硬链接时，文件本身不会被删除，只有当最后一个硬链接被删除时，文件才会被删除。
2. 软链接：是一个指向文件名的链接，它是一个特殊类型的文件，它存储着另一个文件的路径名，相当于快捷方式。软链接可以跨文件系统，因为它们使用路径名标识文件。当删除一个软链接时，原始文件不受影响，只有软链接本身被删除。

总结：软链接更灵活，但是性能不如硬链接。硬链接的缺点是不能跨越文件系统，但是优点是可以减少磁盘空间占用，因为多个硬链接共享一个物理文件。

5.3 硬链接为什么不能跨文件系统？

因为硬链接是通过索引节点建立连接的，然而每个文件系统都有自己的独立索引表，并且每个索引表只维护该文件系统内的索引。在不同的文件系统之间创建硬链接会导致索引节点之间冲突，所以硬链接不能跨文件系统。

5.4 提高文件系统性能的方式有哪些？

• 优化硬件
• 选择合适的文件系统
• 运用缓存
• 避免磁盘过度使用
• 对磁盘进行合理分区

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

常见的磁盘调度算法

1. 先来先服务算法：按照请求到达磁盘调度器的顺序处理。不过平均寻道时间较长，而且后到的请求可能需要等待很长时间。
2. 最短寻道时间优先算法：优先选择距离当前磁头位置最近的请求进行服务。但远离磁头位置的请求可能长时间得不到响应。
3. **扫描算法(SCAN)**：磁头沿着一个方向扫描磁盘，如果有请求就处理，直到磁盘边界，然后改变方向，依次往复。
4. **循环扫描算法(C-SCAN)**：SCAN的变体，只在磁盘的一侧进行扫描，并且只按照一个方向扫描，直到到达磁盘边界，然后回到磁盘起点，重新开始循环。
5. **边扫描边观察算法(LOOK)**：SCAN是到了磁盘边界才改变移动方向，这样可能会做很多无用功，LOOK是移动方向上如果没有请求，就立即改变方向，依次往复。
6. **均衡循环扫描算法(C-LOOK)**：C-SCAN是到边界才改变方向，这样可能会做很多无用功，C-LOOK对C-SCAN做了改进，如果移动方向上没有请求了，就立即让磁头返回，而且不需要返回到起点，只需要返回到有磁道访问请求的位置即可。