La vista antes dada permite llegar a un modelo del sistema operativo donde el nivel más bajo es el planificador y el siguiente lo forman una variedad de procesos (creados por los usuarios o partes del sistema operativo).
0 | 1 | … | N -2 | N -1 |
Planificador | ||||
En el planificador no solo se considera el planificador de procesos sino también los manejadores de interrupción y la comunicación entre los procesos.
La instrumentación efectiva del modelo de procesos se logra mediante el uso de la tabla de procesos antes explicada. Para tener una idea más precisa aún de las informaciones contenidas en esta estructura (Fig2-4, pag. 50, Tanembaun).
Programación Concurrente. Grafos de precedencia.
El término programación concurrente o simplemente concurrencia se refiere a la ejecución paralela de instrucciones o procesos (aunque sea seudoparalela se deberán tener en cuanta las mismas consideraciones). Resulta conveniente revisar primero lo referente a las instrucciones.
Suponga que se dispone de un procesador con varias unidades funcionales para realizar las instrucciones o simplemente se tienen múltiples CPU y se desean ejecutar en grupo de instrucciones pertenecientes a un programa.
S1: a = x + y;
S2: b = z + 1;
S3: c = a – b;
S4: w = c + 1;
Lógicamente la instrucción c = a – b no puede ser ejecutada hasta que no hayan sido realizadas la S1 y la S2 de forma tal que los valores de a y b hayan sido calculados. Lo mismo ocurre con S4 con respecto a S3. En cambio las instrucciones a = x + y, y b = z + 1 se pueden ejecutar concurrentemente debido a que una no depende de la otra.
Lo importante de notar en este ejemplo es que dentro de un proceso existen restricciones de precedencia entre las distintas instrucciones. Para esquematizar estas situaciones se hace uso de los llamados grafos de precedencia.
Un grafo de precedencia es un grafo dirigido y sin ciclos donde los nodos corresponden a instrucciones. Un arco desde un nodo Si a un nodo Sj significa que la instrucción Sj solo puede ser ejecutada después que se realice la Si.
Por ejemplo, en las instrucciones antes indicadas se tendría:
Otro ejemplo de grafo de precedencia podría ser:
Condiciones de concurrencia y especificación.
Para que dos instrucciones puedan ejecutarse concurrentemente deberán cumplir ciertas condiciones. A estas se le llaman condiciones de concurrencia.
Definamos el conjunto
R(Si) = {a1, a2, …, an} como el conjunto de lectura para Si, este está formado por todas las variables cuyos valores son referenciados en las instrucción Si durante su ejecución.
Definamos el conjunto
W(Si) = {b1, b2, …, bm} como el conjunto de escritura para Si, es decir todas las variables que cambian de valor (se escriben) como resultado de la ejecución de la instrucción Si.
Considerando la ecuación a = x + y se tendrá:
R(Si) = {x, y} W(Si) = {a}
Si se toma la ecuación c = a – b
R(S3) = {a, b} W{S3) = {c}
Para que dos instrucciones sucesivas Sa y Sb puedan ser ejecutadas concurrentemente y producir el mismo resultado se tienen que cumplir las siguientes condiciones:
1.- R(Sa) ^ W(Sb) = {}
2.- R(Sb) ^ W(Sa) = {}
3.- W(Sa) ^ W(Sb) = {}
Si aplicamos estas condiciones a S1: a = x + y, y a S3: c = a – b veremos que efectivamente ellas no pueden ejecutarse concurrentemente ya que:
R(S3) ^ W(S1) = {a}
El grafo de precedencia es un medio útil para ver las restricciones de precedencia que puedan existir en un conjunto de instrucciones pertenecientes a un proceso, pero no permiten presentar cálculos concurrentes en un lenguaje de programación.
Las instrucciones fork and join fueron unas de las primeras notaciones que se utilizaron para especificar en un programa la ejecución concurrente de instrucciones.
La instrucción fork L produce en un programa dos hilos de ejecución concurrentes. Uno comienza en la etiqueta L y el otro en la instrucción siguiente al fork
La instrucción join permite unir o recombinar varios hilos de ejecución en uno solo. Cada una de las computaciones deben solicitar ser unidas con las otras. Dado que cada hilo de ejecución debe ejecutar el join y lo realiza en momentos diferentes, todos terminarán menos el último. Debido a que el join necesita saber cuantos hilos se deberán unir para poder terminar a todos menos el último, la instrucción tiene un parámetro con esta información.
El efecto de la instrucción join es como sigue:
count = count – 1;
if (count ! = 0) quit;
donde quit es una instrucción que resulta en la terminación de la ejecución. Ambas instrucciones se ejecutan en forma indivisible.
A manera de ejemplos veamos los dos que se han utilizado anteriormente .
count = 2; count1 = 2;
fork L1; count2 = 2;
a = x + y; S1;
go to L2; fork L1;
L1: b = z + 1; fork l2;
L2: join count; S2;
c = a – b; go to L3;
w = c + 1; L2:S3;
L3:join count2;
S5;
go to L4;
L1:S4;
L4:join count1;
S6;
La construcción fork-join tiene la desventaja de no ser estructurada y por ello le son inherentes todas las críticas que ha recibido el go to.
Una construcción estructurada para especificar concurrencia es la parbegin / parend. Su forma es:
parbegin S1; S2 ; … ; Sn parend;
Todas la instrucciones encerradas entre parbegin y parend se ejecutarán concurrentemente.
A manera de ejemplo veamos los dos anteriormente utilizados con el fork y el join :
parbegin S1;
a = x + y; parbegin
b = z + 1; S4;
parend; {
c = a – b; parbegin
w = c + 1; S2;
S3;
parend;
S5;
}
parend;
S6;
Esta construcción estructurada tiene la desventaja de que no puede especificar todos los grafos de precedencia. No obstante, esta herramienta, unida con otros mecanismos, si da una respuesta totalmente satisfactoria.
Ahora es necesario extender los aspectos antes tratados, en cuanto al uso de grafos de precedencia y las especificaciones de programación, de instrucciones dentro de un proceso a la relación entre procesos.
En este caso, cada nodo de un grafo de precedencia será visto como un proceso secuencial. En tal ambiente los procesos aparecen y desaparecen dinámicamente durante el tiempo de duración de una ejecución.
Cuando un proceso Pi ejecuta una instrucción fork L, se crea un proceso nuevo Pj. Al arribarse a la instrucción join count, el contador es decrementado por uno y si el resultado es cero, el proceso continua su ejecución y en caso contrario terminará .
Jerarquía entre procesos.
Como ya se indicó con anterioridad un proceso puede crear otros procesos. De igual forma los nuevos pueden crear otros y así sucesivamente.
Para representar gráficamente este proceso de creación sucesiva de procesos se utiliza el llamado grafo de procesos que no es más que un árbol dirigido con raíz . Un arco del nodo Pi al nodo Pj. En este caso se dice que Pi es el padre de Pj o que Pj es hijo de Pi. Cada proceso tiene un solo padre, pero tantos hijos como sean necesarios.
Existen diversas formas en que un proceso puede crear uno al hacer uso de una operación con este objetivo (como la fork). Para ello se debe tener en cuenta como continúa la ejecución y como se compartirán los recursos.
Desde el punto de vista de como continúa la ejecución se pueden instrumentar dos casos:
? El padre continúa la ejecución concurrentemente con el hijo (construcción fork/join).
? El padre espera hasta que el hijo termina (construcción parbegin/parend).
Desde el punto de vista de cómo se compartirán los recursos se pueden instrumentar también dos casos:
? El padre y el hijo comparten todas las variables (construcción forK/join).
? El hijo solo tiene acceso a un subconjunto de las variables del padre (esquema del Unix).
Un proceso termina cuando ejecuta su última instrucción, sin embargo existen circunstancias en que se requiere terminarlo en forma forzada. Un proceso termina a otro mediante una instrucción del tipo Kill Id.
La operación kill es usualmente invocada solamente por un proceso padre para culminar la ejecución de un hijo. Como la instrucción requiere la identificación del proceso a ser terminado, la instrucción fork da como retorno esta información (Id = fork L). Existen numerosas razones por las cuales un padre puede detener la ejecución de un hijo.
En muchos sistemas operativos se establece la condición de que los procesos hijos no pueden continuar la ejecución si el padre ha sido finalizado.
Un proceso que no termina su ejecución durante todo el tiempo en que el sistema operativo está funcionando se dice que es estático. Un proceso que finaliza se dice que es dinámico.
Si un sistema operativo consiste de solo un número limitado de procesos estáticos entonces su correspondiente grafo de procesos será también estático (es decir nunca cambia). En caso diferente será dinámico. La estructura estática solo está presente en sistemas operativos muy simples.
La jerarquía de procesos antes discutida está presente en la mayoría de los sistemas operativos que soportan el modelo de procesos.
Para terminar veamos un ejemplo simple consistente de dos procesos secuenciales que se ejecutan concurrentemente y que comparten algunos datos en común. Este es un ejemplo representativo de los sistemas de operación.
El ejemplo consiste en el clásico problema del productor/consumidor. Un proceso productor genera información que es tomada por el proceso consumidor. Por ejemplo, un manejador de una impresora produce caracteres que son consumidos por la impresoras.
Para permitir a los procesos productor y consumidor ejecutarse concurrentemente se creará una piscina de buffers. El productor generará en un buffer, mientas que el consumidor tomará de otro buffer (si lo hicieran en el mismo tendrían que correr secuencialmente).
El productor y el consumidor deberán ser coordinados de forma tal que el consumidor no trate de consumir elementos que aún no han sido producidos. En este caso, el consumidor deberá esperar hasta que el elemento es producido.
El problema que estamos tratando tiene dos formas de presentarse: el primer caso consiste en fijar un límite (diga menos n) en la cantidad de buffers disponibles en la piscina, en segundo no se establece esta restricción y por ello el productor siempre podrá generar nuevos elementos (siempre habrá buffers vacíos).
La solución que se planteará estará referida al primer caso y por ello el productor deberá esperar cuando todos los buffers estén llenos.
La piscina de buffers compartida por ambos procesos se instrumentará como un arreglo circular con dos punteros lógicos: in y out. La variable in apunta al próximo buffer libre, mientras out apunta al primer buffer lleno.
Para controlar las condiciones extremas de todos los buffers vacíos o llenos se podrían utilizar estas dos posibilidades (in = out y in + 1 % n = out, respectivamente), pero en este caso solo se permite que se puedan llenar hasta n – 1 buffers (se obliga a que exista uno vacío).
Para remediar esta dificultad se incorpora en la solución un contador que originalmente recibe valor 0. Esta variable se incrementará cada vez que se llene un buffer de la piscina y decrementando cada vez que se consume uno lleno de información.
/* Ejemplo de productor consumidor */
#define n 100
#define TRUE 1
typedef …item;
item buffer[n];
short int counter = 0, in = 0, out = 0;
void producir_elemento(punt_nextp)
item *punt_nextp;
{
.
.
.
}
void concumir_elemento(nextc)
item nextc;
{
.
.
.
}
void productor()
{
item nextp;
while (TRUE){
producir_elemento(&nextp);
while (counter= =n) skip;
buffer [in] = nextp;
in = (in+1) % n;
counter++;
}
}
void consumidor()
{
item nextc;
while (TRUE) {
while (counter = = 0) skip;
nextc = buffer[out];
out = (out+1) % n;
counter–;
consumir_elemento(nextc);
}
}
main()
{
parbegin
productor();
condumidor();
parend;
}
La instrucción skip no hace nada y por ello el while se repite. Nótese que esta espera implica que se continúe ejecutando aún cuando no se está haciendo nada útil (espera ocupada).
La incorporación de las instrucciones parbegin y parend se hacen con el objetivo de brindar la opción de concurrencia.
Bibliografía:
? Operating System Concepts, Peterson y Silberschatz, pag 103 – 110, pag 307-325.
? Oprating Systems: Design and implementation, Tanembaum, pag 45-51.
Autor:
Maikel J. Menendez
| Página siguiente |