CSCE–410/611/613
Introduction
Kernel-Level Thread Scheduling
In this machine problem you will add scheduling of multiple kernel-level threads to your code base. The emphasis is on scheduling. The test code for this MP (file kernel.C) illustrates that a scheduler is not necessary for multiple threads to happily execute in a system. For example, the following code displays two routines (each executed by a different thread) that explicitly hand the control back and forth, and so achieve a simple form of multithreading:
void fun1() {
console_puts("FUN 1 INVOKED BY THREAD 1\n");
for(;;) {
< do something ... >
thread_dispatch_to(thread2);
}
}
void fun2() {
console_puts("FUN 2 INVOKED BY THREAD 2\n");
for(;;) {
< do something ... >
thread_dispatch_to(thread1);
}
}
In this piece of code the CPU is passed back and forth between Thread 1 and Thread 2. And this works fine, until we want to add a third thread. Do we really want to modify the code of fun2() to dispatch Thread 3 on the CPU? And does the programmer of Thread 3 really want to know that the CPU needs to be dispatched back to Thread 1? What if she does not want to release the CPU at all? So, we cannot rely on the threads to play nice, and we need a third party that allocates the CPU on behalf of the running threads: We need a scheduler. The interface of the scheduler is defined in file scheduler.H. It exports the following functionality:
class Scheduler {
public:
Scheduler();
/* Setup the scheduler. This sets up the ready queue, for example.
If the scheduler implements some sort of round-robin scheme, then the
end_of_quantum handler is installed here as well. */
virtual void yield();
/* Called by the currently running thread in order to give up the CPU.
The scheduler selects the next thread from the ready queue to load onto
the CPU, and calls the dispatcher function defined in class Thread to
do the context switch. */
virtual void resume(Thread * _thread);
/* Add the given thread to the ready queue of the scheduler. This is called
for threads that were waiting for an event to happen, or that have
to give up the CPU in response to a preemption. */
virtual void add(Thread * _thread);
/* Make the given thread runnable by the scheduler. This function is typically
called after a thread has been created. Depending on the
implementation, this may not entail more than simply adding the
thread to the ready queue (see Scheduler::resume). */
virtual void terminate(Thread * _thread);
Ver. 2018C
Page 1
Machine Problem 5
Machine Problem 5:
CSCE–410/611/613 Machine Problem 5
Remove the given thread from the scheduler in preparation for destruction
of the thread. */
};
You are to implement a simple First-In-First-Out (FIFO) scheduler. This is very easy to achieve: The scheduler maintains a so-called ready queue, which is a list of threads (or, better, their thread control blocks) that are waiting to get to the CPU. One thread is running on the CPU, typically. Whenever a running thread calls yield(), the scheduler finds the next thread to run at the head of the ready queue, and calls the dispatcher to invoke a context switch. Whenever the system decides that a thread, say Thread t1, should become ready to execute on the CPU again it calls resume(t1), which adds t1 to the end of the ready queue. Other threads may be waiting for events to happen, such as for a page fault or some other I/O operation to complete. We call these threads blocked. We don’t worry about blocked threads for now, as all the threads are either busy executing or waiting on the ready queue. Later, when threads access devices, we will have to deal with blocked threads as well.
Implementation of the Scheduler
You realize the scheduler by implementing the exported functions (declared in file scheduler.H) inside a file called scheduler.C. Implement primarily the constructor and the functions yield(), add(), and resume(). When you are ready to handle terminating thread functions, you may want to implement the function terminate() as well.
Depending on how you want to implement the ready queue, you may have to modify the thread control block in thread.H.
Testing your Scheduler
The file kernel.C is set up to make testing of your scheduler easy. The file creates four threads, each of which is assigned a different function – called fun1 for Thread 1 to fun4 for Thread 4. These thread functions call a function pass on CPU() to explicitly dispatch the next thread on the CPU in the way described above. A macro USES SCHEDULER defines how control is passed among threads in file kernel.C. If the macro is defined, then the code makes use of the scheduler to hand control from one thread to the next. For details, look at the source code in kernel.C.
Threads with Terminating Thread Functions
Currently, all thread functions in kernel.C are non-terminating (basically infinite loops). They only stop executing when they pass control to another thread. The system at this point does not know what to do when the thread function returns. In other words, there is no support in the low-level thread management for threads with thread functions that return and therefore stop to execute. You are to study the thread management code and propose and implement a solution that allows a thread to cleanly terminate when its thread function returns. You need to worry about releasing the CPU, releasing memory, giving control to the next thread, etc. Test your solution by making the thread functions in kernel.C return. You can easily do this by modifying the for loops to have an upper bound. For example, modify the lines for(int j = 0;; j++) to read for (int j = 0; j < DEFAULT NB ITERS; j++) or similar. A macro TERMINATING FUNCTIONS defines whether the thread functions for the first two threads terminate after 10 iterations or not. For details, look at the source code in kernel.C.
Ver. 2018C Page 2
CSCE–410/611/613 Machine Problem 5
Opportunities for Bonus Points
If you want to extend your work beyond the bare minimum, here are a few options.
OPTION 1: Correct handling of interrupts. (This option carries 15 bonus points.) You will notice that interrupts are disabled after we start the first thread. One symptom is that the periodic clock update message is missing. This is caused by the way we create threads: We set up the context so that the Interrupt Enable Flag (IF) in the EFLAGS status register is zero, which disables interrupts once the created thread returns from the fake ”exception” when it starts. This is ok, because we may not want to deal with interrupts when we are just starting up our thread. But at some point we need to re-enable interrupts. And turn them off again when we need to ensure mutual exclusion. It is up to you to modify the code in the scheduler and the thread management to ensure correct enabling/disabling of interrupts. The functions to do that are provided in machine.H.
OPTION 2: Round-Robin Scheduling: (This option carries 15 bonus points.1) Once we have interrupts set up correctly, we can expand our simple FIFO scheduler into a basic round-robin scheduler. For this, we want to generate an interrupt at a periodic interval (say 50 msec). This can be done by either modifying or replacing the interrupt handler for the simple timer. The new interrupt handler triggers preemption of the currently running thread. During the preemption the currently running thread puts itself on the ready queue and then gives up the CPU.
If you think this is just a resume() followed by a yield(), think again. The situation is a bit more complicated than that. For example, the current thread is giving up the CPU inside an interrupt handler, and the new thread may or may not be returning from a preemption, and therefore may or may not be returning from an interrupt handler. In both cases we need to let the interrupt controller (PIC) know that the interrupt has been handled. In addition, we need to stop the original thread from informing the PIC when it returns from the interrupt possibly much later. It is very likely that you will need to modify the low-level exception and interrupt handling code to get this to work correctly.
OPTION 3: Processes: (This option carries 20 bonus points. 2) Until now, all threads share the same address space. Extend the system to allow for the creation of threads that have different address spaces; basically, implement processes. If you plan to attack this option, you will have to handle a number of different aspects, including creation of multiple address spaces (multiple page tables,) and switching from one address space to another as part of the thread switch. The code for the thread switch needs to be somewhat extended to handle the switch from one page table to the other. We keep the specification of this option intentionally vague in order to have you come up with your own design. Again: Do not underestimate the difficulty of this option!
A Note about the new Main File
The main file for this MP is somewhat similar in nature to the earlier MPs. We have removed page tables and paging, and we have added code to initialize threading, for scheduling, and for creating a small number of threads.3
1Attack this problem only after you have convinced yourself that you are managing interrupts correctly. Otherwise you will waste a lot of time debugging!
2This option is very challenging and only for students who feel totally under-challenged. Contact the instructor before starting on this option!
3Students who decide to attack Option 3 will have to add paging and page tables back in to test their approach.
Ver. 2018C Page 3
CSCE–410/611/613 Machine Problem 5
The Assignment
- Download the provided source code for this MP.
- Implement the routines defined in file scheduler.H (and described above) to initialize the scheduler, to add new threads, and to perform the scheduling operations.
- You may need to modify file scheduler.H. If so, document how and why.
- Modify file kernel.C to replace explicit dispatching with calls to the scheduler. This can be done by uncommenting the definition of macro USES SCHEDULER that enables scheduling. Details about how to do this are given in file kernel.C.
- Add support for threads with terminating thread functions. This may require modifications to file thread.C. If so, document how and why. Test your solution by uncommenting the definition of the appropriate macro in file kernel.C.
- If you decide to pursue one or more of the options, proceed as follows.
Option 1 Fix the interrupt management so that interrupts remain enabled outside of critical sections.
Option 2 Modify the scheduler to implement round-robin with a 50 msec time quantum. (Note: Since the preemption interrupt arrives periodically, this is not a very good round- robin scheduler. Whenever a thread gives up the CPU voluntarily, the next thread is short-changed.)
Option 3 Contact the instructor to discuss your plan to implement multiple address spaces. Modify the thread creation, page table initialization, and thread switching to allow for multiple address spaces. Add page tables back into the code and exercise your new system. It will be up to you to come up with a design, the implementation, and the test suite for your solution.
What to Hand In
You are to hand in the following items:
• A ZIP file, with name mp5.zip, containing the following files:
- A design document, called design.pdf (in PDF format) that describes your design and the implementation of the FIFO scheduler, and any of the selected options. Clearly identify at the beginning of your design document and in your submitted code which options you have selected, if any.
- Two files, called scheduler.H and scheduler.C, which contain the definition and imple- mentation of the functions to initialize the FIFO scheduler and to execute the scheduler operations.
- Two files, called thread.H and thread.C, which contain the modified definition and implementation of the thread description block. Document what changes you have made to the original files, and why.
- Submit any other modified file, and clearly identify and comment the portions of code that you have modified.
Ver. 2018C
Page 4
CSCE–410/611/613 Machine Problem 5
Grading of these MPs is a very tedious chore. These handin instructions are meant to mitigate the difficulty of grading, and to ensure that the grader does not overlook any of your efforts.
Failure to follow the handing instructions will result in lost points.
Ver. 2018C
Page 5