操作系统与并发

高地址
+------------------+
|    栈（Stack）     |  向下增长
|        ↓          |
+------------------+
|        ↑          |
|   堆（Heap）       |  向上增长
+------------------+
|   数据段（Data）   |
+------------------+
|   代码段（Text）   |
低地址
+------------------+

线程（Thread）

什么是线程？

线程是进程内的执行单元，是 CPU 调度的基本单位。

线程的特征：

轻量级：线程的创建、切换开销小
共享资源：同一进程内的线程共享进程的地址空间和资源
独立性：每个线程有独立的栈和寄存器

进程 vs 线程

特性	进程	线程
资源分配	资源分配的基本单位	不拥有资源，共享进程资源
调度	进程切换开销大	线程切换开销小
地址空间	独立的地址空间	共享进程的地址空间
通信	需要 IPC 机制	可以直接读写共享变量
健壮性	一个进程崩溃不影响其他进程	一个线程崩溃可能导致整个进程崩溃
创建开销	大（需要分配独立内存空间）	小（共享内存空间）

用户线程 vs 内核线程

用户线程（User Thread）：

由用户空间的线程库管理
内核不知道用户线程的存在
优点：切换开销小，不占用内核资源
缺点：一个线程阻塞会阻塞整个进程，无法利用多核

内核线程（Kernel Thread）：

由内核管理和调度
内核直接调度线程
优点：一个线程阻塞不影响其他线程，可以利用多核
缺点：切换开销较大

线程模型

一对一模型：每个用户线程对应一个内核线程（Linux、Windows）
多对一模型：多个用户线程对应一个内核线程
多对多模型：多个用户线程对应多个内核线程

进程状态和调度

进程状态

五状态模型

新建（New）：进程正在被创建
就绪（Ready）：进程已准备好运行，等待 CPU
运行（Running）：进程正在 CPU 上执行
阻塞（Blocked）：进程等待某个事件（I/O 完成、信号等）
终止（Terminated）：进程执行完毕或被终止

新建 → 就绪 → 运行 → 终止
            ↑    ↓
            └──阻塞

进程状态转换

就绪 → 运行：进程被调度器选中，获得 CPU
运行 → 就绪：时间片用完或被更高优先级进程抢占
运行 → 阻塞：等待 I/O 或其他事件
阻塞 → 就绪：等待的事件发生

进程调度

调度算法

1. 先来先服务（FCFS, First Come First Served）

按照进程到达的顺序调度
优点：简单、公平
缺点：短作业可能等待长时间（护航效应）

2. 最短作业优先（SJF, Shortest Job First）

优先调度执行时间最短的进程
优点：平均等待时间最短
缺点：可能导致长作业饥饿

3. 最短剩余时间优先（SRTF, Shortest Remaining Time First）

SJF 的可抢占版本
当新进程到达时，如果其剩余时间更短，则抢占 CPU

4. 优先级调度（Priority Scheduling）

根据优先级调度进程
可能出现优先级反转问题

5. 轮转调度（RR, Round Robin）

每个进程分配一个时间片，时间片用完后切换
优点：响应时间好，公平
缺点：时间片设置影响性能

6. 多级队列调度（Multilevel Queue）

将进程分成多个队列，不同队列使用不同调度算法
例如：前台进程（交互式）使用 RR，后台进程（批处理）使用 FCFS

7. 多级反馈队列（Multilevel Feedback Queue）

多级队列的改进，进程可以在队列间移动
动态调整进程优先级

Linux 调度器

CFS（Completely Fair Scheduler）：

Linux 2.6.23+ 的默认调度器
使用红黑树维护进程队列
根据虚拟运行时间（vruntime）调度
保证所有进程公平获得 CPU 时间

调度策略：

SCHED_NORMAL：普通进程，使用 CFS
SCHED_FIFO：实时进程，先进先出
SCHED_RR：实时进程，时间片轮转

内存管理

内存管理概述

内存管理是操作系统的重要功能，负责：

内存分配和回收
地址转换
内存保护
虚拟内存管理

内存分配方式

1. 连续内存分配

固定分区：

内存分为固定大小的分区
优点：简单
缺点：内存利用率低，内部碎片

动态分区：

按需分配不同大小的分区
分配算法：首次适应、最佳适应、最坏适应
缺点：外部碎片

2. 非连续内存分配

分段（Segmentation）：

将程序分成逻辑段（代码段、数据段、栈段等）
每个段有独立的基址和长度
地址 = 段号 + 段内偏移

分页（Paging）：

将物理内存和虚拟内存分成固定大小的页
页表存储虚拟页到物理页的映射
地址 = 页号 + 页内偏移

虚拟内存（Virtual Memory）

什么是虚拟内存？

虚拟内存是操作系统提供的一种内存管理技术，让每个进程都拥有独立的虚拟地址空间。

虚拟内存的作用：

内存扩展：允许程序使用超过物理内存大小的内存空间
内存保护：每个进程的地址空间相互隔离
内存共享：多个进程可以共享同一个物理页（如代码段）
简化内存管理：程序员不需要关心物理内存布局

虚拟内存实现

虚拟地址空间：

32位系统：0 ~ 2^32 - 1 (4GB)
64位系统：0 ~ 2^64 - 1 (非常大的空间)

页表（Page Table）：

存储虚拟页号到物理页号的映射
包含页框号、有效位、保护位、修改位、访问位等

地址转换过程：

虚拟地址 → 页表查找 → 物理地址

TLB（Translation Lookaside Buffer）：

页表的高速缓存
减少页表查找的次数
CPU 先在 TLB 中查找，未命中才访问页表

页面置换算法

当物理内存不足时，需要将一些页面换出到磁盘。

1. 最佳置换（OPT, Optimal）

置换未来最长时间不会被访问的页面
理论最优，但无法实现（需要预知未来）

2. 先进先出（FIFO）

置换最早进入内存的页面
简单，但可能淘汰常用页面

3. 最近最少使用（LRU, Least Recently Used）

置换最近最长时间未被访问的页面
性能较好，但实现复杂

4. 时钟算法（Clock）

LRU 的近似算法
使用访问位，性能接近 LRU，实现简单

5. 最近未使用（NRU, Not Recently Used）

根据访问位和修改位选择置换页面
优先级：未访问未修改 > 未访问已修改 > 已访问未修改 > 已访问已修改

分段（Segmentation）

段表：

存储段号到物理地址的映射
包含段基址、段长度、保护位等

地址转换：

逻辑地址 = 段号 + 段内偏移
物理地址 = 段基址 + 段内偏移

分段的优缺点：

优点：符合程序的逻辑结构，便于共享和保护
缺点：可能产生外部碎片，段的大小不固定

段页式存储

结合分段和分页的优点：

先将程序分段（逻辑分段）
再将每段分页（物理分页）

地址转换：

逻辑地址 → 段号 + 段内地址
         → 段表查找 → 段基址 + 段内地址（变为虚拟地址）
         → 页表查找 → 物理地址

内存保护

内存保护机制

地址空间隔离：每个进程有独立的地址空间
访问权限控制：读、写、执行权限
基址-限界寄存器：限制进程访问的内存范围
页表保护位：每页设置读/写/执行权限

并发与锁

并发（Concurrency）

并发是指多个任务在同一时间段内执行（不一定是同时执行，可能交替执行）。

并发 vs 并行：

并发：多个任务在同一时间段内执行（单核 CPU 通过时间片切换实现）
并行：多个任务真正同时执行（需要多核 CPU）

临界区（Critical Section）

临界区是访问共享资源的代码段，同一时刻只能有一个线程/进程进入。

临界区需要满足的条件：

互斥（Mutual Exclusion）：同一时刻只有一个线程能进入
前进（Progress）：如果没有线程在临界区内，应该有线程能够进入
有限等待（Bounded Waiting）：等待进入临界区的时间是有限的

互斥锁（Mutex）

什么是互斥锁？

互斥锁（Mutual Exclusion Lock）是一种同步原语，用于保护临界区，确保同一时刻只有一个线程能访问共享资源。

互斥锁的特点：

上锁和解锁必须由同一线程完成
如果锁已被占用，其他线程会阻塞等待
保护临界区，防止竞态条件

互斥锁的实现：

1. 软件方法：

# Peterson 算法（双进程）
flag[0] = True
turn = 1
while flag[1] and turn == 1:
    pass
# 临界区
flag[0] = False

2. 硬件方法：

测试并设置（Test-and-Set）：原子操作
交换（Swap）：原子交换
自旋锁（Spinlock）：忙等待的互斥锁

3. 操作系统支持：

信号量（Semaphore）：更通用的同步机制
互斥锁（Mutex）：二值信号量的特例

Python 中的互斥锁

import threading

# 创建互斥锁
mutex = threading.Lock()

def critical_section():
    mutex.acquire()  # 上锁
    try:
        # 临界区代码
        pass
    finally:
        mutex.release()  # 释放锁

# 使用 with 语句（推荐）
def critical_section_with():
    with mutex:
        # 临界区代码
        pass

读写锁（Read-Write Lock）

什么是读写锁？

读写锁允许多个读者同时访问资源，但同一时刻只允许一个写者访问。

读写锁的规则：

多个读者可以同时持有读锁
写者独占资源，与读者和其他写者互斥
适合读多写少的场景

读写锁的实现：

import threading

class ReadWriteLock:
    def __init__(self):
        self._read_ready = threading.Condition(threading.Lock())
        self._readers = 0
    
    def acquire_read(self):
        with self._read_ready:
            self._readers += 1
    
    def release_read(self):
        with self._read_ready:
            self._readers -= 1
            if self._readers == 0:
                self._read_ready.notifyAll()
    
    def acquire_write(self):
        self._read_ready.acquire()
        while self._readers > 0:
            self._read_ready.wait()
    
    def release_write(self):
        self._read_ready.release()

读写锁 vs 互斥锁：

互斥锁：读者和写者都互斥，性能较低
读写锁：读者之间不互斥，读多写少时性能更好

自旋锁（Spinlock）

什么是自旋锁？

自旋锁是一种忙等待的锁，线程在获取锁失败时会一直循环检查锁的状态，而不是阻塞。

自旋锁的特点：

不进入睡眠状态，不会发生上下文切换
适合锁持有时间短的场景
在多核 CPU 上有效，单核 CPU 上可能导致浪费 CPU

自旋锁的实现：

import threading

class Spinlock:
    def __init__(self):
        self._locked = False
    
    def acquire(self):
        while True:
            if not self._locked:
                self._locked = True
                return
            # 自旋等待
    
    def release(self):
        self._locked = False

自旋锁 vs 互斥锁：

自旋锁：忙等待，适合锁持有时间短（微秒级），不进入睡眠，无上下文切换
互斥锁：阻塞等待，适合锁持有时间长，会进入睡眠，有上下文切换

信号量（Semaphore）

什么是信号量？

信号量是一种更通用的同步机制，可以控制同时访问资源的线程数量。

信号量的操作：

P 操作（wait/down）：信号量减 1，如果为 0 则阻塞
V 操作（signal/up）：信号量加 1，唤醒一个等待的线程

信号量的类型：

二值信号量：值只能为 0 或 1，等价于互斥锁
计数信号量：值可以为任意非负整数

Python 中的信号量：

import threading

# 创建信号量，允许最多 5 个线程同时访问
semaphore = threading.Semaphore(5)

def access_resource():
    semaphore.acquire()
    try:
        # 访问共享资源
        pass
    finally:
        semaphore.release()

条件变量（Condition Variable）

条件变量用于线程间的协调，允许线程等待某个条件满足。

import threading

condition = threading.Condition()
shared_resource = []

def producer():
    with condition:
        shared_resource.append("item")
        condition.notify()  # 通知等待的线程

def consumer():
    with condition:
        while not shared_resource:
            condition.wait()  # 等待条件满足
        item = shared_resource.pop()

死锁

什么是死锁？

死锁（Deadlock）是指两个或多个进程/线程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。

死锁的四个必要条件

死锁发生的四个必要条件（同时满足才会发生死锁）：

互斥条件（Mutual Exclusion）
- 资源不能被多个进程同时使用
- 同一时刻只能有一个进程使用资源
请求和保持（Hold and Wait）
- 进程持有资源的同时请求其他资源
- 不会释放已持有的资源
不可抢占（No Preemption）
- 资源不能被强制剥夺
- 只能由持有资源的进程主动释放
循环等待（Circular Wait）
- 存在一个进程资源的循环等待链
- 每个进程都在等待下一个进程持有的资源

死锁示例

import threading

# 两个资源
resource_a = threading.Lock()
resource_b = threading.Lock()

def thread1():
    resource_a.acquire()
    print("Thread 1: Acquired A")
    # 模拟一些处理
    import time
    time.sleep(0.1)
    resource_b.acquire()  # 等待 B
    print("Thread 1: Acquired B")
    resource_b.release()
    resource_a.release()

def thread2():
    resource_b.acquire()
    print("Thread 2: Acquired B")
    import time
    time.sleep(0.1)
    resource_a.acquire()  # 等待 A（可能导致死锁）
    print("Thread 2: Acquired A")
    resource_a.release()
    resource_b.release()

# 运行可能导致死锁
t1 = threading.Thread(target=thread1)
t2 = threading.Thread(target=thread2)
t1.start()
t2.start()

死锁的预防

通过破坏死锁的四个必要条件之一来预防死锁：

1. 破坏互斥条件

让资源可共享（不总是可行，如打印机必须互斥）

2. 破坏请求和保持

一次性申请所有需要的资源
缺点：资源利用率低，可能导致饥饿

3. 破坏不可抢占

允许操作系统抢占资源
实现复杂，可能导致重复执行

4. 破坏循环等待

对资源进行排序，按顺序申请资源
常用方法：资源有序分配法

# 资源有序分配法
# 总是按相同顺序申请资源
def thread_safe():
    # 先申请 A，再申请 B（所有线程都遵循这个顺序）
    resource_a.acquire()
    resource_b.acquire()
    # 使用资源
    resource_b.release()
    resource_a.release()

死锁的避免

银行家算法（Banker’s Algorithm）：

在分配资源前，检查是否会导致死锁
如果会导致死锁，则不分配资源
需要预知每个进程的最大资源需求

安全状态：

存在一个安全序列，使得所有进程都能完成
系统处于安全状态时不会发生死锁

死锁的检测

死锁检测算法：

构建资源分配图
检测是否存在环路
如果存在环路且资源不可满足，则发生死锁

死锁恢复：

进程终止：终止一个或多个死锁进程
资源抢占：从某个进程抢占资源，分配给其他进程

死锁的避免策略

实际应用中的策略：

超时机制：锁获取设置超时时间
锁顺序：统一锁的获取顺序
锁层级：定义锁的层级关系
避免嵌套锁：尽量减少锁的嵌套

import threading
import time

# 使用超时避免死锁
def safe_acquire(lock, timeout=5):
    if lock.acquire(timeout=timeout):
        return True
    else:
        print("Failed to acquire lock within timeout")
        return False

resource_a = threading.Lock()
resource_b = threading.Lock()

def safe_thread1():
    if safe_acquire(resource_a):
        try:
            time.sleep(0.1)
            if safe_acquire(resource_b):
                try:
                    # 使用资源
                    pass
                finally:
                    resource_b.release()
        finally:
            resource_a.release()

竞态条件与线程安全

竞态条件（Race Condition）

什么是竞态条件？

竞态条件是指多个线程/进程同时访问和修改共享资源，导致最终结果依赖于执行顺序的情况。

竞态条件的示例：

import threading

# 共享变量
counter = 0

def increment():
    global counter
    for _ in range(100000):
        counter += 1  # 不是原子操作

# 两个线程同时执行
t1 = threading.Thread(target=increment)
t2 = threading.Thread(target=increment)
t1.start()
t2.start()
t1.join()
t2.join()

print(counter)  # 结果可能小于 200000

原因分析：

counter += 1 实际包含三个步骤：
1. 读取 counter 的值
2. 将值加 1
3. 写回 counter

如果两个线程同时执行：
Thread 1: 读取 counter = 0
Thread 2: 读取 counter = 0
Thread 1: 计算 0 + 1 = 1
Thread 2: 计算 0 + 1 = 1
Thread 1: 写入 counter = 1
Thread 2: 写入 counter = 1

结果：counter = 1（应该是 2）

线程安全（Thread Safety）

什么是线程安全？

线程安全是指多线程环境下，程序能够正确地处理共享资源，不会出现数据不一致的情况。

实现线程安全的方法：

1. 使用锁（Lock）

import threading

counter = 0
lock = threading.Lock()

def increment():
    global counter
    for _ in range(100000):
        with lock:
            counter += 1

2. 使用原子操作

import threading

counter = 0
lock = threading.Lock()

def increment():
    global counter
    for _ in range(100000):
        with lock:
            counter += 1  # 在锁保护下的操作是原子的

3. 使用线程安全的数据结构

from queue import Queue
import threading

# Queue 是线程安全的
queue = Queue()

def producer():
    for i in range(10):
        queue.put(i)

def consumer():
    while not queue.empty():
        item = queue.get()
        print(item)

4. 使用不可变对象

# 不可变对象天然线程安全
import threading

# tuple 是不可变的，线程安全
data = (1, 2, 3)

def read_data():
    print(data)  # 多个线程可以安全地读取

5. 使用局部变量（Thread Local）

import threading

# 每个线程有独立的局部存储
thread_local = threading.local()

def set_value(value):
    thread_local.value = value

def get_value():
    return getattr(thread_local, 'value', None)

常见的线程安全问题

1. 数据竞争（Data Race）

# 不安全的代码
shared_list = []

def append_item(item):
    shared_list.append(item)  # 需要同步

# 安全的代码
import threading
lock = threading.Lock()

def append_item_safe(item):
    with lock:
        shared_list.append(item)

2. 可见性问题（Visibility）

# 变量可能被缓存在 CPU 寄存器中
# 需要内存屏障保证可见性
import threading
import time

flag = False  # 可能不会被其他线程看到

def set_flag():
    global flag
    time.sleep(1)
    flag = True  # 需要 volatile 或同步机制保证可见性

def check_flag():
    while not flag:
        pass
    print("Flag is set")

3. 指令重排序（Reordering）

# 编译器和 CPU 可能重排序指令
# 需要内存屏障防止重排序
x = 0
y = 0

def thread1():
    x = 1
    y = 2  # 可能重排序为在 x = 1 之前执行

def thread2():
    if y == 2:
        assert x == 1  # 可能失败

Python 的 GIL（Global Interpreter Lock）

什么是 GIL？

GIL 是 Python 解释器中的一个全局锁，它确保同一时刻只有一个线程执行 Python 字节码。

GIL 的影响：

CPU 密集型任务：GIL 导致多线程无法充分利用多核 CPU
I/O 密集型任务：GIL 影响较小，因为 I/O 操作会释放 GIL

如何绕过 GIL：

多进程：使用 multiprocessing 模块
C 扩展：在 C 扩展中释放 GIL
使用其他解释器：如 Jython、IronPython（无 GIL）

# 多进程示例
import multiprocessing

def cpu_bound_task(n):
    total = 0
    for i in range(n):
        total += i
    return total

# 多进程可以充分利用多核
with multiprocessing.Pool() as pool:
    results = pool.map(cpu_bound_task, [1000000] * 4)

上下文切换

什么是上下文切换？

上下文切换（Context Switch）是指 CPU 从一个进程/线程切换到另一个进程/线程时，保存当前进程的状态并恢复另一个进程的状态的过程。

上下文切换的过程

1. 保存当前上下文

保存 CPU 寄存器（PC、SP、通用寄存器等）
保存进程状态信息
保存内存管理信息（页表指针等）

2. 选择下一个进程

调度器选择下一个要运行的进程

3. 恢复新进程的上下文

恢复 CPU 寄存器
恢复进程状态
恢复内存管理信息（页表）

4. 切换到新进程

切换页表
切换到新进程的栈
跳转到新进程的指令

上下文切换的开销

上下文切换的成本：

直接开销：
- 保存和恢复寄存器
- 更新页表
- 切换栈指针
- 刷新 TLB（Translation Lookaside Buffer）
间接开销：
- 缓存失效（Cache Miss）
- TLB 失效
- 分支预测失效

典型的上下文切换时间：

微秒级（1-10 微秒）
在频繁切换时，开销可能达到总时间的 10-20%

减少上下文切换的方法

1. 减少线程/进程数量

# 使用线程池而不是创建过多线程
from concurrent.futures import ThreadPoolExecutor

with ThreadPoolExecutor(max_workers=4) as executor:
    # 限制线程数量，减少上下文切换
    futures = [executor.submit(task, i) for i in range(100)]

2. 使用异步 I/O

import asyncio

async def async_task():
    # 异步 I/O 避免线程阻塞和上下文切换
    await asyncio.sleep(1)
    return "result"

async def main():
    results = await asyncio.gather(*[async_task() for _ in range(100)])

3. 使用协程

# 协程是用户态的轻量级线程
# 切换开销远小于线程切换
def coroutine():
    while True:
        value = yield
        print(value)

gen = coroutine()
next(gen)
gen.send(1)  # 协程切换开销很小

4. 优化锁的使用

# 减少锁的持有时间
def optimized_function():
    # 在锁外执行不需要同步的操作
    result = compute_something()
    
    # 只在必要时持有锁
    with lock:
        shared_resource.update(result)

进程切换 vs 线程切换

进程切换：

需要切换页表（内存地址空间）
需要刷新 TLB
开销较大（微秒级）

线程切换：

不需要切换页表（共享地址空间）
不需要刷新 TLB
开销较小（纳秒到微秒级）

常见面试题

1. 进程和线程的区别？

答案：

资源分配：进程是资源分配的基本单位，线程不拥有资源，共享进程资源
调度：进程切换开销大，线程切换开销小
地址空间：进程有独立的地址空间，线程共享进程的地址空间
通信：进程间需要 IPC 机制，线程可以直接读写共享变量
健壮性：进程间相互独立，一个进程崩溃不影响其他进程；线程间相互影响
创建开销：进程创建开销大，线程创建开销小

2. 什么是虚拟内存？有什么作用？

答案：

虚拟内存是操作系统提供的内存管理技术，让每个进程拥有独立的虚拟地址空间
作用：
1. 内存扩展：允许程序使用超过物理内存大小的空间
2. 内存保护：每个进程的地址空间相互隔离
3. 内存共享：多个进程可以共享同一个物理页
4. 简化内存管理：程序员不需要关心物理内存布局

3. 分页和分段的区别？

答案：

特性	分页	分段
大小	固定大小（页）	可变大小（段）
划分方式	物理划分	逻辑划分
地址空间	一维	二维（段号+偏移）
碎片	内部碎片	外部碎片
实现	页表	段表
共享	以页为单位共享	以段为单位共享

4. 死锁的四个必要条件是什么？如何避免死锁？

答案：

四个必要条件：
1. 互斥条件
2. 请求和保持
3. 不可抢占
4. 循环等待
避免死锁的方法：
1. 破坏循环等待：资源有序分配法
2. 破坏请求和保持：一次性申请所有资源
3. 使用超时机制
4. 避免嵌套锁
5. 使用死锁检测和恢复

5. 互斥锁和自旋锁的区别？

答案：

特性	互斥锁	自旋锁
等待方式	阻塞（进入睡眠）	忙等待（自旋）
上下文切换	有	无
适用场景	锁持有时间长	锁持有时间短
CPU 使用	等待时不占用 CPU	等待时占用 CPU
实现复杂度	较高	较低