线程同步

$$线程互斥$$

$RaceCondition(竞态条件)$
$产生不确定性现象的条件之一$。
$系统缺陷$：运行的结果依赖于并发执行或者时间的顺序/时间。

1. 不确定性
2. 不可重现

$AtomicOperation(原子操作)$
$原子操作$：指一次不存在任何中断或者失败的执行。进程使用原子操作可以减少变成竞态的概率。

$线程相互竞争示例：$
$线程A$：

int i  = 0;
while(i < 10)
	i += 1;
printf("A wins！");
1
2
3
4

$线程B$：

i = 0;
while(i > -10)
	i -= 1;
printf("B wins！");
1
2
3
4

$i$是两个线程的共享变量，当两个线程运行的时候，因为对$i$的操作不是原子操作，所以在翻译为机器代码的时候，可能出现竞态。$最后的胜利结果无法预知$。

一些基本概念

1. $Criticalsection(临界区)$：临界区是在进程中访问$共享资源$的区域。
2. $Mutualexclusion(互斥)$：当一个进程在临界区访问共享资源的时候，其他的进程不能够访问临界区中的共享资源($互斥体现$)。
3. $Deadlock(死锁)$：两个或者两个以上的任务，相互等着对方完成任务之后在执行，最终谁也不能够进行下去。
4. $Staravation(饥饿)$：一个已经满足可以向下进行的进程，但是一直被调度器忽略，最终也不能够运行。

$临界区特征$

1. $互斥$：同一时间临界区中最多只能有一个线程。
2. $Progress$：如果一个线程想要进入临界区，那么它最终一定会成功。
3. $有限等待$：如果一个线程$i$处于入口区，那么在$i$被请求接受之前，其他线程进入临界区的时间是有限制的。
4. $有忙等待$：如果一个线程正在等待被处理，那么可以将它挂起，节省$CPU$的资源。

$基于软件的解决方法$

$经典线程互斥模型$

满足进程$P_i$和$P_j$之间互斥的经典$基于软件$的解决方法(基于进程$P_i$一方的算法)：

int turn;		//指示谁应该进入临界区
bool flag[];	//指示当前进程是否准备好了进入临界区

do
{
	flag[i] = true;			//当前的进程i准备好了进入临界区
	turn = j;					//但是真正轮到进入临界区的是进程j
	while(flag[j] && turn == j);			//当轮到进程j进入的时候并且j也准备好了，进程i循环等待
		critical section				//然后进程i进入临界区
	flag[i] = false;						//表示进程i没有准备好了
		remainder section			//进程i进入等待区间
}while(true)
1
2
3
4
5
6
7
8
9
10
11
12

$Bakery算法$($N$个进程的临界区互斥算法)
进入临界区之前，$进程收到一个数字$。
所有进程中，得到数字$最小$的进程进入临界区。
如果进程$P_i$和$P_j$接收了$相同$的数字，那么如果$i<j$，$P_i$先进入临界区，否则$P_j$先进入临界区。
编号的方案总是按照枚举的增加顺序生成数字。

$更高级的抽象方法$

抽象出一个$Lock$数据结构，结合$exchange$原子操作，实现多个线程对于临界区的访问管控。

int lock = 0;	//共享数据(初始化为0)

线程Ti：
	int key;
	do{
		key = 1;
		while(key == 1)
			exchange(lock,key);
		critical section;
		lock = 0;
		remainder section;
	}
1
2
3
4
5
6
7
8
9
10
11
12

$整体流程：$首先所有线程共享的$lock$初始化为$0$。之后例如图中的线程$T_i$，进入循环将每个线程配备的$key$初始化为$1$，之后进入$while$循环，调用$exchange$交换$lock$与$key$内存中的数据。如果此时$lock$是$0$，交换数据之后就会打破$while$循环。此时该线程进入临界区，同时将$lock$置为$1$，意为此时临界区有了线程访问，进行“锁住”。其他的线程无法进入。等到该线程访问完成之后，$lock$置为$0$，下一个线程$exchange$之后就可以进入了。
($所有的线程都配有自己的key，但是所有的线程共用一个lock$)