Preparatoria

Problemas de concurrencia
Problema de la cena de los filósofos
Descripción:
Cinco filósofos se sientan alrededor de una mesa y pasan su vida cenando y pensando. Cada filósofo tiene un plato de fideos y un tenedor a la izquierda de su plato. Para comer los fideos son necesarios dos tenedores y cada filósofo sólo puede tomar los que están a su izquierda y derecha. Si cualquier filósofo coge untenedor y el otro está ocupado, se quedará esperando, con el tenedor en la mano, hasta que pueda coger el otro tenedor, para luego empezar a comer.
Si dos filósofos adyacentes intentan tomar el mismo tenedor a una vez, se produce una condición de carrera: ambos compiten por tomar el mismo tenedor, y uno de ellos se queda sin comer.
Si todos los filósofos cogen el tenedor que está a su derecha almismo tiempo, entonces todos se quedarán esperando eternamente, porque alguien debe liberar el tenedor que les falta. Nadie lo hará porque todos se encuentran en la misma situación (esperando que alguno deje sus tenedores). Entonces los filósofos se morirán de hambre. Este bloqueo mutuo se denomina interbloqueo o deadlock.
Posibles soluciones:
Por turno cíclico: Se empieza por un filósofo, quesi quiere puede comer y después pasa su turno al de la derecha. Cada filósofo sólo puede comer en su turno.
Problema: si el número de filósofos es muy alto, uno puede morir de hambre antes de su turno.
Varios turnos: Se establecen varios turnos. Para hacerlo más claro supongamos que cada filósofo que puede comer (es su turno) tiene una ficha que después pasa a la derecha. Si por ejemplo hay 7comensales podemos poner 3 fichas en posiciones alternas (entre dos de las fichas quedarían dos filósofos). Se establecen turnos de tiempo fijo. Por ejemplo cada 5 minutos se pasan las fichas (y los turnos) a la derecha.
Problema: el tiempo del turno es esencial. Si el tiempo de turno se aproxima al tiempo medio que tarda un filósofo en comer esta variante da muy buenos resultados. Si además eltiempo medio de comer es similar al tiempo medio en volver a tener hambre la solución se aproxima al óptimo.
Colas de tenedores: Cuando un filósofo quiere comer se pone en la cola de los dos tenedores que necesita. Cuando un tenedor está libre lo toma. Cuando toma los dos tenedores, come y deja libre los tenedores.
Visto desde el otro lado, cada tenedor sólo puede tener dos filósofos en cola,siempre los mismos.
Problema: Esto crea el problema comentado de que si todos quieren comer a la vez y todos empiezan tomando el tenedor de su derecha se bloquea el sistema (deadlock).
Resolución de conflictos en colas de tenedores: Cada vez que un filósofo tiene un tenedor espera un tiempo aleatorio para conseguir el segundo tenedor. Si en ese tiempo no queda libre el segundo tenedor, suelta el quetiene y vuelve a ponerse en cola para sus dos tenedores.
Si un filósofo A suelta un tenedor (porque ha comido o porque ha esperado demasiado tiempo con el tenedor en la mano) pero todavía desea comer, vuelve a ponerse en cola para ese tenedor. Si el filósofo adyacente B está ya en esa cola de tenedor (tiene hambre) lo toma y si no vuelve a cogerlo A.
Es importante que el tiempo de espera seaaleatorio o se mantendrá el bloqueo del sistema.
El portero del comedor: Se indica a los filósofos que abandonen la mesa cuando no tengan hambre y que no regresen a ella hasta que vuelvan a estar hambrientos (cada filósofo siempre se sienta en la misma silla). La misión del portero es controlar el número de filósofos en la sala, limitando su número a n-1, pues si hay n-1 comensales seguro que almenos uno puede comer con los dos tenedores.
Soluciones en programación:
Intento con interbloqueo:

El procedimiento coger_tenedor espera hasta que el tenedor especificado esté disponible y lo coge. Por desgracia la solución obvia es incorrecta. Supongamos que los cinco filósofos cogen sus tenedores izquierdos de forma simultánea. Ninguno podría coger su tenedor derecho, lo que produciría un...