# Estado del ejemplo resuelto de los apuntes (semana 12).
# Tres tipos de recurso y cuatro procesos.
recursos   A B C
disponible 2 1 2

maximo          # demanda máxima que declaró cada proceso
P1  5 2 2
P2  3 2 2
P3  2 2 3
P4  1 4 2

asignado        # lo que tiene cada uno ahora
P1  1 1 0
P2  2 0 1
P3  1 1 2
P4  0 2 1

# Dos solicitudes, en orden. Si una se concede, la siguiente parte de ese estado.
pide P1  1 0 1
pide P2  0 1 0

// banker.c — algoritmo del banquero y detección de deadlock con varias
// instancias por recurso.
//
// Uso: ./banker ARCHIVO      lee un estado y lo analiza
//      ./banker -            lee el estado de la entrada estándar
//
// El archivo tiene secciones; '#' empieza un comentario hasta fin de línea:
//
//   recursos   A B C          nombres de los tipos de recurso
//   disponible 2 1 2          instancias libres de cada tipo
//   maximo                    demanda máxima declarada (para evitar), o
//   solicitud                 lo que cada proceso pide ahora (para detectar)
//   P1 5 2 2                  una fila por proceso: nombre y un número por tipo
//   ...
//   asignado                  lo que cada proceso tiene ahora
//   P1 1 1 0
//   ...
//   pide P1 1 0 1             (solo con maximo) solicitudes, en orden
//
// Con maximo: Necesidad = Máximo - Asignado. Dice si el estado es seguro,
// con una secuencia segura, y evalúa cada `pide`: la concede solo si el
// estado que resulta es seguro (y entonces la aplica antes de la siguiente).
// Con solicitud: el mismo algoritmo con Solicitud en vez de Necesidad. Los
// procesos que no pueden terminar están en deadlock; luego prueba abortar a
// cada uno por separado.
//
// En cada vuelta se elige el PRIMER proceso (en el orden del archivo) que
// puede terminar; puede haber otras secuencias seguras.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXP 16
#define MAXR 8
#define MAXREQ 16
#define NAMELEN 16

static int nres, nproc;
static char res[MAXR][NAMELEN];
static char proc[MAXP][NAMELEN];
static int avail[MAXR];
static int max[MAXP][MAXR];     // Máximo (evitar) o Solicitud (detectar)
static int alloc[MAXP][MAXR];
static int detect;              // 1 si el archivo trae `solicitud`

static int nreq;
static int req_p[MAXREQ];
static int req_v[MAXREQ][MAXR];

static FILE *in;
static int line = 1;

static void fail(const char *msg, const char *tok) {
    fprintf(stderr, "línea %d: %s%s%s\n", line, msg, tok ? ": " : "", tok ? tok : "");
    exit(1);
}

// Siguiente palabra del archivo, o NULL al final. Salta comentarios.
static char *word(void) {
    static char buf[64];
    int c, n = 0;
    for (;;) {
        c = getc(in);
        if (c == '#')
            while (c != '\n' && c != EOF)
                c = getc(in);
        if (c == '\n')
            line++;
        if (c == EOF)
            return NULL;
        if (c != ' ' && c != '\t' && c != '\n' && c != '\r')
            break;
    }
    while (c != EOF && c != ' ' && c != '\t' && c != '\n' && c != '\r' && c != '#') {
        if (n < (int)sizeof buf - 1)
            buf[n++] = c;
        c = getc(in);
    }
    if (c != EOF)
        ungetc(c, in);
    buf[n] = '\0';
    return buf;
}

static int number(void) {
    char *w = word(), *end;
    if (w == NULL)
        fail("falta un número", NULL);
    long v = strtol(w, &end, 10);
    if (*end != '\0' || v < 0)
        fail("se esperaba un entero >= 0", w);
    return (int)v;
}

static void numbers(int *v) {
    for (int j = 0; j < nres; j++)
        v[j] = number();
}

static int find_proc(const char *name, int add) {
    for (int i = 0; i < nproc; i++)
        if (strcmp(proc[i], name) == 0)
            return i;
    if (!add)
        fail("proceso desconocido", name);
    if (nproc == MAXP)
        fail("demasiados procesos", name);
    snprintf(proc[nproc], NAMELEN, "%s", name);
    return nproc++;
}

static int keyword(const char *w) {
    return !strcmp(w, "recursos") || !strcmp(w, "disponible") ||
           !strcmp(w, "maximo") || !strcmp(w, "solicitud") ||
           !strcmp(w, "asignado") || !strcmp(w, "pide");
}

static void parse(void) {
    char *w = word();
    int (*rows)[MAXR] = NULL;   // sección de filas en curso
    while (w != NULL) {
        if (!strcmp(w, "recursos")) {
            while ((w = word()) != NULL && !keyword(w)) {
                if (nres == MAXR)
                    fail("demasiados recursos", w);
                snprintf(res[nres++], NAMELEN, "%s", w);
            }
            continue;
        }
        if (nres == 0)
            fail("la primera sección debe ser `recursos`", w);
        if (!strcmp(w, "disponible")) {
            numbers(avail);
            rows = NULL;
        } else if (!strcmp(w, "maximo") || !strcmp(w, "solicitud")) {
            detect = !strcmp(w, "solicitud");
            rows = max;
        } else if (!strcmp(w, "asignado")) {
            rows = alloc;
        } else if (!strcmp(w, "pide")) {
            if (nreq == MAXREQ)
                fail("demasiados pedidos", NULL);
            char *p = word();
            if (p == NULL)
                fail("falta el proceso del pedido", NULL);
            req_p[nreq] = find_proc(p, 0);
            numbers(req_v[nreq++]);
            rows = NULL;
        } else if (rows != NULL) {
            numbers(rows[find_proc(w, 1)]);
        } else {
            fail("palabra inesperada", w);
        }
        w = word();
    }
    if (nproc == 0)
        fail("no hay procesos", NULL);
}

static void vprint(const int *v) {
    for (int j = 0; j < nres; j++)
        printf("%s%d", j ? " " : "", v[j]);
}

static int leq(const int *a, const int *b) {
    for (int j = 0; j < nres; j++)
        if (a[j] > b[j])
            return 0;
    return 1;
}

// Necesidad (evitar) o Solicitud (detectar) del proceso i.
static void need(int i, int *v) {
    for (int j = 0; j < nres; j++)
        v[j] = detect ? max[i][j] : max[i][j] - alloc[i][j];
}

// El algoritmo de seguridad. Devuelve cuántos procesos terminan; deja en
// seq el orden y en finish quién terminó. Con verbose, muestra cada paso.
// `skip` (o -1) es un proceso que se considera ya abortado.
static int safety(int *seq, int *finish, int verbose, int skip) {
    int work[MAXR], n = 0, v[MAXR];
    memcpy(work, avail, sizeof work);
    for (int i = 0; i < nproc; i++)
        finish[i] = 0;
    if (skip >= 0) {
        finish[skip] = 1;
        for (int j = 0; j < nres; j++)
            work[j] += alloc[skip][j];
    }
    for (;;) {
        int found = -1;
        for (int i = 0; i < nproc && found < 0; i++) {
            need(i, v);
            if (!finish[i] && leq(v, work))
                found = i;
        }
        if (verbose) {
            printf("  trabajo ");
            vprint(work);
        }
        if (found < 0)
            break;
        if (verbose) {
            printf(": %s %s ", proc[found], detect ? "pide" : "necesita");
            need(found, v);
            vprint(v);
            printf(", cabe; termina y devuelve ");
            vprint(alloc[found]);
            printf("\n");
        }
        for (int j = 0; j < nres; j++)
            work[j] += alloc[found][j];
        finish[found] = 1;
        seq[n++] = found;
    }
    if (verbose) {
        int rest = 0;
        for (int i = 0; i < nproc; i++)
            rest += !finish[i] && i != skip;
        if (rest == 0) {
            printf(": todos terminaron");
        } else {
            printf(": %s cabe (", n > 0 ? "nadie más" : "nadie");
            for (int i = 0, k = 0; i < nproc; i++) {
                if (finish[i])
                    continue;
                need(i, v);
                printf("%s%s ", k++ ? ", " : "", proc[i]);
                vprint(v);
            }
            printf(")");
        }
        printf("\n");
    }
    return n;
}

// Imprime s y completa con espacios hasta w columnas (cuenta caracteres UTF-8).
static void cell(const char *s, int w) {
    int n = 0;
    for (const char *p = s; *p; p++)
        n += ((unsigned char)*p & 0xC0) != 0x80;
    printf("%s%*s", s, w > n ? w - n : 0, "");
}

static void vcell(const int *v, int w) {
    char buf[64];
    int n = 0;
    for (int j = 0; j < nres; j++)
        n += snprintf(buf + n, sizeof buf - n, "%s%d", j ? " " : "", v[j]);
    cell(buf, w);
}

static void print_state(void) {
    int total[MAXR], v[MAXR], w = 2 * nres + 3;
    if (w < 11)
        w = 11;
    for (int j = 0; j < nres; j++) {
        total[j] = avail[j];
        for (int i = 0; i < nproc; i++)
            total[j] += alloc[i][j];
    }
    printf("recursos:");
    for (int j = 0; j < nres; j++)
        printf(" %s", res[j]);
    printf("   total: ");
    vprint(total);
    printf("   disponible: ");
    vprint(avail);
    printf("\n");
    cell("proceso", 9);
    cell(detect ? "solicitud" : "máximo", w);
    if (detect)
        printf("asignado\n");
    else
        cell("asignado", w);
    printf("%s", detect ? "" : "necesidad\n");
    for (int i = 0; i < nproc; i++) {
        cell(proc[i], 9);
        vcell(max[i], w);
        if (detect)
            vprint(alloc[i]);
        else
            vcell(alloc[i], w);
        if (!detect) {
            need(i, v);
            vprint(v);
            if (!leq(alloc[i], max[i]) || !leq(max[i], total))
                printf("   (inválido: asignado > máximo o máximo > total)");
        }
        printf("\n");
    }
}

static void print_seq(const int *seq, int n) {
    for (int k = 0; k < n; k++)
        printf("%s%s", k ? " " : "", proc[seq[k]]);
}

static void avoid(void) {
    int seq[MAXP], finish[MAXP], v[MAXR];
    printf("\n¿es seguro?\n");
    int n = safety(seq, finish, 1, -1);
    if (n == nproc) {
        printf("estado seguro: ");
        print_seq(seq, n);
        printf("\n");
    } else {
        printf("estado inseguro\n");
    }

    for (int r = 0; r < nreq; r++) {
        int i = req_p[r], *q = req_v[r];
        printf("\npide %s ", proc[i]);
        vprint(q);
        printf("\n");
        need(i, v);
        if (!leq(q, v)) {
            printf("  pide más que su necesidad (");
            vprint(v);
            printf("): error, se rechaza\n");
            continue;
        }
        if (!leq(q, avail)) {
            printf("  no hay suficiente disponible (");
            vprint(avail);
            printf("): %s espera\n", proc[i]);
            continue;
        }
        // Simular que se concede.
        for (int j = 0; j < nres; j++) {
            avail[j] -= q[j];
            alloc[i][j] += q[j];
        }
        printf("  cabe en necesidad y disponible; si se concede, disponible = ");
        vprint(avail);
        printf("\n");
        n = safety(seq, finish, 1, -1);
        if (n == nproc) {
            printf("  seguro (");
            print_seq(seq, n);
            printf("): se concede\n");
        } else {
            printf("  inseguro: se niega; %s espera y el estado vuelve atrás\n", proc[i]);
            for (int j = 0; j < nres; j++) {
                avail[j] += q[j];
                alloc[i][j] -= q[j];
            }
        }
    }
}

static void detection(void) {
    int seq[MAXP], finish[MAXP], dead[MAXP], nd = 0;
    printf("\ndetección (solicitud en lugar de necesidad)\n");
    int n = safety(seq, finish, 1, -1);
    if (n == nproc) {
        printf("sin deadlock: ");
        print_seq(seq, n);
        printf(" pueden terminar en ese orden\n");
        return;
    }
    printf("deadlock:");
    for (int i = 0; i < nproc; i++)
        if (!finish[i]) {
            dead[nd++] = i;
            printf(" %s", proc[i]);
        }
    printf("\n\nrecuperación: abortar a uno solo\n");
    for (int k = 0; k < nd; k++) {
        int f2[MAXP], s2[MAXP];
        int m = safety(s2, f2, 0, dead[k]);
        printf("  abortar %s (libera ", proc[dead[k]]);
        vprint(alloc[dead[k]]);
        if (m == nproc - 1) {
            printf("): los demás terminan: ");
            print_seq(s2, m);
            printf("\n");
        } else {
            printf("): no basta, siguen bloqueados:");
            for (int i = 0; i < nproc; i++)
                if (!f2[i])
                    printf(" %s", proc[i]);
            printf("\n");
        }
    }
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "uso: %s ARCHIVO   (o - para la entrada estándar)\n", argv[0]);
        return 1;
    }
    in = strcmp(argv[1], "-") == 0 ? stdin : fopen(argv[1], "r");
    if (in == NULL) {
        perror(argv[1]);
        return 1;
    }
    parse();
    print_state();
    if (detect) {
        if (nreq > 0)
            fail("`pide` solo tiene sentido con `maximo`", NULL);
        detection();
    } else {
        avoid();
    }
    return 0;
}

// deadlock.c — dos hilos, dos mutex y cuatro formas de tomarlos.
//
// Uso: ./deadlock naive    [iter]   cada hilo toma los locks en orden opuesto
//      ./deadlock ordered  [iter]   orden total: primero el de menor dirección
//      ./deadlock global   [iter]   un lock global alrededor de la adquisición
//      ./deadlock trylock  [iter]   trylock; si falla, suelta todo y reintenta
//
// Cada hilo repite `iter` veces (por omisión 100000): tomar dos locks,
// sumar, soltar. Un hilo vigilante (watchdog) revisa el avance cada 0.5 s;
// si en 2 s nadie avanzó, imprime qué lock tiene y cuál espera cada hilo
// (el grafo de espera) y termina el programa con código 0.
#define _GNU_SOURCE
#include <pthread.h>
#include <sched.h>
#include <stdatomic.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

enum mode { NAIVE, ORDERED, GLOBAL, TRYLOCK };

static pthread_mutex_t A = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t B = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t prevention = PTHREAD_MUTEX_INITIALIZER;

static enum mode mode;
static long iters = 100000;
static long counter;                    // protegido por A y B
static atomic_long progress;            // avance total, para el watchdog
static atomic_long retries;             // reintentos del modo trylock
static atomic_int done;

// Para el diagnóstico: qué lock tiene y cuál espera cada hilo.
static atomic_int holds[2] = {-1, -1};
static atomic_int wants[2] = {-1, -1};

static const char *name(pthread_mutex_t *m) { return m == &A ? "A" : "B"; }
static int id(pthread_mutex_t *m) { return m == &A ? 0 : 1; }

// Tomar m registrando la espera (solo para el diagnóstico).
static void take(int t, pthread_mutex_t *m) {
    atomic_store(&wants[t], id(m));
    pthread_mutex_lock(m);
    atomic_store(&wants[t], -1);
}

static void lock_both(int t, pthread_mutex_t *first, pthread_mutex_t *second) {
    switch (mode) {
    case NAIVE:                         // posible espera circular
        take(t, first);
        atomic_store(&holds[t], id(first));
        take(t, second);
        break;
    case ORDERED:                       // rompe la espera circular
        if (first > second) {           // comparar direcciones
            pthread_mutex_t *tmp = first;
            first = second;
            second = tmp;
        }
        take(t, first);
        atomic_store(&holds[t], id(first));
        take(t, second);
        break;
    case GLOBAL:                        // rompe retener y esperar
        pthread_mutex_lock(&prevention);
        take(t, first);
        take(t, second);
        pthread_mutex_unlock(&prevention);
        break;
    case TRYLOCK:                       // rompe "sin expropiación"
        for (;;) {
            take(t, first);
            if (pthread_mutex_trylock(second) == 0)
                break;
            pthread_mutex_unlock(first);    // soltar lo que tengo
            atomic_fetch_add(&retries, 1);
            sched_yield();                  // ceder un poco
        }
        break;
    }
    atomic_store(&holds[t], -1);
}

static void *worker(void *arg) {
    int t = (int)(long)arg;
    // El hilo 0 pide A y luego B; el hilo 1, B y luego A.
    pthread_mutex_t *first = t == 0 ? &A : &B;
    pthread_mutex_t *second = t == 0 ? &B : &A;
    for (long i = 0; i < iters; i++) {
        lock_both(t, first, second);
        counter++;                      // sección crítica
        pthread_mutex_unlock(second);
        pthread_mutex_unlock(first);
        atomic_fetch_add(&progress, 1);
    }
    return NULL;
}

static double seconds(struct timespec a, struct timespec b) {
    return (b.tv_sec - a.tv_sec) + (b.tv_nsec - a.tv_nsec) / 1e9;
}

// Revisa el avance; si se detiene 2 s, describe el ciclo y termina.
static void *watchdog(void *arg) {
    (void)arg;
    long last = -1;
    int still = 0;
    while (!atomic_load(&done)) {
        usleep(500000);
        long now = atomic_load(&progress);
        still = (now == last) ? still + 1 : 0;
        last = now;
        if (still < 4)
            continue;
        printf("watchdog: 2 s sin avance (%ld de %ld vueltas)\n",
               now, 2 * iters);
        for (int t = 0; t < 2; t++) {
            int h = atomic_load(&holds[t]), w = atomic_load(&wants[t]);
            printf("  hilo %d: tiene %s, espera %s\n", t,
                   h < 0 ? "-" : (h == 0 ? "A" : "B"),
                   w < 0 ? "-" : (w == 0 ? "A" : "B"));
        }
        int h0 = atomic_load(&holds[0]), w0 = atomic_load(&wants[0]);
        int h1 = atomic_load(&holds[1]), w1 = atomic_load(&wants[1]);
        if (h0 >= 0 && h0 == w1 && h1 >= 0 && h1 == w0)
            printf("  ciclo: H0 -> %s -> H1 -> %s -> H0: deadlock\n",
                   name(w0 == 0 ? &A : &B), name(w1 == 0 ? &A : &B));
        else
            printf("  sin ciclo en el grafo de espera\n");
        fflush(stdout);
        exit(0);                        // el deadlock era lo que queríamos ver
    }
    return NULL;
}

int main(int argc, char *argv[]) {
    const char *modes[] = {"naive", "ordered", "global", "trylock"};
    if (argc < 2) {
        fprintf(stderr, "uso: %s naive|ordered|global|trylock [iter]\n", argv[0]);
        return 1;
    }
    int found = 0;
    for (int i = 0; i < 4; i++)
        if (strcmp(argv[1], modes[i]) == 0) {
            mode = (enum mode)i;
            found = 1;
        }
    if (!found) {
        fprintf(stderr, "modo desconocido: %s\n", argv[1]);
        return 1;
    }
    if (argc > 2)
        iters = atol(argv[2]);

    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    pthread_t th[2], wd;
    pthread_create(&wd, NULL, watchdog, NULL);
    for (long t = 0; t < 2; t++)
        pthread_create(&th[t], NULL, worker, (void *)t);
    for (int t = 0; t < 2; t++)
        pthread_join(th[t], NULL);
    clock_gettime(CLOCK_MONOTONIC, &t1);
    atomic_store(&done, 1);
    pthread_join(wd, NULL);

    printf("%s: counter = %ld de %ld en %.3f s", modes[mode], counter,
           2 * iters, seconds(t0, t1));
    if (mode == TRYLOCK)
        printf("\n  %ld reintentos", atomic_load(&retries));
    printf("\n");
    return 0;
}

# Ejemplo de detección de los apuntes (semana 12): en lugar de `maximo`,
# la sección `solicitud` dice qué pide cada proceso en este momento.
recursos   A B C
disponible 0 1 0

solicitud
P1  0 0 1
P2  0 0 1
P3  2 0 0
P4  0 1 0

asignado
P1  1 0 1
P2  0 1 0
P3  1 1 1
P4  1 0 0

// disksched.c — planificación de disco sobre una misma cola de pedidos.
//
// Uso: ./disksched            orden y costo de cada algoritmo
//      ./disksched detalle    además, el costo de cada pedido desde el inicio
//
// Compara FCFS, SSTF, SCAN, C-SCAN y SPTF con un modelo simple de disco:
//   pistas 0..99; el cabezal empieza en la pista START, subiendo
//   búsqueda(d)    = 0 si d = 0; si no, SEEK_BASE + SEEK_PER_TRACK * d  (ms)
//   rotación       = 10 000 RPM: una vuelta en 6 ms, 60 grados por ms
//   transferencia  = XFER ms por pedido
// Cada pedido es (pista, ángulo): el ángulo dice cuántos grados le faltan
// al sector para pasar bajo el cabezal en el instante 0.
// SCAN llega hasta la pista 99 y regresa. C-SCAN llega hasta la 99, vuelve a
// la 0 sin atender (ese viaje cuenta) y sigue subiendo.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NREQ 8
#define MAXTRACK 99
#define START 50
#define SEEK_BASE 0.5
#define SEEK_PER_TRACK 0.05
#define DEG_PER_MS 60.0
#define XFER 0.1

struct req {
    int track;
    double angle;
};

// La cola, en orden de llegada.
static const struct req queue[NREQ] = {
    {85, 300}, {20, 90}, {58, 330}, {93, 150},
    {41, 30}, {10, 240}, {67, 120}, {46, 200},
};

struct state {
    int track;      // pista actual del cabezal
    double t;       // tiempo actual (ms)
    int moved;      // pistas recorridas en total
};

static double seek_ms(int d) {
    d = abs(d);
    return d == 0 ? 0 : SEEK_BASE + SEEK_PER_TRACK * d;
}

// Espera rotacional si llegamos a la pista en el instante t.
static double rot_wait(double angle, double t) {
    double left = angle - DEG_PER_MS * t;
    left -= 360.0 * (long)(left / 360.0);
    if (left < 0)
        left += 360.0;
    return left / DEG_PER_MS;
}

// Mover el cabezal a una pista sin atender nada (fin de SCAN y C-SCAN).
static void move_to(struct state *s, int track) {
    s->t += seek_ms(track - s->track);
    s->moved += abs(track - s->track);
    s->track = track;
}

// Costo (ms) de atender r desde el estado s.
static double cost(const struct state *s, const struct req *r) {
    double seek = seek_ms(r->track - s->track);
    return seek + rot_wait(r->angle, s->t + seek) + XFER;
}

static void serve(struct state *s, const struct req *r) {
    double c = cost(s, r);
    s->moved += abs(r->track - s->track);
    s->track = r->track;
    s->t += c;
    printf(" %d", r->track);
}

static void finish(const struct state *s) {
    printf(" | %3d pistas, %5.2f ms\n", s->moved, s->t);
}

static void fcfs(void) {
    struct state s = {START, 0, 0};
    printf("FCFS   :");
    for (int i = 0; i < NREQ; i++)
        serve(&s, &queue[i]);
    finish(&s);
}

// Elegir el pendiente que minimiza la distancia (SSTF) o el tiempo (SPTF).
static void greedy(const char *name, int by_time) {
    struct state s = {START, 0, 0};
    int done[NREQ] = {0};
    printf("%-7s:", name);
    for (int k = 0; k < NREQ; k++) {
        int best = -1;
        double best_v = 1e9;
        for (int i = 0; i < NREQ; i++) {
            if (done[i])
                continue;
            double v = by_time ? cost(&s, &queue[i])
                               : abs(queue[i].track - s.track);
            if (v < best_v) {
                best_v = v;
                best = i;
            }
        }
        done[best] = 1;
        serve(&s, &queue[best]);
    }
    finish(&s);
}

static int by_track(const void *a, const void *b) {
    return ((const struct req *)a)->track - ((const struct req *)b)->track;
}

static void scan(int circular) {
    struct req sorted[NREQ];
    memcpy(sorted, queue, sizeof sorted);
    qsort(sorted, NREQ, sizeof sorted[0], by_track);
    struct state s = {START, 0, 0};
    printf("%-7s:", circular ? "C-SCAN" : "SCAN");
    for (int i = 0; i < NREQ; i++)          // subiendo
        if (sorted[i].track >= START)
            serve(&s, &sorted[i]);
    move_to(&s, MAXTRACK);                  // hasta el borde
    if (circular) {
        move_to(&s, 0);                     // regreso sin atender
        printf(" (99->0)");
        for (int i = 0; i < NREQ; i++)      // subiendo otra vez
            if (sorted[i].track < START)
                serve(&s, &sorted[i]);
    } else {
        for (int i = NREQ - 1; i >= 0; i--) // bajando
            if (sorted[i].track < START)
                serve(&s, &sorted[i]);
    }
    finish(&s);
}

// Primera decisión: cuánto cuesta cada pedido desde el estado inicial.
static void detail(void) {
    struct state s = {START, 0, 0};
    printf("desde la pista %d en t = 0:\n", START);
    for (int i = 0; i < NREQ; i++) {
        const struct req *r = &queue[i];
        double seek = seek_ms(r->track - s.track);
        double rot = rot_wait(r->angle, seek);
        printf("  pista %2d: %2d pistas, búsqueda %.2f + rotación %.2f"
               " + transf. %.1f = %.2f ms\n", r->track,
               abs(r->track - START), seek, rot, XFER, seek + rot + XFER);
    }
}

int main(int argc, char *argv[]) {
    printf("cola (pista/ángulo):");
    for (int i = 0; i < NREQ; i++)
        printf(" %d/%.0f", queue[i].track, queue[i].angle);
    printf("\ncabezal en la pista %d, subiendo\n", START);
    fcfs();
    greedy("SSTF", 0);
    scan(0);
    scan(1);
    greedy("SPTF", 1);
    if (argc > 1 && strcmp(argv[1], "detalle") == 0)
        detail();
    return 0;
}

// disktime.c — tiempo de E/S de un disco duro: aleatorio vs. secuencial.
//
// Uso: ./disktime                       compara los dos discos de la clase
//      ./disktime RPM SEEK_MS MB_S [KB] [MB_SEQ]
//                                       un disco a medida
//
// Modelo: T_E/S = T_búsqueda + T_rotación + T_transferencia
//   T_búsqueda   = búsqueda promedio del fabricante
//   T_rotación   = media vuelta, en promedio
//   T_transfer.  = tamaño / tasa máxima de transferencia
// E/S aleatoria: cada pedido de KB paga búsqueda + rotación.
// E/S secuencial: un solo pedido de MB_SEQ paga búsqueda + rotación una vez.
// Convención: 1 MB = 1000 KB y 1 KB = 1000 bytes (como los fabricantes).
#include <stdio.h>
#include <stdlib.h>

struct disk {
    const char *name;
    double rpm;
    double seek_ms;     // búsqueda promedio
    double rate_mb_s;   // transferencia máxima
};

struct result {
    double rot_ms, xfer_ms, tio_ms, rate_mb_s, iops;
};

// Tiempo y tasa para un pedido de `kb` kilobytes.
static struct result io_time(const struct disk *d, double kb) {
    struct result r;
    double rev_ms = 60.0 * 1000.0 / d->rpm;            // una vuelta
    r.rot_ms = rev_ms / 2.0;                           // media vuelta
    r.xfer_ms = kb / 1000.0 / d->rate_mb_s * 1000.0;   // KB -> MB -> ms
    r.tio_ms = d->seek_ms + r.rot_ms + r.xfer_ms;
    r.rate_mb_s = (kb / 1000.0) / (r.tio_ms / 1000.0);
    r.iops = 1000.0 / r.tio_ms;
    return r;
}

static void report(const struct disk *d, double kb, double seq_mb) {
    struct result rnd = io_time(d, kb);
    struct result seq = io_time(d, seq_mb * 1000.0);
    printf("%s: %.0f RPM, búsqueda %.1f ms, %.0f MB/s\n",
           d->name, d->rpm, d->seek_ms, d->rate_mb_s);
    printf("  vuelta %.2f ms, rotación promedio %.2f ms\n",
           2 * rnd.rot_ms, rnd.rot_ms);
    printf("  aleatorio %.0f KB:  T_E/S = %.1f + %.2f + %.3f = %.2f ms"
           "  -> %.0f E/S por s, %.2f MB/s\n",
           kb, d->seek_ms, rnd.rot_ms, rnd.xfer_ms, rnd.tio_ms, rnd.iops,
           rnd.rate_mb_s);
    printf("  secuencial %.0f MB: T_E/S = %.1f + %.2f + %.1f = %.1f ms"
           "  -> %.1f MB/s\n",
           seq_mb, d->seek_ms, seq.rot_ms, seq.xfer_ms, seq.tio_ms,
           seq.rate_mb_s);
    printf("  secuencial / aleatorio = %.0f veces\n\n",
           seq.rate_mb_s / rnd.rate_mb_s);
}

int main(int argc, char *argv[]) {
    if (argc >= 4) {
        struct disk d = {"disco", atof(argv[1]), atof(argv[2]), atof(argv[3])};
        double kb = argc > 4 ? atof(argv[4]) : 4;
        double mb = argc > 5 ? atof(argv[5]) : 100;
        if (d.rpm <= 0 || d.rate_mb_s <= 0 || kb <= 0 || mb <= 0) {
            fprintf(stderr, "valores inválidos\n");
            return 1;
        }
        report(&d, kb, mb);
        return 0;
    }
    if (argc != 1) {
        fprintf(stderr, "uso: %s [RPM SEEK_MS MB_S [KB] [MB_SEQ]]\n", argv[0]);
        return 1;
    }
    // Dos discos típicos: uno de servidor y uno de escritorio.
    struct disk server = {"Servidor", 10000, 4.5, 150};
    struct disk desktop = {"Escritorio", 7200, 9.0, 105};
    report(&server, 4, 100);
    report(&desktop, 4, 100);
    return 0;
}

// epollecho.c — servidor de eco con un ciclo de eventos (epoll), un solo hilo.
//
// Uso: ./epollecho serve [puerto]      servidor; probar con: nc 127.0.0.1 9000
//      ./epollecho test [clientes] [mensajes]
//
// En modo test el proceso abre el servidor en un puerto libre de 127.0.0.1 y
// crea con fork un cliente "lento" que se conecta y no envía nada durante
// 1 s, y luego `clientes` clientes (por omisión 50) que envían `mensajes`
// líneas cada uno (por omisión 20) y verifican el eco. El servidor atiende
// a todos sin bloquearse por el lento, y termina cuando se cierran todas
// las conexiones.
#define _GNU_SOURCE
#include <arpa/inet.h>
#include <errno.h>
#include <fcntl.h>
#include <netinet/in.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/epoll.h>
#include <sys/socket.h>
#include <sys/wait.h>
#include <time.h>
#include <unistd.h>

#define MAXEV 64
#define BUFSZ 4096

// Estado de una conexión. Con un hilo por cliente esto viviría en la pila
// del hilo; en un ciclo de eventos hay que guardarlo a mano.
struct conn {
    int fd;
    char buf[BUFSZ];  // datos leídos que falta devolver
    size_t len;       // cuántos bytes hay en buf
    size_t off;       // cuántos ya se escribieron
};

static void die(const char *msg) {
    perror(msg);
    exit(1);
}

static double now(void) {
    struct timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec + t.tv_nsec / 1e9;
}

static void set_nonblocking(int fd) {
    int flags = fcntl(fd, F_GETFL, 0);
    if (flags < 0 || fcntl(fd, F_SETFL, flags | O_NONBLOCK) < 0)
        die("fcntl");
}

static int listen_on(int port) {
    int s = socket(AF_INET, SOCK_STREAM, 0);
    if (s < 0)
        die("socket");
    int one = 1;
    setsockopt(s, SOL_SOCKET, SO_REUSEADDR, &one, sizeof one);
    struct sockaddr_in a = {.sin_family = AF_INET, .sin_port = htons(port)};
    a.sin_addr.s_addr = htonl(INADDR_LOOPBACK);
    if (bind(s, (struct sockaddr *)&a, sizeof a) < 0)
        die("bind");
    if (listen(s, 128) < 0)
        die("listen");
    set_nonblocking(s);
    return s;
}

// Cambiar lo que nos interesa de una conexión: leer o escribir.
static void watch(int ep, struct conn *c, unsigned events) {
    struct epoll_event ev = {.events = events, .data.ptr = c};
    if (epoll_ctl(ep, EPOLL_CTL_MOD, c->fd, &ev) < 0)
        die("epoll_ctl MOD");
}

// Escribir lo pendiente. Devuelve 1 si terminó, 0 si falta, -1 si error.
static int flush(struct conn *c) {
    while (c->off < c->len) {
        ssize_t n = write(c->fd, c->buf + c->off, c->len - c->off);
        if (n < 0 && errno == EAGAIN)
            return 0;               // el socket está lleno: seguir luego
        if (n < 0)
            return -1;
        c->off += n;
    }
    c->len = c->off = 0;
    return 1;
}

// Estadísticas del servidor.
static long waits, accepted, closed, bytes, max_ready;

// El ciclo de eventos. Si `limit` > 0, termina al cerrarse `limit` conexiones.
static void serve(int ls, long limit, long report_at) {
    int ep = epoll_create1(0);
    if (ep < 0)
        die("epoll_create1");
    struct epoll_event ev = {.events = EPOLLIN, .data.ptr = NULL};
    if (epoll_ctl(ep, EPOLL_CTL_ADD, ls, &ev) < 0)  // NULL: el socket de escucha
        die("epoll_ctl ADD");

    double t0 = now();
    struct epoll_event ready[MAXEV];
    while (limit == 0 || closed < limit) {
        int n = epoll_wait(ep, ready, MAXEV, -1);   // única espera del programa
        if (n < 0 && errno == EINTR)
            continue;
        if (n < 0)
            die("epoll_wait");
        waits++;
        if (n > max_ready)
            max_ready = n;
        for (int i = 0; i < n; i++) {
            struct conn *c = ready[i].data.ptr;
            if (c == NULL) {                        // conexiones nuevas
                int fd;
                while ((fd = accept(ls, NULL, NULL)) >= 0) {
                    set_nonblocking(fd);
                    c = calloc(1, sizeof *c);
                    c->fd = fd;
                    struct epoll_event e = {.events = EPOLLIN, .data.ptr = c};
                    if (epoll_ctl(ep, EPOLL_CTL_ADD, fd, &e) < 0)
                        die("epoll_ctl ADD");
                    accepted++;
                }
                continue;
            }
            int r = 1;
            if (ready[i].events & EPOLLOUT) {       // terminar lo pendiente
                r = flush(c);
                if (r == 1)
                    watch(ep, c, EPOLLIN);
            } else if (ready[i].events & (EPOLLIN | EPOLLHUP | EPOLLERR)) {
                ssize_t got = read(c->fd, c->buf, BUFSZ);
                if (got < 0 && errno == EAGAIN)
                    continue;                       // falsa alarma
                if (got <= 0) {
                    r = -1;                         // el cliente cerró
                } else {
                    bytes += got;
                    c->len = got;
                    r = flush(c);
                    if (r == 0)                     // escritura parcial
                        watch(ep, c, EPOLLOUT);
                }
            }
            if (r < 0) {
                close(c->fd);                       // también lo saca de epoll
                free(c);
                closed++;
                if (closed == report_at)
                    printf("servidor: %ld conexiones atendidas en %.3f s; "
                           "%ld sigue abierta sin enviar nada\n",
                           closed, now() - t0, accepted - closed);
            }
        }
    }
    close(ep);
}

static int connect_to(int port) {
    int s = socket(AF_INET, SOCK_STREAM, 0);
    struct sockaddr_in a = {.sin_family = AF_INET, .sin_port = htons(port)};
    a.sin_addr.s_addr = htonl(INADDR_LOOPBACK);
    if (s < 0 || connect(s, (struct sockaddr *)&a, sizeof a) < 0)
        die("connect");
    return s;
}

// Enviar una línea y esperar el mismo texto de vuelta (cliente bloqueante).
static int echo_once(int s, const char *msg) {
    size_t len = strlen(msg), got = 0;
    char back[256];
    if (write(s, msg, len) != (ssize_t)len)
        return -1;
    while (got < len) {
        ssize_t n = read(s, back + got, len - got);
        if (n <= 0)
            return -1;
        got += n;
    }
    return memcmp(msg, back, len) == 0 ? 0 : -1;
}

static void client(int port, int id, int msgs, int slow) {
    int s = connect_to(port);
    char msg[128];
    if (slow) {
        sleep(1);                   // conectado, pero sin enviar nada
        snprintf(msg, sizeof msg, "cliente lento: por fin escribo\n");
        _exit(echo_once(s, msg) == 0 ? 0 : 1);
    }
    for (int i = 0; i < msgs; i++) {
        snprintf(msg, sizeof msg, "cliente %d, mensaje %d\n", id, i);
        if (echo_once(s, msg) < 0)
            _exit(1);
    }
    close(s);
    _exit(0);
}

int main(int argc, char *argv[]) {
    if (argc >= 2 && strcmp(argv[1], "serve") == 0) {
        int port = argc > 2 ? atoi(argv[2]) : 9000;
        int ls = listen_on(port);
        printf("servidor de eco en 127.0.0.1:%d (Ctrl-C para salir)\n", port);
        fflush(stdout);
        serve(ls, 0, -1);
        return 0;
    }
    if (argc < 2 || strcmp(argv[1], "test") != 0) {
        fprintf(stderr, "uso: %s serve [puerto] | test [clientes] [mensajes]\n",
                argv[0]);
        return 1;
    }
    int nclients = argc > 2 ? atoi(argv[2]) : 50;
    int msgs = argc > 3 ? atoi(argv[3]) : 20;

    int ls = listen_on(0);                          // 0: puerto libre
    struct sockaddr_in a;
    socklen_t alen = sizeof a;
    getsockname(ls, (struct sockaddr *)&a, &alen);
    int port = ntohs(a.sin_port);
    printf("servidor: puerto %d, 1 cliente lento + %d clientes x %d mensajes\n",
           port, nclients, msgs);
    fflush(stdout);

    if (fork() == 0)
        client(port, -1, 0, 1);                     // el lento, primero
    for (int i = 0; i < nclients; i++)
        if (fork() == 0)
            client(port, i, msgs, 0);

    serve(ls, nclients + 1, nclients);

    int ok = 0, status;
    while (wait(&status) > 0)
        if (WIFEXITED(status) && WEXITSTATUS(status) == 0)
            ok++;
    printf("servidor: %ld conexiones, %ld bytes, %ld llamadas a epoll_wait "
           "(hasta %ld fd listos a la vez)\n",
           accepted, bytes, waits, max_ready);
    printf("clientes: %d de %d recibieron su eco completo\n", ok, nclients + 1);
    return ok == nclients + 1 ? 0 : 1;
}