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 */
            for ( i = 0; i < packet_size; i++) {

    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

    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 */
                    } else {
                        /* I am the winner */
                } else { /* collision */
                    /* jam the bus */

    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 */
           if (IN(STATUS) & RxRDY) { /* it was a collision */
           } 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;
               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.