June 9, 2020

In my final year at West Virginia State University, my senior seminar teacher instructed us to create a program that
demonstrated the benefits of using a dynamic scheduling algorithm over a fixed priority algorithm. He gave us a paper to
read (written back in 1973), then sent us out to write the program with little guidence. I had a hard time understanding
the paper at first; mostly because I had very little experience with real-systems and the paper is incredibly dry. It was
also pretty difficult to find resources on the paper (despite it actually being a defining paper in the field), so I
decided to make __ the
program__ I wrote public, as well as to write this article in order to help anyone in a similar situation.
This post will (hopefully) explain the algorithms as described in

First, I'll go ahead and give a very brief overview of what a real-time system is, as well as go over some important terms used in the paper. A real-time system is a system that works in real-time. Sounds like I'm being sarcastic, but that's it. A good example of a real-time system is the fly-by-wire system in an airplane. The pilot doesn't have any direct control over the mechanical parts of the plane. Instead, he moves the yoke, which tells a computer what parts to move in real-time.

Fly-by-wire is also a good example of a **hard** real-time system. In a hard real-time system, there would be
catastrophic effects to a task being late (the tasks, in this case, being processing input and controlling the mechanical
parts of the plane).

In contrast, a **soft** real-time environment is one where a task set or two can be missed without something bad
happening to the system. Or, as the paper decides to put it: "where a statistical distribution of response times is
acceptable." The algorithms we're discussing exist in a **hard** real-time environment. This is an important distinction
to make because it means **no** task can be missed when considering these algorithms.

Preemptive means that one task can interrupt another if it has a higher priority. All three algorithms in the paper are preemptive. If they were not preemptive, the first task would have to be completed before the algorithm could start on the second. A Gantt diagram just shows how the algorithm works. Time is shown in units at the bottom of the graph, the green sections represent a task being completed during that time unit. Purple lines represnt a task arriving again and red lines represent that a task has arrived without being completed.

A critical instant is when the tasks arrive at the same time. A critical time zone happens at a critical instant. It is the time between when a task arrives and when it is completed. Request periods are how often the task must be completed. For example, if a task has a request period of 30, the task would need to be completed by time unit 30, 60, 90, etc. C represents period length and T represents task length (how long it takes to complete that task).

If you didn't understand something in that section, don't worry about it. I'll go over it with context here in a second. If you still don't understand it after you've finished reading, you can ask down in the comments.

Now that the background is out of the way, we can start talking about how the algorithms schedule tasks. The
fixed priority rate monotonic algorithm schedules task based on their * period length*. If a task needs to
be completed every 41 time units, it has a higher priority than a task that has to be completed every 62. Of course,
the algorithm is also preemptive and can interrupt other tasks. If the task with 41 time units arrives before the 62
is finished, the algorithm stops the 62 until the 41 is finished. Like so:

The first task arrives a second time at the 41^{st} time unit. However, the third task is not yet completed.
Because the first task has a shorter deadline, it has a higher priority and must go first under this algorithm. The
third task is then allowed to continue after the first is finished. Don't worry about the bound and the utilization, yet.
I'll go over those next. Just make sure you understand this, first.

You may be wondering, "Is there a way to tell if this algorithm will work for a task set?" Yes, there is. First,
let's define some variables. T represents a task's length. If a task takes 20 time units to complete, T = 20. Multiple tasks
are differentiated with a subscript. For example, T_{1} may be equal to 20, T_{2} = 10, etc., etc., up to
T_{i} (i being the number of tasks).

The other variable you need to understand to determine feasibility is C. C is the task's request period. This is how
often a task must be completed. For example, if the request period is C = 30, the task must be completed ** every 30
time units**. If the task is unable to be completed due to conflicts, the algorithm is

Now we can finally get to the math. To calculate whether a task set can be feasible with this algorithm, we must first calculate the utilization bound (represented with U). The utilization bound is the highest percentage of processor time the task set can use and still be feasible. I'll explain a little more after we get the math out of the way.

The utilization bound is calculated with the formula:

Not that tough. As an example, we'll say that there are 4 tasks in a set. That would be U = 4(2^{1/4}-1).
The utilization bound would then be 75.7%. If there were 3 tasks in a set, the bound would be 77.9%. Note that the less
tasks there are, the higher the bound. This is because when there are less tasks, it gives them a better chance to complete.
The utilization bound will only change based on how many tasks there are. Task length/period length will * not*
effect U.

Calculating processor utilization is slightly more difficult and involves summations. The formula is as follows:

Let's say we have a task set: C_{1}=6, C_{2}=1, and C_{3}=26. T_{1}=24, T_{2}=50,
and T_{3}=60. To complete the formula, we'd say:

Which then goes to:

Because the bound for a task set m = 3 is 78%, the task set is feasible under this algorithm.

That's a good question. If U is larger than the bound, the task set ** may** still be feasible. The only
way to find out at that point is to create a Gantt diagram. There are plenty of other resources on how to do that.

Now we've finally made it to the star of the show: the Dynamic Algorithm. This algorithm is the reason the paper
was written. It works by calculating which task needs to be completed * every* time unit. It determines which
unfinished task needs to be completed, then picks the one with the closest deadline. Of course, this algorithm is also
preemptive. Here's an example of a task set being completed with the dynamic algorithm:

Note that the fixed priority algorithm preempts the last task in favor of the first at time unit 31. This is because it was
a shorter task and therefore had a higher priority under this algorithm. Because of this though, the algorithm is not
feasible for this task set. The deadline driven algorithm, however, * completes* the final task before moving on
because it has the earliest uncompleted deadline at that point.

The deadline driven algorithm is feasible as long as the utilization bound is under 100%. That's it. No math for
this one, thank God. Why not, though? Well, it's because the processor is using * every single* time unit,
whereas there were many wasted time units under the fixed priority algorithm.

Liu and Layland's paper also outlined a "mixed" scheduling algorithm. This algorithm is simply a mixture of the
two previous algorithms. Computer Scientists are creative with names, huh? I'll give a very basic run-down on how this
algorithm works, since it isn't particularly relevant today. They basically split the task set into two halves. The first
half contains all the tasks with the shortest periods. The second group contains the tasks with the largest periods. The
first group is completed using the fixed priority algorithm, but the second group is completed with the deadline driven.
The second group can only go when the first group * is not completing a task.* This is very important. The
processor cannot complete two tasks at the same time.

The hardware back in the 70's was much different from the hardware today. Liu and Layland realized that the algorithm they created could not be run on computers at the time. They also realized that it would be incredibly expensive to replace the hardware so they could implement the dynamic algorithm, so they came up with the mixed scheduling algorithm. This algorithm could be implemented on the hardware of the time with only a minor software update, rather than replacing entire machines or hardware. Of course, the algorithm was a product of its time, meaning that it's not really relevant today. Althoug it is still an interesting part of history, in my opinion.

In this article, we outlined how the fixed priority rate monotonic, dynamic deadline driven, and mixed algorithms work as outlined in Dr. Liu and Layland's groundbreaking paper. We showed that the dynamic algorithm is more efficient than the fixed priority. I also showed how to calculate the utilization bound for each algorithm, as well as how to calculate when the algorithms were feasible. Hopefully this made sense to you and feel free to ask questions in the comments.

The paper is much more extensive than I was. I know that this article was long, but the paper goes much more
in-depth. The authors provide mathematical proofs on * why* these things are true, whereas I just presented
you with the basic facts from the paper.

I highly suggest you read the paper
__ HERE__.

You can also see randomly generated Gantt Diagrams *
HERE.*
The program is run in the browser and hosted on this site, so no need to download anything. Seeing some examples on how
the algorithms are scheduled might help you understand how they work.

If you're interested in seeing the code for the program, it can be found *
HERE.*
The program is written in JavaScript and is run in your browser. No additional software is needed.

Thanks for reading,

-John DeHart