ECE344 - Operating Systems
Assignment 5: Pumbaa Operating System Kernel
Due Date: Sunday, March 25, 2000, 11:59:59pm.
Objectives
The objective of this assignment is to more accurately emulate the operation
of an operating system kernel, where the kernel and user-level code run
in different address spaces.
Procedure
In assignment 4 you implemented a user-level thread package. In this assignment,
you are to separate the functionality that implemented the Pumbaa threads
into a user-level library portion and a kernel portion. Each will run in
separate Unix processes, and a message-passing protocol will be used to
communicate between the two.
Specification
In assignment 4, you were encouraged to split function calls into a upper-level
(i.e. "U_") routine and a lower-level (i.e. "L_") routine. In assignment
5, this split is necessary. The high-level part (modified slightly) will
go into a user-level library, and the low-level part (modified slightly)
will go into the kernel. The two parts will thus reside in different address
spaces and share no data and cannot call each others' routines directly.
One restriction on the kernel-side functions is that they cannot allocate
any memory dynamically with malloc().
The two parts are to communicate via message passing. For this purpose,
a message structure is defined in msg.h:
struct Msg {
int opcode;
int args[4];
};
Such a message can be sent from the user-level library code to the kernel
to request for service (i.e. a kernel call). Also, the kernel can respond
with a message to return the result. On requesting service from the kernel,
the opcode is used to identify which service is required, and
the arguments may contain any other data required for the service. For
example, when requesting that a new thread be created, the message might
be initialized as follows:
msg->opcode = THREAD_CREATE;
msg->args[0] = pc;
msg->args[1] = sp;
msg->args[2] = priority;
Since you are writing this code, you can use whatever protocol you find
appropriate as long as you do not change the message structure.
Code provided to you
A number of routines will be provided to you in binary form here.
For the user-level library:
-
void trap(unsigned target, int requesttype, struct Msg *msg )
trap() first causes target, requesttype
and *msg to be loaded into the registers, and then traps into
the kernel. When the kernel returns from the trap, it has placed a response
message into the registers; this message is copied into *msg,
thus overwriting the original message that was sent. For now, requesttype
should always be set to KERNEL_REQUEST, which you may define as
you wish. (In later assignments, other requesttypes will be added). Target
identifies who the recipient of the message should be. For now it should
always be set to KERNEL, which is to be defined as 0.
This code is made available in trap.o, and
should be linked with pumbaa.c, which contains all other user-level
library code, and usertest.c that contains the test code and main().
The only modifications needed for the U_-routines are that each
must allocate a message structure and initialize it appropriately. Then,
instead of calling the corresponding L_ function directly, it
is called indirectly by calling the trap() function.
For the kernel, the following routines are provided and you must use
them as is:
-
main()
This function first calls K_Init() (which you must provide),
and then simply waits for kernel traps in an endless loop. Whenever a trap
is received, the function handleTrap() is called. You will need
to provide handleTrap(), as described below.
-
getmem(void *ptr, int size, void *buff)
This function allows you to read up to 20 bytes from the user program's
address space. A size-sized chunk of memory is copied from ptr
in the user address space into buff in the kernel.
-
putmem(void *ptr, int size, void *buff)
This function allows you to copy up to 20 bytes from the kernel address
space into the user program's address space. A size-sized chunk
of memory is copied from buff in the kernel to ptr in
the user address space.
This code can be found in kernel.o. Of
course, you will never call main(), and all of the system calls
we have implemented so far can be implemented without requiring the use
of getmem() and putmem(), so you can view their use as
optional, allowing you to add additional, more sophisticated system calls
at a later date.
Code you must provide
In a file ksupport.c, you are to provide for the following kernel
support functions:
-
void K_Init()
Initialize all of the kernel data structures (such as the lists required
and the process descriptors) here. Recall, that any data structure needed
in the kernel must be allocated statically.
-
void handleTrap(unsigned target, int requesttype, void *pc, void *sp,
struct Msg *reqmsg)
target identifies who should be getting the message; at this
time it will always be KERNEL. Requesttype identifies
what type the request is; at this time it will always be KERNEL_REQUEST.
pc contains the value of the program counter of the user-level
thread at the time of the trap, and sp contains the value of the
stack pointer of the user-level thread at the time of the trap. Both pc
and sp are to be stored into Active's thread descriptor.
Finally,
reqmsg contains a pointer to the message passed in from
the user thread. HandleTrap() typically looks at the opcode of
the reqmsg and calls the appropriate L_-level routine.
On return, control will be passed to the Active user thread; it
is up to handleTrap() to set Active to the ready to run
thread with the highest priority just before returning.
As part of handling the trap, a response message must be generated.
Since a thread different from the one that invoked the current "system
call" may be dispatched, it is necessary to store the response message
somewhere before handleTrap() returns. The thread descriptor of
the invoking thread seems to be a very good place for this. Hence, the
thread descriptor needs to be extended as follows:
struct TD {
...
int responseMessageExists;
struct Msg msg;
};
Of course, you may use any field names you desire. The response message
is then to be stored in the thread descriptor before handleTrap()
returns. Note, that in some cases, when control is passed back to a user
thread, no message is passed back (for example, when a thread is newly
started up), while in other cases a message is to be passed back. You will
need to be able to differentiate between the two cases, and adding a field
responseMessageExists
to the thread descriptor is useful for this purpose.
As the final step of handling a trap before returning, the ready-to-run
thread with the highest priority is to be dispatched (by setting Active
accordingly).
void *getActivePC()
Should return the program counter of the Active thread as
stored in the Active thread descriptor.
void *getActiveSP()
Should return the stack pointer of the Active thread as stored
in the Active thread descriptor.
struct Msg *getActiveMsg()
Should return a pointer to the message that should be passed back to
the Active thread. If no message is to be passed back, then getActiveMsg()
should return a 0.
You should also write all the L_-level routines that were required
for assignment 4, such as L_CreateThread(), L_Yield(),
etc... Note that the L_-level routines no longer need to get and
store the PC and SP values, as that is now done by the trap handling code
and the values are passed to handleTrap().
Keeping the abstraction levels separate
Note that after you have implemented this all, there are five different
levels of code:
-
Level 1: The application code.
The application makes system calls, by calling the corresponding library
stub routines of Level 2. Note that this code is contained in the file
usertest.c, and this is the code that will be replaced when
we test your library.
-
Level 2: The library stub routines.
The stub routines may process the parameters in user space to make
them more appropriate for the kernel, and check for errors early. They
then save the processor registers on the stack before trapping into the
kernel. These are the U_-level routines, and they are implemented
in pumbaa.c.
-
Level 3: Low-level trap code.
This is low-level code that traps into the kernel and returns from
exception. That is, the registers are loaded with the system call parameters
before issuing the trap instruction, and it similarly loads the registers
with return data before returning from the trap.
This code is provided for you. It is separated into two parts: level
3a is in trap.o and is code executed in the application address
space. Level 3b is in kernel.o and is code executed in the kernel
address space.
(Of course, since we are running not on raw hardware, but on top of
Unix, we are really only emulating this behavior.)
-
Level 4: Kernel code.
This is the main implementation of the operating system kernel. It
includes all of the L_-level routines and the other functions
outlined above. This is in ksupport.c.
It is important to separate each level into different files. Also, note
that Level 4 and 3b execute in the kernel address space, while level 1,
2 and 3a execute in the application address space (and if you had multiple
application spaces, in each application space independently).
Interaction between the Layers
The interaction between user program and kernel then occurs as follows.
When the user program wishes to issue a CreateThread() kernel
call, it calls the appropriate library routine, U_CreateThread.
This library routine sets up a message and passes it to the kernel via
a trap. When the kernel gets the trap, it calls handleTrap(),
which stores away the PC and SP of the user thread that issued the call,
interprets the message passed in through the registers, and calls the appropriate
kernel routine that is capable of servicing the request, in this case L_CreateThread().
L_CreateThread() does what it has to do, and may possibly change
Active, and then returns. At that point, the kernel returns from
the trap, passing back the response message back if there is one.
The Idle Process
There is no longer an "idle thread" in the application address space. Instead,
you should not return from handleTrap() if there is no thread
ready to run. While you are debugging, it might be useful to have a loop
like this:
while( nothing ready to run ) {
PrintInfoOnEachExistingThread();
sleep(1);
}
Running the Kernel
The trap function being provided to you does not really trap into the kernel;
it just emulates that type of functionality. It does this by sending messages
back and forth between two Unix processes. (Do "man msgctl" and
"man msgsnd".) Because of this, the kernel and application must
be run in a certain way. Call your kernel executable kernel and
your application executable appl.
There are two ways in which you can start the two processes.
-
Have the kernel start up the application automatically by typing "kernel
appl". That is, the name of the application executable is given as
an argument to kernel. (This functionality is already implemented
in the main() routine of the kernel, which is provided to you.
It uses the fork() and exec() Unix system calls.)
-
You can start up each program separately (say in different windows). kernel
will then print out a queue id, which you must then give as input to appl
when it asks for it.
Testing
The same applications that were used to test assignment 4 can be used here.
Also, feel free to implement some of the basic synchronization experiments
of assignment 2. Finally, try determining the overhead (in terms of time)
of a context switch and a kernel call. Beware: These can easily be quiz/exam-type
questions.
Submission
In your home directory, create a directory called ece344; create
a subdirectory called as5 and then in that directory create files
with your code. You should only submit source files. To submit the assignment
you should use the submission procedure described in the policies
section.
This directory should contain a copy of the supplied files trap.o
and kernel.o. It should also contain your source files pumbaa.c,
ksupport.c and any other source or header files you require for
your project. You should also have a sample application usertest.c.
Finally, it must contain a Makefile that will correctly compile
and link two executables: appl (comprised of usertest.c,
pumbaa.c, trap.o and any other support files) and kernel
(comprised of kernel.o, ksupport.c, and any other support
files necessary).
Note: As part of the evaluation of your program, a new usertest.c
file will be used in place of the supplied file. This file will interface
with your thread library using the same conventions as Assignment #4.