En este tutorial, aprenderemos un concepto importante en los algoritmos de programación de procesos de CPU. El nombre del concepto importante es 'Por orden de llegada'. Este es el algoritmo básico que todo estudiante debe aprender para comprender todos los conceptos básicos de los algoritmos de programación de procesos de la CPU.
First Come First Serve allana el camino para la comprensión de otros algoritmos. Este algoritmo puede tener muchas desventajas. Pero estas desventajas crearon algoritmos muy nuevos y eficientes. Por lo tanto, es nuestra responsabilidad aprender sobre los algoritmos de programación de procesos de CPU por orden de llegada.
Abreviaturas importantes
- CPU - - - > Unidad Central de Procesamiento
- FCFS - - - > Por orden de llegada
- A - - - > Hora de llegada
- BT - - - > Tiempo de ráfaga
- Peso - - - > Tiempo de espera
- TAT - - - > Tiempo de vuelta
- CT - - - > Tiempo de finalización
- FIFO - - - > Primero en entrar, primero en salir
Se le sirve en orden de llegada
El algoritmo de programación de CPU por orden de llegada, conocido brevemente como FCFS, es el primer algoritmo del algoritmo de programación de procesos de CPU. En el algoritmo 'primero en llegar, primero en servir', lo que hacemos es permitir que el proceso se ejecute de manera lineal.
Esto significa que el proceso que ingresa primero a la cola de listo se ejecuta primero. Esto muestra que el algoritmo por orden de llegada sigue el principio de primero en entrar, primero en salir (FIFO).
El algoritmo por orden de llegada se puede ejecutar de forma preventiva y no preventiva. Antes de entrar en ejemplos, comprendamos qué es el enfoque preventivo y no preventivo en la programación de procesos de CPU.
Enfoque preventivo
En este caso de programación preventiva de procesos, el sistema operativo asigna los recursos a un proceso durante un período de tiempo predeterminado. El proceso pasa del estado en ejecución al estado listo o del estado en espera al estado listo durante la asignación de recursos. Este cambio ocurre porque la CPU puede asignar prioridad a otros procesos y sustituir el proceso actualmente activo por el proceso de mayor prioridad.
Enfoque no preventivo
En este caso de programación de procesos no preventiva, el recurso no se puede retirar de un proceso antes de que el proceso haya terminado de ejecutarse. Cuando un proceso en ejecución finaliza y pasa al estado de espera, los recursos se cambian.
Efecto convoy en orden de llegada (FCFS)
El efecto convoy es un fenómeno que ocurre en el algoritmo de programación denominado First Come First Serve (FCFS). El algoritmo de programación por orden de llegada se produce de forma no preventiva.
La forma no preventiva significa que si se inicia la ejecución de un proceso o trabajo, entonces el sistema operativo debe completar su proceso o trabajo. Hasta que el proceso o trabajo sea cero, el proceso o trabajo nuevo o siguiente no comienza su ejecución. La definición de programación no preventiva en términos de sistema operativo significa que la unidad central de procesamiento (CPU) estará completamente dedicada hasta el final del proceso o trabajo iniciado primero y el nuevo proceso o trabajo se ejecutará solo después de finalizar el proceso o trabajo anterior. trabajo.
Puede haber algunos casos que puedan hacer que la Unidad Central de Procesamiento (CPU) dedique demasiado tiempo. Esto se debe a que en el enfoque no preventivo del algoritmo de programación por orden de llegada, los procesos o los trabajos se eligen en orden en serie. Debido a esto, los trabajos o procesos más cortos detrás de los procesos o trabajos más grandes toman demasiado tiempo para completar su ejecución. Debido a esto, el tiempo de espera, el tiempo de entrega y el tiempo de finalización son muy altos.
Entonces, aquí, como el primer proceso es grande o el tiempo de finalización es demasiado alto, se produce este efecto de convoy en el algoritmo por orden de llegada.
Supongamos que Longer Job tarda un tiempo infinito en completarse. Luego, los procesos restantes tienen que esperar el mismo tiempo infinito. Debido a este efecto de convoy creado por el trabajo más largo, la inanición de los procesos de espera aumenta muy rápidamente. Esta es la mayor desventaja de la programación de procesos de CPU FCFS.
Características de la programación de procesos de CPU FCFS
Las características de la programación de procesos de CPU FCFS son:
- La implementación es sencilla.
- No causa ninguna causalidad durante el uso.
- Adopta una estrategia preventiva y no preventiva.
- Ejecuta cada procedimiento en el orden en que se reciben.
- La hora de llegada se utiliza como criterio de selección de los trámites.
Ventajas de la programación de procesos de CPU FCFS
Las ventajas de la programación de procesos de CPU FCFS son:
- Para asignar procesos, utiliza la cola Primero en entrar, primero en salir.
- El proceso de programación de CPU FCFS es sencillo y fácil de implementar.
- En la situación FCFS de programación preventiva, no hay posibilidad de que el proceso se detenga.
- Como no se considera la prioridad del proceso, es un algoritmo equitativo.
Desventajas de la programación de procesos de CPU FCFS
Las desventajas de la programación de procesos de CPU FCFS son:
- El algoritmo de programación de CPU FCFS tiene un largo tiempo de espera
- La programación de CPU FCFS favorece la CPU sobre las operaciones de entrada o salida
- En FCFS existe la posibilidad de que se produzca el efecto Convoy.
- Debido a que FCFS es tan sencillo, a menudo no es muy efectivo. Esto va acompañado de largos períodos de espera. Todas las demás órdenes quedan inactivas si la CPU está ocupada procesando una orden que requiere mucho tiempo.
Problemas en el algoritmo de programación de CPU por orden de llegada
Ejemplo
S. No Process ID Process Name Arrival Time Burst Time _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 P 1 A 0 9 2 P 2 B 1 3 3 P 3 C 1 2 4 P 4 D 1 4 5 P 5 E 2 3 6 P 6 F 3 2
Enfoque no preventivo
Ahora, resolvamos este problema con la ayuda del algoritmo de programación denominado 'primero en llegar, primero en servir' en un enfoque no preventivo.
El diagrama de Gantt para el ejemplo 1 anterior es:
Tiempo de vuelta = Tiempo de finalización - Hora de llegada
Tiempo de espera = tiempo de respuesta - tiempo de ráfaga
Solución a la pregunta anterior Ejemplo 1
S. No | Identificacion de proceso | Hora de llegada | Tiempo quemado | Tiempo de finalización | Tiempo de vuelta | Tiempo de espera | |
---|---|---|---|---|---|---|---|
1 | P 1 | A | 0 | 9 | 9 | 9 | 0 |
2 | P 2 | B | 1 | 3 | 12 | 11 | 8 |
3 | P 3 | C | 1 | 2 | 14 | 13 | 11 |
4 | P 4 | D | 1 | 4 | 18 | 17 | 13 |
5 | P 5 | Y | 2 | 3 | 21 | 19 | 16 |
6 | P 6 | F | 3 | 2 | 23 | 20 | 18 |
El tiempo promedio de finalización es:
CT promedio = ( 9 + 12 + 14 + 18 + 21 + 23 ) / 6
TC promedio = 97/6
CT promedio = 16.16667
El tiempo promedio de espera es:
comando de retorno java
Peso promedio = ( 0 + 8 + 11 + 13 + 16 + 18 ) /6
Peso promedio = 66/6
Peso promedio = 11
El tiempo promedio de respuesta es:
TAT promedio = ( 9 + 11 + 13 + 17 + 19 +20 ) / 6
TAT promedio = 89/6
TAT promedio = 14,83334
Así se resuelve el FCFS en el Enfoque No Preemptivo.
Ahora, comprendamos cómo se pueden resolver en el enfoque preventivo.
Enfoque preventivo
Ahora, resolvamos este problema con la ayuda del algoritmo de programación denominado 'Primero en llegar, primero en servir', en un enfoque preventivo.
En Pre Emptive Approach buscamos el mejor proceso disponible
El diagrama de Gantt para el ejemplo 1 anterior es:
S. No | Identificacion de proceso | Hora de llegada | Tiempo quemado | Tiempo de finalización | Tiempo de vuelta | Tiempo de espera | |
---|---|---|---|---|---|---|---|
1 | P 1 | A | 0 | 9 | 23 | 23 | 14 |
2 | P 2 | B | 1 | 3 | 8 | 7 | 4 |
3 | P 3 | C | 1 | 2 | 3 | 2 | 0 |
4 | P 4 | D | 1 | 4 | 15 | 14 | 10 |
5 | P 5 | Y | 2 | 3 | 11 | 9 | 7 |
6 | P 6 | F | 3 | 2 | 5 | 2 | 0 |
siguiente → ← anterior Para solucionar el problema del desperdicio de señales de despertador, Dijkstra propuso un método que implica almacenar todas las llamadas de despertador. Dijkstra afirma que, en lugar de dar las llamadas de atención directamente al consumidor, el productor puede almacenar las llamadas de atención en una variable. Cualquiera de los consumidores puede leerlo cuando lo necesite. El semáforo son las variables que almacenan todas las llamadas de atención que se transfieren del productor al consumidor. Es una variable cuya lectura, modificación y actualización se realizan automáticamente en modo kernel. El semáforo no se puede implementar en el modo de usuario porque siempre puede surgir una condición de carrera cuando dos o más procesos intentan acceder a la variable simultáneamente. Siempre necesita soporte del sistema operativo para ser implementado. Según la demanda de la situación, Semaphore se puede dividir en dos categorías.
Discutiremos cada uno en detalle. |