4 并发：互斥和同步

type
status
date
slug
summary
tags
category
icon
password

4.1 背景

引入进程/线程：实现并发执行，提高资源利用率和系统吞吐量，但其异步性造成了混乱
间接制约关系：竞争资源 直接制约关系：合作
进程间的同步：对多个相关进程在执行次序上进行协调，以使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性
进程/线程需要同步的原因：
  • 多个进程/线程共同完成一个任务
  • 在合作过程中，除了“并行”的工作之外，还经常出现相互等待的“协作”过程

竞争条件

共享变量counter可能会出现读写错误，正常结果 = 5， 但实际结果可能为4/5/6
术语1：竞争条件
多个进程/线程并发访问和操作同一（组）数据,且执行结果与访问发生的特定顺序有关
在写counter时阻断其他进程访问counter

临界区

在写counter时阻断其他进程访问counter，共享数据一次只允许一个进程操作
术语2：临界区
  1. 临界资源：把一次仅允许一个进程使用的资源称为临界资源，如只能独享的物理设备（打印机）、共享变量等等。
  1. 临界区：在每个进程中，访问临界资源的那段程序称为临界区。
notion image

互斥

术语3：互斥
当一个进程在临界区访问共享资源时，其它进程不能进入该临界区访问任何共享资源的情景。
解决临界区问题：如何进入和退出临界区，以达到进程互斥及同步的目的，必须满足下面3个条件：
  1. 互斥进入：如果一个进程在临界区中执行，则其他进程不允许进入
  1. 有空让进：若干进程要求进入空闲临界区（临界资源空闲）时，应一定能使某个进程进入临界区
  1. 有限等待：从进程发出进入请求到允许进入，不能无限等待

4.2 实现互斥的软件方案

算法1

满足互斥进入要求
P0完成后P1没来，临界区空闲，P0不能接着再次进入，不满足有空让进

算法2

每个进程有自已进入临界区的指示灯
没有保证互斥访问

算法3

先阻挡后来的其它进程，保证了互斥进入
P0 和 P1 几乎同时把 flag0 和 flag1 改成了 true，可能引发死锁，不满足有限等待

死锁

术语4：死锁
两个或两个以上的进程因每个进程都在等待其它进程做完某些事情，而不能继续执行的情形。

算法4

P0 和 P1 几乎同时把 flag0 和 flag1 改成了 true，都进入循环体出不来了，可能引发活锁

活锁

术语5：活锁
两个或两个以上的进程为响应其它进程中的变化，而持续改变自己的状态，但不做有用的工作的情形。

Dekker算法

Peterson算法

多个进程：面包店算法

4.3 实现互斥的硬件方案

中断禁用

可以通过阻止其它进程执行（被调度）的方法，来达到阻止它们进入临界区的目的
通过关中断阻止进程被调度：让用户开关中断非常危险且不方便，代价高，对多处理器不适用

专用机器指令

处理器的设计者提出了一些机器指令，用于保证两个动作的原子性，在一个指令周期中完成，在指令执行过程中，其它指令访问内存将被阻止
专用机器指令方法的优点：适用于多处理器、简单、可支持多个临界区
专用机器指令方法的缺点：使用了忙等待、可能饥饿、可能死锁

饥饿

术语5：饥饿
由于别的并发的激活的进程持久占有所需资源,使某个异步进程在可预测的时间内不能被激活的情形。

4.4 信号量

原子操作

术语6：原子操作
不会被进程（线程）调度机制打断的操作；这种操作一旦开始，就一直运行到结束，中间不会有任何切换。

信号量

信号量（Semaphore）是由Dijkstra于 1965 年提出的一种用于进程同步和互斥的机制。它是一种特殊的整型变量，但只能通过规定的原子操作访问。
只有三种操作：
  • 初始化：信号量 S可被初始化为一个非负整数，如果用于 互斥，通常初始化为 1，如果用于 资源计数，则初始化为可用资源数（例如 n）。
  • 递减：semWait原子操作
    • 每当一个进程想“占用资源”或“进入临界区”时，就执行 semWait(S)。
    • 如果资源够（S >= 0），进程继续；
    • 如果资源不够（S < 0），进程被阻塞，等待其他进程释放资源。
  • 增加：semSignal原子操作，加1，若值小于等于0，则被semWait阻塞的进程解除阻塞
    • 当一个进程释放资源或离开临界区时执行 semSignal(S)；
    • 如果此时有人在等（S <= 0），就唤醒其中一个被阻塞的进程。
notion image

二元信号量

二元信号量（Binary Semaphore）的值只能是0或1
只有三种操作：
  • 初始化：可以初始化0或1
  • semWaitB原子操作：检查信号，若值为0，则执行该操作的进程就会被阻塞，若值为1，则变为0，并继续运行
  • semSignalB原子操作：检查是否有进程在该信号上受阻，若有则受阻的进程则会被唤醒，若没有受阻的进程，则信号量的值改为1
非二元信号量也被称为计数信号量或一般信号量
区分互斥锁（mutex）和二元信号量：互斥锁的特点是加锁与解锁必须由同一线程完成
强信号量：进程从阻塞队列中移出的顺序遵循先入先出（FIFO）策略，被阻塞时间最久的进程最先从队列释放，可以避免发生饥饿
生产者消费者问题的解决方案：一个或多个生产者，一个消费者。先假定缓冲区无限长：
notion image
在任一时刻只有一个主体（生产者或消费者）可访问缓冲区，缓冲区为空时，消费者应阻塞
semwait和semsignal原子操作的实现：硬件/固件实现、软件实现

课堂练习

notion image
notion image
notion image

4.5 管程（未讲，不考）

4.6 消息传递（未讲，不考）

4.7 读者/写者问题

  1. 任意数量的读进程可以同时读取共享数据区
  1. 一次只有一个写进程可以修改共享数据区
  1. 若一个写进程正在修改数据区，则禁止任何读进程读取共享数据区
  • 与一般互斥问题不同，多个读进程可以同时读
  • 与生产者消费者问题不同，不需要调整队列指针，写进程不需要判断是否队列已满，读进程不需要判断是否队列已空

期末真题

2024秋

二、请回答下列问题。（9分）
1）（描述何为模式切换）分析模式切换和进程切换的区别。（2分）
2）（描述何为竞争条件）举例子直观展示竞争条件，并阐述可以如何避免。（2分）
3）某工厂有两个生产车间和一个装配车间。两个生产车间分别生产A，B两种零件，装配车间负责将两种零件组装到一起。生产车间每生产一个A零件或B零件就会送到装配车间的F1、F2货架上。F1货架只能存放A零件，F2货架只能存放B零件，且都可以存放20个零件。装配工人每次从货架上取一个A零件和一个B零件进行组装。试利用信号量机制同步上述过程。（5分）

2020春

二、关于进程同步，回答下列问题（8分）
1）什么是临界区？什么是死锁？（1分）
2）什么是进程同步？进程为什么需要同步？（2分）
3）有三个进程A、B和C合作解决文件打印问题：进程A将文件记录从磁盘读入缓冲区1，每执行一次读一个记录：进程B将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；进程C将缓冲区2的内容打印出来，每执行一次打印一个记录：缓冲区1和2的大小都等于一个记录大小。请用信号量操作来保证文件的正确打印。（5分）

2014

二．信号量
1）什么是信号量，为什么必须是原子操作。
2）什么是同步，进程为什么要同步。
3）设计信号量：生产者在大小为10的缓冲区产生一个数，消费者进程1接收奇数，消费者进程2接收偶数。
Loading...