多线程访问一个变量 [英] Multiple threads accessing one variable

问题描述

我正在阅读的教科书中发现了这个问题.解决方案也在下面给出.我无法理解最小值可能是2的原因.为什么一个线程不能读取0，所有其他线程都执行并且写入1?而无论是1还是2，最后写入的线程仍必须完成自己的循环吗?

I found this question in a textbook I am reading. The solution is given below it as well. I'm having trouble understanding how the minimum could be 2. Why couldn't a thread read 0, all other threads execute and it writes 1? And whether it is 1 or 2, the thread writing last must still complete its own loop?

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;
}

如果单个线程运行了此应用程序，则您将期望最终 输出为5.如果5个线程并行运行同一循环怎么办?什么 n可以具有的最大值和最小值?最大的应该 不言而喻:25，从5个线程开始以5为增量.然而， 关于最小可能值的推理更加困难.提示:n 可以小于5，但是由您自己确定原因.

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.

解决方案:

有五个线程运行此五迭代循环，而没有 保护并发访问，n可以达到的最小值 是两个.工作时最容易了解如何达到此结果 从最终结果倒退.为了使最终输出为两个， 线程必须已经从n读取了一个值1，对其进行了递增，然后 写两个.这意味着另一个线程写了一个，暗示 它最初也读取零(这也是n的起始值). 这说明了五个线程中两个线程的行为.然而， 为了使此行为发生，其他三个线程的结果必须 已被覆盖.两个有效的执行可以完成此任务. 1)所有三个线程都开始并完成了两个线程之间的执行 第一个线程读取零并写入一个，或者2)所有三个线程 在最终线程读取一个和之间开始并完成执行 写两个.两种执行顺序均有效.

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.

推荐答案

假设每个线程都有一个本地i(即，每个线程无论如何都将运行5次迭代)，让我们尝试获得1作为结果.这意味着 last 线程要写入值，必须在第5 次迭代中为n读取0.发生这种情况的唯一方法是，如果该线程的第5次迭代开始时尚未将任何线程写入n，但要使该线程处于其第5次迭代，该线程本身必须已写入n，因此它是不可能.

Assuming every thread has a local i (i.e., every thread will run for 5 iterations no matter what), let's try to get 1 as the result. This would mean the last thread to write a value would have to read 0 for n on its 5th iteration. The only way this could happen is if no thread has yet written to n at the start of that thread's 5th iteration, yet for that thread to be on its 5th iteration that thread itself must have written to n, hence it is not possible.

因此，可能的最小结果是2，它可能会发生，例如，如下所示:最后一个写入n的线程已完成4次迭代，然后另一个线程写入了1，最后一个线程在其开始处读取了1.第5次迭代，所有其他线程在最后一个线程之前完成所有迭代，最后最后一个线程完成第5次迭代，写入2.

Thus the smallest possible result is 2, which can occur, e.g., as follows: the last thread to write n has completed 4 iterations, then another thread writes 1, the last thread reads the 1 at the start of its 5th iteration, all other threads complete all their iterations before the last thread, and finally the last thread completes its 5th iteration writing the 2.

免责声明:我正在回答关于多线程的概念问题-正如其他人所指出的那样，如果没有C语言，缺乏原子性可能会导致不确定的行为和任意结果提出的按原样使用.基于问题的不言而喻"最大案例，我猜测教科书的作者可能没有意识到这一点，或者正在使用类似C的伪代码来说明这一概念.如果是前者，那么正确的答案将是该书是错误的，但我认为后者的答案也是有教育意义的.

Disclaimer: I am answering the conceptual question about multithreading – as others have pointed out, the lack of atomicity might lead to undefined behaviour and arbitrary results if the C code presented were used as is. Based on the question's "self-evident" largest number case I'm guessing the textbook's author either doesn't realise this, or is using a C-like pseudo code to illustrate the concept. If the former, then the correct answer would be that the book is wrong, but I think the answer in the latter case is also educational.

这篇关于多线程访问一个变量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！