La programación de procesos generalmente ocurre en las siguientes situaciones:
En la programación no preventiva, después de que un proceso comienza a ejecutarse, siempre se puede ejecutar a menos que renuncie activamente a la CPU o se bloquee. .
En la programación preventiva, si llega un proceso de mayor prioridad durante la ejecución, se le quitará el derecho a usar la CPU, especialmente en la programación por intervalos de tiempo, incluso si el intervalo de tiempo no se utiliza. Sin embargo, la preferencia no puede ocurrir en ningún momento. Si el diseño no es bueno, puede ocurrir una inversión de prioridad o un punto muerto.
En diferentes escenarios, para lograr diferentes objetivos, los criterios para evaluar los algoritmos de programación son diferentes. Aquí presentamos algunos estándares de uso común:
Equidad: brinde a cada proceso una oportunidad justa de usar la CPU.
Equilibrio: Maximizar la utilización de todos los componentes del sistema.
Rendimiento Rendimiento: número de tareas completadas por unidad de tiempo.
Tiempo de respuesta: en términos generales, en un sistema de procesamiento por lotes, el intervalo de tiempo entre el envío y la finalización de una tarea de procesamiento por lotes.
Utilización de CPU: CPU Utilización de CPU.
Tiempo de espera: El tiempo que espera el proceso en la cola de listos.
Tiempo de respuesta: En términos generales, en sistemas interactivos, el tiempo entre que un usuario envía una tarea y obtiene la primera respuesta (la tarea puede no completarse).
Cumplir el plazo: Normalmente, los datos se procesan en sistemas en tiempo real para evitar su pérdida o invalidación.
A continuación, veamos los algoritmos de programación comúnmente utilizados en tres tipos diferentes de sistemas.
1. Por orden de llegada
Este es un algoritmo no preventivo por orden de llegada. Sólo hay una cola de proceso listo. Si el proceso se bloquea durante la ejecución, ingresará a la cola de bloqueo y luego se pondrá en cola como un nuevo proceso hasta el final de la cola lista.
Ventajas: Fácil de entender e implementar.
Desventajas: el tiempo de espera promedio suele ser muy largo, lo que no favorece el equilibrio entre los procesos con uso intensivo de CPU y IO.
2.SJF: el trabajo más corto primero
SJF también es una programación no preventiva, que selecciona la tarea más corta para su ejecución cada vez.
3. Siguiente tiempo restante más corto
Es una versión preventiva de SJF. Cuando llega una nueva tarea, reprogramará y seleccionará la tarea con el tiempo restante más corto.
El problema con SJF y el tiempo mínimo restante es que a menudo es difícil juzgar el tiempo de ejecución restante de un proceso. A menos que se trate de una tarea que deba ejecutarse con frecuencia, el rango aproximado de tiempo de ejecución se puede determinar en función del análisis estadístico histórico.
1. Programación circular
Programación de sondeos. Asigne a cada proceso el mismo intervalo de tiempo y ejecútelo secuencialmente. El intervalo de tiempo es generalmente de 20 a 50 ms. Si es demasiado corto, el cambio de proceso perderá tiempo y si es demasiado largo, el tiempo de respuesta se prolongará.
Ventajas: Respuesta más rápida que SJF
Desventajas: Tiempo de respuesta prolongado.
2. Programación de prioridades
La programación de prioridades asigna una prioridad a cada proceso. La prioridad alta se ejecuta primero. También es un algoritmo de programación de intervalos de tiempo. Las prioridades se pueden asignar de forma estática o dinámica. Para evitar que los procesos de alta prioridad ocupen la CPU todo el tiempo, se pueden reducir después de la ejecución secuencial. Se pueden usar otros algoritmos de programación, como la programación por turnos, entre procesos con la misma prioridad, y se pueden usar diferentes algoritmos de programación para diferentes colas.
Ventajas: Introducción prioritaria.
3. Múltiples colas
Para evitar cambios frecuentes de procesos con tiempos de ejecución prolongados, se pueden asignar intervalos de tiempo de diferentes longitudes entre diferentes colas de prioridad. Después de que un proceso se ejecuta una vez, se le asignan otras prioridades que tardan más en ejecutarse. Por ejemplo, si un proceso requiere 100 rangos, se asignará 1 para la primera ejecución, 2 para la siguiente ejecución y 4, 8, 16, 32 y 64 para la siguiente ejecución. En comparación con el algoritmo de sondeo puro que solo asigna 1 a la vez, se reduce la cantidad de programación de procesos.
4. Programación garantizada
Ninguno de los algoritmos mencionados anteriormente puede garantizar el tiempo de CPU que puede obtener el proceso, pero en algunos casos, necesitamos garantizar la oportunidad y el tiempo para la realización. proceso para utilizar la CPU.
Por ejemplo, si n usuarios inician sesión al mismo tiempo, generalmente es necesario asegurarse de que cada usuario pueda obtener 1/n CPU, o podemos comprar un servicio VPN para obtener ciertas garantías de ancho de banda según los diferentes niveles de usuario. Este algoritmo se llama programación garantizada. En la implementación, es necesario realizar un seguimiento de la CPU asignada a cada proceso. El proceso con la proporción más pequeña en comparación con la asignación comprometida obtiene el siguiente uso correcto.
5. Momento de la lotería
El algoritmo de programación de la lotería introduce aleatoriedad y emite un billete de lotería para cada proceso. La programación es como una lotería, quien gana la lotería obtiene los recursos. Los procesos con mayor prioridad pueden obtener múltiples billetes de lotería, aumentando las posibilidades de ganar.
Lo interesante de la programación de lotería es que los procesos pueden darse billetes de lotería entre sí. Por ejemplo, el proceso 1 está pendiente del proceso 2, puede entregar todos sus tickets al proceso 2 para mejorar sus posibilidades de ser programado. Devuelva la lotería al proceso1 después del proceso2.
6. Programación de reparto justo
Consideremos una situación en la que todos los procesos no pertenecen a un solo usuario, lo cual es muy común en los sistemas Linux. Si el usuario1 tiene 99 procesos y el usuario2 tiene solo 1 proceso, según el algoritmo anterior, el usuario1 puede obtener el 99% de la CPU, mientras que el usuario2 solo tiene el 1%. Para lograr equidad a nivel de usuario, es necesario considerar a qué usuario pertenece el proceso al programar.
Hay dos tipos de sistemas en tiempo real:
En los sistemas en tiempo real, los tiempos de las tareas son generalmente más cortos y el programador debe asegurarse de que todos los procesos se completen antes de la fecha límite. Para eventos que ocurren periódicamente, si el ciclo del evento es , entonces el tiempo de procesamiento del evento (el tiempo requerido para ocupar la CPU) es , y solo de esta manera se puede programar.
¿Los algoritmos de programación solo pueden ser implementados por el sistema operativo? ¿Tiene el proceso derecho a decir qué algoritmo de programación utilizar? La respuesta es sí. Los mecanismos y las estrategias están separados. El sistema operativo proporciona múltiples mecanismos de implementación y llamadas al sistema. El proceso pasa parámetros al sistema operativo para especificar qué estrategia de programación utilizar.
Si los subprocesos se implementan en modo de usuario, entonces se requiere una programación de dos niveles. El sistema operativo es responsable de programar los procesos y los procesos son responsables de programar los subprocesos. Si los subprocesos se implementan en modo kernel, el sistema operativo programa el subproceso directamente, independientemente del proceso al que pertenezca.