这个是对之前分析的 mutex、rwmutex、condition、semaphore的回顾和总结.

论文参考

  1. https://swtch.com/semaphore.pdf 谈到 plan9 使用 user-space semaphore 代替 多进程协调中的flag状态的 spin lock. user-space semaphore 使用一个字段表示用户状态下的sema值, 0->1 就是非竞态. 竞态情况下, 使用 内核的 QLock 排队锁 实现.
    其中, 谈到 多进程的内核中, 自旋锁是可以的, 因为锁会被很快释放. 但是在用户态, 自旋锁状态下, 需要不断调度自己 + sleep, 其实什么也没有做.

golang中提供给用户的 Mutex 就是参照这个实现的, 先用 state 表示状态, 初始状态下直接获取锁, 并发争抢的时候, 进入semaRoot的逻辑, 形成sudog队列; 非抢占情况下, 只是简单的一次cas.

futex: redhat的文章 连接不上不去, 参照man

概念解析

  • sudog: goroutine 的 wait的表示, channel和 sudog是多对多的, 一个goroutine可能阻塞在多个对象上, 一个对象可能有多个 goroutine阻塞着, 使用 sudog解耦.

  • 内部mutex: golang自定义的mutex实现, 通过对指针地址操作实现. 最差情况下, 是系统的semaphore. 采用了优化策略, cas -> 空循环 -> os yield -> semaphore. 进入semaphore状态的时候, 是多线程争抢, 存在线程排队的现象, 使用m的字段nextwaitm实现链表排队, 支持抢占.

  • semaRoot: 依赖内部的mutex实现的锁, 使用平衡树维护被锁的地址, 阻塞在同一个地址的sudog被维护在一个叶子上, sudog通过链表维护. 但是只维护了 251 个 semaRoot, 也就是说最多同时锁住 251 个地址.

  • Mutex实现: 直接依赖 semaRoot 实现.

  • cond实现: 依赖内部mutex提供锁的语义, 使用notifyList 维护等待的goroutine. 避免Wait + Signal + Broadcast竞争. 还依赖外部Mutex实现ticket生成的锁

  • syncmap:

  • rwmutex:

  • pool: 每个p都有一个private成员 以及一个 shared 链表, 每次获取, 先获取p本地的private成员, 没有, 就遍历p, 尝试获取shared链表, 还是没有, 就生成一个。但是，每次gc都会清除每个p的private和shared成员

问题: 对比 cond.go 和 Mutex, 因为Mutex更多的是 外部优化, 这里直接对比 cond.go 和 semaRoot.
cond.go 使用了 notifyList, 但是 semaRoot使用 平衡树 + goroutine链表 实现. cond.go 使用head、tail维护sudog链表, semaRoot使用sudog本身的next字段维护, 为什么有这个差异呢？ 1. condition提供了 Wait + Signal + Broadcast 的语义, 实现上, 就是支持添加一个等待者、释放一个等待者、释放所有等待者, 并且Wait是放在列表尾部, Signal是在头部. 3. condition的notifyList用自己的地址 作为 内部mutex锁的地址 4. condition的notifyList 使用 head、tail 两个sudog 维护列表. O(1)复杂度 3. Mutex 提供了 Lock + UnLock 的语义, 借助semaRoot, 默认插入链表的最后面, 也支持插入到前面, 删除的时候, 肯定是删除的头部.
4. Semaroot 使用内部的 mutex 锁住 root 的lock,[ 这样, root 只有251个, Mutex很多的话, 并且lock/ublock比较频繁的话, 抢锁只会在 指定的数量上 的lock竞争. (condition做不到) … ] 4. SemaRoot 只用了一个 sudog 实现了 头部和尾部, 通过sudog的 waitlink 和 waittail.O(1) 复杂度 5. 所以, 从操作的特征上, 两者是类似的. Mutex借助 semaroot, 插入可以定制化(前面或者后面), 都是O(1), 删除的都是头部. cond.go 中 notifyList 是 插入尾部, 删除头部, 也是O(1). 6. 因为 sudog 给 semaRoot 开了后门, 所以只需要一个就可以了.
6. semaRoot 进行了锁的优化.

看下 commit 信息

关于优化点:

  • cond的实现, 本身就需要 Mutex提供互斥语义, 但是只是提供了 生成ticket 的锁的语义. 在 Signal + Broadcast, 并没有 Mutex 加锁的操作, 是依靠 notifyList + 内部 mutex 实现的. 那么, 就一个优化点而言, cond.go 直接依赖 内部的mutex是否可以? 这样, 就避免多依赖一个 Mutex了, 实现能够更干净.