Relaci´on de Ejercicios de Planificaci´on de Procesos Fundamento de los Computadores, E.T.S.I.T. Sistemas Electr´onicos Curso 2005/2006 Ejercicio 1 En un sistema tenemos cuatro procesos con las siguientes caracter´ısticas: P 1 2 3 4
Llegada 0 0.3 0.5 0.6
Prioridad 2 1 3 2
R´afaga CPU (s) 0.7 0.3 0.4 0.1
Los procesos no hacen E/S. Se pide planificar dichos procesos usando: • Algoritmo FCFS • Algoritmo SJF expropiativo • Algoritmo SJF no expropiativo • Algoritmo por prioridad expropiativo • Algoritmo por prioridad no expropiativo • Algoritmo RR con Q = 0.3 s • Algoritmo RR con Q = 0.4 s En todos los casos calcular el tiempo de retorno medio, el tiempo de retorno de cada proceso, el tiempo de espera medio y el tiempo de espera de cada proceso. En RR asumimos que si un proceso llega a la vez que se cumple un quantum, el proceso que estaba en la CPU se encontrar´a antes en la cola de listos. Ejercicio 2 En un sistema inform´atico con multiprogramaci´on existen dos recursos de E/S (disco y cinta) y dos colas de procesos, una de alta prioridad y otra de baja prioridad. Los procesos cuando llegan al sistema se colocan en la cola de alta prioridad y pasar´an a la de baja prioridad s´olo despu´es de realizar una E/S a cinta. • Las r´afagas de los procesos son como siguen (tiempos en ms): P 1 2 3
Llegada 0 50 70
R´afagas 50, cinta, 60 disco, 10 110, disco, 140 disco, 10 40, cinta, 40, cinta, 10
• La cola de baja prioridad s´olo se atender´a cuando la otra est´e vac´ıa. 1
• La planificaci´on entre colas es expropiativa: un proceso de la cola de baja prioridad puede ser expropiado cuando llegue otro proceso a la cola de alta prioridad pero los procesos de alta prioridad no pueden ser expropiados por los de baja. • Si un proceso es sacado de la CPU por el sistema operativo ir´a a esperar a la cola de alta prioridad. • E/S cinta = 100 ms, E/S disco = 50 ms Se pide: 1. Realizar la planificaci´on de los procesos usando el algoritmo SJF expropiativo para ambas colas. 2. Calcular el rendimiento, el tiempo de retorno medio, el tiempo de espera medio, el tiempo de retorno de cada proceso, el tiempo de espera de cada proceso y el uso de la CPU. Ejercicio 3 La siguiente tabla muestra la informaci´on relativa a cinco procesos: P A B C D E
Llegada 0 10 50 70 80
R´afagas 20, 40, 30, 60, 50 20, 50, 10 50 40, 100, 50, 60, 10 30, 70, 20
Los tiempos est´an dados en ms. La columna de r´afagas indica la duraci´on de las r´afagas de CPU y E/S alternativamente, empezando por CPU. Realizar las planificaciones FCFS, SJF expropiativa y RR (quantum=30). Calcular el tiempo de retorno medio, el tiempo de espera medio, el tiempo de retorno de cada proceso, el tiempo de espera de cada proceso, el uso de CPU y el rendimiento. Ejercicio 4 Uno de los algoritmos de planificaci´on del sistema operativo Linux (para procesos de tiempo compartido) es conocido como “expropiativo justo” y est´a basado en cr´editos. Cada proceso en Linux tiene una prioridad base dada por un entero del 1 al 40 y un n´ umero de cr´editos de planificaci´on. Cuando es necesario seleccionar un proceso para que se ejecute se elige el que m´as cr´editos tenga. Cada vez que transcurre una unidad de tiempo el proceso pierde un cr´edito; cuando sus cr´editos llegan a cero, se saca de la CPU y se escoge otro proceso. Si ning´ un proceso preparado tiene cr´editos se renuevan los cr´editos de todos los procesos del sistema (no s´olo los de la cola de listos) siguiendo la regla cr´editos = (cr´editos/2) + prioridad. Supongamos que en el instante de tiempo t=0 se encuentran en un sistema Linux los procesos de la tabla de abajo. En cada fila se indica la duraci´on de las r´afagas de CPU y de E/S de forma alternada (comenzando por CPU). Adem´as se indica la prioridad de los procesos y sus cr´editos. P A B C
Prioridad 10 5 20
Cr´editos 10 12 3
R´afagas 25, 10, 50, 10 10, 10, 10, 20 10, 10, 40
Realizar la planificaci´on de los procesos y calcular el tiempo de retorno medio, el tiempo de retorno de cada proceso, el tiempo de espera medio y el tiempo de espera de cada proceso. Hacer un ranking de los procesos de acuerdo a los cr´editos m´aximos alcanzados durante la planificaci´on.
2