CMPE 401 - Computer Interfacing

Assignment #1

Model Solutions

1. A task is an executing program, together with its context, that can can be stopped at one time, and then restarted later on. (It is possible for several different tasks to be executing multiple instances of the same program. Each such task would be distinguishable by its unique context.) Briefly describe the mechanisms that are required to allow tasks to be stopped at one time and then restarted later on by a multitasking kernel, regardless of the presence of other executing tasks.

   When a task is restarted, it must see exactly the same context that it had
   when it was last executing.  This implies several things:  (1) The CPU
   registers must be restored exactly.  This is usually done by having the
   kernel save the CPU registers in a Task Control Block (TCB) when the task 
   is stopped; when the task is restarted later, the CPU registers are reloaded 
   from the saved values in the TCB. (2) Other resouces that were being used
   by the task must also be protected from being altered.  Memory that was
   allocated dynamically by the operating system should be safe since such
   memory is usually only given out to one task at a time.  Other system 
   resources, such as network connections, might be protected from being used
   by other tasks using semaphores.  (However, care must be taken to avoid
   problems with deadlock if tasks can hold on to two or more resources,
   and there is no mechanism to force them to give up resources.)
   

2. Briefly describe the difference between soft and hard real-time constraints in the context of operating systems or kernels. Characterize each of the following control problems as either soft or hard real-time: (a) control of a robot manipulator arm on a car assembly line; (b) an electronic poker game; (c) a building door-lock control system; (d) a train engine control system; and (e) a video lottery terminal. Briefly justify your classification in each case.

   The difference between soft and hard real-time constraints is qualitative.
   Soft real-time problems are computer applications where sufficiently
   fast and deterministic response times can be obtained using a conventional
   operating system such as Microsoft Windows or UNIX.  Usually the operating
   system must be relatively lightly loaded.  Hard real-time problems 
   require faster and more deterministic response times than can be provided by
   a conventional operating system.  Instead one must use a specially-designed
   operating system like MicroC/OS-II.  (It is also possible to augment
   conventional operating systems with hard real-time subsystems that ensure
   fast response for some signals.)
   
   (a) A robot manipulator arm is hard real-time because its movements must
       be controlled over short time scales.  Also, the consequences of overly
       slow real-time response could be catastrophic in a production line.
   
   (b) An electronic poker game is a soft real-time application.  It could be
       successfully run on a computer with a conventional operating system.
       However, if the game is to be portable, then one would not likely use
       Windows or UNIX as the operating system because of the limited memory.
       There is a reduced size version of Windows, called Windows CE, which
       might be used.  Also, a scalable kernel such as Micro/OS-II might be
       appropriate.
   
   (c) A building door lock control system is likely to be soft real-time.
       (Indeed, the card lock system in the ECERF building is controlled by
       a Macintosh PC.)  The consequences of slower or slightly nondeterministic
       response time are going to be minor since humans are involved.
   
   (d) As in example (a), the problem is likely to be hard real-time.  A train
       needs to be control with great temporal precision to guarantee smooth
       operation and to avoid damage and possibly accidents.
   
   (e) A video lottery terminal is likely to be soft real-time since the main
       interface is with humans involved in a recreational activity.  Safety
       is not a factor.  To reduce cost one might use a simpler operating system
       than Windows or UNIX, however.
   

3. The 68000 family of microprocessors has a rich set of addressing modes and a relatively large instruction set. For this reason the 68000 microprocessors are called complex instruction set computers (CISCs). A contrasting style of computer architecture is the reduced instruction set computer, in which the number of addressing modes and instructions is much smaller than in a CISC. The 68000 was designed at a time (in the late 1970s) when most microprocessors were programmed primarily in assembly language. Why then would a CISC architecture be viewed as being more attractive at that time compared to a RISC architecture? At the present time, when most microprocessors are programmed using compiled programs, why would the RISC architecture be viewed as being more attractive compared to a CISC architecture? Why are most modern processor architectures today a compromise between the CISC and RISC styles?

   In the 1970s and the early 1980s, microprocessors were generally programmed
   using assembly language.  This was done because efficiency was a primary
   concern when pushing to use microprocessors in new and, at that time, rather
   demanding applications.  There were relatively few software developers, and
   many of them could be assumed to be experts at designing very compact and
   efficient assembly language code.  They could benefit from fancy address modes
   that permitted significant gains in efficiency and performance.  Thus to make
   microprocessors more attractive to potential customers, it was important to
   provide the kinds of features (many instructions and many addressing modes)
   that allowed for efficient assembly language programming.  It is also true
   that larger, mainframe computers tended to have CISC architectures, and
   microprocessor architectures tended to follow mainframe architectures.
   
   In the mid-1980s the RISC style of computer architecture became recognized
   as a useful way of increasing computer performance when the software was
   mostly compiled from high-level languages.  The basic idea of RISC is to
   simplify the computer hardware by restricting the number of addressing modes
   and instructions; in return the computer hardware will be simpler and can
   be made to run faster.  Improved compiler technology could be relied upon
   to produce code that made efficient use of the available addressing modes
   and instructions.
   
   Modern microprocessors usually have aspects of both the CISC and RISC
   architectural styles.  The most popular architectures tend to be a compromise
   between an older pre-existing architecture (which must stil be supported to
   keep customers happy) with new features that were added later.  It is rare
   to have the luxury of designing a "clean" new architecture from scratch.
   

4. Briefly explain how the architecture and implementation of MicroC/OS-II makes it easier to port across a variety of different computers. Focus your comments on the main features that enhance portability.

   The main features that enhance the portability of MicroC/OS-II are:
   
   (a) The kernel is written in ANSI C, which is probably the language that is
       supported across the greatest number of different computer architectures.
   
   (b) The features of MicroC/OS-II can be readily accessed by means of
       subroutine calls from application programs written in C.
   
   (c) The software architecture of MicroC/OS-II has been partitioned to hide
       machine dependencies within a relatively small and well defined
       "processor port".  When migrating a system to a new machine architecture,
       the changes will be mostly, if not entirely, restricted to this piece
       of software.
   
   (d) MicroC/OS-II makes relatively few assumptions about the underlying
       hardware.  There must be a CPU to execute compiled ANSI software.
       There must be a hardware timer resource to provide software-independent
       timing for use in functions with programmable real-time time delays.
   

5. Consult the on-line documentation for the CPU32 (follow the links on the course homepage) and then, in your own words, briefly explain how the TBLU and TBLS instructions work. Give a simple example of how each instruction could be used.

   The TBLU and TBLS instructions are intended to simplify the calculation
   of interpolated values based on tabular data.   TBLU provides unsigned
   interpolation with rounding, while TBLS provides signed interpolation with
   rounding.  (Note: There are two other similar instructions, TBLUN and
   TBLSN, which provide unsigned and signed interpolation with no rounding
   of the result.)
   
   The destination operand is always a data register, Dn, which contains the
   independent variable (the variable input for the interpolation).  Bits 15:8
   of Dn hold the integer value of the independent variable: in tables, this
   number gives the index of the first table value.  Bits 7:0 of Dn are a 
   fraction that determine the the interpolation factor between the first
   table value and next table value.  The table values can be given in
   two ways: (1) as an effective address that points to the first long word,
   word or byte in a table of values located in memory; or (2) as two named
   data registers.  An example of the first form is "TBLU.W (A0),D1" and
   of the second form is "TBLS.B D1:D2,D3".  Note that the suffix of the
   instruction mnemonic (.L, .W or .B) gives the size of the table values.
   Note also that bits 15:9 in the destination data register Dn are ignored
   in the second form of the instructions because the two adjacent table
   values can be assumed to be preloaded in the first two data registers.
   
   The unsigned and signed forms determine whether or not the most significant
   bit in the data values is a magnitude bit (unsigned form) or a sign bit
   (signed form).
   

6. The original 68000 microprocessor supported only 8-bit and 16-bit displacements in the branch instructions. (32-bit displacements had to be performed using jump instructions instead.) The CPU32, however, supports 8-bit, 16-bit and 32-bit displacements. Briefly explain what changes were required in the instruction formats to support the larger, 32-bit displacements.

   The added capability was to support 32-bit displacements.  Compared to
   instructions with 16-bit displacements, the new instructions with
   32-bit displacements would require one more word to hold the additional
   16 bits.  68000 instructions have one operand word followed by zero or
   more additional words that specify the addressing modes for the source
   and/or destination operands.  The instructions affected by the change
   already support 16-bit displacements.  To create the new instruction
   format, one could simply modify these instructions by adding a second
   16-bit displacement word right after the 16-bit displacement word
   in the existing instruction format.
   

7. Design a subroutine in 68000 assembly language, to be called READ_DATA, that retrieves the three data fields in a packed list of 11-bit-long records. Each record contains (going from the most significant bit to the least significant bit position) one 4-bit field, one 5-bit field, and one 2-bit field. The records are packed together, without leaving any unused bits, starting at a particular base address in memory. The records are numbered in increasing order, starting with zero. The packed list has a limited size, so there is a maximum allowed record number.

   Your subrountine is to accept two input parameters: the base address of the list in A0.L and the record number in D0.W. The three record fields are to be returned in D1.B, D2.B and D3.B. Register D7.B is to be zero if the record was accessed successfully; otherwise, it is to contain the value one. Your routine is to calculate byte addresses, instead of doing a linear search through the packed list.

   READ_DATA:
           MOVEM.L  A0/D0-D3,-(SP)      // save CPU regs
   
           MOVE.B   #0x01,D7            // assume failure
           CMP.W    #MAX_RECORD_NUM,D0  // compare record number with maximum
           BHI      EXIT_READ_DATA      // exit if number too bit
           CLR.B    D7                  // now indicate success
   
           MULU.W   #11,D0              // compute bit offset to 11-bit record
           MOVE.L   D0,D4
           LSR.L    #3,D4               // form byte offset to record's 1st byte
           ANDI.B   #0x07,D0            // form bit offset into that byte
           MOVE.L   (0,A0,D4.W),D3      // fetch longword containing record
           LSL.L    D0,D3               // left justify record to bit #31
   
           MOVE.L   D3,D1
           LSR.L    #28,D1              // right justify the first field
           ANDI.B   #0x0F,D1            // trim 4-bit field as a precaution
   
           MOVE.L   D3,D2
           LSR.L    #23,D2              // right justify the second field
           ANDI.B   #0x1F,D2            // trim 5-bit field as a precaution
   
           LSR.L    #23,D3              // right justify the third field
           ANDI.B   #0x03,D3            // trim 2-bit field as a precaution
   
   EXIT_READ_DATA:
           MOVEM.L  (SP)+,A0/D0-D3      // restore CPU regs
           RTS