Assignment 10, Solutions
Part of
the homework for 22C:116, fall 2002
|
Note that this set of primitives doesn't require the use of a link table because we allow links to be stored intermixed with normal variables. Note also that the queue table is not necessarily implemented as an array of queues! It is an abstraction which may have additional complexity.
Part A: If it were not for the queueselect service, there would be many ways to implement this set of primitives. Therefore, you must begin your implementation by working out a feasible implementation for queueselect, using semaphore operations for synchronization, plus whatever other data structures are required to make it work. Propose a solution.
Because queueselect blocks until a message is delivered to any subset of the queues in a queue table, delivery of a message to any such queue must signal the same semaphore. Therefore, all messages sent over a link to a queue in a particular queue table must actually be enqueued in the same master queue. When the receiver blocks, it will always block awaiting a message in this master queue. If the message is addressed to the wrong specific queue, the receiver will put the message in the specific queue and try again. In a bit more detail, this gives us something like this for the select operation:
queueselect( q, n, l ):
-- first see if the message is already available
for i in 0..l-1 do
if not empty( q.queues[n[i]] ) return n[i]
endloop
-- the message not already received
loop
threadwait(q.mastersem)
m = dequeue(q.masterq)
enqueue( m, q.queues[m.queuenumber] )
for i in 0..l-1 do
if m.queuenumber = n[i] return n[i]
endloop
endloop
Part B: Give the header file that gives the interface specification for this package. This should conform to the style guidelines referenced from the class web page, and it need not attempt to hide the implementation of the data structures from the reader.
/* demos.h */
/******************************************************
* Demos like message passing interface specification *
******************************************************/
/******************************************************
* Prerequisites for use *
* The user must include "threads.h" *
******************************************************/
/******************************************************
* Private types that users really shouldn't see *
******************************************************/
struct msg {
struct msg * next; /* next message in queue */
/* description of the message itself */
void * buf;
int len;
/* needed to inform the sender of message delivery */
thread_semaphore * sem;
void * returnval;
};
struct queuetab;
struct msgqueue {
/* standard linked-list FIFO queue implementation */
struct msg * head;
struct msg * tail;
/* you may need to add something here */
};
/******************************************************
* Types required for the interface *
******************************************************/
struct queuetab {
thread_semaphore mastersem;
struct msgqueue masterqueue;
int queues;
struct msgqueue[ 1 /* see note below */ ];
/* actual array size will be queues elements */
};
typedef link; /* details depend on your implementation */
/******************************************************
* The Interface *
******************************************************/
int send( link dst, void * buf, int len );
/* send a message
given: dst, the link over which the message is sent
buf, a pointer to the buffer to send
len, the length of the buffer, in bytes
returns: the number of bytes actually delivered
note: returns -1 if the message cannot be delivered
*/
int receive( struct queuetab * t, int num, void * buf, int len );
/* receive a message
given: t, the queue table context to use
num, the queue number in that context
buf, a pointer to the buffer to receive into
len, the length of the buffer, in bytes
returns: the size of the sender's buffer
note: returns -1 if the message cannot be delivered
*/
int queueselect( struct queuetab * t, int * num, int len );
/* block until a message can be received
given: t, the queue table context to use
num, pointer to first element of array of queue numbers
len, the number of queue numbers in the array
returns: the queue number in which a message is waiting
note: what if none of the queue numbers are valid?
*/
struct queuetab * newqueuetable( int len );
/* allocate a new queue table
given: len, the number of queue numbers in the table
returns: a pointer to the new table
*/
link newlink( struct queuetab * t, int num );
/* make a new link
given: t, the queue table context to use
num, queue number in that table the link should reference
returns: a link to that queue
note: an invalid link will be returned if num is out of bounds
*/
Notice: The complete implementation of these functions will be assigned in next week's homework.
The send and receive primitives establish a short-lasting session as they exchange a message. This is a necessary consequence of the non-blocking semantics of message passing in this system.
If mintriptime had been constant, it would need to be carefully tuned. The algorithm presented is adaptive, learning the best trip time by observation and then using it. The mintriptime variable decreases whenever a new shorter trip time is encountered. It increases slightly each time a new minimum is not encountered. If it were not increased slightly, the clocks would only be synchronized when a new minimum is encountered, and after the first few tries, new minima would probably be very rare.
When the user wants to unblock the agent, the user enables the interrupt or enables the signal handler. When the user wants to block the agent, it disables that interrupt or signal handler. The agent can signal the user using a normal semaphore mechanism, but the thread-signal operation from a signal handler or the kernel-level signal from an interrupt service routine must not do any context switching (our thread package has this property, but if the signal operation did a relinquish, it would not be safe for this application).