Proceso

Un proceso es una unidad de procesamiento gestionada por el sistema operativo (es un programa en ejecución)

El sistema operativo implementa una colección de máquinas abstractas

Cada máquina es una simulación del hardware de von Neumann subyacente

El gestor de procesos crea el entorno en el que coexisten varios procesos. Cada uno se ejecuta en su propia máquina abstracta como multitarea

Un recurso es cualquier elemento de la máquina abstracta que puede ser solicitado por un proceso

Un proceso solicita un recurso realizando una llamada al sistema, lo que puede producir que se bloquee si no está disponible

La reserva del recurso produce que el recurso forme parte de la configuración de la máquina abstracta del proceso

Ejemplos de recursos: procesador, memoria principal, dispositivos E/S, archivos

Tablas del sistema operativo

El sistema operativo mantiene tablas que describen a los procesos y a los recursos del sistema:

• Tablas de procesos: tablas de BCPs
• Tablas de memoria: información sobre el uso de la memoria
• Tablas de E/S: información asociada a los periféricos y a las operaciones de E/S
• Tablas de archivos: información sobre los ficheros abiertos

Imagen de memoria del proceso

Un espacio de direcciones del proceso es el conjunto de direcciones lógicas que puede direccionar

En ordenadores de 32 bits el máximo es de 4 GB

En ordenadores de 64 bits el máximo es de 128 GB, sin embargo, en la actualidad no hay placas que admitan memorias tan grandes

La imagen de memoria del proceso es el bloque de memoria física asignada al proceso

El espacio de direcciones del proceso se encuentra limitado al bloque de direcciones físicas correspondientes

El espacio de direcciones es importante para la protección de los recursos frente a los accesos no autorizados

Estado del procesador

Cuando está ejecutándose, el estado del procesador reside en los registros del procesador:

• Registros generales
• Contador de programa (PC)
• Puntero de pila (SP)
• Registros de estado
• Registros especiales

Cuando no ejecuta, su estado del procesador reside en el BCP

Cambio de contexto

Cuando se produce una interrupción:

• Se salva el estado del procesador en el correspondiente BCP
• Se pasa a ejecutar la rutina de tratamiento de interrupción del sistema operativo

Planificador o scheduler:

• Módulo del sistema operativo que selecciona el siguiente proceso a ejecutar

Activador o dispatcher:

• Módulo del sistema operativo que pone en ejecución el proceso seleccionado

Bloque de control de proceso (BCP)

Información de identificación de proceso

• ID del proceso y del padre (pid, ppid)
• ID del usuario real y efectivo (uid, euid)
• ID del grupo real y efectivo (gid, egid)

Información del estado del procesador

Información de control del proceso

• Información de planificación y de estado
• Descripción del espacio de direcciones
• Recursos asignados (ficheros abiertos, puertos, …)
• Comunicación entre procesos
• Punteros para estructurar los procesos en listas o colas

Control de procesos

El control de procesos nos permite hablar de ejecución, hebras o subprocesos, que son una secuencia de tareas encadenadas tan pequeñas que pueden ser ejecutadas por un sistema operativo

Modelo de proceso con dos estados

Un proceso puede estar en uno de estos dos estados básicos:

• Ejecución
• No Ejecución

Procesos en no ejecución

Con una sola cola de procesos en no ejecución, el planificador tendría que recorrerla para buscar un proceso que no está bloqueado. No sirve la estrategia FIFO (First-in, First-out)

Dos tipos de procesos en no ejecución:

• Listos para ejecutarse
• Bloqueados: Esperan a que termine una operación de E/S

Modelo de cinco estados

• Ejecución
• Listo
• Bloqueado
• Nuevo
• Terminado

Procesos suspendidos

El sistema operativo puede decidir “desalojar” un proceso de memoria principal y transferirlo a disco

Dos nuevos estados:

• Bloqueado / Suspendido: El proceso está en memoria secundaria esperando un suceso
• Listo / Suspendido: El proceso está en memoria secundaria disponible para su ejecución

Señales y excepciones

Las señales y las excepciones son mecanismos que utiliza un sistema operativo para notificar a un proceso la ocurrencia de un determinado evento

Las señales son utilizadas en POSIX y las excepciones son utilizadas en Windows

Señales

Una señal es la interrupción de un proceso

Recepción de la señal:

• El proceso detiene su ejecución
• Bifurca a ejecutar una rutina de tratamiento de la señal (el código debe formar parte del propio proceso)
• Una vez ejecutada la rutina de tratamiento, sigue la ejecución del proceso

Envío de la señal:

• El origen puede ser el sistema operativo o un proceso
• En POSIX, se realiza mediante el servicio kill

Excepciones

Evento que ocurre durante la ejecución de un programa y que requiere la ejecución de un fragmento de código fuera del flujo normal de ejecución

Pueden ser generadas por el hardware o el software

El manejo de excepciones necesita el soporte del lenguaje de programación. Por ejemplo, en Java:

try {
	Bloque donde puede producirse la excepción
}
catch {
	Bloque que se ejecutará si se produce una excepción en el bloque anterior
}

Hilos (thread)

Un gestor de procesos moderno separa la ejecución dinámica de los aspectos estáticos del entorno computacional del proceso:

• Proceso moderno: Unidad de propiedad de los recursos
• Hilo (o proceso ligero): Unidad o motor de ejecución

Un proceso puede contener un solo hilo base o varios hilos de ejecución

Estados de un hilo

Estados:

• Ejecución
• Listo
• Bloqueado

El estado suspensión pertenece al concepto de proceso

Operaciones básicas relacionadas con el cambio de estado en hilos:

• Creación / destrucción de un hilo
  • Cuando se crea un proceso, también se crea un hilo
  • Un hilo de un proceso puede crear otros hilos dentro del mismo proceso
• Bloqueo / Desbloqueo
  • Reserva de recursos específicos del hilo

Procesos en un entorno multihilo

Información propia de cada hilo:

• Registros del procesador: contador, pila, de estado, etc
• Estado del hilo: Ejecución, Listo o Bloqueado

Información compartida por todos los hilos de un mismo proceso:

• Espacio de direcciones: código y datos
• Variables globales
• Archivos abiertos
• Otros recursos compartidos

Beneficios de los hilos

Facilita la modularidad permitiendo encapsular cada tarea en un hilo independiente

Aumenta la velocidad de ejecución del trabajo:

• Se tarda menos tiempo en crear / terminar un nuevo hilo que un proceso
• Se tarda menos tiempo en cambiar de contexto entre dos hilos de un mismo proceso
• Puesto que los hilos de un mismo proceso comparten memoria y archivos, pueden comunicarse entre sí sin invocar al núcleo

Permite la programación concurrente

Proceso servidor

Un servidor es un proceso que está pendiente de recibir órdenes de trabajo que provienen de otros procesos (clientes)

Una vez recibida la orden, la ejecuta y responde al cliente con el resultado

La comunicación entre el proceso cliente y el servidor, se realiza mediante los puertos

Proceso demonio (daemon)

Se arrancan al iniciar el sistema. Están siempre activos y no mueren

Se ejecutan en segundo plano y no están asociados a un terminal o proceso login

Están normalmente a la espera de un evento o realizan una tarea de forma periódica

No hacen directamente el trabajo: lanzan otros procesos (o hilos) para que realicen su tarea

Ejemplos: servidor de FTP, servidor web, …

POSIX para la gestión de procesos

Identificación de procesos

POSIX identifica cada proceso por medio de un entero único denominado identificador de proceso de tipo pid_t

La función para obtener el identificador del proceso que realiza la llamada es

pid_t getpid(void);

La función para obtener el identificador del proceso padre es

pid_t getppid(void);

La función para obtener el identificador de usuario real es

pid_t getuid(void);

La función para obtener el identificador de grupo real es

pid_t getgid(void);

Entorno de un proceso

El entorno de un proceso consta de la lista de variables que se pasan al proceso en el momento de empezar su ejecución

Son accesibles a través una variable externa que apunta a una lista de variables de entorno:

extern char **environ

Algunas variable de entorno:

• HOME: directorio de trabajo inicial del usuario
• LOGNAME: nombre del usuario asociado al proceso

La función para obtener el valor de una variable de entorno es char

*getenv(const char *name);

Creación de procesos

La función para crear un proceso es

include <sys/types.h>

pid_t fork(void);

Devuelve el identificador del proceso hijo al proceso padre y 0 al proceso hijo, devolverá -1 en caso de error

Crea un proceso hijo que ejecuta el mismo programa que el padre. Hereda los ficheros abiertos (se copian los descriptores)

Las funciones para ejecutar un programa (código) distinto son:

int execl(const char *path, const char *arg, ...);
int execelp(const char *file, const char *arg, ...);
int execvp(const char *file, char *argv[]);

Como argumentos se utilizan path, file del nombre del archivo ejecutable y arg como argumentos del ejecutable

Devuelve -1 en caso de error. Si tiene éxito no devolverá ningún valor

Cambia la imagen de memoria del proceso. El mismo proceso ejecuta otro programa pero mantiene los ficheros abiertos

Terminación de procesos

La función para terminar un proceso es

void exit(int estado);

Como argumento se utiliza estado, que es el código de retorno al proceso padre

Finaliza la ejecución del proceso

Se cierran todos los descriptores de ficheros abiertos

Se liberan todos los recursos del proceso

Espera la terminaciçon de un proceso

Las funciones para esperar por la finalización de un proceso hijo son:

include <sys/types.h>

pid_t wait(int *estado);
pid_t waitpid(pid_t pid, int *estado, int opciones);

Como argumentos se utilizan estado, el identificador de terminación del proceso hijo, pid, identificador del proceso, opciones, identificador de opciones

Devuelve el identificador del proceso hijo ó -1 en caso de error

Permite a un proceso padre esperar hasta que termine la ejecución de un proceso hijo

Programa de ejemplo

#include <sys/types.h>
#include <stdio.h>

/* programa que ejecuta el comando “ls –l” */

main() {
	pid_t pid;
	int estado;
	pid=fork();
	if (pid == 0) {	/* proceso hijo */
		execlp(“ls”,“ls”, “-l”,NULL);
		exit(-1)	/* se ejecutará si hubo un error */
	}
	else	/* proceso padre */
		while (pid != wait(&estado));
	exit(0);
}

Planificación

Se necesita realizar una planificación para determinar cuáles serán los programas admitidos en el sistema

Tipos de planificación

• Planificación a largo plazo: Decisión de añadir procesos al conjunto de procesos a ejecutar
• Planificación a medio plazo: Decisión de añadir procesos al conjunto de procesos que se encuentran parcial o completamente en la memoria
• Planificación a corto plazo: Decisión sobre qué proceso / hilo disponible será ejecutado en el procesador

Planificación a largo plazo

Determina cuáles son los programas admitidos en el sistema. Debe tomar dos decisiones:

• Cuándo puede crear un nuevo proceso
• Cuál va a ser el siguiente proceso a admitir. Combinar procesos con mayor carga de procesador y procesos con mayor carga de E/S

Controla el grado de multiprogramación. Cuantos más procesos se crean, menor es el porcentaje de tiempo en el que cada proceso se puede ejecutar

Planificación a medio plazo

Forma parte de la función de intercambio

Se basa en la necesidad de controlar el grado de multiprogramación

Si no se emplea memoria virtual, deberá tener en cuenta las necesidades de memoria del proceso

Planificación a corto plazo

Planificación del uso de la CPU: Gestionar la compartición de la CPU entre los procesos / hilos listos para ejecutarse

El objetivo del planificador (scheduler) es repartir el tiempo del procesador entre los procesos / hilos que pueden ejecutar

Debe tener en cuenta factores como:

• Equidad: repartir el uso de la CPU
• Eficiencia: evitar tiempos ociosos de la CPU
• Rendimiento: maximizar el número de peticiones

Mecanismos de planificación

El planificador está compuesto por tres componentes lógicos:

• Encolador: Cuando un proceso cambia al estado Listos, el encolador lo coloca en una estructura de datos de tipo cola
• Conmutador de contexto: Cuando un proceso va a ser desalojado de la CPU, el conmutador de contexto guarda el contenido de los registros de la CPU en el BCP del proceso
• Distribuidor: El distribuidor selecciona uno de los procesos de la cola de Listos y le asigna la CPU

Criterios de la planificación

Criterios para comparar el rendimiento de los diversos algoritmos de planificación:

• Tiempo de servicio (T_s) Tiempo estimado de ejecución
• Tiempo de retorno (T_r) Tiempo transcurrido desde que llega al sistema hasta que termina
• Tiempo de espera (T_w) Suma de tiempos que el proceso está en no ejecución
• Tiempo de retorno normalizado (\frac{T_r}{T_s}) Tiempo de retorno dividido por el tiempo de servicio

Uso de prioridades

El planificador seleccionará siempre a un proceso de mayor prioridad antes que a los de menor prioridad

Utiliza múltiples colas de Listos para representar cada nivel de prioridad

Los procesos de prioridad más baja pueden sufrir inanición (no son elegidos núnca)

Una solución ante la inanición consiste en permitir que un proceso cambie su prioridad en función de su antigüedad o su historial de ejecución

Políticas de planificación

Se basan en una función de selección para determinar qué proceso, de entre los Listos, se elige para ejecutar

La función puede estar basada en prioridades, necesidades de recursos o en las características de ejecución de los procesos

Hay dos clases de algoritmos según el modo de decisión (instante en que se aplica la función de selección):

• Sin expulsión (no apropiativos o no preferentes): Una vez que el proceso pasa al estado de Ejecución, continúa ejecutando hasta que termina o se bloquea en espera de una E/S (ráfaga)
• Con expulsión (apropiativos o preferentes): El proceso que se está ejecutando actualmente puede ser interrumpido y pasado al estado de Listos por el sistema operativo. Permiten dar un mejor servicio ya que evitan que un proceso pueda monopolizar el procesador durante mucho tiempo

Algoritmos de planificación

Algoritmos sin expulsión:

• FIFO (First-come First-served): Primero en llegar, primero en ser servido
  • Se selecciona para ejecutar el proceso más antiguo de la cola de Listos
  • Sencillo de implementar
  • Tiempo medio de espera muy alto
  • Penaliza a los procesos cortos sobre los procesos largos
  • Favorece a los procesos con carga de CPU sobre los procesos con carga de E/S
  • Suele utilizarse combinado con prioridades
• SPN (Shortest Process Next): Primero el proceso más corto
  • Se selecciona el proceso con menor tiempo de servicio
  • Dificultad en estimar el tiempo esperado de ejecución para cada proceso
  • Minimiza el tiempo medio de espera
  • Penaliza a los procesos largo sobre los procesos cortos
  • Posibilidad de inanición para los procesos largos

Algoritmos con expulsión:

• Turno rotatorio (RR, Round Robin)
  • Utiliza un cuanto de tiempo que es una fracción de tiempo que permite a cada proceso utilizar la CPU
  • Se expulsa el proceso que ha consumido su cuanto de tiempo y pasa a ocupar el último lugar de la cola de Listos
  • Hay dificultades para elegir el tamaño del cuanto (inferior al 80% de las ráfagas de CPU)
  • Favorece a los procesos con carga de CPU sobre los procesos con carga de E/S
  • El tiempo de espera grande, pero garantiza un reparto de la CPU con buenos tiempos de respuesta
• FB (Feedback): Realimentación multinivel
  • Divide la cola de Listos en una jerarquía de colas: RQ_0, \cdots, RQ_n, cada una con un nivel de prioridad
  • Utiliza un cuanto de tiempo y un mecanismo dinámico de prioridades
  • Los procesos entran por RQ_0 y en cada ráfaga de ejecución descienden a la siguiente cola
  • En cada cola se utiliza FIFO, excepto en la de menor prioridad que se trata con turno rotatorio
  • Favorece a los procesos cortos frente a los procesos más viejos y largos
    • Los procesos cortos terminarán rápidamente, sin descender demasiado en la jerarquía de colas
    • Los procesos largos serán gradualmente llevados hacia abajo
  • Existe un gran número de variaciones de este esquema
  • Para evitar la inanición de los procesos largos se puede variar el cuanto en función de cada cola

  Planificación en POSIX

  Cada política de planificación lleva asociada un rango de, al menos, 32 niveles de prioridad

  El planificador seleccionará el proceso con la prioridad más alta

  Cuando un proceso es expulsado por otro de mayor prioridad, el proceso pasa a ser el primero de la cola asociada a su prioridad

  En el planificador conviven tres políticas de planificación:

  • SCHED_FIFO: Es una política de planificación expulsora basada en prioridades estáticas, en la que los procesos con la misma prioridad se atienden en el orden de llegada (cola FIFO). Esta política tendrá al menos 32 niveles de prioridad
  • SCHED_RR: Esta política es muy similar a SCHED_FIFO, pero emplea un método round-robin para planificar procesos de la misma prioridad. También tiene 32 niveles de prioridad como mínimo
  • SCHED_OTHER: Es una política de planificación definida por la implementación

  Servicios POSIX para la planificación de procesos

  Las tres políticas de planificación están definidas en el archivo de cabecera

  <sched.h>

  Modificar los parámetros de planificación de un proceso:

  int sched_setparam(pid_t pid, const struct sched_param *param);
  int sched_scheduler(pid_t pid, int policy, const struct sched_param *param);

  Obtener los parámetros de planificación de un proceso:

  int sched_getparam(pid_t pid, const struct sched_param *param);
  int sched_getscheduler(pid_t pid);
  int sched_get_priority_min(int policy);
  int sched_get_priority_max(int policy);

Concurrencia

La concurrencia es una propiedad de los sistemas en la cual los procesos de un cómputo se hacen simultáneamente, y pueden interactuar entre ellos

Modelos de computación en los que se pueden ejecutar procesos concurrentes:

• Multiprogramación con un único procesador
• Multiprocesador
• Procesamiento distribuido

Afecta a un gran número de cuestiones de diseño del sistema operativo:

• Comunicación entre procesos
• Compartición y competencia por los recursos
• Sincronización de la ejecución de varios procesos
• Asignación del tiempo de procesador a los procesos/li>

Interacción entre los procesos

Tipos de procesos:

• Independientes
• Cooperantes

Interacción entre los procesos:

• Los procesos comparten o compiten por el acceso a recursos físicos o lógicos (incluso los procesos independientes)
• Los procesos se comunican y sincronizan entre sí para alcanzar algún objetivo común

Competencia entre procesos por los recursos

El principal problema de control es la necesidad de exclusión mutua. Mientras un proceso está; utilizando un recurso compartido no se debe permitir el acceso al resto de procesos

Hacer que se cumpla la exclusión mutua crea dos problemas adicionales:

• Interbloqueo
• Inanición

Problemas clásicos de comunicación y sincronización

• El problema de la sección crítica
• El problema del productor-consumidor
• El problema de los lectores-escritores
• Comunicación cliente-servidor

El problema de la sección crítica

Tenemos n procesos concurrentes, que pueden ser independientes o cooperantes

La sección crítica de cada proceso tiene un fragmento de código desde el que accede a algún recurso compartido

Cuando un proceso está ejecutando en su sección crítica, ningún otro puede ejecutar en la suya

Ejemplo de sección crítica

Dos procesos P_1 y P_2 comparten las variables a y b. Las variables cumplen la relación a = b

P1(){           P2(){
...             ...
a=a + 1;        b=2 * 1;
b=b + 1;        a=2 * a;
...             ...
}               }

Considérese la siguiente ejecución concurrente:

a=a + 1;
b=2 * b;
a=2 * a;
b=b + 1;

Al final de la ejecución ya no se cumplirá la condición a = b

La solución consiste en utilizar exclusión mutua al entrar en las secciones críticas

Es necesario utilizar algún mecanismo de sincronización:

Entrada en la sección crítica
Código de la sección crítica
Salida de la sección crítica

Requisitos que debe ofrecer cualquier solución:

• Exclusión mutua
• Evitar interbloqueos
• Espera limitada: evitar la inanición

El problema del productor-consumidor

Uno o más productores generan datos y los sitúan en un búfer

Un único consumidor saca elementos del búfer de uno en uno

Sólo un productor o consumidor puede acceder al búfer en un instante dado

Ejemplo de productor-consumidor

El problema de los lectores-escritores

Cualquier número de lectores puede leer el archivo simultáneamente

Sólo puede escribir en el archivo un escritor en cada instante

Si un escritor está accediendo al archivo, ningún lector puede leerlo

Ejemplo de lectores-escritores

Comunicación cliente-servidor

Los procesos servidores ofrecen una serie de servicios a otros procesos clientes

El proceso servidor puede residir en la misma máquina que el cliente o en una distinta

Ejemplo de cliente-servidor

Mecanismos de comunicación

• Archivos
• Variables en memoria compartida
• Tuberías
  • Sin nombre: pipes
  • Con nombre: FIFOS
• Paso de mensajes

Mecanismos de sincronización

• Señales
• Tuberías
  • Sin nombre: pipes
  • Con nombre: FIFOS
• Semáforos
• Monitores y variables condicionales
• Paso de mensajes

Tuberías

Mecanismo de comunicación y sincronización

Una tubería o pipe es una estructura de datos implementada en el núcleo del sistema operativo para la comunicación entre los espacios de direcciones

Sólo puede utilizarse entre procesos que la heredan a través de la llamada

fork()

Tuberías sin nombre: pipes

Utilizan un búfer FIFO con un flujo de datos unidireccional. Tienen un extremo de lectura y otro de escritura tratados mediante descriptores de archivos:

• escritura: poner datos en la tubería
• lectura: extraer datos de la tubería

Servicios POSIX para pipes

Crear una tubería sin nombre

int pipe(int fdes[2]);

Descriptor de archivo para leer del pipe:

fdes[0]

Descriptor de archivo para escribir en el pipe

fdes[1]

Cerrar el extremo de una tubería

int close(int fd);

Descriptor de archivo que se desea cerrar

fd

Leer de una tubería

int read(int fd, char *buffer, int nb);

Como argumentos se utilizan fd descriptor de archivo de lectura del pipe, buffer variable donde se almacenan los datos leídos y nb número máximo de bytes a leer

Si la tubería está vacía, se bloquea el proceso lector hasta que algún proceso escriba datos

Si la tubería no está vacía, la llamada devuelve el número de bytes leídos y elimina de la tubería los datos solicitados

Escribir en una tubería

int write(int fd, char *buffer, int nb);

Como argumentos se utilizan fd descriptor de archivo de escritura del pipe, buffer variable donde se almacenan los datos que serán escritos y nb número máximo de bytes a escribir

Si la tubería se llena, se bloquea el proceso escritor hasta que se pueda completar

Las operaciones de lectura y escritura se realizan de forma atómica

Crear una tubería con nombre

int mkfifo(char *nombre, mode_t modo);

No hay necesidad de heredarlo mediante fork

Abrir una tubería con nombre

int open(char *nombre, int flag);

Borrar una tubería con nombre

int unlink(char *nombre);

Lectura, escritura y cierre de un FIFO, igual que las pipes, mediante:

int read(int fd, char *buffer, int nb);
int write(int fd, char *buffer, int nb);
int close(int fd);