IET110 Sistemas Operativos

P05: Scheduler

Slide: 1

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Temario ://
Procesos Introduccin a los Scheduler Calendarizacin en Sistemas por Lotes (batch) Calendarizacin en Sistemas Interactivos Calendarizacin en Sistemas de Tiempo Real Calendarizacin de subprocesos

Sistemas Operativos ICC243

[2]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Programa v/s Proceso ://

Programa Conjunto de instrucciones, cdigo. Elemento pasivo. Proceso Programa en ejecucin. (Ente dinmico) Un programa puede levantar varios procesos. Tiene asociado un espacio de direcciones.

Sistemas Operativos ICC243

[3]

Prof. Jonathan Makuc

Sistemas Operativos: Conceptos

Espacio de Direcciones ://

El espacio de direcciones es el espacio en memoria asignado al proceso. Aqu se encuentra el cdigo del proceso y los datos que este utiliza.
Desde el punto de vista del proceso, el Address Space es la nica memoria existente en el sistema, no pudiendo acceder a direcciones forneas.

En el caso de sistemas sin paginacin, el espacio de direcciones no puede ser particionado en pginas, y ser cargado por partes o llevado parcialmente a swap; resultando en que el bloque de memoria esta realmente presente ya sea en RAM o disco.
Address Space

Cdigo Datos Stack

Cuando se tiene paginacin, entonces el espacio de direcciones es dividido en pginas, y resultando en que no todo este en RAM, sino solo una porcin. A este concepto de un espacio que realmente no esta por completo ni en memoria, ni en disco; se le denomina Espacio de Direcciones Virtual.

Registros
Sistemas Operativos ICC243 [4] Prof. Jonathan Makuc

Sistemas Operativos: Conceptos

Process Control Block (PCB) ://

El Process Control Block, es una ficha que lleva el sistema operativo con toda la informacin administrativa de un proceso.
Estado del Proceso Process ID Parent Process ID Program Counter

Permite conocer con exactitud el estado del proceso, en que parte de su cdigo se est ejecutando, cual es su nmero identificador, cuanta memoria tiene asociada, cuales archivos estn abiertos, etc.

Registros

Lmites de memoria Listado de archivos abiertos

Sistemas Operativos ICC243

[5]

Prof. Jonathan Makuc

Sistemas Operativos: Conceptos

Tabla de Procesos ://

La tabla de procesos, es una estructura en memoria que contiene la
ubicacin de los PCB de todos los procesos del sistema. A travs de esta, el kernel puede conocer el estado de cada proceso, saber en parte de la memoria se encuentra, etc.

Process Table

0
Estado del Proceso Process ID Parent Process ID Program Counter

1
Estado del Proceso Process ID Parent Process ID Program Counter

2
Estado del Proceso Process ID Parent Process ID Program Counter

3
Estado del Proceso Process ID Parent Process ID Program Counter

4
Estado del Proceso Process ID Parent Process ID Program Counter

5
Estado del Proceso Process ID Parent Process ID Program Counter

Registros

Registros

Registros

Registros

Registros

Registros

Lmites de memoria Listado de archivos abiertos

Lmites de memoria Listado de archivos abiertos

Lmites de memoria Listado de archivos abiertos

Lmites de memoria Listado de archivos abiertos

Lmites de memoria Listado de archivos abiertos

Lmites de memoria Listado de archivos abiertos

Sistemas Operativos ICC243

[6]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Creacin de un proceso ://

Crear un proceso es la accin de poner en memoria un programa, entregarle un contexto donde poder ejecutar sus instrucciones (Espacio Virtual), registrar la informacin de donde est y que caractersticas posee (PCB), e iniciar su funcionamiento (Calendarizar su ejecucin).
Opciones de ejecucin: Concurrente Padre espera conclusin de hijo
Opciones del Address Space Hijo es un duplicado del padre Hijo tiene un programa separado para cargarse Pasos para la creacin de un proceso Cargar el cdigo a la memoria Crear el stack vaco Crear o asignar PCB Inscribir el proceso en el scheduler

Sistemas Operativos ICC243

[7]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Destruccin de un proceso ://

Finalizacin Normal (Voluntario) El programa concluye su ejecucin como se espera, sin errores que reportar. Finalizacin con Error Voluntario (Voluntario) El programa entregando un error, siguiendo los procedimientos establecidos por el programador. Error Fatal (Involuntario) El sistema detecta un error fatal en el programa y termina su ejecucin. (Divisin por cero, acceso indebido a memoria, etc) Terminacin Forzada (Involuntario) Otro proceso con mayor autoridad cierra el proceso actual. Funcin administrativa.

Espacio de usuario
if(variable > 0) exit(0);

Espacio de usuario
if(variable > 0) exit(1);

Espacio de usuario
a = 1234 / 0;

Espacio de KERNEL
kernel->currentThread->yield(true);

Sistemas Operativos ICC243

[8]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Estados de un proceso ://

Nuevo / New: Corriendo / Running: Bloqueado / Waiting: Listo / Ready : Terminado / Terminated:
Sistemas Operativos ICC243

proceso recin creado proceso en ejecucin proceso en espera de un evento (I/O) proceso listo para entrar a la CPU proceso que ha terminado su ejecucin
[9] Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Estados de un proceso :// Procesos Suspendidos (Swap)

Listo y suspendido: Bloqueado y suspendido:

Proceso swapeado listo para entrar a la CPU Proceso swapeado Bloqueado (Esperando I/O)

Sistemas Operativos ICC243

[ 10 ]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Cambio de contexto ://

El Cambio de contexto, es el proceso por el cual el Sistema Operativo pasa de ejecutar el
cdigo de un proceso, a ejecutar el cdigo de otro proceso o a ejecutar cdigo en espacio de kernel. Los registros de la CPU llevan el

ProcesoA
Proceso A Ejecutndose Tiempo Perdido en labores admin. Proceso B Ejecutndose Grabar estado a PCBB Tiempo Perdido en labores admin. Grabar estado a PCBA

ProcesoB

estado de esta; son aquellos que indican que instruccin se esta ejecutando, cuales los valores de las variables en un momento dado, etc. El Cambio de contexto consiste en cambiar los valores de los registros de la CPU de los valores de un proceso a los valores de otro proceso. De manera de no perder el estado actual del proceso saliente, el sistema almacena

Restaurar estado de PCBB

en el PCB los valores de los registros

Restaurar estado de PCBA

actuales, para luego sobreescribirlos con los almacenados en el PCB del proceso entrante.
[ 11 ] Prof. Jonathan Makuc

Proceso A Ejecutndose Sistemas Operativos ICC243

Sistemas Operativos: Scheduler

Cambio de contexto ://

El cambio de contexto es una labor administrativa del sistema operativo que consume tiempo
de CPU. Durante este tiempo, ningn proceso esta en ejecucin por lo que se considera overhead en la administracin de procesos. Se denomina quantum de tiempo o quanto a un periodo de tiempo que el sistema operativo le entrega a un proceso para que este utilice la CPU. El trmino del quantum es indicado por una interrupcin de reloj que es previamente programada, momento en el cual se produce un cambio de contexto. Los cambios de contexto se pueden producir por:

Termino de quantum de tiempo (interrupcin de reloj)

Syscall yield, que solicita al SO que este proceso sea colocado en la ready list. Interrupcin que provoque colocar al proceso bloqueado (I/O, semforos, etc)

Sistemas Operativos ICC243

[ 12 ]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Cambio de contexto ://

Cambio de Contexto Cambio de Contexto

Scheduler

Proc1

Proc2

Restauracin

quanto

Respaldo

Sistemas Operativos ICC243

[ 13 ]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Scheduler - Introduccin ://

Scheduler (Calendarizador)
Componente del sistema operativo que decide cual de los procesos que esta en

estado ready es el que entrara a la CPU. Su decisin es basada segn el sistema

que este administrando y es resuelta por los Algoritmos de Calendarizacin.

P3 P2 P4

P1
Scheduler

P5

P6

CPU
Sistemas Operativos ICC243 [ 14 ] Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Scheduler - Introduccin ://

Comportamiento de los procesos

Dedicados al cmputo

Dedicados al I/O

Con el tiempo, a haber avanzado ms rpido la velocidad de las CPU que la de los dispositivos de I/O, la calendarizacin de procesos dedicados al I/O ha

cobrado mayor importancia.

Sistemas Operativos ICC243

[ 15 ]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Scheduler - Introduccin ://

Cundo Calendarizar
Creacin de proceso: ejecutar el padre o el hijo? Trmino de proceso: que proceso ejecutar ahora? Proceso bloquea por semforo: que hacer? En este caso el motivo afecta la decisin. Si un proceso bloquea por semforo, entonces conviene ejecutar el proceso que sostiene el lock en este momento. Proceso bloquea por I/O listo: entrar el proceso que paso de bloqueado a listo? Entrar al proceso interrumpido? Un tercer proceso?

Proceso IDLE: proceso de inactividad proporcionado por el sistema operativo cuando no existen procesos de usuario de ejecutar, o estn todos a la espera de algn evento.
Sistemas Operativos ICC243 [ 16 ] Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Scheduler - Introduccin ://

Tipos de calendarizacin
No Expropiativo: una vez que inicia un proceso, lo deja correr hasta que termina, realiza I/O o queda a la espera de otro proceso. Expropiativo: existe quantum de tiempo determinado que se le permite a un proceso estar en la CPU. Cuando este expira, el proceso debe salir y se debe

ingresar uno nuevo. Este mtodo requiere de una interrupcin de reloj al final del
quantum para poder ser implementado.
Sistemas por lotes - Sin usuarios en terminales - Algoritmos no expropiativos - Reducido nmero de cambios de contexto Sistemas Interactivos - Algoritmos expropiativos - No se puede permitir la monopolizacin des la CPU por parte un proceso - Se asume hostilidad entre procesos. Sistemas Tiempo Real - Pueden usar expropiativos y no expropiativos. - Generalmente todos los programas trabajan colaborativamente

Sistemas Operativos ICC243

[ 17 ]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Scheduler - Introduccin ://

Objetivos de la calendarizacin
Todos los sistemas Equidad dar a cada proceso una porcin equitativa de tiempo de CPU Cumplimiento de polticas cuidar que se ponga en prctica la poltica establecida Equilibrio mantener ocupadas todas las partes del sistema Sistemas por Lotes Rendimiento procesar el mximo de trabajos por hora Tiempo de retorno reducir al mnimo el lapso entre inicio y trmino de un trabajo Utilizacin de CPU mantener ocupada todo el tiempo la CPU Sistemas Interactivos Tiempo de respuesta responder rpido a las solicitudes Proporcionalidad satisfacer las expectativas de todos los usuarios Sistemas en Tiempo Real Cumplir los plazos evitar la prdida de datos Predicibilidad evitar la degradacin de la calidad en sistemas multimedia
Sistemas Operativos ICC243

[ 18 ]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Scheduler - Introduccin ://

Definiciones
Rendimiento: nmero de trabajos que el sistema termina por hora (ceteris paribus) Tiempo de retorno: promedio estadstico del tiempo que transcurre entre que se presenta un trabajo por lotes y el momento q termina. Starvation: situacin en la cual un proceso se le niega el acceso a un recurso de forma sistemtica, sin que este pueda acceder a l nunca.

Sistemas Operativos ICC243

[ 19 ]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Scheduler - Introduccin ://

Calendarizacin en 3 niveles
Proceso Corriendo

CPU

Scheduler De CPU Corto Plazo Determina que proceso en entra a la CPU. Puede utilizar cualquier mtodo expropiativo o no. Pieza que se le conoce como scheduler.

Nuevo Trabajo

Proceso Listo para correr

RAM Disco
Scheduler De Admision Largo Plazo Determina una combinacin de procesos ptima (CPU I/O, duracion, etc)

Proceso swapeado

Scheduler De Memoria Mediano Plazo Determina que procesos son mantenidos en RAM y cuales swapeados a disco. Determina el grado de mltiprogramacion (cant de procesos). Toma su decisin basado por ejemplo en: - Cuanto hace que el proceso se swapeo a disco? - Cuanto tiempo de CPU ha tenido ltimamente? - Que tan grande es el proceso? - Que tan importante? Sistemas Operativos ICC243 [ 20 ] Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Scheduler - Introduccin ://

Modelamiento de la multiprogramacin
- El punto clave es la cantidad de tiempo de CPU que utiliza un proceso versus la cantidad tiempo I/O. Esta cantidad puede ser expresada en forma de porcentaje de tiempo de I/O, pudindose calcular el aprovechamiento de la CPU por:

Aprovechamiento CPU = 1 - pn
Siendo: p tiempo de espera I/O n cant de procesos en el sist

Ej: 4 procesos en el sistema que cada uno realiza 80% del tiempo I/O. Aprovechamiento = 1 0.84 = 0.5904 4 procesos en el sistema que cada uno realiza 50% del tiempo I/O. Aprovechamiento = 1 0.54 = 0.9375

Sistemas Operativos ICC243

[ 21 ]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Scheduler - Introduccin ://

Modelamiento de la multiprogramacin

20% I/O 50% I/O 80% I/O

Sistemas Operativos ICC243

[ 22 ]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Calendarizacin en sistemas por lotes ://

Scheduling en
sistemas por lotes -- Mayor uso de CPU

Sistemas Operativos ICC243

[ 23 ]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Calendarizacin en sistemas por lotes ://

Primero en llegar, primero en ser atendido (FIFO)
Algoritmo mas simple de todos donde los procesos son ingresados a la CPU en el orden que se recibieron. CPU

De simple programacin y comprensin, tiene la desventaja de ser muy poco eficiente con trabajos de distinta duracin. Si un proceso
CPU

Proceso de larga duracin detendr a los dems hasta que termine

Sistemas Operativos ICC243

[ 24 ]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Calendarizacin en sistemas por lotes ://

Trabajo ms corto primero (SJF: Shortest Job First)
Algoritmo no expropiativo que al conocer a priori los tiempos de ejecucin de los procesos, los ordena de acuerdo a su duracin
4 1 12 8 2 12

CPU

12

12

2 1

CPU

Este mtodo acorta los tiempos promedio de ejecucin considerablemente, pero solo si se tienen disponibles todos los procesos simultneamente. De lo contrario no tiene efecto y su comportamiento se asemeja a FIFO.
Sistemas Operativos ICC243 [ 25 ] Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Calendarizacin en sistemas por lotes ://

SJF v/s FIFO Tiempos de proceso promedio sin expropiacin:
a ( a b) ( a b c ) i
a n

n a (n 1) b n n

FIFO

12

12

CPU

6 12 5 2 4 8 3 12 2 1 4 148 24.67 6 6

SJF

12

12

2 1

CPU

6 1 5 2 4 4 3 8 2 12 12 92 15.3 6 6
Sistemas Operativos ICC243 [ 26 ] Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Calendarizacin en sistemas por lotes ://

Tiempo Restante mas corto a continuacin
Variacin expropiativa de SJF donde al llegar un proceso, su tiempo de ejecucin se compara con el restante del proceso actual. Si el tiempo del nuevo proceso es menor, se suspende el actual para ingresar el recin llegado.
4 12 12 8

CPU

12

12

CPU

Sistemas Operativos ICC243

[ 27 ]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Calendarizacin en sistemas Interactivos ://

Scheduling en sistemas Interactivos -- Percepcin del usuario

Sistemas Operativos ICC243

[ 28 ]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Calendarizacin en sistemas Interactivos ://

Turno Circular Round Robin
Cada proceso recibe un quantum de tiempo en la CPU, debiendo abandonarla al trmino del mismo. De simple implementacin, solo se requiere tener una lista de procesos sobre la cual ciclar. quantum

Proc1

Proc2

Tiempo labores administrativas

Sistemas Operativos ICC243

[ 29 ]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Calendarizacin en sistemas Interactivos ://

Turno Circular Round Robin
Problema: Elegir el tamao del quantum. - Si es muy pequeo, entonces se desperdiciar mucho tiempo en labores administrativas. - Si es muy grande, el usuario percibir al sistema como lento

Sistemas Operativos ICC243

[ 30 ]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Calendarizacin en sistemas Interactivos ://

Por Prioridades
Cada proceso tiene asignado un valor prioridad. Al momento de decidir que proceso entra a la CPU, se selecciona aquel con mayor prioridad que este listo para correr. La asignacin de prioridad puede ser de forma estatica (al inicio del proceso) o de forma dinmica (durante la ejecucin). En linux existe el comando renice que permite a un administrador modificar la prioridad de un proceso en el sistema. Problema: Los procesos de alta prioridad pueden acaparar la CPU provocando starvation a los procesos de baja prioridad.

P7

P1

P4

P10

CPU

Sistemas Operativos ICC243

[ 31 ]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Calendarizacin en sistemas Interactivos ://

Por Prioridades
El scheduler puede decidir variar la prioridad de un proceso de acuerdo a su comportamiento: - Un proceso de I/O que tiene poco proceso y mucho acceso a disco, se le puede dar ms prioridad, pues estar la mayor parte del tiempo bloqueado.

Variacin: Clases de prioridades. Cada clase se ejecuta hasta que no existen ms procesos haciendo round robin al interior de esta. Luego se pasa a la clase con la siguiente prioridad.
P1 P2 P3
Sistemas Operativos ICC243 [ 32 ] Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Calendarizacin en sistemas Interactivos ://

Calendarizacin Garantizada
Enfocado a sistemas multiusuario, entrega porciones equitativas de CPU a cada uno. Si existen N usuarios, entonces cada uno recibir 1/N de la capacidad de CPU. Para su implementacin se cuenta el tiempo de CPU q ha recibido cada uno y luego se calcula el tiempo que le corresponde: TiempoEjecucion = relacin TiempoReal

Si la relacin es bajo 1/N entonces el proceso se ha ejecutado menos de lo que debe; si es mayor, entonces se ha ejecutado ms de lo que debe tomando el scheduler otros procesos hasta que la relacin se equipare.

Sistemas Operativos ICC243

[ 33 ]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Calendarizacin en sistemas Interactivos ://

Calendarizacin por lotera
Se determina la entrada a la CPU de un proceso de acuerdo a la cantidad de billetes de loteria que este posee, indicando as la prioridad del proceso. Al momento de seleccionar el proceso siguiente a entrar a la CPU, se sortea un numero entre los billetes entregados; de esta forma un proceso que tiene 100 nmero de un total de 500, tendr aproximadamente un 20% de posibilidades de ser escogido.

Sistemas Operativos ICC243

[ 34 ]

Prof. Jonathan Makuc

Sistemas Operativos: Scheduler

Calendarizacin en sistemas Interactivos ://

Calendarizacin por porcion equitativa
Metodologa que toma en cuenta a quien pertenecen los procesos en ejecucin. Si 2 usuarios tienen la misma prioridad ante el sistema, entonces sin importar la cantidad de procesos que tenga cada uno, se deber entregar el 50% de la CPU a cada usuario. Ejemplo: Usuario 1: Procesos A B C D Usuario 2: Proceso Z Ejecucion: A Z B Z C Z D Z A Z . Por otra parte, si existe diferencia de prioridad entre estos, tambin se puede modelar. Supngase que el usuario 1 ahora tiene 3 veces mas prioridad que el usuario 2: Ejecucion: A B C Z D A B Z

Sistemas Operativos ICC243

[ 35 ]

Prof. Jonathan Makuc

IET110 Sistemas Operativos

P05: Scheduler

Slide: 36

Prof. Jonathan Makuc