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