Concurrencia: exclusion

mutua y sincronizacion
Multiprogramacion: Es la gestion de varios procesos dentro de un sistema
monoprocesador
Multiproceso: Es la gestion de varios procesos dentro de un sistema
multiprocesador.
Proceso distribuido: Es la gestion de varios procesos que ejecutan en sistemas de
computadores multiples y remotas.

La concurrencia es el punto clave de los tres campos anteriores y fundamentales

para el diseño de sistemas operativos. La concurrencia comprende un gran
numero de cuestiones de diseno, incluyendo la comunicacion entre procesos,
comparticion y competencia por los recursos, sincronizacion de la ejecucion de
varios procesos y asignacion del tiempo de procesador a los procesos. Se vera
que estas cuestiones no solo surgen en entornos de multiprocesadores y proceso
distribuido, sino incluso en sistemas multiprogramados con un solo procesador.

PRINCIPIOS GENERALES DE CONCURRENCIA

En un sistema multiprogramado con un unico procesador, los procesos se
intercalan en el tiempo para dar la apariencia de ejecucion . Aunque no se
consigue un proceso paralelo real y aunque se produce una cierta sobrecarga en
los intercambios de procesos de un sitio a otro, la ejecucion intercalada produce
beneficios importantes en la eficiencia del procesamiento y en la estructuracion de
los programas. En un sistema con varios procesadores, no solo es posible
intercalar los procesos, sino tambien superponerlos. A primera vista, podria
parecer que la intercalacion y la superposicion representan formas de ejecucion
muy diferentes y que introducen problemas distintos. De hecho, ambas tecnicas
pueden contemplarse como ejemplos de proceso concurrente y ambas plantean
los mismos problemas. En el caso de un sistema monoprocesador, los problemas
creados por la multiprogramacion parten del hecho de que la velocidad relativa de
ejecucion de los procesos no puede predecirse. Depende de la actividad de otros
procesos, de la forma en que el sistema operativo trata las interrupciones y de las
politicas de planificacion. Asi surgen las siguientes dificultades:

1. La comparticion de recursos globales esta llena de riesgos. Por ejemplo, si dos

procesos hacen uso al mismo tiempo de la misma variable global y ambos llevan a
cabo tanto lecturas como escrituras sobre la variable, el orden en que se ejecuten
las lecturas y escrituras es critico.
2. Para el sistema operativo resulta dificil asignar los recursos de forma optima.
Por ejemplo, el proceso A puede solicitar el uso de un canal de E/S en particular y
suspenderse antes de hacer uso del canal. Si el sistema operativo bloquea el
canal e impide su uso por parte de otros procesos, se tiene una cierta ineficiencia.

3. Resulta dificil localizar un error de programacion porque los resultados no son

normalmente reproducibles;

Todas las dificultades anteriores se presentan tambien en los sistemas

multiprocesador, ya que tambien en ellos es impredecible la velocidad relativa de
ejecucion de los procesos. Un sistema multiprocesador debe solucionar, ademas,
los problemas originados por el hecho de que varios procesos puedan estar
ejecutando a la vez. Sin embargo, los problemas son, fundamentalmente,
los mismos que en el caso anterior.

Un ejemplo sencillo
Considerese el siguiente procedimiento:

procedure echo;
var sal, ent: caracter;
begin
entrada (ent, teclado); sal ent;
salida (sal, terminal)
end.

Este procedimiento muestra los elementos esenciales de un programa que

implemente la funcion de eco (echo) de un caracter en el terminal; la entrada se
obtiene del teclado, con una pulsacion cada vez. Cada caracter de la entrada se
almacena en la variable ent. Despues se transfiere a la variable sal y se muestra
en la pantalla. Cualquier programa puede llamar a este procedimiento repetidas
veces para recibir la entrada del usuario y mostrarla en la pantalla. Considerese
ahora un sistema multiprogramado con un unico procesador que da soporte a un
solo usuario. El usuario puede pasar de una aplicacion a otra y todas las
aplicaciones usan el mismo teclado para la entrada y la misma pantalla para la
salida. Puesto que cada aplicación tiene que usar el procedimiento echo, tiene
sentido que este sea un procedimiento compartido que se cargue en una parte de
memoria global para todas las aplicaciones. De este modo, solo se usa una copia
del procedimiento y se ahorra espacio.

La comparticion de memoria principal entre los procesos es util para una

interaccion cercana y eficiente entre los procesos. Sin embargo, esta comparticion
puede dar lugar a problemas.

Considerese la siguiente secuencia:

1. El proceso P1 llama al procedimiento echo y es interrumpido inmediatamente
despues de terminar la funcion entrada. En este punto, el ultimo caracter leido, x,
estara almacenado en la variable ent.
2. Se activa el proceso P2 y llama al procedimiento echo, que ejecuta hasta el final
y muestra un caracter y en la pantalla.

3. Se reanuda el proceso P1. Ahora, el valor de x ha sido sobreescrito en la

variable ent y, por tanto, se ha perdido. En su lugar, ent’ contiene el valor y, que se
transfiere a la variable sal y se visualiza.

Asi pues, se pierde el primer caracter y el segundo se visualiza dos veces. La

parte esencial de este problema es la comparticion de la variable global ent. Varios
procesos tienen acceso a esta variable. Si un proceso actualiza la variable y es
interrumpido, otro proceso puede alterar la variable antes de que el primer proceso
pueda usar ese valor. Supongase, sin embargo, que se impone que, aunque echo
sea un procedimiento global, solo pueda estar ejecutandolo un proceso cada vez.
Entonces, la secuencia anterior quedarla como sigue:

1. El proceso P1 llama al procedimiento echo y es interrumpido inmediatamente

despues de terminar la funcion entrada. En este punto, el ultimo caracter leido, x,
esta almacenado en la variable ent.

2. Se activa el proceso P2 y llama al procedimiento echo. Sin embargo, puesto

que P1 permanece aun en el procedimiento, aunque suspendido, P2 se bloquea al
entrar al procedimiento. Por tanto, se suspende a P2 mientras espera poder
acceder al procedimiento echo.
3. Mas adelante, el proceso P1 se reanuda y completa la ejecucion de echo. Se
visualiza el caracter correcto, x.
4. Cuando P1 abandona echo, se retira el bloqueo de P2. Cuando se reanude mas
tarde P2, la llamada al procedimiento echo se hara con exito.

La leccion que hay que aprender de este ejemplo es que es necesario proteger las
variables globales compartidas (y otros recursos globales compartidos) y que la
unica forma de hacerlo es controlar el codigo que accede a la variable. Si se
impone la norma de que solo un proceso puede acceder a echo en cada instante y
que, una vez en echo, el procedimiento debe ejecutar hasta el final antes de estar
disponible para otro proceso, no se producira el tipo de error expuesto antes.
El tema principal de este capitulo es como imponer esta norma.

Este problema se ha enunciado bajo el supuesto de que se dispone de un sistema

operativo multiprogramado con un unico procesador. El ejemplo demuestra que
los problemas de concurrencia se producen incluso cuando hay un unico
procesador. En un sistema multiprocesador surge el mismo problema de
proteccion de los recursos compartidos y es valida la misma solucion. En primer
lugar, supongase que no hay ningun mecanismo para controlar el acceso a la
variable global compartida:

1. Los procesos P1 y P2 estan ejecutando, cada uno en un procesador diferente.

Ambos invocan al procedimiento echo.
2. Se producen los siguientes sucesos; los sucesos de la misma linea tienen lugar
en paralelo:

PROCESO P1 PROCESO P2
_ _
entrada (ent, teclado) _
entrada (ent, teclado)
sal := ent sal := ent
salida (sal, terminal)
_ salida (sal, terminal)
_

El resultado es que el caracter de entrada de P1 se pierde antes de visualizarse y

el caracter de entrada de P2 se visualiza tanto por P1 como por P2. De nuevo, se
va a aplicar la norma de que solo un proceso puede estar en echo en cada
instante. Entonces, se tiene la siguiente secuencia:

1. Los procesos P1 y P2 estan ejecutando, cada uno en un procesador diferente.

P1 invoca al procedimiento echo.
2. Mientras P1 esta en el procedimiento echo, P2 invoca a echo. Puesto que P1
todavia esta ejecutando el procedimiento (tanto si esta suspendido como si esta
ejecutando), P2 se bloquea al entrar al procedimiento. Por tanto, P2 se suspende
en espera de poder acceder al procedimiento echo.
3. Mas tarde, el proceso P1 termina la ejecucion de echo, lo abandona y continua
la ejecucion. Inmediatamente despues de que P1 salga de echo, P2 se reanuda y
comienza a ejecutar echo.

En el caso de un sistema monoprocesador, La razon por la que se presenta el

problema es que una interrupcion puede detener la ejecucion de instrucciones en
cualquier punto de un proceso. En el caso de un sistema multiprocesador, se tiene
la misma condicion y, ademas, el problema puede ser causado por dos procesos
que esten ejecutando simultaneamente y que intenten ambos acceder a la misma
variable global. Sin embargo, la solucion para ambos tipos de problemas es
la misma: controlar el acceso al recurso compartido.

Labores del sistema operativo

.Que elementos de gestion y diseno surgen por causa de la concurrencia? Se
pueden enumerar los siguientes:
1. El sistema operativo debe ser capaz de seguir la pista de los distintos procesos
activos. Esto lo hace por medio de bloques de control de procesos, como se
describio en el capitulo 3.
2. El sistema operativo debe asignar y quitar los distintos recursos a cada proceso
activo. Entre estos recursos se incluyen:

Tiempo de procesador:.
• Memoria: La mayoria de los sistemas operativos emplean esquemas de memoria
vir-tual.
• Archivos:
• Dispositivos de E/S:
3. El sistema operativo debe proteger los datos y los recursos fisicos de cada
proceso contra injerencias no intencionadas de otros procesos. Esto supone
emplear tecnicas relativas a la memoria, archivos y dispositivos de E/S
4. Los resultados de un proceso deben ser independientes de la velocidad relativa
a la que se realiza la ejecucion con respecto a otros procesos concurrentes.

A continuación se enumera tres niveles de conocimiento y las consecuencias de

cada uno de ellos:

• Los procesos no tienen conocimiento de los demas: Estos son procesos

independientes que no estan pensados para operar juntos. El mejor ejemplo de
esta situacion es la multiprogramación de varios procesos independientes. Estos
pueden ser tanto trabajos por lotes como sesiones interactivas o una combinacion
de ambos. Aunque los procesos no trabajen juntos, el sistema operativo tiene que
encargarse de la competencia por los recursos.

• Los procesos tienen un conocimiento indirecto de los otros: Los procesos no

conocen necesariamente a los otros por su nombre, pero comparten el acceso a
algunos objetos, tales como un buffer de E/S. Estos procesos muestran
cooperacion para compartir el objeto comun.

• Los procesos tienen un conocimiento directo de los otros: Los procesos son
capaces de comunicarse con los demas por el nombre y estan disenados para
trabajar conjuntamente en alguna actividad. Estos procesos tambien muestran
cooperacion.

Competencia entre procesos por los recursos

Los procesos concurrentes entran en conflicto cuando compiten por el uso del
mismo recurso. Basicamente, es posible describir esta situacion como sigue. Dos
o mas procesos necesitan acceder a un recurso durante el curso de su ejecucion.
Cada proceso no es consciente de la existencia de los otros y no se ye afectado
por su ejecucion. De aqui se obtiene que cada proceso debe dejar tal y como este
el estado de cualquier recurso que utilice. Como ejemplos de recursos se tienen a
los dispositivos de E/S, la memoria, el tiempo de procesador y el reloj.

En particular, si dos procesos desean acceder a un unico recurso, el sistema

operativo le asignara el recurso a uno de ellos y el otro tendra que esperar. Por
tanto, el proceso a! que se niega el acceso se retrasara. En el peor caso, el
proceso bloqueado puede que no consiga nunca acceder al recurso y, por tanto,
no terminara con exito nunca.

En el caso de que haya procesos en competencia, se deben solucionar tres

problemas de control. El primero es la necesidad de exclusion mutua. Supongase
que dos o mas procesos quieren acceder a un unico recurso no compartible, como
una impresora. Durante el curso de la ejecucion, cada proceso enviara ordenes al
dispositivo de E/S, recibiendo informacion de estado, enviando y/o recibiendo
datos. A estos recursos se les llamara recursos criticos y la parte del programa
que los utiliza se conoce como seccion critica del programa. Es importante que
solo un programa pueda acceder a su seccion critica en un momento dado. No se
puede confiar simplemente en el sistema operativo para aceptar y hacer cumplir
esta restriccion, pues los requisitos especificos pueden no ser tan obvios. En el
caso de la impresora, por ejemplo, se desea que un proceso dado tome el control
mientras imprime un archivo completo. De otro modo, se intercalaran las lineas de
los procesos en competencia. Hacer que se cumpla la exclusion mutua crea dos
problemas de control adicionales. Uno es el interbloqueo.Un ultimo problema de
control es la inanicion. Supongase que tres procesos, P1, P2 y P3, necesitan
acceder periodicamente al recurso R. Considerese la situacion en la que P1 esta
en posesion del recurso y tanto P2 como P3 estan parados, esperando al recurso.
Cuando P1 abandona su seccion critica, tanto P2 como P3 deben poder acceder a
R. Supongase que se le concede el acceso a P3 y que, antes de que termine su
seccion critica, P1 solicita acceso de nuevo. Si se le concede el acceso a P1
despues de que P3 termine y si P1 y P3 se conceden el acceso repetidamente el
uno al otro, se puede negar definidamente a P2 el acceso al recurso, aunque no
se produzca una situacion de interbloqueo. El control de la competencia involucra
al sistema operativo inevitablemente, porque es el sistema operativo el que asigna
los recursos. Ademas, los procesos deben ser capaces por si mismos de expresar
de algun modo los requisitos de exclusion mutua, como puede ser bloqueando los
recursos antes de usarlos. Cualquier solucion conlleva alguna ayuda del sistema
operativo, como la provision del servicio de bloqueo.

program ExclusionMutua;
const n =…; (* nurnero de procesos *)
procedure P(i: entero);
begin
repeat
entrada _ critica (R);
<seccion critica>;
salida _ critica (R);
<resto>
forever
end;

begin (* programa principal *)

parbegin
P(1);
P(2);
…
P(n);
parend
end.
Ejemplo
dos datos, a y b, deben cumplir la relacion a = b. Es decir, cualquier programa que
actualice un valor debe tambien actualizar el otro para que se siga cumpliendo la
relacion. Considerense ahora los siguientes procesos:

P1: a := a + 1;
b := b + 1;

P2: b := 2*b;
a := 2*a;
Si al principio el estado es consistente, cada proceso por separado dejara los
datos cornpartidos en un estado consistente. Considerese ahora la siguiente
ejecucion concurrente, en la que los dos procesos respetan la exclusion mutua
para cada dato individual (a y b):

a := a + 1;
b := 2 * b;
b := b + l;
a := 2 * a;

Al final de esta secuencia de ejecucion, ya no se mantiene la condicion a = b. El

problema puede evitarse declarando la secuencia completa de cada proceso como
seccion critica, incluso aunque, estrictamente hablando, ningun recurso critico se
vea involucrado.

Cooperación entre procesos por comunicación

En los dos primeros casos expuestos, cada proceso posee su propio entorno
aislado, que no incluye a los otros procesos. Las interacciones entre los procesos
son indirectas. En ambos casos, existe comparticion. En caso de competencia, los
procesos estan compartiendo recursos sin tener conocimiento de la existencia de
otros procesos. En el segundo caso, estan compartiendo valores y, aunque cada
proceso no tiene conocimiento explicito de los otros, si es consciente de la
necesidad de conservar la integridad de los datos. Cuando los procesos cooperan
por comunicacion, en cambio, los distintos procesos participan en una labor
comun que une a todos los procesos. La comunicacion es una manera de
sincronizar o coordinar las distintas actividades.

Como ejemplo de interbloqueo, dos procesos pueden estar bloqueados, cada uno
esperando una comunicacion del otro. Como ejemplo de inanicion, considerense
tres procesos, P1, P2 y P3, que muestran el comportainiento siguiente. P1 intenta
comunicar repetidas veces bien con P2 o con P3 y tanto P2 como P3 intentar
comunicar con P1. Puede surgir una secuencia en la que P1 y P2 intercambien
informacion repetidamente, mientras P3 esta bloqueado esperando una
comunicacion desde P1.
No hay interbloqueo porque P1 permanece activo, pero P3 sufre de inanicion.

Requisitos para la exclusión mutua

El uso adecuado de la concurrencia entre procesos exige la capacidad de definir

secciones criticas y hacer cumplir la exclusion mutua. Esto es fundamental para
cualquier esquema de proceso concurrente. Cualquier servicio o capacidad que de
soporte para la exclusion mutua debe cumplir los requisitos siguientes:

1. Debe cumplirse la exclusion mutua: Solo un proceso, de entre todos los que
poseen secciones criticas por el mismo recurso u objeto compartido, debe
tener permiso para entrar en ella en un instante dado.

2. Un proceso que se interrumpe en una seccion no critica debe hacerlo sin

estorbar a los otros procesos.

3. Un proceso no debe poder solicitar acceso a una seccion critica para

despues ser demorado indefinidamente; no puede permitirse el interbloqueo
o la inanicion.

4. Cuando ningun proceso esta en su seccion critica, cualquier proceso que

solicite entrar en la suya debe poder hacerlo sin dilacion.

5. No se pueden hacer suposiciones sobre la velocidad relativa de los

procesos o su numero.

6. Un proceso permanece en su seccion critica solo por un tiempo finito.

Hay varias formas de satisfacer los requisitos de exclusion mutua. Una manera es
dejar la responsabilidad a los procesos que deseen ejecutar concurrentemente.
Asi pues, tanto si son programas del sistema como de aplicacion, los procesos
deben coordinarse unos con otros para cumplir la exclusion mutua, sin ayuda por
parte del lenguaje de programacion o del sistema operativo. Estos metodos se
conocen como soluciones por software. Aunque las soluciones por software son
propensas a errores y a una fuerte carga de proceso, resulta util estudiar estos
metodos para tener un mejor entendimiento de la complejidad del proceso
concurrente.Un segundo metodo propone el uso de instrucciones de la maquina a
tal efecto. Estas tienen la ventaja de reducir la sobrecarga pero, sin embargo, se
vera que no son interesantes. El tercer metodo consiste en dar algun tipo de
soporte en el sistema operativo.