Rust 中的无锁编程技术(四)

在之前的博客里面,我们通过最基本的SpinLock的实现对锁有一个比较完整的认识了,但同时我也指出了自旋锁实际上是相当粗糙的,我们只要仔细想想其工作原理就会发现,最大的问题是线程与线程之间毫无公平性可言,导致这个结果的本质原因是对于Atomic类的对于不同线程之间是完全随机的,也就是这个函数没有办法控制哪个线程将会成功置换共享内存中的值。

那么从理论上来讲,如果我们的操作系统没有很好的处理好CPU调度的优先级的问题,有可能有的线程会饿死,而有的线程可能可以一直占据共有资源。那么我们如何解决这个问题呢?

一个更好的模型(TicketLock)

我们先思考一下SpinLock的模型:

有多个线程在同时试着置换其的。

OS会在这些线程中随机选一个线程,让其成功置换的值。

其他线程会一直卡在代码某处,一直自旋。

当上一个线程结束了对共享资源的使用后,会回到上诉的第二点。

这就好像我们去银行办业务,但是只有一个窗口,大家都挤在这个窗口前面,谁将会是下一个可以办业务的人完全看业务员的心情。更好的做法应该是叫号的模式,我们现在去银行,都会提前去前台拿一个号码,当上一个人的业务办完了,就轮到了持有下一个号码的人去办业务。即使有许多人同时去办业务,前台的工作人员也会按顺序给每一个前来办业务的人一个独有的号码。比起第一种模式,这种模式就会更加的公平,确保了先到先得的顺序。我们可以将这种模式运用到锁的实现里面,这个就是我们常说的TicketLock。

比起SpinLock,TicketLock维护了两个共享变量,以及,其语义表示的是当前正在处理的号码及下一个将会处理的号码。我们来看一下以及函数的实现:

我们还是忽略掉。类型会提供一个的函数,我们还是先忽略掉关于Memory Ordering的参数,函数和一般我们认识的自加函数类似,但是是适用于多线程编程环境的。打个比方,比如100个线程同时对一个变量进行一次操作,并且的初始值为0,那么我们最后得到的结果一定是100,因为这个是CPU指令集给我们提供的最小的保障了。但是如果是一个普通的的变量,那么我们是无法保证最后的结果是100的,有可能是小于或等于100的任何的值。所以通过这个函数,我们可以确保我们的ticket一定是单调线性递增的,并且每个ticket之间相差为1。

那么我们来思考下假设现在有许多线程同时在调用TicketLock的函数,那么每个线程都会得到一个唯一的ticket,如果像我们的例子中,是从0开始的,那么接下来的线程会得到的ticket将会是1,2,3,4…这样的顺序排列下去。

接下来,每个线程都会卡在以下这一行。

在这里每个线程相当于在等待叫号,如果当前办业务的号码并不是自己手里的号码,那么这个线程将会在这个位置等待,直到叫到自己的号码为止才可以继续执行下去。值得注意的地方是,每个线程在拿号的时候,用的是,而线程在等待的时候用的是,其实从语义上来讲,这个是非常好理解的。拿号的时候,我们用的是,而真正等叫号的是。

有了上面对语义的理解,接下来的函数便非常好理解了,当上一个线程结束了对共享资源的使用后,就会,也就是准备让窗口的业务员叫下一个号码,因此,我们在函数中将当前的增加1,这时候,之前卡在处,并且号码是上一个线程ticket的值+1的线程便可以跳出循环得到了共享资源的使用权。

我们可以看到,TicketLock比起SpinLock在实现上面巧妙的运用了。在之前的SpinLock中,就是,并没有好好利用其传递的特性,我们仔细想想,当一个线程成功时,获取了,表示其可以独占共享资源,当这个线程的时候,会作为一个参数传入到函数中,TicketLock通过一个共享变量将上一个线程的信息传递给了下一个线程,这样的实现方式使得线程间具有了公平性。

但是事情并没有那么美好,无论是SpinLock还是TicketLock,所有的线程都在为同一个内存空间在打架,在SpinLock中,线程们都在争夺一个,在TicketLock中,线程们都在争夺一个()。其实这样的设计从资源利用的角度来看是很不好的。

从OS的角度来看,每一次线程的切换,都会有Context Swtich,这对于系统来说都是一笔不小的开销,并且对多个线程同时访问同一个Atomic的内存地址来说,必须要等前一个线程访问结束了,才可以换下一个线程。

那么解决这个问题的思路就是我们能不能通过内存来换取系统等待的时间?最理想的情况就是每个线程只需要访问自己独有的一个内存空间,我们的设计尽量要减少对同一个共享变量访问的线程的数量。这个就是下一个博客会介绍的内容,CLHLock的实现。

相关文章