并发性：互斥和同步

博主： Xherlock
发布时间：2022 年 04 月 07 日
750 次浏览
暂无评论
6146字数
分类：操作系统

# 并发性：互斥和同步

**并发相关术语**

* 原子操作：不可中断的一个或一系列操作
* 临界区（critical section）：一段代码，在这段代码中将访问共享资源，只允许一个进程在其中运行
* 死锁（deadlock）：两个或两个以上的进程因每个进程都在等待其他进程做完某些事情而不能继续执行的情形
* 活锁（livelock）：两个或两个以上的进程为响应其他进程的变化而持续改变自己的状态但不做有用的工作的情形
* 互斥：一个进程在临界区访问共享资源时，其他进程不能进入该临界区访问任何共享资源的情形
* 竞争条件：多个线程或进程在读写一个共享数据时，结果依赖于它们执行的相对时间的情形
* 饥饿：一个可运行进程尽管能继续执行，但被调度程序无线期地忽视，而不能被调度执行的情形

## 并发的原理

**并发的困难**

* 全局共享（eg：两个进程使用同一个全局变量，并且都对其执行读写操作，读写执行顺序十分关键）
* 资源分配最优化（eg：发生死锁）
* 定位程序错误

### 一个简单的例子

**字符回显程序**，输入字符返回显示器

~~~c
void echo()
{
    chin = getchar();
    chout = chin;
    putchar(chout);
}
~~~

情形一：单处理器多道程序设计系统共享过程echo

| Process P1        | Process P2        |
| ------------------- | ------------------- |
| chin = getchar(); |                   |
| chout = chin;     |                   |
|                   | chin = getchar(); |
|                   | chout = chin;     |
|                   | putchar(chout);   |
| putchar(chout);   |                   |

1. 进程P1调用echo，getchar返回x值存储在chin中后中断
2. 进程P2激活并调用echo，getchar返回y值存储在chin中后赋给chout，putchar使屏幕回显chout的值y
3. 进程P1恢复，此时chin中原来的值x已被写覆盖成y，回显也是y

**因此需要控制一次只有一个进程访问共享资源**

这样P2被激活后调用echo，由于P1仍然在echo中且处于阻塞态，所以P2也被堵塞，P1先恢复完成执行显示正确的x，P2其次恢复显示y

情形二：多处理器多道程序设计系统同样存在保护共享资源的问题

| Process P1        | Process P2        |
| ------------------- | ------------------- |
| chin = getchar(); |                   |
|                   | chin = getchar(); |
| chout = chin;     | chout = chin;     |
| putchar(chout);   |                   |
|                   | putchar(chout);   |

同情形一，y会覆盖P1的chout，两个输出都是y，也需要限定对共享资源的访问

### 竞争条件

发生在多个线程或进程在读写一个共享数据时，最终结果取决于多个进程的指令执行顺序

eg：在情形一中，P2在竞争中最后更新全局变量chout，决定了chout的最终值

### 操作系统关注的问题

1. 追踪不同的进程
2. 分配和回收资源（处理器时间、存储器、文件、I/O设备）
3. 保护数据和资源
4. **一个进程的功能和输出结果必须与执行速度无关**

### 进程的交互

* 互不知道：竞争
* 间接知道：共享某些对象（eg：一个I/O缓冲区）时表现出合作行为
* 直接知道：通过进程ID互相通信，合作完成某些活动

进程间的资源竞争：

* 互斥：一次一个程序在临界区
* 死锁：eg：假设两个进程P1、P2，两个资源R1、R2，每个进程都需要两个资源，此时R1分配给P1，R2分配给P2，每个进程都在等待另一个资源，并且在获得其他资源并完成工作前，都不会释放已拥有的资源，此时俩进程就发生死锁
* 饥饿：eg：假设进程P1、P2、P3都周期性访问资源R，此时P1拥有资源，P2、P3延迟，当P1退出临界区，资源被分配给P3，P3退出又分给了P1，轮流授予P1、P3访问权，P2被无限期地拒绝访问资源

### 互斥的要求

* 一次一个进程进入临界区
* 非临界区部分不干涉其他进程
* 无死锁或饥饿
* 临界区无进程，需要进入的进程立即进入
* 对相关进程的执行速度和处理器的数量无要求和限制
* 一个进程停留在临界区时间有限

## 互斥：软件方法

### Dekker算法

***first attempt：***

int turn=0；

![image-20220331113007351.png](http://xherlock.top/usr/uploads/2022/04/3116416086.png)

* 实现了互斥
* 进程交替执行，不灵活，对临界资源访问频率高的依赖访问频率低的进程
* 程序异常终止会导致了另一个进程被永久阻塞

***second attempt***

用一个数组记录进程的需求，禁止进程的状态被其他进程修改，访问资源时查询对方是否访问资源

![image-20220407124301630.png](http://xherlock.top/usr/uploads/2022/04/3215119032.png)

* 不能有效实现互斥，存在多进程进入临界区的情况

![image-20220407124901799.png](http://xherlock.top/usr/uploads/2022/04/554257298.png)

***third attempt***

在算法二基础上访问资源前改变对应的状态，发表请求使用资源的声明

![image-20220407125020546.png](http://xherlock.top/usr/uploads/2022/04/4230742701.png)

* 存在死锁：两个进程同时提起访问，flag都设为true，临界资源无法被访问

***fourth attempt***

在算法三基础上引入随机等待时间

![image-20220407125304985.png](http://xherlock.top/usr/uploads/2022/04/3146984917.png)

* 存在活锁

![image-20220407125412166.png](http://xherlock.top/usr/uploads/2022/04/2123425165.png)

***最终算法***

![image-20220322114105728.png](http://xherlock.top/usr/uploads/2022/04/3111839044.png)

![image-20220322114121253.png](http://xherlock.top/usr/uploads/2022/04/817560499.png)

![请输入图片描述](http://xherlock.top/usr/uploads/2022/04/2485730457.png)![image-20220322114130957.png](http://xherlock.top/usr/uploads/2022/04/2485730457.png)
精简算法(peterson)：

![image-20220407125548668.png](http://xherlock.top/usr/uploads/2022/04/141816305.png)

## 互斥：硬件支持

### 中断禁用

单处理机中，并发进程只能交替。一个进程在调用一个系统服务或被中断前，将一直运行，为保证互斥，只需保证一个进程不被中断即可

~~~c
while (true) {
    /* 禁用中断 */
    /* 临界区 */
    /* 启用中断 */
    /* 其余部分 */
}
~~~

缺点：只能交替运行，执行效率降低；且不能用于多处理器体系结构中

### 专用机器指令

机器指令必须在一个指令周期内完成，同时禁止其他指令对该指令所访问数据资源进行操作

优点：对并发进程数目无限制；简单容易实现；支持多临界区

缺点：存在忙时等待 ；可能饥饿；可能死锁

机器指令案例（by 王道）

![image-20220603101800282.png](http://xherlock.top/usr/uploads/2022/06/1639880446.png)

## 信号量（semaphores）

* 信号量：用于进程间传递信号的一个整数值，在其上可进行初始化、递减和递加（递减用于阻塞一个进程，递增用于接触一个进程的阻塞）

![image-20220401114423105.png](http://xherlock.top/usr/uploads/2022/04/178101191.png)
* 二元信号量：只取0、1的信号量

![image-20220401114535620.png](http://xherlock.top/usr/uploads/2022/04/3049821777.png)
* 互斥量：类似二元信号量，区别在于为其加锁（值设为0）的进程和为其解锁（值设为1）的进程必须为同一个进程
* 条件变量：一种数据类型，用于阻塞进程或线程，直到特定的条件为真

信号量需要初始化为非负数

semWait操作使信号量-1，值为负数则阻塞执行semWait的进程，否则继续执行

semSignal操作使信号量+1，值小于等于0，则被semWait操作阻塞的进程解除阻塞

**semWait和semSignal必须成对出现**，如果在一个进程内出现表示互斥，不同进程内出现表示同步

**信号量实现同步**（by 王道）

![image-20220603105142588.png](http://xherlock.top/usr/uploads/2022/06/2225941317.png)

信号量机制实现前驱关系（后面生产者/消费者问题会用到）

![image-20220603105636157.png](http://xherlock.top/usr/uploads/2022/06/2744852056.png)

### 互斥

![image-20220401173337165.png](http://xherlock.top/usr/uploads/2022/04/2866476366.png)

信号量一般初始化为1，这样第一个执行semWait的进程可立即进入临界区，并把s设为0；接着想进入临界区的进程，每个不成功的尝试都会使s减一；当最初的离开后，s+1，开始进一个被阻塞的进程

应用信号量方法：

* 确定进程数目
* 分析问题本质
* 定义信号量并初始化值
* 在进程中调用semWait和semSignal

### 生产者/消费者问题

一个生产者一个消费者，缓冲区可存放n个商品。如果缓冲区空了，消费者等待；如果缓冲区满了，生产者等待

使用信号量应用：

* 两个进程：生产者和消费者
* 关系：共享合作
* semaphore empty=n（表示生产者可以存放物品的数据，由消费者告诉生产者），product=0（可以消费商品的数量，由生产者告诉消费者）

若需要互斥访问（一次一个人访问缓冲区），加上semaphore  mutex=1#互斥锁

**关系分析**：

* 互斥：生产者进程之间、消费者进程之间、生产者和消费者之间
* 同步：生产者生产一个产品告诉消费者可以消费；消费者消耗一个产品告诉生产者有一个空的仓位

~~~c
semaphore mutex=1;
semaphore empty=n;
semaphore product=0;
void producer()
{
    while(true)
    {
        produce();
        semWait(empty);
        semWait(mutex);
        append();
        semSignal(mutex);
        semSignal(product);
    }
}
void consumer()
{
    while(true)
    {
        semWait(product);
        semWait(mutex);
        take();
        semSignal(mutex);
        semSignal(empty);
        consume();
    }
}
void main()
{
    parbegin(producer, consumer)
}
~~~

## 管程（monitors）

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

特点：

* 局部数据变量只能被管程的过程访问
* 一个进程通过调用管程的一个过程进入管程
* 在任何时候，只有一个进程在管程中执行

最后修改：2022 年 06 月 03 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

Reverse（十一）
浏览次数: 2629
Win11新机鼓捣记录
浏览次数: 2382
栈~数制转换
浏览次数: 1604
C++学习
浏览次数: 1603
Python实现文件管理系统（重命名和删除）
浏览次数: 1575

顶点软件
你写得非常清晰明了，让我很容易理解你的观点。
mars
博主你好，请问怎么知道的alloc函数属于Buffer下的方法...
lj
该评论仅登录用户及评论双方可见
Mr.Guan
:@(赞一个)
Typecho
欢迎加入 Typecho 大家族

嵌入式系统
浏览次数: 489
网络层（一）
浏览次数: 579
Sqli-labs学习4
浏览次数: 826
pytorch数据迁移、转换
浏览次数: 374
Python爬取菜价
浏览次数: 891

并发性：互斥和同步

Xherlock • 2022 年 04 月 07 日

# 并发性：互斥和同步

**并发相关术语**

## 并发的原理

**并发的困难**

### 一个简单的例子

**字符回显程序**，输入字符返回显示器

~~~c
void echo()
{
    chin = getchar();
    chout = chin;
    putchar(chout);
}
~~~

情形一：单处理器多道程序设计系统共享过程echo

**因此需要控制一次只有一个进程访问共享资源**

这样P2被激活后调用echo，由于P1仍然在echo中且处于阻塞态，所以P2也被堵塞，P1先恢复完成执行显示正确的x，P2其次恢复显示y

情形二：多处理器多道程序设计系统同样存在保护共享资源的问题

同情形一，y会覆盖P1的chout，两个输出都是y，也需要限定对共享资源的访问

### 竞争条件

发生在多个线程或进程在读写一个共享数据时，最终结果取决于多个进程的指令执行顺序

eg：在情形一中，P2在竞争中最后更新全局变量chout，决定了chout的最终值

### 操作系统关注的问题

1. 追踪不同的进程
2. 分配和回收资源（处理器时间、存储器、文件、I/O设备）
3. 保护数据和资源
4. **一个进程的功能和输出结果必须与执行速度无关**

### 进程的交互

* 互不知道：竞争
* 间接知道：共享某些对象（eg：一个I/O缓冲区）时表现出合作行为
* 直接知道：通过进程ID互相通信，合作完成某些活动

进程间的资源竞争：

### 互斥的要求

## 互斥：软件方法

### Dekker算法

***first attempt：***

int turn=0；

![image-20220331113007351.png](http://xherlock.top/usr/uploads/2022/04/3116416086.png)

* 实现了互斥
* 进程交替执行，不灵活，对临界资源访问频率高的依赖访问频率低的进程
* 程序异常终止会导致了另一个进程被永久阻塞

***second attempt***

用一个数组记录进程的需求，禁止进程的状态被其他进程修改，访问资源时查询对方是否访问资源

![image-20220407124301630.png](http://xherlock.top/usr/uploads/2022/04/3215119032.png)

* 不能有效实现互斥，存在多进程进入临界区的情况

![image-20220407124901799.png](http://xherlock.top/usr/uploads/2022/04/554257298.png)

***third attempt***

在算法二基础上访问资源前改变对应的状态，发表请求使用资源的声明

![image-20220407125020546.png](http://xherlock.top/usr/uploads/2022/04/4230742701.png)

* 存在死锁：两个进程同时提起访问，flag都设为true，临界资源无法被访问

***fourth attempt***

在算法三基础上引入随机等待时间

![image-20220407125304985.png](http://xherlock.top/usr/uploads/2022/04/3146984917.png)

* 存在活锁

![image-20220407125412166.png](http://xherlock.top/usr/uploads/2022/04/2123425165.png)

***最终算法***

![image-20220322114105728.png](http://xherlock.top/usr/uploads/2022/04/3111839044.png)

![image-20220322114121253.png](http://xherlock.top/usr/uploads/2022/04/817560499.png)

![请输入图片描述](http://xherlock.top/usr/uploads/2022/04/2485730457.png)![image-20220322114130957.png](http://xherlock.top/usr/uploads/2022/04/2485730457.png)
精简算法(peterson)：

![image-20220407125548668.png](http://xherlock.top/usr/uploads/2022/04/141816305.png)

## 互斥：硬件支持

### 中断禁用

单处理机中，并发进程只能交替。一个进程在调用一个系统服务或被中断前，将一直运行，为保证互斥，只需保证一个进程不被中断即可

~~~c
while (true) {
    /* 禁用中断 */
    /* 临界区 */
    /* 启用中断 */
    /* 其余部分 */
}
~~~

缺点：只能交替运行，执行效率降低；且不能用于多处理器体系结构中

### 专用机器指令

机器指令必须在一个指令周期内完成，同时禁止其他指令对该指令所访问数据资源进行操作

优点：对并发进程数目无限制；简单容易实现；支持多临界区

缺点：存在忙时等待 ；可能饥饿；可能死锁

机器指令案例（by 王道）

![image-20220603101800282.png](http://xherlock.top/usr/uploads/2022/06/1639880446.png)

## 信号量（semaphores）

* 信号量：用于进程间传递信号的一个整数值，在其上可进行初始化、递减和递加（递减用于阻塞一个进程，递增用于接触一个进程的阻塞）

![image-20220401114423105.png](http://xherlock.top/usr/uploads/2022/04/178101191.png)
* 二元信号量：只取0、1的信号量

信号量需要初始化为非负数

semWait操作使信号量-1，值为负数则阻塞执行semWait的进程，否则继续执行

semSignal操作使信号量+1，值小于等于0，则被semWait操作阻塞的进程解除阻塞

**semWait和semSignal必须成对出现**，如果在一个进程内出现表示互斥，不同进程内出现表示同步

**信号量实现同步**（by 王道）

![image-20220603105142588.png](http://xherlock.top/usr/uploads/2022/06/2225941317.png)

信号量机制实现前驱关系（后面生产者/消费者问题会用到）

![image-20220603105636157.png](http://xherlock.top/usr/uploads/2022/06/2744852056.png)

### 互斥

![image-20220401173337165.png](http://xherlock.top/usr/uploads/2022/04/2866476366.png)

应用信号量方法：

* 确定进程数目
* 分析问题本质
* 定义信号量并初始化值
* 在进程中调用semWait和semSignal

### 生产者/消费者问题

一个生产者一个消费者，缓冲区可存放n个商品。如果缓冲区空了，消费者等待；如果缓冲区满了，生产者等待

使用信号量应用：

若需要互斥访问（一次一个人访问缓冲区），加上semaphore  mutex=1#互斥锁

**关系分析**：

## 管程（monitors）

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

特点：

* 局部数据变量只能被管程的过程访问
* 一个进程通过调用管程的一个过程进入管程
* 在任何时候，只有一个进程在管程中执行

发表评论 取消回复

并发性：互斥和同步

发表评论取消回复