目錄
1. 互斥鎖的實(shí)現(xiàn)與特點(diǎn)
2. 自旋鎖的實(shí)現(xiàn)和特點(diǎn)
3. 原子操作的原理和實(shí)現(xiàn)方式
4. 三種同步方式的應(yīng)用場(chǎng)景
1. 互斥鎖的實(shí)現(xiàn)和特點(diǎn)
-
linux內(nèi)核中關(guān)于互斥鎖的實(shí)現(xiàn)
//數(shù)據(jù)結(jié)構(gòu)（linux2.6之后，之前是采用信號(hào)量定義一個(gè)mutex抹沪，事實(shí)上它的定義還是類(lèi)似于信號(hào)量）
struct mutex {
/* 1: unlocked, 0: locked, negative: locked, possible waiters */
atomic_t count;
spinlock_t wait_lock;//自旋鎖刻肄，等待獲取互斥鎖中使用的自旋鎖。在獲取互斥鎖的過(guò)程中采够，操作會(huì)在自旋鎖的保護(hù)中進(jìn)行肄方。初始化為為鎖定冰垄。
struct list_head wait_list;//維護(hù)一個(gè)等待隊(duì)列
#if defined(CONFIG_DEBUG_MUTEXES) || defined(CONFIG_MUTEX_SPIN_ON_OWNER)
struct task_struct *owner;//指向擁有互斥鎖的進(jìn)程
#endif
#ifdef CONFIG_MUTEX_SPIN_ON_OWNER
struct optimistic_spin_queue osq; /* Spinner MCS lock */
#endif
#ifdef CONFIG_DEBUG_MUTEXES
void *magic;
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
struct lockdep_map dep_map;
#endif
};
如何使用互斥鎖
- 初始化
mutex_init(&mutex); //動(dòng)態(tài)初始化互斥鎖
DEFINE_MUTEX(mutexname); //靜態(tài)定義和初始化互斥鎖- 上鎖
void mutex_lock(struct mutex lock);//無(wú)法獲得鎖時(shí)蹬癌，睡眠等待权她，不會(huì)被信號(hào)中斷。
int mutex_trylock(struct mutex lock);//此函數(shù)是 mutex_lock()的非阻塞版本逝薪，成功返回1隅要，失敗返回0。
int mutex_lock_interruptible(struct mutex lock);//和mutex_lock()一樣董济，也是獲取互斥鎖步清。在獲得了互斥鎖或進(jìn)入睡眠直到獲得互斥鎖之后會(huì)返回0。如果在等待獲取鎖的時(shí)候進(jìn)入睡眠狀態(tài)收到一個(gè)信號(hào)(被信號(hào)打斷睡眠)虏肾，則返回_EINIR廓啊。- 解鎖
void mutex_unlock(struct mutex lock);
注意：互斥鎖在上鎖的過(guò)程中，需要用自旋鎖保證原子操作（包括修改原子量和鎖的相關(guān)數(shù)據(jù)結(jié)構(gòu)）
-
posix庫(kù)中關(guān)于互斥鎖的實(shí)現(xiàn)(用戶態(tài))
如何使用互斥鎖
- 初始化
int pthread_mutex_init(pthread_mutex_t *mp, const pthread_mutexattr_t *mattr);;//動(dòng)態(tài)初始化互斥鎖
函數(shù)說(shuō)明：初始化互斥鎖之前封豪，必須將其所在的內(nèi)存清零谴轮。如果互斥鎖已初始化，則它會(huì)處于未鎖定狀態(tài)- 設(shè)置鎖的屬性
pthread_mutexattr_init(pthread_mutexattr_t *mattr);//互斥鎖屬性可以由該函數(shù)來(lái)初始化吹埠，然后再調(diào)用其他的函數(shù)來(lái)設(shè)置其屬性
int pthread_mutexattr_setpshared(pthread_mutexattr_t *mattr, int pshared)
int pthread_mutexattr_getshared(pthread_mutexattr_t *mattr,int *pshared))//可以指定是該進(jìn)程與其他進(jìn)程的同步還是同一進(jìn)程內(nèi)不同的線程之間的同步第步。可以設(shè)置為PTHREAD_PROCESS_SHARE和PTHREAD_PROCESS_PRIVATE缘琅。默認(rèn)是后者粘都，表示進(jìn)程內(nèi)使用鎖
init pthread_mutexattr_settype(pthread_mutexattr_t *attr , int type)
init pthread_mutexattr_gettype(pthread_mutexattr_t *attr , int *type)互斥鎖的類(lèi)型,有以下幾個(gè)取值空間：
PTHREAD_MUTEX_TIMED_NP，這是缺省值刷袍，也就是普通鎖翩隧。當(dāng)一個(gè)線程加鎖以后，其余請(qǐng)求鎖的線程將形成一個(gè)等待隊(duì)列呻纹，并在解鎖后按優(yōu)先級(jí)獲得鎖鸽心。這種鎖策略保證了資源分配的公平性。
PTHREAD_MUTEX_RECURSIVE_NP居暖，嵌套鎖顽频，允許同一個(gè)線程對(duì)同一個(gè)鎖成功獲得多次，并通過(guò)多次unlock解鎖太闺。如果是不同線程請(qǐng)求糯景，則在加鎖線程解鎖時(shí)重新競(jìng)爭(zhēng)。
PTHREAD_MUTEX_ERRORCHECK_NP省骂，檢錯(cuò)鎖蟀淮，如果同一個(gè)線程請(qǐng)求同一個(gè)鎖，則返回EDEADLK钞澳，否則與PTHREAD_MUTEX_TIMED_NP類(lèi)型動(dòng)作相同怠惶。這樣就保證當(dāng)不允許多次加鎖時(shí)不會(huì)出現(xiàn)最簡(jiǎn)單情況下的死鎖。
PTHREAD_MUTEX_ADAPTIVE_NP轧粟，適應(yīng)鎖策治，動(dòng)作最簡(jiǎn)單的鎖類(lèi)型脓魏，僅等待解鎖后重新競(jìng)爭(zhēng)。
- 上鎖
void _int pthread_mutex_lock(pthread_mutex_t *mutex);//無(wú)法獲得鎖時(shí)通惫，睡眠等待茂翔，不會(huì)被信號(hào)中斷
返回值：0, 成功；其他值履腋，失斏毫恰；EAGAIN遵湖，由于已超出了互斥鎖遞歸鎖定的最大次數(shù)悔政，因此無(wú)法獲取該互斥鎖；EDEADLK：當(dāng)前線程已經(jīng)擁有互斥鎖延旧。- 解鎖
int pthread_mutex_unlock(pthread_mutex_t *mutex);
函數(shù)說(shuō)明：如果調(diào)用 pthread_mutex_unlock() 時(shí)有多個(gè)線程被 mutex 對(duì)象阻塞卓箫，則互斥鎖變?yōu)榭捎脮r(shí)調(diào)度策略可確定獲取該互斥鎖的線程。對(duì)于 PTHREAD_MUTEX_RECURSIVE 類(lèi)型的互斥鎖垄潮，當(dāng)計(jì)數(shù)達(dá)到零并且調(diào)用線程不再對(duì)該互斥鎖進(jìn)行任何鎖定時(shí)烹卒，該互斥鎖將變?yōu)榭捎?- 非阻塞模式的互斥鎖
int pthread_mutex_trylock(pthread_mutex_t *mutex);
函數(shù)說(shuō)明：pthread_mutex_lock() 的非阻塞版本。如果 mutex 所引用的互斥對(duì)象當(dāng)前被任何線程（包括當(dāng)前線程）鎖定弯洗，則將立即返回該調(diào)用旅急。否則，該互斥鎖將處于鎖定狀態(tài)牡整，調(diào)用線程是其屬主
-
互斥鎖的特點(diǎn)
1）互斥鎖的特性藐吮，是一種信號(hào)量，常用來(lái)防止兩個(gè)線程在同一時(shí)刻訪問(wèn)相同的共享資源逃贝。它有以下三個(gè)特性:
唯一性：如果一個(gè)線程鎖定了一個(gè)互斥量谣辞，在它解除鎖定之前，沒(méi)有其他線程可以鎖定這個(gè)互斥量沐扳；
原子性：把一個(gè)互斥量鎖定為一個(gè)原子操作泥从，這意味著操作系統(tǒng)（或pthread函數(shù)庫(kù)）保證了如果一個(gè)線程鎖定了一個(gè)互斥量，沒(méi)有其他線程在同一時(shí)間可以成功鎖定這個(gè)互斥量沪摄；
非繁忙等待：如果一個(gè)線程已經(jīng)鎖定了一個(gè)互斥量躯嫉，第二個(gè)線程又試圖去鎖定這個(gè)互斥量，則第二個(gè)線程將被掛起（不占用任何cpu資源）杨拐，直到第一個(gè)線程解除對(duì)這個(gè)互斥量的鎖定為止祈餐，第二個(gè)線程則被喚醒并繼續(xù)執(zhí)行，同時(shí)鎖定這個(gè)互斥量哄陶。
2）互斥鎖的作用域
互斥鎖一般用在線程間帆阳，當(dāng)然可以通過(guò)設(shè)置互斥鎖的屬性讓它在進(jìn)程間使用。
- 互斥鎖和信號(hào)量比較
- 互斥鎖功能上基本與二元信號(hào)量一樣屋吨，但是互斥鎖占用空間比信號(hào)量小蜒谤，運(yùn)行效率比信號(hào)量高山宾。所以，如果要用于線程間的互斥芭逝，優(yōu)先選擇互斥鎖。
上面這種解釋是有問(wèn)題了渊胸，除了開(kāi)銷(xiāo)上的區(qū)別, 我們還應(yīng)該關(guān)注兩者在語(yǔ)義上的區(qū)別：
互斥：是指某一資源同時(shí)只允許一個(gè)訪問(wèn)者對(duì)其進(jìn)行訪問(wèn)旬盯，具有唯一性和排它性。但互斥無(wú)法限制訪問(wèn)者對(duì)資源的訪問(wèn)順序翎猛，即訪問(wèn)是無(wú)序的胖翰。舉個(gè)例子，如果資源被鎖定切厘，另外一個(gè)線程嘗試獲取鎖時(shí)萨咳，并阻塞線程，至于下一次什么時(shí)候線程被喚醒是未可知的疫稿，這個(gè)取決于cpu的調(diào)度培他。所以使用互斥鎖會(huì)出現(xiàn)優(yōu)先級(jí)倒置（prority inversion）的問(wèn)題，高優(yōu)先級(jí)的線程反而被延遲執(zhí)行遗座。
同步：是指在互斥的基礎(chǔ)上（大多數(shù)情況）舀凛，通過(guò)其它機(jī)制實(shí)現(xiàn)訪問(wèn)者對(duì)資源的有序訪問(wèn)。在大多數(shù)情況下途蒋，同步已經(jīng)實(shí)現(xiàn)了互斥猛遍，特別是所有寫(xiě)入資源的情況必定是互斥的。少數(shù)情況是指可以允許多個(gè)訪問(wèn)者同時(shí)訪問(wèn)資源号坡。信號(hào)量一般會(huì)采用解鎖通知等待隊(duì)列中的線程（可以設(shè)置調(diào)度順序懊烤，當(dāng)然等待隊(duì)列的開(kāi)銷(xiāo)需要額外支出的）
- 互斥鎖和自旋鎖比較
- 互斥鎖在無(wú)法得到資源時(shí)，內(nèi)核線程會(huì)進(jìn)入睡眠阻塞狀態(tài)宽堆，而自旋鎖處于忙等待狀態(tài)腌紧。因此，如果資源被占用的時(shí)間較長(zhǎng)畜隶，使用互斥鎖較好寄啼，因?yàn)榭勺孋PU調(diào)度去做其它進(jìn)程的工作。
- 如果被保護(hù)資源需要睡眠的話代箭，那么只能使用互斥鎖或者信號(hào)量墩划，不能使用自旋鎖。而互斥鎖的效率又比信號(hào)量高嗡综，所以這時(shí)候最佳選擇是互斥鎖乙帮。
- 中斷里面不能使用互斥鎖，因?yàn)榛コ怄i在獲取不到鎖的情況下會(huì)進(jìn)入睡眠极景，而中斷是不能睡眠的
注意察净，為了防止死鎖驾茴，不能在同一個(gè)線程里面兩次申請(qǐng)同樣的鎖，同時(shí)也不推薦在不同的線程里面同時(shí)申請(qǐng)兩個(gè)一樣的鎖氢卡。
2. 自旋鎖在內(nèi)核中的運(yùn)用
內(nèi)核中自旋鎖的運(yùn)行機(jī)制：
- 單處理器自旋鎖的工作流程是:單處理器中自旋鎖不被啟用锈至，因?yàn)槭褂米孕i的中斷執(zhí)行路徑一旦被嵌套可能會(huì)造成永久等待，同步途徑是關(guān)閉內(nèi)核搶占->運(yùn)行臨界區(qū)代碼->開(kāi)啟內(nèi)核搶占译秦。更加安全的單處理器自旋鎖工作流程是:保存IF寄存器->關(guān)閉當(dāng)前CPU中斷->關(guān)閉內(nèi)核搶占->運(yùn)行臨界區(qū)代碼->開(kāi)啟內(nèi)核搶占->開(kāi)啟當(dāng)前CPU中斷->恢復(fù)IF寄存器峡捡。
- 多處理器自旋鎖的工作流程是：關(guān)閉內(nèi)核搶占->（忙等待->)獲取自旋鎖->運(yùn)行臨界區(qū)代碼->釋放自旋鎖->開(kāi)啟內(nèi)核搶占。更加安全的多處理器自旋鎖工作流程是：保存IF寄存器->關(guān)閉當(dāng)前CPU中斷->關(guān)閉內(nèi)核搶占->（忙等待->)獲取自旋鎖->運(yùn)行臨界區(qū)代碼->釋放自旋鎖->開(kāi)啟內(nèi)核搶占->開(kāi)啟當(dāng)前CPU中斷->恢復(fù)IF寄存器筑悴。
自旋鎖的實(shí)現(xiàn)和特點(diǎn)
//CAS操作在cpu指令集中可以是原子性的
int CompareAndExchange(int *ptr, int old, int new){
int actual = *ptr;
if (actual == old)
*ptr = new;
return actual;
}
void lock(lock_t *lock) {
while (CompareAndExchange(&lock->flag, 0, 1) == 1); // spin
}
void unlock(lock_t *lock) {
lock->flag = 0;
}
這個(gè)實(shí)現(xiàn)是借助cpu的原子指令CAS實(shí)現(xiàn)的们拙，后面會(huì)介紹原子操作
自旋鎖是采用忙等的狀態(tài)獲取鎖，所以會(huì)一直占用cpu資源阁吝，但是允許不關(guān)閉中斷的情況下砚婆，是可以被其他內(nèi)核執(zhí)行路徑搶占的（中斷嵌套的情況下，注意嵌套的中斷不能申請(qǐng)同一個(gè)鎖突勇，這樣會(huì)造成死等）装盯。同時(shí)因?yàn)榫€程對(duì)cpu一直保持占用狀態(tài)，所以對(duì)小資源加鎖效率比較高甲馋，不需要做任何的線程切換验夯，一般情況下如果加鎖資源的運(yùn)行延遲小于線程或者進(jìn)程切換的時(shí)延則推薦使用自旋鎖。如果需要等待耗時(shí)操作摔刁，則建議放棄cpu挥转，采用信號(hào)量或者互斥鎖
3. 原子操作
在介紹原子操作之前需要介紹幾個(gè)概念
- 內(nèi)存屏障
- 編譯優(yōu)化
匯編級(jí)原子操作
最新的處理器能自動(dòng)保證單處理器對(duì)同一個(gè)緩存行里進(jìn)行16/32/64位的操作是原子的，但是復(fù)雜的內(nèi)存操作處理器是不能自動(dòng)保證其原子性的共屈，比如跨總線寬度绑谣、跨多個(gè)緩存行和跨頁(yè)表的訪問(wèn)。但是拗引，處理器提供總線鎖定和緩存鎖定兩個(gè)機(jī)制來(lái)保證復(fù)雜內(nèi)存操作的原子性借宵。如下圖所示就是采用總線鎖定的方式進(jìn)行原子操作：
上圖指令可以實(shí)現(xiàn)加操作的原子性，但是這種總線鎖不能濫用矾削，在沒(méi)有共享同步問(wèn)題的時(shí)候壤玫，這會(huì)阻止cpu并行計(jì)算的優(yōu)化，甚至?xí)枞鹀pu對(duì)其他內(nèi)存的訪問(wèn)哼凯，導(dǎo)致效率的下降欲间。所以除此之外我們可以使用緩存鎖來(lái)執(zhí)行復(fù)雜的原子操作。
使用緩存鎖保證原子性
第二個(gè)機(jī)制是通過(guò)緩存鎖定來(lái)保證原子性断部。在同一時(shí)刻猎贴，我們只需保證對(duì)某個(gè)內(nèi)存地址的操作是原子性即可，但總線鎖定把CPU和內(nèi)存之間的通信鎖住了，這使得鎖定期間她渴，其他處理器不能操作其他內(nèi)存地址的數(shù)據(jù)达址，所以總線鎖定的開(kāi)銷(xiāo)比較大，目前處理器在某些場(chǎng)合下使用緩存鎖定代替總線鎖定來(lái)進(jìn)行優(yōu)化趁耗。
頻繁使用的內(nèi)存會(huì)緩存在處理器的L1沉唠、L2和L3高速緩存里，那么原子操作就可以直接在處理器內(nèi)部緩存中進(jìn)行苛败，并不需要聲明總線鎖满葛，在Pentium 6和目前的處理器中可以使用“緩存鎖定”的方式來(lái)實(shí)現(xiàn)復(fù)雜的原子性。所謂“緩存鎖定”是指內(nèi)存區(qū)域如果被緩存在處理器的緩存行中著拭，并且在Lock操作期間被鎖定纱扭，那么當(dāng)它執(zhí)行鎖操作回寫(xiě)到內(nèi)存時(shí)牍帚，處理器不在總線上聲言LOCK＃信號(hào)儡遮，而是修改內(nèi)部的內(nèi)存地址，并允許它的緩存一致性機(jī)制來(lái)保證操作的原子性暗赶，因?yàn)榫彺嬉恢滦詸C(jī)制會(huì)阻止同時(shí)修改由兩個(gè)以上處理器緩存的內(nèi)存區(qū)域數(shù)據(jù)鄙币，當(dāng)其他處理器回寫(xiě)已被鎖定的緩存行的數(shù)據(jù)時(shí)，會(huì)使緩存行無(wú)效蹂随，在如圖2-3所示的例子中十嘿，當(dāng)CPU1修改緩存行中的i時(shí)使用了緩存鎖定，那么CPU2就不能同時(shí)緩存i的緩存行岳锁。
但是有兩種情況下處理器不會(huì)使用緩存鎖定绩衷。
第一種情況是：當(dāng)操作的數(shù)據(jù)不能被緩存在處理器內(nèi)部，或操作的數(shù)據(jù)跨多個(gè)緩存行（cache line）時(shí)激率，則處理器會(huì)調(diào)用總線鎖定咳燕。
第二種情況是：有些處理器不支持緩存鎖定。對(duì)于Intel 486和Pentium處理器乒躺，就算鎖定的內(nèi)存區(qū)域在處理器的緩存行中也會(huì)調(diào)用總線鎖定招盲。
未完待續(xù)。嘉冒。曹货。。
references：
https://www.cnblogs.com/alinh/p/6905221.html
https://blog.csdn.net/mcgrady_tracy/article/details/34829019
https://leetcode.com/discuss/interview-question/operating-system/125169/Mutex-vs-Semaphore
https://blog.csdn.net/zxx901221/article/details/83033998
https://leetcode.com/discuss/interview-question/operating-system/134290/Implement-your-own-spinlock
