Shalin Dalal

Vivek Rao

Sameer Rajyaguru

Feasibility Analysis

Contents

1. Issues and the solutions
1. Definition of the controlled variable and the way to measure it
2. The Definition of the Manipulated variable and the way to change it.
3. Specification of the flexibility in scheduling by the application.
4. Validation of the scheduling algorithm.
2. Approach to implementation.
1. Study of RED-Linux to determine data structures to modify and hooks to be established.
2. Components that have to be implemented
3. Order of implementation.
3. Milestones.

1.Issues and Solutions

A. Definition of the controlled variable and the way to measure.

The controlled variable in our case is the miss ratio. The miss ration is measured in terms of the percen

Title

We plan to implement the Feedback Control, Earliest Deadline First Scheduling algorithm, in RED- Linux

Description

Static scheduling requires a complete knowledge of the task set and the constraints, dynamic scheduling on the other hand can work with incomplete knowledge however these scheduling algorithms are all open ended, i.e. they do not take into consideration the performance of the schedule. These scheduling algorithms thus work well when the tysk set can be accurately modeled, however in real world situations this is not always possible and its more the case that the task set cannot be modeled correctly or there are transient changes that are not designed for. This leads to the idea of using feedback to dynamically adjust the scheduling algorithm parameters. The leads to the generic idea of feedback scheduling and the specific idea of FC-EDF.

The following is the diagrammatic description of the FC-EDF architecture.

We plan to implement the FC-EDF scheduler in RED –Linux . RED –Linux is a real time variant of Linux , it supports a real time scheduler that is separated into an user level allocator and a kernel dispatcher. It supports the following parameters for the tasks
1. priority

2. Start Time

3. Finish Time

4. Budget

The following is the structure of the RED- linux scheduler.

Solution :

The following are the considerations that we are going to make.

we will implement the admission control and the EDF priority assignment in the allocator. The PID controller , the service level controller will be implemented in the dispatcher. The following are the mappings from the paper to the problem at hand and to RED-Linux

1. What is miss ratio? - It is the number of tasks that missed its deadline in a period of time
2. How to Measure the Miss Ratio? Answer provided above - Missed deadlines within a period
3. How does task specify the levels of service? - By the deadline range , this will require us to change the data structures that are used to communicate between the allocator and the dispatcher.
4. How does the service level control change the service level? By Changing Deadline. What does this mean? This leads to a change in the utilization.
5. When to change the deadline? Change in feedback will cause this.
6. How much to change the deadline? By the returned value from the feedback., the feedback is in units of utilization.
7. Do we consider continuous values between the submitted discrete deadlines? Yes since the task submits a range of deadlines not specific values.
8. Whose service level to change? This is an open question still The options are
1. All tasks
2. Some select task

Only those that submit a range of deadlines

Start with the highest priority task i.e the highest priority according to EDF and try and accommodate the entire change in this task and then if more change is left then pick the next highest priority task.

9. When to measure the feedback(miss ratio)?
1. Periodically

( Practically decide a value.)

10. How does the admission controller work?

If task utilization > available increase in utilization then reject

11. How does the EDF scheduler fit into the picture? picks tasks from the ready queue, How does it schedule the tasks?( Based on EDF)