Module a6_event_sync

BSB - A6: Events and Synchronization

It is time to extend your StuBS with synchronization objects, enabling threads to inform each other about different events or to wait for them.

• Semaphore to synchronize application threads with each other. Use them, for example, to block an application thread after it has queried the keyboard for (yet non-existent) input until a key is pressed.
• BellRinger to put threads to sleep for a certain period.

This also means that we have another state for threads: Blocked

        [ Active ] -----.
         / ^             | block
 resume / /              |
       v /               v
 [ Ready ] <- - - - [ Blocked ]
            wakeup

If the ready list is empty, we want to stop the core to reduce power usage (using the hlt instruction). Since only interrupts will wake up threads, the execution should be continued if new threads are in the ready list after an interrupt. We achieve this behavior by introducing idle threads (exclusively dedicated to each core). They are scheduled as soon as no threads are in the ready queue and perform the idle loop.

It is also necessary to wake up sleeping cores whenever a thread is put back on the ready list by calling Scheduler::ready(). Use a separate IPI triggering a WakeUp, similar to Scheduler::kill() and the Assassin.

This assignment can be split into the following steps:

• Semaphore for guarding the keyboard buffer
• Bell and BellRinger for sleeping
• idle_action and putting processors to sleep
• (optional) Tickless Kernel
• (optional) Use the PC Speaker to create a melody using the functionality of the Bells

1. Semaphore and Keyboard Buffer

Semaphores in StuBS contain a counter and a list of sleeping threads. When a thread calls Semaphore::wait(), the counter is decremented if greater than zero, or the thread must be blocked and inserted into the waiting queue in the semaphore object. When Semaphore::signal() is called, a sleeping thread is awakened or otherwise the counter is incremented. Both methods need access to the Scheduler to block or wake up threads.

Implement these methods and test the semaphore by using it to synchronize the KOUT (ignore any other locks). You have successfully implemented the semaphore if threads do not mess with each other’s output.

Then, the KeyBuffer can be created, which consists of a fixed buffer for chars and a semaphore. The reading threads should use a semaphore when accessing the buffer, forcing them to wait when no content is present to be read. The keyboard interrupt uses the semaphore to signal that it inserted new data into the buffer. A Thread should be adapted to take on the keyboard input and print it onto the screen.

Ensure there are always enough threads ready in the system to keep the processors busy!

2. Bell and BellRinger

The BellRinger allows threads to sleep for a certain time. It also stores the sleeping threads in a list, with their delay in timer ticks. The timer interrupt handler should call to the guarded Bellringer instance’s Bellringer::check() method, which wakes up threads that have slept long enough.

Because the check function is called regularly, it should be quite fast. We usually do not want to traverse the whole list of sleeping threads to find the ones to wake up. Instead, it is better to have a constant runtime (O(1)). The idea is to put the threads in the list in ascending order (based on their sleep time), and only store the relative tick-offset to the previous threads in the list, so that T1.sleep(40) and T2.sleep(10) result in the following list:

Bellringer::bells = [ (T2, 10), (T1, 30) ]

Then the check function can just decrement the tick counter of the first bell and wake its thread up if it reaches zero. Note that you might also have to wake up the next thread if its tick counter is already zero.

With this, it is pretty easy to create periodic threads, letting them sleep for a few milliseconds and then perform an action (e.g., make an output). Demonstrate this with a suitable example (multiple threads that wake up at different intervals).

3. Idle Threads

The previous steps make more and more threads wait passively, so the system needs to schedule other threads when all regular threads are waiting. The CPU still has to do something (like sleeping).

For this, we introduce the idle_action(), which lets the processor go into sleep mode (with the hlt instruction). An x86 processor will then only wake when it receives an interrupt (if they are not masked with cli).

However, this naive approach has a lost-wake-up problem if the scheduler decides to schedule the idle thread and a thread becomes ready before the latter can execute htl. The decision to sleep has already been made.

|----|---------------|-----------------|--->
  schedule         timer           idle thread
idle thread     wake up thread    executes hlt

This can be solved by first disabling interrupts in the idle thread, then rechecking if the ready list is still empty, and finally executing sti; hlt; (enabling interrupts and sleeping). The instructions (sti; hlt;) directly behind each other are executed atomically, ensuring that no interrupt can come between them, which prevents lost wake-ups.

Sleeping threads shall be awakened by Interprocessor Interrupts (with WakeUp) when new threads get ready.

For testing, starve the system of threads, i.e., less than 4.

4. Tickless Kernel (optional)

Once you have solved the idle problem, you can then proceed to enhance your implementation in such a way that the timer does not constantly interrupt idle cores. This is desirable to reduce power consumption. Add the ability to block and unblock the timer in the idle_action().

Hint: Obviously, you should only switch off all cores if there is no bell pending in the BellRinger’s queue.

5. PC-Speaker (optional)

The beeping PC speaker is a historical relic that is sometimes still present in modern systems (like our test boxes). The speaker is connected to the PIT and can produce a tone at the frequency of your choice. Timer::beep() provides you with an interface to set the desired frequency (preferably with interrupts disabled). The speakers should then beep until you change it or silence the device with a frequency of 0.

That makes it a perfect demonstration application for passive waiting: A thread sets a frequency and then sleeps for a given time before continuing with the next frequency.

use stubs::arch::int;
use stubs::arch::pit::Timer;
use stubs::interrupts::guard::GUARD;

extern "C" fn music() -> ! {
    #[rustfmt::skip]
    const MELODY: [[u16; 2]; 77] = [
        [587, 750], [659, 187], [740, 187], [587, 187], [659, 187], [659, 187],
        [659, 187], [740, 187], [659, 375], [440, 375], [  0, 750], [494, 187],
        [554, 187], [587, 187], [494, 187], [  0, 187], [659, 187], [740, 187],
        [659, 562], [440,  93], [494,  93], [587,  93], [494,  93], [740, 280],
        [740, 280], [659, 562], [440,  93], [494,  93], [587,  93], [494,  93],
        [659, 280], [659, 280], [587, 280], [554,  93], [494, 280], [440,  93],
        [494,  93], [587,  93], [494,  93], [587, 375], [659, 187], [554, 280],
        [494,  93], [440, 187], [440, 187], [440, 187], [659, 375], [587, 750],
        [440,  93], [494,  93], [587,  93], [494,  93], [740, 280], [740, 280],
        [659, 562], [440,  93], [494,  93], [587,  93], [494,  93], [880, 375],
        [554, 187], [587, 280], [554,  93], [494, 187], [440,  93], [494,  93],
        [587,  93], [494,  93], [587, 375], [659, 187], [554, 280], [494,  93],
        [440, 375], [440, 187], [659, 375], [587, 750], [  0, 375],
    ];
    for [freq, dur] in MELODY.iter() {
        int::suppress(|| Timer::beep(*freq));
        let g = &mut *GUARD.enter();
        g.bell_ringer.sleep(&mut g.scheduler, *dur as _);
    }
    GUARD.enter().scheduler.exit();
}