// mlfq.c — simulador de una Multi-Level Feedback Queue con tres colas.
//
// Uso:   ./mlfq [-q quantum] [-a asignación] [-b periodo] [-o] trabajo...
//        trabajo: duración[@llegada][:ráfaga/espera]
//          duración  ticks de CPU que necesita en total
//          llegada   tick en que entra al sistema (0 si se omite)
//          ráfaga    corre esa cantidad de ticks y luego hace E/S...
//          espera    ...que tarda esa cantidad de ticks
//        -q  quantum de cada cola (por defecto 4)
//        -a  asignación (allotment) por nivel (por defecto, igual al quantum)
//        -b  boost: cada cuántos ticks subir todo a la cola más alta (0 = nunca)
//        -o  reglas viejas 4a/4b: quien suelta la CPU antes de agotar su
//            asignación conserva la prioridad y su cuenta vuelve a cero.
//            Sin -o se usa la regla 4: la cuenta se acumula aunque haga E/S.
//
// Ejemplos:
//   ./mlfq 20 6@10                       un trabajo largo y uno corto
//   ./mlfq -o 20 12@8:2/2 12@8:2/2       dos interactivos dejan sin CPU a A
//   ./mlfq -o -b 16 20 12@8:2/2 12@8:2/2 lo mismo, con boost cada 16
//   ./mlfq -o 20 15@8:3/1                B hace trampa con las reglas 4a/4b
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define NLEVELS 3
#define MAXJOBS 26
#define MAXTICKS 600

struct job {
    char name;
    int arrival, length, remaining;
    int burst, io;          // patrón de E/S (burst = 0: solo CPU)
    int level;              // cola actual: NLEVELS-1 es la más alta
    int used;               // ticks usados en este nivel (asignación)
    int slice;              // ticks usados del quantum actual
    int run;                // ticks corridos en la ráfaga actual
    int io_until;           // bloqueado hasta este tick (-1 si no)
    int first_run, finish;
};

static struct job jobs[MAXJOBS];
static int njobs;

// Una cola por nivel: arreglos simples, el primero es el que corre.
static int q[NLEVELS][MAXJOBS];
static int qlen[NLEVELS];

// gantt[nivel][t]: letra del trabajo que corrió en t en ese nivel.
static char gantt[NLEVELS][MAXTICKS];

static void push(int lvl, int j) {
    q[lvl][qlen[lvl]++] = j;
}

static void remove_job(int lvl, int j) {
    int k = 0;
    for (int i = 0; i < qlen[lvl]; i++)
        if (q[lvl][i] != j)
            q[lvl][k++] = q[lvl][i];
    qlen[lvl] = k;
}

// Regla 5: todos los trabajos vuelven a la cola más alta.
static void boost(void) {
    int top = NLEVELS - 1;
    for (int lvl = top - 1; lvl >= 0; lvl--) {
        for (int i = 0; i < qlen[lvl]; i++)
            push(top, q[lvl][i]);
        qlen[lvl] = 0;
    }
    for (int j = 0; j < njobs; j++) {
        jobs[j].level = top;    // los bloqueados también suben
        jobs[j].used = 0;
        jobs[j].slice = 0;
    }
}

static int simulate(int quantum, int allot, int period, int old_rules) {
    int top = NLEVELS - 1, done = 0, t;

    for (t = 0; t < MAXTICKS && done < njobs; t++) {
        for (int j = 0; j < njobs; j++) {
            struct job *p = &jobs[j];
            if (p->arrival == t)            // regla 3: entra arriba
                push(top, j);
            if (p->io_until == t) {         // terminó su E/S
                p->io_until = -1;
                push(p->level, j);
            }
        }
        if (period > 0 && t > 0 && t % period == 0)
            boost();

        int lvl = top;                      // regla 1: la cola más alta
        while (lvl >= 0 && qlen[lvl] == 0)
            lvl--;
        if (lvl < 0)
            continue;                       // CPU ociosa

        int j = q[lvl][0];                  // regla 2: RR dentro de la cola
        struct job *p = &jobs[j];
        if (p->first_run < 0)
            p->first_run = t;
        gantt[lvl][t] = p->name;
        p->remaining--;
        p->used++;
        p->slice++;
        p->run++;

        if (p->remaining == 0) {
            p->finish = t + 1;
            remove_job(lvl, j);
            done++;
            continue;
        }

        int does_io = p->burst > 0 && p->run == p->burst;
        int demote = p->used >= allot;      // agotó su asignación
        if (!demote && does_io && old_rules)
            p->used = 0;                    // regla 4b: soltó la CPU a tiempo

        if (demote || does_io || p->slice >= quantum) {
            remove_job(lvl, j);
            p->slice = 0;
            if (demote) {                   // regla 4 (o 4a): baja un nivel
                p->used = 0;
                if (p->level > 0)
                    p->level--;
            }
            if (does_io) {
                p->run = 0;
                p->io_until = t + 1 + p->io;
            } else {
                push(p->level, j);          // al final de su cola
            }
        }
    }
    return t;
}

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)
                i += printf("%d", i) - 1;
            else
                putchar(' ');
        }
        printf("\n");
        for (int lvl = NLEVELS - 1; lvl >= 0; lvl--) {
            printf("Q%d  ", lvl);
            for (int i = start; i < end; i++)
                putchar(gantt[lvl][i] ? gantt[lvl][i] : '.');
            printf("\n");
        }
    }
    printf("\n");
}

static void print_table(int total) {
    printf("trabajo llegada duración  fin  retorno  respuesta\n");
    for (int j = 0; j < njobs; j++) {
        struct job *p = &jobs[j];
        printf("   %c    %5d   %6d", p->name, p->arrival, p->length);
        if (p->remaining > 0)
            printf("    -        -");
        else
            printf(" %4d  %7d", p->finish, p->finish - p->arrival);
        if (p->first_run >= 0)
            printf("  %9d\n", p->first_run - p->arrival);
        else
            printf("          -\n");
    }
    printf("ticks simulados: %d\n", total);
}

static void usage(const char *prog) {
    fprintf(stderr, "uso: %s [-q quantum] [-a asignación] [-b periodo] [-o] "
                    "duración[@llegada][:ráfaga/espera]...\n", prog);
    exit(1);
}

int main(int argc, char *argv[]) {
    int quantum = 4, allot = 0, period = 0, old_rules = 0, opt;
    while ((opt = getopt(argc, argv, "q:a:b:o")) != -1) {
        switch (opt) {
        case 'q': quantum = atoi(optarg); break;
        case 'a': allot = atoi(optarg); break;
        case 'b': period = atoi(optarg); break;
        case 'o': old_rules = 1; break;
        default: usage(argv[0]);
        }
    }
    if (allot == 0)
        allot = quantum;
    if (optind >= argc || quantum < 1 || allot < 1 || period < 0)
        usage(argv[0]);

    for (int i = optind; i < argc && njobs < MAXJOBS; i++) {
        struct job *p = &jobs[njobs];
        p->name = 'A' + njobs;
        const char *s = argv[i];
        int n;
        if (sscanf(s, "%d%n", &p->length, &n) != 1 || p->length < 1)
            usage(argv[0]);
        s += n;
        if (*s == '@') {
            if (sscanf(s + 1, "%d%n", &p->arrival, &n) != 1)
                usage(argv[0]);
            s += 1 + n;
        }
        if (*s == ':' && (sscanf(s + 1, "%d/%d", &p->burst, &p->io) != 2 ||
                          p->burst < 1 || p->io < 1))
            usage(argv[0]);
        p->remaining = p->length;
        p->level = NLEVELS - 1;
        p->io_until = -1;
        p->first_run = -1;
        njobs++;
    }

    printf("MLFQ: %d colas, quantum %d, asignación %d, boost %s, regla %s\n",
           NLEVELS, quantum, allot, period ? "sí" : "no",
           old_rules ? "4a/4b" : "4");
    if (period)
        printf("boost cada %d ticks\n", period);

    int total = simulate(quantum, allot, period, old_rules);
    print_gantt(total);
    print_table(total);
    return 0;
}

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

// sched.c — simulador de planificación: FIFO, SJF, STCF y Round Robin.
//
// Uso:   ./sched [-q quantum] [-c costo] política trabajo...
//        política: fifo | sjf | stcf | rr
//        trabajo:  duración[@llegada]   (los trabajos se llaman A, B, C...)
//
// Ejemplos:
//   ./sched fifo 12 3 3          tres trabajos que llegan en t = 0
//   ./sched stcf 12 3@2 3@2      B y C llegan en t = 2
//   ./sched -q 2 -c 1 rr 6 6 6   Round Robin, quantum 2, cambio de contexto 1
//
// El tiempo avanza en ticks enteros. Reglas de desempate:
//   - FIFO: menor llegada; si empatan, el orden de la línea de comandos.
//   - SJF:  menor duración; luego menor llegada; luego el orden.
//   - STCF: menor tiempo restante; si empatan, sigue el que ya corría.
//   - RR:   los que llegan en t entran a la cola ANTES que el que fue
//           desalojado en t.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define MAXJOBS 26
#define MAXTICKS 10000

enum policy { FIFO, SJF, STCF, RR };

struct job {
    char name;
    int arrival;
    int length;
    int remaining;
    int first_run;   // -1 mientras no haya corrido nunca
    int finish;
};

static struct job jobs[MAXJOBS];
static int njobs;
static char gantt[MAXTICKS];   // una letra por tick: trabajo, '-' ocioso, '*' cambio

// Cola circular para Round Robin.
static int queue[MAXJOBS + 1];
static int qhead, qtail;

static void enqueue(int j) {
    queue[qtail] = j;
    qtail = (qtail + 1) % (MAXJOBS + 1);
}

static int dequeue(void) {
    if (qhead == qtail)
        return -1;
    int j = queue[qhead];
    qhead = (qhead + 1) % (MAXJOBS + 1);
    return j;
}

static int ready(int j, int t) {
    return jobs[j].arrival <= t && jobs[j].remaining > 0;
}

// FIFO, SJF y STCF: elegir entre los trabajos listos en t.
static int pick(enum policy pol, int t, int cur) {
    int best = -1;
    for (int j = 0; j < njobs; j++) {
        if (!ready(j, t))
            continue;
        if (best < 0) {
            best = j;
            continue;
        }
        struct job *a = &jobs[j], *b = &jobs[best];
        if (pol == FIFO && a->arrival < b->arrival)
            best = j;
        if (pol == SJF && (a->length < b->length ||
                           (a->length == b->length && a->arrival < b->arrival)))
            best = j;
        if (pol == STCF && a->remaining < b->remaining)
            best = j;
    }
    // STCF: ante un empate, no desalojar al que está corriendo.
    if (pol == STCF && cur >= 0 && ready(cur, t) &&
        jobs[cur].remaining == jobs[best].remaining)
        best = cur;
    return best;
}

static int simulate(enum policy pol, int quantum, int cost) {
    int t = 0, done = 0;
    int cur = -1;        // trabajo elegido
    int last = -1;       // último trabajo que usó la CPU
    int slice = 0;       // ticks usados del quantum actual
    int overhead = 0;    // ticks de cambio de contexto pendientes

    while (done < njobs && t < MAXTICKS) {
        if (pol == RR)
            for (int j = 0; j < njobs; j++)
                if (jobs[j].arrival == t)
                    enqueue(j);

        if (overhead > 0) {          // el kernel está cambiando de contexto
            gantt[t++] = '*';
            overhead--;
            continue;
        }

        int prev = cur;
        if (pol == RR) {
            if (cur >= 0 && slice == quantum) {   // se acabó el quantum
                enqueue(cur);
                cur = -1;
            }
            if (cur < 0) {
                cur = dequeue();
                slice = 0;
            }
        } else if (pol == STCF || cur < 0) {      // FIFO y SJF no desalojan
            cur = pick(pol, t, cur);
        }

        if (cur < 0) {               // nadie listo: CPU ociosa
            gantt[t++] = '-';
            continue;
        }
        if (cur != prev && last >= 0 && cur != last && cost > 0) {
            gantt[t++] = '*';        // cobrar el cambio antes de correr
            overhead = cost - 1;
            continue;
        }

        struct job *p = &jobs[cur];
        if (p->first_run < 0)
            p->first_run = t;
        gantt[t++] = p->name;
        p->remaining--;
        slice++;
        last = cur;
        if (p->remaining == 0) {
            p->finish = t;
            done++;
            cur = -1;
        }
    }
    return t;
}

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

    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\n");
}

static void print_table(int total) {
    double sum_ta = 0, sum_resp = 0;
    int switching = 0;

    printf("trabajo llegada duración  inicio  fin  retorno  respuesta\n");
    for (int j = 0; j < njobs; j++) {
        struct job *p = &jobs[j];
        int ta = p->finish - p->arrival;       // tiempo de retorno
        int resp = p->first_run - p->arrival;  // tiempo de respuesta
        sum_ta += ta;
        sum_resp += resp;
        printf("   %c    %5d   %6d  %6d %5d  %7d  %9d\n",
               p->name, p->arrival, p->length, p->first_run, p->finish, ta, resp);
    }
    printf("promedio                              %7.2f  %9.2f\n",
           sum_ta / njobs, sum_resp / njobs);

    for (int i = 0; i < total; i++)
        switching += gantt[i] == '*';
    if (switching > 0)
        printf("cambios de contexto: %d ticks de %d (%.0f%% de la CPU)\n",
               switching, total, 100.0 * switching / total);
}

static void usage(const char *prog) {
    fprintf(stderr, "uso: %s [-q quantum] [-c costo] fifo|sjf|stcf|rr "
                    "duración[@llegada]...\n", prog);
    exit(1);
}

int main(int argc, char *argv[]) {
    int quantum = 1, cost = 0, opt;
    while ((opt = getopt(argc, argv, "q:c:")) != -1) {
        if (opt == 'q')
            quantum = atoi(optarg);
        else if (opt == 'c')
            cost = atoi(optarg);
        else
            usage(argv[0]);
    }
    if (argc - optind < 2 || quantum < 1 || cost < 0)
        usage(argv[0]);

    const char *names[] = {"fifo", "sjf", "stcf", "rr"};
    const char *titles[] = {"FIFO", "SJF", "STCF", "Round Robin"};
    int pol = -1;
    for (int i = 0; i < 4; i++)
        if (strcmp(argv[optind], names[i]) == 0)
            pol = i;
    if (pol < 0)
        usage(argv[0]);

    for (int i = optind + 1; i < argc && njobs < MAXJOBS; i++) {
        struct job *p = &jobs[njobs];
        p->name = 'A' + njobs;
        p->arrival = 0;
        if (sscanf(argv[i], "%d@%d", &p->length, &p->arrival) < 1 ||
            p->length < 1 || p->arrival < 0)
            usage(argv[0]);
        p->remaining = p->length;
        p->first_run = -1;
        njobs++;
    }

    printf("política: %s", titles[pol]);
    if (pol == RR)
        printf(" (quantum %d)", quantum);
    if (cost > 0)
        printf(", cambio de contexto: %d", cost);
    printf("\n");

    int total = simulate(pol, quantum, cost);
    print_gantt(total);
    print_table(total);
    return 0;
}

# Semana 3: simuladores de planificación.
#   make         compila todo
#   make test    corre los ejemplos de los apuntes
#   make clean   borra los binarios
CFLAGS = -Wall -Wextra -g
LDLIBS = -lm
PROGS  = sched mlfq rtsched

all: $(PROGS)

test: $(PROGS)
	./sched fifo 12 3 3
	./sched stcf 12 3@2 3@2
	./sched -q 3 -c 1 rr 6 6 6
	./mlfq 20 6@10
	./mlfq -o 20 15@8:3/1
	./mlfq 20 15@8:3/1
	./rtsched 3/6 4/9

clean:
	rm -f $(PROGS)

.PHONY: all test clean