// priosim.c — simulación determinista de la inversión de prioridad.
//
// Uso: ./priosim none      sin protocolo: M retrasa a H sin tocar el lock
//      ./priosim inherit   herencia de prioridad (priority inheritance)
//      ./priosim ceiling   techo de prioridad (priority ceiling)
// Una CPU, prioridades fijas y desalojo: siempre corre el hilo listo de
// mayor prioridad (como SCHED_FIFO). El tiempo avanza en ticks; cada hilo
// sigue un guion de pasos: RUN n (usar la CPU n ticks), LOCK y UNLOCK.
// No necesita privilegios y la salida es siempre la misma.
#include <stdio.h>
#include <string.h>

enum { RUN, LOCK, UNLOCK, END };
struct step { int op, n; };

struct thread {
    const char *name;
    int base, prio;                     // prioridad base y efectiva
    int arrive;                         // tick de llegada
    const struct step *prog;
    int pc, left;                       // paso actual y ticks que le faltan
    int blocked, done, since;           // since: desde cuándo espera la CPU
    char row[64];                       // la línea de tiempo, un carácter por tick
};

// L usa el lock 4 ticks; H lo necesita 2 ticks; M nunca lo toca.
static const struct step progL[] = {{RUN, 1}, {LOCK, 0}, {RUN, 4}, {UNLOCK, 0}, {RUN, 1}, {END, 0}};
static const struct step progM[] = {{RUN, 6}, {END, 0}};
static const struct step progH[] = {{RUN, 1}, {LOCK, 0}, {RUN, 2}, {UNLOCK, 0}, {RUN, 1}, {END, 0}};

#define NT   3
#define CEIL 30                         // techo del lock: la prioridad de H
static struct thread th[NT] = {
    {.name = "H", .base = 30, .prio = 30, .arrive = 2, .prog = progH},
    {.name = "M", .base = 20, .prio = 20, .arrive = 3, .prog = progM},
    {.name = "L", .base = 10, .prio = 10, .arrive = 0, .prog = progL},
};
static struct thread *H = &th[0];

static struct thread *owner;            // owner del lock (NULL: libre)
static int mode;                        // 0 none, 1 inherit, 2 ceiling
static int h_asked;

// Recalcula la prioridad del owner según el protocolo.
static void boost_owner(int t) {
    if (!owner)
        return;
    int p = owner->base;
    if (mode == 2)
        p = CEIL;                       // techo: apenas toma el lock
    if (mode == 1)                      // herencia: la del que más espera
        for (int i = 0; i < NT; i++)
            if (th[i].blocked && th[i].prio > p)
                p = th[i].prio;
    if (p != owner->prio) {
        printf("t=%2d  %s sube a prioridad %d\n", t, owner->name, p);
        owner->prio = p;
    }
}

static void do_unlock(struct thread *me, int t) {
    owner = NULL;
    printf("t=%2d  %s suelta el lock\n", t, me->name);
    if (me->prio != me->base) {
        printf("t=%2d  %s vuelve a prioridad %d\n", t, me->name, me->base);
        me->prio = me->base;
    }
    struct thread *next = NULL;         // el lock pasa al bloqueado de mayor prioridad
    for (int i = 0; i < NT; i++)
        if (th[i].blocked && (!next || th[i].prio > next->prio))
            next = &th[i];
    if (next) {
        next->blocked = 0;
        next->since = t;
        next->pc++;                     // su LOCK ya se cumplió
        owner = next;
        printf("t=%2d  %s obtiene el lock", t, next->name);
        if (next == H)
            printf(" (esperó %d ticks)", t - h_asked);
        printf("\n");
        boost_owner(t);
    }
}

// Ejecuta los pasos instantáneos al frente del guion de `me`, en el instante t.
// Devuelve 1 si quedó listo para usar la CPU; 0 si se bloqueó o terminó.
static int instant_steps(struct thread *me, int t) {
    for (;; me->pc++) {
        const struct step *s = &me->prog[me->pc];
        if (s->op == RUN) {
            if (me->left == 0)
                me->left = s->n;
            return 1;
        }
        if (s->op == END) {
            me->done = 1;
            printf("t=%2d  %s termina\n", t, me->name);
            return 0;
        }
        if (s->op == UNLOCK) {
            do_unlock(me, t);
            continue;
        }
        // LOCK
        if (me == H)
            h_asked = t;
        if (owner) {
            me->blocked = 1;
            printf("t=%2d  %s pide el lock: lo tiene %s, se bloquea\n", t, me->name, owner->name);
            boost_owner(t);
            return 0;
        }
        owner = me;
        printf("t=%2d  %s toma el lock\n", t, me->name);
        boost_owner(t);
    }
}

// ¿Debe correr a antes que b? Mayor prioridad; si empatan, sigue el que
// corría (cur) y si no, el que espera hace más tiempo.
static int before(struct thread *a, struct thread *b, struct thread *cur) {
    if (!b || a->prio != b->prio)
        return !b || a->prio > b->prio;
    if (a == cur || b == cur)
        return a == cur;
    return a->since < b->since;
}

int main(int argc, char *argv[]) {
    const char *m = argc > 1 ? argv[1] : "";
    if (!strcmp(m, "none"))
        mode = 0;
    else if (!strcmp(m, "inherit"))
        mode = 1;
    else if (!strcmp(m, "ceiling"))
        mode = 2;
    else {
        fprintf(stderr, "uso: %s none|inherit|ceiling\n", argv[0]);
        return 1;
    }

    struct thread *cur = NULL;
    int t;
    for (t = 0; t < 60; t++) {
        for (int i = 0; i < NT; i++)
            if (th[i].arrive == t) {
                th[i].since = t;
                printf("t=%2d  %s llega\n", t, th[i].name);
            }
        struct thread *pick;
        do {                            // elegir; si el elegido se bloquea, otra vez
            pick = NULL;
            for (int i = 0; i < NT; i++)
                if (th[i].arrive <= t && !th[i].done && !th[i].blocked &&
                    before(&th[i], pick, cur))
                    pick = &th[i];
        } while (pick && !instant_steps(pick, t));
        if (!pick)
            break;                      // todos terminaron
        if (cur && cur != pick) {
            if (!cur->done && !cur->blocked) {
                printf("t=%2d  %s desaloja a %s\n", t, pick->name, cur->name);
                cur->since = t;
            } else {
                printf("t=%2d  la CPU pasa a %s\n", t, pick->name);
            }
        }
        cur = pick;

        for (int i = 0; i < NT; i++) {  // dibujar el tick t
            struct thread *x = &th[i];
            char c = ' ';
            if (x == pick)
                c = owner == x ? 'X' : '#';
            else if (x->arrive <= t && !x->done)
                c = x->blocked ? '-' : '.';
            x->row[t] = c;
        }
        if (--pick->left == 0) {        // terminó este RUN
            pick->pc++;
            if (pick->prog[pick->pc].op != LOCK)
                instant_steps(pick, t + 1);  // UNLOCK o END: al final del tick
        }
    }

    printf("\n        ");
    for (int i = 0; i < t; i++)
        putchar('0' + i % 10);
    printf("\n");
    for (int i = 0; i < NT; i++)
        printf("%s (%d)  %.*s\n", th[i].name, th[i].base, t, th[i].row);
    printf("X: corre con el lock  #: corre  .: listo  -: bloqueado en el lock\n");
    return 0;
}