Melaksanakan baris gilir tanpa sempadan tanpa kunci menggunakan jenis atomic.Penunjuk baharu

Editor PHP, Strawberry, akan memperkenalkan teknologi baharu kepada anda hari ini - menggunakan jenis atomic.Pointer baharu untuk melaksanakan baris gilir tanpa kunci dan tidak terhad. Dalam pengaturcaraan serentak, baris gilir ialah struktur data biasa, tetapi pelaksanaan baris gilir tradisional biasanya memerlukan penggunaan kunci untuk memastikan keselamatan benang, yang akan menyebabkan kehilangan prestasi. Jenis atomic.Pointer baharu menyediakan penyelesaian bebas kunci yang boleh mencapai operasi baris gilir serentak yang cekap. Di bawah ini kami akan memperkenalkan pelaksanaan baharu ini secara terperinci, serta kelebihannya dan cara menggunakannya.

Kandungan soalan

Saya cuba melaksanakan baris gilir tanpa sekatan dari michael dan scott ini.

Saya cuba menggunakan jenis atomic.pointer baharu yang diperkenalkan dalam go 1.19, tetapi saya mendapat perlumbaan data dalam aplikasi saya.

Ini adalah pelaksanaan saya:

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()
}

Saya menemui pelaksanaan berbeza di sini yang berfungsi dalam apl saya tanpa perlumbaan data, tetapi saya nampaknya tidak dapat mengetahui apa sebenarnya perbezaan antara kedua-duanya.

Terima kasih atas sebarang bantuan atau maklum balas!

Penyelesaian

Ternyata mengubah beberapa perkara boleh menyelesaikan masalah.

Perubahan pertama:

var n = node[t]{}
head.store(&n)
tail.store(&n)

Perubahan kedua ialah menukar dequeue() kembali tandatangan.

Fail akhir kelihatan seperti ini:

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()
}

Atas ialah kandungan terperinci Melaksanakan baris gilir tanpa sempadan tanpa kunci menggunakan jenis atomic.Penunjuk baharu. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!