信号量

1
2
3

#include <semaphore.h>
sem_t s;
sem_init(&s, 0, 1);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int sem_wait(sem_t *s) {
    // Decrement the value of semaphore s by one
    // If the value becomes negative, the calling thread will block until it becomes positive
    // Once the value becomes positive, the thread will continue
}

int sem_post(sem_t *s) {
    // Increment the value of semaphore s by one
    // If there are one or more threads waiting (i.e., the semaphore was previously negative),
    // wake one of the waiting threads
}

1
2
3
4
5
6

sem_t m;
sem_init(&m, 0, X); // Initialize semaphore to X; what should X be?

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

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

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;
}

1
2
3

parent: begin
child
parent: end

 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
40
41
42
43

int buffer[MAX];
int fill = 0;
int use = 0;

void put(int value) {
    buffer[fill] = value;        // Line F1: Place value in the buffer at the current fill index
    fill = (fill + 1) % MAX;     // Line F2: Move the fill index to the next position in a circular buffer
}

int get() {
    int tmp = buffer[use];       // Line G1: Retrieve the value from the buffer at the current use index
    use = (use + 1) % MAX;       // Line G2: Move the use index to the next position in a circular buffer
    return tmp;                  // Return the retrieved value
}

sem_t empty;
sem_t full;

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&empty);        // Line P1: Wait for at least one empty buffer slot
        put(i);                  // Line P2: Produce an item and place it in the buffer
        sem_post(&full);         // Line P3: Signal that a buffer slot has been filled
    }
}

void *consumer(void *arg) {
    int i, tmp = 0;
    while (tmp != -1) {
        sem_wait(&full);         // Line C1: Wait for at least one filled buffer slot
        tmp = get();             // Line C2: Consume an item from the buffer
        sem_post(&empty);        // Line C3: Signal that a buffer slot has been emptied
        printf("%d\n", tmp);
    }
}

int main(int argc, char *argv[]) {
    // ...
    sem_init(&empty, 0, MAX);    // MAX buffers are empty to begin with...
    sem_init(&full, 0, 0);       // ... and 0 are full
    // ...
}

 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

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 (NEW LINE)
        sem_wait(&empty); // Line P1
        put(i); // Line P2
        sem_post(&full); // Line P3
        sem_post(&mutex); // Line P4 (NEW LINE)
    }
}

void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&mutex); // Line C0 (NEW LINE)
        sem_wait(&full); // Line C1
        int tmp = get(); // Line C2
        sem_post(&empty); // Line C3
        sem_post(&mutex); // Line C4 (NEW LINE)
        printf("%d\n", tmp);
    }
}

int main(int argc, char *argv[]) {
    // ...
    sem_init(&empty, 0, MAX); // MAX buffers are empty to begin with...
    sem_init(&full, 0, 0); // ... and 0 are full
    sem_init(&mutex, 0, 1); // mutex=1 because it is a lock (NEW LINE)
    // ...
}

 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

sem_t empty;
sem_t full;
sem_t mutex;

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&empty); // Line P1
        sem_wait(&mutex); // Line P1.5 (MOVED MUTEX HERE...)
        put(i); // Line P2
        sem_post(&mutex); // Line P2.5 (... AND HERE)
        sem_post(&full); // Line P3
    }
}

void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&full); // Line C1
        sem_wait(&mutex); // Line C1.5 (MOVED MUTEX HERE...)
        int tmp = get(); // Line C2
        sem_post(&mutex); // Line C2.5 (... AND HERE)
        sem_post(&empty); // Line C3
        printf("%d\n", tmp);
    }
}

int main(int argc, char *argv[]) {
    // ...
    sem_init(&empty, 0, MAX); // MAX buffers are empty to begin with...
    sem_init(&full, 0, 0); // ... and 0 are full
    sem_init(&mutex, 0, 1); // mutex=1 because it is a lock
    // ...
}

 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

typedef struct _rwlock_t {
    sem_t lock; // binary semaphore (basic lock)
    sem_t writelock; // used to allow ONE writer or MANY readers 
    int readers; // count of readers reading in critical section
} rwlock_t;

void rwlock_init(rwlock_t *rw) {
    rw->readers = 0;
    sem_init(&rw->lock, 0, 1); // Initialize lock semaphore with value 1
    sem_init(&rw->writelock, 0, 1); // Initialize writelock semaphore with value 1
}

void rwlock_acquire_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock); // Lock the critical section
    rw->readers++; // Increment the number of readers
    if (rw->readers == 1)
        sem_wait(&rw->writelock); // First reader acquires writelock, preventing writers
    sem_post(&rw->lock); // Unlock the critical section
}

void rwlock_release_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock); // Lock the critical section
    rw->readers--; // Decrement the number of readers
    if (rw->readers == 0)
        sem_post(&rw->writelock); // Last reader releases writelock, allowing writers
    sem_post(&rw->lock); // Unlock the critical section
}

void rwlock_acquire_writelock(rwlock_t *rw) {
    sem_wait(&rw->writelock); // Acquire writelock, preventing other readers and writers
}

void rwlock_release_writelock(rwlock_t *rw) {
    sem_post(&rw->writelock); // Release writelock, allowing other readers and writers
}

1
2
3
4
5
6

while (1) {
    think();
    getforks();
    eat();
    putforks();
}

1
2

int left(int p) { return p; }
int right(int p) { return (p + 1) % 5; }

1
2
3
4
5
6
7
8
9

void getforks() {
    sem_wait(forks[left(p)]);
    sem_wait(forks[right(p)]);
}

void putforks() {
    sem_post(forks[left(p)]);
    sem_post(forks[right(p)]);
}

1
2
3
4
5
6
7
8
9

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

 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

typedef struct __Zem_t {
    int value;               // Value of the semaphore
    pthread_cond_t cond;    // Condition variable for signaling
    pthread_mutex_t lock;   // Mutex for protecting shared data
} Zem_t;

// Initializes the semaphore with the specified initial value
void Zem_init(Zem_t *s, int value) {
    s->value = value;        // Set initial value
    Cond_init(&s->cond);     // Initialize condition variable
    Mutex_init(&s->lock);    // Initialize mutex
}

// Decrements the value of the semaphore (waits if the value is zero)
void Zem_wait(Zem_t *s) {
    Mutex_lock(&s->lock);          // Lock the mutex
    while (s->value <= 0) {        // Wait while value is less than or equal to 0
        Cond_wait(&s->cond, &s->lock); // Wait on the condition variable
    }
    s->value--;                    // Decrement the value
    Mutex_unlock(&s->lock);        // Unlock the mutex
}

// Increments the value of the semaphore and signals waiting threads
void Zem_post(Zem_t *s) {
    Mutex_lock(&s->lock);          // Lock the mutex
    s->value++;                    // Increment the value
    Cond_signal(&s->cond);         // Signal waiting threads
    Mutex_unlock(&s->lock);        // Unlock the mutex
}