多个线程访问一个变量
Multiple threads accessing one variable
我在正在阅读的教科书中发现了这个问题。下面也给出了解决方案。我无法理解最小值是 2。为什么一个线程不能读取 0，所有其他线程都执行并写入 1？而无论是1还是2，最后写入的线程一定还是要完成自己的循环？
int n = 0;
int main(int argc, char **argv) {
for (i = 0; i < 5; i++) {
int tmp = n;
tmp = tmp + 1;
n = tmp;
}
return 0;
}
If a single thread ran this application, you would expect the final
output to be 5. What if 5 threads ran the same loop in parallel? What
are the largest and smallest values n could have? The largest should
be selfevident: 25, with 5 increments from 5 threads. However,
reasoning about the smallest possible value is more difficult. Hint: n
can be less than 5, but it is up to you to figure out why.
解决方案：
With five threads running this five-iteration loop and with no
protection from concurrent accesses, the lowest value that n can reach
is two. Understanding how to reach this result is easiest when working
backwards from the final result. For the final output to be two, a
thread must have read a value of one from n, incremented it, and then
written two. That means that another thread wrote one, implying that
it also initially read zero (which is also the starting value for n).
This accounts for the behavior of two of the five threads. However,
for this behavior to occur the results of the other three threads must
have been overwritten. Two valid executions could accomplish this.
Either 1) all three threads began and completed execution between the
first thread reading zero and writing one, or 2) all three threads
began and completed execution between the final thread reading one and
writing two. Both execution orderings are valid.
重点是线程共享同一个数据实例。此外，似乎假设所有其他线程 运行 以相同的执行速率。
因此，随着每个线程循环（到达 for 的 i++ 部分），它们几乎同时递增 i，所以就好像代码是写的：
for (i = 0; i < 5; i++, i++, i++, i++, i++)
...
至少在给出最小迭代次数的极端情况下。
仅需补充一些见解：在 C 语言中使用 + 运算符进行加法、减法等不仅仅是 1 次操作。在汇编级别，+ 操作由多条指令组成。如果多个线程要访问一个变量，并且这些指令交织不当，最终结果可能是非常不正确的结果 -> 这是我们需要互斥锁、信号量和条件变量等东西的另一个原因。
The largest should be selfevident: 25, with 5 increments from 5 threads.
完全错误。不管怎么说，这永远都不应该听（至少在涉及线程的事情上），句号。
int tmp = n;
tmp = tmp + 1;
n = tmp;
想象一个 CPU 没有增量操作，但是有一个高效的 "add 10" 操作和一个高效的 "subtract nine" 操作。在这样的 CPU 上，tmp = tmp + 1; 可以优化为 tmp += 10; tmp -= 9;。编译器还可以通过对 n.
进行操作来完全优化掉 tmp
所以这段代码可以等价于：
n += 10;
n -= 9;
现在假设发生这种情况：所有五个线程都加 10，所以 n 现在是 50。第一个线程读取 50，其他四个线程减去 9。第一个线程从它读取的 50 中减去 9并写入 41。所以当所有完成后，n 是 41.
所以，所谓不言自明的说法是完全错误的。写这篇文章的人不了解 C 中的线程。
if every thread writes a 1 then the final value cannot magically be something else
也是彻头彻尾的错误。考虑一个 CPU，它通过先写入 0 然后递增值来写入 1。如果这发生在两个内核上，最终结果可能是 2。这本教科书是由根本不了解线程和未定义行为的人编写的。
（我假设这本教科书不限于它所说的是真的某些特殊上下文。例如，它可能使用 "C-like" 代码作为平台中立的汇编语言的一种形式并且它可能会假设对齐整数具有特定保证的平台。但如果是这样，它所教的内容根本根本不会转化为 C 代码，并且只适用于编写汇编的人CPU 上的代码，其规则符合教科书的假设。）
假设每个线程都有一个本地 i（即，无论如何每个线程都会 运行 进行 5 次迭代），让我们尝试得到 1 作为结果。这意味着要写入值的 last 线程必须在其 5th 迭代中为 n 读取 0。发生这种情况的唯一方法是，如果在该线程的第 5 次迭代开始时还没有线程写入 n，但要使该线程处于第 5 次迭代，该线程本身必须写入 n , 因此这是不可能的。
因此最小的可能结果是2，这可能发生，例如，如下：最后一个写入n的线程已经完成4次迭代，然后另一个线程写入1，最后一个线程读取1在第 5 次迭代开始时，所有其他线程在最后一个线程之前完成所有迭代，最后最后一个线程完成其第 5 次迭代写入 2.
免责声明：我正在回答关于多线程的概念问题——正如其他人所指出的，缺乏原子性可能会导致未定义如果按原样使用提供的 C 代码，则行为和任意结果。基于问题的“不言而喻”的最大数案例，我猜测教科书的作者要么没有意识到这一点，要么正在使用类似 C 的伪代码来说明这个概念。如果是前者，那么正确答案就是书上写错了，但我觉得后一种情况下的答案也很有教育意义。
我在正在阅读的教科书中发现了这个问题。下面也给出了解决方案。我无法理解最小值是 2。为什么一个线程不能读取 0，所有其他线程都执行并写入 1？而无论是1还是2，最后写入的线程一定还是要完成自己的循环？
int n = 0;
int main(int argc, char **argv) {
for (i = 0; i < 5; i++) {
int tmp = n;
tmp = tmp + 1;
n = tmp;
}
return 0;
}
If a single thread ran this application, you would expect the final output to be 5. What if 5 threads ran the same loop in parallel? What are the largest and smallest values n could have? The largest should be selfevident: 25, with 5 increments from 5 threads. However, reasoning about the smallest possible value is more difficult. Hint: n can be less than 5, but it is up to you to figure out why.
解决方案：
With five threads running this five-iteration loop and with no protection from concurrent accesses, the lowest value that n can reach is two. Understanding how to reach this result is easiest when working backwards from the final result. For the final output to be two, a thread must have read a value of one from n, incremented it, and then written two. That means that another thread wrote one, implying that it also initially read zero (which is also the starting value for n). This accounts for the behavior of two of the five threads. However, for this behavior to occur the results of the other three threads must have been overwritten. Two valid executions could accomplish this. Either 1) all three threads began and completed execution between the first thread reading zero and writing one, or 2) all three threads began and completed execution between the final thread reading one and writing two. Both execution orderings are valid.
重点是线程共享同一个数据实例。此外，似乎假设所有其他线程 运行 以相同的执行速率。
因此，随着每个线程循环（到达 for 的 i++ 部分），它们几乎同时递增 i，所以就好像代码是写的：
for (i = 0; i < 5; i++, i++, i++, i++, i++)
...
至少在给出最小迭代次数的极端情况下。
仅需补充一些见解：在 C 语言中使用 + 运算符进行加法、减法等不仅仅是 1 次操作。在汇编级别，+ 操作由多条指令组成。如果多个线程要访问一个变量，并且这些指令交织不当，最终结果可能是非常不正确的结果 -> 这是我们需要互斥锁、信号量和条件变量等东西的另一个原因。
The largest should be selfevident: 25, with 5 increments from 5 threads.
完全错误。不管怎么说，这永远都不应该听（至少在涉及线程的事情上），句号。
int tmp = n;
tmp = tmp + 1;
n = tmp;
想象一个 CPU 没有增量操作，但是有一个高效的 "add 10" 操作和一个高效的 "subtract nine" 操作。在这样的 CPU 上，tmp = tmp + 1; 可以优化为 tmp += 10; tmp -= 9;。编译器还可以通过对 n.
tmp
所以这段代码可以等价于：
n += 10;
n -= 9;
现在假设发生这种情况：所有五个线程都加 10，所以 n 现在是 50。第一个线程读取 50，其他四个线程减去 9。第一个线程从它读取的 50 中减去 9并写入 41。所以当所有完成后，n 是 41.
所以，所谓不言自明的说法是完全错误的。写这篇文章的人不了解 C 中的线程。
if every thread writes a 1 then the final value cannot magically be something else
也是彻头彻尾的错误。考虑一个 CPU，它通过先写入 0 然后递增值来写入 1。如果这发生在两个内核上，最终结果可能是 2。这本教科书是由根本不了解线程和未定义行为的人编写的。
（我假设这本教科书不限于它所说的是真的某些特殊上下文。例如，它可能使用 "C-like" 代码作为平台中立的汇编语言的一种形式并且它可能会假设对齐整数具有特定保证的平台。但如果是这样，它所教的内容根本根本不会转化为 C 代码，并且只适用于编写汇编的人CPU 上的代码，其规则符合教科书的假设。）
假设每个线程都有一个本地 i（即，无论如何每个线程都会 运行 进行 5 次迭代），让我们尝试得到 1 作为结果。这意味着要写入值的 last 线程必须在其 5th 迭代中为 n 读取 0。发生这种情况的唯一方法是，如果在该线程的第 5 次迭代开始时还没有线程写入 n，但要使该线程处于第 5 次迭代，该线程本身必须写入 n , 因此这是不可能的。
因此最小的可能结果是2，这可能发生，例如，如下：最后一个写入n的线程已经完成4次迭代，然后另一个线程写入1，最后一个线程读取1在第 5 次迭代开始时，所有其他线程在最后一个线程之前完成所有迭代，最后最后一个线程完成其第 5 次迭代写入 2.
免责声明：我正在回答关于多线程的概念问题——正如其他人所指出的，缺乏原子性可能会导致未定义如果按原样使用提供的 C 代码，则行为和任意结果。基于问题的“不言而喻”的最大数案例，我猜测教科书的作者要么没有意识到这一点，要么正在使用类似 C 的伪代码来说明这个概念。如果是前者，那么正确答案就是书上写错了，但我觉得后一种情况下的答案也很有教育意义。