|
2.- PROCESOS
| Versión del S.O. | BCP | |||||||||
| Fecha | Estado del proceso | |||||||||
| Directorio de BCP’s | Cont. programa | |||||||||
| Cont. pila | ||||||||||
| PID | ||||||||||
| Registros CPU | ||||||||||
| Lím. de Memoria | ||||||||||
| Adr proceso actual 1 | ... | |||||||||
| Adr proceso actual 2 | ||||||||||
| Adr proceso actual N | ||||||||||
| Adr cola procesador | P1 | P2 | P3 | P4 |
El control y planificación de la interrupción se resume así:
1. El hardware almacenaen una pila el contador del programa
2. El hardware carga el nuevo contador del programa el vector de interrupción
3. El procedimiento del lenguaje ensamblador resguarda los registros.
4. El procedimiento en lenguaje ensamblador configura la nueva pila
5. El procedimiento en C señala el proceso de servicio como listo
6. El planificador decide cual es el proceso que se ejecuta a continuación
7. El procedimiento en C regresa al código en ensamblador
8. El procedimiento en lenguaje ensamblador inicia el proceso activo.
2.7.-Implementación de Procesos
2.7.1.- Operaciones sobre procesos
Los S.O. con multitarea permiten numerosas operaciones dedicadas a la gestión de procesos. Entre ellas, las más importantes : creación, eliminación, obtención de información, modificación, retardo y activación.
Creación de procesos : crear (id_proceso, atributos) ;
El S.O. primero comprobará que no existen errores en la llamada (por ejemplo, comprueba que el procedimiento indicado no exista). A continuación se crea el proceso, se pasan los atributos como parámetros, se reserva memoria para el proceso (tanto para el BCP como para el código y los datos) y se añade a la cola de preparado.
Eliminación de procesos : eliminar (id_proceso) ;
Para eliminar un proceso es necesario que este sea hijo del proceso eliminador, ya que de no ser así podría volverse inconsistente el sistema. Una vez realizada la llamada, el S.O. verifica que no existen errores para a continuación liberar los recursos retenidos por el proceso. Finalmente se destruye el BCP.
Obtención de información : inf_proc (id_proceso,est_BCP) ;
Devolverá una copia del BCP del proceso requerido. El S.O. debe comprobar que no existen errores en los parámetros.
Modificación de la información de un proceso : mod _inf (id_proceso, est_BCP) ;
El proceso modificador debe enviar como parámetros el PID del proceso que modifica y un nuevo BCP que sustituya al actual. El S.O. comprobará los posibles errores producidos.
Retardar un proceso : retardar (tiempo) ;
El proceso que realiza esta llamada se autodetiene durante el tiempo indicado y pierde el control de la CPU durante ese tiempo. Los ciclos de reloj de espera se anotan en el BCP (utilizados posteriormente en la planificación de procesos). Finalmente, cuando el tiempo transcurre, el núcleo del S.O. introduce al proceso en la cola de procesos preparados para intentar ejecutarlo inmediatamente.
Activar procesos retardados : activar (id_proceso);
Esta función es privilegiada. El mecanismo para despertar procesos se activa en cada ciclo de reloj, recorriéndose la cola de procesos retardados para activarlos o disminuir en una unidad el número de pulsos de espera. Devuelve un código de error si el PID que se pasa no existe.
2.8.- Razones para la terminación de un proceso
| Terminación normal | El proceso ejecuta una llamada a un servicio del SO que indica que ha terminado de ejecutar. |
| Tiempo límite excedido | El proceso ha ejecutado por más tiempo límite total especificado. Hay varias posibilidades para la clase de tiempo que se mide. Entre éstas se incluyen el tiempo total transcurrido ("tiempo de reloj"), el tiempo que ha estado ejecutado y, en el caso de un proceso interactivo, el tiempo transucrrido desde que el usuario realizó su última entrada de datos. |
| No hay memoria disponible | El proceso necesita más memoria de la que el sistema le puede proporcionar. |
| Violación de límites | El proceso trata de acceder a una posición de memoria a la que no le está permitido acceder. |
| Error de protección | El proceso intenta utilizar un recurso o un archivo que no le está permitido utilizar, o trata de utilizarlo de forma incorrecta, como escribir en un archivo que es sólo de lectura. |
| Error aritmético | El proceso intenta hacer un cálculo prohibido, como una división por cero, o trata de almacenar un número mayor del que el hardware acepta. |
| Tiempo máximo de espera rebasado | El proceso ha esperado más allá del tiempo máximo especificado para que se produzca cierto suceso. |
| Fallo de E/S | Se produce un error en la entrada o la salida, tal como la incapacidad de encontrar un archivo, un fallo de lectura o escritura después de un número máximo de intentos (cuando, por ejemplo, hay una región defectuosa en una cinta), o una operación ilegal (como intentar leer de una impresora). |
| Instrucción inválida | El proceso intenta ejecutar una instrucción inexistente (a menudo como resultado de un salto a una zona de datos para intentar ejecutar los datos). |
| Instrucción privilegiada | El proceso intenta usar una istrucción reservada para el sistema operativo. |
| Mal uso de los datos | Un elemento de dato es de un tipo equivocado o no está inicializado. |
| Intervención del operador o de SO | Por alguna razón el operador o el sistema operativo termina con el proceso (por ejemplo, si existe un interbloqueo). |
| Terminación del padre | Cuando un proceso padre finaliza, el sistema operativo puede diseñarse para terminar automáticamente con todos sus descendientes. |
| Solicitud del padre | Un proceso padre tiene normalmente la autoridad de terminar con cualquiera de sus descendientes. |
2.9.-Regiones Críticas
¿Cómo evitar las condiciones de competencia? La clave para evitar los problemas en ésta y otras situaciones relacionadas con la memoria compartida, archivos compartidos y cualquier otra cosa compartida, es determinar una forma de prohibir que más de algún proceso lea o escriba en los datos compartidos a la vez. En otras palabras, lo que necesitamos es la exclusión mutua (una forma de garantizar que si un proceso utiliza una variable o archivos compartidos, los demás procesos no puedan utilizarlos).
El problema de evitar las condiciones de competencia también se puede formular de manera abstracta. Durante cierta parte del tiempo, un proceso está ocupado realizando cálculos internos y otras labores que no conducen a condiciones de competencia. Sin embargo, en algunas ocasiones un proceso puede tener acceso a la memoria compartida de archivos o realizando labores críticas que pueden llevar a conflictos. Esa parte del programa, en la cual se tiene acceso a la memoria compartida se llama la Sección o Región Crítica.
Aunque esta condición evita los conflictos, no es suficiente para que los procesos paralelos cooperen en forma correcta y usen de modo eficaz los datos compartidos.
La exclusión mutua debe ponerse en práctica, sólo cuando los procesos obtienen acceso a datos compartidos modificables; cuando los procesos realizan operaciones que no entran en conflictos con otras, deben permitirse que procedan concurrentemente.
Cuando un proceso obtiene acceso a datos compartidos modificables, se dice que se encuentra en una sección crítica. Para evitar alguna clase de problemas se debe asegurar que cuando un proceso se encuentre en una sección crítica, los demás procesos no pueden entrar a sus propias secciones críticas.
Si un proceso se encuentra en su sección crítica, otros procesos pueden seguir ejecutándose fuera de sus secciones críticas. Cuando un proceso abandona su región, otro proceso que esperaba entrar en su propia sección podrá hacerlo. El problema de la programación concurrente está en que se cumpla la exclusión mutua.
Cuando se encuentra en una región crítica se está hablando de un estado especial que se concede a un proceso. El proceso tiene acceso exclusivo a los datos compartidos y los demás procesos que requieren acceso a esos datos y en ese momento deben esperar; por esto las secciones críticas deben ejecutarse tan rápido como sea posible. Un proceso no se debe bloquear dentro de su propia sección crítica y estas deben codificarse con mucho cuidado.
Si un proceso de una sección crítica termina, el S.O. al realizar su mantenimiento de terminaciones, debe liberar la exclusión mutua para que otros procesos puedan entrar en sus regiones críticas.
Necesitamos 4 condiciones para poder obtener una buena solución:
1. Dos procesos no deben encontrarse al mismo tiempo dentro de sus secciones críticas .
2. No se deben hacer hipótesis sobre la velocidad o el número de UCP.
3. Ninguno de los procesos que estén en ejecución fuera de su sección crítica puede bloquear a otros procesos.
4. Ningún proceso debe esperar eternamente para entrar a su sección crítica.
2.10.-Exclusión Mutua
Considérese un sistema con muchas terminales en tiempo compartido. Supóngase que los usuarios terminan con un retorno del carro cada línea que introducen en el sistema, que es necesario vigilar continuamente el número total de líneas introducidas por los usuarios desde que comenzó el día y que cada terminal de usuario está vigilada por un proceso diferente. Cada vez que uno de estos procesos recibe una línea desde una terminal de usuario, suma a una variable global compartida por todo el sistema, LÍNEAS_INTRO. Considérese que sucedería si dos procesos tratan de incrementar LÍNEAS_INTRO simultáneamente. Supóngase que cada proceso tiene su propia copia de código
CARGAR LÍNEAS_INTRO
SUMAR 1
ALMACENAR LÍNEAS_INTRO
Supóngase que LÍNEAS_INTRO tiene en este momento el valor 21687. Ahora supóngase que el primer proceso ejecuta las instrucciones CARGAR y SUMAR, dejando por tanto el valor 21688 en un acumulador. Después el proceso pierde el procesador (por haber expirado un cuanto) y el segundo proceso se apropia de él. El segundo proceso ejecuta las tres instrucciones y deja el valor de 21688 en LINEAS_INTRO.
Debido al acceso no controlado a la variable compartida LINEAS_INTRO, el sistema ha perdido de hecho el rastro de una de las líneas; el total correcto debería ser 21689.
Cada vez que uno de estos procesos recibe una línea desde una terminal de usuario, suma a una variable global compartida por todo el sistema, LINEAS_INTRO.
Considérese que sucedería si dos procesos tratan de incrementar LÍNEAS_INTRO simultáneamente. Supóngase que cada proceso tiene su propia copia de código.
CARGAR LÍNEAS_JNTRO
SUMAR 1
ALMACENAR LÍNEAS_JNTRO
Supóngase que LÍNEAS_JNTRO tiene en este momento el valor 21687. Ahora supóngase que el primer proceso ejecuta las instrucciones CARGAR y SUMAR, dejando por tanto el valor 21688 en un acumulador.
Después el proceso pierde el procesador (por haber expirado un cuanto) y el segundo proceso se apropia de él.
El segundo proceso ejecuta las tres instrucciones y deja el valor de 21688 en LÍNEASJNTRO. Debido al acceso no controlado a la variable compartida LÍNEAS_JNTRO, el sistema ha perdido de hecho el rastro de una de las líneas; el total correcto debería ser 21689.
2.11.- Solución de Peterson.
Un matemático holandés, T- Dekker. combinó la idea de los turnos y la idea de las variables de cerradura y las variables de advertencia con lo que fue el primero en dise-ñar una solución en software a! problema de exclusión mutua sin el requisito de la de alternancia estricta Véase Dijkstra (1965.) para un análisis del algoritmo de Dekker.
En 1981. G. L. Peterson descubrió una forma más sencilla para conseguir la exclu-sión mutua, lo cual hizo obsoleta la solución de Dekker. El algoritmo de Peterson se muestra en la figura . Este algoritmo consta de dos procedimientos escritos en ANSÍ C, lo que indica que hay que proporcionar prototipos de función para todas las funciones definidas y utilizadas. Es convencional la agrupación de dichos prototipos en archivos de encabezado. El primer renglón; de la figura incluye todos esos prototi-pos. Los detalles no son importantes por lo que no se enlistan en este libro.
Antes de utilizar las variables compartidas (es decir, antes de entrar a su región cri-tica). cada proceso llama a enter_region con su propio número de procesos. O o 1, como parámetro. Esta llamada provoca una espera, en caso necesario hasta que pueda entrar.
indude "prototypes.h" . .
#define false 0
#define true 1
#define N 2 . /• Numero de procesos */
int turn: /* ¿de quién es e1 turno? */
int interested[N) /• todos los valores Iniciales son 0(FALSE) •/
void enter_region(int process) /* proceso: quién entra (0 O 1) */
{
int other; . /* numero de los otros procesos •/
other = 1 - process: /* el opuesto de proceso ••I
interested(process) - TRUE: /• muestra que usted esta interesado */
turn = process: . /* establece bandera */
while (turn — proceess && interested[otherl -- TRUE) /* enunciado-null '.'
void 1eave_region(int process) /• proceso: quién sale (0 6 1) •/
intereseted(process) - FALSE: " 7* indica 1a salida de la región critica */
Figura Solución de Peterson para lograr la exclusión muña.——
Después de terminar con las variables compartidas. el proceso llama a leave_region pa-ra indicar que ha terminado y permitir la entrada de otro proceso, si así lo desea.
Veamos cómo funciona esta solución. En principio, ningún proceso esta en su re-gión critica- Ahora, el proceso 0 llama a enter_region. Indica su interés por determinar el elemento de su arreglo y hace turn=0. Puesto que el proceso 1 no está interesado. enier_region regresa en forma inmediata. Si el proceso 1 llama ahora a enter_region. esperará hasta que interested[0}=FALSE. evento que sólo ocurre cuando el proceso O llama a leave_region.
Consideremos ahora el caso en que ambos procesos llaman a enter_region de for-ma casi simultánea- Ambos almacenarán su número de proceso en turn. Sólo cuenta la última operación; la primera se pierde. Supongamos que el proceso 1 almacena el nú-mero en último lugar, por lo que turn=1. Cuando ambos procesos lleguen al enunciado while. el proceso O se ejecuta O veces y entra a su región critica. El proceso 1 hace un ciclo y no entra a su región critica.
2.12- La Instrucción TSL
Analizaremos ahora una propuesta que requiere poca ayuda del hardware. Muchas computadoras, en particular aquellas diseñadas teniendo en mente varios procesadores. tienen una instrucción TEST AND SET LOCK; (TSL) que funciona como sigue. Lee el contenido de una palabra de memoria en un registro para después almacenar un valor dis-tinto de cero en esa dirección de memoria Las operaciones de lectura y almacenamiento de la palabra tienen la garantía de ser indivisibles: ninguno de los de más procesadores puede tener acceso a la palabra hasta terminar la instrucción. La CPU que ejecuta la instrucción TSL cierra el bus de memoria para prohibir a las demás CPU el acceso a la memoria hasta terminar.
Para utilizar la instrucción TSL, se emplea una variable compartida, fiag, la cual coordina el acceso a la memoria compartida. Cuando f1ag=0, cualquier proceso puede darle el valor de 1 mediante la instrucción TSL y después leer o escribir en la memoria compartida. Al terminar, el proceso vuelve a hacer flog=0 mediante una instrucción normal move.
¿Cómo puede utilizarse esta instrucción para evitar que dos procesos entren en for-ma simultánea a sus regiones criticas? La solución aparece en la figura. En ella se muestra una subrutina de cuatro instrucciones en un lenguaje ensamblador ficticio (pe-ro típico). La primera instrucción copia el valor anterior de flag en un registro y des-pués hace flag=l. Después, el valor anterior se compara con 0. Si es distinto de cero. la cerradura ya estaba establecida, por lo que el programa regresa al principio y realiza de nuevo la prueba. Tarde o temprano, valdrá O (cuando salga de su región critica el proceso que &e encuentra en ese momento en dicha región) y la subrutina regresa con la cerradura establecida. La eliminación de la cerradura es sencilla: el programa sólo tiene que almacenar un O fag. No se requieren instrucciones especiales.
Ahora se dispone de una solución directa al problema de la sección crítica- Ante» de entrar a su sección crítica, un proceso Dama a enter_region, que hace una espera ocupada basta que se elimina la cerradura- para entonces retomar la cerradura y repi-sar.
Al salir de la sección crítica, el proceso llama a leave_region. que almacena O en fag. Como con todas las soluciones basadas en las regiones criticas, tos procesos de-ben llamar a enter_region y leave_region en los instantes correctos para que el método funcione. Si un proceso hace un engaño, la exclusión mutua fallara-
enter_region:
ts1 register.flac copia fag al registro y hace fag=1;
cr.r register.#0 ¿fag=0?
jn.í enter_region: si era distinto de cero , la cerradura estaba establecida, por lo que hay que hacer un ciclo
reg regresa a quien hizo la llamada
entra a la region critica
leave_region:
mov fag.#0 almacena un 0 en flag
ret regresa a quien hizo la llamada
Figura . Establecimiento y eliminación de cerraduras mediante TSl-
2.13- El problema del productor y el consumidor
Como ejemplo del uso de estas primitivas, consideremos el problema del produc-tor y el consumidor (también conocido como problema del almacén limitado). Dos procesos comparten un almacén (buffer) de tamaño fijo. Uno de ellos, el productor, co-loca información en el almacén (buffer), mientras que el otro, el consumidor, la obtiene de él.
El problema surge cuando el productor desea colocar un nuevo elemento en el al-macén (buffer). pero éste está totalmente ocupado. La solución para el productor es ir-se a dormir, para ser despenado cuando el consumidor ha eliminado uno o mas elementos. En forma análoga, si el consumidor desea eliminar un elemento del almacén (buffer) y ve que éste está vacio, se va a dormir hasta que el productor coloca algo en el almacén (buíTer) y despierta. '
Este punto de vista suena bástame sencillo, pero lleva al mismo tipo de condicio-nes de competencia que ya vimos en el directorio spooler. Para llevar un registro del número de elementos en el almacén (buffer). necesitamos una variable, cont. Si N es el número más máximo de elementos que pueden entrar en el almacén (buffer), el código del productor debe verificar primero si cont=N. En caso afirmativo, el productor se irá a dormir, en caso contrario, el productor añadirá un elemento e incrementará cont.
El código del consumidor es similar: primero verifica si cont=0. En caso afirmati-vo. se irá a dormir, en caso contrario, elimina un elemento y decremento el contador. Cada uno de los procesos también verifica si el otro debiera estar durmiendo, en caso de que no, lo despierta. El código del productor y el consumidor aparece en la figura .
include 'prototypes.h'
define N 100 /• numero de espacios en el almacén (buffer) •/
Int count = 0; . /•.número de elementos en el almacén (buffer) </
void producer(void)
int item;
while (TRUE) /• se repite eternamente •/ •
produce_item(iitem): /• genera e1 siguiente elemento •/
1f (count — N) s1eep(): /• si e1 almacén (buffer) esta lleno va a dormir */
enter_item(item); . - /• colocar elemento en el almacén (buffer) •/
if(count = couní * 1): /• incrementa el contador de elementos en el almacén (buffer) ••/
If (count =1) wakeup(consumer); . /• ¿Estaba vacio el almacén (buffer)? •/ '
void consumer'(void)
int item;
while (true) 1. /* se repite para siempre */
if (count =0);sep(); /• ,si e1 almacén (buffer) está vació, va a dormir */
remove_item(&item); /* retira el elemento del almacén(buffer) «/
(count - count – 1); /• decrementa el contador de elementos en el almacén (buffer) */
if (count =N-1) –wakeup(producer) /• ¿Estaba lleno el almacén(tuffer)? */
consume_ item(item); /* imprime el elemento */
Figura . El problema del productor y el consumidor con una condición de com-petencia fatal.
Para poder expresar las llamadas al sistema tales como SLEEP y wakeup en C, las exhibiremos como llamadas a rutinas de una biblioteca. No son parte de la biblioteca usual de C, pero podrían estar disponibles en cualquier sistema que contara en realidad con dichas llamadas al sistema. Los procedimientos enter_item y remove_item, que no se muestran, controlan las operaciones de colocación y eliminación de elementos en el almacén (huffer).
Regresemos a la condición de competencia. Esta puede aparecer debido a que count_no tiene restricciones..Podría ocurrir la siguiente situación. El almacén (buffer) está vacío y el consumidor acaba de leer count con un valor 0 En ese momento El planificador decide detener la ejecución del consumidor en forma temporal e iniciar la ejecución del productor
El productor introduce un elemento en el almacén (buffer), incrementa count y observa que su valor actual es 1. Mediante el razonamiento que count valía 0, y que entonces el consumidor estaba durmiendo, el productor llama a wakeup para despenar al consumidor.
Sin embargo, el consumidor no está dormido desde el punto de vista lógico, por lo que la señal de despertar se pierde. En la siguiente ejecución del consumidor, este pro-bará el valor de count que leyó antes, verá que es 0 y se irá a dormir. Tarde o temprano. el productor llenará el almacén (buffer) y también se dormirá. Ambos dormirán por siempre.
La esencia del problema es que un despertar enviado a un proceso que todavía no esté durmiendo se pierde. Si esto no ocurriese, todo iría bien. Un arreglo rápido consiste en modificar las reglas con el fin de añadir un bit de espera de despertar en este marco.
Cuando se intente despertar a un proceso ya despierto, el bit se activa. Más tar-de cuando el proceso intente ir a dormir, si el bit está activo, será desactivado, aunque el proceso siga despierto. Este bit de espera es como una alcancía de las señales para despertar.
Aunque el bit de espera funcione en este sencillo ejemplo, es fácil construir ejem-plos con tres o más procesos en los que un solo bit no_es suficiente. Podría hacer otro parche y añadir un segundo bit de espera o tal vez 8 o 32 de ellos, pero en principie el problema sigue ahí.
2.14- Planificación de Procesos
Justificación y generalidades.-
Ø Cuando son ejecutables varios procesos, tomando en cuenta la existencia de multiprogramación y de tiempo compartido el sistema operativo debe decidir cúal conviene ejecutar primero . La parte del SO a la que concierne esta decisión se llama planificador de procesos y los algoritmos que utiliza se denominan algoritmos de planificación de procesos.
Ø A la hora de planificar procesos es importante estimar la carga de CPU versus demanda de E/S de los mismos, pues interesa que haya un equilibrio entre las dos.
2.15- Elaboración del algoritmo de Planificación
1. IMPARCIALIDAD.- Asegurar que cada proceso tenga la parte que le corresponda de la CPU.
2. EFICIENCIA.- Mantener el CPU ocupada el 100% del tiempo.
3. TIEMPO DE RESPUESTA.- Minimizar el tiempo de respuesta para usuarios interactivos.
4. CAMBIO DE POSICION.- Minimizar el tiempo que los usuarios de un lote deben esperar para obtener salida.
5. RENDIMIENTO.- Maximizar el número de trabajos que se procesan por hora.
2.16- Otros algoritmos de Planificación
1) PLANIFICACION DE UN TORNEO.- Es uno de los algoritmos más antiguos, simples, imparciales y más ampliamente utilizados. En el que a cada proceso se le asigna un intervalo de tiempo, llamado su cantidad, en el cual se le permite su ejecución. Todo lo que el planificador necesita es hacer conservar una lista de procesos ejecutables.
GRAFICAMENTE:
2) PLANIFICACION POR PRIORIDAD.- Consiste en asignar a cada proceso una prioridad y se le permite la ejecución del proceso ejecutable que tenga la prioridad más alta.
2.17- Proceso en Uníx
Ø Un proceso UNIX tiene dos áreas de memoria: ejecución y control
Ø El área de ejecución es el programa (texto) más las zonas de memoria reservadas para la pila y los datos. Está en la zona de memoria virtual asignada al proceso.
Ø El área de control contiene los bloques de control que conserva la información acerca del proceso. Esta zona pertenece al núcleo del SO.
Ø El área de control tiene información que debe residir en memoria continuamente e información que puede ser enviada a disco con el área de ejecución cuando el planificador de procesos decida.
2.18- Conclusiones
Comunicar procesos entre sí mediante primitivas de comunicación (que se utilizan para garantizar que dos procesos no se encuentren jamás al mismo tiempo dentro de sus regiones críticas ).
Calcular las prioridades de los procesos y organizarlos en niveles de prioridad en función de dichos valores.
Seleccionar el proceso que tenga máxima prioridad y asignar tiempo de CPU.
Si el proceso termina su cuenta de ejecución (no hay bloqueo), el proceso pasa a la cola de su nivel de prioridad.
Si el proceso se bloquea durante su cuenta, el planificador selecciona inmediatamente otro proceso y le asigna tiempo de CPU.
Si un proceso retorna de una llamada al sistema y hay un proceso listo con mayor prioridad, el proceso de menor prioridad es desalojado de la CPU.
