U3-DSO - mmmmmmmmmmmmmmmmmmmmmm PDF

Preview

Summary

mmmmmmmmmmmmmmmmmmmmmm...

Description

6 INTERBLOQUEOS

Los sistemas computacionales están llenos de recursos que pueden ser utilizados por sólo un proceso a la vez. Algunos ejemplos comunes son las impresoras, las unidades de cinta y las ranuras en los tableros internos del sistema. Cuando dos procesos escriben de manera simultánea en la impresora se producen incoherencias. Si dos procesos utilizan la misma entrada en la tabla del sistema de archivos invariablemente se corrompe el sistema de archivos. En consecuencia, todos los sistemas operativos tienen la habilidad de otorgar (en forma temporal) a un proceso el acceso exclusivo a ciertos recursos. Para muchas aplicaciones, un proceso necesita acceso exclusivo no sólo a un recurso, sino a varios. Por ejemplo, suponga que cada uno de dos procesos quiere grabar un documento digitalizado en un CD. El proceso pide permiso para utilizar el escáner y se le otorga. El proceso se programa de manera distinta y solicita primero el grabador de CDs, y también se le otorga. Ahora pide el grabador de CDs, pero la petición se rechaza hasta que lo libere. Por desgracia, en vez de liberar el grabador de CD, pide el escáner. En este punto ambos procesos están bloqueados y perLos interbloqueos también pueden ocurrir entre máquinas. Por ejemplo, muchas oficinas tienen una red de área local con muchas computadoras conectadas. A menudo, los dispositivos como escáneres, grabadores de CD, impresoras y unidades de cinta se conectan a la red como recursos compartidos, disponibles para cualquier usuario en cualquier equipo. Si estos dispositivos se pueden reservar de manera remota (es decir, desde el equipo doméstico del usuario), pueden ocurrir los mismos tipos de interbloqueos antes descritos. Las situaciones más complicadas pueden ocasionar interbloqueos que involucren a tres, cuatro o más dispositivos y usuarios. 433

434

INTERBLOQUEOS

CAPÍTULO 6

Los interbloqueos pueden ocurrir en una variedad de situaciones, además de solicitar dispositivos de E/S dedicados. Por ejemplo, en un sistema de bases de datos, un programa puede tener que bloquear varios registros que esté utilizando para evitar condiciones de competencia. Si el proceso bloquea el registro y el proceso bloquea el registro , y después cada proceso trata de bloquear el registro del otro, también tenemos un interbloqueo. Por ende, los interbloqueos pueden ocurrir en los recursos de hardware o de software. En este capítulo analizaremos varios tipos de interbloqueos, veremos cómo surgen y estudiarecontexto de los sistemas operativos, también ocurren en los sistemas de bases de datos y en muchos otros contextos en las ciencias computacionales, por lo que en realidad este material se puede aplicar a una amplia variedad de sistemas de multiproceso. Se ha escrito mucho sobre los interbloqueos. Dos bibliografías sobre el tema han aparecido en Operating Systems Review y deben consultarse en busca de referencias (Newton, 1979; y Zobel, 1983). Aunque estas bibliografías son antiguas, la mayor parte del trabajo sobre los interbloqueos se hizo mucho antes de 1980, por lo que aún son de utilidad.

6.1 RECURSOS Una clase principal de interbloqueos involucra a los recursos, por lo que para empezar nuestro esceso exclusivo a los dispositivos, registros de datos, archivos, etcétera. Para que el análisis sobre los interbloqueos sea lo más general posible, nos referiremos a los objetos otorgados como recur-

computadora tendrá muchos recursos que se pueden adquirir. Para algunos recursos puede haber disponibles varias instancias idénticas, como tres unidades de cinta. Cuando hay disponibles varias copias de un recurso, se puede utilizar sólo una de ellas para satisfacer cualquier petición de ese recurso. En resumen, un recurso es cualquier cosa que se debe adquirir, utilizar y liberar con el transcurso del tiempo.

6.1.1 Recursos apropiativos y no apropiativos Los recursos son de dos tipos: apropiativos y no apropiativos. Un recurso apropiativo es uno que se puede quitar al proceso que lo posee sin efectos dañinos. La memoria es un ejemplo de un recurso apropiativo. Por ejemplo, considere un sistema con 256 MB de memoria de usuario, una impresora y dos procesos de 256 MB, cada uno de los cuales quiere imprimir algo. El proceso A solicita y obtiene la impresora, y después empieza a calcular los valores a imprimir. Antes de terminar con el cálculo, excede su quantum de tiempo y se intercambia por el otro proceso. Ahora el proceso B se ejecuta y trata (sin éxito) de adquirir la impresora: se crea una situación potencial de interbloqueo, ya que A tiene la impresora y B tiene la memoria, y ninguno puede proceder sin el recurso que el otro posee. Por fortuna, es posible apropiarse (quitar) de la memoria de

SECCIÓN 6.1

RECURSOS

435

B al intercambiarlo y colocar el proceso A de vuelta. Ahora A se puede ejecutar, realizar su impresión y después liberar la impresora. Así no ocurre ningún interbloqueo. Por el contrario, un recurso no apropiativo es uno que no se puede quitar a su propietario actual sin hacer que el cómputo falle. Si un proceso ha empezado a quemar un CD-ROM y tratamos de quitarle de manera repentina el grabador de CD y otorgarlo a otro proceso, se obtendrá un CD con basura. Los grabadores de CD no son apropiativos en un momento arbitrario. En general, los interbloqueos involucran a los recursos no apropiativos. Los interbloqueos po-

en los recursos no apropiativos. La secuencia de eventos requerida para utilizar un recurso se proporciona a continuación, en un formato abstracto. 1. Solicitar el recurso. 2. Utilizar el recurso. 3. Liberar el recurso. Si el recurso no está disponible cuando se le solicita, el proceso solicitante se ve obligado a espe-

falla con un código de error y depende del proceso que hizo la llamada decidir si va a esperar un poco e intentar de nuevo. Un proceso al que se le ha negado la petición de un recurso por lo general permanece en un ciclo estrecho solicitando el recurso, después pasa al estado inactivo y después intenta de nuevo. Aunque este proceso no está bloqueado, para toda intención y propósito es como si lo estuviera, decuando a un proceso se le niega un recurso solicitado pasa al estado inactivo. La naturaleza exacta de solicitar un recurso es en gran medida dependiente del sistema. En allos recursos en forma explícita. En otros, los únicos recursos que conoce el sistema operativo son los archivos especiales que sólo un proceso puede tener abiertos en un momento dado. Éstos se abren mediante la llamada al sistema ordinaria. Si el archivo ya está en uso, el proceso que llama es bloqueado hasta que su propietario actual lo cierra.

6.1.2 Adquisición de recursos Para ciertos tipos de recursos, como los registros de una base de datos, es responsabilidad de los procesos de usuario administrar su uso. Una manera de permitir que los usuarios administren los recursos es asociar un semáforo con cada recurso. Estos semáforos se inicializan con 1. Se pueden utilizar mutexes de igual forma. Los tres pasos antes listados se implementan como una operación

436

INTERBLOQUEOS

CAPÍTULO 6

down en el semáforo para adquirir el recurso, usarlo y finalmente realizar una operación up en el recurso para liberarlo. Estos pasos se muestran en la figura 6-1(a).

typedef int semaforo; semaforo recurso_1;

typedef int semaforo; semaforo recurso_1; semaforo recurso_2;

void proceso_A(void) { down(&recurso_1); usar_recurso_1(); up(&recurso_1); }

void proceso_A(void) { down(&recurso_1); down(&recurso_2); usar_ambos_recursos(); up(&recurso_2); up(&recurso_1); }

(a)

(b)

Figura 6-1. Uso de un semáforo para proteger los recursos. (a) Un recurso. (b) Dos recursos.

Algunas veces los procesos necesitan dos o más recursos. Se pueden adquirir de manera secuencial, como se muestra en la figura 6-1(b). Si se necesitan más de dos recursos, sólo se adquieren uno después del otro. Hasta ahora todo está bien. Mientras sólo haya un proceso involucrado, todo funciona sin problemas. Desde luego que con sólo un proceso, no hay necesidad de adquirir formalmente los recursos, ya que no hay competencia por ellos. Ahora consideremos una situación con dos procesos, A y B, y dos recursos. En la figura 6-2 se ilustran dos escenarios. En la figura 6-2(a), ambos procesos piden los recursos en el mismo orden. En la figura 6-2(b), los piden en un orden distinto. Esta diferencia puede parecer insignificante, pero no lo es. En la figura 6-2(a), uno de los procesos adquirirá el primer recurso antes del otro. Después ese proceso adquirirá con éxito el segundo recurso y realizará su trabajo. Si el otro proceso intenta adquirir el recurso 1 antes de que sea liberado, el otro proceso simplemente se bloqueará hasta que esté disponible. En la figura 6-2(b), la situación es distinta. Podría ocurrir que uno de los procesos adquiera ambos recursos y en efecto bloquee al otro proceso hasta que termine. Sin embargo, también podría ocurrir que el proceso A adquiera el recurso 1 y el proceso B adquiera el recurso 2. Ahora cada uno se bloqueará al tratar de adquirir el otro. Ninguno de los procesos se volverá a ejecutar. Esa situación es un interbloqueo. Aquí podemos ver cómo lo que parece ser una diferencia insignificante en el estilo de codificación (cuál recurso adquirir primero) constituye la diferencia entre un programa funcional y uno que falle de una manera difícil de detectar. Como los interbloqueos pueden ocurrir con tanta facilidad, gran parte de la investigación se ha enfocado en las formas de lidiar con ellos. En este capítulo analizaremos los interbloqueos con detalle y lo que se puede hacer con ellos.

SECCIÓN 6.2 typedef int semaforo; semaforo recurso_1; semaforo recurso_2;

INTRODUCCIÓN A LOS INTERBLOQUEOS semaforo recurso_1; semaforo recurso_2;

void proceso_A(void) { down(&recurso_1); down(&recurso_2); usar_ambos_recursos(); up(&recurso_2); up(&recurso_1); }

void proceso_A(void) { down(&recurso_1); down(&recurso_2); usar_ambos_recursos(); up(&recurso_2); up(&recurso_1); }

void proceso_B(void) { down(&recurso_1); down(&recurso_2); usar_ambos_recursos(); up(&recurso_2); up(&recurso_1); }

void proceso_B(void) { down(&recurso_2); down(&recurso_1); usar_ambos_recursos(); up(&recurso_1); up(&recurso_2); }

(a)

437

(b)

Figura 6-2. (a) Código libre de interbloqueos. (b) Código con potencial de interbloqueo.

6.2 INTRODUCCIÓN A LOS INTERBLOQUEOS El interbloqueo se puede definir formalmente de la siguiente manera: Un conjunto de procesos se encuentra en un interbloqueo si cada proceso en el conjunto está esperando un evento que sólo puede ser ocasionado por otro proceso en el conjunto. Debido a que todos los procesos están en espera, ninguno de ellos producirá alguno de los eventos que podrían despertar a cualquiera de los otros miembros del conjunto, y todos los procesos seguirán esperando para siempre. Para este modelo suponemos que los procesos tienen sólo un hilo y que no hay interrupciones posibles para despertar a un proceso bloqueado. La condición sin interrupciones es necesaria para evitar que un proceso, que de cualquier otra forma estaría en interbloqueo, sea despertado por una alarma, por ejemplo, y después ocasione eventos que liberen a otros procesos en el conjunto. En la mayoría de los casos, el evento por el que cada proceso espera es la liberación de algún recurso que actualmente es poseído por otro miembro del conjunto. En otras palabras, cada miembro del conjunto de procesos en interbloqueo está esperando un recurso que posee un proceso en interbloqueo. Ninguno de los procesos se puede ejecutar, ninguno de ellos puede liberar recursos y ninguno puede ser despertado. El número de procesos y el número de cualquier tipo de recursos poseídos y solicitados es irrelevante. Este resultado se aplica a cualquier tipo de recurso, tanto de hardware como de software. A este tipo de interbloqueo se le conoce como interbloqueo de recursos. Es probablemente el tipo

438

INTERBLOQUEOS

CAPÍTULO 6

más común, pero no el único. Primero estudiaremos los interbloqueos de recursos con detalle, y después regresaremos brevemente a los demás tipos de interbloqueos al final del capítulo.

6.2.1 Condiciones para los interbloqueos de recursos Coffman y colaboradores (1971) mostraron que deben aplicarse cuatro condiciones para un interbloqueo (de recursos): 1. Condición de exclusión mutua. Cada recurso se asigna en un momento dado a sólo un proceso, o está disponible. 2. Condición de contención y espera. Los procesos que actualmente contienen recursos que se les otorgaron antes pueden solicitar nuevos recursos. 3. Condición no apropiativa. Los recursos otorgados previamente no se pueden quitar a un proceso por la fuerza. Deben ser liberados de manera explícita por el proceso que los contiene. 4. Condición de espera circular. Debe haber una cadena circular de dos o más procesos, cada uno de los cuales espera un recurso contenido por el siguiente miembro de la cadena. Las cuatro condiciones deben estar presentes para que ocurra un interbloqueo. Si una de ellas está ausente, no es posible el interbloqueo de recursos. Vale la pena observar que cada condición se relaciona con una política que puede o no tener un sistema. ¿Puede asignarse un recurso dado a más de un proceso a la vez? ¿Puede un proceso contener un recurso y pedir otro? ¿Pueden reemplazarse los procesos? ¿Pueden existir esperas circulares? Más adelante veremos cómo se puede atacar a los interbloqueos al tratar de negar algunas de estas condiciones.

6.2.2 Modelado de interbloqueos Holt (1972) mostró cómo se pueden modelar estas cuatro condiciones mediante el uso de gráficos dirigidos. Los gráficos tienen dos tipos de nodos: procesos, que se muestran como círculos, y recursos, que se muestran como cuadros. Un arco dirigido de un nodo de recurso (cuadro) a un nodo de proceso (círculo) significa que el recurso fue solicitado previamente por, y asignado a, y actualmente es contenido por ese proceso. En la figura 6-3(a), el recurso R está asignado actualmente al proceso A. Un arco dirigido de un proceso a un recurso significa que el proceso está actualmente bloqueado, en espera de ese recurso. En la figura 6-3(b), el proceso B espera al recurso S. En la figura 6-3(c) podemos ver un interbloqueo: el proceso C está esperando al recurso T, que actualmente es contenido por el proceso D. El proceso D no va a liberar al recurso T debido a que está esperando el recurso U, contenido por C. Ambos procesos esperarán para siempre. Un ciclo en el gráfico indica que hay un interbloqueo que involucra a los procesos y recursos en el ciclo (suponiendo que hay un recurso de cada tipo). En este ejemplo, el ciclo es C-T-D-U-C. Ahora veamos un ejemplo de cómo se pueden utilizar los gráficos de recursos. Imagine que tenemos tres procesos A, B y C, y tres recursos R, S y T. Las peticiones y liberaciones de los tres pro-

SECCIÓN 6.2

INTRODUCCIÓN A LOS INTERBLOQUEOS

439

Figura 6-3. Gráficos de asignación de recursos. (a) Contención de un recurso. (b) Petición de un recurso. (c) Interbloqueo.

cesos se proporcionan en las figuras 6-4(a) a (c). El sistema operativo es libre de ejecutar cualquier proceso desbloqueado en cualquier momento, por lo que podría optar por ejecutar A hasta que terminara todo su trabajo, después B hasta que completara y por último C. Este orden no produce interbloqueos (debido a que no hay competencia por los recursos), pero tampoco tiene paralelismo. Además de solicitar y liberar recursos, los procesos realizan cálculos y operaciones de E/S. Cuando los procesos se ejecutan en forma secuencial, no hay posibilidad de que mientras un proceso espera la E/S, otro pueda utilizar la CPU. Por ende, ejecutar los procesos estrictamente en forma secuencial puede no ser óptimo. Por otra parte, si ninguno de los procesos realiza operaciones de E/S, es mejor el algoritmo del trabajo más corto primero que el algoritmo por turno rotatorio (round-robin), por lo que en ciertas circunstancias tal vez lo mejor sea ejecutar todos los procesos en forma secuencial. Ahora vamos a suponer que los procesos realizan tanto operaciones de E/S como cálculos, por lo que el algoritmo por turno rotatorio es un algoritmo de programación razonable. Las peticiones de recursos podrían ocurrir en el orden de la figura 6-4(d). Si estas seis solicitudes se llevan a cabo en ese orden, los seis gráficos de recursos resultantes se muestran en las figuras 6-4(e) a (j). Después de haber realizado la petición 4, A se bloquea en espera de S, como se muestra en la figura 6-4(h). En los siguientes dos pasos B y C también se bloquean, lo que en última instancia conduce a un ciclo y al interbloqueo de la figura 6-4(j). Sin embargo, y como ya hemos mencionado, el sistema operativo no tiene que ejecutar los procesos en un orden especial. En particular si al otorgar una petición específica se puede producir un interbloqueo, el sistema operativo simplemente puede suspender el proceso sin otorgar la solicitud (es decir, no sólo programar el proceso) hasta que sea seguro. En la figura 6-4, si el sistema operativo supiera acerca del interbloqueo inminente, podría suspender a B en vez de otorgarle el recurso S. Al ejecutar sólo A y C, obtendríamos las peticiones y liberaciones de la figura 6-4(k) en vez de la figura 6.4(d). Esta secuencia produce los gráficos de recursos de las figuras 6-4(l) a (q), que no producen un interbloqueo. Después del paso (q), se puede otorgar el recurso S al proceso B, debido a que A ha terminado y C tiene todo lo que necesita. Aun si B se hubiera bloqueado al solicitar a T, no puede ocurrir un interbloqueo. B sólo esperará hasta que C termine.

440

INTERBLOQUEOS A Solicitud R Solicitud S Liberación R Liberación S

B Solicitud S Solicitud T Liberación S Liberación T

(a) 1. A solicita a R 2. B solicita a S 3. C solicita a T 4. A solicita a S 5. B solicita a T 6. C solicita a R interbloqueo

CAPÍTULO 6 C Solicitud T Solicitud R Liberación T Liberación R

(b)

(c)

A

B

C

A

B

C

A

B

C

R

S

T

R

S

T

R

S

T

(d)

(e)

(f)

(g)

A

B

C

A

B

C

A

B

C

R

S

T

R

S

T

R

S

T

(h)

(i) (j)

1. A solicita a R 2. C solicita a T 3. A solicita a S 4. C solicita a R 5. A libera a R 6. A libera a S no hay interbloqueo

A

B

C

A

B

C

A

B

C

R

S

T

R

S

T

R

S

T

(k)

(l)

(m)

(n)

A

B

C

A

B

C

A

B

C

R

S

T

R

S

T

R

S

T

Figura 6-4. Un ejemplo sobre cómo puede ocurrir el interbloqueo y cómo se puede evitar.

SECCIÓN 6.3

EL ALGORITMO DE LA AVESTRUZ

441

Más adelante en este capítulo estudiaremos un algoritmo detallado para realizar decisiones de asignación que no produzcan interbloqueos. Por ahora, el punto a comprender es que los gráficos de recursos son una herramienta que nos permite ver si una secuencia d...