操作系统原理面试笔记

参考：CAP 理论、Linux 五种 IO 模型

1 分布式锁

CAP 理论：任何一个分布式系统都无法同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition Tolerance），最多只能同时满足两项。

在单进程系统中，多个线程同时改变可变共享变量时，需要通过同步使其线性执行。同步的本质是通过锁来实现：在某处做一个每个线程都能看到的标记，标记不存在时设置它，后续线程发现已存在则等待拥有者释放。

不同地方实现锁的方式不同，只要能满足所有线程看到标记即可：

Java 中 synchronized 是在对象头设置标记；
Lock 接口实现类基本用 volatile int 变量，保证可见性和原子修改；
Linux 内核用互斥量或信号量做标记。

除了内存数据，任何互斥的事物都能做锁，例如流水号+时间做幂等校验、用文件是否存在作为锁。关键是对标记的修改要原子且内存可见。

基于 Redis setnx/get/getset 的分布式锁

getset(key, newValue)：原子的，对 key 设置 newValue 并返回旧值。若 key 不存在，多次执行：第一次返回 null 且 value 变为 value1，第二次返回 value1 且 value 变为 value2……
使用步骤：
1. setnx(lockKey, 当前时间+过期超时时间)，返回 1 则加锁成功；返回 0 转入 2；
2. get(lockKey) 拿锁的过期时间 oldExpireTime，与当前时间比较，小于当前时间则认为已超时，转入 3；
3. 计算 newExpireTime = 当前时间 + 过期超时，执行 getset(lockKey, newExpireTime)，返回当前值 currentExpireTime；
4. 比较 currentExpireTime 与 oldExpireTime 是否相等：相等说明当前 getset 成功，获取到锁；不相等说明锁被其他请求抢走，直接失败或重试；
5. 业务处理完，比较处理时间与锁超时时间：小于超时则 delete 释放锁；大于超时则无需处理。

注意：过期超时必须大于最大业务处理时间，防止处理中锁过期；业务执行完主动 delete 释放，即使 delete 失败也能依赖 TTL 兜底删除。失效时间太短会提前释放导致并发问题，太长其他线程要平白多等。

2 进程、线程、协程

线程与进程的区别

地址空间：线程是进程内的执行单元，进程内至少有一个线程，它们共享进程的地址空间；进程有独立的地址空间；
资源拥有：进程是资源分配和拥有的单位，同一进程内线程共享资源；
调度：线程是处理器调度的基本单位，进程不是；
二者均可并发执行；
每个线程有独立入口、顺序序列和出口，但线程不能独立执行，必须依附于应用程序。

协程与线程的区别

一个线程可以有多个协程，一个进程也可以单独拥有多个协程；
线程/进程是同步机制，协程是异步；
协程能保留上一次调用时的状态，重入时相当于进入上次调用的状态。

进程间通信方式（IPC）

管道 pipe：半双工、只能用于父子/兄弟进程、FIFO 读写、缓冲区有限（一页）、传输无格式字节流。如 ps -ef | grep redis-server；
有名管道 named pipe：半双工，允许无亲缘关系进程通信；
信号量 semaphore：计数器，控制多进程对共享资源访问，常作锁机制。非负整数，只能通过 wait（P）和 signal（V）两个原子操作访问。互斥量值只能 0/1，信号量可为非负整数；互斥量用于互斥（无序访问），信号量用于同步（有序访问）；
消息队列 message queue：内核中的消息链表，克服了信号信息少、管道无格式字节流和缓冲区受限的缺点；支持消息随机查询，不一定要 FIFO；
信号 signal：异步通信，内核可通知用户空间进程发生了系统事件。生命周期：产生→操作系统选择性传递（阻塞则暂存）→进程接收→中断当前代码→执行中断服务→恢复。常见信号：SIGTERM（kill 默认）、SIGINT（Ctrl+C，结束前台进程）、SIGKILL（kill -9，不可捕获）；
共享内存 shared memory：映射一段能被多个进程访问的内存，最快的 IPC 方式，通常配合信号量同步；
套接字 socket：可用于不同机器间的进程通信，TCP/HTTP 都基于 socket。

线程间通信方式

锁机制：互斥锁（排他防止并发修改）、读写锁（多读一写）、条件变量（与互斥锁配合，阻塞直到条件为真）；
信号量；
信号（主要用于同步）。

协程

协程是用户态轻量级线程，调度完全由用户控制，拥有自己的寄存器上下文和栈。切换时保存/恢复上下文，直接操作栈基本无内核切换开销，可无锁访问全局变量，切换非常快。

3 中断处理流程

中断是使 CPU 中止当前程序转去处理特殊事件的操作，引起中断的事件称中断源。硬件中断通过上下文切换保存执行状态；软件中断作为 CPU 指令集指令（如 int 80h）。

分类：内中断（程序运行错误）、外中断（外部设备）、软件中断；可屏蔽中断 / 不可屏蔽中断（如电源掉电）。

处理过程：请求中断 → 中断响应 → 关闭中断（保存 FR/EFR，清 IF）→ 保护断点（压栈 CS/IP）→ 中断源识别 → 保护现场（PUSH 寄存器）→ 中断服务 → 恢复现场（POP）→ 中断返回（IRET 弹出 IP/CS 和 FR）。

中断 vs 异常：中断是异步的、由外部设备产生；异常是同步的、由执行当前指令引起。异常分为故障（fault，可恢复返回到当前指令）、陷阱（trap，有意识安排返回到下一条指令）、终止（abort，不可恢复）。int 80h 系统调用对 CPU 来说属于同步事件，是异常范畴，不会被屏蔽。

4 动态链接库与静态链接库

动态链接库（.so）：链接延迟到运行期（runtime），初始化时间短但运行期性能略差；多个程序共享，升级方便；
静态链接库（.a）：编译期（compile time）链接，所有相关对象文件合入可执行文件；装载快、执行快，但程序大、多个程序使用会重复装载浪费内存，库变了需重新编译；
差异：链接阶段不同（编译期 vs 运行期）；运行是否需要依赖库文件；静态库不能再包含其他库，动态库可以；静态库导出声明和实现都放一起，动态库只是实现的导出声明。

5 可执行文件是怎么得到的

源码 -> 预处理 -> 编译 -> 汇编 -> 链接 -> 可执行文件

6 并行与并发的区别

并发：一个处理器同时处理多个任务，逻辑上的同时发生；
并行：多个处理器或多核同时处理多个任务，物理上的同时发生。

比喻：一个人同时吃三个馒头（并发）vs 三个人同时吃三个馒头（并行）。单核内线程交替运行不提高效率，多核并行才真正解决运行效率问题。

7 乐观锁与悲观锁

悲观锁：总是假设最坏情况，每次拿数据都上锁，别人阻塞直到拿锁。数据库行锁/表锁、Java synchronized 和 ReentrantLock 都是悲观锁；
乐观锁：总是假设最好情况，不上锁，但更新时判断期间别人是否更新过。用版本号机制或 CAS 算法实现。适用于多读场景提高吞吐量；多写场景冲突多、retry 多，用悲观锁合适。

乐观锁实现方式一：版本号机制

数据表加 version 字段表示修改次数。线程 A 读数据同时读 version，提交更新时若当前 version 等于数据库 version 才更新，否则重试。避免用基于旧版本数据覆盖别人的修改。

乐观锁实现方式二：CAS 算法

即 compare and swap。涉及三个操作数：内存值 V、比较值 A、拟写入新值 B。当且仅当 V == A 时原子地用 B 更新 V，否则不操作。一般是自旋操作（不断重试）。

乐观锁的缺点

ABA 问题：变量从 A 被改成 B 又改回 A，CAS 误认为没被修改。JDK 1.5 的 AtomicStampedReference 通过compareAndSet 检查引用和标志解决；
循环时间长开销大：自旋长时间不成功吃 CPU，可用 pause 指令优化；
只能保证一个共享变量的原子操作：跨多个共享变量时 CAS 无效，可把多个变量放进一个对象用 AtomicReference 操作。

8 mmap 内存映射

mmap 把文件或其他对象映射到进程地址空间，实现文件磁盘地址和进程虚拟地址的一一对应。之后进程用指针方式操作这段内存，系统自动回写脏页到磁盘，无需再调用 read/write。内核对该区域的修改直接反映到用户空间，可实现不同进程间的文件共享。

9 可重入 vs 线程安全

可重入（reentrant）：单个线程执行过程中可以再次进入该子程序仍得到正确结果，强调重新进入同一子程序安全；
线程安全：多线程并发访问函数仍正确，只关心实现。
可重入影响函数外部接口（需数据由调用者提供），线程安全只需改实现（加同步）；
可重入函数未必线程安全（如可重入地读文件但不加锁，别的线程可能同时在改文件）；线程安全函数未必可重入（如锁了共享资源的函数，实例被中断再进入会饥饿/死锁，fprintf 就是线程安全但不可重入）。

10 幂等

幂等性（idempotent）：相同请求执行 N>0 次产生的副作用与执行一次相同。HTTP 中 GET、HEAD、PUT、DELETE 等方法幂等（正确实现下），POST 不幂等；所有 safe 方法都是幂等的。

阅读 — · 全站 —