Real-time operating system services for networked embedded systems.

Abstract

This dissertation examines issues related to the design and implementation of real-time operating system (RTOS) services for consumer item embedded systems such as cars, webTVs, and cellular phones. Since these devices are mass-produced, keeping production costs low is all important, meaning that RTOS services must be highly efficient to enable use of low-cost hardware in these devices. This dissertation explores optimization techniques for basic RTOS services (task scheduling, synchronization, and communication) to meet the requirements of embedded systems. First, dynamic schedulers like earliest-deadline first (EDF) give high processor utilization but incur high run-time overhead while the opposite is true for static schedulers like rate-monotonic (RM). We design the combined static/dynamic (CSD) scheduler which employs both EDF and RM to deliver run-time overhead comparable to RM and utilization comparable to EDF. Second, increasing use of OO programming has made efficient synchronization important for embedded systems. In an OO multitasking environment, accesses to objects have to be protected through semaphores to ensure mutual exclusion. We present a new semaphore implementation scheme which saves one context switch per lock operation in most circumstances by rescheduling threads to minimize blocking. Third, embedded devices with Internet connectivity require efficient processing of network data. We present a protocol architecture for reducing receive overhead for audio and video messages. The architecture reduces I-cache misses by safely bypassing multiple protocol layers (benefiting short audio messages) and real-time message data is copied only once without any hardware support (benefiting long video messages). Finally, embedded systems incoporating local area networks (LANs) require proper LAN message scheduling. Controller Area Network (CAN) is a popular LAN in automotive applications. Pure EDF scheduling is not feasible for CAN because of unacceptable overhead while deadline-monotonic (DM) scheduling is feasible but yields low network utilization. We present the feasible mixed traffic scheduler (MTS) which combines EDF and DM using quantized deadlines to deliver higher utilization than DM. Using these optimizations, we built and evaluated an RTOS that provides a rich set of services to programmers and meets the efficiency/cost requirements of embedded systems.