Guia3Fundamentos Sistemas OperativosII

8/8/2019 Guia3Fundamentos Sistemas OperativosII

1/30

Proceso

Un proceso es un programa en ejecucin, los procesos son gestionados por el sistema operativo y estnformados por:

y Las instrucciones de un programa destinadas a ser ejecutadas por el microprocesador.

y Su estado de ejecucin en un momento dado, esto es, los valores de los registros de la CPU paradicho programa.

y Su memoria de trabajo, es decir, la memoria que ha reservado y sus contenidos.

y Otra informacin que permite al sistema operativo su planificacin.

Esta definicin vara ligeramente en el caso de sistemas operativos multihilo, donde un proceso consta de unoo ms hilos, la memoria de trabajo (compartida por todos los hilos) y la informacin de planificacin. Cada hiloconsta de instrucciones y estado de ejecucin.

Los procesos son creados y destruidos por el sistema operativo, as como tambin este se debe hacer cargode la comunicacin entre procesos, pero lo hace a peticin de otros procesos. El mecanismo por el cual unproceso crea otro proceso se denomina bifurcacin (fork). Los nuevos procesos pueden ser independientes yno compartir el espacio de memoria con el proceso que los ha creado o ser creados en el mismo espacio dememoria.

En los sistemas operativos multihilo es posible crear tanto hilos como procesos. La diferencia estriba en queun proceso solamente puede crear hilos para s mismo y en que dichos hilos comparten toda la memoriareservada para el proceso.

PCB (Bloque de Control del Proceso)

Conjunto de datos en donde se incluyen el estado en cada momento, recursos utilizados, registros, etc.El PCB pretende cubrir:

Localizar la informacin sobre el proceso del sistema operativo. Mantener registrados los datos del proceso en caso de tener que suspender su ejecucin.

La informacin contenida en el bloque de control es el siguiente:

Estado del proceso(Informacin relativa al contenido del contador de programa) Estadsticas de tiempo y ocupacin de recursos(Planificacin del procesador) Recursos en uso(unidades de entrada/salida) Archivos en uso Privilegios


2/30

Tipos de Procesos

Independiente: Los procesos no se comunican entre si. Cooperativo: Los procesos realizan su funcin de modo independiente y se sincronizan

puntualmente para realizar alguna accin. (Proyecto SETI) Competitivo: Los procesos se sincronizan y comunican entre si para competir por los recursos del

sistema

Estados de un proceso

Los bloques de control de proceso se almacenan en colas cada una de las cuales representa un estadoparticular de los procesos.Los estados de los procesos son internos del sistema operativo y transparente para el usuario. Para el usuariocomn los procesos siempre estarn en ejecucinLos estados de los procesos se pueden dividir en 2 tipos:

1) Activos: Son todos aquellos procesos que compiten con el procesador. Ejecucin: Estado que se encuentra en un proceso, cuando tiene el control del procesador. Preparado: Son todos aquellos procesos que estn dispuestos a ser ejecutados, pero no lo estn por

alguna causa. Bloqueado: Son todos aquellos procesos que no pueden ejecutarse por necesitar de algn recurso

(e/s).

2) Inactivo: Son procesos que an no han terminado su trabajo por diferentes causas. Pero pueden volver

activarse nuevamente sin tener que comenzar desde el principio.

Suspendido Bloqueado: Proceso que est suspendido en espera, que ha desaparecido por una

causa de bloqueo.

Suspendido Preparado:Proceso suspendido, pero no tiene causas para estar bloqueado.

Transiciones de un Estados

Puede cambiar de estado varias veces a lo largo de su existencia

Comienzo de la ejecucin: Todo proceso comienza al ser dada la orden de ejecucin. Paso a Estado de Ejecucin:Se encuentra en espera de ser ejecutado.


3/30

Paso a Estado Bloqueado: Proceso que se encuentra en ejecucin y solicita unaoperacin externa(unidad de entrada/salida), teniendo que esperar a que dicha ejecucinfinalice pasara al estado bloqueado.

Paso a estar Preparado: Este proceso debe contener: Orden de ejecucin de los procesos Proceso debe pasar a estado preparado Luego el proceso pasa a estar activado

Paso a suspendido Bloqueado: Si un proceso est bloqueado y el S.O. recibe la orden desuspendido pasa a estar suspendido bloqueado.

Paso a Estado Suspendido Preparado: Este proceso debe contener: Suspensin de un proceso para pasar a preparados. Suspensin de un proceso en ejecucin, con lo cual pasa a la cola de suspensin

preparado.

Desbloqueo de un proceso suspendido.

Operaciones sobre procesos

Un proceso es simplemente, un programa en ejecucin que necesita recursos para realizar su tarea: tiempode CPU, memoria, archivos y dispositivos de E/S. El SO es el responsable de:

y Crear: Se produce con la orden de ejecucin de programa y suele necesitar varios argumentos,como el nombre y la prioridad del proceso. Aparece en este momento el PCB que ser insertado enla cola de procesos preparados. La creacin de un proceso puede ser de dos tipos

Jerrquica: en ella cada proceso que se crea es hijo del proceso creador y hereda elentornodeejecucin de su padre

No jerrquica: cada proceso creado por otro proceso se ejecuta independientemente de sucreador con u entorno diferente. Es un tipo de creacin que no suele darse en sistemasoperativos actuales

y Destruir : Se trata de la orden de eliminacin del proceso con la cual el sistema operativo destruyeel PCB

y Suspender: Es una operacin de alta prioridad que paraliza un proceso que puede ser reanudadoposteriormente. Suele darse en ocasiones de mal funcionamiento o sebrecarga del sistema

y Reanudar: Trata de activar un proceso que ha sido previamente suspendidoy Cambiarprioridad:

y Temporizar la ejecucin: Hace que un determinado proceso se ejecute cada cierto tiempo(segundos, minutos, horas) por etapas o de una sola vez, pero trascurrido un perodo de tiempo fijo

y Despertar:Es una forma de desbloquear un proceso que habr sido bloqueado previamente portemporizacin o cualquier otra causa


4/30

Planificacin del procesador

Introduccin

En este captulo se estudian las distintas polticas y mecanismos ms comunes que poseen los

sistemas operativos actuales para realizar la gestin del procesador que se conoce con el nombre de

planificacin, cuyo objetivo principal es el de dar un buen servicio a todos los procesos que existan en unmomento dado en el sistema.

En general, se distinguen varios niveles de planificacin, como se refleja en la Figura.

Planificacin a largo plazo (planificador de trabajos): Decide cul ser el prximo trabajo que se va a

ejecutar. Este nivel slo existe en los sistemas de proceso por lotes, donde la decisin se basa en las

necesidades de recursos y su disponibilidad. En los sistemas de tiempo compartido tiene como nica misin

cargar los programas que se desean ejecutar en memoria. Este nivel es, por tanto, el encargado de crear los

procesos.

y Planificacin a medio plazo (planificador de swapping): Decide si un proceso que est en

ejecucin en estado bloqueado o suspendido debe ser extrado de la memoria temporalmente.

Posteriormente, cuando el sistema se encuentre ms descargado, devolver dicho proceso a la

memoria y al estado de ejecucin. Este nivel, por tanto, gestiona los procesos suspendidos en

espera de algn recurso no disponible en el momento de la suspensin.

y Planificacin a corto plazo (planificador del procesador): Es el encargado de decidir cmo y

cundo tendr acceso al procesador un proceso que est preparado para utilizarlo. Por tanto, lleva a

cabo las funciones de la multiprogramacin, estando siempre residente en memoria y ejecutndose

con mucha frecuencia; por ello, debe ser de ejecucin muy rpida. En este nivel es donde se debe

dar un buen servicio a los procesos interactivos para que el usuario no perciba, o lo haga en pequeo

grado, que est compitiendo por el procesador junto con otros usuarios.

Objetivos

Las polticas de planificacin intentan cubrir los siguientes objetivos:

y Justicia:La poltica debe ser lo ms justa posible con todo tipo de procesos, sin favorecer a unos y

perjudicar a otros.

y Mxima capacidad de ejecucin: Debe dar un servicio aceptable para que todos los trabajos se

realicen lo ms rpidamente posible. Esto se logra disminuyendo el nmero de cambios de proceso.


5/30


6/30

A partir de los dos valores anteriores, podemos establecer una relacin que nos permite evaluar la actuacin

de la poltica establecida en lo que se denomina ndice de servicio (I).

I = t / T

Este ndice representa el tanto por uno de tiempo que el proceso est en ejecucin respecto al tiempo de vida

del mismo en el sistema.

En caso de que slo exista un proceso ejecutndose en el sistema, segn el valor del ndice de servicio,

podemos decir que:

Cuando I sea prximo a la unidad, el proceso est limitado por proceso.

Si I tiene un valor bajo prximo a 0, el proceso estar limitado por entrada/salida.

En los casos ms usuales en los que existe ms de un proceso en el sistema, no podemos hacer las

consideraciones anteriores puesto que puede desvirtuarse el verdadero comportamiento del sistema. Por este

motivo se establecen las mismas medidas, pero con valores medios obtenidos al considerar el conjunto de

procesos presentes. Estas sern las medidas que nos reflejarn el verdadero comportamiento del sistema.

Las medidas a las que nos referimos son:

y Tiempo medio de servicio.

y Tiempo medio de espera.

y Eficiencia (ndice medio de servicio).

Adems de las anteriores, en la planificacin del procesador suelen emplearse otras dos medidas de

inters:

y Tiempo del ncleo: Es el tiempo consumido por el ncleo del sistema operativo para tomar las

decisiones de planificacin del procesador, donde se incluyen los tiempos de cambio de contexto y

de proceso.

y Tiempo de inactividad (Idle): Es el tiempo consumido cuando la cola de procesos preparados est

vaca y por tanto no puede realizarse ningn trabajo productivo.

Algoritmos de Planificacin

El planificador del procesador tiene como misin la asignacin del mismo a los procesos que estn

en la cola de procesos preparados. Esta cola es alimentada desde dos puntos distintos:

y Cada vez que un usuario inicie la ejecucin de un programa, el planificador a largo plazo recibe la

orden de ejecucin, crea el proceso y lo pasa al planificador a corto plazo, colocndose en la cola de

procesos preparados.

y Cuando un proceso deja de estar en estado de ejecucin y no existen causas para su bloqueo, o

deja de estar bloqueado, pasa nuevamente a la cola de procesos preparados.

Por otro lado, cuando un proceso termina su ejecucin, deja de existir para el planificador.

Las polticas de planificacin se agrupan en:

y Polticas apropiativas: Son las que producen un cambio de proceso con cada cambio de contexto;

es decir, el proceso que est haciendo uso del procesador puede ser temporalmente suspendido y

permitir que otro proceso se apropie del procesador. Se utilizan en sistemas operativos con tiempo

compartido y tiempo real.


7/30

y Polticas no apropiativas: Son aquellas en las que un proceso no abandona nunca el procesador

desde su comienzo hasta su fin. Se utilizan en sistemas de proceso por lotes.

En los sistemas operativos comerciales existen diversas polticas de planificacin, de las cuales

veremos algunas a continuacin, puestas en prctica a travs de algoritmos que en ningn caso son

perfectos. Recordemos que los objetivos y criterios pueden ser contradictorios entre s, de manera que si

favorecemos a un tipo de procesos, normalmente perjudicaremos a otros.

Para el estudio de las diferentes polticas nos basaremos en la situacin de un grupo de procesos

existentes en un sistema, cuyos datos se encuentran en la Tabla y su representacin grfica en la Figura.

Adems de figurar el instante de entrada en el sistema, tambin se ha representado el tiempo de

servicio de cada proceso, es decir, el tiempo que necesita cada uno de ellos para ejecutarse si fuera el nico

presente en el sistema. Por otro lado, supondremos que estos procesos no necesitan realizar operaciones de

entrada/salida (aunque esto sea una utopa) para facilitar el estudio.

Primero en llegar, primero en ser servido (FCFS)

En esta poltica de planificacin FCFS (First Come, First Served), el procesador ejecuta cada proceso

hasta que termina; por tanto, los procesos que entren en cola de procesos preparados permanecern

encolados en el orden en que lleguen hasta que les toque su ejecucin (Figura 4.3). Este mtodo se conoce

tambin como "primero en entrar, primero en salir" (First Input, First Output - FlFO).


8/30

Se trata de una poltica muy simple y sencilla de llevar a la prctica, pero muy pobre en cuanto a su

comportamiento. En la Tabla se muestran los datos de los procesos para esta planificacin, y en la Figura

puede verse cmo despacha FCFS los procesos del ejemplo propuesto, donde las partes sombreadas indican

el tiempo que ha estado cada proceso en espera de acceder al procesador.

Podemos observar que el ndice de servicio mejora cuantos ms largos son los procesos. Es decir,

los procesos cortos que entren en el sistema despus de uno o varios largos tendrn que esperar un perodo

de tiempo relativamente largo hasta su ejecucin.

La cantidad de tiempo de espera de cada proceso depende del nmero de procesos que se

encuentren en cola en el momento de su peticin de ejecucin y del tiempo que cada uno de ellos tenga en

uso al procesador, y es independiente de las necesidades de ejecucin del propio proceso.

Las caractersticas de esta poltica son las siguientes:

y No es apropiativa.

y Es justa, aunque los procesos largos hacen esperar mucho a los cortos.

y Es una poltica predecible.

y El tiempo medio de servicio es muy variable en funcin del nmero de procesos y su duracin.

Round-Robin (RR)

Esta poltica, cuya traduccin podra ser asignacin cclica o planificacin en rueda, es una mejora de

la FCFS. Trata de ser ms justa en cuanto a la respuesta tanto de los procesos cortos como de los largos.

Consiste en conceder a cada proceso en ejecucin un determinado perodo de tiempo q (quantum),

transcurrido el cual, si el proceso no ha terminado, se le devuelve al final de la cola de procesos preparados,

concedindose el procesador al siguiente proceso por su correspondiente quantum


9/30


10/30

A continuacin se repite la planificacin RR para un valor de quantum 3 y con las mismas

condiciones que en el caso anterior. La Tabla y la Figura representan los datos y el grfico, respectivamente,

del ejemplo propuesto para este valor.

En este caso el tiempo de servicio T se mantiene prcticamente constante. Se puede observar que el

tiempo de espera E crece de acuerdo con el tiempo de ejecucin de cada proceso.

Las caractersticas de esta poltica de planificacin son:

y Baja sobrecarga si el cambio de contexto es eficiente y los procesos siempre estn en la memoria

principal.

El tamao ptimo del quantum depende de:

y El tipo de sistema.

y Las cargas que vaya a soportar el sistema.

y El nmero de procesos en el sistema y su tipo.

y Es la poltica ms utilizada para tiempo compartido.

y Ofrece un ndice de servicio uniforme para todos los procesos. Es una poltica apropiativa.

El siguiente proceso, el ms corto (SJN)

Hemos visto que la poltica RR mantiene constante el ndice de servicio de los procesos cortos

basndose en la apropiacin del procesador. El mtodo SJN (Shortest Job Next) es una poltica de

planificacin no apropiativa que trata de cubrir los mismos objetivos que la RR.

Esta poltica toma de la cola de procesos preparados el que necesite menos tiempo de ejecucinpara realizar su trabajo. Para ello debe saber el tiempo de procesador que necesita cada proceso, lo cual es

tarea nada fcil, pero posible a travs de diversos mtodos como pueden ser la informacin suministrada por

el propio usuario, por el propio programa, basndose en la historia anterior (heurstica), etc.

El tiempo de servicio T en esta poltica es bueno para los procesos cortos, saliendo perjudicados los

procesos largos.


11/30

En la Figura y la Tabla pueden verse el grfico y los datos, respectivamente, del ejemplo propuesto

en esta poltica.

Las caractersticas de esta poltica de planificacin son las siguientes:

y No es apropiativa.

y El tiempo de espera aumenta de acuerdo con la longitud de los procesos, pero el tiempo medio de

espera con respecto a otras polticas es ptimo.

y Es poco predecible.

y No es justa con los procesos largos.

y Buen tiempo de servicio.

y Resulta difcil de poner en prctica por los datos que necesita para realizarse la planificacin.

Prximo proceso, el de tiempo ms corto (SRT)

La poltica SRT es una mezcla de los 2 mtodos anteriores y trata de obtener las ventajas de ambos.

Para ello esta tcnica cambia el proceso que est en ejecucin cuando se ejecuta un proceso, con exigencia

de tiempo de ejecucin total menor que el que se est ejecutando en el procesador. El valor del tiempo de

respuesta medio de los procesos largos mejora con respecto a SJN.

Esta poltica presenta las siguientes caractersticas

y Es una variante de SJN, para hacerla apropiativa.

y Puede ser injusta ya que un proceso corto puede echar a uno largo que est haciendo uso del

procesador y que adems est terminando.y Presenta una mayor sobrecarga.

y Excelente tiempo medio de servicio

y Muy eficiente

Prioridad

En esta poltica se asocia a cada proceso una prioridad, de manera que el procesador se asigna al

proceso de mayor prioridad.


12/30

Las prioridades pueden ser definidas interna o externamente. En el primer caso, el sistema operativo

se basa en una serie de informaciones medibles para el clculo y asignacin de dichas prioridades (tiempo

necesitado de procesador, necesidad de memoria, etc.).

El principal problema de esta poltica es el bloqueo o postergacin indefinida, ya que un proceso de

baja prioridad puede estar esperando su turno indefinidamente. Para evitarlo se suele emplear lo que se

denomina envejecimiento de las prioridades, que aumenta gradualmente las prioridades de los procesos que

estn a la espera de utilizar el procesador.

Cualquier algoritmo basado en esta poltica puede ser apropiativo o no apropiativo. En el primer caso,

un proceso puede ser retirado del procesador si aparece otro de mayor prioridad en la cola de procesos

preparados.

El comportamiento de esta poltica como apropiativa puede verse grficamente, para el ejemplo

propuesto, en la Figura, y los datos en la Tabla

.

Colas mltiples

Cuando los procesos que van a ser ejecutados en una computadora se pueden agrupar en distintos

grupos, podemos asignarlos a diferentes colas, cada una con distinta planificacin, para darle a cada una de

ellas la que realmente necesita.

Esta poltica divide a la cola de procesos preparados en varias colas separadas, de manera que los

procesos se asignan a una determinada cola segn sus necesidades y tipo.

Para determinar en cada caso qu colase las que suministrara un proceso para que acceda al

procesador cuando este deje a otro anterior, ser controlada por un algoritmo de planificacin entre las colas,

que normalmente es apreciativo de prioridad fija.


13/30

Principiosgenerales de la Concurrencia

En un sistema multiprogramado con un nico procesador, los procesos se intercalan en el tiempo aparentando

una ejecucin simultnea. Aunque no se logra un procesamiento paralelo y produce una sobrecarga en los

intercambios de procesos, la ejecucin intercalada produce beneficios en la eficiencia del procesamiento y en

la estructuracin de los programas.

La intercalacin y la superposicin pueden contemplarse como ejemplos de procesamiento concurrente en un

sistema monoprocesador, los problemas son consecuencia de la velocidad de ejecucin de los procesos que

no pueden predecirse y depende de las actividades de otros procesos, de la forma en que el sistema

operativo trata las interrupciones surgen las siguientes dificultades:

y Compartir recursos globales es riesgoso

y Para el sistema operativo es difcil gestionar la asignacin ptima de recursos.

Las dificultades anteriores tambin se presentan en los sistemas multiprocesador.

El hecho de compartir recursos ocasiona problemas, por esto es necesario proteger a dichos recursos.

Los problemas de concurrencia se producen incluso cuando hay un nico procesado

Paralelismo

El paralelismo, supone la ejecucin simultanea de varios procesos. Para implementar el paralelismo se

necesita u hardware adecuado (se necesita de varios procesadores). En caso de tener un nico procesador,

se puede simular mediante una ejecucin entrelazada y si el sistema es suficientemente rpido el usuario no

se entera. El paralelismo indica ejecucin simultnea, por lo tanto, es un caso concreto de concurrencia. Se

pueden sacar las siguientes conclusiones

y El paralelismo es un caso particular de la concurrencia

y Sin embargo, concurrencia no implica paralelismo.

y El paralelismo requiere un soporte fsico: varios procesadores.y La concurrencia es el caso general y el paralelismo un caso particular.

y La concurrencia (y el paralelismo) se refiere a la ejecucin de cdigo:


14/30

Se habla de paralelismo cuando ocurre la ejecucin simultnea de instrucciones:

o arquitecturas paralelaso procesamiento paraleloo algoritmos paraleloso programacin paralela

Existen varios tipos de paralelismo, como son:

y Paralelismo independiente: no existe sincronizacin explcita entre los procesos. Cada unorepresenta una aplicacin o trabajo separado e independiente. Un uso clsico de este tipo deparalelismo de dan en sistemas de tiempo compartido.

y Paralelismo de grano grueso y muy grueso: existe una sincronizacin entre los procesos pero a unnivel muy burdo. Este tipo de situacin se maneja fcilmente con un conjunto de procesosconcurrentes ejecutando en un monoprocesador multiprogramado y puede verse respaldado por unmultiprocesador con escasos cambios o incluso ninguno en el software del usuario.

y Paralelismo de grano fino: significa un uso del paralelismo mucho ms complejo que el que seconsigue con el uso de hilos. Si bien gran parte del trabajo se realiza en aplicaciones muy paralelas,este es un campo, hasta el momento, muy especializado y fragmentado, con varias solucionesdiferentes.

Labores del Sistema Operativo

Elementos de gestin y diseo que surgen por causa de la concurrencia:

1) El sistema operativo debe seguir a los distintos procesos activos2) El sistema operativo debe asignar y retirar los distintos recursos a cada proceso activo, entre estos se

incluyen:y Tiempo de procesador

y Memoria

y Archivosy Dispositivos de E/S

3) El sistema operativo debe proteger los datos y los recursos fsicos de cada proceso contra injerencias no

intencionadas de otros procesos.

4) Los resultados de un proceso deben ser independientes de la velocidad a la que se realiza la ejecucin de

otros procesos concurrentes.

Para abordar la independencia de la velocidad debemos ver las formas en las que los procesos interactan.

Interaccin entre Procesos

Se puede clasificar los en que interactan los procesos en funcin del nivel de conocimiento que cada proceso

tiene de la existencia de los dems. Existen tres niveles de conocimiento:

1) Los procesos no tienen conocimiento de los dems: son procesos independientes que no operan juntos. Ej:

la multiprogramacin de procesos independientes. Aunque los procesos no trabajen juntos, el sistemaoperativo se encarga de la "competencia"por los recursos.

2) Los procesos tienen un conocimiento indirecto de los otros: los procesos no conocen a los otros por sus

identificadores de proceso, pero muestran cooperacin el objeto comn.

3) Los procesos tienen conocimiento directo de los otros: los procesos se comunican por el identificador de

proceso y pueden trabajar conjuntamente.


15/30

Competencia entre procesos por los recursos

Los procesos concurrentes entran en conflicto cuando compiten por el uso del mismo recurso; dos o ms

procesos necesitan acceder a un recurso durante su ejecucin .Cada proceso debe dejar tal y como est el

estado del recurso que utilice.

La ejecucin de un proceso puede influir en el comportamiento de los procesos que compiten. Por Ej. Si dosprocesos desean acceder a un recurso, el sistema operativo le asignar el recurso a uno y el otro tendr que

esperar.

Cuando hay procesos en competencia, se deben solucionar tres problemas de control: la necesidad de

exclusin mutua. Suponiendo que dos procesos quieren acceder a un recurso no compartible. A estos

recursos se les llama "recursos crticos" y la parte del programa que los utiliza es la "seccin crtica del

programa. Es importante que slo un programa pueda acceder a su seccin crtica en un momento dado.

Hacer que se cumpla la exclusin mutua provoca un interbloqueo.

Otro problema es la inanicin si tres procesos necesitan acceder a un recurso, P1 posee al recurso, luego lo

abandona y le concede el acceso al siguiente proceso P2, P1 solicita acceso de nuevo y el sistema operativo

concede el acceso a P1 YP2 alternativamente, se puede negar indefinidamente a P3 el acceso al recurso.

El control de competencia involucra al sistema operativo, porque es el que asigna los recursos.

y Cooperacin entre procesos por compartimiento

Comprende los procesos que interactan con otros sin tener conocimiento explcito de ellos. Ej. : Variosprocesos pueden tener acceso a variables compartidas.

Los procesos deben cooperar para asegurar que los datos que se comparten se gestionan correctamente. Losmecanismos de control deben garantizar la integridad de los datos compartidos.

y Cooperacin entre procesos por comunicacin

Los distintos procesos participan en una labor comn que une a todos los procesos.

La comunicacin sincroniza o coordina las distintas actividades, est formada por mensajes de algn tipo. Las

primitivas para enviar y recibir mensajes, vienen dadas como parte del lenguaje de programacin o por el

ncleo del sistema operativo

Sincronizacin

Si una actividad desea impedir que otra acceda a ciertos datos compartidos, mientras no se cumpla una

determinada condicin, debemos sincronizar las actividades con dicha condicin. Por tanto, la sincronizacin

es un elemento necesario para asegurar la exclusin mutua.

Los algoritmos que se han diseado para este fin se clasifican:

Espera activa

Son aquellos algoritmos que basan todo su funcionamiento en establecer la espera de entrada a la seccin

crtica con un bucle que ser roto en el momento en que se cumpla una determinada condicin. Se llaman de

espera activa por que el proceso no queda bloqueado durante su ejecucin, si no que estar compitiendo con

el procesador constantemente. Fueron los primeros motivos en utilizarse y han sido sustituidos por otros ms

eficientes.


16/30

y Espera con mutex: Algoritmo que utiliza un switch (MUTEX) a travs del cual se produce la

sincronizacin.

y Alternancia: Ligeramente mejor que el anterior, utiliza tambin una variable TURNO para realizar el

sincronismo entre procesos.

y AlgoritmoDEKKER: Resuelve el problema mediante la solucin propuesta por Dekker,, basando su

funcionamiento en una tabla unidimensional de dos elementos lgicos.(Switches)

Espera no activa

Son aquellos algoritmos que establecen la espera para entrar en la seccin crtica bloqueando el

proceso, haciendo que deje de competir por el procesador hasta que se cumpla la condicin de desbloqueo.

Entre los algoritmos existentes citaremos los siguientes:

y Semforos: Para eliminar los problemas que se producen con los algoritmos de espera activa,

fundamentalmente los referidos a la sobrecarga que producen en el sistema, E.W. Dijkstra(1965)

diseo un mecanismo basado en una variable de entrada utilizada como contador de peticiones de

entrada a una seccin critica. Esta variable es compartida por todos los procesos del sistema. Este

nuevo tipo de variable se denomina semforo por su capacidad de gestionar el trfico de procesos

que deseen acceder a datos compartidos. Con este sistema, cuando un proceso intente entrar a una

seccin critica mientras otro esta accediendo a los datos compartidos, se bloquear de igual manera

que cuando un proceso accede a un recurso que est ocupado.

y Regiones criticas: Son sistemas que permiten establecer protecciones contra una mala utilizacin

de los usuarios. Para ello solo permiten que datos compartidos puedan acceder desde determinadas

regiones quedando transparentes desde el resto. Tiene pequeos inconvenientes relacionados con la

sincronizacin y no permite que varias actividades puedan realizar operaciones de lectura

simultnea.

y Regiones criticas condicionales: Consiste en una mejora del mtodo anterior tratando de resolver

algunos problemas de sincronizacin que se presentaban.

y Monitores: Uno de los problemas existentes en los mecanismos anteriores es que el programador

tiene que proporcionar de forma explcita el modo de sincronizacin. Para evitarlo, B. Hansen y

C.A.R Hoare desarrollaron un nuevo mecanismo denominado Monitor, que debe ser soportado por

el lenguaje correspondiente. Un monitor permite compartir, segura y eficientemente, datos entre

actividades garantizando la exclusin mutua, sin necesidad de que el programador tenga quesuministrarla explcitamente. Se basa en dos primicias: La primera es la abstraccin de datos

consistente en una tcnica capaz de separar las operaciones a ejecutar los datos, de los detalles de

diseo propio de los mismos. La segunda es que realizan la exclusin mutua en forma implcita. La

finalidad ms til de los monitores es reunir todas las funciones que operan sobre un conjunto de

datos compartidos en un solo modulo, de manera que todos los accesos a esos datos estarn

forzados a utilizar dichas funciones.

y Contadores de eventos: Es un mecanismo para sincronizar actividades sin que sea necesario

forzar la exclusin mutua, ya sea porque no deseamos limitar la concurrencia de las actividades o

simplemente porque no la necesitemos. Se basa en una variable cuya misin es contar determinadas

operaciones.

y Mensajes: Es un mecanismo que permite a los procesos intercambiar aquella informacin que sea

necesaria durante el desarrollo normal de su ejecucin. Por tanto es ms un mecanismo decooperacin y sincronizacin. Esta cooperacin se realiza por medio de mensajes que se envan

entre s los procesos. Se basa en una zona de memoria compartida que gestiona el S.O.

directamente y que permanece oculta a los procesos. De esta manera el proceso que enva un

mensaje a otro deposita la informacin en la zona de memoria compartida y el receptor lo lee de ella

posteriormente. En este sistema las directrices de envo y recepcin establecen una sincronizacin

entre los procesos al tener que esperar dichos mensajes, antes de continuar su ejecucin.

Existen 2 tipos de comunicacin de procesos:


17/30

y Directa: Los procesos se envan y reciben los mensajes directamente entre s, de manera

que se asocia un enlace bidireccional nico entre cada proceso.

y Indirecta: Los mensajes son enviados y recibidos a travs de maixboxes o buzones de

correos. Con este mtodo cada proceso puede estar relacionado con tantos buzones como

desee consiguiendo comunicarse con tantos procesos como sea necesario.

y

Llamadas remotas: El paso de un proceso a otro es un mecanismo muy utilizado para resolver losproblemas de concurrencia entre procesos. Es anlogo al paso de os parmetros en una llamada a

una rutina o procedimiento. Si unimos los conceptos de mensajes y paso de parmetros tendremos

lo que se conoce como rutinas o procedimientos remotos, crendose una copia del mismo cada

vez que son ejecutadas (llamadas remotas), siendo dicha ejecucin concurrente. Este tipo de

interaccin asegura que hasta que un proceso no termine determinadas operaciones, el siguiente

permanecer en espera.

y Rendez-vous: Es la culminacin de todos los mecanismos anteriores, tratndose de una ligera

modificacin del mtodo de las llamadas remotas, donde la llamad, en lugar de ser a todo un

procedimiento, lo es solamente a un grupo de sentencias dentro de l. De igual forma, se trata de un

procedimiento similar al monitor, pero con ms versatilidad y potencia. Este mtodo se ha llevado a

la prctica con el lenguaje Ada.

Mecanismos hardware

Son instrucciones hardware que aseguran la exclusin mutua. Entre las ms utilizadas citaremos las

siguientes:

y Deshabilitar interrupciones: Las computadoras actuales permiten que las interrupciones pueden

ser deshabilitadas, de esta forma, si un dispositivo generase una interrupcin estando deshabilitada,

el reconocimiento y tratamiento de la nueva interrupcin se retendr hasta que se habiliten de nuevo

las interrupciones. Por este medio, se puede forzar la exclusin mutua deshabilitando las

interrupciones mientras haya alguna actividad en la seccin crtica. De este modo, dicha actividad no

podr ser interrumpida y por tanto no se podr producir ningn cambio de proceso. Normalmente la

deshabilitacin y nueva habilitacin de las interrupciones suele hacerse con una instruccin mquina,por lo que resulta ser una operacin muy rpida.

y Instruccin TEST_AND_SET: Muchas de las computadoras actuales suministran una instruccin

mquina denominada Test and Set, cuya misin es la de forzar la exclusin mutua. La ventaja de

este mecanismo es que no puede ser interrumpida por ser una instruccin del hardware y el

inconveniente es que no son muchas las computadoras que la poseen. Esta instruccin, por s sola,

no basta para asegurar la exclusin mutua, por lo que tendremos que basarnos en ella para construir

los denominados locks.

y LOCK: Se basa en la instruccin anterior y su cometido es permitir el acceso a la seccin crtica a un

proceso en caso de no existir otra actividad dentro de su seccin critica, no permitindolo en caso

contrario. En este caso, el nmero de actividades y de procesadores compartiendo memoria principal

puede ser cualquiera, y adems son mecanismos simples y fciles de probar.

Exclusin Mutua

El mtodo ms sencillo de comunicacin entre los procesos de un programa concurrente es el uso comn de

unas variables de datos. El problema de este sistema es que la accin de un proceso interfiere en las

acciones do otro de una forma no adecuada. Para evitar este tipo de errores se pueden identificar aquellas

regiones de los procesos que acceden a variables compartidas y dotarlas de la posibilidad de ejecucin como

si fueran una nica instruccin. Se denomina seccin crtica a aquellas partes de los procesos concurrentes

que no pueden ejecutarse de forma concurrente o, que desde otro proceso se ven como si fueran una nica


18/30

instruccin. Esto quiere decir que si un proceso entra a ejecutar una seccin crtica en la que accede a unas

variables compartidas, entonces otro proceso no puede entrar a ejecutar una

Regin crtica en la que se modifique las variables compartidas con el anterior. Las secciones crticas se

pueden agrupar en clases, siendo mutuamente exclusivas las secciones crticas de cada una. Para conseguir

dicha exclusin se deben implementar protocolos software que impidan o bloqueen el acceso a una seccin

crtica mientras est siendo utilizada por un proceso.

Bloqueo mediante el uso de variables compartidas

Se usa una variable de tipo booleano llamada flag que es compartida por los procesos, se asocia a cada

recurso que se comparte. Si el sistema dispone de una instruccin que permita comprobar el estado de la flag

y modificarlo simultneamente, el programa permitira el uso del recurso sin entrelazamiento. En caso de usar

dos indicadores para un recurso, puede ocurrir que ambos procesos vean los indicadores contrarios como

ocupados, y permanezcan a la espera de liberacin del recurso, pero esto no puede ocurrir al no poder entrar

ninguno en su seccin crtica (Interbloqueo o

deadlock).

Se puede intentar resolver el problema haciendo que el proceso desactive su propio indicador durante la fase

de bloqueo siempre que encuentre que el indicador del otro proceso est activado. El algoritmo permite queen caso de interbloqueo se pueda proseguir siempre que no exista una completa sincronizacin entre los dos

procesos, ya que en el caso bastante improbable, pero que pudiera darse, de que los dos procesos realicen

exactamente las mismas operaciones a la vez, se encontraran permanentemente con los indicadores

contrarios activados. Otro problema con este algoritmo es que puede permitir que un proceso deje su seccin

crtica y vuelva a entrar mientras que el otro proceso desactiva su indicador en la seccin de bloqueo.

El que un proceso no pueda progresar porque se lo impida otro proceso o grupo de procesos se denomina

cierre (lockout o starvation). Veamos ahora dos soluciones al problema de la exclusin mutua que evitan el

interbloqueo y el cierre.

Algoritmo de Peterson:

Una posible solucin es introducir una variable adicional, denominada turno (Peterson, 1981), que slo resultatil cuando se produzca un problema de peticin simultnea de acceso a la regin crtica:

(* Exclusin mutua; Solucin de Peterson *)

module Exclusion_ Mutua_ P;

varflag1, flag2: Boolean;

turno : integer;

Procedure bloqueo (varmi_flag, su_flag: boolean; su_turno:integer);

begin

mi_flag: = true;

turno : = su_turno;

while su_flag and (turno : = su_turno) do; end

end bloqueo;

Procedure desbloqueo (varmi_falg: boolean);

begin


19/30

mi_flag : = false;

end desbloqueo;

process P1

begin

loop

bloqueo(flag1, flag2, 2);

(* Uso del recurso Seccin Crtica *)

desbloqueo (flag1);

(* Resto del proceso *)

end;

end P1;

process P2

begin

loop



desbloqueo (flag2);


end;

end P2;

begin (* Exclusin_ Mutua_ P *)

flag1 : = false

flag2 : = false;

cobegin

P1;

P2;

coend

end Exclusin_ Mutua_ P.

Si slo uno de los procesos intenta acceder a la seccin crtica lo podr hacer sin ningn problema. Sin

embargo, si ambos intentan entrar a la vez, el valor del turno se pondr a 1 y 2 pero slo un valor de ellos

permanecer al escribirse sobre el otro, permitiendo el acceso de un proceso a su regin crtica. El algoritmo


20/30


21/30

desbloqueo (flag1,2);


end;

end P1;

process P2

begin

loop



desbloqueo (flag2,1);


end;

end P2;

begin (* Exclusin_Mutua_D *)

flag1 : = false

flag2 : = false;

turno : =1;

cobegin

P1;

P2;

coend

end Exclusin_Mutua_D.

El programa se inicia con el valor de turno 1, lo que da prioridad al proceso P1. Si ambos programas piden a

la vez el acceso a su seccin crtica, activan sus respectivos indicadores y comprueban si el indicador del otro

est activado.

Ambos encuentran que s, por lo que pasan a evaluar el turno. El segundo encuentra que no es su turno,

desactiva su indicador y se queda en espera de que lo sea. P1 comprueba que si es su turno, entra en su

regin crtica y dar el turno a P2 antes de desactivar su indicador.

Los algoritmos de Peterson y Dekker se pueden extender al caso ms general con n procesos en ejecucin

concurrente; pero no son soluciones adecuadas ya que la espera de acceso a un recurso siempre se realiza

de forma ocupada. El proceso se queda permanente comprobando una variable, lo que puede suponer un

derroche de los recursos del sistema.


22/30

Secciones Crticas

La exclusin mutua necesita ser aplicada solo cuando un proceso acceda a datos compartidos; cuando los

procesos ejecutan operaciones que no estn en conflicto entre si, debe permitrseles proceder de forma

concurrente. Cuando un proceso esta accesando datos se dice que el proceso se encuentra en su seccin

critica ( o regin critica).

Mientras un proceso se encuentre en su seccin crtica, los dems procesos pueden continuar su ejecucin

fuera de sus secciones crticas. Cuando un proceso abandona su seccin critica, entonces debe permitrsele

proceder a otros procesos que esperan entrar en su propia seccin crtica (si hubiera un proceso en espera).

La aplicacin de la exclusin mutual es uno de los problemas clave de la programacin concurrente. Se han

diseado muchas soluciones para esto: algunas de software y algunas de hardware, ms de bajo nivel y otras

de alto nivel; algunas que requieren de cooperacin voluntaria, y algunas que demandan una adherencia

rgida a protocolos estrictos.

Estar dentro de una seccin crtica es un estado muy especial asignado a un estado. El proceso tiene acceso

exclusivo a los datos compartidos, y todos los dems procesos que necesitan accesar a esos datos

permanecen en espera. Por tanto, las secciones crticas deben ser ejecutadas lo ms rpido posible, un

programa no debe bloquearse dentro de su seccin crtica, y las secciones crticas deben ser codificadas con

todo cuidado.

Si un proceso dentro de una seccin crtica termina, tanto de forma voluntaria como involuntaria, entonces, al

realizar su limpieza de terminacin, el sistema operativo debe liberar la exclusin mutua para que otros

procesos puedan entrar en sus secciones crticas

Monitor

En la programacin paralela, los monitores son objetos destinados a ser usados sin peligro por ms de unhilo de ejecucin. La caracterstica que principalmente los define es que sus mtodos son ejecutados conexclusin mutua. Lo que significa, que en cada momento en el tiempo, un hilo como mximo puede estarejecutando cualquiera de sus mtodos. Esta exclusin mutua simplifica el razonamiento de implementarmonitores en lugar de cdigo a ser ejecutado en paralelo.

En el estudio y uso de los semforos se puede ver que las llamadas a las funciones necesarias para utilizarlosquedan repartidas en el cdigo del programa, haciendo difcil corregir errores y asegurar el buenfuncionamiento de los algoritmos. Para evitar estos inconvenientes se desarrollaron los monitores. El conceptode monitor fue definido por primera vez por Charles Antony Richard Hoare en un artculo del ao 1974. Laestructura de los monitores se ha implementado en varios lenguajes de programacin, incluido Pascalconcurrente, Modula-2, Modula-3 y Java, y como biblioteca de programas.

Componentes

Un monitor tiene cuatro componentes: inicializacin, datos privados, procedimientos del monitor y cola deentrada.

y Inicializacin: contiene el cdigo a ser ejecutado cuando el monitor es creado

y Datos privados: contiene los procedimientos privados, que slo pueden ser usados desde dentro delmonitor y no son visibles desde fuera

y Procedimientos del monitor: son los procedimientos que pueden ser llamados desde fuera delmonitor.

y Cola de entrada: contiene a los hilos que han llamado a algn procedimiento del monitor pero no hanpodido adquirir permiso para ejecutarlos an.

Exclusin mutua en un monitor


23/30

Los monitores estn pensados para ser usados en entornos multiproceso o multihilo, y por lo tanto muchosprocesos o threads pueden llamar a la vez a un procedimiento del monitor. Los monitores garantizan que encualquier momento, a lo sumo un thread puede estar ejecutando dentro de un monitor. Ejecutar dentro de unmonitor significa que slo un thread estar en estado de ejecucin mientras dura la llamada a unprocedimiento del monitor. El problema de que dos threads ejecuten un mismo procedimiento dentro delmonitor es que se pueden dar condiciones de carrera, perjudicando el resultado de los clculos. Para evitaresto y garantizar la integridad de los datos privados, el monitor hace cumplir la exclusin

mutuaimplcitamente, de modo que slo un procedimiento est siendo ejecutado a la vez. De esta forma, siun thread llama a un procedimiento mientras otro thread est dentro del monitor, se bloquear y esperar enla cola de entrada hasta que el monitor quede nuevamente libre. Aunque se la llama cola de entrada, nodebera suponerse ninguna poltica de encolado.

Para que resulten tiles en un entorno de concurrencia, los monitores deben incluir algn tipo de forma desincronizacin. Por ejemplo, supngase un thread que est dentro del monitor y necesita que se cumpla unacondicin para poder continuar la ejecucin. En ese caso, se debe contar con un mecanismo de bloqueo delthread, a la vez que se debe liberar el monitor para ser usado por otro hilo. Ms tarde, cuando la condicinpermita al thread bloqueado continuar ejecutando, debe poder ingresar en el monitor en el mismo lugar dondefue suspendido. Para esto los monitores poseen variables de condicin que son accesibles slo desdeadentro. Existen dos funciones para operar con las variables de condicin:

y cond_wait(c): suspende la ejecucin del proceso que la llama con la condicin c. El monitor se

convierte en el dueo del lock y queda disponible para que otro proceso pueda entrary cond_signal(c): reanuda la ejecucin de algn proceso suspendido con cond_wait bajo la misma

condicin c. Si hay varios procesos con esas caractersticas elige uno. Si no hay ninguno, no hacenada.

Ntese que, al contrario que los semforos, la llamada a cond_signal(c) se pierde si no hay tareas esperandoen la variable de condicin c.

Las variables de condicin indican eventos, y no poseen ningn valor. Si un thread tiene que esperar queocurra un evento, se dice espera por (o en) la variable de condicin correspondiente. Si otro thread provocaun evento, simplemente utiliza la funcin cond_signalcon esa condicin como parmetro. De este modo, cadavariable de condicin tiene una cola asociada para los threads que estn esperando que ocurra el eventocorrespondiente. Las colas se ubican en el sector de datos privados visto anteriormente.

La poltica de insercin de procesos en las colas de las variables condicin es la FIFO, ya que asegura queningn proceso caiga en la espera indefinida, cosa que s ocurre con la poltica LIFO (puede que los procesosde la base de la pila nunca sean despertados) o con una poltica en la que se desbloquea a un procesoaleatorio.

Tipos de monitores

Antes se dijo que una llamada a la funcin cond_signalcon una variable de condicin haca que un procesoque estaba esperando por esa condicin reanudara su ejecucin. Ntese que el thread que reanuda suejecucin necesitar obtener nuevamente el lock del monitor. Surge la siguiente pregunta: qu sucede con elthread que hizo el cond_signal? pierde el lock para drselo al thread que esperaba? qu thread continacon su ejecucin? Cualquier solucin debe garantizar la exclusin mutua. Segn quin contina con laejecucin, se diferencian dos tipos de monitores: Hoare yMesa.

Tipo Hoare

En la definicin original de Hoare, el thread que ejecuta cond_signal le cede el monitor al thread que esperaba. El monitortoma entonces el lock y se lo entrega al thread durmiente, que reanuda la ejecucin. Ms tarde cuando el monitor quedelibre nuevamente el thread que cedi el lock volver a ejecutar.

Ventajas:


24/30

y El thread que reanuda la ejecucin puede hacerlo inmediatamente sin fijarse si la condicin secumple, porque desde que se ejecut cond_signal hasta que lleg su turno de ejecutar ningnproceso puede cambiarla.

y El thread despertado ya estaba esperando desde antes, por lo que podra suponerse que es msurgente ejecutarlo a seguir con el proceso despertante.

Desventajas:

y Si el proceso que ejecuta cond_signalno termin con su ejecucin se necesitarn dos cambios decontexto para que vuelva a tomar el lock del monitor.

y Al despertar a un thread que espera en una variable de condicin, se debe asegurar que reanude suejecucin inmediatamente. De otra forma, algn otro thread podra cambiar la condicin. Esto implicaque la planificacin debe ser muy fiable, y dificulta la implementacin.

Tipo Mesa

Butler W. Lampson y David D. Redell en 1980 desarrollaron una definicin diferente de monitores para ellenguaje Mesa que lidia con las desventajas de los monitores de tipo Hoare y aade algunas caractersticas.

En los monitores de Lampson y Redell el thread que ejecuta cond_signalsobre una variable de condicin

contina con su ejecucin dentro del monitor. Si hay otro thread esperando en esa variable de condicin, se lodespierta y deja como listo. Podr intentar entrar el monitor cuando ste quede libre, aunque puede sucederque otro thread logre entrar antes. Este nuevo thread puede cambiar la condicin por la cual el primer threadestaba durmiendo. Cuando reanude la ejecucin el durmiente, debera verificar que la condicin efectivamentees la que necesita para seguir ejecutando. En el proceso que durmi, por lo tanto, es necesario cambiar lainstruccin ifporwhile, para que al despertar compruebe nuevamente la condicin, y de no ser cierta vuelva allamar a cond_wait.

Adems de las dos primitivas cond_wait(c) y cond_signal(c), los monitores de Lampson y Redell poseen lafuncin cond_broadcast(c), que notifica a los threads que estn esperando en la variable de condicin cy lospone en estado listo. Al entrar al monitor, cada thread verificar la condicin por la que estaban detenidos, aligual que antes.

Los monitores del tipo Mesa son menos propensos a errores, ya que un thread podra hacer una llamada

incorrecta a cond_signalo a cond_broadcastsin afectar al thread en espera, que verificar la condicin yseguir durmiendo si no fuera la esperada.

Semforos

Es una solucin sencilla y elegante del problema de la exclusin mutua. Esta tcnica permite solucionar la

mayora de los problemas de sincronizacin entre procesos. Un semforo binario es un indicador de condicin

(s) que registra si un registro est disponible o no. Un semforo slo puede tomar dos valores; 0 y 1. Si para

un semforo, S=1 el recurso est disponible y la tarea lo puede utilizar; si S=0 el recurso no est disponible y

el proceso debe esperar.

Los semforos se implementan mediante una cola de tareas a la que se aaden los procesos que estn en

espera del recurso. Solo se permiten tres operaciones sobre un semforo:

1. Inicializa (s: Semforo_Binario; v: integer) -- > poner el valor del semforo s al valor de v (0,1).2. Espera (wait)(s) ifs = 1 then s: = 0 else Suspender la tarea que hace la llamada y ponerla en la cola

de tareas.3. Seal (signal)(s) ifcola de tareas vaca then s : = 1 else Reanudar la primera tarea de la cola

tareas.


25/30

Estas operaciones son procedimientos que se implementan como acciones indivisibles. En sistemas con un

nico procesador bastar simplemente con inhibir las interrupciones durante la ejecucin de las operaciones

del semforo. Al introducir el semforo se crea un nuevo estado en el diagrama de transiciones, el de espera.

PRINCIPIOS DEL INTERBLOQUEO

El interbloqueo se puede definir como el bloqueo permanente de un conjunto de procesos que compiten por

los recursos del sistema o bien se comunican unos con otros. A diferencia de otros problemas de la gestin

concurrente de procesos, no existe una solucin eficiente para el caso general.

Todos los interbloqueos suponen necesidades contradictorias de recursos por parte de dos o ms procesos.

Ejemplos de Interbloqueo

Ejemplo 1: Interbloqueo de trfico

Cuatro coches llegan aproximadamente en el mismo instante a un cruce de cuatro caminos. Los cuatro

cuadrantes de la interseccin son los recursos compartidos sobre los que se demanda control; por tanto, si los

coches desean atravesar el cruce, las necesidades de recursos son las siguientes:

y El coche que va hacia el norte necesita los cuadrantes 1 y 2.y El coche que va hacia el oeste necesita los cuadrantes 2 y 3.

y El coche que va hacia el sur necesita los cuadrantes 3 y 4.y El coche que va hacia el este necesita los cuadrantes 4 y 1.


26/30


27/30

hasta que B la libere. Por desgracia, en este momento, en vez de liberar unidad de cinta, B solicita la

impresora. Los procesos se bloquean en ese momento y permanecen as por siempre.

Recursos

Un sistema se compone de un numero finito de recursos que se distribuyen entre varios tipos:

y Fsicos: Ciclo de cpu, espacio en memoria, dispositivos de e/s (impresoras, unidades de cinta, etc.)y Lgicos: Ficheros, tablas del sistema, semforos.

Por lo general, una computadora tiene distintos recursos que pueden ser otorgados. Algunos recursos podrn

tener varias instancias idnticas, como es el caso de tres unidades de cinta. Si se tienen disponibles varias

copias de un recurso, cualquiera de ellas se pude utilizar para satisfacer cualquier solicitud del recurso. Un

recurso es cualquier cosa que solo puede ser utilizada por un nico proceso en un instante dado.

Los recursos son de dos tipos:

y Apropiabley No apropiables

Un recurso apropiable es aquel que se puede tomar del proceso que lo posee sin efectos dainos. La

memoria es un ejemplo de recurso apropiable.

Por el contrario, un recurso no apropiable, es aquel que no se puede tomar de su poseedor activo sin provocar

un fallo de calculo. Si un proceso comienza a imprimir una salida, se toma la impresora y se le da a otro

proceso, el resultado ser una salida incomprensible. Las impresoras no son apropiables.

Los interbloqueos se relacionan con los recursos no apropiables. Lo usual es que los bloqueos asociados a

recursos apropiables se pueden resolver, mediante la reasignacin de recursos de un proceso a otro.

La secuencia de eventos necesaria para utilizar un recurso es:

y Solicitar el recursoy Utilizar el recurso

y Liberar el recurso

Si el recurso no esta disponible cuando se le solicita, el proceso solicitante debe esperar. En algunos

sistemas operativos, el proceso se bloquea de manera automtica al fallar una solicitud de un recurso y se

despierta cuando dicho recurso esta disponible.

En otros sistemas la solicitud falla con un cdigo de error y el proceso solicitante debe esperar un poco e

intentar de nuevo.

Un proceso cuya solicitud de un recurso ha sido denegada entra por lo general en un ciclo, en el cual solicita

el recurso, duerme e intenta de nuevo.

Aunque este proceso no esta bloqueado, para todos los efectos esta como bloqueado, puesto que no puede

hacer ninguna labor til.

El interbloque se puede definir entonces de la siguiente forma:

Un conjunto de procesos se encuentra en estado de interbloqueo cuando cada uno de ellos espera un suceso

que solo puede originar otro proceso del mismo conjunto.


28/30

En la mayora de los casos, el evento que espera cada proceso es la liberacin de cierto recurso que posee

por el momento otro miembro del conjunto. En otras palabras, cada miembro del conjunto de procesos

bloqueados espera un recurso posedo por un proceso bloqueado. Ninguno de los procesos puede continuar

su ejecucin, ni liberar recursos, y puede ser despertado.

Condiciones para producir Interbloqueo

En la poltica del sistema operativo, deben darse tres condiciones para que pueda producirse un interbloqueo:

1- Condicin de exclusin mutua: Cada recurso esta asignado a un nico proceso o esta disponible.2- Condicin de posesin y espera: Los procesos que tienen, en un momento dado, recursos

asignados con anterioridad, pueden solicitar nuevos recursos.3- Condicin de no apropiacin: Los recursos otorgados con anterioridad no pueden ser forzados a

dejar un proceso. El proceso que los posee debe liberarlos en forma explicita.

En la mayora de los casos, estas condiciones son bastantes necesarias. La exclusin mutua hace

falta para asegurar la consistencia de resultados y la integridad de la base de datos. De forma

similar, la apropiacin no se puede aplicar arbitrariamente y, cuando se encuentran involucrados

recursos de datos, debe estar acompaada de un mecanismo de recuperacin y reanulacin, que

devuelva un proceso y sus recursos a un estado previo adecuado, desde el que el proceso puedefinalmente repetir sus acciones.

Puede no existir interbloqueo con solo estas tres condiciones. Para que se produzca interbloqueo, senecesita una cuarta condicin:

4- Condicin de espera circular (o circulo vicioso de espera): Debe existir una cadena circular de dos oms procesos, cada uno de los cuales espera un recurso posedo por el siguiente miembro de lacadena.

Las tres primeras condiciones son necesarias, pero no suficientes, para que exista interbloqueo. La cuarta

condicin es, en realidad, una consecuencia potencial de las tres primeras. Es decir, dado que se producen

las tres primeras condiciones, puede ocurrir una secuencia de eventos que desemboque en un circulo vicioso

de espera irresoluble. El circulo de espera de la condicin 4 es irresoluble porque se mantienen las tres

primeras condiciones. Las cuatro condiciones en conjunto constituyen una condicin necesaria y suficiente

para el interbloqueo.

Prevencin del Interbloqueo

La estrategia bsica de la prevencin del interbloqueo consiste, a grandes rasgos, en disear su sistema de

manera que est excluida, a priori, la posibilidad de interbloqueo.

Los mtodos para prevenir el interbloqueo son de dos tipos:


29/30

- Los mtodos indirectos que consisten en impedir la aparicin de alguna de las tres condicionesnecesarias para que se produzca el interbloqueo.

- Los mtodos directos que consisten en evitar la aparicin del circulo vicioso de espera.

Exclusin mutua

Si ningn recurso se puede asignar de forma exclusiva, no se producir interbloqueo. Sin embargo, existen

recursos para los que no es posible negar la condicin de exclusin mutua. No obstante, es posible eliminar

esta condicin en algunos procesos. Por ejemplo, una impresora es un recurso no compatible pues si se

permite que dos procesos escriban en la impresora al mismo tiempo, la salida resulta catica. Pero con el

spooling de salida varios procesos pueden generar salida al mismo tiempo. Puesto que el spooler nunca

solicita otros recursos, se elimina el bloqueo originado por la impresora.

El inconveniente es que no todos los recursos pueden usarse de esta forma (por ejemplo, la tabla de procesos

no se presenta al spooling y, adems, la implementacin de esta tcnica puede introducir nuevos motivos de

interbloqueo, ya que el spooling emplea una zona de disco finita)

Retencin y espera

La condicin de retencin y espera puede prevenirse exigiendo que todos los procesos soliciten todos los

recursos que necesiten a un mismo tiempo y bloqueando el proceso hasta que todos los recursos puedan

concederse simultneamente. Esta solucin resulta ineficiente por dos factores:

y En primer lugar, un proceso puede estar suspendido durante mucho tiempo, esperando queconcedan todas sus solicitudes de recursos, cuando de hecho podra haber avanzado con soloalgunos de los recursos.

y Y en segundo lugar, los recursos asignados a un proceso pueden permanecer sin usarse duranteperiodos considerables, tiempo durante el cual se priva del acceso a otros procesos.

No apropiacin

La condicin de no apropiacin puede prevenirse de varias formas. Primero, si a un proceso que retiene

ciertos recursos se le deniega una nueva solicitud, dicho proceso deber liberar sus recursos anteriores y

solicitarlos de nuevo, cuando sea necesario, junto con el recurso adicional. Por otra parte, si un proceso

solicita un recurso que actualmente esta retenido por otro proceso, el sistema operativo debe expulsar al

segundo proceso y exigirle que libere sus recursos. Este ltimo esquema evitar el interbloqueo slo si no hay

dos procesos que posean la misma prioridad.

Esta tcnica es prctica slo cuando se aplica a recursos cuyo estado puede salvarse y restaurarse ms tarde

de una forma fcil, como es el caso de un procesador.

Circulo vicioso de espera

La condicin del crculo vicioso de espera puede prevenirse definiendo una ordenacin lineal de los tipos de

recursos. Si a un proceso se le han asignado recursos de tipo R, entonces slo podr realizar peticiones

posteriores sobre los recursos de los tipos siguientes a R en la ordenacin.

Para comprobar el funcionamiento de esta estrategia, se asocia un ndice a cada tipo de recurso. En tal caso,

el recurso Ri antecede a Rj en la ordenacin si i


30/30

Prediccin del Interbloqueo

Una forma de resolver el problema del interbloqueo, que se diferencia sutilmente de la prevencin, es la

prediccin del interbloqueo. En la prevencin de interbloqueo, se obligaba a las solicitudes de recursos a

impedir que sucediera, por lo menos, alguna de las cuatro condiciones de interbloqueo. Esto se hace

indirectamente, impidiendo la aparicin de una de las tres condiciones necesarias (exclusin mutua, retencin

y espera, no apropiacin) o directamente, impidiendo la aparicin de un crculo vicioso de espera. Se llega asa un uso ineficiente de los recursos y una ejecucin ineficiente de los procesos. Con prediccin del

interbloqueo, por otro lado, se pueden alcanzar las tres condiciones necesarias, pero se realizan elecciones

acertadas para asegurar que nunca se llega al punto de interbloqueo. La prediccin, por lo tanto, permite ms

concurrencia que la prevencin.

Con prediccin del interbloqueo, se decide dinmicamente si la peticin actual de asignacin de un recurso

podra, de concederse, llevar potencialmente a un interbloqueo. La prediccin del interbloqueo necesita, por lo

tanto, conocer las peticiones futuras de recursos.

Enfoques para la prediccin del interbloqueo:

y No iniciar un proceso si sus demandas pueden llevar a interbloqueo.

y

No conceder una solicitud de incrementar los recursos de un proceso si esta asignacin puede llevara interbloqueo.

Guia3Fundamentos Sistemas OperativosII

Documents

Transcript of Guia3Fundamentos Sistemas OperativosII