CS 537: Introduction to Operating Systems

Project 2: Pass me a note

Executive Summary

In this project, you will build a library to enable threads sharing the same address space to communicate by message-passing. This project will exercise your ability to write correct and efficient parallel programs, and further bolster your C skills. You will have to plan what data structures you will want to use for message state (like mailboxes), and you will have to devise a strategy for synchronizing access to shared state. Remember that devising a good locking strategy involves walking a tightrope between the requirements of performance (or concurrency) and correctness!

You will test your library by writing a short program that uses message-passing to implement a parallel matrix multiplication.

Assigned: July 18

Due: July 27 at 10:00 PM

You must work in groups of two or three students.

Background

In Problem Set 1, you tried your hand at several problems involving shared-memory parallel programming. Multiple threads or processes that share memory communicate implicitly by updating shared values. Such shared values may either correspond to program data (like a shared database table) or synchronization variables (like a mutex or semaphore),

Of course, the model of multiple threads with a shared memory space is only one model for structuring concurrent programs. In message-passing parallel programs, all communication is explicit. Instead of signaling a semaphore, for example, a process could send a message to another process.

When communicating entities share an address space (as is the case with multiple threads or multiple processes that share a memory segment), there is no need to explicitly copy messages; message-passing can be implemented “behind the scenes” on top of shared-memory parallelism. (In fact, message-passing is often implemented this way, whenever feasible, for greater efficiency.)

This project requires you to build a message-passing interface on top of the shared-memory parallel programming model provided by the pthreads library.

Why would we want to use message passing when we could simply use shared memory? Message passing is the de facto standard way to structure parallel programs in many important application domains, and this is the case because it is easier and more scalable than shared-memory parallel programming:

1. Given the choice between message-passing and shared-memory parallel programs, it may be easier to reason about message-passing programs. This is the case because all communication is explicit—there is no need to worry about synchronizing access to data because processes can only share data by sending messages to each other.

2. Message-passing presents a scalable abstraction. A shared-memory parallel program will run well on symmetric multiprocessor systems with uniform memory access, but there is a limit to how large such systems can be. If you write a shared-memory parallel program and need to run it on a larger machine, you may not be able to find a machine large enough! On the other hand, since message-passing programs do not assume the existence of shared memory (the send and receive abstractions may be built on top of shared memory, pipes, sockets, or any other communication mechanism), it is likely to be much easier to convert a message-passing program to run on a cluster or on the grid.

As you might imagine, it can be quite desirable to have a message passing interface with a shared-memory implementation—providing the efficiency of shared-memory programming with the ease-of-use and scalability afforded by the message-passing interface.

Interface Specifics

Recall that the basic communication operations in a message-passing system are send and receive. Each communicating entity (e.g. processes, threads, or machines) has a mailbox. The send and receive operations deal in messages; for the purposes of this assignment, a message has a sender, a type tag, a payload, and a size.

The send function queues a newly-constructed message in the mailbox of a specified recipient, blocking if the recipient’s mailbox is full.

The receive function blocks the caller until an interesting message is available; when one is, it is removed from the recipient’s mailbox and returned to the caller.

What is an “interesting” message? Glad you asked! The entity calling receive may be interested in any message, or the it may be interested only in messages with a specific type tag or from a specific sender. In fact, it may be interested only in messages that have a specific type tag and originate from a specific sender. The receive function, then, allows the caller to identify what sort of messages are interesting by specifying a type tag, a sender ID, both, or neither.

Your library will support the methods and types declared in mp.h.

Tips

Stay tuned to the class list for tips!