Instructions: Enter the Execution Time ($C_i$) and the Period ($T_i$) for each task. In RMS, tasks with shorter periods are assigned higher priority.
Task ID
Execution Time ($C_i$)
Period ($T_i$)
Action
Task 1
Task 2
Analysis Results
Total Utilization ($U$):0
Liu-Layland Bound:0
Status:
–
Understanding Rate Monotonic Scheduling (RMS)
Rate Monotonic Scheduling (RMS) is a priority assignment algorithm used in real-time operating systems (RTOS). It follows a fixed-priority discipline where the priority of a task is inversely proportional to its period. This means the more frequently a task needs to run, the higher its priority.
The Schedulability Formula
To determine if a set of $n$ periodic tasks can meet all their deadlines, we use the Liu and Layland Bound. The total CPU utilization ($U$) is calculated as:
U = Σ (Ci / Ti)
The tasks are guaranteed to be schedulable if:
U ≤ n(21/n – 1)
Interpreting the Results
U ≤ Bound: The task set is definitely schedulable. Deadlines will never be missed.
Bound < U ≤ 1.0: The task set might be schedulable. RMS does not guarantee it, and you would need to perform Response Time Analysis (RTA) for a definitive answer.
U > 1.0: The task set is not schedulable. The CPU is over-utilized, and deadlines will be missed regardless of the scheduling algorithm.
Practical Example
Consider two tasks:
Task 1: Execution Time = 1ms, Period = 3ms (Utilization = 0.33)
Task 2: Execution Time = 2ms, Period = 6ms (Utilization = 0.33)
Total Utilization = 0.66
For n=2, the bound is 2(21/2 – 1) ≈ 0.828
Since 0.66 ≤ 0.828, the set is guaranteed to be schedulable.
function addRow() {
var table = document.getElementById("task-body");
var rowCount = table.rows.length + 1;
var row = table.insertRow(-1);
row.className = "task-row";
row.innerHTML = '
Task ' + rowCount + '
' +
'
' +
'
' +
'
';
}
function removeRow(btn) {
var row = btn.parentNode.parentNode;
row.parentNode.removeChild(row);
// Renumber rows
var rows = document.getElementById("task-body").rows;
for (var i = 0; i < rows.length; i++) {
rows[i].cells[0].innerHTML = "Task " + (i + 1);
}
}
function calculateRMS() {
var execInputs = document.getElementsByClassName("exec-time");
var periodInputs = document.getElementsByClassName("period-time");
var n = execInputs.length;
var totalU = 0;
if (n === 0) {
alert("Please add at least one task.");
return;
}
for (var i = 0; i < n; i++) {
var ci = parseFloat(execInputs[i].value);
var ti = parseFloat(periodInputs[i].value);
if (isNaN(ci) || isNaN(ti) || ti <= 0 || ci ti) {
alert("Task " + (i+1) + " error: Execution time cannot be greater than the period.");
return;
}
totalU += (ci / ti);
}
// Bound formula: n(2^(1/n) – 1)
var bound = n * (Math.pow(2, 1/n) – 1);
// As n approaches infinity, bound approaches ln(2) approx 0.693
if (n > 100) {
bound = 0.693147;
}
document.getElementById("total-utilization").innerText = totalU.toFixed(4);
document.getElementById("ll-bound").innerText = bound.toFixed(4);
var statusEl = document.getElementById("schedulable-status");
var containerEl = document.getElementById("status-container");
var explanationEl = document.getElementById("explanation-text");
document.getElementById("result-box").style.display = "block";
if (totalU <= bound) {
statusEl.innerText = "Guaranteed Schedulable";
statusEl.style.color = "#ffffff";
containerEl.style.backgroundColor = "#34a853";
explanationEl.innerText = "The total utilization is below the Liu-Layland bound for " + n + " tasks. This task set will always meet its deadlines under RMS.";
} else if (totalU <= 1.0) {
statusEl.innerText = "Possibly Schedulable";
statusEl.style.color = "#000000";
containerEl.style.backgroundColor = "#fbbc05";
explanationEl.innerText = "The utilization is above the conservative bound but below or equal to 100%. The task set might meet deadlines, but RMS cannot guarantee it without further Response Time Analysis.";
} else {
statusEl.innerText = "NOT Schedulable";
statusEl.style.color = "#ffffff";
containerEl.style.backgroundColor = "#ea4335";
explanationEl.innerText = "The CPU utilization exceeds 100%. It is mathematically impossible to schedule these tasks on a single processor without missing deadlines.";
}
}