操作系统面试_V2023 思维导图模板_ProcessOn思维导图、流程图

三、内存管理

虚拟内存

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

概念：虚拟内存是一种计算机内存管理技术，它将计算机硬盘空间作为扩展内存使用，使得应用程序能够访问比物理内存更大的地址空间。

作用&优缺点

优点

进程隔离

提升物理内存使用率

提高内存使用安全性：控制进程对物理内存的访问，隔离不同进程的访问权限，提高系统的安全性。

提供更大的可使用内存空间

缺点

虚拟内存的实现需要消耗一定的计算机资源，包括硬盘空间、CPU时间和内存带宽等，可能会影响系统的性能

没有虚拟内存有什么问题？(参考虚拟内存提供的能力回答这个问题)

用户程序可以访问任意物理内存，可能会不小心操作到系统运行必需的内存，进而造成操作系统崩溃，严重影响系统的安全。

程序运行过程中使用的所有数据或指令都要载入物理内存，根据局部性原理，其中很大一部分可能都不会用到，白白占用了宝贵的物理内存资源。

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

物理地址：内存地址寄存器中的地址

虚拟地址：程序所使用的内存地址

虚拟地址与物理内存地址是如何映射的？（操作系统是如何管理虚拟地址与物理地址之间的关系？）

内存管理单元MMU（Memory Management Unit，内存管理单元）

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

1. 分段机制

2. 分页机制

3. 段页机制

常见的内存管理方式有哪些？（虚拟内存实现方式？）

1. 连续内存管理

块式管理：存在严重内存碎片问题。

在Linux中使用Buddy System伙伴系统实现。

对于内部内存碎片的问题，Linux 采用 SLAB 进行解决

2. 非连续内存管理

段式管理

页式管理

段页式管理

分段机制

应用程序的虚拟地址空间被分为大小不等的段，段是有实际意义的，每个段定义了一组逻辑信息，例如有主程序段 MAIN、子程序段 X、数据段 D 及栈段 S 等。

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

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

分段机制下的虚拟地址由两部分组成：段号+段内偏移量

翻译过程

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

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

段表项被删除：软件错误、软件恶意行为等情况可能会导致段表项被删除。

段表项还未创建：如果系统内存不足或者无法分配到连续的物理内存块就会导致段表项无法被创建。

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

分页机制

把主存（物理内存）分为连续等长的物理页，应用程序的虚拟地址空间划也被分为连续等长的虚拟页。

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

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

分页机制下的虚拟地址由两部分组成：页号+页内偏移量

翻译过程

通过虚拟页号一定要找到对应的物理页号吗？找到了物理页号得到最终的物理地址后对应的物理页一定存在吗？

不一定。存在页缺失。

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

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

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

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

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

换页机制有什么用？

什么是页面置换算法？页面置换算法有哪些？

当物理内存不足时，操作系统需要选择一些页面从物理内存中移除，以便为新的页面腾出空间。页面置换算法的目标是最小化页面置换的次数，从而提高系统的性能。

页面置换算法

哪一种页面置换算法实际用的比较多？

LRU 算法是实际使用中应用的比较多

页面置换算法的评价指标是什么？

缺页率：在一段时间内发生缺页的次数与总访问次数的比率，缺页率越低，表示页面置换算法的性能越好

页面置换次数：指在一段时间内发生页面置换的次数，页面置换次数越低，表示页面置换算法的性能越好

页面访问时间：指访问一个页面所需的时间，页面访问时间越短，表示页面置换算法的性能越好。

段页机制

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

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

1. 段式地址映射。

2. 页式地址映射。

四、文件系统

存储管理

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

文件管理

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

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

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

目录管理

文件访问控制

五、常见面试题

一个进程可以创建多少线程。

外中断和异常有什么区别

解决Hash冲突四种方法

开放定址法

链地址法

再hash法

建立公共溢出区

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

共同点

都是非连续内存管理的方式。

都采用了地址映射的方法，将虚拟地址映射到物理地址，以实现对内存的管理和保护。

区别：

分页机制以页面为单位进行内存管理，而分段机制以段为单位进行内存管理。页的大小是固定的，由操作系统决定，通常为 2 的幂次方。而段的大小不固定，取决于我们当前运行的程序。

页是物理单位，即操作系统将物理内存划分成固定大小的页面，每个页面的大小通常是 2 的幂次方，例如 4KB、8KB 等等。而段则是逻辑单位，是为了满足程序对内存空间的逻辑需求而设计的，通常根据程序中数据和代码的逻辑结构来划分。

分段机制容易出现外部内存碎片，即在段与段之间留下碎片空间(不足以映射给虚拟地址空间中的段)。分页机制解决了外部内存碎片的问题，但仍然可能会出现内部内存碎片。

分页机制采用了页表来完成虚拟地址到物理地址的映射，页表通过一级页表和二级页表来实现多级映射；而分段机制则采用了段表来完成虚拟地址到物理地址的映射，每个段表项中记录了该段的起始地址和长度信息。

分页机制对程序没有任何要求，程序只需要按照虚拟地址进行访问即可；而分段机制需要程序员将程序分为多个段，并且显式地使用段寄存器来访问不同的段。

异常和中断的区别

【专项】调度算法

进程调度算法

先来先服务

短作业优先

时间片轮转

最短剩余时间优先

多级反馈队列调度

优先级调度

磁盘调度算法

1. 先来先服务 FCFS

由于没有考虑磁头移动的路径和方向，平均寻道时间较长。同时，该算法容易出现饥饿问题，即一些后到的磁盘请求可能需要等待很长时间才能得到服务。

2. 最短寻道时间优先算法 SSTF

易出现饥饿问题，即磁头附近的请求不断被服务，远离磁头的请求长时间得不到响应。

3. 扫描算法 SCAN

能够保证所有的请求得到服务，解决了饥饿问题。但是，如果磁头从一个方向刚扫描完，请求才到的话。这个请求就需要等到磁头从相反方向过来之后才能得到处理。

4. 循环扫描 C-SCAN

SCAN 算法的变体

5. 边扫描边观察 LOOK

LOOK 算法对 SCAN 算法进行了改进，如果磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向，依此往复。也就是边扫描边观察指定方向上还有无请求，因此叫 LOOK。

6. 均衡循环扫描 C-LOOK

C-SCAN 只有到达磁盘边界时才能改变磁头移动方向，并且磁头返回时也需要返回到磁盘起点，这样可能会做很多无用功。C-LOOK 算法对 C-SCAN 算法进行了改进，如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。

页面置换算法

最佳页面置换算法OPT -- 而该算法无法实现，只是理论最优的页面置换算法

1. FIFO置换算法：一般只需要通过一个 FIFO 队列即可需求。不过，它的性能并不是很好

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

2. 时钟页面置换算法（CLOCK）

3. FIFO

4. LRU最近最少使用算法

5. LFU最不经常使用算法

参考文献

<a class="link" target="_blank" href="https://javaguide.cn/cs-basics/operating-system/operating-system-basic-questions-01.html">JavaGuide(Java面试+学习指南)操作系统常见面试题总结(上)</a>

<a class="link" target="_blank" href="https://javaguide.cn/cs-basics/operating-system/operating-system-basic-questions-02.html#%E4%BB%80%E4%B9%88%E6%98%AF%E5%86%85%E5%AD%98%E7%A2%8E%E7%89%87">JavaGuide(Java面试+学习指南)操作系统常见面试题总结(下)</a>

<a class="link" target="_bank" href="https://xiaolincoding.com/os/3_memory/vmem.html#%E5%A4%9A%E7%BA%A7%E9%A1%B5%E8%A1%A8">小林code</a>

一、计算机结构

冯诺依曼模型

计算机五大核心组成部分：控制器、运算器、存储器、输入、输出

内存、CPU、总线、输入、输出设备

存储器

存储器的层次结构

存储器

CPU Cache： L1 Cache 通常分为 dCache（数据缓存）和 iCache（指令缓存），L3 Cache 则是多个核心共享的

L1 Cache：指令缓存、数据缓存。几十kb到几百kb。随机访问延时是 1 纳秒

cat /sys/devices/system/cpu/cpu0/cache/index0/size

L2 Cache：几百 KB 到几 MB

cat /sys/devices/system/cpu/cpu0/cache/index2/size

L3 Cache：大小在几 MB 到几十 MB

cat /sys/devices/system/cpu/cpu0/cache/index3/size

内存：随机访问延时 100 纳秒

硬盘 SSD HDD

CPU 缓存一致性

缓存一致性问题

缓存一致性的问题具体是怎么发生的呢？

多核CPU对同时写一个共享资源，操作双核中的L1 Cache缓存不一致情况。

如何解决？

1. 写传播。最常见的实现方式：总线嗅探。

缺点： CPU 需要每时每刻监听总线上的一切活动，但是不管别的核心的 Cache 是否缓存相同的数据，都需要发出一个广播事件，这无疑会加重总线的负载。

2. 事务串行化。实现方式：升级版本基于总线嗅探的MESI协议。

CPU是如何执行任务的？

CPU如何读写数据？

CPU架构

CPU读写单位

CPU Cache Line（缓存块）：CPU不再是按字节访问内存，而是以64字节为单位的块(chunk)拿取，称为一个缓存行(cache line)。

CPU伪共享问题

概念：多个线程同时读写同一个 Cache Line 的不同变量时，而导致 CPU Cache 失效的现象

避免伪共享的方法？

1. 填充Padding。通过在对象的字段之间添加填充，使不同的字段位于不同的缓存行，避免多个线程同时访问同一缓存行。

Java中可以使用sun.misc.Contended注解来实现填充。

2. 对齐（Alignment）：通过将对象的字段调整为CPU缓存行的整数倍，确保每个字段位于不同的缓存行，避免多个线程同时访问同一缓存行。

Java中可以使用Unsafe类来手动进行字段对齐。

需要注意的是，填充和对齐都需要针对具体的硬件和操作系统进行优化，因此并不是所有情况下都能够有效解决伪共享问题。

CPU如何选择线程？

中断

中断是什么？

中断是系统用来响应硬件设备请求的一种机制。

如何处理中断处理程序时间过长问题？

为了避免由于中断处理程序执行时间过长，而影响正常进程的调度，Linux 将中断处理程序分为上半部和下半部：

上半部，对应硬中断，由硬件触发中断，用来快速处理中断；

下半部，对应软中断，由内核触发中断，用来异步处理上半部未完成的工作；软中断是以内核线程的方式执行。

系统调用

异常处理

什么是软中断？什么是硬中断？系统里面有哪些软中断？

<a class="link" target="_bank" href="https://xiaolincoding.com/os/1_hardware/soft_interrupt.html#%E7%B3%BB%E7%BB%9F%E9%87%8C%E6%9C%89%E5%93%AA%E4%BA%9B%E8%BD%AF%E4%B8%AD%E6%96%AD">如何定位软中断 CPU 使用率过高的问题？</a>

内核是怎么工作的？

什么是内核态和用户态？

用户态：用户态运行的进程可以直接读取用户程序的数据，拥有较低的权限。当应用程序需要执行某些需要特殊权限的操作，例如读写磁盘、网络通信等，就需要向操作系统发起系统调用请求，进入内核态。

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

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

主要是为了保证计算机系统的安全性、稳定性和性能。

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

系统调用：用户态进程 主动 要求切换到内核态的一种方式。

中断

异常

中断和异常类似，都是通过中断向量表来找到相应的处理程序进行处理。区别在于，中断来自处理器外部，不是由任何一条专门的指令造成，而异常是执行当前指令的结果。

什么是系统调用？

二、进程&线程

进程

概念：是资源（CPU、内存）分配的最小单位

分类

用户态进程：应用程序

内核态进程：内核本身的进程

进程状态

创建

就绪

运行

阻塞

终止

进程间通讯IPC方式

管道：半双工，只能单向。

信号

消息队列

共享内存

信号量

套接字Socket

上下文切换

特殊进程

守护进程

孤儿进程：一个进程的父进程已经终止或者不存在，但是该进程仍在运行。

僵尸进程：子进程已经终止，但是其父进程仍在运行，且父进程没有调用 wait()或 waitpid()等系统调用来获取子进程的状态信息，释放子进程占用的资源，导致子进程的 PCB 依然存在于系统中，但无法被进一步使用。这种情况下，子进程被称为“僵尸进程”。避免僵尸进程的产生，父进程需要及时调用 wait()或 waitpid()系统调用来回收子进程。

线程

用户态线程&内核态线程

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

互斥锁：Java 中的 synchronized 关键词和各种 Lock 都是这种机制。

信号量

屏障

事件Event：Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作。

线程状态有几种？

创建NEW

就绪READY

运行RUNNING

阻塞WAITING