Sistemas Operativos: Calendarizacin de Procesos

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 sistemaque este administrando y es resuelta por los Algoritmos de Calendarizacin.

P3 P2 P4

P1Scheduler

P5

P6

CPU

Comportamiento de los procesosDedicados 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.

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.

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

Objetivos de la calendarizacinTodos 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

Calendarizacin en 3 nivelesProceso Corriendo 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.

CPU

Nuevo Trabajo

Proceso Listo para correr

RAM DiscoScheduler 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?

Calendarizacin en sistemas Interactivos

Scheduling en sistemas Interactivos -- Percepcin del usuario

Turno Circular Round RobinEs un mtodo para seleccionar todos los elementos de un grupo de manera equitativa, y en un orden racional, normalmente comenzando por el primer elemento. 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

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

Por PrioridadesCada 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

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

Calendarizacin en sistemas por lotes

Scheduling ensistemas por lotes -- Mayor uso de CPU

FIFOLos procesos son atendidos en el orden en que entraron a la lista de Ready. El proceso tiene asignado el CPU hasta que termina su ejecucin. * No Apropiativa. * Generalmente se utiliza combinando con otros esquemas. Lista de Procesos Listos

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

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

8

4

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.

Colas Mltiples El movimiento de los procesos se determina a travs 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

estn vacas las colas de los niveles ms altos.

La planificacin de procesos es ms compleja cuando varios CPUs se encuentran disponibles. Generalmente cada CPU tiene su propia cola y su propio algoritmo de planificacin.Se presentan dos casos: Sistema Homogneo:Los procesadores son idnticos. Pueden utilizarse una carga compartida. Todos los procesos se colocan en una sola cola.

Sistema Heterogneo:Los procesos son clasificados por su estructura, ellos deben ejecutarse en un procesador particular.

Scheduling ensistemas de tiempo real -- Mayor uso de CPU

Se caracterizan porque los procesos tienen que ejecutar en instantes predeterminados. Dos tipos: a plazo fijo y peridico. Los de plazo fijo se ejecutan una vez en un instante determinado. Los peridicos se ejecutan cada cierto tiempo. Los proceso que no han alcanzado su tiempo de ejecucin se encuentran en tiempo estn en una cola de espera y los que si pasan a colas de listo para ejecutar. La planificacin parte de seleccionar estos ltimos. Los sistemas en tiempo real crticos tienen asignada una franja de tiempo que no pueden rebasar. Suelen tener pocos procesos en estado de listo a fin de que no se retrase la ejecucin de los mismos. Se introducen retardos en la ejecucin, como puede ser la memoria virtual, puesto que la paginacin puede producir retrasos inadmisibles para el proceso.

Asignacin de Procesadores

Por definicin, un sistema destruido costa de varios procesadores. Estos se pueden organizar como coleccin de estaciones de trabajo personales, una pila de pblica de procesadores o alguna forma hibrida. En todos los casos se necesitan ciertos algoritmos para decidir que proceso ejecutar y en que maquina. Para el modelo de estaciones de trabajo, la pregunta es cuando ejecutar el proceso de forma local y cuando es buscar una estacin inactiva. Para el modelo de la pila de procesadores, hay que tomar una decisin por cada nuevo proceso.