多线程锁原理

• 临界区： 在临界区内，会对共享资源进行访问和修改
• 共享资源： 在同一时间只能被单个线程所持有

访问临界区过程：

1. 申请临界区权限
2. 访问临界区
3. 归还权限， 退出临界区

线程安全问题：
12306卖票问题，既不能多卖又不能少卖

if more_ticket > 0 {
 // 卖票 
 more_ticket -= 1
} 

如果多个线程，同时操作的话，可能会造成多卖票，本来只有1000张票，却卖个1001个人

为了避免这种情况，可以尝试使用标志位来解决

var isSaling = false // 正在售票标志位

while isSaling { // 如果有人售票，则等待
}

isSaling = true // 表示我正在售票，你们先等等
if more_ticket > 0 {
 // 卖票 
 more_ticket -= 1
} 
isSaling =false // 卖完票了，你们可以操作了 

遗憾的是这种方式，仍然无法解决安全问题，关键在于查询操作和修改操作并非不可中断，造成多个程序进入临界区：

Thread 1	Thread 2
query isSaling = false	query isSaling = false
set isSaling = true	set isSaling = true
卖票	卖票

为了防止这种情况发生。于是决定设置两个标志位

var isSaling1 = false // 正在售票标志位
var isSaling2 = false // 正在售票标志位
// =====================
// thread 1
while isSaling2 { // 2号线程正在售票，稍微等等
}

isSaling1 = true // 表示我正在售票，你们先等等
if more_ticket > 0 {
 // 卖票 
 more_ticket -= 1
} 
isSaling1 = false // 卖完票了，你们可以操作了 

// thread 2
// =================================

while isSaling1 { // 1号线程正在售票，稍微等等
}

isSaling2 = true // 表示我正在售票，你们先等等
if more_ticket > 0 {
 // 卖票 
 more_ticket -= 1
} 
isSaling2 = false // 卖完票了，你们可以操作了 

这种思维方式就像，有一条公家的小板凳，我先看下隔壁有没有占用那条小板凳，没有的话我就拿过来坐坐

但是仍然会发生多个线程进入临界区的问题： ** isSaling1 = false, isSaling2 = false, thread1 exec to while isSaling2 expr and thread2 exec to while isSaling1 expr **

可见光增加flag无法解决问题,换一种方式增加临界区大小

var isSaling1 = false // 正在售票标志位
var isSaling2 = false // 正在售票标志位
// =====================
// thread 1
isSaling1 = true // 表示我正在售票，你们先等等
while isSaling2 { // 2号线程正在售票，稍微等等
}


if more_ticket > 0 {
 // 卖票 
 more_ticket -= 1
} 
isSaling1 = false // 卖完票了，你们可以操作了 

// thread 2
// =================================
isSaling2 = true // 表示我正在售票，你们先等等
while isSaling1 { // 1号线程正在售票，稍微等等
}


if more_ticket > 0 {
 // 卖票 
 more_ticket -= 1
} 
isSaling2 = false // 卖完票了，你们可以操作了 

这种方式却会造成死锁，死锁的时机和之前一样。** isSaling1 = false, isSaling2 = false, thread1 exec to while isSaling2 expr and thread2 exec to while isSaling1 expr **， 只不过一个是造成多个线程共同访问临界区，一个是造成死锁

为了解决这个问题，产生了软件上的解法和硬件上的解法，
硬件的解法即源语。

软件上：
这两种算法思想其实是一致的，就是当线程进入临界区之后，发现别的线程也进入了临界区，怎么办？如何避免死锁或者并非， 这个时候就需要制定一个规则让他们能够正确运行
** Dekker 算法

var isSaling1 = false // 正在售票标志位
var isSaling2 = false // 正在售票标志位
var turn = 1
// =====================
// thread 1
isSaling1 = true // 表示我正在售票，你们先等等
while isSaling2 { // 这个时候发现2号正在售票
   if turn == 2 {
        isSaling1 = fasle // 我不卖了，让2号先卖
        while(isSaling2) {} // 等待2号卖票
        isSaling1 = true // 2号已经卖完票了轮到我卖了 
   }
}


if more_ticket > 0 {
 // 卖票 
 more_ticket -= 1
} 
isSaling1 = false // 卖完票了，你们可以操作了 
turn = 2
// thread 2
// =================================
isSaling2 = true // 表示我正在售票，你们先等等
while isSaling1 { // 1号线程正在售票，稍微等等
   if turn == 1 {
        isSaling2 = fasle 
        while(isSaling1) {} 
        isSaling2 = true 
   }
}


if more_ticket > 0 {
 // 卖票 
 more_ticket -= 1
} 
turn = 1
isSaling2 = false // 卖完票了，你们可以操作了 

这里turn = 1时，发生碰撞1号优先卖票，等于2时则相反，双方不断的切换优先级，防止死锁的同时避免多线程并发进入临界区

** Peterson 算法

 var inside:array[1..2] of boolean;
           turn:integer;
    turn := 1 or 2;
    inside[1] := false;
    inside[2] := false;
cobegin
process P1
begin
/* P1 不在其临界区内*/ /* P2 不在其临界区内*/
           inside[1]:= true;
           turn := 2;
           while (inside[2] and turn=2)
do begin end;
             临界区;
           inside[1] := false;
       end;
       process P2
       begin
           inside[2] := true;
           turn := 1;
           while (inside[1] and turn=1)
do begin end; 
             临界区;
           inside[2] := false;
       end;
coend.

这个算法的规则更加简化，由于两个线程都会修改turn的值，那么最后只有一个线程执行，另外一个堵塞，画个表看下会更加清晰

Thread 1	Thread 2
inside[1]:= true	inside[2] := true
turn := 2
if inside[2]
if turn := 2
// 线程1 被堵塞
turn := 1
// 线程1 执行	while (inside[1] and turn=1) 条件为真,线程被堵塞
inside[1] := false
线程2 执行

这个算法还是很精髓的

硬件指令

硬件指令相对于软件算法的不同在于不可分割性，也就是不会被中断，操作一起呵成

Test And Set 指令

TS(x): 若x=true，则x:=false;return true;否则return false;

s : boolean;
s := true;
process Pi /* i = 1,2,...,n*/
           pi : boolean;
       begin
repeat pi := TS(s) until pi; /*上锁*/ 临界区;
s := true; /*开锁*/
end;

关键句子: pi := TS(s)

// s = true
// =============
p0 = TS(s) 
// 执行之后
// s = false , p0 = true ,线程不会被阻塞

// ==========
// 由于TS指令的特殊性，导致执行的时候必然会有先后顺序,哪怕两个线程是同时调用的该指令，这里假定p0线程在前，p1在后
// 此时  s = false
p1 = TS(s) 
//  执行之后
//  p1 = false , s = false , set 失败, 线程被阻塞，直到p0 设置 s = true

Swap 指令

• Swap (a,b): temp:=a; a:=b; b:=temp;

lock : boolean;
lock := false;
process Pi
    pi : boolean;
begin
pi := true;
/* i = 1,2,...,n*/

repeat Swap(lock, pi) until pi = false;/*上锁*/ 临界区;
lock := false; /*开锁*/
end;

原理和上面的类似第一次交换:

// lock = false
// p0 = true
swap(p0,lock)
// p0 = false , lock = true

第二次交换

// lock = true
// p1 = true
swap(p0,lock)
// p1 = true , lock = true, 即swap(true,true)

线程被阻塞