EMBSYS 110:
Design and Optimization of Embedded and Real-time Systems

Course Introduction

The major focus of this course is the study of embedded applications with the goal of optimizing parameters such as robustness, cost, speed, size, and features against real world constraints. Building on the introductory Fundamentals of Embedded and Real-Time Systems course and the intermediate Programming of Embedded Systems course, this hands-on class reinforces and extend students' ability to design and develop real-time embedded applications. Our approach emphasizes developing and deploying multitasking systems of medium complexity.

Students do not need to pursue the Embedded Systems certificate in order to take this course.

Topics covered in the course include

• operating system concepts, such as scheduling and schedulers;
• developing, integrating, and debugging multiple task applications;
• process synchronization, including critical sections, semaphores, monitors, and deadlocks;
• sharing and exchanging data between processes in a safe and robust way;
• developing simple device drivers;
• system performance and optimization;
• reliability and fault tolerance; and
• developing sound software engineering methodologies such as the specification process, developing robust code, and the test process.

The course begins with a discussion of the system development process and hardware-software interaction; it then progresses to the task of translating a set of customer requirements into a working (embedded) system prototype. Critical to such development is analyzing the design to ensure efficiency, optimized performance, robustness, and recovery from errors and exceptions. The lessons build upon the material introduced and studied in the earlier courses through the design and implementation of more complex multitasking applications. The latter half of the course includes a significant development project. The development project is designed to be a scaled down simulation of a real-world project. It includes a student written specification, design description, and test plan, and then concludes with the implementation and testing.

Learning Objectives

By the end of the class, you must be able to specify, design, implement, document, and test the software portion of an embedded systems application written in the C programming language that must run on the Motorola MCF5206e Coldfire processor.

Specification must include:

1. a formal Requirements Specification based upon loosely stated customer's requirements for an embedded product; and
2. a formal Design Specification that expresses and quantifies the requirements, in detail, captured in the requirements specification.

Design must include:

1. a hierarchical functional design capturing the external behavior of the application. Such a design must include a minimum of three levels of refinement; and
2. an architectural design, mapping the functions to hardware and software modules.

Implementation and documentation must:

1. Include a completely working software program written in the C programming language and in MCF5206e assembler.
2. The application must include a minimum of four tasks of differing priorities. The tasks must execute, without conflict, under the Micro C/OS II operating system. The application must include a minimum of four interrupts and the interrupt service routines must be written in MCF5206e assembler.
3. The program must execute on the Motorola MCF5206e microprocessor.
4. The software must be fully annotated. Such annotation must include header blocks for each function and structural data type describing all inputs and outputs as well as the functional behavior of each. All code must be fully annotated to describe the intent and operation of each major segment or the design.

Test must include:

1. a formal Test Plan, based upon the original Requirements Specification, identifying what must be tested in the final product;
2. a formal Test Specification identifying how each requirement in the Test Plan and Requirements Specification is tested to ensure compliance with the original specification;
3. a formal set of test cases ensuring that each item in the Test Specification is tested; and
4. an annotated set of results from executing the test cases identifying what was tested, the results, and how these compared with the expected results.

Prerequisites

It is expected that the student has passed Fundamentals of Embedded and Real-Time Systems and Programming of Embedded Systems (the first two courses in the certificate program) or their equivalents.

About the Online Environment

Your online course offers several advantages to the traditional classroom, including the comprehensive Online Student Handbook, the ability to communicate electronically with students and with your instructor, and links to a rich array of online resources.

Online Student Handbook

This handbook answers questions about your online learning course, such as how to purchase your text, schedule an exam, obtain a transcript, and get technical help if you need it. The handbook also provides additional resources, such as how to order books or journals from the library and how to study for an online course.

Communication with Your Instructor and Student Peers

• Online Discussion Forums, designed by the University of Washington award winning Catalyst team, allow you to communicate with other currently enrolled students and with your instructor. We encourage you to use the discussion forum to exchange ideas, resources, and comments about your course work with other students in this course. This unstructured forum is monitored by your instructor.
• You can use e-mail to ask me a question or preferably post your question on the discussion forum. I will reply to all discussion forum questions on the forum, and to e-mail questions via e-mail.

Online Resources

As an online student, you have access to a wealth of Web resources compiled to provide fast, easy access to information that supports your online learning experience. Organized by subjects, Online Resources link you to sites with help for writing and research, study skills, language learning, and library reference materials. All links have been assessed for credibility and reliability, and they are regularly monitored to ensure their usability.

Required Text

Text: Real-Time Programming, A Guide to 32-Bit Embedded Development, Grehan, Rick, et al. Addison Wesley, 1998. ISBN: 0-201-48540-0 (Real-Time)

The course incorporates material from the required text as well as material from the recommended books, which are listed below. Recommended readings from these books are specified at the beginning of each lesson. The recommended texts are also considered excellent desk references.

Recommended Readings

Embedded and Real-Time Systems

Embedded System Design. Berger, Arnold, CMP Books, 2001

Real-Time Software Systems, Cooling, J.E., PWS Publishing Company, 1997

Embedded Real-Time Systems, Calvez, Jean Paul, John Wiley & Sons, 1993.

An Embedded Software Primer, Simon, David E., Addison Wesley, 1999.

Real-Time Systems, Liu, Jane W.S., Prentice Hall, 2000.

An Introduction to Real-Time Systems From Design to Networking with C/C++, Buhr, Raymond J.A., Bailey, Donald L., Prentice Hall, 1999.

Real-Time Systems, Krishna, C.M. and Shin, Kang G., McGraw Hill, 1997.

Real-Time Systems Design and Analysis An Engineer's Handbook, 2^nd ed., Laplante, Phillip A., IEEE Press, 1997.

Doing Hard Time Developing Real-Time Systems with UML, Objects, Frameworks, and Patterns, Douglass, Bruce Powel, Addison Wesley, 1999.

Distributed Systems

Distributed Systems Concepts and Design 3^rd ed., Coulouris, George, Dollimore, Jean, Kindberg, Tim, Addison Wesley, 2001.

Distributed Operating Systems Concepts and Practices, Galli, Doreen L., Prentice Hall, 2000.

Fundamentals of Multithreaded, Parallel, and Distributed Programming, Andrews, Gregory R., Addison Wesley, 2000.

Distributed Systems, 2^nd ed., Mullender, Sape, Addison Wesley, 1994.

Technology Requirements and Skills

In addition to the technology requirements and skills noted in the Online Student Handbook, for this course you will need

• access to a computer supporting the C language;
• the UW development kit (purchase from UW Extension);
• ability to FTP files for communicating with and getting help from the instructor.

Course Organization

The course is divided into nine lessons. Relevant reading from the text and references are identified at the beginning of each lesson. Each lesson includes an overview, learning objectives, required reading assignment, and commentary. The commentary includes programming examples. Each lesson includes a short self-graded test so that you can review and reinforce what you have learned. In addition, each lesson is accompanied by a homework assignment.

Lesson One: System Design and Development—Part 1

• Objectives
• The Design Process, Systems, and Models
• System Design and Development
• Problem Solving
• Specifications vs. Requirements
• Hardware and Software Specifications
• Prototyping
• Functional Model versus Architectural Model
• Partitioning a System
• Other Considerations
• Requirements and Traceability
• Analyzing the System Design
• Static Analysis
• Dynamic Analysis
• Summary
• Self-Study Exercise

Lesson Two: System Design and Development—Part 2

• Objectives
• Testing
• The Importance of Testing
• Safety and Reliability
• Steps to a Safe Design
• Safety
• Summary
• Self-Study Exercise

Lesson Three: Threads In Depth—Part 1

• Objectives
• Process and Threads
• Time-Based and Reactive Systems
• Scheduling Algorithms
• Scheduling Threads
• Real-Time Scheduling Considerations
• Algorithm Evaluation
• Queuing Models
• Summary
• Self-Study Exercise
• Appendix: What Really Happened on Mars Rover Pathfinder

Lesson Four: Threads In Depth—Part 2

• Objectives
• Tasks, Threads, and Communication
• Messages
• Thread Synchronization
• Monitors
• Deadlocks and Starvation
• Summary
• Self-Study Exercise

Lesson Five: Deadlocks and Memory Management—Part 1

• Objectives
• Deadlocks
• System Model
• Deadlock Characterization
• Deadlock Detection
• Task Termination
• Resource Preemption
• Summary of Deadlocks
• Self-Study Exercise

Lesson Five: Deadlocks and Memory Management—Part 2

• Objectives
• Process Stacks
• Task Control Block
• Stacks
• Dynamic Memory Allocation
• Swapping
• Overlays
• Multiprogramming
• Summary
• Self-Study Exercise

Lesson Six: Looking at Performance in Embedded Systems—Part 1

• Objectives
• Performance Considerations
• Time Loading
• Context
• Analyzing Flow of Control
• Self-Study Exercise

Lesson Six: Looking at Performance in Embedded Systems—Part 2

• Working Outside of the Processor
• Learning Objectives
• Memory Loading
• Memory Map
• Evaluating Performance
• Analytical Modeling
• Performance Optimization
• Approaches to Performance Optimization
• Reducing Response Times and Time-Loading
• Summary
• Self-Study Exercise

Lesson Seven: Interfacing to the Outside World

• Input and Output Subsystems
• Elements of a Bus
• Timing Requirements
• Data Source or Destination
• Where the Procedure Resides
• Summary
• Self-Study Exercise

Lesson Eight: Working Outside of the Processor—Part 1

• Objectives
• Data Source or Destination
• Nature of the Exchange
• Timing of the Exchange
• RS 232—What Could Be Easier?

Lesson Eight: Working Outside of the Processor—Part 2

• Interrupts and Polling
• Interrupts
• How I/O Procedure is Invoked
• Summary
• Self-Study Exercise

Lesson Nine: Working Inside and Outside of the Processor

• Objectives
• Interprocess Communication
• Communication Patterns
• Building Blocks
• Group Communication—Multicast
• Pipes, Streams, and Sockets
• Remote Services
• Summary
• Self-Study Exercise

Asking for Help

If you send e-mail to your instructor asking about a specific programming problem, please include a short program fragment illustrating your problem. If you can distill your problem to a small example, you get a quicker reply from the instructor. Quite often, during the process of distilling the program example down, you are able to determine the cause of the problem on your own. Remember, too, that the cause of a problem often is rooted in code far from where the symptoms occur. So, including only the line where you get the fault may be of little help. For example,

Dear Instructor,

My code doesn't work. Here's the line that fails. Can you fix it?

char myVariable = *myPointer;

Thanks in advance.

Bewildered Student"

probably isn't going to get much of a response. In contrast,

Dear Instructor,

Here's a description of the problem I'm having:

char * myPointer = NULL; // Represents the cause
                         // of the problem
  
  *                      // 1000 lines of code

   *

   *

char myVariable = *myPointer; //   Produces a General 
                              // Protection Fault

Thank you.

Student

puts your problem in a meaningful context and enables your instructor to help you solve it.

Grading

You receive either a satisfactory completion (SC) or an unsatisfactory completion (UC) based on your performance on the homework assignments—including the final project. . To obtain a SC grade, you must earn an 80 percent average in the course.

Each homework assignment counts equally toward your final grade. Assignments 5, 6, 7, and 8 encompass a programming project designed to simulate a real world development project. Your grade is based only on your assignments.: There are no exams in this course.

Assignment	Percent
Assignment 1	10
Assignments 2 and 3	15
Assignments 4 and 5	20
Assignments 6–9	55
Total	100

The instructor provides you with a grade and written feedback on each of your assignments within one week of your submission. In addition, the instructor provides you with a cumulative summary of your progress with each homework assignment.

Evaluating Activities and Exercises

A completed assignment consists of a code listing, printout of the output, and annotated test cases and their results. Assignments are evaluated based upon clarity and consistency of style (30 percent), the correctness of the solution (40 percent), and demonstrated testing of the solution (30 percent)

Criteria for Evaluating Programming Style

Embedded applications involve significant amounts of software. Such software is a major portion of the deliverables for each assignment. Each implementation file should start with a comment block briefly describing what is implemented in this file and the author's name. Each function should start with a block comment describing what the function does. Here is an example of good style in an implementation file:

Code Example 1

/ / filename:  xxxxx.c   

/ / Title:  Assignment 4, Problem 2  - Implementation

/ / By:  Student's Name, ID, and e-mail; e.g.,   

/ / Jane Smith (23456)  jsmith@hotmail.com

/ / Course: Embedded Systems 110

/ / Instructor: Instructor's Name

/ / Date:  xx/xx/xx

/ / Description of what is in the file

/ / Revision History



#include 

#include 



// Globals defined in this file.

structname GlobalInstance;



// Function header - what does this function do? 

// It is OK to refer to documentation in the 

// struct header file here.

void structname::method(args....)

{

  structname& autovariable;

  for (;;) {

   code in a loop....;

  }

}

Each header file should start with a block comment describing what the struct does. Following is an example of good style in a header file. Note the order of the public, protected and private sections in the struct definition.

Code Example 2

// filename.h - Interfaces for Homework 1.
/ / Title: Assignment 4, Problem 2 - Implementation

/ / By: Student's Name, ID, and e-mail; e.g.,  
/ / Jane Smith (23456) jsmith@hotmail.com

/ / Course: Embedded Systems 110

/ / Instructor: Instructor's Name

/ / Date: xx/xx/xx

/ / Description of what is in the file

// Revision History



// Prevent multiple definitions if the 

// file is included more than once.

#if !defined(header_h)

#define header_h



// Struct header - what this struct does, 

// how to use the struct, 

// who this struct collaborates with, etc.

struct structname

{

  // Public interfaces



  // Data and functions.



};



#endif // header_h

How you line up your {}'s is not of concern to the instructor, as long as you are consistent throughout your source code. Also, good indentation to set off code blocks is essential.

Criteria for Evaluating Programming Correctness

Programming correctness is evaluated based on:

• Correctness of the algorithms implemented—does the program correctly implement the homework specification?
• Completeness of the implementation—are all of the required constructors and operators included in the struct implementation?
• Robustness of the implementation—are invalid input parameters considered?
• Memory allocation—is all memory properly managed?

Criteria for Evaluating Testing

Include the test program you wrote to verify correct operation of your program and the results of executing each of the test cases. Testing should include testing at boundary conditions, including invalid arguments to functions. Each struct member function should include test cases that test that function.

Contributing Author and Course Reviewer

Contributing author: Jim Peckol, University of Washington Department of Electrical Engineering

Jim Peckol has more than 25 years experience developing embedded systems, conducting research, and teaching. He founded Oxford Consulting, Ltd., which provides product design and development, project leadership and training services, with a specialty in embedded systems and fuzzy logic.

Course reviewer: Arnold Berger, University of Washington Department of Computing and Software Systems

Arnold Berger is a Senior Lecturer in the Department of Computing and Software Systems at the University of Washington-Bothell. His major area of interest is simulations in real-time and embedded systems. He is the author of the book, Embedded System Design (CMP Books, 2001).

---

©2007, University of Washington. All rights reserved.
No part of this publication may be reproduced in any form or by any means without permission in writing from the publisher.