CMPE 401 - Computer Interfacing

Assignment #1 Solutions

1. Briefly describe the difference between serial and parallel digital interfaces. What are the major advantages and disadvantages of serial versus parallel digital interfaces? Why do you suppose that interfaces for connecting external PC peripherals (e.g., scanners, external hard drives, webcams) are increasingly using serial interfaces such as USB and Firewire instead of parallel interfaces (e.g. the Centronics printer interface)?

   [15 marks]
   In a serial digital interface, the data bits going in one direction (e.g. from system A to system B) must travel one-by-one over the same electrical connection. Likewise, the data bits travelling in the opposite direction (B to A) must travel one-by-one over another connection. (There are also clever ways of using one wire to carry the signals for both data directions.) A serial interface may contain additional wires to provide control signals, timing signals, a shared ground connection, etc. In a parallel digital interface, there are multiple data-carrying connections that can communicate multiple bits at the same time.

   A serial interface has the advantage of requiring fewer wires than a parallel interface. Fewer wires will usually imply lower cost because of the reduced wiring and smaller connectors. The disadvantage of a serial interface is that the data bits must be communicated at a higher bit rate than a parallel interface to obtain the same total rate of bits transmitted.

   The recent interfaces for connecting peripherals to PCs are increasingly serial interfaces in order to simplify the installation hassles and to keep the cabling costs low for very price-sensitive consumer products. Older PC standard interfaces evolved in a somewhat chaotic way. The new interface standards are attempts to simplify the situation by agreeing to use a smaller number of universal standards that can connect to many different kinds of peripheral devices. The newer interfacing standards also include standardized software and autoconfiguration features (e.g. plug and play capability) to further simplify the installation hassles for consumers.

2. What is the purpose of a task control block (TCB) in a kernel or operating system? What task-specific information would one expect to find in the TCB, and what task-specific information would be omitted? What determines which information should be included in the TCB?

   [20 marks]
   The task control block is a data structure that is used to store task state information during the time that it is not actually running on the CPU. The TCB must contain enough information to allow the task to be restarted later on in exactly the same state as the time when it was last suspended (or when it was first created).

   The TCB will be organized to be general enough to handle all the different types of tasks that are expected in the kernel or operating system. Bulky data fields will be avoided since they will take too long to copy; pointers will be used instead in such situations. Resources that were obtained by the task, such as dynamically-allocated objects in memory or dynamically-allocated network connections, might not be stored in the TCB since only that task will have access to those resources and so the resources will be left alone when the task is not running. On the other hand, having pointers to those resources is probably safer since this would make it easier to terminate the task (without having to have its cooperation) and release all of the system resources that were associated with the task. Determining which task-specific information can be left out of the TCB is not always a simple matter, especially in a complicated system.

   In MicroC/OS-II, the TCB contains many fields including the following:

   • The task's current state (e.g. blocked, suspended, ready-to-run, etc.).
   • The task's priority (e.g. an integer from 0 to 63).
   • A pointer to the current top of stack location in the task's stack region. The upper region of the task's stack contains the saved contents of all CPU registers (e.g., data registers, address registers, status register, program counter).
   • A pointer to a task-specific TCB region.
   • The task's stack size.
   • A pointer to the bottom of the stack.
   • An extended task ID.
   • A pointer to the event control block (ECB) of the kernel object (e.g., a semaphore) that is currently blocking the task.
   • A pointer to the first waiting message that is associated with the task.
   • A time field that is used (1) to keep track of the time in ticks if the task has been suspended for a fixed amount of time; and (2) to keep track of the time elapsed when a maximum time-out was specified when the task pended on an event.
   • Pointers to the next and previous TCBs, to allow the creation of a doubly-linked list of TCBs.

3. In a preemptive multitasking kernel, the various tasks are associated with an ordered set of priorities. The highest-priority ready-to-run task is always supposed to be executing on the CPU (as long as there is no active interrupt being serviced). The kernel software is responsible for enforcing this constraint. What events, therefore, must be monitored by the kernel to allow for the possibility of a context switch from one task to second task with higher priority? Hint: Review the events in lecture slide 3-11.

   [15 marks]
   Every event that could possibly create a new, highest-priority, ready-to-run task must be closely monitored by the kernel so that a necessary context switch can be triggered immediately. Here are a few examples, taken from the state transition diagram on lecture slide 3-11, where the kernel must "switch the context" to a new highest-priority ready-to-run task:

   • The currently running task suspends itself.
   • The currently running task pends to a semaphore and is blocked because the semaphore count is zero or negative.
   • The currently running task starts to wait for a requested time delay.
   • The currently running task is interrupted, and the interrupt service routine causes a higher-priority blocked task to become unblocked.

4. What is meant by a real-time operating system as opposed to an ordinary operating system? What is the difference between hard real time and soft real time? Give two examples of each kind of real time problem.

   [20 marks]
   A real-time operating system is one that is designed to respond promptly and with predictable response time to external events. Real-time operating systems are widely used in industry to allow computers to control moving machinery (e.g. vehicles, robots) and industrial processes (e.g. sawmills, refineries).

   Hard real time refers to a computer interfacing problem that requires the use of a specially designed real time kernel or operating system so that the response time is both fast and predictable (e.g. deterministic). An ignition control system in a car engine would be a very demanding example of hard real time. The timing contraints are such that a mostly hardware-based solution (with very little executing software) may be required. An assembly line robot is a somewhat less demanding hard real time application that would be slow enough to permit extensive software-based control, but too demanding to be satisfactorily solved using an ordinary commercial operating system like Unix or MS Windows.

   Soft real time refers to a computer interfacing problem that can be adequately solved using conventional operating systems, provided that they are not too heavily loaded with work. For example, the card lock system in a building requires only modest response times because the users are humans. A vending machine is another example of a soft real time problem. Word processing software, spreadsheets, and most PC-based computer games are further examples of soft real time problems.

5. A typical human reaction time is about 200 milliseconds. The CPU32 inside the MC68332 microcontroller requires 2 clock cycles to execute the NOP (no operation) instruction. Assuming that the clock frequency is 16.78 MHz, what is the number of NOP instructions that will be executed within one human reaction time?

   [5 marks]
   Number of NOPs = 200 ms / (2 / 16780000) = 1.678 million

6. Design three MicroC/OS-II application tasks in C that share access to a database using a semaphore. The semaphore, called DB_IDLE, is assumed to be initialized to 1 by the start-up task. The first application task, ProducerTask, has an endless loop that alternately calls two functions: GetData and StoreData. GetData has no input arguments, but returns a pointer to a record of type DataType. StoreData has one input argument, a pointer to type DataType, and returns an error code. This error code is 0 if no error occurred, but is 1 if the database was full and could not store the new record (in which case the record is simply discarded). Outside of this critical section, ProducerTask is to update a global integer counter, DB_FULL, that records the number of times that calls to StoreData failed to store a record. StoreData is to lie in one critical section protected by semaphore DB_IDLE.

   The second application task, UpdateTask, has an endless loop that calls three functions in the following order: RetrieveData, UpdateData and StoreData. The three functions are to lie in one critical section protected by semaphore DB_IDLE. RetrieveData has no input argument and returns a pointer to a record of type DataType. The input and output arguments of UpdateData are both pointers to records of type DataType. StoreData has no input argument but produces an output argument that is 0 if a record was added successfully to the database, and is 1 if the record could not be added because the database was full. Outside of this critical section, UpdateTask is to update the global integer counter, DB_FULL, that records the number of times that calls to StoreData failed to store a record.

   The third application task, CleanupData, has an endless loop that calls the function DeleteData ten times per second. DeleteData has no input argument tbut produces an output argument that is 0 if a record was deleted successfully from the database, and is 1 if no record was deleted. Function DeleteData is to be protected by semaphore DB_IDLE. Outside of this critical section, CleanupData is to update a global integer counter, DB_EMPTY, that records the number of times that calls to DeleteData failed to delete a record.

   Your solution to this problem is to contain the begin() initialization routine, the startup task, and all three application tasks. Should the updates to DB_FULL and DB_EMPTY have been protected in critical sections? Are the priorities assigned to the three tasks important to the correct operation of the system?

   [25 marks]
   

   #define TASK_STACK_SIZE  512
   #define NUM_TASKS  4
   
   #define StartTaskID        19
   #define ProducerTaskID     20
   #define UpdateTaskID       21
   #define CleanupDataTaskID  22
   #define BaseTaskID         StartTaskID
   
   OS_STK    TaskStack[NUM_TASKS][TASK_STACK_SIZE]
   OS_EVENT  *DB_IDLE;
   INT32U    DB_FULL  = 0;
   INT32U    DB_EMPTY = 0;
   
   /* Declare function prototypes for all tasks */
   void StartTask( void *data );
   void ProducerTask( void *data );
   void UpdateTask( void *data );
   void CleanupDataTask( void *data );
   
   begin( void )
   {
       INT8U err;
   
       /* load the trap #0 vector for the context switching routine */
       *((int *)0x80) = (int)OSCtxSw; 
   
       /* Create the start-up task*/
       err = OSTaskCreate( StartTask, (void *)0,
             &TaskStack[StartTaskID-BaseTaskID][Task_Stack_Size - 1],
             StartTaskID );
   
       OSStart();   /* Start multitasking */
   }
   
   void StartTask( void *data )
   {
       INT8U   err;
   
       TickInit();
   
       DB_IDLE = OSSemCreate( 0 );
   
       /* Create the three required application tasks */
       err = OSTaskCreate( ProducerTask, (void *)0,
             &TaskStack[ProducerTaskID-BaseTaskID][Task_Stack_Size-1],
             ProducerTaskID );
   
       err = OSTaskCreate( UpdateTask, (void *)0,
             &TaskStack[UpdateTaskID-BaseTaskID][Task_Stack_Size-1],
             UpdateTaskID );
   
       err = OSTaskCreate( CleanupDataTask, (void *)0,
             &TaskStack[CleanupDataTaskID-BaseTaskID][Task_Stack_Size-1],
             CleanupDataTaskID );
   
       OSTaskDel( OS_PRIO_SELF );
   }
   
   void ProducerTask( void *data )
   {
       DataType  *DataTypePtr;
       INT8U     Err, Err2, *ErrPtr; 
   
       while ( TRUE )
       {
           /* enter critical section protected by DB_IDLE */
           OSSemPend( DB_IDLE, 0, ErrPtr );
           DataTypePtr = GetData();
           Err = StoreData( DataTypePtr );
   	Err2 = OSSemPost( DB_IDLE );
           /* exit critical section protected by DB_IDLE */
   
   	if ( Err != 0 ) DB_FULL++;
       }
   }
   
   void UpdateTask( void *data )
   {
       DataType  *DataTypePtr, *DataTypePtr2;
       INT8U     Err, Err2, *ErrPtr; 
   
       while ( TRUE )
       {
           /* enter critical section protected by DB_IDLE */
           OSSemPend( DB_IDLE, 0, ErrPtr );
           DataTypePtr = RetrieveData();
           UpdateData( DataTypePtr, DataTypePtr2 );
           Err = StoreData( DataTypePtr );
   	Err2 = OSSemPost( DB_IDLE );
           /* exit critical section protected by DB_IDLE */
   
   	if ( Err != 0 ) DB_FULL++;
       }
   }
   
   void CleanupDataTask( void *data )
   {
       INT8U     Err; 
   
       while ( TRUE )
       {
           /* enter critical section protected by DB_IDLE */
           OSSemPend( DB_IDLE, 0, ErrPtr );
           Err = DeleteData();
           OSTimeDlyHMSM( 0, 0, 0, 100 );    /* wait 100 ms */
   	Err2 = OSSemPost( DB_IDLE );
           /* exit critical section protected by DB_IDLE */
   
   	if ( Err != 0 ) DB_EMPTY++;
       }
   }