Operaciones, Planificación y Gestión de Procesos e Hilos en Sistemas Operativos

Operaciones sobre Procesos

Creación de Procesos

Cuando se crea un proceso, el sistema operativo asigna un espacio de direcciones para almacenar sus datos e instrucciones y establece las estructuras de datos necesarias para su administración.

• En sistemas por lotes (batch) se crea un proceso al recibir un nuevo trabajo.
• En sistemas interactivos, cuando un usuario se conecta, el sistema operativo genera un proceso para ejecutar el intérprete de comandos.
• Procesos de servicio: un proceso de usuario puede solicitar al sistema operativo que cree otro proceso para realizar una tarea específica.

Relación Padre-Hijo: Un proceso puede crear otros procesos, formando un árbol de procesos en el que existe una relación de padre e hijo. El hijo puede obtener recursos de distintas formas:

• Directamente del sistema operativo: Padre e hijo no comparten recursos.
• Recursos compartidos: El hijo puede compartir todos o solo una parte de los recursos del proceso padre.

Formas de ejecución:

• Padre e hijo se ejecutan de forma concurrente.
• El padre espera a que el hijo termine.

Espacio de direcciones:

• El proceso hijo es un duplicado exacto del padre, incluyendo el espacio de direcciones. (Unix o Linux)
• El hijo carga un programa distinto al del padre. (VMS o Windows 2000)

En UNIX, la llamada al sistema fork() crea un nuevo proceso duplicando el proceso padre. Después, la llamada exec() reemplaza el espacio de direcciones del hijo con un programa nuevo, permitiendo que el proceso hijo ejecute una tarea diferente.

Tareas necesarias para crear un proceso:

• Asignar un identificador único (PID).
• Asignación de espacio.
• Crear e inicializar el PCB.
• Registrar el proceso en la tabla de procesos y agregarlo a la cola de planificación correspondiente.
• Establecer la prioridad inicial.

Terminación de Procesos

Finalización voluntaria:

• Cuando un proceso ejecuta la última instrucción, solicita al SO su finalización (exit).
• El proceso puede enviar datos de salida a su proceso padre, y el sistema operativo libera todos los recursos que estaban asignados a este proceso.

Finalización por el proceso padre:

• El padre puede finalizar la ejecución de sus hijos (abort o kill). Esto puede ocurrir si:
  • El hijo ha excedido sus recursos asignados.
  • La tarea que el hijo estaba realizando ya no es necesaria.
  • El proceso padre está a punto de finalizar, y el sistema operativo no permite que el proceso hijo continúe sin su padre (terminación en cascada).

Finalización forzada por el sistema operativo:

• El sistema operativo también puede terminar un proceso si detecta errores graves o condiciones de fallo. Esta acción es automática.

Hebras

Concepto de Hebra

Hebra (hilo, proceso ligero): unidad básica de utilización de la CPU. Las hebras permiten dividir un proceso en subprocesos que se ejecutan en paralelo o de forma concurrente, compartiendo el espacio de direcciones del proceso. Cada hebra contiene un PC, un conjunto de registros, su espacio de pila y un indicador de estado.

Ventajas de las Hebras

• Cambiar de una hebra a otra es más rápido que cambiar de un proceso a otro, ya que las hebras comparten el espacio de direcciones y otros recursos, lo que minimiza la sobrecarga.
• En un proceso con múltiples hebras, si una hebra queda bloqueada, otra hebra del mismo proceso puede continuar ejecutándose. Esto mejora el uso de la CPU y reduce el tiempo de espera de las aplicaciones.
• Las hebras de un mismo proceso pueden comunicarse directamente a través de la memoria compartida sin necesidad de usar mecanismos complejos como los usados entre procesos.
• Las aplicaciones que necesitan compartir memoria se benefician de la hebras, ya que estas pueden acceder al mismo espacio de direcciones y datos sin la necesidad de duplicarlos.

Funcionalidades de las Hebras

• Estados de las hebras: una hebra puede estar en ejecución, preparada o bloqueada, al igual que un proceso.
• Operaciones básicas: también podemos hablar de la creación, bloqueo, desbloqueo y terminación de una hebra.
• Sincronización entre hebras: cuando varias hebras trabajen sobre los mismos datos, necesitaremos implementar mecanismos de sincronización (semáforos, monitores) para evitar interfoliaciones.

Tipos de Hebras

• Hebras de Usuario: son gestionadas por la aplicación misma, sin intervención directa del núcleo del sistema operativo.

  • Se implementan mediante una biblioteca en el nivel de usuario que proporciona funciones para crear, gestionar, planificar y realizar cambios de contexto entre las hebras.
  • Para el núcleo, la unidad de planificación sigue siendo el proceso completo, sin tener conocimiento de las hebras individuales dentro de este.

• Hebras de Núcleo: la gestión de las hebras la realiza el núcleo del sistema operativo.

  • El sistema operativo proporciona un conjunto de llamadas al sistema específicas para la gestión de hebras, similar a las funciones que maneja para los procesos.
  • El núcleo mantiene un contexto de cada hebra, por lo que la unidad de planificación es la hebra individual, permitiendo así la planificación y sincronización de cada hebra por separado.

• Enfoque híbrido: combina hebras a nivel de usuario y a nivel kernel. (Solaris 2)

  • La creación de hebras, la planificación y sincronización se realizan en el espacio de usuario, evitando la sobrecarga de cambio de modo.
  • Cada hebra de usuario está asociada a una hebra de núcleo (a veces en una relación de uno a uno o de varios a uno), permitiendo que el sistema operativo gestione múltiples hebras en paralelo en un entorno multiprocesador.
  • Las múltiples hebras de una aplicación se pueden paralelizar y las llamadas al sistema bloqueadoras no necesitan bloquear todo el proceso.

Planificación, PCB y Colas de Estado

Colas de estado: El sistema operativo utiliza colas de estado para organizar los procesos según su estado actual. Cada cola representa un estado específico.

El PCB de cada proceso está asociado a una cola de estado, dependiendo del estado en que se encuentre (por ejemplo, en la cola de bloqueados).

Conforme un proceso cambia de estado, su PCB es retirado de una cola y encolado en otra. Por ejemplo, si un proceso pasa de listo a ejecución, su PCB se mueve de la cola de listos a la de ejecución.

Colas de Estado Específicas

• Cola de trabajos: Esta cola contiene todos los trabajos pendientes de ser admitidos en el sistema. Son procesos que aún no han sido cargados en memoria principal y suelen ser trabajos en espera en sistemas por lotes.
• Cola de preparados: Contiene todos los procesos que ya están en memoria principal, listos para ser ejecutados por la CPU. Los procesos en esta cola esperan su turno para acceder a la CPU.
• Colas de bloqueados: Estas colas agrupan procesos que están en espera de un evento específico. Un proceso en la cola de bloqueados no puede avanzar hasta que el evento que espera se complete.

Tipos de Planificadores

• Planificador: parte del SO encargado de asignar recursos (CPU) a los procesos de acuerdo con sus necesidades y prioridades.
• Planificador a largo plazo (o de trabajos): Controla el grado de multiprogramación, seleccionando los procesos que deben pasar a la cola de preparados. Se invoca con menos frecuencia (en segundos o minutos), por lo que puede ser más lento.
• Planificador a corto plazo (o de la CPU): Selecciona el siguiente proceso a ejecutarse en la CPU, gestionando cambios de contexto de forma frecuente. Es invocado con mucha frecuencia (en milisegundos), por lo que debe ser muy rápido para evitar retrasos en la ejecución.
• Planificador a medio plazo: Ajusta el número de procesos en memoria mediante swapping, sacando procesos al disco para liberar memoria y luego reincorporándolos.

Clasificación de Procesos

• Procesos limitados por E/S (o procesos cortos): pasan más tiempo realizando operaciones de E/S que utilizando la CPU.
  • Suelen tener muchas ráfagas cortas de CPU seguidas de largos periodos de espera mientras se completan las operaciones de E/S.
• Procesos limitados por CPU (o procesos largos): requieren principalmente tiempo de CPU, con menos dependencia de E/S.
  • Tienen pocas ráfagas de CPU pero son largas, dedicándose a cálculos intensivos y menos a esperar recursos externos.

Mezcla de Trabajos

Es importante que el planificador a largo plazo seleccione una buena mezcla de trabajos, ya que si todos los trabajos están limitados por E/S, la cola de preparados estará casi siempre vacía y el planificador a corto plazo tendrá poco que hacer. Y si todos los procesos están limitados por CPU, la cola de E/S estará casi siempre vacía y el sistema estará de nuevo desequilibrado.

Planificador a Medio Plazo

Cuando hay demasiados procesos en ejecución, el rendimiento puede disminuir porque todos compiten por la memoria y otros recursos. El planificador a medio plazo actúa para ajustar el grado de multiprogramación sacando algunos procesos de la memoria principal cuando no necesitan ejecutarse inmediatamente (swapping), especialmente en sistemas de tiempo compartido, enviándolos a memoria secundaria. Estos procesos esperan hasta que el planificador a medio plazo decida reintroducirlos en la memoria principal cuando los recursos lo permitan o cuando se necesite mejorar la mezcla de procesos (por ejemplo, tener un equilibrio entre procesos de CPU y de E/S).

Despachador

Despachador (dispatcher): módulo del sistema operativo encargado de ceder el control de la CPU al proceso seleccionado por el planificador a corto plazo. Esto involucra:

• Se realiza un cambio de contexto (en modo kernel).
• Cambia el modo de ejecución de la CPU de privilegiado a usuario para ejecutar el proceso de usuario.
• Reanuda la ejecución del proceso entrante en la posición de memoria adecuada.

Un despachador cambia el proceso en ejecución cuando se termina o bloquea un proceso, lo decide el sistema operativo, se agota el quantum de tiempo o se cambia de estado de bloqueado a ejecutable.

Latencia de despacho: el tiempo que tarda el despachador en detener un proceso y comenzar a ejecutar otro.

Políticas de Planificación de la CPU

Dado un proceso P que necesita un tiempo de servicio (ráfaga) t, definimos:

• Tiempo de respuesta (T): Es el tiempo total desde que el proceso entra en la cola de preparados hasta que termina su ejecución.
• Tiempo de espera (M): Este tiempo mide cuánto ha estado el proceso esperando en la cola de preparados, y se calcula como la diferencia entre el tiempo de respuesta (T) y el tiempo de servicio (t). M=T-t
• Penalización (P): Este valor representa el “costo” del tiempo de espera, calculado como la relación P=T/t
• Índice de respuesta (R): Mide la eficiencia del servicio recibido por el proceso, calculado como R=t/T. Valores cercanos a 1 indican que el proceso ha estado en ejecución casi todo el tiempo que ha estado en el sistema.
• Tiempo del núcleo: tiempo que el sistema operativo invierte en tomar decisiones de planificación y en realizar cambios de contexto. En sistemas eficientes, el tiempo de núcleo debería representar entre el 10% y el 30% del tiempo total de procesamiento. Valores más altos indican una sobrecarga administrativa, lo cual afecta la eficiencia.
• Tiempo de inactividad: Representa los periodos en que la cola de ejecutables está vacía y no se realiza trabajo productivo. Un tiempo de inactividad alto significa que la CPU está ociosa y no se aprovecha bien.
• Tiempo de retorno: Este tiempo mide cuánto tiempo se necesita para completar la ejecución de un proceso completo.

Clasificación de las Políticas de Planificación

Las políticas de planificación se adaptan de manera distinta según el tipo de proceso que manejan (por ejemplo, procesos que requieren mucha E/S versus procesos que requieren más CPU).

Ninguna política es completamente satisfactoria para todos los tipos de procesos, y mejorar el rendimiento para un tipo suele reducir la eficiencia para otros. Esta compensación obliga a seleccionar una política adecuada para el contexto específico del sistema.

• No apropiativas (no expulsivas): una vez que se le asigna la CPU a un proceso, éste retiene la CPU hasta que termine voluntariamente, es decir, cuando finaliza su tarea o se bloquea. Ejemplo de estas políticas incluyen "First Come, First Served" (FCFS) y "Shortest Job First" (SJF) en su versión no expulsiva.
• Apropiativas (expulsivas): permiten que el sistema operativo recupere la CPU de un proceso activo para asignársela a otro proceso. Esto ocurre, por ejemplo, cuando un proceso de mayor prioridad entra en la cola o cuando un proceso agota su quantum de tiempo asignado en políticas como el "Round Robin" o "Shortest Remaining Time First" (SRTF).

First Come, First Served (FCFS)

• Los procesos son atendidos en el orden en el que llegan a la cola de ejecutables. El proceso retiene la CPU hasta que completa su ejecución o se bloquea debido a una operación de E/S u otra espera. (No apropiativa)
• Es fácil de implementar ya que simplemente sigue el orden de llegada, utilizando una estructura de cola básica para organizar los procesos.
• Los procesos cortos pueden verse muy penalizados si se encuentran detrás de un proceso largo en la cola.
• Los procesos largos se benefician en términos de tiempo de espera.

Shortest Job First (SJF)

• El proceso con el menor tiempo de servicio estimado es el que recibe la CPU. Esto permite minimizar el tiempo medio de espera en la cola de ejecutables, ya que los procesos más cortos pasan primero y no se quedan bloqueados detrás de procesos largos. El proceso retiene la CPU hasta que completa su ejecución o se bloquea debido a una operación de E/S u otra espera (no apropiativo).
• Si hay varios procesos con el mismo tiempo estimado de servicio, SJF sigue la política FCFS (atendiendo en orden de llegada).
• SJF necesita conocer el tiempo de servicio de cada proceso de antemano, lo cual es difícil de obtener con exactitud en muchos sistemas.
• Ventaja para procesos cortos, desventaja para largos.

Shortest Remaining Time First (SRTF)

• A diferencia de SJF, SRTF es apropiativa, lo que significa que cada vez que un nuevo proceso llega a la cola de ejecutables, el sistema compara su tiempo de servicio con el tiempo de servicio restante del proceso que está ejecutándose.
• Si el nuevo proceso tiene un tiempo de servicio menor que el tiempo restante del proceso en ejecución, el sistema realiza un cambio de contexto para ejecutar el proceso nuevo.
• Al ejecutar siempre el proceso con el menor tiempo restante, SRTF minimiza el tiempo promedio de respuesta para los procesos más cortos.
• SRTF logra la menor penalización promedio de entre las políticas de planificación debido a que mantiene la cola de ejecutables en su mínimo posible, atendiendo primero a los procesos que pueden completarse más rápido.
• Los procesos con tiempos de servicio largos pueden experimentar retrasos significativos, ya que los procesos cortos pueden interrumpirlos constantemente, lo cual puede llevar a un caso de inanición para los procesos largos.

Planificación por Prioridades

• Cada proceso recibe un número de prioridad, generalmente un entero, y los procesos con un número de prioridad menor (que significa mayor prioridad) tienen preferencia para recibir la CPU. Así, el proceso con la prioridad más alta en la cola de ejecutables es el que se ejecuta.
• Apropiativa: El sistema puede interrumpir el proceso en ejecución si llega a la cola un proceso con mayor prioridad.
• No apropiativa: Una vez que un proceso empieza a ejecutarse, continúa hasta que finaliza o se bloquea, incluso si llega un proceso de mayor prioridad.
• Problema de inanición: Esta política puede llevar a la inanición de procesos de baja prioridad, ya que podrían no recibir nunca la CPU si continuamente llegan procesos de alta prioridad.
• Solución: Para evitar la inanición, el sistema puede implementar una técnica de envejecimiento, en la cual se incrementa la prioridad de los procesos de baja prioridad con el tiempo. Esto asegura que eventualmente recibirán la CPU.

Planificación por Turnos (Round Robin)

• La CPU se asigna a los procesos en intervalos de tiempo llamados quantum. Una vez que un proceso comienza a ejecutarse, tiene un tiempo limitado (quantum) para ejecutar su tarea.
• Si el proceso finaliza o se bloquea antes de que se agote su quantum, libera la CPU y el sistema selecciona el siguiente proceso en la cola de ejecutables.
• Si el proceso no termina durante su quantum, se interrumpe su ejecución, se coloca al final de la cola de ejecutables y el siguiente proceso recibe la CPU.
• Round Robin es una política apropiativa, ya que interrumpe el proceso en ejecución cuando se agota su quantum y asigna la CPU al siguiente proceso en la cola.
• El quantum suele estar entre 1/60 de segundo y 1 segundo, aunque su valor óptimo depende de la carga del sistema y del tipo de tareas en ejecución.
• Quantum muy grande: Si el quantum es excesivamente largo y supera el tiempo de servicio de todos los procesos, RR se comporta como una política FCFS.
• Quantum muy pequeño: Si el quantum es demasiado corto, el sistema pasa demasiado tiempo en cambios de contexto.

Colas Múltiples

• En esta política, la cola de procesos preparados se divide en varias subcolas, y cada proceso se asigna de forma permanente a una cola específica. Cada subcola puede tener su propio algoritmo de planificación.
• El sistema establece una planificación entre las subcolas para decidir el orden en el que se asigna la CPU a cada cola.
• Prioridad fija: Por ejemplo, primero se pueden atender los procesos interactivos, y luego los de tipo batch.
• Tiempo compartido: Se asigna una proporción del tiempo de CPU a cada cola (por ejemplo, 80% a interactivos con RR y 20% a batch con FCFS).

Colas Múltiples con Realimentación

• En este modelo los procesos pueden moverse entre colas según su comportamiento en tiempo de ejecución. Este enfoque permite ajustar la prioridad de un proceso a lo largo del tiempo, optimizando el uso de la CPU. Requiere definir:
• Número de colas: Se define cuántas subcolas existen.
• Algoritmo de cada cola: Cada subcola puede tener un algoritmo de planificación diferente.
• Método para cambiar procesos de cola: Se establecen reglas para trasladar procesos de una cola a otra (por ejemplo, reducir la prioridad de un proceso que consume mucha CPU).
• Método para asignar procesos a colas inicialmente: Algunos sistemas asignan procesos nuevos a la cola más alta y los degradan progresivamente si requieren más tiempo de CPU.
• Este tipo de planificación es común en sistemas operativos como Unix, Linux y Windows NT.

Planificación en Multiprocesadores

• Los sistemas multiprocesador pueden manejar la asignación de procesos de dos formas:
• Colas dedicadas para cada procesador, en los que el procesador solo asigna procesos de su propia cola.
• Una única cola de procesos preparados compartida por todos los procesadores, desde la cual se seleccionan los procesos para cada CPU.
• Cada procesador puede ejecutar varios procesos simultáneamente, alternándolos según una política de planificación específica.
• El sistema operativo decide cuándo y en qué procesador se activa un proceso.
• La planificación de procesos en multiprocesadores es similar a la planificación en sistemas monoprocesador, pero se deben tener en cuenta el número de CPUs y cómo se asignan y liberan los procesos en los distintos procesadores.
• La planificación de hilos en un sistema multiprocesador permite aprovechar el paralelismo real dentro de una aplicación. La ejecución simultánea de múltiples hilos de una misma tarea en diferentes procesadores puede mejorar significativamente el rendimiento de aplicaciones que pueden dividirse en tareas concurrentes.

Estrategias de Planificación de Hilos en Multiprocesadores

• Compartición de carga: los procesadores comparten una cola global de hilos preparados. Cuando un procesador está ocioso, selecciona un hilo de esta cola para ejecutar.
• Planificación en pandilla (gang scheduling): un grupo de hilos relacionados (de una misma tarea) se asigna para ejecutarse de manera simultánea en un conjunto de procesadores (relación 1 a 1). Es útil para aplicaciones que requieren sincronización frecuente entre hilos, ya que evita que un hilo quede esperando a otros.
• Asignación de procesador dedicado: cada hilo de una aplicación recibe un procesador dedicado desde el inicio de su ejecución hasta su finalización. De esta manera, el procesador no cambia de hilo ni realiza multiprogramación. Elimina la sobrecarga de cambio de contexto y es útil para tareas que requieren tiempos de ejecución constantes o mínimas interrupciones.
• Planificación dinámica: el número de hilos de un proceso puede variar a lo largo del tiempo. El sistema operativo ajusta la cantidad de hilos que pueden ejecutarse simultáneamente en función de la carga de trabajo y disponibilidad de procesadores.

Sistemas de Tiempo Real

• En un sistema de tiempo real, no basta con que el sistema produzca resultados correctos; también es crucial la puntualidad en la entrega.
• Tipos de tareas de tiempo real:
  • Tareas de tiempo real duro: Deben cumplir estrictamente con sus plazos límite. Si no se completan a tiempo, el sistema puede fallar.
  • Tareas de tiempo real suave: Tienen un plazo límite preferido, pero no obligatorio. Si se completan fuera de este plazo, el rendimiento del sistema puede disminuir.
  • Tareas periódicas: deben ejecutarse a intervalos de tiempo regulares. Su tiempo de ejecución es predecible.
  • Tareas aperiódicas: No tienen una frecuencia de ejecución predefinida y pueden ser impredecibles en cuanto a cuándo deben comenzar o terminar. Aun así, pueden tener restricciones de tiempo para empezar o concluir.

Planificación de Sistemas de Tiempo Real

• En los sistemas de tiempo real, la planificación debe analizarse para verificar que las tareas se completarán en sus plazos límite.
• El sistema debe asegurar que todas las tareas periódicas puedan cumplirse de acuerdo con sus periodos.
• Puede realizarse de manera estática (antes de la ejecución) o dinámica (durante la ejecución).
• Planificación estática:
  • Dirigida por tabla: Genera un plan fijo antes de la ejecución, especificando cuándo debe comenzar cada tarea. Es ideal para entornos predecibles.
  • Expulsiva por prioridad: No crea un plan fijo, pero asigna prioridades altas a tareas críticas, de modo que las más importantes se ejecuten primero.
• Planificación dinámica:
  • Basada en un plan: Evalúa en tiempo real si una nueva tarea puede ser completada a tiempo. Solo se acepta si el sistema puede cumplir con el plazo.
  • De menor esfuerzo: No realiza un análisis previo; el sistema intenta cumplir con todos los plazos y aborta tareas si no pueden completarse a tiempo.

Problema de la Inversión por Prioridad

• La inversión de prioridad ocurre cuando una tarea de alta prioridad queda bloqueada esperando a que una tarea de menor prioridad libere un recurso que tiene en uso. Esto puede causar que la tarea de alta prioridad no cumpla con su plazo límite.
• Enfoques para evitar la inversión de prioridad:
  • Herencia de prioridad: En este método, la tarea de baja prioridad "hereda" temporalmente la prioridad de la tarea de alta prioridad que está esperando por el recurso. Una vez que la tarea de baja prioridad libera el recurso, recupera su prioridad original.
  • Techo de prioridad: Cada recurso tiene un "techo de prioridad" que es mayor que cualquier prioridad de las tareas que puedan requerir ese recurso. Al asignar el recurso a una tarea, se le asigna temporalmente esta prioridad máxima, evitando que otras tareas interfieran.

Diseño e Implementación de Procesos e Hilos en Linux

Introducción

• En Linux, cada proceso es identificado por un número único llamado PID (Process ID), que permite al sistema operativo gestionar y diferenciar entre procesos.
• El proceso 0 es el primer proceso creado al iniciar el sistema y se encarga de crear al proceso 1 (Init), que es el proceso padre de todos los demás procesos en el sistema. Init permanece activo durante toda la vida del sistema.
• Los procesos en Linux se crean mediante la llamada al sistema fork(), que genera una copia del proceso actual, o clone(), que permite compartir recursos entre procesos, creando efectivamente hilos (threads) dentro del mismo espacio de memoria.

Estructura Task

• Linux mantiene una lista de todos los procesos del sistema en una estructura llamada task list, que es una lista doblemente enlazada y circular.
• Cada entrada en esta lista es una estructura task_struct, que representa a un descriptor de proceso. (PCB)
• La estructura task_struct es el descriptor de proceso en Linux, que almacena información sobre el estado del proceso, su prioridad, relaciones con otros procesos, permisos, y otra información de control y planificación.
• task_struct está definido en <include/linux/sched.h>

Estados de un Proceso en Linux

• La variable state de task_struct especifica el estado actual de un proceso.
• Ejecución (TASK_RUNNING): Un proceso en este estado está ejecutándose o listo para ejecutarse en la CPU.
• Interrumpible (TASK_INTERRUPTIBLE): El proceso está bloqueado esperando un evento y puede ser interrumpido por señales.
• No interrumpible (TASK_UNINTERRUPTIBLE): El proceso está bloqueado esperando un evento, pero no responde a señales. Solo cambia de estado cuando ocurre el evento esperado.
• Parado (TASK_STOPPED): El proceso ha sido detenido, generalmente por una señal, y solo puede reanudarse mediante una acción externa.
• Traceado (TASK_TRACED): El proceso está siendo observado por otro proceso, generalmente un depurador.
• Zombie (EXIT_ZOMBIE): El proceso ha terminado su ejecución, pero aún conserva su entrada en la tabla de procesos. Este estado persiste hasta que su proceso padre llama a wait(), lo cual elimina la entrada y libera recursos.

Árbol de Procesos

• Cada task_struct incluye punteros que definen las relaciones jerárquicas entre procesos:
• Puntero al proceso padre (parent): Apunta al proceso que creó al proceso actual.
• Lista de hijos (children): Apunta a una lista de todos los procesos hijos creadados por este proceso.
• Lista de hermanos (sibling): Apunta a una lista que enlaza a todos los procesos hijo del mismo padre.
• En Linux, todos los procesos son descendientes del proceso init.

Implementación de Hilos en Linux

• En Linux, no existe una diferencia formal entre procesos e hilos desde el punto de vista del núcleo. Un hilo en Linux es simplemente un proceso que comparte ciertos recursos con otros procesos.
• Cada hilo tiene su propia task_struct, igual que un proceso completo
• La llamada al sistema clone() es la clave para crear hilos en Linux. A diferencia de fork(), clone() permite crear un nuevo proceso que comparte recursos específicos (como el espacio de direcciones, archivos abiertos y manejadores de señales) con el proceso que lo creó.
• La función clone() recibe una serie de banderas (flags) que indican qué recursos compartir entre el proceso padre y el hijo, logrando así la funcionalidad de los hilos.
• int clone(int (*fn)(void *), void *child_stack, int flags, void *arg);

Hebras Kernel

• Las hebras del núcleo se crean para que el núcleo lleve a cabo operaciones en segundo plano dentro del sistema operativo. Estas tareas no están vinculadas a un proceso de usuario específico, por lo que no tienen un espacio de direcciones de usuario. Su puntero de memoria es NULL, ya que operan únicamente en el espacio del núcleo.
• Las hebras del núcleo están sujetas a la planificación del sistema operativo y pueden ser expropiadas, interrumpidas temporalmente para dar prioridad a otras tareas.
• Las hebras del núcleo se crean cuando el sistema arranca, utilizando la llamada al sistema clone() con banderas que permiten la creación de un hilo en el espacio del núcleo.
• Una hebra del núcleo finaliza su ejecución cuando completa su tarea o al llamar a la función do_exit. También puede ser finalizada por otra parte del núcleo si es necesario.

Operaciones con Procesos en Linux

Creación de Procesos

copy_process() lleva a cabo las siguientes tareas:

Crea una nueva estructura thread_info (que contiene la pila del núcleo) y task_struct

Configura los valores iniciales en task_struct para el proceso hijo. Algunos valores son copiados del padre.

Inicialmente, el estado del hijo se establece en TASK_UNINTERRUPTIBLE.

Ajusta ciertas banderas en task_struct del hijo para definir permisos y comportamiento:

PF_SUPERPRIV = 0: Indica que el proceso no tiene privilegios de superusuario.

PF_FORKNOEXEC = 1: Indica que el proceso se ha creado mediante fork, pero aún no ha ejecutado exec para cargar un nuevo programa.

Llama a la función alloc_pid() para asignar un PID único al proceso hijo.

Según las banderas pasadas a clone(), el nuevo proceso puede compartir o duplicar recursos específicos del padre.

Finalmente, cambia el estado del hijo a TASK_RUNNING. Luego, devuelve un puntero a la estructura task_struct del hijo, completando el proceso de creación.

2.7.2. Terminación de procesos

Cuando un proceso termina, el kernel libera todos sus recursos y notifica al padre su terminación. Ocurre generalmente cuando se ejecuta la llamada al sistema exit(), la cual puede ser:

Explícita: El programador incluye la llamada a exit() en el código del proceso.

Implícita: El compilador agrega automáticamente una llamada a exit() cuando la función main() finaliza.

Un proceso también puede terminar si recibe una señal que tiene definida la acción de terminación. Las señales pueden ser enviadas por el sistema operativo o por otros procesos.

2.7.3. Actuación de do_exit()

El trabajo de liberación de recursos lo hace la función do_exit(), la cual:

Activa la bandera de salida (PF_EXITING):

Para cada recurso usado por el proceso, el sistema decrementa un contador que indica cuántos procesos están utilizando ese recurso. Si el contador llega a cero, el recurso se libera definitivamente.

El valor pasado a exit() se almacena en el campo exit_code del task_struct, que representa el estado de terminación para el proceso padre.

El sistema envía una señal al proceso padre, informándole de la finalización de su hijo.

Si el proceso que termina tiene procesos hijo, estos se asignan al proceso init (con PID = 1) como su nuevo padre, salvo que el grupo de procesos indique lo contrario.

El estado del proceso se cambia a EXIT_ZOMBIE.

Finalmente, do_exit() llama a schedule() para que el planificador seleccione otro proceso para ejecutar. Este es el último paso del proceso antes de su eliminación.

3.  PLANIFICACIÓN DE PROCESOS EN LINUX

3.1. PLANIFICACIÓN DE TIEMPO REAL

Los procesos bajo estas políticas tienen prioridades entre 1 y 99 y existe una cola para cada prioridad.

SCHED_FIFO (First In, First Out): Los procesos se ejecutan hasta que finalizan, se bloquean, o un proceso con mayor prioridad los interrumpe. Si se interrumpe por otro proceso de mayor prioridad, el proceso permanece al inicio de su cola.

SCHED_RR (Round Robin): Este algoritmo asigna a cada proceso una rodaja de tiempo durante la cual se ejecuta. Si un proceso no agota su rodaja por ser interrumpido por un proceso de mayor prioridad, podrá completarla cuando vuelva a recibir la CPU.

SCHED_DEADLINE: utilizado para procesos que requieren activarse periódicamente con un tiempo máximo de finalización en cada periodo. Los procesos se seleccionan según las restricciones de cada uno.

3.2. PLANIFICACIÓN DE TIEMPO NO REAL

Los procesos bajo estas políticas tienen prioridad 0 y por lo tanto no se ejecutarán mientras haya algún proceso de tiempo real listo para ejecutarse.

SCHED_OTHER/SCHED_NORMAL: se aplica un algoritmo de reparto de tiempo. Se establece otro nivel de prioridad (nice value) con valores entre -20 (más prioridad) y 19 (menos prioridad) para establecer prioridades en ese reparto.

SCHED_BATCH: derivada de la anterior. El planificador asumirá que los procesos hacen un uso intensivo del procesador y no requieren de medidas para reducir la latencia. Útil para procesos no interactivos donde se desea reducir los cambios de contexto.

SCHED_IDLE: adecuada para procesos que se desean ejecutar con la mínima prioridad (por debajo de los procesos con nice value igual a 19 de SCHED_OTHER o SCHED_BATCH)

3.3. PREMISAS

El objetivo es distribuir el tiempo de CPU de manera justa entre los procesos listos para ejecutarse, asignando a cada uno una porción de tiempo proporcional a su peso.

Cada proceso tiene un peso que el planificador utiliza para determinar cuánta CPU se le asigna. Así, los procesos con mayor peso reciben una mayor proporción del tiempo de CPU.

Asumimos un procesador hipotético que podría repartir de manera infinitesimal el tiempo entre procesos de acuerdo con sus pesos, aunque en la práctica no es posible ya que una CPU real solo puede ejecutar una instrucción a la vez.

3.4. TIEMPO VIRTUAL

Para asegurar un reparto equitativo de CPU, se introduce el concepto de tiempo virtual. Este tiempo se normaliza de acuerdo con el peso de cada proceso y la cantidad de procesos listos para ejecutarse.

Unidad de tiempo virtual: Es el tiempo necesario para que cada proceso ejecute una cantidad de tiempo real proporcional a su peso. 𝑉𝑇𝑅𝑇=𝑟𝑡/∑𝑃𝑒𝑠𝑜𝑗 permite calcular el tiempo virtual transcurrido 𝑉𝑇𝑅𝑇 durante un período 𝑟𝑡 de tiempo real, tomando en cuenta el peso de cada proceso 𝑃𝑒𝑠𝑜𝑗 en un conjunto de 𝑁 procesos.

Tiempo real necesario para el proceso 𝑃𝑖 durante un tiempo 𝑝𝑡: 𝑅𝑇𝑃𝑇=𝑝𝑡×(∑𝑃𝑒𝑠𝑜𝑗/𝑃𝑒𝑠𝑜𝑖)

Tiempo virtual para ejecutar el proceso 𝑃𝑖 durante un tiempo 𝑝𝑡: 𝑉𝑇𝑃𝑇=𝑟𝑡/∑𝑃𝑒𝑠𝑜𝑗=𝑝𝑡/𝑃𝑒𝑠𝑜𝑖 

CPU real vs. CPU hipotética:

En la práctica, una CPU real no puede repartir tiempo infinitesimalmente, por lo que existen dos enfoques para simular el tiempo virtual:

Asignar rodajas de tiempo de CPU predefinidas, ejecutando los procesos en un orden que simule el comportamiento de la CPU hipotética. Este método se utiliza en el algoritmo EEVDF (Earliest Eligible Virtual Deadline First).

Planificar la ejecución para que, dentro de un período específico, todos los procesos acumulen una cantidad de tiempo virtual proporcional a su peso. Este es el principio que usa el planificador CFS (Completely Fair Scheduler).

3.5. ALGORITMO EEVDF (Earliest Eligible Virtual Deadline First)

EEVDF es el algoritmo de planificación de procesos predeterminado para la política SCHED_OTHER/SCHED_NORMAL.

Selecciona el proceso con el plazo de finalización de rodaja más cercano (próximo deadline) entre los procesos elegibles.

Un proceso es elegible si su tiempo de elegibilidad es menor o igual al tiempo virtual del sistema. Si un proceso ha recibido más tiempo de CPU del ideal, no será elegible hasta que se cumpla el plazo de su próxima rodaja.

La fórmula para el cálculo del tiempo de finalización virtual de la próxima rodaja es: 𝑉𝑇𝐸𝑁𝑆(𝑃𝑖)=tiempo_elegible(𝑃𝑖)+tamaño_rodaja(𝑃𝑖)/Peso(𝑖)

El valor de 𝑉𝑇𝐸𝑁𝑆(𝑃𝑖) indica el momento en el tiempo virtual en el que la rodaja actual del proceso debería finalizar.

Si el proceso no agota su rodaja, se usa la duración real de la ráfaga de CPU en lugar del tamaño completo de la rodaja.

Al finalizar su rodaja, el tiempo de elegibilidad del proceso se actualiza al próximo valor de VTENS, lo que permite que los procesos se ejecuten proporcionalmente a su peso.

Cuando se crea un proceso, se inicializa su tiempo de elegibilidad al tiempo virtual del sistema. La finalización de la rodaja se calcula con VTENS para definir cuándo podrá ser elegible de nuevo.

Al terminar o bloquearse un proceso durante su rodaja, su tiempo de elegibilidad se ajusta para la siguiente ejecución.

Los procesos de mayor peso tienen un incremento de VTENS más pequeño, lo cual los hace elegibles antes y les permite recibir más tiempo de CPU proporcionalmente.

3.6. ALGORITMO CFS (Completely Fair Scheduler )

CFS fue el planificador principal en Linux desde la versión 2.6.23 hasta la 6.6.

Fue reemplazado por EEVDF debido a su complejidad en la gestión de casos específicos, como procesos muy sensibles a la latencia.

CFS utiliza el tiempo virtual de ejecución (vruntime) para llevar un registro del tiempo que cada proceso ha usado la CPU en función de su prioridad.

El peso se basa en el valor de nice del proceso, que varía entre -20 y 19, y se calcula con la fórmula:

Peso(prioridad)≈1024/1.25prioridad

Un proceso con mayor prioridad (menor nice) tendrá más peso y recibirá más tiempo de CPU.

Cálculo de vruntime: vruntime se incrementa con el tiempo en que el proceso consume CPU, ajustado por el peso. La fórmula para actualizar vruntime es:

vruntime(𝑃𝑖)+=𝑝𝑡×Peso(0)/Peso(𝑃𝑖) donde Peso(0) representa un peso de referencia (con nice 0) y pt es el tiempo de CPU usado por el proceso 𝑃𝑖.

Asignación de rodajas de CPU: CFS establece un horizonte de planificación (período) y distribuye el tiempo de CPU proporcionalmente según el peso de cada proceso. La rodaja asignada a un proceso depende de su peso:

rodaja(𝑃𝑖)=periodo×Peso(𝑃𝑖)/∑Peso(𝑃𝑗) 

Ejecución según vruntime: Durante un período de planificación, CFS ejecuta todos los procesos listos, respetando sus pesos para distribuir el tiempo de CPU de manera justa.

Cuando un proceso se bloquea, su vruntime se congela y, al reanudarse, se beneficia con un valor reducido, lo que facilita su retorno a la CPU sin monopolizarla.

Al crearse un nuevo proceso, se le asigna el valor mínimo de vruntime entre los procesos listos, evitando desventajas frente a procesos en ejecución.

CFS mantiene un árbol balanceado (RB-Tree) para ordenar los procesos listos según vruntime, priorizando el proceso con menor vruntime (ubicado en la hoja más a la izquierda) para garantizar que cada proceso reciba su parte de tiempo de CPU.

3.7. PLANIFICACIÓN EN SISTEMAS MULTIPROCESADOR

En este esquema, cada procesador tiene su propia cola de procesos, lo que reduce la competencia por acceso a una única cola.

Se utilizan criterios de migración para equilibrar la carga entre procesadores. Esto asegura que ningún procesador esté inactivo mientras otros tienen exceso de carga.

La gestión de los procesadores y el algoritmo de planificación son independientes entre sí.

Este esquema permite que los procesos mantengan una afinidad natural con un procesador específico, lo cual maximiza el uso de la memoria caché del procesador. La afinidad evita que los procesos se muevan entre procesadores innecesariamente.

3.8. ARQUITECTURA NUMA (Non-Uniform Memory Access)

En arquitecturas NUMA, cada procesador tiene acceso directo a una parte específica de la memoria total del sistema.

Aunque cualquier procesador puede acceder a toda la memoria, el acceso a la memoria de acceso directo es más rápido que a la memoria de otros nodos, ya que este último requiere comunicación a través de buses entre nodos, lo que es menos eficiente.

Esta arquitectura surge para reducir la complejidad de mantener la coherencia de las memorias caché entre procesadores, especialmente en sistemas grandes con múltiples CPUs.

Se debe intentar que la memoria usada por los procesos ejecutados en un procesador sea accesible de forma directa.

4. PROCESOS E HILOS EN WINDOWS

Windows utiliza un modelo de colas múltiples donde cada cola tiene un nivel de prioridad.

Si un proceso (o hebra) con mayor prioridad se vuelve activo, interrumpe al proceso en ejecución, independientemente de si este ha agotado su rodaja de tiempo. Esto asegura que los procesos de mayor prioridad reciban la CPU lo antes posible.

Las prioridades en Windows van de 0 a 31:

Prioridades 16 a 31: Se reservan para procesos de tiempo real.

Prioridades 1 a 15: Se destinan a procesos normales con prioridades dinámicas.

Prioridad 0: Está reservada para el sistema y no se asigna a procesos de usuario.

El quantum de CPU (rodaja de tiempo) es más largo en versiones de Windows para servidores, optimizando la eficiencia en entornos que requieren estabilidad en la ejecución de tareas.

Se puede incrementar temporalmente la prioridad de una hebra en programas interactivos, para favorecer a hebras que han completado operaciones de E/S y están listas para ejecutarse, para evitar la inanición.

En sistemas multiprocesador (a partir de Windows 8/2012), las hebras listas para ejecutarse se agrupan en colas por grupos de procesadores.

Los procesadores se organizan en grupos para mantener la afinidad de las hebras con procesadores específicos, optimizando el uso de la memoria caché y reduciendo la necesidad de migrar hebras entre CPUs.