Notes@Tsukino

第4周_星期二_第2大节

14分钟阅读

第4周 星期二 第2大节

  • 视频：screen_操作系统与分布式计算_第4周_星期二_第2大节.mp4
  • 字幕：transcripts/第4周_星期二_第2大节.srt

时间轴

  • [03:10] 检查作业：Linux调度策略（学生回答CFS、实时FIFO/RR/Deadline）
  • [14:23] 线程概念引入：TCB、线程组成
  • [17:31] 线程优势：开销小、切换快、通信效率高、并发度高
  • [23:08] 用户级线程 vs 内核级线程 vs 混合实现
  • [28:19] 并发执行的同步与互斥问题
  • [56:01] 同步（直接制约）vs 互斥（间接制约）
  • [01:06:28] 生产者-消费者问题（链表buffer数据丢失）
  • [01:14:37] 临界资源CR与临界段CS概念
  • [01:20:22] 软件互斥：Dekker算法→Peterson算法
  • [01:45:03] 硬件方法：关中断、TestAndSet、Swap
  • [01:54:35] 信号量机制（Dijkstra）：P/V操作
  • [02:10:00] 课堂练习：S1~S7任务图PV同步设计

Linux调度策略复习

  • Linux调度分三类：普通调度（CFS完全公平调度，基于红黑树+vruntime，始终选vruntime最小进程执行）、实时调度（FIFO先进先出、RR时间片轮转、Deadline明确时间约束）、扩展调度（标志位配合使用）
  • CFS虚拟化CPU：假设N个进程，每个分得1/N资源，vruntime增长速率受优先级影响
  • 实时调度策略均为静态优先级
  • Deadline可与其它调度策略配合使用，整体非常灵活

线程概念

  • 线程提出目的：让CPU并行粒度更细，进程间并行粒度太大→同一进程内部不同任务也可并行
  • 线程与进程是包含关系：每个线程从属于一个进程，一个进程可有多个线程
  • TCB（线程控制块）：记录线程所属进程ID、运行现场数据保护恢复、寄存器组、程序计数器、工作区（参数传递等）
  • 同进程内线程共享进程的PCB、程序数据、地址空间、资源分配

线程优势

  1. 开销小：切换时保护恢复的信息量比进程小得多
  2. 切换快：上下文信息少，同进程内线程切换尤其快（不同进程的线程切换退化为进程切换）
  3. 通信效率高：同进程线程共享地址空间，通过共享内存直接通信
  4. 并发度高：一个进程内部可多个线程并发

线程 vs 进程比较

进程线程
地址空间独立地址空间共享所属进程地址空间
资源分配以进程为单位线程体量很小
切换开销上下文切换信息量大，开销大同进程内切换只需切换线程部分资源
安全性进程间相互独立同进程线程可修改彼此数据，需保证一致性

用户级线程 vs 内核级线程 vs 混合

  • 用户级线程：操作系统仍以进程管理，线程在用户空间实现，调度由应用程序自己完成，OS不参与
  • 内核级线程（Windows/Linux等主流）：OS层面按线程粒度调度CPU，提供线程相关API直接调用
  • 混合实现（如Solaris）：用户级与内核级两种层面都支持，融合两者优点

并发程序设计的三种方法

  1. 自动识别：写顺序程序，工具自动分析代码中可并行部分，OS利用进程/线程并发执行
  2. 并行程序设计语言：语言语法直接表达并行，编译系统映射到进程/线程
  3. 传统语言+操作系统API（重点）：利用OS提供的并发机制（fork等），在串行语言中实现并发

parbegin/parend 伪代码

  • parbegin 和 parend 之间的任务可以并发执行
  • 例如 S1和S2可并发，之后执行S3：parbegin S1, S2 parend; S3
  • 优点：结构化特征好，清楚表明哪些模块可并发
  • 缺点：无法描述并发任务之间的优先/同步关系（复杂任务图需用信号量）

fork/exit/wait 系统调用

  • fork：创建子进程，复制父进程的data、code、战区等内存映像到子进程。父进程和子进程从同一点（fork返回处）继续执行。返回值为子进程PID（父进程看到）或0（子进程看到）
    • if (pid > 0) 父进程执行代码；if (pid == 0) 子进程执行代码
  • exit：结束进程
  • wait/waitpid：进程间消息传递，父进程等待子进程结束，waitpid可指定等待特定进程

并发执行的同步与互斥

  • 并发任务带来两个问题：同步（Synchronization）和 互斥（Mutual Exclusion）

同步 vs 互斥

  • 同步（直接制约）：为共同完成同一任务，伙伴进程间需要在某些位置协调工作先后顺序，传递信息产生的制约关系。例如S3必须在S1和S2完成后才能执行
  • 互斥（间接制约）：进程竞争使用独占资源（如打印机、共享变量、缓冲区）产生的制约关系。进程间本身不需要协作，因竞争同一资源而被迫等待

临界资源CR与临界段CS

  • 临界资源 CR（Critical Resource）：一次仅允许一个进程使用的资源，如打印机、共享变量、缓冲池
  • 临界段 CS（Critical Section）：各进程必须互斥执行的程序段，即访问临界资源的代码段
  • 临界区访问四准则：
    1. 互斥使用：同一时刻只能有一个进程在临界区
    2. 让权等待：等待进入临界区的进程必须释放CPU，将自己阻塞
    3. 有空让进：临界区外运行的进程不能阻止其他进程进入临界区（临界区空时任何进程有权申请）
    4. 有限等待：不应使要进入临界区的进程无限期等待

生产者-消费者问题

  • 抽象：往buffer写数据的进程=生产者，从buffer读数据的进程=消费者
  • 共享数据：链表表头指针first（producer插入新节点时修改first，consumer取数据时也修改first）
  • 若不互斥：producer和consumer并发访问first指针，数据可能丢失（新节点未正确插入就被覆盖）
  • 典型的一类互斥问题

软件互斥方法

软件实现需额外加入entry code和exit code控制临界区互斥访问，不能假设硬件指令、处理机数目、进程相对速度。

简单turn令牌算法（失败）

  • 定义全局变量turn（0或1），turn=0表示P0可进入，turn=1表示P1可进入
  • 问题：P0不想进入时P1也无法进入（违反有空让进）；进程在CS内失败时其他进程无限等待

Dekker算法演进

  1. 改进一（flag数组）：flag[0]/flag[1]表示各自对CS的使用情况。先检测对方flag再进入
    • 问题：同时检测到CS为空，两个进程都进入（违反互斥）
  2. 改进二（先举手先声明）：先置flag为true表明意愿，再检测对方flag
    • 问题：双方同时举手，谁也进不去（违反有空让进）
  3. 最终Dekker算法：融合turn令牌 + flag数组（举手示意）
    • 先举手(flag=true)，如果有意愿且令牌给对方，则放手(flag=false)等待令牌变回来
    • 正确解决互斥，满足所有准则

Peterson算法

  • 代码比Dekker更简洁，思想类似，结合turn和flag实现

硬件方法

  1. 关中断（disable/enable interrupt）

    • 原理：CPU调度发生在中断时，关中断后不会发生进程切换
    • 缺点：限制CPU并发能力；上层应用若关中断可能忘开；多CPU系统失效（其他核仍可运行）

  2. TestAndSet 指令

    • 硬件原子指令：读取lock值到rv，将lock置为true，返回rv
    • while TestAndSet(lock) 忙等，直到lock为false才进入CS，退出时置lock=false

  3. Swap 指令

    • 硬件原子指令：交换两个变量的值
    • 局部变量key=true，while (key) swap(lock, key) 忙等，lock被释放时key变为false则进入CS，退出时lock=false

信号量机制（Dijkstra）

  • 信号量：特殊数据结构，专门用于实现进程同步和互斥，代表需要互斥访问的共享资源
  • 信号量的值只能通过 P/V原语操作 改变

P操作（申请资源）

P(S) {
    S--;
    if (S < 0) 将当前进程放入阻塞队列;
}

V操作（释放资源）

V(S) {
    S++;
    if (S <= 0) 从阻塞队列唤醒一个进程到就绪队列;
}

信号量类型

类型用途初值
公用信号量进程间互斥（代表临界资源）1
私有信号量进程内同步（进程内部任务间）0 或 N

互斥模式（P和V在同一进程）

P(mutex); // 进入CS前申请
CS;
V(mutex); // 退出CS后释放

同步模式（P和V在不同进程）

// P1进程              // P2进程
S1;                   P(sync);
V(sync);              S2;
  • 同步信号量初值=0
  • P1执行完S1后V(sync)通知P2，P2在S2前P(sync)等待

S1~S7任务图PV同步设计（课堂练习）

任务依赖关系：

  • S1→S2→S4→S5→S7（串行主线）
  • S1完成后可并行执行S3
  • S3完成后可执行S6
  • S5和S6都完成后才能执行S7

方案一（三个进程）：

  • P1进程：S1, S2, S4, S5, S7（顺序执行）
  • P2进程：S3（与P1中的S2并发）
  • P3进程：S6（与P1中的S5并发）

同步点及信号量设计：

  • sync1：S1→S3（P1中S1后V(sync1)，P2中S3前P(sync1)）
  • sync2：S3→S6（P2中S3后V(sync2)，P3中S6前P(sync2)）
  • sync3：S6→S7（P3中S6后V(sync3)，P1中S7前P(sync3)）
  • 所有同步信号量初值=0

也可将S3和S6合并到一个进程（两进程方案），体现多种划分可能

信号量底层实现要点

  • P操作若资源不可用，将进程挂入阻塞队列并让出CPU（不是忙等）
  • V操作从等待队列唤醒进程到就绪队列
  • PV操作本身的互斥通过屏蔽中断或硬件加锁实现
  • 信号量数据结构包含：整型value + 等待队列指针

考勤/签到/小测

  • 点名：曹凯琪、黄康、李毅佳、梅智轩、周丁男、杜春雨、杨寿辉、曾建成
  • 缺勤率高被指出
  • 下节课上机安排（地点在乐学平台公布）

作业

  • 课外作业：调研Linux调度策略（已检查）

考试/复习重点

  • 同步 vs 互斥区别（直接制约 vs 间接制约）
  • 临界区访问四准则
  • Dekker算法、Peterson算法
  • P/V操作原语（互斥模式与同步模式的区别）
  • 信号量解决生产者-消费者、任务图同步问题

其他需要回看的片段

  • [01:06:28] 生产者-消费者数据丢失问题（链表first指针互斥）
  • [01:54:35] 信号量P/V操作讲解
  • [02:10:00] S1~S7任务图PV练习（三种同步信号量设计）

省流

  • 线程概念（TCB/共享进程资源/优势） + 并发同步互斥问题（同步=直接制约协同，互斥=间接制约竞争） + 三种互斥机制（软件Dekker→Peterson/硬件关中断TAS Swap/信号量PV），重点：P/V操作原语、信号量解决同步互斥、S1~S7任务图PV设计

关系图谱