Information Technology Reference
In-Depth Information
Lock::acquire()
waits until the lock isFree, and then it atomically
makes the lockBusy.
Checking the state to see if it isFreeand setting the state toBusyare
together an atomic operation. Een if multiple thread are trying to acquire
the lock, at most one thread will succeed|only one thread will observe
that the lock isFreeand set it toBusy; the other threads will just see
that the lock isBusyand wait.
Lock::release()
makes the lockFree. If there are pending
acquire()
operations, then this state change causes one of them to proceed.
We will describe how to implement locks with the above properties in Sec-
tion 5.5. But, assuming we can implement such a lock, solving the Too Much
Milk problem is trivial. Both threads run the following code:
lock.acquire();
if(milk==0){
//ifnomilk
milk++;
//buymilk
}
lock.release();
Formal properties. The above definition describes the basic operation of a
lock. A lock can be defined more precisely as follows.
We say that a thread holds a lock if it has returned from a lock's
acquire()
method more often than it has returned from a lock's
release()
method. We
say that a thread is attempting to acquire a lock if it has called but not yet
returned from a call to
acquire()
on the lock.
A lock should ensure the following three properties:
1. Mutual Exclusion. At most one thread holds the lock.
2. Progress. If no thread holds the lock and any thread attempts to acquire
the lock, then eventually some thread succeeds in acquiring the lock.
3. Bounded waiting. If thread T attempts to acquire a lock, then there
exists a bound on the number times other threads successfully acquire the
lock before T does.
The first property is a safety property. It says that we can use locks to
enforce mutual exclusion on access to shared state.
The second and third properties are liveness properties. The second says
that if a lock isFree, some thread must be able to acquire it. The third
defines a fairness property: any particular thread that wants to acquire the
lock must eventually succeed in doing so. If the definitions above sound a bit
stilted, it is because they are carefully crafted to avoid introducing subtle corner
