开发者

what is value of x for load and store [closed]

开发者 https://www.devze.com 2022-12-28 15:17 出处:网络
It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical andcannot be reasonably answered in its current form. For help clari
It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 10 years ago. 开发者_如何学C

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;


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


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.


Each thread will have 5 sets of the instructions:

LOAD X
INCREMENT X
STORE X

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

  • The very higherest X can become is 10.This occurs when each thread finishes executing without yielding 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.


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


umm, 10. Enlighten me otherwise.

0

精彩评论

暂无评论...
验证码 换一张
取 消