Semaphore 数据结构分解详解

│     parent *sudog     │───┘ └─────────────────────────│     parent *sudog     │ 

├───────────────────────┤                               ├───────────────────────┤ 

│  elem unsafe.Pointer  │                               │  elem unsafe.Pointer  │ 

├───────────────────────┤                               ├───────────────────────┤ 

│     ticket uint32     │                               │     ticket uint32     │ 

└───────────────────────┘                               └───────────────────────┘ 

在这个 treap 结构里，从 elem 的视角(其实就是 lock 的 addr)来看，这个结构是个二叉搜索树。从 ticket 的角度来看，整个结构就是一个小顶堆。

所以才叫树堆(treap)。

相同 addr，即对同一个 mutex 上锁的 g，会阻塞在同一个地址上。这些阻塞在同一个地址上的 goroutine 会被打包成 sudog，组成一个链表。用 sudog 的 waitlink 相连:

┌──────────┐                         ┌──────────┐                          ┌──────────┐              

│  sudog   │                  ┌─────▶│  sudog   │                   ┌─────▶│  sudog   │              

├──────────┴────────────┐     │      ├──────────┴────────────┐      │      ├──────────┴────────────┐ 

（编辑：ASP站长）

【免责声明】本站内容转载自互联网，其相关言论仅代表作者个人观点绝非权威，不代表本站立场。如您发现内容存在版权问题，请提交相关链接至邮箱：bqsm@foxmail.com，我们将及时予以处理。