Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

x/talks: concurrency 2012 sequenceboring.go fails to ensure lockstep sequenced behavior #47135

Closed
WhisperingChaos opened this issue Jul 12, 2021 · 3 comments

Comments

@WhisperingChaos
Copy link

What version of Go are you using (go version)?

go1.16.5.

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

go env Output
The environment of: https://play.golang.org/

What did you do?

Eliminate simulated workload represented by the randomly assigned timer from sequenceboring.go

See playground version.

What did you expect to see?

The lockstep, sequenced, round-robin scheduling as communicated by speaker during this presentation.

Ann: 0
Joe: 0
Ann: 1
Joe: 1
Ann: 2
Joe: 2
Ann: 3
Joe: 3
Ann: 4
Joe: 4
You're all boring; I'm leaving.

Or a similar alternating sequence starting instead with Joe: 0

What did you see instead?

Joe or Ann can take an out of order turn from the other.

Please note the output varies from run to run depending on the go scheduler's state. For example, the code may periodically produce the intended lockstep behavior, however, entropy dictates otherwise.

Ann: 0
Joe: 0
Joe: 1
Ann: 1
Ann: 2
Joe: 2
Joe: 3
Ann: 3
Ann: 4
Joe: 4
You're all boring; I'm leaving.

Program exited.

Why does the bug occur?

The code doesn't encode a strict happens before to order go routine messaging. The coordination mechanism using the wait channel abstraction becomes a race condition within the scheduler when the effort to process the simulated workloads conclude at nearly the same instance.

Why does the bug matter?

Due to the speaker's prominence:

  • The code is often replicated without questioning its correctness - propagating the bug.
  • When filing an issue in another repository of code derived from this example, the site exhibited a bias favoring the correctness of the speaker's implementation, although evidence to the contrary was provided.
@gopherbot gopherbot added this to the Unreleased milestone Jul 12, 2021
@cherrymui cherrymui changed the title x/talks concurrency 2012 sequenceboring.go fails to ensure lockstep sequenced behavior x/talks: concurrency 2012 sequenceboring.go fails to ensure lockstep sequenced behavior Jul 12, 2021
@cherrymui
Copy link
Member

I don't think the author claimed this outputs in "round-robin scheduling". The lockstep here means both Ann and Joe outputting 0, then both outputting 1, ..., i.e. no one can output 1 before both have outputted 0. In particular, this is in contrast of the example a couple of slides before, where Joe can output 3, 4, 5 before Ann outputs 3 ( https://www.youtube.com/watch?v=f6kdp27TYZs&t=1095s ). I think this works as intended.

cc @robpike in case there is anything to clarify. Thanks.

@robpike
Copy link
Contributor

robpike commented Jul 12, 2021

Working as intended. No claim made for lockstep.

@robpike robpike reopened this Jul 12, 2021
@robpike robpike closed this as completed Jul 12, 2021
@WhisperingChaos
Copy link
Author

@cherrymui

  • Thanks for fixing the issue’s title.

  • You are correct, Rob never uttered "round-robin scheduling" during his presentation. I apologize for including this phrase in the initial post.

  • I believe we agree that Rob intended the messaging in sequenceboring.go to execute in a lockstep synchronous/sequenced way. This is exactly what Rob said by the link provided in the initial post:

    "So when we run it now, you can see they're back in lockstep, because even though the timing is random, the sequencing here, with message 1 wait and message 2 wait, means that the..."

    Moreover, Rob concisely states when he begins the set of slides titled: “Restoring sequencing” his intention: “We wanted to have them be totally lockstep and synchronous.”

  • I’m confident that the intended “sequence” behavior should strictly alternate between “Joe: N” and “Ann: N:” or vice versa due to the context of Rob’s statements. He titled the slides that explain the code in sequenceboring.go as “Restoring sequencing”. This phrase refers back to the discussion of generator2boring.go and focuses on its code segment. Rob describes the resultant message ordering as derived from: “the two guys are taking turns, not only in printing the values out but also in executing them”.

    In fact, due to the explicit Happens Before encoding of generator2boring.go Joe’s messages will always precede Ann’s which isn’t the case in sequenceboring.go.

  • Although Rob posted “Working as intended.” to this thread, I believe he reviewed the link you provided which referenced the slides titled “Multiplexing”. The code discussed by the “Multiplexing” slides do not enforce lockstep behavior.

  • Finally, I’m not the first individual to experience the reported anomaly in sequenceboring.go. I thought if others had encountered it, the issue might be more thoroughly reviewed instead of being immediately closed. I checked golang-nuts for an existing thread and found this mention by Tony Worm.

@golang golang locked and limited conversation to collaborators Jul 14, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

4 participants