Back to Questions
2.9k
views5
comments
Producer/consumer concurrency problem using immutable data structures
f#

Hi,

I have read that immutable data structures is the best way to remove concurrency issues, so I was wondering if there was an example somewhere demonstrating how to implement something like a work queue using immutable data structures. I've thought a lot about it and for the life of me can't seem to figure it out. If anyone has an example handy, I'd really appreciate it.

Thanks.

.

Not sure exactly what you're looking for, but see

[link:blogs.msdn.com]

in case it helps.

By on 7/16/2009 10:59 AM ()

Thanks, guys. I guess I'm asking a more stupid question. So once I have declared this immutable queue, how do I share it between threads, such that when one thread dequeues something, the producer thread will wait for that copy of the queue before it enqueues something. Do I need a mutable variable here guarded with a lock? And if that's what's required, does it essentially make the point of immutable data structures moot?

By on 7/17/2009 3:23 PM ()

Hi,

it's true that immutable data is the best way to handle concurency issues - that is every operation you do on an object don't change it but creates a new - changed - one.

Of course than you can't have a "immutable queue" that reflects changes in one thread to the other (if thread A changes the queue it gets a new one and thread B never will see it) - that's exactly why you don't have issues with concurency - because you can't share ;)

So immutable data is not a mean to solve concurency but a mean to stop you from ever sharing mutable state that can get you into concurency-trouble-land.

But of course you have to rethink the way of communicating between threads because mutable states are out of the question.

That's were messages shine (see post 2).

By on 7/31/2009 2:06 AM ()

I would use a MailboxProcessor. x is the container that i wanted to push/pop or queue/dequeue, and f is the function to add to the container.

The producer thread:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

type Message<'a> =

    | Fetch of AsyncReplyChannel<'a> // get the current state

let interactiveFunction f f_zero =

    MailboxProcessor.Start(fun inbox ->

        let rec loop x i =

            async {

                let! msg = inbox.TryReceive(timeout=0)

                match tryMsg with

                    | None ->

                        return! loop (f x) (i+1)

                    | Some msg ->

                         match msg ->

                            | Fetch replyChannel ->

                                do replyChannel.Reply(x)

                                return! loop (f x) (i+1) 

            }

        loop f_zero 0)

To get an element in the consumer thread:

1
2

mailbox.PostAndReply(fun replyChannel -> Fetch(replyChannel))

Hope this helps. (Sorry about the lousy indentation)

By on 7/16/2009 8:27 AM ()

@none: This is not a producer/consumer solution. A p/c queue has Put and Get methods, and Get blocks if there is no item in the queue. In some solutions Put can also block if there is no more room in the queue.

By on 12/16/2010 1:38 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper