We think we might have our semaphore primitives working. What's a good way to test these? The test(0-2).c files in the proj2/sample directory seem to be geared towards testing montty and semtty, and we're not quite sure how we ought to go about stress testing our semaphore primitives short of writing semtty itself, and we'd like to check the correctness of sem-test first.

Answer

One thing you could do is to write a quick program that counts. Implement separate threads to increment the one's tens, and thousands digits and use semaphores to synchronize them. Or you could write a producer-consumer problem using multiple producers and consumers and a common buffer and test that. In this case, you probably want to colect a few statistics to make sure that all of the consumers and all of the producers are getting near-equal access..

To continue the question - basically, Zach and I were wondering if ReceiveInterrupt and TransmitInterrupt, being interrupt handlers, can be considered "atomic" with respect to both each other and the other processes we might have running. For instance, one of the interrupts won't be called in the middle of the other's running, and neither of them will yield cycles to the system scheduler. This assumption was based on the fact that interrupt handlers should get in and out fast and can't do that if they get suspended by the kernel, but it was a big assumption still so we wanted to verify it. I'm still not certain about the issue as a whole.

Answer

To answer your question, the simulator only prevents interruptions in ReceiveInterrupt by ReceiveInterrupt -- this causes a core dump. Other types of interrupts are legal and possible. But keep in mind that it would be difficult to have an instance of TransmitInterrupt disturb another instance of TransmitInterrupt -- since it can only occur after a character has been processed by the terminal and only one character can be sent to the terminal at a time. So the last case is a RecieveInterrupt interfereing with a TransmitInterrupt or vice versa. These could happen. Depending on your implementation, they may or may not be interesting.

Is it safe to call cond_signal() without holding the mutex that protects the condition variable?

Answer

Probably not. I don't believe that the cond_signal() will fail, but you will potentially have the lost signal problem mentioned in the Sun man page below.

Are "interrupts" preemptable by other threads?

Answer

Yes.

If there's an '\r\n' to be sent to the terminal or a '\b \b', and it so happens that the buffer overflows in the middle of the sequence, is it permissible to drop one of the later chars (as in, if you put \r into the buffer but \n just does not fit), or must the chars be treated as a single sequence?

Answer

These multi-character sequences should be written atomically to the terminal, i.e. all or none of the characters should arrive. It sounds like you might want to consider carefully where you put the buffering in your terminal driver.

should we be doing: typedef struct sem_t sem_t or typedef struct sem_t *sem_t ? I have heard conflicting stories on which of these we should be using, so I'ld like to know

Answer

Just make sure your definition is compatible with the libraries so we can test it. The semantics should not be changed. If you want to do a typedef your first option is the right one. (typedef struct sem_t sem_t)

In the packet, it is explicitly stated that: A \\n sent to the terminal by a program (via WriteTerminal) should be converted to \\r\\n when it is sent to the terminal (this moving the cursor to the beginning of the next line). An \\r received from the terminal should be converted to a \\n when sent to programs via ReadTerminal. Am I correct in assuming that a \\r received from the terminal should be echoed back as \\r\\n, thus performing the expected reaction to the 'enter' key?

Answer

Yes, the \\r should be echoed back to the terminal as the sequence: \\r\\n.

There is one section of code that seems difficult to implement without the
use of multiple mutex variables.

Right now, there is protection around the functions called from
receiveinterrupt and transmitinterrupt, which basically protect the echo
buffer from interference from both functions at once.  However, when
WriteTerminal is called, there is a problem:

First, echo has to be allowed to continue no matter what.
Second, other WriteTerminals have to be blocked.

That seems to require two mutex variables, because blocking the writes
requires one set of variables and blocking echo another, thus:

acquire(writemutex)

for each character to be written {
    acquire(bufmutex)
    cond_wait(nothing_to_be_echoed, bufmutex)
        write character
    release(bufmutex)
}

release(writemutex)

There does not seem to be a way to write that block of code without two
mutex variables, yet the instructions strongly suggest only one mutex per c
function. Is there something wrong with the above code, or is there a
different possible implementation we are overlooking?

Answer

If you're having to use more than one mutex, then there's probably something that you're not considering in your implementation. I'm not sure exactly how you're implementing the terminal driver; I think it would be best if you spoke to a TA during their office hours about this.

Okay, that is a fundamental statement, and in direct contradiction to what was stated in class. So, just so as to get a definite ruling on this, interrupts ARE preemptable. Second, is it okay to acquire a mutex in an interrupt handler, as was suggested in the code below:

interrupt_handler() {
        mutex_acquire(&mymutex);
        cond_signal(&mycond);
        mutex_release(&mymutex);
}

Answer

Recieve interrupt cannot be interrupted by a receive interrupt -- it will generate a core dump if more input is received by the same terminal.
Transmit interrupt cannot be interrupted by a transmit interrupt, since you can't send more data until you receive the previous one.
Transmit interrupt can interrupt receive interrupt, and vice versa. But in most cases these do not directly affect the same data structures and do not represent problems in student solutions. But this really depends on your solution and some people do need to eb careful about echo.
You should avoid considering interrupt handlers to be part of your monitors. They should not wait for entry, &c.
(later on) I was thinking about my answer to you, and it may have been a bit unclear.
Although it is possible to solve the problem, while guaranteeing mutual exclusion, without blocking in the ISR, this is not necessary.
But is is necessary that you ensure that ReceiveInterrupt cannot block on TransmitInterrupt. And it is possible -- and a common error -- for this to occur indirectly, where both lock down a common queue. In some cases this happens directly, and in other cases a pending write, waiting for the TransmitInterrupt, causes this -- either are bad situations.
Just make sure that ReceiveInterrupt will be serviced rapidly and without violating bounded wait (except the usual scheduling indeterminism).
As for your second question about aquiring mutexes in the interrupt handlers, let's think about that. The project description says that your device driver should not block for an indeterminate amount of time, when running from an interrupt handler... (in section 3.7, first bullet) So I don't think that it's a good idea to put a mutex in your interrupt handler. Instead, you should make sure that the interrupt handler is never going to be called more than once at a time for the same minor number, depending on your implementation, and I'm not sure what you're doing. If this isn't clear, it would probably be best to see a TA during office hours and discuss it.

Say I want to have an array of size MAX_NUM_TERMINALS that I want initialzed all to zeros so that I can keep track of which terminals have been initialized. Since there doesn't seem to be a general initialization routine to put this in, what is the syntax for setting such an array to be all zeros regardless of the setting of MAX_NUM_TERMINALS?

Answer

You could put these initialization in InitTerminal, and somehow with a global variable guarantee that it is only done the first time InitTerminal is called.

Quick question; apologies if it's been asked before- Is it in fact the case that all our code for the monitor term driver must compile into one _object_ file? One library would make sense, or multiple objects, but one object makes the code really ugly... Thanks very much! -Chris White

Answer

The project description says one single object file, montty.o. I would stick to what it says.

One more (sorry)- Does ReadTerminal put the trailing newline in the buffer it returns? Thanks! -Chris

Answer

Yes, ReadTerminal puts the newline in the buffer it returns, but only if the newline is in the number of characters ReadTerminal requested.

How do you enter and exit a monitor? Here are two possible pieces of code:

1) mutex_t spin; cond_t cond;

// proper initialization of above

precode..... Entry: mutex_acquire(&spin); cond_wait(&cond,&spin); mutex_release(&spin);

Critical Code.....

Exit: cond_signal(&cond);

aftercode....

The problem with this seems to be that this calls wait when there may not be anyone already in the monitor. This could be very, very bad depending on the implementation of the condition variable; specifically, does cond_wait block when no one else is in the monitor? If it does, then this code would seem to be necessary:
mutex_t spin; cond_t cond; bool occupied = false; // okay, so this isn't c exactly
Entry: mutex_acquire(&spin); if (occupied) cond_wait(&cond,&spin); occupied = true; mutex_release(&spin);
Exit: mutex_acquire(&spin); occupied = false; cond_signal(&cond); mutex_release(&spin);
Yet this would seem to be an implementation of a binary semaphore without the wrappers of P() and V(), and so the monitor section of this project would seem to be rather pointless.
And one more unrelated question: Without some kind of DestroyTerminal(int term), how do we delete any memory we allocated in InitTerminal? Does it simply hand around?

Answer

Please remember that we don't have language-supported monitors. Instead we must simulate a monitor using other synchronization primitives. The best approach is probably this:
Use a condition variable (and the requisite mutex) to construct the entry queue. Basically, at the beginning of every entry procedure, grab the mutex and check to see if you can exit the monitor. If you can, flag the monitor as in use and release the mutex.
If you can't enter, wait on the condition. This will require passing cond_wait both the condition variable and the mutex.
At the end of each entry procedure (those that enter the monitor), flag the monitor as available and signal on the condition using cond_signal. Remember to do this at ever possible return within an entry procedure.
This approach will ensure that you only wait while the monitor is occupied and that you don't lose any signals.

What I did was I created a sem-test.c file that contains the SystemBoot() call, and try to create the sem-test executable. This is the linking error I got when compling:

gcc -o sem-test  sem.o sem-test.o 
/afs/andrew.cmu.edu/scs/cs/15-412/pub/proj2/lib/libthread412.a -L
/afs/andrew.cmu.edu/scs/cs/15-412/pub/proj2/lib -L/usr/lib -lthread412
-lthread
Undefined                       first referenced
 symbol                             in file
main
/afs/andrew/system/dest/@sys/local/gnucc/011/lib/gcc-lib/sparc-sun-solaris2.6/2.95.1/crt1.o
ld: fatal: Symbol referencing errors. No output written to sem-test
collect2: ld returned 1 exit status
*** Error code 1
make: Fatal error: Command failed for target `sem-test'

Answer

are you not using the makefile we provided? You need to use this because it links in a procedure named main, so you do not need to provide one.

1. I'm a little confused by the word "terminal" in the project. Does it refer to the xterm window shown on the screen? Or it also include the keyboard? Otherwise, how can the driver "ReadTerminal()"?

2. Does each terminal have two registers, one is input data register, another is output data register? Can each register only hold one character, i.e. one byte? Are there really two such hardware registers for each terminal, or they are emulated by the library functions you provide?

Answer

"terminal" refers in this case to teh xterm on your screen, but it also includes the input from your keyboard.
Yes, each terminal has two registers, one for input and one for output. These registers hold one character each. In the Yalnix terminal driver, these are emulated by the library functions we provide.

so if you're amidst a synchronous multicast, can some random write terminal "butt in line", print its line to the screen, then allow synchmulti to resume, so long as the two don't jump back and forth and mangle their output, and so long as all the synch multi terminals stay within one character of eachother? don't think the handout specifies this.

Answer

no, a write cannot interrupt a multicast, but echo can.

If we call ReadTerminal with a buffer length of 8 characters, and then another ReadTerminal with a buffer length of 24 characters, if I type in 16 characters and a carriage return, should the second ReadTerminal take only the last 8 characters?
Also, if I call one ReadTerminal a while ago, and then another ReadTerminal sometime much later in the program, should it start with the characters received from the last ReadTerminal, or from the time when the second ReadTerminal was called?

Answer

The second read terminal should start from where the first stopped, otherwise, how would you know where to start the second ReadTerminal?

Some questions about testing the project. When you test our project, what exactly are you going to do? Could you describe the steps, like first start a xterm window, then type......??? You said in section 3.5 that we shouldn't have any main() there, then how do you start the testing program, and how do you start the device drive we write?

Answer

The libraries we provide have a main function, so you do not need to provide this. These libraries will also cause an xterm-like window to appear when you call DeviceInit, this is the terminal provided by Yalnix. So to test your program, you should write a file named semtty-test.c or montty-test.c and include this in your makefile. This file will have a main in it and will act like a user program which calls ReadTerminal and WriteTerminal, InitTerminal, adn SynchronousMulticast. Once you compile your code, you should be able to type montty or semtty to start your program. If you are unclear about any of this, please feel free to write back. Also, there is example code in /afs/andrew/scs/cs/15-412/pub/proj2/sample

We are getting a "Not enough space" error (when printed with 
thr_perror).  We never have more than 5 threads or so going (one for each 
term in a Synchronous Multicast).  Over the lifetime of the program we have 
many threads created that end quickly.  Printing the thread numbers we 
notice that the numbers keep incrementing with every spawned thread -- we 
die at about 144.  is there something that needs to be done to clean up 
after threads once they are done?

Answer

You have essentially created "zombie" threads.  Like with processes,
threads have an exit status that you must explicitly "wait" for to
remove from the set of threads/processes.

This interface isn't available to you for this assignment.

The constraint is that each terminal must have only one spinlock and only
one signal (and that the spinlock should not be held for any more time than
absolutely necessary.  So basically, the only thing one can do to insure
mutual exclusion is to enter the monitor.
[...]

Answer

So, there actually is no constraint that says that the terminal
must have only one spin lock.

Each "monitor" will have one mutex.  You can have several monitors
in your program, each would have their own mutex.  A monitor can
call a monitor (with the obvious caveats to beware of deadlock).

Each "monitor" can have any number of condition variables.  
Look, for example, at one of the readers/writers solutions that
was discussed in class (or a bounded buffer problem).

There is a function for InitTerminal and DeviceInit. Are we to assume that
once created a terminal will be around forever?  This seems like it could
be undesirable.  Is this really what you intended?

Answer

Yes, once a terminal is created, it will exist forever.

	I am using the make file provided in
/afs/andrew/scs/cs/15-412/pub/proj2/sample/  the only thing I changed in
there was to let ALL=sem-test.  and I created a file called sem-test that
have the Systemboot function call in it.  and included the proj2.h and
stdio.h header files.  Is there some standard library I need to include in
any of my files to make the linking work?

Answer

There are two sets of libraries.  The first is linked with your program if
you compile it as

cc -o foo foo.o -lproj412 -lthread

This links in the library for the terminal driver.  This library
has a procedure in it called main() that initializes the simulator.
As part of the simulator initialization, it calls your function
called "SystemBoot".

The second set of libraries allows you to test code *independently*
of the terminal simulation.  This is the library that you would
get if you be linking against with a command like:

cc -o foo foo.o -lthread412 -lthread

This library contains only the thread calls (thr_*, mutex_* and cond_*).
It lets you test code, for example the semaphore code, indepenently
of this simulator.  As such, it's just a normal C program and you
need to define a main() function.

In section 2 of the project, is the condition variable (cond_t) the same
as the one we learned from the class, i.e. condition variables defined
in a monitor?

Answer

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

So, yes, provided that you don't misuse them.

Do we need to support terminal input or output speeds of 0ms? Our driver 
works fine on input and output delays of 1ms, but 0 clobbers input if you
smash the keyboard.

Answer

We will only require that your solution work with an input delay of 1 ms.
However, it is possible to create a solution which works correctly with
0 ms. delays - but it is fairly tricky and involves some non-obvious
tricks (or hacks, depending on your point of view).

I've implemented monitors in the follwoing way:

whatever foo(whatever)
{
	mutex_acquire(&MonitorMutex);
		.
		.
		.
	mutex_release(&MonitorMutex);
}

On the Q&A archive, a more elaborate system for implementing monitors
involving both mutexes and condition variables is presented as the
proper implementation.  What makes my simpler approach incorrect?

Answer

mutex_acquire is traditionally implemented as a busy wait.  Whereas,
monitor entry really should block any threads that are not currently
able to enter a monitor.  Otherwise, the system is much too slow
to be useful!

ok, so (void * (*func)(void *), ... is a little difficult to digest.

We're spawning a thread, lets say our prototype looks like:
void * Proc(void * myvoid)

should we call:
thr_spawn(Proc,...
or
thr_spawn(&Proc,...

They uh, both seem to work, properly.
Is there a difference?  Which is "correct"?

Answer

They're really equivalent. The name of a function is implicitly a pointer
to that function. I don't think the compiler will view the & as having any
meaning at all.

We spawn a thread which uses a while(1) loop which never ends. It works without a hitch except the thread never dies. Is this ok?

Answer

In this project, terminals are created but never destroyed. So, you don't really have to worry about how you would shutdown a terminal. But, it's possibly worth thinking about how you would do so with your implementation.

The handout says the character appearing on the monitor after a keystroke should be that keystroke. Sometimes the previous character (from a user thread) hasn't finished writing to the data register and thus hasn't yet appeared on screen. Is this OK?

Answer

If you have started to write a character, it is fine to let that write finish. Also, if you were writing "\r\n" because you saw "\n" then either neither or both characters should be output before the echo occurs.

There must be some sort of buffering done when performing readline (as suggested by the handout). Is it OK to have a fixed-length buffer?

Answer

It is acceptable to have a fixed-length buffer. However, you should ensure that your terminal behaves reasonably when the buffer is full, and (as always) be prepared to explain your design choices during the demo.

Is it acceptable to have more than one wait queue associated with a particular monitor (in other words, to use more than one condition variable)?

Answer

For your implementation to match the definition of Mesa monitors, you should have only a single wait queue. Also, from a practical standpoint, it would be very tricky to correctly impelement a monitor-like thing with two condition variables that didn't have a good deal of busy waiting.

Is it alright to have a maximum line length, and drop any characters that exceed that line length?

Answer

Try not to impose any additional constraints above and beyond those imposed by using fixed-length buffers. For instance, limiting the length of a line to less than your buffer size would be bad.

is it okay to not print any/all dropped characters, using the theory that if the user doesn't see the character get typed, they'll assume it's their fault and manually correct the error? This would seem reasonable, since it would keep the system in a consistent state.

Answer

As you observe, it is a good idea not to echo dropped characters to the screen. The lab handout mentions that you might want to ring the bell in these situations, but that is optional.

Are we allowed to signal the condition variables from inside ReceiveInterrupt and TransmitInterrupt even though they never acquire a mutex?

Answer

It is very dangerous to signal a condition variable unless you hold the mutex that protects that condition variable. The problem is that, unless you are very careful, another thread could miss the signal and wait forever on the cv, deadlocking your system.

Is there some easy way too look up our group number?

Answer

If you did have a directory, you could locate it by doing an "fs la *" inside of the usr/proj2 directory.

Is the scheduler guaranteed to be fair to multple threads waiting on a condition variable?

Answer

There are no guarantees when it comes to scheduling -- this depends on the scheduling discipline that is used. FIFO scheduling is fair and prevents starvation, whereas SJF or PRI are not fair and permit starvation. But we generally neglect this level of detail in implementing our solutions. We just assume that there is enough CPU power, a sufficiently small load, and scheduling discipline that is fair enough to ensure that in a practical way, bounded wait is not violated.

When implementing SynchronousMulticast, we were assuming that it has to be in exclusion with WriteTerminal. That is, if SynchronousMC is writing into a terminal, WriteTerminal has to wait and reverse. This seems to make sense, since WriteTerminals wait on each other, too. I just wanted to make sure that this is an admissible solution.

Answer

WriteTerminal has to block until SynchronousMC finishes. The echo function, however,should not block when a SynchronousMC is in progess. In this case, SynchronousMC should stop printing to all terminals until echo is finished, and then continue printing synchronously an all terminals.

We have a question about the behavior of our reads... here's a slightly modified example from the handout:

int len1, len2;

char buf1[4];

char buf2[10];

len1 = ReadTerminal(0, &buf1,4);

len2 = ReadTerminal(0, &buf1,10);

and suppose that we type this:

Hello\b\b\n

Our implementation will produce this:

len1=4

buf1="Hell"

len2=1

buf2="\n"

Our question is... should buf1 actually be "Hel" since there are two backspaces involved. Right now, our Readterminal will just return after the first four characters and the extra backspace will cause a bell and be ignored, since it's the beginning of the new buffer.

Answer

As you say, since you have 2 backspaces typed after "Hello" before reading you have to process those 2 backspaces leaving in the buffer Hel\n, whish, as you say, is what you should be reading.

that doesn't really answer our question.. our program will behave in that manner if there is no PENDING ReadTerminal, but our question really pertained to the situation where the user is inputting while there IS a pending ReadTerminal. If there is one pending, that call is actively awaiting input and our program gives it to it as soon as it is ready. I can't think of any other way to handle this, unless ALL calls to ReadTerminal wait for a '\n' effectively ending the possibility that the user can erase any input.

Answer

That is exactly what you have to do. Wait for the user to type a \n (wait until the end of line) to do the character processing to the current line and decide if you have enough chars to satisfy the pending ReadTerminal. You also have to take care of the case of outstanding chars in the buffer after a ReadTerminal, which should be read by the next ReadTerminal.

Currently, we are having functions that read from certain buffers do a while loop when those buffers are empty, until they have something put into them. Would it be ok to make a condition variable outside of any monitor or semaphore for those to wait on when they detect an empty buffer, and have functions that put items in the buffers signal that condition variable when they have done so? the code that would be affected looks like this: while(tm[term]->out_begin == tm[term]->out_end); and would be changed to something like: while(tm[term]->out_begin == tm[term]->out_end) wait(tm[term]->wrotecv;

Answer

Yes, that is a valid way to do this, and probably better than just busy waiting in your while loop.

what should be the behaviour of synchronous multicast when you type to one of the terminals that the cast is affecting?

Answer

The echo functionality of your terminal should have precedence over any user program which is outputting to the terminal. So the echo and multicast output should be interleaved. If this doesn't make sense, please email me back.

Our Drivers seem to choke when we hit escape a few times. Is that okay? or do we have more work to do?

Answer

I think that typing escape actually puts more than one character as input to your program. So this is a harder test to put your driver through. You need to make sure that your ReceiveInterrupt function is as short as possible; if it's crashing when you hit escape a few times, you might have something in it that's causing it to not respond fast enough. If you feel that it's short enough, you might want to go talk to a TA in their ofice hours today.

Is it necessary to have sem_p calls and sem_v calls in a one to one ratio? by this i mean: with monitors, you can signal as many times as you want, the uncaught signals are simply ignored, so signalling extra times does nothing (essentially) if we implement semaphores to have a similar activity, is that valid? (ie, when our semaphore is negative or 0, we increment, but if its already one, we don't signal anything, ie, essentially ignore it) or do we need to enforce the 1:1 ratio of p's and v's? (but if you start the semaphore with value 0, you will have one extra v, but the rest will be 1:1, if you start it at -1, you will have two extra v's, etc..)

Answer

By definition, counting semaphores should not have uncaught signals. So you need to enforce a one to one ration of P's and V's. If you have any other questions, please email me back.

In sem_v, is it necessary to grab the mutex? because if it is, then it seems that we would not be able to use sem_v in our receive interrupt. or are we thinking in the wrong direction entirely?

Answer

Yes, you need to grab a mutex in sem_v because you are changing the value of a shared variable. But it is ok to call sem_v in your receive interrupt because this mutex should only be grabbed for very short periods of time in your sem_v and sem_p functions.

the specs say that the echo takes priority over everything, i. e. if a key is pressed we have to output that before any other output takes place. what if my WriteTerminal processes an \n character and so has to output \r\n to the screen? is echo allowed to break \r\n sequence, so if i pressed j, i would have \rj\n, which wouldn't look right on the screen, or should i treat \r\n as 'one character'?

Answer

You should treat the \r\n as one character. If you have any other questions, please email back.

I have two questions about the Makefile: 1. What do "clean and squeaky" mean? 2. what does $@ represent?

Answer

If you look at the Makefile, squeaky and clean both represent different targets. They both remove different files, which you can see by the "rm" line following them. The $@ is a macro which represents the current target. For example, in our sample makefile, $ALL represents montty semtty and sem-test. So the $@ would represent montty, then semtty, then sem-test respectively. I suggest that you read the man page on make. It's very helpful in understanding how makefiles work.

Okay, one more SynchronousMulticast question: If we're in the process of doing a write on one terminal, and then get a SMcast on that terminal and another terminal, is it okay to print the first character on the other terminal before the first one finishes? i.e.:

tty0:
...stuvwxyz.0*1*2*3*
tty1:
     0*       1*2*3*...

Answer

What about a transmit delay of 0 ms? Do we have to properly support that, or not?

Answer

Nah -- I don't think infinitely fast input is a likely real-world situation. I've seen solutions seem to work reliably with this parameter set to 0, but to be honest, I'm not sure that the underlying code can actually guarantee that.

I am a little confused about what we can and can't do with regards to busy waiting. This is a busy wait: while(blah); But this is not: while(blah) cond_wait(condition variable,mutex); right? So since we can't use busy waiting for the transmit interrupt, is this a solution which doesn't violate Mesa semantics?

In MainPrintingThread:
before:                     after:
lock=1                      lock=1;
WriteDataRegister('char');  mutex_acquire(term_mutex);
while(lock);                WriteDataRegister('char');
                            cond_wait(term_cn,term_mutex);

In TransmitInterrupt:
before:                     after:
lock=0                      cond_signal(term_cn,term_mutex);
	                    mutex_release(term_mutex);

Answer

Your solution looks fine to me. It's ok for one function to acquire a mutex and the other to release it in this case.

Synchronous Multicast is not allowed to overlap on a given terminal with either other multicasts or with writeterminals. That creates a deadlock problem - if two multicasts have overlapping targets and happen to enter the writeterminal monitors of some of the targets each, neither could proceed. The only way I can think of fixing this (at least for the monitor implementation) such that neither deadlock nor livelock is possible is to have a global monitor, so only on cast can be grabbing terminals at a same time. (although that is still an imperfect solution.. since a cast could go forward (all of its terminals are free) could be forced to wait in a queue for another which can't go forward - but that's another problem). However, there is no way to initialize a mutex at the beginning of execution, and initializing it from a terminal would be difficult, since then it could end up initialized multiple times. Is there a way to work around this problem (initializing a mutex), or is the above approach incorrect for solving the deadlock / mutual exclusion for multicast problem?

Answer

You could initialize this mutex in the first InitTerm call. Just use another global to keep track of whether or not InitTerm has been called or not. I think your global mutex solution would work, and as usual, just be able to justify it in your demo.

We were wondering if there is a limit to how many threads we can spawn, and if it is a bad idea to spawn say, a thread for each character needs to be echoed (it would end once that char was printed). Basically, we're wondering if it would be a bad idea to create so many threads.

Answer

I don't think it's such a good idea to spawn so many threads, even though you'd be killing the immediately. I'm not sure why you think you need to do this. I suggest you talk to a ta during office hours tomorrow.

Let's say that terminal 1 is currently WriteTerminal()ing the uppercase alphabet and has the lowercase alphabet 'queued'. At this point, someone does a SynchronousMulticast including terminal 1 of the digits. Which of the following would be the correct behavior:

a)
ABCDEFGHIJKL0123456789
MNOPQRSTUVWXYZ
abcdefghijklmnopqrstuvwxyz

b)
ABCDEFGHIJKLMNOPQRSTUVWXYZ
0123456789
abcdefghijklmnopqrstuvwxyz

c)
ABCDEFGHIJKLMNOPQRSTUVWXYZ
abcdefghijklmnopqrstuvwxyz
0123456789

Answer

c) is correct.

If a WriteTerminal does a newline, and there is input on the current line (i.e. no return typed by the user), is it OK if backspace 'removes' the characters from the buffer without removing them from the screen?

Answer

This is okay. But as with any of these subjective behaviors, be prepared to defend your answer to the grader.

Is the 'one mutex per function, at the beginning and end' restriction absolute? Depending on the answer to question 1, it seems like it would be much simpler to implement SynchronousMulticast with additional mutexes. I can implement the additional spinlocks myself without using the mutex library, but it seems a bit silly to do so...

Answer

The one-mutex-per-function applies ot the entry queue. You can use a similar mutex-condition variable pair to implement a wait/blcoked queue. This is the best approach to the SynchronousMulticast problem given the monitor constraint.

How do you feel about waiting on the value of a variable to change with something like: "while(something) {}" ?

This can be avoided with monitors. Maybe it can be avoided with semaphores, but does it have to be?

Answer

In general, busy-waiting is not a good thing -- it burns cycles. Typically it isn't too hard to avoid it in the semaphore-based solution.

There can be cases where it is more efficient than other solutions, because of very short critical sections. But these can usually be addressed with mutexes.

We'd really prefer that you use semaphores as the only synchronization mechanism in the semaphore-based implementation. If you do something like this, you need to be able to discuss a specific semaphore-based alternative with the grader and explain why the busy-waiting approach is better.

Can we assume that the list of terminals provided for synchronousmulticast has no duplicates? (in the current implementation, it would cause a rather unpleasant deadlock.. sort of like the philosopher picking up the left fork.. then trying to pick up the left fork again). If we can not assume that, then should we
1) return an error on such an attempt
2) silently remove the duplicate and ignore it
or
3) somehow handle it (have twin outputs to one terminal?)

Answer

I think all three options sound reasonable. As always, just be ready to justify why you picked one of them during the demo.

How should our program behave if a user program calls a WriteTerminal on a string containing a "\b" character?

Should it simply ignore it and print out the "\b", or treat it as an actual backspace, printing "\b \b"?

Answer

It should print "\b".

If a ReadTerminal thread is going on, can a WriteTerminal thread interrupt it? It should be possible to have WriteTerminal (or multicast output) appear while other threads are waiting for ReadTerminals to complete.

We just wanted to make sure of something about the sem_t declarations.

in the testing program, should we assume they do the following?

(A)                     (B)
sem_t *s;               sem_t

sem_create(s);          sem_create(&s);
...
sem_destroy(*s);        sem_destroy(s);

Answer

B) is correct.

I was testing my implementation of character processing, and I came across a question.

If I have a WriteTerminal going to the screen and I type on my terminal a backspace, should it erase the characters on the screen from the WriteTerminal?

Answer

Yes.

Must synchronous multicast finish outputting all of its output before a WriteTerminal can run? Or can there be entire WriteTerminal outputs between characters of a Synchrounous multicast?

Answer

The synchronous multicast is "atomic". So, there shouldn't be any WriteTerminal output in the middle of the output of a multicast.

What semantics will the testing program use for invoking sem_create and sem_deestroy?

Answer

sem_t s;

sem_create(&s);
...
sem_destroy(s);

When a the terminal's input buffer is full and Enter is pressed, should the newline simply be ignored or should an end-of-line be signalled but the newline not be placed in the buffer? (Or is there a third behaviour which is correct which I don't know about :) ?

Answer

In general, you can choose any reasonable behavior for this scenario (but, be able to describe why you chose that behavior during the demo). Unreasonable behaviors include dumping core, or locking the terminal so that no more characters could be read. Dropping character(s) is reasonable. One thing that it might help to consider here is what would happen if the user fills the entire buffer up with numbers, then presses eneter after the buffer is full. It should be possible for a ReadTerminal to eventually complete.

In the assignment spec it says that we should check the validity of the bounds of the buffers passed to WriteTerminal and ReadTerminal. Is this important? Is there an easy way to do this?

Answer

You should check the obvious cases, for example NULL pointers. While there are kernel-level functions which allow the OS to check the validity of memory pointers, I'm not aware of any easy way to do this at the user level. Therefore, you don't need to check whehter the pointer references valid memory.

On occasion, when we get a little adrenaline rush, and we're able to thrash our fingers REALLY quickly, we sometimes get a "new char written while old one still unread" core dump - our ReceiveInterrupt is apparently not tossing the character into the buffer and returning quickly enough. Do we have to do some optimzation to make ReceiveInterrupt handle things even fast beyond our current implementation, or is handling "pretty fast keyboard input" good enough?

Answer

You should be able to handle the keyboard thrashing and cut-and-paste scenarios with a delay of 1 ms. We won't test these cases with a delay of 0 ms.

I had a question about backspacing when a WriteTerminal is happening. I wasn't quite sure from the assignment spec whether we should just echo the '\b \b' sequence even if there is a WriteTerminal happening (and thus delete one of the outputted chars) or account for it by not echoing the sequence.

Answer

The details of this are unspecified. You should do what makes sense to you and be prepared to justify your decision as the "user friendly" or "intuitive" approach to the graders.

How important is the speed of Synchronous Multicast? In our semaphore implementation, right now we're blocking after each character we send, to assure that if, say, one terminal is doing a WriteTerminal, or echoing, all others will have to wait. This works properly, according to the definition given in the handout. However, it goes somewhat slowly, because it is blocking after each character. (Terminal i+1 doesnt get the next char until terminal i has gotten confirmation of output from the TransmitInterrupt) We figure that we could make it run faster if we spawn separate threads for each terminal, and just assure that everybody has output the current character before moving on. (Terminal i+1 could output before, at the same time as, or after terminal i, but it wouldn't move on to the next char until EVERYONE was finished.)

Answer

Clearly this offers a big performance improvement and is a better solution. It reduces the (average case) time to perform a multicast (after it has begun) to number_of_characters * slowest_terminal_speed as compared to number_of_characters * number_of_terminals * average_terminal_speed. ...this is clearly a big win. I don't know how we'll grade the project, though. We don't assign "points off" until we review the entire collection of solutions.