A cada grupo se le da un paper de USENIX por ejemplo, el cual tienen que leer (traducir?), entender, exponer y si dá, mostrar alguno de los resultados.

Me parece bueno respecto al “tema de investigacion” porque

• Tienen que entender algo si o si, no solo copiar y pegar de la web.
• Los fuerza a leer probablemente su primer paper.
• Los ayudantes que tomen ese grupo ya lo tienen leido y entendido y pueden guiarlos en la lectura.

Cons:

• Aburrido!!!, no hay hands-on.

• (flaco) Scheduler de caracteres
• (nico) Inspección del kernel con DTrace-like (SystemTap)
• (nico) ProjectOZ y Windows Operating System Internals Curriculum Resource Kit (CRK) de Microsoft, tengo CDs de un curso que dieron en UTN.
• (matias) Usar hilos de Java para aprender concurrencia.
• (nico?) Hacer algo con Fuse, por ejemplo FUSE Lab.

(nico) Resumen de una charla con MartínD

• Todos los alumnos entraron en 1 comisión en LabGrande! Notar que es la materia anterior a la nuestra. Dijo que todo funcionó muy bien respecto al año anterior, “terminamos antes”.
• Manejo de punteros, máximo alcanzado: hash abierto, AVL con listas ligadas de nodos.
• Herramientas de programación y depuración: asserts para representación de clase y algoritmo, ElectricFence para tener mejor reporte de errores de memoria runtime, Valgrind para 0-memory-leak.

Parece más que viable, ver reporte de Algoritmos2. Discutir el horario.

En algún momento van a usar el apunte de strings.

(julio) Los labs del año pasado fueron Baash, sincronización de threads, Kernel, el nuevo, y los de investigación. ¿Se mantendría esa estructura?

(nico) Copio la estructura acá abajo:

Creación, espera, muerte de procesos. Redirecciones. Parseo. Estructura de datos no trivial. División en módulos. Programación defensiva.

Detección, explicación y solución de problemas de concurrencia en hilos. Dos problemas: una “función” int→void* implementado con un arreglo, una “función” char*→char* implementada con un rbtree.

Un clásico. Sincro in-kernel. Exploración de todo el software stack a través de programas userspace y printk allá abajo.

A partir de trazas reales de malloc,realloc,free, implementar políticas para un alocador de bloques de tamaño fijo en un pool de memoria (firstfit, bestfit, etc.)

(julio) El año pasado se implementó el lab ¿4?, en el cual se trabajaba sobre el manejo de recursos, según recuerdo. Me parece que deberíamos replantearlo, porque me pareció que no fue fácil de comprender.

(pelado) Si van a repetir el práctico, estaría bueno pedirles que agreguen las políticas usando dlopen (como plugins…)

(rafa) Uy, bendita memoria mia que es un fiasco, me engañaron en la repartición, jej.
Recuerdo que habiamos tenido problemas porque no había cantidad ni calidad de trazas reales, creo que había 1 sola que la usábamos de a pedasos para simular otras trazas o que nunca la usábamos por completo. Estaría bueno hacer trazas “oficiales”(entregadas por SO) de algo que le propuso Beatriz ;) a algunos grupos que es hacer algunas a manopla, cortitas con resultados faciles de calcular a lapiz y papel. O hace un programillo simple que genere algunas trazas simples. Todo esto como para que los chicos puedan comprobar que están haciendo las cosas bien cuando están a mitad de camino.
Me acuerdo también que se hubo mucha incertidumbre porque las estadísticas que generaba el driver parecían “raras” y no había FORMA en el mundo de verificarlas en una traza gigante y stressing(para el software) como la que había.
También tuve problemas con mis grupos para exigirles que hicieran la política custom. Todo el mundo me venía con worst fit… o sea, no gastaban NI UN SEGUNDO en pensar si podían hacer algo mejor.

* Las trazas tienen una pinta que no se adapta bien a un memory manager que tienen páginas de tamaño fijo, ya que hay quichicientos pedidos de bloques pequeños. Eso lleva a que no haya tanta difierencia a la hora de medir fragmentación interna, externa.

Mmm, tal vez por esto las mediciones parecían raras.

* Se les dio tanto tanto código de soporte que lo que ellos tenían que codificar fue muy poco, ?una centena de líneas?

Si, la verdad que era muy pobre lo que tenían que escribir. Pero se compensaba por un lado porque tenían pinta de no entender NADA de lo que tenían que hacer… no sé… tampoco era tan difícil, no?
Si se quisiera darles más trabajo se les podría pedir que implementen ellos el bitmap, la tabla hash o el programa que parsea el trace, creo que cualquiera de los tres es fácil de hacer.

* Faltó darles la tarea de que ellos mismos extrajeran las trazas de varios programas para testear contra sus políticas y ver que los “patrones de uso” son salvajemente distintos.

Estaría bueno, aunque creo recordar que era medio bardo conseguirlas… Charly se habia puesto con eso, no?

  >(nico) Lab4, memory allocation se puede arreglar haciendo que implementen un [[http://en.wikipedia.org/wiki/Buddy_memory_allocation|Buddy Allocator]]. Lo que faltaría ver es si hay diferentes “políticas” de placement para luego medir fragmentación. Parece que algo hay [[http://lwn.net/Articles/126592/|aca]].
  >Otra posibilidad es manejar bloques fijos pero realmente chicos (una palabra?) como dice en este glosario acerca del [[http://www.memorymanagement.org/glossary/b.html#bitmapped.fit|bitmapped fit]]. ?Será terrible el overhead?
  >Probablemente hay que leer esto: Paul R. Wilson, Mark S. Johnstone, Michael Neely, David Boles. 1995. Dynamic Storage Allocation: A Survey and Critical Review. University of Texas at Austin. Abstract. [[http://www.cs.utexas.edu/users/oops/papers.html#allocsrv|Online]].

• Lab Grande: 40 puestos de trabajo, 80 sillas
  • 1/2 lab en XTerminal: 9 x P1@200+64MB (HP viejas), ? x P3@500+64MB (Fujitsu Kammerath)
  • 1/2 lab con login local: ? x P2*2@400+256MB (ex-cluster), ? x P3@500+128MB (HP nuevas)

• Lab Chico: 15 puestos de trabajo, 30 sillas
  • 15 x P4@?+512MB

(nico) Pichu se plantea upgradear todos los kernels (Debian?) a 2.6.x antes de empezar el cuatrimestre.

Horario Teórico: mie, vie 16 a 18 Lab: mie, vie 18 a 20

Daniel plantea armar un esqueleto de KSamp bien hecho (coding style, TADs, asserts, manejo de errores de llamados a bibliotecas), pero con algunas cosas mal hechas en todos estos aspectos, más el agregado de alguna funcionalidad que falta.

• Hacer Makefile.
• Completar cosas de coding style.
• Terminar de armar un TAD.
• Solucionar memory leaks y enredos con punteros.
• … mas cosas que el Dani completará …

> (nico) usar sysfs?

Entrega la semana que sigue, no tiene un gran peso en la nota final, y sirve de warm-up para lo que sigue. Intentamos aprovechar el tiempo de un Lab1 de 4 semanas donde la 1ra no se hace nada.

Cosas a solucionar:

• Apuntar a la generalidad en ; y |, pero ser superclaros y brindar una buena estructura de forma tal que si hacen ciegamente lo que les decimos, terminen con algo que digan “opa opa, funciona!”.

Idem como en la recursión: “pibe/a, supone que para n está resuelto, como resolves para n+1”.

Matías y alguien más trabajará en este nuevo Lab.

• Manejar una cola de hilos-listos y un pool de n hilos creados.
• Cuando hay lugar para ejecutar se saca de la readyQueue y se lo pone ahi.
• Manejar la concurrencia de la queue, notar que es un ProdCons con n consumidores (?fijos?) y k productores (potencialmente infinitos trabajos).
• Se puede plantear el tema de affinities, donde hay atributos en los ejecutores como en las tareas y tiene que haber matching.
• ?Política de crecimiento y decrecimiento de cantidad de ejecutores? Estaría bueno para empezar a presentar el tema de políticas.
• Explicar que todo esto es por el costo de crear hilos.
• Ademas de todo, que las tareas sean algo útil!!! microserver de http? o que al menos la llegada de las tareas sean una traza de algo real.

Bianco y Hames a cargo de subirlo a 2.6 (documentación, ejemplo de hello world, ejemplo de /dev/cero, scripts de carga descarga).

• Sacar, eliminar, destruir, todo rbuffer con bugs producidos por uso incorrecto de aritmética modular.

Nico a cargo de toquetear esto para que produzca resultados significativos.

• Fijar un tamaño de bloque chico (8 bytes?), mirar el tamaño del overhead.
• Plantearlo asi: dada una traza y una política, ?Cuál es la mínima cantidad de memoria que puede completar la traza?
• Revisar las estadísticas, en particular hay algún bug que Natalia reportó el año pasado.
• Que los mismos alumnos obtengan trazas y encuentren las 3 trazas que muestran que cada uno de los 3 algorimos son mejores, aka “no hay el mas-mejor”.
• Evitar el worst-fit, por ejemplo viendo que en la mayoría de las trazas es el peorcito, o en todo caso dejarlo como una posibilidad, pero que magoya encuentre la traza que muestra que es mejor.

Natalia apuntó a que las investigaciones del estilo “NTFS” apestan, Luis dijo que las investigaciones bibliográficas apestan. Entonces: generar nuevos proyectos que tengan cosas para probar.

Por ejemplo:

• El querido planificador programable Bossa.
• Parches del kernel donde se pueda mostrar algo Scheduler O(1), CFS (completely fair scheduler).
• Proyectos Fuse.
• Proyectos nackos, geekos-like.
• Algún FS, pero con instalación, experimentos, medidas de performance.
• Ya haremos la lista …
• (flaco) Para hacer threading: Threading Building Blocks

Poner acá abajo las propuestas con buen nivel de detalle asi hacemos copy&paste.

• ¿Es Linux es tan rápido como se publicita?
• ¿Es Windows tan pesado como se comenta?
• ¿Cuál es el SO más rápido?
• ¿Cuánta performance se pierde si cambiamos el foco del SO a la seguridad?

Este trabajo consiste en tratar de encontrar respuestas a este tipo de preguntas midiendo la performance de aplicaciones de uso común en PCs de escritorio o servidores corriendo Linux 2.6.22/23, FreeBSD 6.1-RELEASE/7.0-CURRENT, OpenBSD 4.1/4.2, Windows XP/Vista/2003 Server/2008 Server.

Los sistemas de archivos tienen diseños distintos según el uso que se les quiere dar. ¿Cómo afectan estas decisiones a la performance del sistema de archivos? Comparar la performance de filesystems para discos rígidos (ext3/4, reiserfs3/4, NTFS, XFS, JFS, ZFS), medios ópticos (ISO9660, UDF), memoria flash (LogFS, JFFS2, YAFFS) en distintos medios.

Los usuarios de DOS y Windows (en especial aquellos que no usan NTFS sobre NT, XP o Vista)saben por conocimiento popular que periodicamente hay que correr “defrag” para que la computadora ande “más rápido”. El proyecto consiste en validar y cuantificar estas nociones. Las tareas para hacer son:

• Armar un programa que lea un sistema de archivos FAT, lo analice, y den una métrica de su fragmentación.

• Construir programas de prueba para llenar de archivos un disco FAT vacío, que obtenga alta y baja fragmentación.

• Realizar un programa de benchmark de performance y correrlo sobre sistemas de archivos muy fragmentados y defragmentados, para obtener resultados comparativos. Correr estos benchmarks en distintos medios de almacenamiento (diskette, disco duro, y pendrive).

Un sistema operativo de escritorio moderno (en este trabajo, GNU/Linux) puede demorar más de un minuto desde que empieza a arrancar hasta que el usuario puede interactuar con las aplicaciones (por ej: la pantalla de login). En este intervalo de tiempo, hay múltiples esperas de disco (se leen cientos/miles de archivos), como también esperas de CPU (se inician muchos procesos, se configura hardware) o de red. Una forma de acelerar este proceso es, al principio del arranque, lanzar un proceso en paralelo que lea del disco los bloques que son necesarios por el proceso de arranque. Esto tiene un costo bajo en CPU, y reduce mucho las esperas de disco de los procesos iniciandose (se paraleliza la lectura a disco con otras tareas no atadas a disco del arranque). El trabajo incluye:

* Construir un mecanismo para registrar en un arranque normal la lista de bloques requeridos * Armar un programa que lea esta lista, e instalarlo al inicio del arranque de un sistema Linux * Medir cuanta mejora produce.

• Virtualización
  • Para qué sirve?
  • Comparación entre distintos modelos de virtualización.
  • lguest - permite ejecutar varias copias del mismo núcleo de 32-bits.
  • xen - monitor de máquina virtual.
  • qemu - un emulador y virtualizador de procesador.
  • (nicow) Debido a que las implementaciones de cada virtualizador tienen un approach muy diferente, armar programitas de ejemplo donde muestra las fortalezas y debilidades de cada uno en cuanto a performance

• Programación multihilos usando Threading Building Blocks: TBB es una biblioteca que ayuda a aprovechar el rendimiento de procesadores multinúcleo sin necesidad de ser un experto en hilos.
  • Introducción a TBB
  • Ejemplos de código con y sin TBB
  • Comparación de performance
• Comunicación con el núcleo
  • Llamadas al sistema
  • Señales
  • Interrupciones
  • Cómo y cuándo se disparan estos mecanismos
  • Agregar una llamada al sistema, un ISR y una señal

Boot loading:

• Investigar el proceso de inicialización del Sistema Operativo.
• Implementar un Boot loader básico que ejecute algún programa simple emulando el proceso de inicialización del sistema Operativo.
• Implementar un Boot Loader que permita arrancar Linux

http://it.wikipedia.org/wiki/Boot_loader http://www.osdev.org/wiki/Bootloader http://www.viralpatel.net/taj/tutorial/hello_world_bootloader.php http://msdn2.microsoft.com/en-us/library/ms901837.aspx http://linuxdevices.com/articles/AT5085702347.html

Build your own operating system:

Investigar el proceso de desarrollo de un sistema operativo.

Basar el estudio en MikeOS:

• Desarrolla una versión Hello World del Sistema operativo.
• Expandir este SO para agregarle alguna funcionalidad.
• Presentarlo corriendo sobre QEmu

http://mikeos.sourceforge.net/ http://mikeos.sourceforge.net/handbook.html http://mikeos.sourceforge.net/handbook.html#firstos http://nasm.sourceforge.net/ http://fabrice.bellard.free.fr/qemu/

Basar el estudio en GeekOS

• Ccompilar y probar GeekOS.
• Carga de archivos ejecutables (parseo de un ELF).
• Agregar procesos de usuario.

http://geekos.sourceforge.net/ http://gcc.gnu.org/ http://bochs.sourceforge.net/

Implementar un sistema de archivos en espacio de usuario, que ahorre espacio mediante el uso de block hashes para identificar cada bloque y asi poder almacenar una sola vez cada bloque sin importar la cantidad de veces aparece en el sistema de archvos.

• Instalar e investigar la API de fuse
• Implementar un filesystem sencillo usando fuse y block hashes
• Medir la performance y el ahorro de espacio, comparando con un filesystem trivial en memoria.

Implementar un sistema de archivos en espacio de usuario, que encripte lo bloques para que solo pueda ser leído con exito por lo usuarios que posean la clave.

• Instalar e investigar la API de fuse.
• Implementar un filesystem sencillo usando fuse y encriptando los bloques.
• Medir el overhead producido por la encriptación y desencriptación.

Home Fuse Función de hash (wikipedia) Módulo criptográfico de GNU

• Génesis, relación con Staircase Deterministic (SD) de Con Kolivas.
• Proceso de desarrollo, controversias y discusiones, estado actual.
• Funcionamiento general, ideas matemáticas y comparación con Really Fair Scheduler (RFS).
• Highlights del código.
• Benchmarking de O(1), SD y CFS en el estado actual (¿Ya mezclado en 2.6.23?).
• Fuentes: CFS en KernelTrap, Página de Ingo Molar en RedHat

• Estudiar DTrace de Solaris.
• Estudiar, instalar y hacer funcionar ejemplos de SystemTap.
• Implementar y mostrar como funcionan scripts que ayuden a detectar:
  • Fallas de performance en servidores Linux.
  • Procesos con programas mal hechos: muchas system calls, mucha I/O corta, demasiado locking, etc.
• Instalar OpenSolaris o Solaris10 y mostrar DTrace funcionando.
• Comparar DTrace con SystemTap.
• Otros links: http://blogs.sun.com/ahl/entry/dtrace_knockoffs, http://prefetch.net/articles/solaris.dtracetopten.html

• Buddy, Slab, Slub.
• Estudio de las implementaciones.
• Como usar slabtop para mirar el estado de la memoria del kernel y diagnosticar problemas.
• Benchmarking.
• Estado actual del kernel de Linux.
• Links: http://en.wikipedia.org/wiki/Buddy_memory_allocation, http://en.wikipedia.org/wiki/Slab_allocation, http://kernelnewbies.org/Linux_2_6_22#head-b8a3a2eee0cd6ebd97e500bdcd941f08a24e622d

• Estudiar el tema, ver que arquitecturas soportan superpages (i386 seguro, ia64 más).
• Ver que estado tiene en Linux, FreeBSD, Solaris, WindowsNT/Vista.
• Hacer un benchmark en cualquier par OS/arch que permita conectar y desconectar esta característica.
• Links: What's cooking for FreeBSD 7?, Practical, transparent operating system support for superpages, A transparent Linux super page kernel for Alpha, Sparc64 and IA32: reducing TLB misses of applications.

• Es algo muy necesario para todos los dispositivos que utilizan Linux y se alimentan de una batería: Handhelds, Laptops, XO-1, GPS, mediaplayers, etc. .
• Modificaciones del kernel: tickless kernel, cpufreq governor.
• Links: Linux, reducing the power consumption, Powertop, LessWatts