3
$\begingroup$

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

  1. 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.

  2. 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!

$\endgroup$
3
  • $\begingroup$ It means the compiler is decomposing the ++ operator into multiple instructions. First tally gets loaded into a local processor register, then the register gets incremented, eventually the value gets stored back to memory. It is unspecified in this problem what exactly the compiler did. It might be storing the value of the register back into the memory location for tally after each iteration of the loop, or it might just be doing the store once, after all 50 increments have occurred. It's also unspecified whether each process reads tally from memory once or 50 times. $\endgroup$
    – Wandering Logic
    Apr 30, 2014 at 15:58
  • $\begingroup$ @WanderingLogic Convert comment into an answer? $\endgroup$
    – Yuval Filmus
    Apr 30, 2014 at 18:13
  • $\begingroup$ Thanks every one for comments,helps and raphael's edit. @wanderingLogic :I understand you made it clear for me !we should consider every possibility in these concurrent execution because of this it doesn't make it clear ! $\endgroup$
    – haleh
    Apr 30, 2014 at 19:26

3 Answers 3

Reset to default
2
$\begingroup$

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
$\endgroup$
2
  • $\begingroup$ It might also be worth noting that read-modify-write instructions (like x86's ADD when using a destination operand in memory) are generally atomic with respect to interrupts but not with respect to cache coherence (for x86 the LOCK prefix is required for the other sense of atomic). For threads time sliced on a single hardware thread, interrupt atomic is sufficient. $\endgroup$
    – Paul A. Clayton
    May 3, 2014 at 13:35
  • $\begingroup$ I think it is possible to get tally==2 by the following: T0 and T1 both load 0, T0 is interrupted, T1 increments to 49 and stores 49, T0 resumes and stores 1, T1 loads 1, T1 is interrupted, T0 increments to 50, T1 resumes performing its final increment and stores 2. $\endgroup$
    – Paul A. Clayton
    May 3, 2014 at 13:59
1
$\begingroup$

All operations are done in the CPU, the value is read from memory, incremented, and written back. This is so even in machines with "increment memory" instructions.

$\endgroup$
1
  • $\begingroup$ First, the question is obviously concerned with atomic w.r.t. interrupts (e.g., the case where thread 0 loads tally==0, takes an interrupt, thread 1 increments 50 times, thread 0 restarts and increments 50 times so tally=50 at the end) and w.r.t. other processors. I.e., it is implying that increment is not atomic in either sense. Second, it is quite possible to implement operations like Fetch-and-Add in the interconnect fabric or even the memory controller (to avoid cache line ownership transfer overhead, cache line ping-pong in this case). $\endgroup$
    – Paul A. Clayton
    May 1, 2014 at 13:15
0
$\begingroup$

if we suppose the processes P1 and P2,at first P1 executes. it increments tally to 1 but before it loads it to memory,it lose the processor,then P2 is processing and after 49 iteration it makes tally to 49 and stores it then it lose processor and again P1 is processing and store 1 to tally then lose processor and P2 load 1 to register and lose processor, P1 increment tally to 1+49 = 50(within 49 iteration) and tally = 50 ,then lose processor ,P2 increment the register which was 1 and loads 2 to tally and now it is complete and tally = 2 ; so answer is : 

1.  2 <= tally <= 100
2.  2 <= tally <= 2*numbers of process

.

$\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.