The synchronization objects to be implemented are fundamentally different from the mechanisms already programmed to switch off interrupts or the guard. While the latter solve the competition between ISRs and normal control flow or between processors at the lower level, synchronization objects allow mutual exclusion between user threads. The guard is nevertheless required for the implementation, as there are critical sections within the synchronization objects that must be protected with the existing mechanisms.

Ultimately, we are building a new synchronization mechanism based on the existing ones, but one that is better suited to threads because it allows passive waiting.

Synchronization on different levels of the system

Passive vs. active waiting

Already implemented primitives such as the spinlock or the ticketlock, which are used for mutual exclusion between processors, actively wait in a loop for a value to change. While they wait for the critical section to be released, no other control flow can take over, as the dispatcher that would realize the control flow change is itself dependent on the spinlock/ticketlock.

When passively waiting for a semaphore or a mutex, on the other hand, the waiting thread can or must be displaced by other threads. The waiting thread is not brought back into scheduling until the wait condition is fulfilled. This allows the system to make more progress than if the waiting thread were actively waiting for the condition. In a cooperative Scheduling, waiting threads would have to relinquish control and may no longer be scheduled until the condition is fulfilled.

Active waiting can also be useful for user applications in some cases, as passive waiting provokes a context switch, which may be more expensive than (briefly) actively waiting.

Synchronization objects

Boolean synchronization (mutex)

A very simple synchronization object is the mutex. A mutex consists of a Boolean variable that is set when the critical section is entered and reset when it is exited. Access to the Boolean variable must be protected against race conditions. If the mutex is taken, the thread must wait until the owning thread releases it again.

Semaphores

A more general concept than a mutex is the semaphore. Semaphores can also be used to express Boolean mutexes. A semaphore contains an integer variable that can be counted down (Semaphore::P(), Dutch "Prolaag", Engl. mem: "procure") and up (Semaphore::V(), Dutch "Verhoog", Engl. mem: "vacate"). If the counter is zero when entering the critical section (P()), the calling thread must wait. When leaving the critical section (V()), the counter is incremented and sleeping threads are woken up. The start value of a semaphore depends on its specific use.

There are three possible uses for semaphores:

Protection of a critical section
signaling
Limiting resource requirements

Protection of a critical section (use as mutex)

If a semaphore is shared between threads and its start value is initialized to 1, it can be used to protect critical sections, similar to a Boolean mutex.

// shared semaphore
Semaphore s = newSemaphore ( 1 );
 
P(S)
// critical section
V(S)

Signaling

A semaphore can also be used for signaling the arrival of data. For example, the keyboard driver may have just placed a new character in the character buffer. It then increments the semaphore by one to indicate to the user application that there are new characters in the buffer. The user thread is added to the ready list, scheduled later and can read the character. In one of the next runs, it will get stuck again during the P() operation if there are no more characters in the buffer.

// shared semaphore
Semaphore s = newSemaphore ( 0 );
 
// user thread
void usr_thread () {
    while ( 1 ) {
        s.P();
        // read character
    }
}
 
// keyboard driver
void keyboard_driver ( char newChar ) {
    // put character in buffer
    s.V()
}

Limit resource requirements

A limited buffer could be used in the communication between threads. A semaphore can then be pre-initialized to the size of the buffer. The writer executes P(), decrementing the counter that specifies the remaining memory locations. The reader can use V() to release memory in the buffer that has already been read.

#define N 42
int buffer[N];
 
// shared semaphore
Semaphore s = newSemaphore ( N );
 
// reader
int reader () {
    int x = buffer[curPos];
    curPos++;
    s.V()
    return x;
}
 
// writer
int writer ( int x ) {
    buffer[curWritePos] = x;
    curWritePos++;
    s.P();
}

Sleep on time

Threads sometimes want to do nothing for a certain period of time. This requires the Bellringer, which manages a list of Bells. Bells are waiting rooms.

The bell is created by the thread itself, but must be checked with every timer interrupt. As the check is more frequent than the insertion, it makes sense to design the data structure in such a way that the check is very fast. The Bell created can be placed on the stack of the thread to be put to sleep, because once the thread is woken up, it no longer needs the Bell object anyway.

Idle

If we keep putting more and more threads to sleep, it can happen that there are no more threads in the system that can be processed. However, processors always need something to do or you have to put them to sleep (hlt).

Therefore, each CPU should have an idle thread to keep the CPU busy when there is nothing else to do. Idle threads should never be placed in the ready list!

void idle () {
    while (1);
}

An infinite loop would work, but it kills polar bears. Therefore, we prefer to put the processor to sleep so that this core consumes less power. For this, we can use the hlt instruction, which halts the processor until the next interrupt occurs.

Between loading the idle thread and the `hlt` instruction, a thread becomes executable

What happens, however, if, between deciding that there is no work to be done and actually hlting, a thread becomes active as a consequence of an interrupt? We could miss the change of the thread's ready state, which leads to a Lost Wakeup situation. The processor goes to sleep even though the bellringer has woken up a thread.

Fortunately, the effect of sti, enabling interrupts, only comes into effect after/during the next instruction. Core::idle therefore does sti; hlt; directly after each other, so that no interrupt can intervene between sti and hlt (if interrupts were disabled before).

Tickless kernel

Interrupts wake up the CPU again, this also applies to the timer interrupt. However, this in particular often leads to an unintentional wake-up, as the CPU only wakes up to check that there is still no work to be done. For this reason, it makes sense to implement a tickless kernel that switches off the timer in idle mode before the CPU is put to sleep.

void idle() {
    watch.block();
    CPU::idle();
    watch.unblock();
}

Unfortunately, this approach does not quite work, as the bellringer also needs the timer to function correctly. This must therefore be handled separately.

Table of Contents