Overview¶
Welcome to this simulator! The idea is to gain familiarity with threads by
seeing how they interleave; the simulator, x86.py, will help you in
gaining this understanding.
The simulator mimicks the execution of short assembly sequences by multiple threads. Note that the OS code that would run (for example, to perform a context switch) is not shown; thus, all you see is the interleaving of the user code.
The assembly code that is run is based on x86, but somewhat
simplified. In this instruction set, there are four general-purpose
registers (%ax, %bx, %cx, %dx), a program counter (PC), and a small
set of instructions which will be enough for our purposes. We’ve also
added a few extra GP registers (%ex, %fx) which don’t quite match
anything in x86 (but that is OK, isn’t it?).
Here is an example code snippet that we will be able to run:
.main
mov 2000, %ax # get the value at the address
add $1, %ax # increment it
mov %ax, 2000 # store it back
halt
The code is easy to understand. The first instruction, an x86 “mov”, simply loads a value from the address specified by 2000 into the register %ax. Addresses, in this subset of x86, can take some of the following forms:
2000: the number (2000) is the address(%cx): contents of register (in parentheses) forms the address1000(%dx): the number + contents of the register form the address10(%ax,%bx): the number + reg1 + reg2 form the address10(%ax,%bx,4): -> the number + reg1 + (reg2*scaling) form the address
To store a value, the same mov instruction is used, but this time with the
arguments reversed, e.g.:
mov %ax, 2000
The add instruction, from the sequence above, should be clear: it
adds an immediate value (specified by $1) to the register specified in
the second argument (i.e., %ax = %ax + 1).
Thus, we now can understand the code sequence above: it loads the value at address 2000, adds 1 to it, and then stores the value back into address 2000.
The fake-ish halt instruction just stops running this thread.
Let’s run the simulator and see how this all works! Assume the above code
sequence is in the file simple-race.s.
prompt> ./x86.py -p simple-race.s -t 1
Thread 0
1000 mov 2000, %ax
1001 add $1, %ax
1002 mov %ax, 2000
1003 halt
prompt>
The arguments used here specify the program (-p), the number of
threads (-t 1), and the interrupt interval, which is how often a
scheduler will be woken and run to switch to a different task. Because
there is only one thread in this example, this interval does not
matter.
The output is easy to read: the simulator prints the program counter (here shown from 1000 to 1003) and the instruction that gets executed. Note that we assume (unrealistically) that all instructions just take up a single byte in memory; in x86, instructions are variable-sized and would take up from one to a small number of bytes.
We can use more detailed tracing to get a better sense of how machine state changes during the execution:
prompt> ./x86.py -p simple-race.s -t 1 -M 2000 -R ax,bx
2000 ax bx Thread 0
? ? ?
? ? ? 1000 mov 2000, %ax
? ? ? 1001 add $1, %ax
? ? ? 1002 mov %ax, 2000
? ? ? 1003 halt
Oops! Forgot the -c flag (which actually computes the answers for you).
prompt> ./x86.py -p simple-race.s -t 1 -M 2000 -R ax,bx -c
2000 ax bx Thread 0
0 0 0
0 0 0 1000 mov 2000, %ax
0 1 0 1001 add $1, %ax
1 1 0 1002 mov %ax, 2000
1 1 0 1003 halt
By using the -M flag, we can trace memory locations (a comma-separated list
lets you trace more than one, e.g., 2000,3000); by using the -R flag we can
track the values inside specific registers.
The values on the left show the memory/register contents AFTER the instruction
on the right has executed. For example, after the add instruction, you can
see that %ax has been incremented to the value 1; after the second mov
instruction (at PC=1002), you can see that the memory contents at 2000 are
now also incremented.
There are a few more instructions you’ll need to know, so let’s get to them now. Here is a code snippet of a loop:
.main
.top
sub $1,%dx
test $0,%dx
jgte .top
halt
```sh
A few things have been introduced here. First is the `test` instruction.
This instruction takes two arguments and compares them; it then sets implicit
"condition codes" (kind of like 1-bit registers) which subsequent instructions
can act upon.
In this case, the other new instruction is the `jump` instruction (in this
case, `jgte` which stands for "jump if greater than or equal to"). This
instruction jumps if the second value is greater than or equal to the first
in the test.
One last point: to really make this code work, dx must be initialized to 1 or
greater.
Thus, we run the program like this:
```sh
prompt> ./x86.py -p loop.s -t 1 -a dx=3 -R dx -C -c
dx >= > <= < != == Thread 0
3 0 0 0 0 0 0
2 0 0 0 0 0 0 1000 sub $1,%dx
2 1 1 0 0 1 0 1001 test $0,%dx
2 1 1 0 0 1 0 1002 jgte .top
1 1 1 0 0 1 0 1000 sub $1,%dx
1 1 1 0 0 1 0 1001 test $0,%dx
1 1 1 0 0 1 0 1002 jgte .top
0 1 1 0 0 1 0 1000 sub $1,%dx
0 1 0 1 0 0 1 1001 test $0,%dx
0 1 0 1 0 0 1 1002 jgte .top
0 1 0 1 0 0 1 1003 halt
The -R dx flag traces the value of %dx; the -C flag traces the values of
the condition codes that get set by a test instruction. Finally, the -a dx=3
flag sets the %dx register to the value 3 to start with.
As you can see from the trace, the sub instruction slowly lowers the value
of %dx. The first few times test is called, only the “>=”, “>”, and “!=”
conditions get set. However, the last test in the trace finds %dx and 0 to
be equal, and thus the subsequent jump does NOT take place, and the program
finally halts.
Now, finally, we get to a more interesting case, i.e., a race condition with multiple threads. Let’s look at the code first:
.main
.top
# critical section
mov 2000, %ax # get the value at the address
add $1, %ax # increment it
mov %ax, 2000 # store it back
# see if we're still looping
sub $1, %bx
test $0, %bx
jgt .top
halt
The code has a critical section which loads the value of a variable (at address 2000), then adds 1 to the value, then stores it back.
The code after just decrements a loop counter (in %bx), tests if it
is greater than or equal to zero, and if so, jumps back to the top
to the critical section again.
prompt> ./x86.py -p looping-race-nolock.s -t 2 -a bx=1 -M 2000 -c
2000 bx Thread 0 Thread 1
0 1
0 1 1000 mov 2000, %ax
0 1 1001 add $1, %ax
1 1 1002 mov %ax, 2000
1 0 1003 sub $1, %bx
1 0 1004 test $0, %bx
1 0 1005 jgt .top
1 0 1006 halt
1 1 ----- Halt;Switch ----- ----- Halt;Switch -----
1 1 1000 mov 2000, %ax
1 1 1001 add $1, %ax
2 1 1002 mov %ax, 2000
2 0 1003 sub $1, %bx
2 0 1004 test $0, %bx
2 0 1005 jgt .top
2 0 1006 halt
Here you can see each thread ran once, and each updated the shared variable at address 2000 once, thus resulting in a count of two there.
The Halt;Switch line is inserted whenever a thread halts and another
thread must be run.
One last example: run the same thing above, but with a smaller interrupt frequency. Here is what that will look like:
[mac Race-Analyze] ./x86.py -p looping-race-nolock.s -t 2 -a bx=1 -M 2000 -i 2
2000 Thread 0 Thread 1
?
? 1000 mov 2000, %ax
? 1001 add $1, %ax
? ------ Interrupt ------ ------ Interrupt ------
? 1000 mov 2000, %ax
? 1001 add $1, %ax
? ------ Interrupt ------ ------ Interrupt ------
? 1002 mov %ax, 2000
? 1003 sub $1, %bx
? ------ Interrupt ------ ------ Interrupt ------
? 1002 mov %ax, 2000
? 1003 sub $1, %bx
? ------ Interrupt ------ ------ Interrupt ------
? 1004 test $0, %bx
? 1005 jgt .top
? ------ Interrupt ------ ------ Interrupt ------
? 1004 test $0, %bx
? 1005 jgt .top
? ------ Interrupt ------ ------ Interrupt ------
? 1006 halt
? ----- Halt;Switch ----- ----- Halt;Switch -----
? 1006 halt
As you can see, each thread is interrupt every 2 instructions, as we specify
via the -i 2 flag. What is the value of memory[2000] throughout this run?
What should it have been?
Now let’s give a little more information on what can be simulated
with this program. The full set of registers: %ax, %bx, %cx, %dx, %ex, %fx
and the PC and a stack pointer %sp.
The full set of instructions simulated are:
mov immediate, register # moves immediate value to register
mov memory, register # loads from memory into register
mov register, register # moves value from one register to other
mov register, memory # stores register contents in memory
mov immediate, memory # stores immediate value in memory
add immediate, register # register = register + immediate
add register1, register2 # register2 = register2 + register1
sub immediate, register # register = register - immediate
sub register1, register2 # register2 = register2 - register1
neg register # negates contents of register
test immediate, register # compare immediate and register (set condition codes)
test register, immediate # same but register and immediate
test register, register # same but register and register
jne # jump if test'd values are not equal
je # ... equal
jlt # ... second is less than first
jlte # ... less than or equal
jgt # ... is greater than
jgte # ... greater than or equal
push memory or register # push value in memory or from reg onto stack
# stack is defined by sp register
pop [register] # pop value off stack (into optional register)
call label # call function at label
xchg register, memory # atomic exchange:
# put value of register into memory
# return old contents of memory into reg
# do both things atomically
yield # switch to the next thread in the runqueue
nop # no op
Notes:
- ‘immediate’ is something of the form $number
- ‘memory’ is of the form ‘number’ or ‘(reg)’ or ‘number(reg)’ or
‘number(reg,reg)’ or ‘number(reg,reg,scale)’ (as described above)
- ‘register’ is one of %ax, %bx, %cx, %dx, %ex, %fx, %sp
Finally, here are the full set of options to the simulator are available with
the -h flag:
prompt> ./x86.py -h
Usage: x86.py [options]
Options:
-s SEED, --seed=SEED the random seed
-t NUMTHREADS, --threads=NUMTHREADS
number of threads
-p PROGFILE, --program=PROGFILE
source program (in .s)
-i INTFREQ, --interrupt=INTFREQ
interrupt frequency
-P PROCSCHED, --procsched=PROCSCHED
control exactly which thread runs when
-r, --randints if interrupts are random
-a ARGV, --argv=ARGV comma-separated per-thread args (e.g., ax=1,ax=2 sets
thread 0 ax reg to 1 and thread 1 ax reg to 2);
specify multiple regs per thread via colon-separated
list (e.g., ax=1:bx=2,cx=3 sets thread 0 ax and bx and
just cx for thread 1)
-L LOADADDR, --loadaddr=LOADADDR
address where to load code
-m MEMSIZE, --memsize=MEMSIZE
size of address space (KB)
-M MEMTRACE, --memtrace=MEMTRACE
comma-separated list of addrs to trace (e.g.,
20000,20001)
-R REGTRACE, --regtrace=REGTRACE
comma-separated list of regs to trace (e.g.,
ax,bx,cx,dx)
-C, --cctrace should we trace condition codes
-S, --printstats print some extra stats
-v, --verbose print some extra info
-H HEADERCOUNT, --headercount=HEADERCOUNT
how often to print a row header
-c, --compute compute answers for me
Most are obvious. Usage of -r turns on a random interrupter (from 1 to intfreq
as specified by -i), which can make for more fun during homework problems.
-Plets you specify exactly which threads run when; e.g., 11000 would run thread 1 for 2 instructions, then thread 0 for 3, then repeat-Lspecifies where in the address space to load the code.-mspecified the size of the address space (in KB).-Sprints some extra stats-clets you see the values of the traced registers or memory values (otherwise they show up as question marks)-Hlets you specify how often to print a row header (useful for long traces)
Now you have the basics in place; read the questions at the end of the chapter to study this race condition and related issues in more depth.