INTRODUCCIÓN
Un proceso se puede definir simplemente como un programa en ejecución con una serie de variables, registros y contadores activos.
La diferencia entre un programa y un proceso es sutil pero también crítica. Por ejemplo, cuando una persona está cocinando tiene una receta y una cocina abastecida con los ingredientes necesarios para preparar su plato. En esta analogía, la receta es el programa, la persona que cocina es la CPU y los ingredientes son los datos de entrada. El proceso es la actividad en la que la persona lee la receta, busca los ingredientes y cocina.
La idea clave es que un proceso es una entidad dinámica.
En este tema se verán las características de los procesos y las acciones que debe llevar a cabo el Sistema Operativo para realizar su gestión.
CONCEPTOS BÁSICOS
Ya se ha comentado que el Sistema Operativo realiza la gestión de los procesos y para ello, almacena información sobre los mismos en el Bloque de Control de Proceso (PCB) o Process Control Block y está formada por:
Estado en que está el proceso.
Un apuntador a la siguiente instrucción del programa a ejecutar.
El estado de todos los registros de la CPU.
Un identificador de proceso.
Un apuntador que sirve para ubicar el proceso de las diferentes colas de estado.
Estadísticas como el uso que se ha hecho de la CPU, el tiempo,etc.
ESTADOS DE UN PROCESO
Los estados en que podemos encontrar un proceso son los siguientes:
En ejecución (usando el procesador)
Bloqueado (sin poder hacer nada hasta que ocurra un evento externo)
Listo (ejecutable, se detiene temporalmente para que pueda ejecutarse otro proceso)
Hay cuatro transiciones posibles entre los diversos estados. La transición 1 ocurre cuando un proceso descubre que no puede continuar. Esto suele deberse a que ha de esperar datos de entrada todavía no disponibles.
El planificador de procesos lleva a cabo las transiciones 2 y 3. La transición 2 sucede cuando el planificador considera que el proceso en ejecución ya ha dispuesto del procesador durante suficiente tiempo, y decide que es el momento de asignarlo a otro proceso. Estando en el estado listo, un proceso es candidato para lograr el uso del procesador. Cuando esto ocurre, el planificador lo selecciona y le asigna el procesador. Esto corresponde a la transición 3.
Cuando sucede el evento externo que el proceso estaba esperando tiene lugar la transición 4. Si no hay en ese momento ningún proceso en ejecución, se llevará a cabo inmediatamente la transición 3 y el proceso comenzará a ejecutarse.
PROCESOS CONCURRENTES
Se dice que dos o más procesos son concurrentes si se están ejecutando simultáneamente. En un sistema monoprocesador, sólo se podrá dar la concurrencia aparente puesto que en el mismo instante de tiempo, solo un proceso podrá ocupar la CPU.
Las CPU’s que soportan la ejecución de más de un proceso de forma simultánea reciben el nombre de CPU’s multiprogramables.
Las razones para permitir la ejecución concurrente son principalmente la compartición de recursos y acelerar los cálculos.
SINCRONIZACIÓN ENTRE PROCESOS
Cuando los procesos pueden acceder a recursos compartidos como variables, BBDD o dispositivos, pueden producirse resultados inesperados y errores.
La solución a estos problemas de acceso a recursos compartidos es relativamente sencilla: prohibir que más de un proceso lea o escriba simultáneamente datos compartidos, es decir, establecer una exclusión mutua.
La sección crítica será aquella parte del programa en la cual se accede al recurso compartido. De este modo, si se puede evitar que dos procesos entren simultáneamente en una sección crítica, se evitarán las condiciones de competencia.
EXCLUSIÓN MUTUA
Los métodos de exclusión mutua pretenden evitar que dos o más procesos se solapen en sus secciones críticas.
DESACTIVACIÓN DE INTERRUPCIONES
Dado que incluso la alternancia entre procesos es controlada por interrupciones, un posible método para llevar a cabo la exclusión mutua podría ser que el proceso que entra en una región crítica las desactive todas. Este método no es admisible ya que no es correcto que un proceso desactive todas las interrupciones ya que tendría el control completo del sistema y además si el sistema tuviera más de una CPU la desactivación correspondería sólo a una de ellas.
CERROJOS
Podría pensarse que consultar el valor de una variable cerrojo antes de acceder a una sección crítica y modificar su valor para indicar que está ocupada solucionaría el problema. Pero no es así ya que el propio cerrojo presentaría condiciones de competencia.
ALGORITMO DE PETERSON
Antes de acceder a su región crítica los procesos tienen que llamar al procedimiento entrarEnSeccionCritica pasando como parámetro su número de proceso. Si el otro proceso está en su sección crítica esperará hasta que la abandone para entrar, en caso contrario entrará inmediatamente. Al final de su sección crítica, cada proceso debe llamar a salirRegionCritica.
Esta solución funciona pero presenta el problema de realizar espera activa.
DORMIR Y DESPERTAR
Intenta solucionar el problema de la espera activa ampliando el número de estados de un proceso. Para ello se definen dos primitivas, dormir (sleep) y despertar (wakeUp). La primera es una llamada al sistema que provoca la suspensión de quien efectúa la llamada. La segunda requiere de un parámetro que es el identificador del proceso que se desea despertar.
Este sistema puede dar lugar a condiciones de competencia. El problema radica en la pérdida de una llamada a la primitiva despertar cuando el proceso destinatario no está dormido.
SEMÁFOROS
El mecanismo por excelencia utilizado para manejar la exclusión mutua son los semáforos.
Básicamente, un semáforo es una variable de tipo entero no negativo sobre la que se definen dos funciones que se ejecutan de forma atómica: p y v. P se puede asociar con la función reservar y V, con la función liberar.
Por ejemplo, si se desea controlar el acceso a una impresora, se inicializaría la variable semáforo a 1 indicando que la impresora, inicialmente, se encuentra libre y cuando un proceso necesite utilizar la impresora, el procedimiento reservar_impresora, se reduciría a ejecutar p sobre dicho semáforo y reservar_impresora, sería ejecutar v sobre el semáforo.
Este tipo de semáforos son los llamados semáforos binarios, que únicamente pueden tomar el valor 0 o 1.
MONITORES
Un monitor es una construcción de un lenguaje de programación que contiene tanto los datos como los procedimientos necesarios para asignar un recurso compartido.
Para ejecutar una función de asignación de recursos, un proceso debe llamar a una entrada del monitor específica, pero no tiene acceso a sus estructuras internas. Los procesos que desean usar el monitor cuando ya hay un proceso activo deben esperar, el monitor controla automáticamente esta espera. Como la exclusión mutua está garantizada, se evitan los problemas de competencia.
COMUNICACIÓN ENTRE PROCESOS
El problema más general que debe resolverse en el tratamiento de los procesos concurrentes, es el de la comunicación, que consiste en proporcionarles mecanismos que les permitan intercambiar información.
MEMORIA COMPARTIDA
Los procesos comparten algunas variables para el intercambio de información. La responsabilidad de proporcionar la comunicación recae sobre los programadores de aplicaciones, el sistema operativo únicamente tiene que ofrecer la memoria compartida.
INTERCAMBIO DE MENSAJES
Concepto
La forma general de enviar y recibir mensajes es usando las siguientes primitivas del sistema operativo: enviar (destinatario, mensaje); recibir(origen, mensaje);
Se trata de llamadas al sistema y no comandos del lenguaje por lo que son accesibles desde muchos entornos de lenguajes de programación.
Un envío con bloqueo debe esperar hasta que el receptor reciba el mensaje constituyendo un ejemplo de comunicación síncrona. Un envío sin bloqueo permite al transmisor continuar con otras tareas aunque el receptor no haya recibido aún el mensaje permitiendo pues que ambos interlocutores se comuniquen asincronamente. El envío sin bloqueo requiere de buffers para almacenar los mensajes hasta que los reciba el receptor. La comunicación asincrona aumenta la posibilidad de paralelismo.
En la transmisión de mensajes pueden darse errores en la comunicación y es necesario un protocolo que permita solucionar este problema. También es necesario poder identificar mediante un nombre de forma no ambigua a los procesos destinos y origen. Estos y otros aspectos relativos a la comunicación son tratados en otros temas del temario por lo que no nos extendemos más sobre ellos.
Buzones y puertos
Un buzón consiste en un buffer en el que se almacenan los mensajes enviados antes de ser extraídos por el receptor. En este caso, el transmisor y el receptor especifican el buzón, en lugar del proceso, con el que se van a comunicar.
Un puerto se define como un buzón utilizado por múltiples transmisores y un único receptor. En los sistemas cliente/servidor, cada servidor tiene un puerto asignado por el cual recibe los mensajes de multitud de clientes.
Conductos (pipes)
UNIX introdujo la noción de conductos como un esquema para manejar comunicaciones entre procesos. Un conducto es en esencia un buzón que permite extraer un número específico de bytes a la vez. El conducto no mantiene las fronteras entre mensajes. Si los procesos convienen en leer y escribir mensajes con un tamaño determinado o terminar cada mensaje con un señalador especial la utilización de los conductos no presenta ningún problema.
LLAMADAS A PROCEDIMIENTOS REMOTOS (RPC)
Son un mecanismo estructurado de alto nivel para realizar la comunicación entre procesos en sistemas distribuidos. Con una llamada a un procedimiento remoto, un proceso de un sistema A llama a un procedimiento de un proceso de otro sistema B. El proceso A se bloquea esperando el retorno desde el procedimiento llamado en el sistema remoto y después continúa su ejecución desde el punto que sigue inmediatamente a la llamada.
El procedimiento llamado y el que llama residen en procesos distintos, con espacios de direcciones distintos, por lo cual no existe la noción de variables globales compartidas, por lo que las RPC transfieren la información estrictamente a través de los parámetros de la llamada.
Un problema de las RPC es que las llamadas por referencia son difíciles de implementar ya que una RPC comunica espacios de direcciones diferentes.
INTERBLOQUEOS
Un sistema está interbloqueado o deadlock cuando dos o más procesos esperan por un evento que no va a ocurrir. Por ejemplo, supongamos que existen dos procesos P1 y P2 que comparten dos recursos R1 y R2. P1 solicita el recurso R2 mientras tiene asignado R1 y simultáneamente P2 solicita R1 mientras tiene asignado R2. En este caso se presenta interbloqueo.
La situación de interbloqueo es indeseable porque los procesos nunca terminan su ejecución, los recursos del sistema se paralizarán impidiendo que se inicien otros procesos.
Las soluciones al interbloqueo son evitar que ocurra o permitir que ocurra, detectarlo y corregirlo.
PLANIFICACIÓN DE PROCESOS
Existen varios niveles de planificación, sin embargo, la más utilizada es la planificación de bajo nivel, en la que se determina a qué proceso en estado listo se le va a asignar la CPU, convirtiéndose en proceso en ejecución.
El encargado de realizar esta tarea es el planificador (scheduler) que utiliza para ello un algoritmo de planificación.
Un buen planificador debe cumplir con ciertos criterios:
Equidad: garantizar que cada proceso obtiene una proporción justa de CPU.
Eficacia: mantener ocupada la CPU al 100%.
Tiempo de respuesta: minimizar el tiempo de respuesta para los usuarios interactivos.
Tiempo de proceso global: minimizar el tiempo que deben esperar los usuarios por lotes para obtener resultados.
Rendimiento: maximizar el número de tareas procesadas por unidad de tiempo.
Hay que tener en cuenta que algunos de estos objetivos son contradictorios.
Un buen planificador además debe tener en cuenta que el comportamiento de cada proceso es impredecible. Algunos utilizan una gran cantidad de tiempo en espera de operaciones de E/S, mientras otros utilizan varias horas la CPU, en forma ininterrumpida, si tienen la posibilidad.
Cuando el planificador deja que un proceso se comience a ejecutar, no está en capacidad de saber cuanto tiempo transcurrirá hasta que el proceso se bloquee ya sea para E/S, por un semáforo, o por alguna otra razón. Para garantizar que ningún proceso se ejecute en un tiempo excesivo, los ordenadores recurren a interrupciones generadas por el reloj y en cada una de ellas el sistema operativo decide si el proceso que se ejecuta en ese momento tiene permiso para continuar o si debe suspenderlo para dar el control a otro proceso.
ALGORITMOS DE PLANIFICACIÓN
Cuando un proceso en Ejecución abandona tal estado pasa a Espera o Preparado, dependiendo si deja el procesador voluntaria o involuntariamente. Si los procesos de un sistema nunca dejan la CPU de forma involuntaria, se dice que la política de planificación de CPU es no expulsora o no expropiativa. Por el contrario, si pueden perder la posesión del procesador sin solicitarlo, nos encontramos con una planificación expulsora o expropiativa.
Las políticas no expulsoras suelen aplicarse en sistemas batch o en pequeños entornos monousuario, como el sistema operativo MS-DOS o el entorno Windows. Algunos algoritmos que se emplean en esta planificación son: primero en llegar – primero en servir, el más cortó primero y por prioridades.
Por otra parte, los algoritmos expropiativos se utilizan en sistemas de control industrial y entornos multiusuario. Los algoritmos más utilizados aquí incluyen: Round-Robin, por prioridades, de múltiples colas, y de múltiples colas realimentadas.
PRIMERO EN LLEGAR, PRIMERO EN SERVIR (FCFS)
Es de tipo no expulsivo. Los procesos se almacenan en una cola FIFO y son atendidos por orden de llegada. El primer proceso que accede a la CPU se mantiene en ella hasta que se bloquea (por espera de E/S u otro motivo) o termina. Es el tipo de planificación usada en Windows 3.x. Presenta el problema de que los procesos largos hacen esperar a los cortos con lo cual la capacidad de concurrencia del sistema disminuye.
POR TURNO. ROUND ROBIN (RR)
Es una de las más sencillas y utilizadas. Los procesos entran en la CPU siguiendo un esquema FIFO, pero con una cantidad de tiempo de CPU limitada denominada quantum. Si el proceso activo sigue en ejecución al final de su quantum es extraído de la CPU por el planificador y el siguiente proceso se apropia del procesador. También se asigna la CPU al siguiente proceso si el proceso activo termina o se bloquea antes del fin del quantum.
Es fundamental el tamaño del quantum. Si es muy pequeño se dedica demasiada CPU al cambio de contexto y si es demasiado grande degenera en FCFS.
PLANIFICACIÓN CON PRIORIDAD
La prioridad es la precedencia de un proceso respecto a los otros procesos que puedan ocupar la CPU. Cada proceso tendrá un nivel de prioridad asignada y el proceso listo con máxima prioridad es el que consigue la CPU.
Las prioridades pueden ser asignadas dinámicamente por el sistema y modificadas a lo largo de la vida del sistema.
PRIMERO EL MÁS CORTO (SJF)
Es un sistema no expulsivo. Concede la CPU de forma ininterrumpida al proceso que necesita la CPU durante menos tiempo. Si dos procesos tienen la misma duración se elije uno mediante FCFS.
Se comporta bien en la planificación a largo plazo de los procesos batch, en los que se conocen los requisitos de tiempo total de CPU. El problema es conocer la estimación de tiempo del resto de procesos (se puede hacer una estimación estadística basada en ejecuciones anteriores).
Una variante denominada prioridad con tasa de respuesta alta, highest response-ratio next (HRN) considera además del tiempo de ejecución el tiempo que el proceso lleva esperando para ser atendido para no hacer esperar indefinidamente a los procesos largos.
MENOR TIEMPO RESTANTE (SRT)
Es la versión expulsiva del método SJT. Como en general no es posible conocer anticipadamente el tiempo de ejecución de un proceso se acude a estimaciones del tiempo restante de ejecución, en función de las ejecuciones anteriores del proceso, asignándole la prioridad de manera inversamente proporcional a este valor.
COLAS CON DIFERENTE NIVEL DE PRIORIDAD
Un esquema usual es agrupar procesos en clases de prioridad y utilizar la planificación por prioridad entre las clases y otros modos de planificación (round robin, SJT, SRT) entre los procesos listos de cada clase.
Por ejemplo podríamos tener un sistema con cuatro colas de prioridad. Mientras hubiera procesos ejecutables en la cola de mayor prioridad, se ejecutaría cada uno un quantum siguiendo un sistema round robin, y no se ejecutarían de las otras colas. Las otras colas podrían usar el algoritmo RR u otro.
COLAS DE DIFERENTE NIVEL DE PRIORIDAD REALIMENTADAS
Es una variación de la anterior en la que los procesos no tienen por qué mantenerse en la misma cola hasta que se ejecutan, si no que si llevan mucho tiempo en una cola pueden ir subiendo a las colas de más prioridad.
PLANIFICACIÓN GARANTIZADA
Consiste en llegar a un compromiso con el usuario sobre el rendimiento del sistema que se va a poner a su disposición. Por ejemplo si hay n usuarios conectados dar 1/n del tiempo del procesador a cada usuario.
HILOS
Los hilos son en realidad subprocesos. Cada hilo se ejecuta secuencialmente y tiene su propio contador de programa y una pila para llevar un registro de posición pero comparte el resto de recursos asignados al proceso (archivos abiertos, procesos hijos, cronómetros, etc) con los otros hilos del proceso.
Una ventaja del uso de hilos es que la comunicación entre los hilos es muy rápida. Además es más rápido crear otro hilo que otro proceso.