CSCE 313 Lecture 10

« previous | Thursday, February 16, 2012 | next »

Hardware Support for Synchronization

Atomic Operations

Test-And-Set

// defined in hardware
extern bool TestAndSet(bool& var) {
    bool temp = var;
    var = TRUE;
    return temp;
}

bool lock = FALSE;
while (TRUE) {
    while (TestAndSet(lock)) no_op;

    critical_section();

    lock = FALSE;
}

Exchange (Swap)

// defined in hardware
extern void Exchange(bool& a, bool& b) {
    bool temp = a;
    a = b;
    b = temp;
}

bool lock = FALSE;
while (TRUE) {
    dummy = TRUE;
    do Exchange(lock, dummy);
    while (dummy);
    
    critical_section();

    lock = FALSE;
}

Compare-And-Swap

// defined in hardware
extern bool CompareAndSwap(Type* x, Type old, Type new) {
    if (*x == old) {
        *x = new;
        return TRUE;
    } else {
        return FALSE;
    }
}

// push C onto a shared stack
CompareAndSwap(head, newNode.next, newNode);

Semaphores

The previous solutions are complex. A semaphore has two operations:

• P(Semaphore* s) (wait): decrement value of s by 1. If the value becomes negative, the process invoking the P operation is blocked.
• V(Semaphore* s) (signal): increment value of s by 1. in a single indivisible action. If value is not positive (≤ 0), then pracess blocked by a P is unblocked.

Two Types of semaphores:

binary

Value of s can be either 1 or 0 (TRUE or FALSE)

also known as a mutex lock

general

value of s can be an integer

BinSemaphore* s; // init to TRUE
while (TRUE) {
    P(s);
    critical_section();
    V(s);
}

Implementation: Spinlock

Binary Semaphores

void P(BinSemaphore* s) {
    key = FALSE;
    do Exchange(s.value, key);
    while (key == FALSE);
}

void V(BinSemaphore* s) {
    s.value = TRUE;
}

General Semaphores

BinSemaphore* mutex // TRUE
BinSemaphore* delay // FALSE

P(Semaphore* s) {
    P(mutex);                   // enter internal critical section
    s.value = s.value - 1       // decrement value
    if (s.value < 0) {          // if value is not positive...
        V(mutex);               // exit internal critical section
        P(delay);               // tell process to wait
    } else {
        V(mutex);
    }
}

V(Semaphore* s) {
    P(mutex);
    s.value = s.value + 1;
    if (s.value <= 0) V(delay);
    V(mutex);
}

Deadlock and Other Problems

Two or more processes are waiting indefinitely for each other

P0	P1
wait(S);	wait (Q);
wait(Q); (P0 blocked)	wait(S); (P1 blocked)

Starvation

Indefinite blocking; a process may never be removed from the semaphore queue in which it is suspended.

Priority Inversion

a lower-priority process holds a lock on resources needed by a higher-priority process.

Classical Problems

Producer-Consumer with Unlimited Buffer

Semaphore* n; // 0
BinSemahpore* mutex; // TRUE

// Producer
while (TRUE) {
    produce_item();

    P(mutex);

    deposit_item();

    V(mutex);

    V(n);
}

// Consumer
while (TRUE) {
    P(mutex);

    remove_item();

    V(mutex);

    V(n);
}

Producer-Consumer with Bounded Buffer

Semaphore* full; // 0
Semaphore* empty; // n
BinSemaphore* mutex; // TRUE

// Producer
while (TRUE) {
    produce_item();

    P(empty);
    P(mutex);

    deposit_item();

    V(mutex);
    V(full);
}

// Consumer
while(TRUE) {
    P(full);
    P(mutex);

    remove_item();

    V(mutex);
    V(empty);
    
    consume_item();
}