operating system - resueltos - Round Robin Programar: Dos soluciones diferentes: ¿cómo es posible?
round robin scheme (2)
De hecho, no existe un algoritmo RR "correcto". RR es simplemente una familia de algoritmos, basada en el concepto común de programar varias tareas en un orden circular. Las implementaciones pueden variar (por ejemplo, puede considerar prioridades de tarea o puede descartarlas, o puede establecer manualmente la prioridad como una función de la longitud de la tarea o cualquier otra cosa).
Entonces la respuesta es que ambos algoritmos parecen ser correctos, simplemente son diferentes.
Problema:
Cinco trabajos por lotes de la A a la E llegan a un centro de cómputo casi al mismo tiempo. Han estimado tiempos de ejecución de 10, 6, 2, 4 y 8 minutos. Sus prioridades (externamente determinadas) son 3, 5, 2, 1 y 4, respectivamente, siendo 5 la prioridad más alta. Determine el tiempo medio de vuelta del proceso. Ignore la sobrecarga de cambio de proceso. Para Round Robin Scheduling, suponga que el sistema es de multiprogramación y que cada trabajo obtiene la parte justa de la CPU. Todos los trabajos están completamente vinculados a la CPU.
Solución n. ° 1 La siguiente solución proviene de esta página :
Para round robin, durante los primeros 10 minutos, cada trabajo obtiene 1/5 de la CPU. Al final de los 10 minutos, C finaliza. Durante los próximos 8 minutos, cada trabajo obtiene 1/4 de la CPU, luego de lo cual finaliza D. Luego, cada uno de los tres trabajos restantes obtiene 1/3 de la CPU durante 6 minutos, hasta que B finaliza y así sucesivamente. Los tiempos de finalización para los cinco trabajos son 10, 18, 24. 28, 30, por un promedio de 22 minutos.
La solución n.º 2, la siguiente solución proviene de la Universidad de Cornell, se puede encontrar aquí , y es obviamente diferente de la anterior, aunque el problema se da exactamente de la misma forma (esta solución, por cierto, tiene más sentido para mí):
Recuerde que el tiempo de respuesta es la cantidad de tiempo que transcurre entre la llegada del trabajo y la finalización del trabajo. Como asumimos que todos los trabajos llegan en el tiempo 0, el tiempo de respuesta será simplemente el tiempo que completen. (a) Round Robin: La siguiente tabla muestra un desglose de los trabajos que se procesarán durante cada cuántica de tiempo. A * indica que el trabajo se completa durante ese cuanto.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
A B C D E A B C* D E A B D E A B D* E A B E A B* E A E A E* A A*
Los resultados son diferentes: en el primero, C finaliza después de 10 minutos, por ejemplo, mientras que en el segundo, C finaliza después de 8 minutos.
¿Cuál es el correcto y por qué? Estoy confundido .. Gracias de antemano!
Los problemas son diferentes El primer problema no especifica un tiempo cuántico, por lo que debe suponer que el cuanto es muy pequeño en comparación con un minuto. El segundo problema especifica claramente un cuántico de programador de un minuto.
El misterio con la segunda solución es por qué asume que las tareas se ejecutan en orden de letras. Solo puedo suponer que se hizo esta suposición a lo largo del curso, por lo que se esperaría que los estudiantes supieran hacerlo aquí.