Shell: Este es un proyecto de la asignatura Sistemas Operativos donde tuvimos que implementar un Shell para Linux, bastante completo, usando C.

Nuestro Shell teniene funcionalidades como multi-pipe, redirección de entrada y de salida, concatenación de comandos, posibilidad de poner procesos en background y foreground y un historial de comandos.

Para interpretar el comando de entrada se parsea y se almacena en una estructura de datos que permite ejecutar cada instrucción de la concatenación secuencialmente, y desacoplando el procesamiento de un "átomo" del comando, del procesamiento de los conectores "&&", "||", ";", "|". Los pipes y las redirecciones de entrada y salida las implementamos trabajando con la tabla de file descriptors y los métodos dup2 y pipe.

Los comandos se ejecutan usando nuevos procesos usando los métodos fork y execv. Hicimos un handler para SIGCHLD para cosechar los procesos terminados. Se necesita ejecutar los comandos en procesos separados para que el proceso raíz se quede manteniendo el estado de la ejecución, pues puede haber conjunto de comandos concatenados o incluso varios procesos ejecutandose en el background en el momento que se pidió el comando.

Para implementar los jobs y el foreground se utilizó una pila para almacenar los procesos en background, la cual se mantiene actualizada con el handler de SIGCHLD y el método waitpid con el flag WNOHANG, siempre teniendo cuidado con las condiciones de carrera que pueden ocurrir. La funcionalidad de enviar un método al foreground se implementó llamando waitpid con pid -1, de forma tal que se iban cosechando procesos hasta que se cosechase el proceso que fue enviado al foreground

El historial se implementó guardando en un archivo la información de los comandos que se iban ejecutando. El formato que diseñamos para esto consiste en siempre escribir el tamaño antes y después los datos es decir ({size}{value}{size}{value}). Size siempre es un unsigned int indicando el tamaño que ocupa su value correspondiente, de forma que se puede leer el archivo facilmente.

Más detalles de la implementación en el readme del proyecto

Web Server: Este es un proyecto de la asignatura de Sistemas Operativos, en el que tuvimos que diseñar e implementar un Servidor FTP solo usando C y funcionalidades del kernel de linux.

El objetivo principal de este proyecto era implementar un servidor que permita navegar por un conjunto de carpetas y descargar archivos usando un navegador. Para poder resolver este proyecto nos tuvimos que enfrentar a varios retos: el trabajo con sockets, el protocolo http, mucho trabajo con punteros, manejo de memoria y la paralelización de las funcionalidades.

El funcionamiento del servidor consiste en aceptar constantemente conexiones y crear un proceso a parte para atenderlas. Para poder terminar el servidor correctamente implementamos un handler de SIGINT y guardamos el pid de cada proceso creado para poder terminarlos enviando SIGKILL y cosecharlos, pues pueden estar ejecutando algo que demora, como la descarga de un archivo . El cliente puede hacer dos tipos de peticiones: cambiar de dirección o descargar un archivo y esta distinción se hace por un caracter en la url.

Una de las funcionalidades que nos pidieron fue implementar distintas formas de dar orden a los archivos que se muestran, nosotros implementamos 3: ordenar por nombre, ordenar por tamaño y ordenar por fecha de modificación. Quisimos que se pudieran agregar nuevos métodos de ordenación con facilidad, por lo que intentamos desacoplar esta parte del código lo más posible del resto. La mejor manera que encontramos de lograr esto fue que cada método de ordenación fuera un programa que que recibiera la dirección como parámetro y que respondiera el correspondiente respuesta http con el código html. Para poder facilitar esto creamos un conjunto de funcionalidades para generar el diseño de la ventana en html y enviarlo usando el protocolo http. También implementamos un sort que recibe un delegado con el criterio de comparación. De esta forma solo hay que agregar un programa con el nuevo criterio de comparación y reutilizar los métodos que brindamos para crear y enviar la página.

Se hicieron structs para representar los http_request y http_response y los métodos correspondientes para parsear el request y serializar el response para enviarlo. Para leer eficientemente el request se usa un buffer para el cual se creó un struct y varios métodos para leer del socket, como un método remplazando el lseek y otro para leer hasta que se encuentre con cierto caracter. Los header se guardan en una linked list de pair key-values. En el caso de la respuesta, el comportamiento depende de si se quiere descargar un archivo o cambiar de directorio. Para enviar un archivo primero se construye un struct http_response con el request line y los header necesarios, para después de serializarlo y enviarlo, y después se empieza a enviar el archivo con el método sendfile. En el caso de cambiar de directorio se utilizan los métodos de ordenación que fueron comentados que fueron comentados anteriormente.

Skyrim: este es el proyecto correspondiente a la asignatura de Ingeniería de Software en el que tuvimos que diseñar una base de datos y una pagina web con la que se puedan recolectar datos de batallas ficticias en el juego y mostrar de manera atractiva varios insights a partir de los datos.

🚧Writting in progress ...🚧

3Models-SRI:Este es el proyecto correspondiente a la asignatura de Sistemas de Recuperación de Información donde tuvimos que estudiar e implementar dos modelos de recuperación de información que permitieran recomendar documentos de una colección a partir de una Query

🚧Writting in progress ...🚧

IFSL: Este es el proyecto correspondiente a la asignatura de Inteligencia Artificial. Utilizamos Inteligencia Artificial Clásica para desarrollar un simulador de batallas en el que un conjunto de agentes trabajaban en cooperativo para derrotar un enemigo.

El entorno del simulador consiste en una cuadrícula donde algunas casillas son obstáculos. Los agentes tienen características variables, como salud, daño, debilidad,rango de visión y velocidad(cantidad de turnos que necesita para avanzar una casilla). Para implementar el simulador desacoplamos el comportamiento del agente, del comportamiento del entorno, de forma tal que el agente "interactue" con el "entorno" y el "entorno" se encargue de comprobar si la interacción es válida, realizar los cambios en el estado y retornar la información para la retroalimentación del agente. Este simulador lo utilizamos para probar las capacidades de una IA para agentes cooperativos que desarrollamos usando IA clásica.

El problema de explorar el mapa es conocido como Coverage Path Planning. Para resolverlo utilizamos la descomposición de "Boustrophedon" del mapa y modelamos el problema como un Travelling Salesman Problem(TSP) en el grafo de las celdas adyacentes. Para encontrar una solución suficientemente buena utilizamos un algorítmo genético para TSP(Más info sobre la exploración aquí)

El movimiento cooperativo de los agentes presenta varios retos, como lograr que no se obstaculicen unos a otros y a la vez llegen en el menor tiempo posible. Para resolver este problema usamos una adaptación de A*, específicamente Windowed Hierachical Cooperative A* o WHCA*. La idea central es darle un orden de prioridad a los agentes y solo planificar con más exactitud tramos cortos(Más info sobre el movimiento cooperativo aquí)

Los agentes usan el movimiento cooperativo para formarse en un lugar pero estos pueden ocupar distintas posiciones en la formación. Para asignar posiciones convenientes diseñamos una función para aproximar cuantas interrupciones iban a tener los caminos óptimos de los agentes. Luego intentamos encontrar la asignación que hace esa métrica 0, modelandolo como un problema de Satisfacción de Restricciones(CSP) y en caso de que no exista intentamos encontrar una buena asignación usando con un algoritmo de Busqueda Local, Stocastic Hill Climbing.(Más info sobre asignación aquí)

Ya formados los agentes y encontrado el enemigo toca mover a la formación, alejándonos lo más posible de los obstáculos, para esto calculamos el Diagrama de Voronoi del mapa y nos movimos por los bordes de las celdas. Para el combate cooperativo generalmente se usa Aprendizaje Reforzado pero necesitabamos una solución con IA clásica por lo que usamos una adaptación de MiniMax(Más info sobre el combate cooperativo aquí)

FormationDSL: Este es el proyecto correspondiente a la asignatura de Compilación en el que se diseñamos un Domain Specific Language(DSL) e implementamos un transpilador de ese lenguaje a Python.

Nosotros decidimos crear un lenguaje Turing Completo que permitiera especificar rutinas de formaciones complejas. El transpilador luego generaría el correspondiente código en Python que usara los códigos del proyecto IFSL que acabábamos de terminar para hacer los cálculos y las animaciones.

Para permitirle al usuario crear formaciones con el nivel de complejidad que desée, hicimos que la declaración de formaciones tuviera la sintaxis de un método, en el que pueda pasar parámetros para que el usuario pueda tener mayor reusabilidad del mismo código. Además dentro de la declaración de la formación se pueden usar ciclos while, y condicionales, además de que también puede declarar variables del tipo int, bool, array, y group que es un tipo especial utilizado para referirse a conjuntos de agentes.

Crear nuestro propio lenguaje nos permitió añadir características específicas para el trabajo con groups, creando dinámicas más intuitivas y expresivas con los conjuntos de agentes. Dentro de la definición de una formación el usuario se puede referir a la variable especial G, la cual es el group que va a realizar la formación. Restrigimos la creación de variables de este tipo, de forma que en todo momento estas constituyecen una partición del group G original. También creamos operadores especiales para definir las posiciones relativas entre agentes como si fueran ordenes naturales como "down of" o "all_of G at down of prev".

Para poder compilar el lenguaje tuvimos que definir una gramática, la cual como era de esperar por su complejidad no pudo ser LL(1). Implementamos un tokenizer con expresiones regulares, un parser LR(1) y aprovechamos su recorrido bottom-up para ir construyendo el Abstract Sintax Tree(AST). Luego se usa el Patrón Visitor para realizar varios checkeos en el AST, como el checkeo de tipos, checkeo semántico y un checkeo para saber si las variables o funciones que se usan están definidas, y en el caso de las variables se tiene en cuenta el scope donde se llaman. Luego para facilitar la generación de código en Python se realizaron unas transformaciónes en el AST como, renombrar algunas funciones, declarar otras y reemplazar instrucciones como all_of por otras más cercanas a python. El código en python se generó recursivamente usando también el Patrón Visitor y un sistema de plantillas que implementamos usando el módulo de expresiones regulares de python.

Distributed Twitter: Este es el proyecto correspondiente a la asignatura de Sistemas Distribuidos en las que se nos pidió realizar una implementación de una versión simplificada de Twitter con las que se debería poder:

Era un requerimiento que las funcionalidades estén listas para un crecimiento de la demanda y la consecuente incorporación de recursos, además de ser capaz de seguir funcionando a pesar del fallo de una cantidad determinada de servidores. Por esta razón optamos por la replicación de servicios y por un almacenamiento distribuido basado en una Distributed Hash Table (DHT).

La arquitectura por la que optamos consistía en un conjunto de servidores que hacían de intermediarios entre el cliente y los servicios y otro conjunto que iban a mantener la DHT y la base de datos, los cuales se implementaron para funcionar en procesos separados para lograr un diseño más desacoplado.

Por motivos didácticos nuestro equipo decidió implementar todo sin ayuda de alguna librería externa que no sea la que utilizamos para consultar y modificar la base de datos local en SQLite pues no era objetivo del trabajo. Con este objetivo, a base de candados, diseñé para mi equipo un conjunto de clases que nos permitían tener un comportamiento parecido a el de una función callback que era totalmente independiente del contexto en el que era usado(Ver ThreadHolder y State Storage). Siguiendo con la idea de implementarlo todo a mano también hice un objeto que nos permitía a mí y a mis compañeros abstraernos del hecho de que todo se estaba ejecutando en multiples hilos y solo preocuparnos por la función que debía recibir el socket de la conexión a atender. El diseño de este objeto giraba en torno a una multiproducer-multiconsumer queue y nos permitía reutilizar los hilos cuando terminaban de atender a un cliente(Ver MultithreadedServer).

Ya con estas herramientas pude enfocarme en el desarrollo de la Distributed Hash Table que iba a encargarse de organizar en que servidor se debían almacenar que datos. Para su diseño me basé en la idea de Chord, pero realicé algunas modificaciones. Su función en el sistema era que el EntryServer le preguntaba a cualquiera de los servidores que estuviera participando en el almacenamiento distribuido por las direcciones IP de los servidores que debían responder por el dato que quería almacenar o consultar. También en el momento de incorporar una replica o un nuevo nodo en el almacenamiento distribuido la DHT jugaba un papel fundamental, pues en el caso de incorporar una replica, la esta se encargaba de encontrar las direcciones IP de las otras réplicas que contenían los datos de los nodos que querían replicar y en el caso de incorporar un nuevo nodo la DHT resolvía las direcciones de las replicas del nodo que iba a ser su sucesor (Ver Chord DHT)

Para poder probar todo de forma local utilizamos containers de Docker y es mi responsabilidad estudiarme esta herramienta, crear la imagen y un pequeño script para permitir a mis compañeros utilizarlo de manera sencilla.

DAA Solutions: 📖 En estos repos están las soluciones y los respectivos análisis de un conjunto de problemas que formaban parte del sistema de evaluación de la asignatura Diseño y Análisis de Algoritmos

• DAA-Solution: Este primer problema es de combinatoria. Para la creación de un tester se implementó un generador de casos y una solución con backtrack, que es menos eficiente pero al menos se conoce su correctitud con facilidad. Como parte del problema se analizó la complejidad y la correctitud de la solución con backtrack. La solución eficiente que se encontró fue hecha usando programación dinámica basada en propiedades de unas particiones en las que dividí en conjunto a contar. La explicación del problema, la solución y las demostraciones están en el readme del repo. (github renderiza mal las notaciones, pero otras herramientas como la extensión de MarkDown de VsCode lo muestra bien)
• DAA-Solution2: Este segundo problema es basado en grafos. Para resolverlo aprovechamos propiedades del recorrido que realiza el Algoritmo de Dijkstra para calcular ciertos valores correspondientes a cada vértice del grafo, para luego acumular los valores correspondientes a los vértices que cumplían cierta propiedad. Para testear los resultados se implementó un generador de grafos aleatorio y una solución que también usa el Algoritmo de Dijkstra pero se basa en una idea más intuitiva. La explicación del problema, la solución y las demostraciones están en el readme del repo.(github renderiza mal las notaciones, pero otras herramientas como la extensión de MarkDown de VsCode lo muestra bien)
• DAA-Solution3: El tercer problema consistía en demostrar la NP-Completitud de un problema de un problema de satisfacibilidad de expresiones booleanas, implementar un solver y encontrar alguna k-aproximación. La NP-Completitud se demostró reduciendo nuestro problema al 3-CNF-SAT. Para la solución de nuestro problema decidi usar una reducción conocida de SAT a 3-CNF-SAT para generar una expresión equissatisfacible a la original pero que se encuentra en 3ra forma normal conjuntiva y utilizar un solver que aprovecha esta forma. Para obtener esta expresión se tuvo que crear una gramática para expresiones booleanas e implementar un parser LL(1), pues se necesitaba el árbol de derivación de la expresión. Luego se implementaron 2 algoritmos y se demostró pq eran k-aproximaciones del problema de optimización asociado a nuestro problema. La explicación del problema, la solución y las demostraciones están en el readme del repo.(github renderiza mal las notaciones, pero otras herramientas como la extensión de MarkDown de VsCode lo muestra bien)