设为首页 - 加入收藏 核心网 ()- 云主机,资讯,互联网,人工智能,云计算,大赢家论坛,区块链,VR,站长网!
热搜: 2019 统一 潜艇 模式
当前位置: 主页 > 水果奶奶论坛 > 正文

Semaphore 数据结构分解详解

发布时间:2021-05-28 04:28 所属栏目:[水果奶奶论坛] 来源:互联网
导读://Go语言中暴露的semaphore实现 //具体的用法是提供sleep和wakeup原语 //以使其能够在其它同步原语中的竞争情况下使用 //因此这里的semaphore和Linux中的futex目

// Go 语言中暴露的 semaphore 实现 

// 具体的用法是提供 sleep 和 wakeup 原语 

// 以使其能够在其它同步原语中的竞争情况下使用 

// 因此这里的 semaphore 和 Linux 中的 futex 目标是一致的 

// 只不过语义上更简单一些 

// 

// 也就是说,不要认为这些是信号量 

// 把这里的东西看作 sleep 和 wakeup 实现的一种方式 

// 每一个 sleep 都会和一个 wakeup 配对 

// 即使在发生 race 时,wakeup 在 sleep 之前时也是如此 

// 

// See Mullender and Cox, ``Semaphores in Plan 9,'' 

//  

 

// 为 sync.Mutex 准备的异步信号量 

 

// semaRoot 持有一棵 地址各不相同的 sudog(s.elem) 的平衡树 

// 每一个 sudog 都反过来指向(通过 s.waitlink)一个在同一个地址上等待的其它 sudog 们 

// 同一地址的 sudog 的内部列表上的操作时间复杂度都是 O(1)。顶层 semaRoot 列表的扫描 

// 的时间复杂度是 O(log n),n 是被哈希到同一个 semaRoot 的不同地址的总数,每一个地址上都会有一些 goroutine 被阻塞。 

// 访问 golang.org/issue/17953 来查看一个在引入二级列表之前性能较差的程序样例,test/locklinear.go 

// 中有一个复现这个样例的测试 

type semaRoot struct { 

    lock  mutex 

    treap *sudog // root of balanced tree of unique waiters. 

    nwait uint32 // Number of waiters. Read w/o the lock. 

 

// Prime to not correlate with any user patterns. 

const semTabSize = 251 

 

var semtable [semTabSize]struct { 

    root semaRoot 

    pad  [sys.CacheLineSize - unsafe.Sizeof(semaRoot{})]byte 

 

func semroot(addr *uint32) *semaRoot { 

    return &semtable[(uintptr(unsafe.Pointer(addr))>>3)%semTabSize].root 

┌─────┬─────┬─────┬─────┬─────┬────────────────────────┬─────┐                  

│  0  │  1  │  2  │  3  │  4  │         .....          │ 250 │                  

└─────┴─────┴─────┴─────┴─────┴────────────────────────┴─────┘                  

   │                                                      │                     

   │                                                      │                     

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

网友评论
推荐文章