Procesos

Concepto de Procesos

Todos los programas cuya ejecucion solicitan los usuarios, se ejecutan en forma de procesos, de ahi la importancia para le informatico de conocerlos en detalle. El proceso se puede definir como un programa de gestion por el sistema operativo. Durante su eleccion el proceso va modificando en ejecucion y, de una forma un poco mas precisa, como la unidad de procesamiento los registro del modelo de programacion de la computadora, de acuerdo a las intrusiones de maquina involucradas.
El sistema operativo mantiene por cada proceso una serie de estructuras de informacion que permiten identificar las caracteristicas de este, asi como los recursos que tiene asignados. En esta ultima categoria entran los descriptores de los segmentos de memoria asignados, los descriptores de los archivos abiertos, los descriptores de los puertos de comunicaciones, etc.
Una parte muy importante de esta informacion se encuentra normalmente como en el llamado bloque de control de procesos (BCP). El sistema operativo mantiene una tabla de procesos con todos los BCP de los procesos. Por razones de eficiencia, la tabla de procesos se construyen normalmente como una estructura estatica, que tiene un determinado numero de BCP, todos ellos del mismo tamano. La informacion que compone un proceso es la siguiente:

Estado y Transiciones del Proceso

Como se indico anteriormente, el proceso es la unidad de procesamiento gestionada por el sistema operativo. Para poder realizar este cometido, el proceso tiene asociado una serie de elementos de informacion, que se resumen en la Figura 3.8, que se analizan seguidamente. Estos elementos se organizan en tres grupos: estado del procesador, imagen de memoria y tablas del sistema operativo.

Estado del procesador

El estado del procesador esta formado por el contenido de todos sus registros, que se enumeran seguidamente:

Informacion del proceso

• Puntero de pila.
• Registro o registros de estado.
• Registros especiales. Como puede ser el RIED (registro identificador de espacio de direccionamiento).

El estado del procesador de un proceso reside en los registros del procesador, cuando el proceso esta en ejecucion, o en el bloque de control de proceso (BCP), cuando el proceso no esta en ejecucion.

Cuando el proceso esta ejecutando, el estado del procesador varia de acuerdo al flujo de instrucciones maquina ejecutado. En este caso, la copia del estado del procesador que reside en el BCP no esta actualizada. Tengase en cuenta que los registros de la maquina se utilizan para no tener que acceder a la informacion de memoria, dado que es mucho mas lenta. Por tanto, no tiene sentido plantear que, en cada modificacion de un registro, se actualice su valor en el BCP, puesto que esta en memoria.

Sin embargo, cuando se detiene la ejecucion de un proceso, como consecuencia de la ejecucion de una interrupcion, es muy importante que el sistema operativo actualice la copia del estado del procesador en su BCP. En terminos concretos, la rutina del sistema operativo que trata las Interrupciones lo primero que ha de hacer es salvar el estado del procesador en el BCP del proceso interrumpido.

 

Concurrencia y Secuenciabilidad 

Los procesos son concurrentes si existen simultaneamente. Los procesos concurrentes pueden funcionar en forma totalmente independiente unos de otros, o pueden ser asincronos, lo cual significa que en ocasiones requieren cierta sincronizacion o cooperacion.

Cuando dos o mas procesos llegan al mismo tiempo a ejecutarse, se dice que se ha presentado una concurrencia de procesos. Es importante mencionar que para que dos o mas procesos sean concurrentes , es necesario que tengan alguna relacion entre ellos como puede ser la cooperacion para un determinado trabajo o el uso de informacion o recursos compartidos, por ejemplo: en un sistema de un procesador , la multiprogramacion es una condicion necesaria pero no suficiente para que exista concurrencia, ya que los procesos pueden ejecutarse de forma totalmente independiente.

Por otro lado en un sistema de varios procesos se puede presentar la concurrencia siempre y cuando las actividades necesiten actuar entre si ya sea para utilizar informacion en comun o para cualquier otra cosa.
Existen tres formas modelos de computadora en los que se puede pueden ejecutar procesos concurrentes:

Multiprogramacion con un unico procesador.

En este modelo todos los procesos concurrentes ejecutan sobre un unico procesador. El sistema operativo se encarga de ir repartiendo el tiempo del procesador entre los distintos procesos, intercalando la ejecucion de los mismos para dar asi una apariencia de ejecucion simultanea.

Multiprocesador.

Un multiprocesador es una maquina formada por un conjunto de procesadores que comparten memoria principal. En este tipo de arquitecturas, los procesos concurrentes no solo pueden intercalar su ejecucion sino tambien superponerla. En este caso si existe una verdadera ejecucion simultanea de procesos, al coincidir las fases de procesamiento de distintos procesos. En un instante dado se pueden ejecutar de forma simultanea tantos procesos como procesadores haya.

Multicomputadora.

Una multicomputadora es una maquina de memoria distribuida, en contraposicion con el multiprocesador que es de memoria compartida. Esta formada por una serie de computadoras completas con su UCP, memoria principal y, en su caso, periferia. Cada uno de estos procesadores completo se denomina nodo. Los nodos se encuentran conectados y se comunican entre si a traves de una red de interconexion, empleando el metodo de paso de mensajes. En este tipo de arquitecturas tambien es posible la ejecucion simultanea de los procesos sobre los distintos procesadores.

En general la concurrencia sera aparente siempre que el numero de procesos sea mayor que el de procesadores disponibles, es decir, cuando haya mas de un proceso por procesador. La concurrencia sera real cuando haya un proceso por procesador

Mecanismo de Semaforos

 

Las diversas soluciones hardware al problema de la seccion critica, basadas en las instrucciones TestAndSet () y Swap (), son complicadas de utilizar por los programadores de aplicaciones. Para superar esta dificultad, podemos usar una herramienta de sincronizacion denominada semaforo.

Un semaforo S es una variable entera a la que, dejando aparte la inicializacion, solo se accede mediante dos operaciones atomicas estandar: wait () y signal (). Originalmente, la operacion wait () se denominaba P (del termino holandes proberen, probar); mientras que signal( ) denominaba originalmente V (verhogen, incrementar). La definicion de wait () es la que sigue:

wait (S) {
while S <= 0
;??? // no-op
S--;
}
La definicion de signal () es:
signal(S) {
S++;
}

Todas las modificaciones del valor entero del semaforo en las operaciones wait () y signal () deben ejecutarse de forma indivisible. Es decir, cuando un proceso modifica el valor del semaforo, ningun otro proceso puede modificar simultaneamente el valor de dicho semaforo. Ademas, en el caso de wait(), la prueba del valor entero de S (S <- 0), y su posible modificacion (S - -) tambien se deben ejecutar sin interrupcion.

Utilizacion

Los sistemas operativos diferencian a menudo entre semaforos contadores y semaforos binarios. El valor de un semaforo contador puede variar en un dominio no restringido, mientras que el valor de un semaforo binario solo puede ser 0 01. En algunos sistemas, los semaforos binarios se conocen como cerrojos mutex, ya que son cerrojos que proporcionan exclusion mutua.
Podemos usar semaforos binarios para abordar el problema de la seccion critica en el caso de multiples procesos. Los n procesos comparten un semaforo, mutex, inicializado con el valor 1. Cada proceso P; se organiza como se muestra en la Figura 6.9.

Los semaforos contadores se pueden usar para controlar el acceso a un determinado recurso formado por un numero finito de instancias. El semaforo se inicializa con el numero de recursos disponibles. Cada proceso que desee usar un recurso ejecuta una operacion wait () en el semaforo (decrementando la cuenta). Cuando un proceso libera un recurso, ejecuta una operacion signal()(incrementando la cuenta). Cuando la cuenta del semaforo llega a 0, todos los recursos estaran en uso. Despues, los procesos que deseen usar un recurso se bloquearan hasta que la cuenta sea mayor que 0.

Tambien podemos usar los semaforos para resolver diversos problemas de sincronizacion. Por ejemplo, considere dos procesos que se esten ejecutando de forma concurrente: P1 con una instruccion S1 y P2 con una instruccion S2. Suponga que necesitamos que S2 se ejecute solo despues de que Sl se haya completado. Podemos implementar este esquema dejando que P1 Y P2 compartan un semaforo comun synch, inicializado con el valor 0, e insertando las instrucciones:

s1;
signal(synch);
en el proceso P1, y las instrucciones
wait(synch); S2;

en el proceso P2. Dado que synch se inicializa con el valor 0, P2 ejecutara S2 solo despues de que P1 haya invocado signal ( synch), instruccion que sigue a la ejecucion de S1.

do
waiting(mutex);

???????????? // seccion critica
signal(mutex);

??????????? // seccion restante
}while (TRUE);

??? Implementacion
La principal desventaja de la definicion de semaforo dada aqui es que requiere una espera activa. Mientras un proceso esta en su seccion critica, cualquier otro proceso que intente entrar en su seccion critica debe ejecutar continuamente un bucle en el codigo de entrada. Este bucle continuo plantea claramente un problema en un sistema real de multiprogramacion, donde una sola CPU se comparte entre muchos procesos.

La espera activa desperdicia ciclos de CPU que algunos otros procesos podrian usar de forma productiva. Este tipo de semaforo tambien se denomina cerrojo mediante bucle sin fin (spinlock), ya que el proceso "permanece en un bucle sin fin" en espera de adquirir el cerrojo. (Los cerrojos mediante bucle sin fin tienen una ventaja y es que no requieren ningun cambio de contexto cuando un proceso tiene que esperar para adquirir un cerrojo.

Los cambios de contexto pueden llevar un tiempo considerable. Por tanto, cuando se espera que lo-s cerrojos se mantengan durante un periodo de tiempo corto, los cerrojos mediante bucle sin fin pueden resultar utiles; por eso se emplean a menudo en los sistemas multiprocesador, donde una hebra puede "ejecutar un bucle" sobre un procesador mientras otra hebra ejecuta su seccion critica en otro procesador).

Para salvar la necesidad de la espera activa, podemos modificar la definicion de las operaciones de semaforo wa i t () y s i gna 1(). Cuando un proceso ejecuta la operacion wa i t () y determina que el valor del semaforo no es positivo, tiene que esperar. Sin embargo, en lugar de entrar en una espera activa, el proceso puede bloquearse a si mismo. La operacion de bloqueo coloca al proceso en una cola de espera asociada con el semaforo y el estado del proceso pasa al estado de espera. A continuacion, el control se transfiere al planificador de la CPU, que selecciona otro proceso para su ejecucion.

Un proceso bloqueado, que esta esperando en un semaforo S, debe reiniciarse cuando algun otro proceso ejecuta una operacion signal (). El proceso se reinicia mediante una operacion wakeup () , que cambia al proceso del estado de espera al estado de preparado. El proceso se coloca en la cola de procesos preparados. (La CPU puede o no conmutar del proceso en ejecucion al proceso que se acaba de pasar al estado de preparado, dependiendo del algoritmo de planifigacion de la CPU.)
Para implementar semaforos usando esta definicion, definimos un semaforo como una estructura "C":

typedef struct {
int value;
struct process *list;
}semaphore;

Cada semaforo tiene un valor (value) entero y una lista de procesos list. Cuando un proce
so tiene que esperar en un semaforo, se anade a la lista de procesos. Una operacion signa1 () elimina un proceso de la lista de procesos en espera y lo despierta.
La operacion de semaforo wait () ahora se puede definir del siguiente modo:

wait(semaphore *S) {
S->value--;
if (S->value < 0) {
anadir este proceso a S->list;
block();
}
}

    La operacion de semaforo signal () ahora puede definirse asi:

signal(semaphore *S) {
S->value++;}
if (S->value <= 0) {
eliminar un proceso P de S->list;
wakeup(P);
}
}

La operacion block () suspende al proceso que la ha invocado. La operacion wakeup () reanuda la ejecucion de un proceso bloqueado P. Estas dos operaciones las proporciona el sistema operativo como llamadas al sistema basicas.

Observe que, aunque bajo la definicion clasica de semaforos con espera activa, el valor del semaforo nunca es negativo, esta implementacion si que puede tener valores negativos de semaforo. Si el valor del semaforo es negativo, su modulo es el numero de procesos en espera en dicho semaforo. Este hecho resulta de conmutar el orden de las operaciones de decremento y de prueba en la implementacion de la operacion wait ().

 La lista de procesos en espera puede implementarse facilmente mediante un campo de enlace en cada bloque de control de proceso (PCB). Cada semaforo contiene un valor entero y un puntero a la lista de bloques PCB. Una forma de anadir y eliminar procesos de la lista de manera que se garantice un tiempo de espera limitado consiste en usar una cola FIFO, donde el semaforo contenga punteros a ambos extremos de la cola. Sin embargo, en general, la lista puede utilizar cualquier estrategia de gestion de la cola. El uso correcto de los semaforos no depende de la estrategia concreta de gestion de la cola que se emplee para las listas de los semaforos.

 El aspecto critico de los semaforos es que se deben ejecutar atomicamente: tenemos que garantizar que dos procesos no puedan ejecutar al mismo tiempo sendas operaciones waitO y signal () sobre el mismo semaforo. Se trata de un problema de seccion critica. En un entorno de un solo procesador (es decir, en el que solo exista una CPU), podemos solucionar el problema de forma sencilla inhibiendo las interrupciones durante el tiempo en que se ejecutan las operaciones wait () y signal (). Este esquema funciona adecuadamente en un entorno de un solo procesador porque, una vez que se inhiben las interrupciones, las instrucciones de los diferentes procesos no pueden intercalarse: solo se ejecuta el proceso actual hasta que se reactivan las interrupciones y el planificador puede tomar de nuevo el control.

En un entorno multiprocesador, hay que deshabilitar las interrupciones en cada procesador; si no se hace asi, las instrucciones de los diferentes procesos (que esten ejecutandose sobre diferentes procesadores) pueden intercalarse de forma arbitraria. Deshabilitar las interrupciones en todos los procesadores puede ser una tarea compleja y, ademas, puede disminuir seriamente el rendimiento. Por tanto, los sistemas SMP deben proporcionar tecnicas alternativas de bloqueo, como por ejemplo cerrojos mediante bucle sin fin, para asegurar que las operaciones wait () y signa l () se ejecuten atomicamente.

 Es importante recalcar que no hemos eliminado por completo la espera activa con esta definicion de las operaciones wait () y signal (); en lugar de ello, hemos eliminado la espera activa de la seccion de entrada y la hemos llevado a las secciones criticas de los programas de aplicacion. Ademas, hemos limitado la espera activa a las secciones criticas de las operaciones wait() y signal (), y estas secciones son cortas (si se codifican apropiadamente, no deberian tener mas de unas diez instrucciones). Por tanto, la seccion critica casi nunca esta ocupada y raras veces se produce este tipo de espera; y, si se produce, solo dura un tiempo corto. En los programas de aplicacion, la situacion es completamente diferente, porque sus secciones criticas pueden ser largas (minutos o incluso horas) o pueden estar casi siempre ocupadas. En tales casos, la espera activa resulta extremadamente ineficiente.

Interbloqueos e inanicion

La implementacion de un semaforo con una cola de espera puede dar lugar a una situacion en la que dos o mas procesos esten esperando indefinidamente a que se produzca un suceso que solo puede producirse como consecuencia de las operaciones efectuadas por otro de los procesos en espera. El suceso en cuestion es la ejecucion de una operacion signal (). Cuando se llega a un estado asi, se dice que estos procesos se han interbloqueado.

Para ilustrar el concepto, consideremos un sistema que consta de dos procesos, Po y Pl, con acceso cada uno de ellos a dos semaforos, S y Q, configurados con el valor 1:

Po ??????????????????     Pi
wait (S)?????????? ?wait (Q);
wait (Q)??????????  wait (S);
signal (S)??????  signal (Q);
signal (Q)??????  signal (S);

Suponga que Po ejecuta wait(S) y luego P1 ejecuta wait(Q). Cuando Po ejecuta wait(Q), debe esperar hasta que P1 ejecute signal (Q). De forma similar, cuando P1 ejecuta wait (S), tiene que esperar hasta que Po ejecute signal(S). Dado que estas operaciones signal() no pueden ejecutarse, Po y Pl se interbloquean.

Decimos que un conjunto de procesos esta en un estado de interbloqueo cuando todos los procesos del conjunto estan esperando un suceso que solo puede producirse como consecuencia de las acciones de otro proceso del conjunto. Los sucesos que mas nos interesan aqui son los de adquisicion y liberacion de recursos, pero tambien hay otros tipos de sucesos que pueden dar lugar a interbloqueos. En ese capitulo describiremos varios mecanismos para tratar los problemas de interbloqueo.

Otro problema relacionado con los interbloqueos es el del bloqueo indefinido o muerte por inanicion, una situacion en la que algunos procesos esperan de forma indefinida dentro del semaforo. El bloqueo indefinido puede producirse si anadimos y eliminamos los procesos a la lista asociada con el semaforo utilizando un esquema LIFO (last-in, first-out).

Mecanismos de Monitoreo 

 

Aunque los semaforos proporcionan un mecanismo adecuado y efectivo para el proceso de sin-cronizacion, un uso incorrecto de los mismos puede dar lugar a errores de temporizacion que son dificiles de detectar, dado que estos errores solo ocurren si tienen lugar algunas secuencias de eje-cucion concretas y estas secuencias no siempre se producen.

Hemos visto un ejemplo de dichos errores en el uso de contadores en la solucion del problema productor-consumidor (Seccion 6.1). En ese ejemplo, el problema de temporizacion se producia raras veces, e incluso entonces el valor del contador parecia ser razonable: lo que pasaba es que diferia en 1 del valor correcto. Pero aunque el valor pareciera correcto, no era aceptable y es por esta razon que se introdujeron los semaforos.

Lamentablemente, estos errores de temporizacion pueden producirse tambien cuando se emplean semaforos. Para ilustrar como, revisemos la solucion con semaforos para el problema de la seccion critica. Todos los procesos comparten una variable de semaforo mutex, que se iniciali-za con el valor 1. Cada proceso debe ejecutar una operacion wait (mutex) antes de entrar en la seccion critica y una operacion signal (mutex) despues de la misma. Si esta secuencia no se lleva a cabo, dos procesos podrian estar dentro de sus secciones criticas al mismo tiempo. Examinemos los problemas a los que esto da lugar. Observe que estos problemas surgiran inclu-so aunque solo sea un unico proceso el que no se comporte de la forma adecuada; dicha situacion puede deberse a un error de programacion no intencionado o a que un cierto programador no tenga muchas ganas de cooperar.

Suponga que un proceso intercambia el ordenen el que se ejecutan las operaciones wait() y signal (), dando lugar a la siguiente secuencia de ejecucion:

signal(mutex);
seccion critica
wait(mutex);

En esta situacion, varios procesos pueden estar ejecutando sus secciones criticas simultane-amente, violando el requisito de exclusion mutua. Observe que este error solo puede des-cubrirse si varios procesos estan activos simultaneamente en sus secciones criticas y que esta situacion no siempre se produce.

???? Suponga que un proceso reemplaza signal(mutex) por wait(mutex). Es decir, ejecuta

wait(mutex);

seccion critica wait(mutex);

En este caso, se producira un interbloqueo.

•     Suponga que un proceso omite la operacion wait( mutex ), la operacion signal (mutex) , o ambas. En este caso, se violara la exclusion mutua o se producira un interbloqueo.

Estos ejemplos ilustran los distintos tipos de error que se pueden generar facilmente cuando los programadores emplean incorrectamente los semaforos para solucionar el problema de la seccion critica..

Para abordar tales errores, los investigadores han desarrollado estructuras de lenguaje de alto nivel. En esta seccion, vamos a describir una estructura fundamental de sincronizacion de alto nivel, el tipo monitor.

    Utilizacion

Un tipo, o un tipo abstracto de datos, agrupa una serie de datos privados con un conjunto de metodos publicos que se utilizan para operar sobre dichos datos. Un tipo monitor tiene un con-junto de operaciones definidas por el programador que gozan de la caracteristica de exclusion mutua dentro del monitor. El tipo monitor tambien contiene la declaracion de una serie de variables cuyos valores definen el estado de una instancia de dicho tipo, junto con los cuerpos de los procedimientos o funciones que operan sobre dichas variables. En la Figura 6.16 se muestra la sin-taxis de un monitor. La representacion de un tipo monitor no puede ser utilizada directamente por los diversos procesos. Asi, un procedimiento definido dentro de un monitor solo puede acceder a las variables declaradas localmente dentro del monitor y a sus parametros formales. De forma similar, a las variables locales de un monitor solo pueden acceder los procedimientos locales.

La estructura del monitor asegura que solo un proceso este activo cada vez dentro del monitor. En consecuencia, el programador no tiene que codificar explicitamente esta restriccion de sincronizacion. Sin embargo, la estructura de monitor, como se ha definido hasta ahora, no es lo suficientemente potente como para modelar algunos esquemas de sincronizacion. Para ello, necesitamos definir mecanismos de sincronizacion adicionales. Estos mecanismos los proporciona la estructura condition. Un programador que necesite escribir un esquema de sincronizacion a medida puede definir una o mas variables de tipo condition:

    condition x, y;

Las unicas operaciones que se pueden invocar en una variable de condicion son wait () y signal () . La operacion

x.wait();

indica que el proceso que invoca esta operacion queda suspendido hasta que otro proceso invo-que la operacion

x.signal();

La operacion x.signal() hace que se reanude exactamente uno de los procesos suspendidos. Si no habia ningun proceso suspendido, entonces la operacion signal () no tiene efecto, es decir, el estado de x sera el mismo que si la operacion nunca se hubiera ejecutado Compare esta operacion con la operacion signal () asociada con los semaforos, que siempre afectaba al estado del semaforo.

Suponga ahora que, cuando un proceso invoca la operacion x. signal(), hay un proceso en estado suspendido asociado con la condicion x. Evidentemente, si se permite al proceso sus-pendido Q reanudar su ejecucion, el proceso P que ha efectuado la senalizacion debera esperar; en caso contrario, P y Q se activarian simultaneamente dentro del monitor. Sin embargo, observe que conceptualmente ambos procesos pueden continuar con su ejecucion. Existen dos posibilidades:

1. Senalizar y esperar. P espera hasta que Q salga del monitor o espere a que se produzca otra condicion.
2. Senalizar y continuar. Q espera hasta que P salga del monitor o espere a que se produzca otra condicion.

Hay argumentos razonables en favor de adoptar cualquiera de estas opciones. Por un lado, puesto que P ya estaba ejecutandose en el monitor, el metodo de senalizar y continuar parece el mas razonable. Por otro lado, si permitimos que la hebra P continue, para cuando se reanude la ejecu-cion de Q, es posible que ya no se cumpla la condicion logica por la que Q estaba esperando. En el lenguaje Pascal Concurrente se adopto un compromiso entre estas dos opciones: cuando la hebra P ejecuta la operacion signal, sale inmediatamente del monitor. Por tanto, la ejecucion de Q se reanuda de forma inmediata.

monitor nombre del monitor {
// declaraciones de variables compartidas procedimiento P1 ( . . . )?????????????????????????????????????????????????????????? {

}
procedimiento P2 (??????????????? . . )???????? {

}
procedimiento Pn ( .????????????????????? )????? {

}
codigo de inicializacion ( .???? )?????????? {
}
}