The last article talked about the basic use of channel and some matters needing attention when using channel. This article will focus on two data structures in channel: circular queue and double-entailed linked list.

Description of channel requirements

To understand what these data structures solve, let’s start with a brief review of why these two data structures are needed and what problems they solve. We know that goroutines are user-mode threads, and there is a need for message passing between different Goroutines. In the original process and thread (system thread) programming we used pipes, and a channel is a type safe implementation of a pipe for user-mode threads to pass messages.

Since a channel is a channel, it is used to exchange messages between different Goroutines. So how do you implement such a pipeline?

Let’s take a look at our daily messaging requirements:

1. Can have more than onegoroutine 向 channelRead and write, and ensure that there are no competition problems, need to useThe queueTo manage congestiongoroutineTo solve competition problems;
2. Need to manage sending tochannelFor cached messages (buffered and unbuffered)channelCan be usedCircular queueTo manage multiple messages.

Of course, the above requirements are simplified, such as the channel’s ability to block and wake up goroutine, but for the sake of this article we will focus on the above two issues.

Channel data structure

Let’s look at the structure of a channel in action. Of course, there are two types, buffered and unbuffered. Let’s look at an unbuffered case.

There is no buffer

Post the sample code first. Two read Goroutines are blocked on an unbuffered channel.

func main(a) {
 ch := make(chan int) / / no buffer

 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) } Copy the code

Let’s see what the structure of the channel looks like when we get to ch < -1!

Note that the stored length of the BUF field is 0, because unbuffered channels do not use circular queues to store data. It must wait until the goroutine is ready to read and write, and then hand the data directly to the other side. Let’s look at an unbuffered data exchange using a diagram.

The figure above depicts the data exchange process, and take a look at the structure diagram that reads goroutine blocked. The blocked goroutine is mounted to the corresponding queue, which is a two-ended queue.

In the above example, both read goroutines are suspended in the queue because the writes are not ready when the two read goroutines start. When a write Goroutine is ready, the write is not blocked and suspended in sendq because the read is ready. You can modify the above code to see for yourself what happens when write blocks and read immediately.

A buffer

Let’s change the above code to a buffered channel, and then look at the buffered case.

func main(a) {
 ch := make(chan int.3) / / a buffer

 // It will not block
 ch <- 1
 ch <- 2  ch <- 3  // blocks and hangs in sendq  go func(a) {  ch <- 4 } ()  // Just for debug  var a int  fmt.Println(a)   go goRoutineA(ch)  go goRoutineA(ch)  go goRoutineB(ch)  go goRoutineB(ch) // Guess what?   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) } Copy the code

Post the structure fill of hchan when executing go goRoutineA(ch) on the first line.

You can see here that the buffer size is 3. Because of the increased buffer, as long as the goroutine does not fill the buffer, it will not cause the coroutine to block. But once the buffer runs out of space, goroutine is hung in Sendq until it wakes up when it has space (there are other wake up scenarios, which are skipped).

Buffered channels turn synchronous communication into asynchronous communication. A written channel does not need to care about reading a channel, as long as it has space to write; The same is true for reading. As long as there is data, it can be read normally. If there is no data, it will hang to the queue and wait to be woken up. The following diagram illustrates how cached channels exchange data.

Let’s look at what the structure looks like in graph form, and this is a little bit lazy, but I’m just going to add a description of the loop queue, and actually in this example, reading the Goroutine will not block, so you have to be careful about that when you look at it.

Circular queue

The most important thing today is to understand two key data structures in channels. In preparation for reading the source code in the next lecture, I have abstracted the loop queue part of the channel.

// The queue is full
var ErrQFull = errors.New("circular is full")

/ / no value
var ErrQEmpty = errors.New("circular is empty")
 // Define the loop queue // How to determine whether a queue is empty or full? q.sendx = (q.sendx+1) % q.dataqsiz type queue struct {  buf []int // Queue element storage  dataqsiz uint // circular queue length  qcount uint Qcount = len(buf)  sendx uint // Write data to queue  recvx uint // read data from the queue }  func makeQ(size int) *queue {  q := &queue{  dataqsiz: uint(size),  buf: nil. }   q.buf = make([]int, q.dataqsiz)   return q }  // Write data to buF // See the chansend function func (c *queue) insert(ele int) error {  // Check whether the queue has space  if c.dataqsiz > 0 && c.qcount == c.dataqsiz {  return ErrQFull  }   // Store data  c.buf[c.sendx] = ele  c.sendx++ // The tail pointer moves back  if c.sendx == c.dataqsiz { // If it is equal, the queue is full and sendx is put in the start position  c.sendx = 0  }  c.qcount++   return nil }  // Read data from buF func (c *queue) read(a) (int, error) {  // There is no data in the queue  if c.dataqsiz > 0 && c.qcount == 0 {  return 0, ErrQEmpty  }   ret := c.buf[c.recvx] // Fetch the element  c.buf[c.recvx] = 0  c.recvx++  if c.recvx == c.dataqsiz { Recvx = recvx = recvx = recvx = recvx  c.recvx = 0  }  c.qcount--   return ret, nil } Copy the code

The above code is basically an implementation of the loop queue part of a channel. The implementation of this queue is slightly different from our usual implementation of a circular queue. (tail+1)%n=head; (tail+1)%n=head; However, the loop queue in channel has a count of loop queue elements, which ensures that the space will not be wasted, and can also satisfy O(1) time complexity to calculate the number of cached channel elements.

conclusion

To sum up today’s main message.

1. Channel uses two data structures: a circular queue and a double-entailed list;
2. Circular queues are used only in buffered channels. They are mainly used to buffer messages and ensure the order of messages.
3. Double – enqueued lists are used to suspend blocking goroutine reads and writes, and are notified fairly in queue order when awakened.
4. An unbuffered channel does not use loop queue-related structures. It must have both goroutines ready for message exchange.
5. The loop queue that serves as a buffer message is marked with a current number of elements field, avoiding a waste of data space.

In the next chapter, we will try to read the source code of channel and try to record a video to talk about this part of the source code!

The resources

• [1] Diving Deep Into The Golang Channels.
• [2] Understanding Channels
• [3] The Nature Of Channels In Go