0
$\begingroup$

I'm studying for an exam and have run into a problem that I do not understand. The main program starts two threads that execute the following program concurrently, whenever both threads terminate the program will print the result of counter. I am assuming that the maximum value of counter will be 10? But what will the minimum value be? 1?

The following image shows the pseudocode for the program.

enter image description here

$\endgroup$
3
  • 1
    $\begingroup$ Why $10$ for the maximum and $1$ for the minimum ? Explain your reasoning. $\endgroup$ Oct 23, 2022 at 15:57
  • $\begingroup$ Well my thought is that the continuation of the while-loop is dependent on the value of i, but i is only effected by itself and not by any variable that is local to the threads themselves (in the way that counter is dependent on the value of cnt). So in that way the program will only ever loop 10 times, limiting the value of counter. But maybe I am thinking completely wrong. $\endgroup$ Oct 23, 2022 at 17:16
  • $\begingroup$ What about $1$ ? $\endgroup$ Oct 23, 2022 at 18:35

3 Answers 3

1
$\begingroup$

First of all, lets clarify the functional difference between

i = i+1

and

cnt = counter
counter = cnt+1

There is none! Both segments must first read a value from global memory into a register, operate on/with said register and write the result back to global memory. So both execute three instructions; a read, an add, and a write.

With that said, the rest of the problem is an exercise of arranging blocks in a way that one thread "undoes" the work of the other, either for i or for counter.

For the minimum value of counter, see the execution flow below. The grey box represents a single iteration of the loop. The value of counter, after both threads finish, will be 1. enter image description here

For the maximum value of coutner, see the execution flow below. Again, the grey boxes represent a single iteration of the loops. If all iterations are executed with the alignment shown, at the end, counter will be 20. enter image description here

$\endgroup$
1
  • $\begingroup$ Truly appreciate your answer! Thank you! $\endgroup$ Oct 23, 2022 at 19:10
1
$\begingroup$

While I was initialy convinced by the two previous answers, a colleague of mine showed me the light about this exercise.

He claims that the maximum value of the counter is $65$, not $20$.

As proof, consider the following execution :

  • Thread $t$ reads $i = 0$; counter = 0
  • Thread $u$ executes $10$ loops in total; counter = 10
  • Thread $t$ writes $i = 1$;
  • Thread $u$ enters the loop and reads $i = 1$;
  • Thread $t$ executes $10$ loops in total; counter = 20
  • Thread $u$ writes $i = 2$;
  • Thread $t$ enters the loop and reads $i = 2$;
  • Thread $u$ executes $9$ loops in total; counter = 29
  • Thread $t$ writes $i = 3$;
  • Thread $t$ writes $i = 9$;
  • Thread $u$ enters the loop and reads $i = 9$;
  • Thread $t$ executes $2$ loops in total; counter = 64
  • Thread $u$ writes $i = 10$;
  • Thread $u$ finishes the loop; counter = 65
  • Both tests $i < 10$ are false and both threads exit.

The value $65$ is $10 +10 + 9 + 8 + … + 2 +1$.

$\endgroup$
0
$\begingroup$

The minimum cannot be $0$, because $\text{cnt}\ge0$, and some assignment $\text{counter}=\text{cnt}+1$ will inevitably be performed.

But the minimum can be $1$, as follows:

  • the left process executes with $i=0$, until the assignment $\text{cnt = counter;}$ (hence $\text{i}==1$ and $\text{cnt}==0$).

  • the right process executes all iterations with $i= 1, \cdots9$ and exits.

  • the left process finishes processing and performs the assigment $\text{counter = 0 + 1;}$ and terminates.

Then, unless the incrementation of $i$ is done atomically, the maximum is $20$, as follows:

  • both processes execute the $\text{while}$ test and the RHS of the assignment $\cdots=\text i+1$.

  • both processes perform the LHS of the assignment, $\text i=\cdots$.

  • both processes execute the rest of the loop without overlap.

This way, both loops run $10$ times, for a total of $20$.

If the incrementation is atomic, the maximum is $10$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.