如何将这段代码转换为非阻塞和无锁的形式?

huangapple go评论85阅读模式
英文:

How to convert this code to be non-blocking & lock-free?

问题

我有一个队列,需要具有增长的缓冲区,这就排除了在Go中使用缓冲通道的可能性。

经过一些谷歌搜索,我找到了以下代码:

import (
    "sync"
)

type Queue struct {
    nodes []interface{}
    head, tail, count int
    lck sync.RWMutex
}

func (q *Queue) Enqueue(v interface{}) {
    q.lck.Lock()
    defer q.lck.Unlock()

    if q.nodes == nil {
        q.nodes = make([]interface{}, 2)
    }

    if q.head == q.tail && q.count > 0 {
        nodes := make([]interface{}, len(q.nodes) * 2)
        copy(nodes, q.nodes[q.head:])
        copy(nodes[len(q.nodes) - q.head:], q.nodes[:q.head])
        q.head = 0
        q.tail = len(q.nodes)
        q.nodes = nodes
    }

    q.nodes[q.tail] = v
    q.tail = (q.tail + 1) % len(q.nodes)
    q.count++
}

func (q *Queue) Dequeue() interface{} {
    q.lck.Lock()
    defer q.lck.Unlock()

    if len(q.nodes) == 0 {
        return nil
    }

    node := q.nodes[q.head]
    q.head = (q.head + 1) % len(q.nodes)
    q.count--

    return node
}

func (q *Queue) Len() int {
    q.lck.RLock()
    defer q.lck.RUnlock()

    return q.count
}

有没有办法将这个代码转换为非阻塞和无锁队列?

英文:

I have queue, witch has to have growing buffer, this excludes usage of buffered channels in go for me.

After some google searching I've come up with this code:

import (
"sync"
)
type Queue struct {
nodes []interface{}
head, tail, count int
lck sync.RWMutex
}
func (q *Queue) Enqueue(v interface{}) {
q.lck.Lock()
defer q.lck.Unlock()
if q.nodes == nil {
q.nodes = make([]interface{}, 2)
}
if q.head == q.tail && q.count > 0 {
nodes := make([]interface{}, len(q.nodes) * 2)
copy(nodes, q.nodes[q.head:])
copy(nodes[len(q.nodes) - q.head:], q.nodes[:q.head])
q.head = 0
q.tail = len(q.nodes)
q.nodes = nodes
}
q.nodes[q.tail] = v
q.tail = (q.tail + 1) % len(q.nodes)
q.count++
}
func (q *Queue) Dequeue() interface{} {
q.lck.Lock()
defer q.lck.Unlock()
if len(q.nodes) == 0 {
return nil
}
node := q.nodes[q.head]
q.head = (q.head + 1) % len(q.nodes)
q.count--
return node
}
func (q *Queue) Len() int {
q.lck.RLock()
defer q.lck.RUnlock()
return q.count
}

Is there any way I could convert this to be non-blocking & lock-free queue?

答案1

得分: 3

Evan Huus的channels提供了ResizableChannel类型,似乎提供了你所需要的功能。

>>ResizableChannel通过在输入和输出之间使用可调整大小的缓冲区来实现Channel接口。该通道最初具有1个缓冲区大小,但可以通过调用Resize()来调整大小。

英文:

Evan Huus's channels package provides the ResizableChannel type which seems to provide what you're after.

>>ResizableChannel implements the Channel interface with a resizable buffer between the input and the output. The channel initially has a buffer size of 1, but can be resized by calling Resize().

huangapple
  • 本文由 发表于 2014年2月21日 18:21:26
  • 转载请务必保留本文链接:https://go.coder-hub.com/21931545.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定