海森堡bug:不可重现的bug。如果程序重启,bug就可能不再出现。
可能原因:
- 调试器本身影响了bug的产生;
- 编译器的不恰当优化;
- 未初始化变量的值;
- 时间敏感的bug:常在多进程/多线程并发的程序发生
对共享变量的并发写操作(读没关系),有必要互斥共享变量,如果不做相关保护措施,会有极大的可能造成bug
在实现同步之前,进/线程:
- 可能在任何时间被暂停与重启;
- 一旦暂停,其等待的时间未知;
- 多个进/线程可能以任意顺序运行;
进程同步的基本概念
- 竞争条件(race condition):多个进程在操作一个共享数据时,结果取决于多个进程的指令执行顺序
- 同步( Synchronization ): 协调多个进程的执行次序,确保并发的进程之间按照一定的规则共享系统资源,很好的相互合作,使程序的执行具有可再现性。
- 互斥( Mutual Exclusion ):当某进/线程正在做某件事时,不允许其它进/线程也做这件事
- 临界资源(Critical Resource):操作系统中一次允许一个进程访问的资源
- 如:打印机、文件、全局变量……
- 对临界资源应采用互斥方式共享
- 临界区( Critical Section ): 一次只有一个进程以执行的那段代码。即进程中访问临界资源的那段程序。
- 实现了互斥,也就有了临界区
- 锁( Lock ): 防止其它进程进入的工具
- 进入临界区前上锁
- 离开后解锁
- 如果已有锁,则在临界区外等待
进程同步的准则
原子操作
所有动作要么全做,要么全不做,操作过程中不能被打断又称原语(Primitive)
实现互斥的软件方法
忙等: 不能进入临界区的进程,一直占用CPU等待进入
- 等待中的进程白白占用处理机周期
- 拿着锁的进程的时间被无效的等待进程占用
- 优先级反转(priority inversion)
例外:
- 在多核CPU系统中,对于只占用很少时间的临界区,忙等 反而可以节约上下文切换的开销。
Peterson算法
- 当Note && turn 的条件不满足,进入忙等
- 代码必然让线程PA,PB都至少执行到了给turn复制的一步(哪个线程还没到,另一个就会等待)
- 完成后,就是看谁先执行turn赋值,谁先进入临界区,另一个仍然在等待
- 先执行的线程完成后,收走自己的纸条,让另一个线程运行,实现了互斥
软件同步的局限
纯软件方法利用最低限度的原子操作支持(Load和Store),也可以实现同步,但是
- 算法的设计和实现都很困难
- 在现代计算机架构下可能失效
- 编译器/CPU可能使指令乱序执行(需内存屏障) 所以很少使用纯软件同步方法,多是操作系统配合硬件实现同步,封装成各个api函数给程序员使用,所以不能直接调用。
硬件同步
设法实现两个原语(原子操作)
Lock() – 加锁,当无人用锁时获得锁;若多人同时尝试拿锁,则只有一人能拿到,其余人等待;
Unlock() – 解锁,唤醒在等待的人
Lock(); //进入区 if (noPaper) { buy Paper; //临界区 } Unlock(); //退出区
需要硬件提供更多的原子操作。
关中断
进程切换
- 内因:进程做了某事(系统调用或异常),自己释 放了CPU
- 外因:中断导致内核介入,进程失去CPU
如果关闭了中断,无论内因外因均不再响应,则可以避开进程切换
关中断方案,又称屏蔽(mask)中断
问题
- 不能允许用户使用这种锁!只可能内核使用
- 由于临界区的代码运行的时间未知,不能保证实时性;更重要任务发生时,系统也无法响应(死循环关闭中断)
- 仅能关闭单个CPU,不适合多核CPU
读-修改-写型原子操作swap
可以用于多核处理器的指令
Test-and-Set
锁
上述硬件原语通常不直接给程序员使用,于是操作系统和高级语言将它们封装为各种接口,供程序员使用。最常见的一类工具就是“锁(locks)”。
- 锁是原子操作,多个进程同时lock,最终须依次执行
- 最先执行lock的进入临界区并加锁,后来的无法进入临界区
- 进不去的进程有两种选择:忙等,或睡眠
- 非忙等——互斥锁——重量级(悲观)锁
- 忙等——自旋锁——轻量级(乐观)锁
信号量
并发问题分为两类:
- 互斥(Mutual Exclusion):确保临界资源被互斥的使用
- 工具:锁(Lock)
- 程序员只需识别出临界区
- 竞争共享资源,用mutex=1,P、V操作成对出现
- 同步(Synchronization):确保进程按照期望的先后顺序运行
- 工具:条件变量(condition variable)
- 不满足条件的进程等待(wait),直到条件满足,才通知(signal)其执行
- 控制进程间的先后顺序,初值根据具体情况设置,P、V分开在不同的进程使用对每个约束设置一个信号量
信号量是一种抽象数据类型
- 由一个整形变量(Sem)和两个原子操作(P, V)组成
- P——wait()——等待,信号量值-1(可以负数)
- V——signal()——唤醒,信号量值+1
用法
- 实现进程互斥,信号量mutex
- 实现进程间前趋后继(又称同步)关系,可以让进程之间相互等待
生产者和消费者问题
问题描述:
- 一个或多个生产者将产品放入一个共享的缓冲区
- 多个消费者从缓冲区中取出使用
- 生产者和消费者之间并发运行,保持同步
以自动售货机为例,约束条件包括:
- 每次只允许一个人对售货机进行操作(互斥约束)
- 当饮料已售空,消费者必须等待生产者(同步约束)
- 当饮料已放满,生产者必须等待消费者(同步约束)
用信号量实现问题时的准则:
对每个约束条件,各使用一个单独的信号量
- Semaphore mutex; //互斥的约束
- Semaphore drinkSlots ; //消费者的约束
- Semaphore emptySlots; //生产者的约束
生产者和消费者的工作并不需要互斥。
生产者每次只能一个(互斥),消费者同样
因为buffer的容量只有1,PV操作在实现信号量同步,保持生产者消费者之间的关系时,也天然实现了互斥,最多只有一个访问共享条件。
- P表示等待这个条件
读写者问题
问题描述:
- 共享数据,有两类使用者
- 读者:只读取/查询数据
- 写者:修改数据
- 读-读允许:同一时刻,允许有多个读者同时读
- 读-写互斥:
- 当有读者在,写者不能写
- 当有写者在,读者不能读
- 写-写互斥:两个写者不能同时写
示例:访问查询型数据库,通常,读者的数量远大于写者
可否直接用一个互斥信号量实现?
- 不能。当读者获得数据库后无法让其它读者访问。
能否借用生产者-消费者中的同步思路?
- 与生产者-消费者问题不同,不存在一个有界的缓冲区,因此不能用一组信号量来控制读者-写者的互相等待
读者-写者问题解决方案
读者-写者锁
一些程序语言和操作系统提供了读写锁(Readers-writer lock)接口 读写锁适合于:
- 读进程和写进程可以区分开
- 读者进程数量比写者进程多
读者优先
- 又称第一类读者写者问题
- 只要有读者正在读,后来的读者都能直接进入
- 如读者持续不断进入,则写者就处于饥饿
写者优先
- 第二类读者写者问题
- 只要有写者就绪,写者应尽快执行写操作
- 如写者持续不断就绪,则读者就处于饥饿
- 该方法并发度和效率较低
读写锁替代策略:RCU
读写锁允许读者之间不互斥的读取数据
- 但是对于Rcount变量的操作需要加锁
- 当99%以上都是读者,且数量很大时,开销太大
- 读-复制-更新(Read-Copy-Update)
哲学家就餐问题
5个哲学家围圆桌而坐,每2人之间放一只叉子,哲学家的动作包括思考和进餐,同时拿到左右两边的叉子才能进餐,思考时将叉子放回原处。
可能的解决方案
- 至多只允许有四位哲学家去拿左边的筷子,最终能保证至少 有一位哲学家能够进餐,并可在用毕时释放出他用过的筷子, 从而使更多的哲学家能够进餐。
- 仅当哲学家的左、右两只筷子均可用时,才允许他拿起筷子 进餐。
- 规定奇数号哲学家先拿左边的筷子再拿右边的筷子;而偶数 号哲学家先拿右边的筷子再拿左边的筷子。
- 增加一根筷子(完美解决)
管程
管程是一种抽象数据类型(ADT),代表共享资源,及对该资源的互斥操作确保任一时刻最多只有一个进程进入管程,使用共享数据
思想:用锁(locks,通常是隐含的)实现互斥,用条件变量 (condition variable)实现同步,提供与信号量相同的功能
包含面向对象思想,封装了同步机制