2.1 进程的基本概念

进程与程序的区别：

进程控制块 (PCB) 是进程存在的唯一标志，包含：

• 进程描述信息：进程标识符 PID、用户标识符 UID。
• 进程控制和管理信息：进程当前状态、优先级、代码入口地址。
• 资源分配清单：代码段指针、数据段指针、堆栈指针、文件描述符、I/O 设备。
• 处理机相关信息：通用寄存器、PC、PSW 等现场信息（用于切换时保存/恢复）。

2.2 进程的状态与转换

进程的三种基本状态：

• 就绪 (Ready)：已获得除 CPU 外的所有资源，等待被调度。
• 运行 (Running)：正在 CPU 上执行。单核系统中只有一个进程处于运行态。
• 阻塞 (Blocked/Wait)：因等待某事件（如 I/O 完成）而暂停执行。

五种状态（加入创建和结束）的转换关系：

2.3 进程控制

进程控制由 OS 内核的原语实现，保证原子性：

• 创建原语：申请空白 PCB → 分配资源（内存、文件）→ 初始化 PCB（状态置为就绪）→ 插入就绪队列。
• 撤销原语：从队列摘除 PCB → 释放资源 → 撤销子进程 → 释放 PCB。
• 阻塞原语：运行态 → 保存现场到 PCB → 置为阻塞态 → 插入等待队列 → 调度其他进程。
• 唤醒原语：从等待队列摘除 → 置为就绪态 → 插入就绪队列。
• 切换原语：保存当前进程现场到 PCB → 从新进程 PCB 恢复现场 → 切换。

2.4 线程

线程分为用户级线程（由应用程序通过线程库管理，内核感知不到）和内核级线程（由内核管理调度）。多对一模型中，一个线程阻塞会导致整个进程阻塞。

2.5 进程调度

调度层次

• 高级调度（作业调度）：从外存的后备队列选作业调入内存，创建进程。频率低。
• 中级调度（内存调度）：将暂时不能运行的进程调至外存（挂起），需要时再调回。频率中等。
• 低级调度（进程调度）：从就绪队列选进程分配 CPU。频率最高，基本调度。

调度算法评价指标

• CPU 利用率 = CPU 忙碌时间 / 总时间。
• 系统吞吐量 = 单位时间内完成的作业数。
• 周转时间 = 完成时间 − 到达时间；平均周转时间 = 各进程周转时间之和 / n。
• 带权周转时间 = 周转时间 / 服务时间；等待时间 = 周转时间 − 服务时间。
• 响应时间 = 从提交到首次响应的时间。

调度算法

HRRN 高响应比优先调度

HRRN 是非抢占式调度算法，综合了 FCFS 和 SJF 的优点：

• 等待时间长的进程响应比升高，可获得优先调度（避免饥饿，体现 FCFS 的公平性）。
• 运行时间短的进程响应比也高（等待相同时，分母小的响应比大），获得优先调度（体现 SJF 的高效率）。

示例计算：设 P1 到达时间 0、服务时间 10；P2 到达时间 1、服务时间 2。在时刻 10（P1 刚完成时），P2 已等待 9 个单位时间，响应比 R₂ = (9+2)/2 = 5.5；若 P3 到达时间 2、服务时间 5，在时刻 10 时等待了 8，R₃ = (8+5)/5 = 2.6 → 选 P2。

// HRRN 高响应比优先
while(就绪队列非空){
  float maxR = -1;
  PCB best = null;
  for(each P in 就绪队列){
    float R = (P.waitTime + P.svcTime) / P.svcTime;
    if(R > maxR){ maxR = R; best = P; }
  }
  dispatch(best);
  while(best 未完成) best 运行;
}

调度算法伪代码

// FCFS 先来先服务
while(就绪队列非空){
  P = 就绪队列队首;
  dispatch(P);                     // 分配 CPU
  while(P 未完成) P 运行;
  if(P 完成) 撤销 P;
  else P 回到就绪队列队尾;
}

// SJF 短作业优先（非抢占）
while(就绪队列非空){
  // 选择服务时间最短的进程
  P = argmin(ready, p => p.svcTime);
  dispatch(P);
  while(P 未完成) P 运行;
}

// RR 时间片轮转
while(就绪队列非空 || 有进程运行){
  P = 就绪队列队首;
  dispatch(P, q);                // 最多运行 q 时间
  if(P 完成) 撤销 P;
  else 就绪队列.入队(P);
  if(新进程到达) 就绪队列.入队(新进程);
}

// 多级反馈队列 MLFQ
for 每个新进程 P: Q1.入队(P);
while(true){
  if(Q1 非空): RR_dispatch(Q1, q1);
  else if(Q2 非空): RR_dispatch(Q2, q2);
  else if(Q3 非空): FCFS_dispatch(Q3);
}
// 规则：用完时间片未完成 → 降级；完成 → 撤销；
//       在高优先级队列等待过久 → 优先级提升

2.6 同步与互斥

临界区互斥的四条准则：

• 空闲让进：临界区空闲时，应允许一个进程进入。
• 忙则等待：已有进程在临界区时，其他进程必须等待。
• 有限等待：等待进程必须在有限时间内进入，防止死等。
• 让权等待：不能进入时应释放 CPU，避免"忙等"。

进程同步基本实现方法

实现进程互斥的基本方法主要有软件方法和硬件方法。其中Peterson 算法是最经典的软件实现方案。

Peterson 算法（两进程互斥）

Peterson 算法使用两个共享变量来实现两个进程的严格互斥：

• flag[0], flag[1]：布尔数组，flag[i] = true 表示进程 i 想进入临界区。
• turn：整数，表示谦让变量——当两个进程同时想进入临界区时，turn 决定哪一方先让步。

bool flag[2] = {false, false};
int turn = 0;

// 进程 i（i=0 或 i=1）
void Pi(int i){
  int j = 1 - i;
  while(true){
    flag[i] = true;              // ① 表示想进入临界区
    turn = j;                     // ② 谦让对方，让对方先走
    while(flag[j] && turn == j);   // ③ 若对方想进且对方被谦让，则等待
    临界区;
    flag[i] = false;              // ④ 离开临界区
    其余区;
  }
}

Peterson 算法满足临界区的三条准则：

• 互斥 (Mutual Exclusion)：两个进程不会同时进入临界区。若两个进程都想进入（flag[0]=flag[1]=true），turn 只能等于 0 或 1，只有一个进程能通过 while 循环。
• 前进 (Progress)：若临界区空闲且有进程想进入，则一定可以进入。若只有一方想进，对方 flag 为 false，while 条件不成立，可直接进入。
• 有限等待 (Bounded Waiting)：一个进程不会无限等待。turn 在对方退出临界区后会变成对方的谦让值，等待的进程在对方执行完临界区后即可进入。

信号量机制与 PV 操作

信号量的应用：

• 互斥信号量：初值为 1，P(mutex) 和 V(mutex) 包裹临界区，实现互斥。
• 同步信号量：初值为 0，前操作后 V(S)，后操作前 P(S)，保证执行顺序。
• 资源信号量：初值为资源数量 n，实现资源计数。

经典问题：生产者-消费者

一组生产者向缓冲区放入产品，一组消费者从缓冲区取出产品。缓冲区大小为 N。需三个信号量：

// 信号量定义
semaphore mutex = 1;   // 互斥访问缓冲区
semaphore empty  = N;   // 空缓冲区数量（同步）
semaphore full   = 0;   // 满缓冲区数量（同步）

producer(){
  while(1){
    生产一个产品;
    P(empty);      // 申请空位，无空位则阻塞
    P(mutex);      // 互斥访问缓冲区
    放入产品;
    V(mutex);      // 释放缓冲区访问权
    V(full);       // 增加产品计数，唤醒消费者
  }
}
consumer(){
  while(1){
    P(full);       // 申请产品，无产品则阻塞
    P(mutex);      // 互斥访问缓冲区
    取出产品;
    V(mutex);      // 释放缓冲区访问权
    V(empty);      // 增加空位，唤醒生产者
    消费产品;
  }
}

交互式动画 · 生产者-消费者问题

可视化物品在有界缓冲区中流动，观察 empty/full/mutex 三个信号量的变化。

经典同步问题

1. 读者-写者问题

一组读者进程只读共享数据，一组写者进程可修改。规则：① 允许多个读者同时读；② 写者必须互斥且独占；③ 读者与写者必须互斥。

需要三个信号量：rwmutex（写者互斥，初值 1）、rmutex（读者计数互斥，初值 1）、writeblock（写者阻塞读者，初值 1，解决"写饥饿"）。

// 信号量
semaphore rwmutex = 1;    // 写者互斥
semaphore rmutex  = 1;    // 读者计数互斥
semaphore writeblock = 1; // 写饥饿解决
int readcount = 0;

reader(){
  while(1){
    P(writeblock);          // 无写者请求时才进入
    P(rmutex);              // 互斥更新 readcount
    readcount++;
    if(readcount==1) P(rwmutex);   // 第一个读者阻止写者
    V(rmutex);
    V(writeblock);
    读数据;
    P(rmutex);
    readcount--;
    if(readcount==0) V(rwmutex);   // 最后一个读者放行写者
    V(rmutex);
  }
}
writer(){
  while(1){
    P(writeblock);          // 请求写入，阻塞后续读者
    P(rwmutex);             // 互斥其他写者
    写数据;
    V(rwmutex);
    V(writeblock);
  }
}

交互式动画 · 读者-写者问题

按钮触发读者进入/离开、写者请求/完成，观察读者共享与写者互斥。

2. 哲学家就餐问题

5 位哲学家围坐一圈，每人需同时获得左右两支筷子才能就餐。用 5 个互斥信号量 chopstick[i] 表示每支筷子。

semaphore chopstick[5] = {1,1,1,1,1};

philosopher(int i){
  while(1){
    思考;
    P(chopstick[i]);              // 取左
    P(chopstick[(i+1)%5]);        // 取右
    进餐;
    V(chopstick[(i+1)%5]);
    V(chopstick[i]);
  }
}

交互式动画 · 哲学家就餐问题

5位哲学家围坐圆桌，观察死锁形成与预防策略效果。切换策略对比差异。

锁与条件变量 [22新增]

自旋锁 vs 阻塞锁

条件变量 (Condition Variable)

条件变量的基本操作：

• wait(cond, lock)：原子地释放锁并将当前线程加入 cond 的等待队列，线程进入阻塞状态。被唤醒后重新获取锁。
• signal(cond)：唤醒 cond 等待队列中的一个线程（若有）。
• broadcast(cond)：唤醒 cond 等待队列中的所有线程。

// 条件变量典型用法（生产者-消费者）
lock mutex;
cond  notFull, notEmpty;

producer(){
  lock_acquire(mutex);
  while(缓冲区满) cond_wait(notFull, mutex);
  放入产品;
  cond_signal(notEmpty);
  lock_release(mutex);
}

consumer(){
  lock_acquire(mutex);
  while(缓冲区空) cond_wait(notEmpty, mutex);
  取出产品;
  cond_signal(notFull);
  lock_release(mutex);
}

与信号量的对比

管程 (Monitor)

管程的特征：① 模块化封装数据与操作；② 过程互斥调用；③ 通过条件变量 (wait/signal) 实现同步。典型应用：用管程实现 bounded buffer、读者-写者。

信号 (Signal) IPC [25新增]

常见信号类型

信号处理方式

进程收到信号后可选择三种处理方式之一：

• 忽略（Ignore）：对信号不做任何处理。但 SIGKILL 和 SIGSTOP 不能被忽略。
• 捕获并自定义处理（Handler）：用 signal() 或 sigaction() 注册一个信号处理函数。当信号到达时，内核中断当前执行流，调用处理函数，处理完再返回。
• 默认动作（Default）：按系统默认方式处理——通常为终止进程（Term）、终止并转储 core dump（Core）、停止进程（Stop）、忽略（Ign）等。

发送信号

• kill 系统调用：kill(pid, signum) 向指定进程发送信号。pid > 0 发给该进程；pid = 0 发给同组所有进程；pid = -1 发给所有有权限发送的进程。
• 键盘组合键：Ctrl+C 发送 SIGINT；Ctrl+\ 发送 SIGQUIT；Ctrl+Z 发送 SIGTSTP。
• 内核产生：硬件异常（如除零→SIGFPE、非法访存→SIGSEGV）由内核向当前进程发送。

进程通信 IPC

• 共享内存：两进程映射同一块物理内存，直接读写，速度最快；需额外同步。
• 管道 (Pipe)：半双工，父子进程间通信；匿名管道只能用于亲缘进程，命名管道可用于无亲缘关系进程。
• 消息队列：以消息为单位，可跨进程，先进先出；有格式，便于结构化通信。
• 信号量：用于进程间同步互斥。
• 信号 (Signal)：用于进程间异步通知（如中断、超时）。
• 套接字 (Socket)：网络环境下进程间通信的通用接口。

2.7 死锁

死锁产生的四个必要条件

• 互斥条件：资源一次只能被一个进程使用。
• 请求和保持条件：进程保持已有资源的同时请求新资源。
• 不剥夺条件：已分配的资源不能被强行剥夺。
• 循环等待条件：存在进程-资源的循环等待链。

死锁处理策略

• 预防死锁：破坏四个必要条件之一（如一次性申请所有资源破坏"请求保持"；资源编号顺序申请破坏"循环等待"）。
• 避免死锁：在资源分配时判断是否安全，典型算法是银行家算法。
• 死锁检测与解除：允许死锁发生，检测到后通过撤销进程、回滚、剥夺资源来解除。
• 鸵鸟策略：忽略死锁（实际系统常用）。

银行家算法

是最著名的死锁避免算法。在进程申请资源时，先试探性分配，再执行安全性算法：能否找到一个安全序列，使所有进程都能顺利完成。若安全则真正分配，否则让进程等待。

银行家算法伪代码

// 数据结构
int Available[m];     // 可用资源向量
int Max[n][m];        // 最大需求矩阵
int Allocation[n][m]; // 已分配矩阵
int Need[n][m];       // 需求矩阵 = Max - Allocation

bool SafetyCheck(){
  vector<int> Work = Available;
  bool Finish[n] = {false};
  for(int i=0; iint k = -1;
    for(int j=0; jif(!Finish[j] && Need[j] <= Work){ k=j; break; }
    if(k==-1) return false;   // 不安全
    Finish[k] = true;
    Work += Allocation[k];          // 释放资源
  }
  return true;   // 安全
}

bool Request(int i, int Request[m]){
  if(Request > Need[i]) return false;
  if(Request > Available) return false;
  // 试探分配
  Available -= Request;
  Allocation[i] += Request;
  Need[i] -= Request;
  if(SafetyCheck()) return true;
  else { // 回滚
    Available += Request;
    Allocation[i] -= Request;
    Need[i] += Request;
    return false;
  }
}

交互式动画 · 死锁检测（资源分配图化简）

通过资源分配图化简法判断死锁，步进观察化简过程。