Information Technology Reference
In-Depth Information
7. Wikipedia provides an implementation of Peterson's algorithm to provide
mutual exclusion using loads and stores at
http://en.wikipedia.org/
wiki/Peterson's_algorithm
.
Unfortunately, this code is not guaranteed
to work with modern compilers or hardware. Update the code to include
memory barriers where necessary. (Of course you could add a memory
barrier before and after each instruction; your solution should instead add
memory barriers only where necessary for correctness.)
8. Linux provides a
sysfutex()
system call to assist in implementing hybrid
user-level/kernel-level locks and condition variables.
A call to
longsysfutex(void*addr1,FUTEXWAIT,intval1,NULL,
NULL,0
checks to see if the memory at address
addr1
has the same value
as
val1
. If so, the calling thread is suspended. If not, the calling thread
returns immediately with the error return value
EWOULDBLOCK
. In addition,
the system call will return with the value
EINTR
if the threadreceives a
signal.
A call to
longsysfutex(void*addr1,FUTEXWAKE,1,NULL,NULL,
0)
causes one thread waiting on
addr1
to return.
Consider the following (too) simple implementation of a hybrid user-
level/kernel-level lock.
classTooSimpleFutexLock{
private:
intval;
public:
TooSimpleMutex():val(0){}
//Constructor
voidAcquire(){
intc;
while((c=atomic_inc(val))!=0){
//atomic_increturns*old*value
futex_wait(&val,c+1);
}
}
voidRelease(){
val=0;
futex_wake(&val,1);
}
};
There are three problems with this code.
(a.) Peformance. The goal of this code is to avoid making (expensive)
system calls in the uncontested case when an Acquire() tries to ac-
quire a free lock or a
Release()
call releases a lock with no other
waiting threads. This code fails to meet this goal. Why?
(b.) Performance. There is a subtle corner case when multiple threads
try to acquire the lock at the same time that can show up as occa-
sional slowdowns and bursts of CPU usage. What is the problem?