This paper describes an embedded workflow framework (EMWF) that enables flexible personal and home automation and assistive devices and service and social robots (collectively referred to as SISARL) to be built on workflow architecture The process definition language supported by EMWF is called SISARL-XPDL. It consists of a subset of the WfMC standard XML Process Definition Language (XPDL) 2.0, together with elements that implement common mechanisms for robot behavior coordination. SISARL-XPDL definitions of workflows are first translated into standard XPDL and execution directives and then are parsed either directly into binary workflow scripts for execution or into intermediate scripts in C. EMWF provides workflow engines for Linux and Windows CE platforms. The engines are written in C in order to keep their memory footprint and runtime overhead small. Performance data show that the overheads introduced by the engine and workflow data are tolerable for most SISARL devices.

Researchers in the real-time system community have designed and studied many advanced scheduling algorithms. However, most of these algorithms have not been implemented since it is very difficult to support new scheduling algorithms on most operating systems. To address this problem, we enhance the scheduling mechanism in Linux to provide a flexible scheduling framework. In the real-time and embedded Linux (RED-Linux) project, we implement a general scheduling framework which divides the system scheduler into two components: dispatcher and allocator. The dispatcher provides the mechanism of system scheduling and resides in the kernel space. The allocator is used to define the scheduling policy and implemented as a user space function. This framework allows users to implement application-specific schedulers in the user space which is easy to program and to debug. The framework also relieves the deficiency from the stock Linux scheduler which is not designed for real-time applications. To further enhance its power, a hierarchical scheduling mechanism has been provided in RED-Linux to allow a system designer to integrate different real-time applications together. Using scheduling groups, real-time jobs can be managed and scheduled in a hierarchical manner. In this paper, we discuss how the group mechanism is implemented in RED-Linux.

A hierarchical scheduling mechanism has been implemented in RED-Linux to integrate different scheduling paradigms together. We extend the concept of group so that the execution budget for jobs in RED-Linux can be managed in a hierarchical way. A budget group contains a set of jobs that share the available budget for the group. The jobs in a budget group could be a normal job or another budget group job, which contains its own group of jobs. Every job has its system budget. But if it belongs to a budget group, the job's budget is also constrained by its group's budget. We discuss how the budget group mechanism is implemented in RED-Linux. We also show how to use the mechanism to implement several schedulers.

Hierarchical schedulers are useful to integrate different scheduling paradigms together. The original RED-Linux general scheduling framework does not support hierarchical schedulers efficiently because the dispatcher cannot tell whether a job is an aperiodic job or a real-time job. In the work reported in this paper, we add an extra parameter, the group number, to the RED-Linux scheduling framework in order to identify the type of jobs. This mechanism does not introduce any overhead to normal real-time tasks and only a constant overhead per job for hierarchical jobs. We discuss how to implement hierarchical schedulers and how to use this extension to support sporadic schedulers. We also discuss various versions of the sporadic server algorithm.

Most computer-based systems have hard real-time constraints. Schedulers in complex systems must be designed to manage a set of applications developed and deployed independently. We study an open real-time environment architecture for distributed systems where real-time applications may run concurrently with non-real-time applications. The architecture uses a two-level scheduling scheme. Each application is assigned a sporadic server to schedule the processes in the application. All sporadic servers are then scheduled by a system-wide fixed priority scheduler. Using the proposed open environment architecture, all hard real-time applications are guaranteed to have their reserved CPU utilization in order to meet all their deadlines. The guarantee is independent of the behaviors of all other applications in the same system. We present the schedulability analysis methods on systems with or without shared memory.

Many scheduling paradigms have been studied for real-time applications and real-time communication network. Among them, the most commonly used paradigms include priority-driven, time-driven and share-driven paradigms. In this paper, we present a general scheduling framework which is designed to integrate these paradigms in one framework. The framework is implemented in our real-time extension of the Linux kernel, RED-Linux. Two scheduler components are used in the framework: Allocator and Dispatcher. For each job, the framework identifies four scheduling attributes: priority, start time, finish time and budget. We show that the framework can be used to efficiently implement many well-known scheduling algorithms. We also measure and analyze the performance of the framework implemented in RED-Linux.