• Author / Uploaded
• spjjoe2

Citation preview

Universidad Nacional de Educaci´on a Distancia

Gu´ıa Did´actica Programaci´on Concurrente (Ingenier´ıa T´ecnica Inform´atica de Sistemas)

Equipo docente: David Fern´andez Amor´os

.

c

2008 David Fern´andez Amor´os. Todos los derechos reservados.

2

´ INDICE

´ Indice 1. Informaci´on general

5

1.1. Presentaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.2. Introducci´on a la asignatura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2. Presentaci´on de los contenidos 2.1. Objetivos generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 8

3. Requisitos previos

8

4. Materiales

9

5. Orientaciones generales para el estudio

10

6. Distribuci´on del tiempo de estudio

12

7. Evaluaci´on

12

7.1. Pruebas de evaluaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

7.2. Criterios de calificaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

8. Programa

13

8.1. Bloque tem´atico 1: Introducci´on y conceptos b´asicos . . . . . . . . . . . . . . . . . .

13

8.1.1. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

8.1.2. Orientaciones espec´ıficas de los temas . . . . . . . . . . . . . . . . . . . . . .

15

8.2. Bloque tem´atico 2: Herramientas para manejar la concurrencia . . . . . . . . . . . . .

17

8.2.1. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

8.3. Orientaciones espec´ıficas de los temas . . . . . . . . . . . . . . . . . . . . . . . . . .

19

3

´ INDICE

8.4. Bloque tem´atico 3: Problemas de aplicaci´on . . . . . . . . . . . . . . . . . . . . . . .

23

8.4.1. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

8.5. Orientaciones sobre los contenidos . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

9. Actividades

24

4

1 Informaci´on general

1. 1.1.

Informaci´on general Presentaci´on

Esta gu´ıa pretende orientar al alumno en la planificaci´on y el estudio de la asignatura. Se recomienda leer la gu´ıa en su totalidad al principio del cuatrimestre para tener una visi´on de conjunto de la din´amica del curso. Esta informaci´on se complementa con el enunciado de la pr´actica obligatoria, las preguntas frecuentes y los problemas de examen disponibles en el curso virtual, de forma que el estudiante pueda planificar desde el principio el estudio y realizaci´on de la pr´actica para aprovechar el tiempo al m´aximo y no perder los plazos de entrega.

1.2.

Introducci´on a la asignatura

El a´ mbito de conocimiento de esta asignatura es el de la programaci´on en computaci´on paralela o distribuida. La programaci´on concurrente (en adelante PC) a˜nade una capa suplementaria de complejidad respecto de la secuencial, por cuanto que es una extensi´on de esta, en el sentido de que un programa concurrente est´a compuesto por varios programas secuenciales que pueden ejecutarse simultaneamente, compartiendo el acceso a unos recursos compartidos, con vistas a la consecuci´on de un objetivo com´un. De la compartici´on de recursos surge la necesidad de arbitrar mecanismos adecuados para permitir el acceso, ya sea para leer, ya sea para modificar el recurso compartido, de manera que se garantice que la informaci´on que proporciona en cualquier momento sea coherente. Esta necesidad de coherencia, unida a la articulaci´on de los programas individuales que constituyen el programa concurrente en un c´alculo com´un, lleva a la cuesti´on de la sincronizaci´on entre los programas. Se estudiar´an diferentes herramientas propuestas hist´oricamente para manejar la ejecuci´on simultanea de programas junto con esquemas algor´ıtmicos desarrollados para el tratamiento de situaciones comunes en PC. Las t´ecnicas aprendidas se pondr´an en aplicaci´on en un trabajo pr´actico de car´acter obligatorio en el que se desarrollar´a un programa concurrente que sirva de modelo a una situaci´on descrita en el enunciado del mismo. Los contenidos de esta asignatura se encuentran incluidos en otros planes de estudio dentro las asignaturas de sistemas operativos o de sistemas en tiempo real, si bien com´unmente en dichas materias la problem´atica espec´ıfica de la PC no se encuentra desarrollada, ni en extensi´on ni en profundidad al nivel en que se hace en esta. En el marco docente que desarrolla el actual plan de estudios, PC es una asignatura optativa de tercer curso de la titulaci´on de Ingenier´ıa T´ecnica en Inform´atica de Sistemas, si bien est´a disponible como asignatura de libre configuraci´on y de libre elecci´on dentro de la Escuela 5

1.2

Introducci´on a la asignatura

Superior de Ingenier´ıa Inform´atica de la UNED. Se imparte durante el primer cuatrimestre del tercer curso. La evaluaci´on de la asignatura incluye un trabajo obligatorio de ´ındole pr´actica por imperativo del reglamento del departamento LSI. En la pr´actica obligatoria de la asignatura y en el examen s´olo se exigir´a la codificaci´on de los programas en pseudoc´odigo, sin embargo, se recomienda encarecidamente que el programa de la pr´actica y los ejercicios se codifiquen y prueben con un lenguaje de programaci´on concreto. En la bibliograf´ıa de la asignatura se hace hincapi´e principalmente en los lenguajes PASCAL-FC, Java y en menor medida Ada, aunque el lenguaje elegido no es importante siempre que se utilicen las herramientas de sincronizaci´on pertenecientes al temario, aunque sea de forma simulada. Cada uno de ellos tiene sus ventajas e inconvenientes: PASCAL-FC es el decano de los lenguajes de programaci´on concurrente, no tanto por su antig¨uedad sino por el hecho de no haber sido actualizado desde hace d´ecadas. Con implementaciones para DOS, Windows y Linux, sus ventajas son la simplicidad del lenguaje, que tiene las m´ınimas caracter´ısticas de programaci´on, y la variedad de herramientas de concurrencia que soporta. Existen editores espec´ıficos para Windows e incluso un plugin para el entorno de programaci´on multiplataforma ECLIPSE. Entre las desventajas, se podr´ıa mencionar que tiene un cuarto de siglo con todo lo que ello conlleva, restricciones absurdas hoy en d´ıa respecto al n´umero m´aximo de procesos y de monitores, falta de tipos de datos b´asicos como ser´ıan las cadenas de caracteres (s´olo existe el tipo car´acter) y hasta m´aximo n´umero de instrucciones ejecutadas. Un programa que ejecute 200000 instrucciones es abortado y autom´aticamente sospechoso de livelock. Tampoco hay manera de definir una funci´on dentro de un monitor, aunque te´oricamente es posible. Estas limitaciones pueden ser severas incluso a la hora de realizar la pr´actica de la asignatura. Java es un lenguaje de prop´osito general, multiplataforma y constantemente modernizado. Existen editores y documentaci´on de todo tipo. Si bien las limitaciones de sus implementaciones en diversas plataformas y el hecho de ser muy a menudo interpretado pueden afectar negativamente sus posibilidades reales, sus limitaciones est´an a a˜nos luz de las de PASCAL-FC. Aunque sus primitivas de sincronizaci´on inicialmente no ten´ıan nada que ver con las estudiadas en la asignatura, hoy en d´ıa la situaci´on ha mejorado considerablemente. El punto m´as d´ebil de Java para esta asignatura es que requiere el aprendizaje de un lenguaje complejo, mientras que PASCAL-FC es casi inmediato. Ada es un lenguaje de prop´osito general, multiplataforma. Se considera un lenguaje especializado. Entre sus principios de dise˜no se encuentran la eficiencia y la concurrencia, cosa que no puede decirse a la vez de los dos lenguajes anteriormente mencionados. Sus primitivas de concurrencia apenas coinciden con las del temario de la asignatura, excepto en el caso de la invocaci´on remota (tambi´en conocida como cita de Ada o rendez-vous). Las desventajas son claras: se trata de un lenguaje de una extraordinaria complejidad, 6

2 Presentaci´on de los contenidos

con una curva de aprendizaje alta, poca variedad de compiladores y pocas posibilidades de uso fuera del departamento de defensa de los Estados Unidos de Am´erica, donde fue desarrollado originalmente. La PC se ha restringido tradicionalmente a unas a´ reas de aplicaci´on muy concretas, pero de una importancia incuestionable: Sistemas empotrados: Sistemas sencillos, habitualmente sin sistema operativo, en un hardware espec´ıfico, en los que unos programas que se ejecutan concurrentemente leen unos sensores y toman decisiones como activar o desactivar otros componentes electr´onicos. Un ejemplo sencillo ser´ıa un termostato. Sistemas operativos: En un sistema operativo multiprogramado lo normal es que haya varios procesos ejecut´andose en paralelo (ya se trate de paralelismo real o simulado). Es necesario sincronizar dichos procesos para que los programas del sistema y los de los usuarios puedan compartir los recursos de la m´aquina. Un caso particular pero especialmente relevante ser´ıa el de los sistemas operativos distribuidos. Sistemas de Gesti´on de Bases de Datos: Los SS.GG.BB.DD tienen entre sus objetivos de dise˜no el proporcionar un acceso eficiente a los datos manteniendo la consistencia de los mismos. Para permitir el acceso simultaneo de varios programas y mantener al mismo tiempo la consistencia de los datos entre las transacciones, se aplican t´ecnicas de PC. Computaci´on en malla: Se utilizan muchos ordenadores, conectados en red, para realizar un c´alculo entre todos. El ejemplo m´as conocido quiz´a sea el del proyecto SETI@Home, en el que ordenadores situados a lo largo de todo el planeta buscan coordinadamente indicios de vida extraterrestre. Pese a sus comienzos especializados, en la inform´atica de consumo se ha popularizado en los u´ ltimos tiempos el uso de sistemas multiprocesador. En estas CPU’s con dos, tres o cuatro n´ucleos, las ventajas de la PC son incluso m´as claras que en un entorno monoprocesador, lo que hace previsible un aumento de la demanda de profesionales con conocimientos s´olidos en este campo.

2.

Presentaci´on de los contenidos

Tras presentar algunos conceptos fundamentales de la PC, el foco se desplaza al uso de t´ecnicas concretas de PC. En particular, se hace un recorrido por algunas de las herramientas 7

2.1

Objetivos generales

de sincronizaci´on de procesos concurrentes en el a´ mbito de la memoria compartida: sem´aforos, regiones cr´ıticas, regiones cr´ıticas condicionales y monitores. En los temas siguientes se introducen los conceptos asociados al paso de mensajes y algunas de las herramientas correspondientes, en concreto buzones e invocaci´on remota. En todos los temas referentes a herramientas concretas se estudian soluciones a los dos problemas-tipo de la PC, que pueden verse como esquemas algor´ıtmicos: El problema de los lectores y escritores y el problema de los productores y consumidores. Otro aspecto transversal es el de la equivalencia de las distintas herramientas; el comportamiento de cualquier herramienta puede simularse mediante otra, a pesar de lo cual todas ellas poseen caracter´ısticas distintivas que hacen que unas sean m´as apropiadas que otras frente a un problema concreto.

2.1.

Objetivos generales Presentar los problemas derivados de la ejecuci´on simultanea de tareas Introducir esquemas algor´ıtmicos generales aplicables a numerosos problemas Adiestrar al estudiante en el empleo de diversas herramientas de sincronizaci´on de procesos Desarrollar la capacidad de an´alisis y dise˜no de soluciones a un problema de simulaci´on mediante el uso de t´ecnicas aprendidas en la asignatura

3.

Requisitos previos

En un modelo de capas o niveles de abstracci´on, la PC se encontrar´ıa en un nivel superior al de la programaci´on convencional. Dado que es el sistema el que proporciona la concurrencia, lo que corresponde al programador es administrar dicha concurrencia, de forma que las diferentes partes de un programa concurrente calculen juntas un resultado al tiempo que se mantiene la consistencia de los datos. Las t´ecnicas de programaci´on secuencial se dan por supuestas. Sin embargo, dicho esto hay que matizar que el e´ nfasis de la materia se centra en los mecanismos de sincronizaci´on de procesos, por lo que no se presta demasiada atenci´on a los aspectos formales y metodol´ogicos de la programaci´on. Por tal motivo, los u´ nicos requisitos previos ser´ıan un conocimiento s´olido de los contenidos correspondientes a la asignatura Programaci´on I, de primer curso. Ser´ıa u´ til, aunque no imprescindible, que el alumno tuviera una cierta familiaridad con con los contenidos de la asignatura Estructuras de Datos y Algoritmos, de segundo curso, especialmente en lo referido a tipos abstractos de datos. Por u´ ltimo, el contenido de la asignatura se relaciona con el de Sistemas Operativos I, de segundo curso, por lo que respecta a la relaci´on de los estados de un programa concurrente en relaci´on con el sistema operativo, por lo que una cierta familiaridad con los conceptos fundamentales de este tambi´en 8

4 Materiales

resulta conveniente. Con esta asignatura hay un cierto grado de solapamiento, puesto que en ella se dedica un tema de estudio a la PC. Evidentemente, el enfoque de aquella resulta m´as ligero, por lo que su estudio podr´ıa proporcionar una introducci´on a los temas desarrollados en esta asignatura. Dejando de lado algunas cuestiones de estilo de programaci´on, los problemas habituales de la asignatura no suelen estar relacionados con un aprendizaje deficiente de asignaturas anteriores, por lo que no se considera necesario reforzar capacidades anteriores. Se recomienda que se implementen y se prueben los problemas de los ejercicios y de la pr´actica obligatoria, por lo que se asume cierta destreza en la instalaci´on y utilizaci´on de entornos de compilaci´on y desarrollo.

4.

Materiales Los contenidos de la asignatura se desarrollan completamente en el texto base: Programaci´on Concurrente, Palma et al., Editorial Thomson, 2003.

En el texto base se discuten los conceptos fundamentales de la asignatura, as´ı como numerosos ejemplos de aplicaci´on y ejercicios resueltos. Tambi´en se proponen problemas por resolver, de modo que resulta un texto adecuado para el aprendizaje a distancia. Es cierto que en algunas de sus consideraciones pr´acticas, como la implementaci´on en Java de algunas de las t´ecnicas, ya est´a obsoleto debido al r´apido avance de la t´ecnica, pero afortunadamente, la presentaci´on de los conceptos y t´ecnicas es completamente actual. El alumno encontrar´a en el curso virtual materiales adicionales para el seguimiento de la asignatura. Entre ellos, enunciados de ex´amenes anteriores, ex´amenes resueltos, demostraciones de simulaciones realizadas aplicando las t´ecnicas objeto de estudio, as´ı como compiladores y documentaci´on sobre lenguajes de programaci´on con posibilidades de concurrencia. Como resultado de un seguimiento de las dificultades de los alumnos en relaci´on con la asignatura, se ha realizado un lista de preguntas frecuentes para optimizar el proceso de aprendizaje y evitar la sobrecarga del equipo docente, que redunda en unos tiempos de respuesta m´as largos a las dudas del alumnado. Una parte del mismo material se ha incluido en el DVD de la Escuela Superior de Ingenier´ıa Inform´atica, para aquellos alumnos a los que les resulte m´as conveniente este medio. La bibliograf´ıa complementaria consta de las siguientes obras: Programaci´on concurrente. 2a edici´on corregida, P´erez Mart´ınez, J. E., Madrid, Editorial Rueda, 1990. 9

5 Orientaciones generales para el estudio

Durante algunos a˜nos, esta obra fue el texto base de la asignatura. Esta obra peca quiz´as de un enfoque un tanto te´orico para una disciplina aplicada como es la programaci´on, pero supone un excelente contrapunto al estudio del texto base, ya que, a menudo, la bibliograf´ıa b´asica menciona r´apidamente aspectos vitales, como pueden ser la necesidad absoluta de la exclusi´on mutua en los accesos no compatibles, o las causas de los interbloqueos y las pol´ıticas para evitarlo, pero no los subraya. Este libro profundiza te´oricamente y ejemplifica los conceptos. El an´alisis de los puntos fuertes y d´ebiles de cada una estas obras en relaci´on con la otra permite obtener una visi´on de conjunto de la disciplina mucho m´as completa, y altamente recomendable, que la proporcionada por cada una de ellas individualmente. Principles of Concurrent and Distributed Programming. 2o Edici´on, Ben-Ari, M., AddisonWesley, 2006 Mordechai Ben-Ari es una de las figuras de referencia de la PC actual. Este matem´atico israel´ı, premiado por sus contribuciones a la ense˜nanza de la inform´atica ha sido un activo colaborador en el desarrollo del lenguaje Ada. Una prueba de lo influyente de esta obra, desde la primera edici´on en 1990, la da la mera comparaci´on de su ´ındice con el de las dos obras citadas anteriormente. Ada for Software Engineers, Ben-Ari, M., John Wiley & Sons, 1998. Este libro proporciona una introducci´on al lenguaje Ada de la mano de unos los expertos en el campo de la computaci´on distribuida. Las caracter´ısticas concurrentes forman parte de los principios de dise˜no de Ada, hecho este que lo diferencia de la mayor´ıa de los lenguajes de programaci´on con posibilidades de concurrencia, en las que estas no suponen m´as que un a˜nadido a posteriori.

5.

Orientaciones generales para el estudio

Una primera lectura r´apida del libro puede proporcionar una adecuada visi´on de conjunto de los problemas que se van a tratar. En esta primera lectura se pueden ignorar los apartados relativos a la puesta en pr´actica de la teor´ıa en los diversos lenguajes considerados (PASCALFC, Java y Ada). La primera unidad did´actica se corresponde con parte de los tres primeros cap´ıtulos del texto base, que pueden considerarse como una introducci´on extendida a los conceptos fundamentales de la PC. La informaci´on relevante de estos cap´ıtulos puede ser extra´ıda en la primera lectura, de forma que no se precise una relectura m´as adelante. La segunda unidad did´actica trata las diversas herramientas para manejar la concurrencia. La tercera consiste en las soluciones a problemas de aplicaci´on. Estas dos unidades est´an entremezcladas en el texto. Esta parte del libro puede estudiarse siguiendo el esquema de distribuci´on del tiempo de la siguiente secci´on, o bien leerse en orden ya que, despu´es de 10

5 Orientaciones generales para el estudio

presentar una herramienta para controlar la concurrencia, se pasa a implementar la soluci´on a los problemas-tipo utilizando dicha herramienta. Este enfoque ofrece la ventaja de que el estudiante se familiariza r´apidamente con los problemas que se resuelven y pronto s´olo le resulta novedosa la soluci´on que emplea la herramienta espec´ıfica considerada. Estas dos unidades did´acticas se merecen una segunda lectura m´as interpretativa. En primer lugar, para ser capaz de programar correctamente una soluci´on a un problema concreto, es necesario dominar los detalles de cada herramienta. Cada herramienta consta de una sintaxis, sem´antica y conjunto de estados espec´ıfico para los procesos (con sus diversos circuitos de colas de espera asociadas) que deben conocerse y manejarse con soltura. Un ejercicio muy u´ til para aclarar dudas y retener conceptos es implementar las primitivas de una herramienta utilizando otra. Este ejercicio tiene adem´as la ventaja de que a menudo un lenguaje de PC no soporta de forma nativa m´as que unas pocas herramientas de sincronizaci´on, de forma que si queremos usar otras deberemos primero simularlas mediante esas herramientas nativas. Otro aspecto sobre el que conviene reflexionar a medida que se estudia el texto base, es el comparar unas herramientas de sincronizaci´on con otras. No hay herramientas mejores que otras, puesto que a nivel te´orico todas son equivalentes, pero s´ı se pueden clasificar seg´un sean de alto o bajo nivel, sirvan para cualquier arquitectura, caso de las de paso de mensajes, o s´olo sean aptas para entornos de memoria compartida, etc. . . En una situaci´on concreta, es muy posible que haya unas herramientas m´as adecuadas que otras, por ello hay que intentar ser consciente de las diferencias entre ellas. En cualquier caso, tras esa primera lectura es cuando se puede comenzar a trabajar la pr´actica obligatoria de la asignatura, aunque este trabajo se limite a poco m´as que el an´alisis del enunciado. Es por desgracia frecuente que un alumno, presionado por los plazos de entrega, decida enfocar la asignatura con el m´etodo de tirarse a la piscina, o sea, empezar a programar sin leerse el libro apenas, o sin haberlo le´ıdo en absoluto. Habida cuenta de la abundancia de material sobre programaci´on disponible en la Red, esta posibilidad supone una tentaci´on, sin embargo dicho enfoque suele dejar unas lagunas que terminan suponiendo un grave lastre, que es detectado por el equipo docente m´as tarde de lo que ser´ıa deseable (t´ıpicamente despu´es de la primera entrega de la pr´actica, lo que lleva a hacer una segunda entrega no deseada previamente por ninguna de las partes). Una aproximaci´on m´as interesante puede ser la siguiente; despu´es de hacer una lectura r´apida de los temas del libro correspondientes al temario, se puede analizar el enunciado de la pr´actica y tomar una decisi´on sobre la herramienta que se va a utilizar en la pr´actica obligatoria. Resulta vital analizar si el problema de la pr´actica se puede asimilar de alguna manera a alg´un problema-tipo. Como s´olo hay dos problemas-tipo, la comprobaci´on no deber´ıa ser dif´ıcil. A continuaci´on, se puede estudiar detenidamente dicha herramienta, de modo que el trabajo sobre la pr´actica pueda ser llevado paralelamente al estudio del resto del temario.

11

6 Distribuci´on del tiempo de estudio

Unidad Did´actica I

II

III

Temario

Horas de estudio

Teor´ıa Pr´actica Tema 1. Introducci´on 2 Tema 2. Procesos vs. hilos 1 Tema 3. Exclusi´on mutua 2 Tema 4. Sem´aforos 3 Tema 5. Regiones Cr´ıticas Condicionales 2 Tema 6. Monitores 3 20 Tema 7. Buzones 3 Tema 8. Invocaci´on Remota 3 Tema 9. Equivalencia de Herramientas 3 Tema 10. Problemas de aplicaci´on 5 Figura 1: Temporizaci´on de la asignatura

6.

Distribuci´on del tiempo de estudio

Programaci´on concurrente es una asignatura cuatrimestral de cinco cr´editos: tres de teor´ıa y dos de pr´actica. Un cr´edito equivale a diez horas de estudio, lo que resulta en cincuenta horas de estudio. En la figura 6 se puede ver la temporizaci´on propuesta. Se propone un plan de trabajo de unas dos horas y media de estudio te´orico por semana. A partir de la tercera semana, el estudio te´orico se combina con la realizaci´on de la pr´actica a raz´on de unas dos horas por semana.

7. 7.1.

Evaluaci´on Pruebas de evaluaci´on

La calificaci´on de la asignatura tendr´a en cuenta la calificaci´on de la pr´actica obligatoria de la asignatura y la calificaci´on de la prueba presencial. Para aprobar la asignatura, tanto la pr´actica como la prueba presencial deben estar aprobadas. La nota de la pr´actica en una convocatoria se guarda para las siguientes del mismo curso. La pr´actica s´olo tiene dos calificaciones: apto y no apto. La superaci´on de la pr´actica no implica aumento de la calificaci´on final, aunque en algunos casos excepcionales puede aumentar o disminuir ligeramente la calificaci´on total. En el SIRA s´olo quedar´a reflejada la calificaci´on global, aunque en el curso virtual aparecer´a detallada la calificaci´on de la pr´actica. No hay pruebas de evaluaci´on a distancia. La pr´actica de la asignatura no comporta la asistencia a sesiones presenciales. Los alumnos sin 12

7.2

Criterios de calificaci´on

tutor pueden consultar sus dudas sobre la pr´actica en el foro correspondiente del curso virtual. La no superaci´on de la pr´actica en una convocatoria conlleva el suspenso en dicha convocatoria, por lo que si las nota de la pr´actica est´a disponible antes de los ex´amenes y no ha sido superada, no tiene sentido realizar la prueba presencial.

7.2.

Criterios de calificaci´on

En la prueba presencial se pedir´a el desarrollo de un programa concurrente similar al de la pr´actica. El programa del examen requiere la puesta en pr´actica de los conocimientos adquiridos durante el estudio de la asignatura, pero habitualmente no suele consistir en una aplicaci´on inmediata de un concepto te´orico o problema-tipo. Es frecuente que se mezclen los problemastipo de alguna forma, e incluso que sea necesario generalizar y combinar los problemas-tipo de forma no trivial y con cierto grado de creatividad. Tambi´en ocurre con frecuencia que el programa del examen no responda claramente a un esquema algor´ıtmico. En funci´on de la complejidad del mismo, puede haber tambi´en cuestiones te´orico-pr´acticas. Los criterios de evaluaci´on de la pr´actica y del problema de la prueba presencial son similares.

8.

Programa La asignatura se articula a trav´es de tres bloques tem´aticos: Bloque tem´atico 1: Introducci´on y conceptos b´asicos Bloque tem´atico 2: Herramientas para manejar la concurrencia Bloque tem´atico 3: Problemas de aplicaci´on Estos bloque tem´aticos se describen en detalle a continuaci´on.

8.1.

Bloque tem´atico 1: Introducci´on y conceptos b´asicos

Este bloque tem´atico presenta las particularidades suplementarias de la PC respecto a la programaci´on secuencial. Se motiva la necesidad y conveniencia de la PC, y se realizan algunas consideraciones sencillas sobre su implementaci´on a bajo nivel. Tambi´en se introducen los conceptos de proceso e hilo, lo que permite profundizar en la problem´atica de la PC en general y de la exclusi´on mutua en particular. 13

8.1

Bloque tem´atico 1: Introducci´on y conceptos b´asicos

8.1.1.

Objetivos

Tras estudiar este bloque tem´atico, el estudiante deber´a haber comprendido las diferencias esenciales entre la PC y la secuencial, as´ı como ser consciente de las diferentes arquitecturas f´ısicas de los sistemas en los que puede emplearse la PC. Una de estas caracter´ısticas a˜nadidas es el concepto de estado del de un proceso. En programaci´on cl´asica los estados de un programa son limitados; el sistema operativo carga y lanza el programa, que se ejecuta hasta su finalizaci´on. En PC cada proceso o hilo es un correlato del programa secuencial, pero puede encontrarse en un conjunto de estados mayor. Estos estados adicionales se derivan del hecho de que los procesos tienen que sincronizarse entre ellos, lo que a menudo significa que algunos de ellos deben esperar a que otros hayan realizado parte de su tarea. El otro gran problema de la PC es el de la exclusi´on mutua. Dos procesos no deben acceder concurrente a un mismo recurso (como una variable compartida o un perif´erico) de forma no compatible. Una vez que un programa concurrente se sincroniza en sus diversas partes correctamente y preserva la exclusi´on mutua a los recursos no compartibles, se puede considerar correcto. Sin embargo, hay otros problemas graves que pueden hacer poco aceptable un programa concurrente correcto. Algunos de estos problemas son la inanici´on, el establecimiento de turnos, la baja concurrencia, la espera activa y el interbloqueo. El interbloqueo se trata extensamente en el libro de P´erez Garc´ıa, donde se discuten t´ecnicas diferenciadas para detectarlo, evitarlo y prevenirlo. El estudiante deber´a ser capaz de identificar estas situaciones para poder evitarlas empleando las herramientas descritas en el segundo bloque tem´atico.

Temas 1. INTRODUCCION Conceptos fundamentales de la programaci´on concurrente Concepto de programaci´on concurrente Beneficios de la programaci´on concurrente Concurrencia y arquitecturas hardware Especificaci´on de ejecuci´on concurrente Caracter´ısticas de los sistemas concurrentes Problemas inherentes a la programaci´on concurrente 2. PROCESOS vs. HILOS Procesos Hilos 14

8.1

Bloque tem´atico 1: Introducci´on y conceptos b´asicos

Grafos de estados de un proceso / hilo Ciclo de vida de un proceso / hilo Grafos y diagramas de precedencia 3. EXCLUSION MUTUA. Introducci´on al problema Tipos de sincronizaci´on y su soluci´on Soluciones con espera ocupada (excepto algoritmos de Eisenberg-McGuire y Algoritmo de Lamport)

8.1.2.

Orientaciones espec´ıficas de los temas

Tema 1 Introducci´on La introducci´on a la Programaci´on Concurrente, como toda la asignatura, puede estudiarse por el libro de Palma et al., en adelante texto base. La secciones que proporcionan una introducci´on a los conceptos fundamentales de la PC, son la 1.1 (introducci´on) junto con la 1.2 (concepto de PC), 1.3 (beneficios de la PC), 1.4 (concurrencia e arquitecturas hardware), 1.5 (especificaci´on de ejecuci´on concurrente), 1.6 (caracter´ısticas de los sistemas concurrentes), 1.7 (problemas inherentes a la PC) y 1.8 (correcci´on de programas concurrentes). El estudio de este tema debe proporcionar al estudiante una visi´on de conjunto de la problem´atica de la PC y de algunas caracter´ısticas diferenciales respecto a la programaci´on secuencial. En particular, las diferentes arquitecturas hardware posibles, el concepto de traza de ejecuci´on y el indeterminismo tienen una influencia determinante en PC. Junto a los beneficios presentados de la PC, hay que ser consciente de los problemas asociados, que pueden ser de diversos tipos. Lo m´as importante que hay retener de este tema es que un programa concurrente no debe hacer ninguna suposici´on sobre la arquitectura del sistema en el que se ejecuta. Un programa concurrente se puede ejecutar en un entorno monoprocesador multiprogramado, en el cual no se produce concurrencia real sino que se simula. Sin embargo, tambi´en es frecuente (quiz´a lo m´as frecuente en nuestros d´ıas) que la m´aquina cuente con varios procesadores, de manera que, de hecho, haya varios procesos ejecut´andose en el mismo momento. El programador, en principio, s´olo deber´ıa preocuparse de saber si la arquitectura admite memoria compartida o, por el contrario, se trata de un sistema distribuido. En el primer caso, todas las primitivas de sincronizaci´on pueden ser consideradas, en el segundo, s´olo las herramientas basadas en paso de mensaje son admisibles.

15

8.1

Bloque tem´atico 1: Introducci´on y conceptos b´asicos

Las condiciones de Bernstein pueden ayudar a determinar qu´e es lo que se puede ejecutar de forma concurrente y lo que no, aunque como resumen, se puede decir que cualquier n´umero de procesos puede leer de un determinado recurso de forma concurrente. Sin embargo, el que haya un proceso escribiendo en el recurso lo hace incompatible tanto con otros procesos escritores como con procesos lectores. Esta cuesti´on est´a estrechamente relacionada con la del indeterminismo. Si bien el indeterminismo en programaci´on no es negativo per se (imaginemos, por ejemplo, un generador de n´umeros pseudoaleatorios) un programa concurrente querr´a en la mayor´ıa de los casos mantener cierta coherencia en los datos. En el ejemplo de la subsecci´on 1.6.2, vemos como un acceso no controlado a una variable hace que el valor de la misma sea impredecible. Pensemos ahora en un programa que controle el funcionamiento de una red de cajeros autom´aticos. Podemos querer cierta concurrencia, pero seguramente no queremos que se cree ni se destruya dinero en el proceso. La forma correcta de enfocar el problema tiene que garantizar el acceso en exclusi´on mutua a las cuentas en los accesos incompatibles con las condiciones de Bernstein. Esta cuesti´on es lo suficiente importante como para repetirla una vez m´as: Una variable compartida debe ser accedida siempre en exclusi´on mutua, salvo en los casos en los que se asegure que no hay ning´un otro proceso intentando modificar dicha variable al mismo tiempo. En la pr´actica, esto significa que las variables compartidas deben accedidas (ya sea para leer o para modificar sus valores) en exclusi´on mutua, salvo que se desarrolle un esquema de lectores y escritores, objeto de estudio del tercer bloque tem´atico. Tema 2 Procesos vs. hilos En el segundo cap´ıtulo del libro de Palma et al. se profundiza en las diferencias entre procesos e hilos en las secciones 2.1 (procesos) y 2.3 (hilos) Los conceptos m´as importantes de este tema son: • La distinci´on entre programa, proceso e hilo. • El concepto de estados de un proceso o hilo y su ciclo de vida. • Los grafos y diagramas de precedencia. • Los problemas de la PC, en particular la exclusi´on mutua y la condici´on de sincronizaci´on. Excepci´on hecha de las dos secciones mencionadas, el resto de este cap´ıtulo del libro no est´a muy relacionado con el contenido de la asignatura. Contiene multitud de detalles t´ecnicos que son a la vez demasiado avanzados y relativamente irrelevantes a la hora de comprender conceptualmente la asignatura. En alg´un caso la informaci´on all´ı expuesta puede servir para el estudiante a la hora de codificar y ejecutar sus programas concurrentes. Tema 3 Exclusi´on mutua

16

8.2

Bloque tem´atico 2: Herramientas para manejar la concurrencia

En la secci´on 3.1 se hace una introducci´on al problema. En la 3.2 (tipos de sincronizaci´on y su soluci´on) se plantea el problema de la exclusi´on mutua y su divisi´on entre soluciones con espera activa y sin espera activa. Tambi´en se plantea el problema de la condici´on de sincronizaci´on. En la secci´on 3.3 (soluciones con espera ocupada) excepto 3.3.5 (algoritmo de Eisenberg-McGuire) y 3.3.6 (algoritmo de Lamport) se estudian varios algoritmos, algunos de ellos incorrectos, otros correctos pero con problemas inaceptables y finalmente algunas soluciones aceptables desde el punto de vista te´orico basadas en espera activa. Al terminar de estudiar este tema, los conocimientos m´ınimos que se deben haber adquirido son: • Las diferencias principales entre las soluciones con espera activa y sin esperada activa. • Ser capaz de distinguir una soluci´on con espera activa correcta al problema de la exclusi´on mutua de una incorrecta. Tambi´en distinguir, entre las correctas, las aceptables de las inaceptables y poder explicar por qu´e (alternancia, espera infinita,. . . ). Las soluciones hardware explicadas en el texto base quedan fuera del a´ mbito de la asignatura. Lo u´ nico que el estudiante requiere saber es que todas las soluciones software al problema de la exclusi´on mutua son de una ineficiencia tal que resulta evidente que la exclusi´on mutua debe implementarse a nivel de hardware. La forma concreta de estas soluciones hardware de bajo nivel es irrelevante para nosotros, que nos centraremos en c´omo aprovechar las posibilidades para la exclusi´on mutua de las herramientas para manejar la concurrencia que son el objeto del siguiente bloque tem´atico.

8.2.

Bloque tem´atico 2: Herramientas para manejar la concurrencia

En este bloque se discuten diversos conjuntos de herramientas que se han propuesto te´oricamente para manejar la concurrencia. Dichas herramientas est´an implementadas en proporci´on desigual en los lenguajes de programaci´on. Mientras algunas de ellas, como los sem´aforos, han sido aceptadas de forma casi universal, otras han retenido su condici´on de propuestas m´as te´oricas. Es digno de menci´on sin embargo, que otras han superado este status en fechas relativamente recientes, como es el caso de la programaci´on orientada a sucesos o eventos, popularizada con el uso de las interfaces gr´aficas de usuario y la programaci´on orientada a objetos. El proceso inverso, conjuntos de herramientas diferentes de los cl´asicos, pero implementados por los lenguajes de uso frecuente, como podr´ıa ser el objeto protegido de Ada y las primitivas wait y notify de Java, tambi´en son frecuentes. En este bloque tem´atico se estudia tambi´en como superar esta separaci´on entre propuestas te´oricas y lo que de verdad est´a disponible a la hora de programar. La PC es un campo que evoluciona r´apidamente, por lo que el estudiante comprobar´a que es dif´ıcil establecer cu´ales son dichas diferencias. El caso de

17

8.2

Bloque tem´atico 2: Herramientas para manejar la concurrencia

Java es paradigm´atico en este sentido, ya que implementa de forma nativa primitivas de concurrencia no disponibles anteriormente en dicho lenguaje a una velocidad sorprendente, que convierte en obsoletas algunas de las recomendaciones del texto base. Todas las herramientas para manejar la concurrencia tienen la misma potencia y expresividad. No hay nada que pueda hacerse con una de ellas que no pueda hacerse con otra. Sin embargo, los distintos planteamientos pueden producir resultados muy diferentes en cada problema concreto. La elecci´on de una de ellas para un problema concreto puede venir forzada por el planteamiento o por el lenguaje, ser una cuesti´on de preferencias personales o el resultado de un compromiso entre elegancia y eficiencia.

8.2.1.

Objetivos

El estudiante deber´a familiarizarse con estas herramientas y ser consciente de sus diferencias. Las caracter´ısticas de una herramienta concreta, o la simulaci´on de una de ellas mediante la otra suelen ser objeto de evaluaci´on por parte del equipo docente.

Temas ´ 4. SEMAFOROS Introducci´on Definici´on de un sem´aforo Inconvenientes de los sem´aforos 5. REGIONES CR´ITICAS CONDICIONALES (RCC) Introducci´on Definici´on de RCC Inconvenientes de las RCC 6. MONITORES Introducci´on Definici´on de monitor Condici´on de sincronizaci´on Sem´antica de la operaci´on resume 7. BUZONES 18

8.3

Orientaciones espec´ıficas de los temas

Introducci´on Identificaci´on en el proceso de comunicaci´on Sincronizaci´on Canal de comunicaci´on y mensajes Espera selectiva Funcionamiento de los buzones ´ REMOTA 8. INVOCACION Introducci´on Funcionamiento de la invocaci´on remota 9. EQUIVALENCIA DE HERRAMIENTAS

8.3.

Orientaciones espec´ıficas de los temas

Tema 4 Sem´aforos. Los sem´aforos pueden estudiarse en el cap´ıtulo 4 del texto base, en concreto en las secciones 4.1 (introducci´on), 4.2 (definici´on de un sem´aforo), y 4.6 (inconvenientes del mecanismo de los sem´aforos). Los sem´aforos son indiscutiblemente la herramienta de PC m´as popular y m´as extendida. Todos los sistemas operativos multiprogramados est´an programados usando sem´aforos como herramienta de sincronizaci´on entre procesos. Las razones son claras: Se trata de una herramienta de bajo nivel que se puede implementar de forma casi inmediata por hardware en cualquier arquitectura que lo admita y adem´as permite un grado de control y flexibilidad que no es posible con ninguna otra herramienta de sincronizaci´on. Adem´as, pr´acticamente todos los lenguajes de programaci´on con posiblidades de concurrencia los implementan de forma nativa, as´ı que un programa concurrente concebido con sem´aforos ser´a f´acilmente portable a cualquier lenguaje y cualquier plataforma, al menos en lo que se refiere a los aspectos concurrentes. Por otro lado, las desventajas de los sem´aforos son considerables. Se trata de una herramienta de muy bajo nivel l´ogico. Un programa concurrente con unos pocos sem´aforos puede ir desde lo dif´ıcil de seguir por parte de un eventual lector a lo directamente incomprensible. Es f´acil cometer errores y puede resultar complejo encontrarlos. En PC, el mero hecho de que un programa se ejecute sin problemas durante un buen rato, no es o´ bice para que falle al instante siguiente. Los fallos pueden ser de una sutileza desconocida en la programaci´on secuencial. Un error frecuente con respecto a los sem´aforos, es pensar que despu´es de ejecutar la sentencia signal sobre un sem´aforo, un proceso cede la ejecuci´on a otro. Eso no s´olo no 19

8.3

Orientaciones espec´ıficas de los temas

es as´ı, sino que raras veces ocurre. Basta releer la sem´antica de la operaci´on signal para comprenderlo. Como explicaci´on adicional de por qu´e no hay motivo para que ocurra esto, basta pensar en un ordenador con dos procesadores y dos procesos. Si uno de ellos ejecuta un signal, no hay ninguna raz´on para que el proceso ceda la CPU al otro proceso, ya que ambos pueden seguir en ejecuci´on de forma concurrente. Es un hecho digno de menci´on que las secciones del libro dedicadas a la simulaci´on de sem´aforos mediante las primitivas de Java son tanto obsoletas como posiblemente incorrectas. Desde hace algunas versiones de Java existe la clase semaphore de forma nativa. Por otro lado, la simulaci´on basada en las antiguas primitivas de Java; wait, notify y notifyall tienen el inconveniente de que al llamar a notify o notifyall, el hilo que sale del estado bloqueado (del llamado waiting set) se elige de manera aleatoria, lo cual es contradictorio con la definici´on de los sem´aforos que implica la existencia de una cola, es decir, que el primero en entrar es el primero en salir. Hay que notar que esta diferencia de funcionamiento es lo bastante sutil como no afectar de forma perceptible el comportamiento de los programas, por lo que la simulaci´on puede usarse en la pr´actica sin problemas, pese a que ya no hay raz´on para no usar la implementaci´on nativa de los sem´aforos. Tema 5 Regiones cr´ıticas condicionales Las regiones cr´ıticas condicionales (RCC) se explican en el cap´ıtulo 5 del texto base, en particular en las secciones 5.1 (introducci´on), 5.2 (definici´on de RCC) y 5.5 (inconvenientes del mecanismo de RCC). Las regiones cr´ıticas a secas se pueden considerar como un caso particular de regi´on cr´ıtica condicional en la que la condici´on siempre es cierta. Las regiones cr´ıticas condicionales son una herramienta de nivel conceptual superior a los sem´aforos. Por alg´un motivo, es raro que est´en implementadas de forma nativa en lenguajes reales. En cualquier caso, permiten soluciones bastante elegantes para algunos problemas de PC que resultar´ıan enrevesadas con sem´aforos. Una diferencia interesante es el uso de dos colas para bloquear los procesos. Adem´as de la cola principal, existe una segunda cola, llamada cola de eventos, que permite que aquellos procesos que obtuvieron la exclusi´on mutua y despu´es la devolvieron por no cumplir la condici´on, tengan preferencia a la hora de reevaluarla ante los procesos que llegan al comienzo de la regi´on. Tema 6 Monitores El temario sobre los monitores se ajusta a lo explicado en el cap´ıtulo 6 del texto base, concretamente las secciones 6.1 (introducci´on), 6.2 (definici´on de monitor), 6.3 (condici´on de sincronizaci´on en monitores), y 6.6 (sem´antica de la operaci´on resume). Los monitores representan el nivel m´as elevado en t´erminos de abstracci´on conceptual en lo que respecta a herramientas de sincronizaci´on de memoria compartida. Esto los

20

8.3

Orientaciones espec´ıficas de los temas

sit´ua en el extremo opuesto a los sem´aforos, lo que puede observarse en lo complicado que resulta simular un monitor mediante sem´aforos. Los monitores no han gozado hist´oricamente de un gran apoyo en t´erminos de implementaci´on en lenguajes populares. El mecanismo de la exclusi´on mutua es autom´atico en los procedimientos del monitor, por lo que el e´ nfasis se sit´ua l´ogicamente en la sincronizaci´on. A este respecto, la operaci´on resume admite cuatro sem´anticas operacionales distintas. Nosotros adoptaremos la misma que el texto base, la denominada ”desbloquear y espera urgente”. Con esta sem´antica, el proceso que ejecuta una operaci´on resume sale del monitor y va inmediatamente a una cola llamada cola de cortes´ıa. Probablemente este comportamiento es que el despista a muchos estudiantes cuando piensan que un proceso que ejecuta un signal sobre un sem´aforo tambi´en se bloquea, lo que, como ya hemos mencionado, no es cierto. La situaci´on es completamente diferente. Aunque tengamos muchos procesadores, la caracter´ıstica principal del monitor es que s´olo un proceso puede estar activo dentro de un procedimiento del monitor, de modo que si se quiere despertar a otro proceso que se qued´o bloqueado cuando estaba dentro del monitor, hay que tomar una decisi´on, pero no pueden estar ejecut´andose los dos al mismo tiempo. Cuando un proceso ejecuta resume dentro de un monitor pueden pasar dos cosas. La primera es que no haya ning´un proceso bloqueado en la cola de cortes´ıa asociada a la variable de condici´on. En ese caso la sentencia resume no tiene efecto. La otra es que s´ı haya procesos. Un comentario incorrecto, pero frecuente, es que el proceso que ejecuta el resume sale del monitor y entra en la cola de cortes´ıa hasta que alg´un proceso ejecute resume, momento en el cual el proceso volver´a al monitor. La cola de cortes´ıa es, en efecto, una cola, por lo que si se ejecutan varios resume seguidos, un proceso que ejecut´o resume despu´es que otros puede tardar bastante en volver a entrar en el monitor; es decir, no volver´a al monitor al primer resume, sino cuando le toque. La secci´on del libro sobre monitores en Java est´a totalmente desfasada, ya que desde hace unas pocas versiones los monitores est´an implementados en Java de forma casi nativa. Una forma sencilla de implementarlos es utilizando las clases Lock y Condition. Los equivalentes de delay y resume ser´ıan los m´etodos await y signal de Condition. Un error frecuente con los monitores es usarlos para simular sem´aforos, definiendo unos procedimientos exportados wait y signal, para despu´es utilizar estos wait y signal para enmarcar una regi´on cr´ıtica. Es obvio que resulta mucho m´as l´ogico aprovechar el hecho de que los procedimientos del monitor se ejecutan en exclusi´on mutua para hacer un procedimiento que implemente la regi´on cr´ıtica. Por otra parte, es un error que demuestra poca familiaridad con el funcionamiento de los monitores. Tema 7 Buzones Los buzones corresponden a los cap´ıtulos 7 y 8 del texto base. En el cap´ıtulo 7 se siembran las bases para la comprensi´on de la herramienta buzones, explicando los mecanismos de paso de mensaje. Entran en el temario las secciones 7.1 (introducci´on), 7.2 21

8.3

Orientaciones espec´ıficas de los temas

(identificaci´on en el proceso de comunicaci´on), 7.3 (sincronizaci´on), 7.4 (canal de comunicaci´on y mensajes) y 7.6 (espera selectiva). Los buzones propiamente dichos se explican en el cap´ıtulo 8, en la secci´on 8.1 (introducci´on). En este tema se entra en el campo de las herramientas basadas en paso de mensajes, en contraposici´on a las herramientas basadas en memoria compartida. Las herramientas de paso de mensajes son las u´ nicas que se pueden utilizar en arquitecturas distribuidas. Aunque nada evita en principio utilizar variables compartidas, no es recomendable, ya que supone una restricci´on innecesaria y que priva al programa de la posibilidad de ejecutarse en sistemas distribuidos. Los buzones en s´ı se suelen declarar en el programa principal, es decir, est´an declarados de forma global, pero no se considera que sean variables globales, sino mecanismos de comunicaci´on. Por esa raz´on, el mero hecho de usar buzones no significa utilizar memoria compartida. Conviene recordar que los buzones son herramientas bloqueantes. Si un proceso intenta leer de un buz´on vac´ıo, quedar´a bloqueado hasta que otro proceso escriba en dicho buz´on. Una forma de evitar esta situaci´on es usar adecuadamente la funci´on EMPTY. Si el buffer es de tama˜no finito, las operaciones de escritura en el buz´on tambi´en provocan bloqueo cuando el buffer asociado est´e lleno. Una excepci´on a ambas situaciones es el uso de la sentencia SELECT. Otro error com´un, quiz´as influencia de la herramienta canales, es usar un buz´on distinto por cada dos procesos que quieran comunicarse entre ellos. Un mismo buz´on puede ser utilizado por todos los procesos. Un u´ ltimo error com´un es olvidar que la comunicaci´on en los buzones puede ser bidireccional. Un proceso puede utilizar un mismo buz´on tanto para leer como para escribir en e´ l. Tema 8 Invocaci´on remota La herramienta conocida como rendez-vous, cita de Ada o invocaci´on remota se explica en el cap´ıtulo 10 del texto base, en las secciones 10.1 (introducci´on) y 10.2 (invocaci´on remota). La invocaci´on remota es la herramienta de m´as alto nivel conceptual de todas las herramientas de sincronizaci´on basadas en paso de mensajes. Mediante la invocaci´on remota, un proceso puede ejecutar un procedimiento de otro proceso que adem´as puede (y suele) estar ejecut´andose en otra m´aquina. La invocaci´on remota es la herramienta concurrente m´as claramente enfocada al desarrollo de aplicaciones cliente-servidor. Una diferencia sustancial de la invocaci´on remota respecto a cualquier otra herramienta de PC, es que el que uso de invocaci´on remota suele llevar parejo el uso de procesos adicionales que act´uan como servidor o controlador. En particular, la simulaci´on de otras herramientas de sincronizaci´on mediante invocaci´on remota implica la creaci´on de nuevos procesos. A este respecto, la simulaci´on de un sem´aforo mediante invocaci´on remota en la p´agina 332 del texto base es bastante clarificadora.

22

8.4

Bloque tem´atico 3: Problemas de aplicaci´on

Un error com´un es suponer que el empleo de la invocaci´on remota proporciona de forma ”m´agica” exclusi´on mutua. En primer lugar, es perfectamente posible, y posiblemente conveniente, utilizar la invocaci´on remota sin usar memoria compartida. En ese caso la cuesti´on ni se plantea. Si se combina memoria compartida e invocaci´on remota puede haber problemas, especialmente si tenemos en cuenta que la invocaci´on remota permite el paso de par´ametros en ambas direcciones entre el proceso llamador y el llamado. El paso de par´ametros implica copia de los mismos, por lo que si se pasan como par´ametros de una invocaci´on remota variables compartidas, los resultados pueden ser impredecibles.

8.4.

Bloque tem´atico 3: Problemas de aplicaci´on

En PC hay dos problemas-tipo cuyo conocimiento es absolutamente imprescindible: Se trata del problema de los lectores y escritores y del problema de los productores y consumidores. Multitud de los aspectos de colaboraci´on entre los procesos de un programa concurrente responden a alguno de estos esquemas, ya sea directamente o mediante variaciones, combinaciones o generalizaciones de los mismos. S´olo por este motivo su incorporaci´on al temario estar´ıa sobradamente justificada, pero adem´as, el estudio de su resoluci´on mediante las diferentes herramientas del segundo bloque tem´atico supone una excelente manera de comprender su funcionamiento en la pr´actica. Por otra parte, es l´ogico suponer que tambi´en hay problemas que no responden en absoluto a dichos esquemas algor´ıtmicos. El otro problema resuelto en el texto base usando todas las herramientas de sincronizaci´on es el problema de la comida de los fil´osofos. Se trata de un problema cl´asico propuesto por Andrew Tanembaum para ilustrar muchos de los problemas que se producen al intentar solucionar un problema de PC de apariencia inocente, pero que no tiene una soluci´on plenamente satisfactoria.

8.4.1.

Objetivos Reflexionar sobre el uso de cada herramienta y despejar dudas sobre su funcionamiento. Al completar este bloque tem´atico, se espera que el estudiante sea capaz de identificar un problema-tipo si se enfrenta a uno en alguna de las pruebas de la asignatura.

8.5.

Orientaciones sobre los contenidos

Este bloque tem´atico consta de un u´ nico tema: 23

9 Actividades

Tema 10 Problemas de aplicaci´on Los problemas de aplicaci´on pueden estudiarse en las siguientes secciones del texto base: 4.3 (resoluci´on de problemas usando sem´aforos), 5.3 (resoluci´on de problemas usando RCC), 6.4 (resoluci´on de problemas usando monitores), la 8.2 (resoluci´on de problemas empleando paso de mensajes as´ıncrono) y 10.3 (resoluci´on de problemas mediante invocaci´on remota en PASCAL-FC). En ocasiones es necesario que varios procesos puedan leer un recurso al mismo tiempo. Si el recurso no tiene siempre el mismo valor, cosa que tendr´ıa poco sentido, tambi´en habr´a procesos que intenten modificarlo. La primera restricci´on descarta el acceso en exclusi´on mutua al recurso. La segunda descarta el acceder al recurso compartido sin ning´un tipo de sincronizaci´on. El esquema algor´ıtmico de los lectores y escritores es un ingenioso mecanismo que permite satisfacer ambas restricciones al mismo tiempo. El texto base trata la cuesti´on desde un punto de vista bastante te´orico. Como la divisi´on en cap´ıtulos se realiza en funci´on de las diferentes herramientas, los problemas resueltos y propuestos al final de cada cap´ıtulo suelen restringirse a proponer problemas de ´ındole general de cada herramienta concreta. En el curso virtual puede encontrarse una cierta cantidad de ex´amenes resueltos que enfocan los problemas-tipo. En la implementaci´on de lectores y escritores con preferencia para la escritura resuelto mediante sem´aforos, en la p´agina 101 del texto base, hay una errata: Donde pone ”ne := ne -1;”, deber´ıa poner ”escribiendo := false”. El problema-tipo de los productores y consumidores suele provocar menos problemas de comprensi´on que el de los lectores y escritores, por lo que se recomienda al estudiante que intensifique su estudio de este segundo. El problema de la cena de los fil´osofos no es un problema-tipo, sino m´as bien el tipo de problema que no se ajusta a ning´un tipo, por lo que identificar cualquier problema (excepto el de los fil´osofos y sus variaciones, claro est´a) como un caso del problema-tipo de los fil´osofos es un hecho bizarro que se recomienda evitar.

9.

Actividades

En el texto base y la bibliograf´ıa complementaria pueden encontrarse numerosos ejercicios propuestos y resueltos. Del mismo modo, en el curso virtual pueden encontrarse pr´acticas y ex´amenes de otros a˜nos, algunos de ellos resueltos.

24