A Little Book Of Semaphores 笔记/翻译
Preface:
a set of primitives (mutexes, semaphores, monitors)
一组单元(互斥体,信号量,监视器 )
Chapter 1 Introduction
1.1 同步
同步约束 synchronization constraints
同步意味着两个事情同时发生
事务顺序
序列化 Serialization: 事件A先于事件B发生
互斥 Mutual exclusion: 事件A 禁止与事件B,同时发生
在现实生活中,我们经常使用时钟检查并强制执行同步约束——检查两个事情发生的时间, 那没有时钟呢?
1.2 执行模型
线程是一系列顺序执行的指令。
通常程序员无法控制哪个线程可以何时运行,OS特别是scheduler作出这些决定。 出于同步的目的,并行模型(parallel)和多线程模型(multithread)之间没有区别。
在一个处理器(或一个线程)内我们知道执行的顺序,但在多个处理器(或多个线程)之间是不可能分辨的。
时钟的问题
1、即使准确,精度还是有限的;
2、事件(大多数)无法记录时间
3、发生太快(大多数), 无法记录确切时间
1.3 使用消息进行序列化
这种方法看似微不足道,但是背后的基本思想—消息传递,是许多同步问题的真正解决方案
每一行代表你操作的一系列动作——>也就是一个线程的执行。
上图中顺序为:a1 < a2 < a3 < a4, b1 < b2 < b3 (其中关系a1 <a2表示a1发生在a2之前)
假设事件是吃完饭后打电话给Bob,那么 b3 > b2 > a4 > a3
sequentially vs serilazation?
serilazation是针对颗粒度较小的事务,定义更加严格.
sequence== happen in order!是针对线程之间的,与之相反的是:concurrently是指线程之间的关系
如果我们无法通过查看将首先发生的程序来判断两个事件是并发的!? (Two events are concurrent if we cannot tell by looking at the program which will happen first.)
有时我们可以分辨,在程序运行之后什么首先发生,但大部分情况下不行。即使可以,也不能保证下次会得到相同的结果。
1.4 非确定性
并发编程通常是非确定性的,这意味着通过查看程序,可能告诉它在执行时会发生什么。For example:
因为两个线程并发运行,所以执行顺序取决于Scheduler上。以上可能是”yes no”,也可能是”no yes”。
非确定性使并发编程难以debug, 程序可能正确1000次,然后再1001次崩溃。而且通过测试几乎找不到这些类型的错误,只能通过正确编程避免。
1.5 共享变量
例如,一种在线程之间传递信息的方法, 是A线程读取线程写入的值。
并发读取不会产生同步问题。
1.5.1 并发Write
1.5.2 并发Update
Update操作 = Read old value+ Compute new value + Write new value
初看之下不会有问题,如果我们用临时变量temp重写代码,问题就更明显了。
假设 a1 < b1 < b2 < a2,并且初始值count = 0 ,
那么最终值会是什么?
一个不能被打断的操作(operation)被称为原子性(atomic)
如果不知道那个操作是原子性的,我们怎么做concurrent编程?
最常见方法是: 假设所有操作都是non-atomic,并使用同步约束,控制读shared 变量的并发访问。
最常见约束是:互斥mutual exclusion
互斥可确保一次只有一个线程访问共享变量,从而消除了本节中的各种同步错误
1.5.3 使用消息互斥