what is value of x for load and store

Question

This is some challenge

On a single processor system, in which load and store are assumed to be atomic, what are all the possible values for x after both threads have completed in the following execution, assuming that x is initialised to O? Hint: you need to consider how this code might be compiled into machine language.

for (int i = 0; i < 5; i++) : x = x + 1;

for (int j = 0; j < 5; j++) : x = x + 1;

Answer 1

well, most decent compilers will optimise that to x=10;

Answer 2

umm, 10. Enlighten me otherwise.

Answer 3

Each of the two lines in your question is meant to represent a separate thread. Since the shared variable x is not guarded, pretty much anything can happen. What are the possibilities you came up with? (otherwise I would feel like I'm just answering your problem for you)

SECOND HINT: Let a C compiler help you by showing you some examples...

int x;

void f(void)
{
  int i;
  for (i = 0; i < 5; i++)  x = x + 1;
}

(this is your program translated into C)

gcc -S -fno-PIC t.c 

(this is what I have to type on my machine to get readable assembly)

_f:
pushl   %ebp
movl    %esp, %ebp
subl    $24, %esp
movl    $0, -12(%ebp)
jmp L2
L3:
movl    _x, %eax
incl    %eax
movl    %eax, _x
leal    -12(%ebp), %eax
incl    (%eax)
L2:
cmpl    $4, -12(%ebp)
jle L3
leave
ret

Now with optimizations (adding option -O2 to the compilation):

_f:
movl    _x, %eax
xorl    %edx, %edx
pushl   %ebp
movl    %esp, %ebp
.align 4,0x90
L2:
incl    %edx
incl    %eax
cmpl    $5, %edx
jne L2
movl    %eax, _x
leave
ret

Answer 4

Hint: you don't need to consider all the possible sequences, you just need to consider the most extreme cases. What is the minimum value that x could possibly be ? And what is the maximum value that x could possibly be ?

The minimum case will occur when the loads for one thread always occur after a load and before a store in the other thread.

The maximum case will occur when there are no overlapping load-modify-store sequences.

That should be enough hints for you to work it out now.

Answer 5

Each thread will have 5 sets of the instructions:

LOAD X
INCREMENT X
STORE X

After each instruction the CPU can choose to yeild execution two another thread.

• The very higherest X can become is 10.This occurs when each thread finishes executing without yeilding to the other.
• The lowest I could see being is 5. This is when first load instruction occurs on both threads, then one finishes execution, then the other finishes.