多線程鎖原理

臨界區(qū)：在臨界區(qū)內(nèi)，會(huì)對(duì)共享資源進(jìn)行訪問和修改
共享資源：在同一時(shí)間只能被單個(gè)線程所持有

訪問臨界區(qū)過程：

申請(qǐng)臨界區(qū)權(quán)限
訪問臨界區(qū)
歸還權(quán)限，退出臨界區(qū)

線程安全問題：
12306賣票問題，既不能多賣又不能少賣

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

如果多個(gè)線程，同時(shí)操作的話，可能會(huì)造成多賣票，本來只有1000張票，卻賣個(gè)1001個(gè)人

為了避免這種情況，可以嘗試使用標(biāo)志位來解決

var isSaling = false // 正在售票標(biāo)志位

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

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

遺憾的是這種方式，仍然無法解決安全問題，關(guān)鍵在于查詢操作和修改操作并非不可中斷，造成多個(gè)程序進(jìn)入臨界區(qū)：

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

為了防止這種情況發(fā)生。于是決定設(shè)置兩個(gè)標(biāo)志位


var isSaling1 = false // 正在售票標(biāo)志位
var isSaling2 = false // 正在售票標(biāo)志位
// =====================
// thread 1
while isSaling2 { // 2號(hào)線程正在售票，稍微等等
}

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

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

while isSaling1 { // 1號(hào)線程正在售票，稍微等等
}

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

這種思維方式就像，有一條公家的小板凳，我先看下隔壁有沒有占用那條小板凳，沒有的話我就拿過來坐坐

但是仍然會(huì)發(fā)生多個(gè)線程進(jìn)入臨界區(qū)的問題： ** isSaling1 = false, isSaling2 = false, thread1 exec to while isSaling2 expr and thread2 exec to while isSaling1 expr **

可見光增加flag無法解決問題,換一種方式增加臨界區(qū)大小


var isSaling1 = false // 正在售票標(biāo)志位
var isSaling2 = false // 正在售票標(biāo)志位
// =====================
// thread 1
isSaling1 = true // 表示我正在售票，你們先等等
while isSaling2 { // 2號(hào)線程正在售票，稍微等等
}


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

// thread 2
// =================================
isSaling2 = true // 表示我正在售票，你們先等等
while isSaling1 { // 1號(hào)線程正在售票，稍微等等
}


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

這種方式卻會(huì)造成死鎖，死鎖的時(shí)機(jī)和之前一樣。** isSaling1 = false, isSaling2 = false, thread1 exec to while isSaling2 expr and thread2 exec to while isSaling1 expr **，只不過一個(gè)是造成多個(gè)線程共同訪問臨界區(qū)，一個(gè)是造成死鎖

為了解決這個(gè)問題，產(chǎn)生了軟件上的解法和硬件上的解法，
硬件的解法即源語。

軟件上：
這兩種算法思想其實(shí)是一致的，就是當(dāng)線程進(jìn)入臨界區(qū)之后，發(fā)現(xiàn)別的線程也進(jìn)入了臨界區(qū)，怎么辦？如何避免死鎖或者并非，這個(gè)時(shí)候就需要制定一個(gè)規(guī)則讓他們能夠正確運(yùn)行
** Dekker 算法


var isSaling1 = false // 正在售票標(biāo)志位
var isSaling2 = false // 正在售票標(biāo)志位
var turn = 1
// =====================
// thread 1
isSaling1 = true // 表示我正在售票，你們先等等
while isSaling2 { // 這個(gè)時(shí)候發(fā)現(xiàn)2號(hào)正在售票
   if turn == 2 {
        isSaling1 = fasle // 我不賣了，讓2號(hào)先賣
        while(isSaling2) {} // 等待2號(hào)賣票
        isSaling1 = true // 2號(hào)已經(jīng)賣完票了輪到我賣了 
   }
}


if more_ticket > 0 {
 // 賣票 
 more_ticket -= 1
} 
isSaling1 = false // 賣完票了，你們可以操作了 
turn = 2
// thread 2
// =================================
isSaling2 = true // 表示我正在售票，你們先等等
while isSaling1 { // 1號(hào)線程正在售票，稍微等等
   if turn == 1 {
        isSaling2 = fasle 
        while(isSaling1) {} 
        isSaling2 = true 
   }
}


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

這里turn = 1時(shí)，發(fā)生碰撞1號(hào)優(yōu)先賣票，等于2時(shí)則相反，雙方不斷的切換優(yōu)先級(jí)，防止死鎖的同時(shí)避免多線程并發(fā)進(jìn)入臨界區(qū)

** 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 不在其臨界區(qū)內(nèi)*/ /* P2 不在其臨界區(qū)內(nèi)*/
           inside[1]:= true;
           turn := 2;
           while (inside[2] and turn=2)
do begin end;
             臨界區(qū);
           inside[1] := false;
       end;
       process P2
       begin
           inside[2] := true;
           turn := 1;
           while (inside[1] and turn=1)
do begin end; 
             臨界區(qū);
           inside[2] := false;
       end;
coend.

這個(gè)算法的規(guī)則更加簡(jiǎn)化，由于兩個(gè)線程都會(huì)修改turn的值，那么最后只有一個(gè)線程執(zhí)行，另外一個(gè)堵塞，畫個(gè)表看下會(huì)更加清晰

Thread 1	Thread 2
inside[1]:= true	inside[2] := true
turn := 2
if inside[2]
if turn := 2
// 線程1 被堵塞
turn := 1
// 線程1 執(zhí)行	while (inside[1] and turn=1) 條件為真,線程被堵塞
inside[1] := false
線程2 執(zhí)行

這個(gè)算法還是很精髓的

硬件指令

硬件指令相對(duì)于軟件算法的不同在于不可分割性，也就是不會(huì)被中斷，操作一起呵成

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; /*上鎖*/ 臨界區(qū);
s := true; /*開鎖*/
end;

關(guān)鍵句子: pi := TS(s)

// s = true
// =============
p0 = TS(s) 
// 執(zhí)行之后
// s = false , p0 = true ,線程不會(huì)被阻塞

// ==========
// 由于TS指令的特殊性，導(dǎo)致執(zhí)行的時(shí)候必然會(huì)有先后順序,哪怕兩個(gè)線程是同時(shí)調(diào)用的該指令，這里假定p0線程在前，p1在后
// 此時(shí)  s = false
p1 = TS(s) 
//  執(zhí)行之后
//  p1 = false , s = false , set 失敗, 線程被阻塞，直到p0 設(shè)置 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;/*上鎖*/ 臨界區(qū);
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)

線程被阻塞

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

多線程鎖原理