B站 陈渝老师 清华大学
https://www.bilibili.com/video/av6538245?from=search&seid=436175425155932048
(1)计算机内有多个线程,有独立的线程,互相不影响,也有可能相互之间需要合作的线程。
-不和其他线程共享资源或状态
-确定性=>输入状态决定结果
-可重现=>能够重现起始条件,I/O
-调度顺序不重要
-在多个线程中共享状态
-不确定性
-不可重现
-不确定性和不可重现意味着bug可能是间歇性发生的
(2)为什么需要线程合作?
-一台电脑,多个用户
-一个银行存款余额,多台ATM机
-嵌入式系统(机器人控制:手臂和手的协调)
-1/0操作和计算可以重叠
-多处理器-将程序分成多个部分井行执行
-将大程序分解成小程序
以编译为例,gcc会调用cpp, cc1, cc2, as, ld
-使系统易于扩展
(3)线程并发引起的可能出现一个不确定性。举个例子
操作系统需要分配一个新的并且唯一的进程ID
因此在内核中,这个系统调用会运行
- new_pid=next_pid++ ; //共享的全局变量 原子操作?
- LOAD next_pid Reg1
- STORE Reg1 new_pid
- INC Reg1
- STORE Reg1 next_ pid
◆假设两个进程并发执行
如果next_pid等于100, 那么其中一个进程得到的ID应该是100,另一个进程 的ID应该是101,next_pid应该增加到102
(1)竞态条件 Race Condition
上述例子的现象称为竞态条件。
◆系统缺陷:结果依赖于并发执行或者事件的顺序/时间
➢不确定性
➢不可重现
◆怎样避免竞态?可以引入原子操作。
(2)原子操作 Atomic Operation
-该执行成功结束
-或者根本没有执行
-并且不应该发现任何部分执行的状态
-有些看上去是原子操作,实际上不是
-连x++这样的简单语句,实际上是由3条指令构成的
-有时候甚至连单条机器指令都不是原子的 Pipeline, super- scalar, out- of- order, page fault
第二个例子,假设内存读取和存储是原子的,但是加1和减1操作不是原子的。 因为线程共享数据段资源,可能会出现线程A:i++,接着调度B:i–,没有人赢。
(3)临界区、互斥、死锁、饥饿
(4)锁、解锁、死锁
例如,在冰箱上设置一个锁和钥匙( lock&key )
第三个例子,买太多面包问题:
-去买面包之前锁住冰箱并且拿走钥匙
-修复了“太多”的问题:要是有人想要果汁怎么办?
-可以改变“锁(lock)”的含义
-“锁(lock)”包含“等待(waiting)”
-互斥:同一时间临界区中最多存在一个线程
-Progress: 如果一个线程想要进入临界区,那么它最终会成功
-有限等待:如果一个线程处于入口区,那么在i的请求被接受之前其他线程进入临界区的时间是有限制的
-无忙等待(可选):如果一个进程在等待进入临界区,那么在它可以进入之前会被挂起。尽量不要忙等。
1.禁止硬件中断
2.基于软件的解决方案
3.更高级的抽象,基于硬件的原子操作指令
中断有使操作系统强制打断进程执行、完成进程切换的能力,可以在进入临界区前把中断屏蔽了,等线程出临界区再重新使能中断。
-没有中断,没有上下文切换,因此没有并发
-硬件将中断处理延迟到中断被启用之后
-大多数现代计算机体系结构都提供指令来完成
禁用中断
开启中断
缺点
在分布式系统中
线程i线程j
缺点:只能交替进行,才能保证另一个进程进去临界区
改进->用flag[]数组来
正确的解法:Peterson算法
除此之外还有两种算法。Dekker、Bakery。
Dekker进出入临界区相比于Peterson算法更复杂。感兴趣的同学课后再去了解。
软件来做的不足:开销、时间复杂性比较大
改进:基于硬件原子操作的高级抽象实现
-像中断禁用,原子操作指令等
-大多数现代体系结构都这样
-例如:锁,信号量
-从硬件原语中构建
-一个二进制状态(锁定/解锁),两种方法
-Lock::Acquire() -锁被释放前一直等待,然后得到锁
-Lock::Release() -释放锁,唤醒任何等待的进程
锁抽象怎么来实现:
-两个特殊的操作可以帮助互斥:Test-and-Set 或 交换。
大多数现代体系结构都提供特殊的原子操作指令
-通过特殊的内存访问电路
-针对单处理器和多处理器
Test- and -Set测试和置位
-从内存中读取值
-测试该值是否为1 (然后返回真或假)
-内存值设置为1
交换
-交换内存中的两个值
用上述两个操作来实现锁:
缺点:使用忙等待的锁
->就像上面使用test-and-set实现的锁一样
->线程在等待的时候消耗cpu周期
改进:等待的时候加入等待序列,进入睡眠
◆优点
-适用于单处理器或者共享主存的多处理器中任意数量的进程
-简单并且容易证明
-可以用于支持多临界区
◆缺点
-忙等待消耗处理器时间
-当进程离开临界区并且多个进程在等待的时候可能导致饥饿
-死锁 :如果一个低优先级的进程拥有临界区并且一个高优先级进程也需求,那么高优先级进程会获得处理器并等待临界区
总结
-互斥可以使用锁来实现
-通常需要一定等级的硬件支持
-禁用中断(仅限于单处理器)
-软件方法(复杂)
-原子操作指令(单处理器或多处理器均可)
-有忙等待
-无忙等待
目前,原子操作指令来完成这个的比较多。
参考资料:操作系统_清华大学(向勇、陈渝)
https://www.bilibili.com/video/BV1js411b7vg?from=search&seid=15059545862768601253
本文地址:https://blog.csdn.net/qq_38229259/article/details/107446437
如对本文有疑问, 点击进行留言回复!!
[杭电多校2020]第一场 1004 Distinct Sub-palindromes
Swift -- 将本地生成的UIImage进行持久化保存(存到文件中fileManager.createFile)
网友评论