Java多线程同步内部如何实现的( 二 )


futexlinux底层用futex实现锁,futex由一个内核层的队列和一个用户空间层的atomic integer构成 。当获得锁时,尝试cas更改integer,如果integer原始值是0,则修改成功,该线程获得锁,否则就将当期线程放入到 wait queue中(即操作系统的等待队列) 。
上述说法有些抽象,如果你没看明白也没关系 。我们先看一下没有futex之前,linux是怎么实现锁的 。
futex诞生之前在futex诞生之前,linux下的同步机制可以归为两类:用户态的同步机制 和内核同步机制 。用户态的同步机制基本上就是利用原子指令实现的自旋锁 。关于自旋锁其缺点也说过了,不适用于大的临界区(即锁占用时间比较长的情况) 。
内核提供的同步机制,如semaphore等,使用的是上文说的自旋+等待的形式 。它对于大小临界区和都适用 。但是因为它是内核层的(释放cpu资源是内核级调用),所以每次lock与unlock都是一次系统调用,即使没有锁冲突,也必须要通过系统调用进入内核之后才能识别 。
理想的同步机制应该是没有锁冲突时在用户态利用原子指令就解决问题,而需要挂起等待时再使用内核提供的系统调用进行睡眠与唤醒 。换句话说,在用户态的自旋失败时,能不能让进程挂起,由持有锁的线程释放锁时将其唤醒? 如果你没有较深入地考虑过这个问题,很可能想当然的认为类似于这样就行了(伪代码):
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进行等待,但之后就没有人再将该线程唤醒了 。
futex诞生之后我们来看看futex的方法定义:
//uaddr指向一个地址,val代表这个地址期待的值,当*uaddr==val时,才会进行waitint futex_wait(int *uaddr, int val);//唤醒n个在uaddr指向的锁变量上挂起等待的进程int futex_wake(int *uaddr, int n);futex_wait真正将进程挂起之前会检查addr指向的地址的值是否等于val,如果不相等则会立即返回,由用户态继续trylock 。否则将当期线程插入到一个队列中去,并挂起 。
futex内部维护了一个队列,在线程挂起前会线程插入到其中,同时对于队列中的每个节点都有一个标识,代表该线程关联锁的uaddr 。这样,当用户态调用futex_wake时,只需要遍历这个等待队列,把带有相同uaddr的节点所对应的进程唤醒就行了 。
作为优化,futex维护的其实是个类似java 中的concurrent hashmap的结构 。其持有一个总链表,总链表中每个元素都是一个带有自旋锁的子链表 。调用futex_wait挂起的进程,通过其uaddr hash到某一个具体的子链表上去 。这样一方面能分散对等待队列的竞争、另一方面减小单个队列的长度,便于futex_wake时的查找 。每个链表各自持有一把spinlock,将"*uaddr和val的比较操作"与"把进程加入队列的操作"保护在一个临界区中 。另外,futex是支持多进程的,当使用futex在多进程间进行同步时,需要考虑同一个物理内存地址在不同进程中的虚拟地址是不同的 。

【Java多线程同步内部如何实现的】


推荐阅读