What does it mean that a value can only be incremented after it's been loaded into a register?

Consider the following program:

const int n = 50;
int tally;

void total() {
  int count;
  for (count = 1; count <= n; count++){
    tally++;
  }
}

void main() {
  tally = 0;
  parbegin (total (), total ());
  write (tally);
}

-
Determine the proper lower bound and upper bound on the final value of the
shared variable tally output by this concurrent program.Assume processes can execute
at any relative speed and that a value can only be incremented after it has
been loaded into a register by a separate machine instruction.

-
Suppose that an arbitrary number of these processes are permitted to execute in
parallel under the assumptions of part (a).What effect will this modification have
on the range of final values of tally?


My problem is that I don't understand the question what does this mean ?


... and that a value can only be incremented after it has been loaded into a register by a separate machine instruction.

I feel that when two processes execute simultaneously due to this assumption some value of tally will be lost but I don't know how it can happen because I don't know what this assumption means so I can't find lower bound!it is obvious that if 2 or n process execute one after the other tally will be 100 hence 100 = (number of process *50) is upper bound!

Here are some more concepts to help with this.

CPUs use load and store instructions to execute the high level language concept of tally++;. This is not atomic, unlike atomic CPU operations such as read-modify-write.

This question is alluding to the fact that there is no atomicity and that the common set of instructions can be executed in any interleaving by the $n$ processes.

The "lost update" concept is the enemy here. Wikipedia's "Concurrency control" article talks about this but mostly in a database transaction sense. Nevertheless it is absolutely the same high level concept of:

• Thread1 reads tally into register (likely the ALU) (observes 6)

• Thread2 reads tally (observes 6)

• Thread1 increments ALU (now is 7)

• Thread2 increments ALU (now is 7)

• Thread1 writes ALU to tally memory (value stored is 7)

• Thread2 writes ALU to tally memory (value stored is 7)

So BOTH threads/processes/whatever have "incremented" tally but the shared memory value of tally is ONLY 1 larger than when it started. Thread2's write to memory caused a lost update; Thread1's write was "lost".

By setting the question to say that there are at least three instructions required to increment (i.e. tally++;) the asker is saying that it is entirely possible that lost updates can occur due to interleaving of the instructions by multiple processes and causing lost updates.

I'd say the lower bound of tally is 50 (maximum destructive interleavings occur).
Upper bound is 50 * numProcesses (where no unscrupulous interleavings of the increment code occur).

Concepts to look up are:

• Shared memory concurrency/parallel

• Atomic and non-atomic instructions like load store and read modify write

• Interleaving of instructions

• Lost update

StackExchange Computer Science Q#24255, answer score: 2