Implementing locks on uniprocessors and multiprocessors.

We will develop a full multi-processor lock implementation.

These examples come from Stanford University:

http://web.stanford.edu/~ouster/cgi-bin/cs140-spring14

Uniprocessor locks: disable interrupts:

struct lock {
    int locked;
    struct queue q;
};

void lock_acquire(struct lock *l) {
    intr_disable();
    if (!l->locked) {
        l->locked = 1;
    } else {
        queue_add(&l->q, thread_current());
        thread_block();
    }
    intr_enable();
}

void lock_release(struct lock *l) {
    intr_disable();
    if (queue_empty(&l->q) {
        l->locked = 0;
    } else {
        thread_unblock(queue_remove(&l->q));
    }
    intr_enable();
}

For multiprocessors, disabling interrupts won't work (can't easily disable interrupts on all CPUs/cores at the same time).

We need an atomic update instruction (read-modify-write): swap(address, value)

Swap returns the old value located at address and updates the contents of address with the new value. This is done atomically.

Attempt 1

struct lock {
    int locked;
};

void lock_acquire(struct lock *l) {
    while (swap(&l->locked, 1)) {
        /* Do nothing */
    }
}

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

Attempt 2

struct lock {
    int locked;
    struct queue q;
};

void lock_acquire(struct lock *l) {
    if (swap(&l->locked, 1) != 0) {
        queue_add(&l->q, thread_current());
        thread_block();
    }
}

void lock_release(struct lock *l) {
    if (queue_empty(&l->q) {
       l->locked = 0;
    } else {
        thread_unblock(queue_remove(&l->q));
    }
}

Attempt 3

struct lock {
    int locked;
    struct queue q;
    int sync;         /* Normally 0. */
};

void lock_acquire(struct lock *l) {
    while (swap(&l->sync, 1) != 0) {
        /* Do nothing */
    }
    if (!l->locked) {
        l->locked = 1;
        l->sync = 0;
    } else {
        queue_add(&l->q, thread_current());
        l->sync = 0;
        thread_block();
    }
}

void lock_release(struct lock *l) {
    while (swap(&l->sync, 1) != 0) {
        /* Do nothing */
    }
    if (queue_empty(&l->q) {
        l->locked = 0;
    } else {
        thread_unblock(queue_remove(&l->q));
    }
    l->sync = 0;
}

Attempt 4

struct lock {
    int locked;
    struct queue q;
    int sync;         /* Normally 0. */
};

void lock_acquire(struct lock *l) {
    while (swap(&l->sync, 1) != 0) {
        /* Do nothing */
    }
    if (!l->locked) {
        l->locked = 1;
        l->sync = 0;
    } else {
        queue_add(&l->q, thread_current());
        thread_block(&l->sync);
    }
}

void lock_release(struct lock *l) {
    while (swap(&l->sync, 1) != 0) {
        /* Do nothing */
    }
    if (queue_empty(&l->q) {
        l->locked = 0;
    } else {
        thread_unblock(queue_remove(&l->q));
    }
    l->sync = 0;
}

Attempt 5

struct lock {
    int locked;
    struct queue q;
    int sync;         /* Normally 0. */
};

void lock_acquire(struct lock *l) {
    intr_disable();
    while (swap(&l->sync, 1) != 0) {
        /* Do nothing */
    }
    if (!l->locked) {
        l->locked = 1;
        l->sync = 0;
    } else {
        queue_add(&l->q, thread_current());
        thread_block(&l->sync);
    }
    intr_enable();
}

void lock_release(struct lock *l) {
    intr_disable();
    while (swap(&l->sync, 1) != 0) {
        /* Do nothing */
    }
    if (queue_empty(&l->q) {
        l->locked = 0;
    } else {
        thread_unblock(queue_remove(&l->q));
    }
    l->sync = 0;
    intr_enable();
}

Final Solution

struct lock {
    int locked;
    struct queue q;
    int sync;         /* Normally 0. */
};

void lock_acquire(struct lock *l) {
    intr_disable();
    while (swap(&l->sync, 1) != 0) {
        while(&l->sync) {
            /* do nothing */
        }
    }
    if (!l->locked) {
        l->locked = 1;
        l->sync = 0;
    } else {
        queue_add(&l->q, thread_current());
        thread_block(&l->sync);
    }
    intr_enable();
}

void lock_release(struct lock *l) {
    intr_disable();
    while (swap(&l->sync, 1) != 0) {
        while(&l->sync) {
            /* do nothing */
        }
    }
    if (queue_empty(&l->q) {
        l->locked = 0;
    } else {
        thread_unblock(queue_remove(&l->q));
    }
    l->sync = 0;
    intr_enable();
}