时间戳

首页 > 解决方案 > Ktor 默认池

kotlin - Ktor 默认池

问题描述

参考Ktor Pool 实现，有人可以解释一下这个 pop 和 push 实现背后的概念。我试图单步执行代码，但在研究了代码后我仍然不聪明。

以下是我难以理解的代码片段：

   private fun pushTop(index: Int) {
    require(index > 0) { "index should be positive" }
    while (true) { // lock-free loop on top
        val top = this.top // volatile read
        val topVersion = (top shr 32 and 0xffffffffL) + 1L 
        val topIndex = (top and 0xffffffffL).toInt() 
        val newTop = topVersion shl 32 or index.toLong() 
        next[index] = topIndex
        if (Top.compareAndSet(this, top, newTop)) return
    }
}

private fun popTop(): Int {
    // lock-free loop on top
    while (true) {
        // volatile read
        val top = this.top
        if (top == 0L) return 0
        val newVersion = (top shr 32 and 0xffffffffL) + 1L
        val topIndex = (top and 0xffffffffL).toInt()
        if (topIndex == 0) return 0
        val next = next[topIndex]
        val newTop = newVersion shl 32 or next.toLong()
        if (Top.compareAndSet(this, top, newTop)) return topIndex
    }
}

这可以写成更简单的方法吗？

标签： kotlinpoolktor

解决方案

有两件事使这段代码看起来有点不寻常。第一个是它被设计为由多个线程访问而不使用锁。第二个是它使用单个 64 位值来存储两个 32 位整数。

锁定自由

这看起来像是无锁堆栈的一些变体。它被设计成可以同时被多个线程访问。粗略的算法是这样工作的：

  • 获取旧值并记录下来
  • 确定新值应该是什么
  • 当且仅当该值仍然与我们在开始时看到的旧值匹配时，执行原子比较和设置以替换该值
  • 如果比较和设置失败（即在我们计算新值时其他人更改了值），循环回到开始并重试

在某些类型的应用程序中，像这样的无锁算法可能更适合性能。另一种方法是锁定整个堆栈，这样当一个线程正在使用堆栈时，所有其他线程都必须等待。

位移位

使这段代码看起来更复杂的另一件事是它似乎将两个值存储在一个变量中。index传递给的值pushTop是一个 32 位整数。version然后在存储之前与 32 位递增计数器 结合。所以top实际上是一个 64 位的值，其中前 32 位是“版本”，后 32 位是我们传入的“索引”。同样，这种紧凑的存储格式可能是一种性能优化。

如果我们在代码中添加一些注释pushTop，它看起来像这样：

val top = this.top // get the current 64-bit value containing 'version' and 'index'
val topVersion = (top shr 32 and 0xffffffffL) + 1L  // get the 32 high bits (version) and add 1
val topIndex = (top and 0xffffffffL).toInt() // get the 32 low bits (the old index)
val newTop = topVersion shl 32 or index.toLong() // combine version and new index to a new 64-bit value

你可以看到很多相同的事情发生在popTop. 如果堆栈包含重复项，则可能包含版本号，以便无锁算法可以区分相同值的不同副本之间的差异。

推荐阅读