SISTEMAS OPERATIVOS
TEMA:
PROCESOS y PLANIFICACIÓN
Ing. Robiro A. Asuaje L.
05-01-99.
PROCESOS
Un programa en
ejecución
H. M. Deitel.
El concepto central en
cualquier sistema operativo
es el proceso: una
abstracción de un programa
en ejecución.
Andrew S. Tanenbaum.
BLOQUE DE CONTROL
DEL PROCESO (P.C.B).
Es una Estructura de datos, que permite al
Sistema Operativo manejar la información
relacionada con cada uno de los procesos. Esto
incluye:
 Estado Actual del Proceso.
 Identificador del Proceso.
 Un apuntador hacia el padre del proceso.
 Apuntadores a los hijos del proceso.
BLOQUE DE CONTROL
DE PROCESO(P.C.B).
 Prioridad del Proceso.
 Información de Administración de memoria del proceso.
 Apuntadores a los recursos asignados al proceso.
 Un área para salvaguarda de los registros relacionados con la
ejecución del proceso.
 El Procesador en que se está ejecutando el proceso
(en un sistema de procesadores múltiples).
ESTADOS DE UN PROCESO
Terminación de la operación
de E/S o del evento
Listo
S
U
S
P
E
N
D
E
R
Despachar
R
E
A
N
U
D
A
R
Expiración
del tiempo
Espera de E/S
o de algún
evento
En
ejecución
Bloqueado
S
U
S
P
E
N
D
E
R
R
E
A
N
U
D
A
R
E
S
T
A
D
O
S
A
C
T
I
V
O
S
SUSPENDER
Suspendido
Listo
Suspendido
Bloqueado
Terminación de la operación
de E/S o del evento
Estados
Pasivos
Operaciones sobre Procesos
* Crear un proceso.
* Destruir un proceso.
* Cambiar la prioridad de un proceso.
* Bloquear un proceso.
* Despachar un proceso.
* Permitir la comunicación entre procesos.
* Suspender un proceso.
* Reanudar un proceso.
Planificación de Procesos.
Cuando son ejecutables varios procesos,
el sistema operativo debe decidir cuál conviene
ejecutar si el CPU se encuentra disponible.
El elemento del sistema quien toma esta
decisión se llama PLANIFICADOR (Scheduling)
y el algoritmo del cual hace uso se denomina
ALGORITMO PLANIFICADOR.
Tipos de Planificación
No Apropiativa:
Una vez que el CPU ha sido asignado a un
proceso, ya no se le puede arrebatar.
Ejemplos: FIFO, Primer trabajo más corto
Tipos de Planificación
Apropiativa:
Cuando a un proceso, el sistema operativo
le puede quitar el CPU antes asignado.
Ejemplos:
Round Robin, Prioridades,
Tiempo restante más corto,
Colas múltiples.
Objetivos de la Planificación
1. Los procesos deben tratarse de la misma forma.
2. Evitar el aplazamiento indefinido.
3. Atender la mayor cantidad de procesos por unidad
de tiempo.
4. Mantener ocupados los recursos del sistema.
5. Lograr un equilibrio entre la respuesta y el uso de los
recursos.
6. Una tarea debe ejecutarse aproximadamente en el
mismo tiempo, cada vez que se ejecute.
Criterios de Planificación
1. Si el proceso utiliza exhaustivamente el CPU
(CPU Bound) o los diversos dispositivos (I/O
Bound).
2. Importancia del proceso. Tipo de procesamiento.
3. Cuánto tiempo real de ejecución lleva un proceso
y cuánto tiempo estimado necesita para terminar.
4. Frecuencia con la que el proceso utiliza la
memoria principal.
Niveles de Planificación
Planificación de Alto nivel:
Selecciona los trabajos que deben admitirse en el sistema.
Tareas:
1. Administrar todos los recursos del sistema excepto
el CPU.
2. Mantiene las colas de procesos bloqueados y
suspendidos.
3. Controla la creación de procesos.
4. Maneja el nivel de multiprogramación.
Niveles de Planificación
Planificación de nivel intermedio:
Determina cuáles procesos pueden competir por el
CPU.
Tareas:
1. Equilibrar la admisión de trabajos en el sistema
con la asignación del CPU a dichos procesos.
2. Nivelar la carga del sistema (procesos activos
y pasivos)
Niveles de Planificación
Planificación de bajo nivel:
Determina a cuál proceso listo se le asignará el CPU
cuando éste se encuentre disponible.
Tarea:
1. Despachar el proceso.
Políticas de Planificación:
FIFO
Los procesos son atendidos en el orden en que entraron a
la lista de Ready. El proceso tiene asignado el CPU hasta
que termina su ejecución.
* No Apropiativa.
* Generalmente se utiliza combinando con otros
esquemas.
Lista de Procesos Listos
Culminación
C
B
A
CPU
Políticas de Planificación:
Primer Trabajo más corto (SJF)
Se ejecuta primero el proceso en espera que tiene el
próximo menor tiempo estimado de ejecución, hasta
terminar.
* No Apropiativa
* Favorece a los trabajos cortos a expensa de
los largos.
* La prioridad del proceso es inversamente
proporcional al tiempo de ejecución.
Políticas de Planificación:
ROUND ROBIN
Consiste en asignar el CPU al primer proceso de
la lista de Ready durante un tiempo de ejecución
(Quantum), el cual es igual para todos los procesos.
* Variación del FIFO
* Apropiativa.
* El quantum puede variar: Carga del sistema,
prioridad de los procesos.
ROUND ROBIN
Lista de Procesos Listos
A
C
B
Apropiación
A
CPU
Políticas de Planificación:
Tiempo restante más corto (SRT)
Una vez que un proceso comienza su ejecución,
puede ser desplazado por un nuevo con menor tiempo
de ejecución estimado.
* Apropiativa.
* Implica mayor actividad que el Primer
Trabajo Más Corto (SJF).
Política de Planificación:
Prioridades
A cada proceso se le asigna una prioridad. Se le permite la ejecución al trabajo que tenga la mayor prioridad.
* Las prioridades pueden ser:
- Externas: Definidas por el usuario.
- Internas: Determinadas por el sistema.
* Pueden además clasificarse en:
- Estáticas: Cuando los procesos mantienen su prioridad constante durante su existencia en el sistema
- Dinámicas: Cuando las prioridades sufren cambios.
Política de Planificación:
Colas Múltiples
El movimiento de los procesos se determina a través de
varias colas de diferentes niveles.
 Un proceso nuevo entra a la red de colas, al final de la
primera cola. Se desplaza por FIFO.
 Cuando a un proceso se le termina su quantum de
tiempo, se coloca al final de la cola del siguiente nivel.
 El quantum asignado a un proceso cuando pasa a una
cola de nivel inferior alcanza un valor mayor.
 Un proceso en cierta cola no puede ejecutarse a menos
que estén vacías las colas de los niveles más altos.
Colas Múltiples
Nivel 1 FIFO
Uso
del
CPU
Nivel 2 FIFO
Uso
del
CPU
Nivel 3 FIFO
Uso
del
CPU
Nivel N
ROUND
ROBIN
Uso
del
CPU
Terminación
Terminación
Terminación
Multiples Procesadores
La planificación de procesos es más compleja cuando varios CPU’s se
encuentran disponibles. Generalmente cada CPU tiene su propia cola y su propio algoritmo de planificación.
Se presentan dos casos:
Sistema Homogéneo:
Los procesadores son idénticos.
•
Pueden utilizarse una carga compartida. Todos los procesos se
•
colocan en una sola cola.
Sistema Heterogéneo:
žLos procesos son clasificados por su estructura, ellos deben ejecutarse
en un procesador particular.
Evaluación de los Algoritmos
de Planificación
Tipos de Evaluación:
1. Analítica: Toman una serie de valores y se elabora
una especie de corrida en frío.
2. Simulación: Elaboración de modelos con algunas
herramientas y se trata de lograr un comportamiento
real de los procesos.
3. Implementación: Funcionar el sistema en su entorno
real de trabajo.
Evaluación de los Algoritmos
de Planificación
Elementos de Medida:
Tiempo
de respuesta (T): Tiempo durante el cual el proceso está
presente en el sistema
T= tiempo finalización - tiempo de llegada
Tiempo de ejecución en el CPU (t)
Tiempo desperdiciado(W): W = T - t
Tasa de penalización (P): P = T/ t
Evaluación del Algoritmo
F.I.F.O. (P.E.P.S.)
L
U
E
L
U
E
A
0
D
B
1
C
3
2
4
5
6
7
D
9
8
10
A
A
A
B
B
B
B
B
C
C
11
E
12
13
14
15
16
17
18
19
20
D
D
Proceso Tiempo
llegada
A
0
B
1
C
3
D
9
E
12
D
D
t
3
5
2
5
5
Tiempo
Arranque
0
3
8
10
15
E
E
Tiempo
Finalización
3
8
10
15
20
E
T
3
7
7
6
8
Promedio: 6.2
E
E
W
0
2
5
1
3
P
1.0
1.4
3.5
1.2
1.6
2.2
1.74
Evaluación del Algoritmo
Primer Trabajo más corto (S.J.F.)
L
U
E
L
U
E
A
0
B
1
A
10
2
A
A
E
12
11
D
C
3
D
4
C
13
D
Proceso Tiempo
llegada
A
0
B
1
C
3
D
9
E
12
C
14
D
t
3
5
2
5
5
5
6
B
15
D
Tiempo
Arranque
0
5
3
10
15
7
B
16
E
8
B
17
E
Tiempo
Finalización
3
10
5
15
20
D
9
B
18
E
T
3
9
2
6
8
Promedio: 5.6
10
B
19
E
20
E
W
0
4
0
1
3
P
1.0
1.8
1.0
1.2
1.6
1.6
1.32
Evaluación del Algoritmo
Tiempo restante más corto (S.R.T.)
L
U
E
L
U
E
A
0
B
1
2
A
10
A
11
E
Proceso
C
3
B
12
E
Tiempo
llegada
C
13
D
t
Tiempo
Arranque
0
1
2
5
0
2
C
D
E
3
9
10
2
4
2
3
9
10
5
C
14
D
A
B
1.22
4
6
7
B
B
D
9
8
B
B
D
15
D
Tiempo
Finalización
2
9
5
15
12
Promedio:
E
10
T
W
P
2
8
0
3
1.0
1.6
2
6
2
4
0
2
0
1
1.0
1.5
1.0
Evaluación del Algoritmo
Prioridades
L
U
E
L
U
E
A
0
B
1
A
10
2
B
Proceso Tiempo
llegada
A
0
B
1
C
3
D
9
E
12
B
E
12
11
D
C
3
D
4
C
13
D
5
C
14
D
6
B
15
D
Tiempo
t Prioridad Arranque
3
4
0
5
2
1
2
0
3
5
4
10
5
4
15
7
B
16
E
8
B
17
E
D
9
A
18
E
10
A
19
E
Tiempo
Finalización
T
10
10
8
7
5
2
15
6
20
8
Promedio: 6.6
20
E
W
7
2
0
1
3
4.3
P
3.3
1.4
1.0
1.2
1.6
1.7
Evaluación del Algoritmo
Round Robin
L
U
E
L
U
E
A
0
B
1
A
10
2
A
Proceso Tiempo
llegada
A
0
B
1
C
3
D
9
E
12
A
E
12
11
D
C
3
D
t
3
5
2
5
5
4
B
13
D
5
B
14
D
Tiempo
Arranque
0
3
7
10
14
6
B
15
E
7
B
16
E
Tiempo
Finalización T
3
3
10
9
9
6
19
10
20
8
Promedio: 7.2
8
C
17
E
D
9
10
C
18
E
B
19
D
20
E
W
0
4
4
5
3
P
1.0
1.8
3.0
2.0
1.6
3.2
1.88
Descargar

Sistemas Operativos: Procesos y Planificación