深入理解Linux内核的futex同步机制
在关于同步的一点思考-下一文中,我们知道glibc的pthread_cond_timedwait
底层是用linux futex机制实现的。
更多文章见个人博客:https://github.com/farmerjohngit/myblog
理想的同步机制应该是没有锁冲突时在用户态利用原子指令就解决问题,而需要挂起等待时再使用内核提供的系统调用进行睡眠与唤醒。换句话说,在用户态的自旋失败时,能不能让进程挂起,由持有锁的线程释放锁时将其唤醒?
如果你没有较深入地考虑过这个问题,很可能想当然的认为类似于这样就行了(伪代码):
void lock(int lockval) {
//trylock是用户级的自旋锁
while(!trylock(lockval)) {
wait();//释放cpu,并将当期线程加入等待队列,是系统调用
}
}
boolean trylock(int lockval){
int i=0;
//localval=1代表上锁成功
while(!compareAndSet(lockval,0,1)){
if(++i>10){
return false;
}
}
return true;
}
void unlock(int lockval) {
compareAndSet(lockval,1,0);
notify();
}
上述代码的问题是trylock和wait两个调用之间存在一个窗口:
如果一个线程trylock失败,在调用wait时持有锁的线程释放了锁,当前线程还是会调用wait进行等待,但之后就没有人再唤醒该线程了。
为了解决上述问题,linux内核引入了futex机制,futex主要包括等待和唤醒两个方法:futex_wait
和futex_wake
,其定义如下
//uaddr指向一个地址,val代表这个地址期待的值,当*uaddr==val时,才会进行wait
int futex_wait(int *uaddr, int val);
//唤醒n个在uaddr指向的锁变量上挂起等待的进程
int futex_wake(int *uaddr, int n);
futex在真正将进程挂起之前会检查addr指向的地址的值是否等于val,如果不相等则会立即返回,由用户态继续trylock。否则将当期线程插入到一个队列中去,并挂起。
在关于同步的一点思考-上文章中对futex的背景与基本原理有介绍,对futex不熟悉的人可以先看下。
本文将深入分析futex的实现,让读者对于锁的最底层实现方式有直观认识,再结合之前的两篇文章(关于同步的一点思考-上和关于同步的一点思考-下)能对操作系统的同步机制有个全面的理解。
下文中的进程一词包括常规进程与线程。
futex_wait
在看下面的源码分析前,先思考一个问题:如何确保挂起进程时,val的值是没有被其他进程修改过的?
代码在kernel/futex.c中
static int futex_wait(u32 __user *uaddr, int fshared,
u32 val, ktime_t *abs_time, u32 bitset, int clockrt)
{
struct hrtimer_sleeper timeout, *to = NULL;
struct restart_block *restart;
struct futex_hash_bucket *hb;
struct futex_q q;
int ret;
...
//设置hrtimer定时任务:在一定时间(abs_time)后,如果进程还没被唤醒则唤醒wait的进程
if (abs_time) {
...
hrtimer_init_sleeper(to, current);
...
}
retry:
//该函数中判断uaddr指向的值是否等于val,以及一些初始化操作
ret = futex_wait_setup(uaddr, val, fshared, &q, &hb);
//如果val发生了改变,则直接返回
if (ret)
goto out;
//将当前进程状态改为TASK_INTERRUPTIBLE,并插入到futex等待队列,然后重新调度。
futex_wait_queue_me(hb, &q, to);
/* If we were woken (and unqueued), we succeeded, whatever. */
ret = 0;
//如果unqueue_me成功,则说明是超时触发(因为futex_wake唤醒时,会将该进程移出等待队列,所以这里会失败)
if (!unqueue_me(&q))
goto out_put_key;
ret = -ETIMEDOUT;
if (to && !to->task)
goto out_put_key;
/*
* We expect signal_pending(current), but we might be the
* victim of a spurious wakeup as well.
*/
if (!signal_pending(current)) {
put_futex_key(fshared, &q.key);
goto retry;
}
ret = -ERESTARTSYS;
if (!abs_time)
goto out_put_key;
...
out_put_key:
put_futex_key(fshared, &q.key);
out:
if (to) {
//取消定时任务
hrtimer_cancel(&to->timer);
destroy_hrtimer_on_stack(&to->timer);
}
return ret;
}
在将进程阻塞前会将当期进程插入到一个等待队列中,需要注意的是这里说的等待队列其实是一个类似Java HashMap的结构,全局唯一。
struct futex_hash_bucket {
spinlock_t lock;
//双向链表
struct plist_head chain;
};
static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];
着重看futex_wait_setup
和两个函数futex_wait_queue_me
static int futex_wait_setup(u32 __user *uaddr, u32 val, int fshared,
struct futex_q *q, struct futex_hash_bucket **hb)
{
u32 uval;
int ret;
retry:
q->key = FUTEX_KEY_INIT;
//初始化futex_q
ret = get_futex_key(uaddr, fshared, &q->key, VERIFY_READ);
if (unlikely(ret != 0))
return ret;
retry_private:
//获得自旋锁
*hb = queue_lock(q);
//原子的将uaddr的值设置到uval中
ret = get_futex_value_locked(&uval, uaddr);
...
//如果当期uaddr指向的值不等于val,即说明其他进程修改了
//uaddr指向的值,等待条件不再成立,不用阻塞直接返回。
if (uval != val) {
//释放锁
queue_unlock(q, *hb);
ret = -EWOULDBLOCK;
}
...
return ret;
}
函数futex_wait_setup
中主要做了两件事,一是获得自旋锁,二是判断*uaddr是否为预期值。
static void futex_wait_queue_me(struct futex_hash_bucket *hb, struct futex_q *q,
struct hrtimer_sleeper *timeout)
{
//设置进程状态为TASK_INTERRUPTIBLE,cpu调度时只会选择
//状态为TASK_RUNNING的进程
set_current_state(TASK_INTERRUPTIBLE);
//将当期进程(q封装)插入到等待队列中去,然后释放自旋锁
queue_me(q, hb);
//启动定时任务
if (timeout) {
hrtimer_start_expires(&timeout->timer, HRTIMER_MODE_ABS);
if (!hrtimer_active(&timeout->timer))
timeout->task = NULL;
}
/*
* If we have been removed from the hash list, then another task
* has tried to wake us, and we can skip the call to schedule().
*/
if (likely(!plist_node_empty(&q->list))) {
//如果没有设置过期时间 || 设置了过期时间且还没过期
if (!timeout || timeout->task)
//系统重新进行进程调度,这个时候cpu会去执行其他进程,该进程会阻塞在这里
schedule();
}
//走到这里说明又被cpu选中运行了
__set_current_state(TASK_RUNNING);
}
futex_wait_queue_me
中主要做几件事:
- 将当期进程插入到等待队列
- 启动定时任务
- 重新调度进程
如何保证条件与等待之间的原子性
在futex_wait_setup
方法中会加自旋锁;在futex_wait_queue_me
中将状态设置为TASK_INTERRUPTIBLE
,调用queue_me
将当期线程插入到等待队列中,然后才释放自旋锁。也就是说检查uaddr的值的过程跟进程挂起的过程放在同一个临界区中。当释放自旋锁后,这时再更改addr地址的值已经没有关系了,因为当期进程已经加入到等待队列中,能被wake唤醒,不会出现本文开头提到的没人唤醒的问题。
futex_wait小结
总结下futex_wait
流程:
- 加自旋锁
- 检测*uaddr是否等于val,如果不相等则会立即返回
- 将进程状态设置为
TASK_INTERRUPTIBLE
- 将当期进程插入到等待队列中
- 释放自旋锁
- 创建定时任务:当超过一定时间还没被唤醒时,将进程唤醒
- 挂起当前进程
futex_wake
futex_wake
static int futex_wake(u32 __user *uaddr, int fshared, int nr_wake, u32 bitset)
{
struct futex_hash_bucket *hb;
struct futex_q *this, *next;
struct plist_head *head;
union futex_key key = FUTEX_KEY_INIT;
int ret;
...
//根据uaddr的值填充&key的内容
ret = get_futex_key(uaddr, fshared, &key, VERIFY_READ);
if (unlikely(ret != 0))
goto out;
//根据&key获得对应uaddr所在的futex_hash_bucket
hb = hash_futex(&key);
//对该hb加自旋锁
spin_lock(&hb->lock);
head = &hb->chain;
//遍历该hb的链表,注意链表中存储的节点是plist_node类型,而而这里的this却是futex_q类型,这种类型转换是通过c中的container_of机制实现的
plist_for_each_entry_safe(this, next, head, list) {
if (match_futex (&this->key, &key)) {
...
//唤醒对应进程
wake_futex(this);
if (++ret >= nr_wake)
break;
}
}
//释放自旋锁
spin_unlock(&hb->lock);
put_futex_key(fshared, &key);
out:
return ret;
}
futex_wake
流程如下:
- 找到uaddr对应的
futex_hash_bucket
,即代码中的hb - 对hb加自旋锁
- 遍历fb的链表,找到uaddr对应的节点
- 调用
wake_futex
唤起等待的进程 - 释放自旋锁
wake_futex
中将制定进程状态设置为TASK_RUNNING
并加入到系统调度列表中,同时将进程从futex的等待队列中移除掉,具体代码就不分析了,有兴趣的可以自行研究。
End
Java中的ReentrantLock,Object.wait和Thread.sleep等等底层都是用futex进行线程同步,理解futex的实现能帮助你更好的理解与使用这些上层的同步机制。另外因篇幅与精力有限,涉及到进程调度的相关内容没有具体分析,不过并不妨碍理解文章内容,
推荐阅读
-
深入探究 Linux 内核可装载模块的版本检查机制
-
深入理解Linux内核调试技术——kprobe的使用和实现(第二部分)
-
深入理解微服务架构:Soul微服务网关的数据同步机制
-
理解Linux内核中的spinlock_t自旋锁机制
-
理解Linux的同步机制(1):从线程锁入手
-
深入理解Linux内核的futex同步机制
-
深入理解 Linux 中的线程锁机制
-
epoll简介及触发模式(accept、read、send)-epoll的简单介绍 epoll在LT和ET模式下的读写方式 一、epoll的接口非常简单,一共就三个函数:1. int epoll_create(int size);创建一个epoll的句柄,size用来告诉内核这个监听的数目一共有多大。这个参数不同于select中的第一个参数,给出最大监听的fd+1的值。需要注意的是,当创建好epoll句柄后,它就是会占用一个fd值,在linux下如果查看/proc/进程id/fd/,是能够看到这个fd的,所以在使用完epoll后,必须调用close关闭,否则可能导致fd被耗尽。2. int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);epoll的事件注册函数,它不同与select是在监听事件时告诉内核要监听什么类型的事件,而是在这里先注册要监听的事件类型。第一个参数是epoll_create的返回值,第二个参数表示动作,用三个宏来表示:EPOLL_CTL_ADD:注册新的fd到epfd中;EPOLL_CTL_MOD:修改已经注册的fd的监听事件;EPOLL_CTL_DEL:从epfd中删除一个fd;第三个参数是需要监听的fd,第四个参数是告诉内核需要监听什么事,struct epoll_event结构如下:struct epoll_event { __uint32_t events; /* Epoll events */ epoll_data_t data; /* User data variable */};events可以是以下几个宏的集合:EPOLLIN :表示对应的文件描述符可以读(包括对端SOCKET正常关闭); EPOLLIN事件:EPOLLIN事件则只有当对端有数据写入时才会触发,所以触发一次后需要不断读取所有数据直到读完EAGAIN为止。否则剩下的数据只有在下次对端有写入时才能一起取出来了。现在明白为什么说epoll必须要求异步socket了吧?如果同步socket,而且要求读完所有数据,那么最终就会在堵死在阻塞里。 EPOLLOUT:表示对应的文件描述符可以写; EPOLLOUT事件:EPOLLOUT事件只有在连接时触发一次,表示可写,其他时候想要触发,那要先准备好下面条件:1.某次write,写满了发送缓冲区,返回错误码为EAGAIN。2.对端读取了一些数据,又重新可写了,此时会触发EPOLLOUT。简单地说:EPOLLOUT事件只有在不可写到可写的转变时刻,才会触发一次,所以叫边缘触发,这叫法没错的!其实,如果真的想强制触发一次,也是有办法的,直接调用epoll_ctl重新设置一下event就可以了,event跟原来的设置一模一样都行(但必须包含EPOLLOUT),关键是重新设置,就会马上触发一次EPOLLOUT事件。1. 缓冲区由满变空.2.同时注册EPOLLIN | EPOLLOUT事件,也会触发一次EPOLLOUT事件这个两个也会触发EPOLLOUT事件 EPOLLPRI:表示对应的文件描述符有紧急的数据可读(这里应该表示有带外数据到来);EPOLLERR:表示对应的文件描述符发生错误;EPOLLHUP:表示对应的文件描述符被挂断;EPOLLET: 将EPOLL设为边缘触发(Edge Triggered)模式,这是相对于水平触发(Level Triggered)来说的。EPOLLONESHOT:只监听一次事件,当监听完这次事件之后,如果还需要继续监听这个socket的话,需要再次把这个socket加入到EPOLL队列里3. int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);等待事件的产生,类似于select调用。参数events用来从内核得到事件的集合,maxevents告之内核这个events有多大,这个maxevents的值不能大于创建epoll_create时的size,参数timeout是超时时间(毫秒,0会立即返回,-1将不确定,也有说法说是永久阻塞)。该函数返回需要处理的事件数目,如返回0表示已超时。-------------------------------------------------------------------------------------------- 从man手册中,得到ET和LT的具体描述如下EPOLL事件有两种模型:Edge Triggered (ET)Level Triggered (LT)假如有这样一个例子:1. 我们已经把一个用来从管道中读取数据的文件句柄(RFD)添加到epoll描述符2. 这个时候从管道的另一端被写入了2KB的数据3. 调用epoll_wait(2),并且它会返回RFD,说明它已经准备好读取操作4. 然后我们读取了1KB的数据5. 调用epoll_wait(2)......Edge Triggered 工作模式:如果我们在第1步将RFD添加到epoll描述符的时候使用了EPOLLET标志,那么在第5步调用epoll_wait(2)之后将有可能会挂起,因为剩余的数据还存在于文件的输入缓冲区内,而且数据发出端还在等待一个针对已经发出数据的反馈信息。只有在监视的文件句柄上发生了某个事件的时候 ET 工作模式才会汇报事件。因此在第5步的时候,调用者可能会放弃等待仍在存在于文件输入缓冲区内的剩余数据。在上面的例子中,会有一个事件产生在RFD句柄上,因为在第2步执行了一个写操作,然后,事件将会在第3步被销毁。因为第4步的读取操作没有读空文件输入缓冲区内的数据,因此我们在第5步调用 epoll_wait(2)完成后,是否挂起是不确定的。epoll工作在ET模式的时候,必须使用非阻塞套接口,以避免由于一个文件句柄的阻塞读/阻塞写操作把处理多个文件描述符的任务饿死。最好以下面的方式调用ET模式的epoll接口,在后面会介绍避免可能的缺陷。 i 基于非阻塞文件句柄 ii 只有当read(2)或者write(2)返回EAGAIN时才需要挂起,等待。但这并不是说每次read时都需要循环读,直到读到产生一个EAGAIN才认为此次事件处理完成,当read返回的读到的数据长度小于请求的数据长度时,就可以确定此时缓冲中已没有数据了,也就可以认为此事读事件已处理完成。Level Triggered 工作模式相反的,以LT方式调用epoll接口的时候,它就相当于一个速度比较快的poll(2),并且无论后面的数据是否被使用,因此他们具有同样的职能。因为即使使用ET模式的epoll,在收到多个chunk的数据的时候仍然会产生多个事件。调用者可以设定EPOLLONESHOT标志,在 epoll_wait(2)收到事件后epoll会与事件关联的文件句柄从epoll描述符中禁止掉。因此当EPOLLONESHOT设定后,使用带有 EPOLL_CTL_MOD标志的epoll_ctl(2)处理文件句柄就成为调用者必须作的事情。然后详细解释ET, LT:LT(level triggered)是缺省的工作方式,并且同时支持block和no-block socket.在这种做法中,内核告诉你一个文件描述符是否就绪了,然后你可以对这个就绪的fd进行IO操作。如果你不作任何操作,内核还是会继续通知你的,所以,这种模式编程出错误可能性要小一点。传统的select/poll都是这种模型的代表.ET(edge-triggered)是高速工作方式,只支持no-block socket。在这种模式下,当描述符从未就绪变为就绪时,内核通过epoll告诉你。然后它会假设你知道文件描述符已经就绪,并且不会再为那个文件描述符发送更多的就绪通知,直到你做了某些操作导致那个文件描述符不再为就绪状态了(比如,你在发送,接收或者接收请求,或者发送接收的数据少于一定量时导致了一个EWOULDBLOCK 错误)。但是请注意,如果一直不对这个fd作IO操作(从而导致它再次变成未就绪),内核不会发送更多的通知(only once),不过在TCP协议中,ET模式的加速效用仍需要更多的benchmark确认(这句话不理解)。在许多测试中我们会看到如果没有大量的idle -connection或者dead-connection,epoll的效率并不会比select/poll高很多,但是当我们遇到大量的idle- connection(例如WAN环境中存在大量的慢速连接),就会发现epoll的效率大大高于select/poll。(未测试)另外,当使用epoll的ET模型来工作时,当产生了一个EPOLLIN事件后,读数据的时候需要考虑的是当recv返回的大小如果等于请求的大小,那么很有可能是缓冲区还有数据未读完,也意味着该次事件还没有处理完,所以还需要再次读取: 这里只是说明思路(参考《UNIX网络编程》) while(rs) {buflen = recv(activeevents[i].data.fd, buf, sizeof(buf), 0);if(buflen < 0){// 由于是非阻塞的模式,所以当errno为EAGAIN时,表示当前缓冲区已无数据可读// 在这里就当作是该次事件已处理处.if(errno == EAGAIN)break; else return; }else if(buflen == 0) { // 这里表示对端的socket已正常关闭. } if(buflen == sizeof(buf) rs = 1; // 需要再次读取 else rs = 0; } 还有,假如发送端流量大于接收端的流量(意思是epoll所在的程序读比转发的socket要快),由于是非阻塞的socket,那么send函数虽然返回,但实际缓冲区的数据并未真正发给接收端,这样不断的读和发,当缓冲区满后会产生EAGAIN错误(参考man send),同时,不理会这次请求发送的数据.所以,需要封装socket_send的函数用来处理这种情况,该函数会尽量将数据写完再返回,返回-1表示出错。在socket_send内部,当写缓冲已满(send返回-1,且errno为EAGAIN),那么会等待后再重试.这种方式并不很完美,在理论上可能会长时间的阻塞在socket_send内部,但暂没有更好的办法. ssize_t socket_send(int sockfd, const char* buffer, size_t buflen) { ssize_t tmp; size_t total = buflen; const char *p = buffer; while(1) { tmp = send(sockfd, p, total, 0); if(tmp < 0) { // 当send收到信号时,可以继续写,但这里返回-1. if(errno == EINTR) return -1; // 当socket是非阻塞时,如返回此错误,表示写缓冲队列已满, // 在这里做延时后再重试. if(errno == EAGAIN) { usleep(1000); continue; } return -1; } if((size_t)tmp == total) return buflen; total -= tmp; p += tmp; } return tmp; } 二、epoll在LT和ET模式下的读写方式 在一个非阻塞的socket上调用read/write函数, 返回EAGAIN或者EWOULDBLOCK(注: EAGAIN就是EWOULDBLOCK) 从字面上看, 意思是: * EAGAIN: 再试一次 * EWOULDBLOCK: 如果这是一个阻塞socket, 操作将被block * perror输出: Resource temporarily unavailable 总结: 这个错误表示资源暂时不够, 可能read时, 读缓冲区没有数据, 或者, write时,写缓冲区满了 。 遇到这种情况, 如果是阻塞socket, read/write就要阻塞掉。 而如果是非阻塞socket, read/write立即返回-1, 同 时errno设置为EAGAIN. 所以, 对于阻塞socket, read/write返回-1代表网络出错了. 但对于非阻塞socket, read/write返回-1不一定网络真的出错了. 可能是Resource temporarily unavailable. 这时你应该再试, 直到Resource available. 综上, 对于non-blocking的socket, 正确的读写操作为: 读: 忽略掉errno = EAGAIN的错误, 下次继续读 写: 忽略掉errno = EAGAIN的错误, 下次继续写 对于select和epoll的LT模式, 这种读写方式是没有问题的. 但对于epoll的ET模式, 这种方式还有漏洞. epoll的两种模式 LT 和 ET
-
深入理解Linux内核的流量控制机制(第11篇)
-
理解Linux中uname命令的-s, -r, -a参数:深入查看内核版本的方法