清华大学操作系统课程笔记:同步互斥

本文已收录于 清华大学操作系统课程笔记 系列,共计 3 篇,本篇是第 2 篇

同步互斥

并发多线程,如果不用锁的话,每次运行结果都可能不同。

如果对多并发进程之间要求每次结果应该一样,就需要考虑同步互斥问题;有时候却还需要多进程不同运行时候的结果不一样,例如在通信的时候,就期望不同,这时候就不需要考虑这种问题。

这就会出现间歇性问题。但进程并发执行有很多好处,我们不能抛弃它。

进程并发的好处

好处一:共享资源

好处二:提高速度:IO和CPU计算可以重叠。多处理机执行。

好处三:模块化:多个进程完成一个功能。

并发 创建进程 时的标志分配

这是我们所期望的结果。下面是可能出现的一种错误:

出现了错误,分配的进程pid相同

然后进程B执行 INC Reg1,next_pid变为101

切换到进程A,执行INC reg1,next_pid变为101。

我们发现,next_pid被赋值了两次

原子操作

同步问题与解决方案

下面来解决原子性问题。举个例子:

如何解决?

上面这种办法也行,但似乎傻fufu的

方案一:

如果是计算机的思维来看:

进程A发现现在没面包也没便签,这时候B来了,他也看见没有面包没有便签,这时候A出门买面包并留下标签了。B接下来也离开了去买面包留下便签。——最后md… …留下两个便签,买回来两个面包。

方案二:

哈哈哈哈,都不买了。

方案三:

这下倒好,都不检查有面包没,就直接结束了。。。(双方都认为对方去买)

方案四:

这种方法是有效的。虽然方法是有效的,但很复杂。例如如果有更多的进程怎么办?md … …这问题更复杂。还有个缺点就是A一直在等待,它没法去做其他事。

方案五:

互斥:仅有一个进程占用资源。

死锁:多个进程各自占用部分资源,形成循环等待。

饥饿:

临界区 方法

我怎么感觉临界区的概念有点像铁路上的闭塞区间。

临界区的访问规则:

(1)空闲让进:当无进程处于临界区,表明临界资源处于空闲状态,允许请求进去临界区的进程进去临界区

(2)忙则等待:当有进程处于临界区,表明临界资源正在访问,其他请求进入临界区的进程必须等待。

(3)有限等待:应使在等待的进程在有限的事件内进入自己的临界区,避免”死等”状态

(4)让权等待:当进程不能进入自己的临界区,应立即释放处理机,以避免进入”忙等”状态

下面介绍三类临界区的实现方法,分别是禁用中断、软件方法、更高级的抽象方法

临界区的实现方法 – 禁用中断

基本思路是:第二个进程发现临界区被上锁了,就直接让第二个进程陷入内核态去等待。

在计算机中,目前是不能不用,才会用,是下下策

临界区的实现方法 -软件办法

暂时略… …

临界区的实现方法 -更高级的抽象办法

锁:抽象的数据结构

中断禁用、原子操作指令。

原子操作指令:CPU底层硬件的实现。

内部基于原子操作指令,是CPU所提供的原子操作指令——这一部分请参考CPU自制实验

确保不会出现 部分执行 的情况。

(这里的原子操作指令,,我没懂。等回头看看系统结构视频里的同步互斥。感觉这里应该更偏近底层的东西,可能是纯硬件实现的吧。)

解答:确实是,在CPU指令集中会将这三个指令糅合在一起,确保原子性操作,中间不会暂停。

基于上面两个原子指令,TS指令,我们可以实现锁。接下来先实现自旋锁。

什么是自旋锁?

第二个进程对第一个进程的独占区想要进行操作的时候发现独占区的二进制变量被定义为锁上了,那么第二个进程就会通过while语句不断的询问判断这个独占区是否被解锁。CPU不会将第二个进程放置在内核态,而是一直在用户态运行。

实现自旋锁

自旋锁需要语言层面支持原子操作,也就是说不能在我上锁过程中还会有进程来打断我。这一部分的实现是基于CPU底层的交换指令的,这部分等我写CPU的时候再来看看——参考自制CPU实验。

作者: 高志远

高志远,23岁,男生,毕业于上海杉达学院电子商务系。

发表评论

邮箱地址不会被公开。