Futex設(shè)計與實現(xiàn)

介紹

futex (fast userspace mutex) 是Linux的一個基礎(chǔ)組件庆械,可以用來構(gòu)建各種更高級別的同步機制,比如鎖或者信號量等等菌赖,POSIX信號量就是基于futex構(gòu)建的缭乘。大多數(shù)時候編寫應(yīng)用程序并不需要直接使用futex,一般用基于它所實現(xiàn)的系統(tǒng)庫就夠了琉用。

歷史

傳統(tǒng)的SystemV IPC(inter process communication)進(jìn)程間同步機制都是通過內(nèi)核對象來實現(xiàn)的堕绩,以 semaphore 為例薄啥,當(dāng)進(jìn)程間要同步的時候,必須通過系統(tǒng)調(diào)用semop(2)進(jìn)入內(nèi)核進(jìn)行PV操作逛尚。系統(tǒng)調(diào)用的缺點是開銷很大,需要從user mode切換到kernel mode刁愿、保存寄存器狀態(tài)绰寞、從user stack切換到kernel stack、等等铣口,通常要消耗上百條指令滤钱。事實上,有一部分系統(tǒng)調(diào)用是可以避免的脑题,因為現(xiàn)實中很多同步操作進(jìn)行的時候根本不存在競爭件缸,即某個進(jìn)程從持有semaphore直至釋放semaphore的這段時間內(nèi),常常沒有其它進(jìn)程對同一semaphore有需求叔遂,在這種情況下他炊,內(nèi)核的參與本來是不必要的,可是在傳統(tǒng)機制下已艰,持有semaphore必須先調(diào)用semop(2)進(jìn)入內(nèi)核去看看有沒有人和它競爭痊末,釋放semaphore也必須調(diào)用semop(2)進(jìn)入內(nèi)核去看看有沒有人在等待同一semaphore,這些不必要的系統(tǒng)調(diào)用造成了大量的性能損耗哩掺。

futex設(shè)計思想

futex的解決思路是:在無競爭的情況下操作完全在user space進(jìn)行凿叠,不需要系統(tǒng)調(diào)用,僅在發(fā)生競爭的時候進(jìn)入內(nèi)核去完成相應(yīng)的處理(wait 或者 wake up)嚼吞。所以說盒件,futex是一種user mode和kernel mode混合的同步機制,需要兩種模式合作才能完成舱禽,futex變量必須位于user space炒刁,而不是內(nèi)核對象,futex的代碼也分為user mode和kernel mode兩部分呢蔫,無競爭的情況下在user mode切心,發(fā)生競爭時則通過sys_futex系統(tǒng)調(diào)用進(jìn)入kernel mode進(jìn)行處理

實現(xiàn)

// 在uaddr指向的這個鎖變量上掛起等待(僅當(dāng)*uaddr==val時)
int futex_wait(int *uaddr, int val);
// 喚醒n個在uaddr指向的鎖變量上掛起等待的進(jìn)程
int futex_wake(int *uaddr, int n);
/* 
 * This sample show how to use futex betwen two process, and use system v  
 * shared memory to store data 
 */  
  
#include <unistd.h>  
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <sys/ipc.h>  
#include <sys/mman.h>  
#include <sys/types.h>  
#include <sys/syscall.h>  
#include <sys/wait.h>  
#include <sys/stat.h>  
#include <fcntl.h>  
#include <errno.h>  
  
#if __GLIBC_PREREQ(2, 3)      
#if defined FUTEX_WAIT || defined FUTEX_WAKE   
#include <linux/futex.h>  
#else  
#define FUTEX_WAIT      0  
#define FUTEX_WAKE      1  
#endif  
  
#ifndef __NR_futex  
#define __NR_futex     202  
#endif  
#endif  
  
#define FILE_MODE (S_IRUSR | S_IWUSR)  
  
const char shmfile[] = "/tmp";  
const int size = 100;  
  
struct namelist   
{  
    int  id;   
    char name[20];  
};  
  
int   
main(void)  
{  
    int fd, pid, status;      
    int *ptr;  
    struct stat stat;  
          
    // create a Posix shared memory  
    int flags = O_RDWR | O_CREAT;  
    fd = shm_open(shmfile, flags, FILE_MODE);  
    if (fd < 0)  
    {  
        printf("shm_open failed, errormsg=%s errno=%d", strerror(errno), errno);  
        return 0;  
    }  
    ftruncate(fd, size);  
    ptr = (int *)mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);     
  
    pid = fork();  
    if (pid == 0) { // child process  
        sleep(5);  
        printf("Child %d: start/n", getpid());  
          
        fd = shm_open(shmfile, flags, FILE_MODE);  
        fstat(fd, &stat);         
        ptr = (int *)mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);     
        close(fd);  
        struct namelist tmp;  
  
        // store total num in ptr[0];  
        *ptr = 3;  
          
        namelist *cur = (namelist *)(ptr+1);  
  
        // store items  
        tmp.id = 1;  
        strcpy(tmp.name, "Nellson");  
        *cur++ = tmp;  
        tmp.id = 2;  
        strcpy(tmp.name, "Daisy");  
        *cur++ = tmp;  
        tmp.id = 3;  
        strcpy(tmp.name, "Robbie");  
        *cur++ = tmp;  
  
        printf("wake up parent/n");  
        syscall(__NR_futex ,ptr, FUTEX_WAKE, 1, NULL );  
  
        exit(0);  
    } else{ // parent process  
        printf("parent start waiting/n");  
        syscall(__NR_futex , ptr, FUTEX_WAIT, *(int *)ptr, NULL );  
        printf("parent end waiting/n");  
  
        struct namelist tmp;  
  
        int total = *ptr;  
        printf("/nThere is %d item in the shm/n", total);     
          
        ptr++;  
        namelist *cur = (namelist *)ptr;  
  
        for (int i = 0; i< total; i++) {  
            tmp = *cur;  
            printf("%d: %s/n", tmp.id, tmp.name);  
            cur++;  
        }  
  
        printf("/n");  
        waitpid(pid, &status, 0);  
    }  
  
    // remvoe a Posix shared memory from system  
    printf("Parent %d get child status:%d/n", getpid(), status);  
    return 0;  
}  

上層應(yīng)用

互斥鎖pthread_mutex_t的實現(xiàn)原理

// pthread_mutex_lock:
atomic_dec(pthread_mutex_t.value);
if (pthread_mutex_t.value!=0)
  futex(WAIT)
else
  success

// pthread_mutex_unlock:
atomic_inc(pthread_mutex_t.value);
if(pthread_mutex_t.value!=1)
futex(WAKEUP)
else
success

信號量sem_t的實現(xiàn)原理

sem_wait(sem_t *sem)
{
for (;;) {
   if (atomic_decrement_if_positive(sem->count))
       break;
   futex_wait(&sem->count, 0)
   }
}

sem_post(sem_t *sem)
{
   n = atomic_increment(sem->count);
   // Pass the new value of sem->count
   futex_wake(&sem->count, n + 1);
}

論文
參考一
參考二
https://github.com/torvalds/linux/blob/master/kernel/futex.c

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市片吊,隨后出現(xiàn)的幾起案子绽昏,更是在濱河造成了極大的恐慌,老刑警劉巖俏脊,帶你破解...
    沈念sama閱讀 212,657評論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件全谤,死亡現(xiàn)場離奇詭異,居然都是意外死亡爷贫,警方通過查閱死者的電腦和手機认然,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,662評論 3 385
  • 文/潘曉璐 我一進(jìn)店門补憾,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人卷员,你說我怎么就攤上這事盈匾。” “怎么了毕骡?”我有些...
    開封第一講書人閱讀 158,143評論 0 348
  • 文/不壞的土叔 我叫張陵削饵,是天一觀的道長蛔添。 經(jīng)常有香客問我孽拷,道長丛晦,這世上最難降的妖魔是什么怪蔑? 我笑而不...
    開封第一講書人閱讀 56,732評論 1 284
  • 正文 為了忘掉前任捷绑,我火速辦了婚禮窖认,結(jié)果婚禮上弊攘,老公的妹妹穿的比我還像新娘镶柱。我一直安慰自己握爷,他們只是感情好跛璧,可當(dāng)我...
    茶點故事閱讀 65,837評論 6 386
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著新啼,像睡著了一般赡模。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上师抄,一...
    開封第一講書人閱讀 50,036評論 1 291
  • 那天漓柑,我揣著相機與錄音,去河邊找鬼叨吮。 笑死辆布,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的茶鉴。 我是一名探鬼主播锋玲,決...
    沈念sama閱讀 39,126評論 3 410
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼涵叮!你這毒婦竟也來了惭蹂?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 37,868評論 0 268
  • 序言:老撾萬榮一對情侶失蹤割粮,失蹤者是張志新(化名)和其女友劉穎盾碗,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體舀瓢,經(jīng)...
    沈念sama閱讀 44,315評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡廷雅,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,641評論 2 327
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片航缀。...
    茶點故事閱讀 38,773評論 1 341
  • 序言:一個原本活蹦亂跳的男人離奇死亡商架,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出芥玉,到底是詐尸還是另有隱情蛇摸,我是刑警寧澤,帶...
    沈念sama閱讀 34,470評論 4 333
  • 正文 年R本政府宣布灿巧,位于F島的核電站皇型,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏砸烦。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 40,126評論 3 317
  • 文/蒙蒙 一绞吁、第九天 我趴在偏房一處隱蔽的房頂上張望幢痘。 院中可真熱鬧,春花似錦家破、人聲如沸颜说。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,859評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽门粪。三九已至,卻和暖如春烹困,著一層夾襖步出監(jiān)牢的瞬間玄妈,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,095評論 1 267
  • 我被黑心中介騙來泰國打工髓梅, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留拟蜻,地道東北人。 一個月前我還...
    沈念sama閱讀 46,584評論 2 362
  • 正文 我出身青樓枯饿,卻偏偏與公主長得像酝锅,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子奢方,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 43,676評論 2 351

推薦閱讀更多精彩內(nèi)容