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.
精彩评论