ALGORITMOS DE PLANIFICACIÓN




1. FCFS (Primero en llegar, Primero en ser servido)

• Es el algoritmo más simple de implementar
• La cola de Listos se gestiona como una cola FIFO
• (First Input First Output)
• Muy sensible al orden de llegada de los
• procesos/hilos
• Puede producir grandes tiempos de espera

  Ejemplo

Proceso          Duración

P1                   9

P2                   4

P3                   2

• 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, P3    
• Realizar los mismos cálculos suponiendo que llegan en el siguiente orden: P2, P3 y P1.

Tiempos de Espera: P1=0; P2=9; P3=13

Tiempos de Retorno: P1=9; P2=13; P3=15

• Entra en CPU el proceso con la ráfaga de CPU más breve
• Minimiza el tiempo de espera medio
• Riesgo de inanición de los procesos/hilos de larga duración
• Se pueden estimar las próximas ráfagas de CPU de los procesos/hilos según su historia reciente
• Versión expulsiva (SRTF): el proceso en CPU es desalojado si llega a la cola un proceso/hilo con duración más corta (SRTF : Primero se trata el proceso de tiempo restante menor)
  
  

Ejemplo

Proceso          Llegada           Duración

P1                   0                      7

P2                   2                      4

P3                   4                      1

P4                   5                      4

• 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)

SJF no expulsivo

espera media: (0+6+3+7)/4=4

SJF expulsivo

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

• Ventajas:
  • SJF es óptimo en cuánto a reducir el tiempo de espera
• Problemas:
  • Es necesario conocer a priori o predecir el tiempo de servicio del trabajo
  • Existe posibilidad de inanición para trabajos largos

3. SRTF

• Corresponde a SJF con expropiación
• Se planifica como siguiente el que tenga menor tiempo de proceso hasta su término
• Si llega un trabajo con menor tiempo de proceso que el actual en ejecución, lo saca del procesador (expropiación)
• Se debe recordar el tiempo remanente de proceso para cada trabajo desplazado

4. Round Robin (Turno rotatorio - circular)

• Adecuado para implementar tiempo compartido
• Corresponde a FCFS con expropiación
• Cada proceso/hilo dispone de un cuanto de tiempo máximo q
  • Si cuando expira el cuanto de tiempo el proceso continúa en CPU, el planificador lo desaloja y lo ingresa al final de la cola de Listos
• La cola de Listos se gestiona como una cola FIFO
• Se usa en sistemas interactivos
• Evita o reduce el efecto convoy
• Si hay n procesos, cada uno obtiene 1/n del tiempo de la CPU en intervalos de q unidades, como máximo.

Tiempos de Retorno: P1=30; P2=7; P3=10

T. espera Medio: (0+4+7)/3= 3.6

T. espera máximo? : 7 (P3)

• Round Robin. Influencia del cuanto de tiempo (q)
  • La cola de procesos preparados es FIFO
    • Si la ráfaga de CPU > q _ Interrupción TIME-OUT
    • Si la ráfaga de CPU < q_ Liberación de CPU
  • Rendimiento: dependen fuertemente de q
    • q à oo    _ round-robin degenera en FCFS (se pierde interactividad)
    • q à 0 _ CPU/n
  • Mas influencias:
    • Si q es muy pequeño se pierde mucho tiempo en el cambio de contexto (overhead). Disminuye la eficacia del procesador
    • Si q es grande, los tiempos de respuesta aumentan
  • Problema: sólo existe una cola de trabajos preparados, no distingo entre tipos de trabajos

SEÑALES

Las señales son interrupciones al proceso

Envío o generación

–      Proceso- Proceso (dentro del grupo) con el kill

–      SO - Proceso