4.planificacion de uso del procesador
TRANSCRIPT
Planificacin de uso del procesador
Contenidos
(T5)Planificacin en VAX/VMS Planificacin en UNIX 4.4 BSD Estructuras de datos Clculo de prioridades Planificacin en W2K
Concepto de planificacin Estados de un proceso Planificador / Dispatcher Planificadores Algoritmos de planificacin Criterios de evaluacin Planificacin FIFO Planificacin SJFMtodo de prediccin
QuantumEscenarios de planificacin Ajuste de prioridad en W2K
Planificacin prioridades Planificacin Planificacin Planificacin multinivel
con con requisa round-robin con colas
Colas multinivel realimentadasPlanificacin del procesador2
1
Concepto de planificacin (i)La ejecucin de un trabajo se compone de secuencias de procesador y de espera Objetivo de la planificacin:Incrementar el rendimiento global del sistema Maximizar el uso de la CPU
Ejemplos de planificacin:Multitarea cooperativa: Windows 3.x Multitarea expulsiva o apropiativa: Windows 2k
Planificacin del procesador
3
Concepto de planificacin (ii)Estados de un proceso
Cola de listos
CPU
E/S
Cola de E/S
E/S
Cola de E/S
E/S
Cola de E/S
Planificacin del procesador
4
2
Concepto de planificacin (iii)Planificador / DispatcherPlanificador o scheduler: Determina en quin es el siguiente proceso en hacer uso de la CPU Dispatcher o repartidor: Conmuta el procesador de un trabajo a otroCambio de contexto Ejecuta el proceso durante un momento Salva el estado del proceso en el BCPCP
Flags de estadoRegistros de propsito general Registros de operaciones en coma flotante Informacin relativa a la memoria: punteros a las tablas de pginas, punteros a las tablas de segmentos, TLB, etc.
Restaura el estado de otro proceso Transfiere el control al nuevo procesoPlanificacin del procesador5
Concepto de planificacin (iv)Proceso 1En ejecucinInterrupcin o llamada al sistema
Sistema operativoDispatcher Dispatcher
Proceso 2
Planificador
Listo
ListoDispatcher Dispatcher
En ejecucinInterrupcin o llamada al sistema
Planificador
En ejecucin
Listo
Planificador
Dispatcher
polticas mecanismos
Planificacin del procesador
6
3
Concepto de planificacin (v)PlanificadoresPlanificador a largo plazoCarga del proceso en memoria Controla el grado de multiprogramacin
Planificador a corto plazoSelecciona entre los trabajos cargados en memoria y que estn listos para ejecutarse, cul har uso del procesador Debe ser muy rpido ya que entra en juego con una frecuencia muy alta
Planificador a medio plazoCarga y descarga trabajos (swap in-out) desde el disco a la memoria y de la memoria al disco en funcin del grado de sobrecarga del sistema
Planificacin del procesador
7
Algoritmos de planificacin (i)Criterios de evaluacinGrado de utilizacin del procesador Rendimiento (Throughput)Trabajos completados por unidad de tiempo
Tiempo de estancia (Turnaround time)Tiempo transcurrido desde que se lanza hasta que finaliza
Tiempo de esperaTiempo que est un proceso en una cola (no ejecucin)
Tiempo de respuestaImportante en aplicaciones interactivas o de tiempo real (hasta la 1 respuesta del sistema)
Grado de sobrecargaRecursos que emplea el planificador: tiempo de procesador y memoriaPlanificacin del procesador8
4
Algoritmos de planificacin (ii)
Planificacin Planificacin Planificacin Planificacin Planificacin Planificacin
FIFO primero el ms corto por prioridades
round robincon colas multinivel con colas multinivel realimentadas
Planificacin del procesador
9
Planificacin FIFO (i)FIFO: First in first out primero en entrar, primero en salir Gestiona la cola de procesos listos como una cola FIFO Ventaja:Es el algoritmo ms sencillo de codificar
Inconveniente:Un proceso puede monopolizar la CPU efecto convoy Depende fuertemente de los tipos de trabajo y del instante en que llegan
Ejemplo:T1: 12 u.t., T2: 3 u.t., T3: 6 u.t. T1: 100 u.t., T2: 1 u.t., T3: 1 u.t., T4: 1 u.t.Planificacin del procesador10
5
Planificacin FIFO (ii)Ejemplo FIFOCaso 1:Trabajo 1 0 Trabajo 2 12 15 Trabajo 3 21
Caso 2:Trabajo 2 0 3 Trabajo 3 9 Trabajo 1 21
Los tiempos medios de respuesta varan dependiendo de cmo se encolen los trabajosCaso 1: t Caso 2: t = 16 respuesta = 11respuesta
Planificacin del procesador
11
Planificacin FIFO (iii)Ejemplo FIFOCaso 1: Efecto convoyTrabajo 1 0 T2 T3 T4 100 101 102 103
Caso 2:T2 T3 T4 0 1 2 3 Trabajo 1 103
Los tiempos medios de respuesta varan dependiendo de cmo se encolen los trabajosCaso 1: t Caso 2: t = 101,5 u.t. respuesta = 27,25 u.t.respuesta
Planificacin del procesador
12
6
Planificacin SJF (i)SJF: shortest job first primero el ms corto Asigna la CPU al trabajo con la siguiente rfaga ms pequea Calcula, de forma dinmica, la longitud de la siguiente rfaga de CPU para cada proceso Ventaja:Reduce los tiempos medios de respuesta
Inconveniente:Conocer cules van a ser las duraciones de las prximas rfagas de CPU de cada proceso Produce inanicin en procesos con rfagas largas
Planificacin del procesador
13
Planificacin SJF (ii)Mtodo de prediccinLa siguiente rfaga de CPU se predice como una media exponencial de las longitudes medias en anteriores rfagas n+1 = tn + (1-) n Sea:tn: longitud de la n-sima rfaga de CPU n: valor predicho para la n-sima rfaga de CPU : parmetro de ajuste tn: contiene la informacin ms reciente n: contiene la historia pasada
Ejemplo:T1: 3 u.t., T2: 12 u.t., T3: 7 u.t., T4: 5 u.t. t respuesta = 13,25 u.t.Planificacin del procesador14
7
Planificacin con prioridadesSe asigna la CPU al trabajo con la prioridad ms alta Las prioridades pueden definirse:Internamente: Segn los requisitos del SOTiempo de CPU, memoria usada, recursos empleados, etc.
Externamente: Requisitos ajenos al SOTipo de usuario, tipo de aplicacin, etc.
Estticas: No vara durante la vida del proceso Dinmicas: Vara a lo largo de la vida del proceso, dependiendo de las decisiones del planificador
Inconveniente:Produce inanicin en procesos de baja prioridad Solucin: Utilizar envejecimientoPlanificacin del procesador15
Planificacin con requisaEn los algoritmos anteriores, un proceso usa la CPU hasta pedir una E/S o terminar monopolizar la CPU Solucin: Un proceso puede desalojar al que usa la CPU Algoritmos con requisa (preemption):SJF con requisa Prioridades con requisa
Ejemplo: SJF con requisaT1: t = 0, 8 u.t. T2: t = 3, 4 u.t. T3: t = 2, 11 u.t.Trabajo 1 Trabajo 2 0 3 7 Trabajo 1 12Planificacin del procesador
Trabajo 3 2316
8
Planificacin round-robin (i)Planificacin por turno rotatorio La CPU se asigna a cada proceso listo durante un cuanto de tiempo qEvita la monopolizacin de uso de CPU En sistemas de tiempo compartido
La cola de procesos preparados es FIFO Si la rfaga de CPU > q Interrupcin TIME-OUT Si la rfaga de CPU < q Liberacin de CPU Prestaciones: dependen fuertemente de q q round-robin degenera en FCFS q 0 CPU/n n es el nmero de procesos listosPlanificacin del procesador17
Planificacin round-robin (ii)Si q es muy pequeo se pierde mucho tiempo en el cambio de contexto. Disminuye la eficacia del procesador Si q es grande los tiempos de respuesta aumentan Regla emprica:El 80% de las rfagas de CPU deben ser menores que el cuanto
Problema:Slo existe una cola de trabajos preparados, no distingue entre tipos de trabajos
Planificacin del procesador
18
9
Planificacin con colas multinivel (i)Objetivo: Diferenciar entre distintos tipos de trabajos Existen colas separadas en funcin del tipo de trabajo Cada cola tiene su propio algoritmo de planificacin Debe existir otro algoritmo para elegir la cola en cada momentoPrioridad alta Tareas del sistema Tareas interactivas Tareas de edicin Prioridad baja Tareas batchPlanificacin del procesador19
Planificacin con colas multinivel (ii)Colas multinivel realimentadasTcnicas adaptativasLos trabajos cambian de prioridad y de cola
Consideraciones:El algoritmo de planificacin de cada cola Mtodos para ascender y descender entre colas Dnde poner inicialmente a los trabajos+ PrioridadTareas de TR Quantum = 10 Quantum = 20 FCFSPlanificacin del procesador20
10
Planificacin en VAX/VMS (i)Caractersticas:Entorno multiusuario Tiempo compartido Aplicaciones interactivas Planificacin de procesos
Planificacin con prioridades [0 31] y desalojo Procesos de usuario [0 15] : Prioridad base fija + offsetOffset: hasta 6 niveles sobre la prioridad baseSe beneficia a las tareas limitadas por E/S
Procesos de tiempo real [16 31] :Su prioridad no suele cambiarPlanificacin del procesador21
Planificacin en VAX/VMS (ii)+31
...16 15
Tareas de tiempo real
...0
Tareas ordinarias
Cont. W2KPlanificacin del procesador22
11
Planificacin en UNIX 4.4 BSD (i)Caractersticas:Entorno multiusuario Tiempo compartido Aplicaciones interactivas Planificacin de procesos
Planificacin con prioridades dinmicas [127 0] y desalojoProcesos en modo supervisor [49 0] Procesos en modo usuario [127 50]
Existen 32 colasCola Prioridad / 4 q = 0,1 sPlanificacin del procesador23
Planificacin en UNIX 4.4 BSD (ii)Estructuras de datoswhichqs 0 0 1 0 1 qs Cola 0 Cola 1 Cola 2 Cola 3 Cola 4 Prio. 0-3 Prio. 4-7 Prio. 8-11 Prio. 12-15 Prio. 16-19 ... Cola 31 Prio. 124-127 Proc Proc Proc Proc Proc ... Indica qu cola contiene procesos listos
Planificacin del procesador
24
12
Planificacin en UNIX 4.4 BSD (iii)Estructuras de datosEstructura proc:p_usrpri p_estcpu p_nice p_slptime Prioridad en modo usuario Tiempo de procesador acumulado Definido por el usuario [-20 +20] Tiempo bloqueado por algn evento
1 tick = 10 ms. Interrupciones de un reloj hardware
Planificacin del procesador
25
Planificacin en UNIX 4.4 BSD (iv)Clculo de prioridadeshardclock()Incrementa el valor de p_estcpu del proceso activo hasta un mximo de 127 cada 1 tick
setpriority()Recalcula la prioridad de cada proceso cada 4 ticks: p_usrpri = PUSER + (p_estcpu/4) + 2p_nice
schedcpu()Recalcula las prioridades cada 1 s: p_estcpu = decay p_estcpu + p_nice (decrementa p_estcpu) donde: decay = 2 carga / (2 carga) + 1 p_estcpu = decayp_slptime p_estcpu
roundrobin() conmuta el procesador cada 100 msPlanificacin del procesador26
13
Planificacin en W2K (i)Caractersticas:Entorno monousuario Tiempo compartido Aplicaciones interactivas o como servidor Planificacin de hilos
Planificacin apropiativa con prioridades [031]Tareas de tiempo real [16 31] Tareas ordinarias [1 15] Prioridades dinmicas: base + offset Prioridad 0: Zero page threadProceso inactivo del sistemaColas VAX/VMSPlanificacin del procesador27
Planificacin en W2K (ii)
Quantum1 tick:
q=q3 10 ms en sistemas monoprocesador i80x86 15 ms en sistemas multiprocesador i80x86
W2K Professional:6 unidades lgicas 2 ticks 20 ms Interactividad, tiempo de respuesta ms bajo
W2K Server:36 unidades lgicas Mejor rendimiento 12 ticks 120 msListo Ejecucin
Ensanchamiento de q:
W2K professional Valores: 6, 4 2 ticks Mejora tiempo de respuesta Aplicable a la tarea que se ejecuta en 1er. plano
Planificacin del procesador
28
14
Planificacin en W2K (iii)El planificador se activa, cuando un hilo:Abandona el estado de ejecucin porque acaba su q, pasa al estado de espera o finaliza su ejecucin Pasa al estado de listo porque acaba de ser creado o finaliza una operacin de E/S Cambia de prioridad de forma implcita definida por el SO o de forma explcita definida pro el programador Cambia la afinidad de procesadorTerminado Ejecucin Espera Transicin ListoPlanificacin del procesador29
Standby
Planificacin en W2K (iv)Escenarios de planificacinConmutacin voluntariaEl hilo en ejecucin pasa al estado de espera Se elige el 1er. trabajo de la cola de mayor prioridadListo Ejecucin
Finalizacin del quantumSi la prioridad del hilo es la prioridad base
Espera
Si ha habido aumento de prioridad (no en tareas de TR)
Planificacin del procesador
30
15
Planificacin en W2K (v)Escenarios de planificacinRequisaSi pasa al estado de listo un hilo de mayor prioridad que el que est en ejecucin Existe requisa para hilos en modo ncleo, si IRLQ