CMPE 401 - Computer Interfacing

Assignment #4 Solutions

1. The Lightweight IP stack has a software architecture that is intended to help achieve several goals: (1) portability across processors; (2) portability across operating systems; (3) portability across communications hardware; (4) minimum memory requirements; and (5) fast processing speed. Briefly explain how architectural and design features of lwIP were used to achieve each of these goals.

   [15 marks]
   

   1. Portability across processors is maximized by coding the implementation of lwIP in standard ANSI C. This language is likely the most widely supported high-level language, with compilers available for most processors.
   2. Portability across operating systems is maximized by the fact that lwIP makes only very few basic assumptions about the operating system. For example, lwIP expects to be able to: (a) set one-shot hardware timers with at least 200 ms resolution; (b) have access to a semaphore synchronization mechanism; and (c) have access to a mailbox system, which has a nonblocking message post function and a blocking receive message function. The operating system specific code in lwIP is contained within an "Operating System Emulation Layer", which makes it easier to modify lwIP to work with new operating systems.
   3. Portability across communications hardware is maximized by accessing all network interfaces through device drivers. The device drivers are used in the same way by lwIP, thus shielding lwIP from hardware differences. Hardware-specific details of each network interface are contained inside the corresponding device driver, so it is easier to accommodate new hardware by developing new device drivers.
   4. Memory requirements are minimized by the way that lwIP uses its own buffer system, in which a common buffer format is used in all protocol levels. Duplicate copies of buffer data are thus avoided, but at the cost of less strict partitioning between layers.
   5. Fast processing speed is achieved by avoiding unnecessary copying of data across the protocol layers. Also, the entire stack is implemented within one task, thus minimizing the required inter-task communication.

2. Direct Memory Access (DMA) implements what is effectively a block move operation, which usually terminates with an interrupt to alert the CPU that the transfer has finished. A technical challenge exists when DMA is used in a computer with virtual memory. With virtual memory, the amount of information (programs and data) in a CPU's memory space exceeds the size of available fast semiconductor memory (usually DRAM), and most of the information must be stored in slower mass storage devices such as hard disks. To speed up the effective access time to stored information, fixed-size pages (i.e., buffers) of information are brought into regions in a faster physical memory space (usually implemented using DRAM). Address translation hardware is used to translate virtual addresses (used by the software) into physical addresses (used to locate information in the fast physical memory). A DMA controller (DMAC) could be installed to use either physical addresses or virtual addresses. Briefly explain what the advantages would be for a DMAC to use physical addresses or virtual addresses.

   [10 marks]
   If the DMA controller were to use physical addresses, then the biggest advantage would be that there would be no need to translate virtual addresses to physical addresses during the transfer. Thus there would be no need to have a separate address translation circuit for the DMA controller. However, the DMA operation would likely need to be restricted to accessing information within the same page of physical memory, and the contents of that page would need to be kept unchanged for the duration of the DMA transfer.

   If the DMA controller were to use virtual addresses, then the main advantage would be that the DMA transfer could use the same addresses as those used by the software that is executing on the CPU. The DMA transfer could go across page boundaries in physical memory (although there would be an access time delay if a page fault occurred and a new page had to be brought into physical memory). The extra cost would be the need for an address translation circuit for the DMA controller. The address mappings in that circuit would have to be kept synchronized with the address mappings in the address translation circuit used by the CPU.

3. Both ping-pong buffers and first-in first-out (FIFO) buffers can be used to absorb short-term mismatches in the data rates of a producer process with a consumer process. Briefly describe what the likely advantages and disadvantages would be of a ping-pong buffer versus a FIFO? What aspects of a particular application would lead you to pick one buffer method over the other?

   [10 marks]
   The advantage of a ping-pong buffer is that the data writing and data reading processes can access the data stored in their respective buffers in any arbitrary order. For example, the elements of a matrix could be written row-by-row into the write buffer, and then read column-by-column from the the read buffer. Also, only some of the buffer needs to be read out of the read buffer, and it can be read out in any order. In a FIFO the data must be written (by the write process) and read (by the read process) in exactly the same order. An added complication and disadvantage of a ping-pong buffer, however, is that some mechanism needs to be designed that determines the time instants when the read and write buffers can be safely swapped.

   The advantage of a FIFO buffer is that it is a very simple way of temporarily adding delay to an ordered stream of data. No addresses need to be provided at the write and read ports of the FIFO. No complicated mechanism is required to manage the storage of data inside the buffer; the only complexity is that the read and write pointers need to be wrapped around to avoid going beyond the fixed boundaries of the of the buffer. The disadvantage of a FIFO is that the data can only be written and read in the same fixed order.

4. A circular buffer is accessed by exactly one writing process, and can be accessed by one or more read processes. Design pseudo-code that shows how a circular buffer with one writing process and two reading processes could be implemented.

   [25 marks]
   Two separate read addresses or pointers need to be maintained. There must be a way of tracking which of the read addresses is the furthest behind in reading data. If the one write address reaches the slowest read address, then the buffer is declared to be full. The two read ports will have separate buffer empty status conditions since the buffer can be empty with respect to one of the read ports, but not empty with respect to the other. Interestingly, the buffer can at the same time be full with respect to the write port, but empty with respect to one of the read ports.

   void procedure init_cir_buf( void )
   begin
     empty_flag1 = true;
     empty_flag2 = true;
     full_flag = false;
     write_addr = min_buf_addr;
     read_addr1 = min_buf_addr;
     read_addr2 = min_buf_addr;
     slowest_read_addr = min_buf_addr;
     read_addr1_is_slowest = true;
     read_addr2_is_slowest = true;
   end;
   

   err_type procedure write( data_type data_elem )
   begin
     if full_flag then return( ERR_BUF_FULL );
     else
       buffer( write_addr ) = data_elem;
       empty_flag1 = false;
       empty_flag2 = false;
       write_addr++;
       if ( write_addr > max_buf_addr ) then
         write_addr = min_buf_addr;
       endif;
       if ( write_addr == slowest_read_addr ) then 
         full_flag = true; 
       endif;
       return( ERR_OK );
     endif;
   end;
   

   err_type procedure read1( data_type *Pdata_elem )
   begin
     if empty_flag1 then return( ERR_BUF_EMPTY );
     else
       *Pdata_elem = buffer( read_addr1 );
       read_addr1++;
       if ( read_addr1 > max_buf_addr ) then
         read_addr1 = min_buf_addr;
       endif;
       if ( read_addr1 == write_addr ) then empty_flag1 = true; endif;
       if ( read_addr2_is_slowest ) then 
         read_addr1_is_slowest = false;
       else
         slowest_read_addr = read_addr1;
         full_flag = false;
         if ( read_addr1 == read_addr2 ) then
           read_addr2_is_slowest = true;
         endif;
       endif;
       return( ERR_OK );
     endif;
   end;
   

   err_type procedure read2( data_type *Pdata_elem )
   begin
     if empty_flag2 then return( ERR_BUF_EMPTY );
     else
       *Pdata_elem = buffer( read_addr2 );
       read_addr2++;
       if ( read_addr2 > max_buf_addr ) then
         read_addr2 = min_buf_addr;
       endif;
       if ( read_addr2 == write_addr ) then empty_flag2 = true; endif;
       if ( read_addr1_is_slowest ) then 
         read_addr2_is_slowest = false;
       else
         slowest_read_addr = read_addr2;
         full_flag = false;
         if ( read_addr2 == read_addr1 ) then
           read_addr1_is_slowest = true;
         endif;
       endif;
       return( ERR_OK );
     endif;
   end;
   

5. TCP uses a window-based flow control strategy to ensure that all data bytes arrive at the receiver without overwhelming the receiver. The flow control method operates independently in both directions. Briefly explain how the transmitter determines whether or not to retransmit data packets, and explain how that ensures that information bytes in lost packets will eventually get received correctly at the receiving end (in one direction). Be sure to mention why TCP needs to have the ability to set a certain number of timers to be able to provide its services.

   [10 marks]
   A TCP transmitter assigns a sequence number to each byte that it transmits, and it uses the sequence number of the first data byte of a segment as the sequence number for the entire segment. The TCP transmitter determines how many bytes have been safely received at the TCP receiver by monitoring the acknowledge numbers that appear in TCP segments travelling in the opposite direction along the same connection. The acknowledgement number gives the sequence number of the next byte that is expected at the receiver, and so all bytes up until the immediately preceding sequence number can be assumed to have been received at the other end.

   Whenever a segment is sent, a one-shot timer is started that will expire at some reasonable maximum time in the future. Such a timer is required to cause the TCP transmitter to eventually retransmit data bytes if they are never acknowledged. It is essential that the TCP transmitter not wait forever since that would "hang" the connection; retransmission of lost packets allows the TCP connection to recover in a predictable way from lost segments. The value of the time-out delay is typically set to be about twice the expected round trip delay for the connection.

6. In TCP, briefly explain how the receiving end can prevent itself from being overwhelmed with more data that it can handle.

   [10 marks]
   The TCP entity at the receiving end in one direction of a connection can avoid getting overwhelmed with arriving data using the following different mechanisms. First, when the TCP connection is first established, the receiver sends back to transmitter at the other end the maximum window size that it can handle. This window size can be set to zero to completely disable transmissions (like an X-OFF). Second, the receiver can delay or withhold sending back acknowledgements to the transmitter. Any further received TCP segments could be discarded as an emergency measure, and the transmitter can be relied upon to continue to retransmit them each time the transmission time-out expires.

7. In the context of a stepper motor with three phases, explain how one could implement full stepping and half stepping. Be sure to provide a table that shows how the three pairs of stator windings (i.e. three phases) would be energized. Whenever a phase is energized, be sure to indicate the direction of polarization.

   [20 marks]
   In full-stepping all of the phases are energized all of the time to ensure maximum torque on the rotor. In the case of a three-phase stepper motor one would obtain the following full-stepping phase control sequence:

   Step #	Phase A	Phase B	Phase C
   1	forward	forward	forward
   2	reverse	forward	forward
   3	reverse	reverse	forward
   4	reverse	reverse	reverse
   5	forward	reverse	reverse
   6	forward	forward	reverse

   In half-stepping the total winding current is allowed to vary, and this flexibility allows some windings to be turned off to produce additional rotor step positions. In the case of a three-phase stepper motor one would obtain the following half-stepping phase control sequence:

   Step #	Phase A	Phase B	Phase C
   1	forward	forward	forward
   2	off	forward	forward
   3	reverse	forward	forward
   4	reverse	off	forward
   5	reverse	reverse	forward
   6	reverse	reverse	off
   7	reverse	reverse	reverse
   8	off	reverse	reverse
   9	forward	reverse	reverse
   10	forward	off	reverse
   11	forward	forward	reverse
   12	forward	forward	off