介紹
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