Mutex

Tags

comp-arch

Is a synchronisation primitive for threads. It locks a resource such that multiple threads cannot access it simultaneously. If the resource is locked while another thread tries to access it, that thread is blocked until the resource becomes available (I.E. it's relinquished by the thread that locked it).

Note: The thread that locks a MUTEX is the only thread that can unlock it.

// Must be shared visible to all the threads,
// perhaps as a global variable.
pthread_mutex_t *m = malloc(sizeof(pthread_mutex_t));
pthread_mutex_init(m, NULL);

// Or we could've used the PTHREAD_MUTEX_INITIALIZER macro
// which only works with static (global) locks.
// pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;

pthread_mutex_lock(&m); // start of Critical Section
// ...
pthread_mutex_unlock(&m); //end of Critical Section
// ...
pthread_mutex_destroy(lock);
free(lock);

Critical Section Problem

Relates to the problem of mutual-exclusion in multi-threaded applications. It addresses:

1. Mutual Exclusion: The thread/process gets exclusive access to the critical section. Others must wait until they exit the critical section (release the lock).
2. Bounded Wait: A thread/process cannot get superseded by another thread infinite amounts of the time.
3. Progress: If no thread is inside the critical section then the thread/process should be able to proceed without having to wait.

Note: The term raising and lowering a flag is used to represent a thread/processes intention to enter the critical section.

Dekker's Algorithm algorithm

Is the first known correct solution to the critical-section problem.

It's limited only to two threads, doesn't address the issues of out-of-order instruction execution, and several other issues.

wants_to_enter = [False, False]  # Ix has raised flag, give me control
turn = 0  # which threads turn it is

# Procedure for thread 0
def p0():
    global turn
    wants_to_enter[0] = True
    # While other thread wants control and hasn't given up control.
    while wants_to_enter[1]:
	if turn != 0:
	    wants_to_enter[0] = False
	    while turn != 0:
		pass  # Spin until control is returned
	    wants_to_enter[1] = True
    # ... critical section stuff
    turn = 1  # Yield control over to the other thread
    wants_to_enter[0] = False

# Procedure for thread 1
def p1():
    global turn
    wants_to_enter[1] = True
    while wants_to_enter[0]:
	if turn != 1:
	    wants_to_enter[1] = False
	    while turn != 1:
		pass
	    wants_to_enter[1] = True
    # ... critical section stuff
    turn = 0
    wants_to_enter[1] = False

The turn variable in code:dekker dictates which thread has current access to the critical section. In the outer while loop we do a quick-check as to whether the other thread wants (and maybe has) entered the critical section or not. When not we immediate proceed which meets the Progress condition. In the inner while loop we:

• If its our threads turn then we wait for the other thread to give up control.
• Otherwise we set wants_to_enter false for ourselves so that the outer while loop of the other thread breaks and it can continue into the critical section.

This makes it so only one thread can be in the critical section at any time so we meet the condition of Mutual Exclusion condition. Lastly once the active (current-turn) thread exits the critical section we set turn to the other thread so that it can take control, achieving the Bounded Wait condition.

Peterson's Algorithm algorithm

Is a newer and simpler solution to the critical-section problem.

flag = [False, False]  # Ix has raised flag, give me control
turn = 0  # which threads turn it is

# Procedure for thread 0
def p0():
    global turn
    # Let the other thread have its turn, and wait for it if it's taking
    # it (flag[1] is set). It'll do the same and wait for us to finish
    # our turn if we go ahead here.
    turn = 1
    flag[0] = True
    while flag[1] and turn == 1:
	pass  # Spin until control is returned
    # ... Critical section
    flag[0] = False

# Procedure for thread 1
def p1():
    global turn
    turn = 0
    flag[1] = True
    while flag[0] and turn == 0:
	pass
    # ... Critical section
    flag[1] = False

You can see this implemented in code:peterson. This algorithm makes it so that if another thread is waiting to enter the critical section control is passed to it before its given to us; by having each thread set turn to the other thread at the beginning. We then wait until flag[o] is disabled to continue and enter the critical section. Notice if flag[o] (for the other thread) is disabled already then we immediately enter the critical section meaning we have the Progress problem solved. If the other thread tries to acquire the lock while the first thread is in the critical section it'll be blocked until the flag for the other thread is disabled meaning no two thread can enter the critical section simultaneously (achieving Mutual Exclusion). Lastly because control is immediately handed to the other thread if it asked for it at the start of each thread, no thread can infinitely acquire the lock meaning we have Bounded Wait.