// cfs.c — la idea central de CFS: correr siempre al de menor vruntime.
//
// Uso: ./cfs <ms> <nice1> <nice2> ...
// Ejemplo: ./cfs 30 0 5
//
// Cada trabajo acumula vruntime = tiempo real * 1024 / peso. El peso sale de
// la tabla de Linux (sched_prio_to_weight en kernel/sched/core.c). Un trabajo
// con más peso acumula vruntime más despacio y por eso corre más.
// Simplificación: quantum fijo de 1 ms y búsqueda lineal (Linux usa un árbol
// rojo-negro y slices variables).
#include <stdio.h>
#include <stdlib.h>

#define MAX_JOBS 8

// Pesos de Linux para nice -20 .. 19 (nice 0 = 1024).
static const int prio_to_weight[40] = {
    88761, 71755, 56483, 46273, 36291, 29154, 23254, 18705, 14949, 11916,
    9548,  7620,  6100,  4904,  3906,  3121,  2501,  1991,  1586,  1277,
    1024,  820,   655,   526,   423,   335,   272,   215,   172,   137,
    110,   87,    70,    56,    45,    36,    29,    23,    18,    15,
};

struct job {
    char name;
    int nice;
    int weight;
    double vruntime;  // en ms "virtuales"
    int ran;          // ms reales de CPU
};

int main(int argc, char *argv[]) {
    if (argc < 3 || argc - 2 > MAX_JOBS) {
        fprintf(stderr, "uso: %s <ms> <nice>...\n", argv[0]);
        return 1;
    }
    int ms = atoi(argv[1]);
    int n = argc - 2;
    struct job jobs[MAX_JOBS];
    long total_weight = 0;
    for (int i = 0; i < n; i++) {
        int nice = atoi(argv[2 + i]);
        if (nice < -20 || nice > 19) {
            fprintf(stderr, "nice debe estar entre -20 y 19\n");
            return 1;
        }
        jobs[i] = (struct job){'A' + i, nice, prio_to_weight[nice + 20], 0.0, 0};
        total_weight += jobs[i].weight;
    }

    for (int t = 0; t < ms; t++) {
        int best = 0;
        for (int i = 1; i < n; i++)
            if (jobs[i].vruntime < jobs[best].vruntime)
                best = i;
        jobs[best].ran++;
        jobs[best].vruntime += 1.0 * 1024 / jobs[best].weight;
        if (t < 12) {
            printf("ms %2d: corre %c   vruntime:", t + 1, jobs[best].name);
            for (int i = 0; i < n; i++)
                printf("  %c=%.2f", jobs[i].name, jobs[i].vruntime);
            printf("\n");
        }
    }

    printf("\ntrabajo  nice   peso  esperado  obtenido\n");
    for (int i = 0; i < n; i++)
        printf("   %c     %3d  %5d    %5.1f%%    %5.1f%%\n", jobs[i].name, jobs[i].nice,
               jobs[i].weight, 100.0 * jobs[i].weight / total_weight,
               100.0 * jobs[i].ran / ms);
    return 0;
}

// fairness.c — ¿qué tan justa es la lotería en trabajos cortos?
//
// Uso: ./fairness [ensayos]
//
// Dos trabajos con los mismos boletos y la misma duración (en quanta).
// Injusticia U = (instante en que termina el primero) / (instante en que
// termina el segundo). U = 1 es perfectamente justo; U cercano a 0.5, muy
// injusto. Se compara la lotería (promedio de muchos ensayos) con stride.
#include <stdio.h>
#include <stdlib.h>

static unsigned int rng_state = 12345;

static unsigned int next_random(void) {
    unsigned int x = rng_state;
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    rng_state = x;
    return x;
}

// Lotería con dos trabajos de 1 boleto cada uno: cada quantum es una moneda.
static double lottery_unfairness(int len) {
    int left[2] = {len, len};
    int t = 0, first_done = 0;
    while (left[0] > 0 || left[1] > 0) {
        int w;
        if (left[0] == 0)
            w = 1;  // solo queda uno: gana siempre
        else if (left[1] == 0)
            w = 0;
        else
            w = next_random() % 2;
        left[w]--;
        t++;
        if (first_done == 0 && left[w] == 0)
            first_done = t;
    }
    return (double)first_done / t;
}

// Stride con dos trabajos iguales: se alternan, A B A B ...
static double stride_unfairness(int len) {
    int pass[2] = {0, 0};
    int left[2] = {len, len};
    int t = 0, first_done = 0;
    while (left[0] > 0 || left[1] > 0) {
        int w;
        if (left[0] == 0)
            w = 1;
        else if (left[1] == 0)
            w = 0;
        else
            w = (pass[1] < pass[0]) ? 1 : 0;
        pass[w] += 100;  // mismo stride para los dos
        left[w]--;
        t++;
        if (first_done == 0 && left[w] == 0)
            first_done = t;
    }
    return (double)first_done / t;
}

int main(int argc, char *argv[]) {
    int trials = (argc > 1) ? atoi(argv[1]) : 1000;
    int lens[] = {1, 2, 5, 10, 20, 50, 100, 1000};
    int nlens = sizeof(lens) / sizeof(lens[0]);

    printf("duración   U lotería   U stride\n");
    for (int i = 0; i < nlens; i++) {
        double sum = 0;
        for (int k = 0; k < trials; k++)
            sum += lottery_unfairness(lens[i]);
        printf("%6d       %.3f       %.3f\n", lens[i], sum / trials,
               stride_unfairness(lens[i]));
    }
    return 0;
}

// falseshare.c — el costo de la coherencia de caché (false sharing).
//
// Uso: ./falseshare [millones de iteraciones]
//
// Dos hilos incrementan cada uno SU PROPIO contador: no comparten datos.
// Si los dos contadores están en la misma línea de caché (64 bytes), cada
// escritura invalida la copia del otro CPU y la línea "rebota" entre cachés.
// Con relleno (padding), cada contador vive en su propia línea.
// Se usa una suma atómica (como un contador compartido real): obliga a cada
// CPU a tener la línea en exclusiva en cada incremento.
#define _GNU_SOURCE
#include <pthread.h>
#include <sched.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>

#define LINE 64
#define ALIGNED __attribute__((aligned(LINE)))

// Juntos: dos long seguidos, en la misma línea.
static struct {
    long a;
    long b;
} ALIGNED together;

// Separados: cada contador ocupa una línea completa.
static struct {
    long a;
    char pad[LINE - sizeof(long)];
    long b;
} ALIGNED apart;

struct arg {
    long *counter;
    long iters;
    int cpu;
};

static void *worker(void *p) {
    struct arg *a = p;
    // Fijar el hilo a un CPU (afinidad), para que sean dos cachés distintas.
    cpu_set_t set;
    CPU_ZERO(&set);
    CPU_SET(a->cpu, &set);
    pthread_setaffinity_np(pthread_self(), sizeof(set), &set);
    for (long i = 0; i < a->iters; i++)
        __atomic_fetch_add(a->counter, 1, __ATOMIC_RELAXED);
    return NULL;
}

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

static double run(long *x, long *y, long iters) {
    pthread_t t1, t2;
    struct arg a1 = {x, iters, 0}, a2 = {y, iters, 1};
    double t0 = now();
    pthread_create(&t1, NULL, worker, &a1);
    pthread_create(&t2, NULL, worker, &a2);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    return now() - t0;
}

int main(int argc, char *argv[]) {
    long iters = (argc > 1 ? atol(argv[1]) : 100) * 1000000L;
    if (sysconf(_SC_NPROCESSORS_ONLN) < 2) {
        fprintf(stderr, "se necesitan al menos 2 CPUs\n");
        return 1;
    }
    printf("distancia entre contadores: juntos %ld bytes, separados %ld bytes\n",
           (long)((char *)&together.b - (char *)&together.a),
           (long)((char *)&apart.b - (char *)&apart.a));

    double t_together = run(&together.a, &together.b, iters);
    double t_apart = run(&apart.a, &apart.b, iters);

    printf("misma línea:      %.3f s\n", t_together);
    printf("líneas distintas: %.3f s\n", t_apart);
    printf("relación:         %.1fx\n", t_together / t_apart);
    return 0;
}

// lottery.c — planificación por lotería con una lista de trabajos.
//
// Uso: ./lottery <semilla> <quanta> <boletos1> <boletos2> ...
// Ejemplo: ./lottery 7 20 100 50
//
// En cada quantum se sortea un número entre 0 y el total de boletos - 1, y se
// recorre la lista sumando boletos hasta pasar el número: ese trabajo gana.
#include <stdio.h>
#include <stdlib.h>

#define MAX_JOBS 8
#define SHOW 20  // cuántos sorteos mostrar uno por uno

struct job {
    char name;
    int tickets;
    int wins;
};

// Generador pseudoaleatorio simple (xorshift32): mismo resultado en
// cualquier máquina para la misma semilla.
static unsigned int rng_state;

static unsigned int next_random(void) {
    unsigned int x = rng_state;
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    rng_state = x;
    return x;
}

// Recorre la lista sumando boletos hasta pasar al ganador: O(n).
static int pick_winner(struct job *jobs, int n, int winner) {
    int counter = 0;
    for (int i = 0; i < n; i++) {
        counter += jobs[i].tickets;
        if (counter > winner)
            return i;
    }
    return n - 1;  // no debería pasar
}

int main(int argc, char *argv[]) {
    if (argc < 4 || argc - 3 > MAX_JOBS) {
        fprintf(stderr, "uso: %s <semilla> <quanta> <boletos>...\n", argv[0]);
        return 1;
    }
    rng_state = (unsigned int)atoi(argv[1]);
    if (rng_state == 0)
        rng_state = 1;  // xorshift no admite estado 0
    int quanta = atoi(argv[2]);
    int n = argc - 3;

    struct job jobs[MAX_JOBS];
    int total = 0;
    for (int i = 0; i < n; i++) {
        jobs[i].name = 'A' + i;
        jobs[i].tickets = atoi(argv[3 + i]);
        jobs[i].wins = 0;
        total += jobs[i].tickets;
    }

    for (int q = 0; q < quanta; q++) {
        int ticket = next_random() % total;  // el boleto sorteado
        int w = pick_winner(jobs, n, ticket);
        jobs[w].wins++;
        if (q < SHOW)
            printf("quantum %2d: boleto %3d -> %c\n", q + 1, ticket, jobs[w].name);
    }
    if (quanta > SHOW)
        printf("... (%d quanta más)\n", quanta - SHOW);

    printf("\n  boletos  esperado  obtenido\n");
    for (int i = 0; i < n; i++)
        printf("%c %7d  %7.1f%%  %7.1f%%\n", jobs[i].name, jobs[i].tickets,
               100.0 * jobs[i].tickets / total, 100.0 * jobs[i].wins / quanta);
    return 0;
}

// pin.c — ¿en qué CPU corre un proceso? Afinidad con sched_setaffinity.
//
// Uso: ./pin          (el kernel elige el CPU)
//      ./pin <cpu>    (fija el proceso a ese CPU)
//
// Muestrea sched_getcpu() durante un trabajo de CPU con varios hilos
// compitiendo y cuenta las migraciones (cambios de CPU).
#define _GNU_SOURCE
#include <pthread.h>
#include <sched.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>

#define SAMPLES 2000

static volatile int stop = 0;

// Hilos de relleno: mantienen ocupados a los demás CPUs.
static void *burn(void *arg) {
    (void)arg;
    while (!stop)
        ;
    return NULL;
}

static void spin_us(long us) {
    struct timespec t0, t;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    do {
        clock_gettime(CLOCK_MONOTONIC, &t);
    } while ((t.tv_sec - t0.tv_sec) * 1000000L + (t.tv_nsec - t0.tv_nsec) / 1000 < us);
}

int main(int argc, char *argv[]) {
    long ncpu = sysconf(_SC_NPROCESSORS_ONLN);
    if (argc > 1) {
        int cpu = atoi(argv[1]);
        cpu_set_t set;
        CPU_ZERO(&set);
        CPU_SET(cpu, &set);
        if (sched_setaffinity(0, sizeof(set), &set) < 0) {
            perror("sched_setaffinity");
            return 1;
        }
        printf("fijado al CPU %d\n", cpu);
    }

    // El doble de hilos de relleno que CPUs: hay más trabajo que CPUs.
    // Se crean después de fijar la afinidad, así que la heredan.
    pthread_t th[64];
    int nth = 2 * ncpu < 64 ? 2 * (int)ncpu : 64;
    for (int i = 0; i < nth; i++)
        pthread_create(&th[i], NULL, burn, NULL);

    int seen[1024] = {0};
    int last = -1, migrations = 0;
    for (int i = 0; i < SAMPLES; i++) {
        spin_us(500);
        int c = sched_getcpu();
        if (c >= 0 && c < 1024)
            seen[c] = 1;
        if (last != -1 && c != last)
            migrations++;
        last = c;
    }
    stop = 1;
    for (int i = 0; i < nth; i++)
        pthread_join(th[i], NULL);

    printf("CPUs en línea: %ld\nCPUs usados:", ncpu);
    for (int c = 0; c < 1024; c++)
        if (seen[c])
            printf(" %d", c);
    printf("\nmigraciones en %d muestras: %d\n", SAMPLES, migrations);
    return 0;
}

// stride.c — planificación por stride, paso a paso.
//
// Uso: ./stride <L> <quanta> <boletos1> <boletos2> ...
// Ejemplo: ./stride 60 6 3 2 1
//
// Cada trabajo tiene stride = L / boletos y un contador pass que empieza en 0.
// En cada quantum corre el trabajo con menor pass (en empate, el de menor
// índice) y su pass aumenta en su stride.
#include <stdio.h>
#include <stdlib.h>

#define MAX_JOBS 8

struct job {
    char name;
    int tickets;
    int stride;
    int pass;
    int runs;
};

int main(int argc, char *argv[]) {
    if (argc < 4 || argc - 3 > MAX_JOBS) {
        fprintf(stderr, "uso: %s <L> <quanta> <boletos>...\n", argv[0]);
        return 1;
    }
    int big = atoi(argv[1]);
    int quanta = atoi(argv[2]);
    int n = argc - 3;

    struct job jobs[MAX_JOBS];
    for (int i = 0; i < n; i++) {
        jobs[i].name = 'A' + i;
        jobs[i].tickets = atoi(argv[3 + i]);
        if (jobs[i].tickets <= 0) {
            fprintf(stderr, "los boletos deben ser positivos\n");
            return 1;
        }
        jobs[i].stride = big / jobs[i].tickets;
        jobs[i].pass = 0;
        jobs[i].runs = 0;
    }

    printf("stride:");
    for (int i = 0; i < n; i++)
        printf("  %c=%d", jobs[i].name, jobs[i].stride);
    printf("\n\npass al inicio de cada quantum:\nq  ");
    for (int i = 0; i < n; i++)
        printf("    %c   ", jobs[i].name);
    printf("corre\n");

    for (int q = 1; q <= quanta; q++) {
        // Elegir el menor pass (búsqueda lineal; una cola de prioridad en la práctica).
        int best = 0;
        for (int i = 1; i < n; i++)
            if (jobs[i].pass < jobs[best].pass)
                best = i;

        printf("%-3d", q);
        for (int i = 0; i < n; i++)
            printf(" %4d   ", jobs[i].pass);
        printf("%c\n", jobs[best].name);

        jobs[best].pass += jobs[best].stride;
        jobs[best].runs++;
    }

    printf("\nveces que corrió:");
    for (int i = 0; i < n; i++)
        printf("  %c=%d", jobs[i].name, jobs[i].runs);
    printf("\n");
    return 0;
}

diff --git a/Makefile b/Makefile
index a26f3db..0893966 100644
--- a/Makefile
+++ b/Makefile
@@ -151,6 +151,7 @@ UPROGS=\
 	$U/_forphan\
 	$U/_dorphan\
 	$U/_sync\
+	$U/_readcount\
 
 fs.img: mkfs/mkfs README $(UPROGS)
 	mkfs/mkfs fs.img README $(UPROGS)
diff --git a/kernel/syscall.c b/kernel/syscall.c
index 1800f20..45cd5e2 100644
--- a/kernel/syscall.c
+++ b/kernel/syscall.c
@@ -103,6 +103,7 @@ extern uint64 sys_link(void);
 extern uint64 sys_mkdir(void);
 extern uint64 sys_close(void);
 extern uint64 sys_sync(void);
+extern uint64 sys_getreadcount(void);
 
 // An array mapping syscall numbers from syscall.h
 // to the function that handles the system call.
@@ -130,6 +131,7 @@ static uint64 (*syscalls[])(void) = {
   [SYS_mkdir]   = sys_mkdir,
   [SYS_close]   = sys_close,
   [SYS_sync]    = sys_sync,
+  [SYS_getreadcount] = sys_getreadcount,
   // clang-format on
 };
 
diff --git a/kernel/syscall.h b/kernel/syscall.h
index 5a4a39f..b337d29 100644
--- a/kernel/syscall.h
+++ b/kernel/syscall.h
@@ -21,3 +21,4 @@
 #define SYS_mkdir  20
 #define SYS_close  21
 #define SYS_sync   22
+#define SYS_getreadcount 23
diff --git a/kernel/sysfile.c b/kernel/sysfile.c
index 7781287..7390195 100644
--- a/kernel/sysfile.c
+++ b/kernel/sysfile.c
@@ -65,6 +65,9 @@ sys_dup(void)
   return fd;
 }
 
+// Llamadas a read() desde el arranque.
+uint64 readcount = 0;
+
 uint64
 sys_read(void)
 {
@@ -72,6 +75,9 @@ sys_read(void)
   int n;
   uint64 p;
 
+  // Varios CPUs a la vez: suma atómica.
+  __atomic_fetch_add(&readcount, 1,
+                     __ATOMIC_RELAXED);
   argaddr(1, &p);
   argint(2, &n);
   if (argfd(0, 0, &f) < 0)
diff --git a/kernel/sysproc.c b/kernel/sysproc.c
index cd25557..3a9f5da 100644
--- a/kernel/sysproc.c
+++ b/kernel/sysproc.c
@@ -22,6 +22,15 @@ sys_getpid(void)
   return myproc()->pid;
 }
 
+extern uint64 readcount; // en kernel/sysfile.c
+
+uint64
+sys_getreadcount(void)
+{
+  // Un solo ld de 64 bits: no se corta.
+  return readcount;
+}
+
 uint64
 sys_fork(void)
 {
diff --git a/user/readcount.c b/user/readcount.c
new file mode 100644
index 0000000..b775e6b
--- /dev/null
+++ b/user/readcount.c
@@ -0,0 +1,17 @@
+#include "kernel/types.h"
+#include "kernel/fcntl.h"
+#include "user/user.h"
+
+int
+main(void)
+{
+  char buf[64];
+  int before = getreadcount();
+  int fd = open("README", O_RDONLY);
+  while (read(fd, buf, sizeof(buf)) > 0)
+    ;
+  close(fd);
+  int after = getreadcount();
+  printf("antes %d, despues %d\n", before, after);
+  exit(0);
+}
diff --git a/user/user.h b/user/user.h
index 29aad59..501d3bb 100644
--- a/user/user.h
+++ b/user/user.h
@@ -25,6 +25,7 @@ char *sys_sbrk(int, int);
 int pause(int);
 int uptime(void);
 int sync(void);
+int getreadcount(void);
 
 // ulib.c
 int stat(const char *, struct stat *);
diff --git a/user/usys.pl b/user/usys.pl
index 4d054e8..f5d3cd7 100755
--- a/user/usys.pl
+++ b/user/usys.pl
@@ -43,3 +43,4 @@ entry("sbrk");
 entry("pause");
 entry("uptime");
 entry("sync");
+entry("getreadcount");

# Semana 4: lotería, stride, CFS y multiprocesadores.
# El parche de xv6 (xv6-getreadcount.patch) no se compila aquí: se aplica
# dentro de un clon de xv6-riscv con `git apply`.
CFLAGS = -Wall -Wextra -g
LDLIBS = -pthread
PROGS  = lottery stride fairness cfs falseshare pin

all: $(PROGS)

clean:
	rm -f $(PROGS)

.PHONY: all clean