操作系统3-并发性

Posted on

概念

原子操作：一个函数或者动作，由一个或多个指令序列实现，

  • 对外不可见，没有其他进程可以看到其中间状态或者中断这个操作
  • 保证指令序列要么都执行，要么都不执行
  • 保证了并发进程的隔离

同步：为了完成任务而建立的多个进程，这些进程为了需要在某些位置上协调工作而等待，传递信息而产生的制约关系

  • 空闲让进：没有进程处于临界区时，可以允许一个请求进入临界区
  • 忙则等待：已有进程进入临界区时，其他试图进入临界区的进程必须等待
  • 有限等待：对要求访问临界资源的进程，保证要在有限时间内进入临界区
  • 让权等待：当进程不能进入临界区时，应该释放处理机

互斥：当一个进程在临界区访问共享资源时，其他进程不能进入临界区访问共享资源
临界区：进程将访问共享资源的一段代码

  • 一个进程在临界区运行时，另一个进程无法进入临界区

  • 一次只有一个程序在临界区

死锁：多个进程相互等待导致都不能执行
活锁：进程为像一个其他进程的变化，持续改变自己的状态，但不做有用的工作
竞争：多个进程读写一个共享变量，该变量的最终指依赖它们的相对调度
饥饿：进程已经完全具备了了执行条件，但是得不到CPU资源

进程并发面临问题

  • 忙等：没有执行有用的事情但是一直占用处理机，违背了让权等待的原则；
  • 永久阻塞：需要得到临界资源的进程永远得不到资源，违背了有限等待的原则；
  • 死锁：每个进程误以为对方进入了临界区，使自己处于阻塞
  • 互斥礼让：代表进入临界资源区的标志为不断的重置和检查，重置序列无限延伸，任何进程不能进入自己的临界区

硬件方法实现互斥和同步

中断屏蔽

  • 利用开关中断指令实现，类似于原语
  • 即先关中断，关中断后即不允许当前进程被中断，也必然不会发生进程切换，然后进入临界区，直到当前进程访问完临界区，再执行开中断指令，才有可能有别的进程上处理机访问临界区。
  • 简单高效，但是不适合多处理机，只适用于操作系统内核进程，不适合用户进程

TestAndSet，Swap(TS指令/TSL指令/Swap指令)

  • TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。相比软件实现方法，TSL 指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。
  • 实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞
  • 适用于多处理机环境
  • 不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”

整形信号量

将可用的资源数定义为一个整型量$S$，初始化后可通过两个原子操作访问

  • wait(S):P操作,while(S<=0);S—-;
  • signal(S):V操作,`S++
    整形信号量不遵循让权等待原则；

记录型信号量

由两部分构成：

  • 代表资源数目的整型变量Value
  • 表示所有等待进程的进程链表L
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct Semaphore {
	int Value;
	List_of_Process L;
};
void Wait(Semaphore s){
    s.Value --;
    if(s.Value < 0){
    	L.push(now_process);
        block(now_process);
    }
}
void Signal(Semaphore s){
    s.Value ++;
    if(s.Value <= 0 ) {
        next_process = L.top();
        wakeup(next_process);
    }
}

当Value初值为1，表示只允许一个进程访问临界资源，转化为互斥信号量（二元信号量）；

简单说明互斥锁和二元信号量的区别：

  • 为互斥量加锁和解锁的进程只能是同一进程；
  • 可能有某个进程对二元信号量加锁，另一个进程为其解锁；

一般来说，对于多个进程互斥访问临界资源的情况，每个进程应该都要设计代表访问临界资源的锁；

1
2
3
4
5
6
7
8
9
10
Semaphore mutex(1);
void Process1{
	// 申请访问其他资源
	
	P(mutex); // 申请进入临界区
	// Critical Section 临界区代码
	V(mutex); // 释放临界区资源
	
	// 释放已申请的其余资源
}

进一步还可以利用信号量设计进程间的前趋关系；

AND信号量

将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。
对临界资源的分配采用原子操作的方式；

信号量集

对每一类资源，设定一个下限值$t$和需求单位值$d$；

1
2
3
4
5
Swait(S1, t1, d1, …, Sn, tn, dn)
 	if ( S1≥t1 and … and Sn≥tn )
 	for  ( i=1;i<=n; i++)
 		Si =Si-di;
 	else
  • Swait(S, d, d) 此时在信号量集中只有一个信号量$S$， 但允许它每次申请d个资源，当现有资源数少于d时，不予分配;
  • Swait(S, 1, 1) 此时的信号量集已退化为一般的记录型信号量($S＞1$时)或互斥信号量($S=1$时);
  • Swait(S, 1, 0)这是一种很特殊且很有用的信号量 操作。当$S≥1$时，允许多个进程进入某特定区；当$S$变为0后， 将阻止任何进程进入特定区。换言之，它相当于一个可控开关。

管程Monitor

管程是由一个或多个过程，一个初始化序列和局部数据组成的软件模块

  • 局部变量数据只能被管程的过程访问，外部过程无法访问
  • 一个进程通过调用管程的一个过程进入管程，设计一个入口，进入管程之前先进入管程的待进入队列中；
  • 只能有一个进程在管程中执行，其他调用管程的进程将被阻塞；

image-20241026152806438

管程通过条件变量支持同步,其原子操作和普通的信号量不同；

  • cwait(c): 调用进程的执行 在条件c阻塞，管程可以被另一个进程使用；
  • csignal(c)：恢复在cwait(c)之后因为某些条件被阻塞的进程；

在一个进程在管程中时，因为某种原因，这个进程发送cwait(x)将自己暂时阻塞在条件x上，此时加入条件x的条件队列，之后这个进程等待条件x的改变，以重新进入管程的待进入队列中，若进程发现条件x真的发生了改变，则发送csignal(x)通知相应的条件队列条件已经改变；

Producer-Consumer Problem

描述

  • 有一个或多个生产者生产某种资源，放入缓冲池
  • 有一个消费者从缓冲池读取资源，每次读取一项
  • 任何时候仅有一个生产者/消费者可以访问缓冲池，
  • 缓冲池已满时，生产者不再往其中添加资源；
  • 缓冲池为空时，消费者不会从中移走资源；

信号量实现

  • 利用互斥信号量mutex实现对缓冲池的互斥使用
  • 利用信号量empty full表示缓冲池中空区和满区的数量；

image-20241026162308732

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
size_t n;
Semaphore mutex(1);
Semaphore full(0), empty(n);
Item Buffer[n];
int in=0;
int out=0;

void append(Item v){
	Buffer[in] = v;
    in = (in+1)%n;
}
Item take(){
    v = Buffer[out];
    out = (out+1)%n;
    return v;
}

void Producer(){
    while(true) {
        v = produce();
        
        P(empty);
        P(mutex);
        append(v);
        V(mutex);
        V(empty);
    }
}
void Consumer(){
    while(true){
        P(full);
        P(mutex);
        v = take();
        V(mutex);
        V(full);
        
        comsume(v);
    }
}

对于一系列P操作和V操作，也可以用AND信号量实现，不过注意，对P操作的顺序不能颠倒，否则将可能导致死锁；

Reader-Writer Problem

描述

  • 多个进程对同一个文件进行读写
  • 不能同时写文件
  • 不能同时读和写文件
  • 可以同时读文件

信号量实现

  • 设置写锁Wmutex,由于最多有一个进程在写，因此这应该是一个互斥信号量
  • 设置读锁Rmutex，用于记录目前在读文件的进程数ReaderCnt，这些进程应该互斥地修改它；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Semaphore Rmutex(1)
Semaphore Wmutex(1);
int ReaderCnt = 0;

void Reader(file) {
	P(Rmutex);
    if(ReaderCnt == 0) P(Wmutex);
 	ReaderCnt ++;
    V(Rmutex);
    
    open(file);
    read(file);
    close(file);
    
    P(Rmutex);
    ReaderCnt --;
    if(ReaderCnt == 0) V(Wmutex);
    V(Rmutex);
}

void Writer(file) {
    P(Wmutex);
    
    open(file);
    write(file);
    close(file);
    
    V(Wmutex);
}

死锁

哲学家进餐问题

  • 5个哲学家坐在圆桌，他们中间穿插5只筷子
  • 哲学家进餐必须同时具备左边和右边的筷子
  • 一只筷子在同一时刻只能由一位哲学家使用，
  • 哲学家在进餐完毕后必须将筷子放回原处，然后思考哲学问题；

一般我们将5只筷子设置为5个信号量，哲学家进餐前默认先拿起左边的筷子，再拿起右边的筷子后，进餐，完毕后先放下右手的筷子，再放下左手的筷子，然后思考或等待下一次进餐；

注意：

假如五位哲学家同时饥饿而都拿起的左边的筷子，就会使代表筷子的5个信号量同时置0，这时他们试图拿起右边的筷子时，都因为相互等待二陷入死锁；

可以进行如下的改进策略：

  • 限制并发量：至多允许4个哲学家同时进餐
  • 解除环路等待：指定一位哲学家必须先拿起右边的筷子
  • 恢复策略：死锁发生时，指定一位哲学家放下自己的筷子；
  • 检测策略：哲学家进餐前，同时申请两只筷子；
  • 管程优化：每次只有一个进程进入管程

产生原因

  • 竞争资源：资源包括可剥夺资源和非剥夺性资源，一般是竞争非剥夺性资源，竞争临时性资源引起；
  • 进程间推进顺序不当；

充分必要条件

  1. 互斥条件：至少有一个资源是非剥夺性的
  2. 请求并保持条件：进程因请求新的资源而保持对已有资源的占有
  3. 不可剥夺条件：已获得的资源在未使用完之前，不能被其他进程抢占
  4. 环路等待条件：存在一组进程，使得每个进程都在等待其他进程所持有的资源

注意，前三者是死锁发生的必要条件，而非充分的；

预防死锁

预防死锁发生的可能（一般不会禁止互斥条件，如果操作系统实现了互斥的话）

  • 预防请求并保持条件
    • 进程在执行前，一次申请完执行过程中可能用到的所有资源；
  • 预防不可剥夺条件
    • 进程已占用一些资源，但后续资源得不到满足，必须释放已经占用的资源；
    • 高优先级进程申请被低优先级进程占用的资源，系统将后者资源抢占，分配给前者；
  • 预防环路等待条件
    • 将资源进行排序（定义资源的线性顺序），若进程获得资源$R_i$，后续资源序号只能都大于或都小于$i$;

注意，预防死锁可能会导致资源的低效使用和低效的进程执行

避免死锁

死锁避免允许三个必要条件的发生，但是明智的选择确保不会到达死锁点，因此允许了更多的进程并发；

安全状态
系统能找到进程的执行序列，为每个进程分配所需资源，直到每个进程的最大需求 ，使得每个进程都可以顺利完成

  • 允许进程动态地申请资源
  • 分配之前检查会不会导致系统进入不安全的状态

考虑一个有$n$个进程，$m$个不同类型资源的系统，定义

1
2
3
4
5
6
struct state {
	int resource[m]; 		// 系统中每种资源的总量，向量R
    int avalaible[m];		// 未分配给进程的每种资源的总量,向量V
    int claim[n][m];		// 进程i对资源j的最大需求,矩阵C
    int allocation[n][m];	// 	系统为进程i分配资源j的数量,矩阵A
}

不难看出以下关系成立：

  • 对于每类资源，要么可用，要么已被分配：$\forall j,R_j=V_j+\sum_{i=1}^n A_{ij}$
  • 任何进程对任何资源的请求不能超过这个系统中的资源总量：$C_{ij}\le R_i$
  • 任何进程得到的资源数不会超过最开始声明得到此资源的最大数量：$A_{ij}\le C_{ij}$
  • 启动新进程$P_{n+1}$的充分必要条件：$\forall j,R_j\ge C_{(n+1)j}+\sum_{i=1}^n C_{ij}$

安全性检查算法

系统如果要将资源分配给进程$i$,必须满足：
$$
\forall j, C_{ij}-A_{ij}\le V_j
$$
那么只需要以此找到满足上述约束关系的进程，执行完成后释放，找到下一个满足的进程；

安全性检查算法描述如下：

  1. 设置工作向量work[m]:表示系统可提供给进程继续运行所需的各类资源的数目； finish[n]：表示系统是否有足够的资源分配给进程，使之运行完成；

  2. 初始化work := available finish := false

  3. 从满足finish[i]=false的进程集合找到满足上述约束条件的进程i

    • 若能找到，执行4
    • 若不能找到，执行5

  4. 进程i得到资源执行后，释放其资源，应该执行

    1
    2
    work[j] += allocation[i][j]
    finish[j] = true

    后，返回2

  5. 若所有进程的finish值均为true，则说明系统安全，否则系统处于不安全状态；

银行家算法

某一时刻收到进程i的对系统资源的请求向量request_i；

按照以下步骤对系统资源状态进行检查：

  1. 检查request_i[j]<=claim[i][j]-allocation[i][j]

    • 真，则进行2；
    • 否则认为系统出错，资源数不满足其先决条件；

  2. 检查request_i[j]<=available[j]

    • 真，则进行3；
    • 否则认为尚无足够的资源，进程i必须等待；

  3. 系统尝试为进程i分配资源，状态修改如下：

    1
    2
    available[j] -= request_i[j];
    allocation[i][j] += request_i[j];

  4. 系统执行安全性检查算法

    • 若通过检查，则正式分配资源给进程i
    • 否则恢复原来的资源状态，宣布让进程i等待；

检测和解除死锁

额外定义请求矩阵Q[n][m]，表示进程i请求资源j的数量；

维护一个标记表L,最初所有进程都是未标记的；

检测死锁按照以下步骤进行：

  1. 标记allocation矩阵中一行全为0的进程；
  2. 初始化临时向量w := available
  3. 尝试查找下标i，使进程i当前未被标记，且其请求小于w;
    • 若查找失败，终止算法
  4. 进程i加入标记表L,更新w[k] += allocation[i][k]
  5. 当且仅当算法结束时存在未被标记的进程时，意味着死锁存在于这些进程之中

解除死锁的思路比较简单，以下是常见的设计：

  • 撤销所有死锁的进程：这是操作系统最常用的办法；
  • 死锁进程回滚到某些检查点，重新启动
  • 连续撤销死锁进程直到死锁不存在
  • 连续抢占资源直到不存在死锁

进程间通信

对于PV操作可以用于进程的同步和互斥，属于低级进程通信，对网络进程通信和数据交换量较大的单机进程通信不适用；
进程间通信可以利用共享存储器/消息传递/管道实现；

共享存储器

  • 基于共享数据结构的通信方式：公用某一个数据结实现信息交换
  • 基于共享存储器的通信方式：划分一块存储空间作为公用

消息传递

  • 直接消息传递：多个进程利用系统调用相互发送消息；
    • 利用send，receive原语
    • 可能产生安全问题：消息丢失，对象假冒，消息篡改
    • 一般通信有三种情况：阻塞send+阻塞receiver，无阻塞send+阻塞receiver，无阻塞send+无阻塞receiver
  • 简介消息传递：不直接发送消息给接收者，而是发到某个共享空间
    • 接受者和发送者的关系不确定：一对一，多对多，一对多，多对一
    • 需要解决共享空间的所有权问题

管道

在UNIX中，一般采用半双工的方式工作；
利用pipe函数创建管道

1
2
# include <unistd.h>
int pipe(int fd[2]);

fd[1]的输出fd[0]的输入；创建成功返回0，失败返回-1；