二、进程与线程

本章导览

共 7 个小节：进程与线程、进程与线程、处理机调度、处理机调度、同步与互斥、同步与互斥、死锁

本章重点

• 进程是资源分配单位、线程是 CPU 调度单位；进程靠 PCB 描述
• 进程五状态：创建、就绪、运行、阻塞、终止；就绪 ↔ 运行 ↔ 阻塞是核心转换
• 三大重点：处理机调度（FCFS/SJF/优先级/RR）、同步互斥（PV 操作）、死锁（银行家算法）

进程与线程

关键点

• 进程是程序的一次执行，是资源分配的基本单位；由 PCB + 程序段 + 数据段组成
• 特征：并发、异步、独立、动态、结构性
• 五状态转换：运行→就绪是时间片到，运行→阻塞是等 I/O（主动），阻塞→就绪是 I/O 完成（被动）

进程与线程

关键点

• 线程是 CPU 调度的基本单位；同进程内线程共享资源、切换开销小
• 实现方式：用户级 ULT（切换快，但一个阻塞则全阻塞）、内核级 KLT（可并行，切换需进核心态）
• 一句话：进程像「资源容器」，线程是「执行流」

进程的概念、组成、特征

关键点

程序：是静态的，就是个存放在磁盘里的可执行文件，如：QQ.exe。 进程：是动态的，是程序的一次执行过程，如：可同时启动多次 QQ 程序 同一个程序多次执行会对应多个进程

进程的状态与转换、进程的组织

进程控制

进程通信

关键点

进程间通信（Inter-Process Communication， IPC）是指两个进程之间产生数据交互。 写进程往管道写数据，即便管道没被写满，只要管道没空，读进程就可以从管道读数据 读进程从管道读数据，即便管道没被读空，只要管道没满，写进程就可以往管道写数据

线程的概念

线程的实现方式 & 多线程模型

线程状态与转换

处理机调度

关键点

• 调度三层次：高级（作业）、中级（内外存对换）、低级（进程，最频繁）
• 进程调度时机：主动放弃（终止 / 阻塞）或被剥夺（时间片到 / 更高优先级到）
• 闲逛进程：无就绪进程时 CPU 运行的兜底进程

处理机调度

关键点

• 调度算法：FCFS（公平、利长作业）、SJF/SRTF（平均等待最短但饿死长作业）、RR（时间片轮转、响应快）、优先级、多级反馈队列 MLFQ（综合最优）
• 评价指标：CPU 利用率、吞吐量、周转时间、等待时间、响应时间
• 时间片是 RR 的关键：太大退化成 FCFS，太小切换开销大

调度的概念、层次

进程调度的时机、切换与过程、方式

调度器 & 闲逛进程

调度算法的评价指标

调度算法

关键点

FCFS 算法是在每次调度的时候选择一个等待时间最长的作业（进程）为其服务。但是没有考虑到作业的运行时间，因此导致了对短作业不友好的问题。 SJF 算法是选择一个执行时间最短的作业为其服务。但是又完全不考虑各个作业的等待时间，因此导致了对长作业不友好的问题，甚至还会造成饥饿问题。 一般来说，设计时间片时

同步与互斥

关键点

• 同步：协调进程执行先后（协作）；互斥：同一资源同时只一个进程用（竞争）
• 互斥软件法：单标志、双标志、Peterson；硬件法：中断屏蔽、TestAndSet、Swap
• 互斥锁：加锁 / 解锁，简单但忙等

同步与互斥

关键点

• 信号量是最通用的同步工具：P（wait） 申请资源减 1、V（signal） 释放加 1
• 可实现互斥（初值 1）、同步（初值 0，前 V 后 P）、前驱关系
• 三大经典问题：生产者-消费者、读者-写者、哲学家进餐；管程是更高级的封装

进程同步 & 进程互斥

进程互斥的软件实现方法

进程互斥的硬件实现方法

互斥锁

信号量机制

用信号量实现进程互斥、同步、前驱关系

进程同步互斥问题

关键点

（1）生产者——消费者问题 （2）多生产者——多消费者问题 （3）吸烟者问题 （4）读者写者问题 （5）哲学家进餐问题

管程

死锁

关键点

• 死锁四个必要条件：互斥、占有并等待、不可剥夺、循环等待（同时成立才死锁）
• 预防：破坏任一必要条件；避免：运行时用银行家算法判断是否进入不安全状态
• 检测与解除：用资源分配图找环，再剥夺 / 撤销进程解除

死锁的概念

预防死锁

避免死锁（银行家算法）

死锁的检测和解除