A lock can be in one of two states: locked and unlocked.
Semantics of lock operations:
Lock(name) : creates a lock that starts out in the unlocked state.
Acquire() : Atomically waits until the lock state is unlocked, then
sets the lock state to locked.
Release() : Atomically changes the lock state to unlocked from
locked.
In assignment 1 you will implement locks in Nachos on top of semaphores.
What are requirements for a locking implementation?
Only one thread can acquire lock at a time. (safety)
If multiple threads try to acquire an unlocked lock, one of the
threads will get it. (liveness)
All unlocks complete in finite time. (liveness)
What are desirable properties for a locking implementation?
Efficiency: take up as little resources as possible.
Fairness: threads acquire lock in the order they ask
for it. Are also weaker forms of fairness.
Simple to use.
When use locks, typically associate a lock with pieces of
data that multiple threads access. When one thread wants to
access a piece of data, it first acquires the lock. It then
performs the access, then unlocks the lock. So, the lock allows
threads to perform complicated atomic operations on each
piece of data.
Can you implement unbounded buffer only using locks? There is
a problem - if the consumer wants to consume a piece of data
before the producer produces the data, it must wait. But locks
do not allow the consumer to wait until the producer produces
the data. So, consumer must loop until the data is ready. This
is bad because it wastes CPU resources.
There is another synchronization abstraction called
condition variables just for this kind of situation. Here is
the Nachos interface:
Wait(Lock *l) : Atomically releases the lock and waits.
When Wait returns the lock will have been reacquired.
Signal(Lock *l) : Enables one of the waiting threads to run.
When Signal returns the lock is still acquired.
Broadcast(Lock *l) : Enables all of the waiting threads
to run. When Broadcast returns the lock is still acquired.
All locks must be the same.
In assignment 1 you will implement condition
variables in Nachos on top of semaphores.
Typically, you associate a lock and a condition variable with
a data structure. Before the program performs an operation on the
data structure, it acquires the lock. If it has to wait before
it can perform the operation, it uses the condition variable
to wait for another operation to bring the data structure into
a state where it can perform the operation. In some cases
you need more than one condition variable.
Let's say that we want to implement an unbounded buffer
using locks and condition variables. In this case we have
2 consumers.
Lock *l;
Condition *c;
int avail = 0;
void consumer(int dummy) {
while (1) {
l->Acquire();
if (avail == 0) {
c->Wait(l);
}
consume the next unit of data
avail--;
l->Release();
}
}
void producer(int dummy) {
while (1) {
l->Acquire();
produce the next unit of data
avail++;
c->Signal(l);
l->Release();
}
}
void main() {
l = new Lock("l");
c = new Condition("c");
Thread *t = new Thread("consumer");
t->Fork(consumer, 1);
Thread *t = new Thread("consumer");
t->Fork(consumer, 2);
t = new Thread("producer");
t->Fork(producer, 1);
}
