Sistemas Operativos Unidad 2 y 3

Procesos e hilos

En los sistemas operativos multi-programados surge el concepto de proceso, asociado a la ejecución de un programa. En general, un proceso es un flujo de ejecución, representado básicamente por un contador de programa, y su contexto de ejecución, que puede ser más o menos amplio. Así, un proceso incluye en su contexto el estado de la pila, el estado de la memoria y el estado de la E/S, mientras que un thread típico tiene como contexto propio poco más que la pila. En algunos sistemas es posible determinar el contexto propio de un proceso en el momento de su creación, como ocurre con la llamada al sistema clone () de Linux.

Uno de los objetivos del sistema operativo es la representación de los procesos y el soporte de los cambios de contexto entre procesos, que posibilitan la compartición del recurso CPU. El acceso a otros recursos compartidos y la comunicación entre procesos relacionados (por ejemplo, de una misma aplicación) hacen necesaria la utilización de mecanismos de sincronización dentro del sistema operativo. Típicamente, un proceso requiere la CPU durante un periodo de tiempo, realiza alguna operación de E/S, y vuelve a requerir la CPU, repitiéndose este ciclo hasta la finalización del programa.

Los tipos de llamadas al sistema referidas a los procesos, que un sistema operativo normalmente ofrece son:

·         Finalizar, abortar

·         Cargar, ejecutar.

·         Crear proceso, terminar proceso

·         Obtener atributos de proceso, establecer atributos de proceso.

·         Esperar un lapso de tiempo.

·         Esperar suceso, indicar la ocurrencia del suceso.

·         Asignar y liberar memoria.

Estados de un proceso: En su ciclo de vida el proceso pasa por diferentes estados. Básicamente:

·         Nuevo (new).

·         Ejecutándose (running)

·         En espera (waiting)

·         Listo para ejecutar (ready)

·         Terminado (terminated)

Bloque de control de procesos: cada proceso se representa en el sistema operativo con un bloque de control de proceso (PCB, Process control block) también llamado bloque de control de tarea.

·         Estado del proceso: el estado puede ser: nuevo, listo, en ejecución, en espera, detenido.

·         Contador de programa: el contador indica la dirección de la siguiente instrucción que se ejecutara para este proceso.

·         Registro de CPU: el número y tipo de registros varía dependiendo de la arquitectura del computador. Los registros incluyen acumuladores, registros, índice, punteros de pila y registros de propósito general, así como cualquier información de códigos de condición que haya. Junto con el contador de programa, esta información de estado se debe guardar cuando ocurre una interrupción, para que el proceso pueda continuar correctamente después.

·         Información de planificación de CPU: Esta información incluye una prioridad del proceso, punteros a colas de planificación y cualquier otro parámetro de planificación que haya.

·         Información de gestión de memoria: Esta información puede incluir datos tales como el valor de los registros de base y límite, las tablas de páginas o las tablas de segmentos, dependiendo del sistema de memoria empleado por el sistema operativo.

·         Información contable: Esta información incluye la cantidad de tiempo de CPU y tiempo real consumida, límites de tiempo, números de cuenta, números de trabajo o proceso, y demás.

·         Información de estado de E/S: La información incluye la lista de dispositivos de E/S asignadas a este proceso, una lista de archivos abiertos, etcétera.

El PCB sirve como depósito de cualquier información que pueda variar de un proceso a otro.

Jerarquía de procesos: La secuencia de creación de procesos genera un árbol de procesos. Para referirse a las relaciones entre los procesos de la jerarquía se emplean los términos de padre, hermano o abuelo. Cuando el proceso A solicita al sistema operativo que cree el proceso B, se dice que A es padre de B y que B es hijo de A. Bajo esta óptica, la jerarquía de procesos puede considerarse como un árbol genealógico. Algunos sistemas operativos, como Unix, mantienen de forma explícita esta estructura jerárquica de procesos un proceso sabe quién es su padre -, mientras que otros sistemas operativos como el Windows NT no la mantienen. Planificador y activador: El planificador (scheduler) forma parte del núcleo del sistema operativo. Entra en ejecución cada vez que se activa el sistema operativo y su misión es seleccionar el proceso que se ha de ejecutar a continuación. El activador (dispatcher) también forma parte del sistema operativo y su función es poner en ejecución el proceso seleccionado por el planificador.

Cambio de contexto: La activación del sistema operativo se realiza mediante el mecanismo de las interrupciones. Cuando se produce una interrupción se realizan las dos operaciones siguientes:

Se salva el estado del procesador en el correspondiente PCB.

Se pasa a ejecutar la rutina de tratamiento de interrupción del sistema operativo.

Llamaremos cambio de contexto (context switch) al conjunto de estas operaciones. El tiempo de conmutación de contexto es exclusivamente gasto extra (overhead), porque el sistema no realiza trabajo útil durante la conmutación. Por ser un cuello de botella tan importante para el desempeño del sistema operativo se están empleando estructuras nuevas (hilos) para evitarla hasta donde sea posible.

Procesos ligeros, hilos o threads: Un proceso ligero es un programa en ejecución (flujo de ejecución) que comparte la imagen de memoria y otras informaciones con otros procesos ligeros. Un proceso puede contener un solo fljo de ejecución, como ocurre en los procesos clásicos, o más de un flujo de ejecución (procesos ligeros). Desde el punto de vista de la programación, un proceso ligero se define como una función cuya ejecución se puede lanzar en paralelo con otras. El hilo de ejecución primario, o proceso ligero primario, corresponde a la función main. Todos los procesos ligeros de un mismo proceso comparten el mismo espacio de direcciones de memoria, que incluye el código, los datos y las pilas de los diferentes procesos ligeros.

El proceso ligero constituye la unidad ejecutable en Windows NT

Planificación en POSIX (Linux): POSIX especifica una serie de políticas de planificación, aplicables a procesos y procesos ligeros, que debe implementar cualquier sistema operativo que ofrezca esta interfaz.

Planificación en Windows NT/2000: En Windows NT la unidad básica de ejecución es el proceso ligero y, por tanto, la planificación se realiza sobre este tipo de procesos.

Planificación de CPU

Conceptos

La planificación es una función fundamental del sistema operativo. Siendo la CPU uno de los principales recursos, la planificación de su uso es sumamente importante.

En un ambiente de multiprogramación, el sistema operativo debe decidir a qué proceso le da la CPU entre los que están listos para ejecutarse. ¿Cuál es el criterio por el cual se prefiere la ejecución de uno sobre los otros?

Existen diferentes algoritmos de selección, pero para escoger cuál es el que corresponde a nuestro sistema debemos tener claro bajo qué criterios nos interesa fijar las pautas. Por ejemplo:

·         Maximizar el uso de la CPU: que se mantenga ocupada el mayor tiempo posible.

·         Maximizar la Productividad (throughput), considerando que productividad (o rendimiento) es el número de procesos que se ejecutan por unidad de tiempo.

·         Minimizar el Tiempo de retorno (turnaround time), que es el tiempo transcurrido desde que el proceso ingresa hasta que termina, sumando espera para entrar en memoria, en cola de procesos listos, ejecutándose en CPU y haciendo E/S.

·         Minimizar el Tiempo de espera (waiting time), que es el tiempo que el proceso está en la cola de listos.

·         Minimizar el Tiempo de respuesta (response time), que es el tiempo que transcurre desde que se presenta una solicitud hasta que se tiene respuesta. Es el tiempo que tarda en comenzar a responder, no incluyendo el tiempo de la respuesta en sí.

Lo ideal es maximizar el uso de la CPU y la productividad y minimizar los tiempos de retorno, respuesta y espera.

Son otros criterios:

·         La equidad: que todos los procesos tienen que ser tratados de igual forma y a todos se les debe dar la oportunidad de ejecutarse, para que ninguno sufra inanición.

·         Recursos equilibrados: la política de planificación que se elija debe mantener ocupados los recursos del sistema, favoreciendo a aquellos procesos que no abusen de los recursos asignados, sobrecargando el sistema y bajando la performance general.

Organización. Colas y schedulers

Colas

En un sistema operativo los recursos compartidos exigen la organización en colas de las solicitudes pendientes. Tenemos colas para la planificación del uso de la cpu como también colas para el uso de dispositivos, device queues, que son utilizadas para ordenar los requerimientos que varios procesos pueden tener sobre un dispositivo específico.

Al ser creados, los procesos se colocan en la cola de trabajos, formada por los procesos que aún no residen en la memoria principal pero están listos para su ejecución.

La residencia en memoria es imprescindible para la ejecución de un proceso. La cola de trabajos listos (ready queue) es aquélla formada por los procesos que están listos para la ejecución, en memoria principal. Son los procesos que compiten directamente por CPU.

Un proceso que está en la cola de listos no puede estar en las colas de dispositivo, pues en este último caso está esperando por E/S, por lo tanto no puede estar compitiendo por cpu.

Los elementos de cualquiera de estas colas no son los procesos en sí, sino sus PCB’s, que están en memoria.

La cola de procesos listos (ready queue) se almacena como una lista enlazada donde la cabecera (header) de la ready queue tiene punteros al primer y al último PCB de los procesos de la lista. Cada PCB apunta al próximo en la lista.

Schedulers, dispatchers – Planificadores, activadores

Hay módulos del sistema operativo para elegir un proceso para su ejecución de entre los que están compitiendo por CPU. Esa elección dependerá del criterio adoptado (según lo explicado en el primer punto). La elección estará asociada al carácter del sistema. Por ejemplo, en un sistema batch no hay tanta exigencia en cuanto al tiempo de respuesta. En un sistema interactivo minimizar este tiempo es imprescindible.

El algoritmo que se eligirá para la elección de procesos será diferentes en cada caso.

Recordemos que los sistemas operativos modernos permiten la convivencia de las dos modalidades (batch e interactivo): ¿cómo lo solucionamos?

Necesitamos que el sistema operativo, a través de sus módulos, elija un proceso de acuerdo al criterio elegido, haga el cambio de contexto, lo cargue en memoria y le dé la CPU. Cuando un proceso termina, normal o anormalmente, debe elegirse otro proceso para cargar en memoria.

¿Qué pasa cuando un proceso de mayor prioridad debe ejecutarse y no hay memoria suficiente? Un módulo debe encargarse de seleccionar uno de los procesos que está en memoria y sacarlo temporariamente a memoria secundaria para dar lugar (swapping), pero teniendo en cuenta que sigue compitiendo por CPU y que se debe resguardar su contexto.

Estos módulos del sistema operativo son rutinas especiales y dependerá de la implementación cómo las funciones que citamos se realizan en cada sistema.

En un sistema hay procesos con mayor proporción de ráfagas E/S (I/O bound process) y otros con mayor necesidad de cpu que de E/S (CPU bound). Si cuando se seleccionan procesos para ejecutar se eligieran todos I/O bound, tendríamos las colas de dispositivo llenas de solicitudes y, probablemente, la CPU ociosa. Si se eligen muchos procesos limitados por CPU la cola de listos estará llena y las colas de dispositivo, vacías.

Por eso es muy importante de qué manera se realiza la selección de trabajos para mantener el sistema en equilibrio.

Esta selección la realizan los planificadores o schedulers.

Hay distintos planificadores que participan en diferentes momentos:

·         El de largo plazo o long term, que elige entre la cola de listos, para cargarlo en memoria;

·         El de corto plazo o short term (también llamado CPU scheduler), que elige entre los que están listos en memoria para darle la CPU;

·         El de medio plazo o medium term, que selecciona un proceso de entre los que están en memoria para llevarlo temporariamente a memoria secundaria por necesidades de espacio en memoria.

Es importante aclarar que en las colas los registros son normalmente las PCBs de los procesos.

Otro módulo de importante participación en la planificación es el activador o dispatcher.

Es el que da el control de la CPU al proceso elegido por el planificador de corto plazo.

Debe ser muy rápido pues una de sus funciones es encargarse del cambio de contexto

(context switch). Al tiempo entre detener un proceso y comenzar a correr otro se le llama

dispatch latency.

El dispatcher es también el que se encarga de pasar a modo usuario el proceso que esta activando y “saltar” a la dirección de la instrucción que comienza la ejecución del programa.

Procesos orientados a la E/S y procesos orientados a la CPU

Hay procesos orientados a la E/S y procesos orientados a la CPU.

Los procesos orientados a la CPU tienen proporcionalmente ráfagas de CPU mayores a las de E/S, siendo estas últimas además, pocas.

Normalmente los procesos de este tipo utilizan toda su porción de tiempo o quantum al no tener que abandonar la CPU por E/S.

Los procesos orientados a la E/S tienen proporcionalmente ráfagas de E/S mayores a las

de CPU y muy seguidas. En un ambiente de multiprogramación donde haya preponderancia

de estos procesos, habrá una intervención muy frecuente del planificador de corto plazo, y mucho cambio de contexto.

Algoritmos de planificación

Estos algoritmos tratan sobre la decisión de elegir a cuál de los procesos que están en la cola de listos se le asignara la CPU. Veamos algunos de ellos.

FCFS (first-come, first-serve) Primero en llegar, primero en ser atendido

Se le asigna la CPU al proceso que la requirió primero. Se maneja a través de una cola FIFO

(First In First Out), tal que cuando un proceso requiere CPU, su PCB se coloca la final de la cola.

Cuando se debe elegir un proceso para asignarle CPU se elige el proceso cuya PCB esta primera en la cola.

El código para implementar este algoritmo es simple y comprensible. Pero el tiempo promedio de espera puede ser largo.

El efecto convoy del FCFS

Una situación indeseable que puede ocurrir cuando se mezclan procesos CPU bound con proceso I/O bound es el efecto convoy.

EL proceso CPU bound toma la CPU y la mantiene pues el resto de los procesos al tener tanto I/O se la pasa circulando por las diferentes colas (de ready, de dispositivo) o en espera. El resultado es un bajo rendimiento de la CPU, que está prácticamente atendiendo un solo proceso.

Este efecto podría evitarse atendiendo procesos más cortos primero, aumentando la productividad.

Shortest-job-first Scheduling (SJF). Planificación “primero el trabajo más corto”

Este algoritmo elige entre los procesos de la cola de listos, aquel que tenga la próxima ráfaga de CPU más corta. Para ello este dato debe ser conocido, obviamente.

Es un algoritmo que permite que el tiempo de espera promedio sea bajo.

Se puede utilizar en planificadores de largo plazo, pero no en los de corto plazo pues no hay manera de conocer la medida de la próxima ráfaga. Se podría aproximar considerando el valor de la previa.

Por prioridad

Se le asocia un valor a cada proceso que representa la prioridad, y se le asigna la CPU al proceso de la cola de ready que tenga la mayor prioridad.

Los valores asociados a la prioridad son un rango fijo, de 0 a n, según cada sistema.

También lo determina cada sistema si el número más bajo es la más alta o la más baja prioridad.

La prioridad puede ser fija o variable, externa o interna.

Si es fija, ese valor no varía en el ciclo de vida del proceso. Si es variable, significa que ese valor puede cambiar dinámicamente de manera tal que haya factores, por ejemplo, el tiempo que lleva esperando en colas, que puedan “ayudar” a que haya un mejor nivel de competencia elevando la prioridad de procesos postergados y evitar una situación indeseable llamada starvation (inanición). A la técnica de elevar la prioridad a un proceso de acuerdo al tiempo que hace que esta en el sistema se le llama aging.

Si la prioridad es interna, es determinada en función del uso de los recursos (memoria, archivos abiertos, tiempos). Si es externa, puede decidirse darle alta prioridad a un proceso de importancia, a consideración del operador.

POSIX proporciona planificación basada en prioridades.

Round-Robin Scheduling (RR). Planificación por turno circular.

Se la asigna a cada proceso de la cola de listos un intervalo de tiempo de CPU. Ese intervalo es llamado time slice o quantum.

Para implementar este algoritmo la cola de listos se mantiene como una cola FIFO. Y la CPU se va asignando dándole un máximo de 1 quantum a cada proceso.

Si el proceso no va a usar todo ese tiempo, usa lo necesario y libera la CPU. Se elige entonces otro proceso de la cola. Si excede el quantum, se produce una interrupción.

En ambos casos al dejar la CPU hay un cambio de contexto.

El tiempo promedio de espera puede ser largo. Su performance depende fuertemente de la elección del quantum. Y el tiempo gastado en context switch es una variable que se debe tener muy en cuenta. Se debe determinar un quantum que sea mucho mayor que el tiempo de context switch.

Se utiliza en los sistemas time-sharing.

Colas multinivel

En un sistema conviven procesos mixtos. Puede haber requerimientos de tiempo de respuesta distintos si conviven proceso interactivos con procesos batch (o para aquellos que provienen del Unix, procesos en foreground y procesos en background).

Existen algoritmos que contemplan esta situación dividiendo la cola de ready en distintas colas según el tipo de proceso, estableciendo una competencia entre las colas y entre los procesos del mismo tipo entre sí.

Cada cola puede tener su algoritmo de scheduling: los procesos batch pueden ser planificados” por un algoritmo FCFS y la cola de procesos interactivos, por un RR.

Colas multinivel con retroalimentación

En el caso planteado anteriormente, un proceso permanecía en la cola asignada hasta su atención. En el modelo con retroalimentación, un proceso puede “moverse” entre colas, es decir, según convenga puede llegar a asignarse a otra cola.

Los procesos se separan de acuerdo a la ráfaga de CPU que usan. Si está usando mucha CPU se lo baja a una cola de menor prioridad. Se trata de mantener los procesos interactivos y de mucha I/O en las colas de mayor prioridad.

Si además un proceso estuvo demasiado tiempo en una cola de baja prioridad puede moverse a una cola de mayor prioridad para prevenir inanición (starvation).

Scheduling apropiativo, expropiativo o expulsivo (preemptive)

Hay que considerar en el esquema de planificación en qué momento se realiza la selección.

Un algoritmo no apropiativo es aquel que una vez que le da la CPU a un proceso se ejecuta hasta que termina o hasta que se bloquea hasta la ocurrencia de determinado evento.

En cambio, un algoritmo apropiativo es aquel en que un proceso que se está ejecutando puede ser interrumpido y pasado a cola de listos (ready queue) por decisión del sistema operativo. Esta decisión puede ser porque llego un proceso de mayor prioridad, por ejemplo.

Si bien los algoritmos apropiativos tienen un mayor costo que los no apropiativos, el sistema se ve beneficiado con un mejor servicio pues se evita que algún proceso pueda apropiarse de la CPU.

No obstante si se utilizaran algoritmos apropiativos debe considerarse si el sistema operativo está preparado para desplazar en cualquier momento un proceso. Por ejemplo, si ese proceso en ese momento, a causa de una llamada al sistema (system call) está modificando estructuras de kernel y se lo interrumpe, esas estructuras pueden quedar en un estado inconsistente. O puede ocurrir con procesos que comparten datos y uno de ellos está modificándolos al ser interrumpido.

La planificación de procesos en ambientes multiprocesador Sistemas Operativos UTN – FRM

En el caso en que los procesadores son idénticos, cualquier procesador disponible puede usarse para atender cualquier proceso en la cola. No obstante, debemos tener en cuenta que puede haber dispositivos asignados de manera privada o única a un procesador, y si un proceso quiere hacer uso de ese dispositivo deberá ejecutarse en ese procesador. Otra ventaja es implementar load sharing (carga compartida), permitiendo que si un procesador esta ocioso puedan pasarse procesos de la cola de otro procesador a este, o hacer una cola común, y la atención se realiza de acuerdo a la actividad de cada uno.

En ambientes de procesadores heterogéneos no olvidemos que un procesador podría ejecutar solo aquellos procesos que fueron compilados de acuerdo a su conjunto de instrucciones.

En otros sistemas se asume una estructura de procesadores master-slave que asigna a un procesador la toma de decisiones en cuanto a scheduling y otras actividades, dedicándose los otros procesadores a ejecutar código de usuario. La ventaja es que solo el procesador master accede a estructuras del kernel, evitando inconsistencias.