1  Introduction

Threads provide a mechanism for creating and exploiting concurrency within a program. Since threads share a single address space, context switching between threads can be done much more quickly than between processes in separate address spaces. Sharing a single address space also allows threads to share data structures, but the convenience and efficiency that this sharing provides also comes with the cost of needing at times to control and synchronize the threads' access to these shared data structures. The tools for this synchronization are often provided to the programmer through either semaphores or monitors. Semaphores and monitors are abstractions that encapsulate specific atomic operations upon which we can build (almost) arbitrary shared data structures.

The project requires that you complete several tasks:

• Use our threads package to implement a terminal driver using monitors.
• Implement semaphore primitives in terms of the primitives we provide.
• Implement a second terminal driver using the semaphore primitives you have implemented.

Section 4 describes how you should go about implementing semaphores in terms of the monitors provided, section 5 describes how to use monitors in C, section 6 re-iterates what you should do for the project, section 7 proposes a strategy to attack the assignment, and, finally, section 8 takes care of describing the logistics for compiling and handing-in your completed work.

This document is long, but don't be afraid: the length comes mostly from trying to make it clear and unambiguous, not from complexity. While it will take you a few hours to assimilate it, you will soon be comfortable with it.

2  The Thread Package

• int thr_spawn(void * (*func)(void *), void * arg, int * tid)

 

 

int mutex_create(mutex_t *)

int mutex_acquire(mutex_t *)

int mutex_release(mutex_t *)

int mutex_destroy(mutex_t *)

int cond_create(cond_t *)

int cond_wait(cond_t *, mutex_t *)

int cond_signal(cond_t *)

int cond_destroy(cond_t *)

int thr_gettid(void)

int thr_msleep(long)

int thr_perror(int, char *, ...)

/afs/andrew/scs/cs/15-412/pub/proj2/include/proj2.h.

In order to use the procedures above, you must include their prototypes by putting the following:

#include <proj2.h>

among the other #include's at the top of each C file. You will also need to explicitly link the thread library when you link your program. Thus, for example, to link foo.o into an executable file foo, you would use:

cc -o foo foo.o -lproj2 -lthread

You may notice that there appear not to be any references to monitors in this list. Real monitor implementations require programming language support for monitors, which is not available in C. Instead, we will achieve the same effect by using mutex locks and condition variables, as implemented by the functions above. Achieving the semantics of true monitors using these functions requires that you follow some guidelines in the use of mutexes and condition variables. More on this in section .

Note that the condition variable and mutex primitives in the provided library implement Mesa semantics of monitors, when properly used.

The library proj2 actually includes the terminal emulation as well as the thread library. This is what you want when you are linking your terminal drivers. However, you may want to test your implementation of semaphores in isolation from the terminal emulation. In that case, you would link as follows:

cc -o foo foo.o -lthread412 -lthread

The file

/afs/andrew/scs/cs/15-412/pub/proj2/sample/Makefile.template

is a sample file that will make make do the right thing (when renamed to Makefile in your work directory.) To use this Makefile you should only need to specify the names of your C files in the indicated places. You should feel free to modify this file, for as long as the resulting Makefile can successfully compile and link your code.

3  A Simplified Terminal Driver

Device drivers are modules within operating systems that encapsulate the messy details of the hardware of I/O devices. Encapsulation is particularly necessary for devices because there is a great variety of them; it is easier to provide many small modules that make all devices of a particular type look the same, than to add support for each new device in many places within the operating system. I/O devices are particularly messy because they are ``far away'' and run at very different speeds. This makes the protocols of hardware interaction baroque as well as diverse, and exposes the OS device driver to some insidious concurrency constraints. Fortunately, you are by now experts in this field and shall have no difficulties.

Device drivers are often structured into a ``top half'' and a ``bottom half.'' The top half deals with reacting to the programs that request service from the I/O device, e.g, to read and write system calls issued by the program. The bottom half deals with acting on and reacting to the hardware, e.g, by writing device registers and servicing interrupts from the actual device. The top and bottom halves coordinate their work by sharing data structures. To work correctly, this coordination must use some form of synchronization in controlling access to those shared data structures. Also, device drivers usually must implement some sort of synchronization with user programs in order to keep different requests from different programs from interfering with each other.

In this project, you will not need to deal with the particular strange aspects of any specific terminal I/O hardware, but you will need to provide for the necessary synchronization described above. Your computer will run multiple user threads instead of multiple user processes.

3.1  The Terminal Hardware

The terminals in this project are simulated on top of xterms running on your display (or, if you are not on an X display, directly on your terminal.) The terminals support both input and output, with all data being sent and/or received one character at a time.

The terminal controller hardware implements two data registers and triggers two interrupt lines, for each terminal it supports. The hardware supports up to a maximum of MAX_NUM_TERMINALS, a value defined in the header file mentioned below.

Each terminal's hardware displays characters written onto the Output Data Register for that terminal, but does not do so instantaneously. While the hardware is busy transmitting the character, the output register must not be used. When the transmission is complete, the hardware raises a transmit interrupt.

Characters typed onto a terminal are deposited in the Input Data Register for that terminal. When the hardware places a new character in this register, it raises an interrupt. In real-life hardware, further input characters from the same terminal are typically placed on the input data register regardless of whether the previous value of the input register has been read by the device driver. If the previous value hasn't yet been read by the driver, that is, if the driver failed to respond sufficiently ambly to the previous input interrupt, the character would be typically lost without having ever been seen by the device driver. In our emulated hardware, however, this is not so. To help you debug, your driver will be convinced to dump core when an arriving character would overwrite a character that hasn't yet been read from the input data register.

A class of devices implemented with the same hardware and device driver is often called a major device. Each instance of that class is often called a minor device. The major device number typically identifies the code that should service any of the actual (minor) devices. In this project, we only have one major device, but we have up to MAX_NUM_TERMINALS minor devices.

Specifically, the hardware provides the following procedures:

• void WriteDataRegister(int minor, char c)

 

 

This hardware operation places the character c in the output data register of the terminal identified by minor.

• char ReadDataRegister(int minor)

 

 

This hardware operation reads (and returns) the current contents of the input data register of the terminal identified by minor.

• int DeviceInit(int minor)

 

 

This hardware operation initializes the terminal identified by minor. It must be called once and only once before calling any of the other hardware procedures on the terminal identified by minor.

• int DeviceInputSpeed(int minor, int msecs)

 

 

This hardware operation may be used to set the average character reception speed of the terminal identified by minor. The parameter msecs specifies the average number of milliseconds of delay between the time at which a character is typed on the terminal and the time at which the character is available on the input data register. The actual delay is not predictable (depends on physics) but its statistical distribution is. DeviceInputSpeed returns the previous value of the reception speed. If msecs is equal to NO_CHANGE, this function returns the speed value without changing it.

• int DeviceOutputSpeed(int minor, int msecs)

 

 

This hardware operation may be used to set the average character transmission speed of the terminal controller. The parameter msecs specifies the average number of milliseconds of delay between the time at which a character is written to the output data register and the time at which the output data register again becomes available for writing another character. DeviceOutputSpeed returns the previous value of the transmission speed. If msecs is equal to NO_CHANGE, this function returns the speed value without changing it.
 
 

The use of the procedures DeviceInputSpeed and DeviceOutputSpeed is optional. You may find them useful for debugging, since they vary the timing of the device and thus produce different schedules of thread execution in your program.

The above definitions of the hardware interface can be found in the include file hardware.h, which will be automatically included in your programs if you put the line #include <hardware.h> in your file and use the provided Makefile template.

3.2  Required Terminal Driver Procedures

The device driver you write will need to service interrupts from the hardware as well as requests from the programs (threads) executing in the system. The procedures in this section must be written by you, and are called either from the interrupt dispatcher or from a user thread that requests access to the device.

3.2.1  Interrupt handlers

As mentioned above, when the transmission of a character to a terminal completes, the terminal controller hardware signals a transmit interrupt. Similarly, when the receipt of a new character from a keyboard completes, the terminal controller hardware signals a receive interrupt. In your terminal driver, you must write a separate procedure to handle each of these types of interrupts. Specifically, your terminal driver must provide the following interrupt handlers:

• void TransmitInterrupt(int minor)

 

 

This procedure is called by the hardware once for each character written to the output data register, after the character has been completely transmitted to the terminal identified with minor. After executing a WriteDataRegister operation, you must assume that the output data register for that minor device is busy with the transmission until you receive the corresponding transmit interrupt and your TransmitInterrupt procedure is called with the same minor number.

• void ReceiveInterrupt(int minor)

 

 

This procedure is called by the hardware once for each character typed into the keyboard, after that character has been placed in the input data register of the terminal identified by minor. The character that caused the interrupt should be read from the input data register using the ReadDataRegister operation. Your receive interrupt handler should not block for very long periods because it is probably not reentrant, and further receive interrupts will be blocked until the current invocation of the handler returns.
 
 

3.2.2  Program Requests

• int WriteTerminal(int term, char * buf, int buflen)

 

 

This call should write to terminal term buflen characters from the buffer that starts at address buf. The characters must be transmitted one at a time to the terminal by your terminal driver. Your driver must block the calling thread until the transmission of the last character of the buffer is completed. This function should return the number of characters written (buflen), or -1 in case of any error.
 

• int ReadTerminal(int term, char * buf, int buflen)

 

 

This call should read characters from terminal term, placing each into the buffer beginning at address buf, until either buflen characters have been read or a newline ('\n') has been read. The characters must be received by your terminal driver, one at a time. This function should return the number of characters read, or -1 in case of any error. Note that the ReadTerminal procedure should not place a null character at the end of the buffer.
 

• int InitTerminal(int term)

 

 

This procedure will be called once and only once by applications before any calls to use the terminal term are issued. InitTerminal must initialize the terminal controller hardware by calling the DeviceInit operation.
 

• int SynchronousMulticast(const int * terms, int term_count, char * buf, int buflen)

 

 

This call should write to the terminals specified in termsbuflen characters from the buffer that starts at address buf. Your terminal driver must transmit the characters one at a time to each terminal specified in terms. Your driver must block the calling thread until the transmission of the last character of the buffer is completed. This function should return the number of characters written (buflen), or -1 in case of any error.

Furthermore, the writes to the terminals must be synchronous. This means that no terminal can be, at any time, more than one character ahead of the other terminals in displaying buf, even if the terminals operate at very different speeds.

The terminals to which the buffer is output are specified as an array of integers, each of which is a minor number. The array's base address is terms and the length of the array is passed in the term_count argument.
 

The above definitions of the terminal driver interface can be found in the include file tty.h, which will be automatically included in your programs if you put the line #include <tty.h> in your file and use the provided Makefile template.

While in this project the application threads will be calling your terminal driver via a direct procedure call, in real operating systems (e.g, project 3) the procedures above would actually be system calls. Remember that a system call traverses a protection boundary. To insulate the all-powerful operating system from bogosity in the sandboxed user-level code, it is always of paramount importance, in processing system calls, to check the validity of the arguments. A real operating system would check that the buf arguments above refer to valid addresses in their entirety, for example. In these calls it may also be necessary to check the terminal number, for example.

3.3  Input and Output Character Processing

Terminal drivers typically do much more than transfer characters from memory to the terminal hardware. They also process characters in a myriad modes before (on reading) or after (on writing) the application program sees them (see man termio if you want to get a taste of the many settable parameters.) In this project we are not going to ask you to implement a complete set of these operations, but we do ask for some. Specifically, you must carry out the following character processing:

• Any line feed ('\n')output to the terminal by the user program must be transmitted to the device as the sequence of the two characters '\r' (carriage return) and '\n', in that order. In C, the character '\n' is called ``newline'', and has the same ASCII code as the device carriage return (which returns the cursor to the beginning of the same line,) but the meaning in C of ``newline'' is, in the domain of the device, a device carriage return followed by a device line feed (which moves the cursor one line down without changing its column.) C changes the meaning of '\n' for programmer convenience, and in so doing confuses the issue a bit. Make sure you understand that C characters are not always exactly what should be sent to the terminal.

 

 

The terminal hardware provides a carriage return ('\r' in C) when you type ``Enter'' at the keyboard. This carriage return should be converted to a single ``newline'' ('\n'.) This is again necessary because the meaning of '\n' in C is the same as the terminal meanings of both '\n' and '\r'.

All characters input from the terminal must be ``echoed'' back to the terminal. This allows the user typing on the keyboard to see each character as it is typed. In order for the terminal to appear responsive, the echoed characters should be transmitted back to the terminal at the earliest opportunity, regardless of what the user threads are doing or have done in the recent past. In particular, no application output should go to the terminal between the time a character is typed at the terminal and the time the input character is echoed to the terminal. Please remember this. There are always some 412 students that claim to not have read this paragraph.

Special processing is required when you receive either a ``backspace'' character ('\b') or a ``delete'' character ('\177') from the terminal. When either of these two characters is typed, you should delete the last character from the current input line (if any.) The current input line consists of those characters you have received from the terminal that have not yet been terminated as a line of input by the receipt of a newline character ('\n' after the processing described above.) If the current input line is empty, you should ignore the backspace or delete character. If the current input line is nonempty, you should delete the last character in the line. In no case should you include the backspace or delete character itself in the input line that is returned to a user program calling the ReadTerminal procedure.

In processing a backspace or delete character as described above, if you delete a character from the current input line (because the current line was not empty,) you should also echo the three-character sequence of ``backspace'' ('\b') followed by ``space'' (' ') followed by ``backspace'' ('\b'.) In no case should you echo the delete or backspace character itself to the terminal. This is necessary because the ``C'' meaning of '\b' and '\177' is to delete a character, which the terminal hardware can only do with the sequence above. This sequence will result in the last character on the screen appearing to be ``erased.''. If the current input line was already empty when the backspace or delete character was received, you should ignore the backspace or delete character and do not echo anything for this character (some of you may want to ring the bell, as some terminals do: you do this by sending '\007' to the terminal.)

3.4  Line-oriented Terminal

You will notice that the specification of ReadTerminal() considers the input as consisting of lines of text delimited with `\n', but that, at the same time, the terminal hardware gives you a single character every time it raises the read interrupt. Something similar can be said for WriteTerminal() and the write interrupt.

This implies that your terminal driver must implement the illusion (abstraction) of a line-oriented terminal on top of a character-oriented hardware device. It is usually true, as it is in this case, that the diverse pieces of the operating system implement abstractions that are not directly or completely supported by the hardware.

That the driver implements the concept of ``line'' presents some complications that may not be obvious at first. Consider the following application code:

         int len1, len2, len3;
         char buf1[4];
         char buf2[10];
         char buf3[10];
         char buf4[10];
         len1 = ReadTerminal(0, &buf1, 4);
         len2 = ReadTerminal(0, &buf2, 10);
         len3 = ReadTerminal(0, &buf3, 10);
         len1 = ReadTerminal(0, &buf4, 10);

         Hello\b\n
         Universe\b\b\b\b\b\b\b\bWorld\n
         Good bye

         len1 = 4
         buf1 = "Hell"
         len2 = 1
         buf2 = "\n"
         len3 = 6
         buf3 = "World\n''

Think about why this is the case. You may come to realize that you need some buffering inside your terminal driver.

3.5  The User Programs

In this project, the user programs are threads which call WriteTerminal, ReadTerminal, DeviceInputSpeed, DeviceOutputSpeed and SynchronousMulticast() at will, but only after one of these threads (and only one) has called InitTerminal once (and only once) for each terminal used.

The one thread that starts all of the user threads (e.g, in the test programs) is the boot thread, which is started by the hardware at start-up time. This thread must not call the exit() routine but may return before the user threads spawned by it complete their work. Any thread spawned by the boot thread, or the boot thread itself, can call InitTerminal, but only one can do so. When the boot thread is started, neither the terminal hardware nor your terminal driver are active.

The boot thread's entry point is the procedure

int SystemBoot(int argc, char ** argv)

which is to be provided when testing your terminal driver, but which is not itself part of the driver. The argc and argv arguments to this procedure are just like the arguments to the main procedure of a C program.

Please note that you should not provide a main function anywhere, neither in your terminal device driver nor in your test programs that use the terminal driver.

Please note again that the SystemBoot() procedure is not part of the terminal driver, but is instead the part of the system that uses the terminal driver. Thus, any code related to your device driver, including the initialization of any data structures you define, should not depend on any particular SystemBoot() function - your terminal driver should be able to work with any mix of application threads. In particular, when we test your driver, we will replace the SystemBoot() function with one of our own. Because of this, you should put the code for any SystemBoot() you use in a source file separate form the files you use to hold the code for your device driver. We provide several sample SystemBoot() files in /afs/andrew/scs/cs/15-412/pub/proj2/sample.

3.6  Terminal Behavior Constraints

When used from different threads, the terminal functions can be called concurrently. Furthermore, program-driven output also occurs concurrently with the output from the echoing of input characters. We expect you to decide what behavior is reasonable in the presence of concurrency, but here we set some minimum standards.

• When a mix of more than one WriteTerminal occurs concurrently to the same terminal, their outputs must not be interleaved on the screen. Programmatic output to two different terminals may be interleaved.

 

 

The echoed input characters must be displayed at the earliest opportunity, as previously mentioned. They can (indeed, some times must) be migled, on the screen, with the output from one or more WriteTerminals.

Multi-character sequences resulting from the character processing described above must be displayed atomically, even if, as in the case of the echo stream, the stream itself can be interleaved. This is to preserve the display effect of these sequences.

If there is more than one ReadTerminal waiting to read characters from a terminal, the contents of each of their buffers must be formed by characters typed sequentially at the keyboard. That is, input characters should go to a single ReadTerminal until that ReadTerminal returns, and then on to the other one. Concurrent ReadTerminals reading from the same terminal should not alternate the reading of the input data register for that terminal.

Your device driver should implement line-oriented terminals. For this project, this means that no data is returned to a ReadTerminal call until a newline has been read. This does not necessarily imply that the whole line is returned to the ReadTerminal: only as many characters as requested should be returned, and the rest remain available for the next ReadTerminal(), even if it is issued by a different user thread.

3.7  Driver Implementation Constraints

Device drivers are critical parts of the code of the operating system: they are very stressed by concurrency, and operate at a very low level. Notably, they are often invoked from hardware interrupt handlers, which typically preempt any other system activity, including important OS functions. They are also restricted, for reasons that will become clear later in the course, to using small portions of well-defined ``pinned'' memory.

Because of this, your device driver should:

• not block for an indeterminate amount of time, when running from an interrupt handler. In particular, it should never, when called from an interrupt handler, block on a resource being held by some other blocked thread.

 

 

allocate and use a fixed amount of memory for its internal data structures. In the event that a sequence of terminal operations should require the driver to use more memory, the last operation of the sequence should be either not carried out or blocked, depending on whether the operation is executed from within an interrupt handler, or not. In particular, it is all right to drop input characters if they are coming in faster, on the average, than they can be consumed by the applications. However, it is also unreasonable to require applications to have a pending ReadTerminal at the time every single character arrives. You must use buffers to deal with bursts and temporarily ``absent'' applications, but the buffers must be of finite size.

When adding one character to one such buffer would overflow the buffer, and the driver cannot block waiting for the buffer to drain (e.g, if within an interrupt handler) you may choose a course of action. You may drop the character as stated above, and you might, depending on the situation, try to output a bell (`\007') to the terminal. The bell is not required and may not be possible in all cases, but we expect you to implement reasonable behavior for these cases.

4  Semaphores

As we state more clearly in section , the second part of this assignment is to implement semaphores in terms of the mutexes and condition variables we provide. You should do this in separate files, sem.c and sem.h, which define the type sem_t (using typedef) and the following procedures to operate on this type:

• int sem_create(sem_t * sem, int value)

 

 

Creates a new semaphore (returned in sem) and initializes its value to value. Returns 0 on success and -1 on any error.
 

• int sem_destroy(sem_t sem)

 

 

Destroys the semaphore identified by sem. Before this procedure is called any of the other procedures may be called. After this procedure is called any semaphore procedure calls have undefined results. Returns 0 on success and -1 on any error. You should be careful to deallocate (using free()) any memory (if any) allocated by malloc() inside sem_create.
 

• int sem_P(sem_t sem)

 

 

Performs a semaphore P operation on the semaphore identified by sem. Returns 0 on success and -1 on any error. Note that the text book for this course refers to this semaphore operation as ``wait''. We use the more common ``P'' to avoid confusion with the ``wait'' operation of monitor condition variables.
 

• int sem_V(sem_t sem)

 

 

Performs a semaphore V operation on the semaphore identified by sem. Returns 0 on success and -1 on any error. Note that the text book for this course refers to this semaphore operation as ``signal''. We use the more common ``V'' to avoid confusion with the ``signal'' operation of monitor condition variables.

5  ``Monitors'' in C Using Locks and Condition Variables

As you know from lecture, monitors are synchronization primitives that are similar to ``objects'' in the ``object-oriented'' sense, with ``private'' variables that can only be accessed through public ``methods'' (entry procedures) provided by the monitor. Monitors of course have the added semantics of mutual exclusion and condition variables.

Object-oriented programming is most often carried out using object-oriented languages, but this is not a sine qua non: while object-oriented languages provide protection (not C++!) and facilities that ease the task of programming with objects, what is often referred to as ``object-oriented programming'' is more a style of programming than a language choice. For instance, one can program objects in C through careful discipline, albeit C++, Java and others make it easier by providing syntactic sugar and separate but helpful facilities such as operator overloading and polymorphism.

Similarly, even though monitors were designed to be embedded in the language, with the language guaranteeing their correct usage, it is possible to program using the monitor concept in languages that do not support them intrinsically. For this to be possible, a language needs to be enriched with mutual exclusion locks and condition variables, but these can be added at link time, without the knowledge of the language's compiler or run-time system. In this project, you are asked to write the device driver using monitors in C. More accurately, you will write it using the mutex_t and cond_t primitives defined in the library we provide.

With these procedures, you can program sets of related functions that work like monitors do. To make these monitor-like programs you write work like real, language-embedded monitors, we strongly suggest you follow the following guidelines:

• You may use only a static set of mutex locks and condition variables. That is, you may not dynamically create more mutex locks or condition variables beyond the ones you create in your InitTerminal procedure.

 

 

You should structure your synchronization code as if you were programming in a language with direct support for monitors, that is:

• Your C procedures should not acquire more than one mutex each.

 

 

Any procedure that acquires a mutex should do so at the very top of the procedure, and should release it immediately before returning.

Remember to release the mutex before every exit point from each monitor entry procedure; for example, if a procedure returns from inside a conditional, you should release the mutex lock within the conditional. You may want to write macros to automate this task, to make sure you don't miss any exit points.

Consider associating the data protected by a monitor or semaphore with the monitor or semaphore constructs that are used to protect it. You might even group them together with a data structure.

We establish these rules to help you organize and debug your code. Monitors become difficult to fathom when these simple rules are not observed. Unfortunately, C cannot enforce these rules, as do languages with intrinsic support for monitors.

6  Your Assignment

Your assignment for this project is to do each of the following three parts:

1. Implement the semaphore primitives specified in section 4, using the mutex and condition variable primitives provided in the provided thread library described in section 2. Put these in a separate .c file (e.g, sem.c.)
2. Implement the terminal driver described in section 3, using the provided thread package. Your driver must implement each of the procedures in section 3.2 and must perform the character processing described in section 3.3. In implementing this version of the terminal driver, you should follow the monitor programming guidelines in section 5. Make your terminal driver code compile into a single object file, e.g, montty.o. The procedure SystemBoot described in section 3.5 is not part of the terminal driver: it is the ``init'' thread (akin to the UNIX ``init'' process discussed in class.)
3. Implement a different version of the terminal driver using your semaphores primitives described in section 4. The mutex and condition variable primitives should be used within sem.c to implement your semaphores, but may not be used anywhere else in the code. Make this terminal driver compile into a single object file different from the object file for the monitor version of the driver, e.g, semtty.o.

 

 
 
 

6.1  Checkpoint

To help you fight the demons (or daemons?) of procrastination, we will be checking your progress a week after we hand out this assignment. By the end of Friday, February 11th, we will expect to find a subdirectory named CHECKPOINT within your group directories that will contain a snapshot of your monitor terminal driver source files, your implementation of semaphore primitives, and a Makefile. This snapshot of the driver, when compiled, should be capable of echoing characters typed into any terminal, and your implementation of semaphore primitives should be complete. This snapshot will need to use at least WriteDataRegister, ReadDataRegister, TransmitInterrupt and ReceiveInterrupt. You will be in substantial trouble with the assignment if you haven't gotten that far by then. You will not be graded on this checkpoint, but failure to show us a working echoing driver and semaphore implementation will severely affect your final grade for the project.

7  Plan of Attack

There is no need for you to do things in any order. However, some parts of this assignment will take longer than you think. This is not because you will have to write a lot of code, but because some of the bugs you will encounter will be reluctant to show themselves. Typical solutions have about 400-500 lines of C code. Start early. One of many reasonable plans to attack this project follows. In particular, depending on whether you feel more comfortable with semaphores or with monitors, you might want to implement semaphores and the semaphore driver first.

1. Read this handout. Read it again. Make sure you understand the bit about the top and bottom halves of device drivers. Think about how to join them. Realize that the top and the bottom may have completely different and independent timing, and that the granularity of the objects they operate on are different (lines versus characters.)

 

 

Make inventory of the driver entry functions you will have to write. Decide what each of these functions will do in relation to whatever data structures you designed to join the two halves. Don't be vague, though there is no need to write complete pseudo-code (it wouldn't hurt though.)

Add shared data structure synchronization to your mental code. Try to find synchronization problems with it. Focus on how the monitor and semaphore implementations will differ, and try to modularize the differences so that you can re-use as much of the code as possible.

Write a monitor bottom half that succesfully echoes characters to the terminal, without having the ReceiveInterrupt handler block on the TransmitInterrupt.

To decongest your mind, write the semaphore implementation using monitors. At this point you are done with the checkpoint.

Splice WriteTerminal() into your bottom half. Make sure that the echo has priority over WriteTerminal() and that two or more concurrent WriteTerminal()s do not interfere with each other.

Splice ReadTerminal() into your driver. Make sure that echoing of characters to the screen is not affected by an application's failure to call ReadTerminal().

Think about where best to introduce input and output character processing. Realize that the processing required for echo, output, and input, are different, but that they are not entirely dissimilar either.

Add character processing.

Thoroughly test what you have written so far.

Implement the semaphore version of what you have done so far.

Implement SynchronousMulticast() in both semaphore and monitor versions of the driver.

8  Logistics

The logistics are similar to those of project one. You will soon receive electronic mail notifying you of the creation of your work directory. You can do your work in that directory or in any other directory of your choosing but, come the deadline, only the work present in the work directory will be evaluated. A few days before the deadline we will give you an opportunity to sign up for a demo.

Your code need not be exhaustively documented, but it is good practice to comment code (lines, or procedures) that is particularly compact or whose purpose is not obvious. If you are particularly proud of something, it also deserves to be commented. You may also want to make other comments to us that don't find a natural place in your programs. You should write these comments in a file named NOTES, and mention it to us during your demo.

8.1  Preparing your work directory: the Makefile

/afs/andrew/scs/cs/15-412/pub/proj2/sample/Makefile.template.

Copy this file into your work directory and rename it to Makefile.

In the Makefile that you now have in your directory, there are rules to make the executables sem-test, montty, and semtty. These are to be the executables for the three parts of the project. The rules that make these executables will automatically link the hardware emulation library and the thread library.

Your source files must be linked by these rules, too. You may modify the definitions of the variables SEMTEST_OBJ, MONTTY_OBJ and SEMTTY_OBJ within the Makefile to include the names of your source files. These are already set to defaults so that if your source files are sem.c, montty.c and semtty.c you need not modify the ``make'' variables.

If you prefer to use the GNU C Compiler (gcc) or the Solaris native C compiler cc, you may also change the ``make'' variable CC in the Makefile.

The files sem-test.c, montty-test.c and semtty-test.c are the programs implementing the user threads that will use your monitors and/or terminal driver. You can write your own tests, and we also supply some tests in the directory /afs/andrew/scs/cs/15-412/pub/proj2/samples. To use one of these tests, you should copy its file into your directory and rename it to montty-test.c or semtty-test.c depending on what part of your project you want to compile (or all of them.)

Any include files written by you and included by your programs should be in your work directory and should be included with double quotes, that is, you should include them using #include "file.h" rather than #include <file.h>.

Remember, as in project 1, to set your PATH to include /opt/SUNWspro/bin if you want to compile with the Solaris C compiler: the one you get by default is broken.

8.2  Running your terminal driver

The executable, as linked with the library proj2, will try to open an xterm into your display whenever DeviceInit is called. This xterm will emulate the terminal device with which the hardware procedures (e.g, WriteDataRegister) interact.

Any output from your program (written to stdout and stderr via e.g. fprintf) will go to the Solaris shell from which you invoked the executable.

If you would like all this output to go into a file, you can run your executable with the -log command line switch. For example, if you wanted to save the output from your program (which may be important for debugging) into the file ttylog, you might type the following at your shell command line:

ttytest -log ttylog

You can use xterm even if you are not sitting directly in front of a Sun computer running the Solaris operating system. You do this by telneting to a Solaris machine (several are available by telneting to far-sun4.andrew.cmu.edu) and setting the DISPLAY environment variable like this:

setenv DISPLAY machine.andrew.cmu.edu:0.0

where machine is the name of the computer you are sitting at.

You may run your 15-412 terminal driver even if you are at a computer that does not run X (PC, Mac.) To do this you run your executable with the -noX command line switch. The simulated terminals will then output everything to the single terminal, but input from that terminal will only go to minor device 0. In this case, you would do well to redirect the output of your program via the -log switch, as described before. So, if you are sitting at a computer that does not run the X window system, you might type:

tty -noX -log ttylog

Remember that in all cases you must be logged onto a Sun Solaris machine before you can run your terminal driver.

8.3  Questions and Problems

If you have questions or are running into a sizable block, do not hesitate to ask questions by sending e-mail to staff-412@cs.cmu.edu, or by contacting any of the members of the course staff.

We may need to make announcements or clarifications. We will use the academic.cs.15-412.announce bboard for this purpose.

8.4  Workload

8.5  Deadline