CMPE 401 - Computer Interfacing

Assignment #1 Model Solutions

1. In section 1 of the lecture slides we saw that it is possible to use Manchester encoding to encode a clock in the same signal as the data. This method allows us to send a unidirectional synchronous signal over a single wire. Essentially, a logic "0" is encoded as a high signal followed by a low signal, while a logic "1" is encoded as a low signal followed by a high signal. In this way, every bit signal contains one transition, and these transitions can be exploited at the receiver to allow it to "lock into" and thus recover the transmitter clock. The clock recovery process can be accelerated at the start of a transmission by sending a training sequence containing strictly alternating 0s and 1s. Why would this be a good sequence to use for this purpose? What would be the disadvantage of sending a string of 0s or a string of 1s? In practice, how could one lock into the correct timing, and thus be able to recover the encoded bits, if the encoded data contains a reasonably random sequence of 0s and 1s?

   [14 marks]
   The advantage of strictly alternating 0s and 1s is that the only signal transitions present in the signal correspond to the times of the data-encoding transitions. The receiver circuit thus should have an easier time obtaining the correct timing for data recovery purposes later on since there are no other transitions to contend with in the training signal.

   However, a string of only 0s or a string of only 1s could also be used as a training sequence. The number of signal transitions would be twice as great as the number of transitions in a strictly alternating 0s and 1s signal, but this could be handled relatively easily by the receiver circuit. Of course there would have to be a preagreed upon convention concerning whether the signal was only 0s or only 1s. There would thus probably be no real advantage to using a string of 0s or a string of 1s over a string of alternating 0s and 1s as long as the transmitter and receiver had a convention for the training sequence.

   If the signal encodes a reasonably random sequence of 0s and 1s, then a receiver circuit will see two sequences of signal transitions at the expected bit frequency. One sequence will have a transition at every possible bit time: this sequence will encode the data bits. The other sequence will be 180 degrees out of phase with the first sequence: it will not have a transition at every possible bit time, and it will not encode any data bits. It should be straightforward to design a receiver circuit that rapidly distinguishes between the data carrying signal transitions and the other, non-data-carrying signal transitions. A state machine in the receiver could start out choosing one of the two transition sequences (it won't know at this point whether or not it guesssed correctly). Very soon afterwards, the presence of the non-data-carrying sequence would be quickly detected as soon as missing signal transitions are encountered. If the non-data-carring sequence were picked at first, the receiver could then switch to the other sequence which has the data-carrying transitions. The data-carrying sequence will never have any missing signal transitions at the expected bit times.

2. Consult the on-line documentation for the CPU32 (follow the links on the course homepage) and determine how the LPSTOP instruction works. How could this instruction be used to implement a microcomputer system that exists in sleep mode most of the time, conserving power while it is waiting for work to do?

   [14 marks]
   The LPSTOP (low power stop) instruction puts the microprocessor into a state where the clock is shut down for most of the CPU's circuitry to minimize the power consumption for the time period when no instructions need to be executed. As the first step in LPSTOP execution, the current interrupt priority level (IPL) mask bits are saved from the CPU status register. Then the CPU goes into a deep sleep mode, from which it can be awakened only by (a) a hardware reset signal, or (b) the arrival of an interrupt that exceeds the priority of the IPL mask.

   The LPSTOP instruction is thus ideal for implementing a microcomputer system that must conserve power while it is waiting for work to do. An example of such a system is a cell phone, which might not need to execute any instructions on its CPU when the phone is in roaming mode. Before executing the LPSTOP, the CPU must ensure that the IPL bits are set to the appropriate level, one which will allow an interrupt of the correct priority to bring it out of the sleep mode.

3. In your own words, briefly explain the difference between time-sliced multitasking, pre-emptive multitasking, and cooperative multitasking. MicroC/OS-II is a real-time kernel that provides a pre-emptive multitasking environment. How could one implement cooperative multitasking in MicroC/OS-II? How could one implement time-sliced multitasking in MicroC/OS-II? You do not have to provide detailed code in your brief explanations.

   [24 marks]
   A multitasking computing environment is one where the CPU's execution time is shared among one or more different tasks. Only one task can execute at any given time on the one CPU. The kernel must maintain data structures, called "task control blocks", that store the CPU state (e.g. the contents of all CPU registers) for each task that is not currently executing on the CPU. During a context switch, the state of the currently running task is saved in its task control block, and the CPU is loaded with the state stored in the task control block of the next task to be granted use of the CPU.

   In time-sliced multitasking a hardware timer is used to create a series of interrupts. The timer interrupt service routine will usually perform a context switch to load the next ready-to-run task onto the CPU.

   In pre-emptive multitasking a priority is assigned to each task. In the simplest case (e.g. as in MicroC/OS-II) no more than one task can have each priority level. The highest priority task is always allowed to use the CPU; each lower priority task is automatically blocked until it becomes the highest priority ready-to-run task. If there two or more such high-priority tasks, then another method can be used to share the CPU among those tasks.

   In cooperative multitasking the tasks must fairly share the CPU by voluntarily giving up the CPU after some period of time. Thus the currently running task is responsible for not holding on to the CPU longer than some fair time interval.

   MicroC/OS-II is a pre-emptive multitasking real-time kernel, but it can be used to effectively simulate cooperative multitasking or time-sliced multitasking. The MicroC/OS-II routines OSTaskSuspend and OSTaskResume are used to get around the prioritized execution normally enforced by the pre-emptive kernel.

   To simulate cooperative multitasking, a chain of tasks must cooperate together. Most of the time, only one of the ready-to-run task is not suspended; the others are all suspended due to a previous call to OSTaskSuspend. Assume, for a moment, that the currently running task is not the highest priority ready-to-run task. All higher priority ready-to-run tasks are prevented from executing because they are suspended. When the currently running task has finished executing for a fair amount of time, it unsuspends the otherwise ready-to-run, next lowest priority task by calling OSTaskResume. It then gives up the CPU to the next lowest priority ready-to-run task by calling OSTaskSuspend on itself. This action repeats itself, going lower and lower in priority, until the lowest priority task starts executing on the CPU. When the lowest priority task has finished executing for a fair amount of time, it simply unsuspends the highest priority task that was otherwise ready-to-run. At that point, the highest priority task starts executing on the CPU. This task could choose to suspend the lowest priority task, but this step is really not necessary. When the currently running task has finished executing for a fair amount of time, it unsuspends the otherwise ready-to-run, next lowest priority task by calling OSTaskResume. It then gives up the CPU to the next lowest priority ready-to-run task by calling OSTaskSuspend on itself.

   To simulate time-sliced multitasking, the timer interrupt service routine (ISR) can be used to selectively unsuspend only one task at a time. The task priorities are in this way over-ruled. When the ISR starts running, it suspends the currently running ready-to-run task and then unsuspends the next ready-to-run task. The ISR must maintain an ordered table of ready-to-run tasks, and it must have an indicator or pointer to keep track of the currently running task.

4. In your own words briefly explain the difference between a kernel and an operating system. When can one properly call a kernel a "real-time" kernel?

   [14 marks]
   A kernel provides the most basic services in an operating system, such as those the allow tasks to be created and executed on the CPU in a fair and predictable manner. For example, a pre-emptive kernel allows tasks to be created and associated with execution priorities. The highest priority task is given the CPU ahead of lower-priority tasks. A kernel may also provide basic synchronization primitives, such as semaphores, to allow different tasks to interact in a controlled way.

   An operating system typically adds many useful features onto the kernel. For example, an operating system will typically provide a file system, high-level access to input/output devices, access to a network interface, etc.

   A kernel can be called a real-time kernel if it provides fast and predictable response times to externally-generated events. Speed and predictable response time (also called "determinism") are ensured by various design practices. The kernel data structures should be updateable in a time that is independent of the number of ready-to-run tasks. Interrupts should be rarely locked out, and if they are locked out, they should be locked out for only very brief periods of time. Task priorities also make it easier to ensure speed and predictable response times.

5. A typical human reaction time is about 150 milliseconds. The CPU32 inside the MC68332 microcontroller requires 4 clock cycles to execute the BF instruction (Branch conditional with false condition). Assuming that the clock frequency is 16.78 MHz, what is the number of BF instructions that will be executed within one human reaction time? If one could print out the same number of BF instructions on a single roll of paper, at a line spacing of 4 mm per line of text, for how much distance would the printed text continue along the paper?

   [4 marks]
   Number of BF instructions = 0.150 x 16780000 / 4 = 629250

   Text length = 629250 x 0.004 = 2.517 km

6. MicroC/OS-II is a relatively portable real-time kernel in large part because it is written in ANSI C, which is one of the most widely supported programming languages today. In what ways does the software architecture, and not just the implementation language, of MicroC/OS-II promote portability across different microprocessors?

   [15 marks]
   The software architecture of MicroC/OS-II enhances portability by being partitioned into a processor-specific "port", a processor-independent "core", and an application-specific "configuration". The application software, in most cases, will have minimal interaction with the hardware associated with MicroC/OS-II. Instead, the application software calls processor-independent functions provided by MicroC/OS-II. Most of the software in MicroC/OS-II is in the processor-independent core, and none of this code would need to be changed to adapt to a new processor. The processor-specific port gathers together, in one place, the software that would need to be modified to adapt MicroC/OS-II to a new processor. This software is also limited in size, with only four assembly language routines in OS_CPU_A.s and only ten initialization functions in OS_CPU_C.c. Creating a port for a new processor should therefore be simplified.

7. Which of the 14 addressing modes in the 68000 architecture cannot be used to specify destination operands? For each of these unavailable addressing modes, briefly explain why this restriction is either required or is probably a good idea.

   [15 marks]
   The immediate data and quick immediate data addressing modes are used to specify constant values, and so they cannot be used to give destination operands. It doesn't make sense to send the result of an operation to a constant value.

   The program counter relative with displacement and the program counter relative with displacement and offset addressing modes could, in principle, be used to specify destination operands in an instruction set. But Motorola (now called Freescale Semiconductor) decided that it would be unsafe to allow these two addressing modes for destination operands since they would make it too easy for programmers to introduce "self-modifying" code into their software. Self-modifying code is widely regarded as being difficult to design and debug, and thus is best avoided. In addition, allowing self-modifying code would greatly increase the problem of maintaining security in a microcomputer. For these reasons, the two program relative addressing modes cannot be used in 68000-family processors to specify destination operands.

   The implied register addressing mode can be used to specify both source and destination operands, but the permitted addressing modes depends very much on the instruction type. Certainly, for some instructions, the implied addressing mode is used for destination operands (e.g. JSR and BSR).