TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

When the Simplest Concurrent Program Goes Against All Intuition

45 点作者 simplegeek4 个月前

10 条评论

colonCapitalDee4 个月前
It&#x27;s never actually explained how n=2 is possible. Here&#x27;s how it works:<p>P1 and P2 start executing. P1 sets temp=1, then P2 runs through the loop for i=1..9. Then P1 sets n=temp=1. P2 sets temp=2, then P1 resumes executing for i=2..10, and completes. P2 sets n=temp=2, then completes.<p>The intuition is P1 checkpoints, P2 runs through the loop up until the last iteration, P1 resets n to the checkpoint + 1, P2 checkpoints, P1 runs through the loop, then P2 resets n to the checkpoint + 1.
评论 #42747001 未加载
tombert4 个月前
This was fun to port over to PlusCal to verify it myself:<p><pre><code> EXTENDS Naturals, Sequences (*--algorithm StateStore { variables n = 0; completions = &lt;&lt;&gt;&gt;; define { Invar == Len(completions) = 2 =&gt; n # 2 } fair process (thing \in {&quot;p&quot;, &quot;q&quot;}) variables i = 0, temp = 0; { Loop: while (i &lt; 10) { First: temp := n + 1; Second: n := temp; Last: i := i + 1; }; Complete: completions := Append(completions, 1) } }*) </code></pre> (I acknowledge that this isn&#x27;t the most elegant Pluscal but I think it is a roughly accurate?)
评论 #42746099 未加载
Groxx4 个月前
To be pedantic (which I feel is fair because it&#x27;s a concurrency question about possibilities):<p>&gt;<i>If we run P and Q concurrently, with ‘n’ initialized to zero, what would the value of ‘n’ be when the two processes finish executing their statements?</i><p>It depends a lot on the observer of `n` and what relationship it has with P and Q. Which isn&#x27;t defined.<p>E.g. a trivial boundary-answer is that it can be 0, if nothing guarantees that P&#x27;s and Q&#x27;s threads&#x27; memory reaches the `n`-observer&#x27;s thread. This is somewhat common if you try to synchronize via `sleep`, because that usually doesn&#x27;t guarantee anything as all.<p>We also don&#x27;t know the computer architecture. We can probably assume at least one byte moves between memory levels atomically, because basically every practical system does that, but that doesn&#x27;t have to be true. If <i>bits</i> move between memory levels independently, this could observe <i>31</i>, because it can be any combination of the bits between `00000` and `10100`, which includes `01011` -&gt; there can be a `1` in any position, including all positions, so you can observe a number that was <i>never</i> assigned. (IRL: multi-word values and partial initializations can do this, e.g. it&#x27;s why double-checked locking is flawed without something to guarantee initialization completes before the pointer is exposed)
评论 #42746148 未加载
fjfaase4 个月前
This implicitely assumes atomic assignments, meaning that during an assignment all bits representing a value are transfered in one atomic unit. This sounds a bit trivial, but if one would be working with large integers that are stored in multiple memory words, it is less trivial.<p>I think it is possible to implement locking with only atomic assigments.
评论 #42749260 未加载
评论 #42751029 未加载
评论 #42744953 未加载
hedin_hiervard4 个月前
I was once asked a very similar problem during a job interview for a position of a software engineer. I was offered to solve it on a piece of paper or orally. We ran out of time and they offered me to take it home. I did and I spent a few hours thinking about it. Google and ChatGPT were not able to produce better results than the intuitive answer, so I built a test program that confirmed the weird behaviour. After meditating for a few hours I was able to find the correct answer and I was indeed fascinated by this. Do you also think it&#x27;s too much for a usual interview?
评论 #42747224 未加载
sim7c004 个月前
the best thing i think i read somewhere is to think of modern cpus as a bunch of computers on a network. each task is transmitted in messages over the network potentially, executed and its result sent back in a packet. despite this not being fully accurate it does give an idea that even in a set of 100 operations, due to caches, latencies and also kernel&#x2F;hardware stuff happening during these 100 operations however much you try to isolate them, the first operation submitted might see its result sent back last.<p>this will help to determine or realize better when and where synchronization is needed even though you might not expect it. (or remoddeling of the code).<p>its extremely hard to writr concurrent code well. i think i&#x27;ve hardly ever managed lockless code that wasnt super bugy (yet! :D). it takes a lot of focus and patience, and tons details about the platform(s) it might run on.
chozang4 个月前
Bonus points for mentioning Spin. My &quot;Software Engineering&quot; course in 1987 in grad school would have been more accurately titled, &quot;Using the Spin Model Checker&quot;. Except when I was looking for it, I had never came across any mention of Spin since.
jpc04 个月前
As another commentator mentioned, you have violated a precondition, there&#x27;s no point trying to understand what would happen because its indeterminate.
Izikiel434 个月前
The intuition I developed over the years says that result is unknown, it&#x27;s a race condition, all bets are off. Specially since doing N+1.
dtgriscom4 个月前
Seems pretty clear that the result could be anything from 1 to 20.<p>(Assumes atomic assignments, as noted by someone else.)
评论 #42746021 未加载