• Author / Uploaded
• Alonso Castro

Citation preview

Round-robin es un m�todo para seleccionar todos los abstractos en un grupo de manera equitativa y en un orden racional, normalmente comenzando por el primer elemento de la lista hasta llegar al �ltimo y empezando de nuevo desde el primer elemento. El nombre del algoritmo viene del principio de Round-Robin conocido de otros campos, donde cada persona toma una parte de un algo compartido en cantidades, es decir, "toma turnos". En operaciones computacionales, un m�todo para ejecutar diferentes procesos de manera concurrente, para la utilizaci�n equitativa de los recursos del equipo, es limitando cada proceso a un peque�o per�odo (quantum), y luego suspendiendo este proceso para dar oportunidad a otro proceso y as� sucesivamente. A esto se le denomina com�nmente como Planificaci�n Round-Robin. �ndice 1 Aplicaci�n circular 1.1 Pasos de ciclos 2 Plani?caci�n circular 3 Aplicaci�n en redes 4 Round-Robin ego�sta Aplicaci�n circular Round-Robin es un algoritmo de planificaci�n de procesos simple de implementar, dentro de un sistema operativo se asigna a cada proceso una porci�n de tiempo equitativa y ordenada, tratando a todos los procesos con la misma prioridad. En Sistemas operativos, la planificaci�n Round-robin da un tiempo m�ximo de uso de CPU a cada proceso, pasado el cual es desalojado y retornado al estado de listo, la lista de procesos se planifica por FIFO, del ingl�s "First In, First Out" (primero en entrar, primero en salir o primero llegado, primero atendido). Pasos de ciclos Para averiguar los pasos de ciclos de procesos totales se toman todos los n�meros de procesos y se calculan con los procesos necesarios para la realizaci�n de estos... Suponga que hay tres procesos y se desea averiguar cuanto tarda. proceso A: 3 veces. proceso B: 4 veces. proceso C: 5 veces. siguiendo {\displaystyle tp=tProceso+[(tProcesoultimo-tProceso)-(tProcesoultimotProcesoproximo)]+tProceso\!} {\displaystyle tp=tProceso+[(tProcesoultimotProceso)-(tProcesoultimo-tProcesoproximo)]+tProceso\!} Plani?caci�n circular Este algoritmo de plani?caci�n, conocido por Round robin, est� dise�ado especialmente para sistemas de tiempo compartido. Se define un intervalo de tiempo denominado "Quantum", cuya duraci�n var�a seg�n el sistema. La cola de procesos se estructura como una cola circular. El plani?cador la recorre asignando un cuanto de tiempo a cada proceso. La organizaci�n de la cola es FIFO. El Quantum se suele implantar mediante un temporizador que genera una interrupci�n cuando se agota el Quantum de tiempo. Si el proceso agota su r�faga de CPU antes de ?nalizar el Quantum, el plani?cador asigna la CPU inmediatamente a otro proceso. Este algoritmo tiene un tiempo de espera relativamente grande. Sin embargo, garantiza un reparto de la CPU entre todos los usuarios y arroja tiempos de respuesta buenos. Como ejemplo, supongamos los siguientes tres procesos en un instante en el sistema: Proceso P1 24 P2 3 P3 3 �tw = 5,66:

Duraci�n de la r�faga tw 6 4 7 Tiempos de proceso y de espera seg�n la plani?caci�n RR.

Vemos que el tiempo de espera podr�a ser inferior, por ejemplo 3 unidades para el algoritmo SJF. Si tenemos n procesos, y un Quantum de tiempo de q, el resultado es que cada trabajo recibe 1/n de tiempo de CPU en Quantum's de q unidades. Ning�n proceso debe esperar m�s de (n - 1)q unidades de tiempo antes de recibir servicio. El rendimiento del algoritmo depende mucho del tama�o del Quantum. Si se utiliza un valor muy grande el algoritmo tiende a degenerar hacia el FCFS. Si el tama�o del Quantum es muy peque�o, el costo de los constantes cambios de contexto degrada mucho el rendimiento del procesador. Hay que tener en cuenta que el porcentaje relativo de cambio de contexto respecto al cuanto, es el porcentaje relativo de p�rdida de la CPU. Una regla emp�rica dice que el cuanto de tiempo debe ser inferior al 80 % de las r�fagas de CPU. Aplicaci�n en redes La planificaci�n Round Robin puede ser aplicada tambi�n a otros problemas de planificaci�n, como la planificaci�n de redes. En las redes inal�mbricas, donde varios servidores comparten un mismo canal, este algoritmo provee a cada servidor un intervalo regular de tiempo para transmitir o recibir informaci�n mediante el canal compartido. Esto hace parecer a Round Robin como un algoritmo justo, pero, de todos modos, por ser mucho menos eficiente que el "algoritmo de proporcionalidad justa", es muy dif�cil proveer un buen servicio a los suscriptores. El operador de la red tambi�n sufrir� capacidad reducida en la red. La causa principal es que este algoritmo no tiene en cuenta el cambio de condiciones de recepci�n en los diferentes receptores, por lo que planear� transmisiones desde/hacia los suscriptores de la mitad de tiempo cuando sus condiciones de recepci�n sean peores que las habituales. En contraste, el planeamiento de proporcionalidad justa tendr� en cuenta el cambio de condiciones de recepci�n en los diferentes receptores y agendar� las transmisiones desde/hacia los suscriptores cada vez que las condiciones de recepci�n est�n peores que lo normal. Round-Robin ego�sta Es una variaci�n del algoritmo normal, con dos colas. En la primera est�n los procesos "aceptados", que se ejecutan compartiendo el tiempo de procesador mediante round-robin. En la segunda est�n los procesos "nuevos", y a ella se incorporan los procesos nuevos que tienen que ser ejecutados. La prioridad de los procesos en ambas colas se incrementa seg�n dos tasas diferentes (siendo mayor la tasa de los procesos "nuevos"), de tal manera que cuando la prioridad de un proceso en la cola de "nuevos" alcanza a la de los procesos "aceptados", se pasa a dicha cola y comienza a ejecutarse, compartiendo el procesador con ellos.