CMSC 412 Project #6

Message Passing

Due Tuesday, Dec 13, 2005 (6:00 PM)

  • Grading Criteria
  • Submission Instructions
  • Slides used in recitation
  • New project files

    None of the projects 0..5 are required for this project, so you are free to start building on top of whichever project you like. Having implemented semaphores correctly in project 3 will make your job easier, since there are a lot of similarities between this project and semaphore implementation in project 3.

    We provide two options for starting a base project 6 kernel. You can choose whichever option you find easier.

    1. This option is probably the faster one. Follow these steps to incorporate the project 6 stuff into whatever working project you prefer.
    2. Start project 6 on top of this project6.tgz distribution, then follow the steps in the Introduction of Project 5 and Final Notes of Project 3 for merging your sources. The project6.tgz distribution is nothing but a project 2 base kernel, plus the additions/changes listed in the option 1 above.


    The purpose of this project is to add communication via message passing to GeekOS.

    To better understand the concepts behind this project, you might want to review section 3.4.2 in the textbook first.

    Message passing allows processes to communicate by sending messages.   In this project, those messages will be sent via message queues.  You can think of the message queues as mailboxes (heretofore we'll use message queue and mailbox interchangeably).   A send to a mailbox will insert the message to the queue of messages corresponding to that mailbox. A receive reads from the queue and returns it to the receiver.  The queues will be FIFO so a send should append message to the end of a queue.  Correspondingly, a receive should read from the front of a queue. In terms of implementation, a message queue is essentially a circular buffer.


    Like semaphores, message queues have a name and an id. A message queue is created by Message_Queue_Create() and destroyed by Message_Queue_Destroy(). All the associated operations take a message queue id (mqid).

    Message queues have variable size, set at queue creation time via the queue_size parameter.

    Message_Queue_Send() / Message_Queue_Receive()

    Messages have arbitrary sizes, limited only by practical concerns (MESSAGE_MAX_SIZE in mqueue.h in our case).

    The sender uses Message_Queue_Send() for sending and the receiver uses Message_Queue_Receive for receiving; so the receiver has no idea how many bytes has the sender actually written; the FIFO mechanism will assure bytes are read in exactly the order they were received. The kernel must copy the message from the process sending the message and append it to message queue.    On a receive, the kernel will read from the queue and copy the message into the buffer passed by the receiver.   If the message is longer than the buffer size of the receiver, part of the message (up to the buffer size) is given to the receiver, while the rest is left in the message queue.   

    An attempt to write to a full message queue should block the process and an attempt to read from an empty message queue will block the process (as you might have noticed, this is the UNIX semantics for pipes, but the queue size varies here).  The operations of message queues are defined for the case of one process reading from a message queue and a second process writing to it.  You do not need to handle the case of more than one process reading from (or writing to) the same message queue simultaneously.


    Message_Queue_Destroy(int mqid) will remove the passed mailbox from the list of mailboxes the calling thread is allowed to use.

    Implementation issues

    You will define a structure holding the mailbox (e.g. struct Mailbox) in include/geekos/mqueue.h). An easy way to model the queue is a circular buffer : an array queue_size large with two indexes, one for reading and for writing. The message queue API implementation should go in src/geekos/mqueue.c.
    You have to add a mailbox list to the user context (user.h).

    Message_Queue_Create() is a request by the current thread to use a message queue. A thread can not call Message_Queue_Send() / Message_Queue_Receive() / Message_Queue_Destroy() unless it has called Message_Queue_Create() first.

    The user gives a name for the mailbox, as well as the mailbox's size, and will get back a message queue ID mqid, an integer between 0 and N - 1. Your operating system should be able to handle at least 20 (thus N = 20) mailboxes whose names may be up to 25 characters long. If there are no mailboxes left (i.e., there were 20 mailboxes with unique names already given), an error must be returned.

    In the implementation of your kernel function Sys_MessageQueueCreate, you will check if another thread has made this system call with the same name. If so, you must return back the mqid associated with this name. The parameter queue_size is ignored in this case. The mqid value returned will allow the calling thread to tell the kernel which mailbox it wants to use later. You also need to add this mqid to the list of mailboxes the calling thread can use, as well increment the count of registered threads which are permitted to use the mailbox. So, for each thread you have to store the list of mailbox IDs it can use, and for each mailbox, you will store the number of threads using it. (This will be used as a reference count.)

    If this is the first time Message_Queue_Create() has been called by the name passed in, then find an unused mqid, and allocate message_size space associated with this mailbox. Again, add the mqid to the list of mailboxes the current thread can use, as well as incrementing the mailbox's count of authorized threads.

    Whenever a thread calls Message_Queue_Send() or Message_Queue_Receive(), the kernel will check if the thread has permission to make this call. It will do so by checking if the thread has the mqid in its list of mqids that it can access If it is there, it will be allowed to execute Message_Queue_Send() or Message_Queue_Receive(). If not, the kernel should return back an error.

    Message_Queue_Destroy(int mqid) will remove the passed mailbox from the list of mailboxes the calling thread is allowed to use. It will also keep track of how many threads have references to the mailbox, and delete the mailbox from the table (i.e. mark is as an unused mailbox) when the last thread that can access this mailbox calls Message_Queue_Destroy(). Note: when a thread exits, the kernel should automatically call Message_Queue_Destroy() on behalf of this thread, for all the mailboxes it has in its list.

    New System Calls

    You have to implement the semantics of the new system calls as described below.

    NOTE: All user-supplied pointers (e.g. strings, buffers) must be checked for validity.

    Call User Function Return on success Return on failure Reasons for failure Comment
    SYS_MESSAGEQUEUE_CREATE int Message_Queue_Create(const char *name, ulong_t queue_size) new message queue id < 0
  • all mailboxes are currently in use
  • name is an invalid pointer
  • queue_size is larger than MQUEUE_MAX_SIZE (defined in mqueue.h)
  • This call should create a new message queue if it does not exist. Otherwise, it should open it in the current process.
    SYS_MESSAGEQUEUE_DESTROY int Message_Queue_Destroy(int mqid) 0 < 0
  • mqid is not an open mailbox
  • Removes this mailbox from the current thread's list of usable mailboxes. If the refcount is 0, free the mailbox.
    SYS_MESSAGEQUEUE_SEND int Message_Queue_Send(int mqid, void * buffer, ulong_t message_size) 0 < 0
  • mqid is not an open mailbox
  • buffer is an invalid pointer
  • size exceeds the maximum message size
  • Appends buffer to the message queue. Blocks if the queue is full.
    SYS_MESSAGEQUEUE_RECEIVE int Message_Queue_Receive(int mqid, void * buffer, ulong_t message_size) 0 < 0
  • mqid is not an open mailbox
  • buffer is an invalid pointer
  • size exceeds the maximum message size (MESSAGE_MAX_SIZE defined in mqueue.h)
  • Reads from the message queue into buffer. Blocks until the buffer can be filled.


    You need to support at least 20 mailboxes whose names may be up to 25 characters long. If all mailboxes are currently used (i.e., all mailboxes have at least one user), an error should be returned. Maximum message and mailbox sizes are defined in mqueue.h.

    Testing your code

    Please use the files in the Grading Criteria

  • p6test.c is a test battery intended to check the requirements, in a similar fashion to p5test.c used in project 5
  • ppstart.c is a ping-pong test case intended to check synchronization via message passing
  • fstart.c is a test case intended to check whether message fragmentation is properly implemented (message size bigger than mailbox)

    Web Accessibility