文档章节

走进Golang之Channel的数据结构

大愚Talk
 大愚Talk
发布于 06/27 11:03
字数 2106
阅读 1.2W
收藏 31

行业解决方案、产品招募中!想赚钱就来传!>>>

上篇文章讲了 channel 的基本使用,讲了一些使用时需要注意的事项,本文将重点介绍 channel 中的两个数据结构:循环队列双端链表

channel 的需求描述

为了理解这些数据结构解决了什么问题,我们先来做个简单的回顾,看看为什么需要这两个数据结构,他们解决了什么问题。我们知道 goroutine 是用户态的线程,不同的 goroutine 之间是有消息传递这个需求的。在原始的进程与线程(系统线程)编程中我们会采用管道的方式,而 channel 就是用户态线程传递消息的管道实现,并且是类型安全的。

既然 channel 是一个管道,用来满足不同 goroutine 间交换消息的。那么实现这样一个管道要怎么做呢?

来看看我们日常传递消息的需求:

  1. 能够有多个 goroutinechannel 进行读写,并且保证没有竞争问题,需要用 队列 来管理阻塞的 goroutine,解决竞争问题;
  2. 需要管理发送到 channel 的消息(有缓冲、无缓冲),对于有缓存的 channel 可以采用 循环队列 来管理多个消息。

当然上面的需求是经过简化的,比如 channel 还需要具备阻塞、唤醒 goroutine 的能力,不过为了本文我们更加专注焦点问题,先只关注上面两个问题。

channel 的数据结构

接下来我们分析一下 channel 在实际运行中,它的结构体是怎么样的。当然这又分为两种类型,有缓冲与无缓冲的。我们先来看一个无缓冲的情况。

无缓冲

先把示例代码贴出来。就是两个读的 goroutine 被阻塞在一个无缓冲的 channel 上。

func main() {
 ch := make(chan int// 无缓冲

 go goRoutineA(ch)
 go goRoutineB(ch)
 ch <- 1

 time.Sleep(time.Second * 1)
}

func goRoutineA(ch chan int) {
 v := <-ch
 fmt.Printf("A received data: %d\n", v)
}

func goRoutineB(ch chan int) {
 v := <-ch
 fmt.Printf("B received data: %d\n", v)
}

来看看当代码执行到 ch <- 1 这一行之后 channel 的结构体被填充成什么样子了!

无缓冲 channel

注意其中 buf 字段可存储的长度是0,这是因为 无缓冲 channel 不会用到循环队列来存储数据。它一定是等读、写 goroutine 都准备好了,然后直接把数据交给对方。我们用一副图来看一下无缓冲的数据交换过程。

交换数据

上图描述的是数据交换过程,再看一下读 goroutine 被阻塞的结构示意图。被阻塞的 goroutine 会挂载到对应的队列上,该队列是一个双端队列。

上面的例子,由于两个读 goroutine 在启动的时候,写还没有准备好,因此读全部被挂起在队列中;当有写goroutine准备好的时候,由于此时读已经就绪,因此写不会阻塞,挂起放到 sendq 中。大家可以修改上面的代码,自己看一下写阻塞,读立马执行的情况。

结构示例

有缓冲

我们将上面的代码改成有缓冲的通道,然后再来看看有缓冲的情况。

func main() {
 ch := make(chan int3// 有缓冲

 // 都不会阻塞
 ch <- 1
 ch <- 2
    ch <- 3
    // 会阻塞,被挂起到 sendq 中
 go func() {
  ch <- 4
 }()

 // 只是为了debug
 var a int
 fmt.Println(a)

 go goRoutineA(ch)
 go goRoutineA(ch)
 go goRoutineB(ch)
 go goRoutineB(ch) // 猜猜这里会被挂起吗?

 time.Sleep(time.Second * 2)
}

func goRoutineA(ch chan int) {
 v := <-ch
 fmt.Printf("A received data: %d\n", v)
}

func goRoutineB(ch chan int) {
 v := <-ch
 fmt.Printf("B received data: %d\n", v)
}

贴出执行到第一行的 go goRoutineA(ch) 时, hchan 的结构填充情况。

有缓冲 channel

在这里可以看到缓冲的大小是3,由于增加了缓冲,只要写 goroutine 没有把缓冲写满,则不会导致协程阻塞。但是一旦缓冲没有多余的空间,则会把写 goroutine 挂起到 sendq 中,直到有空间时将他唤醒(还有其它唤醒的场景,这一略过)。

其实有缓冲的 channel,就是把同步的通信变为了异步的通信。写的 channel 不需要关注读 channel,只要有空间它就写;而读也一样,只要有数据就正常读就可以,如果没有就挂起到队列中,等待被唤醒。下图形象的展示了有缓冲 channel 是如何交换数据的。

交换数据

我们再来用图的形式看一下此时结构体的样子,这里图有些偷懒,只是在上面图的基础上增加了循环队列部分的描述,实际到该例子中,读 goroutine时不会被阻塞的,看的时候需要注意这一点。

结构示例

循环队列

今天最重要的是理解 channel 中两个关键的数据结构。为了下一讲阅读源码做准备,我把 channel 中的循环队列部分的代码抽象出来了。

// 队列满了
var ErrQFull = errors.New("circular is full")

// 没有值
var ErrQEmpty = errors.New("circular is empty")

// 定义循环队列
// 如何确定队空,还是队满?q.sendx = (q.sendx+1) % q.dataqsiz
type queue struct {
 buf      []int // 队列元素存储
 dataqsiz uint  // circular 队列长度
 qcount   uint  // 有多少元素在buf中 qcount = len(buf)
 sendx    uint  // 可以理解为队尾指针,向队列写入数据
 recvx    uint  // 可以理解为队头指针,从队列读取数据
}

func makeQ(size int) *queue {
 q := &queue{
  dataqsiz: uint(size),
  buf:      nil,
 }

 q.buf = make([]int, q.dataqsiz)

 return q
}

// 向buf中写入数据
// 请看 chansend 函数
func (c *queue) insert(ele int) error {
 // 检查队列是否有空间
 if c.dataqsiz > 0 && c.qcount == c.dataqsiz {
  return ErrQFull
 }

 // 存入数据
 c.buf[c.sendx] = ele
 c.sendx++                  // 尾指针后移
 if c.sendx == c.dataqsiz { // 如果相等,说明队列写满了,sendx放到开始位置
  c.sendx = 0
 }
 c.qcount++

 return nil
}

// 从buf中读取数据
func (c *queue) read() (int, error) {
 // 队列中没有数据了
 if c.dataqsiz > 0 && c.qcount == 0 {
  return 0, ErrQEmpty
 }

 ret := c.buf[c.recvx] // 取出元素
 c.buf[c.recvx] = 0
 c.recvx++
 if c.recvx == c.dataqsiz { // 如果相等,说明写到末尾了,recvx放到开始位置
  c.recvx = 0
 }
 c.qcount--

 return ret, nil
}

上面的代码基本上就是 channel 的循环队列部分的实现。这个队列的实现与我们平常实现的循环队列稍微有些不一样。一般我们为了方便判空,会浪费一个buf的空间来方便判空,公式是:(tail+1)%n=head ;但是在 channel 这里的循环队列,由于有了一个循环队列元素的计数,确保了这个空间不会被浪费,并且同时也能够满足 O(1) 时间复杂度计算有缓冲 channel 元素个数。

总结

总结一下今天的主要信息。

  1. channel 中用到了两个数据结构: 循环队列双端链表
  2. 循环队列 只有在有缓冲 channel 中才会使用,它主要是做为消息的缓冲、保证消息的有序性;
  3. 双端链表 是用来挂起阻塞的读、写 goroutine 的,在被唤醒时会按照入队顺序公平的进行通知;
  4. 无缓冲的 channel 不会用到 循环队列 相关的结构,它必须读写 goroutine 都准备好后才能进行消息交换;
  5. 做为缓冲消息的 循环队列 通过一个当前元素个数字段的标记,避免了浪费一个数据空间。

下一章我们就尝试阅读一下 channel 的源码,想要尝试录制一个视频来讲这部分源码!

参考资料

  • [1] [Diving Deep Into The Golang Channels.](https://codeburst.io/diving-deep-into-the-golang-channels-549fd4ed21a8)

  • [2] [Understanding Channels](https://speakerdeck.com/kavya719/understanding-channels)

  • [3] [The Nature Of Channels In Go](https://www.ardanlabs.com/blog/2014/02/the-nature-of-channels-in-go.html)


推荐阅读



    程序改变的不止是世界

    也改变了你我的头发

    公众号ID

    dayuTalk


    本文分享自微信公众号 - 大愚Talk(dayuTalk)。
    如有侵权,请联系 support@oschina.cn 删除。
    本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

    大愚Talk
    粉丝 4
    博文 55
    码字总数 82802
    作品 0
    成都
    私信 提问
    加载中
    请先登录后再评论。
    Netty那点事(三)Channel与Pipeline

    Channel是理解和使用Netty的核心。Channel的涉及内容较多,这里我使用由浅入深的介绍方法。在这篇文章中,我们主要介绍Channel部分中Pipeline实现机制。为了避免枯燥,借用一下《盗梦空间》的...

    黄亿华
    2013/11/24
    2W
    22
    极速博客引擎--Gor

    gor 是使用 golang 实现的类Ruhoh静态博客引擎(Ruhoh like),基本兼容ruhoh 1.x规范. 相当于与ruhoh的官方实现(ruby实现), 有以下优点: 速度完胜 -- 编译wendal.net近200篇博客,仅需要1秒 安装...

    wendal
    2013/01/20
    3.8K
    0
    代码生成器--Codgen

    Codgen是一个基于数据库元数据模型,使用freemarker模板引擎来构建输出的代码生成器。freemarker的数据模型结构通常来说都是一个Map树状结构模型,codgen也不例外,它的数据模型这棵树的根节...

    黄天政
    2013/01/29
    1.4W
    2
    C++模板库--C++ B-tree

    这是一个google开源的C++模板库,实现了基于B-tree数据结构的有序内存容器。类似于STL的map、set、multimap和multiset模板,C++ B-tree也提供了btreemap、btreeset、btreemultimap和btreemu...

    匿名
    2013/02/05
    3.3K
    1
    开源数据访问组件--Smark.Data

    Smark.Data是基于Ado.net实现的数据访问组件,提供基于强类型的查询表达式进行灵活的数据查询,统计,修改和删除等操作;采用基于条件驱动的操作模式,使数据操作更简单轻松;内部通过标准SQL...

    泥水佬
    2013/03/12
    2.5K
    0

    没有更多内容

    加载失败,请刷新页面

    加载更多

    鼠年吉祥,新年快乐

    今天是大年初一,很高兴在过去一年中有您的陪伴,希望大家在新的一年中平安健康,一切顺利,加油。 邓飞 202001250539 于后园爷爷家 本文分享自微信公众号 - 育种数据分析之放飞自我(R-bre...

    育种数据分析之放飞自
    01/25
    0
    0
    不烧脑、不耗时、全免费,带你0基础学Python

    文末有福利 Python是人工智能的未来。 最近,电气和电子工程师协会( IEEE)发布了顶级编程语言交互排行榜:Python高居首位。 而且随着大数据和人工智能的发展,Python受到了越来越多程序员的...

    kunjian
    今天
    0
    0
    R语言入门系列之一

    写在前面 计算机语言的学习并不困难,关键是一定要由浅入深的实际操作练习。也许最开始的比较简单,学习者一带而过没有实际操作,之后的进一步学习很可能会陷入不知所云的困境,实际操作所带...

    SYSU星空
    2019/02/17
    0
    0
    Istio-本地运行

    概述 基于上一篇 Istio1.6-二进制编译和本地运行 但集中在 pilot-discovery 和 envoy(pilot-agent 大部分功能仅作为 envoy 的 watchdog,略过) NOTE: 以下的描述,相对路径都基于目录 /g...

    深蓝苹果
    36分钟前
    9
    0
    基于Linux、C、JSON、Socket的编程实例(附代码)

    点击上方「嵌入式大杂烩」,选择「置顶公众号」第一时间阅读编程笔记! 一、前言 之前在学习socket编程的时候有分享一个基于控制台的简易天气客户端的实现,当时提供的是window下的代码,最近...

    学以解忧
    2019/10/29
    0
    0

    没有更多内容

    加载失败,请刷新页面

    加载更多

    返回顶部
    顶部