CH5 - Process Synchronization

The Critical-Section Problem

有些資源只能同時被一個 process 使用。

1
2
3
4
5
6


do {
    entry_section();
    // critical section
    exit_section();
    // remainder section
while (true);

Mutual Excusion
Progress (Freedom from Deadlock)
Bounded Wait (Freedom from Starvation)

preemptive: 資源被使用時可以被打斷
non-preemptive

Peterson’s Solution

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


class PetersonLock {
    // shared var.
    bool flag[2];
    int victim;
  public:
    void lock() {
        int i = ThreadID.get();
        int j = 1 - i;
        flag[i] = true;
        victim = i;
        while (flag[j] && victim == i);
    }
    void unlock() {
        int i = ThreadID.get();
        flag[i] = false;
    }
};

1
2
3
4
5
6


do {
    lock();
    // critical section
    unlock();
    // remainder section
while (true);

Test & Set

1
2
3
4
5
6


// atomic
bool test_and_set (bool *target) {
    bool ret = *target;
    *taget = true;
    return ret;
}

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


do {
    wait[i] = true;
    while (wait[i] && test_and_set(&lock) );
    wait[i] = false;
    // critical section
    j = (i + 1) % n;
    while ( (j != i) && !waiting[j] )
        j = (j + 1) % n;
    if (j == i)
        lock = flase;
    else
        wait[j] = false;
} while (true);

Compare & Swap

1
2
3
4
5
6


int compare_and_swap (int * val, int expected, int new_val) {
    int tmp = *val;
    if (*val == expected)
        *val = new_value;
    return tmp;
}

1
2
3
4
5
6


do {
    while (compare_and_swap(&lock, 0, 1) );
    // critical section
    lock = 0;
    // remainder section
} while (true);

Mutex

acqueire() and release() are atomic.

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


acquire() {
    while (!available) ;
    available = false;
}
release () {
    available = true;
}

do {
    acquire();
    // critical section
    release();
    // remainder section
} while (true);

Semaphore

counting/binary semaphore
semaphore S : integer
wait() and signal() are atomic

1
2
3
4
5
6
7
8


wait(S) {
    while (S <= 0)
        yeild();
    S--;
}
signal(S) {
    S++;
}    

Implementation (Blocking)

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


struct sempaphore {
    int cnt;
    queue q;
}

void wait(semaphore *S) {
    S->cnt--;
    if (S->cnt < 0) {
        S->q.push(process);
        block();
    }
}

void signal(semaphore *S) {
    S->cnt++;
    if (S->cnt >= 0) {
        P = S->q.pop();
        wakeup(P);
    }
}

Examples

1. Bounded-Buffer Problem

1
2
3
4


init Semaphores:
    mutex->cnt = 1;
    full->cnt = 0;
    empty->cnt = N;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


// producer
do {
    // produce an item
    wait(empty);
    wait(mutex);
    // add the item to buffer;
    buffer[in] = product;
    in = (in + 1) % N;
    signal(mutex);
    signal(full);
} while (true);    

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


// consumer
do {
    // produce an item
    wait(full);
    wait(mutex);
    // add the item to buffer;
    product = buffer[out];
    out = (out + 1) % N;
    signal(mutex);
    signal(empty);
} while (true); 