Reference no: EM132713074

Assignment Goals

The purpose of this assignment is to give you an opportunity to practice the theories about response time analysis. The assignment will be focusing on the Rate Monotonic (RM) and Fixed Priority Schedulability (FPS) analyses. It will also cover how to take into account factors like blocking and jitter in the analysis.

ASSIGNMENT

You find the detailed assignment description in assignment.pdf . Use a PDF viewer to read and print it. Please download FpsCalc user manual and the example code below to learn how to use the tool. Unix/Linux distribution: fpscalc_linux.tar.gz
FpsCalc User Manual : fpscalc.pdf
Example file : one_system_example.fps
For Linux machine, download the fpscalc_linux package and extract it in a folder.
Place your formula file (.fps) in the extracted folder fpscalc_linux and then you can execute FpsCalc by typing following command in shell:
./fpscalc < your_program_name.fps

Response Time Analysis using FpsCalc

Assignment 1
1.1 What is the priority ordering for the tasks using the RM priority ordering?
1.2 Will all tasks complete before their deadlines according to the schedulability formula in Equation 2 on page 3? Draw a critical instant schedule for the given tasks (as in Figure 2, but have all tasks simultaneously released at time 0). What is the system utilization bound?
1.3 Assume that we keep all the parameters in Figure 3 and only increase the computation time for task τ1 to be C1 = 5. Will all task complete before their deadlines? Draw a critical instant schedule for the given tasks. What is the system utilization bound?
1.4 Assume that we instead of modifying τ1 in Figure 3, (set C1 = 2), want to increase the computation time for task τ3 to be C3 = 17. Will all task complete before their deadlines? Draw a critical instant schedule for the given tasks. What is the system utilization bound?
1.5 What conclusion can you draw from all this for the schedulability formula in Equation 2 on page 3? Specify your conclusion in terms of the system utilization bound, the n(21/n - 1) expression and 1.00.
1.6 Now, assume that we change the relative deadline for task τ3 in Figure 3 to be D3 = 15. Draw a demand bound function (check lecture slide scheduling theory part2.pdf) of the changed task set and explain if it's feasible on a single preemptive processor.

Assignment 2

2.1 Given the task set in Figure 4 what is the priority ordering for the tasks using the DM priority ordering? What is the priority ordering using RM priority ordering? Use FpsCalc to calculate the response time for the tasks in both ordering. Will all tasks complete before their deadlines? If you are not convinced by the formulas you can do a critical instant schedule.
2.2 Sometimes it is preferable to not use strict RM or DM priority assignment when giving priorities to tasks. This can for example happen when we want to give a task with low deadline demands a better service rate or when the system is part of a larger distributed system. Find two different priority assignments of the tasks in Figure 4 which is neither RM or DM and where deadlines are missed and met respectively.
2.3 Assume that we want to implement the tasks given in Figure 4 on a RT-kernel that only supports

3 priority levels and where tasks with the same priority will be handled in FIFO order by the scheduler. Assume that task τ2 and τ3 are set to have the same priority and that we use a DM priority assignment.

Define how the response time formula in Equation 3 on page 4 will be changed when we allow several tasks to have the same priority. Make sure that it is shown in your formula that a task, due to the FIFO order, might have to wait for one instance, but can't be preempted, of an equal priority task. How will the corresponding FpsCalc formula look like, (observe that sigma(ep, ...) includes the current task, τi)?

What will now the worst case response time for each task be? Will all tasks meet their deadlines? Will the worst case response time for task τ1 or τ4 be affected? Conclusions?

Assignment 3
3.1 Assume that we have the tasks shown in Figure 6 on the next page. Give priorities to the tasks according to the DM priority assignment. Will all tasks always meet their deadlines?

3.2 Assume that task τ2 and τ4 in Figure 6 are sharing a semaphore S1 and that τ2 and τ4 executes for at most 1 ms and 2 ms respectively in the critical section. Show, by doing a critical instant scheme that the deadline for task τ2 can be missed if semaphores and no mechanism for limiting priority inversion (see below) is used. Tip: You might have to model that τ4 has taken the semaphore, just before the moment where you let all the other tasks start executing at the same time.

The phenomena that a higher priority task not only can be blocked by tasks accessing the same resource but also be delayed by tasks with priorities between the blocking task and the higher priority task is called priority inversion.

One protocol that handles the priority inversion is the priority inheritance protocol. It works by letting a low priority task that has a semaphore inherit the priority of the highest priority task blocked waiting for the semaphore. When the lower priority task releases the semaphore it will go back to the priority it had before. Notice that the priority of a task now is dynamic so the name 'Fixed Priority' is not really true anymore

Assignment 4

4.1 Another source of jitter is varying execution and response times for tasks (or messages) that start other tasks. To illustrate this assume a system with two tasks τ1 and τ2. Let task τ1 have a period T1 = 10 and a fixed (non-varying) execution time C1 = 3. Let task τ2 arrives always 2 time units after τ1 arrives, but it waits for τ1 finishing before it gets released (we can see it as that τ2 waits for the result of τ1 before it can execute). Assume task τ1 always ends its execution by releasing task τ2 (τ2 can now be scheduled for execution). Let τ2 have a worst case execution time of C2 = 2.

Draw a schedule that shows two instances of τ1 and τ2 respectively. What is the period T2 of task τ2?

4.2 To illustrate that varying execution time of τ1 might cause jitter of τ2 assume that τ1's execution time no longer is fixed but varies between C1min = 3 and C1max = 5. Task τ1 still starts task τ2 at the end of its execution. Draw a schedule with two instances of τ1 that shows that the varying execution time of τ1 might give raise to jitter of τ2. What is the jitter that task τ2 can experience?

4.3 To illustrate that interference of high priority tasks might give raise to further jitter of low priority tasks we add a task τ0 to the system. Let task τ0 have higher priority than both τ1 and τ2, a period T0 = 20 and a worst case execution time C0 = 2.

Draw a schedule that shows that varying response time of τ1 due to interference of τ0 will give raise to further jitter of τ2. Task τ1's execution time still varies between C1min and C1max. What is the jitter that τ2 can experience due to varying response and execution time of τ1? After the above example of how jitter can be derived we will now investigate how jitter of different tasks might interact to cause larger response times of lower priority tasks.

4.4 For the given tasks τA and τB in Figure 10 with DM priority ordering, what is the worst case response time for respective task assuming that we have no jitter. Will both tasks be able to complete before their deadlines?

4.5 Given the formula in Equation 5 what is the worst case response time for respective tasks assuming that they can experience jitter? Will both tasks be able to complete before their deadlines? We can construct a task schedule giving the same worst case response time for tasks as the formula in Equation 5.

4.6 Draw a task schedule for the tasks τA and τB in Figure 10 which gives the same worst case response times as the formula in Equation 5. Indicate arrival, jitter, beginning of execution, execution, preemption, and completion for each task in your schedule.

Attachment:- CSE_1assignment.rar