Algoritmos de Planificación

Vista previa del material en texto

INTRODUCCIÓN
Los algoritmos de planificación son herramientas fundamentales en el campo de la informática y la inteligencia artificial. Estos algoritmos permiten la organización y secuenciación de tareas o acciones con la finalidad de lograr un objetivo específico de manera eficiente. Estos algoritmos se utilizan ampliamente en diferentes plataformas, como Android, macOS y Linux, para asegurar un uso equitativo y óptimo de los recursos del sistema. En un sistema operativo, el algoritmo de planificación se encarga de tomar decisiones sobre qué tarea o proceso se ejecutará y durante cuánto tiempo, con el objetivo de optimizar la utilización de la CPU y otros recursos del sistema. El sistema operativo asigna recursos de la CPU a cada tarea en función de su prioridad, asegurando así una ejecución eficiente y equitativa de las aplicaciones en el dispositivo. Por otro lado, macOS, el sistema operativo utilizado en los dispositivos Apple, utiliza un algoritmo de planificación llamado "planificación en tiempo real de prioridades fijas". En el caso de Linux, un sistema operativo de código abierto ampliamente utilizado, existen diferentes algoritmos de planificación disponibles, cada uno diseñado para satisfacer necesidades específicas. Algunos de los algoritmos de planificación más comunes en Linux son el algoritmo de planificación de lotería, el algoritmo de planificación en tiempo real y el algoritmo de planificación por prioridad.
ÍNDICE
Planificación por prioridad.	4
Cómo funcionan los algoritmos en Windows	7
Como funcionan los algoritmos en Android	8
Cómo funcionan los algoritmos en Mac OS	9
Cómo funcionan los algoritmos en Linux	10
Cómo funciona un algoritmo FCFS	11
Cómo funciona en Linux	11
Conclusión:	12
Bibliografía	13
Planificación por prioridad.
El algoritmo de planificación de procesos "Primero el trabajo más corto" (SJF) asume que los tiempos de ejecución de los procesos se conocen de antemano. Shortest Job First es un algoritmo el cuál cuando un proceso se encuentra en ejecución, cambia voluntariamente de estado ya que el tiempo de ejecución del proceso no es determinado, por esto cada proceso tiene una asignación de tiempo cada que vuelve a ser ejecutado y así mismo ejecutando el proceso con menor cantidad de tiempo asignado. Mantiene dos esquemas: 
Apropiativo 
Tiempo de espera promedio = ((0 + ( 11-2 )) + ( 0 + (5 – 4)) + (0) + (7 – 5))/4 = (9+1+0+2)/4 = 3
Tiempo de entrega promedio = (16 + (7 - 2) + (5 - 4) + ( 11-5))/4 = (16 + 5 + 1 + 6)/4 = 7 
No apropiativo
En la siguiente tabla se presentan cuatro procesos: Word, Excel, Paint y Calculadora. Cada proceso requiere una ráfaga de CPU para completar su ejecución, que se representa en unidades de tiempo como segundos, milisegundos o nanosegundos. Se muestra el tiempo de llegada de cada proceso, que indica cuándo se hace disponible para su ejecución en el sistema operativo.
El orden de ejecución no es el mismo porque el algoritmo prioriza es ráfaga de CPU el más corto, el primer proceso que se ejecuta es Word, segundo la calculadora, tercero Paint y por último el programa Excel tomando las unidades de tiempo de ráfaga de CPU que se requieren para que el proceso se ejecute completamente. En caso de empate se ejecuta el proceso que llegue primero. 
Para calcular el tiempo del sistema del ejercicio anterior vamos a hacer uso de la siguiente formula: 
Tiempo del sistema = tiempo de salida – tiempo de llegada 
Para nuestro caso los resultados quedan de la siguiente forma:
	Word
	Excel
	Paint
	Calculadora
	8-0=8
	18-4=14
	14-2=12
	10-6=4
Tiempo de espera: tiempo de ejecución – Tiempo de llegada
Tiempo de ejecución: es el tiempo cuando se empieza a ejecutar el proceso, y tiempo de llegada es el momento en que llega el proceso. Resultado de nuestro caso: 
	Word
	Excel
	Paint
	Calculadora
	0-0=0
	14-4=10
	10-2=8
	8-6=2
Otro ejemplo puede ser el siguiente: Da bastante prioridad a los procesos más cortos a la hora de ejecución y los coloca en la cola.
Cómo funcionan los algoritmos en Windows
Por lo general en Windows se utiliza una política de planificación: Round Robin. La desventaja principal es que cambia los procesos en ejecución con demasiada frecuencia. Lo que supone una pequeña pérdida de tiempo.
En el algoritmo de Round Robin cada proceso tiene asignado un intervalo de tiempo de ejecución, llamado quantum o cuánto. Si el proceso agota su quantum de tiempo, se elige a otro proceso para ocupar la CPU. Si el proceso se bloquea o termina antes de agotar su quantum también se alterna el uso de la CPU. La cola de procesos se estructura como una cola circular. La organización de la cola es FIFO.
Ejemplo práctico: 
	PROCESO
	LLEGADA
	DURACIÓN
	P1
	0
	5
	P2
	4
	2
	P3
	1
	7
	P4
	2
	1
	P5
	3
	8
Como funcionan los algoritmos en Android
En Android, el sistema utiliza un algoritmo de planificación de procesos basado en prioridades para gestionar la ejecución de tareas en la CPU. A cada proceso se le asigna un numero entero de prioridad, donde un valor menor indica una mayor prioridad. El objetivo es planificar la entrada de procesos directamente a la CPU de acuerdo con la prioridad asociada a cada una. El algoritmo de planificación utilizado en Android es conocido como Round Robin con prioridad. Lo cual significa que se sigue una política de rotación, donde cada proceso tiene un intervalo de tiempo fijo para poder ejecutarse en la CPU. Sin embargo, la prioridad de los procesos determina el orden en el que se les otorga la CPU. 
El sistema mantiene una lista ordenada pseudo-LRU (Last recently used) de procesos que nos ayuda a evitar que algunos procesos se apoderen de los recursos. Esta lista está organizada según las prioridades asignadas a cada proceso. Además de la prioridad de un proceso puede aumentar si es un subproceso de mayor prioridad. Ejemplo, si un conjunto de procesos esta interdependiente la prioridad de todo el conjunto se igualara a la prioridad del componente que sea más prioritario del conjunto.
Cuando un proceso entra en un estado de espera o finalización, se almacena en cache en zRAM. Esto se hace para poder acelerar su carga en la RAM si se vuelve a solicitar más adelante.
Estado de un proceso en Android 
 
En Android, se asigna prioridad a los procesos según la jerarquía de importancia. La jerarquía de estados de proceso en Android incluye.
Procesos en primer plano (Active process): Es la aplicación que contiene la actividad ejecutada en primer plano. 
Procesos visibles (Visible process): Es un proceso que aloja una actividad que no se está ejecutando en primer plano. 
Procesos de servicio (Started service process): Son aquellos que ocurren cuando un servicio ha sido invocado. Estos procesos no son visibles, hacen cosas en segundo plano que normalmente son importantes para el usuario (conexión de servidores, actualización del GPS, reproductor música).
Procesos en segundo plano (background process): Es un proceso que contiene una actividad que actualmente no es visible por el usuario y que ya no tienen demasiada importancia. 
Procesos vacíos (Empty process): Es un proceso que no aloja ningún tipo de componente. Su razón de ser es el de tener una cache disponible para la próxima aplicación que lance el usuario. 
Cómo funcionan los algoritmos en Mac OS
En Mac OS, la gestión de procesos es realizada mediante el uso de varias colas de procesos, cada una con un nivel de prioridad diferente. Estas colas nos permiten organizar y planificar la ejecución de los procesos en el sistema operativo. Un hilo de un proceso puede pasar de una cola a otra según los requerimientos y prioridades establecidas. Los niveles de prioridad que se utilizan en Mac OS son: normal, alta, kernel y tiempo real.
La prioridad de un proceso para poder acceder al procesador se determina mediante varios factores. En primer lugar, se asigna una prioridad base al proceso. Además, se considera el tiempo de CPU que el proceso ha utilizado previamente y el tiempo que ha pasado en cola esperandosu turno a ejecutarse. A medida que un proceso reciba tiempo de procesador, su prioridad disminuye.
El algún caso, un proceso que puede reducir significativamente su prioridad, lo que significa que el procesador tardara más en volver a tomarlo para su ejecución. Esto suele ocurrir cuando un proceso ha pasado mucho tiempo en cola de espera. Sim embargo a medida que un proceso pasa más tiempo en cola, la prioridad de este aumenta gradualmente. Esto permite que los procesos que han estado esperando durante mucho tiempo tengan la oportunidad de ejecutarse.
Sin embargo, en situaciones en las que el sistema tiene una alta carga de trabajo y todos los procesos reciben muy poco tiempo de procesador, la prioridad de los procesos puede aumentar significativamente. Esto puede afectar negativamente la respuesta general del sistema operativo, ya que los procesos de alta prioridad pueden dominar la ejecución y otros procesos pueden experimentar retrasos.
Para abordar este problema, al calcular la prioridad de un proceso, se tiene en cuenta la carga actual del procesador. Esto asegura que las prioridades no crezcan descontroladamente debido a la carga de trabajo del sistema. Este busca mantener un equilibrio en la asignación de tiempo de procesador para garantizar un rendimiento optimo del sistema operativos.
Cómo funcionan los algoritmos en Linux
Las clases de planificación de Linux son las siguientes:
SCHED_RR: Se comportan igual que en el caso anterior, salvo que cuando se les acaba el quantum ceden el procesador voluntariamente a otros procesos de tiempo real con la misma prioridad (Se colocan al final de la "cola" de su prioridad).
Planificación de procesos en Linux
· Dos algoritmos: tiempo compartido y tiempo real
· Tiempo compartido
· Prioridad basada en créditos: El proceso con más créditos se despacha.
· Se restan los créditos cuando suceden interrupciones de temporizador.
· Cuando el crédito = 0 se elige otro proceso.
· Cuando todos los procesos tienen crédito = 0 se re acreditan (Cr=Cr/2+Pr).
o Con base en factores como prioridad e historia.
· Tiempo real
· Tiempo real blando.
· Cumple con POSIX.1b – de dos clases.
· FCFS y RR.
· El proceso de mayor prioridad siempre se ejecuta primero.
A continuación, se realiza un ejemplo con el algoritmo
Cómo funciona un algoritmo FCFS
Supongamos que hay tres solicitudes para procesar en la cola de la CPU: P1, P2 y P3, suponiendo que P1 es un proceso complejo que requiere aproximadamente 25 segundos, P2 una solicitud mucho más simple que requiere solo 10 segundos de procesamiento y P3 una solicitud moderadamente simple que requiere 15 segundos.
Cuando P1 se coloca por primera vez en la cola, el tiempo de espera es cero y la CPU inicia el procesamiento de inmediato. P2, por otro lado, tendría un tiempo de espera de 25 segundos. Y P3, al haber llegado el último, tendría que esperar 35 segundos. En total, un algoritmo de programación FCFS necesitaría 50 segundos para completar las tres solicitudes y vaciar la cola, lo que sería lo mismo que otros sistemas mono-CPU de procesamiento secuencial.
Debido a que FCFS no evalúa las solicitudes antes de comenzar, tiene menos tareas completas por período de tiempo establecido en comparación con un algoritmo de programación inteligente. En este escenario, el algoritmo de programación FCFS completaría una sola tarea en la primera mitad de su tiempo de ejecución de 25 segundos. Otros algoritmos, que comienzan con las solicitudes más simples, por ejemplo, habrían terminado dos solicitudes.
Cómo funciona en Linux
Consiste en que a cada proceso se le asigna un intervalo de tiempo, conocido como quantum (q), durante el cual el proceso puede ejecutarse, si al proceso le falta tiempo para ejecutarse se coloca de nuevo al final de la cola de listos, es decir los procesos se ejecutan en orden del algoritmo FIFO, pero solo se le permite utilizar la CPU el tiempo del quantum.
A continuación, se realiza un ejemplo con el algoritmo RR, considerando un q = 3.
Conclusión:
El proyecto que realizamos se ha contribuido de manera muy importante para identificar y
resaltar los puntos que hay que cubrir y considerar, para llevar a cabo una implementación
exitosa de los sistemas de información. 
Dentro de los puntos que consideramos en nuestro proyecto es de que los sistemas operativos como Windows, Linux, macOS y Android se basan en una variedad de algoritmos seleccionados para brindar una funcionalidad eficiente y segura a los usuarios. Estos algoritmos abarcan áreas como la planificación de procesos, la gestión de memoria, los sistemas de archivos y la seguridad. Gracias a estos algoritmos, los sistemas operativos pueden proporcionar una experiencia de uso fluida, optimizar el rendimiento y salvaguardar la integridad de los datos.
Bibliografía
Calidonio, R. A. (13 de Octubre de 2017). Blog Sistemas Operativos II. Obtenido de https://sistemasoperativosunah.wordpress.com
Carreres, J. (5 de Octubre de 2015). JoseCarreres. Obtenido de https://josecarreres.wordpress.com/2015/10/05/planificacion-y-procesos-en-windows-y- linux/
Castaño, F. J. (29 de Noviembre de 2011). infoMacOS. Obtenido de http://infosmac- os.blogspot.com/p/gestion-de-procesos.html
Dister, G. (2020). Obtenido de https://cs.uns.edu.ar/~gd/soyd/clasesgus/05- PlanificacióndeCPU.pdf
Ivan, E. (5 de Octubre de 2015). PortfolioWordpress. Obtenido de https://ivanlopezjorda.wordpress.com/2015/10/05/planificacion-de-procesos-windows-y- linux/
Lafuente, A. (13 de Junio de 2023). OpenCourseWare.
Perez, J. C., & Saenz, S. (13 de Junio de 2023). Upv. Obtenido de http://sop.upv.es/gii-dso/es/t7- 1-gestion-de-procesos/gen-t7-1-gestion-de-procesos.html
Rouse, M. (14 de Marzo de 2022). Techopedia. Obtenido de https://www.techopedia.com/definition/23455/first-come-first-served- fcfs#:~:text=14%20March%2C%202022-
,What%20Does%20First%20Come%2C%20First%20Served%20Mean%3F,the%20order
%20of%20their%20arrival