FAQ
I need help implementing this in pure Go (without needing external library.
Standard lib is OK):

I have an array of n pointers, each point to a struct that store some
incremental counters. No two pointers in the array point to the same struct
in memory so it's a straightforward 1-1 relationship.

Each struct is updated by an independent goroutine. Therefore we have n
goroutines, called workers. But they share nothing because each only
operate on their own struct, so no synchronization needed between them.

A scheduler run on another independent goroutine periodically needs to sort
the array based on the counters in the structs. Using the sorted array, the
scheduler will do some processing of its own (I can't mention the details
here). No matter what scheduler's processing is, it will only read from the
structs.

To be clear: workers write to the structs and scheduler read from those.

When the array is being sorted (or used) by scheduler, no update (write)
from workers is allowed to occur to the structs. But the workers must keep
running (processing things, doing IOs, ...), without updating the counters
in the structs. The purpose of it is for scheduler to have a consistent
view/snapshot of the structs at processing time. Of course, those counters
could temporarily be store locally to the stack at that time and later when
the scheduler is done, it will be synced back to the structs again by the
workers.

What I want is some kind of lock that:
+ There is only a single lock instance that is referenced by all workers
and the scheduler.
+ Has the same characteristics/properties as readers-writer lock but in
reverse for this case: the readers is the workers that write, the writer is
the scheduler that read. To be specific:
_ Any number of readers (workers) could hold the lock at the same time but
if and only if the writer (scheduler) isn't currently holding the lock. And
the writer could hold the lock if and only if no readers is currently
holding the lock.
_ When writer want to acquire the lock, all future wanna-be-readers must
fail to acquire the lock until the writer release it. But still writer must
wait for all current already-be-readers to release the lock to be able to
hold it.
+ Only writer could be blocked waiting for all current readers to release
the lock. Any worker who wants to be reader may try to acquire the lock but
it must not be blocked when failed (because the lock is currently held by
the writer).

I am still an amateur in concurrent programming so please be specific and
give as much information as you care in your answers. I'd appreciate any
information or advices you could give me. Thanks very much.

--
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+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Search Discussions

  • Ox at Dec 26, 2014 at 1:29 am
    Here's one solution - https://gist.github.com/oxtoacart/893b783bd80dae21f5b2

    Key things:

    1. When writing Go, it's useful to think about sharing state by
    communicating rather than communicating by sharing state. That means using
    channels instead of locks.

    2. Go's select <https://golang.org/ref/spec#Select_statements> statement is
    very powerful and worth learning. It allows your code to plug into Go's
    scheduler when sending and receiving data via channels, and with the use of
    a default clause it allows you to continue on to other work when a send or
    receive would block.

    3. When I have multiple operations that need to be synchronized, I will
    often accomplish the synchronization by doing all of those operations on a
    single goroutine. In your case, that means doing not just the sorting and
    scheduling in your scheduler goroutine, but actually doing the update of
    counts for each struct as well.

    4. To accomplish #3, it's common to need to introduce some data types
    purely for messaging (in this example the "update" type). Compared with
    something like Java, Go makes this quite easy and terse, so there's no
    reason to shy away from it.

    5. I don't know what your "scheduler" goroutine does, but you might find
    that once you're more comfortable with concurrency in Go, you may be able
    to express your actual problem in such a way that you don't need a
    "scheduler" goroutine at all.

    Cheers,
    Ox
    On Wednesday, December 24, 2014 10:04:40 PM UTC-6, kimkh...@gmail.com wrote:

    I need help implementing this in pure Go (without needing external
    library. Standard lib is OK):

    I have an array of n pointers, each point to a struct that store some
    incremental counters. No two pointers in the array point to the same struct
    in memory so it's a straightforward 1-1 relationship.

    Each struct is updated by an independent goroutine. Therefore we have n
    goroutines, called workers. But they share nothing because each only
    operate on their own struct, so no synchronization needed between them.

    A scheduler run on another independent goroutine periodically needs to
    sort the array based on the counters in the structs. Using the sorted
    array, the scheduler will do some processing of its own (I can't mention
    the details here). No matter what scheduler's processing is, it will only
    read from the structs.

    To be clear: workers write to the structs and scheduler read from those.

    When the array is being sorted (or used) by scheduler, no update (write)
    from workers is allowed to occur to the structs. But the workers must keep
    running (processing things, doing IOs, ...), without updating the counters
    in the structs. The purpose of it is for scheduler to have a consistent
    view/snapshot of the structs at processing time. Of course, those counters
    could temporarily be store locally to the stack at that time and later when
    the scheduler is done, it will be synced back to the structs again by the
    workers.

    What I want is some kind of lock that:
    + There is only a single lock instance that is referenced by all workers
    and the scheduler.
    + Has the same characteristics/properties as readers-writer lock but in
    reverse for this case: the readers is the workers that write, the writer is
    the scheduler that read. To be specific:
    _ Any number of readers (workers) could hold the lock at the same time but
    if and only if the writer (scheduler) isn't currently holding the lock. And
    the writer could hold the lock if and only if no readers is currently
    holding the lock.
    _ When writer want to acquire the lock, all future wanna-be-readers must
    fail to acquire the lock until the writer release it. But still writer must
    wait for all current already-be-readers to release the lock to be able to
    hold it.
    + Only writer could be blocked waiting for all current readers to release
    the lock. Any worker who wants to be reader may try to acquire the lock but
    it must not be blocked when failed (because the lock is currently held by
    the writer).

    I am still an amateur in concurrent programming so please be specific and
    give as much information as you care in your answers. I'd appreciate any
    information or advices you could give me. Thanks very much.
    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Kimkhanh535 at Dec 26, 2014 at 2:44 pm
    The details of your answer is astounding, especially the example. I am
    forever in your debt.

    But there are some points I'm still wondering:

    + Is there any chance a worker's updates to it's struct (sent to `updates`
    channel) could be delayed much by other workers, till the point of
    starvation? Because I can't see fairness here, just whoever comes first
    win. If a worker comes late (after the channel is full), then its update
    will be lost. And if that happened many times in a row, the counter in the
    struct could be so stale that the scheduler's processing will be based on
    wrong/old data.
      + Is the overhead of creating and sending updates negligible? And also
    while the scheduler is sorting (or doing it's processing thingy),
    unnecessary updates still pour into the channel until it's full. Isn't that
    overhead compared to the lock concept I describe in my question?
      + Why just sending delta value in update, while we could send full value?
    Because with full value, we could skip all previous redundant updates and
    go straight to the newest, not having to sum consecutively all deltas. Even
    though I know that it's more efficient but I couldn't think of any way to
    implement it.
    I guess Go is not the language to efficiently solve my problem. But I am
    stuck with it so if a better solution couldn't be found, I will go with
    your idea. Better some than nothing.
    On Thursday, December 25, 2014 11:04:40 AM UTC+7, kimkh...@gmail.com wrote:

    I need help implementing this in pure Go (without needing external
    library. Standard lib is OK):

    I have an array of n pointers, each point to a struct that store some
    incremental counters. No two pointers in the array point to the same struct
    in memory so it's a straightforward 1-1 relationship.

    Each struct is updated by an independent goroutine. Therefore we have n
    goroutines, called workers. But they share nothing because each only
    operate on their own struct, so no synchronization needed between them.

    A scheduler run on another independent goroutine periodically needs to
    sort the array based on the counters in the structs. Using the sorted
    array, the scheduler will do some processing of its own (I can't mention
    the details here). No matter what scheduler's processing is, it will only
    read from the structs.

    To be clear: workers write to the structs and scheduler read from those.

    When the array is being sorted (or used) by scheduler, no update (write)
    from workers is allowed to occur to the structs. But the workers must keep
    running (processing things, doing IOs, ...), without updating the counters
    in the structs. The purpose of it is for scheduler to have a consistent
    view/snapshot of the structs at processing time. Of course, those counters
    could temporarily be store locally to the stack at that time and later when
    the scheduler is done, it will be synced back to the structs again by the
    workers.

    What I want is some kind of lock that:
    + There is only a single lock instance that is referenced by all workers
    and the scheduler.
    + Has the same characteristics/properties as readers-writer lock but in
    reverse for this case: the readers is the workers that write, the writer is
    the scheduler that read. To be specific:
    _ Any number of readers (workers) could hold the lock at the same time but
    if and only if the writer (scheduler) isn't currently holding the lock. And
    the writer could hold the lock if and only if no readers is currently
    holding the lock.
    _ When writer want to acquire the lock, all future wanna-be-readers must
    fail to acquire the lock until the writer release it. But still writer must
    wait for all current already-be-readers to release the lock to be able to
    hold it.
    + Only writer could be blocked waiting for all current readers to release
    the lock. Any worker who wants to be reader may try to acquire the lock but
    it must not be blocked when failed (because the lock is currently held by
    the writer).

    I am still an amateur in concurrent programming so please be specific and
    give as much information as you care in your answers. I'd appreciate any
    information or advices you could give me. Thanks very much.
    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Ox Cart at Dec 26, 2014 at 4:12 pm

    The details of your answer is astounding, especially the example. I am
    forever in your debt.
    You're welcome. No big debt, I enjoy this stuff!
    But there are some points I'm still wondering:

    + Is there any chance a worker's updates to it's struct (sent to `updates`
    channel) could be delayed much by other workers, till the point of
    starvation? Because I can't see fairness here, just whoever comes first
    win. If a worker comes late (after the channel is full), then its update
    will be lost. And if that happened many times in a row, the counter in the
    struct could be so stale that the scheduler's processing will be based on
    wrong/old data.
    Great insight, starvation is a problem with the original example. I
    created an updated example that solves the starvation issue by giving each
    worker its own update channel and then selecting across those. This works
    because select chooses from among all available channels randomly. So, if
    two workers have an update ready to be selected, either one may be selected
    in any given loop, so over time both will eventually get selected. To make
    this work, I had to make each update channel buffered. That ensures that
    multiple workers will have updates that are eligible for selection.

    https://gist.github.com/oxtoacart/62869d732db06a9e1766

    Note - this is my first time using reflect.Select, so I don't know how it
    compares with a typical hardcoded select. If you know the number of workers
    at compile time or you're willing to over-allocate channels, you can just
    hardcode the select statement instead of using reflection.

      + Is the overhead of creating and sending updates negligible? And also
    while the scheduler is sorting (or doing it's processing thingy),
    unnecessary updates still pour into the channel until it's full. Isn't that
    overhead compared to the lock concept I describe in my question?
    This sort of overhead is not something that I would typically worry about,
    because I do network programming and the cost of actually sending data over
    the network dwarves these kinds of considerations.

    + Why just sending delta value in update, while we could send full
    value? Because with full value, we could skip all previous redundant
    updates and go straight to the newest, not having to sum consecutively all
    deltas. Even though I know that it's more efficient but I couldn't think of
    any way to implement it.
    Good point. While I was at it, in the new example, I eliminated the update
    struct so now I'm just sending over an int. Which struct this corresponds
    to is index-based. This will be marginally more efficient than the
    original, but depending on what actual work your workers do, this is
    unlikely to be your bottleneck.

    I guess Go is not the language to efficiently solve my problem. But I am
    stuck with it so if a better solution couldn't be found, I will go with
    your idea. Better some than nothing.
    You can't make a conclusion like this without benchmarking. Are you
    assuming that a lock-based solution would be more efficient than one based
    on channels? Are you seeing something in here that looks like a potential
    bottleneck? My advice to you would be to build a prototype, test it and if
    it's not fast enough, find your bottlenecks and see if you can fix those.
    Here's an excellent article on profiling Go programs -
    http://blog.golang.org/profiling-go-programs.

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Ox at Dec 26, 2014 at 4:38 pm
    Just for fun, here's one more solution
    - https://gist.github.com/oxtoacart/fd6175cc3b188eac38c4

    In this solution, we have both a global updates channel like in the first
    solution, as well as per-worker update channels like in the second
    solution. Each worker gets an additional submitter goroutine that handles
    sending updates to the global channel, which allows the worker to submit an
    updated count as soon as it's available. The submitter goroutine is the one
    that blocks, which allows the worker to avoid blocking and continue.

    I think I like this solution the best, since it eliminates any potential
    performance concerns about reflection, and it's considerably shorter too.

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Kimkhanh535 at Dec 27, 2014 at 2:22 pm
    Me too. I love your latest solution. It's ingenious and beautiful. All
    known problems are gone (except memory usage is slightly increased due to
    double goroutines per struct, but nothing is perfect, right?). I guess
    internally Go maintain a queue of blocking senders (goroutines) for each
    channel therefore everyone got a chance if they are waiting in that queue.
    Fairness is served!

    I'd better work on it now. Thank you so much for everything.
    On Friday, December 26, 2014 11:37:58 PM UTC+7, o...@getlantern.org wrote:

    Just for fun, here's one more solution -
    https://gist.github.com/oxtoacart/fd6175cc3b188eac38c4
    <https://www.google.com/url?q=https%3A%2F%2Fgist.github.com%2Foxtoacart%2Ffd6175cc3b188eac38c4&sa=D&sntz=1&usg=AFQjCNHMwMxdORBec93Fss3EG7I4-qko6Q>

    In this solution, we have both a global updates channel like in the first
    solution, as well as per-worker update channels like in the second
    solution. Each worker gets an additional submitter goroutine that handles
    sending updates to the global channel, which allows the worker to submit an
    updated count as soon as it's available. The submitter goroutine is the one
    that blocks, which allows the worker to avoid blocking and continue.

    I think I like this solution the best, since it eliminates any potential
    performance concerns about reflection, and it's considerably shorter too.
    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Kevin Malachowski at Dec 28, 2014 at 8:28 pm
    The Go runtime does keep a set of goroutines that are blocked and waiting as well as those that are unblocked and ready to be run on a processor. I think runnable goroutines are scheduled in pseudo random order but that knowledge may be outdated. I'm pretty sure its not just a straightforward fifo system, though.

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Kevin Malachowski at Dec 28, 2014 at 8:32 pm
    Whoops, I didn't tie that in to specifically talking about sending on channel. There's definitely no fairness when multiple goroutines try to read from an empty chan or write to a full one: any goroutine that is blocked has a chance to be picked once the channel is ready to be sent to/received from. There is no first come first serve, but since a goroutine is pseudorandomly picked it ends up being "fair enough" for practical use.

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Kimkhanh535 at Jan 7, 2015 at 4:28 pm
    Are there any official specifications on "pseudorandomly picked" a
    goroutine to proceed when encountering many waiting goroutines
    reading/writing on a blocked channel? And if so, why are they implemented
    that way rather than pure FIFO? I know that select statement behave
    pseudorandomly, but to think that blocked channels behave that way too is
    making me feel like it's a waste of processing resource.
    On Monday, December 29, 2014 3:32:39 AM UTC+7, Kevin Malachowski wrote:

    Whoops, I didn't tie that in to specifically talking about sending on
    channel. There's definitely no fairness when multiple goroutines try to
    read from an empty chan or write to a full one: any goroutine that is
    blocked has a chance to be picked once the channel is ready to be sent
    to/received from. There is no first come first serve, but since a goroutine
    is pseudorandomly picked it ends up being "fair enough" for practical use.
    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Ian Lance Taylor at Jan 7, 2015 at 4:51 pm

    On Wed, Jan 7, 2015 at 8:28 AM, wrote:
    Are there any official specifications on "pseudorandomly picked" a goroutine
    to proceed when encountering many waiting goroutines reading/writing on a
    blocked channel? And if so, why are they implemented that way rather than
    pure FIFO? I know that select statement behave pseudorandomly, but to think
    that blocked channels behave that way too is making me feel like it's a
    waste of processing resource.
    The only pseudo-random choice is for select. Channel reads and writes
    other than select are handled with a FIFO queue. Of course the exact
    ordering on the queue is unpredictable when multiple goroutines are
    running simultaneously.

    Ian

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedDec 25, '14 at 9:15p
activeJan 7, '15 at 4:51p
posts10
users4
websitegolang.org

People

Translate

site design / logo © 2022 Grokbase