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.

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 Implementar el proyecto 0: compilar y probar GeekOS. Implementar el proyecto 1: carga de archivos ejecutables (parseo de un ELF). Implementar el proyecto 2: agregar procesos de usuario.

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

• 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.