操作系统核心概念笔记：进程、线程、调度、同步与死锁

一、进程（Process）

1. 什么是进程？

• 进程：程序运行时，将相关数据打包成的管理单元。是操作系统分配资源的最小单位。

• 进程的组成：

  • 代码段：存放程序代码。
  • 数据段：存放全局变量和常量。
  • 栈（Stack）：像一叠盘子，后进先出。用于存放局部变量、函数参数、返回地址等。
  • 堆（Heap）：像一堆盘子，是一大块内存空间，通常存放程序实例对象等动态分配的数据。
  • 进程控制块（PCB）：登记管理进程的表，记录进程ID、运行状态、CPU现场信息等。PCB的创建意味着进程的创建。

2. 进程的五种状态

状态	说明
创建态	PCB已创建，正在分配内存等资源
就绪态	资源已分配好，等待被调度系统选中
运行态	正在使用CPU执行（单核下同时只有一个）
阻塞态	等待某个IO资源（如打印机），主动放弃CPU
终止态	正常结束、异常退出或被强制终止

3. 进程的组织方式

• 链接方式：每个PCB记录下一个PCB的内存地址，像手拉手一样（链表）。插入/删除进程方便。
• 索引方式：使用索引表记录PCB指针，像书的目录页。

4. 进程的特性

• 并发性：多个进程交替使用CPU，交叉执行。
• 异步性：进程的先后顺序不再确定。
• 并行：多核CPU下，多个进程可以同时执行（真正的并行）。

---

二、线程（Thread）

1. 为什么需要线程？

• 问题：程序顺序执行时，遇到IO操作（输入/输出操作，程序与计算机外部设备（或外部世界）进行数据交换的过程）会让CPU空闲，利用率不高。
• 解决：把程序”切碎”，将需要使用IO的片段分成”申请-执行-释放”三个阶段，调整顺序，让CPU在等待IO时去执行其他指令。

2. 用户级线程 vs 内核级线程

类型	特点	缺点
用户级线程	仅调整指令执行顺序，本质同属一个进程，由用户程序自己调度	所有线程分配到同一个CPU核心，无法利用多核
内核级线程	由操作系统内核直接调度管理，可分发到不同CPU核心并行执行	开销较大

3. 线程与进程的关系

• 进程：操作系统分配资源的最小单位（拥有独立的地址空间、文件句柄等）。
• 线程：CPU调度的最小单位（共享进程的资源）。
• 线程控制块（TCB）：登记线程信息的表，包含进程ID、线程ID、调度状态等，与PCB非常相似。

---

三、处理器调度策略

1. 基本调度算法

算法	核心思想	缺点
先到先服务（FCFS）	按先后顺序排队，依次使用CPU	前面的任务耗时太久，后面全部等待
最短作业优先（SJF）	让耗时短的任务排在前面	不断有短作业插入时，长作业会饥饿
最短剩余时间优先（SRTN）	抢占式的最短作业优先，比的是剩余时间	同样可能导致饥饿

抢占式和非抢占式

当一个新的线程到来时，把CPU上的线程拉下来，重新决策，重新决定谁使用CPU，这就是抢占式。 当一个新的线程到来时，CPU继续处理手头的任务，手头的线程处理完了再决定下一个谁来，这就是非抢占式。

2. 解决饥饿问题的策略

• 最高响应比优先（HRRN）：
  • 公式：响应比 = 1 + 等待时间 / 预估运行时间
  • 等待越久或预估时间越短，响应比越高，优先执行。
• 时间片轮转（RR）：每个线程限定使用CPU的时间，超时则强行拉下来排到队尾，循环执行。无饥饿问题。
• 优先级调度：给作业分配不同优先级，优先级高的先执行。可能导致低优先级饥饿。
  • 解决方案：引入动态优先级，运行期间动态调整。

3. 多级反馈队列（MLFQ）—— 综合最优

• 设计：将作业分成多个等级队列（如实时、分时、批处理），等级越高优先执行。
• 动态调整：
  • 时间片用完 → 移动到更低级队列（说明耗时超过该等级时间片）
  • 时间片没用完就让出CPU → 移动到更高级队列（说明耗时比当前队列短）
• 特点：高等级队列时间片较小，适合交互式任务快速响应；低等级队列时间片较大。

4. 多处理器调度

• 目标：

  • 负载均衡：防止有人忙碌、有人空闲。
  • 缓存亲和性：尽量让线程在上次运行的同一个CPU上运行，提高Cache命中率
  • 减少同步开销：减少核心之间的锁竞争、缓存一致性的开销
  • 扩展性：处理器数量增加N倍，系统吞吐量也应增加N倍。

• 策略：

  • 对称多处理（SMP）：所有的CPU核心共享同一个队列，结合单处理器调度策略，将作业平均分配到不同的CPU核心上。这样的分配方式是需要锁机制来避免争抢，而锁机制则是该策略的性能瓶颈。

  • 私有就绪队列：每个CPU有自己的任务队列，调度器定期从繁忙队列迁移任务到空闲队列，或让空闲CPU主动”偷”任务。

问：一个进程被分配到不同的核心会导致Cache失效，怎么避免呢？

可以采用软亲和的方式提高缓存亲和性。

软亲和是尽力而为,但不强求。 调度器会尽量让一个线程回到它之前运行过的核心上,但如果那个核心太忙,或者为了系统的整体负载均衡,调度器也可以把它安排到其他核心上

硬亲和是锁定核心,强制绑定。 通过系统调用,明确指定一个线程只允许在某个或某几个特定的CPU核心上运行。

---

四、进程/线程同步与互斥

1. 基本概念

• 临界资源：需要争抢的资源。
• 临界区：使用临界资源的代码。
• 互斥：两个进程争抢同一个资源时，只能有一个进入临界区。

2. 软件实现互斥的演进

方法	核心思想	存在的问题
单标志法	定义一个标志，掰到左边归A，右边归B，交替使用	如果一方一直不用，另一方永远进不去
双标志先检查法	先检查对方标志，若对方没在用，则设置自己的标志为”在用”	两个线程同时检查到对方没在用，同时设置标志，同时进入
双标志后检查法	先设置自己的标志为”在用”，再检查对方标志	两个线程同时设置标志，同时检查到对方在用，同时返回等待
Peterson算法	双标志后检查法 + 单标志法组合，增加竞争标志	只能解决两个线程的互斥，扩展到N个线程逻辑复杂
面包店算法	先取号（正在取号时其他人等待），再比号（号小的优先），号码相同比线程ID	实现了N个线程互斥，但实现较复杂

3. 硬件实现互斥

• 中断屏蔽：进入临界区前关闭中断，防止被切换。但会导致单进程状态，性能差。
• 原子指令（如X86的exchange、compare-and-swap）：
  • 硬件层面实现一条指令完成”读-改-写”操作，中间不会被插队。
  • 悲观锁（Test-and-Set）：先上锁后操作，失败则循环等待（自旋）。
  • 乐观锁（Compare-and-Swap）：不上锁，写入时比对版本号，一致则写入成功，不一致则重试。

4. 信号量（Semaphore）

• 定义：一种数据结构，包含计数器（表示资源数量）和等待队列（存放休眠进程）。

• 操作：

  • P操作（借资源）：计数器减1。若结果<0，则进程进入等待队列。
  • V操作（还资源）：计数器加1。若结果≤0，则从等待队列中唤醒一个进程。

• 优点：优雅地处理线程互斥和同步问题。

5. 经典同步问题

生产者-消费者问题

• 场景：一个缓冲区，生产者写数据，消费者读数据。
• 约束：不能同时读写、不能同时写、缓冲区满时生产者等、缓冲区空时消费者等。
• 解决方案：使用三个信号量
  • empty = 缓冲区大小（空位数）
  • full = 0（满位数）
  • mutex = 1（读写互斥锁）

读者-写者问题

• 场景：一个存储空间，可读可写。
• 约束：允许多个读者同时读、不允许同时读写、不允许同时写。
• 解决方案：定义读写锁信号量，第一个读者上锁，后续读者跟风（不上锁），最后一个读者解锁；写者必须单独上锁。

---

五、死锁（Deadlock）

1. 什么是死锁？

多个进程循环等待对方持有的资源，导致所有进程都无法继续执行。

2. 死锁发生的四个必要条件（缺一不可）

条件	说明	破坏方法
互斥	只有互相抢资源的进程才可能死锁	使用spooling技术将争抢变为异步队列（但场景很少）
占有且等待	拿了一个资源后，又等待另一个资源	打包分配：要么一起获得，要么一个都拿不到（但资源利用率低）
不可抢占	进程拿到资源后，只要不放手，就一直占着	强行剥夺持有资源太久的进程（但会增加复杂度）
循环等待	形成A等B、B等A的循环链	规定资源申请顺序

3. 死锁避免：银行家算法

• 核心思想：在资源分配前进行安全性检查，判断能否找到一种让所有进程都顺利完成的序列。
• 原理：
  • 每个线程声明总共需要多少资源。
  • 当线程申请更多资源时，先”假装分配”，检查系统是否处于安全状态。
  • 若存在安全序列（所有线程都能依次执行完并释放资源），则同意申请；否则拒绝。

---

六、进程间通信（IPC）

通信方式	说明
共享内存	将同一块物理内存映射到不同进程的虚拟地址空间，进程直接读写（最快）
管道	内存中开辟固定大小缓冲区，半双工（数据单向流动），一边写入一边读出
直接通信	发送者和接收者明确知道对方，通过内核消息队列传递消息（像写信）
间接通信	把消息寄到”代收点”（共享数据结构），需要的人自取
信号	用于通知接收进程某个事件已发生（如Ctrl+C），只传递数字信号，不传复杂数据

---

参考视频

操作系统-进程-透视版