Buscar algoritmo de programación de procesos

Parte 1: Introducción a los algoritmos de programación en tiempo real

POSIX 1003.b define qué es un sistema en tiempo real: se refiere a la capacidad del sistema para proporcionar el nivel requerido dentro de un Servicios de tiempo de respuesta limitado. Una definición más aceptada propuesta por Donald Gillies es: un sistema en tiempo real significa que la exactitud del cálculo depende no sólo de la corrección lógica del programa, sino también del momento en que se generan los resultados si las limitaciones de tiempo del mismo. sistema no se obtienen. Si se cumple, se producirá un error del sistema.

Los sistemas en tiempo real se pueden dividir en dos tipos: tiempo real suave y tiempo real duro en función de sus diferentes requisitos de tiempo real. Un sistema estricto en tiempo real se refiere a un sistema que tiene un tiempo de servicio garantizado en el peor de los casos, es decir, la fecha límite para el tiempo de respuesta al evento debe cumplirse pase lo que pase. Por ejemplo, el control de naves espaciales en el sector aeroespacial es en realidad un sistema de este tipo. Todos los demás sistemas con características de tiempo real pueden denominarse sistemas blandos en tiempo real. Para ser claros, los sistemas blandos en tiempo real son aquellos que, desde un punto de vista estadístico, una tarea (en la siguiente discusión, no distinguiremos entre tareas y procesos) puede obtener un tiempo de procesamiento garantizado, y los eventos que llegan al sistema también pueden obtener un tiempo de procesamiento garantizado. Se procesa antes de que llegue la fecha límite, pero violar la fecha límite no genera errores fatales. Un sistema multimedia en tiempo real es un sistema suave en tiempo real.

Para que un sistema informático proporcione soporte en tiempo real, su sistema operativo debe programar y gestionar eficazmente la CPU y otros recursos. En los sistemas multitarea en tiempo real, la programación y gestión de recursos son más complejas. El siguiente artículo analizará primero varios algoritmos de programación de tareas en tiempo real desde una perspectiva de clasificación, y luego estudiará la programación de procesos de los sistemas operativos Linux comunes y las mejoras realizadas por varios sistemas Linux en tiempo real a los sistemas Linux comunes para admitir la programación real. características del tiempo. Finalmente, se analizan algunos problemas que surgen cuando el sistema operativo Linux se aplica al campo del tiempo real y se resume cómo varios Linux en tiempo real resuelven estos problemas.

1. Clasificación de los algoritmos de programación de CPU en tiempo real

Los algoritmos de programación en tiempo real de varios sistemas operativos en tiempo real se pueden dividir en las siguientes tres categorías [Wang99][Gopalan01 ]: Algoritmo de programación basado en prioridades (Programación basada en prioridades-PD), un algoritmo de programación basado en recursos compartidos basado en la proporción de uso de la CPU (Programación basada en recursos compartidos-SD) y un algoritmo de programación de procesos basado en el tiempo (Programación basada en tiempos- TD), de la siguiente manera: Estos tres algoritmos de programación se presentan uno por uno.

1.1. Algoritmo de programación basado en prioridades

El algoritmo de programación basado en prioridades asigna una prioridad a cada proceso Cuando se programa cada proceso, el programador siempre programa la tarea con mayor prioridad. se ejecuta. Según los diferentes métodos de asignación de prioridades, los algoritmos de programación basados ​​en prioridades se pueden dividir en los siguientes dos tipos [Krishna01][Wang99]:

Algoritmo de programación de prioridades estáticas:

Este tipo La programación El algoritmo asigna estáticamente una prioridad a todos los procesos que se ejecutan en el sistema. La asignación de prioridad estática puede basarse en atributos de la aplicación, como el ciclo de tareas, la prioridad del usuario u otras políticas predeterminadas. El algoritmo de programación RM (Rate-Monotonic) es un algoritmo de programación de prioridad estática típico. Determina la prioridad de programación en función de la duración del ciclo de ejecución de la tarea. Las tareas con un ciclo de ejecución pequeño tienen mayor prioridad.

Algoritmo de programación de prioridades dinámicas:

Este algoritmo de programación asigna dinámicamente la prioridad de las tareas según sus requisitos de recursos. Su propósito es lograr una mayor eficiencia en la asignación y flexibilidad de recursos. Existen muchos algoritmos de programación de este tipo en sistemas que no son de tiempo real, como los algoritmos de programación de trabajos cortos primero. Entre los algoritmos de programación en tiempo real, el algoritmo EDF es el algoritmo de programación de prioridad dinámica más utilizado. Este algoritmo asigna prioridad a cada tarea en la cola lista de acuerdo con su fecha límite (fecha límite). La tarea con la última fecha límite tiene la prioridad más alta.

1.2. Algoritmo de programación de intercambio proporcional

Aunque el algoritmo de programación basado en prioridades es simple y eficaz, este algoritmo de programación proporciona una programación difícil en tiempo real. para utilizar este algoritmo de programación: por ejemplo, aplicaciones suaves en tiempo real, como sistemas de conferencias multimedia en tiempo real. Para este tipo de aplicación suave en tiempo real, es más adecuado utilizar un algoritmo de programación de recursos compartidos proporcional (algoritmo SD).

El algoritmo de programación compartida proporcional se refiere a un algoritmo de programación compartida basado en la proporción de uso de la CPU. Su idea básica es programar un grupo de tareas que deben programarse de acuerdo con un cierto peso (proporción). su tiempo de ejecución sea exactamente proporcional a su peso.

Podemos implementar el algoritmo de programación de intercambio proporcional [Nieh01] de dos maneras: el primer método es ajustar la frecuencia de cada proceso listo que aparece al principio de la cola de programación y programar el proceso al principio. de la ejecución de la cola; el segundo método es programar cada proceso en la cola lista para que se ejecute uno por uno, pero ajustar el tiempo de ejecución de cada proceso de acuerdo con el peso asignado.

Los algoritmos de programación de intercambio proporcional se pueden dividir en las siguientes categorías: método de rotación, reparto justo, cola justa, método de programación de lotería (Lotería), etc.

Un problema con el algoritmo de programación de intercambio proporcional es que no define ningún concepto de prioridad; todas las tareas comparten recursos de CPU según la proporción que solicitan cuando el sistema está en un estado de sobrecarga. de todas las tareas será proporcionalmente más lenta. Por lo tanto, para garantizar que los procesos en tiempo real en el sistema puedan obtener una cierta cantidad de tiempo de procesamiento de la CPU, generalmente se utiliza un método para ajustar dinámicamente los pesos de los procesos.

1.3. Algoritmo de programación de procesos basado en el tiempo

Para sistemas simples con entradas estables y conocidas, se puede utilizar el algoritmo de programación basado en el tiempo (TD), que puede proporcionar una buena previsibilidad. para el procesamiento de datos. Este algoritmo de programación es esencialmente un método de programación estático fuera de línea determinado en el momento del diseño. En la etapa de diseño del sistema, después de que todas las condiciones de procesamiento en el sistema estén claras, se hacen arreglos y diseños claros con anticipación para el tiempo de inicio, cambio y finalización de cada tarea. Este algoritmo de programación es adecuado para entornos de aplicaciones como pequeños sistemas integrados, sistemas de control automático y sensores.

La ventaja de este algoritmo de programación es que la ejecución de las tareas es muy predecible, pero la mayor desventaja es la falta de flexibilidad, y habrá situaciones en las que las tareas deben ejecutarse pero la CPU permanece inactiva.

2. Programación de CPU en sistemas Linux generales

Los sistemas Linux generales admiten procesos en tiempo real y no real. Los procesos en tiempo real tienen prioridad absoluta en relación con los procesos ordinarios. En consecuencia, los procesos en tiempo real utilizan la estrategia de programación SCHED_FIFO o SCHED_RR, y los procesos ordinarios utilizan la estrategia de programación SCHED_OTHER.

En la implementación del algoritmo de programación, cada tarea en Linux tiene cuatro parámetros relacionados con la programación, que son rt_priority, Policy, Priority (nice) y Counter. El planificador programa procesos en función de estos cuatro parámetros.

En la política de programación SCHED_OTHER, el programador siempre selecciona el proceso con mayor prioridad+valor de contador para programar la ejecución. Desde un análisis lógico, la política de programación SCHED_OTHER tiene un ciclo de programación (época). En cada ciclo de programación, la prioridad y el valor del contador de un proceso afectan qué proceso debe programarse para su ejecución en el momento actual, donde la prioridad es un valor fijo. El valor cambiante se determina cuando se crea el proceso. Representa la prioridad del proceso y el número de intervalos de tiempo que el proceso puede obtener en cada ciclo de programación es un valor que cambia dinámicamente y refleja el intervalo de tiempo restante de un; proceso en el ciclo de programación actual. Al comienzo de cada ciclo de programación, el valor de prioridad se asigna al contador y luego, cada vez que se programa la ejecución del proceso, el valor del contador disminuye. Cuando el valor del contador es cero, el proceso ha agotado su intervalo de tiempo en este ciclo de programación y ya no participa en la programación del proceso en este ciclo de programación.

Un ciclo de programación finaliza cuando se han agotado todos los intervalos de tiempo de los procesos y luego el ciclo comienza de nuevo. Además, se puede ver que el ciclo de programación en el sistema Linux no es estático, es una cantidad que cambia dinámicamente. Por ejemplo, la cantidad de procesos en el estado ejecutable y sus valores de prioridad pueden afectar la duración de una época. . Vale la pena señalar que en los núcleos superiores a 2.4, la prioridad se reemplaza por agradable, pero los dos tienen funciones similares.

Se puede ver que la política de programación SCHED_OTHER es esencialmente una política de programación de intercambio proporcional. Su método de diseño puede garantizar la equidad de la programación del proceso: un proceso de baja prioridad en cada proceso En la época, también obtendrá. el tiempo de ejecución de la CPU que se merece. Además, también proporciona diferenciación de prioridad para diferentes procesos. Los procesos con valores de alta prioridad pueden obtener más tiempo de ejecución.

Para procesos en tiempo real, utilizan la estrategia de programación de prioridades basada en la prioridad de tiempo real rt_priority. Sin embargo, según las diferentes estrategias de programación, los métodos de programación entre procesos con la misma prioridad en tiempo real son diferentes. :

SCHED_FIFO: diferentes procesos se ponen en cola de acuerdo con prioridades estáticas y luego, en la misma cola de prioridad, quien esté listo para ejecutarse primero se programará primero y el proceso en ejecución no finalizará hasta que se cumplan las siguientes condiciones. Ocurrencia: 1. La CPU está ocupada por un proceso con una prioridad más alta; 2. Está bloqueada debido a solicitudes de recursos 3. Entrega voluntariamente la CPU (llamando a sched_yield);

SCHED_RR: esta programación; La estrategia es similar al SCHED_FIFO anterior y es exactamente la misma, excepto que asigna un intervalo de tiempo a cada proceso. Cuando el intervalo de tiempo llega al proceso en ejecución, abandonará la ejecución y se puede obtener llamando a sched_rr_get_interval;

Dado que el sistema Linux en sí es un sistema orientado a escritorio, existen algunos problemas al aplicarlo a aplicaciones en tiempo real:

La unidad de programación en; el sistema Linux dura 10 ms, por lo que no puede proporcionar una sincronización precisa.

Cuando un proceso llama a una llamada al sistema para ingresar al modo kernel, no se puede adelantar.

La implementación del kernel de Linux utiliza un; una gran cantidad de operaciones de interrupción de bloqueo provocarán la pérdida de interrupciones.

Debido al uso de tecnología de memoria virtual, cuando ocurre una falla de página, los datos de intercambio deben leerse desde el disco duro, pero es duro; la lectura y escritura del disco provocará tiempos de lectura y escritura aleatorios debido a la aleatoriedad de las ubicaciones de almacenamiento, lo que afectará en algunos casos la fecha límite de las tareas en tiempo real.

Aunque la programación de procesos de Linux también admite el tiempo real; prioridad, carece de un mecanismo y algoritmo de programación efectivos para el procesamiento de protocolos en tiempo real de su subsistema de red y el procesamiento de interrupciones de otros dispositivos. Ninguno de ellos está asociado con la programación de sus procesos correspondientes y ellos mismos no tienen un mecanismo de programación claro;

3. Varios sistemas Linux en tiempo real

3.1 RT-Linux y RTAI

RT-Linux es un resultado de investigación del Instituto de Tecnología de Nuevo México [. RTLinuxWeb][Barabanov97]. Su idea básica es que para proporcionar soporte estricto en tiempo real en el sistema Linux, implementa un pequeño sistema operativo en tiempo real con un microkernel (también lo llamamos el subsistema en tiempo real de RT-Linux) y convierte el sistema Linux normal en Se ejecuta como una tarea de baja prioridad dentro del sistema operativo. Además, las tareas en sistemas Linux normales pueden comunicarse con tareas en tiempo real a través de FIFO. El marco de RT-Linux se muestra en la Figura 1:

Figura 1 Estructura de RT-Linux

La tecnología clave de RT-Linux es simular el controlador de interrupciones de hardware a través del software. Cuando el sistema Linux quiere bloquear la interrupción de la CPU, el subsistema en tiempo real en RT-Linux interceptará la solicitud y la registrará, sin bloquear realmente la interrupción del hardware. Esto evita fallas del sistema causadas por interrupciones de bloqueo. durante un período de tiempo, mejorando así el rendimiento en tiempo real.

Cuando llega una interrupción de hardware, RT-Linux intercepta la interrupción y determina si hay una rutina de interrupción en el subsistema en tiempo real para manejarla o si se pasa al kernel de Linux normal para su procesamiento. Además, la precisión de sincronización mínima en los sistemas Linux normales está determinada por la frecuencia del reloj en tiempo real del sistema. Generalmente, los sistemas Linux configuran el reloj en 100 interrupciones de reloj por segundo, por lo que la precisión de sincronización general en los sistemas Linux es de 10 ms. , que es el ciclo del reloj es de 10 ms, y RT-Linux puede proporcionar una granularidad de programación a nivel de más de una docena de microsegundos configurando el reloj en tiempo real del sistema en un estado de disparo único.

La programación de tareas en el subsistema en tiempo real RT-Linux puede utilizar algoritmos basados ​​en prioridades como RM y EDF, u otros algoritmos de programación.

RT-Linux es de hecho una buena opción para sistemas propietarios que funcionan con cargas pesadas, pero solo proporciona la programación de recursos de CPU y la relación entre sistemas en tiempo real y sistemas Linux comunes. En este caso, los desarrolladores no pueden aprovechar al máximo las funciones que se han implementado en el sistema Linux, como las pilas de protocolos, etc. Por lo tanto, RT-Linux es adecuado para entornos con tareas simples en tiempo real, como control industrial y requisitos estrictos en tiempo real. Sin embargo, si se va a aplicar en el procesamiento multimedia, queda mucho trabajo por hacer.

La RTAI (Interfaz de aplicaciones en tiempo real) de Italia se deriva de RT-Linux y su filosofía de diseño es exactamente la misma que la de RT-Linux. Fue diseñado originalmente para resolver el problema de que RT-Linux es difícil de trasplantar entre diferentes versiones de Linux. Para este fin, RTAI define una capa de abstracción de hardware en tiempo real en Linux. Las tareas en tiempo real se llevan a cabo con el sistema Linux. Interfaz proporcionada por esta capa de abstracción interactiva, de modo que el código fuente del kernel de Linux se pueda modificar lo menos posible al agregar soporte en tiempo real al kernel de Linux.

3.2. Kurt-Linux

Kurt-Linux fue desarrollado por la Universidad de Kansas y puede proporcionar precisión en tiempo real a nivel de microsegundos [KurtWeb] [Srinivasan]. A diferencia de RT-Linux, que implementa solo un kernel en tiempo real, Kurt-Linux se implementa sobre la base de un sistema Linux general. También es el primer sistema en tiempo real basado en Linux que puede utilizar llamadas ordinarias al sistema Linux.

Kurt-Linux divide el sistema en tres estados: estado normal, estado en tiempo real y estado mixto. En el estado normal, adopta la estrategia de programación ordinaria de Linux. ejecuta tareas en tiempo real en estado mixto. Se pueden ejecutar tareas en tiempo real y no en tiempo real en situaciones con requisitos estrictos de tiempo real.

Para mejorar las características en tiempo real del sistema Linux, se debe mejorar la precisión del reloj admitida por el sistema. Sin embargo, simplemente aumentar la frecuencia del reloj provocará un aumento en la carga de programación, lo que reducirá seriamente el rendimiento del sistema. Para resolver esta contradicción, Kurt-Linux adopta el método utilizado por UTIME para mejorar la precisión del reloj en los sistemas Linux [UTIMEWeb]: configura el chip del reloj en un estado de disparo único (modo One Shot), es decir, configurando un reloj. chip cada período de tiempo de espera, y luego, cuando se produzca el evento de tiempo de espera, establezca nuevamente un período de tiempo de espera para el chip de reloj según sea necesario en el controlador de interrupciones de reloj. La idea básica es que una sincronización precisa significa que necesitamos que la interrupción del reloj ocurra en un momento relativamente preciso que necesitamos, pero no necesariamente necesitamos que la frecuencia del reloj del sistema alcance esta precisión. Utiliza el contador de reloj de la CPU TSC (Contador de marca de tiempo) para proporcionar precisión de tiempo hasta la frecuencia principal de la CPU.

Para la programación de tareas en tiempo real, Kurt-Linux utiliza un algoritmo estático de programación de CPU en tiempo real basado en el tiempo (TD). Las tareas en tiempo real deben especificar explícitamente cuándo ocurrirán sus eventos en tiempo real durante la fase de diseño. Este algoritmo de programación puede lograr mejores resultados de programación para tareas que se ejecutan cíclicamente.

Una ventaja de Kurt-Linux sobre RT-Linux es que puede usar la llamada del sistema del propio sistema Linux. Fue diseñado originalmente para brindar soporte en tiempo real, pero porque es simple. Implementación Reemplace el programador de Linux con un programador simple basado en el tiempo, de modo que su programación de procesos en tiempo real se vea fácilmente afectada por otras tareas que no son en tiempo real, de modo que en algunos casos no se pueda cumplir con la fecha límite de las tareas en tiempo real. también se le llama sistema estricto en tiempo real (Firm Real-time). Las aplicaciones actuales basadas en Kurt-Linux incluyen: ARTS (ATM Reference Traffic System), software de reproducción multimedia, etc. Además, el método adoptado por Kurt-Linux requiere una programación frecuente del chip del reloj.

3.3.RED-Linux

RED-Linux es un sistema Linux en tiempo real desarrollado por la Universidad de California, Irvine [REDWeb][Wang99]. La programación muy bien con Linux se implementa en el mismo kernel del sistema operativo. Admite tres tipos de algoritmos de programación al mismo tiempo, a saber: basados ​​en tiempo, basados ​​en prioridad y basados ​​en compartir.

Para mejorar la granularidad de programación del sistema, RED-Linux toma prestado el mecanismo de gestión de interrupciones de simulación de software de RT-Linux y aumenta la frecuencia de las interrupciones del reloj. Cuando llega una interrupción de hardware, el programa de simulación de interrupciones de RED-Linux simplemente coloca la interrupción entrante en una cola y no ejecuta el controlador de interrupciones real.

Además, para resolver el problema de que los procesos de Linux no pueden ser reemplazados en el estado del kernel, RED-Linux ha insertado primitivas de puntos de preferencia en muchas funciones del kernel de Linux, de modo que el proceso también pueda ser Se aprovechó hasta cierto punto en el estado del núcleo. De esta forma se mejoran las características en tiempo real del kernel.

El objetivo de diseño de RED-Linux es proporcionar un marco de programación universal que pueda admitir varios algoritmos de programación. El sistema agrega los siguientes atributos a cada tarea y los utiliza como base para la programación de procesos:

Prioridad: la prioridad del trabajo;

Hora de inicio: la hora de inicio del trabajo;

Hora de finalización: la hora de finalización del trabajo

Presupuesto: la cantidad de recursos que utilizará el trabajo durante la operación

Ajustando los valores de estas propiedades y el orden de prioridad en el que el programador usa estos valores de propiedad; , Se puede lograr casi todo Algoritmo de programación. De esta manera, se pueden combinar de manera perfecta y uniforme tres algoritmos de programación diferentes.