OSTEP Note with xv6: Concurrency

lock_t mutex; // some globally-allocated lock ’mutex’
...
lock(&mutex);
balance = balance + 1;
unlock(&mutex);

struct lock{
    int locked;
}lock;

void init(struct lock *l){
    l->locked = 0;
}

void lock(struct lock *l){
    while (l->locked)
        ;
    l->locked = 1;
    return;
}

void unlock(struct lock *l){
    l->locked = 0;
}

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

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

void lock(lock_t *lock) {
    while (TestAndSet(&lock->flag, 1) == 1)
        ; // spin-wait (do nothing)
}
void lock(lock_t *lock) {
    while (CompareAndSwap(&lock->flag, 0, 1) == 1)
        ; // spin
}

int LoadLinked(int *ptr) {
    return *ptr;
}
int StoreConditional(int *ptr, int value) {
    if (no update to *ptr since LL to this addr) {
        *ptr = value;
        return 1; // success!
    } else {
        return 0; // failed to update
    }
}

void lock(lock_t *lock) {
    while (1) {
        while (LoadLinked(&lock->flag) == 1)
            ; // spin until it’s zero
        if (StoreConditional(&lock->flag, 1) == 1)
            return; // if set-to-1 was success: done
        // otherwise: try again
    }
}
void unlock(lock_t *lock) {
    lock->flag = 0;
}

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

typedef struct __lock_t {
    int ticket;
    int turn;
} lock_t;

void lock_init(lock_t *lock) {
    lock->ticket = 0;
    lock->turn = 0;
}
void lock(lock_t *lock) {
    int myturn = FetchAndAdd(&lock->ticket);
    while (lock->turn != myturn)
        ; // spin
}
void unlock(lock_t *lock) {
    lock->turn = lock->turn + 1;
}

struct spinlock {
  uint locked; // Is the lock held?

  // For debugging:
  char *name;      // Name of lock.
  struct cpu *cpu; // The cpu holding the lock.
};

void
initlock(struct spinlock *lk, char *name)
{
  lk->name = name;
  lk->locked = 0;
  lk->cpu = 0;
}

// Acquire the lock.
// Loops (spins) until the lock is acquired.
void
acquire(struct spinlock *lk)
{
  push_off(); // disable interrupts to avoid deadlock.
  if (holding(lk))
    panic("acquire");
  while (__atomic_exchange_n(&lk->locked, 1, __ATOMIC_ACQUIRE) != 0)
    ;
  lk->cpu = mycpu();
}

// Release the lock.
void
release(struct spinlock *lk)
{
  if (!holding(lk))
    panic("release");
  lk->cpu = 0;
  __atomic_store_n(&lk->locked, 0, __ATOMIC_RELEASE);
  pop_off();
}

int flag[2];
int turn;
void init() {
    // indicate you intend to hold the lock w/ ’flag’
    flag[0] = flag[1] = 0;
    // whose turn is it? (thread 0 or 1)
    turn = 0;
}
void lock() {
    // ’self’ is the thread ID of caller
    flag[self] = 1;
    // make it other thread’s turn
    turn = 1- self;
    while ((flag[1-self] == 1) && (turn == 1- self))
        ; // spin-wait while it’s not your turn
}
void unlock() {
    // simply undo your intent
    flag[self] = 0;
}

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

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)
        ; //acquire guard lock by spinning
    if (m->flag == 0) {
        m->flag = 1; // lock is acquired
        m->guard = 0;
    } else {
        queue_add(m->q, gettid());
        m->guard = 0;
        park();     // put a calling thread to sleep,
    }
}
void unlock(lock_t *m) {
    while (TestAndSet(&m->guard, 1) == 1)
        ; //acquire guard lock by spinning
    if (queue_empty(m->q))
        m->flag = 0; // let go of lock; no one wants it
    else    // wake a particular thread as designated by queue_remove(m->q)
        unpark(queue_remove(m->q)); // hold lock
                                    // (for next thread!)
    m->guard = 0;
}

void mutex_lock (int *mutex) {
    int v;
    // Bit 31 was clear, we got the mutex (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;
        }
        // Have to waitFirst to make sure futex value
        // we are monitoring is negative (locked).
        v = *mutex;
        if (v >= 0)
            continue;
        futex_wait (mutex, v);
    }
}
void mutex_unlock (int *mutex) {
    // Adding 0x80000000 to 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);
}

// Long-term locks for processes
struct sleeplock {
  uint locked;       // Is the lock held?
  struct spinlock lk; // spinlock protecting this sleep lock
  
  // For debugging:
  char *name;        // Name of lock.
  int pid;           // Process holding lock
};
void initsleeplock(struct sleeplock *lk, char *name) {
  initlock(&lk->lk, "sleep lock");  // locked=0, cpu=0, name="sleep lock"
  lk->name = name;
  lk->locked = 0;
  lk->pid = 0;
}

void acquiresleep(struct sleeplock *lk) {
  acquire(&lk->lk);
  while (lk->locked) {
    sleep(lk, &lk->lk); // 进程的chan成员设置成lk地址，并且释放自旋锁，获得进程锁，并进入睡眠
  }
  lk->locked = 1;
  lk->pid = myproc()->pid;
  release(&lk->lk);
}

void releasesleep(struct sleeplock *lk) {
  acquire(&lk->lk);
  lk->locked = 0;
  lk->pid = 0;
  wakeup(lk);       // 遍历进程数组，唤醒每一个chan成员为lk地址的进程
  release(&lk->lk);
}

int holdingsleep(struct sleeplock *lk) {
  int r;

  acquire(&lk->lk);
  r = lk->locked && (lk->pid == myproc()->pid); // 检查进程是否持有睡眠锁
  release(&lk->lk);
  return r;
}

// Atomically release lock and sleep on chan.
// Reacquires lock when awakened.
void sleep(void *chan, struct spinlock *lk) {
  struct proc *p = myproc();

  if (lk != &p->lock) {  // DOC: sleeplock0
    acquire(&p->lock);   // DOC: sleeplock1
    release(lk);
  }

  // Go to sleep.
  p->chan = chan;
  p->state = SLEEPING;

  sched();

  // Tidy up.
  p->chan = 0;

  // Reacquire original lock.
  if (lk != &p->lock) {
    release(&p->lock);
    acquire(lk);
  }
}

// Wake up all processes sleeping on chan.
// Must be called without any p->lock.
void wakeup(void *chan) {
  struct proc *p;

  for (p = proc; p < &proc[NPROC]; p++) {
    acquire(&p->lock);
    if (p->state == SLEEPING && p->chan == chan) {
      p->state = RUNNABLE;
    }
    release(&p->lock);
  }
}

typedef struct __counter_t {
    int value;
} counter_t;
void init(counter_t *c) {
    c->value = 0;
}
void increment(counter_t *c) {
    c->value++;
}
void decrement(counter_t *c) {
    c->value--;
}
int get(counter_t *c) {
    return c->value;
}

typedef struct __counter_t {
    int
    value;
    pthread_mutex_t lock;
} counter_t;
void init(counter_t *c) {
    c->value = 0;
    Pthread_mutex_init(&c->lock, NULL); // 这里 Pthread_mutex_init() 是 OSTEP 自己包装过的函数
}
void increment(counter_t *c) {
    Pthread_mutex_lock(&c->lock);
    c->value++;
    Pthread_mutex_unlock(&c->lock);
}
void decrement(counter_t *c) {
    Pthread_mutex_lock(&c->lock);
    c->value--;
    Pthread_mutex_unlock(&c->lock);
}
int get(counter_t *c) {
    Pthread_mutex_lock(&c->lock);
    int rc = c->value;
    Pthread_mutex_unlock(&c->lock);
    return rc;
}

void increment(counter_t *c, int threadID) {
    // pthread_mutex_lock(&c->llock[threadID]);
    c->local[threadID]++;
    if (c->local[threadID] >= c->threshold) {
        pthread_mutex_lock(&c->glock);
        c->global += c->local[threadID];
        pthread_mutex_unlock(&c->glock);
        c->local[threadID] = 0;
    }
    // pthread_mutex_unlock(&c->llock[threadID]);
}

typedef struct __node_t {
    int key;
    struct __node_t *next;
} node_t;

typedef struct __list_t {
    node_t *head;
    pthread_mutex_t llock;
} list_t;

void node_init(node_t *node, int key) {
    node->key = key;
    node->next = NULL;
}

void list_init(list_t *list) {
    list->head = NULL;
    pthread_mutex_init(&list->llock, NULL);
}

int list_insert(list_t *list, int key) {
    node_t *new = malloc(sizeof(node_t));
    if (new == NULL) {
        perror("malloc");
        return -1; // fail
    }
    node_init(new, key);
    pthread_mutex_lock(&list->llock);

    if (list->head == NULL) {
        list->head = new;
    } else {
        new->next = list->head;
        list->head = new;
    }
    pthread_mutex_unlock(&list->llock);

    return 0; // success
}

int list_lookup(list_t *list, int key) {
    int rv = -1;
    pthread_mutex_lock(&list->llock);
    node_t *curr = list->head;
    if (curr == NULL) {
        pthread_mutex_unlock(&list->llock);
        return rv;
    }
    while (curr->next) {
        if (curr->key == key) {
            rv = 0;
            break;
        }
        node_t *temp = curr;
        curr = curr->next;
    }
    if (curr != NULL && curr->key == key) {
        rv = 0;
    }
    pthread_mutex_unlock(&list->llock);
    return rv; // now both success and failure
}

typedef struct __node_t
{
    int key;
    struct __node_t *next;
    pthread_mutex_t lock;
} node_t;

typedef struct __list_t {
    node_t *head;
    pthread_mutex_t llock;
} list_t;

void node_init(node_t *node, int key) {
    node->key = key;
    node->next = NULL;
    pthread_mutex_init(&node->lock, NULL);
}

void list_init(list_t *list) {
    list->head = NULL;
    pthread_mutex_init(&list->llock, NULL);
}

int list_insert(list_t *list, int key) {
    node_t *new = malloc(sizeof(node_t));
    node_init(new, key);
    if (list->head == NULL)
        list->head = new;
    else {
        pthread_mutex_lock(&list->head->lock);
        new->next = list->head;
        list->head = new;
        pthread_mutex_unlock(&new->next->lock);
    }
    return 0; // success
}

int list_lookup(list_t *list, int key) {
    int rv = -1;
    node_t *curr = list->head;
    if (curr == NULL)
        return rv;
    pthread_mutex_lock(&curr->lock);
    while (curr->next) {
        if (curr->key == key) {
            rv = 0;
            break;
        }
        pthread_mutex_lock(&curr->next->lock);
        node_t *temp = curr;
        curr = curr->next;
        pthread_mutex_unlock(&temp->lock);
    }
    if (curr != NULL && curr->key == key) {
        rv = 0;
    }
    pthread_mutex_unlock(&curr->lock);
    return rv; // now both success and failure
}

void Queue_Enqueue(queue_t *q,intvalue){
    node_t *tmp= malloc(sizeof(node_t));
    assert(tmp!=NULL);
    tmp->value=value;
    tmp->next =NULL;

    pthread_mutex_lock(&q->tail_lock);
    q->tail->next=tmp;
    q->tail= tmp;
    pthread_mutex_unlock(&q->tail_lock);
}
int Queue_Dequeue(queue_t *q,int *value){
    pthread_mutex_lock(&q->head_lock);
    node_t *tmp= q->head;
    node_t *new_head= tmp->next;
    if (new_head==NULL){
        pthread_mutex_unlock(&q->head_lock);
        return -1;//queuewas empty
    }
    *value=new_head->value;
    q->head= new_head;
    pthread_mutex_unlock(&q->head_lock);
    free(tmp);
    return 0;
}

#define BUCKETS (101)
typedef struct __hash_t {
    list_t lists[BUCKETS];
} hash_t;
void Hash_Init(hash_t *H) {
    int i;
    for (i = 0; i < BUCKETS; i++)
    List_Init(&H->lists[i]);
}
int Hash_Insert(hash_t *H, int key) {
    return List_Insert(&H->lists[key % BUCKETS], key);
}
int Hash_Lookup(hash_t *H, int key) {
    return List_Lookup(&H->lists[key % BUCKETS], key);
}

volatile int done = 0;
void *child(void *arg) {
    printf("child\n");
    done = 1;
    return NULL;
}
int main(int argc, char *argv[]) {
    printf("parent: begin\n");
    pthread_t c;
    Pthread_create(&c, NULL, child, NULL); // child
    while (done == 0)
        ; // spin
    printf("parent: end\n");
    return 0;
}

int done = 0;
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t c = PTHREAD_COND_INITIALIZER;
void thr_exit() {
    Pthread_mutex_lock(&m);
    done = 1;
    Pthread_cond_signal(&c);
    Pthread_mutex_unlock(&m);
}
void *child(void *arg) {
    printf("child\n");
    thr_exit();
    return NULL;
}
void thr_join() {
    Pthread_mutex_lock(&m);
    while (done == 0)
        Pthread_cond_wait(&c, &m);
    Pthread_mutex_unlock(&m);
}
int main(int argc, char *argv[]) {
    printf("parent: begin\n");
    pthread_t p;
    Pthread_create(&p, NULL, child, NULL);
    thr_join();
    printf("parent: end\n");
    return 0;
}

void thr_exit(){
    done= 1;
    Pthread_cond_signal(&c);
}

void thr_join(){
    if (done==0)
        Pthread_cond_wait(&c);
}

int buffer;
int count = 0; // initially, empty
void put(int value) {
    assert(count == 0);
    count = 1;
    buffer = value;
}
int get() {
    assert(count == 1);
    count = 0;
    return buffer;
}
void *producer(void *arg) {
    int i;
    int loops = (int) arg;
    for (i = 0; i < loops; i++) {
        put(i);
}
}
void *consumer(void *arg) {
    while (1) {
        int tmp = get();
        printf("%d\n", tmp);
    }
}

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex);             // p1
        if (count == 1)                         // p2
            Pthread_cond_wait(&cond, &mutex);   // p3
        put(i);                                 // p4
        Pthread_cond_signal(&cond);             // p5
        Pthread_mutex_unlock(&mutex);           // p6
    }
}
void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex);             // c1
        if (count == 0)                         // c2
            Pthread_cond_wait(&cond, &mutex);   // c3
        int tmp = get();                        // c4
        Pthread_cond_signal(&cond);             // c5
        Pthread_mutex_unlock(&mutex);           // c6
        printf("%d\n", tmp);
    }
}

cond_t empty, fill;
mutex_t mutex;
void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex);             // p1
        while (count == 1)                      // p2
            Pthread_cond_wait(&cond, &mutex);   // p3
        put(i);                                 // p4
        Pthread_cond_signal(&cond);             // p5
        Pthread_mutex_unlock(&mutex);           // p6
    }
}
void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex);             // c1
        while (count == 0)                      // c2
            Pthread_cond_wait(&cond, &mutex);   // c3
        int tmp = get();                        // c4
        Pthread_cond_signal(&cond);             // c5
        Pthread_mutex_unlock(&mutex);           // c6
        printf("%d\n", tmp);
    }
}

int buffer[MAX];
int fill_ptr= 0;
int use_ptr = 0;
int count = 0;
void put(intvalue){
    buffer[fill_ptr]= value;
    fill_ptr= (fill_ptr+ 1)% MAX;
    count++;
}
int get(){
    int tmp= buffer[use_ptr];
    use_ptr= (use_ptr+1)% MAX;
    count--;
    return  tmp;
}
cond_t empty, fill;
mutex_t mutex;
void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex);             // p1
        while (count == MAX)                    // p2
            Pthread_cond_wait(&cond, &mutex);   // p3
        put(i);                                 // p4
        Pthread_cond_signal(&cond);             // p5
        Pthread_mutex_unlock(&mutex);           // p6
    }
}
void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex);             // c1
        while (count == 0)                      // c2
            Pthread_cond_wait(&cond, &mutex);   // c3
        int tmp = get();                        // c4
        Pthread_cond_signal(&cond);             // c5
        Pthread_mutex_unlock(&mutex);           // c6
        printf("%d\n", tmp);
    }
}

#include <semaphore.h>
int sem_init(sem_t *sem, int pshared, unsigned int value);
int sem_wait(sem_t *sem);       // 也被称为 P(), 源于荷兰语
int sem_post (sem_t *sem);      // 也被称为 V(), 源于荷兰语

int sem_init(sem_t *sem, int pshared, unsigned int value){
    // 将信号量的 value 初始化
    // pshared 参数决定信号量是在进程间共享还是仅限于当前进程的所有线程共享。
    // 当 pshared 的值为0时，信号量将被进程内的线程共享，否则，如果 pshared 是非零值，信号量将在进程之间共享。
}
int sem_wait(sem_t *s) {
    // 将信号量的 value 减一
    // 如果信号量的 value 小于0，wait
}
int sem_post(sem_t *s) {
    // 将信号量的 value 加一
    // 如果有线程正在等待，wake 其中一个
}

sem_t m;
// 0 indicates that the semaphore is shared between threads in the same process
sem_init(&m, 0, 1); // 信号量的 value 初始化为 1

sem_wait(&m);
// critical section here
sem_post(&m);

sem_t s;
void *child(void *arg) {
    printf("child\n");
    sem_post(&s); // signal here: child is done
    return NULL;
}
int main(int argc, char *argv[]) {
    sem_init(&s, 0, X); // what should X be?
    printf("parent: begin\n");
    pthread_t c;
    Pthread_create(&c, NULL, child, NULL);
    sem_wait(&s); // wait here for child
    printf("parent: end\n");
    return 0;
}

int buffer[MAX];
int fill = 0;
int use = 0;
void put(int value){
    buffer[fill] = value;       // Line F1
    fill = (fill + 1) & MAX;    // Line F2
}
int get(){
    int tmp = buffer[use];      // Line G1
    use = (use + 1) : MAX;      // Line G2
    return tmp;
}
sem_t empty;
sem_t full;
void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&empty);       // Line P1
        put(i);                 // Line P2
        sem_post(&full);        // Line P3
    }
}
void *consumer(void *arg) {
    int tmp = 0;
    while (tmp !=-1) {
        sem_wait(&full);        // Line C1
        tmp = get();            // Line C2
        sem_post(&empty);       // Line C3
        printf("%d\n", tmp);
    }
}
int main(int argc, char *argv[]) {
    // ...
    sem_init(&empty, 0, MAX); // MAX are empty
    sem_init(&full, 0, 0);
    // 0 are full
    // ...
}

sem_t empty;
sem_t full;
sem_t mutex;
void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&mutex);       // Line P0
        sem_wait(&empty);       // Line P1
        put(i);                 // Line P2
        sem_post(&full);        // Line P3
        sem_post(&mutex);       // Line P4
    }
}
void *consumer(void *arg) {
    int tmp = 0;
    while (tmp !=-1) {
        sem_wait(&mutex);       // Line C0
        sem_wait(&full);        // Line C1
        tmp = get();            // Line C2
        sem_post(&empty);       // Line C3
        sem_post(&mutex);       // Line C4
        printf("%d\n", tmp);
    }
}
int main(int argc, char *argv[]) {
    // ...
    sem_init(&mutex, 0, 1);
    sem_init(&empty, 0, MAX); // MAX are empty
    sem_init(&full, 0, 0);
    // 0 are full
    // ...
}

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&empty);       // Line P1
        sem_wait(&mutex);       // Line P1.5
        put(i);                 // Line P2
        sem_post(&mutex);       // Line P2.5
        sem_post(&full);        // Line P3
    }
}
void *consumer(void *arg) {
    int tmp = 0;
    while (tmp !=-1) {
        sem_wait(&full);        // Line C1
        sem_wait(&mutex);       // Line C1.5
        tmp = get();            // Line C2
        sem_post(&mutex);       // Line C2.5
        sem_post(&empty);       // Line C3
        printf("%d\n", tmp);
    }
}

typedef struct _rwlock_t {
    sem_t lock;         // binary semaphore (basic lock)
    sem_t writelock;    // allow ONE writer/MANY readers
    int readers;        // #readers in critical section
} rwlock_t;
void rwlock_init(rwlock_t *rw) {
    rw->readers = 0;
    sem_init(&rw->lock, 0, 1);
    sem_init(&rw->writelock, 0, 1);
}
void rwlock_acquire_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    rw->readers++;
    if (rw->readers == 1) // first reader gets writelock
    sem_wait(&rw->writelock);
    sem_post(&rw->lock);
}
void rwlock_release_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    rw->readers--;
    if (rw->readers == 0) // last reader lets it go
    sem_post(&rw->writelock);
    sem_post(&rw->lock);
}
void rwlock_acquire_writelock(rwlock_t *rw) {
    sem_wait(&rw->writelock);
}
void rwlock_release_writelock(rwlock_t *rw) {
    sem_post(&rw->writelock);
}

#include "common_threads.h" // OSTEP 提供的包装过的函数
typedef struct __rwlock_t {
    int reader_count;
    sem_t mutex;    // protect reader_count
    sem_t writelock;
    sem_t turnstile;
} rwlock_t;


void rwlock_init(rwlock_t *rw) {
    rw->reader_count = 0;
    Sem_init(&rw->mutex, 1);
    Sem_init(&rw->writelock, 1);
    Sem_init(&rw->turnstile, 1);
}

void rwlock_acquire_readlock(rwlock_t *rw) {
    Sem_wait(&rw->turnstile);
    Sem_post(&rw->turnstile);
    Sem_wait(&rw->mutex);
    if (rw->reader_count==0)
    Sem_wait(&rw->writelock);
    rw->reader_count++;
    Sem_post(&rw->mutex);
}

void rwlock_release_readlock(rwlock_t *rw) {
    Sem_wait(&rw->mutex);
    if (rw->reader_count==1)
    Sem_post(&rw->writelock);
    rw->reader_count--;
    Sem_post(&rw->mutex);
}

void rwlock_acquire_writelock(rwlock_t *rw) {
    Sem_wait(&rw->turnstile);
    Sem_wait(&rw->writelock);
}

void rwlock_release_writelock(rwlock_t *rw) {
    Sem_post(&rw->turnstile);
    Sem_post(&rw->writelock);
}

while(1){
    think();
    get_forks(p);
    eat();
    put_forks(p);
}

void get_forks(int p) {
    sem_wait(&forks[left(p)]);
    sem_wait(&forks[right(p)]);
}
void put_forks(int p) {
    sem_post(&forks[left(p)]);
    sem_post(&forks[right(p)]);
}

void get_forks(int p) {
    if (p == 4) {
        sem_wait(&forks[right(p)]);
        sem_wait(&forks[left(p)]);
    } else {
        sem_wait(&forks[left(p)]);
        sem_wait(&forks[right(p)]);
    }
}

F0(P0,P1) → P0
F1(P1,P2) → P1
F2(P2,P3) → P2
F3(P3,P4) → P3
F4(P4,P0) → P0

typedef struct __Zem_t {
int value;
pthread_cond_t cond;
pthread_mutex_t lock;
} Zem_t;
// only one thread can call this
void Zem_init(Zem_t *s, int value) {
    s->value = value;
    Cond_init(&s->cond);
    Mutex_init(&s->lock);
}
void Zem_wait(Zem_t *s) {
    Mutex_lock(&s->lock);
    while (s->value <= 0)
    Cond_wait(&s->cond, &s->lock);
    s->value--;
    Mutex_unlock(&s->lock);
}
void Zem_post(Zem_t *s) {
    Mutex_lock(&s->lock);
    s->value++;
    Cond_signal(&s->cond);
    Mutex_unlock(&s->lock);
}

#define BATCH_SIZE 5
typedef struct __ns_mutex_t
{
    sem_t resource_lock;
    sem_t queue_lock;
    sem_t count_lock;
    int full_flag;
    int count;
} ns_mutex_t;

void ns_mutex_init(ns_mutex_t *m) {
    Sem_init(&m->resource_lock, 1);
    Sem_init(&m->queue_lock, 1);
    Sem_init(&m->count_lock, 1);
    m->count = 0;
    m->full_flag = 0;
}

void ns_mutex_acquire(ns_mutex_t *m) {
    Sem_wait(&m->queue_lock);
    Sem_wait(&m->count_lock);
    m->count++;
    if (m->count < BATCH_SIZE) {
        Sem_post(&m->queue_lock);
    } else {
        m->full_flag = 1;   // 不释放 queue lock，后来的进程都会卡在 queue lock 获取上
        printf("Queue Full!\n");
    }
    Sem_post(&m->count_lock);
    Sem_wait(&m->resource_lock);
}
void ns_mutex_release(ns_mutex_t *m){
    Sem_wait(&m->count_lock);
    m->count--;
    if (m->count == 0 && m->full_flag) {
        Sem_post(&m->queue_lock);
        m->full_flag = 0;
    }
    Sem_post(&m->resource_lock);
    Sem_post(&m->count_lock);
}

semaphore mutex = 1
semaphore t1 = 1
semaphore t2 = 0

int room1 = 0
int room2 = 0

acquire(){
    wait(mutex) // 直接进入 room1
    room1++
    signal(mutex)

    wait(t1)    // 尝试进入 room2
    room2++
    wait(mutex)
        room1-- // 转移到 room2
        if room1 == 0
            signal(mutex)
            signal(t2)  // room1 已经空了，临界区开一个口
        else
            signal(mutex)
            signal(t1)  // 继续放行 room1 的线程进入 room2
    wait(t2)            // 尝试进入临界区
    room2--
}

release(){
    if room2 == 0
        signal(t1)  // room2 空了，room2 放一个线程进来
    else
        signal(t2)  // room2 不是空的，临界区放一个线程进来
}

Thread 1::
if (thd->proc_info) {
    fputs(thd->proc_info, ...);
}

Thread 2::
thd->proc_info = NULL;

pthread_mutex_t proc_info_lock = PTHREAD_MUTEX_INITIALIZER;
Thread 1::
pthread_mutex_lock(&proc_info_lock);
if (thd->proc_info) {
    fputs(thd->proc_info, ...);
}
pthread_mutex_unlock(&proc_info_lock);

Thread 2::
pthread_mutex_lock(&proc_info_lock);
thd->proc_info = NULL;
pthread_mutex_unlock(&proc_info_lock);

Thread 1::
void init() {
    mThread = PR_CreateThread(mMain, ...);
}
Thread 2::
void mMain(...) {
    mState = mThread->State;
}

pthread_mutex_t mtLock  = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t mtCond   = PTHREAD_COND_INITIALIZER;
int mtInit              = 0;
Thread 1::
void init() {
    ...
    mThread = PR_CreateThread(mMain, ...);
    // signal that the thread has been created...
    pthread_mutex_lock(&mtLock);
    mtInit = 1;
    pthread_cond_signal(&mtCond);
    pthread_mutex_unlock(&mtLock);
    ...
}
Thread 2::
void mMain(...) {
    ...
    // wait for the thread to be initialized...
    pthread_mutex_lock(&mtLock);
    while (mtInit == 0)
        pthread_cond_wait(&mtCond, &mtLock);
    pthread_mutex_unlock(&mtLock);
    mState = mThread->State;
...
}

Thread 1:
pthread_mutex_lock(L1);
pthread_mutex_lock(L2);

Thread 2:
pthread_mutex_lock(L2);
pthread_mutex_lock(L1);

Thread 1:
vector_add(&v[0], &v[1]);

Thread 2:
vector_add(&v[1], &v[0]);

void vector_add(vector_t *v_dst, vector_t *v_src) {
    Pthread_mutex_lock(&v_dst->lock);
    Pthread_mutex_lock(&v_src->lock);
    int i;
    for (i = 0; i < VECTOR_SIZE; i++)
        v_dst->values[i] = v_dst->values[i] + v_src->values[i];
    Pthread_mutex_unlock(&v_dst->lock);
    Pthread_mutex_unlock(&v_src->lock);
}

pthread_mutex_lock(prevention); // begin acquisition
pthread_mutex_lock(L1);
pthread_mutex_lock(L2);
...
pthread_mutex_unlock(prevention); // end

top:
    pthread_mutex_lock(L1);
    if (pthread_mutex_trylock(L2) != 0) {
        pthread_mutex_unlock(L1);
        goto top;
    }

lock(L1);
do_something();

if (trylock(L2)失败) {
    // 撤销 do_something() 的影响
    // 释放所有资源
    // 回到起点
}

int CompareAndSwap(int *address, int expected, int new) {
    if (*address == expected) {
        *address = new;
        return 1; // success
    }
    return 0; // failure
}

void AtomicIncrement(int *value, int amount) {
    do {
        int old = *value;
    } while (CompareAndSwap(value, old, old + amount) == 0)
        ;
}

void insert(int value) {
    node_t *n = malloc(sizeof(node_t));
    assert(n != NULL);
    n->value = value;
    pthread_mutex_lock(listlock); // begin critical section
    n->next = head;
    head = n;
    pthread_mutex_unlock(listlock); // end critical section
}

void insert(int value) {
    node_t *n = malloc(sizeof(node_t));
    assert(n != NULL);
    n->value = value;
    do {
        n->next = head;
    } while (CompareAndSwap(&head, n->next, n) == 0);
}

          Pi 请求 Request
                 │
                 ↓
       Request ≤ Need ?
          │             │
         否             是
          ↓             ↓
        拒绝      Request ≤ Available ?
                         │
                    ┌────┴────┐
                   否         是
                   ↓           ↓
                  等待     假设分配
                              │
                              ↓
                         安全性算法
                              │
                    ┌─────────┴─────────┐
                   安全                 不安全
                    ↓                     ↓
                  分配                   回滚

while (1) {
    events = getEvents();
    for (e in events)
        processEvent(e);
}

int select(int nfds,
           fd_set *restrict readfds,
           fd_set *restrict writefds,
           fd_set *restrict errorfds,
           struct timeval *restrict timeout);

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <sys/types.h>
#include <unistd.h>
int main(void) {
    // open and set up a bunch of sockets (not shown)
    // main loop
    while (1) {
        // initialize the fd_set to all zero
        fd_set readFDs;
        FD_ZERO(&readFDs);
        // now set the bits for the descriptors
        // this server is interested in
        // (for simplicity, all of them from min to max)
        int fd;
        for (fd = minFD; fd < maxFD; fd++)
            FD_SET(fd, &readFDs);
        // do the select
        int rc = select(maxFD+1, &readFDs, NULL, NULL, NULL);
        // check which actually have data using FD_ISSET()
        int fd;
        for (fd = minFD; fd < maxFD; fd++)
            if (FD_ISSET(fd, &readFDs))
        processFD(fd);
    }
}

struct aiocb {
    int             aio_fildes; // File descriptor
    off_t           aio_offset; // File offset
    volatile void   *aio_buf;   // Location of buffer
    size_t          aio_nbytes; // Length of transfer
};

int aio_read(struct aiocb *aiocbp);

int aio_error(const struct aiocb *aiocbp);

void handle(int arg) {
    printf("stop wakin’ me up...\n");
}
int main(int argc, char *argv[]) {
    signal(SIGHUP, handle);
    while (1)
        ; // doin’ nothin’ except catchin’ some sigs
    return 0;
}

int rc = read(fd, buffer, size);
rc = write(sd, buffer, size);

                 ┌── 网络 socket
                 │
                 ↓
             select()
                 │
                 ↓
          网络 I/O 就绪
                 
                 +
                 
                 ┌── 磁盘文件
                 │
                 ↓
              AIO API
                 │
                 ↓
          磁盘 I/O 完成

#include <pthread.h>
// thread: 即将被初始化的线程
// attr:   指定这个线程初始化的参数，一般传 NULL 使用默认参数即可
// start_routine: 线程入口的函数指针，返回类型和参数类型都是 void*
// arg:    传入函数的参数
int pthread_create(pthread_t            *thread,
                   const pthread_attr_t *attr,
                   void                 *(*start_routine)(void*),
                   void                 *arg);

#include <stdio.h>
#include <pthread.h>
typedef struct {
    int a;
    int b;
} myarg_t;
void *mythread(void *arg) {
    myarg_t *args = (myarg_t *) arg;
    printf("%d %d\n", args->a, args->b);
    return NULL;
}
int main(int argc, char *argv[]) {
    pthread_t p;
    myarg_t args = { 10, 20 };
    int rc = pthread_create(&p, NULL, mythread, &args);
    ...
}

int pthread_join(pthread_t thread, void **value_ptr);

typedef struct { int a; int b; } myarg_t;
typedef struct { int x; int y; } myret_t;
void *mythread(void *arg) {
    myret_t *rvals = Malloc(sizeof(myret_t));   // Wrapped malloc
    rvals->x = 1;
    rvals->y = 2;
    return (void *) rvals;
}
int main(int argc, char *argv[]) {
    pthread_t p;
    myret_t *rvals;
    myarg_t args = { 10, 20 };
    Pthread_create(&p, NULL, mythread, &args);
    Pthread_join(p, (void **) &rvals);
    printf("returned %d %d\n", rvals->x, rvals->y);
    free(rvals);
    return 0;
}

void *mythread(void *arg) {
    long long int value = (long long int) arg;
    printf("%lld\n", value);
    return (void *) (value + 1);
}
int main(int argc, char *argv[]) {
    pthread_t p;
    long long int rvalue;
    Pthread_create(&p, NULL, mythread, (void *) 100);
    Pthread_join(p, (void **) &rvalue);
    printf("returned %lld\n", rvalue);
    return 0;
}

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; // or whatever your critical section is
pthread_mutex_unlock(&lock);

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

int rc = pthread_mutex_init(&lock, NULL);
assert(rc == 0); // always check success!

pthread_mutex_destroy()

pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);
int pthread_cond_signal(pthread_cond_t *cond);

// 其中一个线程
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
Pthread_mutex_lock(&lock);
while (ready == 0)
    Pthread_cond_wait(&cond, &lock);
Pthread_mutex_unlock(&lock);

// 另一个线程
Pthread_mutex_lock(&lock);
ready = 1;
Pthread_cond_signal(&cond);
Pthread_mutex_unlock(&lock);