Los
sistemas operativos usan colas de espera para gestionar los procesos bloqueados
esperando un evento. Responda razonadamente a las siguientes preguntas sobre
este tipo de estructuras.
a)
Analice qué colas de espera se requerirán en los siguientes
operaciones del S.O., especificando a qué entidad estarán asociadas, y en qué
activación del S.O. y bajo qué condiciones se encolarán y desencolarán los
procesos.
b)
En algunos sistemas UNIX, se plantea un esquema alternativo de gestión
de procesos en el que, manteniendo el carácter no expulsivo del sistema
operativo, a un proceso que se bloquea en una cola de espera se le asigna una
prioridad más alta que la de cualquier otro proceso del sistema que no esté en
esta situación (el valor concreto de la prioridad depende del tipo de evento
por el que se bloquea), con independencia de cuál sea la prioridad que tuviera
previamente el proceso. Cuando continúa su ejecución después de desbloquearse,
el proceso ejecuta con esta prioridad muy alta hasta que vuelve a modo usuario,
momento en el que recupera su prioridad original.
1.
¿Cuál
considera que es el motivo de usar esta estrategia?
2.
Debido a
su carácter no expulsivo, los SS.OO. UNIX no proporcionan buen soporte para
procesos con características de tiempo real. A continuación, analice si con la
nueva estrategia, aunque el S.O. siga siendo no expulsivo, mejoraría o
empeoraría el tratamiento de los procesos con estas características.
c)
Se plantea comparar el esquema de gestión de procesos convencional (o
sea, en el que no se altera la prioridad del proceso cuando se bloquea) con el
planteado en el apartado anterior. Supóngase un sistema monoprocesador con un
único disco y un algoritmo de planificación de procesos basado sólo en
prioridades. En este sistema un proceso P1 de prioridad media solicita
leer un bloque de un fichero que no está en la caché y, justo después, sin
terminar la operación anterior, P2 de prioridad baja ejecuta y causa un
fallo en una página de código no habiendo marcos libres y estando modificado el
marco que se pretende reemplazar. Analice cómo será la ejecución de estos
procesos, especificando los cambios de contexto voluntarios e involuntarios que
se produzcan, en los siguientes supuestos:
a)
Antes de analizar cada uno de los
casos planteados, hay que resaltar que el proceso de determinar qué colas se usarán
para gestionar los procesos que están esperando por distintos eventos no tiene
una única solución válida. En un extremo, se podría utilizar una única cola
para todos los procesos bloqueados, sea cuál sea el evento por el que están
esperando. Evidentemente, esta solución requeriría que se almacene para cada
proceso bloqueado cuál es el motivo del bloqueo y conllevaría una gestión
ineficiente, ya que el desencolado de procesos cuando se cumple el evento
correspondiente implicaría recorrer la cola única de bloqueados buscando los
procesos que estaban esperando ese evento. En el otro extremo estaría el
dedicar una cola específica a cada evento individual, que proporciona una
solución más eficiente, aunque requiere un poco más de espacio de almacenamiento
para la información de control de las colas. En los sistemas reales, así como
en esta solución, se usa esta segunda estrategia, aunque para algunos eventos
relacionados, a veces se usa una sola cola. A continuación, se analizan las
operaciones planteadas en el enunciado:
Con respecto al sistema de ficheros, se provocará una operación de lectura cuando un proceso realice una llamada al sistema para leer o escribir datos de un fichero que no están presentes en la caché de bloques (en el caso de la escritura, debe de tratarse de una operación que no involucre a bloques completos, ya que en ese caso se escribe completamente el contenido de los bloques por lo que no sería necesario leerlos del disco). Además, si para traer estos datos requeridos, es necesario expulsar algún bloque modificado, la propia operación de lectura o escritura del fichero requerirá una escritura previa en el disco del bloque expulsado. Además de escrituras debidas a expulsión, habrá escrituras periódicas al disco de los bloques modificados para asegurar que no se pierden datos. Estas escrituras son generalmente realizadas por un proceso del núcleo especializado.
En cuanto al gestor de
memoria, el
tratamiento de los fallos de página del sistema de memoria virtual puede
requerir una lectura del disco, ya sea del sistema de ficheros o del swap,
y de manera similar al caso de los ficheros, pueden necesitar una escritura
previa al dispositivo si es necesario expulsar una página modificada. En el
caso de que se use la técnica del buffering de páginas, habrá escrituras
cuando haya que expulsar páginas modificadas, debido a que no exista un número
suficiente de marcos libres. Como ocurre con el sistema de ficheros, estas
escrituras son habitualmente realizadas por un proceso del núcleo
especializado.
El manejador de disco mantiene una cola
de las peticiones pendientes de satisfacer que hay para cada disco, ya sean
generadas por el sistema de ficheros o por el gestor de memoria. A priori,
puede parecer que bastaría con mantener una cola de procesos bloqueados en
paralelo a la lista de peticiones, tal que cada proceso bloqueado en esta cola
se corresponda con una petición en la lista de peticiones pendientes. Sin
embargo, hay que tener en cuenta que esto no sería suficiente ya que puede
ocurrir que un proceso necesite acceder a un bloque, ya sea por una llamada al
sistema de ficheros o en el tratamiento de un fallo de página, que otro proceso
ha solicitado previamente al manejador de disco pero tal que la petición
todavía no se ha completado (podría haberse iniciado ya la operación o no). En
este caso, no habría que hacer una nueva solicitud al disco, sino bloquear al
segundo proceso en el mismo evento que al proceso previo. La solución habitual
es que haya una cola de procesos bloqueados asociada a cada bloque solicitado
(en el sistema de ficheros la cola puede estar incluida en la cabecera que
describe cada bloque de la caché de bloques; en el gestor de memoria la cola
puede estar en la información contenida en la tabla de marcos para cada página
residente).
Cuando un proceso solicita al manejador
realizar una operación sobre un bloque de un disco y el dispositivo está libre,
se programa la operación en el controlador del dispositivo y el proceso se
bloquea en la cola de procesos asociada al bloque correspondiente. En el caso
de que el disco se encuentre ocupado, se encola la petición y se bloquea al
proceso en la cola asociada al bloque solicitado. Si mientras se sirve la
petición de un bloque, otro proceso intenta acceder al mismo, el sistema de
ficheros o el gestor de memoria, según el caso, detectan que el bloque ya ha
sido pedido pero no se ha completado la operación, con lo que el proceso se
bloquea en la cola asociada al bloque sin necesidad de contactar con el
manejador del disco.
En el momento que termina una operación
en el disco, el controlador genera una interrupción cuya rutina de tratamiento
se encarga, directamente o de forma diferida usando una interrupción software,
de desbloquear a los procesos esperando por ese bloque. Además, si hay
peticiones pendientes, selecciona una usando el algoritmo de planificación del
disco y realiza la programación del controlador.
·
Operaciones
de entrada en un terminal serie o en una consola. En este caso el tratamiento
es similar para ambos tipos de terminales, ya que ambos están dirigidos por
interrupciones, ya sea del puerto serie o del controlador de teclado,
respectivamente. Por cada terminal, será necesario definir una cola de procesos
bloqueados esperando que haya datos disponibles en el mismo. Téngase en cuenta
que, en el caso de que el terminal esté en modo línea, sólo habrá datos
disponibles en el momento que se complete una línea. Cuando un proceso realiza
una llamada al sistema para leer del terminal y no hay datos disponibles en el buffer
de entrada del terminal, se bloqueará en la cola de procesos asociados al
mismo. Al llegar una interrupción del terminal que produzca datos disponibles
para los procesos (nótese que si el terminal está en modo línea, no habrá datos
disponibles hasta que llegue una interrupción correspondiente al carácter de
fin de línea), si hay procesos bloqueados esperando datos, se desbloquearán.
·
Operaciones
de salida en un terminal serie. En este tipo de terminales la salida va también
dirigida por interrupciones. Cada vez que se solicita al puerto serie
transmitir un dato, hay que esperar que llegue la interrupción para poder
enviar el siguiente. Por tanto, es necesario tener una cola de procesos que
quedarán bloqueados mientras se realiza la transmisión de un dato. Cuando un
proceso realiza una llamada al sistema para escribir en un terminal de este
tipo, se copian los datos en el buffer de salida del terminal y será
necesario bloquear al proceso en la cola mientras se transmiten.
·
Operaciones
de salida en una consola. En este caso sólo es necesario copiar en la memoria
de vídeo la información correspondiente a la petición de escritura del proceso,
no requiriéndose bloquear el proceso.
·
Como P1
intenta escribir sobre un byte (escritura incompleta) de un bloque que no está
en la caché de bloques, solicita al manejador ese bloque. Al estar el disco
libre, el manejador programa la operación y el proceso se bloquea en la cola de
espera asociada al bloque solicitado.
·
Al
comprobar si el bloque solicitado por P2 está en la caché de bloques, se
detecta que el bloque ya ha sido solicitado previamente, por lo que P2 se
bloquea en la cola de procesos asociada al bloque (la misma en la que está
P1), sin contactar con el manejador.
·
En el
tratamiento del fallo de página causado por P3 se comprueba que la página no
está residente y se solicita el bloque correspondiente al manejador, que al
comprobar que el disco está ocupado, encola una nueva petición y bloquea al
proceso en la cola asociada al bloque pedido.
·
Cuando P4
provoca un fallo de página, se detecta en la tabla de marcos que la página
requerida ya ha sido solicitada previamente, por lo que P4 se bloquea en la
cola de procesos asociada al bloque (la misma en la que está P2), sin contactar con el manejador.
·
Cuando
llega la primera interrupción del disco, se desbloquean los procesos P1 y P2 y
se programa la siguiente petición.
·
Finalmente,
llega la interrupción correspondiente a la segunda operación, que desbloquea a
P3 y P4.
b)
A continuación, se responde a las preguntas sobre el esquema
alternativo de asignación de prioridad a los procesos.
En
resumen, se da prioridad a los procesos ejecutando el código del sistema operativo
en modo núcleo, de manera que no pueda darse una situación en la que se esté
ejecutando un proceso en modo usuario estando listo un proceso en modo núcleo.
Nótese que, dado el carácter no expulsivo del núcleo de UNIX, mientras se está
ejecutando una llamada al sistema que no bloquea al proceso, no puede entrar a
ejecutar ningún otro proceso. Con esta nueva estrategia, se extiende esta
propiedad no sólo al código de la llamada hasta el bloqueo, sino también al
código de la misma posterior al bloqueo, en el caso de que lo haya.
c)
A continuación, se analizan las trazas de ejecución resultantes para
los distintos casos planteados. Previamente, es conveniente recordar que el
tratamiento de un fallo de página puede causar dos bloqueos al proceso en el
caso de que haya que expulsar una página modificada, como ocurre en el ejemplo
planteado, ejecutándose todo ello dentro de la misma activación del sistema
operativo.
a.
P1
solicita leer un bloque que no está en la caché de bloques. El manejador
programa la operación y el proceso se bloquea en la cola de espera asociada al
bloque solicitado, produciéndose un cambio de contexto voluntario a P2.
b.
P2
provoca un fallo de página. Se solicita el bloque correspondiente al manejador,
que al comprobar que el disco está ocupado, encola una nueva petición y bloquea
al proceso en la cola asociada al bloque pedido. Se produce un cambio de
contexto voluntario al proceso nulo.
c. Se produce una interrupción del disco que, en primer lugar, desbloquea
a P1 que estaba en la cola de procesos asociada al bloque. A continuación,
programa la operación de escritura de la página expulsada solicitada por P2.
Por último, al detectar que el proceso desbloqueado es más prioritario que el
actual, se activa una interrupción software para realizar un cambio de contexto
involuntario diferido.
d. Al finalizar la rutina de tratamiento de la interrupción del disco, se
ejecuta la rutina de tratamiento de la interrupción software, que lleva a cabo
el cambio de contexto involuntario del proceso nulo a P1.
e. P1 termina la
llamada de lectura del fichero y vuelve a modo usuario ejecutando un bucle de
cálculo.
f.
Posteriormente, termina la operación de
escritura produciéndose una interrupción del disco que, desbloquea a P2 que
estaba en la cola de procesos asociada al bloque. Dado que P2 tiene menos
prioridad que P1, no hay cambio de contexto, terminando la rutina de interrupción
y retornando P1 a modo usuario.
g. P1 termina su
ejecución realizando un cambio de contexto voluntario a P2.
h. P2 continúa con la
rutina de tratamiento del fallo programando una lectura del disco y quedando
bloqueado en la
cola de espera asociada al bloque solicitado, produciéndose un cambio de
contexto voluntario al proceso nulo.
i.
Se produce una interrupción del disco que, en
primer lugar, desbloquea a P2 que estaba en la cola de procesos asociada al
bloque. Al detectarse que el proceso desbloqueado es más prioritario que el
actual, se activa una interrupción software para realizar un cambio de contexto
involuntario diferido.
j.
Al finalizar la rutina de tratamiento de la
interrupción del disco, se ejecuta la rutina de tratamiento de la interrupción
software, que lleva a cabo el cambio de contexto involuntario del proceso nulo
a P2.
k. P2 termina la rutina
de tratamiento del fallo de página y vuelve a modo usuario ejecutando la misma
instrucción que causó el fallo.
f.
Posteriormente, termina la operación de
escritura produciéndose una interrupción del disco que, desbloquea a P2 que estaba
en la cola de procesos asociada al bloque. Dado que P2 tiene más prioridad que
P1, ya que al bloquearse obtuvo una prioridad muy alta, se activa una
interrupción software para realizar un cambio de contexto involuntario
diferido.
g. Al finalizar la rutina de tratamiento de la interrupción del disco, se
ejecuta la rutina de tratamiento de la interrupción software, que lleva a cabo
el cambio de contexto involuntario del proceso P1 a P2.
h. P2 continúa con la
rutina de tratamiento del fallo programando una lectura del disco y quedando
bloqueado en la
cola de espera asociada al bloque solicitado, produciéndose un cambio de
contexto voluntario al proceso P1.
i.
P1 continúa con el bucle de cálculo hasta que se produce la
interrupción del disco.
j.
Se produce una interrupción del disco que, en
primer lugar, desbloquea a P2 que estaba en la cola de procesos asociada al
bloque. Al detectarse que el proceso desbloqueado es más prioritario que el
actual, se activa una interrupción software para realizar un cambio de contexto
involuntario diferido.
k. Al finalizar la rutina de tratamiento de la interrupción del disco, se
ejecuta la rutina de tratamiento de la interrupción software, que lleva a cabo
el cambio de contexto involuntario del proceso P1 a P2.
l.
P2 termina la rutina de tratamiento del fallo de página pero, cuando va
a volver a modo usuario, se restaura su prioridad original, por lo que hay un cambio de contexto involuntario del proceso P2 a P1.
m. P1 continúa su
ejecución hasta que termina realizando un cambio de contexto voluntario a P2.