# Notes

# Overview

── ** RSWiki** ──

# Related Link

**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.*

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, , 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.

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

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.

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:

- Tasks with deadlines are periodic.
- Each execution of task must be completed before the next execution of the same task occurs.
- Tasks are independent.
- Execution times of tasks are constant.
- 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 , every task consists of a sequence of jobs . Task has a constant execution time for assumptions and a temporal distance constraint . The temporal between two jobs of a task is defined to be the difference of the finish times of these two consecutive jobs. The distance constraint requires that the distance between any two consecutive jobs of must be .

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 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 be the task of executing on node . has the distance constraint and execution time . W.l.o.g., . We assume that all transactions have the same sequence of processor, i.e. all transactions have the first task running on node , the second task on node , etc.

Algorithm **DSr** works as follows: We first define . And, let be the density of the task set in node when their distance constraints are transformed with respect to , i.e.,

,

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

In {[crilit_real_time_sync_on_multios_for_multiprocessor:article-dispinwheel]}, they analyzed the complexity is 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 loops. So the time complexity is with n transactions.

**Theorem 1.** *The time complexity for* **DSr** *with n transactions in m nodes is* .

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, , **DSr** is guaranteed to find a feasible schedule for X if , . Moreover, the bound is tight.

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

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

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

- None.

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

- None