Tema 5: Planificacion de procesos - de procesos...  Algoritmo FCFS Algoritmo SJF ... Diagrama de

  • View
    220

  • Download
    0

Embed Size (px)

Text of Tema 5: Planificacion de procesos - de procesos...  Algoritmo FCFS Algoritmo SJF ... Diagrama...

  • Sistemas OperativosTema 5. Planificacin de

    procesos

    1

    1998-2008 Jos Miguel Santos Alexis Quesada Francisco Santana

  • Contenido

    Modelo del sistema y criterios de rendimiento Algoritmo FCFS Algoritmo SJF Mtodos basados en prioridades Turno rotatorio (Round-Robin) Mtodos multicolas Multiprocesadores

    2

  • Planificacin de procesos

    El sistema operativo decide:qu proceso entra en la CPU cuando sta queda libre;en qu momento el proceso que est en ejecucin debe abandonar la CPU.

    En otras palabras:El S.O. debe aplicar una poltica de planificacin de procesos

    3

  • Qu buscamos?

    Podemos definir mltiples polticas de planificacin de procesos: en orden de llegada, primero la tarea ms breve, por orden de prioridadQu poltica nos interesa ms?Qu objetivos mnimos debe cumplir una poltica de planificacin?Cmo valoramos si una poltica es mejor o peor que otra?

    4

  • Criterios de rendimiento

    Se usan varias magnitudes para medir el rendimiento de los algoritmos de planificacin:

    Utilizacin de CPU: % de tiempo que la CPU est ocupada Tiempo de retorno: tiempo transcurrido entre la llegada de un proceso y su finalizacin 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 CPU, desde que ocurre el evento que lo bloquea

    5

  • Criterios de rendimiento (2)

    Posibles objetivos de la planificacin: Minimizar el tiempo medio de espera o de retorno Maximizar la utilizacin de CPU Mantener el tiempo de respuesta por debajo de un valor mximo

    Se pueden considerar las medias, valores extremos o varianzas de estas magnitudes. No existe una poltica de planificacin ptima para todos los criterios.

    Habr que llegar a un compromiso.

    6

  • Modelo del sistema: rfagas de CPU y E/S

    Podemos considerar que la vida activa de un proceso es una sucesin de:

    rfagas de CPU -> el proceso ejecuta instrucciones rfagas de E/S -> el proceso utiliza o espera por la E/S

    Segn la utilizacin de los recursos, se observan:

    procesos intensivos en CPU (ej. clculos numricos) procesos intensivos en E/S (ej. interactivos)

    7

  • Histograma de tiempos de rfaga de CPU

    duracin de la rfaga (milisegundos)0 4016 328 24

    160

    140

    120

    100

    80

    60

    40

    20

    8

  • Polticas expulsivas (preemptive)

    No expulsivas: el proceso que est en CPU la abandona cuando quiere (ej. FCFS)

    problema de acaparamiento injusto de la CPUWindows 3.11, Apple Macintosh

    Expulsivas: el planificador puede desalojar al proceso que est en CPU

    para implementar tiempo compartido y tiempo real, es necesaria una planificacin expulsiva: Unix, Windows NT/XP, Mac OS X

    9

  • Despachador (dispatcher)

    Mdulo que cede el control de la CPU al proceso seleccionado por el planificador a corto plazo

    Cambia de contextoCambia a modo usuarioSaltar al punto apropiado del programa de usuario

    10

  • FCFS (en orden de llegada)

    Calcular el tiempo de espera, tiempo de retorno y tiempo medio de espera si aplicamos el algoritmo FCFS suponiendo que llegan en el mismo instante en el siguiente orden: P1, P2, P3Realizar los mismos clculos suponiendo que llegan en el siguiente orden: P2, P3 y P1

    Proceso DuracinP1 9P2 4P3 2

    11

  • FCFS:ejemplo de diagrama de Gantt

    Proceso DuracinP1 9P2 4P3 2

    P2P1 P3

    Tiempos de espera: P1=0; P2=9; P3=13Tiempos de retorno: P1=9; P2=13; P3=15t. espera medio: (0+9+13)/3 = 7.3

    Si P1 hubiera llegado el ltimo, los tiempos hubieran mejorado bastante (espera media=3.3):

    0 9 13 15

    P2 P1P30 4 6 15

    Diagrama de Gantt

    12

  • FCFS: caractersticas

    La cola de preparados se gestiona como una FIFO Simple de implementar Muy sensible al orden de llegada de los procesos Perjudica a los procesos intensivos en E/S (efecto convoy)

    13

  • SJF (primero el ms corto)

    SJF = Shortest Job FirstEntra en CPU el proceso con la rfaga de CPU ms breve.Minimiza el tiempo de espera medio.Versin expulsiva: Shortest Remaining Time First(SRTF). El proceso en CPU es desalojado si llega a la cola un proceso con duracin ms corta.

    14

  • SJF - ejemplo

    Calcular el tiempo medio de espera que resulta de aplicar un algoritmo SJF no expulsivo Calcular el tiempo medio de espera que resulta de aplicar un algoritmo SJF expulsivo (SRTF)

    Proceso Llegada DuracinP1 0 7P2 2 4P3 4 1P4 5 4

    15

  • SJF - ejemplo

    Proceso Llegada Duracin esperaSJF

    esperaSRTF

    P1 0 7 0 9P2 2 4 6 1P3 4 1 3 0P4 5 4 7 2

    P10

    P3 P2 P4

    P1 P2 P3 P2 P4 P1

    7 8 12 16

    0 2 4 5 7 11 16

    SJF no expulsivoespera media: (0+6+3+7)/4=4

    SJF expulsivoespera media: (9+1+0+2)/4=3

    16

  • SJF: inconvenientes

    Riesgo de inanicin de los procesos de larga duracin.El SJF no es implementable se pueden estimar las duraciones de los procesos, segn su historia reciente.

    17

  • Planificacin por prioridades

    Cada proceso tiene una prioridad; entra en CPU aquel con mayor prioridad.

    la poltica puede ser expulsiva o no Prioridades definidas de forma interna (por el S.O.) o externa (por los usuarios) El SJF es un caso (prioridad=duracin estimada)

    Riesgo de inanicin de los procesos con menos prioridad. Solucin: envejecimiento. Aumentar progresivamente la prioridad a los procesos en espera.

    18

  • Turno rotatorio (Round-Robin)

    Adecuado para implementar tiempo compartido Como el FCFS, pero cada proceso dispone de un cuanto de tiempo mximo

    si cuando expira el cuanto de tiempo el proceso contina en CPU, el planificador lo desaloja y lo ingresa al final de la cola de preparados

    La cola de preparados se gestiona como FIFO Si el cuanto de tiempo es Q y hay N procesos en cola, el tiempo de respuesta es como mucho Q(N-1)

    19

  • Round Robin: ejercicio

    Probar con Q=4, Q=2, Q=1

    Proceso DuracinP1 15P2 4P3 3

    20

  • Influencia del cuanto de tiempo

    Si Q es muy grande, los procesos terminan sus rfagas 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). Ojo, si Q es muy pequeo, ocurren ms cambios de contexto y baja el rendimiento.

    21

  • Multicolas

    Varias colas de preparados, cada una gestionada con una poltica diferente. Las colas se reparten la CPU segn alguna poltica:

    por prioridad absoluta un % de tiempo para cada cola

    Multicolas con realimentacin: posibilidad de que un proceso se mueva de una cola a otra, p.ej. si cambia su comportamiento Ej. UNIX: un proceso que lleva mucho tiempo en espera se mueve a una cola de ms prioridad

    22

  • Multicolas - ejemplo

    procesos del sistema (FCFS)

    procesos interactivosde profesores (RR)

    procesos interactivosde estudiantes (RR)

    procesos por lotes (FCFS)

    CPU

    23

  • Planificacin en multiprocesadores

    Mismo objetivo que con una CPU, pero ahora ampliamos el nmero de recursos disponibles para atender a los procesos.Sirven las mismas polticas? (FCFS, SJF, RR)Cmo gestionamos la cola de procesos preparados?

    24

  • Multiprocesadores:colas de procesos preparados

    Varias alternativas:Una cola por procesador: A cada proceso de le asigna un procesador y sigue en l toda su vida. Ojo, la carga de trabajo puede quedar mal repartida. Una cola comn: reparto ms equilibrado, pero hay riesgos de inconsistencia si varios procesadores manipulan simultneamente la cola(ej. dos procesadores podran elegir al mismo proceso!!)

    25

    Sistemas OperativosTema 5. Planificacin de procesosContenidoPlanificacin de procesosQu buscamos?Criterios de rendimientoCriterios de rendimiento (2)Modelo del sistema: rfagas de CPU y E/SHistograma de tiempos de rfaga de CPUPolticas expulsivas (preemptive)Despachador (dispatcher)FCFS (en orden de llegada)FCFS:ejemplo de diagrama de GanttFCFS: caractersticasSJF (primero el ms corto)SJF - ejemploSJF - ejemploSJF: inconvenientesPlanificacin por prioridadesTurno rotatorio (Round-Robin)Round Robin: ejercicioInfluencia del cuanto de tiempoMulticolasMulticolas - ejemploPlanificacin en multiprocesadoresMultiprocesadores:colas de procesos preparados