Gabriel Rocha
Projetos

Scheduler

Simulador em C que compara os escalonadores de tempo real rate-monotonic e earliest-deadline-first.

2026Repositório

Neste projeto escrevi, em C, um simulador que compara dois escalonadores de tempo real, o rate-monotonic (rate) e o earliest-deadline-first (edf), sobre tarefas periódicas com C ≤ D ≤ P (a rajada C não passa do deadline D, e o deadline não passa do período P). O programa lê um arquivo de texto, simula o tempo em unidades discretas e grava o resultado em um arquivo .out, sem imprimir nada no stdout.

Como o programa funciona

O main faz três etapas: valida o modo recebido como argumento, abre o arquivo de tarefas e chama validarArquivo para parsear; depois chama simular, que faz a simulação e escreve a saída:

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;
}

O formato de entrada é simples: a primeira linha traz o tempo total da simulação e cada linha seguinte descreve uma tarefa como NOME PERÍODO DEADLINE RAJADA:

100
ATT 20 12 8
NAV 50 30 15

Na validação eu uso um %c extra no sscanf para detectar lixo no fim da linha. O espaço antes do %c engole espaços e quebra de linha, então o %c só captura um caractere não branco sobrando, e o retorno do sscanf passa de 4 campos. Para a primeira linha o truque é o mesmo, só que esperando exatamente um inteiro:

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;
}

Todo erro de entrada vai para o stderr com código de saída diferente de 0, e o arquivo de saída não chega a ser criado.

O núcleo da simulação

A estrutura Task guarda o que muda a cada instância (restante, deadline_abs, ativa) e os contadores acumulados (completas, perdidas, mortas). Em cada unidade de tempo o simular faz quatro fases, nesta ordem:

  1. descarta instâncias que estouraram o deadline absoluto;
  2. libera a instância seguinte quando o tempo é múltiplo do período;
  3. escolhe a tarefa pronta de maior prioridade;
  4. executa uma unidade e atualiza os contadores.

O descarte vem antes da liberação, então uma instância atrasada é perdida no instante exato do deadline e só volta a concorrer na próxima liberação:

// 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;
    }
}

Para não duplicar o laço de simulação, mantive uma única função simular que recebe o modo e muda apenas o critério de escolha: no rate vence o menor período (prioridade fixa) e no edf, o menor deadline absoluto (prioridade dinâmica). Os empates ficam com a tarefa que aparece primeiro no arquivo, pois a comparação é estrita:

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++;
    }
}

Como o log é escrito

Em vez de escrever um evento por unidade de tempo, eu acumulo as unidades consecutivas na variável conta e só emito uma linha quando a tarefa em execução muda. As marcações são F (a rajada terminou), H (preemptada por outra de maior prioridade), L (perdeu o deadline) e idle (nenhuma tarefa pronta):

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;
}

No fim da janela o arquivo traz três blocos de resumo, um contador por tarefa: LOST DEADLINES, COMPLETE EXECUTION e KILLED. O nome do arquivo sai do modo usado, rate_gnfr.out ou edf_gnfr.out, e o cabeçalho indica qual algoritmo rodou.

Particularidades e pontos que revisaria

  1. Nome lido sem limite de largura. Uso %s em um char nome[100]; um nome maior que o buffer estoura a stack do validarArquivo. É o scanf clássico sem largura, o correto seria %99s.

  2. Desempate pela ordem no arquivo. Como a comparação é estrita (<), em empate fica a tarefa que aparece primeiro na entrada. É simples e determinístico, mas é uma regra que vale deixar explícita, porque trocar a ordem das tarefas no arquivo pode mudar o log em cenários de fronteira.

  3. Tempo discreto e janela inteira. Tudo corre em unidades inteiras, C, D, P e o tempo total são int, e a simulação roda até o tempo_total da primeira linha. Para comparar os algoritmos isso basta, mas não modela liberações assíncronas nem tempo contínuo.

Pontos de melhoria