RR

De Manuais Informática - IES San Clemente.
Revisión del 20:31 3 oct 2019 de Bardal (discusión | contribuciones)
(dif) ← Revisión anterior | Revisión actual (dif) | Revisión siguiente → (dif)
Ir a la navegación Ir a la búsqueda

RR (Round-Robin; De roda; Carrusel)

Este algoritmo respecta a quenda de chegada, mais soamente deixa un quanto (q) de tempo o uso da CPU para cada proceso.

Imos ver un exemplo para explicar como traballa o algoritmo RR:

  • Supoñemos a situación seguinte:
  • Tempo de chegada: P1-->0, P2-->5, P3-->4, P4-->2
  • Cola: P1, P4, P3, P2
  • Duración Proceso: P1-->4 ciclos de CPU, P2-->7 ciclos de CPU, P3-->4 ciclos de CPU, P4-->1 ciclo de CPU.
  • Quanto: q=2

sendo,

te|Pi O tempo de espera do Proceso Pi
tr|Pi O tempo de retorno do Proceso Pi

Imos calcular o tempo de espera(te), o tempo medio de espera, o tempo de espera máximo e o tempo de retorno(tr), así como o Diagrama de Gantt correspondente,

RR.png

Como podemos ver na imaxe o primeiro en entrar na CPU é o proceso P1 pois na orde de chegada é o primeiro da cola de procesos. O algoritmo RR determina que ao entrar un proceso esté ocupará a CPU durante un quanto de tempo q, no exemplo q=2, deixando liberada a CPU para o seguinte proceso que a acaparé segundo o algoritmo RR, así:
  1. Ciclo 1 da CPU-Tempo de Chegada 0: Entra o proceso P1 na CPU e acapara 2 ciclos da mesma, quedando para o remate do mesmo outros 2 ciclos -pois a duración deste proceso son 4 ciclos de CPU-.
  2. Ciclo de CPU 3-Tempo de Chegada 2: A continuación entra o proceso P4 que acapararía 2 ciclos de CPU, xa que q=2, mais soamente acapara 1 ciclo de CPU -pois a duración deste proceso é 1 ciclo de CPU-.
  3. Ciclo de CPU 4-Tempo de Chegada 3: Nesta situación aínda non temos ningún outro proceso en cola agás o P1 co cal entrará o P1 outros dous ciclos de CPU, xa que q=2, rematando así o proceso -pois a duración deste proceso son 4 ciclos de CPU-.
  4. Ciclo de CPU 6-Tempo de Chegada 5: Agora entra na CPU o proceso P3, xa que os procesos P3 e P2 están en cola mais o proceso P3 leva máis tempo na mesma -cando debe entrar un proceso na CPU e varios dos que están en cola teñen as mesmas posibilidades ou probabilidades resolvemos este conflicto mediante o algoritmo FCFS-. Así entra o proceso P3 durante 2 ciclos de CPU -quedandolle outros 2 ciclos para o seu remate-.
  5. Ciclo de CPU 8-Tempo de Chegada 7: Logo entra o proceso P2 durante 2 ciclos de CPU -quedándolle 5 ciclos de duración-.
  6. Ciclo de CPU 10-Tempo de Chegada 9: Logo entra de novo P3 2 ciclos de CPU e remata a súa execución.
  7. Ciclo de CPU 12-Tempo de Chegada 11: Entra P2 2 ciclos de CPU -quedándolle 3 ciclos de duración-.
  8. Ciclo de CPU 14-Tempo de Chegada 13: Como agora non existe ningún outro proceso en cola segue entrando na CPU o proceso P2 ata o remate da súa execución.


--ricardofc 24 nov 2008