Sistemas Operativos | Conjunto 15

Se han hecho las siguientes preguntas en el examen GATE CS 2006.

1) Considere tres procesos (id de proceso 0, 1, 2 respectivamente) con ráfagas de tiempo de cálculo de 2, 4 y 8 unidades de tiempo. Todos los procesos llegan en el tiempo cero. Considere el algoritmo de programación de tiempo restante más largo primero (LRTF). En LRTF los empates se rompen dando prioridad al proceso con el id de proceso más bajo. El tiempo de respuesta promedio es:
(A) 13 unidades
(B) 14 unidades
(C) 15 unidades
(D) 16 unidades

Respuesta (A)
Sean los procesos p0, p1 y p2. Estos procesos se ejecutarán en el siguiente orden.

  p2  p1  p2  p1  p2  p0  p1   p2   p0   p1   p2
0   4   5   6   7   8   9   10    11   12   13   14 

El tiempo de respuesta de un proceso es el tiempo total entre el envío del proceso y su finalización.
Tiempo de vuelta de p0 = 12 (12-0) Tiempo de
vuelta de p1 = 13 (13-0) Tiempo
de vuelta de p2 = 14 (14-0)

El tiempo promedio de respuesta es (12+13+14)/3 = 13.

2) Considere tres procesos, todos llegando al tiempo cero, con un tiempo total de ejecución de 10, 20 y 30 unidades, respectivamente. Cada proceso dedica el primer 20 % del tiempo de ejecución a realizar E/S, el siguiente 70 % del tiempo a realizar cálculos y el último 10 % del tiempo a realizar E/S nuevamente. El sistema operativo utiliza un primer algoritmo de programación de tiempo de cómputo restante más corto y programa un nuevo proceso cuando el proceso en ejecución se bloquea en E/S o cuando el proceso en ejecución finaliza su ráfaga de cómputo. Suponga que todas las operaciones de E/S se pueden superponer tanto como sea posible. ¿Qué porcentaje de tiempo permanece inactiva la CPU? (A) 0%
(B) 10,6%
(C) 30,0%
(D) 89,4%

Respuesta (B)
Sean tres procesos p0, p1 y p2. Su tiempo de ejecución es de 10, 20 y 30 respectivamente. p0 gasta primero 2 unidades de tiempo en E/S, 7 unidades de tiempo de CPU y finalmente 1 unidad en E/S. p1 gasta las primeras 4 unidades en E/S, 14 unidades de tiempo de CPU y finalmente 2 unidades en E/S. p2 gasta las primeras 6 unidades en E/S, 21 unidades de tiempo de CPU y finalmente 3 unidades en E/S.

 idle   p0    p1     p2    idle
0    2     9     23     44     47

Total time spent = 47
Idle time = 2 + 3 = 5
Percentage of idle time = (5/47)*100 = 10.6 %

3) La instrucción atomic -fetch-and-set x, y establece incondicionalmente la ubicación de memoria x en 1 y obtiene el valor antiguo de x en y sin permitir ningún acceso intermedio a la ubicación de memoria x. Considere la siguiente implementación de las funciones P y V en un semáforo binario.

void P (binary_semaphore *s) {
  unsigned y;
  unsigned *x = &(s->value);
  do {
     fetch-and-set x, y;
  } while (y);
}

void V (binary_semaphore *s) {
  S->value = 0;
}

¿Cuál de las siguientes es verdadera?
(A) Es posible que la implementación no funcione si el cambio de contexto está deshabilitado en P.
(B) En lugar de usar buscar y configurar, se puede usar un par de carga/almacenamiento normales
(C) La implementación de V es incorrecta
(D) El código no implementa un semáforo binario.

Respuesta (A)
Hablemos de la operación P(). Almacena el valor de s en x, luego obtiene el valor anterior de x, lo almacena en y y establece x como 1. El ciclo while de un proceso continuará para siempre si algún otro proceso no ejecuta V() y establece el valor de s como 0. Si el cambio de contexto está deshabilitado en P, el ciclo while se ejecutará para siempre ya que ningún otro proceso podrá ejecutar V().

4) Considere la siguiente instantánea de un sistema que ejecuta n procesos. El proceso i contiene instancias Xi de un recurso R, 1 <= i <= n. Actualmente, todas las instancias de R están ocupadas. Además, para todo i, el proceso i ha realizado una solicitud de instancias Yi adicionales mientras mantiene las instancias Xi que ya tiene. Hay exactamente dos procesos p y q tales que Yp = Yq = 0. ¿Cuál de los siguientes puede servir como condición necesaria para garantizar que el sistema no se acerca a un punto muerto?
(A) min (Xp, Xq) < max (Yk) donde k != p y k != q (B) Xp + Xq >= min (Yk) donde k != p y k != q
(C) max (Xp, Xq) > 1
(D) min (Xp, Xq) > 1

Respuesta (B)
Dado que tanto p como q no necesitan recursos adicionales, ambos pueden terminar y liberar recursos Xp + Xq sin solicitar ningún recurso adicional. Si los recursos liberados por p y q son suficientes para otro proceso que espera los recursos Yk, entonces el sistema no se acerca a un punto muerto.

Consulte GATE Corner para ver todos los documentos/soluciones/explicaciones del año anterior, programa de estudios, fechas importantes, notas, etc.

Escriba comentarios si encuentra que alguna de las respuestas/explicaciones es incorrecta, o si desea compartir más información sobre los temas discutidos anteriormente.