Due Date: Sunday, April 8, 2001, 11:59:59pm.
The objective of this Assignment is to extend the code you wrote for Assignment 5 to add message passing capabilities. Specifically, you will add additional library functions that enable threads to send and receive messages to and from any other thread. In addition, you will design a program that thoroughly tests this message passing facility.
To implement message passing, you will need to add three new system calls. At the application-level, these are:
All data structures and definitions are as specified in Assignment 5 with the following additions:
#define SENDERROR -5 #define REPLYERROR -6
The message scheme you are to implement for this Assignment should be based on a synchronous send-receive-reply policy. This means that if thread T1 executes a U_Send() to thread T2, then T1 must be blocked until two events take place: first, thread T2 must receive the message by calling U_Receive(), and then T2 must form a response to the message and reply to the sender with U_Reply(). Only when T2 calls U_Reply() will T1 be unblocked. Note that in the case where T2 happens to call U_Receive() before T1 calls U_Send(), T2 would be blocked waiting for a thread to U_Send() it a message. The fact that U_Send() and U_Receive() can cause blocking complicates the implementation of these functions somewhat.
To support synchronous message passing, you will need to add some data members to your TD structure. You will need two linked lists as well as space for the return value (i.e. int, ThreadId, and int, respectively):
struct TD {
...
struct LL *SendBlocked; /* new */
struct LL *ReceivedBlocked; /* new */
int returnValue; /* new */
};
SendBlocked is a list that contains TDs of threads that have sent a message to this thread, but whose messages have not yet been received by the thread. ReceivedBlocked is a list that contains TDs of threads that have sent a message to this thread and whose messages have been received but not replied to. (Note that it is possible for a server thread to receive multiple messages before responding to them.) All of those threads that have sent messages that have not yet been replied to are blocked. But instead of being in a global blocked list, their TDs are enqueued onto the target thread's TD. In contrast, any thread that becomes blocked as a result of U_Receive(), waiting for another thread to send it a message, is enqueued onto the global blocked list until it receives a message, at which point it is put back on the ready queue.
You will also need to add a new function in the kernel:
int getActiveReturnValue() ;
that is used similar to the way
void *getActivePC() void *getActiveSP() struct Msg * getActiveMsg()
are used. It is called by the trap handling code just before passing control back to the application thread being dispatched.
Also, trap() has been changed to return an int value; that is, the interface of trap() has been changed from
void trap(unsigned target, int requesttype, struct Msg *msg)
to
int trap(unsigned target, int
requesttype, struct Msg *msg)
To get a better idea of what needs to be implemented, consider in more detail what could happen when two threads communicate using the synchronous message passing model. Assume thread T1, with tid 1, wants to send a message to Thread T2 with tid 2. At the application level, U_Send( 2, &messageA) gets implemented by passing the target tid (2, in this case), the requesttype SEND and messageA to trap, which traps to the kernel, passing these arguments in registers. In the kernel, the sequence of events that occur would be as follows: T1 (currently the Active thread) executes the call L_Send( 2, &msg ), causing the message contents be stored in T1's TD, and T1 to be removed from Active and placed onto T2's SendBlocked queue. Then, T2 (assuming it is now the Active thread) executes U_Receive(&MessageB)at the application level. In the kernel, L_Receive():
T2 later calls U_Reply( 1, &Replyessage) that in turn calls trap(1,REPLY,...). In the kernel, L_Reply() will copy ReplyMessage into T1's TD, remove T1's TD from T2's ReceivedBlocked queue, and return both T1's and T2's TD to the ReadyQueue. Then, when T1 is dispatched, the message in its TD is copied to overwrite MessageA. The following paragraphs provide more details:
int U_Send(ThreadId tid, struct Msg *msg)
At the application level, the code in U_Send() should approximate the following:
int U_Send(ThreadId Tid, struct Msg *msg)
{
volatile int retVal;
SAVE_REGS();
retVal = trap(tid, SEND, msg);
RESTORE_REGS();
return retVal;
}
(Note the "volatile" keyword in the declaration of retVal. That forces retVal to be stored in memory instead of a register, so it won't be clobbered by RESTORE_REGS.)
On the kernel side, you will have to extend handleTrap() to handle the request types SEND, RECEIVE and REPLY:
...
case SEND:
...
L_Send(...) ;
break;
case RECEIVE:
...
...
The behavior of L_Send() depends on whether or not the thread that is to receive the message is already blocked (because it called Receive() before the sender called Send()) or not. If it is blocked, the target thread must be unblocked and set up so that it can be dispatched such that the appropriate return values and message are returned, and the invoking thread descriptor must be enqueued on the ReceivedBlocked list. If the target thread is not blocked, the invoking thread descriptor only needs to be enqueued onto the target thread's SendBlocked list. An outline of code that might be used for L_Send() is:
L_Send(ThreadID targetTid, struct Msg *msg)
{
struct TD *td;
td = TDlookup(targetTid); /* some function that give TD for a tid */
if (!td) {
/* do stuff to handle the error
* - set Active's returnValue to SENDERROR so it can be returned
* when the thread is next dispatched
* - put Active on the ReadyQueue
* - set Active to NULL */
}
/* td now points to the TD of the send target */
/* check if thread pointed to by td is already blocked */
if (/* td is blocked */) {
/* Set *td up so that when it is dispatched it will properly
* return as if from L_Receive; that is, copy Active's tid
* into the returnValue field of *td, and copy *msg into the
* message field of *td. Then, add *td to the ReadyQueue,
* add Active (the sender) to the ReceivedBlocked queue of *td,
* and set Active to NULL */
} else { /* *td is not already blocked */
/* Copy *msg into Active's message field,
* add Active to *td's SendBlocked list,
* and set Active to NULL */
}
}
/* Note: In handleTrap(), the last step should be dispatching the next
* thread that is ready to run */
ThreadId U_Receive(struct Msg *msg)
The code for U_Receive() and L_Receive() are in similar to the corresponding Send()functions. In the case of L_Receive(), it is necessary to differentiate between the case where there is already a SendBlocked thread and the case where there is not. For example, L_Receive() might be similar to:
L_Receive()
{
struct TD *td;
td = DequeueHead(Active->SendBlocked);
if (!td) {
L_BlockThread(); /* wait for a sender thread */
/* once a sender comes along, it will unblock the thread
* and set everything up so that a message and return value
* are returned */
} else {
/* td points to thread to receive from.
* copy message from *td to *Active,
* enqueue *td onto Active's ReceivedBlocked list,
* set Active's returnValue to td->tid,
* put Active back onto the ReadyQueue, so that it can be
* dispatched (at which point it will get the message and return value),
* and set Active to NULL */
}
}
int U_Reply(ThreadId tid, struct Msg *msg)
Again, U_Reply() will be similar to U_Send(). Given the above descriptions of L_Send() and L_Receive(), it should be apparent how to implement L_Reply():
int L_Reply(ThreadId tid, struct Msg *msg)
{
struct TD *td ;
td = TDlookup(targetTid); /* some function that gives TD for a tid */
if (!td) {
/* ... handle error condition:
* set Active's returnValue to REPLYERROR so it can be
* returned when the thread is next dispatched
* put Active on ReadyQueue.
* set Active to NULL.
*/
}
/* td now points to the TD of the originally sending thread
* but to make sure, check if *td is in Active's ReceivedBlocked list.
* If not, we return an error to Active
*/
if( /* (td = Dequeue from Active's ReceivedBlocked queue) == NULL */ )
{
/* not there, so we need to return an error to Active */
/* Active->returnValue = error code...
* put active on ready queue
* set Active to NULL
*/
}
else
{
/* set *td's returnValue to OK so that it
* gets returned when td's Send returns
* copy *msg into the message field of *td
* put *td onto the Ready Queue
* set Active's returnValue to OK
* put Active onto Ready Queue
*/
}
...
}
Notice that L_Reply() copies the response message into the Message fields of *td. This allows the response message to be copied back into the application level when this thread is next dispatched. Also note that L_Reply() must check through its SendBlocked queue for *td, rather than just dequeueing the head of the queue. This is because, in general, a thread may execute multiple calls to U_Receive() before it executes a call to U_Reply(), and may therefore have received messages from more than one thread.
There are a couple of things worth noting. First, the kernel calls, implemented in Assignment 5 (i.e. CreateThread(), Yield(), etc.) are effectively implemented by passing messages to the kernel, and the kernel is effectively behaving as a server process continuously receiving messages and servicing them one by one. Hence, Send(), Receive(), and Reply() can be viewed as the primitive operations on which everything else is constructed.
Second, the values returned by Send(), Receive(), and Reply() relate only to the passing of messages, and not the services requested in the messages. The users of the message passing facility (including the kernel) return their responses in the message itself.
Finally, with Send(), Receive(), and Reply() there are now a few additional cases where no message is passed back to the invoking thread when it is dispatched. For example, Reply() does not return a message. Moreover, if Send() and Receive() result in errors, then no message will be returned either.
You are to write a minimal application that fully tests the message passing facility. This code should test every possible combination of situations that may occur when threads communicate via message passing. This code should be named usertest.c and will be evaluated in addition to the rest of your code.
In your home directory, create a directory called ece344; create a subdirectory called as6 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, must have 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 may be used in place of the supplied file. This file will interface with your thread library using the conventions of Assignments 4, 5, and any new functions introduced in this assignment.