1
Indice
Objetivos de planificación
Algoritmos de planificación
Detección y prevención de bloqueos
2
Objetivos de planificación
El S.O debe decidir qué proceso ejecutar de aquellos que están listos para ejecución
Planificador (scheduler): parte del S.O que realiza la decisión mediante el algoritmo de planificación
Objetivos:
Equidad
Eficiencia
Tiempo de respuesta
Minimizar tiempo de proceso global
Maximizar el nº de trabajos procesados
Pueden ser contradictorios
3
Planificación
Problema:
el comportamiento de los procesos es único e impredecible
Mucha E/S
Mucho cálculo
Para asegurar que un proceso no monopoliza el procesador
Temporizador hardware
Con cada interrupción el S.O toma el control y decide si seguir con el proceso actual o pasar a otro
Se pueden utilizar distintos algoritmos de planificación.
4
Algoritmos de planificación
Planificación por turno rotatorio
Planificación por prioridad
Lista de espera múltiples
Prioridad al más corto
Planificación determinada por el comportamiento
Planificación a dos niveles
5
Planificación por turno rotatorio
A cada proceso se le asigna un intervalo de tiempo o cuanto
Cambio de contexto lleva tiempo
Si 5 ms, el tiempo utilizado en el cambio:
Si cuanto de 20 ms => 20%
Si cuanto de 500 ms => 1%
Si 10 procesos, 1/2 s, 1 s . en empezar.
Compromiso entre eficiencia del procesador y velocidad de respuesta
A
F
D
B
Lista de
procesos
6
Planificación por prioridad
Se asignan prioridades a los procesos y se ejecuta el de más alta prioridad
Se pueden agrupar por prioridades y utilizar turno rotatorio para cada prioridad
asignación estática o dinámica
Ejemplo: prioridad = 1/f ; f= T utilizado del último cuanto/ T del cuanto
2 ms de 100 => prioridad = 50
50 ms de 100 => prioridad = 2
100 ms de 100 => prioridad = 1
7
Múltiples listas de espera
Para sistemas que sólo pueden mantener en memoria un proceso
Baja el nº de transferencias
Si un proceso agota su cuanto, se le pasa a la categoría inferior. A los procesos con más cálculo se le da más tiempo de procesador
Proceso que necesita 100 cuantos:
1 2 4 8 16 32 64
Accede cada vez menos frecuentemente al procesador
1 c.
2 c.
4 c.
8 c.
16 c.
Prioridad
+
–
8
Prioridad al más corto
Para sistemas por lotes
Se conoce el tiempo de respuesta de los procesos
A B C D
ta tb tc td
ta ta+tb ta+tb+tc ta+tb+tc+td
T. promedio= 4ta+3tb+2tc+1td
A B C D
8 4 4 4
8 12 16 20
D B C A
4 4 4 8
4 8 12 20
T. promedio= 14
T. promedio= 11
T. Ejecución
T. Respuesta
9
Planificación determinada por el comportamiento
n usuarios => 1/n de la potencia del procesador
Se contabiliza:
tiempo de procesador consumido
tiempo tanscurrido = t. que lleva el proceso en el sistema
Se calcula:
t. al que se tiene derecho
t. transcurrido/n
Se ejecuta el proceso con el valor más bajo para:
t. de procesador consumido/ t. al que se tiene derecho
100 / 200 = 0.5
200 / 100 = 2
10
Planificación a dos niveles
Planificador de alto nivel
Se encarga de llevar procesos de disco a memoria y viceversa
Planificador de bajo nivel
Se encarga de pasar de un proceso a otro en memoria principal
Varios criterios
Tiempo en memoria
Tiempo de procesador
Prioridad
Tamaño
11
Detección y prevención de bloqueos
Interbloqueos
Se dan por la necesidad de uso exclusivo de algunos recursos por parte de los procesos
Ejemplo: proceso A necesita recurso 1 y 2 proceso B necesita recurso 2 y 1
proceso A pide 1
proceso B pide 2
proceso A pide 2 => se bloquea
proceso B pide 1 => se bloquea
Interbloqueo
En dispositivos de E/S, en bases de datos.
12
Recurso
Sólo puede ser utilizado por un proceso en un instante dado
Su uso conlleva:
Solicitar el recurso
Usar el recurso
Dejar el recurso
Si no está disponible, el proceso debe esperar
Los procesos se interbloquean si cada uno de ellos espera que se genere algún evento que sólo otro proceso del conjunto puede generar.
El evento es normalmente la liberación de un recurso que está siendo utilizado por otro proceso.
Página siguiente |