Análisis de varios algoritmos de programación de procesos

Cuando estaba haciendo la tarea del sistema operativo hace dos días, aprendí varios algoritmos de programación de procesos. Después de pensar y discutir, se me ocurrieron algunas ideas que ahora escribiré y discutiré con ellas. tú. , o que solo hay recursos de CPU limitados. Cuando varios procesos en el sistema están listos y quieren competir por los recursos de la CPU, el sistema operativo es responsable de completar la tarea de asignar recursos. En el sistema operativo, el programador completa este trabajo de selección y asignación, y el algoritmo utilizado por el programador es el algoritmo de programación. Los principales indicadores que deben considerarse en el algoritmo de programación son intentar garantizar la equidad en la asignación de recursos de la CPU; hacer cumplir la programación del algoritmo de acuerdo con ciertas políticas para equilibrar todo el sistema informático y tratar de mantener todas las partes ocupadas; Según las diferentes características y requisitos de los sistemas, los algoritmos de programación tienen diferentes enfoques y objetivos. Por lo tanto, los algoritmos se dividen principalmente en tres categorías según las diferencias del sistema: Algoritmos de programación en sistemas de procesamiento por lotes, los algoritmos de programación representativos son: primero en llegar. , Servicio por orden de llegada, primero el trabajo más corto, primero el tiempo restante más corto. Algoritmos de programación en sistemas interactivos, los algoritmos de programación representativos incluyen: programación por turnos, programación por prioridad, cola de varios niveles, proceso más corto primero, programación garantizada, programación por lotería, programación de participación justa. Algoritmos de programación en sistemas en tiempo real, los algoritmos de programación representativos incluyen: programación monotónica de velocidad y programación de prioridad de tiempo final más temprana. Centrémonos en analizar algunos de los algoritmos de programación mencionados anteriormente: Programación garantizada La programación garantizada se refiere al uso de algoritmos para dejar claras las garantías de rendimiento a los usuarios y luego hacer todo lo posible para lograr la asignación de recursos de CPU de acuerdo con esta garantía. El uso de este algoritmo es establecer un estándar para el tiempo que un proceso ocupa la CPU y luego comparar el tiempo real ocupado por la CPU de acuerdo con este estándar. El proceso de programación permite que el proceso más alejado de este estándar obtenga recursos cada vez y de forma continua. cumple con el estándar garantizado El proceso más avanzado, equilibrando así la asignación de recursos para cumplir con los requisitos de este criterio. La ventaja del algoritmo de programación garantizada es que puede garantizar una participación justa de CPU del proceso cuando el sistema se caracteriza por: no hay mucha diferencia en la prioridad del proceso, los estándares de garantía establecidos no son muy diferentes y los requisitos de CPU de cada proceso son relativamente cercanos. Por ejemplo, si el sistema requiere que cada proceso entre n procesos solo ocupe 1/n de los recursos de la CPU, la programación garantizada puede lograr fácilmente requisitos de asignación de CPU estables. Pero la desventaja es que esta situación es demasiado ideal. Cuando la urgencia de los requisitos de CPU de cada proceso en el sistema es diferente y las garantías son más complejas, este algoritmo es más difícil de implementar. Programación de lotería La programación de lotería es un algoritmo que proporciona boletos de lotería con varios recursos del sistema, como recursos de CPU, al proceso. Cuando el sistema necesita tomar una decisión de programación, se selecciona un boleto de lotería al azar y el propietario del boleto de lotería obtiene los recursos. . En el sistema de programación de lotería, si aparece un nuevo proceso y obtiene algunos billetes de lotería, en la siguiente lotería el proceso tendrá posibilidades de ganar una recompensa proporcional a la cantidad de billetes de lotería que tenga. Cuantos más billetes de lotería tenga un proceso, mayores serán las posibilidades de resultar sorteado. El planificador puede programar controlando el número de billetes de lotería que tiene el proceso. La programación de lotería tiene muchas ventajas: en primer lugar, es muy flexible. Cuando el sistema aumenta la cantidad de boletos asignados a un determinado proceso, aumentará en gran medida la posibilidad de que ocupe recursos. Se puede decir que la respuesta de la programación de lotería. es rápido y la demanda de una respuesta rápida es un requisito importante para los sistemas interactivos. En segundo lugar, en el algoritmo de programación de lotería, los procesos pueden intercambiar billetes de lotería. Esta característica puede garantizar mejor el equilibrio del sistema y hacer que todas las partes estén lo más ocupadas posible. Además, la programación de la lotería también puede resolver muchos problemas que son difíciles de resolver con otros algoritmos. Por ejemplo, el uso de la CPU se puede dividir aproximadamente en proporción a las necesidades específicas. Programación monotónica de tasa El algoritmo de programación monotónica de tasa es un algoritmo de programación estático en tiempo real clásico aplicable a procesos periódicos interrumpibles. Cuando los procesos en un sistema en tiempo real satisfacen: cada proceso periódico debe completarse dentro de su período y no hay interdependencia entre procesos, cada proceso requiere la misma cantidad de tiempo de CPU en una ráfaga y los procesos no periódicos cuando hay sin límite de tiempo final y cuatro condiciones, y para la conveniencia del modelado, asumimos que la preferencia del proceso ocurre inmediatamente sin sobrecarga del sistema, y ​​se puede considerar el algoritmo de tasa monótona.

El algoritmo de programación de tasa monótona asigna la tasa del proceso (el número de respuestas por segundo calculadas de acuerdo con el ciclo del proceso) como prioridad, lo que garantiza que la prioridad esté relacionada linealmente con la tasa del proceso. Esto es lo que llamamos tasa monótona. El programador ejecuta el que tiene la mayor prioridad cada vez, siempre que sea necesario ejecutar el programa de mayor prioridad, inmediatamente se adelantará al proceso de menor prioridad, y el proceso de menor prioridad debe esperar a todos los procesos con una prioridad mayor. que termine antes de que pueda ejecutarse. El algoritmo de programación monotónica de velocidad puede garantizar que las tareas más críticas del sistema siempre estén programadas. Sin embargo, la desventaja es que, como algoritmo estático, no es lo suficientemente flexible. Cuando aumenta el número de procesos y la programación del sistema se vuelve compleja. Es posible que no pueda funcionar bien. Asegúrese de que el proceso se ejecute dentro del ciclo. El algoritmo de programación de la primera fecha límite final más temprana es un algoritmo dinámico que no requiere que el proceso sea periódico. Siempre que un proceso necesite tiempo de CPU, anuncia su hora de llegada y su fecha límite final. El programador mantiene una lista de procesos ejecutables, ordenados por fecha límite final, y programa un proceso con la fecha límite final más temprana para obtener la CPU cada vez. Cuando un nuevo proceso está listo, el sistema verifica si su fecha límite es anterior al final del proceso actualmente en ejecución y, de ser así, adelanta el proceso actual. Debido a que es un algoritmo dinámico, la ventaja de la programación de prioridad final más temprana es la flexibilidad. Cuando el número de procesos no excede la carga, la asignación de recursos es mejor. Pero también debido a sus atributos dinámicos, la prioridad del proceso cambia constantemente. por lo que tampoco se garantiza que ningún proceso cumpla con el cronograma. Cuando el número de procesos excede la carga, la racionalidad de la asignación de recursos disminuirá rápidamente, por lo que es inestable.