// rtsched.c — simulador de planificación de tiempo real: rate-monotonic (RM)
// y earliest deadline first (EDF) con tareas periódicas.
//
// Uso:   ./rtsched tarea...
//        tarea: C/T   (cómputo por periodo / periodo; las tareas se llaman A, B, C...)
//
// Ejemplo:
//   ./rtsched 3/6 4/9     A necesita 3 ticks cada 6; B, 4 cada 9
//
// Modelo: cada tarea suelta una instancia en t = 0, T, 2T, ... y el plazo
// (deadline) de cada instancia es el inicio de la siguiente (D = T). Simula
// las dos políticas hasta el hiperperiodo (el mcm de los periodos).
//
// En cada tick t, en este orden:
//   1. Plazos: si una instancia llega a su plazo sin terminar, es un plazo
//      perdido. Se anota y se descarta lo que le faltaba.
//   2. Llegadas: las tareas con t múltiplo de T sueltan una instancia nueva.
//   3. Elegir: RM, la de menor periodo (empate: el orden de la línea de
//      comandos). EDF, la de plazo más cercano (empate: sigue la que ya
//      corría; si no, el orden de la línea de comandos).
//   4. Correr un tick. '.' en el diagrama = CPU ociosa.
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#define MAXTASKS 8
#define MAXTICKS 1000

enum policy { RM, EDF };

struct task {
    char name;
    int c, t;        // cómputo y periodo
    int remaining;   // lo que le falta a la instancia actual
    int deadline;    // plazo absoluto de la instancia actual
};

static struct task tasks[MAXTASKS];
static int ntasks;
static char gantt[MAXTICKS + 1];
static char misses[MAXTICKS + 2];   // '!' en el instante de un plazo perdido

// Plazos perdidos, para imprimirlos después del diagrama.
static struct { char name; int t, left; } lost[MAXTASKS * (MAXTICKS + 1)];
static int nlost;

static long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

static int pick(enum policy pol, int cur) {
    int best = -1;
    for (int i = 0; i < ntasks; i++) {
        if (tasks[i].remaining == 0)
            continue;
        if (best < 0 ||
            (pol == RM && tasks[i].t < tasks[best].t) ||
            (pol == EDF && tasks[i].deadline < tasks[best].deadline))
            best = i;
    }
    // EDF: ante un empate de plazos, no desalojar a la que está corriendo.
    if (pol == EDF && cur >= 0 && tasks[cur].remaining > 0 &&
        tasks[cur].deadline == tasks[best].deadline)
        best = cur;
    return best;
}

static void simulate(enum policy pol, int end) {
    int cur = -1;
    nlost = 0;
    for (int i = 0; i < ntasks; i++)
        tasks[i].remaining = 0;

    for (int t = 0; t <= end; t++) {
        misses[t] = ' ';
        for (int i = 0; i < ntasks; i++) {
            struct task *p = &tasks[i];
            if (p->remaining > 0 && p->deadline == t) {   // 1. plazo perdido
                lost[nlost].name = p->name;
                lost[nlost].t = t;
                lost[nlost++].left = p->remaining;
                misses[t] = '!';
                p->remaining = 0;
            }
            if (t % p->t == 0 && t < end) {               // 2. llegada
                p->remaining = p->c;
                p->deadline = t + p->t;
            }
        }
        if (t == end)
            break;
        cur = pick(pol, cur);                             // 3. elegir
        if (cur < 0) {
            gantt[t] = '.';
            continue;
        }
        gantt[t] = tasks[cur].name;                       // 4. correr
        tasks[cur].remaining--;
    }
    gantt[end] = misses[end + 1] = '\0';
}

static void print_gantt(int total) {
    for (int start = 0; start < total; start += 60) {
        int end = start + 60 < total ? start + 60 : total;
        printf("       ");
        for (int i = start; i < end; i++) {
            if (i % 5 == 0) {
                int n = printf("%d", i);
                i += n - 1;
            } else {
                putchar(' ');
            }
        }
        printf("\ngantt  %.*s\n", end - start, gantt + start);
        // los plazos perdidos caen en el borde izquierdo del tick t
        int last = -1;
        int lim = end == total ? end : end - 1;   // t = 60 va en la fila siguiente
        for (int i = start; i <= lim; i++)
            if (misses[i] == '!')
                last = i;
        if (last >= 0)
            printf("plazo  %.*s\n", last - start + 1, misses + start);
    }

    printf("tramos ");
    for (int i = 0; i < total;) {
        int k = i;
        while (k < total && gantt[k] == gantt[i])
            k++;
        printf("%c[%d,%d) ", gantt[i], i, k);
        i = k;
    }
    printf("\n");
}

static void run(enum policy pol, int end) {
    if (pol == RM)
        printf("\nRM (prioridad fija: menor periodo primero)\n");
    else
        printf("\nEDF (prioridad dinámica: plazo más cercano primero)\n");
    simulate(pol, end);
    print_gantt(end);
    printf("plazos perdidos: %d\n", nlost);
    for (int i = 0; i < nlost; i++)
        printf("  %c en t = %d (le faltaba%s %d)\n", lost[i].name, lost[i].t,
               lost[i].left > 1 ? "n" : "", lost[i].left);
}

static void usage(const char *prog) {
    fprintf(stderr, "uso: %s C/T...   (1 <= C <= T, hasta %d tareas)\n",
            prog, MAXTASKS);
    exit(1);
}

int main(int argc, char *argv[]) {
    if (argc < 2 || argc - 1 > MAXTASKS)
        usage(argv[0]);

    long long hyper = 1;
    double u = 0;
    for (int i = 1; i < argc; i++) {
        struct task *p = &tasks[ntasks];
        p->name = 'A' + ntasks;
        if (sscanf(argv[i], "%d/%d", &p->c, &p->t) != 2 ||
            p->c < 1 || p->c > p->t)
            usage(argv[0]);
        if (hyper <= MAXTICKS)   // más allá no hace falta el valor exacto
            hyper = hyper / gcd(hyper, p->t) * p->t;
        u += (double)p->c / p->t;
        ntasks++;
    }

    int n = ntasks;
    double bound = n * (pow(2.0, 1.0 / n) - 1);   // cota de Liu y Layland
    printf("tarea   C   T   C/T\n");
    for (int i = 0; i < n; i++)
        printf("  %c   %3d %3d  %.3f\n", tasks[i].name, tasks[i].c, tasks[i].t,
               (double)tasks[i].c / tasks[i].t);
    printf("U = %.3f   cota de RM para n = %d: %.3f   hiperperiodo: ", u, n, bound);
    if (hyper <= MAXTICKS)
        printf("%lld\n", hyper);
    else
        printf("más de %d (se simulan solo los primeros %d ticks)\n",
               MAXTICKS, MAXTICKS);
    if (u <= bound + 1e-9)
        printf("U <= cota: RM y EDF cumplen todos los plazos\n");
    else if (u <= 1 + 1e-9)
        printf("cota < U <= 1: EDF cumple; RM no está garantizado (hay que simular)\n");
    else
        printf("U > 1: ninguna política puede cumplir todos los plazos\n");

    int end = hyper <= MAXTICKS ? (int)hyper : MAXTICKS;
    run(RM, end);
    run(EDF, end);
    return 0;
}