Ciencias de la Computación FAMAF

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
(el usuario //blanco// puede editar, Nico)

==== Ejemplos Formativos vs. Informativos ====

Dividir ejemplos en:
  * Formativos: se mostrarán y pensarán en detalle
  * Informativos: paseo rápido.

=== Formativos ===
  * BoundedBuffer (aka Productores/Consumidores, aka BoundedCounter)
  * Concurrent Vector Writing [Fei99] vs. //Hand-over-hand locking// [2.5.1.4, Lea99]

=== Informativos ===
  * Nested monitor


















===== Taller =====

Investigar
  * Inyectar ruido en el scheduler, a través de Thread.yield() o toqueteando la JVM.
    * Ver [Goe06, 12.1.6 -- Generating More Interleavings]
  * Mostrar optimizaciones con algún ejemplo simple (//*[ x:=x+1; x:=x-1 ]//)
    * ''javap -c'' desensabla bytecode. Listado de los [[http://java.sun.com/docs/books/jvms/second_edition/html/Mnemonics.doc.html|VM Opcodes]].
    * ''-server'' en la ''jre'' optimiza más.
  * Ver como meter algo de ''assert'' para los invariantes.
    * En [[http://www.junit.org/index.htm|JUnit]] hay métodos ''[[http://junit.sourceforge.net/javadoc/junit/framework/Assert.html|assertTrue]]'', ''assertEqual'', etc.
    * La palabra ''[[http://java.sun.com/j2se/1.4.2/docs/guide/lang/assert.html|assert]]'' está desde JDK 1.4.2.
    * Algunos compiladores necesitan ''-source 1.4'' o ''-source 5.0'' para aceptarla.
    * En la JVM se activa con ''java -ea'', ver también ''-esa''.
  * ?Se puede hacer un ejemplo donde se muestre la sincronización de memoria ya sea con ''volatile'' o con ''synchronized''?
  * Ver el sourcecode de la JVM en el scheduler y como maneja el ''wait''.
  * Que hay en java.util.concurrent: ''CondVar'' sobre todo en Java 6 y Java 5, en Java 1.4.2 no está
    * [[http://java.sun.com/javase/6/docs/api/java/util/concurrent/package-summary.html|Java6]]
    * [[http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/package-summary.html|Java5]]
  * Notar que hay opciones muy específicas en la [[http://java.sun.com/javase/technologies/hotspot/vmoptions.jsp|HotSpot]] JVM como:
   <code>
-XX:PreBlockSpin=10

Spin count variable for use with -XX:+UseSpinning.
Controls the maximum spin iterations allowed before entering operating system thread synchronization code. (Introduced in 1.4.2.)

-XX:-UseSpinning

Enable naive spinning on Java monitor before entering operating system thread synchronizaton code. (Relevant to 1.4.2 and 5.0 only.) [1.4.2, multi-processor Windows platforms: true]
   </code>


== IncDecStar ==

Implementar *[ x:=x+1; x:=x-1 ]
Deducir el grado de atomicidad de x:=x+1 a partir de si se cumple el invariante 0<=x<=2.
Es notoria la diferencia entre 1 CPU y 2 CPUs en la riqueza del scheduling.
Relacionar esto con el hecho de que el planificador de Java es cooperativo en realidad, o sea no tiene Quanto.
Está bueno mostar:
  * Como una mala sincronización para hacer incremento atómico falla, por ejemplo ''synchronized(this) { }'' sincroniza con el mismo objeto thread.
  * Usar [[http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/atomic/AtomicInteger.html|AtomicInteger]].
    * Mirar la implementación de esto que básicamente usa ''compareAndSwapInt'' que internamente usa ''sun.misc.Unsafe'', y de esta última no encontre sourcecode FIXME. Aparentemente está en los fuentes del SDK que se bajan del sitio "developers".
  * Desensablar con ''javap -c'' y ver que el incremento está desacoplado. Notar los ''monitorenter'', ''monitorexit''.
<code>
   36:  monitorenter
   37:  aload_0
   38:  getfield        #15; //Field N:LMyInt;
   41:  dup
   42:  getfield        #52; //Field MyInt.value:I
   45:  iconst_1
   46:  iadd
   47:  putfield        #52; //Field MyInt.value:I
   50:  aload_1
   51:  monitorexit
</code>



== DoubleCheckTest ==

Bill Pugh, produjo un [[http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckTest.java|ejemplo]] limpio del problema //[[http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html|The "Double-Checked Locking is Broken" Declaration]]//.

El problema es que para Java5 no saltan los errores. FIXME


== Lock-free, wait-free linked lists ==

  * //"[[http://www.cs.rochester.edu/u/scott/papers/1996_PODC_queues.pdf|Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms]]"//
  * **ABA problem**. Problema con las arquitecturas de 64bits en [[http://www.research.ibm.com/people/m/michael/RC23089.pdf|ABA Prevention Using Single-Word Instructions]]. Alguna discusión de problemas de addressing-shrink en las arquitecturas de 64bits: [[http://blogs.msdn.com/oldnewthing/archive/2004/08/17/215682.aspx|The Old New Thing : Why is the virtual address space 4GB anyway?]].
  * FIXME Ver como es la implementación en ''java.util.concurrent''.
  * Pensar en algo más global con Producer/Consumer.