Mutual exclusion means that a critical section cannot be entered a second time in the entire system as long as the first thread / processor / ... has not left it again. A critical section is a piece of program code that can lead to undesirable effects if two threads or processors execute it at the same time. Depending on the interleaving of the instructions, for example, variable updates may not become visible because they are overwritten directly by the other thread.

For example, the following code may cause problems (the assumption is that thread1() and thread2() are executed simultaneously or at least interleaved):

int sum = 42;
 
int thread1 () {
    sum+=1;
}
 
int thread2 () {
    sum-=1;
}

The shared variable is first read by each thread, then edited and written back. If the instructions are interleaved unfavorably, updates (+1 or -1) may be lost if, for example, thread 2 overwrites the new value of thread 1 with its old value.

There are different types of actors in the operating system. On the one hand, there is the normal program flow and interrupt service routines that can get in each other's way. On the other hand, several CPU cores in the multi-core system can execute program code at the same time. Not only can there be any number of overlaps between any instructions and data, but several interrupt services can also be executed at the same time.

Disabling interrupts

Interrupts must be disabled in two places. Firstly, when accessing shared data structures, the operating system must ensure that no interrupt can occur that would also access this data structure. The system programmer must also think about whether interrupt handling may be nested, i.e. executed within one another.

To exclude nested interrupt handling, you can simply use interrupt gates, where the Intel processors exclude further interrupt handling. For normal program execution, interrupts can be masked out in the processor. For this purpose, the instructions cli and sti can be used to mask out and re-enable interrupt requests.

Exclusion between processors

Exclusion must also take place between several cores if shared data structures are accessed. The instructions that set the interrupt flag in the status register are not sufficient for this. To ensure mutual exclusion between cores, a memory variable is used that indicates (in various ways) whether any processor is currently in the critical section or not. The operations lock() and unlock() are then typically used to access this variable. The lock() operation returns when the critical section can be entered, while the unlock() operation releases it again. If the critical section is not free, lock() will not return.

There are many ways to implement locks. We will implement the classic spinlock and optionally the ticketlock.

Spinlock

A spinlock is a data structure that can be implemented using a Boolean variable, i.e. the variable is set if a processor is in the critical section and is otherwise unset.

When entering the critical section, you must therefore wait until the variable is free. It is then set and the critical section is entered. When leaving the critical section, the variable must be reset.

Caution: If the variable is checked and set in two steps, this can lead to a race condition, as a second processor running in parallel could also have already performed the check positively and entered the critical section before the first processor can set the variable. Checking and setting must therefore run atomically, i.e. simultaneously.

Intel processors provide suitable instructions for executing such actions simultaneously, and GCC comes with built-in macros that make these instructions available.

Ticketlock

A ticket lock is implemented by two integer variables. All users of the lock go to a "switch" and take a ticket, i.e. a number, when they want to enter. If the lock displays the number of the thread, the critical section can be entered, otherwise the user must wait. When leaving the critical section, the counter indicating the current ticket is incremented so that the next waiting thread can enter the critical section. Which operations must be atomic here?

Table of Contents

Disabling interrupts

Exclusion between processors

Spinlock

Ticketlock