Cursus — Codexion pendiente

Concurrencia en C con hilos POSIX: varias personas programando comparten pocos dongles USB y tienen que compilar antes de agotarse. Es el proyecto de C del rank 03 de 42next y el heredero directo de Philosophers.

De dónde viene — En 1965 Edsger Dijkstra planteó a sus alumnos un ejercicio sobre cinco ordenadores que compiten por unidades de cinta, y Tony Hoare lo rebautizó como la cena de los filósofos: filósofos sentados en círculo, un tenedor entre cada dos, y cada uno necesita los dos de sus lados para comer. Es el ejemplo clásico de interbloqueo (todos cogen el tenedor izquierdo y se quedan esperando el derecho para siempre) y de inanición (alguien que nunca consigue los dos). En el camino antiguo de 42 esto era el proyecto Philosophers; en 42next se llama Codexion y cambia el disfraz: los filósofos son personas que programan, los tenedores son dongles USB, comer es compilar y morir de hambre es agotarse (burnout). Pero el enunciado añade tres cosas que Philosophers no tenía: un tiempo de enfriamiento de los dongles, un planificador que decide quién se lleva un dongle disputado (fifo o edf) y la obligación de programar tu propia cola de prioridad. Es decir, del «que no se bloquee» se pasa al «que además sea justo».

Qué pide

Rank: 03 Lenguaje: C Programa: codexion Entrega: Makefile, *.c, *.h en coders/ Libft: no Individual/grupo: no confirmado

Un único programa, codexion, que simula la mesa con un hilo por persona y un hilo monitor aparte, y escribe por la salida un log con marca de tiempo de cada cambio de estado. La simulación acaba cuando alguien se agota o cuando todo el mundo ha compilado al menos el número de veces pedido.

Las reglas generales son las de los proyectos de C de siempre: Norma, nada de segfaults ni double free, sin fugas de memoria, Makefile con $(NAME), all, clean, fclean y re que no haga relink, compilando con cc y -Wall -Wextra -Werror -pthread. Y una específica de este proyecto: las variables globales están prohibidas.

Funciones autorizadas: pthread_create, pthread_join, pthread_mutex_init, pthread_mutex_lock, pthread_mutex_unlock, pthread_mutex_destroy, pthread_cond_init, pthread_cond_wait, pthread_cond_timedwait, pthread_cond_broadcast, pthread_cond_destroy, gettimeofday, usleep, write, malloc, free, printf, fprintf, strcmp, strlen, atoi y memset. Fíjate en lo que no está: ni pthread_detach, ni pthread_cond_signal (solo broadcast), ni semáforos.

No hay parte bonus en el enunciado. Sí hay recode: en la evaluación pueden pedirte una modificación pequeña del proyecto en directo.

01El modelo: mesa, dongles y ciclo

Las personas se sientan en círculo, numeradas de 1 a number_of_coders; la 1 se sienta junto a la última y cada N entre N - 1 y N + 1. Hay tantos dongles como personas, uno entre cada dos, y para compilar hay que tener los dos de los lados a la vez. Si solo hay una persona, sobre la mesa hay un único dongle.

Cada persona repite el ciclo coger dos dongles → compilar → soltarlos → depurar → refactorizar y, al acabar de refactorizar, intenta enseguida volver a coger dongles. Los tres estados se excluyen entre sí. Las personas no se comunican y no saben si otra está a punto de agotarse.

Qué te obliga a aprender — A pensar en un recurso compartido como algo que hay que proteger. Dos hilos que leen y escriben a la vez el estado de un dongle pueden acabar creyendo los dos que lo tienen: el enunciado pide proteger el estado de cada dongle con su propio pthread_mutex_t precisamente «para evitar que se dupliquen dongles». Y el caso de una sola persona con un solo dongle es la trampa clásica de Philosophers: nunca podrá tener dos, así que la simulación tiene que acabar en burnout en lugar de quedarse colgada.

02Argumentos y logs

Ocho argumentos, todos obligatorios:

./codexion number_of_coders time_to_burnout time_to_compile time_to_debug \
           time_to_refactor number_of_compiles_required dongle_cooldown scheduler
ArgumentoSignificado (según el enunciado)
number_of_coderspersonas, y también dongles
time_to_burnoutms: si alguien no empieza a compilar en ese tiempo desde el inicio de su última compilación (o desde el inicio de la simulación), se agota
time_to_compilems compilando, con los dos dongles en la mano
time_to_debugms depurando
time_to_refactorms refactorizando
number_of_compiles_requiredsi todo el mundo llega a este número de compilaciones, la simulación se detiene
dongle_cooldownms que un dongle queda no disponible después de soltarlo
schedulerexactamente fifo o edf

Hay que rechazar las entradas no válidas: números negativos, valores que no sean enteros o un planificador distinto de esos dos.

Los únicos mensajes posibles son estos cinco, con el tiempo en milisegundos y el número de la persona:

timestamp_in_ms X has taken a dongle
timestamp_in_ms X is compiling
timestamp_in_ms X is debugging
timestamp_in_ms X is refactoring
timestamp_in_ms X burned out

Dos mensajes nunca pueden mezclarse en una línea, y el de burned out tiene que salir como mucho 10 ms después del momento real del agotamiento. El enunciado recomienda gettimeofday() para medir el tiempo.

Qué te obliga a aprender — Que el tiempo en un programa concurrente es resbaladizo. usleep(200000) no duerme exactamente 200 ms: duerme al menos eso, y luego el sistema operativo te devuelve la CPU cuando le parece. Con muchos hilos esos retrasos se acumulan, y es justo lo que puede hacer que el burnout se anuncie tarde. El margen de 10 ms es la versión medible de «tu programa reacciona a tiempo».

03Mutex, variables de condición y monitor

Lo que pide la parte obligatoria, punto por punto:

Una variable de condición es la forma de esperar «hasta que pase algo» sin estar preguntando en bucle (espera activa). El patrón general, que viene en cualquier manual de pthreads, es siempre el mismo: se espera dentro de un while que vuelve a comprobar la condición, porque al despertar no hay garantía de que siga cumpliéndose:

pthread_mutex_lock(&m);
while (!condicion)
    pthread_cond_wait(&c, &m);   /* suelta m, duerme, y lo recupera al despertar */
/* aquí condicion es cierta y tienes m */
pthread_mutex_unlock(&m);

pthread_cond_timedwait hace lo mismo pero con un tiempo límite, algo útil cuando además de esperar a un recurso tienes un reloj corriendo.

Qué te obliga a aprender — Las condiciones de Coffman (Edward Coffman y otros, 1971): un interbloqueo solo puede producirse si se dan a la vez exclusión mutua, retener y esperar, no expropiación y espera circular. Basta con romper una para que sea imposible, y el README te pide explicar cuál rompes y cómo. También las condiciones de carrera: el monitor lee la hora de la última compilación mientras el hilo de la persona la escribe, así que esa lectura también tiene que ir protegida. Y el problema contrario al interbloqueo: proteger demasiado, con un único mutex para todo, hace que los hilos se esperen entre sí y el programa vaya a trompicones.

04Cooldown y planificador: fifo y edf

Enfriamiento obligatorio. Cuando alguien suelta un dongle, nadie puede volver a cogerlo hasta que pasen dongle_cooldown milisegundos.

Arbitraje justo obligatorio. Si varias personas piden el mismo dongle, se concede según el planificador:

El enunciado exige que, con edf, nadie se agote siempre que los parámetros sean viables, y que la planificación se haga con una cola de prioridad (heap) programada por ti, porque C89 no trae ninguna en su biblioteca estándar.

Qué te obliga a aprender — Planificación de tiempo real. EDF es un algoritmo clásico (Liu y Layland, 1973): servir siempre primero a quien vence antes, y se demuestra óptimo en un procesador con expropiación para tareas con plazos. FIFO es la cola de toda la vida, justa en el orden de llegada pero ciega a la urgencia. La diferencia se ve en los casos apretados: con FIFO alguien que llegó tarde a la cola puede agotarse esperando a otros que iban sobrados de tiempo. Y el heap es la estructura que hace barato «dame el más urgente»: un árbol binario guardado en un array donde cada nodo es menor que sus hijos, con inserción y extracción en O(log n). Es el mismo tipo de estructura que usa el algoritmo de Dijkstra que aparece en Fly-in.

05El README obligatorio

Además de lo de siempre (primera línea en cursiva con los logins, secciones de Descripción, Instrucciones y Recursos con el uso de IA), este proyecto pide dos secciones más:

El idioma del README es libre (se recomienda inglés). La convención del usuario de tener un README en cada repo encaja aquí sin esfuerzo extra.

Puntos delicados

Fuente

El enunciado no está aún en el pack. Esta ficha sale de una transcripción pública del enunciado en castellano (versión 1.0), contrastada con los README de dos entregas de otros estudiantes, que coinciden en argumentos, mensajes, planificadores y cola de prioridad:

No confirmado: si se hace individual o en grupo, y las horas estimadas.