Multi-Tier OSes


Build up multi-tier oses.


  With more rigid system requirements, it is common that a heterogeneous operating system (OS) only fulfills part of the system requirements. However, due to different OS architectures and tremendous developing cost, it is very difficult to integrate all needed features to one operating system. Therefore, the hardware-software co-design of configurable heterogeneous multi-core systems with real-time multi-tier operating systems becomes one of the most advanced designs to achieve this objective. Scheduling on the multiprocessor is a popular issue in recent years, but a real-time scheduling of synchronization between multi-core does not work fine. In this paper, the architecture of multi-tier OSes is presented and an end-to-end scheduling model based on the pinwheel scheduling algorithms for distributed system is studied. We discuss how tasks might run on the multi-tier OSes for multi-core by pinwheel algorithms to achieve a better real-time communication. After pinwheel algorithm is applied, we provide some metrics for measuring and adjusting communicated rate. We also present a distributed algorithm for integer distance constraint, and study the minimized total delay and minimized maximized delay by using the algorithms for adjusting the phases between schedules on neighboring processors. Using the distributed pinwheel approach, schedules on different OSes for different processors is closly synchronized and more predictable.

Group Member


  In this project, an end-to-end scheduling approach DSr based on the pinwheel scheduling algorithms is studied for distributed real-time systems. The DSr algorithm process all nodes (processors) at the same time, and it produces harmonic distance constraints for real numbers in polynomial time. To obtain a better real-time synchronization, a controlled task (transaction) is joined, we extend the pinwheel algorithm (DSr) to the multi-core systems and apply it to achieve communication in the multi-tier operating system without affecting the architecture of each OS. Since it is common that CPU scheduling with a smallest schedulable integer time unit (tick), i.e. one tick per 10 ms in 100 Hz. Therefore, we also extend a general pinwheel scheduling, Graph, and DSr to the distributed pinwheel algorithm (DSx) with integer distance constraints for the multi-tier OSes. Finally, some metrics for measuring and adjusting communicated rate between OSes are presented, i.e. lower down the rate of communication. We believe that the multi-tier OSes design enables higher portability, achieves higher performance by the support of real-time process and thread scheduling, so as to provide reliable operating environment for all kinds of applications.

1 Framework

  We want build a loader file as follow, which contained second stage loader and two OSes (such as uC/OS-II, uClinux, …, etc).

Pinwheel Scheduling on Multi-core

  Real-time applications running on multi-tier OSes for multiprocessor often have timing constraints on tasks running. In order to meet these timing constraints, we need to have algorithms on mult-tier OSes to schedule and to coordinate tasks on different OSes for different processors. In this section, an multiprocessor scheduling algorithm based on pinwheel scheduling model is presented {[crilit_real_time_sync_on_multios_for_multiprocessor:phdthesis-pinwheel]}. We present how tasks on multi-tier OSes for different processors might be transformed to a set of periods of harmonic numbers. For these harmonic periods, the start and finish times of each task are same relative to its read time in each period. Then, we discuss the phase alignment algorithms which adjust the phases between schedules of neighboring processors so that the overall delay is minimized. Using the pinwheel approach, schedules on different processors are better synchronized and the end-to-end delays are more predictable.

1 Distance-Constrained Model

  In order to simplify the analytical results, we have some assumptions as {[crilit_real_time_sync_on_multios_for_multiprocessor:article-rm_and_edf]} as follow:

  1. Tasks with deadlines are periodic.
  2. Each execution of task must be completed before the next execution of the same task occurs.
  3. Tasks are independent.
  4. Execution times of tasks are constant.
  5. Any aperiodic tasks are special.

  In some real-time applications, tasks must be executed in a distance-constrained environment, rather than periodically. That is, the temporal distance {[crilit_real_time_sync_on_multios_for_multiprocessor:article-schedontempdc]} between any two consecutive executions of a task stream is always less than a well-defined time interval. Such a real-time system is called a Distance-constrained Task System (DCTS) {[crilit_real_time_sync_on_multios_for_multiprocessor:article-dc]}. For example, video systems need to ensure the interarrival time between video frames to always be less than 33 ms. This is different from receiving at least one frame in every 33 ms interval, which allows for an interarrival time that might be greater than 33 ms.
  In a distance-constrained (DC) tasks set Graph, every task Graph consists of a sequence of jobs Graph. Task Graph has a constant execution time Graph for assumptions and a temporal distance constraint Graph. The temporal Graph between two jobs of a task is defined to be the difference of the finish times of these two consecutive jobs. The distance constraint Graph requires that the distance between any two consecutive jobs of Graph must be Graph.

2 Distributed Pinwheel Scheduling Algorithm

  In this section, we present a distributed pinwheel scheduling algorithm {[crilit_real_time_sync_on_multios_for_multiprocessor:article-dispinwheel, crilit_real_time_sync_on_multios_for_multiprocessor:proceeding-dispinwheel]}, which allows tasks are scheduled on multi-tier OSes for multiprocessor. Let Graph be a set of transactions in an end-to-end system. Suppose the number of transactions is n, and the number of processor nodes is m. Let Graph be the task of Graph executing on node Graph. Graph has the distance constraint Graph and execution time Graph. W.l.o.g., Graph. We assume that all transactions have the same sequence of processor, i.e. all transactions have the first task running on node Graph, the second task on node Graph, etc.
  Algorithm DSr works as follows: We first define Graph. And, let Graph be the density of the task set in node Graph when their distance constraints are transformed with respect to Graph, i.e.,

where Graph. And, let Graph. DSr works on every node Graph to compute Graph using every Graph in Graph. Any Graph which causes any of the nodes to have a total density greater than 1 will be removed form consideration. DSr selects the Graph with minimum value of Graph. This Graph is selected as Graph to convert the distances of all transactions.

  In {[crilit_real_time_sync_on_multios_for_multiprocessor:article-dispinwheel]}, they analyzed the complexity is Graph in DSr for theorem 1. We can easy to see the line 5 in algorithm DSr, it involves a summation of numbers and it is nested in Graph loops. So the time complexity is Graph with n transactions.
  Theorem 1. The time complexity for DSr with n transactions in m nodes is Graph.

  The schedulability bound for DSr is also shown in {[crilit_real_time_sync_on_multios_for_multiprocessor:article-dispinwheel]} as follows:
  Theorem 2. Given a distance constraint transaction set X with n transactions executing on m nodes, Graph, DSr is guaranteed to find a feasible schedule for X if Graph, Graph. Moreover, the bound Graph is tight.

  They also improved the time complexity of DSr algorithm to Graph. By a technique as used in {[crilit_real_time_sync_on_multios_for_multiprocessor:proceeding-scheddctasks]}, it first sorts Graph into Graph with duplicates removed and computes Graph, then uses Graph to derive Graph, etc.


  The mult-tier oses could be communicated through L2 memory (on ADSP-BF561), here is the layout of share memory.

Experimental Result

  • Porting two uC/OS-IIs on ADSP-BF561 platform.


  • None.

Future Work

  • Implementation of Synchronization API.
  • Mechanism of communication.
    • Distributed pinwheel scheduler.


  • None



projects/dualos/multi-os.txt · 上一次變更: 2008/03/28 00:04 由 crilit
CC Attribution-Noncommercial-Share Alike 3.0 Unported Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0