PDF de programación - Tema 5: Planificación de procesos - Unidad 2: Gestión de Procesos

Unidad 2:
Gestión de Procesos

Tema 5: Planificación de procesos.

5.1 Criterios y tipos de planificación.
5.2 Algoritmos de planificación.
5.3 Métodos multicolas y multiprocesadores.
5.4 Evaluación de políticas de planificación.

Escuela Universitaria de
Informática (Segovia)

1

5.1 Criterios y tipos de planificación.

Introducción:

Objetivo de la multiprogramación:

• Tener un proceso en ejecución en todo momento para un

mayor aprovechamiento de la CPU.

En un sistema monoprocesador nunca habrá más de un

proceso en ejecución. Si hay más procesos, tendrán que
esperar a que la CPU quede libre para reasignarse.

Para un mayor aprovechamiento, se mantienen varios

procesos en memoria a la vez. Cuando un proceso
necesita esperar, el SO le quita la CPU y se la da a otro
proceso.

Casi todos los recursos del computador se planifican

antes de usarse; la planificación es fundamental en el
diseño de un SO.

Escuela Universitaria de
Informática (Segovia)

2

5.1 Criterios y tipos de planificación.

Ciclo de ráfagas de CPU y E/S:

La ejecución de un proceso consiste en un ciclo de

ejecución alternando de manera sucesiva:

• Ráfagas de CPU (que inician el proceso), durante las cuales el

proceso ejecuta instrucciones.

• Ráfagas de E/S, durante las cuales el proceso utiliza o espera

por la E/S.

Se ha medido la duración de las ráfagas de CPU y resulta

que varían considerablemente de un proceso a otro y
de un procesador a otro, sin embargo tienden a tener una
curva de frecuencia bien tipificada.

Escuela Universitaria de
Informática (Segovia)

3

5.1 Criterios y tipos de planificación.

Ciclo de ráfagas de CPU y E/S:

Histograma de tiempos de ráfaga de CPU:

• Se observa:

• Gran nº de ráfagas de CPU cortas y pocas ráfagas de CPU largas.
• Ráfagas de CPU cortas: programas limitados por E/S.
• Ráfagas de CPU largas: programas limitados por CPU.

Escuela Universitaria de
Informática (Segovia)

4

5.1 Criterios y tipos de planificación.

Planificación expropiativa:

Las decisiones de planificación de CPU se toman según

las cuatro situaciones siguientes:

• 1. Cuando un proceso pasa del estado en ejecución a en espera.
• 2. Cuando un proceso pasa del estado en ejecución a listo.
• 3. Cuando un proceso pasa del estado en espera al estado listo.
• 4. Cuando un proceso termina.

Los casos 1 y 4 corresponden a una planificación no

expropiativa (a la fuerza hay que escoger un nuevo
proceso).

Los casos 2 y 3 corresponden a una planificación

expropiativa.

Escuela Universitaria de
Informática (Segovia)

5

5.1 Criterios y tipos de planificación.

Criterios de planificación:

Utilización de CPU: % de tiempo que la CPU está ocupada.
Rendimiento: nº de procesos, trabajos, que se completan

por unidad de tiempo.

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 la CPU desde que ocurre el suceso que lo
bloquea.

Escuela Universitaria de
Informática (Segovia)

6

5.1 Criterios y tipos de planificación.

Criterios de planificación:

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áximo.

En sistemas interactivos, como los sistemas de tiempo
compartido, se consideran también la estadística (las
medias) de esas magnitudes.

No existe ninguna política de planificación óptima. La

bondad de un método depende de:

• Tipo de procesos.
• Criterio.

Escuela Universitaria de
Informática (Segovia)

7

5.2 Algoritmos de planificación.

FCFS (First Come, First Served).
SJF (Shortest Job First) o SPN (Shortest Process Next).
SRTF (Shortest Remaining Time First).
Planificación por prioridad.
Planificación por turno circular, RR (Round Robin).
Realimentación.
HRRN (Highest Response Ratio Next).

Escuela Universitaria de
Informática (Segovia)

8

5.2 Algoritmos de planificación.

FCFS (First Come, First Served), ejemplo:

Planificación de servicio por orden de llegada.
Calcular el tiempo de espera, tiempo de retorno y

tiempo medio de espera si aplicamos el algoritmo FCFS
suponiendo que los procesos siguientes llegan en el mismo
instante y en el orden: P1, P2, P3.

¿Y si el orden de llegada es: P2, P3, P1?.

Escuela Universitaria de
Informática (Segovia)

9

5.2 Algoritmos de planificación.

FCFS, ejemplo:

Escuela Universitaria de
Informática (Segovia)

10

5.2 Algoritmos de planificación.

FCFS:

Planificación de servicio por orden de llegada.
Es el algoritmo más sencillo, el primer proceso que solicita

la CPU es el primero en recibirla.

Fácil de implementar con una política FIFO para la cola de

preparados.

Tiempo de espera promedio bastante largo.

Escuela Universitaria de
Informática (Segovia)

11

5.2 Algoritmos de planificación.

SJF (Shortest Job First), ejemplo:
Primero el trabajo más corto.
Calcular el tiempo medio de espera que resulta de aplicar:

• Un algoritmo SJF no expulsivo.
• Un algoritmo SJF expulsivo (SRTF, Shortest Remaining Time

First).

Escuela Universitaria de
Informática (Segovia)

12

5.2 Algoritmos de planificación.

SJF, ejemplo:

Escuela Universitaria de
Informática (Segovia)

13

5.2 Algoritmos de planificación.

SJF:

Entra en la CPU el proceso con la ráfaga de CPU más

corta.

Minimiza el tiempo de espera medio.
Riesgo de inanición de los procesos de larga duración.
No es implementable. Se pueden estimar las duraciones de

los procesos, según su historia reciente.

Versión expulsiva (SRTF): el proceso en CPU es desalojado

si llega a la cola un proceso con duración más corta.

Escuela Universitaria de
Informática (Segovia)

14

5.2 Algoritmos de planificación.

Planificación por prioridad:

Cada proceso tiene una prioridad, entrará primero en la

CPU el que tenga mayor prioridad.

• Política de prioridades expulsiva o no.
• La prioridad se puede definir:

• De forma interna, la define el SO.
• De forma externa, la definen los usuarios.

• SJF es un caso de planificación por prioridad.

Los procesos de prioridad más baja tienen riesgo de

inanición.

Solución: envejecimiento. Ir aumentando de forma

progresiva la prioridad de los procesos en espera.

Escuela Universitaria de
Informática (Segovia)

15

5.2 Algoritmos de planificación.

Planificación por turno circular:

RR (Round Robin):

• Adecuado para implementar tiempo compartido.
• Comportamiento como FCFS, con la diferencia de que cada

proceso dispone de un cuanto de tiempo máximo.

• Si cuando expira el cuanto de tiempo el proceso continúa en CPU, el
planificador lo desaloja y lo ingresa al final de la cola de preparados.

• La cola de preparados se gestiona como FIFO.
• Según sea el cuanto de tiempo, Q:

• Si Q es muy grande, los procesos terminan sus ráfagas de CPU

antes de que termine el cuanto: se comporta como un FCFS.

• Si Q=>0, se tiende a un sistema en el que cada proceso dispone de

un procesador a 1/N de la velocidad del procesador real (procesador
compartido).

• Si Q es muy pequeño se suceden constantemente los cambios

de contexto y del rendimiento disminuye mucho.

Escuela Universitaria de
Informática (Segovia)

16

5.2 Métodos Multicola y Multiprocesador.

Planificación con colas de múltiples niveles:

Distinguimos entre procesos que pueden tener distintas
necesidades en cuanto al tiempo de respuesta y por
tanto distintas necesidades de planificación.

• Procesos que se ejecutan en primer plano o interactivos.
• Procesos que se ejecutan en segundo plano o por lotes.

Escuela Universitaria de
Informática (Segovia)

17

5.2 Métodos Multicola y Multiprocesador.

Planificación con colas de múltiples niveles:

Un algoritmo de planificación con colas de múltiples niveles

divide la cola de procesos listos en varias colas.

Cada cola tiene su propio algoritmo de planificación.
Existirá, por tanto, una planificación entre colas.
Las colas se pueden planificar según:

• Planificación expropiativa de prioridades fijas.
• Dividiendo el tiempo de CPU entre las colas.

Escuela Universitaria de
Informática (Segovia)

18

5.2 Métodos Multicola y Multiprocesador.

Planificación con colas de múltiples niveles y

realimentación:

Se permite que un proceso pase de una cola a otra.
Si un proceso gasta demasiado tiempo de CPU, se le pasa

a una cola de menor prioridad.

Si un proceso espera mucho tiempo en una cola de baja
prioridad se le puede pasar a una de mayor prioridad,
evitando la inanición. (Caso del sistema UNIX)

Escuela Universitaria de
Informática (Segovia)

19

5.2 Métodos Multicola y Multiprocesador.

Planificación con colas de múltiples niveles y

realimentación:

Un planificador de colas multinivel con realimentación

está definido por los siguientes parámetros:

• El número de colas.
• El algoritmo de planificación para cada cola.
• Los métodos para determinar cuando mover un proceso a

una cola de distinta prioridad a la que ocupa.

• El método para determinar en qué cola ingresará un

proceso.

Escuela Universitaria de
Informática (Segovia)

20

5.2 Métodos Multicola y Multiprocesador.

Planificación en multiprocesa