Una Implementacion de los semaforos de a PDF

Preview

Summary

Implementacion de semaforos en los sistemas operativos...

Description

Una Implementación de los semáforos de android para solucionar el problema de interbloqueo de procesos Jhoan Andrés Melo Pérez 20082020056 [email protected] Resumen— La interacción entre procesos que requieren un acceso a recursos compartidos genera situaciones críticas que deben ser resueltas por el sistema operativo por medio de métodos de asignación y uso de tales recursos, lo anterior teniendo en cuenta el principio de exclusión mutua y la situación de interbloqueo de procesos a la que esta, como primera condición da lugar. El presente artículo expone los términos anteriormente mencionados y especifica una solución por medio del método de semáforos en el sistema operativo Android. Abstract— The interaction between processes that require access to shared resources generated critical situations to be resolved by the operating system through methods such allocation and use of resources, the above taking into account the principle of mutual exclusion and deadlock of processes to which this leads. This paper describes the above terms and specifies a solution through xxxxxxx algorithm implemented in the OS xxxxx.

tópicos de exclusión mutua e interbloqueo de procesos, su definición, algunas soluciones establecidas y finalmente una implementación de la solución mediante semáforos en Android. II.

CONDICIONES DE CARRERA

Este término hace referencia a las condiciones que surgen cuando dos o más procesos intentan acceder a un espacio de memoria o recurso en el mismo instante de tiempo, un ejemplo típico es el de un sistema de reservación de Aerolínea que busca asignar el ultimo asiento del avión a varios clientes solicitantes, en los sistemas de cómputo podemos ilustrar la situación mediante el conflicto entre dos procesos que buscan ocupar una misma posición de memoria[2] instantáneamente, las variables asociadas a las posiciones de memoria son usadas por ambos procesos y al final alguno de los valores o estados de las variables se perderá y una de las salidas de los procesos jamás se dará.

Palabras claves— Exclusion mutua, interbloqueo entre procesos, condiciones de carrera, concurrencia, sección crítica, I.

INTRODUCCIÓN

El acceso a recursos compartidos por parte de los procesos ejecutados representa uno de los problemas fundamentales a solucionar por parte de cada sistema operativo. Tal acceso implica una interacción entre procesos, interacción que puede tomar la forma de competencia o carrera por el acceso y uso del recurso requerido; en este orden de ideas el sistema operativo debe implementar mecanismos que administren y gestionen la comunicación entre procesos en busca de sincronización, y ecuanimidad. La concurrencia se define como la propiedad o capacidad que tiene un sistema de llevar a cabo dos o más acciones en progreso al mismo tiempo [1], no implica que instantáneamente se ejecuten n procesos (lo cual es paralelismo). El objetivo es que la ejecución óptima en términos de uso de recursos disponibles y disminución de tiempo necesario de ejecución de los procesos sea independiente de las limitaciones o ventajas relativas a la arquitectura de los sistemas de cómputo (como el número de procesadores, por ejemplo).En el presente artículo se exponen los

Fig. 1. Dos procesos buscan acceder a una misma posición de memoria en una cola destinada a impresión por ejemplo, sal y ent son variables que almacenan la dirección del archivo a salir a imprimir y a la nueva cabeza de la cola respectivamente [3].

Fig 2. Condicion de carrera, accediendo a un recurso compartido. III. EXCLUSIÓN MUTUA A principios de los años 60 (1962) fue propuesto el problema de la exclusión mutua [4], cuando un proceso accede un recurso lo debe hacer de tal manera que excluya a los otros que también requieren su uso simultáneamente, es un mecanismo de protección de recursos que deben emplear los procesos, se denomina sección critica cuando un proceso se encuentra haciendo uso de un recurso de manera exclusiva, los demás procesos en espera se encuentran en sección no critica. En el ejemplo de acceso a posiciones de memoria en el tópico de condiciones de bloqueo, se debe considerar que hay dos operaciones: lectura y escritura, la condición de exclusion mutua establece que ambas tareas deben estar protegidas, en una base de datos el acceso para lectura no representa una situación problemática, pero la actualización o escritura de datos debe excluir a los demás tareas de escritura y lectura de la base. La exclusión mutua existe para solucionar los problemas de condiciones de carrera, todos los procesos tiene tareas extrínsecas e intrínsecas, estas últimas no requieren el uso de recursos compartidos, las primeras si, cuando un proceso hace uso de estos recursos se dice que está en sección crítica, la cual se define como una porción de código que garantice la exclusion mutua, mientras un proceso está en sección critica los demás están en sus procesos internos, logra esto todo el tiempo de progreso de los procesos es lo que evita las condiciones de carrera.

Fig. 2. Realizando exclusion mutua por medio de secciones críticas [5].

El código que realice esta tarea debe hacerlo de tal forma que [6]: 1.

Cuando un proceso se encuentre en su sección crítica ningún otro proceso tendrá acceso a su sección crítica, no hay secciones críticas simultáneas.

2.

Cuando ningún proceso está en su sección crítica, cualquier proceso que requiera entrar en su sección crítica debe poder hacerlo.

3.

Cuando varios procesos compiten para entrar en su sección critica, se debe permitir a uno (uno solamente) entrar en su sección critica durante un tiempo finito.

4.

Siempre debe haber un proceso apto a acceder a su sección crítica.

III. SOLUCIONES QUE ABORDAN EL PROBLEMA DE SECCION CRÍTICA Y EXCLUSION MUTUA

Algoritmo de Dekker El primer método propuesto para evitar las condiciones de carrera y garantizar la exclusión mutua de procesos mediante el uso de secciones criticas fue el algoritmo de Dekker, Edsger Dijkstra implemento probó el algoritmo propuesto y lo generalizo para un numero de procesos mayor a 2 que era para el cual se había escrito[7]. Respecto a esta generalización algunos autores afirman que no es “justa” en el sentido de que todos los procesos no tienen equiprobabilidad de acceder a la sección critica como debería ser[8]. La idea básica detrás de la aplicación del algoritmo de Dekker para dos procesos es que un proceso entre inmediatamente a la sección critica cuando el otro proceso no está compitiendo para ingresar a esta[9]. Intento 1 int processNumber = 0; void processZero() { while (TRUE) do { while (processNumber == 1) do {} //spin-wait CriticalRegionZero; processNumber = 1;

OtherStuffZero; } } void processOne() { while (TRUE) do { while (processNumber == 0) do {} //spin-wait CriticalRegionOne; threadNumber = 0; OtherStuffOne; }

} [10] La variable processNumber indica el número de proceso que se alterna en la ejecución 0 para el proceso cero (Zero) o 1 para el proceso 1. Para el método processszero el ciclo while que compara la condición processNumber ==1 “pone a esperar el progreso del proceso 1, dando acceso al proceso 0 a su región critica CriticalRegionZero, una vez termina esta sección critica la variable processNumber cambia su valor a 1, se realizan las tareas de proceso 0 OtherStuffZero, el método processsOne ejecuta las mismas instrucciones pero obviamente en busca de dejar en sección critica al proceso1, de esta forma se observa el concepto de bandera la cual en este caso es processNumber , en esta variable está basada la lógica del primer intento. Se genera una dependencia estricta entre procesos lo cual lleva a que los más lentos “retrasen ” a los mas Intento 2 int process0inside = 0; int process1inside = 0; void process Zero() { while (TRUE) do { while (Thread1inside) do {} // spin-wait process0inside = 1; CriticalRegionZero; process0inside = 0; OtherStuffZero; } } void process One() { while (TRUE) do { while (Thread0inside) do {} process1inside = 1; CriticalRegionOne; process1inside = 0; OtherStuffOne; } }[11] Este intento busca solucionar el problema de la sincronización de los dos procesos por medio de dos indicadores o banderas para cada proceso estos son process0inside y process1inside en

el pseudocódigo considerado, antes de ingresar a su sección critica cada proceso pregunta si el otro está en ejecución, si es así se ejecuta una espera circular hasta que acabando el otro proceso su ejecución el actual pueda entrar a sección critica primero dándole el valor 1 a su bandera correspondiente, luego ejecutando su sección crítica y finalmente actualizando su bandera a 0. El algoritmo no soluciona el problema en general y puede llevar a una violación al principio de Exclusion mutua, los dos procesos podría entrar a sección critica, si se da la siguiente secuencia[12] en los pasos 5 y 6 la exclusión mutua se rompe: 1. 2. 3. 4. 5. 6.

proceso 0 evalúa process1inside en el condicional del while proceso 0 encuentra que process1inside == 0 (la condición resulta FALSE). Proceso 1 evalúa process0inside en el condicional del while proceso 1 encuentra que process0inside == 0 (la condición resulta FALSE). Proceso 0 ingresa a la sección crítica. Proceso 1 ingresa a la sección crítica

Intento 3 A diferencia de la solución anterior en la cual los procesos se comportan de una manera “egoísta” (ya que cada uno usa una bandera para indicar que entrará en su sección crítica) el tercer intento considera en cada progreso del proceso si el otro “desea ingresar ” a sección critica.

int process0WantsToEnter = 0; int process1WantsToEnter = 0; void processZero() { while (TRUE) do { process0WantsToEnter = 1; while (process1WantsToEnter) do {} // spin wait CriticalRegionZero; process0WantsToEnter = 0; OtherStuffZero; } } void processOne() { while (TRUE) do { process1WantsToEnter = 1; while (process0WantsToEnter) do {} CriticalRegionOne; process1WantsToEnter = 0; OtherStuffOne; } }

Aunque parece similar al intento anterior, se debe observar claramente como la banderas process0WantsToEnter o process1WantsToEnter toman el valor correspondiente antes de evaluar la condición de si el otro proceso requiere entrar a sección critica, si es así se queda en espera de lo contrario procede a su región crítica y finalmente cambia su indicador a 0. Se puede presentar la situación en que los dos queden en una especie de espera de cortesía donde cada uno aguarda para que el otro, un caso clásico de interbloqueo ambos quedan a la espera de que uno de los 2 cambie su indicador de querer entrar a la sección critica a false. Intento 4 En el cuarto intento se definen unas instrucciones en el ciclo de espera (spin watt), las cuales alternan el “deseo” de entrar a sección crítica de cada proceso, por medio de un retardo, en busca de que el otro proceso ingrese si los dos se encuentran en espera simultánea, evitando la situación de interbloqueo. int process0WantsToEnter = 0; int process 1WantsToEnter = 0; void process Zero() { while (TRUE) do { process 0WantsToEnter = 1; while (process 1WantsToEnter) do { // not quite a spin-wait process 0WantsToEnter = 0; delay(someRandomCycles); process 0WantsToEnter = 1; } CriticalRegionZero; process 0WantsToEnter = 0; OtherStuffZero; } } void processOne() { while (TRUE) do { process1WantsToEnter = 1; while (process0WantsToEnter) do { process1WantsToEnter = 0; delay(someRandomCycles); Thread1WantsToEnter = 1; } CriticalRegionOne; process1WantsToEnter = 0; OtherStuffOne; } }

Se puede presentar el caso en el que el tiempo de los dos retardos sea el mismo, situación que daría lugar al abrazo mortal del tercer intento, pero al respecto se puede decir que la probabilidad de que ocurra este evento es mínima. Sin embargo es posible que se presente una sucesión de eventos en al que un proceso no obtenga entrada a sección critica, aunque se den las condiciones para que uno de los procesos abandonara sección critica el proceso entrante no lograra ingresar, cayendo este en inanición. La generalización de Dijkstra El matemático de Rotterdam propuso una implementación del algoritmo para más de 2 procesos, aunque él mismo no considero su solución como una generalización al algoritmo de Dekker.

Fig. 4 Algoritmo de Dijkstra para n procesos[13] En este algoritmo se debe observar que la variable turn (cambio) no se ha inicializado, y permanece sin cambios después de cada ejecución en sección crítica. Esta solución no está exenta de fallas y también es susceptible a generar inanición. Se da prioridad de acceso al proceso más reciente, si este proceso (que tiene el turno en sección critica actualmente) está continuamente interesado en entrar en sección critica conducirá a inanición. [14] Otras generalizaciones Martin Alain propuso en los años 80 otra generalización para el algoritmo de Dekker, Martin indica que los procesos están en alternancia

continua entre sección crítica y no critica, estas dos acciones se dejan sin especificar más, aparte del hecho de que ambas acciones dejan las variables de control sin cambios . Knuth proporciona una modificación al algoritmo de Dijkstra que garantizaba el acceso de un proceso en

2

N −1

−1

La solución de Peterson G.L. Peterson en 1981 ideó un algoritmo más simple parta solucionar el problema que plantea la exclusión mutua, el último intento de Dekker quedaba obsoleto [17].

turnos.

DeBruijn planteó otra solución para proporcionar acceso, dentro de

1 N (N−1) 2

cambios.

Eisenber y McGuire propusieron una solución que garantiza el acceso a sección crítica de un proceso en no más de N-1 vueltas[15]. Justifican su propuesta indicando que 1.

2.

3.

Existe un área protegida dentro del algoritmo que incluye la sección crítica y dentro del cual no hay dos procesos simultáneos. El sistema caer en un bloqueo (es decir, cuando uno o varios procesos están compitiendo por la entrada a su sección crítica, la decisión de determinar que algún proceso puede entrar no puede posponerse indefinidamente). Un proceso no puede ser bloqueado (es decir, la decisión de determinar la entrada de un proceso a su sección crítica no puede posponerse indefinidamente.

Fig. 5. Algoritmo de Peterson para lograr Exclusion mutua

El término de Busy Wait hace referencia al ciclo en el que ingresa un proceso en el cual una instrucción comprueba el valor de una variable y regresa de nuevo a esa instrucción debido al valor actual de la variable [16].

Para este ejemplo se definen 2 procesos, l variable turno nos indicará de quien es el turno, la variable entera INTERESADO es 0 al iniciar, el proceso es 1 o 0, la variable OTRO indica el número del otro proceso, la variable INTERESADO cambia su valor a TRUE (el proceso actual quiere ingresar a sección crítica), asigna la bandera (turno) al proceso que se quiere ejecutar se realiza una espera en caso de que se dé la condición de que aunque el turno sea del proceso actual el otro proceso este interesado en entrar (interesado[otro]=TRUE)

Se denomina también algoritmo del panadero o panadería, ya que simula los eventos de una panadería, el cliente ingresa, luego obtiene un turno o número de servicio, procede a esperar su turno, cuando es llamado recibe el servicio solicitado y cuando se le termina de brindar su servicio abandona la panadería.

Finalmente el algoritmo ejecuta salir_region (int proceso) para indica que el proceso actual ya no está interesado en ingresar a su sección crítica, el valor de la variable turno se sobrescribe, se toma el último valor asignado. Al llegar al ciclo while el turno es del proceso actual y el otro no está interesado en acceder por tanto se ejecuta la

Algoritmo de Lamport El algoritmo de Lamport se propuso con el fin de eliminar la espera activa (Busy Wait) en el acceso de los procesos además de usar criterios de prioridad para el acceso.

sección critica del proceso actual y se excluye el otro proceso.

2.

IV INTERBLOQUEO

3.

Cuando dos o más procesos se encuentran en progreso de manera simultánea y requieren uno o varios recursos se pueden presentar situaciones en las que ambos procesos requieran el uso de un mismo recurso o más recursos, supóngase que hay dos procesos A y B que están ambos en la tarea de grabar un documento en un CD , A empieza haciendo uso del scanner (su sección critica) y B elige iniciar usando el grabador de CD, liego A requiere el grabador, pero B no lo libera y complicando la situación solicita el Scanner, ahora los dos procesos están interbloqueos. Los programas que hacen uso de varias secciones críticas son propensos a sufrir interbloqueos. Esta situación se puede presentar en muchos escenarios y sistemas, bases de datos, redes de computo (un ejemplo clásico es el de la impresora compartida). En síntesis es una situación en la que uno o más procesos están esperando un evento que nunca se producirá. La situación más común es cuando dos procesos cada uno con un objeto de sincronización que el otro proceso quiere y no hay forma de que un proceso libere el objeto que tiene para permitir que el otro proceso continúe.

4.

Retención y espera: Hilos que ya están reteniendo algunos recursos pueden intentar mantener nuevos recursos Ninguna condición de preferencia (No expropiación) Una vez que el proceso se encuentra reteniendo un recurso, esos recursos sólo puede ser removido cuando el proceso que lo está reteniendo voluntariamente libera el recurso, no hay apropiación de recurso por parte de un proceso “entrante”. Espera Circular. Puede existir una cadena circular de procesos que solicitan los recursos que están en uso por parte del próximo proceso en la cadena.

“Ninguno de los procesos se puede ejecutar, ninguno de ellos puede liberar recursos y ninguno puede ser despertado”[20]

V SOLUCIONES AL PROBLEMA DE INTERBLOQUEO Existen tres tipos de soluciones para el problema de Interbloqueo: 1. 2. 3.

A nivel de software, dentro de estas se puede hacer referencia a los algoritmos de Dekker y Peterson. A nivel de programación y Sistema Operativo A nivel de Hardware haciendo uso de interrupciones (truncando los ciclos de la CPU, por ejemplo) en cada proceso para inhabilitar procesos.

VI. DETECCION Y RECUPERACION DE INTERBLOQUEO Existen dos casos de detección de interbloqueos: Cuando la cadena de procesos solo tiene un recurso de cada tipo disponible, Fig 6. Gráficos de asignación de recursos. (a) Contención de un recurso. (b) Petición de un recurso. (c) Interbloqueo[18]. Condiciones de Coffman En 1970 Coffman y Shoshani establecieron las 4 condiciones para que se dé la situación de interbloqueo entre procesos[19]. 1.

Exclusion Mutua

Fig 7. (a) Un gráfico de recursos. (b) Un ciclo extraído de (a)

Las letras A a G representan los procesos y las letras R a W los recursos, del grafo se pueden extraer las interacciones entre procesos y recursos y se identifica rápidamente el interbloqueo (b) [21]. La detección cuando hay varios recursos de cada tipo es diferente y se hace uso de matrices para representar los vectores de procesos y de recursos, en los algoritmos que se implementan para realizar esta detección se realizan comparaciones entre los elementos de los dos vectores. Si al final luego de marcar los procesos que no incurren en interbloqueos queda alguno sin marcar se ha detectado un interbloqueo. El algoritmo de detección de interbloqueos se muestra a continuación. 1. Buscar un proceso desmarcado, Pi para el que la i-pésima fila de R sea menor o igual que A. 2. Si se encuentra dicho proceso, agregar la ipésima fila de C a A, marcar el proceso y regresar al paso 1. 3. Si no existe dicho proceso, el algoritmo termina

el programa finaliza obviamente no se presentó ningún interbloqueo. Finalmente está el análisis estático, en el cual no se requieren pruebas o ejecuciones del pro...