PROBLEMA DE EXCLUSION MUTUA Y DE FILOSOFOS COMENSALES EN PYTHON

PROBLEMA DE EXCLUSION MUTUA Y DE FILOSOFOS COMENSALES EN PYTHON

IntroduccionEn un sistema multiprogramado con un nico procesador, los procesos se intercalan con el tiempo, para dar apariencia de ejecucin simultanea.Aunque no se consigue un procesado paralelo real, y aunque se produce un sobrecargado en la CPU por el hecho de tener que cambiar de tarea constantemente, las ventajas de todo esto son muy elevadas.

Uno de los problemas que nos podemos encontrar es que el hecho de compartir recursos esta lleno de riesgos:Si dos procesos hacen uso al mismo tiempo de una variable global y ambos llevan a cabo operaciones tanto de lectura como de escritura sobre dicha variable, el tiempo en el que se ejecuten estas operaciones es crtico puesto que podra afectar el valor de la variable.

Exclusin mutuaDefinicin:Consiste en que un solo proceso excluye temporalmente a todos los dems para usar un recurso compartido de forma que garantice la integridad del sistema.

Los algoritmos de exclusin mutua se usan en programacin concurrente para evitar el ingreso a sus secciones crticas por ms de un proceso a la vez. La seccin crtica es el fragmento de cdigo donde puede modificarse un recurso compartido.

La mayor parte de estos recursos son las seales, contadores, colas y otros datos que se emplean en la comunicacin entre el cdigo que se ejecuta cuando se da servicio a una interrupcin y el cdigo que se ejecuta el resto del tiempo. Se trata de un problema de vital importancia porque, si no se toman las precauciones debidas, una interrupcin puede ocurrir entre dos instrucciones cualesquiera del cdigo normal y esto puede provocar graves fallos.

Para solucionar el problema de la exclusin mutua se tienen 3 tipos de soluciones:

Soluciones de softwareSoluciones de hardwareSoluciones de Sistema operativoExclusin mutua

Soluciones de softwareAlgoritmo de PetersonEs un algoritmo de programacin concurrente para la exclusin mutua, que permite a dos o mas procesos o hilos compartir un recurso sin conflictos, utilizando solo la memoria compartida para la comunicacin.

Primer intento

Cualquier intento de exclusin mutua debe depender de algunos mecanismos bsicos de exclusin en el hardware. El ms habitual es que slo se puede acceder a una posicin de memoria en cada instante, teniendo en cuenta esto se reserva una posicin de memoria global llamada turno. Un proceso que desea ejecutar su seccin crtica primero evala el contenido de turno. Si el valor de turno es igual al nmero del proceso, el proceso puede continuar con su seccin crtica. En otro caso el proceso debe esperar. El proceso en espera, lee repetitivamente el valor de turno hasta que puede entrar en su seccin crtica. Este procedimiento se llama espera activa.Despus de que un proceso accede a su seccin crtica y termina con ella, debe actualizar el valor de turno para el otro proceso.

Segundo intento:

Cada proceso debe tener su propia llave de la seccin crtica para que, si uno de ellos falla, pueda seguir accediendo a su seccin crtica; para esto se define un vector booleano seal. Cada proceso puede evaluar el valor de seal del otro, pero no modificarlo. Cuando un proceso desea entrar en su seccin crtica, comprueba la variable seal del otro hasta que tiene el valor falso (indica que el otro proceso no est en su seccin crtica). Asigna a su propia seal el valor cierto y entra en su seccin crtica. Cuando deja su seccin crtica asigna falso a su seal.

Si uno de los procesos falla fuera de la seccin crtica, incluso el cdigo para dar valor a las variables seal, el otro proceso no se queda bloqueado. El otro proceso puede entrar en su seccin crtica tantas veces como quiera, porque la variable seal del otro proceso est siempre en falso. Pero si un proceso falla en su seccin crtica o despus de haber asignado cierto a su seal, el otro proceso estar bloqueado permanentemente.

Tercer intento

El segundo intento falla porque un proceso puede cambiar su estado despus de que el otro proceso lo ha comprobado pero antes de que pueda entrar en su seccin crtica.

Si un proceso falla dentro de su seccin crtica, incluso el cdigo que da valor a la variable seal que controla el acceso a la seccin crtica, el otro proceso se bloquea y si un proceso falla fuera de su seccin crtica, el otro proceso no se bloquea.

Si ambos procesos ponen sus variables seal a cierto antes de que ambos hayan ejecutado una sentencia, cada uno pensar que el otro ha entrado en su seccin crtica, generando as un interbloqueo.

Cuarto intento

En el tercer intento, un proceso fijaba su estado sin conocer el estado del otro. Se puede arreglar esto haciendo que los procesos activen su seal para indicar que desean entrar en la seccin crtica pero deben estar listos para desactivar la variable seal y ceder la preferencia al otro proceso.

Existe una situacin llamada bloqueo vital, esto no es un interbloqueo, porque cualquier cambio en la velocidad relativa de los procesos rompera este ciclo y permitira a uno entrar en la seccin crtica. Recordando que el interbloqueo se produce cuando un conjunto de procesos desean entrar en sus secciones crticas, pero ninguno lo consigue. Con el bloqueo vital hay posibles secuencias de ejecucin con xito.

Una solucin correctaHay que observar el estado de ambos procesos, que est dado por la variable seal, pero es necesario imponer orden en la actividad de los procesos para evitar el problema de "cortesa mutua". La variable turno del primer intento puede usarse en esta labor, indicando que proceso tiene prioridad para exigir la entrada a su seccin crtica.

Algoritmo para dos procesos

Algoritmo de DekkerAlgoritmo para la programacin concurrente para exclusin mutua, que permite a dos procesos compartir recursos si conflictos, si ambos procesos intentan acceder a la seccin critica simultneamente, el algoritmo elige un proceso segn una variable en turno.

Soluciones de software

El algoritmo de Deker resuelve el problema de la exclusin mutua pero mediante un programa complejo, difcil de seguir y cuya correccin es difcil de demostrar. Peterson ha desarrollado una solucin simple y elegante. Como antes, la variable global seal indica la posicin de cada proceso con respecto a la exclusin mutua y la variable global turno resuelve los conflictos de simultaneidad.

Considrese el proceso P0. Una vez que ha puesto seal[0] a cierto, P1 no puede entrar en su seccin crtica. Si P1 esta aun en su seccin crtica, entonces seal[1] = cierto y P0 est bloqueado en su bucle while. Esto significa que seal[1] es cierto y turno = 1. P0 puede entrar en su seccin crtica cuando seal[1] se ponga a falso o cuando turno se ponga a 0.

Considrense ahora los siguientes casos exhaustivos:

P1 no est interesado en entrar en su seccin crtica. Este caso es imposible porque implica que seal[1] = falso.P1 est esperando entrar en su seccin crtica. Este caso es tambin imposible porque si turno = 1, P1 podra entrar en su seccin crtica.P1 entra en su seccin crtica varias veces y monopoliza el acceso a ella. Esto no puede pasar porque P1 est obligado a dar a P0 una oportunidad poniendo turno a 0 antes de cada intento de entrar en su seccin crtica.As pues, se tiene una solucin posible al problema de la exclusin mutua para dos procesos. Es ms, el algoritmo de Peterson se puede generalizar fcilmente al caso de n procesos.

Soluciones de HardwareOptimistas: Consideran que lo mas probable es que no haya conflictos, y si los hay que sea en un nmero reducido, por lo que permiten cualquier acceso a la variable compartidaPesimistas: Bloquean todo aquello que pueda interferir Actualizan la variableDesbloquean lo bloqueado al principio.

Soluciones del sistema operativoSemforosBinarios: Este permite resolver la mayoria de los problemas de sincronizacin entre procesos, es un indicador de condicion que registra si un recurso esta disponible o no.Solo puede tener los valores 1 y 0Los semaforos solo permiten tres operaciones sobre ellos:Espera, Seal, Inicializar

MonitoresConsiste en una estructura formada por una cabecera que los identifica, un conjunto de variables globales a todos los procedimientos del monitor, un conjunto de procedimientos y un bloque de inicializacin.Soluciones del sistema operativo

MensajesSon una solucin del sistema operativo que nos permite la sincronizacion de procesos y la comunicacin entre ambos.Es una cadena de texto transmitida de un proceso que enva el mensaje al receptor, un mensaje puede tener cdigo, texto, datos

Soluciones del sistema operativo

Los mensajes suelen tener dos partesCabecera(obligatoria)Cuerpo (optativa)Tenemos dos tipos de ordenes para gestionar mensajes:Send(destino,mensaje)Receive(origen, mensaje)

Filsofos comensales Cincofilsofosse sientan alrededor de una mesa y pasan su vida cenando y pensando. Cada filsofo tiene un plato de fideos y un tenedor a la izquierda de su plato. Para comer los fideos son necesarios dos tenedores y cada filsofo slo puede tomar los que estn a su izquierda y derecha. Si cualquier filsofo toma un tenedor y el otro est ocupado, se quedar esperando, con el tenedor en la mano, hasta que pueda tomar el otro tenedor, para luego empezar a comer.Si dos filsofos adyacentes intentan tomar el mismo tenedor a una vez, se produce unacondicin de carrera: ambos compiten por tomar el mismo tenedor, y uno de ellos se queda sin comer.

Si todos los filsofos toman el tenedor que est a su derecha al mismo tiempo, entonces todos se quedarn esperando eternamente, porque alguien debe liberar el tenedor que les falta. Nadie lo har porque todos se encuentran en la misma situacin (esperando que alguno deje sus tenedores). Entonces los filsofos se morirn de hambre. Este bloqueo mutuo se denomina interbloqueo odeadlock

Algunas posibles solucionesPor turno cclicoVarios turnosColas de tenedoresEl portero del comedor