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

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Why $10$ for the maximum and $1$ for the minimum ? Explain your reasoning. $\endgroup$ Commented 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$ Commented Oct 23, 2022 at 17:16
  • $\begingroup$ What about $1$ ? $\endgroup$ Commented Oct 23, 2022 at 18:35

3 Answers 3

Reset to default
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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Truly appreciate your answer! Thank you! $\endgroup$ Commented 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$.

Improve this answer
$\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$.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.