Re: [go-nuts] Is this a valid way of implementing a mutex?
Op zo 17 mrt. 2019 om 15:28 schreef Louki Sumirniy : > As my simple iterative example showed, given the same sequence of events, > channels are deterministic, so this is an approach that is orthogonal but in > the same purpose - to prevent multiple concurrent agents from desynchronising > shared state, without blocking everything before access. It's not a journal > but the idea is to have each goroutine acting on the final state of the value > at the time it is invoked to operate on it. So you let everyone at it but > everyone stops at this barrier and checks if anyone else changed it and then > they try again to have a conflict free access. Channels are deterministic in the sense that if items A and B are enqueued in that order, they will be delivered in that order. They are not deterministic in two ways: if items A and B are enqueued concurrently, the order could be A B or B A; if two consumers of the channel read from it concurrently, it is not deterministic which will read. This doesn't seem to me to be related in any way to locking / mutual exclusion. The purpose of mutual exclusion is to serialize some execution history. In other words, the idea is to make an interleaved / concurrent execution history of some set of instructions impossible. That's not what a channel does. While a channel will act like a FIFO, when multiple concurrent producers and / or consumers are present, one cannot say which concurrent producer or consumer "wins" reading or writing. So this pattern is really only meaningful for SPSC workloads. What you term "access contention" seems to me somewhat analogous to "data race". Assuming "somestate" is a pointer to some shared mutable state, you might be able to determine whether that state changed after the channel operation, but: a) You're still susceptible to ABA problems when the state does not change deterministically. b) Even with a deterministically mutated state (such as a counter increasing by a constant factor), you still have TOCTOU (time-of-check versus time-of-use) issues. If your test of the state after the channel operation doesn't show that the state has changed, what guarantees that the state hasn't changed after your check? It's turtles all the way down from here. c) Both the assignment of "somestate" and a read from a channel create a copy of the thing that was yielded from the function or was sent over the channel, respectively. Unless that thing is a pointer to shared mutable state, that state can't be observed to change via external influence, anyway. The channel use you've demonstrated is much more analogous to a binary semaphore than any sort of lock in the sense that readers block on a binary condition (whether or not the channel contains a value). You can implement a mutex on a binary semaphore, but you need some notion of "lock" and "unlock". To achieve locking semantics with an unbuffered channel, the channel must begin in a non-empty state. When the channel is read from, the state transitions to "locked". When the lock is meant to be released, the releasing process writes to the channel. This is perilous: 1) if you ever accidentally write twice, you no longer have the guarantee of mutual exclusion, and 2) "unlocking" blocks until there's a a new process wishing to acquire the lock. You can solve the second point with a buffered channel with a capacity of 1, but you seem to be explicitly talking about unbuffered channels. The first point can be solved, but I don't think it's super relevant. If all you want to do is determine that some state was valid at the time it was accessed, atomics or mutexes are the correct approach. If you want to have multiple concurrent processes "agree" that they're both working with the same state for the entire duration of some execution history, you still need some sort of consensus protocol. --dho > On Sunday, 17 March 2019 20:52:12 UTC+1, Robert Engels wrote: >> >> https://g.co/kgs/2Q3a5n >> >> On Mar 17, 2019, at 2:36 PM, Louki Sumirniy wrote: >> >> So I am incorrect that only one goroutine can access a channel at once? I >> don't understand, only one select or receive or send can happen at one >> moment per channel, so that means that if one has started others can't start. >> >> I was sure this was the case and this seems to confirm it: >> >> https://stackoverflow.com/a/19818448 >> >> https://play.golang.org/p/NQGO5-jCVz >> >> In this it is using 5 competing receivers but every time the last one in >> line gets it, so there is scheduling and priority between two possible >> receivers when a channel is filled. >> >> This is with the range statement, of course, but I think the principle I am >> seeing here is that in all cases it's either one to one between send and >> receive, or one to many, or many from one, one side only receives the other >> only sends. If you consider each language element in the construction, and >> the 'go' to be something like a unix fork(), this means that the first >>
Re: [go-nuts] Is this a valid way of implementing a mutex?
This was a good link to follow:
https://en.wikipedia.org/wiki/Bulk_synchronous_parallel
led me here:
https://en.wikipedia.org/wiki/Automatic_mutual_exclusion
and then to here:
https://en.wikipedia.org/wiki/Transactional_memory
I think this is the pattern for implementing this using channels as an
optimistic resource state lock during access:
// in outside scope
mx := new(chan bool)
// routine that needs exclusive read or write on variable:
go func() {
for {
somestate := doSomething()
<-mx
if currentState() == somestate {
break
}
}
}
mx <- true
This is not a strict locking mechanism but a way to catch access
contention. somestate might be a nanosecond timestamp or a value that is
only read and always incremented by every accessor, signifying the number
of accesses and thus the synchronisation state before the channel is
emptied can be compared to after, and if no other access incremented that
value then it knows it can continue with the state being correctly shared.
I am deeply fascinated by distributed systems programming and this type of
scheduling system suits better dealing with potentially large and complex
state (like a database) is to take note of access sequence. If we didn't
have the possibility of one central counter that only increments, the event
could be tagged with a value that derives out of the event that called it
and the result of the next event.
As my simple iterative example showed, given the same sequence of events,
channels are deterministic, so this is an approach that is orthogonal but
in the same purpose - to prevent multiple concurrent agents from
desynchronising shared state, without blocking everything before access.
It's not a journal but the idea is to have each goroutine acting on the
final state of the value at the time it is invoked to operate on it. So you
let everyone at it but everyone stops at this barrier and checks if anyone
else changed it and then they try again to have a conflict free access.
On Sunday, 17 March 2019 20:52:12 UTC+1, Robert Engels wrote:
>
> https://g.co/kgs/2Q3a5n
>
> On Mar 17, 2019, at 2:36 PM, Louki Sumirniy > wrote:
>
> So I am incorrect that only one goroutine can access a channel at once? I
> don't understand, only one select or receive or send can happen at one
> moment per channel, so that means that if one has started others can't
> start.
>
> I was sure this was the case and this seems to confirm it:
>
> https://stackoverflow.com/a/19818448
>
> https://play.golang.org/p/NQGO5-jCVz
>
> In this it is using 5 competing receivers but every time the last one in
> line gets it, so there is scheduling and priority between two possible
> receivers when a channel is filled.
>
> This is with the range statement, of course, but I think the principle I
> am seeing here is that in all cases it's either one to one between send and
> receive, or one to many, or many from one, one side only receives the other
> only sends. If you consider each language element in the construction, and
> the 'go' to be something like a unix fork(), this means that the first
> statement inside the goroutine and the very next one in the block where the
> goroutine is started potentially can happen at the same time, but only one
> can happen at a time.
>
> So the sequence puts the receive at the end of the goroutine, which
> presumably is cleared to run, whereas the parent where it is started is
> waiting to have a receiver on the other end.
>
> If there is another thread in line to access that channel, at any given
> time only one can be on the other side of send or receive. That code shows
> that there is a deterministic order to this, so if I have several
> goroutines running each one using this same channel lock to cover a small
> number of mutable shared objects, only one can use the channel at once.
> Since the chances are equal whether one or the other gets the channel at
> any given time, but it is impossible that two can be running the accessor
> code at the same time.
>
> Thus, this construction is a mutex because it prevents more than one
> thread accessing at a time. It makes sense to me since it takes several
> instructions to read and write variables copying to register or memory. If
> you put two slots in the buffer, it can run in parallel, that's the point,
> a single element in the channel means only one access at a time and thus it
> is a bottleneck that protects from simultaneous read and right by parallel
> threads.
>
> On Sunday, 17 March 2019 14:55:58 UTC+1, Jan Mercl wrote:
>>
>> On Sun, Mar 17, 2019 at 1:04 PM Louki Sumirniy
>> wrote:
>>
>> > My understanding of channels is they basically create exclusion by
>> control of the path of execution, instead of using callbacks, or they
>> bottleneck via the cpu thread which is the reader and writer of this shared
>> data anyway.
>>
>> The language specification never mentions CPU threads. Reasoning about
>> the
Re: [go-nuts] Is this a valid way of implementing a mutex?
Ah yes, probably 'loop1' 'loop2' would be more accurate names. Yes the number of each routine is in that 'i' variable, those other labels are just to denote the position within the loops and before and after sending and the state of the truthstate variable that is only accessed inside the goroutine. Yes, this is a very artificial example because the triggering of send operations is what puts all the goroutines into action. The serial nature of the outer part in the main means that this means only the sequentially sent and received messages will mostly always come out in the same order as they go in (I'd say, pretty much always, except maybe if there was a lot of heavy competition for goroutines compared to the supply of CPU threads. If in an event driven structure with multiple workers that need to share and notify state through state variables, one goroutine might send and then another runs and receives. So, maybe this means I need to have a little more code in the goroutine after it empties the channel that verifies by reading that state hasn't changed and starts again if it has. So, ok, I guess the topic is kinda wrongly labeled. I am just looking for a way to queue read and write access to a couple of variables, and order didn't matter just that one read or write is happening at any given moment. So to be a complete example I would need randomised and deliberately congested spawing of threads competing to push to the channel, and inside the loop it should have a boolean or maybe 'last modified' stamp that after it empties the channel it checks that isn't changed and if it is restarts. But yes, that could still get into a deadlock if somehow two routines get into a perfect rhythm with each other. I will have to think more about this, the code I am trying to fix I suppose it would help if I understood its logic flow before I just try and prevent contention by changing the flow if this is possible. On Sunday, 17 March 2019 21:59:30 UTC+1, Devon H. O'Dell wrote: > > I like to think of a channel as a concurrent messaging queue. You can > do all sorts of things with such constructs, including implementing > mutual exclusion constructs, but that doesn't mean that one is the > other. > > Your playground example is a bit weird and very prone to various kinds > of race conditions that indicate that it may not be doing what you > expect. At a high level, your program loops 10 times. Each loop > iteration spawns a new concurrent process that attempts to read a > value off of a channel three times. Each iteration of the main loop > writes exactly one value into the channel. > > As a concurrent queue, writes to the channel can be thought of as > appending an element, reads can be thought of as removing an element > from the front. > > Which goroutine will read any individual value is not deterministic. > Since you're only sending 11 values over the channel, but spawn 10 > goroutines that each want to read 3 values, you have at best 6 > goroutines still waiting for data to be sent (and at worse, all 10) at > the time the program exits. > > I would also point out that this is not evidence of mutual exclusion. > Consider a case where the work performed after the channel read > exceeds the time it takes for the outer loop to write a new value to > the channel. In that case, another goroutine waiting on the channel > would begin executing. This is not mutual exclusion. In this regard, > the example you've posted is more like a condition variable or monitor > than it is like a mutex. > > Also note that in your second playground post, you're spawning 12 > goroutines, so I'm not sure what "goroutine1" and "goroutine2" are > supposed to mean. > > Kind regards, > > --dho > > Op zo 17 mrt. 2019 om 13:07 schreef Louki Sumirniy > >: > > > > https://play.golang.org/p/13GNgAyEcYv > > > > I think this demonstrates how it works quite well, it appears that > threads stick to channels, routine 0 always sends first and 1 always > receives, and this makes sense as this is the order of their invocation. I > could make more parallel threads but clearly this works as a mutex and only > one thread gets access to the channel per send/receive (one per side). > > > > On Sunday, 17 March 2019 14:55:58 UTC+1, Jan Mercl wrote: > >> > >> On Sun, Mar 17, 2019 at 1:04 PM Louki Sumirniy < > louki.sumir...@gmail.com> wrote: > >> > >> > My understanding of channels is they basically create exclusion by > control of the path of execution, instead of using callbacks, or they > bottleneck via the cpu thread which is the reader and writer of this shared > data anyway. > >> > >> The language specification never mentions CPU threads. Reasoning about > the language semantics in terms of CPU threads is not applicable. > >> > >> Threads are mentioned twice in the Memory Model document. In both cases > I think it's a mistake and we should s/threads/goroutines/ without loss of >
Re: [go-nuts] Is this a valid way of implementing a mutex?
I like to think of a channel as a concurrent messaging queue. You can do all sorts of things with such constructs, including implementing mutual exclusion constructs, but that doesn't mean that one is the other. Your playground example is a bit weird and very prone to various kinds of race conditions that indicate that it may not be doing what you expect. At a high level, your program loops 10 times. Each loop iteration spawns a new concurrent process that attempts to read a value off of a channel three times. Each iteration of the main loop writes exactly one value into the channel. As a concurrent queue, writes to the channel can be thought of as appending an element, reads can be thought of as removing an element from the front. Which goroutine will read any individual value is not deterministic. Since you're only sending 11 values over the channel, but spawn 10 goroutines that each want to read 3 values, you have at best 6 goroutines still waiting for data to be sent (and at worse, all 10) at the time the program exits. I would also point out that this is not evidence of mutual exclusion. Consider a case where the work performed after the channel read exceeds the time it takes for the outer loop to write a new value to the channel. In that case, another goroutine waiting on the channel would begin executing. This is not mutual exclusion. In this regard, the example you've posted is more like a condition variable or monitor than it is like a mutex. Also note that in your second playground post, you're spawning 12 goroutines, so I'm not sure what "goroutine1" and "goroutine2" are supposed to mean. Kind regards, --dho Op zo 17 mrt. 2019 om 13:07 schreef Louki Sumirniy : > > https://play.golang.org/p/13GNgAyEcYv > > I think this demonstrates how it works quite well, it appears that threads > stick to channels, routine 0 always sends first and 1 always receives, and > this makes sense as this is the order of their invocation. I could make more > parallel threads but clearly this works as a mutex and only one thread gets > access to the channel per send/receive (one per side). > > On Sunday, 17 March 2019 14:55:58 UTC+1, Jan Mercl wrote: >> >> On Sun, Mar 17, 2019 at 1:04 PM Louki Sumirniy >> wrote: >> >> > My understanding of channels is they basically create exclusion by control >> > of the path of execution, instead of using callbacks, or they bottleneck >> > via the cpu thread which is the reader and writer of this shared data >> > anyway. >> >> The language specification never mentions CPU threads. Reasoning about the >> language semantics in terms of CPU threads is not applicable. >> >> Threads are mentioned twice in the Memory Model document. In both cases I >> think it's a mistake and we should s/threads/goroutines/ without loss of >> correctness. >> >> Channel communication establish happen-before relations (see Memory Model). >> I see nothing equivalent directly to a critical section in that behavior, at >> least as far as when observed from outside. It was mentioned before that >> it's possible to _construct a mutex_ using a channel. I dont think that >> implies channel _is a mutex_ from the perspective of a program performing >> channel communication. The particular channel usage pattern just has the >> same semantics as a mutex. >> >> -- >> >> -j > > -- > 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+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. -- 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+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [go-nuts] Is this a valid way of implementing a mutex?
Then use a mutex or atomic spin lock (although that may have issues in the current Go implementation) > On Mar 17, 2019, at 3:56 PM, Louki Sumirniy > wrote: > > I am pretty sure the main cause of deadlocks not having senders and receivers > in pairs in the execution path such that senders precede receivers. Receivers > wait to get something, and in another post here I showed a playground that > demonstrates that if there is one channel only one thread is every accessing > them (because the code has those variables only accessed in there). In a > nondeterministic input situation where a listener might trigger a send (and > run this protected code), it is still going to be one or another is in front > of the queue, in this case we are not concerned with sequence only excluding > simultaneous read/write operations. > > I would not use a buffered channel to implement a mutex, as this implicitly > means two or more threads can read and write variables inside the goroutine. > > That was my main question, as I want to use the lightest possible mechanism > to simply control that only one reader or writer is working at one moment on > two variables. that the race detector is flagging in my code. > >> On Sunday, 17 March 2019 20:51:33 UTC+1, Jan Mercl wrote: >> On Sun, Mar 17, 2019 at 8:36 PM Louki Sumirniy >> wrote: >> >> > So I am incorrect that only one goroutine can access a channel at once? I >> > don't understand, only one select or receive or send can happen at one >> > moment per channel, so that means that if one has started others can't >> > start. >> >> All channel operations can be safely used by multiple, concurrently >> executing goroutines. The black box inside the channel implementation can do >> whatever it likes as long as it follows the specs and memory model. But from >> the outside, any goroutine can safely send to, read from, close or query >> length of a channel at any time without any explicit synchronization >> whatsoever. By safely I mean "without creating a data race just by executing >> the channel operation". The black box takes care of that. >> >> However, the preceding _does not_ mean any combination of channel operations >> performed by multiple goroutines is always sane and that it will, for >> example, never deadlock. But that's a different story. >> >> -- >> -j >> > > -- > 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+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. -- 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+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [go-nuts] Is this a valid way of implementing a mutex?
I am pretty sure the main cause of deadlocks not having senders and receivers in pairs in the execution path such that senders precede receivers. Receivers wait to get something, and in another post here I showed a playground that demonstrates that if there is one channel only one thread is every accessing them (because the code has those variables only accessed in there). In a nondeterministic input situation where a listener might trigger a send (and run this protected code), it is still going to be one or another is in front of the queue, in this case we are not concerned with sequence only excluding simultaneous read/write operations. I would not use a buffered channel to implement a mutex, as this implicitly means two or more threads can read and write variables inside the goroutine. That was my main question, as I want to use the lightest possible mechanism to simply control that only one reader or writer is working at one moment on two variables. that the race detector is flagging in my code. On Sunday, 17 March 2019 20:51:33 UTC+1, Jan Mercl wrote: > > On Sun, Mar 17, 2019 at 8:36 PM Louki Sumirniy > wrote: > > > So I am incorrect that only one goroutine can access a channel at once? > I don't understand, only one select or receive or send can happen at one > moment per channel, so that means that if one has started others can't > start. > > All channel operations can be safely used by multiple, concurrently > executing goroutines. The black box inside the channel implementation can > do whatever it likes as long as it follows the specs and memory model. But > from the outside, any goroutine can safely send to, read from, close or > query length of a channel at any time without any explicit synchronization > whatsoever. By safely I mean "without creating a data race just by > executing the channel operation". The black box takes care of that. > > However, the preceding _does not_ mean any combination of channel > operations performed by multiple goroutines is always sane and that it > will, for example, never deadlock. But that's a different story. > > -- > > -j > -- 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+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [go-nuts] Is this a valid way of implementing a mutex?
Without reading too deeply, and only judging based on your statements, it seems you are confusing implementation with specification. The things you cite are subject to change. You need to reason based on the specification not the observed behavior. Then use the observed behavior to argue that it doesn’t meet the specification. > On Mar 17, 2019, at 3:50 PM, Louki Sumirniy > wrote: > > https://play.golang.org/p/Kz9SsFeb1iK > > This prints something at each interstice of the execution path and it is of > course deterministic. > > I think the reason why the range loop always chooses one per channel, last > one in order because it uses a LIFO queue so the last in line gets filled > first. > > The example in there shows with 1, 2 and 3 slots in the buffer, the exclusion > only occurs properly in the single slot, first goroutine always sends and > second always receives. This is because of the order of execution. If the > sends were externally determined and random it still only gets written within > one location. If you only read and write these variables inside this loop > they can never be clobbered while you read them, which is the contention that > a mutex is for determining the sequence of execution. > > The main costs I see are that though the overhead is lower, there is still > overhead so there is some reasonable ratio between the amount of code you > execute in a given moment is shorter the other competing parallel threads > with external, not-deterministic inputs will lock the value for not longer > than you want to avoid with adding response latency. The scheduling overhead > escalates with the number of threads and costs also in memory. > > But my main point is that it functions correctly as a mutex mechanism and > code inside the goroutine can count on nobody else accessing the variables > that are only read and written inside it. > >> On Sunday, 17 March 2019 20:36:40 UTC+1, Louki Sumirniy wrote: >> So I am incorrect that only one goroutine can access a channel at once? I >> don't understand, only one select or receive or send can happen at one >> moment per channel, so that means that if one has started others can't >> start. >> >> I was sure this was the case and this seems to confirm it: >> >> https://stackoverflow.com/a/19818448 >> >> https://play.golang.org/p/NQGO5-jCVz >> >> In this it is using 5 competing receivers but every time the last one in >> line gets it, so there is scheduling and priority between two possible >> receivers when a channel is filled. >> >> This is with the range statement, of course, but I think the principle I am >> seeing here is that in all cases it's either one to one between send and >> receive, or one to many, or many from one, one side only receives the other >> only sends. If you consider each language element in the construction, and >> the 'go' to be something like a unix fork(), this means that the first >> statement inside the goroutine and the very next one in the block where the >> goroutine is started potentially can happen at the same time, but only one >> can happen at a time. >> >> So the sequence puts the receive at the end of the goroutine, which >> presumably is cleared to run, whereas the parent where it is started is >> waiting to have a receiver on the other end. >> >> If there is another thread in line to access that channel, at any given time >> only one can be on the other side of send or receive. That code shows that >> there is a deterministic order to this, so if I have several goroutines >> running each one using this same channel lock to cover a small number of >> mutable shared objects, only one can use the channel at once. Since the >> chances are equal whether one or the other gets the channel at any given >> time, but it is impossible that two can be running the accessor code at the >> same time. >> >> Thus, this construction is a mutex because it prevents more than one thread >> accessing at a time. It makes sense to me since it takes several >> instructions to read and write variables copying to register or memory. If >> you put two slots in the buffer, it can run in parallel, that's the point, a >> single element in the channel means only one access at a time and thus it is >> a bottleneck that protects from simultaneous read and right by parallel >> threads. >> >>> On Sunday, 17 March 2019 14:55:58 UTC+1, Jan Mercl wrote: >>> On Sun, Mar 17, 2019 at 1:04 PM Louki Sumirniy >>> wrote: >>> >>> > My understanding of channels is they basically create exclusion by >>> > control of the path of execution, instead of using callbacks, or they >>> > bottleneck via the cpu thread which is the reader and writer of this >>> > shared data anyway. >>> >>> The language specification never mentions CPU threads. Reasoning about the >>> language semantics in terms of CPU threads is not applicable. >>> >>> Threads are mentioned twice in the Memory Model document. In both
Re: [go-nuts] Is this a valid way of implementing a mutex?
https://play.golang.org/p/Kz9SsFeb1iK This prints something at each interstice of the execution path and it is of course deterministic. I think the reason why the range loop always chooses one per channel, last one in order because it uses a LIFO queue so the last in line gets filled first. The example in there shows with 1, 2 and 3 slots in the buffer, the exclusion only occurs properly in the single slot, first goroutine always sends and second always receives. This is because of the order of execution. If the sends were externally determined and random it still only gets written within one location. If you only read and write these variables inside this loop they can never be clobbered while you read them, which is the contention that a mutex is for determining the sequence of execution. The main costs I see are that though the overhead is lower, there is still overhead so there is some reasonable ratio between the amount of code you execute in a given moment is shorter the other competing parallel threads with external, not-deterministic inputs will lock the value for not longer than you want to avoid with adding response latency. The scheduling overhead escalates with the number of threads and costs also in memory. But my main point is that it functions correctly as a mutex mechanism and code inside the goroutine can count on nobody else accessing the variables that are only read and written inside it. On Sunday, 17 March 2019 20:36:40 UTC+1, Louki Sumirniy wrote: > > So I am incorrect that only one goroutine can access a channel at once? I > don't understand, only one select or receive or send can happen at one > moment per channel, so that means that if one has started others can't > start. > > I was sure this was the case and this seems to confirm it: > > https://stackoverflow.com/a/19818448 > > https://play.golang.org/p/NQGO5-jCVz > > In this it is using 5 competing receivers but every time the last one in > line gets it, so there is scheduling and priority between two possible > receivers when a channel is filled. > > This is with the range statement, of course, but I think the principle I > am seeing here is that in all cases it's either one to one between send and > receive, or one to many, or many from one, one side only receives the other > only sends. If you consider each language element in the construction, and > the 'go' to be something like a unix fork(), this means that the first > statement inside the goroutine and the very next one in the block where the > goroutine is started potentially can happen at the same time, but only one > can happen at a time. > > So the sequence puts the receive at the end of the goroutine, which > presumably is cleared to run, whereas the parent where it is started is > waiting to have a receiver on the other end. > > If there is another thread in line to access that channel, at any given > time only one can be on the other side of send or receive. That code shows > that there is a deterministic order to this, so if I have several > goroutines running each one using this same channel lock to cover a small > number of mutable shared objects, only one can use the channel at once. > Since the chances are equal whether one or the other gets the channel at > any given time, but it is impossible that two can be running the accessor > code at the same time. > > Thus, this construction is a mutex because it prevents more than one > thread accessing at a time. It makes sense to me since it takes several > instructions to read and write variables copying to register or memory. If > you put two slots in the buffer, it can run in parallel, that's the point, > a single element in the channel means only one access at a time and thus it > is a bottleneck that protects from simultaneous read and right by parallel > threads. > > On Sunday, 17 March 2019 14:55:58 UTC+1, Jan Mercl wrote: >> >> On Sun, Mar 17, 2019 at 1:04 PM Louki Sumirniy >> wrote: >> >> > My understanding of channels is they basically create exclusion by >> control of the path of execution, instead of using callbacks, or they >> bottleneck via the cpu thread which is the reader and writer of this shared >> data anyway. >> >> The language specification never mentions CPU threads. Reasoning about >> the language semantics in terms of CPU threads is not applicable. >> >> Threads are mentioned twice in the Memory Model document. In both cases I >> think it's a mistake and we should s/threads/goroutines/ without loss of >> correctness. >> >> Channel communication establish happen-before relations (see Memory >> Model). I see nothing equivalent directly to a critical section in that >> behavior, at least as far as when observed from outside. It was mentioned >> before that it's possible to _construct a mutex_ using a channel. I dont >> think that implies channel _is a mutex_ from the perspective of a program >> performing channel communication.
Re: [go-nuts] Is this a valid way of implementing a mutex?
https://play.golang.org/p/13GNgAyEcYv I think this demonstrates how it works quite well, it appears that threads stick to channels, routine 0 always sends first and 1 always receives, and this makes sense as this is the order of their invocation. I could make more parallel threads but clearly this works as a mutex and only one thread gets access to the channel per send/receive (one per side). On Sunday, 17 March 2019 14:55:58 UTC+1, Jan Mercl wrote: > > On Sun, Mar 17, 2019 at 1:04 PM Louki Sumirniy > wrote: > > > My understanding of channels is they basically create exclusion by > control of the path of execution, instead of using callbacks, or they > bottleneck via the cpu thread which is the reader and writer of this shared > data anyway. > > The language specification never mentions CPU threads. Reasoning about the > language semantics in terms of CPU threads is not applicable. > > Threads are mentioned twice in the Memory Model document. In both cases I > think it's a mistake and we should s/threads/goroutines/ without loss of > correctness. > > Channel communication establish happen-before relations (see Memory > Model). I see nothing equivalent directly to a critical section in that > behavior, at least as far as when observed from outside. It was mentioned > before that it's possible to _construct a mutex_ using a channel. I dont > think that implies channel _is a mutex_ from the perspective of a program > performing channel communication. The particular channel usage pattern just > has the same semantics as a mutex. > > -- > > -j > -- 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+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [go-nuts] Is this a valid way of implementing a mutex?
https://g.co/kgs/2Q3a5n > On Mar 17, 2019, at 2:36 PM, Louki Sumirniy > wrote: > > So I am incorrect that only one goroutine can access a channel at once? I > don't understand, only one select or receive or send can happen at one moment > per channel, so that means that if one has started others can't start. > > I was sure this was the case and this seems to confirm it: > > https://stackoverflow.com/a/19818448 > > https://play.golang.org/p/NQGO5-jCVz > > In this it is using 5 competing receivers but every time the last one in line > gets it, so there is scheduling and priority between two possible receivers > when a channel is filled. > > This is with the range statement, of course, but I think the principle I am > seeing here is that in all cases it's either one to one between send and > receive, or one to many, or many from one, one side only receives the other > only sends. If you consider each language element in the construction, and > the 'go' to be something like a unix fork(), this means that the first > statement inside the goroutine and the very next one in the block where the > goroutine is started potentially can happen at the same time, but only one > can happen at a time. > > So the sequence puts the receive at the end of the goroutine, which > presumably is cleared to run, whereas the parent where it is started is > waiting to have a receiver on the other end. > > If there is another thread in line to access that channel, at any given time > only one can be on the other side of send or receive. That code shows that > there is a deterministic order to this, so if I have several goroutines > running each one using this same channel lock to cover a small number of > mutable shared objects, only one can use the channel at once. Since the > chances are equal whether one or the other gets the channel at any given > time, but it is impossible that two can be running the accessor code at the > same time. > > Thus, this construction is a mutex because it prevents more than one thread > accessing at a time. It makes sense to me since it takes several instructions > to read and write variables copying to register or memory. If you put two > slots in the buffer, it can run in parallel, that's the point, a single > element in the channel means only one access at a time and thus it is a > bottleneck that protects from simultaneous read and right by parallel threads. > >> On Sunday, 17 March 2019 14:55:58 UTC+1, Jan Mercl wrote: >> On Sun, Mar 17, 2019 at 1:04 PM Louki Sumirniy >> wrote: >> >> > My understanding of channels is they basically create exclusion by control >> > of the path of execution, instead of using callbacks, or they bottleneck >> > via the cpu thread which is the reader and writer of this shared data >> > anyway. >> >> The language specification never mentions CPU threads. Reasoning about the >> language semantics in terms of CPU threads is not applicable. >> >> Threads are mentioned twice in the Memory Model document. In both cases I >> think it's a mistake and we should s/threads/goroutines/ without loss of >> correctness. >> >> Channel communication establish happen-before relations (see Memory Model). >> I see nothing equivalent directly to a critical section in that behavior, at >> least as far as when observed from outside. It was mentioned before that >> it's possible to _construct a mutex_ using a channel. I dont think that >> implies channel _is a mutex_ from the perspective of a program performing >> channel communication. The particular channel usage pattern just has the >> same semantics as a mutex. >> >> -- >> -j >> > > -- > 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+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. -- 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+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [go-nuts] Is this a valid way of implementing a mutex?
On Sun, Mar 17, 2019 at 8:36 PM Louki Sumirniy < louki.sumirniy.stal...@gmail.com> wrote: > So I am incorrect that only one goroutine can access a channel at once? I don't understand, only one select or receive or send can happen at one moment per channel, so that means that if one has started others can't start. All channel operations can be safely used by multiple, concurrently executing goroutines. The black box inside the channel implementation can do whatever it likes as long as it follows the specs and memory model. But from the outside, any goroutine can safely send to, read from, close or query length of a channel at any time without any explicit synchronization whatsoever. By safely I mean "without creating a data race just by executing the channel operation". The black box takes care of that. However, the preceding _does not_ mean any combination of channel operations performed by multiple goroutines is always sane and that it will, for example, never deadlock. But that's a different story. -- -j -- 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+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [go-nuts] Is this a valid way of implementing a mutex?
So I am incorrect that only one goroutine can access a channel at once? I don't understand, only one select or receive or send can happen at one moment per channel, so that means that if one has started others can't start. I was sure this was the case and this seems to confirm it: https://stackoverflow.com/a/19818448 https://play.golang.org/p/NQGO5-jCVz In this it is using 5 competing receivers but every time the last one in line gets it, so there is scheduling and priority between two possible receivers when a channel is filled. This is with the range statement, of course, but I think the principle I am seeing here is that in all cases it's either one to one between send and receive, or one to many, or many from one, one side only receives the other only sends. If you consider each language element in the construction, and the 'go' to be something like a unix fork(), this means that the first statement inside the goroutine and the very next one in the block where the goroutine is started potentially can happen at the same time, but only one can happen at a time. So the sequence puts the receive at the end of the goroutine, which presumably is cleared to run, whereas the parent where it is started is waiting to have a receiver on the other end. If there is another thread in line to access that channel, at any given time only one can be on the other side of send or receive. That code shows that there is a deterministic order to this, so if I have several goroutines running each one using this same channel lock to cover a small number of mutable shared objects, only one can use the channel at once. Since the chances are equal whether one or the other gets the channel at any given time, but it is impossible that two can be running the accessor code at the same time. Thus, this construction is a mutex because it prevents more than one thread accessing at a time. It makes sense to me since it takes several instructions to read and write variables copying to register or memory. If you put two slots in the buffer, it can run in parallel, that's the point, a single element in the channel means only one access at a time and thus it is a bottleneck that protects from simultaneous read and right by parallel threads. On Sunday, 17 March 2019 14:55:58 UTC+1, Jan Mercl wrote: > > On Sun, Mar 17, 2019 at 1:04 PM Louki Sumirniy > wrote: > > > My understanding of channels is they basically create exclusion by > control of the path of execution, instead of using callbacks, or they > bottleneck via the cpu thread which is the reader and writer of this shared > data anyway. > > The language specification never mentions CPU threads. Reasoning about the > language semantics in terms of CPU threads is not applicable. > > Threads are mentioned twice in the Memory Model document. In both cases I > think it's a mistake and we should s/threads/goroutines/ without loss of > correctness. > > Channel communication establish happen-before relations (see Memory > Model). I see nothing equivalent directly to a critical section in that > behavior, at least as far as when observed from outside. It was mentioned > before that it's possible to _construct a mutex_ using a channel. I dont > think that implies channel _is a mutex_ from the perspective of a program > performing channel communication. The particular channel usage pattern just > has the same semantics as a mutex. > > -- > > -j > -- 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+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [go-nuts] Is this a valid way of implementing a mutex?
On Sun, Mar 17, 2019 at 1:04 PM Louki Sumirniy < louki.sumirniy.stal...@gmail.com> wrote: > My understanding of channels is they basically create exclusion by control of the path of execution, instead of using callbacks, or they bottleneck via the cpu thread which is the reader and writer of this shared data anyway. The language specification never mentions CPU threads. Reasoning about the language semantics in terms of CPU threads is not applicable. Threads are mentioned twice in the Memory Model document. In both cases I think it's a mistake and we should s/threads/goroutines/ without loss of correctness. Channel communication establish happen-before relations (see Memory Model). I see nothing equivalent directly to a critical section in that behavior, at least as far as when observed from outside. It was mentioned before that it's possible to _construct a mutex_ using a channel. I dont think that implies channel _is a mutex_ from the perspective of a program performing channel communication. The particular channel usage pattern just has the same semantics as a mutex. -- -j -- 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+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [go-nuts] Is this a valid way of implementing a mutex?
I didn't mention actually excluding access by passing data through values either, this was just using a flag to confine accessor code to one thread, essentially, which has the same result as a mutex as far as its granularity goes. On Sunday, 17 March 2019 13:04:26 UTC+1, Louki Sumirniy wrote: > > My understanding of channels is they basically create exclusion by control > of the path of execution, instead of using callbacks, or they bottleneck > via the cpu thread which is the reader and writer of this shared data > anyway. > > I think the way they work is that there is queues for read and write > access based on most recent, so when a channel is loaded, the most > proximate (if possible same) thread executes the other side of the channel, > and then if another thread off execution bumps into a patch involving > accessing the channel, if the channel is full and it wants to fill, it is > blocked, if it wants to unload, and it's empty, it is blocked, but the main > goroutine scheduler basically is the gatekeeper and assigns exeuction > priority based on sequence and first available. > > So, if that is correct, then the version with the load after the goroutine > and unload at the end of the goroutine functions to grab the thread of the > channel, and when it ends, gives it back, and if another is ready to use > it, it is already lined up and the transfer is made. So any code I wrap > every place inside the goroutine/unload-load pattern (including inside > itself) can only be run by one thread at once. If you ask me, that's better > and more logical than callbacks. > > On Sunday, 17 March 2019 11:05:35 UTC+1, Jan Mercl wrote: >> >> >> On Sun, Mar 17, 2019 at 10:49 AM Louki Sumirniy >> wrote: >> >> > I just ran into my first race condition-related error and it made me >> wonder about how one takes advantage of the mutex properties of channels. >> >> I'd not say there are any such properties. However, it's easy to >> implement a semaphore with a channel. And certain semaphores can act as >> mutexes. >> >> > If I understand correctly, this is a simple example: >> >> That example illustrates IMO more of a condition/signal than a typical >> mutex usage pattern. >> >> -- >> >> -j >> > -- 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+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [go-nuts] Is this a valid way of implementing a mutex?
My understanding of channels is they basically create exclusion by control of the path of execution, instead of using callbacks, or they bottleneck via the cpu thread which is the reader and writer of this shared data anyway. I think the way they work is that there is queues for read and write access based on most recent, so when a channel is loaded, the most proximate (if possible same) thread executes the other side of the channel, and then if another thread off execution bumps into a patch involving accessing the channel, if the channel is full and it wants to fill, it is blocked, if it wants to unload, and it's empty, it is blocked, but the main goroutine scheduler basically is the gatekeeper and assigns exeuction priority based on sequence and first available. So, if that is correct, then the version with the load after the goroutine and unload at the end of the goroutine functions to grab the thread of the channel, and when it ends, gives it back, and if another is ready to use it, it is already lined up and the transfer is made. So any code I wrap every place inside the goroutine/unload-load pattern (including inside itself) can only be run by one thread at once. If you ask me, that's better and more logical than callbacks. On Sunday, 17 March 2019 11:05:35 UTC+1, Jan Mercl wrote: > > > On Sun, Mar 17, 2019 at 10:49 AM Louki Sumirniy > wrote: > > > I just ran into my first race condition-related error and it made me > wonder about how one takes advantage of the mutex properties of channels. > > I'd not say there are any such properties. However, it's easy to implement > a semaphore with a channel. And certain semaphores can act as mutexes. > > > If I understand correctly, this is a simple example: > > That example illustrates IMO more of a condition/signal than a typical > mutex usage pattern. > > -- > > -j > -- 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+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[go-nuts] Is this a valid way of implementing a mutex?
I just ran into my first race condition-related error and it made me wonder
about how one takes advantage of the mutex properties of channels.
If I understand correctly, this is a simple example:
mx := make(chan bool)
// in separate scope, presumably...
go func() {
<-mx
doSomething()
}()
mx <- true
So what happens here is the contents of the goroutine are waiting on
something to come out of the channel, which is executed in parallel, or in
sequential order, the content of the goroutine doesn't start until the
channel is loaded, which happens at the same time, so it's impossible for
two competing over the same lock to hold it at the same time.
If we have one thread, I think the goroutine runs first, it hits a block,
and then the main resumes which blocks loading the other one, so if another
thread also tries to wait on that channel it will be second (or later) in
line waiting on that channel to pop something out.
I can see there is also another strategy where the shared memory is the
variable passing through the channel (so it would also probably be a chan
*type as well, distinguishing it), and the difference and which to choose
would depend on how many locks you want to tie to how many sensitive items.
If it's a bundle of things, like a map or array, then it might be better to
pass the object around with its pointers, using channels as entrypoints.
But more often it's one or two out of a set of other variables so it makes
more sense to lock them separately, and with channels each lock would be
just one extra (small) field.
Or maybe I am saying that backwards. If the state is big, use a few small
locks to cover each part of the ephemeral shared state, if the state is
small, pass it around directly through channels.
I'm really a beginner at concurrent programming, I apologise for my
noobishness... and thanks to anyone who helps me and anyone understand it
better :)
--
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
