Algoritmos de programación del sistema operativo
Un programador de procesos programa diferentes procesos que se asignarán a la CPU en función de algoritmos de programación particulares. Hay seis algoritmos de programación de procesos populares que discutiremos en este capítulo:
- Programación por orden de llegada (FCFS)
- Programación del siguiente trabajo más corto (SJN)
- Programación prioritaria
- Tiempo restante más corto
- Programación de Round Robin (RR)
- Programación de colas de varios niveles
Estos algoritmos son non-preemptive or preemptive. Los algoritmos no preventivos están diseñados para que una vez que un proceso entre en el estado de ejecución, no se pueda adelantar hasta que complete el tiempo asignado, mientras que la programación preventiva se basa en la prioridad donde un programador puede adelantarse a un proceso en ejecución de baja prioridad en cualquier momento cuando haya una prioridad alta. el proceso entra en un estado listo.
Primero llega, primero sirve (FCFS)
- Los trabajos se ejecutan por orden de llegada.
- Es un algoritmo de programación preventivo y no preventivo.
- Fácil de entender e implementar.
- Su implementación se basa en la cola FIFO.
- Deficiente rendimiento debido a que el tiempo medio de espera es elevado.
Wait time de cada proceso es el siguiente:
| Proceso | Tiempo de espera: hora de servicio - hora de llegada |
|---|---|
| P0 | 0-0 = 0 |
| P1 | 5 - 1 = 4 |
| P2 | 8 - 2 = 6 |
| P3 | 16 - 3 = 13 |
Tiempo medio de espera: (0 + 4 + 6 + 13) / 4 = 5,75
Trabajo más corto siguiente (SJN)
Esto también se conoce como shortest job firsto SJF
Este es un algoritmo de programación preventivo y no preventivo.
El mejor enfoque para minimizar el tiempo de espera.
Fácil de implementar en sistemas Batch donde el tiempo de CPU requerido se conoce de antemano.
Imposible de implementar en sistemas interactivos donde no se conoce el tiempo de CPU requerido.
El procesador debe saber de antemano cuánto tiempo llevará el proceso.
Dado: Tabla de procesos, y su Hora de llegada, Hora de ejecución
| Proceso | Hora de llegada | Tiempo de ejecución | Tiempo de servicio |
|---|---|---|---|
| P0 | 0 | 5 | 0 |
| P1 | 1 | 3 | 5 |
| P2 | 2 | 8 | 14 |
| P3 | 3 | 6 | 8 |
Waiting time de cada proceso es el siguiente:
| Proceso | Tiempo de espera |
|---|---|
| P0 | 0-0 = 0 |
| P1 | 5 - 1 = 4 |
| P2 | 14 - 2 = 12 |
| P3 | 8 - 3 = 5 |
Tiempo promedio de espera: (0 + 4 + 12 + 5) / 4 = 21/4 = 5.25
Programación basada en prioridades
La programación de prioridades es un algoritmo no preventivo y uno de los algoritmos de programación más comunes en los sistemas por lotes.
A cada proceso se le asigna una prioridad. El proceso con mayor prioridad se ejecutará primero y así sucesivamente.
Los procesos con la misma prioridad se ejecutan por orden de llegada.
La prioridad se puede decidir en función de los requisitos de memoria, los requisitos de tiempo o cualquier otro requisito de recursos.
Dado: Tabla de procesos, y su hora de llegada, tiempo de ejecución y prioridad. Aquí estamos considerando que 1 es la prioridad más baja.
| Proceso | Hora de llegada | Tiempo de ejecución | Prioridad | Tiempo de servicio |
|---|---|---|---|---|
| P0 | 0 | 5 | 1 | 0 |
| P1 | 1 | 3 | 2 | 11 |
| P2 | 2 | 8 | 1 | 14 |
| P3 | 3 | 6 | 3 | 5 |
Waiting time de cada proceso es el siguiente:
| Proceso | Tiempo de espera |
|---|---|
| P0 | 0-0 = 0 |
| P1 | 11 - 1 = 10 |
| P2 | 14 - 2 = 12 |
| P3 | 5 - 3 = 2 |
Tiempo medio de espera: (0 + 10 + 12 + 2) / 4 = 24/4 = 6
Tiempo restante más corto
El tiempo restante más corto (SRT) es la versión preventiva del algoritmo SJN.
El procesador se asigna al trabajo más cercano a su finalización, pero puede ser reemplazado por un nuevo trabajo listo con un tiempo de finalización más corto.
Imposible de implementar en sistemas interactivos donde no se conoce el tiempo de CPU requerido.
A menudo se utiliza en entornos por lotes donde los trabajos cortos deben dar preferencia.
Programación Round Robin
Round Robin es el algoritmo de programación de procesos preventivos.
Cada proceso tiene un tiempo fijo para ejecutarse, se llama quantum.
Una vez que un proceso se ejecuta durante un período de tiempo determinado, se reemplaza y otro proceso se ejecuta durante un período de tiempo determinado.
La conmutación de contexto se utiliza para guardar estados de procesos apropiadamente.
Wait time de cada proceso es el siguiente:
| Proceso | Tiempo de espera: hora de servicio - hora de llegada |
|---|---|
| P0 | (0 - 0) + (12 - 3) = 9 |
| P1 | (3 - 1) = 2 |
| P2 | (6 - 2) + (14 - 9) + (20 - 17) = 12 |
| P3 | (9 - 3) + (17 - 12) = 11 |
Tiempo promedio de espera: (9 + 2 + 12 + 11) / 4 = 8.5
Programación de colas de varios niveles
Las colas de varios niveles no son un algoritmo de programación independiente. Hacen uso de otros algoritmos existentes para agrupar y programar trabajos con características comunes.
- Se mantienen múltiples colas para procesos con características comunes.
- Cada cola puede tener sus propios algoritmos de programación.
- Se asignan prioridades a cada cola.
Por ejemplo, los trabajos vinculados a la CPU se pueden programar en una cola y todos los trabajos vinculados a E / S en otra cola. Luego, el Programador de procesos selecciona alternativamente trabajos de cada cola y los asigna a la CPU según el algoritmo asignado a la cola.