Thread safe queue

[Charles Thompson]

What is the best way to make a thread safe queue in Go? In Java you
write queue class that wraps a list, then synchronizes enqueue and
dequeue activities using a mutex.

This enables multiple threads to add to and pull from the same data
structure without corrupting the queue.

In Go should you synchronize access to the queue using a semaphore?
(described in the Channel section of http://golang.org/doc/effective_go.html)

Or do you simply use channels themselves as the queue?

Code Sample:


package main

import "fmt"
import "container/list"
import "time"

type Queue struct {
sem chan int
list *list.List
}

func NewQueue() *Queue {
sem := make(chan int, 1)
list := list.New()
return &Queue{sem, list}
}

func(q *Queue) Size() int {
return q.list.Len()
}

func (q *Queue) Enqueue (val interface{}) *list.Element{
q.sem <- 1
e := q.list.PushFront(val)
<-q.sem
return e
}

func (q *Queue) Dequeue() *list.Element {
q.sem <-1
e := q.list.Back()
q.list.Remove(e)
<-q.sem
return e
}

func main() {
fmt.Println("Making new queue ...")
q := NewQueue()

//Add 10 items to the Q
for i:=0; i<10; i++ {
go q.Enqueue(i)
}

//Pull 5 items from the Q
for i:=0; i<5; i++ {
go q.Dequeue()
}

//Wait for the go-routines to do their thing
time.Sleep(2000000000)

//Should end up with 5 items stuck in the queue
fmt.Printf("Queue size: %d\n", q.Size())
fmt.Println("Done.")


}

[Russ Cox]

> Or do you simply use channels themselves as the queue?

Yes, unless you have a specific reason not to.

Russ

[roger peppe]

On 20 October 2010 18:34, Russ Cox <r...@golang.org> wrote:
>> Or do you simply use channels themselves as the queue?
>
> Yes, unless you have a specific reason not to.

i wonder if there's room in the standard library for
an unlimited size queue where readers block
if the queue is empty (a slightly harder problem
than the original above).

something like that described by the following interface:

type Q interface {
Put(x interface{})
Get() interface{}
Close()
Closed() bool
}

it's not often what you need, but when you do need
it, it's useful to avoid implementing it again.

[Corey Thomasson]

On 20 October 2010 14:14, roger peppe <rogp...@gmail.com> wrote:
> On 20 October 2010 18:34, Russ Cox <r...@golang.org> wrote:
>>> Or do you simply use channels themselves as the queue?
>>
>> Yes, unless you have a specific reason not to.
>
> i wonder if there's room in the standard library for
> an unlimited size queue where readers block
> if the queue is empty (a slightly harder problem
> than the original above).

This seems trivial to implement in my mind, a single goroutine
maintaining a vector of data that does a select{} (if theres data to
send) on an input and output channel, input received goes into the
vector, output goes out on request.

[roger peppe]

On 20 October 2010 19:20, Corey Thomasson <cthom...@gmail.com> wrote:
> On 20 October 2010 14:14, roger peppe <rogp...@gmail.com> wrote:
>> On 20 October 2010 18:34, Russ Cox <r...@golang.org> wrote:
>>>> Or do you simply use channels themselves as the queue?
>>>
>>> Yes, unless you have a specific reason not to.
>>
>> i wonder if there's room in the standard library for
>> an unlimited size queue where readers block
>> if the queue is empty (a slightly harder problem
>> than the original above).
>
> This seems trivial to implement in my mind, a single goroutine
> maintaining a vector of data that does a select{} (if theres data to
> send) on an input and output channel, input received goes into the
> vector, output goes out on request.

it's trivial but not *that* trivial.
and it would be nice if it could avoid the extra goroutine,
so they could be garbage collected as easily as buffered channels.

[Charles Thompson]

Thanks for the replies!

--
Charles Thompson
(360) 941-1762
charleswt...@gmail.com

[Scott Nelson]

I'm having trouble implementing just this.  Do you have an implementation you'd be willing to share?  I'd like to have both a blocking and non-blocking dequeue method.

[Kyle Lemons]

Example code for one is here (created to test out a theory, NOT for actual use):

https://github.com/kylelemons/iq

I strongly encourage you to not base a solution on infinite queues, however.  They tend to imply a design flaw elsewhere.

On Mon, Aug 12, 2013 at 3:40 PM, Scott Nelson <sc...@scttnlsn.com> wrote:

I'm having trouble implementing just this.  Do you have an implementation you'd be willing to share?  I'd like to have both a blocking and non-blocking dequeue method.

Channels already have blocking and non-blocking send and receive.

 

On Wednesday, October 20, 2010 2:20:57 PM UTC-4, Corey Thomasson wrote:

On 20 October 2010 14:14, roger peppe <rogp...@gmail.com> wrote:
> On 20 October 2010 18:34, Russ Cox <r...@golang.org> wrote:
>>> Or do you simply use channels themselves as the queue?
>>
>> Yes, unless you have a specific reason not to.
>
> i wonder if there's room in the standard library for
> an unlimited size queue where readers block
> if the queue is empty (a slightly harder problem
> than the original above).

This seems trivial to implement in my mind, a single goroutine
maintaining a vector of data that does a select{} (if theres data to
send) on an input and output channel, input received goes into the
vector, output goes out on request.

> something like that described by the following interface:
>
> type Q interface {
>    Put(x interface{})
>    Get() interface{}
>    Close()
>    Closed() bool
> }
>
> it's not often what you need, but when you do need
> it, it's useful to avoid implementing it again.
>

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Scott Nelson]

Thanks!  You're right...I do want an infinite queue but the in-memory data should be bounded and continue on disk.

[andyxning]

Yes, i am now looking for such an impl. Python already has a module Queue implementing this. 

在 2010年10月21日星期四 UTC+8上午2:14:04，rog写道：