SandovalFernandoD01Act12 - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

UNIVERSIDAD DE GUADALAJARA 
Centro Universitario de Ciencias Exactas e Ingenierías 
Departamento de Ciencias Computacionales 
Seminario de Solución de Problemas de Uso, Adaptación y Explotación de 
Sistemas Operativos 
 
 
Actividad de Aprendizaje 12 
“Soluciones al Interbloqueo (filósofos)” 
 
 
 
Profesora: Sección: Fecha: 
Becerra Velázquez, Violeta del Roció D01 12/11/2021 
 
 
 
 
 
 
 
 
 
 
Soluciones al Interbloqueo (filósofos) 
 
2 
Índice 
Tabla de imágenes ................................................................................................ 2 
Introducción ........................................................................................................... 2 
Interbloqueo ........................................................................................................... 3 
El problema ........................................................................................................ 3 
Condiciones para el interbloqueo ....................................................................... 3 
Tratamiento del interbloqueo .............................................................................. 4 
Prevención del interbloqueo ............................................................................... 4 
Problema de los filósofos comensales ................................................................... 5 
Objetivo .............................................................................................................. 6 
Soluciones propuestas ....................................................................................... 6 
Código fuente ........................................................................................................ 7 
Repositorio: ........................................................................................................ 7 
Capturas: ............................................................................................................ 8 
Video...................................................................................................................... 9 
Conclusión ............................................................................................................. 9 
Bibliografía ........................................................................................................... 10 
 
Tabla de imágenes 
Ilustración 1 Interbloqueo, bloqueo mutuo, abrazo mortal (deadlock). .................. 3 
Ilustración 2 filósofos comensales ......................................................................... 5 
Ilustración 3 main.py .............................................................................................. 8 
Ilustración 4 Filósofo.py ......................................................................................... 8 
Ilustración 5 Mesero.py .......................................................................................... 9 
Ilustración 6 Tenedor.py ........................................................................................ 9 
Introducción 
En el presente documento analizaremos el concepto de interbloqueo a fondo, ya 
que es importante conocer sus condiciones que lo favorecen y como pueden ser 
tratas estas condiciones, es decir, las soluciones propuestas para el interbloqueo, 
siendo en este caso un enfoque concreto en el problema de los filósofos 
comensales, ya sea mediante semáforos, monitores, colas de exclusión, etc. 
Seminario de Solución de Problemas de Uso, Adaptación y Explotación de 
Sistemas Operativos 
 
 
Fernando Cesar Sandoval Padilla 
Interbloqueo 
El interbloqueo es una anomalía que puede ocurrir durante la ejecución de 
procesos concurrentes debido a la competencia por los recursos. 
Si bien es cierto que prácticamente ningún sistema operativo real incorpora 
mecanismos de tratamiento de interbloqueo, esto es debido a una cuestión de la 
pérdida de rendimiento que conlleva su tratamiento para la baja probabilidad que 
hay de que ocurra. En un sistema operativo ideal, sin embargo, sí deberían 
incluirse mecanismos para su tratamiento, dado que existen y son bien conocidos. 
 
El interbloqueo es un problema que afecta a procesos concurrentes que utilizan 
recursos en un sistema. 
Los procesos solicitan recursos al sistema y los liberan cuando ya no los 
necesitan. Un recurso puede estar disponible o bien asignado a algún proceso. 
Ejemplares. Puede haber varios ejemplares de un mismo tipo de recurso (ej. 
Varias impresoras). En este caso, cuando un proceso solicita un recurso, se le 
concede cualquiera de los ejemplares que esté disponible. 
Si un proceso solicita un recurso que no tiene ejemplares disponibles, el proceso 
queda bloqueado, esperando hasta que se le asigna un ejemplar. 
El problema 
Un conjunto de procesos bloqueados, cada uno de ellos esperando por un recurso 
que retiene otro proceso de ese conjunto. 
• Ningún proceso del conjunto puede avanzar 
 
Ilustración 1 Interbloqueo, bloqueo mutuo, abrazo mortal (deadlock). 
Condiciones para el interbloqueo 
Si en un sistema se produce una situación de interbloqueo, entonces se cumplen 
simultáneamente estas cuatro condiciones: 
• Exclusión mutua. Los recursos no se pueden compartir. 
• Retención y espera. Un proceso que retiene uno o varios recursos se 
encuentran esperando por recursos asignados a otros procesos. 
Soluciones al Interbloqueo (filósofos) 
 
4 
• No expropiación. Un recurso sólo puede ser liberado por el proceso que lo 
retiene, voluntariamente. 
• Espera circular. Existe una serie de procesos en espera {Po, P1,...Pn} en la 
que todo Pi espera por un recurso retenido por Pi+1; y Pn espera por un 
recurso retenido por Po. 
Tratamiento del interbloqueo 
Garantizar que en el sistema nunca ocurren interbloqueos 
• Prevención: diseñar el sistema de manera que nunca se cumpla alguna de 
las cuatro condiciones del interbloqueo. 
• Evitación: tratar de no caer nunca en un estado de interbloqueo. 
• Permitir la aparición de interbloqueos y recuperarse cuando ocurran 
necesitamos un sistema de detección y un mecanismo de recuperación 
• No tratar el problema si hay interbloqueos, el usuario tiene que intervenir 
Prevención del interbloqueo 
Se trata de eliminar la aparición de alguna de las cuatro condiciones necesarias 
para el interbloqueo. 
• Exclusión mutua. Depende de la naturaleza del recurso, así que esta 
condición no se puede eliminar. 
• Retención y espera. Hay que garantizar que un proceso no pueda quedar 
bloqueado si retiene algún recurso. ¿Cómo conseguirlo? 
o El proceso tiene que pedir todos sus recursos de una vez, p.ej. antes 
de empezar a ejecutarse efecto negativo: muchos recursos 
retenidos, pero no usados, un proceso sólo puede solicitar recursos 
cuando no tiene ninguno asignado. 
• Efecto negativo: puede ocurrir que tengamos que liberar un recurso y volver 
a pedirlo para poder solicitar otros recursos. 
o En ambos casos puede que un proceso nunca se ejecute (inanición) 
• No expropiación. Permitir que el S.O. desasigne recursos a un proceso 
bloqueado. 
o Si un proceso se bloquea por un recurso, los recursos retenidos 
quedan a disposición de los procesos activos 
o El proceso bloqueado tiene ahora que esperar por todos los recursos 
o Penaliza a los procesos que necesitan muchos recursos 
o Es posible seguir este protocolo en recursos cuyo estado se puede 
guardar fácilmente y después restaurarse (registros de CPU, espacio 
de memoria, etc.). Generalmente no puede aplicarse a recursos tales 
como impresoras y unidades de cinta. 
• Espera circular. Se puede evitar forzando un orden en la petición de los 
recursos. 
o Cada recurso tiene asignado un número de orden 
Seminario de Solución de Problemas de Uso, Adaptación y Explotación de 
Sistemas Operativos 
 
 
Fernando Cesar Sandoval Padilla 
o Los recursos se deben pedir en orden ascendente 
o Aconsejable: el ordende petición de los recursos se establezca 
según el orden de uso normal de los recursos de un sistema 
o Efectos negativos: 
▪ Se limita la libertad de escritura de código 
▪ Se puede inducir a una mala utilización de los recursos 
Problema de los filósofos comensales 
También conocido como “El problema de los filósofos cenando” o “El problema de 
los filósofos comensales”, es un problema clásico de las ciencias de la 
computación propuesto por el cientí-fico Edsger Dijkstra* para representar los 
inconvenientes que plantea la sincronización de procesos en un sistema operativo. 
 
Ilustración 2 filósofos comensales 
Hay cinco filósofos sentados alrededor de una mesa que pasan su vida cenando 
y pensando. Cada uno dispone de un plato de arroz y un tenedor a la izquierda de 
su plato, pero para comer son necesarios dos tenedores y cada filósofo sólo puede 
coger el que está a su izquierda o el que hay a su derecha. Con un solo tenedor 
en la mano no tienen más remedio que esperar hasta que atrapen otro y puedan 
seguir comiendo. 
Si dos filósofos adyacentes intentan tomar el mismo tenedor a la vez se produce 
una condición de carrera: ambos compiten por lo mismo, pero uno se queda sin 
comer. 
Si todos los filósofos cogen el tenedor de su derecha al mismo tiempo, todos se 
quedarán esperando eternamente porque alguien debe liberar el tenedor que les 
falta, cosa que nadie hará porque todos se encuentran en la misma situación 
(esperando que alguno deje su tenedor). Llegado esto, los filósofos se morirán de 
hambre. A este bloqueo mutuo se le denomina interbloqueo o deadlock. 
Soluciones al Interbloqueo (filósofos) 
 
6 
Objetivo 
El objetivo consiste en encontrar un recurso que permita que los filósofos nunca 
se mueran de hambre. Porque: 
• Dos filósofos contiguos no pueden comer a la vez (exclusión mutua). 
• Si un filósofo está comiendo, los contiguos no pueden hacerlo hasta que 
aquél termine (sincronización). 
• El filósofo que termina de comer debe ceder los tenedores para su posterior 
utilización (interbloqueo). 
Este sencillo planteamiento resulta muy útil para los que estudian informática 
porque ayuda a pensar en los sistemas que tienen recursos limitados (en el 
ejemplo anterior los tenedores son limitados) y en los clientes (programas y 
usuarios): hay que darles servicio (comida) a todos en un tiempo razonable. 
 
Se trata de que los recursos sean utilizados de la manera más eficiente por todos 
los procesos implicados. Hay algoritmos para solucionarlo, pero todos los métodos 
pasan por asignar prioridades y/o tiempos máximos de uso de los recursos. 
La finalidad es demostrar que se presentarán problemas ante la falta de una 
apropiada sincronización y evitar la peligrosa condición de carrera. 
Condición de carrera es una expresión que proviene del inglés “race condition”, si 
bien sería mejor hablar de “estado de carrera”, igual que se habla de estado de 
espera. Una condición de carrera describe el error que se produce en programas 
o circuitos lógicos cuando no han sido diseñados adecuadamente para su 
ejecución simultánea con otros. 
El ejemplo típico de interbloqueo se produce cuando dos procesos están 
esperando a que el otro realice una acción: ninguno llega a realizar la acción por 
estar a la espera del otro. Este tipo de errores de programación pueden ser 
aprovechados por exploits locales para vulnerar los sistemas. 
Soluciones propuestas 
• Primera solución correcta y eficiente 
La mejor solución a este problema es introducir un orden en los mutex y pedirlos 
siempre en orden ascendente. En este caso los filósofos 0 a 3 piden los mutex en 
orden ascendente, pero el número 4 lo pide en orden descendente (4 primero y 
luego el 0). El siguiente código se asegura de que el filósofo 4 también pida los 
mutex en orden ascendente: 
 
pthread_mutex_t palillos[5]; 
 
void filosofo(int i) { 
 for (;;) { 
Seminario de Solución de Problemas de Uso, Adaptación y Explotación de 
Sistemas Operativos 
 
 
Fernando Cesar Sandoval Padilla 
 int m1= min(i, (i+1)%5); 
 int m2= max(i, (i+1)%5); 
 pthread_mutex_lock(&palillos[m1]); 
 pthread_mutex_lock(&palillos[m2]); 
 comer(i, (i+1)%5); 
 pthread_mutex_unlock(&palillos[i]); 
 pthread_mutex_unlock(&palillos[(i+1)%5]); 
 pensar(); 
 } 
} 
Observamos que los mutex se pueden devolver en cualquier orden. 
El interés de esta solución es que se puede aplicar en el caso más complejo en 
que un número variable de threads necesita acceder a varias estructuras de datos 
compartidas para poder realizar una transacción. En ese caso, se introduce un 
orden en las estructuras de datos y el programa debe pedir ordenadamente los 
mutex que protegen cada estructura. Esto garantiza la ausencia de deadlock. 
• Segunda solución correcta y eficiente 
La segunda solución se basa en que el deadlock solo se produce si los 5 filósofos 
llegan a cenar. Si se limita a 4 los filósofos que pueden cenar, ya no habrá 
deadlock. Entonces se usa un semáforo con 4 tickets iniciales: 
 
pthread_mutex_t palillos[5]; 
sem_t portero; /* con 4 tickets iniciales */ 
 
void filosofo(int i) { 
 for (;;) { 
 sem_wait(&portero); 
 pthread_mutex_lock(&palillos[i]); 
 pthread_mutex_lock(&palillos[(i+1)%5]); 
 comer(i, (i+1)%5); 
 pthread_mutex_unlock(&palillos[i]); 
 pthread_mutex_unlock(&palillos[(i+1)%5]); 
 sem_post(&portero); 
 pensar(); 
 } 
} 
El problema de esta solución es que solo se aplica a 5 filósofos y 5 tenedores. No 
se puede generalizar a un número variable de threads accediendo a múltiples 
estructuras de datos. 
Código fuente 
Repositorio: 
https://drive.google.com/drive/folders/1TFjguwpXTMjWyRVtX_7qs4sTF5QzzFiL?
usp=sharing 
https://drive.google.com/drive/folders/1TFjguwpXTMjWyRVtX_7qs4sTF5QzzFiL?usp=sharing
https://drive.google.com/drive/folders/1TFjguwpXTMjWyRVtX_7qs4sTF5QzzFiL?usp=sharing
Soluciones al Interbloqueo (filósofos) 
 
8 
Capturas: 
Main 
 
Ilustración 3 main.py 
Filósofo 
 
Ilustración 4 Filósofo.py 
Seminario de Solución de Problemas de Uso, Adaptación y Explotación de 
Sistemas Operativos 
 
 
Fernando Cesar Sandoval Padilla 
 
 
Mesero 
 
Ilustración 5 Mesero.py 
Tenedor 
 
Ilustración 6 Tenedor.py 
Video 
https://drive.google.com/drive/folders/1TFjguwpXTMjWyRVtX_7qs4sTF5QzzFiL?
usp=sharing 
Conclusión 
Considero la realización de esta actividad como exitosa ya que me ayudo a 
comprender un poco mas el concepto de interbloqueo y lo que esto implica en un 
sistema operativo, pues programando una solución al problema de los filósofos 
comensales se logra un mejor entendimiento del proceso que conlleva el conseguir 
la exclusión mutua para que los procesos no se vean afectados unos a otros. Pese 
a que las soluciones para este tipo de problema pueden ser muy variadas, se 
https://drive.google.com/drive/folders/1TFjguwpXTMjWyRVtX_7qs4sTF5QzzFiL?usp=sharing
https://drive.google.com/drive/folders/1TFjguwpXTMjWyRVtX_7qs4sTF5QzzFiL?usp=sharing
Soluciones al Interbloqueo (filósofos) 
 
10 
analizo algunas posibilidades para así finalmente decidir cual es la que pondría en 
práctica. 
Finalmente puedo decir que esta actividad me deja un conocimiento que espero 
me sirva en las próximas actividades que tengan que ver con procesos o hilos ya 
que desde mi perspectiva es interesante tratar con estos problemas que me hacen 
ver como funciona un sistema operativo. 
Bibliografía 
• La cena de los filósofos. (s. f.). cartagena99. Recuperado 11 de noviembre de 
2021, de 
https://www.cartagena99.com/recursos/alumnos/apuntes/La%20cena%20de
%20los%20filosofos.pdf 
• Hermano Temblón. (2019, 5 septiembre). El problema de la cena de los 
filósofos. Recuperado 11 de noviembre de 2021, de 
https://www.hermanotemblon.com/el-problema-de-la-cena-de-los-filosofos/ 
• Sistemas Operativos - Interbloqueo. (s. f.). Sistemasoperativos. Recuperado 
11 de noviembre de 2021, de 
https://sistemasoperativos07.es.tl/Interbloqueo.htm