Hardware solutions

Disabling interrupts

Uniprocessor computational system

• The switching of processes, in a multiprogrammed environment, is always caused by an external device:

  • real time clock (RTC) – cause the time-out transition in preemptive systems.

  • device controller – can cause the preempt transitions in case of waking up of a higher priority process.

  • In any case, interruptions of the processor.

• Thus, access in mutual exclusion can be implemented disabling interrupts.

• Only valid in kernel.

  • Malicious or buggy code can completely block the system.

Multiprocessor computational system

• Disabling interrupts in one processor has no effect.

Special instructions

TAS

The test_and_set function, if implemented atomically (without interruptions), can be used to construct the lock (enter critical section) primitive.

In the instruction set of some of the current processors, there is an atomic instruction implementing this behavior.

Surprisingly, it is often called TAS (test and set).

CAS

The compare_and_swap function, if implemented atomically (without interruptions), can be used to construct the lock (enter critical section) primitive.

In the instruction set of some of the current processors, there is an atomic instruction implementing that behavior.

In some instruction sets, there is a compare_and_set variant this returns a bool.

Busy waiting

The previous solutions suffer from busy waiting.

• The lock primitive is in the active state (using the CPU) while waiting.

• It is often referred to as a spinlock, as the process spins around the variable while waiting for access.

In uniprocessor systems, busy waiting is unwanted, as there is:

• loss of efficiency – the time quantum of a process is used for nothing.

• risk of deadlock – if a higher priority process calls lock while a lower priority process is inside its critical section, none of them can proceed.

In multiprocessor systems with shared memory, busy waiting can be less critical.

• switching processes cost time, that can be higher than the time spent by the other process inside its critical section.

Block and wake up

In general, at least in uniprocessor systems, there is the requirement of blocking a process while it is waiting for entering its critical section.

Atomic operations are still required.