Mutual Exclusion and Synchronization

Mutual Exclusion and Synchronization

Many processes compete for limited, exclusive, nonpreemptible resources. This contention is called competition; a race condition occurs when the result depends on uncontrolled concurrent execution order.

Process constraints can be divided into two categories:

1. Mutual exclusion: processes have no inherent ordering relationship but constrain each other when competing for a critical resource, such as a printer, that cannot be used by several processes simultaneously.
2. Synchronization: processes have an inherent ordering relationship, such as one process completing an operation before another can continue.

Processes have independent data storage and cannot directly access each other's private data. Pipes and other mechanisms provide communication. When different processes operate on one resource, data synchronization must be considered.

To understand synchronization, first consider what happens without it.

Ticket Sales (Buggy Version)

import multiprocessing
import time

def sell_ticket(dict):
	while True:
		num = dict.get("ticket")
		if num > 0:
			time.sleep(1)
			num -= 1
			print("[Ticket Machine %d] Ticket sold. Ticket remaining: %d" % (
				multiprocessing.current_process().pid,
				num
			))
			dict.update({"ticket": num})
		else:
			break

def main():
	manager = multiprocessing.Manager()
	ticket_dict = manager.dict(ticket=5)
	sellers = [
		multiprocessing.Process(
			target=sell_ticket, args=(ticket_dict,)
		)
		for _ in range(5)
	]
	for seller in sellers:
		seller.start()
	for seller in sellers:
		seller.join()

if __name__ == "__main__":
	main()

When several processes check the ticket count without synchronizing the complete read, test, and update, they can sell the same ticket or overwrite each other's updates.

There are two waiting approaches for mutual exclusion:

1. Busy waiting: repeatedly test until execution can continue.
2. Sleep and wakeup: mechanisms such as semaphores block waiting processes, which other processes wake.

Critical Sections

A critical resource is a shared resource used by at most one process at a time under mutual exclusion. Examples include printers, variables, and buffers.

The code that accesses a critical resource is a critical section. At most one process may enter the corresponding section for that resource at a time. Both hardware and software critical resources require mutual exclusion. Critical sections should be short: waiting participants may spin or block, affecting performance.

WHILE true DO
    Perform entry section: request access
    Perform critical section: access the shared resource
    Perform exit section: release access
    Perform remainder section: do other work
END WHILE

Peterson's Algorithm

Gary L. Peterson introduced this two-participant mutual-exclusion algorithm in 1981. Correctness requires atomic accesses and suitable memory ordering; plain unsynchronized C variables are insufficient.

The two processes share two data items:

int turn;
bool flag[2];

Mutex

A mutex controls access to shared resources through locking and has two states: locked (acquire) and unlocked (release).

Acquiring the mutex must be atomic, ensuring that after one process succeeds, no other process can acquire it simultaneously. Testing availability and locking cannot be separate ordinary accesses; the following code illustrates the acquire/release flow, not a directly usable atomic implementation.

void acquire(void) {
	while (!available) {
		; // busy wait
	}
	available = false;
}

void release(void) {
	available = true;
}

do {
	acquire();
	// critical section
	release();
	// remainder section
} while (true);

Concurrent processes must synchronize certain core code. Python provides Lock to ensure that only one process executes the protected code at a time.

Ticket Sales (Correct Version)

import multiprocessing
import time

def sell_ticket(lock, dict):
	while True:
		if not lock.acquire(timeout=5):
			break
		try:
			num = dict.get("ticket")
			if num > 0:
				time.sleep(1)
				num -= 1
				print("[Ticket Machine %d] Ticket sold. Ticket remaining: %d" % (
					multiprocessing.current_process().pid,
					num
				))
				dict.update({"ticket": num})
			else:
				break
		finally:
			lock.release()

def main():
	lock = multiprocessing.Lock()
	manager = multiprocessing.Manager()
	ticket_dict = manager.dict(ticket=5)
	sellers = [
		multiprocessing.Process(
			target=sell_ticket, args=(lock, ticket_dict)
		)
		for _ in range(5)
	]
	for seller in sellers:
		seller.start()
	for seller in sellers:
		seller.join()

if __name__ == "__main__":
	main()

Adding a lock allows only one process to execute the corresponding critical section and can introduce waiting and synchronization overhead. Appropriate synchronization is required to keep shared data correct.

Hardware Implementation

Hardware provides test_and_set() as an atomic operation. The following C syntax describes its semantics; ordinary C loads and stores do not provide atomicity.

bool test_and_set(bool *target) {
    bool rv = *target;
    *target = true;
    return rv;
}

The shared lock starts at false. The semicolon in while (test_and_set(&lock)); denotes waiting for the lock.

do {
	while (test_and_set(&lock)) {
		; // do nothing
	}
	// critical section
	lock = false;
	// remainder section
} while (true);

compare_and_swap() must also be atomic. The following C syntax describes its operation; ordinary separate loads and stores do not provide atomicity.

int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;
    if (*value == expected) {
        *value = new_value;
    }
    return temp;
}

The mutex lock starts at 0.

do {
	while (compare_and_swap(&lock, 0, 1) != 0) {
		; // do nothing
	}
	// critical section
	lock = 0;
	// remainder section
} while (true);

Machine instructions are simple to reason about and support multiple critical sections, each with its own variable. Their drawbacks include busy waiting and possible starvation: without a fair selection rule, a process may be denied entry indefinitely.