并发程序设计

6.1 并发进程

6.1.1 并发程序设计的概念

顺序程序设计

  • 程序执行的内部顺序性：程序在处理器上的执行是严格有序的
  • 程序执行的外部顺序性：将具体问题的求解过程设计为一个程序或者严格顺序执行的程序序列

顺序程序设计特性

  1. 程序执行的顺序性
  2. 计算环境的封闭性：独占资源
  3. 计算结果的确定性
  4. 计算过程的可再见性

进程的并发执行

  • 多道程序设计允许多个程序同时进入内存竞争处理器
  • OS允许多个进程并发执行
  • OS保证按照“顺序程序设计”思想编制的程序在并发执行时不受影响，如同独占计算机
  • 按照“顺序程序设计”思想编制的进程在OS中并发执行属于无关的并发进程

并发程序设计

把一个具体问题求解设计成若干个可同时执行的程序模块的方法

并发程序设计的特性

  • 并发性
  • 共享性：共享软件资源
  • 交往性：并发执行时存在制约

6.1.2 并发进程的制约关系

1、无关与交往的并发进程

  • 无关：分别在不同的变量集合上运行，满足Bernstein条件

  • 交往：共享某些变量

2、与时间有关的错误

交往的并发进程可能会由于设计不当出现（1）结果错误（2）永远等待

3、进程互斥与进程同步（竞争与协作）

进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源，是对进程使用资源次序上的一种协调

  • ==进程互斥==：并发进程之间因相互争夺独占型资源而产生的竞争制约关系，引发死锁、饥饿问题
  • ==进程同步==：为完成共同任务基于某个条件来协调执行先后关系而产生的协作制约关系

6.2 临界区管理

6.2.1 临界区

  • 临界资源：互斥共享变量所代表的资源（一次只能被一个进程所使用）
  • 临界区（critical section）：并发进程中与互斥共享变量相关的程序段
  • 临界区管理的三个要求
    • 一次至多允许一个进程停留在临界区
    • 不能无限停留在临界区
    • 不能无限等待进入临界区

6.2.2 临界区管理——软件方法

1
2
3
4
5
6
7
8
9
10
11
P1:
	while flag2 {} // 语句1
	flag1 = true; // 语句2
	// 临界区
	flag1 = false;

P2:
	while flag1 {}
	flag2 = true;
	// 临界区
	flag2 = false;

语句1和语句2可以交换顺序，但是都是不可行的，本质是因为语句1和语句2是可以被中断的，就会导致同时进入或者同时等待

Dekker算法

进程联系与临界区管理

Peterson算法

P0和P1使用临界区的次序变成了完全1:1的交替方式，并不符合临界区互斥使用的完全随机性

6.2.3 临界区管理——硬件方法

TS指令

SWAP指令

开关中断

  • TS和SWAP指令均为忙等式，效率低
  • 【关中断】；【临界区】；【开中断】
  • 不便交给用户进程使用（防止滥用）

6.3 PV操作

6.3.1 PV操作与进程互斥

==信号量==

1
2
3
4
typedef struct semaphore {
    int value; // 信号量值
    struct pcb* list; // 等待信号量的进程队列
}

==PV操作==

1
2
3
4
5
6
7
8
9
P(semaphore s){
    s -= 1;
    if (s < 0) W(s); // 将进程加入等待队列
}

V(semaphore s){
    s += 1;
    if (s <= 0) R(s); // 从等待队列中释放一个进程
}

6.3.2 PV操作与进程同步（生产者消费者问题）

1消费者1生产者1缓冲区

需要两个信号量：1、生产者的空位；2、消费者的产品

1消费者1生产者N缓冲区

需要为消费者和生产者增加两个指针

N消费者N生产者N缓冲区

需要增加两个信号量：N个消费者互斥使用getptr；N个生产者互斥使用putptr；

6.4 管程

为什么要引入管程?

  • 把分散在各进程中的临界区集中起来进行管理
  • 防止进程有意或无意的违法同步操作
  • 便于用高级语言来书写程序

管程

管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成的软件模块。

  • 条件变量：用于阻塞进程的信号量
  • 同步原语wait：阻塞进程
  • 同步原语signal：释放进程

signal操作存在一个问题：会导致释放进程和被释放进程同时存在于管程中

霍尔管程：执行signal进程等待，直到被释放进程退出管程或等待另一个条件

霍尔管程

霍尔管程基于PV操作原语实现，wait和signal可以是程序过程；可以使用语言机制实现霍尔管程。

不要求signal操作是过程题的最后一个操作，且wait和signal可以被中断

1
2
3
4
5
6
7
8
// 霍尔管程中的信号量
mutex; // 调用管程过程的互斥信号量
next; // 发出signal操作的进程挂起自己的信号量
next_count; // 在next上等待的信号量

// 霍尔管程中的条件变量
x_sem; // 与资源相关的信号量
x_count; // 在x_sem上等待的进程数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
procedure wait(var x_sem : semaphore, var x_count : integer, var IM){
    x_count += 1
    // 如果有在next上等待的进程，先释放在next上等待的进程
    // 如果没有就释放等待进入管程的进程
    if IM.next_count > 0 then V(IM.next) else V(IM.mutex)
    P(x_sem)
    x_count -= 1
}

procedure signal(var x_sem : semaphore, var x_count : integer, var IM){
	if x_count > 0 then
		IM.next_count += 1
		V(x_sem)
		P(IM.next) // 执行signal操作的进程阻塞自己
		IM.next_count -= 1
}
1
2
3
4
5
6
7
8
9
10
void enter(InterfaceModule &IM){
    P(IM.mutex);
}

void leave(InterfaceModule &IM){
    if (IM.next_count > 0)
        V(IM.next);
    else 
        V(IM.mutex);
}

哲学家问题

  • 等待叉子的方案：可能会产生死锁（先拿一个再拿一个）
  • 等待盘子的方案：一次拿两个叉子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
process philosopher_i(){
    L: thinking();
    // 进入管程的队列
    P(IM.mutex);
    dining_philosopers.pickup(i);
    if IM.next_count > 0 then V(IM.next); else V(IM.mutex);
    
    eating();
    
    P(IM.mutex);
    dining_philosophers.putdown();
    if IM.next_count > 0 then V(IM.next); else V(IM.mutex);
    
    goto L;
}

读者写者问题

生产者消费者问题

苹果橘子问题

6.5 进程通信

6.5.1 进程通信

  • 交往进程通过信号量操作实现进程互斥和同步，这是一种低级通信方式
  • 进程有时还需要交换更多的信息，可以引进高级通信方式——进程通信机制，实现进程间用==信件==来交换信息
  • 进程通信扩充了并发进程的数据共享、
  • 进程直接通信
    • 发送或接收信件的进程指出信件发给谁或从谁那里接收信件
    • send(P, 信件)：把信件发送给进程P
    • receive(Q, 信件)：从进程Q接收信件
  • 进程间接通信
    • 发送或者接收信件通过一个信箱来进行，该信箱有唯一标识符
    • 多个进程共享一个信箱
      • send(A, 信件)：把信件发送给信箱A
      • receive(A, 信件)：从信箱A接收信件
    • 信箱可以分成信箱特征和信箱体两部分
      • 信箱特征：指出信箱容量、信件格式、指针等
      • 信箱体用来存放信件，分成若干个区，每个区容纳一封信
  • 发送信件原语处理流程
    • 指定的信箱未满=》把信件送入信箱中指针所指示位置，释放等待该信箱中指针的等待者
    • 否则=》发送信件者被置成等待信箱的状态
  • 接收信件原语处理流程
    • 指定信箱有信件=》取出一封信件，释放等待信箱的等待者
    • 否则=》接收信件者被置成等待信箱中信件的状态

6.5.2 高级进程通信机制

  • 基于字节流的进程信息规约

  • 基于RPC（远程过程调用）/XDR（外部数据表示）的高级通信规约

6.6 死锁

6.6.1 死锁的产生

  • ==死锁==：一组进程处于死锁状态是指：每一个进程都在等待被另一个进程所占有的、不能抢占的资源。
  • 死锁的产生不仅与系统拥有的资源数量相关，而且与资源分配策略，进程对资源的使用要求以及并发进程的推进顺序有关
  • 产生死锁的4个必要条件：
    1. ==互斥条件==：进程应互斥使用资源，任一时刻一个资源仅为一个进程独占
    2. ==占有和等待条件==：一个进程请求不到资源得不到满足而等待时，不释放已占有的资源
    3. ==不剥夺条件==：任一进程不能从另一进程那里抢夺资源
    4. ==循环等待条件==：存在一个循环等待链，每一个进程分别等待它前一个进程所持有的资源

6.6.2 死锁的防止

破坏产生死锁的四个必要条件之一，就可以防止死锁

  1. 互斥条件：将独占型资源改成共享性资源，使资源可以同时访问而不是互斥使用
    • 部分资源是天生具有互斥性，不能被同时访问
  2. 占有和等待条件：静态分配。一个进程必须在执行前就申请它所要的全部资源，并且直到它所要的资源都得到满足之后才开始执行
    • 实现简单，但是会严重降低操作系统资源利用率
  3. 不剥夺条件：采用剥夺式调度方法
  4. 循环等待条件：层次分配，动态分配。资源被分成多个层次（排序）；
    • 一个进程得到某一层的一个资源后，只能再申请在较高层的资源；
    • 一个进程要释放某一层的一个资源，必须先释放所占用的较高层的资源；
    • 对于同一层的资源，只能一个一个地占有。

6.6.3 死锁的避免

在为申请者分配资源前先测试系统状态，若把资源分配给申请者会产生死锁的话，则拒绝分配，否则接受申请，分配资源

==银行家算法==：检查申请者对资源的最大需求量，如果现存的资源可以满足它的最大需求量就允许当前的申请。

  • 给定四个集合：\(R、V、C、A\)，分别表示资源总数、当前可用资源总数、进程声称需要的最大资源数、已经分配给进程的资源数
  • 如果可以找到一个进程序列，按照该进程序列去分配资源，可以满足所有资源的需要，则称系统处于安全性状态

6.6.4 死锁的检测

定时运行一个”死锁检测“程序，判断系统内是否已出现死锁，若检测到死锁则设法加以解除

  • 建立两张表：等待资源表和占用资源表
  • 列出所有的”等待占用关系“
  • 用Warshall传递闭包算法检测是否有死锁发生
  • 解决方法（死锁是一个小概率事件）
    • 重新执行
    • 设置 校验点，回退到校验点开始执行
nju-course-review
#OS
并发程序设计
http://example.com/2023/02/10/nju-course-review-notes/os/concurrent-programming/
作者
zhc
发布于
2023年2月10日
许可协议