Homework 7 Solutions
22C:116, Spring 1997
Ioana M. Lungeanu
Problem 1:
Suppose the UART has the following 3 ports:
TBUF the transmission buffer. Writing a byte in this port
will make the UART serialize it on the bus.
RBUF the receive buffer. The UART packs a received byte in it.
STATUS the status port. Contains at least the following 2 bits:
TxRDY transmit ready. This bit is set when TBUF is empty.
RxRDY receive ready. This bit is set when RBUF is full.
Here, we'll assume that transmission does not use interrupts and that
the receive interrupt is always enabled; this is a bad assumption, but
it simplifies things a bit.
Suppose also that writing and reading these ports is possible through
the following functions:
char IN(int port);
void OUT(int port, char data);
To send a byte on the bus, we must wait until TBUF is empty and then
write the byte in the TBUF. To read a byte from the bus, RBUF must
be full and then read the byte from RBUF. The following functions
are useful:
void send(char c) {
while(!(IN(STATUS) & TxRDY)); /* polling loop */
OUT(TBUF, c);
}
char receive() { /* used only when RxENAB is reset!
while(!(IN(STATUS) & RxRDY)); /* polling loop */
return IN(RxRDY);
}
The function send_packet() is used to send a fixed_size packet after
winning access to the bus. Here is a simple version:
void send_packet(chr *d, char a) {
/* send packet d of packet_size bytes to address a */
win_bus();
send(a);
(void)receive();
for ( i = 0; i < packet_size; i++) {
send(d[i]);
(void)receive();
}
}
The receive() calls here clear the bytes out of RBUF, preventing
the UART from reporting overrun errors (the error typically reported
if RBUF is not read before the next data byte is received from the
line).
This simple version of send_packet() could check each byte transmitted
for correct receipt and declare a collision if the byte is not
received correctly, but here, we don't do this. Also, we should
include a checksum in each packet. Here, we assume that this is
done by higher level code.
The win_bus() function handles the basic CSMA-CD function
void win_bus() {
for (;;) { /* loop exits with return */
while( busy ); /* wait while the bus is busy */
send( myAddress );
if (receive() == myAddress) {
/* if I receive what I sent, I may be the */
wait( JAMperiod );
if (IN(STATUS) & RxRDY) { /* it was a collision */
wait(rand());
} else {
/* I am the winner */
return;
}
} else { /* collision */
send(0xFF);
/* jam the bus */
wait(rand());
}
}
}
The receive_packet() function waits until the interrupt service
routine signals that a packet has been received, and then
copies it from the system buffer into the user's buffer. This
is trivial, so it isn't included here; a better design would have
the input interrupt service routine directly receive packets into
the buffers from the queued input requests, and discard received
packets in the event a buffer is not available. In addition, the
input interrupt service routine is responsible for detecting when
the bus is busy and when not. The following code is actually
fairly nasty and should not be used, because it has wait operations
in it! Nonetheless, it is easier to explain the basic algorithm
this way than to code it properly:
void interrupt receiveByte() {
c = IN(RBUF); /* read the byte received */
if(!busy) { /* if the bus was free */
/* wait to see if it was a collision */
wait(JAMperiod);
if (IN(STATUS) & RxRDY) { /* it was a collision */
return;
} else { /* somebody won the bus */
winner = c; /* c is the address of the winner */
busy = 1; /* the bus is busy now */
}
} else { /* during sending a packet */
if (receiveCount == 0) {
/* c is the destination */
packetForMe = (c == myAddress);
} else {
/* in the middle of the packet */
if (packetForMe) { /* get the byte */
receiveBuffer[receiveCount++] = c;
}
receiveCount++;
if (receiveCount == packet_size) {
/* if the packet is finished */
receiveCount = 0;
busy = 0; /* the bus is free now */
if (packetForMe) {
/* tell user that a packet is in! */
signal( received );
}
}
}
}
}
Problem 2:
Transparency: Tannenbaum vs. Parnas
In Tannenbaum's view a distributed system would be said to be
transparent if it manages to hide from the user/programmer the
nature of the system, in such a way that the user is able to use
the system in the old fashioned way as if it were a plain, stand
alone machine.
For Parnas, a system is transparent if the upper layers can see
(and manipulate) states of the lower layers. For protection
purposes here it is desirable that the system be opaque. This is
closer to the normal meaning of the word "transparent". For
Tannenbaum transparency is more like the addition in complexity
given by a distributed architecture does not necessary stand in
ones way when the goal is to use this system as before.
Distributivity is transparent so one does not rally see it's
there with the naked eye.
Problem 3
In the early networks, the speed of data communications was
very low compared to the speed of computation. So the bottleneck
was the communication line. Under these conditions it seemed like
a good idea to layer the communication protocols on different
layers. This has a couple of advantages. Firstly splitting the
problem into small problems facilitates solving it, simplifies
each step making it less error prone, easier and faster to get
things done. Secondly, changes caused by advances in technologies,
better solutions and algorithms and the such, would involve one
one layer, so the are easier to make keeping the old modules still
functional. Of course there is a price to pay in overhed, both
for computations needed for passing from one layer to another,
and in extra bits in the final packet that is send over the line.
Assuming that the CPU is more heavily loaded by the layering than
the line, since the CPU was historically faster relative to the data
rates, the loss was not actally felt by the overall transmission.
If the gap between the two speeds decreases and becomes lower than
the time needed for the overhead computations, the layering
technique needs to be rethought. The number of layers need to be
decreased, and/or part of the burden of the machine's CPU must be
moved to new "inteligent" networks, at the lowest layer.