Shopee后端面试题整理 - 操作系统篇_Tscharrl的专栏文章_微信文章

1. 进程和线程的区别

进程是分配资源的基本单位，线程是CPU调度的基本单位，同一进程下的各个线程共享资源。

进程有独立的地址空间，一个进程如果在保护模式下崩溃，不会对其它进程产生影响。
线程是一个进程中的不同执行路径。线程有自己的堆栈和局部变量（线程有独立的程序计数器、一组寄存器和栈），但线程之间没有单独的地址空间，一个线程崩溃，统一进程下所有线程都崩溃。（所以多进程程序比多线程程序更健壮）
一个程序至少有一个进程，一个进程至少有一个线程
线程的划分尺度小于进程，所以多线程程序并发性高
同一进程下的多个线程共享内存（地址空间），从而极大地提高了程序运行效率
每个线程都有独立的程序运行入口、顺序执行序列和程序出口，但线程不能独立执行，必须依赖进程
从逻辑角度来看，多线程的意义在于在一个应用程序中，有多个执行部分时可以同时执行。但OS并不把多个线程看成独立应用。
优缺点：线程开销小，进程方便资源管理和保护；进程可以跨机器迁移。
进程切换和线程切换：
- 进程切换：① 切换页目录以使用新地址空间；② 切换内核栈和硬件上下文；
- 线程切换不用切地址空间，也就是不用做①
- 上下文切换通过OS内核完成，性能损耗主要来源于① 寄存器内容切出切入；② 切换后CPU原本的缓存作废，TLB（页表缓冲）等都被刷新，导致一段时间的内存访问十分低效（线程切换没有这个问题）
内核线程、用户线程、轻量级线程
用户态、内核态

2. 进程通信 (七种)

www.jianshu.com/p/c1015f5ff…

管道（匿名管道、有名管道）、共享内存、信号量、消息队列、信号、套接字

管道（匿名管道）

半双工，数据只能沿一个方向流动；双方通信需要两个管道；
只能用于父子/兄弟进程；
数据读写类似队列，先进先出，写数据加在管道缓冲区的末尾，读数据从缓冲区头部读取；
缓冲区大小有限（管道存在于内存中，管道创建时，内存为缓冲区分配一个页面大小）；
管道传送无格式字节流，读写双方必须事先约定数据格式，比如多少个字节算一个消息；

命名管道（FIFO）

将路径名与管道关联，名字存在于文件系统中，管道中的内容存放在内存中；
因为有名字，所以没有亲缘关系的进程也能通信，只要能访问名字路径即可；

匿名管道和命名管道总结： （1）管道是特殊类型的文件，在满足先入先出的原则条件下可以进行读写，但不能进行定位读写。（2）匿名管道是单向的，只能在有亲缘关系的进程间通信；命名管道以磁盘文件的方式存在，可以实现本机任意两个进程通信。（3）**无名管道阻塞问题：**无名管道无需显示打开，创建时直接返回文件描述符，在读写时需要确定对方的存在，否则将退出。如果当前进程向无名管道的一端写数据，必须确定另一端有某一进程。如果写入无名管道的数据超过其最大值，写操作将阻塞，如果管道中没有数据，读操作将阻塞，如果管道发现另一端断开，将自动退出。（4）**命名管道阻塞问题：**有名管道在打开时需要确实对方的存在，否则将阻塞。即以读方式打开某管道，在此之前必须一个进程以写方式打开管道，否则阻塞。此外，可以以读写（O_RDWR）模式打开有名管道，即当前进程读，当前进程写，不会阻塞。

使用管道需要注意：

使用管道需要注意的几个点

使用管道需要注意的四种特殊情况

共享内存

多个进程直接读写同一块内存空间
最快。原因：进程间通信不需要通过内核，只需要对共享内存区域操作即可
内核留出一块内存区，需要共享内存的进程将其映射到自己的私有地址空间（同一内存区映射到共享它的不同进程的地址空间），该进程就可以直接读写这一块内存，无需数据拷贝
多进程共享同一块内存，需要同步机制达到进程间的同步与互斥（如信号量）（也就是说和其他进程间通讯方式不同，共享内存需要用户自己实现同步）

信号量

是一个计数器
创建、等待、挂出信号量：
- 创建：调用者指定信号量初值，对二值信号量来说为0或1
- 等待（P操作）：测试信号量的值，小于0就阻塞
- 挂出（V操作）：信号量值加1
P操作、V操作、信号量值加减应当是原子操作；因此，信号量通常在内核中实现

消息队列

存放在内核中的消息链表，有特定格式，每个消息队列由消息队列标识符表示
先进先出。但允许随机定位查询查询，消息不一定要以先进先出的次序读取，也可以按消息类型读取
消息队列存放在内核中，只有在内核重启（即OS重启）或显式删除一个消息队列时，消息队列才会真正删除
- 无名管道：只存在于内存
- 命名管道：存在于实际的磁盘介质或者文件系统
与管道不同的是，消息队列在某个进程往一个队列写入消息之前，并不需要另外某个进程在该队列上等待消息的到达
允许一个或多个进程写入与读取消息
消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点

信号

信号是软件层次上对中断机制的一种模拟，是一种异步通信方式，信号可以在用户进程和内核之间直接交互，内核可以利用信号来通知用户空间的进程发生了哪些系统事件，信号事件主要有两个来源：
- 硬件来源：用户按键输入Ctrl+C退出、硬件异常如无效的存储访问等；
- 软件终止：终止进程信号、其他进程调用kill函数、软件异常产生信号；
信号可以在任何时候发给某一进程，而无需知道该进程的状态
- 如果该进程当前并未处于执行状态，则该信号由内核保存起来，直到该进程恢复执行并传递给它为止
信号生命周期和处理流程
- 信号被某个进程产生，并设置此信号传递的对象（一般为对应进程的pid），然后传递给操作系统；
- 操作系统根据接收进程的设置（是否阻塞）而选择性的发送给接收者
  - 如果接收者阻塞该信号（且该信号是可以阻塞的），操作系统将暂时保留该信号，而不传递，直到该进程解除了对此信号的阻塞（如果对应进程已经退出，则丢弃此信号）
  - 如果对应进程没有阻塞，操作系统将传递此信号；
- 目的进程接收到此信号后，将根据当前进程对此信号设置的预处理方式，暂时终止当前代码的执行，保护上下文（主要包括临时寄存器数据，当前程序位置以及当前CPU的状态）、转而执行中断服务程序，执行完成后在回复到中断的位置。当然，对于抢占式内核，在中断返回时还将引发新的调度。

套接字

套接字是支持TCP/IP的网络通信的基本操作单元，可以看做是不同主机之间的进程进行双向通信的端点，简单的说就是通信的两方的一种约定，用套接字中的相关函数来完成通信过程。
可以实现跨机器进程通讯
套接字特性由三个属性决定：域、端口号、协议类型
- 域：指定套接字通信中使用的网络介质。
  - AF_INET指Internet网络
  - AF_UNIX指UNIX文件系统，它就是文件输入/输出，地址是文件名
- 端口号：
  - 每一个基于TCP/IP网络通讯的程序(进程)都被赋予了唯一的端口和端口号，端口是一个信息缓冲区，用于保留Socket中的输入/输出信息，端口号是一个16位无符号整数，范围是0-65535，以区别主机上的每一个程序（端口号就像房屋中的房间号），低于256的端口号保留给标准应用程序，比如pop3的端口号就是110，每一个套接字都组合进了IP地址、端口，这样形成的整体就可以区别每一个套接字。
- 协议类型：
  - 流套接字：可靠、有序、面向连接，使用TCP
  - 数据报套接字：不可靠、无序、无连接，使用UDP
  - 原始套接字：允许直接访问底层协议IP或ICMP，常用于网络监听，能够对网络传输机制进行控制
  1. 流套接字只能读取TCP协议的数据
  2. 数据报套接字只能读取UDP协议的数据
  3. 原始套接字可以读写内核没有处理的IP数据包
  因此，如果要访问其他协议发送数据必须使用原始套接字。
套接字通信的建立

3. socket客户端和服务端通信过程

服务器端

（1）首先服务器应用程序用系统调用socket来创建一个套接字，它是系统分配给该服务器进程的类似文件描述符的资源，它不能与其他的进程共享。（2）然后，服务器进程会给套接字起个名字，我们使用系统调用bind来给套接字命名。然后服务器进程就开始等待客户连接到这个套接字。（3）接下来，系统调用listen来创建一个队列并将其用于存放来自客户的进入连接。（4）最后，服务器通过系统调用accept来接受客户的连接。它会创建一个与原有的命名套接不同的新套接字，这个套接字只用于与这个特定客户端进行通信，而命名套接字（即原先的套接字）则被保留下来继续处理来自其他客户的连接（建立客户端和服务端的用于通信的流，进行通信）。

客户端

（1）客户应用程序首先调用socket来创建一个未命名的套接字，然后将服务器的命名套接字作为一个地址来调用connect与服务器建立连接。（2）一旦连接建立，我们就可以像使用底层的文件描述符那样用套接字来实现双向数据的通信（通过流进行数据传输）。

简略步骤

客户端步骤

创建套接字
向服务器发送连接请求（connect）
通信（send/recv)
关闭套接字

服务器端步骤

创建用于监听的套接字（socket）
将套接字绑定到本地地址和端口上（bind）
将套接字设为监听模式（listen）
等待客户请求（accept），此处要不断的调用accept
通信（send/receive），完成后返回4
关闭套接字（close socket）

http通信和socket通信的差异

http连接使用“请求-响应方式”，即在请求时建立连接通道，当客户端向服务器发送请求后，服务端才能向客户端返回数据
socket通信则是在双方建立连接后，可以直接进行数据传输，在连接时可以实现信息的主动推送，无需每次都由客户端向服务器发送请求。

4. 线程通信

线程通信的目的主要是线程同步，所以线程没有像进程通信中的用于数据交换的通信机制。

线程通信方式 (三种)

锁机制

包括: 互斥锁、读写锁、条件变量
- 互斥锁提供了以排他方式防止数据结构被并发修改的方法。
- 读写锁允许多个线程同时读共享数据，而对写操作是互斥的。
- 条件变量可以以原子的方式阻塞进程，直到某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用。

信号量机制

包括无名线程信号量和命名线程信号量

信号机制

类似进程间的信号处理

5. 进程调度算法（6个）

先来先服务、短进程有限、时间片轮转、多级反馈队列、优先级调度算法、高相应比优先调度算法

先来先服务

每次调度都是从就绪队列中选择一个最先进入该队列的进程，为之分配CPU，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。
优缺点：
- 优点：公平，实现简单
- 缺点：平均等待时间长，不利于短作业

短进程优先

从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。
优缺点：
- 优点：平均等待时间短
- 缺点：长进程饥饿

时间片轮转

系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。
当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。
这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。
优缺点：
- 优点：兼顾长短作业
- 缺点：平均等待时间较长，上下文切换较费时。适用于分时系统。

多级反馈队列

设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，第i+1个队列的时间片要比第i个队列的时间片长一倍。
当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n队列便采取按时间片轮转的方式运行。
仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1～(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1～(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即第i队列中某个正在运行的进程的时间片用完后，由调度程序选择优先权较高的队列中的那一个进程，把处理机分配给它。
优缺点：
- 优点：是兼顾长短作业，有较好的响应时间。
- 缺点：不断有新进程到来时，则长进程可能饥饿。

优先级调度算法

非抢占式优先级调度算法

在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。
这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不高的实时系统中。

抢占式优先级调度算法

在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要出现了另一个其优先级更高的进程，进程调度程序就立即停止当前进程的执行，重新将处理机分配给新到的优先权最高的进程。
因此，在采用这种调度算法时，是每当系统中出现一个新的就绪进程i时，就将其优先级Pi与正在执行的进程j的优先级Pj进行比较。如果Pi≤Pj，原进程Pj便继续执行；但如果是Pi>Pj，则立即停止Pj的执行，做进程切换，使i进程投入执行。
抢占式优先级调度算法能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。

高相应比优先调度算法

为每个进程设置动态优先权，并使作业的优先权随着等待时间的增加而提高。保证长作业在等待一定的时间后，必然有机会分配到处理机。
优先权公式：
算法过程
- 设置一个就绪队列；
- 若就绪队列中作业数多于1个且当前有作业使用CPU，则按照优先权公式，对照计算就绪队列中每个作业的优先权，否则直接执行作业；
- 按照优先权数值排序，优先权数值越高，则作业越先被执行；
- 等待当前作业使用完CPU，按照步骤3计算好的队列顺序执行作业；
- 重复步骤3、4直到所有作业执行完毕。

6. 内存置换算法（6个）

局部置换算法 (物理页面数固定)

为每个进程分配一组固定数量的物理块，进程运行时不再改变。若发生缺页，从分配的N个页面中选出一页换出，调入下一页。
- OPT (最佳替换算法)
- LRU (最近最久未使用)
- FIFO (先进先出)
- Clock (时钟置换算法)
- Enhanced Clock (改进的时钟算法) (二次机会法)
- LFU (最不常用算法)
全局置换算法 (逻辑页面数固定)

进程运行时，根据情况增加或减少物理块。发生缺页时，从空闲物理块取出一块分配给该进程，仅当所有物理块都用完时，OS才从内存中选择一页调出。
- 工作集置换算法
- 缺页率置换算法

OPT

选择未来预计访问时间最远的页面进行置换

FIFO

选择在内存中驻留时间最长的页面进行置换
链表实现。
- 系统维护一个链表，记录了所有位于内存当中的逻辑页面。从链表的排列顺序来看，链首页面的驻留时间最长，链尾页面的驻留时间最短。当发生一个缺页中断时，把链表首页面置换掉，并把新的页面添加到链表的末尾。
性能较差，调出的页面有可能是经常要访问的页面，并且有Belady现象。FIFO算法很少单独使用。

LRU

选择最久未使用的页面进行置换
它是对最优页面置换算法的一个近似，其依据是程序的局部性原理，即在最近一小段时间内，如果某些页面被频繁的访问，那么在将来的近一小段时间，它们还可能被频繁访问。反过来说，如果在过去某些页面长时间未被访问，那么在将来它们还可能会长时间的得不到访问。
LRU算法需要记录各个页面使用时间的先后顺序，开销比较大。两种可能实现的方法：
- 系统维护一个页面链表，最近刚刚使用过的页面作为首结点，最久未使用的页面作为尾结点。每一次访问内存时，找到相应的页面，把它从链表中摘下来，再移动到链表之首。每次缺页中断发生时，淘汰链表末尾的页面。
- 设置一个活动页面栈，当访问某页时，将此页号压入栈顶，然后考察栈内是否有与此页面相同的页号，若有则抽出。当需要淘汰一个页面时，总是选择栈底的页面，它就是最久未使用的。

CLOCK

开销和性能都介于FIFO和LRU之间，是LRU的近似。对FIFO的一种改进。
思路：
- 需要用到页表项当中的访问位，当一个页面被装入内存时，把该位初始化为0。然后如果这个页面被访问（读/写），则把该位置为1。
- 把各个页面组织成环形链表（类似时钟表面），把指针指向最老的页面（最先进来）。
- 当发生一个缺页中断时，考察指针所指向的最老页面。若它的访问位为0，立即淘汰；若访问位为1，则把该位置为0，然后指针向下移动一格。如此下去，直到找到被淘汰的页面，然后把指针向下移动一格。
实现：维持一个环形页面链表保存在内存中。

Enhanced Clock

在Clock基础上区分读和写，写为11、读为10
指针修改顺序: 11 -> 10 -> 00，遇到00就置换
修改Clock算法，使它允许脏页总是在一次时钟头扫描中保留下来，同时使用脏位和使用位来指导置换。

LFU

选择累计访问次数最少的页面进行置换
实现方法：对每个页面设置一个访问计数器。每当一个页面被访问时，该页面的访问计数器加一。在发生缺页中断时，淘汰计数值最小的那个页面。
LRU考察的是多久未访问，时间越短越好；

LFU考察的是访问的次数或频度，访问次数越多越好。
问题：一个页面在进程开始时使用的最多，但以后就不使用了，实现费时费力。

解决：定期把次数寄存器右移一位。

Belady现象

Belady现象：在采用FIFO等算法时，有时会出现分配的物理页面数增加，缺页率反而提高的异常现象。
Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的。与置换算法的目标是不一致的（即替换较少使用的页面），因此被它置换出去的页面并不一定是进程不会访问的。

LRU和FIFO比较

LRU算法和FIFO本质上都是先进先出的思路。
只不过LRU是针对页面的最近访问时间来进行排序，所以需要在每一次页面访问的时候动态的调整各个页面之间的先后顺序（有一个页面的最近访问时间变了）；
而FIFO是针对页面进入内存的时间来进行排序。这个时间是固定不变的，所以各页面之间的先后顺序是固定的。如果一个页面在进入内存之后没有被访问，那么它的最近访问时间就是它进入内存的时间。
换句话说，如果内存当中的所有页面都未曾访问过，那么LRU就退化为FIFO算法。

局部/ 全局页面置换算法

7. CPU缓存

CPU缓存（cache）

老CPU有两级缓存L1和L2，新CPU有三级缓存L1、L2和L3
- L1 cache分为Instruction Cache（指令缓存）和Data Cache（数据缓存）
- 对于多核CPU，L1和L2在每个CPU核中，L3由多CPU核共享
- 越接近CPU的cache速度越快，L1快于L2快于L3

cache命中

cache比内存小很多，将内存数据加载到cache中需要决策放在哪一块，这就是cache的映射问题，我们的目标是使用合理的映射手段提高cache命中率。映射的单位为cache line（块）。

直接映射

规则：
- 主存中的一块映射到cache中一个固定的块内
具体：
- 主存与cache分成相同大小的数据块。
- 主存容量应是cache容量的整数倍，将主存空间按cache容量分区，区大小 = cache大小。
- 主存中某区的一块存入缓存时只能存入缓存中块号相同的位置。
缺点：替换操作频繁，命中率比较低。

全相联映射

规则：
- 主存的任意一块可以映射到Cache中的任意一块
具体：
- 主存与缓存分成相同大小的数据块。
- 主存的某一数据块可以装入缓存的任意一块空间中。
- 如果Cache的块数为C，主存的块数为M，则映象关系共有C×M种。
缺点：访问相关存储器时，每次都要与全部内容比较，速度低，成本高，因而应用少。

组相联映射

主存和cache都分组，主存一个组内块数和cache分组数相同，组间直接映射，组内全相联映射
- 即：主存放到cache的哪个组是固定的，存到该组的哪一块是随机的
实际：
- 常采用的组相联结构Cache，每组内有2、4、8、16块，称为2路、4路、8路、16路组相联Cache

CPU访存完整过程

8. 缓存一致性

coolshell.cn/articles/20…

8.1 Cache写方式

Cache写操作方式有两种：

Write through（写通）：
- 每当CPU更新cache内容，就立即更新到内存
- 优点：高一致性
- 缺点：每次CPU写数据，都会导致总线事务，会经常引起总线竞争，效率低下
Write back（写回）：
- CPU修改cache数据后不会立即更新内存，而是等到合适时机再更新

为了保持缓存一致性（多核CPU的核内cache数据一致），CPU又提供了两个操作：

Write invalidate（写失效）：
- 当一个CPU修改了cache数据，如果其他CPU有该数据，则通知其为无效
Write Update（写更新）：
- 当一个CPU修改了数据，如果其他CPU有该数据，则通知其更新数据

写更新会导致大量的更新操作，因此在MESI协议中，采取的是写失效（即MESI中的I：ivalid，如果采用的是写更新，那么就不是MESI协议了，而是MESU协议）。

8.2 MESI协议

单核Cache中每个Cache line有2个标志：dirty和valid标志，它们很好的描述了Cache和Memory(内存)之间的数据关系(数据是否有效，数据是否被修改)
在多核处理器中，多个核会共享一些数据，MESI协议就包含了描述共享的状态。

MESI协议状态

在MESI协议中，每个Cache line有4个状态，可用2个bit表示，它们分别是：

M(Modified)：当前CPU cache拥有最新数据（最新的cache line），其他CPU拥有失效数据（cache line的状态是invalid），虽然当前CPU中的数据和主存是不一致的，但是以当前CPU的数据为准；
E(Exclusive)：只有当前CPU中有数据，其他CPU中没有改数据，当前CPU的数据和主存中的数据是一致的；
S(Shared)：当前CPU和其他CPU中都有共同数据，并且和主存中的数据一致；
I(Invalid)：当前CPU中的数据失效，数据应该从主存中获取，其他CPU中可能有数据也可能无数据，当前CPU中的数据和主存被认为是不一致的；

MESI cache操作

MESI协议中，每个cache的控制器不仅知道自己的操作（local read和local write），每个核心的缓存控制器通过监听也知道其他CPU中cache的操作（remote read和remote write），进而再确定自己cache中共享数据的状态是否需要调整。

Cache操作有四种：

local read（LR）：读本CPU cache中的数据；
local write（LW）：将数据写到本CPU cache；
remote read（RR）：其他CPU cache发生read；
remote write（RW）：其他CPU cache发生write；

Shopee后端面试题整理 - 操作系统篇