1. Locks
-
mutex = mutual exclusion, only one thread can hold the lock at any time
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER; ... Pthread_mutex_lock(&lock); // wrapper; exits on failure balance = balance + 1; Pthread_mutex_unlock(&lock);
How to implement?Issues: Correctness (even on multiprocessors), Performance (time overhead), Fairness (no starve)
2. Simple Flag
-
Assume flag=0 to begin: 
Correct: no
3. Test-and-Set
-
Hardware test-and-set instruction (atomic exchange):
int TestAndSet(int *ptr, int new);
returns the old value and simultaneously updates to the new value.
Correct: yes; Performance: bad (spinning); Fairness: no
Fix performance --> yield; Fix fairness --> queue
4. Other Hardware Primitives
-
Compare-and-swap:
int CompareAndSwap(int *ptr, int expected, int new);
returns the old value and simultaneously updates to the new value if old == expected.
Fetch-and-add:int FetchAndAdd(int *ptr);
returns the old value and simultaneously adds 1 and stores the new value.Can be used to implement ticket lock and ensure fairness.
5. Exercises
-
See the book for exercises using x86.py
$ cat flag.s .var flag .var count .main .top .acquire mov flag, %ax # get flag test $0, %ax # if we get 0 back: lock is free! jne .acquire # if not, try again mov $1, flag # store 1 into flag # critical section mov count, %ax # get the value at the address add $1, %ax # increment it mov %ax, count # store it back # release lock mov $0, flag # clear the flag now # see if we're still looping sub $1, %bx test $0, %bx jgt .top halt
6. Q2
-
$ python ./x86.py -p flag.s -R ax,bx -a bx=2 -M flag,count -c flag count ax bx Thread 0 Thread 1 0 0 0 2 0 0 0 2 1000 mov flag, %ax 0 0 0 2 1001 test $0, %ax 0 0 0 2 1002 jne .acquire 1 0 0 2 1003 mov $1, flag 1 0 0 2 1004 mov count, %ax 1 0 1 2 1005 add $1, %ax 1 1 1 2 1006 mov %ax, count 0 1 1 2 1007 mov $0, flag 0 1 1 1 1008 sub $1, %bx 0 1 1 1 1009 test $0, %bx 0 1 1 1 1010 jgt .top 0 1 0 1 1000 mov flag, %ax 0 1 0 1 1001 test $0, %ax 0 1 0 1 1002 jne .acquire 1 1 0 1 1003 mov $1, flag 1 1 1 1 1004 mov count, %ax 1 1 2 1 1005 add $1, %ax 1 2 2 1 1006 mov %ax, count 0 2 2 1 1007 mov $0, flag 0 2 2 0 1008 sub $1, %bx 0 2 2 0 1009 test $0, %bx 0 2 2 0 1010 jgt .top 0 2 2 0 1011 halt 0 2 0 2 ----- Halt;Switch ----- ----- Halt;Switch ----- 0 2 0 2 1000 mov flag, %ax 0 2 0 2 1001 test $0, %ax 0 2 0 2 1002 jne .acquire 1 2 0 2 1003 mov $1, flag 1 2 2 2 1004 mov count, %ax 1 2 3 2 1005 add $1, %ax 1 3 3 2 1006 mov %ax, count 0 3 3 2 1007 mov $0, flag 0 3 3 1 1008 sub $1, %bx 0 3 3 1 1009 test $0, %bx 0 3 3 1 1010 jgt .top 0 3 0 1 1000 mov flag, %ax 0 3 0 1 1001 test $0, %ax 0 3 0 1 1002 jne .acquire 1 3 0 1 1003 mov $1, flag 1 3 3 1 1004 mov count, %ax 1 3 4 1 1005 add $1, %ax 1 4 4 1 1006 mov %ax, count 0 4 4 1 1007 mov $0, flag 0 4 4 0 1008 sub $1, %bx 0 4 4 0 1009 test $0, %bx 0 4 4 0 1010 jgt .top 0 4 4 0 1011 halt
7. Q4
-
$ python ./x86.py -p flag.s -R ax,bx -a bx=2 -M flag,count -c -i 6 flag count ax bx Thread 0 Thread 1 0 0 0 2 0 0 0 2 1000 mov flag, %ax 0 0 0 2 1001 test $0, %ax 0 0 0 2 1002 jne .acquire 1 0 0 2 1003 mov $1, flag 1 0 0 2 1004 mov count, %ax 1 0 1 2 1005 add $1, %ax 1 0 0 2 ------ Interrupt ------ ------ Interrupt ------ 1 0 1 2 1000 mov flag, %ax 1 0 1 2 1001 test $0, %ax 1 0 1 2 1002 jne .acquire 1 0 1 2 1000 mov flag, %ax 1 0 1 2 1001 test $0, %ax 1 0 1 2 1002 jne .acquire 1 0 1 2 ------ Interrupt ------ ------ Interrupt ------ 1 1 1 2 1006 mov %ax, count 0 1 1 2 1007 mov $0, flag 0 1 1 1 1008 sub $1, %bx 0 1 1 1 1009 test $0, %bx 0 1 1 1 1010 jgt .top 0 1 0 1 1000 mov flag, %ax 0 1 1 2 ------ Interrupt ------ ------ Interrupt ------ 0 1 0 2 1000 mov flag, %ax 0 1 0 2 1001 test $0, %ax 0 1 0 2 1002 jne .acquire 1 1 0 2 1003 mov $1, flag 1 1 1 2 1004 mov count, %ax 1 1 2 2 1005 add $1, %ax 1 1 0 1 ------ Interrupt ------ ------ Interrupt ------flag count ax bx Thread 0 Thread 1 1 1 0 1 1001 test $0, %ax 1 1 0 1 1002 jne .acquire 1 1 0 1 1003 mov $1, flag 1 1 1 1 1004 mov count, %ax 1 1 2 1 1005 add $1, %ax 1 2 2 1 1006 mov %ax, count 1 2 2 2 ------ Interrupt ------ ------ Interrupt ------ 1 2 2 2 1006 mov %ax, count 0 2 2 2 1007 mov $0, flag 0 2 2 1 1008 sub $1, %bx 0 2 2 1 1009 test $0, %bx 0 2 2 1 1010 jgt .top 0 2 0 1 1000 mov flag, %ax 0 2 2 1 ------ Interrupt ------ ------ Interrupt ------ 0 2 2 1 1007 mov $0, flag 0 2 2 0 1008 sub $1, %bx 0 2 2 0 1009 test $0, %bx 0 2 2 0 1010 jgt .top 0 2 2 0 1011 halt 0 2 0 1 ----- Halt;Switch ----- ----- Halt;Switch ----- 0 2 0 1 1001 test $0, %ax 0 2 0 1 ------ Interrupt ------ ------ Interrupt ------ 0 2 0 1 1002 jne .acquire 1 2 0 1 1003 mov $1, flag 1 2 2 1 1004 mov count, %ax 1 2 3 1 1005 add $1, %ax 1 3 3 1 1006 mov %ax, count 0 3 3 1 1007 mov $0, flag 0 3 3 1 ------ Interrupt ------ ------ Interrupt ------ 0 3 3 0 1008 sub $1, %bx 0 3 3 0 1009 test $0, %bx 0 3 3 0 1010 jgt .top 0 3 3 0 1011 halt
8. Q5
-
$ cat test-and-set.s .var mutex .var count .main .top .acquire mov $1, %ax xchg %ax, mutex # atomic swap of 1 and mutex test $0, %ax # if we get 0 back: lock is free! jne .acquire # if not, try again # critical section mov count, %ax # get the value at the address add $1, %ax # increment it mov %ax, count # store it back # release lock mov $0, mutex # see if we're still looping sub $1, %bx test $0, %bx jgt .top halt
9. Q6
-
$ python ./x86.py -p test-and-set.s -R ax,bx -a bx=2 -M mutex,count -c -i 6 mutex count ax bx Thread 0 Thread 1 0 0 0 2 0 0 1 2 1000 mov $1, %ax 1 0 0 2 1001 xchg %ax, mutex 1 0 0 2 1002 test $0, %ax 1 0 0 2 1003 jne .acquire 1 0 0 2 1004 mov count, %ax 1 0 1 2 1005 add $1, %ax 1 0 0 2 ------ Interrupt ------ ------ Interrupt ------ 1 0 1 2 1000 mov $1, %ax 1 0 1 2 1001 xchg %ax, mutex 1 0 1 2 1002 test $0, %ax 1 0 1 2 1003 jne .acquire 1 0 1 2 1000 mov $1, %ax 1 0 1 2 1001 xchg %ax, mutex 1 0 1 2 ------ Interrupt ------ ------ Interrupt ------ 1 1 1 2 1006 mov %ax, count 0 1 1 2 1007 mov $0, mutex 0 1 1 1 1008 sub $1, %bx 0 1 1 1 1009 test $0, %bx 0 1 1 1 1010 jgt .top 0 1 1 1 1000 mov $1, %ax 0 1 1 2 ------ Interrupt ------ ------ Interrupt ------ 0 1 1 2 1002 test $0, %ax 0 1 1 2 1003 jne .acquire 0 1 1 2 1000 mov $1, %ax 1 1 0 2 1001 xchg %ax, mutex 1 1 0 2 1002 test $0, %ax 1 1 0 2 1003 jne .acquire 1 1 1 1 ------ Interrupt ------ ------ Interrupt ------ 1 1 1 1 1001 xchg %ax, mutex 1 1 1 1 1002 test $0, %ax 1 1 1 1 1003 jne .acquire 1 1 1 1 1000 mov $1, %ax 1 1 1 1 1001 xchg %ax, mutex 1 1 1 1 1002 test $0, %ax 1 1 0 2 ------ Interrupt ------ ------ Interrupt ------mutex count ax bx Thread 0 Thread 1 1 1 1 2 1004 mov count, %ax 1 1 2 2 1005 add $1, %ax 1 2 2 2 1006 mov %ax, count 0 2 2 2 1007 mov $0, mutex 0 2 2 1 1008 sub $1, %bx 0 2 2 1 1009 test $0, %bx 0 2 1 1 ------ Interrupt ------ ------ Interrupt ------ 0 2 1 1 1003 jne .acquire 0 2 1 1 1000 mov $1, %ax 1 2 0 1 1001 xchg %ax, mutex 1 2 0 1 1002 test $0, %ax 1 2 0 1 1003 jne .acquire 1 2 2 1 1004 mov count, %ax 1 2 2 1 ------ Interrupt ------ ------ Interrupt ------ 1 2 2 1 1010 jgt .top 1 2 1 1 1000 mov $1, %ax 1 2 1 1 1001 xchg %ax, mutex 1 2 1 1 1002 test $0, %ax 1 2 1 1 1003 jne .acquire 1 2 1 1 1000 mov $1, %ax 1 2 2 1 ------ Interrupt ------ ------ Interrupt ------ 1 2 3 1 1005 add $1, %ax 1 3 3 1 1006 mov %ax, count 0 3 3 1 1007 mov $0, mutex 0 3 3 0 1008 sub $1, %bx 0 3 3 0 1009 test $0, %bx 0 3 3 0 1010 jgt .top 0 3 1 1 ------ Interrupt ------ ------ Interrupt ------ 1 3 0 1 1001 xchg %ax, mutex 1 3 0 1 1002 test $0, %ax 1 3 0 1 1003 jne .acquire 1 3 3 1 1004 mov count, %ax 1 3 4 1 1005 add $1, %ax 1 4 4 1 1006 mov %ax, count 1 4 3 0 ------ Interrupt ------ ------ Interrupt ------ 1 4 3 0 1011 halt 1 4 4 1 ----- Halt;Switch ----- ----- Halt;Switch ----- 0 4 4 1 1007 mov $0, mutex 0 4 4 0 1008 sub $1, %bx 0 4 4 0 1009 test $0, %bx 0 4 4 0 1010 jgt .top 0 4 4 0 1011 halt