practicas/practica2/informe.rst

   1 ===============================
   2 Sistemas Distribuidos I (75.74)
   3 ===============================
   4
   5 ----------------------------------
   6 Práctica 2: Repaso de concurrencia
   7 ----------------------------------
   8
   9 :Author: Leandro Lucarella (77891)
  10
  11 .. contents:: Índice
  12 .. sectnum::
  13   :depth: 3
  14
  15 Exclusión Mutua
  16 ===============
  17
  18
  19 Problema de los jardines con shared memory
  20 ------------------------------------------
  21
  22 Como implementa el mutex con el algoritmo de Dekker con turnos sólo funciona
  23 para 2 procesos y hay que numerarlos a mano. Se corre con::
  24
  25   $ ./P02e1101 0 & ./P02e1101 1 &
  26
  27 El primer parámetro es el número de proceso, debe ser 0 o 1, se puede pasar un
  28 segundo parametro opcional con la cantidad de iteraciones a realizar. El proceso
  29 0 debe ejecutarse primero porque es el que inicializa las estructuras
  30 compartidas.
  31
  32 Se provee un script lanzador::
  33
  34   $ ./P02e1101.sh
  35
  36 Recibe un parámetro opcional con la cantidad de iteraciones.
  37
  38 Código fuente (P02e1101.cpp)
  39 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  40 .. include:: P02e1101.cpp
  41   :literal:
  42
  43 Código fuente (P02e1101.sh)
  44 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
  45 .. include:: P02e1101.sh
  46   :literal:
  47
  48 Corrida de ./P02e1101.sh
  49 ^^^^^^^^^^^^^^^^^^^^^^^^
  50 .. include:: P02e1101.corrida
  51   :literal:
  52
  53
  54 Problema de los jardines con semáforos y shared memory
  55 ------------------------------------------------------
  56
  57 Muy similar al anterior pero se puede correr con N procesos porque se usan
  58 semáforos para hacer exclusión mutua. Por ejemplo::
  59
  60   $ ./P02e1201 0 & ./P02e1201 1 & ./P02e1201 2 & ./P02e1201 3 & ./P02e1201 4
  61
  62 También acepta un párametro extra para la cantidad de iteraciones.
  63
  64 Se provee un script lanzador::
  65
  66   $ ./P02e1201.sh
  67
  68 Recibe un parámetro opcional con la cantidad de iteraciones, este lanzador
  69 corre 5 instancias como en la línea de ejecución de ejemplo.
  70
  71 Código fuente (P02e1201.cpp)
  72 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  73 .. include:: P02e1201.cpp
  74   :literal:
  75
  76 Código fuente (P02e1201.sh)
  77 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
  78 .. include:: P02e1201.sh
  79   :literal:
  80
  81 Corrida de ./P02e1201.sh
  82 ^^^^^^^^^^^^^^^^^^^^^^^^
  83 .. include:: P02e1201.corrida
  84   :literal:
  85
  86
  87 Análisis de entrelazado, interbloqueo y espera activa
  88 -----------------------------------------------------
  89 En el primer programa no hay posibilidad de interbloqueo ya que se utiliza el
  90 algoritmo de Dekker que es un algoritmo muy conocido y probado que garantiza
  91 tanto la ausencia de interbloqueo como *fairness*. Sin embargo sí hay espera
  92 activa (el algoritmo se basa en espera activa sobre variables compartidas). El
  93 entrelazado puede observarse gracias a la llamada a sched_yield(). De no
  94 utilizarse, el entrelazado se ve de manera mucho menos frecuente, ya que hay que
  95 esperar que se agote el *timeslice* del proceso en ejecución (que se queda
  96 ejecutando la espera activa) para que el kernel ponga a ejecutar otro proceso.
  97
  98 En el segundo programa, con el entrelazado pasa exactamente lo mismo, porque los
  99 semáforos se utilizan como mutex, de la misma manera que fue usado el mutex
 100 construido con el algoritmo de Dekker. Tampoco hay posibilidad de interbloqueo
 101 porque no hay anidamiento de mutex ni ninguna otra condición que pueda llevar a
 102 esto, es un uso muy básico y simple de un sólo semáforo a modo de mutex. Sin
 103 embargo, la espera activa desaparece gracias a la utilización de los semáforos,
 104 ya que si un proceso hace el wait y el semáforo está en 0, el kernel pone el
 105 proceso en pausa y continúa ejecutando otros procesos hasta que el estado del
 106 semáforo cambie con un signal.
 107
 108
 109
 110 Sincronización
 111 ==============
 112
 113
 114 Usando semáforos binarios y shared memory
 115 -----------------------------------------
 116
 117 Esquema productor-consumidor
 118 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 119 Productor-consumidor usando semáforos binarios y shared memory. Debe coincidir
 120 la cantidad de cosas a producir y a consumir, y debe correrse primero el
 121 productor porque inicializa las estructuras compartidas. Por ejemplo::
 122
 123   $ ./P02e2111 0 & ./P02e2111 1 &
 124
 125 También acepta un parámetro extra para la cantidad de iteraciones. 0 es
 126 productor, 1 es consumidor.
 127
 128 Otra forma de probar con varios consumidores es::
 129
 130   $ ./P02e2111 0 20 & ./P02e2111 1 12 & ./P02e2111 1 8 &
 131
 132 Se provee un script lanzador::
 133
 134   $ ./P02e1201.sh
 135
 136 Recibe un parámetro opcional con la cantidad de iteraciones, este lanzador
 137 corre 1 productor y 1 consumidor.
 138
 139 Código fuente (P02e2111.cpp)
 140 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 141 .. include:: P02e2111.cpp
 142   :literal:
 143
 144 Código fuente (P02e2111.sh)
 145 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 146 .. include:: P02e2111.sh
 147   :literal:
 148
 149 Corrida de ./P02e2111.sh
 150 ~~~~~~~~~~~~~~~~~~~~~~~~
 151 .. include:: P02e2111.corrida
 152   :literal:
 153
 154
 155 Esquema productor-consumidor con 3 productores y 2 consumidores
 156 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 157 Productor-consumidor usando semáforos binarios y shared memory pero con 3
 158 productores que producen parcialmente y 2 consumidores que consumen todo.
 159 Debe correr primero el primer productor porque inicializa las estructuras
 160 compartidas. Por ejemplo::
 161
 162   $ ./P02e2121 0 & ./P02e2121 1 & ./P02e2121 2 & ./P02e2121 3 & ./P02e2121 4 &
 163
 164 El proceso 0 a 2 son productores, el 3 y 4 consumidores.
 165
 166 Se provee un script lanzador::
 167
 168   $ ./P02e2121.sh
 169
 170 Recibe un parámetro opcional con la cantidad de iteraciones.
 171
 172 Código fuente (P02e2121.cpp)
 173 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 174 .. include:: P02e2121.cpp
 175   :literal:
 176
 177 Código fuente (P02e2121.sh)
 178 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
 179 .. include:: P02e2121.sh
 180   :literal:
 181
 182 Corrida de ./P02e2121.sh
 183 ~~~~~~~~~~~~~~~~~~~~~~~~
 184 .. include:: P02e2121.corrida
 185   :literal:
 186
 187
 188 Usando colas de mensajes
 189 ------------------------
 190
 191 Esquema productor-consumidor
 192 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 193 Productor-consumidor usando colas de mensajes. Debe coincidir la cantidad de
 194 cosas a producir y a consumir, y puede haber sólo un productor (que debe
 195 correr primero) y un solo consumidor. Por ejemplo::
 196
 197   $ ./P02e2211 0 & ./P02e2211 1 &
 198
 199 También acepta un parámetro extra para la cantidad de iteraciones. 0 es
 200 productor, 1 es consumidor.
 201
 202 Se provee un script lanzador::
 203
 204   $ ./P02e2211.sh
 205
 206 Recibe un parámetro opcional con la cantidad de iteraciones.
 207
 208 Código fuente (P02e2211.cpp)
 209 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 210 .. include:: P02e2211.cpp
 211   :literal:
 212
 213 Código fuente (P02e2211.sh)
 214 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
 215 .. include:: P02e2211.sh
 216   :literal:
 217
 218 Corrida de ./P02e2211.sh
 219 ~~~~~~~~~~~~~~~~~~~~~~~~
 220 .. include:: P02e2211.corrida
 221   :literal:
 222
 223
 224 Esquema productor-consumidor con 3 productores y 2 consumidores
 225 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 226 Productor-consumidor usando colas de mensajes pero con 3 productores que
 227 producen parcialmente y 2 consumidores que consumen todo. Debe correr
 228 primero el primer productor porque inicializa las estructuras compartidas.
 229 Por ejemplo::
 230
 231   $ ./P02e2221 0 & ./P02e2221 1 & ./P02e2221 2 & ./P02e2221 3 & ./P02e2221 4 &
 232
 233 El proceso 0 a 2 son productores, el 3 y 4 consumidores.
 234
 235 Se provee un script lanzador::
 236
 237   $ ./P02e2221.sh
 238
 239 Recibe un parámetro opcional con la cantidad de iteraciones.
 240
 241 Código fuente (P02e2221.cpp)
 242 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 243 .. include:: P02e2221.cpp
 244   :literal:
 245
 246 Código fuente (P02e2221.sh)
 247 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
 248 .. include:: P02e2221.sh
 249   :literal:
 250
 251 Corrida de ./P02e2221.sh
 252 ~~~~~~~~~~~~~~~~~~~~~~~~
 253 .. include:: P02e2221.corrida
 254   :literal:
 255
 256
 257 Usando pipes
 258 ------------
 259
 260 Esquema productor-consumidor
 261 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 262 Productor-consumidor usando pipes. Debe coincidir la cantidad de cosas a
 263 producir y a consumir, y puede haber sólo un productor (que debe correr
 264 primero) y un sólo consumidor. Por ejemplo::
 265
 266   $ ./P02e2311 0 & ./P02e2311 1 &
 267
 268 También acepta un parámetro extra para la cantidad de iteraciones. 0 es
 269 productor, 1 es consumidor.
 270
 271 Se provee un script lanzador::
 272
 273   $ ./P02e2311.sh
 274
 275 Recibe un parámetro opcional con la cantidad de iteraciones.
 276
 277 Código fuente (P02e2311.cpp)
 278 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 279 .. include:: P02e2311.cpp
 280   :literal:
 281
 282 Código fuente (P02e2311.sh)
 283 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
 284 .. include:: P02e2311.sh
 285   :literal:
 286
 287 Corrida de ./P02e2311.sh
 288 ~~~~~~~~~~~~~~~~~~~~~~~~
 289 .. include:: P02e2311.corrida
 290   :literal:
 291
 292
 293 Esquema productor-consumidor con 3 productores y 2 consumidores
 294 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 295 Productor-consumidor usando pipes pero con 3 productores que producen
 296 parcialmente y 2 consumidores que consumen todo. Debe correr primero el
 297 primer productor porque inicializa las estructuras compartidas. Por ejemplo::
 298
 299   $ ./P02e2321 0 & ./P02e2321 1 & ./P02e2321 2 & ./P02e2321 3 & ./P02e2321 4 &
 300
 301 El proceso 0 a 2 son productores, el 3 y 4 consumidores.
 302
 303 Se provee un script lanzador::
 304
 305   $ ./P02e2321.sh
 306
 307 Recibe un parámetro opcional con la cantidad de iteraciones.
 308
 309 Código fuente (P02e2321.cpp)
 310 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 311 .. include:: P02e2321.cpp
 312   :literal:
 313
 314 Código fuente (P02e2321.sh)
 315 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
 316 .. include:: P02e2321.sh
 317   :literal:
 318
 319 Corrida de ./P02e2321.sh
 320 ~~~~~~~~~~~~~~~~~~~~~~~~
 321 .. include:: P02e2321.corrida
 322   :literal:
 323
 324
 325 Análisis de entrelazado, interbloqueo y espera activa
 326 -----------------------------------------------------
 327 En el punto 2.1.2 es el único ejemplo en donde puede observarse espera activa,
 328 ya que se verifica si un flag está seteado. Este flag indica si la parte
 329 correspondiente al productor en ejecución ya fue producida, de ser así espera
 330 (activamente) que los demás productores terminen de producir lo que les
 331 corresponda para luego pasar el control a los consumidores. La espera activa es
 332 realmente **muy** notoria.
 333
 334 Con respecto a interbloqueo, a menos que haya algún bug, no debería haber en
 335 ninguno de los 3 casos, porque los ejercicios fueron pensados para que no hayan
 336 2 procesos esperando condiciones complementarias.
 337
 338 Finalmente con el entrelazado pasa algo similar a lo comentado en el punto 1.3,
 339 excepto (nuevamente) por el ejericio 2.1.2, que por la forma en la que está
 340 resuelto, obliga a la existencia de entrelazado entre cada proceso, porque cada
 341 productor espera a que el resto termine, y ambos consumidores esperan a que
 342 todas las partes estén producidas. Hay libertad sobre la forma que pueden
 343 entrelazarse los productores entre sí, y los consumidores entre sí (aunque no se
 344 aprecie en la corrida), pero debe haber entrelazado entre el conjunto de
 345 productores y consumidores 1 a 1. En los otros ejemplo sí pasa lo descripto en
 346 el punto 1.3, que, si no se utilizara la llamada a sched_yield(), no se vería
 347 entrelazado entre los consumidores y productores a menos que se haga una corrida
 348 mucho más larga (más iteraciones) de forma que se agote el *timeslice* (o que se
 349 acabe el *buffer* de las colas o pipes y se ponga a dormir el proceso) de los
 350 procesos antes de que estos finalicen.
 351