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).

Map of important classes for the sixth assignment

Learning Objectives

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

Implementation Notes

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

Waitingroom and Semaphores for guarding the keyboard buffer
Bell and Bellringer
Idlethreads and putting processors to sleep

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. It's 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.