Elian's blog page

管程把共享数据和访问共享数据的过程封装在一起，并由语言或编译器负责保证互斥进入。程序员不再直接在每段临界区外手写 P(mutex) 和 V(mutex)，而是调用管程提供的入口过程。 管程管程是一种特殊的软件模块，通常由四部分组成： 组成部分 含义 管程名 标识这一组共享数据和操作 局部共享数据结构 只能在管程内部被访问的数据，如缓冲区、计数器 一组过程 对共享数据进行操作的入口，如 insert、remove 初始化语句 设置共享数据的初值 管程的基本特征有三条： 局部于管程的数据只能被局部于管程的过程访问。 进程只能通过调用管程内的过程进入管程，从而访问共享数据。 每次只允许一个进程在管程内执行某个内部过程。 封装共享数据，自动保证互斥进入。 互斥进入管程内部可以有多个入口过程，但同一时刻只允许一个进程在管程内执行。若 P1 正在执行 insert，P2 此时调用 remove，P2...

死锁死锁是指多个并发进程因为竞争资源而互相等待，导致这些进程都被阻塞、都无法继续向前推进的现象。 典型结构是： P1 已经持有 R1，还想申请 R2。 P2 已经持有 R2，还想申请 R1。 P1 等 P2 释放 R2，P2 等 P1 释放 R1。 如果没有外力干预，两个进程都不会主动离开阻塞状态。 从 Dining-Philosophers-Problem...

处理策略总览死锁处理有三类策略： 策略 发生时机 核心思想 预防死锁 分配规则设计阶段 破坏死锁四个必要条件之一 避免死锁 每次资源分配之前 判断分配后是否仍处于安全状态 检测与解除 允许死锁发生之后 检测死锁进程，再采取措施解除 预防最保守，避免需要提前知道进程最大资源需求，检测与解除允许系统先冒险运行。 预防死锁预防死锁就是破坏四个必要条件的若干个。 破坏条件 方法 代价 互斥条件 把独占资源改造成共享资源，如 SPOOLing...

问题模型哲学家就餐问题描述的是 5 个哲学家围坐在圆桌旁。每两个哲学家之间有一支筷子。哲学家不断在“思考”和“进餐”之间切换： 思考不需要共享资源。 进餐必须同时拿到左、右两支筷子。 每支筷子是互斥资源，同一时刻只能被一个哲学家持有。 如果需要的筷子已经被别人持有，哲学家就等待。 进餐结束后，哲学家释放两支筷子，再继续思考。 编号约定： 哲学家编号为 0 到 4。 筷子编号为 0 到 4。 哲学家 i 左边的筷子是 chopstick[i]。 哲学家 i 右边的筷子是 chopstick[(i + 1) % 5]。 这个问题只有互斥关系，但每个进程不是只申请一个临界资源，而是需要同时持有两个临界资源。 朴素写法与死锁最直接的写法是每个哲学家先拿左筷子，再拿右筷子： 1234567891011121314semaphore chopstick[5] = {1, 1, 1, 1, 1};Pi 进程：while (1) { 思考; P(chopstick[i]); // 拿左筷子 ...

问题模型读者-写者问题描述的是这样两类并发进程共享同一个文件或共享数据： 读者只读取共享数据，不改变数据内容。 写者会修改共享数据。 多个读者同时读同一份数据，不会产生副作用。 写者和读者同时访问，可能读到不一致的数据。 多个写者同时访问，可能互相覆盖写入结果。 因此它不是简单的所有进程互斥。真正的约束是读读共享，读写互斥，写写互斥。 三个基本量读者-写者问题的关键是把当前正在读的一组读者看作一个整体。 名称 初值 含义 rw 1 共享文件访问权；写者独占，读者组整体占有 count 0 当前正在访问共享文件的读者数量 mutex 1 保护 count 的检查和修改，使其不可交错 rw 控制文件本身。写者写文件前执行 P(rw)，写完后执行 V(rw)。 count 记录读者组的人数。第一个读者进入时把 rw 锁住，最后一个读者退出时把 rw 释放。 mutex 不保护文件内容。它只保护 count。因为“检查 count、决定是否操作 rw、修改...

问题模型生产者-消费者问题描述的是一组生产者进程和一组消费者进程通过共享缓冲区交换数据： 生产者每次生产一个产品，并把产品放入缓冲区。 消费者每次从缓冲区取出一个产品，并使用这个产品。 缓冲区初始为空，容量为 $n$。 缓冲区满时，生产者不能继续放入产品。 缓冲区空时，消费者不能继续取出产品。 缓冲区是临界资源，放入和取出都必须互斥执行。 三个信号量生产者-消费者问题同时包含互斥和同步。不只一个 mutex，还得有 empty、full 信号量 初值 含义 谁 P 谁 V mutex 1 缓冲区访问权，同一时刻只允许一个进程放入或取出 生产者/消费者进入缓冲区前 生产者/消费者离开缓冲区后 empty n 空闲缓冲区数量 生产者放入前 消费者取出后 full 0 已有产品数量，也就是非空缓冲区数量 消费者取出前 生产者放入后 empty 和 full 是两个方向的同步关系： 生产者需要空位。若 empty == 0，说明缓冲区满，生产者等待消费者释放空位。 消费者需要产品。若 full ==...

信号量互斥实现方法有两个明显问题： 软件算法依赖普通语句组合，检查、上锁之间可能被进程切换打断。 TSL、Swap、自旋锁虽然能保证互斥，但等待者会反复占用 CPU，不能让权等待。 信号量把“申请资源”和“释放资源”做成操作系统提供的原语。原语执行时不可被中断，因此可以把关键操作一气呵成；记录型信号量还可以把不能继续的进程阻塞起来，而不是让它原地忙等。 信号量可以理解为一种受限变量：普通程序不能随便读写它，只能初始化，并通过 wait(S) / signal(S) 操作它。wait(S) 常记为 P(S)，signal(S) 常记为 V(S)。 操作 语义 可能导致死锁吗 典型位置 P(S) / wait(S) 申请一个单位的资源 S 可能 使用资源之前 V(S) / signal(S) 释放一个单位的资源 S 不会 使用资源之后，或产生条件之后 P(S) 可能会导致死锁，因此它的位置非常敏感；V(S) 不会有这个问题，因此多个 V 操作之间通常没有 P...

互斥实现方法的读法每一种方法都要看三件事： 进入区做什么：如何检查临界区是否可进入，如何表达“我要进入”。 退出区做什么：如何释放临界区，如何让其他进程继续。 是否违反某原则：空闲让进、忙则等待、有限等待、让权等待中哪条做不到。 软件方法完全依靠普通变量和程序执行顺序。硬件方法把某些关键动作做成不可中断的原子操作。 下面均以两个进程 $P_0$、$P_1$ 竞争同一个临界资源为例。 软件实现方法 方法 共享变量 进入区核心动作 退出区核心动作 主要问题 单标志法 turn 只允许 turn == i 的进程进入 把 turn 改成对方编号 必须轮流进入，违反空闲让进 双标志先检查法 flag[2] 先检查对方意愿，再设置自己意愿 清除自己意愿 检查后、上锁前可被切换，违反忙则等待 双标志后检查法 flag[2] 先设置自己意愿，再检查对方意愿 清除自己意愿 双方都先上锁时会互相等待，违反空闲让进和有限等待 Peterson...

进程同步与进程互斥并发进程有异步性：各进程以各自独立、不可预知的速度推进。异步本身不是错误，但如果进程之间存在共享数据、共享设备或先后依赖，操作系统就要提供同步互斥机制。 同步解决先后顺序问题。互斥保证不能同时访问的资源访问不出问题。 概念 关注点 典型问题 制约关系 进程同步 进程之间的执行先后 B 必须等 A 产生数据后才能继续处理 直接制约 进程互斥 同一资源不能同时访问 A 使用打印机时，B 不能同时使用同一打印机 间接制约 同步的关键是“某个动作必须发生在另一个动作之后”。例如进程 A 先对缓冲区数据预处理并写回，进程 B 再读取处理后的数据。若 B 提前读取，就会得到旧数据或未处理数据。 互斥的关键是“同一时刻最多一个进入”。例如打印机、摄像头、某些共享变量、内存缓冲区，都可能在一个时间段内只允许一个进程使用。 临界资源与临界区临界资源是一个时间段内只允许一个进程使用的资源。它可以是物理设备，也可以是共享变量、共享数据结构或缓冲区。 临界区是进程中访问临界资源的那段代码，也称临界段。 一次互斥访问在逻辑上分为四段： 1234567Pi...

多处理机调度单处理机调度只需要回答一个问题：让哪个就绪进程上 CPU。 多处理机调度还要多回答一个问题：让它上哪个 CPU。因此，同一个进程调度算法放到多 CPU 环境下，还要考虑队列组织、负载均衡和处理机亲和性。 场景 调度决策 单处理机 从就绪队列中选出一个进程，让它运行 多处理机 先选进程，再决定放到哪个 CPU 上运行 两个目标多处理机调度常见的两个目标。 目标 含义 好处 代价 负载均衡 尽量让各 CPU 同等忙碌 避免某些 CPU 空闲、某些 CPU 排队过长 进程可能被迁移到别的 CPU 处理机亲和性 尽量让同一进程继续在同一 CPU 上运行 更容易复用该 CPU Cache 中的数据 可能造成某些 CPU 忙、某些 CPU 闲 处理机亲和性来自缓存局部性。进程上次在某个 CPU 上运行时，它访问过的数据和指令可能还留在该 CPU 的 Cache 中；如果下次仍在这个 CPU 上运行，Cache 命中率更可能较高。若频繁换...