I'm writing to ask about this question from 'The Little Book of Semaphores' by Allen B. Downey.

Question from 'The Little Book of Semaphores'

Puzzle: Suppose that 100 threads run the following program concurrently. (if you are not familiar with Python, the for loop runs the update 100 times.):

for i in range(100):
   temp = count
   count = temp   1

What is the largest possible value of count after all threads have completed? What is the smallest possible value? Hint: the first question is easy; the second is not.

My understanding is that count is a variable shared by all threads, and that it's initial value is 0. I believe that the largest possible value is 10,000, which occurs when there is no interleaving between threads.

I believe that the smallest possible value is 100. If line 2 is executed for each thread, they will each have a value of temp = 0. If line 3 is then executed for each thread, they will each set count = 1. If the same behaviour occurs in each iteration, the final value of count will be 100.

Is this correct, or is there another execution path that can result in a value smaller than 100 for count?

CodePudding user response：

The worst case that I can think of will leave count equal to two. It's extremely unlikely that this would ever happen in practice, but in theory, it's possible. I'll need to talk about Thread A, Thread B, and 98 other threads:

1. Thread A reads count as zero, but then it is preempted before it can do anything else,
2. Thread B is allowed to run 99 iterations of its loop, and 98 other threads all run to completion before thread A finally is allowed to run again,
3. Thread A writes 1 to count before—are you ready to believe this?—it gets preempted again!
4. Thread B starts its 100th iteration. It gets as far as reading count as 1 (just now written by thread A) before thread A finally comes roaring back to life and runs to completion,
5. Thread B is last to cross the finish line after it writes 2 to count.