Sistemas Operativostema 5. Planificación De Procesos

Sistemas Operativos Tema 5. Planificación de procesos

© 1998-2008 José Miguel Santos – Alexis Quesada – Francisco Santana
1

Contenido
Modelo del sistema y criterios de rendimiento Algoritmo FCFS Algoritmo SJF Métodos basados en prioridades Turno rotatorio (Round-Robin) Métodos multicolas Multiprocesadores

2

Planificación de procesos
El sistema operativo decide:
qué proceso entraen la CPU cuando ésta queda libre; en qué momento el proceso que está en ejecución debe abandonar la CPU.

En otras palabras:
El S.O. debe aplicar una política de planificación de procesos

3

¿Qué buscamos?
Podemos definir múltiples políticas de planificación de procesos: en orden de llegada, primero la tarea más breve, por orden de prioridad… ¿Qué política nos interesa más? ¿Quéobjetivos mínimos debe cumplir una política de planificación? ¿Cómo valoramos si una política es mejor o peor que otra?

4

Criterios de rendimiento
Se usan varias magnitudes para medir el rendimiento de los algoritmos de planificación:
Utilización de CPU: % de tiempo que la CPU está ocupada Tiempo de retorno: tiempo transcurrido entre la llegada de un proceso y su finalización Tiempo de espera:tiempo que un proceso permanece en la cola de preparados Tiempo de respuesta: tiempo que un proceso bloqueado tarda en entrar en CPU, desde que ocurre el evento que lo bloquea

5

Criterios de rendimiento (2)
Posibles objetivos de la planificación:
Minimizar el tiempo medio de espera o de retorno Maximizar la utilización de CPU Mantener el tiempo de respuesta por debajo de un valor máximoSe pueden considerar las medias, valores extremos o varianzas de estas magnitudes. No existe una política de planificación óptima para todos los criterios.
Habrá que llegar a un compromiso.

6

Modelo del sistema: ráfagas de CPU y E/S
Podemos considerar que la vida activa de un proceso es una sucesión de:
ráfagas de CPU -> el proceso ejecuta instrucciones ráfagas de E/S -> el procesoutiliza o espera por la E/S

Según la utilización de los recursos, se observan:
procesos intensivos en CPU (ej. cálculos numéricos) procesos intensivos en E/S (ej. interactivos)

7

Histograma de tiempos de ráfaga de CPU
160 140 120 100 80 60 40 20 0 8 16 24 32 40

duración de la ráfaga (milisegundos)

8

Políticas expulsivas (preemptive)
No expulsivas: el proceso que está en CPU laabandona cuando quiere (ej. FCFS)
problema de acaparamiento injusto de la CPU Windows 3.11, Apple Macintosh…

Expulsivas: el planificador puede desalojar al proceso que está en CPU
para implementar tiempo compartido y tiempo real, es necesaria una planificación expulsiva: Unix, Windows NT/XP, Mac OS X…

9

Despachador (dispatcher)
Módulo que cede el control de la CPU al procesoseleccionado por el planificador a corto plazo
Cambia de contexto Cambia a modo usuario Saltar al punto apropiado del programa de usuario

10

FCFS (en orden de llegada)
Proceso P1 P2 P3 Duración 9 4 2

Calcular el tiempo de espera, tiempo de retorno y tiempo medio de espera si aplicamos el algoritmo FCFS suponiendo que llegan en el mismo instante en el siguiente orden: P1, P2, P3 Realizar losmismos cálculos suponiendo que llegan en el siguiente orden: P2, P3 y P1
11

FCFS: ejemplo de diagrama de Gantt
Proceso P1 P2 P3 Duración 9 4 2

Diagrama de Gantt
0 9 13 15

P1

P2

P3

Tiempos de espera: P1=0; P2=9; P3=13 Tiempos de retorno: P1=9; P2=13; P3=15 t. espera medio: (0+9+13)/3 = 7.3 Si P1 hubiera llegado el último, los tiempos hubieran mejorado bastante (espera media=3.3):0 4 6 15

P2

P3

P1
12

FCFS: características
La cola de preparados se gestiona como una FIFO Simple de implementar Muy sensible al orden de llegada de los procesos Perjudica a los procesos intensivos en E/S (efecto convoy)

13

SJF (primero el más corto)
SJF = Shortest Job First Entra en CPU el proceso con la ráfaga de CPU más breve. Minimiza el tiempo de espera medio....