Determine the proper lower hound and upper hound on the fina

Determine the proper lower hound and upper hound on the final value of the shared variable tally output by this concurrent program Assume processes can execute at any relative speed that a value can only he incremented after it has been loaded into a register by a separate machine instruction More specifically the increment operation is actually composed of 3 separate machine instructions, a load from memory, an add, then a store back to memory The casual quirk answer most people intuitively think of first for this problem has a subtle problem and is incorrect. Suppose that an arbitrary number of these processes are permitted to execute in parallel under the assumptions of part what effect will this modification have on the range of final values of tally?

Solution

On casual inspection, it appears that tally will fall in the range of 50<=tally<=100 since from 0 to 50 increments could go unrecorded due to the lack of mutual exclusion. on running the two processes concrrently, we shouldnot be able to derive a result lower than result produced by executed by just onw of these processes sequentially . The logic is quite clear.

but , consider the sequence of load, increment and store operations performed by these two rpocesses when altering the value of the shared variable,

1)Process A loads the value of tally ,increments tally, but then looses the processor ,it has incremented accumulator ro 1 but not yet stored the value

2)Process B loads the value of tally(still 0) , performs complete 49 increment operations, losing the processor after it has stored the value 49 into shared variable tally

3)Process A regains it control to perform its first store operation ,replacing tally value if 49 with 1 , but it then immediately has to give control of the processor to B

4)The process B resumes long enough to load 1 into its accumulator ,then it is als oforces to give up the processor

5)Process A is rescheduled, now it is not interrupted and it tends to completion (since B has its final load done) performings the remaining 49 load , increment and store operations , making value of tally to be 50

6)Process B is reactivated with only one increment and store operation left ,it increments accumulator to 2 , stores this value as final value of the shared variable .

All the values in range 2 to 49 are likewise potential results

The interleaved sequences cause process B to loose processor after completing 50-k incremental cycles .

so 1<=k<=48 are the upper and lower bounds of k