Due Friday, October 14, 2005 (6:00 PM)
This project has two parts:
Queues and Preference Levels. You will augment the existing GeekOS Round Robin scheduling algorithm with a multilevel feedback scheduler (MLF). In Round Robin, all threads sit in a FIFO queue. In the MLF which you will implement, you will use four queues instead of one. Each queue is assigned a scheduling preference level, i.e. all threads in the same queue have the same preference level. The queues will be numbered 0 through 3, with 0 being the most preferred, and 3 being the least. For this reason, s_runQueue in kthread.c has changed from being a struct to being an array of structs, one for each preference level. Note that the queue scheduling preference level is distinct from the kthread priority field; the latter is used to choose which thread to run within a given queue (see below). Moreover, the highest preference level queue is numbered 0, while 0 is the lowest priority for a thread within a queue at a given level (see kthread.h).
A newly created thread will be placed on the most preferred
queue (i.e., 0). Each time a thread completes a full quantum, it should
be placed
on the run queue with the next lowest preference level, until it
reaches
level 3, at which point it can not go any lower. Hence,
CPU-intensive
threads
will eventually end up in the least preferred queue.
When a thread becomes blocked (namely, in Wait), it has to go
into a higher preference level queue. In this project, the
kthread struct has been extended with a field currentReadyQueue
which indicates the queue the thread should go on when it is ready to
run. Thus, this field should be decremented when a thread is
about to block, and incremented when it uses a full quantum. Make_Runnable
will insert a thread in the appropriate queue for you.
Scheduling Algorithm. To schedule a thread to run, look at the highest preference level queue. If there are threads there, choose the highest priority (i.e. highest numbered) process in the queue. If there are no threads there, go to the next lowest preferred queue, and keep repeating until you find a thread. Scheduling always attempts to look at the highest preferred queue and work down. This may mean low preference level processes are starved. You will need to handle the case of the Idle thread specially. It should be placed on the lowest level queue and should never be permitted to move out of that level.
You might want to look at the scenarios to better understand how you should implement MLF.
Switching
Between Round Robin and MLF. Your operating system should
be able to select which scheduling
algorithm is being used via a system call: the system call int
Set_Scheduling_Policy(int policy, int quantum) should be
implemented for this purpose. If the value of policy is 0, the system
should
switch to round robin scheduling,
if the policy is 1,
the system should switch to MLF.
Other values of this parameter should result in an error code being
returned (i.e. a -1 return value). The value of the quantum parameter
should be the number of ticks that a user thread may run before getting
removed from the processor. To implement the tunable quantum, you will
have to modify g_Quantum in timer.c to the value quantum
that's passed
as argument to Set_Scheduling_Policy(). Allowed values for
the quantum are integers in the
interval [2,100]. This will prevent the OS from switching too often
(too low quantum) or starving other runnable processes (too high
quantum).
When the system boots up, it will have to use MLF. So don't
forget to set MLF as the initial scheduler.
The choice of which scheduler to use should be made within the
function Get_Next_Runnable() (see kthread.c). Any
function that calls Get_Next_Runnable() should be unaware of
which scheduling algorithm is being used (i.e., do not try to pass the
scheduling type as an argument). It should only be aware that some
thread has been selected.
Get_Time_Of_Day() will return the value of the kernel
global variable g_numTicks. The variable is already
implemented
in the kernel (see timer.h), you only need to implement the
system call to read it.
You can use this system call in a user program to determine how much
time has elapsed while the program was running. You can do this by
calling
Get_Time_Of_Day() once at the beginning of the process
(in the user code) and once at the end. You can calculate how long the
process took to run, as well as when the process first got scheduled
(based
on ticks). Notice that there is no attempt to remove time spent by
other processes. For example, if your process context switches out,
then a
second process runs, the second process's time during the context
switch will be
included in the first process's elapsed time. This is known as "wall
clock"
time. One can also just calculate the time used by the process itself.
This is called "process time" (or sometimes virtual time) but
you
do not need to care about it in this project.
Additional Reading. Scheduling is covered in Chapter 5 of the text. Multi-level feedback scheduling is covered in Section 5.3.6, pps. 168-169. (In this project the quantum is identical for all four queues.)
You will add system calls that provide user programs with
semaphores, to enable thread synchronization among different threads.
The systems calls (on the user side) will be:
int Create_Semaphore(const char *name, int ival)
int P(int sem)
int V(int sem)
int Destroy_Semaphore(int sem)
Create_Semaphore(name, ival) is a request by the current
process to use a semaphore. The user
gives a name for
the semaphore, as well as the semaphore’s initial value, and will get
back a semaphore ID, an
integer between 0 and N - 1. The semaphore ID denotes a particular
semaphore datastructure in the kernel, which you must implement.
The semaphore ID is then passed by the user program to the operations
P() and V(), described next, to wait or signal the associated
semaphore.
Your operating
system should be able to handle at least 20 (thus N =
20) semaphores whose names may be up to 25 characters long. If
there are no semaphores left
(i.e., there
were 20 semaphores with unique names already given), -1
must be returned indicating an error.
The returned semaphore ID is chosen in one of two ways.
The P(sem) system call is used to decrement the value of
the semaphore associated with sempahore ID sem. This operation is
referred to as wait() in the text. Similarly, the V(sem)
system call is used to increment (signal() in the text) the value of
the semaphore associated with sem.
As you know, when P() is invoked using a semaphore ID whose associated semaphore's count is less than 0, the invoking process should block. To block a thread, you can use the Wait function in the kernel. Each semaphore data structure will contain a thread queue for its blocked threads. The file thrqueue.h provides an implementation of a thread queue. You should look at kthread.h and kthread.c to see how it is declared and used. To wake up one thread/all threads waiting on a given semaphore, i.e. because of a V(), you can use Wake_Up_One()/Wake_Up() routines from kthread.h.
A process may only legally invoke P(sem) or V(sem) if sem was
returned by a call to Create_Semaphore for that process (and the
semaphore has not been subsequently destroyed). If this is not
the case, these routines should return back -1.
Destroy_Semaphore(sem) should be called when a process is
done using a semaphore; subsequent calls to P(sem) and V(sem) (and
additional calls to Destroy_Semaphore(sem) by this process) will return
-1.
In this, and other projects, you will rely heavily upon a list data structure. For this reason an implementation has been provided to you in list.h file. Please familiarize yourself with its syntax and functionality. It could be a little tricky to understand the syntax since functions are written using #define. Naturally you are always free to extend, modify, or write your own implementation that would better suit your needs.
Additional Reading.
Semaphores are covered in Chapter 6, Section 6.5, of the text;
pps. 202-204 describe implementation issues.
| Identifier | Kernel Function | User Function | Effect |
| SYS_SETSCHEDULINGPOLICY | int Sys_SetSchedulingPolicy(struct Interrupt_State* state) | int Set_Scheduling_Policy(int policy, int quantum) | if policy is 0 or 1 and 2 <= quantum
<= 100
switch to that scheduler, setting MAX_TICKS accordingly; else return -1 |
| SYS_GETTIMEOFDAY | unsigned long Sys_GetTimeOfDay(struct Interrupt_State* state) | unsigned long Get_Time_Of_Day() | return g_numTicks |
| SYS_CREATESEMAPHORE | int Sys_CreateSemaphore(struct Interrupt_State* state) | int Create_Semaphore(const char *name, int ival) |
if name is longer than 25 characters, return -1
if a semaphore with this name doesn't exist, create it and return its SID; if it exists, return its SID; note that SID must be >= 0 |
| SYS_P | int Sys_P(struct Interrupt_State* state) | int P(int sem) | might block wait() semantics returns -1 if sem invalid returns 0 on success |
| SYS_V | int Sys_V(struct Interrupt_State* state) | int V(int sem) | never blocks signal() semantics returns -1 if sem invalid returns 0 on success |
| SYS_DESTROYSEMAPHORE | int Sys_DestroySemaphore(struct Interrupt_State* state) | int Destroy_Semaphore(int sem) | never blocks returns -1 if sem invalid returns 0 on success |
The files we provided can be used to test your semaphores or scheduling algorithm:
% /c/workload.exe [algorithm] [quantum]
where algorithm can take any of the values rr or mlf
and quantum is the scheduling algorithm's quantum.
% /c/ping.exe &
% /c/pong.exe
In addition to the code, you should run several tests on the supplied application workload.exe, varying the quantum length as well as the two scheduling algorithms. At minimum try running the system with the inputs of:
% /c/workload.exe rr 2
% /c/workload.exe rr 100
% /c/workload.exe mlf 2
% /c/workload.exe mlf 100
In your proj3 directory add a file called INTERPRETATION listing the results, as well as explaining why the results occurred. This exercise is meant to let you consider the effects of quantum length and scheduling algorithms on the run of several processes. The proj3.tar.gz that you submit must include this file as well.
$ cd ~/project2/src/geekos $ diff -u -r . ~/project2-solution/src/geekos > ~/diff.patch
$ cd ~project3/src/geekos $ patch -p0 < ~/diff.patch $ rm *orig