面试-操作系统知识点整理

进程

进程间通信方式

各自的原理以及存在什么样的问题（没有银弹）

1. 管道（pipe）：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有血缘关系的进程间使用。进程的血缘关系通常指父子进程关系。（Linux的实现之一是|）

   优点：简单

   缺点：

   • 是半双工的，具有固定的读端和写端
   • 只能用于具有亲缘关系的进程之间的通信
   • 缓冲区大小有限

   步骤：

   1. 父进程创建管道，得到两个文件描述符，指向管道的两边
   2. 父进程fork出子进程，子进程也有两个文件描述符指向同一个管道
   3. 父子进程通过管道就可以通信了

2. 命名管道（fifo）：有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间通信。

   缺点：

   • 长期以文件形式存在于文件系统中，使用不当容易出错
   • 缓冲区有限

   可以用于不同计算机之间的通信。客户端通过一个公共的FIFO发请求到服务器，服务器为每个客户端创建一个专用的FIFO实现回传应答。不足就是服务器要应答许多客户端，以及处理客户端崩溃或无应答时服务器如何处理

3. 信号（signal）：信号是用于通知接收进程某一事件已经发生，如中断信号（SIGINT）

4. 消息队列（message queue）：消息队列是由消息组成的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。消息队列与管道通信相比，其优势是对每个消息指定特定的消息类型，接收的时候不需要按照队列次序，而是可以根据自定义条件接收特定类型的消息。

   优点：系统调用函数来实现消息发送和接收之间的同步，无需考虑同步问题

   缺点：信息的复制需要额外消耗CPU的时间

5. 信号量（semophore）：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它通常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。主要作为进程间以及同一进程内不同线程之间的同步手段。

   优点：同步进程

   缺点：信号量有限

   PV操作：P操作将信号量减1，V操作将信号量加1

6. 共享内存（shared memory）：共享内存就是映射一块能被多个进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问，共享内存是最快的IPC（进程间通信）方式，它是针对其他进程间的通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量配合使用，来实现进程间的同步和通信。

   优点：无须复制，信息量大

   缺点：进程需要同步

7. 套接字（socket）：套接字是一种通信机制，凭借这种机制，客户/服务器（即要进行通信的进程）系统的开发工作既可以在本地单机上进行，也可以跨网络进行。它可以让不在同一台计算机但通过网络连接计算机上的进程进行通信。因此，套接字明确地将客户端和服务器区分开来。

   优点：传输数据时间短，性能高；可以加密

   缺点：需对传输的数据进行解析

线程间通信（同步）方式

1. 互斥量(Mutex)：用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。比如Java中的synchronized和各种Lock都是这种机制。
2. 信号量(Semphares) ：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量
3. 事件(Event)：Wait/Notify，通过通知操作的方式来保持多线程同步

进程的状态

1. 创建状态
2. 就绪状态
3. 运行状态
4. 阻塞状态
5. 结束状态

线程的状态

1. NEW：一个线程处于新建状态
2. RUNNABLE：线程在执行或者在等待CPU资源
3. BLOCKED：同步阻塞，未能获得锁（在同步方法或者同步代码块中）
4. WAITING：等待状态，如wait()、join()、LockSupport#park
5. TIMED_WAITING：超时等待状态，如sleep、wait(time)、join(time)、LockSupport#parkNanos/parkUtil
6. TERMINATED ：运行结束

进程切换和线程切换的区别：进程切换涉及到虚拟地址空间的切换（涉及请求分页、页面置换、CPU寻址等），而线程共享所在进程的虚拟地址空间，线程切换不涉及虚拟地址空间的切换。因此进程之间切换的开销大于线程之间切换的开销。

进程的调度算法

1. 先来先服务（FCFS）

   优缺点：

   • 有利于长作业，不利于短作业
   • 有利于CPU密集型作业，不利于IO密集型作业

2. 短作业优先(SJF)：平均等待时间最短

   缺点：

   • 长作业线程饥饿

3. 时间片轮转

   每个进程执行完给定的时间片后，被中断放入到任务队列某尾

   缺点：时间片太小，会频繁发生中断、进程上下文切换，增加系统开销；太大，会退化成FCFS

4. 多级反馈队列

   原理：设置多个优先级的队列，每个队列用的是FCFS+时间片轮转，时间片随优先级的增加而减小，每个作业会先进入优先级最高的队列

5. 优先级调度：按优先级顺序进行调度

用户态和内核态

• 用户态：运行用户程序。进程所能访问的内存空间和对象受到限制
• 内核态：运行操作系统程序、操作硬件。能访问所有的内存空间和对

用户态切换为内核态的三种情况

• 系统调用：用户态进程通过系统调用申请使用操作系统提供的服务程序完成工作。访问文件、访问硬件
• 异常（也称为内中断）：CPU在执行用户态下的程序时，发生了某些事先不可知的异常，使当前进程切换到处理此异常的内核相关程序中。比如缺页异常
• 中断（也称为外中断）：CPU接收到来自系统的信号，表示发生了某个事件，CPU中止正在执行的程序而转去处理特殊事件。如IO中断。

临界资源和临界资源

临界资源是一次只允许一个进程使用的共享资源。

临界区是访问临界资源的代码片段。

内存

内存管理

做什么的？负责内存的分配与回收，以及地址转换（逻辑地址转换成相应的物理地址，称为CPU寻址）

连续分配管理

为一个用户程序分配一个连续的内存空间，如分块管理。将内存分为几个固定大小的块，每个块中只包含一个进程。空间浪费大

非连续分配管理

允许程序使用的内存分布在不相邻的内存中，如分页管理、分段管理、段页式管理。

分页管理：把内存分为大小相等且固定的一页一页的形式，页较小。通过页表对应逻辑地址和物理地址

分段管理：将程序按照逻辑关系划分为若干个段，每个段在内存中连续，各段之间可以不相邻。通过段表对应逻辑地址和物理地址

段页式管理机制：对于用户来说，按照段的逻辑关系进行划分，内存中按页划分每一段。通过段表找到页表的相关信息，再去页表中找对应的物理地址

分页与分段的共同点和区别

共同点：

• 离散分配内存的方式
• 都提高内存利用率，减少了内存碎片

区别：

• 页的大小是固定的，而段的大小取决于运行的程序
• 分页是为了满足操作系统内存管理的需求，而段是逻辑信息的单位，为了满足用户的需求

虚拟（逻辑）地址空间

是什么？虚拟地址空间是虚拟地址的集合，假设虚拟地址空间是N位，那么它有\(2^N\)个虚拟地址

有什么用？

• 程序可以使用一系列相邻的虚拟地址来访问物理内存中不相邻的区域
• 程序可以使用一系列虚拟地址来访问大于可用物理内存的内存缓冲区。当物理内存的供应量变小时，内存管理器会将物理内存页（通常大小为 4 KB）保存到磁盘文件。数据或代码页会根据需要在物理内存与磁盘之间移动。
• 不同进程使用虚拟地址彼此隔离。一个进程中的代码无法更改正在由另一进程或操作系统使用的物理内存。

局部性原理

局部性原理表现在两方面：

1. 时间局部性：如果程序中的某条指令执行，不久以后该指令可能再次执行；如果某数据被访问过，不久以后该数据可能再次被访问。产生时间局部性的典型原因，是由于在程序中存在着大量的循环操作。
2. 空间局部性：如果程序访问了某个存储单元，不久之后其附近的存储单元也将被访问。这是因为指令通常是顺序存放、顺序执行的。

应用：

• 内存管理中的快表
• 虚拟内存
• MySQL的B+树利用磁盘预读减少IO次数

页表管理

快表（Translation Lookaside Buffer，TLB）

快表是一种访问速度比内存快很多的高速缓冲存储器，用于加速逻辑地址到物理地址的转换。因为局部性原理，一般来说快表的命中率可以达到90%以上。

转换流程（类似Redis缓存）：

1. 根据逻辑地址中的页号查快表；
2. 如果该页在快表中，直接从快表中读取相应的物理地址；
3. 如果该页不在快表中，就访问内存中的页表，再从页表中得到物理地址，同时将页表中的该映射表项添加到快表中；
4. 当快表填满后，按照一定的算法对旧的页表项进行替换。

多级页表

原理：二级页表可以不存在或者不存在于内存

为什么要用它？避免把全部页表一直放在内存中占用过多空间，特别是那些根本就不需要的页表。多级页表属于时间换空间的典型场景。

虚拟内存

什么是虚拟内存？虚拟内存是内存管理的一种技术

优点：

• 虚拟内存让进程可以拥有超过系统物理内存大小的可用内存空间
• 虚拟内存提供一段连续的虚拟地址，便于内存管理

有哪些技术实现？

• 请求分页：建立在分页管理上，增加了请求调页和页面置换功能
• 请求分段：建立在分段管理上，增加了请求调段和分段置换功能
• 请求段页式：建立在请求段页式管理上

页面置换算法

若在页面中发现所要访问的页面不在内存中，则发生缺页中断，需要页面置换

1. OPT页面置换算法（最佳页面置换算法）：选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，保证获得最低的缺页率。
2. FIFO页面置换算法
3. LRU（Least Currently Used）页面置换算法（最近最少使用算法）
4. CLOCK算法(时钟置换算法)：
   • 简单CLOCK算法：每个页面设置一个访问位，将页面链接成循环队列。如果某个页被访问，则将访问位置为1，淘汰页面时，如果访问位是0则淘汰它，否则将访问位置为0，检查下一个页面；如果所有页面都是1，则进行第二次扫描
   • 改进的CLOCK算法：在考虑访问位的同时，再添加一个修改位。在其他条件相同时优先淘汰没有被修改过的页面，以避免IO操作。
5. LFU（Least Frequently Used）页面置换算法（最少使用算法）：选择使用频率最少的页面淘汰。缺点在于新加入的页面有更大概率被置换掉

IO多路复用

select

通过设置或检查存放描述符（fd）来进行下一步操作

缺点：

• 单个进程可监视的描述符数量有限，默认是1024（基于数组）
• 对socket扫描是线性扫描，时间复杂度是O（N）的
• 每次调用都要将fd从应用进程缓冲区拷贝到内核缓冲区
• 不是线程安全的，一个线程对某个描述符调用select，另一个线程关闭该描述符，会导致结果不确定

poll

类似于select，不过做了一些改变

• 描述符是pollfd，因此数量没有限制（基于链表）
• 对描述符的重复利用上比 select 高（select每次调用之前需要对参数进行重新设置，而poll不需要）

epoll

访问时间O（1），内核和用户空间共享一块内存，线程安全

• 当某个进程调用 epoll_create() 方法时，内核会创建一个 eventpoll 对象

• 创建 epoll 对象后，可以用 epoll_ctl() 向内核注册新的描述符或者是改变某个文件描述符的状态。

  • 已注册的描述符在内核中会被维护在一棵红黑树上
  • 通过回调函数内核会将 I/O 准备好的描述符加入到一个链表中管理，进程调用 epoll_wait() 便可以得到事件完成的描述符。

• 描述符事件有两种触发模式：LT（水平触发）和 ET（边沿触发）

  • LT：当 epoll_wait() 检测到描述符事件到达时，将此事件通知进程，进程可以不立即处理该事件，下次调用 epoll_wait()会再次通知进程。
  • ET：通知之后进程必须立即处理事件，下次再调用 epoll_wait() 时不会再得到事件到达的通知。

磁盘寻道算法

1. FCFS
2. 最短寻道算法
3. 扫描算法：如果从里到外扫描时，选择的下一个进程所访问的磁道最近且方向相同，直到扫描到最外面后再从外往里扫描
4. 循环扫描算法：从里到外扫描完之后，直接返回最里面继续从里到外扫描。（因为此时外部的磁道请求刚被处理完，而另一端的请求比较密集且等待时间较长）