【总结】第二章:进程与线程

考研提示:本章是操作系统最重头的一章,每年必考,且必有大题。重点掌握:进程状态转换图、CPU调度算法计算、信号量PV操作写代码、死锁银行家算法。


一、进程基础

1.1 进程 vs 程序

对比项程序进程
本质静态代码文件动态执行过程
资源不占用占CPU/内存/文件等资源
数量关系一个程序可对应多个进程一个进程只对应一段程序
标识文件名PID + PCB

进程控制块(PCB):进程存在的唯一标志,内核区存储。包含:PID、进程状态、寄存器值、内存地址、优先级、I/O信息等。

1.2 进程五状态转换(必须会画!)

             ①创建完成
                 ↓
            【新建态】
                 │ ②OS允许
                 ↓
  ⑥事件发生 ←← 【就绪态】 ←←←←←← ⑤时间片到/被抢占
  (I/O完成)       │  ↑                    ↑
                 ③被调度  ⑤              ⑤
                 ↓                       │
            【运行态】 →→→→→→→→→→→→→→→→→→→┘
                 │
            ④等待事件(I/O请求/等信号量)
                 ↓
            【阻塞态】
                 │ ⑦结束
                 ↓
            【终止态】

关键转换规则:

  • 运行→阻塞:进程主动等待(只能由运行态主动发起)
  • 阻塞→就绪:等待的事件发生(被动唤醒)
  • ⚠️ 阻塞不能直接变运行! 必须先经过就绪态

1.3 虚拟地址空间各区域

区域存放内容典型变量
内核区PCB、内核代码OS维护,用户不可直接访问
用户栈局部变量、函数形参、返回地址int length;(函数内)
运行时堆动态分配内存(向上增长)malloc()申请的空间
可读写数据段全局变量、静态变量char *ptr;(函数外)、static int cnt;
只读代码段机器指令、字面常量函数体编译后的二进制、"hello"

口诀:指针变量本身看定义位置,malloc申请的内存永远在堆。


二、线程

2.1 线程 vs 进程

对比项进程线程
资源资源分配基本单位共享进程资源,不独立拥有
调度传统OS调度单位现代OS的调度基本单位
开销创建/切换/通信开销大开销小
隔离性地址空间相互独立同进程线程共享地址空间

线程私有:线程ID、PC寄存器、栈(局部变量) 线程共享:代码段、数据段、堆、打开的文件

2.2 用户级线程 vs 内核级线程

用户级线程(ULT)内核级线程(KLT)
OS是否感知不感知感知,内核管理
切换开销小(不入内核)大(需内核介入)
一个线程阻塞整个进程阻塞其他线程可继续运行
多核利用不能并行可以并行

三、进程间通信(IPC)

方式原理速度特点
共享内存多进程映射同一物理内存最快需配合信号量同步
消息传递send/receive原语传消息中等有直接/间接(邮箱)两种
管道字节流,单向,先进先出中等无名管道(亲缘进程),有名管道(任意进程)
信号OS发异步通知快(但只传数字)不能传数据内容

四、CPU调度

4.1 三级调度

名称作用频率
高级调度(作业调度)作业从磁盘→内存(新建→就绪)最低
中级调度(内存调度)进程挂起/激活中
低级调度(进程调度)就绪队列→CPU最高,408重点

4.2 调度评价指标与公式

其中:=进程数,完成时间=进程结束时刻,到达时间=进程进就绪队列时刻,运行时间=实际需要在CPU上的时间

4.3 调度算法对比

算法规则是否抢占优点缺点
FCFS先来先服务否简单公平长进程优先,短进程等待久
SJF运行时间最短优先否(SRTF是抢占版)平均等待时间最短长进程饥饿
优先级优先级高者先可选灵活低优先级进程饥饿(老化解决)
RR(轮转)时间片轮流是公平,响应好时间片选择关键
多级反馈队列多队列,新进程高优先级,超时降级是综合最优实现复杂

RR时间片大小:太大→退化为FCFS;太小→切换开销占主导,效率下降

调度时机:进程主动放弃CPU、时间片用完、更高优先级进程到达(仅抢占式);临界区内/中断处理中不应调度


五、同步与互斥(最重要!)

5.1 基本概念

  • 临界资源:每次只允许一个进程访问的资源
  • 临界区:访问临界资源的那段代码
  • 互斥:同一时刻只有一个进程在临界区
  • 同步:进程间有先后执行顺序的约束

临界区四原则:空闲让进、忙则等待、有限等待、让权等待

5.2 信号量(Semaphore)

信号量S是一个整数,只能通过原子操作P/V修改:

P操作(申请资源):

P(S): S--; if(S < 0) block(S.L);  // S<0则阻塞,挂入等待队列

V操作(释放资源):

V(S): S++; if(S <= 0) wakeup(S.L); // S<=0说明有进程在等,唤醒一个

信号量值的含义:

使用规范:

  • 互斥信号量:初值=1,用于保护临界区,在同一进程内成对P...V
  • 同步信号量:初值=0,用于表示”事件未发生”,P和V分布在两个不同进程

5.3 三大经典同步问题(大题必考!)

① 生产者-消费者(缓冲区大小N)

semaphore mutex = 1;  // 互斥:保护缓冲区
semaphore empty = N;  // 同步:空缓冲区数量
semaphore full  = 0;  // 同步:满缓冲区数量
 
生产者:
    P(empty);     // ①先申请空位(若为0则等待)
    P(mutex);     // ②再申请互斥锁
    放入数据;
    V(mutex);     // ③先释放互斥锁
    V(full);      // ④再通知消费者
 
消费者:
    P(full);      // ①先申请产品(若为0则等待)
    P(mutex);     // ②再申请互斥锁
    取出数据;
    V(mutex);     // ③先释放互斥锁
    V(empty);     // ④再通知生产者

⚠️ 铁律:P(同步信号量) 必须在 P(互斥信号量) 之前!否则死锁!

② 读者-写者(读者优先)

semaphore rw = 1;      // 互斥:保护写操作
semaphore mutex = 1;   // 互斥:保护readCount
int readCount = 0;     // 当前读者数量
 
读者:
    P(mutex);
    readCount++;
    if(readCount == 1) P(rw);  // 第一个读者阻止写者
    V(mutex);
    读数据;
    P(mutex);
    readCount--;
    if(readCount == 0) V(rw);  // 最后一个读者放行写者
    V(mutex);
 
写者:
    P(rw);
    写数据;
    V(rw);

③ 哲学家进餐(5人5筷,防死锁)

方案:加互斥锁,一次性拿起两根:

semaphore mutex = 1;           // 拿筷子的动作互斥
semaphore chopstick[5]={1,1,1,1,1};
 
哲学家i:
    P(mutex);                  // 原子性拿两根
    P(chopstick[i]);
    P(chopstick[(i+1)%5]);
    V(mutex);
    吃饭;
    V(chopstick[i]);
    V(chopstick[(i+1)%5]);

多类产品变体(2009统考):奇数/偶数消费者,需将full拆为odd=0和even=0两个信号量,不能合并!


六、死锁

6.1 四个必要条件(记”互持不循”)

条件含义
互斥资源不可共享
持有并等待拿着资源还在等别的资源
不可抢占资源不能被强制剥夺
循环等待进程链形成等待环

四个条件是必要条件,不是充分条件(满足四个未必死锁)

6.2 处理策略

策略思路方法
预防破坏四个条件之一一次性申请所有资源(破持有等待);资源按序编号(破循环等待)
避免动态判断安全再分配银行家算法
检测+解除允许死锁,发现后处理资源分配图化简;终止进程或抢占资源

6.3 银行家算法(必考计算!)

数据结构(n个进程,m种资源):

变量含义
Available[m]当前各资源的可用数量
Max[n][m]各进程对各资源的最大需求量
Allocation[n][m]各进程已分配到的各资源数量
Need[n][m]各进程还需要的各资源数量

安全性检查算法:

  1. 令 Work = Available,Finish[n] = {False}
  2. 找满足条件的进程i:Finish[i]=False 且 Need[i] ≤ Work
  3. 找到则:Work += Allocation[i],Finish[i] = True,回到②
  4. 所有Finish[i]=True → 安全;否则不安全

资源请求算法(进程Pi请求Request):

  1. 若Request > Need[i]→出错
  2. 若Request > Available→等待
  3. 试探分配:Available-=Request,Allocation[i]+=Request,Need[i]-=Request
  4. 做安全性检查,安全则真正分配,否则回滚

七、高频易错汇总

易错点正确理解
进程是调度基本单位引入线程后,线程才是调度基本单位
阻塞→直接运行阻塞必须先到就绪,再到运行
P操作增加信号量P操作减少,V操作增加
同步信号量初值=1同步信号量初值=0
P(mutex)先于P(empty)同步P操作必须早于互斥P操作
死锁四条件是充分条件只是必要条件,满足未必死锁
安全状态=不会死锁安全状态一定不死锁;不安全状态可能死锁