Assignment 4 — ECEN 449/749 

Assignment 4 — ECEN 449/749 

Overview
In this assignment, you need to write several C programs to emulate real-time scheduling policies for
systems with periodic tasks. For each programming problem, your program should read input from the
file “input.txt.” The input file contains multiple lines, each line has two integer numbers. The first number
is the period of the task, and the second number is the execution time. For example, the sample input
below describes a system with two tasks. Task 1 has period 2 and execution time 1, and task 2 has period
3 and execution time 1. Assume that all tasks release their first jobs when the system starts, and all tasks
are preemptable.
Sample Input
2 1
3 1
Your program needs to emulate the system for one hyperperiod and check whether all deadlines are
met. If some deadlines are missed, your program only outputs a single line: “Fail”, like the following:
Sample Output 1
Fail
If all deadlines are met, your program first outputs a line: “Succeed”. In the next line, your program
outputs the duration of a hyperperiod, denoted by H. In the third line, your program outputs H integers
to describe the scheduling decision in each of the H time units. If the i-th integer is k, then that means
your program schedules a job for task k at time i. If the i-th integer is 0, then that means your program
idles at time i.
For example, if your program emulates EDF, then the output for the sample input above would be
Sample Output 2
Succeed
6
1 2 1 2 1 0
1. (25pt)
Write a C program to emulate EDF.
2. (25pt)
Write a C program to emulate RM.
3. (25pt)
Construct an example where the total utilization of the system is larger than URM(n), but RM produces
a feasible schedule. Explain your answer. Your system needs to contain at least four tasks, that is, n ≥ 4.
4. (25pt)
A system contains four periodic tasks: (8,1), (15,3), (20,4), and (22,6). Construct the EDF schedule and
the RM schedule in the time interval [0, 50]. Compare your answer to the outputs of your C programs.
5. (749 only, 25pt)
Write a C program to emulate LST.
2