Scheduler

In this project I wrote, in C, a simulator that compares two real-time schedulers, rate-monotonic (rate) and earliest-deadline-first (edf), over periodic tasks with C ≤ D ≤ P (the burst C does not exceed the deadline D, and the deadline does not exceed the period P). The program reads a text file, simulates time in discrete units and writes the result to an .out file, without printing anything to stdout.

How the program works

main performs three steps: it validates the mode received as an argument, opens the task file and calls validarArquivo to parse it; then it calls simular, which runs the simulation and writes the output:

if (strcmp(argv[1], "rate") != 0 && strcmp(argv[1], "edf") != 0) {
    fprintf(stderr, "Erro: modo não existente. Modos suportados: 'rate' e 'edf'\n");
    return 1;
}
...
if (validarArquivo(f, t, &n, &tempo_total) != 0) {
    fclose(f);
    return 1;
}
if (simular(argv[1], t, n, tempo_total) != 0) {
    fclose(f);
    return 1;
}

The input format is simple: the first line carries the total simulation time and each following line describes a task as NOME PERÍODO DEADLINE RAJADA:

100
ATT 20 12 8
NAV 50 30 15

In validation I use an extra %c in sscanf to detect garbage at the end of the line. The space before %c swallows spaces and the newline, so the %c only captures a leftover non-blank character, and the sscanf return goes past 4 fields. For the first line the trick is the same, except that it expects exactly one integer:

int campos = sscanf(line, "%d %c", &total, &resto);
if (campos != 1 || total <= 0) {
    fprintf(stderr, "Erro: primeira linha inválida\n");
    return 1;
}
...
char nome[100];
char resto;
int P, D, C;
int campos = sscanf(line, "%s %d %d %d %c", nome, &P, &D, &C, &resto);

if (campos != 4 || P <= 0 || D <= 0 || C <= 0 || C > D || D > P) {
    fprintf(stderr, "Erro: linha %d inválida\n", linha);
    return 1;
}

Every input error goes to stderr with a non-zero exit code, and the output file is never created.

The core of the simulation

The Task structure holds what changes per instance (restante, deadline_abs, ativa) and the accumulated counters (completas, perdidas, mortas). At every time unit simular runs four phases, in this order:

1. discard instances that exceeded the absolute deadline;
2. release the next instance when the time is a multiple of the period;
3. choose the ready task with the highest priority;
4. execute one unit and update the counters.

Discarding comes before releasing, so a late instance is lost at the exact instant of the deadline and only competes again at the next release:

// 1. instância perde o deadline absoluto
for (int i = 0; i < n; i++) {
    if (t[i].ativa && t_atual == t[i].deadline_abs && t[i].restante > 0) {
        t[i].ativa = 0;
        t[i].restante = 0;
        t[i].perdidas++;
    }
}

// 2. nova instância a cada múltiplo do período
for (int i = 0; i < n; i++) {
    if (t_atual % t[i].P == 0) {
        t[i].ativa = 1;
        t[i].restante = t[i].C;
        t[i].deadline_abs = t_atual + t[i].D;
    }
}

To avoid duplicating the simulation loop, I kept a single simular function that receives the mode and changes only the selection criterion: in rate the shortest period wins (fixed priority) and in edf, the shortest absolute deadline (dynamic priority). Ties go to the task that appears first in the file, because the comparison is strict:

int melhor = -1;
for (int i = 0; i < n; i++) {
    if (!t[i].ativa) continue;
    if (melhor == -1) {
        melhor = i;
        continue;
    }
    if (is_rate) {
        if (t[i].P < t[melhor].P) melhor = i;
    } else {
        if (t[i].deadline_abs < t[melhor].deadline_abs) melhor = i;
    }
}

if (melhor != -1) {
    t[melhor].restante--;
    if (t[melhor].restante == 0) {
        t[melhor].ativa = 0;
        t[melhor].completas++;
    }
}

How the log is written

Instead of writing one event per time unit, I accumulate consecutive units in the conta variable and only emit a line when the running task changes. The markers are F (the burst finished), H (preempted by a higher-priority task), L (missed the deadline) and idle (no task ready):

if (melhor != rodando) {
    if (conta > 0) {
        if (rodando == -1)
            fprintf(f, "idle for %d units\n", conta);
        else if (t[rodando].ativa)
            fprintf(f, "[%s] for %d units - H\n", t[rodando].nome, conta);
        else
            fprintf(f, "[%s] for %d units - L\n", t[rodando].nome, conta);
    }
    rodando = melhor;
    conta = 1;
} else {
    conta++;
}

if (melhor != -1 && t[melhor].restante == 0) {
    fprintf(f, "[%s] for %d units - F\n", t[melhor].nome, conta);
    rodando = -1;
    conta = 0;
}

At the end of the window the file carries three summary blocks, one counter per task: LOST DEADLINES, COMPLETE EXECUTION and KILLED. The file name comes from the mode used, rate_gnfr.out or edf_gnfr.out, and the header indicates which algorithm ran.

Particularities and points I would revisit

1. Name read without a width limit. I use %s into a char nome[100]; a name longer than the buffer overflows the validarArquivo stack. It is the classic scanf without a width, the correct form would be %99s.

2. Tie-break by order in the file. Since the comparison is strict (<), a tie goes to the task that appears first in the input. It is simple and deterministic, but it is a rule worth making explicit, because swapping the order of the tasks in the file can change the log in boundary scenarios.

3. Discrete time and a whole window. Everything runs in integer units, C, D, P and the total time are int, and the simulation runs until the tempo_total of the first line. For comparing the algorithms this is enough, but it models neither asynchronous releases nor continuous time.

Improvement points

• Limit the name width when reading (%99s) and validate the line size.
• Optional: extract the best-choice selection into a function that receives the criterion, so the simulation loop does not need the if (is_rate) on every tick.