OSTEP

1
2
3
4
5
6
7

int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);

pthread_mutex_t lock;
pthread_mutex_lock(&lock);
x=x+1;
pthread_mutex_lock(&lock);

1
2

int rc = pthread_mutex_init(&lock,NULL);
assert(rc==0);

1
2

int pthread_mutex_trylock(pthread_mutex_t *mutex);
int pthread_mutex_timedlock(pthread_mutex_t *mutex, struct timespec *abs_timeout);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int flag[2];
int turn;
void init() {
    flag[0] = flag[1] = 0; turn = 0;
}
void lock() {
    flag[self] = 1;
    turn = 1 - self;
    while ((flag[1-self] == 1) && (turn == 1 - self))
    ; // spin-wait
}
void unlock() {
    flag[self] = 0; // simply undo your intent 
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

bool flag[2] = {false, false};
int turn;

P0:      flag[0] = true;
P0_gate: turn = 1;
         while (flag[1] == true && turn == 1)
         {
             // busy wait
         }
         // critical section
         ...
         // end of critical section
         flag[0] = false;

P1:      flag[1] = true;
P1_gate: turn = 0;
         while (flag[0] == true && turn == 0)
         {
             // busy wait
         }
         // critical section
         ...
         // end of critical section
         flag[1] = false;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

int TestAndSet(int *old_ptr, int new) {
    int old = *old_ptr; // fetch old value at old_ptr
    *old_ptr = new; // store 'new' into old_ptr
    return old; // return the old value
}

typedef struct lock_t {
    int flag;
} lock_t;

void init(lock_t *lock) {
    // 0 indicates that lock is available, 1 that it is held lock->flag = 0;
}
void lock(lock_t *lock) {
    while (TestAndSet(&lock->flag, 1) == 1)
    ; // spin-wait (do nothing)
}
void unlock(lock_t *lock) {
    lock->flag = 0;
}

1
2
3
4
5
6

int CompareAndSwap(int *ptr, int expected, int new) {
    int actual = *ptr;
    if (actual == expected)
        *ptr = new;
    return actual;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

int LoadLinked(int *ptr) {
    return *ptr;
}
int StoreConditional(int *ptr, int value) {
    if (no one has updated *ptr since the LoadLinked to this address) {
        *ptr = value;
        return 1; // succes
    } else {
        return 0; // failed to update
    }
}

void lock(lock_t *lock){
    while(1){
        while(LoadLinked(&lock->flag) == 1){
            ;
        }
        if(StoredConditional(&lock->flag,1)==1){
            return;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

int FetchAndAdd(int *ptr){
    int old = *ptr;
    *ptr = old + 1;
    return old;
}

typedef struct lock_t {
    int ticket;
    lock->turn;
} lock_t;

void lock(lock_t *lock){
    int myturn = FetchAndAdd(&lock->ticket);
    while(lock->turn != myturn){
        ;
    }
}

void unlock(lock_t *lock){
    FetchAndAdd(&lock->turn);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void init(){
    flag = 0;
}

void lock(){
    while(TestAndSet(&flag,1)==1){
        yield(); // give up CPU
    }
}

void unlock(){
    flag = 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

typedef struct lock_t{
    int flag;
    int guard;
    queue_t *q;
} lock_t;   

void lock_init(lock_t *m){
    m->flag = 0;
    m->guard = 0;
    queue_init(m->q);
}

void lock(lock_t *m){
    while(TestAndSet(&m->guard,1) == 1){
        ;
    }
    if(m->flag == 0){
        m->flag = 1;
        m->guard = 0;
    }
    else{
        queue_add(m->q,gettid());
        m->guard = 0;
        park();
    }
}

void unlock(lock_t *m){
    while(TestAndSet(&m->guard,1) == 1){
        ;
    }
    if(queue_empty(m->q){
        m->flag = 0;
    }
    else{
        unpark(queue_remove(m->q));
    }
    m->guard = 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

void mutex_lock (int *mutex) {
    int v;
    /* Bit 31 was clear, we got the mutex (this is the fastpath) */
    if (atomic_bit_test_set (mutex, 31) == 0)
        return;
    atomic_increment (mutex);
    while (1) {
        if (atomic_bit_test_set (mutex, 31) == 0) {
            atomic_decrement (mutex);
            return;
        }
        /* We have to wait now. First make sure the futex value we are monitoring is truly negative (i.e. locked). */
        v = *mutex;
        if (v >= 0) continue;
        futex_wait (mutex, v);
    }
}

void mutex_unlock (int *mutex) {
    /* Adding 0x80000000 to the counter results in 0 if and only if
        there are not other interested threads */
    if (atomic_add_zero (mutex, 0x80000000))
        return;
    /* There are other threads waiting for this mutex, wake one of them up. */
    futex_wake (mutex);
}