OSTEP:26 Concurrency:An Introduction Homework

bxz

2023-04-15

OSTEP

临界区（critical section）是访问共享资源的一段代码，资源通常是一个变量或数据结构
竞态条件（race condition）出现在多个执行线程大致同时进入临界区时，它们都试图更新共享的数据结构

没有共享变量，哪来的竞态条件

grxer@grxer ~/D/s/O/o/threads-intro> cat looping-race-nolock.s
# assumes %bx has loop count in it

.main
.top
# critical section
mov 2000, %ax  # get 'value' at address 2000
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
grxer@grxer ~/D/s/O/o/threads-intro> python ./x86.py -p looping-race-nolock.s -t 2 -M 2000  -i 4 -r -s 0 -c
ARG seed 0
ARG numthreads 2
ARG program looping-race-nolock.s
ARG interrupt frequency 4
ARG interrupt randomness True
ARG argv
ARG load address 1000
ARG memsize 128
ARG memtrace 2000
ARG regtrace
ARG cctrace False
ARG printstats False
ARG verbose False

 2000          Thread 0                Thread 1
    0
    0   1000 mov 2000, %ax
    0   1001 add $1, %ax
    1   1002 mov %ax, 2000
    1   1003 sub  $1, %bx
    1   ------ Interrupt ------  ------ Interrupt ------
    1                            1000 mov 2000, %ax
    1                            1001 add $1, %ax
    2                            1002 mov %ax, 2000
    2                            1003 sub  $1, %bx
    2   ------ Interrupt ------  ------ Interrupt ------
    2   1004 test $0, %bx
    2   1005 jgt .top
    2   ------ Interrupt ------  ------ Interrupt ------
    2                            1004 test $0, %bx
    2                            1005 jgt .top
    2   ------ Interrupt ------  ------ Interrupt ------
    2   1006 halt
    2   ----- Halt;Switch -----  ----- Halt;Switch -----
    2                            1006 halt
grxer@grxer ~/D/s/O/o/threads-intro> python ./x86.py -p looping-race-nolock.s -t 2 -M 2000  -i 4 -r -s 1 -c
ARG seed 1
ARG numthreads 2
ARG program looping-race-nolock.s
ARG interrupt frequency 4
ARG interrupt randomness True
ARG argv
ARG load address 1000
ARG memsize 128
ARG memtrace 2000
ARG regtrace
ARG cctrace False
ARG printstats False
ARG verbose False

 2000          Thread 0                Thread 1
    0
    0   1000 mov 2000, %ax
    0   ------ Interrupt ------  ------ Interrupt ------
    0                            1000 mov 2000, %ax
    0                            1001 add $1, %ax
    1                            1002 mov %ax, 2000
    1                            1003 sub  $1, %bx
    1   ------ Interrupt ------  ------ Interrupt ------
    1   1001 add $1, %ax
    1   1002 mov %ax, 2000
    1   1003 sub  $1, %bx
    1   1004 test $0, %bx
    1   ------ Interrupt ------  ------ Interrupt ------
    1                            1004 test $0, %bx
    1                            1005 jgt .top
    1   ------ Interrupt ------  ------ Interrupt ------
    1   1005 jgt .top
    1   1006 halt
    1   ----- Halt;Switch -----  ----- Halt;Switch -----
    1   ------ Interrupt ------  ------ Interrupt ------
    1                            1006 halt
grxer@grxer ~/D/s/O/o/threads-intro> python ./x86.py -p looping-race-nolock.s -t 2 -M 2000  -i 4 -r -s 2 -c
ARG seed 2
ARG numthreads 2
ARG program looping-race-nolock.s
ARG interrupt frequency 4
ARG interrupt randomness True
ARG argv
ARG load address 1000
ARG memsize 128
ARG memtrace 2000
ARG regtrace
ARG cctrace False
ARG printstats False
ARG verbose False

 2000          Thread 0                Thread 1
    0
    0   1000 mov 2000, %ax
    0   1001 add $1, %ax
    1   1002 mov %ax, 2000
    1   1003 sub  $1, %bx
    1   ------ Interrupt ------  ------ Interrupt ------
    1                            1000 mov 2000, %ax
    1                            1001 add $1, %ax
    2                            1002 mov %ax, 2000
    2                            1003 sub  $1, %bx
    2   ------ Interrupt ------  ------ Interrupt ------
    2   1004 test $0, %bx
    2   ------ Interrupt ------  ------ Interrupt ------
    2                            1004 test $0, %bx
    2   ------ Interrupt ------  ------ Interrupt ------
    2   1005 jgt .top
    2   1006 halt
    2   ----- Halt;Switch -----  ----- Halt;Switch -----
    2                            1005 jgt .top
    2                            1006 halt

不在临界区之间发生中断就可以的到正确结果

可想而知，只有-i 3及更大可以避开竞态区

围绕着不在临界区发生中断来

-i 大于597(执行100次共600条指令，后面三条和竞态没关系)或者是3的倍数就可以

grxer@grxer ~/D/s/O/o/threads-intro> cat wait-for-me.s
.main
test $1, %ax     # ax should be 1 (signaller) or 0 (waiter)
je .signaller

.waiter
mov  2000, %cx
test $1, %cx
jne .waiter
halt

.signaller
mov  $1, 2000
halt

grxer@grxer ~/D/s/O/o/threads-intro> python ./x86.py -p wait-for-me.s -a ax=1,ax=0 -R ax,cx -M 2000 -c
ARG seed 0
ARG numthreads 2
ARG program wait-for-me.s
ARG interrupt frequency 50
ARG interrupt randomness False
ARG argv ax=1,ax=0
ARG load address 1000
ARG memsize 128
ARG memtrace 2000
ARG regtrace ax,cx
ARG cctrace False
ARG printstats False
ARG verbose False

 2000      ax    cx          Thread 0                Thread 1
    0       1     0
    0       1     0   1000 test $1, %ax
    0       1     0   1001 je .signaller
    1       1     0   1006 mov  $1, 2000
    1       1     0   1007 halt
    1       0     0   ----- Halt;Switch -----  ----- Halt;Switch -----
    1       0     0                            1000 test $1, %ax
    1       0     0                            1001 je .signaller
    1       0     1                            1002 mov  2000, %cx
    1       0     1                            1003 test $1, %cx
    1       0     1                            1004 jne .waiter
    1       0     1                            1005 halt

相当于交换线程，在线程0等待到中断后线程1把eax设为1，之前都在做无用循环

0       0     0   1002 mov  2000, %cx
 0       0     0   1003 test $1, %cx
 0       1     0   ------ Interrupt ------  ------ Interrupt ------
 0       1     0                            1000 test $1, %ax