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).
This assignment can be split into the following steps:
- Waitingroom and Semaphores for guarding the keyboard buffer
- Bell and Bellringer
- Idlethreads and putting processors to sleep
- (optional) Tickless Kernel
- (optional) Use the PC-Speaker to create a melody using the functionality of the Bells
Learning Objectives
- Synchronization using semaphores and other core objects
- Waiting passively and idling
Synchronisation and Idling
(A) Semaphore Implementation and Keyboard Buffer
We need the Waitingroom for implementing bells and semaphores. These synchronization objects are characterized by storing the sleeping threads inside them. When a thread sleeps on Semaphore::p() it will be inserted into the queue of threads in the semaphore object. When a thread then calls Semaphore::v() a sleeping thread is awakened.
First, implement the classes Waitingroom, Semaphore, Thread, Scheduler and GuardedSemaphore. With semaphores we an prevent threads from messing with the output of others, if we use them correctly.
Then Keyboard::getKey() can be extended. 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 show that it inserted new data into the buffer. A Thread should be adapted to take on the keyboard input and print them onto the screen.
Make sure, that there are always enough threads ready in the system to keep the processors busy!
(B) 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).
(C) 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 systme to keep all processors busy, we still have to make them do something.
For this, introduce IdleThreads, which let the processor go into sleep mode. An x86-processor will wake automatically, when it receives an interrupt (if they are not masked with cli). The instructions sti; hlt; directly behind each others are executed atomically, ensuring that no interrupt can come between these two instructions. Sleeping threads shall be awakened by Interprocessor Interrupts when new threads get ready.
For testing, starve the system of threads, i.e. less than 4 for MPStuBS or no ready threads for the OOStuBS case.
(D) 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 Watch in the IdleThread.
- Note
- Obviously, you should only switch off all cores if there is no Bell pending in the Bellringer's queue.
(E) 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. 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 withQEMU_AUDIO_DRV=alsa make kvm
