【9. 同步与互斥】

在这里插入图片描述

?作者简介:?

c

+

+

,

g

o

,

p

y

t

h

o

n

,

目前熟悉

c

+

+

，

g

o

语言，数据库，网络编程，了解分布式等相关内容

\textcolor{orange}{博主在读机器人研究生，目前研一。对计算机后端感兴趣，喜欢c++,go,python,目前熟悉c++，go语言，数据库，网络编程，了解分布式等相关内容}

$博主在读机器人研究生，目前研一。对计算机后端感兴趣，喜欢 c + +, g o, p y t h o n, 目前熟悉 c + + ， g o 语言，数据库，网络编程，了解分布式等相关内容$

?

\textcolor{gray}{个人主页：}

$个人主页：$

小呆鸟_coding

?

:

\textcolor{gray}{支持:}

$支持 :$

\textcolor{green}{如果觉得博主的文章还不错或者您用得到的话，可以免费的关注一下博主，如果三连收藏支持就更好啦}

$如果觉得博主的文章还不错或者您用得到的话，可以免费的关注一下博主，如果三连收藏支持就更好啦$

?

\textcolor{green}{就是给予我最大的支持！}

$就是给予我最大的支持！$

?

?本文摘要?

本专栏主要是讲解操作系统的相关知识本文主要讲解同步与互斥

文章目录

?同步与互斥

?1. 背景

?2. 一些概念（Part 1）

?3. 一些概念（Part 2）

?4. 一些概念（Part 3）

?5. 临界区

?5.1 方法1：禁用硬件中断

?5.2 方法2：基于软件的解决方法

?5.3 方法3：更高级的抽象

?5.3.1 现代操作系统提供的方法

?6. 总结

清华操作系统系列文章：可面试可复习

1. 操作系统—概述


2. 操作系统—中断、异常、系统调用


3. 操作系统—物理内存管理


4. 操作系统—非连续内存分配


5. 虚拟内存管理


6. 操作系统—虚拟内存管理技术页面置换算法


7. 进程管理


8. 调度算法


9. 同步与互斥


10. 信号量和管程


11. 死锁和进程通信


12. 文件系统管理

?同步与互斥

?1. 背景

一些概念
临界区
方法1：禁用硬件中断
方法2：基于软件的解决方法
方法3：更高级的抽象

到目前为止

多道程序设计
: 现代操作系统的重要特性
并行很有用(为什么?) 提示:
- 多个并发实体: CPU IO 用户等
进程,线程
: 操作系统抽象出来用于支持多道程序设计
CPU调度
: 实现多道程序设计的机制
调度算法: 不同的策略

如果资源处理不当，会发生饥饿和死锁等，出现一系列问题，跟调度有关

独立的线程:

不和其他线程共享资源或状态
确定性: 输入状态决定结果
可重现: 能够重现起始条件, IO
调度顺序不重要

合作线程:

在多个线程中共享状态
不确定性（对于单个进程而言，执行时间不确定，可能会被其他进程抢占）
不可重现

不确定性和不可重现意味着bug可能是间歇性发生的

进程,线程;计算机,设备需要合作

合作优点:：

优点1：共享资源

一台电脑,多个用户

一个银行存款余额,多台ATM机

嵌入式系统

优点2：加速

IO操作和计算可以重叠

多处理器

优点3：模块化

将大程序分解成小程序

以编译器为例， gcc会调用cpp,cc1,cc2,as,ld

使系统易于扩展

在这里插入图片描述

将
next_pid
赋给
寄存器1
（将内存中的内容加载到寄存器中）
store
将寄存器中的内容存到内存中，将
寄存器1
中的内容存到
new_pid
这个里面(此时
new_pid
具有了
next_pid
的值)

在这里插入图片描述

进程执行的时候会保存寄存器的值在自己的堆栈里
进程切换会把进程的资源保存起来，切回来时，再把资源恢复回去
恢复进程1的上下文

无论多个线程的指令序列怎样交替执行,程序都必须正常工作

多线程程序具有不确定性和不可重现的特点

不经过专门设计,调试难度很高

不确定性要求并行程序的正确性

先思考清楚问题,把程序的行为设计清楚

切忌给予着手编写代码,碰到问题再调试

同步互斥就是解决上述不确定，不重现问题

?2. 一些概念（Part 1）

前面的现象称为
Race Condition
(竞态条件)

系统缺陷: 结果依赖于并发执行或者时间的顺序,时间

不确定性
不可重现

怎么样避免竞态?

让指令不被打断
Atomic Operator(原子操作)

解决办法（原子操作）

原子操作是指一次不存在任何终端或者失败的执行
- 该执行成功结束
- 或者根本没有执行
- 并且不应发生任何部分执行的状态
实际上操作往往不是原子的
- 有些看上去是原子操作,实际上不是
- 连x++这样的简单语句,实际上是由三条指令构成的
- 有时候甚至连单条假期指令都不是原子的
  - Pipeline,super-scalar,out-of-order,pape fault

实例

load和store是原子操作，但是++不是原子操作
死锁：当俩个进程都拥有一定的资源，同时还需要其他共享资源时，俩个进程相互等待，进程A等待进程B的资源,进程B等待进程A的资源

?3. 一些概念（Part 2）

举例

在这里插入图片描述

在这里插入图片描述

交换一下顺序

?4. 一些概念（Part 3）

为note贴上标签，指定是谁留下的纸条，仍然会出现问题，当进程A留下标签后，切换到进程B，也会留下标签，此时结果就是都没有买面包

在这里插入图片描述

设置不同的控制逻辑

可以解决，但是太复杂

在这里插入图片描述

临界区：
只允许一个进程去访问临界区的代码，这个代码主要对一起共享的资源进行读操作或写操作，如果有一个程序在临界区执行了，其他程序就需要等地
互斥：
确保只有一个程序在临界区叫互斥

在这里插入图片描述

解决办法

在这里插入图片描述

?5. 临界区

互斥
: 同一时间临界区中最多存在一个线程
Progress
: 如果一个线程想要进入临界区,那么它最终会成功
有限等待
: 如果一个线程i处于入口区,那么在i的请求被接受之前,其他线程进入临界区的时间是有限制的
无忙等待(可选)
: 如果一个进程在等待进入临界区,那么在它可以进入之前会被挂起

?5.1 方法1：禁用硬件中断

中断除了响应硬件事件之外，中断还会使得进程切换，这也就会导致死锁和饥饿等问题

时钟中断即使当前程序在执行，也会打断该程序，OS完成调度，切换到其他进程

没有中断,没有上下文切换,因此没有并发
- 硬件将中断处理延迟到中断被启用之后
- 大多数现代计算机体系结构都提供指令来完成
进入临界区
- 禁用中断
离开临界区
- 开启中断

缺点

对于多CPU是有限制的，因为一个CPU执行屏蔽中断时，他只会中断它自己的，并不会中断其他CPU的中断，其他CPU还是会继续执行
受制于临界区的执行时间，，对整个系统效率会产生影响，不适合多CPU

?5.2 方法2：基于软件的解决方法

在这里插入图片描述

进程1和进程2只能交替进行，一旦有一个程序退出，那么另一个程序下次还想进入临界区，那么它一直等待，一直进不去

缺点

满足互斥但是不满足前进

改进

无法满足互斥

在这里插入图片描述

将flag[i]=1,放在前面，此时满足互斥但是存在死锁

在这里插入图片描述

正确方法
:把前面的方法综合一下
满足进程Pi和Pj之间互斥的经典的基于软件的解决方法(1981年)
使用两个共享数据项
- int turn; //指示该谁进入临界区
- bool flag[]; //指示进程是否准备好进入临界区
进入临界区:

flag[i] = true;
turn = j;
while(flag[j] && turn == j);

退出临界区

flag[i] = false;

实例

do{
	flag[i] = true;
	turn = j;
	while(flag[j] && turn == j);
	CRITICAL SECTION
	flag[i] = false;
	REMAINDER SECTION
}while(true);

Bakery 算法(N个进程的临界区)

进入临界区之前,进程接收一个数字
得到的数字最小的进入临界区
如果进程Pi和Pj收到相同的数字,那么如果i<j,Pi先进入临界区,否则Pj先进入临界区
编号方案总是按照枚举的增加顺序生成数字

俩个窗口，很多人去窗口取钱，首先取票号，当俩个人取的票号一样时，此时比较身份证，看谁的身份证小则优先取钱。

总结

Dekker算法(1965):
第一个针对双线程例子的正确解决方案

Bakery算法(1979):
针对n线程的临界区问题解决方案

复杂:

需要两个进程的共享数据项

需要忙等待:

浪费CPU时间

没有硬件保证的情况下无真正的软件解决方案:

Perterson算法需要原子的LOAD和STORE指令

?5.3 方法3：更高级的抽象

硬件提供了一些原语

像中断禁用, 原子操作指令等
大多数现代体系结构都这样

操作系统提供更高级的编程抽象来简化并行编程

例如,锁,信号量
从硬件原语中构建

锁是一个抽象的数据结构

一个二进制状态(锁定,解锁),两种方法
Lock::Acquire() 锁被释放前一直等待,然后得到锁
Lock::Release() 锁释放,唤醒任何等待的进程

使用锁来编写临界区

前面的例子变得简单起来:

lock_next_pid->Acquire();
new_pid = next_pid++;
lock_next_pid->Release();

?5.3.1 现代操作系统提供的方法

大多数现代体系结构都提供特殊的原子操作指令

通过特殊的内存访问电路
针对单处理器和多处理器

Test-and-Set 测试和置位

从内存中读取值
测试该值是否为1(然后返回真或假)
内存值设置为1

交换

交换内存中的两个值

这俩个程序，虽然由多条指令完成，但是被封装成了机器指令，意味着在执行这三条指令的时候，不允许打断

bool TestandSet(bool *target){
		bool rv = *target;
		*target = true;
		return rv;
}

void Exchange(bool *a, bool *b){
		bool tmp = *a;
		*a = *b;
		*b = tmp;
}

不止适用于俩个进程，也适用于多个进程，而且多个进程，进入临界区与退出临界区的操作步骤是一样的

在这里插入图片描述

问题

在这里插入图片描述

在这里插入图片描述

解决办法1：使用
test-and-set

当一个进程发现自己进不了临界区，需要等待时，可以让该进程阻塞睡眠，将该进程挂在队列中去,把CPU让出来，给其他进程使用，当之前的进程，退出临界区后，他会唤醒睡眠的进程
如果临界区很短，则使用忙等待，不需要进行上下文切换，上下文切换开销相对大
如果临界区很长，开销远远大于上下文切换，选择无忙等待

解决办法2：使用
exchange

共享数据（初始化为0）
int lock = 0;

线程Ti
	int key:
	do {
		key = 1;
		while (key == 1) exchange(lock, key);
			critical section
		lock = 0;
			remainder section
		}

优点

适用于单处理器或者共享主存的多处理器中任意数量的进程
简单并且容易证明
可以用于支持多临界区

缺点

忙等待消耗处理器时间
当进程离开临界区并且多个进程在等待的时候可能导致饥饿
死锁
- 如果一个低优先级的进程拥有临界区并且一个高优先级进程也需求，那么高优先级进程会获得处理器并等待临界区（使得高优先级进程忙等待，使得低优先级进程无法释放锁）

?6. 总结

锁是更高等级的编程抽象
- 互斥可以使用锁来实现
- 通常需要一定等级的硬件支持
常用的三种实现方法
- 禁用中断(仅限于单处理器)
- 软件方法(复杂)
- 原子操作指令(单处理器或多处理器均可)——最常用
可选的实现内容:
- 有忙等待
- 无忙等待

原文链接：https://blog.csdn.net/weixin_45043334/article/details/126477243

文章目录

?同步与互斥

?1. 背景

?2. 一些概念（Part 1）

?3. 一些概念（Part 2）

?4. 一些概念（Part 3）

?5. 临界区

?5.1 方法1：禁用硬件中断

?5.2 方法2：基于软件的解决方法

?5.3 方法3：更高级的抽象

?5.3.1 现代操作系统提供的方法

?6. 总结

你可能也喜欢