php小編草莓今天要為大家介紹一種新的技術－使用新的atomic.Pointer類型實作無鎖無界佇列。在並發程式設計中，佇列是一種常見的資料結構，但傳統的佇列實作通常需要使用鎖定來確保執行緒安全，這會帶來效能的損耗。而新的atomic.Pointer類型則提供了一個無鎖的解決方案，可以實現高效的並發佇列操作。以下我們將詳細介紹這種新的實作方式，以及它的優點和使用方法。
我正在嘗試實作 michael 和 scott 的這個非阻塞佇列。
我正在嘗試使用 go 1.19 中引入的新的atomic.pointer 類型，但我的應用程式中出現了資料爭用。
這是我的實作：
package queue
import (
"errors"
"sync/atomic"
)
// LockfreeQueue represents a FIFO structure with operations to enqueue
// and dequeue generic values.
// Reference: https://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html
type LockFreeQueue[T any] struct {
head atomic.Pointer[node[T]]
tail atomic.Pointer[node[T]]
}
// node represents a node in the queue
type node[T any] struct {
value T
next atomic.Pointer[node[T]]
}
// newNode creates and initializes a node
func newNode[T any](v T) *node[T] {
return &node[T]{value: v}
}
// NewQueue creates and initializes a LockFreeQueue
func NewLockFreeQueue[T any]() *LockFreeQueue[T] {
var head atomic.Pointer[node[T]]
var tail atomic.Pointer[node[T]]
n := &node[T]{}
head.Store(n)
tail.Store(n)
return &LockFreeQueue[T]{
head: head,
tail: tail,
}
}
// Enqueue adds a series of Request to the queue
func (q *LockFreeQueue[T]) Enqueue(v T) {
n := newNode(v)
for {
tail := q.tail.Load()
next := tail.next.Load()
if tail == q.tail.Load() {
if next == nil {
if tail.next.CompareAndSwap(next, n) {
q.tail.CompareAndSwap(tail, n)
return
}
} else {
q.tail.CompareAndSwap(tail, next)
}
}
}
}
// Dequeue removes a Request from the queue
func (q *LockFreeQueue[T]) Dequeue() (T, error) {
for {
head := q.head.Load()
tail := q.tail.Load()
next := head.next.Load()
if head == q.head.Load() {
if head == tail {
if next == nil {
return head.value, errors.New("queue is empty")
}
q.tail.CompareAndSwap(tail, next)
} else {
v := next.value
if q.head.CompareAndSwap(head, next) {
return v, nil
}
}
}
}
}
// Check if the queue is empty.
func (q *LockFreeQueue[T]) IsEmpty() bool {
return q.head.Load() == q.tail.Load()
}
我在這裡發現了一個不同的實現，它可以在我的應用程式中工作而無需數據競爭，但我似乎無法弄清楚兩者之間到底有什麼不同。
感謝任何幫助或回饋！
事實證明，更改一些內容可以解決問題。
第一個變更：
var n = node[t]{}
head.store(&n)
tail.store(&n)
第二個變更是變更 dequeue() 傳回簽章。
最終檔案如下所示：
package queue
import (
"sync/atomic"
)
// LockfreeQueue represents a FIFO structure with operations to enqueue
// and dequeue generic values.
// Reference: https://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html
type LockFreeQueue[T any] struct {
head atomic.Pointer[node[T]]
tail atomic.Pointer[node[T]]
}
// node represents a node in the queue
type node[T any] struct {
value T
next atomic.Pointer[node[T]]
}
// newNode creates and initializes a node
func newNode[T any](v T) *node[T] {
return &node[T]{value: v}
}
// NewQueue creates and initializes a LockFreeQueue
func NewLockFreeQueue[T any]() *LockFreeQueue[T] {
var head atomic.Pointer[node[T]]
var tail atomic.Pointer[node[T]]
var n = node[T]{}
head.Store(&n)
tail.Store(&n)
return &LockFreeQueue[T]{
head: head,
tail: tail,
}
}
// Enqueue adds a series of Request to the queue
func (q *LockFreeQueue[T]) Enqueue(v T) {
n := newNode(v)
for {
tail := q.tail.Load()
next := tail.next.Load()
if tail == q.tail.Load() {
if next == nil {
if tail.next.CompareAndSwap(next, n) {
q.tail.CompareAndSwap(tail, n)
return
}
} else {
q.tail.CompareAndSwap(tail, next)
}
}
}
}
// Dequeue removes a Request from the queue
func (q *LockFreeQueue[T]) Dequeue() T {
var t T
for {
head := q.head.Load()
tail := q.tail.Load()
next := head.next.Load()
if head == q.head.Load() {
if head == tail {
if next == nil {
return t
}
q.tail.CompareAndSwap(tail, next)
} else {
v := next.value
if q.head.CompareAndSwap(head, next) {
return v
}
}
}
}
}
// Check if the queue is empty.
func (q *LockFreeQueue[T]) IsEmpty() bool {
return q.head.Load() == q.tail.Load()
}
以上是使用新的atomic.Pointer類型實現無鎖無界佇列的詳細內容。更多資訊請關注PHP中文網其他相關文章！
