Completions

Linux 2.4 also makes use of another synchronization primitive similar to semaphores: the completions. They have been introduced to solve a subtle race condition that occurs in multiprocessor systems when process A allocates a temporary semaphore variable, initializes it as closed MUTEX, passes its address to process B, and then invokes down( ) on it. Later on, process B running on a different CPU invokes up( ) on the same semaphore. However, the current implementation of up( ) and down( ) also allows them to execute concurrently on the same semaphore. Thus, process A can be woken up and destroy the temporary semaphore while process B is still executing the up( ) function. As a result, up( ) might attempt to access a data structure that no longer exists.

Of course, it is possible to change the implementation of down( ) and up( ) to forbid concurrent executions on the same semaphore. However, this change would require additional instructions, which is a bad thing to do for functions that are so heavily used.

The completion is a synchronization primitive that is specifically designed to solve this problem. The completion data structure includes a wait queue head and a flag:

struct completion {

unsigned int done; wait_queue_head_t wait;

The function corresponding to up( ) is called complete( ). It receives as an argument the address of a completion data structure, sets the done field to 1, and invokes wake_up( ) to wake up the exclusive process sleeping in the wait wait queue.

The function corresponding to down( ) is called wait_for_completion( ). It receives as an argument the address of a completion data structure and checks the value of the done flag. If it is set to 1, wait_for_completion( ) terminates because complete( ) has already been executed on another CPU. Otherwise, the function adds current to the tail of the wait queue as an exclusive process and puts current to sleep in the task_uninterruptible state. Once woken up, the function removes current from the wait queue, sets done to 0, and terminates.

The real difference between completions and semaphores is how the spin lock included in the wait queue is used. Both complete( ) and wait_for_completion( ) use this spin lock to ensure that they cannot execute concurrently, while up( ) and down( ) use it only to serialize accesses to the wait queue list.

0 0

Post a comment