Aufgabe 6: Synchronisation

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

Create the following synchronization objects:

• 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.
• Bell to put threads to sleep for a certain period of time.

Create a Waitingroom (containing Threads waiting for events) and the Bellringer (efficiently checking for Bells to activate) for this purpose. You'll have to modify Scheduler, Thread, Keyboard and Watch, and create the system call wrappers GuardedBell, GuardedSemaphore and GuardedKeyboard.

To cut power usage, a core should sleep (using the hlt instruction) if no threads are waiting for their execution. Since only interrupt handling routines will activate threads, the execution should be continued if there are new threads in the ready list after an interrupt. You can achieve this behaviour by introducing idle threads (exclusively dedicated to each core). They are scheduled as soon as there are no threads in the ready queue and perform the idle loop.

For MPStuBS, it is 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(Thread *that) and the Assassin).

Learning Objectives

• Synchronization using semaphores and other core objects
• Waiting passively and while idling

Videos (WS21, in German)

• Gegenseitiger Ausschluss (7 min)
• Zeitgesteuertes Warten (5 min)
• Aufgabe 6 (8 min)

Implementation Notes

We recommend the following order to allow good separate testing of the individual parts:

1. Waitingroom and Semaphores for guarding the keyboard buffer
2. Bell and Bellringer
3. Idlethreads and putting processors to sleep
4. (optional) Tickless Kernel and/or PC-Speaker

Semaphore Implementation

It is best to start with Waitingroom: We need it for implementing bells and semaphores. These synchronization objects are characterized by storing the sleeping threads inside them: If a thread will sleep due to Semaphore::p(), it is inserted into the internal thread queue. When another thread calls Semaphore::v(), a sleeping thread from this queue gets awakened.

Using semaphore variables, you should be able to prevent your application threads from interfering with each other during screen output.

Blocking Keyboard Input

In the next step, you can extend the Keyboard with the getKey() method. The method uses a Semaphore to access the buffer, forcing threads to wait when no Key to retrieve is present. A subsequent keyboard interrupt uses the Semaphore to notify about the new key stroke in the buffer (by waking up the Thread). Extend your Application in such a way that one thread queries the Keyboard (and prints its result).

Do not forget to add a GuardedKeyboard which shall be used by your application.

Time Events using the Bell

Afterwards, you can start working on Bellringer. Check the correct behaviour of all possible cases: insertion at the front, back, somewhere in the middle, empty list, etc. Watch should frequently make calls to the global Bellringer instance's Bellringer::check() method. Having the Bell (or rather GuardedBell), it is quite 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, and print a counter at a fixed location).

Bellringer::check() is called from the Watch. How many cores will call Bellringer::check() in MPStuBS? Is this desirable? Think about a solution.

Idle Thread

The previous steps make more and more threads wait passively, so the system needs to schedule other threads. Waiting threads can't be scheduled for the time being. If there are not enough threads in the system to keep all processors busy, we still have to make them do something.

It is finally time to address the idle core problem: We introduce IdleThreads, which let the processor go into sleep mode. An x86-processor will wake automatically when it receives an interrupt (unless they are masked with cli). Have a look at Core::idle() - the instructions sti; hlt; directly behind each others are executed atomically, ensuring that no interrupt handler will interfere. An IdleThread shall be scheduled if no other thread is ready. Its sole purpose is to make a core idle with interrupts enabled. It should not be enqueued in the ready list.

For MPStuBS, sleeping cores shall be awakened by Inter-Processor Interrupts (IPI) when new threads get ready. Hence, a core's IdleThread has to ask the Scheduler if new threads are ready. Keep in mind that the latter operation has to be performed atomic with respect to interrupts. If there are threads to be scheduled, the idle thread shall trigger the Scheduler.

Include test scenarios in your example application with too few (in MPStuBS) or no threads available for execution.

Tickless Kernel (Voluntary)

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 Watch in the IdleThread.

Note

Obviously, you should only switch off all cores if there is no Bell pending in the Bellringer's queue.

PC Speaker (Voluntary)

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. PIT::pcspeaker() provides you with an interface to set the desired frequency (preferably with interrupts disabled). The speakers should then skril accordingly, 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 goes to sleep for a given time before switching to the next frequency.

Note

Actually, the PIT is comparatively easy to handle, the difficulty here lies rather in the test environment: Usually, Qemu/KVM will remain silent. A remedy is the (rather poorly documented) environment variable QEMU_AUDIO_DRV – try starting with QEMU_AUDIO_DRV=alsa make kvm

Further Reading

• Overview of files and classes
• List of mandatory and voluntary tasks