多线程锁原理
- 临界区： 在临界区内，会对共享资源进行访问和修改
- 共享资源： 在同一时间只能被单个线程所持有
访问临界区过程：
- 申请临界区权限
- 访问临界区
- 归还权限， 退出临界区
线程安全问题：
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)
线程被阻塞
