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