o Controlan la operación de la
computadora en sí.
Programas de aplicación:
o Resuelven problemas para los
usuarios.
En este
contexto, el Sistema Operativo es el programa fundamental de todos los
programas de sistema. El S. O. protege y libera a los programadores de la
complejidad del hardware, colocándose un nivel de software por sobre el
hardware para:
- Controlar
todas las partes del sistema.
- Presentar
al usuario una interfaz o máquina virtual.
El esquema
típico de un sistema de cómputos incluye:
Programas de aplicación:
o Sistema bancario, reservaciones en
una línea aérea, juegos, etc.
Programas de sistema:
o Compiladores, editores, intérpretes
de comandos.
o Sistema Operativo.
Hardware:
o Lenguaje de máquina.
o Microprogramación.
o Dispositivos físicos.
Las
principales características del microprograma son:
- Se
trata de software que generalmente se localiza en la memoria de solo
lectura.
- Busca
las instrucciones de lenguaje de máquina para ejecutarlas como una serie
de pequeños pasos.
- El
conjunto de instrucciones que interpreta define al lenguaje de máquina.
- En
ciertas máquinas se implanta en el hardware y no es en realidad una capa
distinta.
Respecto
del lenguaje de máquina es preciso señalar que:
- Generalmente
posee entre 50 y 300 instrucciones, sirviendo la mayoría para desplazar
datos, hacer operaciones aritméticas y comparar valores.
- Los
dispositivos de e / s (entrada / salida) se controlan al cargar valores en
registros del dispositivo especiales.
Una de las
principales funciones del S. O. es ocultar toda esta complejidad y
brindar al programador un conjunto más conveniente de instrucciones para
trabajar.
El
S. O. se ejecuta en modo central o modo de supervisión, con máxima prioridad y
generalmente con protección por hardware.
Los
compiladores, editores y demás programas se ejecutan en modo usuario.
El
S. O. es la serie de programas, dispuestos ya sea en el software o en la
memoria fija (microcódigo), que hacen al hardware utilizable.
Los
S. O. ponen el “poder computacional básico” del hardware
convenientemente a disposición del usuario, pero consumen parte de ese poder
computacional para funcionar.
Los S. O.
son, en primer lugar, administradores de recursos, siendo el recurso
primario el hardware del sistema (ver Figura 1.1).
Las principales
características de los S. O. son:
- Definir
la “Interfaz del Usuario”.
- Compartir
el hardware entre usuarios.
- Permitir
a los usuarios compartir los datos entre ellos.
- Planificar
recursos entre usuarios.
- Facilitar
la entrada / salida.
- Recuperarse
de los errores.
Los principales
recursos administrados por los S. O. son:
- Procesadores.
- Almacenamiento.
- Dispositivos
de e / s.
- Datos.
Los S. O.
son una interfaz con:
- Operadores.
- Programadores
de aplicaciones.
- Programadores
de sistemas (administradores del S. O.).
- Programas.
- Hardware.
- Usuarios.
El S. O.
debe presentar al usuario el equivalente de una máquina extendida o máquina
virtual que sea mas fácil de programar que el hardware subyacente.
Los
S. O. han estado relacionados históricamente con la arquitectura de las
computadoras en las cuales se ejecutan, razón por la cual su historia puede
analizarse según las siguientes generaciones y sus principales características:
·
Generación
Cero (década de 1940):
o Carencia total de S. O.
o Completo acceso al lenguaje de
máquina.
·
Primera
generación (1945-1955): bulbos y conexiones:
o Carencia de S. O.
o En los años cincuenta comienzan como
transición entre trabajos, haciendo la misma más simple.
·
Segunda
generación (1955-1965): transistores y
sistemas de procesamiento por lotes (batch):
o En los años sesenta aparecen los S.
O. para sistemas compartidos con:
§ Multiprogramación: varios programas de usuarios se
encuentran al mismo tiempo en el almacenamiento principal, cambiando el
procesador rápidamente de un trabajo a otro.
§ Multiprocesamiento: varios procesadores se utilizan en
un mismo sistema para incrementar el poder de procesamiento.
o Posteriormente aparece la independencia
de dispositivo:
§ El programa del usuario especifica
las características de los dispositivos que requieren los archivos.
§ El S. O. asigna los dispositivos
correspondientes según los requerimientos y las disponibilidades.
·
Tercera
generación (1965-1980): circuitos integrados y
multiprogramación:
o Difusión de la multiprogramación:
§ Partición de la memoria en
porciones, con trabajos distintos en cada una de ellas.
§ Aprovechamiento del tiempo de espera
consecuencia de operaciones de e / s, para utilizar la CPU para otros procesos.
o Protección por hardware del
contenido de cada partición de memoria.
o Aparición de técnicas de spooling:
§ Simultaneous Peripheral Operation On
Line: operación simultánea y en línea de periféricos.
§ Almacenamiento de trabajos de
entrada y de salida en dispositivos transitorios rápidos (discos), para
disminuir el impacto de los periféricos mas lentos.
o Son sistemas de modos múltiples,
es decir que deben soportar sistemas de propósitos generales; son
grandes y complejos pero muy poderosos.
o Interponen una capa de software
entre el usuario y el hardware.
o Aparecen los lenguajes de control
de trabajos, necesarios para especificar el trabajo y los recursos
requeridos.
o Soportan timesharing (tiempo
compartido), variante de la multiprogramación con usuarios conectados
mediante terminales en línea, permitiendo la operación en modo interactivo
o conversacional.
o Aparecen los sistemas de tiempo
real, que requieren tiempos de respuesta muy exigentes, especialmente para
usos industriales o militares.
o Se difunden las computadoras de
rango medio.
·
Cuarta
generación (1980-1990): computadoras
personales:
o Aparición de software amigable
con el usuario, destinado a usuarios no profesionales y con una interfase
gráfica muy desarrollada.
o Desarrollo de sistemas operativos
de red y sistemas operativos distribuidos.
o Sistemas operativos de red:
§ Los usuarios están conscientes de la
existencia de varias computadoras conectadas.
§ Cada máquina ejecuta su propio S. O.
local.
§ Son similares a los S. O. de un solo
procesador pero con el agregado de:
§ Controlador de interfaz de la red y
su software de bajo nivel.
§ Software para conexión y acceso a
archivos remotos, etc.
o Sistemas operativos distribuidos:
§ Aparece ante los usuarios como un S.
O. de un solo procesador, aún cuando de soporte a varios procesadores.
§ Los usuarios no son conscientes del
lugar donde se ejecutan sus programas o donde se encuentran sus archivos, ya
que lo debe administrar el S. O. automáticamente.
§ Deben permitir que un programa se
ejecute mediante varios procesadores a la vez, maximizando el paralelismo.
o Aparición de emuladores de terminal
para el acceso a equipos remotos desde computadoras personales (PC).
o Gran énfasis en la seguridad,
en especial por el desarrollo de los sistemas de comunicaciones de datos.
o El S. O. crea un ambiente de trabajo
según el concepto de máquina virtual, que lo aísla del funcionamiento
interno de la máquina.
o Proliferación de sistemas de
bases de datos, accesibles mediante redes de comunicación.
La
interfaz entre el S. O. y los programas del usuario se define como el conjunto
de “instrucciones ampliadas” que proporciona el S. O. y son las “llamadas
al sistema”:
·
Crean,
eliminan y utilizan objetos del software controlados por el S. O.:
o Los más importantes son procesos y
archivos.
Procesos:
·
Es
el concepto central de todos los S. O.
·
Es
básicamente un programa en ejecución.
·
Consta
del programa ejecutable, sus datos y pila, contador y otros registros, además
de la información necesaria para ejecutar el programa.
·
La
información de control relacionada con los procesos se almacena en la tabla
de procesos:
o Es administrada por el S. O.
o Posee un arreglo de estructuras, una
por cada proceso existente en ese momento.
·
Un
proceso (suspendido) consta de:
o Un espacio de dirección.
o Los datos pertinentes de la tabla de
procesos.
·
Un
proceso puede crear procesos hijo y estos nuevos procesos hijo,
conformando un árbol de procesos.
Archivos:
·
Una
de las funciones principales del S. O. es brindar independencia de
dispositivo.
·
Muchos
S. O. soportan el concepto de directorio como una forma de agrupar
archivos.
·
Los
directorios se estructuran jerárquicamente, por lo que a cada archivo le
corresponde una ruta de acceso.
·
Existen
distintos esquemas de seguridad de archivos en los distintos S. O.
Llamadas
al sistema:
·
Permiten
a los programas comunicarse con el S. O. y solicitarle servicios.
·
A
cada llamada le corresponde un procedimiento:
o Pone los parámetros de la llamada en
un lugar especí…co para luego ejecutar una instrucción tipo “trap” de llamada a
procedimiento protegido para iniciar el S. O.
o Luego de “trap” el S. O. recupera el
control , examina los parámetros y si son válidos ejecuta el trabajo
solicitado.
o Luego de terminar, el S. O. coloca
un código de estado en un registro indicando si tuvo éxito o fracaso y ejecuta
una instrucción del tipo “return from trap” para regresar el control al
procedimiento.
o El procedimiento regresa al programa
llamador con un código de estado como un valor de función; dentro de los
parámetros pueden regresar valores adicionales.
Procesos y Administración del Procesador
El
concepto central de cualquier Sistema Operativo es el de proceso: una
abstracción de un programa en ejecución también llamada tarea.
- Un
programa que se está ejecutando.
- Una
actividad asincrónica.
- El emplazamiento
del control de un procedimiento que está siendo ejecutado.
- Aquello
que se manifiesta por la existencia en el Sistema Operativo de un bloque
de control de proceso.
- Aquella
entidad a la cual son asignados los procesadores.
- La
unidad despachable.
En
sistemas de multiprogramación la cpu alterna de programa en programa, en
un esquema de seudo paralelismo, es decir que la cpu ejecuta en cierto
instante un solo programa, intercambiando muy rápidamente entre uno y otro.
El paralelismo
real de hardware se da en las siguientes situaciones:
- En
ejecución de instrucciones de programa con más de un procesador de
instrucciones en uso simultáneamente.
- Con
la superposición de ejecución de instrucciones de programa con la
ejecución de una o más operaciones de entrada / salida.
El objetivo es aumentar el paralelismo en la ejecución.
El modelo
de procesos posee las siguientes características:
- Todo
el software ejecutable, inclusive el Sistema Operativo, se organiza en
varios procesos secuenciales o procesos.
- Un
proceso incluye al programa en ejecución y a los valores activos del
contador, registros y variables del mismo.
- Conceptualmente
cada proceso tiene su propia CPU virtual.
- Si la
cpu alterna entre los procesos, la velocidad a la que ejecuta un proceso
no será uniforme, por lo que es necesario aclarar lo siguiente:
- Que los procesos no deben programarse con hipótesis
implícitas acerca del tiempo.
- Que normalmente la mayoría de los procesos no son
afectados por la multiprogramación subyacente de la CPU o las velocidades
relativas de procesos distintos.
- Un
proceso es una actividad de un cierto tipo, que tiene un programa,
entrada, salida y estado.
- Un
solo procesador puede ser compartido entre varios procesos con cierto “algoritmo
de planificación” , el cual determina cuándo detener el trabajo en un
proceso y dar servicio a otro distinto (ver Figura 2.1).
En cuanto a las jerarquías de procesos es necesario señalar que los Sistemas Operativos deben disponer de una forma de crear y destruir procesos cuando se requiera durante la operación, teniendo además presente que los procesos pueden generar procesos hijos mediante llamadas al Sistema Operativo, pudiendo darse ejecución en paralelo.
Respecto
de los estados del proceso deben efectuarse las siguientes
consideraciones:
- Cada
proceso es una entidad independiente pero frecuentemente debe interactuar
con otros procesos (ver Figura 2.2).
- Los
procesos pueden bloquearse en su ejecución porque:
- Desde el punto de vista lógico no puede continuar
porque espera datos que aún no están disponibles.
- El Sistema Operativo asignó la cpu a otro proceso.
- Los
estados que puede tener un proceso
son (ver Figura 2.3):
- En ejecución: utiliza la cpu en el instante dado.
- Listo:
ejecutable, se detiene en forma temporal para que se ejecute otro
proceso.
- Bloqueado: no se puede ejecutar debido a la ocurrencia de
algún evento externo.
- Son
posibles cuatro transiciones entre estos estados.
Durante su existencia un proceso
pasa por una serie de estados discretos, siendo varias las circunstancias que
pueden hacer que el mismo cambie de estado.
Debido a ello se puede establecer
una “Lista de Listos” para los procesos “listos” y una “Lista de Bloqueados”
para los “bloqueados”.
La “Lista de Listos” se
mantiene en orden prioritario y la “Lista de Bloqueados” está
desordenada, ya que los procesos se desbloquean en el orden en que tienen lugar
los eventos que están esperando.
Al admitirse un trabajo en el
sistema se crea un proceso equivalente y es insertado en la última parte de la “Lista
de Listos”.
La asignación de la cpu al primer
proceso de la “Lista de Listos” se denomina “Despacho”, que es ejecutado
por una entidad del Sistema Operativo llamada “Despachador”.
El “Bloqueo” es la única transición
de estado iniciada por el propio proceso del usuario, puesto que las otras
transiciones son iniciadas por entidades ajenas al proceso.
La manifestación de un proceso en un
Sistema Operativo es un “Bloque de Control de Proceso” (PCB) con
información que incluye:
- Estado actual del proceso.
- Identificación única del proceso.
- Prioridad del proceso.
- Apuntadores para localizar la memoria del proceso.
- Apuntadores Para asignar recursos.
- Área para preservar registros.
Cuando el Sistema Operativo cambia la atención de la cpu entre los procesos, utiliza las áreas de preservación del PCB para mantener la información que necesita para reiniciar el proceso cuando consiga de nuevo la CPU.
Los sistemas que administran los
procesos deben poder crear, destruir, suspender, reanudar, cambiar la
prioridad, bloquear, despertar y despachar un proceso.
La “creación” de un proceso significa:
- Dar nombre al proceso.
- Insertar un proceso en la lista del sistema de procesos
conocidos.
- Determinar la prioridad inicial del proceso.
- Crear el bloque de control del proceso.
- Asignar los recursos iníciales del proceso.
Un proceso puede “crear un nuevo proceso”, en cuyo caso el proceso creador se denomina “proceso padre” y el proceso creado “proceso hijo” y se obtiene una “estructura jerárquica de procesos”.
La “destrucción” de un proceso implica:
- Borrarlo del sistema.
- Devolver sus recursos al sistema.
- Purgarlo de todas las listas o tablas del sistema.
- Borrar su bloque de control de procesos.
Un proceso “suspendido” no puede proseguir hasta que otro proceso lo reanude. Reanudar (reactivar) un proceso implica reiniciarlo en el punto donde fue suspendido.
La “destrucción” de un
proceso puede o no significar la destrucción de los procesos hijos, según el
Sistema Operativo. Generalmente se denomina “Tabla de Procesos” al
conjunto de información de control sobre los distintos procesos.
Una “interrupción” es un evento que
altera la secuencia en que el procesador ejecuta las instrucciones; es un hecho
generado por el hardware del computador.
Cuando ocurre una interrupción, el Sistema Operativo:
- Obtiene el control.
- Salva el estado del proceso interrumpido, generalmente
en su bloque de control de procesos.
- Analiza la interrupción.
- Transfiere el control a la rutina apropiada para la
manipulación de la interrupción.
Una interrupción puede ser iniciada por un proceso en estado de ejecución o por un evento que puede o no estar relacionado con un proceso en ejecución.
Generalmente las interrupciones
se pueden clasificar por tipos según el siguiente detalle (ver Tabla
2.1:
- “SVC (llamada al supervisor)”: es
una petición generada por el usuario para un servicio particular del
sistema, por ejemplo, realización de Entrada / Salida u obtención de más
memoria.
- “Entrada / Salida”: son
iniciadas por el hardware de Entrada / Salida, indicando a la CPU que ha
cambiado el estado de un canal o dispositivo, por ejemplo, finalización de
Entrada / Salida u ocurrencia de un error.
- “Externas”: son causadas por distintos
eventos, por ejemplo, expiración de un cuanto en un reloj de interrupción
o recepción de una señal de otro procesador en un sistema multiprocesador.
- “De reinicio”: ocurren
al presionar la “tecla de reinicio” o cuando llega una instrucción de
reinicio de otro procesador en un sistema multiprocesador.
- “De verificación de programa”: son
causadas por errores producidos durante la ejecución de procesos, por
ejemplo:
- Un intento de dividir por
cero.
- Un intento de un proceso de
usuario de ejecutar una instrucción privilegiada.
- Un intento de ejecutar un
código de operación inválido.
- “De verificación de máquina”: son
ocasionadas por un mal funcionamiento del hardware.
Tipo de Interrupción
|
Descripción
|
SVC
|
Llamada al Sistema Operativo
|
Entrada / Salida
|
Cambio de estado de un canal o dispositivo
|
Externa
|
Evento externo al sistema
|
De Reinicio
|
Reinicio del procesamiento
|
De Verificación de Programa
|
Errores de procesos
|
De Verificación de Máquina
|
Errores de hardware
|
Tabla 2.1: Tipos de
interrupciones.
|
|
El Sistema Operativo incluye rutinas
llamadas “Manipuladores de Interrupciones (IH)” para procesar cada tipo
diferente de interrupción.
Cuando se produce una interrupción el Sistema Operativo efectúa las siguientes acciones:
Cuando se produce una interrupción el Sistema Operativo efectúa las siguientes acciones:
- Salva el estado del proceso interrumpido.
- Dirige el control al manipulador de interrupciones
adecuado.
- Se aplica la técnica de “Cambio de Contexto” .
Los Sistemas Operativos instrumentan información de control que puede aparecer como las “Palabras de Estado de Programa (PSW)”, las cuales controlan el orden de ejecución de las instrucciones y contienen información sobre el estado del proceso.
Existen tres tipos de PSW, que son
la “actual”, la “nueva” y la “vieja”.
La “PSW Actual” almacena la
dirección de la próxima instrucción que será ejecutada e indica los tipos de
instrucciones actualmente “habilitadas” e inhabilitadas”.
En un sistema uniprocesador existe:
- Solo una PSW actual.
- Seis PSW nuevas (una para cada tipo de interrupción).
- Seis PSW viejas (una para cada tipo de interrupción).
La PSW nueva para un tipo de interrupción dado contiene la dirección en el hardware donde reside el manipulador de interrupciones para este tipo específico.
Cuando ocurre una interrupción para
la cual el procesador no está inhabilitado, ocurren las siguientes acciones:
- El hardware cambia las PSW en los casos siguientes:
- Al almacenar la PSW actual en
la PSW vieja, para este tipo de interrupción.
- Al almacenar la PSW nueva en
la PSW actual, para este tipo de interrupción.
- Luego de este “intercambio de PSW”:
- La PSW actual contiene la
dirección del manipulador de interrupción adecuado.
- El manipulador de
interrupciones procesa la interrupción.
- Luego de procesar la
interrupción, la cpu es enviada al:
- Proceso que estaba en
ejecución en el momento de la interrupción, o al
- Proceso de listo de más alta
prioridad.
- La acción precedente depende
de si el proceso de interrupción es:
- “Apropiativo”:
obtiene la cpu solo si no hay procesos de listos.
- “No apropiativo”:
obtiene de nuevo la cpu.
El “núcleo” del Sistema
Operativo controla todas las operaciones que implican procesos y representa
solo una pequeña porción del código de todo el Sistema Operativo pero es de
amplio uso.
Generalmente permanece en el
almacenamiento primario.
El proceso de interrupciones se
incluye en el núcleo ya que debe ser rápido (especialmente en sistemas
multiusuario), para optimizar el uso de los recursos del sistema y proveer
tiempos de respuesta aceptables a los usuarios interactivos.
El núcleo inhabilita las
interrupciones mientras responde a una interrupción. Las interrupciones son
habilitadas de nuevo después de completar el proceso de una interrupción.
El núcleo del Sistema
Operativo generalmente realiza las siguientes funciones:
- Manipulación de interrupciones.
- Creación y destrucción de procesos.
- Cambio de estados de procesos.
- Despacho.
- Suspensión y reanudación de procesos.
- Sincronización de procesos.
- Comunicación entre procesos.
- Manipulación de bloques de control de proceso.
- Soporte de las actividades de Entrada / Salida.
- Soporte de la asignación y desasignación de
almacenamiento.
- Soporte del sistema de archivos.
- Soporte de un mecanismo de llamada / regreso al
procedimiento.
- Soporte de ciertas funciones contables (estadísticas)
del sistema.
Cuando más de un proceso es
ejecutable desde el punto de vista lógico, el Sistema Operativo debe decidir
cuál de ellos debe ejecutarse en primer término.
El Planificador es la porción
del Sistema Operativo que decide y el Algoritmo de Planificación es el
utilizado.
Los principales “criterios”
respecto de un buen algoritmo de planificación son la equidad, la eficacia, el
tiempo de respuesta, el tiempo de regreso y el rendimiento (ver Tabla 2.2).
Criterio
|
Descripción
|
Equidad
|
Garantizar que cada proceso obtiene su proporción justa de
la cpu
|
Eficacia
|
Mantener ocupada la cpu el ciento por ciento del tiempo
|
Tiempo de respuesta
|
Minimizar el tiempo de respuesta para los usuarios
interactivos
|
Tiempo de regreso
|
Minimizar el tiempo que deben esperar los usuarios por
lotes (batch) para obtener sus resultados
|
Rendimiento
|
Maximizar el número de tareas
procesadas por hora
|
Tabla 2.2: Criterios de un buen
algoritmo de planificación.
|
|
Algunas de estas metas son
contradictorias, por ejemplo, minimizar el tiempo de respuesta para los
usuarios interactivos significaría no ejecutar las tareas batch.
Cada proceso es único e
impredecible, es decir que pueden requerir intensivamente operaciones de
Entrada / Salida o intensivamente cpu; el planificador del Sistema Operativo no
tiene la certeza de cuánto tiempo transcurrirá hasta que un proceso se bloquee,
ya sea por una operación de Entrada / Salida o por otra razón .
Para evitar que un proceso se
apropie de la cpu un tiempo excesivo, los equipos poseen un dispositivo que
provoca una interrupción en forma periódica, por ejemplo 60 hz, o sea sesenta
veces por segundo.
En cada interrupción del reloj el
Sistema Operativo decide si el proceso que se está ejecutando continúa o si el
proceso agotó su tiempo de cpu y debe suspenderse y ceder la cpu a otro
proceso.
Los principales conceptos
relacionados con Planificación del Procesador son los siguientes:
- Planificación apropiativa: es
la estrategia de permitir que procesos ejecutables (desde el punto de
vista lógico) sean suspendidos temporalmente.
- Planificación no apropiativa: es
la estrategia de permitir la ejecución de un proceso hasta terminar.
- Planificación del procesador:
determinar cuándo deben asignarse los procesadores y a qué procesos, lo
cual es responsabilidad del Sistema Operativo.
Se consideran tres niveles
importantes de planificación, los que se detallan a continuación (ver Figura2.4):
- Planificación de alto nivel:
- También se denomina
Planificación de trabajos.
- Determina a qué trabajos se
les va a permitir competir activamente por los recursos del sistema, lo
cual se denomina Planificación de admisión.
- Planificación de nivel intermedio:
- Determina a qué procesos se
les puede permitir competir por la cpu.
- Responde a fluctuaciones a
corto plazo en la carga del sistema y efectúa “suspensiones” y
“activaciones” (“reanudaciones”) de procesos.
- Debe ayudar a alcanzar ciertas
metas en el rendimiento total del sistema.
- Planificación de bajo nivel:
- Determina a qué proceso listo
se le asigna la CPU cuando esta queda disponible y asigna la cpu al
mismo, es decir que “despacha” la CPU al proceso.
- La efectúa el Despachador
del Sistema Operativo, el que opera muchas veces por segundo y reside
siempre en el almacenamiento primario.
Los distintos Sistemas Operativos utilizan varias Políticas de Planificación, que se instrumentan mediante Mecanismos de Planificación.
Tipos de Planificación
Ciertos trabajos se planifican para
ser terminados en un tiempo específico o plazo fijo. Es una planificación
compleja debido a los siguientes factores:
- El usuario debe suministrar anticipadamente una lista precisa
de recursos necesarios para el proceso, pero generalmente no se dispone de
dicha información.
- La ejecución del trabajo de plazo fijo no debe producir
una grave degradación del servicio a otros usuarios.
- El sistema debe planificar cuidadosamente sus necesidades
de recursos hasta el plazo fijo, lo que se puede complicar con las
demandas de recursos de nuevos procesos que ingresen al sistema.
- La concurrencia de varios procesos de plazo fijo
(activos a la vez) puede requerir métodos sofisticados de optimización.
- La administración intensiva de recursos puede generar
una considerable sobrecarga adicional.
Se establecen compromisos de
desempeño con el proceso del usuario, por ejemplo, si existen “n”
procesos en el sistema, el proceso del usuario recibirá cerca del “1 / n”
de la potencia de la cpu.
El sistema debe tener un registro
del tiempo de cpu que cada proceso ha tenido desde su entrada al sistema y del
tiempo transcurrido desde esa entrada.
Con los datos anteriores y el registro
de procesos en curso de ejecución, el sistema calcula y determina qué procesos
están más alejados por defecto de la relación “1 / n” prometida y
prioriza los procesos que han recibido menos cpu de la prometida.
Es muy simple, los procesos se
despachan de acuerdo con su tiempo de llegada a la cola de listos.
Una vez que el proceso obtiene la CPU,
se ejecuta hasta terminar, ya que es una disciplina “no apropiativa”.
Suele utilizarse integrado a otros
esquemas, por ejemplo, de la siguiente manera:
- Los procesos se despachan con algún esquema de
prioridad.
- Los procesos con igual prioridad se despachan “FIFO”.
Los procesos se despachan en “FIFO”
y disponen de una cantidad limitada de tiempo de cpu, llamada “división de
tiempo” o “cuanto”.
Si un proceso no termina antes de
expirar su tiempo de cpu ocurren las siguientes acciones:
- La CPU es apropiada.
- La CPU es otorgada al siguiente proceso en espera.
- El proceso apropiado es situado al final de la lista de
listos.
Es efectiva en ambientes de tiempo compartido.
La sobrecarga de la apropiación se
mantiene baja mediante mecanismos eficientes de intercambio de contexto y con
suficiente memoria principal para los procesos.
La determinación del tamaño del
cuanto es decisiva para la operación efectiva de un sistema computacional.
Los interrogantes son: ¿cuánto
pequeño o grande?, ¿cuánto fijo o variable? y ¿cuánto igual para todos los
procesos de usuarios o determinado por separado para cada uno de ellos?.
Si el cuanto se hace muy grande,
cada proceso recibe todo el tiempo necesario para llegar a su terminación, por
lo cual la asignación en rueda (“RR”) degenera en “FIFO”. Si el cuanto se hace muy pequeño, la
sobrecarga del intercambio de contexto se convierte en un factor dominante y el
rendimiento del sistema se degrada, puesto que la mayor parte del tiempo de cpu
se invierte en el intercambio del procesador (cambio de contexto) y los
procesos de usuario disponen de muy poco tiempo de CPU.
El cuanto debe ser lo suficientemente grande como para
permitir que la gran mayoría de las peticiones interactivas requieran de menos
tiempo que la duración del cuanto, es decir que el tiempo transcurrido desde el
otorgamiento de la CPU a un proceso hasta que genera una petición de Entrada /
Salida debe ser menor que el cuanto establecido, de esta forma, ocurrida la
petición la cpu pasa a otro proceso y como el cuanto es mayor que el tiempo
transcurrido hasta la petición de Entrada / Salida, los procesos trabajan al
máximo de velocidad, se minimiza la sobrecarga de apropiación y semaximiza la
utilización de la
Entrada / Salida.
Entrada / Salida.
El cuanto óptimo varía de un sistema
a otro y con la carga, siendo un valor de referencia 100 mseg (cien
milisegundos).
Es una disciplina no apropiativa y
por lo tanto no recomendable en ambientes de tiempo compartido.
El proceso en espera con el menor
tiempo estimado de ejecución hasta su terminación es el siguiente en
ejecutarse.
Los tiempos promedio de espera son
menores que con “FIFO”.
Los tiempos de espera son menos
predecibles que en “FIFO”.
Favorece a los procesos cortos en
detrimento de los largos.
Tiende a reducir el número de
procesos en espera y el número de procesos que esperan detrás de procesos
largos.
Requiere un conocimiento preciso del
tiempo de ejecución de un proceso, lo que generalmente se desconoce.
Se pueden estimar los tiempos en
base a series de valores anteriores.
Es la contraparte apropiativa del
SJF.
Es útil en sistemas de tiempo
compartido.
El proceso con el tiempo estimado de
ejecución menor para …analizar es el siguiente en ser ejecutado.
Un proceso en ejecución puede ser
apropiado por un nuevo proceso con un tiempo estimado de ejecución menor.
Tiene mayor sobrecarga que la
planificación SJF.
Debe mantener un registro del tiempo
de servicio transcurrido del proceso en ejecución, lo que aumenta la
sobrecarga.
Los trabajos largos tienen un
promedio y una varianza de los tiempos de espera aún mayor que en SJF.
La apropiación de un proceso a punto
de terminar por otro de menor duración recién llegado podría significar un
mayor tiempo de cambio de contexto (administración del procesador) que el
tiempo de finalización del primero.
Al diseñarse los Sistemas Operativos
se debe considerar cuidadosamente la sobrecarga de los mecanismos de administración
de recursos comparándola con los beneficios esperados.
Corrige algunas de las debilidades
del SJF, tales como el exceso de perjuicio hacia los procesos (trabajos) largos
y el exceso de favoritismo hacia los nuevos trabajos cortos.
Es una disciplina no apropiativa.
La prioridad de cada proceso está en
función no sólo del tiempo de servicio del trabajo, sino que también influye la
cantidad de tiempo que el trabajo ha estado esperando ser servido.
Cuando un proceso ha obtenido la
cpu, corre hasta terminar.
Las prioridades, que son dinámicas,
se calculan según la siguiente fórmula, donde pr es la “prioridad”,
te es el “tiempo de espera” y ts es
el “tiempo de servicio”:
Considera factores externos al
proceso.
Las ideas centrales son que cada
proceso tiene asociada una prioridad y que el proceso ejecutable con máxima
prioridad es el que tiene el permiso de ejecución.
Los procesos de alta prioridad
podrían ejecutar indefinidamente, ya que el planificador del sistema puede
disminuir la prioridad del proceso en ejecución en cada interrupción del reloj.
Las prioridades también pueden ser
asignadas dinámicamente por el sistema para lograr ciertas metas relacionadas
con el procesador o la Entrada / Salida.
Los procesos limitados por la
Entrada / Salida (requerimientos intensivos de Entrada / Salida) ocupan mucho
de su tiempo en espera de operaciones de Entrada / Salida, por lo tanto:
- Deben tener prioridad para usar la CPU y efectuar la
siguiente petición de Entrada / Salida, ya que se ejecutará (la operación
de Entrada / Salida) en paralelo con otro proceso que utilice la CPU.
- Si deben esperar mucho tiempo a la CPU estarán ocupando
memoria por un tiempo innecesario.
Un algoritmo sencillo consiste en establecer que la
prioridad sea “1 / f”, donde “f” es la fracción del último cuanto
utilizado por el proceso.
Un proceso que utilice 2 mseg (dos
milisegundos) de su cuanto de 100 mseg (cien milisegundos) tendrá prioridad 50
(cincuenta).
Un proceso que se ejecutó 50 mseg
antes del bloqueo tendrá prioridad 2.
Un proceso que utilizó todo el
cuanto tendrá prioridad 1.
Frecuentemente los procesos se
agrupan en “Clases de Prioridad”, en cuyo caso se utiliza la
Planificación con Prioridades entre las clases y con Round Robin (RR) dentro de
cada clase. Si las prioridades no se reajustan en algún momento, los procesos
de las clases de prioridad mínima podrían demorarse indefinidamente.
Proporcionan una estructura para
lograr los siguientes objetivos:
- Favorecer trabajos cortos.
- Favorecer trabajos limitados por la Entrada / Salida
para optimizar el uso de los dispositivos de Entrada / Salida.
- Determinar la naturaleza de un trabajo lo más rápido
posible y planificar el trabajo (proceso) en consecuencia.
Un nuevo proceso entra en la red de línea de espera al final
de la cola superior.
Se mueve por esta cola “FIFO” hasta
obtener la CPU.
Si el trabajo termina o abandona la CPU
para esperar por la terminación de una operación de Entrada / Salida o la
terminación de algún otro suceso, el trabajo abandona la red de línea de
espera.
Si su cuanto expira antes de
abandonar la CPU voluntariamente, el proceso se coloca en la parte trasera de
la cola del siguiente nivel inferior.
El trabajo recibe servicio al llegar
a la cabeza de esta cola si la primera está vacía.
Mientras el proceso continúe
consumiendo totalmente su cuanto en cada nivel, continuará moviéndose hacia el
final de las colas inferiores.
Generalmente hay una cola en la
parte más profunda a través de la cual el proceso circula en asignación de
rueda hasta que termina.
Existen esquemas en los que el
cuanto otorgado al proceso aumenta a medida que el proceso se mueve hacia las
colas de los niveles inferiores, en tal caso, cuanto más tiempo haya estado el
proceso en la red de línea de espera, mayor será su cuanto cada vez que obtiene
la cpu y no podrá obtener la CPU muy a menudo debido a la mayor prioridad de
los procesos de las colas superiores.
Un proceso situado en una cola dada
no podrá ser ejecutado hasta que las colas de los niveles superiores estén
vacías.
Un proceso en ejecución es apropiado
por un proceso que llegue a una cola superior.
Es un mecanismo adaptable, es decir
que se adapta a cargas variables.
A los efectos de una revisión
gráfica de lo enunciado precedentemente, ver la figura 2.5.
Puede ocurrir que haya procesos con
muchos procesos hijos ejecutándose bajo su control, por ejemplo, un proceso en
un DBMS con procesos hijos atendiendo funciones específicas, tales como,
análisis de interrogantes, acceso a discos, etc.
Es posible que el proceso principal
(padre) pueda identificar la importancia (o criticidad) de sus procesos hijos,
pero los planificadores analizados no aceptan datos de los procesos de usuario
relativos a decisiones de planificación.
La solución es separar el mecanismo
de planificación de la política de planificación, para ello se parametriza
el algoritmo de planificación y los parámetros pueden ser determinados por
medio de procesos del usuario; así el mecanismo está en el núcleo del Sistema
Operativo pero la política queda establecida por un proceso del usuario.
Los esquemas analizados hasta ahora
suponen que todos los procesos ejecutables están en la memoria principal.
Si la memoria principal es
insuficiente, ocurrirá lo siguiente:
- Habrá procesos ejecutables que se mantengan en disco.
- Habrá importantes implicaciones para la planificación,
tales como las siguientes:
- El tiempo de alternancia entre
procesos para traer y procesar un proceso del disco es considerablemente
mayor que el tiempo para un proceso que ya está en la memoria principal.
- Es más eficiente el
intercambio de los procesos con un planificador de dos niveles.
El esquema operativo de un
planificador de dos niveles es como sigue:
- Se carga en la memoria principal cierto subconjunto de
los procesos ejecutables.
- El planificador se restringe a ellos durante cierto
tiempo.
- Periódicamente se llama a un planificador de nivel
superior para efectuar las siguientes tareas:
- Eliminar de la memoria los
procesos que hayan permanecido en ella el tiempo suficiente.
- Cargar a memoria los procesos
que hayan estado en disco demasiado tiempo.
- El planificador de nivel inferior se restringe de nuevo
a los procesos ejecutables que se encuentren en la memoria.
- El planificador de nivel superior se encarga de
desplazar los procesos de memoria a disco y viceversa.
Los criterios que podría utilizar el planificador de nivel
superior para tomar sus decisiones son los que se indican a continuación:
- ¿Cuánto tiempo ha transcurrido desde el último
intercambio del proceso?.
- ¿Cuánto tiempo de cpu ha utilizado recientemente el
proceso?.
- ¿Qué tan grande es el proceso? (generalmente los
procesos pequeños no causan tantos problemas en este sentido).
- ¿Qué tan alta es la prioridad del proceso?.
El planificador de nivel superior podría utilizar cualquiera
de los métodos de planificación analizados.
Administración de la Memoria
La
organización y administración de la “memoria principal”, “memoria
primaria” o “memoria real” de un sistema ha sido y es uno de los`
factores más importantes en el diseño de los S. O. Los términos “memoria”
y “almacenamiento” se consideran equivalentes.
Los
programas y datos deben estar en el almacenamiento principal para:
- Poderlos
ejecutar.
- Referenciarlos
directamente.
Se
considera “almacenamiento secundario” o “almacenamiento auxiliar”
al generalmente soportado en discos.
Los
hechos demuestran que generalmente los programas crecen en requerimientos de
memoria tan rápido como las memorias:
- “Ley
de Parkinson parafraseada”: Los programas se desarrollan para ocupar toda
la memoria disponible para ellos.
La parte
del S. O. que administra la memoria se llama “administrador de la memoria”:
- Lleva
un registro de las partes de memoria que se están utilizando y de aquellas
que no.
- Asigna
espacio en memoria a los procesos cuando estos la necesitan.
- Libera
espacio de memoria asignada a procesos que han terminado.
Históricamente
el almacenamiento principal se ha considerado como un recurso costoso, por lo
cual su utilización debía optimizarse.
Por
organización del almacenamiento se entiende la manera de considerar este
almacenamiento:
- ¿ se
coloca un solo programa de usuario o varios ?.
- Si se
encuentran varios programas de usuario:
- ¿ se concede a cada uno la misma cantidad de espacio o
se divide el almacenamiento en porciones o “particiones” de
diferente tamaño ?.
- ¿ se utilizará un esquema rígido de número y tamaño de
particiones o un esquema dinámico y adaptable ?.
- ¿ se requerirá que los trabajos de los usuarios sean
diseñados para funcionar en una partición específica o se permitirá que
se ejecuten en cualquiera donde quepan ?.
- ¿ se requerirá o no que cada trabajo sea colocado en
un bloque contiguo de memoria ?.
Administración del
Almacenamiento
Independientemente del esquema de organización hay que decidir las estrategias que se utilizarán para optimizar el rendimiento.
Independientemente del esquema de organización hay que decidir las estrategias que se utilizarán para optimizar el rendimiento.
Las
“estrategias de administración” deben considerar:
- ¿cuándo
se consigue un nuevo programa para colocar en la memoria?:
- ¿cuando el sistema lo pide específicamente o se
intenta anticiparse a las peticiones?
- ¿dónde
se colocará el programa que se ejecutará a continuación?:
- ¿se prioriza el tiempo de carga o la optimización en
el uso del almacenamiento?
- ¿con
qué criterio se desplazarán programas?
Los
programas y datos tienen que estar en la memoria principal para poder
ejecutarse o ser referenciados. Los
programas y datos que no son necesarios de inmediato pueden mantenerse en el
almacenamiento secundario.
El
almacenamiento principal es más costoso y menor que el secundario pero de
acceso más rápido.
Los
sistemas con varios niveles de almacenamiento requieren destinar recursos para
administrar el movimiento de programas y datos entre niveles (ver Figura 3.1 ).
Están
dirigidas a la obtención del mejor uso posible del recurso del almacenamiento principal.
Se
dividen en las siguientes categorías:
- Estrategias
de búsqueda:
- Estrategias de búsqueda por demanda.
- Estrategias de búsqueda anticipada.
- Estrategias
de colocación.
- Estrategias
de reposición.
Las “estrategias
de búsqueda” están relacionadas con el hecho de cuándo obtener el siguiente
fragmento de programa o de datos para su inserción en la memoria principal.
En
la “búsqueda por demanda” el siguiente fragmento de programa o de datos
se carga al almacenamiento principal cuando algún programa en ejecución lo
referencia.
Se
considera que la “búsqueda anticipada” puede producir un mejor
rendimiento del sistema.
Las
“estrategias de colocación” están relacionadas con la determinación del
lugar de la memoria donde se colocará (cargará) un programa nuevo.
Las
“estrategias de reposición” están relacionadas con la determinación de
qué fragmento de programa o de datos desplazar para dar lugar a los programas
nuevos.
Los
compiladores, ensambladores y cargadores de relocalización:
- Se
usan para producir programas relocalizables que puedan ser ejecutados en
cualquier partición disponible de tamaño suficiente para aceptarlos (ver
Figura 3.6 ).
- Son
más complejos que los absolutos.
- Mejoran
la utilización del almacenamiento.
- Confieren
más flexibilidad en el armado de la carga de procesos.
Si
se utiliza asignación contigua de memoria la protección suele implementarse con
varios “registros de límites” (ver Figura 3.7 y Figura 3.8 ).
Los
extremos superior e inferior de una partición pueden ser:
- Delineados
con dos registros.
- Indicados
el límite inferior o superior y el tamaño de la partición o región.
La
“fragmentación de almacenamiento” ocurre en todos los sistemas
independientemente de su organización de memoria.
En
los S. O. de multiprogramación de partición fija la fragmentación se produce
cuando:
- Los
trabajos del usuario no llenan completamente sus particiones designadas.
- Una
partición permanece sin usar porque es demasiado pequeña para alojar un
trabajo que está en espera.
Los
procesos ocupan tanto espacio como necesitan, pero obviamente no deben superar
el espacio disponible de memoria (ver Figura 3.9).
No
hay límites fijos de memoria, es decir que la partición de un trabajo es su
propio tamaño.
Se
consideran “esquemas de asignación contigua”, dado que un programa debe
ocupar posiciones adyacentes de almacenamiento.
Los
procesos que terminan dejan disponibles espacios de memoria principal llamados “agujeros”:
- Pueden
ser usados por otros trabajos que cuando finalizan dejan otros “agujeros”
menores.
- En
sucesivos pasos los “agujeros” son cada vez más numerosos pero más
pequeños, por lo que se genera un desperdicio de memoria principal.
Combinación
de agujeros (áreas libres)
Consiste
en fusionar agujeros adyacentes para formar uno sencillo más grande.
Se
puede hacer cuando un trabajo termina y el almacenamiento que libera tiene
límites con otros agujeros.
Puede
ocurrir que los agujeros (áreas libres) separados distribuidos por todo el
almacenamiento principal constituyan una cantidad importante de memoria:
- Podría
ser suficiente (el total global disponible) para alojar a procesos
encolados en espera de memoria.
- Podría
no ser suficiente ningún área libre individual (ver Figura 3.10).
La
técnica de compresión de memoria implica pasar todas las áreas ocupadas
del almacenamiento a uno de los extremos de la memoria principal:
- Deja
un solo agujero grande de memoria libre contigua.
- Esta
técnica se denomina “recogida de residuos” (ver Figura 3.11).
Principales desventajas de la compresión
Consume
recursos del sistema (ver Figura 3.12).
El
sistema debe detener todo mientras efectúa la compresión, lo que puede afectar
los tiempos de respuesta.
Implica
la relocalización (reubicación) de los procesos que se encuentran en la
memoria:
- La
información de relocalización debe ser de accesibilidad inmediata.
Una
alta carga de trabajo significa mayor frecuencia de compresión que incrementa
el uso de recursos.
Se
utilizan para determinar el lugar de la memoria donde serán colocados
los programas y datos que van llegando y se las clasifica de la siguiente
manera:
- “Estrategia
de mejor ajuste”:
- Un trabajo nuevo es colocado en el agujero en el cual
quepa de forma más ajustada:
- Debe dejarse el menor espacio
sin usar.
- “Estrategia
de primer ajuste”:
- Un trabajo nuevo es colocado en el primer agujero
disponible con tamaño suficiente para alojarlo.
- “Estrategia
de peor ajuste”:
- Consiste en colocar un programa en el agujero en el
que quepa de la peor manera, es decir en el más grande posible:
- El agujero restante es
también grande para poder alojar a un nuevo programa relativamente
grande.
En
el esquema de “intercambio” los programas del usuario no requieren
permanecer en la memoria principal hasta su terminación.
Una
variante consiste en que un trabajo se ejecuta hasta que ya no puede continuar:
- Cede
el almacenamiento y la CPU al siguiente trabajo.
- La
totalidad del almacenamiento se dedica a un trabajo durante un breve
período de tiempo.
- Los
trabajos son “intercambiados”, dándose que un trabajo puede ser
intercambiado varias veces antes de llegar a su terminación.
Es un
esquema razonable y eficiente para un número relativamente reducido de procesos
de usuarios.
Los sistemas de intercambio fueron los predecesores de los
sistemas de paginación.
El
rendimiento de los sistemas de intercambio mejora al reducir el tiempo de
intercambio:
- Manteniendo
al mismo tiempo varias “imágenes de usuario o imágenes de memoria”
en la memoria principal.
- Retirando
una imagen de usuario de la memoria principal solo cuando es necesario su
almacenamiento para una nueva imagen.
- Incrementando
la cantidad de memoria principal disponible en el sistema.
Las
imágenes de usuario (imágenes de memoria) retiradas del almacenamiento
principal se graban en el almacenamiento secundario (discos).
“Almacenamiento virtual” significa la capacidad de direccionar un espacio de
almacenamiento mucho mayor que el disponible en el almacenamiento primario de
determinado sistema de computación.
Esta
tecnología apareció en 1960 en la Universidad de Manchester (Inglaterra), en el
sistema “Atlas”.
Los
métodos más comunes de implementación son mediante:
- Técnicas
de “paginación”.
- Técnicas
de “segmentación”.
- Una
combinación de ambas técnicas.
Las
direcciones generadas por los programas en su ejecución no son, necesariamente,
aquellas contenidas en el almacenamiento primario (memoria real), ya que las direcciones
virtuales suelen seleccionarse dentro de un número mucho mayor de
direcciones que las disponibles dentro del almacenamiento primario.
La
evolución en las organizaciones de almacenamiento puede resumirse como
sigue:
- Real:
- Sistemas dedicados a un solo usuario.
- Real:
- Sistemas de multiprogramación en memoria real:
- Multiprogramación en
partición fija:
- Absoluta.
- Relocalizable (reubicable).
- Multiprogramación en
partición variable.
- Virtual:
- Multiprogramación en almacenamiento virtual:
- Paginación pura.
- Segmentación pura.
- Combinación paginación /
segmentación.
La
clave del concepto de memoria (almacenamiento) virtual esta en la disociación:
- De
las direcciones a las que hace referencia un programa.
- De
las direcciones disponibles en la memoria real (almacenamiento primario).
Los
principales conceptos son los siguientes:
- “Direcciones
virtuales”:
- Son las referidas por un proceso en ejecución.
- “Direcciones
reales”:
- Son las disponibles dentro del almacenamiento
primario.
- “Espacio
de direcciones virtuales (v)”
de un proceso:
- Es el número de direcciones virtuales a que puede
hacer referencia el proceso.
- “Espacio
de direcciones reales (r)”
de un computador:
- Es el número de direcciones reales disponibles en el
ordenador.
Los
procesos hacen referencia a direcciones virtuales pero éstas deben ejecutarse en el almacenamiento real:
- Las
direcciones virtuales deben ser transformadas dentro de las direcciones
reales, mientras el proceso está en ejecución.
- La traducción
de direcciones deberá hacerse rápidamente para no degradar al sistema.
Existen
varios medios para asociar las direcciones virtuales con las reales (ver Figura
3.13).
Los
mecanismos de “traducción dinámica de direcciones” (dat) convierten las
direcciones virtuales en reales al ejecutarse el proceso.
Las
direcciones contiguas dentro del espacio de direcciones virtuales de un proceso
no tienen por qué ser contiguas dentro del almacenamiento real, a esto se
denomina “contigüidad artificial” (ver Figura 3.14).
Se
deben proporcionar los medios para retener programas y datos en un gran
almacenamiento auxiliar para:
- Permitir
que el espacio de direcciones virtuales de un usuario sea mayor que
el espacio de direcciones reales.
- Soportar
multiprogramación de forma efectiva en un sistema con muchos
usuarios que compartan el almacenamiento real.
Se utiliza
un esquema de almacenamiento de dos niveles (ver Figura 3.15):
- Primer
nivel: “almacenamiento real ”:
- En él se ejecutan los procesos y en él deben estar los
datos para que un proceso pueda referirse a ellos.
- Segundo
nivel: “almacenamiento auxiliar, secundario o adicional ”:
- Generalmente consta de discos de gran capacidad que
pueden mantener los programas y datos que no caben al mismo tiempo en el
más limitado almacenamiento real.
Cuando se
va a ejecutar un proceso su código y datos se pasan al almacenamiento
principal.
El
almacenamiento real es compartido por varios procesos:
- Cada
proceso puede tener un espacio de direcciones virtuales mucho mayor que el
almacenamiento real.
- Solo
se mantiene al mismo tiempo una pequeña parte de los programas y datos de
cada proceso en el almacenamiento real.
Sistemas de Paginación / Segmentación
Ofrecen
las ventajas de las dos técnicas de organización del almacenamiento virtual.
El
tamaño de los segmentos es múltiplo del de las páginas.
No es necesario que todas las páginas de un segmento se
encuentren al mismo tiempo en el almacenamiento primario.
Las
páginas de almacenamiento virtual, que son contiguas en este almacenamiento, no
necesitan ser contiguas en el almacenamiento real.
El
direccionamiento es tridimensional con una dirección de almacenamiento
virtual “v = (s,p,d)”:
- “s” es el número del segmento.
- “p” es el número de página.
- “d” es el desplazamiento en la
página donde se encuentra asignado el elemento deseado.
Se
considera la traducción dinámica de direcciones de virtuales a reales en un
sistema de paginación / segmentación utilizando la combinación de
transformación asociativa / directa (ver Figura 3.31).
El
proceso en ejecución hace referencia a la dirección virtual v = (s,p,d)
(ver Figura 3.32).
Las
páginas de referencia más reciente tienen entradas en un almacenamiento
asociativo.
Se
realiza una búsqueda asociativa para intentar localizar (s,p) en el
almacenamiento asociativo:
- Si se
encuentra (s,p), entonces el marco de página “p ’ ” en el
cual reside dicha página en la memoria real, se concatena al
desplazamiento “d” para formar la dirección de memoria real “r”
correspondiente a la dirección virtual v= (s,p,d).
- Si no
se encuentra (s,p), entonces:
- La dirección base “b” de la tabla de segmentos
se añade al número de segmento “s” formando la dirección “b +
s” de la entrada de la tabla de mapa de segmentos para el segmento “s”
de la memoria real.
- La entrada de la tabla de mapa de segmentos indica la
dirección base “s ’ ” de la tabla de páginas para el segmento “s”.
- El número de página “p” se añade a “s ’ ”
formando la dirección “p + s ’ ” de la entrada en la tabla de
páginas para la página “p” del segmento “s”:
- Indica que “p ’ ” es
el número del marco correspondiente a la página virtual “p”.
- “p ’ ” se concatena con el
desplazamiento “d” formando la dirección real “r ” que
corresponde a la dirección virtual v = (s,p,d).
Si el
segmento “s” no se encuentra en el almacenamiento primario se produce un
“fallo de pérdida de segmento”, cuyo caso el S. O. localiza el segmento
en el almacenamiento secundario, crea una tabla de páginas para el segmento y
carga la página apropiada en el almacenamiento primario, pudiendo producir
reemplazos de páginas.
Si
el segmento “s” está en el almacenamiento primario y si la referencia a
la tabla de mapa de páginas indica que la página deseada no se encuentra en el
almacenamiento primario, se produce un “fallo de pérdida de página”, en
tal caso el S. O. obtiene el control, localiza la página en el almacenamiento
secundario y la carga, pudiendo reemplazar otra página.
Si
una dirección de almacenamiento virtual está más allá del final del segmento se
genera un “fallo de desbordamiento de segmento”, el que debe ser
atendido por el S. O.
Si
los bits de protección indican que la operación que se va a ejecutar en
la dirección virtual referida no se permite, se genera un “fallo de
protección de segmento”, el que también debe ser atendido por el S. O.
Si
se utiliza un mecanismo de transformación directa pura, manteniendo el mapa
completo dentro del almacenamiento primario, la referencia promedio de
almacenamiento virtual requeriría:
- Un
ciclo de almacenamiento para acceder a la tabla de mapa de segmentos.
- Un
segundo ciclo de almacenamiento para hacer referencia a la tabla de
mapa de páginas.
- Un
tercer ciclo de almacenamiento para referenciar al elemento deseado del almacenamiento
real.
Cada
referencia a un elemento comprende tres ciclos de almacenamiento:
- El
sistema correría casi a 1 / 3 de su velocidad nominal.
- La
traducción de direcciones insumiría 2 / 3 del tiempo.
Con la
utilización de registros asociativos (por ej. 16 registros), se logran
velocidades de ejecución del 90 % o más de la velocidad total de procesamiento
de sus procesadores de control.
La
estructura de tablas de procesos, de mapas de segmentos y de mapas de páginas
puede consumir un porcentaje importante del almacenamiento primario cuando se
ejecutan un gran número de procesos.
La
traducción procede mucho más rápido si todas las tablas están en el
almacenamiento primario, lo que resta espacio para los procesos.
Se
implementa disponiendo entradas en tablas de mapa de segmentos para diferentes
procesos que apunten a la misma tabla de mapa de páginas (ver Figura
3.33 ).
El
compartimiento requiere una administración cuidadosa por parte del S. O., ya
sea en sistemas de paginación, segmentación o paginación / segmentación, pues
se debe considerar qué sucedería si una nueva página reemplazara a otra página
compartida por muchos procesos.
Las
diferentes organizaciones de almacenamiento virtual generalmente
implementadas son
- Paginación.
- Segmentación.
- Segmentación
y paginación.
Las
estrategias para la administración de sistemas de almacenamiento virtual
condicionan la conducta de los sistemas de almacenamiento virtual que operan
según esas estrategias.
Se
consideran las siguientes estrategias:
- “Estrategias
de búsqueda”:
- Tratan de los casos en que una página o segmento deben
ser traídos del almacenamiento secundario al primario.
- Las estrategias de “búsqueda por demanda”
esperan a que se haga referencia a una página o segmento por un proceso
antes de traerlos al almacenamiento primario.
- Los esquemas de “búsqueda anticipada” intentan
determinar por adelantado a qué páginas o segmentos hará referencia un
proceso para traerlos al almacenamiento primario antes de ser
explícitamente referenciados.
- “Estrategias
de colocación”:
- Tratan del lugar del almacenamiento primario donde se colocará
una nueva página o segmento.
- Los sistemas toman las decisiones de colocación de una
forma trivial ya que una nueva página puede ser colocada dentro de
cualquier marco de página disponible.
- “Estrategias
de reposición”:
- Tratan de la decisión de cuál página o segmento
desplazar para hacer sitio a una nueva página o segmento cuando el
almacenamiento primario está completamente comprometido.
Las
principales son:
- El
principio de optimización.
- Reposición
de páginas al azar.
- Primero
en entrar - primero en salir.
- Menos
recientemente usada.
- Menos
frecuentemente usada.
- No
usada recientemente.
- Conjuntos
de trabajo.
El
“principio de optimización” indica que para obtener un rendimiento
óptimo, la página que se va a reponer es una que no se va a utilizar en el
futuro durante el período de tiempo más largo.
El
problema es que no es factible predecir el futuro.
Consiste
en escoger al azar la página que va a ser reemplazada.
Todas
las páginas del almacenamiento principal deben tener la misma probabilidad
de ser reemplazadas.
Debe
poder seleccionar cualquier página, incluyendo la que va a ser referenciada a
continuación (peor selección).
Este
esquema es raramente usado.
Administración de archivo
Todas
las aplicaciones computarizadas necesitan almacenar y recuperar la información:
- Superando
las limitaciones del almacenamiento real.
- Trascendiendo
a la duración de los procesos que las utilizan o generan.
- Independizando
a la información de los procesos permitiendo el acceso a la misma a través
de varios procesos.
Las
condiciones esenciales para el almacenamiento de la información a largo plazo
son:
- Debe
ser posible almacenar una cantidad muy grande de información.
- La
información debe sobrevivir a la conclusión del proceso que la utiliza.
- Debe
ser posible que varios procesos tengan acceso concurrente a la
información.
La
solución es el almacenamiento de la información en discos y otros medios
externos en unidades llamadas archivos:
- Los
archivos deben ser persistentes, es decir que no deben verse
afectados por la creación o terminación de un proceso.
- Los
archivos son una colección de datos con nombre.
- Pueden
ser manipulados como una unidad por operaciones como: open, close, create,
destroy, copy, rename, list.
- Los
elementos de datos individuales dentro del archivo pueden ser manipulados
por operaciones como: read, write, update, insert, delete.
El
“Sistema de Archivos” es la parte del sistema de administración del
almacenamiento responsable, principalmente, de la administración de los
archivos del almacenamiento secundario.
Es
la parte del S. O. responsable de permitir “compartir controladamente”
la información de los archivos.
Los
usuarios deben poder crear, modificar y borrar archivos.
Se
deben poder compartir los archivos de una manera cuidadosamente controlada.
El
mecanismo encargado de compartir los archivos debe proporcionar varios tipos de
acceso controlado:
- Ej.: “Acceso
de Lectura”, “Acceso de Escritura”, “Acceso de Ejecución”,
varias combinaciones de estos, etc.
Se debe
poder estructurar los archivos de la manera más apropiada a cada aplicación.
Los
usuarios deben poder ordenar la transferencia de información entre archivos.
Se
deben proporcionar posibilidades de “respaldo” y “recuperación”
para prevenirse contra:
- La
pérdida accidental de información.
- La
destrucción maliciosa de información.
Se debe
poder referenciar a los archivos mediante “Nombres Simbólicos”,
brindando “Independencia de Dispositivos”.
En
ambientes sensibles, el sistema de archivos debe proporcionar posibilidades de “Cifrado”
y “Descifrado”.
El
sistema de archivos debe brindar una interfase favorable al usuario:
- Debe
suministrar una “visión lógica” de los datos y de las funciones que
serán ejecutadas, en vez de una “visión física”.
- El
usuario no debe tener que preocuparse por:
- Los dispositivos particulares.
- Dónde serán almacenados los datos.
- El formato de los datos en los dispositivos.
- Los medios físicos de la transferencia de datos hacia
y desde los dispositivos.
Un
“Archivo” es un conjunto de registros relacionados.
El
“Sistema de Archivos” es un componente importante de un S. O. y suele
contener:
- “Métodos
de acceso”
relacionados con la manera de acceder a los datos almacenados en archivos.
- “Administración
de archivos”
referida a la provisión de mecanismos para que los archivos sean
almacenados, referenciados, compartidos y asegurados.
- “Administración
del almacenamiento auxiliar”
para la asignación de espacio a los archivos en los dispositivos de
almacenamiento secundario.
- “Integridad
del archivo” para
garantizar la integridad de la información del archivo.
El sistema
de archivos está relacionado especialmente con la administración del espacio de
almacenamiento secundario, fundamentalmente con el almacenamiento de disco.
Una
forma de organización de un sistema de archivos puede ser la siguiente:
- Se
utiliza una “raíz” para indicar en qué parte del disco comienza el “directorio
raíz ”.
- El “directorio
raíz” apunta a los “directorios de usuarios”.
- Un “directorio
de usuario” contiene una entrada para cada uno de los archivos del
usuario.
- Cada
entrada de archivo apunta al lugar del disco donde está almacenado el
archivo referenciado.
Los
nombres de archivos solo necesitan ser únicos dentro de un directorio de
usuario dado.
El
nombre del sistema para un archivo dado debe ser único para el sistema de
archivos.
En
sistemas de archivo “jerárquicos” el nombre del sistema para un archivo
suele estar formado como el “nombre de la trayectoria” del directorio
raíz al archivo.
Se
considerará el punto de vista del usuario.
Las
reglas exactas para los nombres de archivos varían de sistema a sistema.
Algunos
sistemas de archivos distinguen entre las letras mayúsculas y minúsculas,
mientras que otros no.
Muchos
S. O. utilizan nombres de archivo con dos partes, separadas por un punto:
- La
parte posterior al punto es la extensión de archivo y generalmente
indica algo relativo al archivo, aunque las extensiones suelen ser meras
convenciones.
Los
archivos se pueden estructurar de varias maneras, las más comunes son:
- “Secuencia
de bytes”:
- El archivo es una serie no estructurada de bytes.
- Posee máxima flexibilidad.
- El S. O. no ayuda pero tampoco estorba.
- “Secuencia
de registros”:
- El archivo es una secuencia de registros de longitud
fija, cada uno con su propia estructura interna.
- “Árbol
”:
- El archivo consta de un árbol de registros, no
necesariamente de la misma longitud.
- Cada registro tiene un campo key (llave
o clave) en una posición fija del registro.
- El árbol se ordena mediante el campo de clave para
permitir una rápida búsqueda de una clave particular.
Muchos
S. O. soportan varios tipos de archivos, por ej.: archivos regulares,
directorios, archivos especiales de caracteres, archivos especiales de bloques,
etc., donde:
- Los Archivos
Regulares son aquellos que contienen información del usuario.
- Los Directorios
son archivos de sistema para el mantenimiento de una estructura del
sistema de archivos.
- Los Archivos
Especiales de Caracteres:
- Tienen relación con la e / s.
- Se utilizan para modelar dispositivos seriales de e /
s (terminales, impresoras, redes, etc.).
- Los Archivos
Especiales de Bloques se utilizan para modelar discos.
Los
tipos de acceso más conocidos son:
- Acceso
Secuencial: el
proceso lee en orden todos los registros del archivo comenzando por el
principio, sin poder:
- Saltar registros.
- Leer en otro orden.
- Acceso
Aleatorio: el
proceso puede leer los registros en cualquier orden utilizando dos métodos
para determinar el punto de inicio de la lectura:
- Cada operación de lectura (read) da la posición en el
archivo con la cual iniciar.
- Una operación especial (seek) establece la posición de
trabajo pudiendo luego leerse el archivo secuencialmente.
Los
sistemas de archivos generalmente contienen información muy valiosa para sus
usuarios, razón por la que los sistemas de archivos deben protegerla.
Se
entenderá por seguridad a los problemas generales relativos a la garantía de
que los archivos no sean leídos o modificados por personal no autorizado; esto
incluye aspectos técnicos, de administración, legales y políticos.
Se
consideraran mecanismos de protección a los mecanismos específicos del sistema
operativo utilizados para resguardar la información de la computadora.
La
frontera entre seguridad y mecanismos de protección no está bien
definida.
Dos
de las más importantes facetas de la seguridad son:
- La
pérdida de datos.
- Los
intrusos.
Algunas de
las causas más comunes de la pérdida de datosson:
- Actos
y hechos diversos, como incendios, inundaciones, terremotos, guerras,
revoluciones, roedores, etc.
- Errores
de hardware o de software, como fallas en la cpu, discos o cintas
ilegibles, errores de telecomunicación, errores en los programas, etc.
- Errores
humanos, por ej., entrada incorrecta de datos, mal montaje de cintas o
discos, ejecución incorrecta de programas, pérdida de cintas o discos,
etc.
La mayoría
de estas causas se pueden enfrentar con el mantenimiento de los respaldos
(back-ups) adecuados; debería haber copias en un lugar alejado de los datos
originales.
Respecto
del problema de los intrusos, se los puede clasificar como:
- Pasivos: solo desean leer archivos que
no están autorizados a leer.
- Activos: desean hacer cambios no
autorizados a los datos.
Para
diseñar un sistema seguro contra intrusos:
- Hay
que tener en cuenta el tipo de intrusos contra los que se desea tener
protección.
- Hay
que ser consciente de que la cantidad de esfuerzo que se pone en la
seguridad y la protección depende claramente de quién se piensa sea el
enemigo.
Algunos tipos
de intrusos son los siguientes:
- Curiosidad
casual de usuarios no técnicos.
- Conocidos
(técnicamente capacitados) husmeando.
- Intentos
deliberados por hacer dinero.
- Espionaje
comercial o militar.
Otro
aspecto del problema de la seguridad es la privacía:
- Protección
de las personas respecto del mal uso de la información en contra de uno
mismo.
- Implica
aspectos legales y morales.
También
debe señalarse la posibilidad del ataque del caballo de Troya:
- Modificar
un programa normal para que haga cosas adversas además de su función
usual.
- Arreglar
las cosas para que la víctima utilice la versión modificada.
Además
debe considerarse la posibilidad de ataques al estilo del gusano de
Internet:
- Fue
liberado por Robert Tappan Morris el 02/11/88 e hizo que se bloquearan la
mayoría de los sistemas Sun y Vax de Internet (fue descubierto y
condenado).
- Constaba
de un programa arrancador y del gusano propiamente dicho.
- Utilizaba
fallas se seguridad del Unix y de los programas Finger y Sendmail de
Internet.
Una forma
de probar la seguridad de un sistema es contratar un grupo de expertos en
seguridad, conocido como el equipo tigre o equipo de penetración,
cuyo objetivo es intentar penetrar el sistema de seguridad para descubrir sus
falencias y proponer soluciones.
Otro
aspecto importante de la seguridad consiste en no subestimar los problemas
que puede causar el personal.
El
diseño del sistema debe ser público, ya que pensar que el intruso no conocerá
la forma de funcionamiento del sistema es un engaño.
El
estado predefinido debe ser el de no acceso, dado que los errores
en donde se niega el acceso válido se reportan más rápido que los errores en
donde se permite el acceso no autorizado.
Verificar
la autorización actual:
- El
sistema no debe:
- Verificar el permiso.
- Determinar que el acceso está permitido.
- Abandonar esta información para su uso posterior.
- El sistema
tampoco debe:
- Verificar el permiso al abrir un archivo y no después
de abrirlo, pues un acceso habilitado permanecería como válido aunque
haya cambiado la protección del archivo.
Dar a cada
proceso el mínimo privilegio posible, lo que implica un esquema de “protección
de grano fino”.
El
mecanismo de protección debe ser simple, uniforme e integrado hasta las
capas más bajas del sistema:
- Dotar
de seguridad a un sistema inseguro es casi imposible.
- La
seguridad no es una característica que se pueda añadir fácilmente.
El esquema
de seguridad debe ser sicológicamente aceptable:
- Los
usuarios no deben sentir que la protección de sus archivos les implica
demasiado trabajo:
- Podrían dejar de proteger sus archivos.
- Se quejarían en caso de problemas.
- No aceptarían fácilmente su propia culpa.
Limitar
los intentos de acceso fallidos y registrarlos.
Registrar
todos los accesos.
Tender
trampas para atrapar a los intrusos.
Muchos
objetos del sistema necesitan protección, tales como la cpu, segmentos
de memoria, unidades de disco, terminales, impresoras, procesos, archivos,
bases de datos, etc..
Cada
objeto se referencia por un nombre y tiene habilitadas un conjunto de operaciones
sobre él.
Un
dominio es un conjunto de parejas (objeto, derechos):
- Cada
pareja determina:
- Un objeto.
- Un subconjunto de las operaciones que se pueden llevar
a cabo en él.
Un derecho
es el permiso para realizar alguna de las operaciones.
Es
posible que un objeto se encuentre en varios dominios con “distintos”
derechos en cada dominio.
Un
proceso se ejecuta en alguno de los dominios de protección:
- Existe
una colección de objetos a los que puede tener acceso.
- Cada
objeto tiene cierto conjunto de derechos.
Los
procesos pueden alternar entre los dominios durante la ejecución.
Una
llamada al S. O. provoca una alternancia de dominio.
En
algunos S. O. los dominios se llaman anillos.
Una
forma en la que el S. O. lleva un registro de los objetos que pertenecen a cada
dominio es mediante una matriz:
- Los
renglones son los dominios.
- Las
columnas son los objetos.
- Cada
elemento de la matriz contiene los derechos correspondientes al objeto en
ese dominio, por ej.: leer, escribir, ejecutar.
Las
“matrices de protección” son muy grandes y con muchos lugares vacíos:
- Desperdician
espacio de almacenamiento.
- Existen
métodos prácticos que almacenan solo los elementos no vacíos por filas o
por columnas.
La lista
de control de acceso (ACL: Access control list):
- Asocia
a cada objeto una lista ordenada con:
- Todos los dominios que pueden tener acceso al objeto.
- La forma de dicho acceso (ej.: lectura (r), grabación
(w), ejecución (x)).
Una forma
de implementar las ACL consiste en:
- Asignar
tres bits (r, w, x) para cada archivo, para:
- El propietario, el grupo del propietario y los demás
usuarios.
- Permitir
que el propietario de cada objeto pueda modificar su ACL en cualquier momento:
- Permite prohibir accesos antes permitidos.
Manejo de E/S y planificación del Disco
Introducción
Una
de las funciones principales de un S. O. es el control de todos los
dispositivos de e / s de la computadora.
Las
principales funciones relacionadas son:
- Enviar
comandos a los dispositivos.
- Detectar
las interrupciones.
- Controlar
los errores.
- Proporcionar
una interfaz entre los dispositivos y el resto del sistema:
- Debe ser sencilla y fácil de usar.
- Debe ser la misma (preferentemente) para todos los
dispositivos (independencia del dispositivo).
El código
de e / s representa una fracción significativa del S. O.
El
uso inapropiado de los dispositivos de e / s frecuentemente genera
ineficiencias del sistema, lo que afecta la performance global.
El
enfoque que se considerará tiene que ver con la interfaz que desde el hardware
se presenta al software:
- Comandos
que acepta el hardware.
- Funciones
que realiza.
- Errores
que puede informar.
Se
pueden clasificar en dos grandes categorías:
- Dispositivos
de bloque.
- Dispositivos
de carácter.
Las
principales características de los dispositivos de bloque son:
- La
información se almacena en bloques de tamaño fijo.
- Cada
bloque tiene su propia dirección.
- Los
tamaños más comunes de los bloques van desde los 128 bytes hasta los 1.024
bytes.
- Se
puede leer o escribir en un bloque de forma independiente de los demás, en
cualquier momento.
- Un
ejemplo típico de dispositivos de bloque son los discos.
Las
principales características de los dispositivos de caracter son:
- La
información se transfiere como un flujo de caracteres, sin sujetarse a una
estructura de bloques.
- No se
pueden utilizar direcciones.
- No
tienen una operación de búsqueda.
- Unos
ejemplos típicos de dispositivos de carácter son las impresoras de línea,
terminales, interfaces de una red, ratones, etc.
Algunos
dispositivos no se ajustan a este esquema de clasificación, por ejemplo los relojes, que no
tienen direcciones por medio de bloques y no generan o aceptan flujos de
caracteres.
El
sistema de archivos solo trabaja con dispositivos de bloque
abstractos, por lo que encarga la parte dependiente del dispositivo
a un software de menor nivel, el software manejador del dispositivo.
Las
unidades de e / s generalmente constan de:
- Un componente
mecánico.
- Un
componente electrónico, el controlador del dispositivo o
adaptador.
Muchos
controladores pueden manejar más de un dispositivo.
El
S. O. generalmente trabaja con el controlador y no con el dispositivo.
Los
modelos más frecuentes de comunicación entre la cpu y los controladores
son:
- Para
la mayoría de las micro y mini computadoras:
- Modelo de bus del sistema.
- Para
la mayoría de los mainframes:
- Modelo de varios buses y computadoras especializadas
en e / s llamadas canales de e / s.
La
interfaz entre el controlador y el dispositivo es con frecuencia de muy
bajo nivel:
- La
comunicación es mediante un flujo de bits en serie que:
- Comienza con un preámbulo.
- Sigue con una serie de bits (de un sector de disco,
por ej.).
- Concluye con una suma para verificación o un código
corrector de errores.
- El preámbulo:
- Se escribe al dar formato al disco.
- Contiene el número de cilindro y sector, el tamaño de
sector y otros datos similares.
El controlador
debe:
- Convertir
el flujo de bits en serie en un bloque de bytes.
- Efectuar
cualquier corrección de errores necesaria.
- Copiar
el bloque en la memoria principal.
Cada
controlador posee registros que utiliza para comunicarse con la cpu:
- Pueden
ser parte del espacio normal de direcciones de la memoria: e / s
mapeada a memoria.
- Pueden
utilizar un espacio de direcciones especial para la e / s, asignando a
cada controlador una parte de él.
El
S. O. realiza la e / s al escribir comandos en los registros de los
controladores; los parámetros de los comandos
también se cargan en los registros de los controladores.
Al
aceptar el comando, la cpu puede dejar al controlador y dedicarse a otro
trabajo.
Al
terminar el comando, el controlador provoca una interrupción para
permitir que el S. O.:
- Obtenga
el control de la cpu.
- Verifique
los resultados de la operación.
La cpu obtiene
los resultados y el estado del dispositivo al leer uno o más bytes de
información de los registros del controlador.
Ejemplos
de controladores, sus direcciones de e / s y sus vectores de
interrupción en la PC IBM pueden verse en la Tabla 5.1.
Controlador
de e / s
|
Dirección
de e / s
|
Vector
de interrupciones
|
Reloj
|
040 -
043
|
8
|
Teclado
|
060 -
063
|
9
|
Disco
duro
|
320 -
32f
|
13
|
Impresora
|
378 -
37f
|
15
|
Disco
flexible
|
3f0 -
3f7
|
14
|
Rs232
primario
|
3f8 -
3ff
|
12
|
Rs232
secundario
|
2f8 -
2ff
|
11
|
Tabla 5.1: Controladores de e / s, direcciones de e / s y
vector de interrupciones.
|
||
Muchos
controladores, especialmente los correspondientes a dispositivos de bloque,
permiten el DMA.
Si
se lee el disco sin DMA:
- El
controlador lee en serie el bloque (uno o más sectores) de la unidad:
- La lectura es bit por bit.
- Los bits del bloque se graban en el buffer interno del
controlador.
- Se
calcula la suma de verificación para corroborar que no existen errores de
lectura.
- El
controlador provoca una interrupción.
- El S.
O. lee el bloque del disco por medio del buffer del controlador:
- La lectura es por byte o palabra a la vez.
- En cada iteración de este ciclo se lee un byte o una
palabra del registro del controlador y se almacena en memoria.
- Se desperdicia
tiempo de la cpu.
DMA
se ideó para liberar a la cpu de este trabajo de bajo nivel.
La
CPU le proporciona al controlador:
- La
dirección del bloque en el disco.
- La
dirección en memoria adonde debe ir el bloque.
- El
número de bytes por transferir.
Luego de
que el controlador leyó todo el bloque del dispositivo a su buffer y de que
corroboró la suma de verificación:
- Copia
el primer byte o palabra a la memoria principal.
- Lo
hace en la dirección especificada por medio de la dirección de memoria de
DMA.
- Incrementa
la dirección DMA y decrementa el contador DMA en el número
de bytes que acaba de transferir.
- Se
repite este proceso hasta que el contador se anula y por lo tanto el
controlador provoca una interrupción.
- Al
iniciar su ejecución el S. O. luego de la interrupción provocada, no debe
copiar el bloque en la memoria, porque ya se encuentra ahí (ver Figura
5.1).
El controlador necesita un buffer interno porque una vez iniciada una
transferencia del disco:
- Los
bits siguen llegando del disco constantemente.
- No
interesa si el controlador está listo o no para recibirlos.
- Si el
controlador intentara escribir los datos en la memoria directamente:
- Tendría que recurrir al bus del sistema para c / u de
las palabras (o bytes) transferidas.
- El bus podría estar ocupado por otro dispositivo y el
controlador debería esperar.
- Si la siguiente palabra llegara antes de que la
anterior hubiera sido almacenada, el controlador la tendría que almacenar
en alguna parte.
Si el
bloque se guarda en un buffer interno:
- El
bus no se necesita sino hasta que el DMA comienza.
- La
transferencia DMA a la memoria ya no es un aspecto crítico del tiempo.
Los
controladores simples no pueden atender la e / s simultánea:
- Mientras
transfieren a la memoria, el sector que pasa debajo de la cabeza del disco
se pierde; es decir que el bloque siguiente al recién leído se pierde.
- La
lectura de una pista completa se hará en dos rotaciones completas, una
para los bloques pares y otra para los impares.
- Si el
tiempo necesario para una transferencia de un bloque del controlador a la
memoria por medio del bus es mayor que el tiempo necesario para leer un
bloque del disco:
- Sería necesario leer un bloque y luego saltar dos o
más bloques.
- El salto de bloques:
- Se ejecuta para darle tiempo
al controlador para la transferencia de los datos a la memoria.
- Se llama separación.
- Al formatear el disco, los
bloques se numeran tomando en cuenta el factor de separación (ver
Figura 5.2).
- Esto permite al S. O.:
- Leer los bloques con
numeración consecutiva.
- Conservar la máxima
velocidad posible del hardware.
·
Un
“buffer” es un área de almacenamiento primario destinada a contener datos
durante transferencias de e / s.
·
Cuando
concluye la transferencia los datos pueden ser accedidos por el procesador.
·
Esquema
de “entradas de buffer simple”:
o El canal deposita datos en el
buffer.
o El procesador procesa estos datos.
o El canal deposita nuevos datos, etc.
o No puede haber simultaneidad entre
operaciones de colocar datos en el buffer y procesarlos:
§ Afecta la performance.
·
Esquema
de “entradas de buffer doble”:
o Permite la sobre posición de
operaciones de e / s con el procesamiento:
§ Mejora la performance.
o Mientras el canal deposita datos en
un buffer el procesador puede estar procesando los datos del otro buffer.
o Cuando el procesador concluye el
proceso de los datos del primer buffer, puede continuar con los datos del
segundo, mientras el canal deposita nuevos datos en el primer buffer:
§ Es la técnica de “buffer
biestable ( o en flip flop)”.
Principios del Software de E / S
La
idea básica es organizar el software como una serie de capas donde:
- Las capas
inferiores se encarguen de ocultar las peculiaridades del hardware a
las capas superiores.
- Las capas
superiores deben presentar una interfaz agradable, limpia y regular a
los usuarios.
Un
concepto clave es la independencia del dispositivo:
- Debe
ser posible escribir programas que se puedan utilizar con archivos en
distintos dispositivos, sin tener que modificar los programas para
cada tipo de dispositivo.
- El
problema debe ser resuelto por el S. O.
El
objetivo de lograr nombres uniformes está muy relacionado con el de
independencia del dispositivo.
Todos
los archivos y dispositivos adquieren direcciones de la misma forma, es decir
mediante el nombre de su ruta de acceso.
Otro
aspecto importante del software es el manejo de errores de e / s:
- Generalmente
los errores deben manejarse lo más cerca posible del hardware.
- Solo
si los niveles inferiores no pueden resolver el problema, se informa a los
niveles superiores.
- Generalmente
la recuperación se puede hacer en un nivel inferior y de forma
transparente.
Otro
aspecto clave son las transferencias síncronas (por bloques) o asíncronas
(controlada por interruptores):
- La
mayoría de la e / s es asíncrona: la cpu inicia la transferencia y
realiza otras tareas hasta una interrupción.
- La
programación es más fácil si la e / s es síncrona (por bloques): el
programa se suspende automáticamente hasta que los datos estén disponibles
en el buffer.
El S. O.
se encarga de hacer que operaciones controladas por interruptores parezcan del
tipo de bloques para el usuario.
También
el S. O. debe administrar los dispositivos compartidos (ej.: discos) y
los de uso exclusivo (ej.: impresoras).
Generalmente el software de e / s se estructura en capas (ver Figura 5.3):
- Manejadores
de interrupciones.
- Directivas
de dispositivos.
- Software
de S. O. independiente de los dispositivos.
- Software
a nivel usuario.
Las
interrupciones deben ocultarse en el S. O.:
- Cada
proceso que inicie una operación de e / s se bloquea hasta que termina la
e / s y ocurra la interrupción.
- El
procedimiento de interrupción realiza lo necesario para desbloquear el
proceso que lo inicio.
Todo
el código que depende de los dispositivos aparece en los manejadores
de dispositivos.
Cada
controlador posee uno o más registros de dispositivos:
- Se
utilizan para darle los comandos.
- Los
manejadores de dispositivos proveen estos comandos y verifican su
ejecución adecuada.
La labor
de un manejador de dispositivos es la de:
- Aceptar
las solicitudes abstractas que le hace el software independiente del
dispositivo.
- Verificar
la ejecución de dichas solicitudes.
Si al
recibir una solicitud el manejador está ocupado con otra solicitud, agregara la
nueva solicitud a una cola de solicitudes pendientes.
La
solicitud de e / s, por ej. Para un disco, se debe traducir de términos
abstractos a términos concretos:
- El manejador
de disco debe:
- Estimar el lugar donde se encuentra en realidad el
bloque solicitado.
- Verificar si el motor de la unidad funciona.
- Verificar si el brazo está colocado en el cilindro
adecuado, etc.
- Resumiendo: debe decidir cuáles son las
operaciones necesarias del controlador y su orden.
- Envía los comandos al controlador al escribir en los
registros de dispositivo del mismo.
- Frecuentemente el manejador del dispositivo se bloquea
hasta que el controlador realiza cierto trabajo; una interrupción lo
libera de este bloqueo.
- Al finalizar la operación debe verificar los errores.
- Si todo esta o.k. transferirá los datos al software
independiente del dispositivo.
- Regresa información de estado sobre los errores a
quien lo llamó.
- Inicia otra solicitud pendiente o queda en espera.
Funciones generalmente realizadas por el software
independiente del dispositivo:
- Interfaz
uniforme para los manejadores de dispositivos.
- Nombres
de los dispositivos.
- Protección
del dispositivo.
- Proporcionar
un tamaño de bloque independiente del dispositivo.
- Uso
de buffers.
- Asignación
de espacio en los dispositivos por bloques.
- Asignación
y liberación de los dispositivos de uso exclusivo.
- Informe
de errores.
Las
funciones básicas del software independiente del dispositivo son:
- Efectuar
las funciones de e / s comunes a todos los dispositivos.
- Proporcionar
una interfaz uniforme del software a nivel usuario.
El
software independiente del dispositivo asocia los nombres simbólicos de los
dispositivos con el nombre adecuado.
Un
nombre de dispositivo determina de manera única el nodo-i de un archivo
especial:
- Este
nodo-i contiene el número principal del dispositivo, que se utiliza
para localizar el manejador apropiado.
- El
nodo-i contiene también el número secundario de dispositivo, que se
transfiere como parámetro al manejador para determinar la unidad por leer
o escribir.
El software
independiente del dispositivo debe:
- Ocultar
a los niveles superiores los diferentes tamaños de sector de los distintos
discos.
- Proporcionar
un tamaño uniforme de los bloques, por ej.: considerar varios sectores
físicos como un solo bloque lógico.
La
mayoría del software de e / s está dentro del S. O.
Una
pequeña parte consta de bibliotecas ligadas entre sí con los programas del
usuario.
La
biblioteca estándar de e / s contiene varios procedimientos relacionados con e
/ s y todos se ejecutan como parte de los programas del usuario.
Otra
categoría importante de software de e / s a nivel usuario es el sistema de
spooling.
El
spooling es una forma de trabajar con los dispositivos de e /s de uso exclusivo
en un sistema de multiprogramación:
- El
ejemplo típico lo constituye la impresora de líneas.
- Los
procesos de usuario no abren el archivo correspondiente a la impresora.
- Se
crea un proceso especial, llamado demonio en algunos
sistemas.
- Se
crea un directorio de spooling.
Para imprimir
un archivo:
- Un
proceso genera todo el archivo por imprimir y lo coloca en el directorio
de spooling.
- El
proceso especial, único con permiso para utilizar el archivo especial de
la impresora, debe imprimir los archivos en el directorio.
- Se
evita el posible problema de tener un proceso de usuario que mantenga un
recurso tomado largo tiempo.
Un esquema
similar también es aplicable para la transferencia de archivos entre
equipos conectados:
- Un
usuario coloca un archivo en un directorio de spooling de la red.
- Posteriormente,
el proceso especial lo toma y transmite. Un ej. son los sistemas de correo
electrónico.
Las
siguientes son las principales ventajas con respecto del uso de la
memoria principal como almacenamiento:
- Mucha
mayor capacidad de espacio de almacenamiento.
- Menor
precio por bit.
- La
información no se pierde al apagar la computadora.
Un
uso inapropiado de los discos puede generar ineficiencia, en especial en
sistemas con multiprogramación.
Los
discos están organizados en cilindros, pistas y sectores.
El
número típico de sectores por pista varía entre 8 y 32 (o más).
Todos
los sectores tienen igual número de bytes.
Los
sectores cercanos a la orilla del disco serán mayores físicamente que los
cercanos al anillo.
Un
controlador puede realizar búsquedas en una o más unidades al mismo tiempo:
- Son
las búsquedas traslapadas.
- Mientras
el controlador y el software esperan el fin de una búsqueda en una unidad,
el controlador puede iniciar una búsqueda en otra.
Muchos
controladores pueden:
- Leer o
escribir en una unidad.
- Buscar
en otra.
Los
controladores no pueden leer o escribir en dos unidades al mismo tiempo.
La capacidad de búsquedas traslapadas puede reducir
considerablemente el tiempo promedio de acceso.
Los
datos se graban en una serie de discos magnéticos o platos.
El
eje común de los discos gira a una velocidad del orden de las 4.000 o más
revoluciones por minuto.
Se
lee o escribe mediante una serie de cabezas de lectura - escritura (ver Figura
5.4]):
- Se
dispone de una por cada superficie de disco.
- Solo
puede acceder a datos inmediatamente adyacentes a ella:
- La parte de la superficie del disco de donde se leerá
(o sobre la que se grabará) debe rotar hasta situarse inmediatamente
debajo (o arriba) de la cabeza de lectura - escritura.
- El tiempo de rotación desde la posición actual hasta
la adyacente al cabezal se llama tiempo de latencia.
Todas las
cabezas de lectura - escritura están montadas sobre una barra o conjunto de
brazo móvil:
- Puede
moverse hacia adentro o hacia afuera, en lo que se denomina operación
de búsqueda.
- Para
una posición dada, la serie de pistas accesibles forman un cilindro
vertical.
A los tiempos
de búsqueda y de latencia se debe agregar el tiempo de transmisión
propiamente dicha (ver Figura 5.5).
El
tiempo total de acceso a un registro particular:
- Involucra
movimientos mecánicos.
- Generalmente
es del orden de centésimas de segundo, aunque el tiempo de latencia sea de
algunas milésimas de segundo (7 a 12 aproximadamente).
En
la mayoría de los discos, el tiempo de búsqueda supera al de retraso
rotacional y al de transferencia , debido a ello, la reducción del
tiempo promedio de búsqueda puede mejorar en gran medida el rendimiento del
sistema.
Si
el manejador del disco utiliza el algoritmo primero en llegar primero
en ser atendido (FCFS), poco se puede hacer para mejorar el tiempo de
búsqueda.
Es
posible que mientras el brazo realiza una búsqueda para una solicitud, otros
procesos generen otras solicitudes.
Muchos
manejadores tienen una tabla:
- El
índice es el número de cilindro.
- Incluye
las solicitudes pendientes para cada cilindro enlazadas entre sí en
una lista ligada.
- Cuando
concluye una búsqueda, el manejador del disco tiene la opción de elegir
la siguiente solicitud a dar paso:
- Se atiende primero la solicitud más cercana, para minimizar
el tiempo de búsqueda.
- Este algoritmo se denomina primero la búsqueda más
corta (SSF: shor-test seek first).
- Reduce a la mitad el número de movimientos del brazo
en comparación con FCFS.
Ej. de SSF:
- Consideramos
un disco de 40 cilindros.
- Se
presenta una solicitud de lectura de un bloque en el cilindro 11.
- Durante
la búsqueda, llegan solicitudes para los cilindros 1, 36, 16, 34, 9 y 12,
en ese orden.
- La
secuencia de búsqueda SSF será: 12, 9, 16, 1, 34, 36.
- Habrá
un número de movimientos del brazo para un total de:
- 111 cilindros según FCFS.
- 61 cilindros según SSF.
El algoritmo
SSF tiene el siguiente problema:
- El
ingreso de nuevas solicitudes puede demorar la atención de las más
antiguas.
- Con
un disco muy cargado, el brazo tenderá a permanecer a la mitad del disco
la mayoría del tiempo, como consecuencia de ello las solicitudes lejanas a
la mitad del disco tendrán un mal servicio.
- Entran
en conflicto los objetivos de:
- Tiempo mínimo de respuesta.
- Justicia en la atención.
La
solución a este problema la brinda el algoritmo del elevador (por su
analogía con el ascensor o elevador):
- Se
mantiene el movimiento del brazo en la misma dirección, hasta que no tiene
más solicitudes pendientes en esa dirección; entonces cambia de dirección.
- El
software debe conservar el bit de dirección actual.
Ej. del algoritmo
del elevador para el caso anterior, con el valor inicial arriba del bit de
dirección:
- El
orden de servicio a los cilindros es: 12, 16, 34, 36, 9 y 1.
- El
número de movimientos del brazo corresponde a 60 cilindros.
El algoritmo
del elevador:
- Ocasionalmente
es mejor que el algoritmo SSF.
- Generalmente
es peor que SSF.
- Dada
cualquier colección de solicitudes, la cuota máxima del total de
movimientos está fija, siendo el doble del número de cilindros.
Una
variante consiste en rastrear siempre en la misma dirección:
- Luego
de servir al cilindro con el número mayor:
- El brazo pasa al cilindro de número menor con una
solicitud pendiente.
- Continúa su movimiento hacia arriba.
Algunos
controladores de disco permiten que el software inspeccione el número del
sector activo debajo del cabezal:
- Si
dos o más solicitudes para el mismo cilindro están pendientes:
- El manejador puede enviar una solicitud para el sector
que pasará debajo del cabezal.
- Se pueden hacer solicitudes consecutivas de distintas
pistas de un mismo cilindro, sin generar un movimiento del brazo.
Cuando
existen varias unidades, se debe tener una tabla de solicitudes pendientes
para cada unidad.
Si
una unidad está inactiva, deberá buscarse el cilindro siguiente necesario, si
el controlador permite búsquedas traslapadas.
Cuando
termina la transferencia actual se verifica si las unidades están en la
posición del cilindro correcto:
- Si
una o más unidades lo están, se puede iniciar la siguiente transferencia
en una unidad ya posicionada.
- Si
ninguno de los brazos está posicionado, el manejador:
- Debe realizar una nueva búsqueda en la unidad que
terminó la transferencia.
- Debe esperar hasta la siguiente interrupción para ver
cuál brazo se posiciona primero.
Generalmente,
las mejoras tecnológicas de los discos:
- Acortan
los tiempos de búsqueda (seek).
- No
acortan los tiempos de demora rotacional (search).
- En
algunos discos, el tiempo promedio de búsqueda ya es menor que el retraso
rotacional.
- El
factor dominante será el retraso rotacional, por lo tanto, los algoritmos que optimizan los
tiempos de búsqueda (como el algoritmo del elevador) perderán importancia
frente a los algoritmos que optimicen el retraso rotacional.
Una
tecnología importante es la que permite el trabajo conjunto de varios
discos.
Una
configuración interesante es la de treinta y ocho (38) unidades ejecutándose
en paralelo.
Cuando
se realiza una operación de lectura:
- Ingresan
a la cpu 38 bit a la vez, uno por cada unidad.
- Los
38 bits conforman una palabra de 32 bits junto con 6 bits para
verificación.
- Los
bits 1, 2, 4, 8, 16 y 32 se utilizan como bits de paridad.
- La
palabra de 38 bits se puede codificar mediante el código Hamming,
que es un código corrector de errores.
- Si
una unidad sale de servicio:
- Se pierde un bit de cada palabra.
- El sistema puede continuar trabajando; se debe a que
los códigos Hamming se pueden recuperar de un bit perdido.
Este
diseño se conoce como RAID; siglas en inglés de “arreglo redundante
de discos no costosos”.
En
los sistemas de multiprogramación muchos procesos pueden estar generando
peticiones de e / s sobre discos:
- La
generación de peticiones puede ser mucho más rápida que la atención
de las mismas:
- Se construyen líneas de espera o colas para
cada dispositivo.
- Para reducir el tiempo de búsqueda de registros
se ordena la cola de peticiones: esto se denomina planificación
de disco.
La
planificación de disco implica:
- Un
examen cuidadoso de las peticiones pendientes para determinar la forma
más eficiente de servirlas.
- Un
análisis de las relaciones posicionales entre las peticiones en
espera.
- Un reordenamiento
de la cola de peticiones para servirlas minimizando los movimientos
mecánicos.
Los
tipos más comunes de planificación son:
- Optimización
de la búsqueda.
- Optimización
rotacional (latencia).
Generalmente
los tiempos de búsqueda superan a los de latencia, aunque la diferencia
disminuye:
- Muchos
algoritmos de planificación se concentran en la reducción de los
tiempos de búsqueda para un conjunto de peticiones.
- Generalmente
la reducción de la latencia recién tiene efectos bajo cargas de
trabajo muy pesadas.
Bajo
condiciones de carga ligera (promedio bajo de longitud de la cola), es
aceptable el desempeño del método FCFS (primero en llegar, primero en
ser servido).
Bajo
condiciones de carga media o pesada, es recomendable un algoritmo de
planificación de las colas de requerimientos.
Los
principales criterios de categorización de las políticas de planificación
son:
- Capacidad
de ejecución.
- Media
del tiempo de respuesta.
- Varianza
de los tiempos de respuesta (predecibilidad).
Una
política de planificación debe intentar maximizar la capacidad de ejecución:
- Maximizar
el número de peticiones servidas por unidad de tiempo.
- Minimizar
la media del tiempo de respuesta.
- Mejorar
el rendimiento global, quizás a costa de las peticiones individuales.
La
planificación suele mejorar la imagen total al tiempo que reduce los
niveles de servicio de ciertas peticiones:
- Se
mide utilizando la varianza de los tiempos de respuesta.
- La
varianza es un término estadístico que indica hasta qué punto tienden a
desviarse del promedio de todos los elementos los elementos individuales.
- A
menor varianza mayor predecibilidad.
- Se
desea una política de planificación que minimice la varianza, es decir que
maximice la predecibilidad.
- No
debe haber peticiones que puedan experimentar niveles de servicio
erráticos.
Las
estrategias más comunes de optimización de la búsqueda son las
siguientes:
- FCFS.
- SSTF.
- SCAN.
- SCAN
de N - Pasos.
- C
- SCAN.
- Esquema
Eschenbach.
Una
petición no puede ser desplazada por la llegada de una petición con prioridad
más alta.
No hay reordenamiento de la cola de peticiones pendientes.
Se
ignoran las relaciones posicionales entre las peticiones pendientes.
Ofrece
una varianza pequeña aunque perjudica a las peticiones situadas al final de la
cola.
El
brazo del disco se sitúa en la siguiente petición que minimice el movimiento
del brazo.
No
respeta el orden de llegada de las peticiones a la cola.
Tiende
a favorecer a las pistas del centro del disco.
La
media de tiempos de respuesta tiende a ser más baja que con FCFS,
para cargas moderadas.
Las
varianzas tienden a ser mayores que con FCFS por el efecto de las pistas
interiores y exteriores.
El
brazo del disco se desplaza sirviendo a todas las peticiones que encuentra a
su paso.
Cambia
de dirección cuando ya no hay peticiones pendientes en la dirección actual.
Ha sido la base de la mayoría de las estrategias de
planificación implementadas.
Elimina
las discriminaciones de SSTF y tiene menor varianza.
Las
pistas exteriores son menos visitadas que las intermedias, pero no es tan grave
como con SSTF.
La
estrategia de movimiento del brazo es como en SCAN; solo da servicio a
las peticiones que se encuentran en espera cuando comienza un recorrido
particular.
Las
peticiones que llegan durante un recorrido son agrupadas y ordenadas y
serán atendidas durante el recorrido de regreso.
Posee
menor varianza de los tiempos de respuesta si se compara con las
planificaciones SSTF y SCAN convencionales.
El
brazo se mueve del cilindro exterior al interior, sirviendo a las
peticiones sobre una base de búsqueda más corta.
Finalizado
el recorrido hacia el interior, salta a la petición más cercana al cilindro
exterior y reanuda su desplazamiento hacia el interior.
No
discrimina a los cilindros exterior e interior.
La
varianza de los tiempos de respuesta es muy pequeña.
El
brazo del disco se mueve como en C - SCAN, pero:
- Las peticiones
se reordenan para ser servidas dentro de un cilindro para tomar
ventaja de la posición rotacional.
- Si
dos peticiones trasladan posiciones de sectores dentro de un cilindro,
solo se sirve una en el movimiento actual del brazo del disco.
Esta
estrategia tiene en cuenta el retraso rotacional.
Bloqueos
Introducción y ejemplos de bloqueo (o interbloqueo)
Un
proceso dentro de un sistema de multiprogramación está en un estado de
interbloqueo (o interbloqueado) si está esperando por un evento
determinado que no ocurrirá.
Cuando
los recursos son compartidos entre usuarios:
- Pueden
producirse interbloqueos en los cuales los procesos de algunos
usuarios nunca podrán llegar a su término.
- Se
debe considerar la prevención, evitación, detección y
recuperación del interbloqueo y la postergación indefinida,
que se da cuando un proceso, aunque no esté interbloqueado, puede estar
esperando por un evento que probablemente nunca ocurrirá.
- En
algunos casos:
- El precio de liberar interbloqueos en un sistema es
demasiado alto.
- Permitir el interbloqueo podría resultar catastrófico.
Los
sistemas de cómputos tienen muchos recursos que solo pueden ser utilizados
por un proceso a la vez:
- Ej.:
impresoras, unidades de cinta, espacio de la tabla de nodos-i.
- Los
S. O. tienen la capacidad de otorgar temporalmente a un proceso el acceso
exclusivo a ciertos recursos.
- Frecuentemente
un proceso necesita el acceso exclusivo no solo a un recurso, sino
a varios.
Ej. de bloqueo
(deadlock):
- Dos
procesos desean imprimir grandes archivos en cinta.
- El
proceso “a” solicita la impresora, que se le concede.
- El
proceso “b” solicita la unidad de cinta, que se le concede.
- El
proceso “a” solicita la unidad de cinta, pero se deniega la
solicitud hasta que “b” la libera.
- El
proceso “b” solicita la impresora y se produce el bloqueo
(deadlock).
Ejemplo de
interbloqueo de tráfico:
Tiene
similitud con el congestionamiento del tránsito en las ciudades.
El
tráfico puede detenerse completamente.
Es
necesaria una intervención externa para poner orden y restablecer la
normalidad.
Ejemplo
de interbloqueo de un recurso simple:
Tiene
su origen en la contención normal de los recursos dedicados o reutilizables en
serie:
- Pueden
ser utilizados por un solo usuario a la vez.
- Cada
proceso está esperando por el otro para liberar uno de los recursos.
- El
recurso retenido no será liberado hasta que el otro proceso usuario libere
su recurso.
- Este
último proceso usuario no liberará su recurso retenido hasta que el primer
proceso usuario libere su recurso retenido.
- Se
produce una espera circular (ver Figura 6.1).
Ejemplo
de interbloqueo en sistemas de spool:
Un
sistema de spool es utilizado para incrementar la capacidad de ejecución
del sistema, al disasociar un programa de la lenta velocidad de los
dispositivos (ej.: impresoras):
- Si un
programa envía líneas a una impresora, en realidad son enviadas a un
dispositivo más rápido (disco).
- Se
almacenan temporalmente hasta ser impresas.
Varios
trabajos en ejecución que generan líneas de spool pueden interbloquearse si el
espacio disponible se llena antes de completarse alguno de estos trabajos:
- Se reduce
la probabilidad de interbloqueos del spool:
- Proporcionando un espacio en disco considerablemente
mayor que el necesario, preferentemente con asignación dinámica.
- Limitando los spoolers de entrada para que no lean más
trabajos cuando los archivos de spool llegan a cierto nivel de
saturación.
Un
problema relacionado: postergación indefinida:
Es
posible que un proceso sea postergado indefinidamente en tanto que otros
reciben la atención del sistema:
- Se
trata de la postergación indefinida.
- Cuando
los recursos son planificados en función de prioridades, un proceso
dado puede esperar indefinidamente, mientras sigan llegando procesos de
prioridades mayores.
En algunos
sistemas, la postergación indefinida se evita al permitir que la prioridad de
un proceso aumente mientras espera por un recurso; a esto se llama envejecimiento.
El
S. O. es, sobre todo, un administrador de recursos.
Los
recursos pueden ser “apropiativos”, como la CPU y la memoria principal.
La apropiatividad es extremadamente importante para el éxito
de los sistemas computacionales multiprogramados.
Ciertos
recursos son “no apropiativos”, como las unidades de cinta o cartridge
magnéticos, o sea que no pueden sacarse de los procesos a los que están
asignados.
Algunos
recursos:
- Pueden
ser compartidos entre varios procesos.
- Pueden
estar dedicados a procesos individuales.
También
son recursos compartibles (de uso compartido) ciertos programas:
- Se
carga una copia del código a memoria.
- Se
habilitan varias copias de las estructuras de datos, una para cada
usuario.
- Como
el código puede ser utilizado por varios usuarios a la vez, no puede
cambiar durante la ejecución:
- El código que no cambia durante la ejecución se
denomina reentrante.
- El código que puede ser cambiado, pero se
inicializa cada vez que se usa, se denomina reutilizable en serie.
El
código reentrante puede ser compartido simultáneamente por varios procesos.
El código reutilizable en serie puede ser usado solo por un
proceso a la vez.
Cuando
se consideran compartidos a determinados recursos, se debe establecer
si son utilizables por varios procesos simultáneamente o de a uno por vez,
estos últimos son los recursos que más a menudo están implicados en los
interbloqueos.
La
secuencia de eventos necesarios para utilizar un recurso es la
siguiente:
- Solicitar el recurso.
- Utilizar
el recurso.
- Liberar
el recurso.
Si el
recurso no está disponible cuando se lo solicita:
- El
proceso solicitante debe esperar.
- En
algunos S. O. el proceso se bloquea automáticamente y se despierta cuando
dicho recurso está disponible.
- En
otros S. O. la solicitud falla y el proceso debe esperar para luego
intentar nuevamente.
Un bloqueo
se puede definir formalmente como sigue:
- Un
conjunto de procesos se bloquea si cada proceso del conjunto espera un
evento que solo puede ser provocado por otro proceso del conjunto:
- Ya que todos los procesos están esperando:
- Ninguno realizará un evento
que pueda despertar a los demás miembros del conjunto.
- Todos los procesos esperarán
por siempre.
- Generalmente el evento que espera cada proceso es la
liberación de cierto recurso que posee por el momento otro miembro del
conjunto:
- Cada miembro del conjunto de
procesos bloqueados espera un recurso poseído por un proceso bloqueado.
- Ninguno de los procesos
bloqueados puede continuar su ejecución, ni liberar recursos, ni puede
ser despertado.
Las condiciones
necesarias para el bloqueo son (Coffman):
- Los
procesos reclaman control exclusivo de los recursos que piden (condición
de exclusión mutua).
- Los
procesos mantienen los recursos que ya les han sido asignados mientras
esperan por recursos adicionales (condición de espera por).
- Los
recursos no pueden ser extraídos de los procesos que los tienen hasta su
completa utilización (condición de no apropiatividad).
- Existe
una cadena circular de procesos en la que cada uno mantiene a uno o más
recursos que son requeridos por el siguiente proceso de la cadena (condición
de espera circular).
Modelación de Bloqueos
La
modelación de bloqueos se puede mostrar mediante gráficas dirigidas
(Holt) (ver Figura 6.2
Las
gráficas tienen dos tipos de nodos:
- Procesos
(aparecen como círculos).
- Recursos
(aparecen como cuadrados).
- Un
arco de un nodo de recurso a uno de proceso indica que el recurso fue
solicitado con anterioridad, fue otorgado y es poseído en ese momento por
dicho proceso.
- Un
arco de un proceso a un recurso indica que el proceso está bloqueado, en
espera de ese recurso.
- Un
ciclo en la gráfica indica la existencia de un bloqueo relacionado
con los procesos y recursos en el ciclo (ver Figura 6.3 y Figura 6.4 ).
Las
estrategias utilizadas para enfrentar los bloqueos son:
- Ignorar
todo el problema.
- Detección
y recuperación.
- Evitarlos
dinámicamente mediante una cuidadosa asignación de recursos.
- Prevención
mediante la negación estructural de una de las cuatro condiciones
necesarias.
Los
principales aspectos son los siguientes:
- Prevención
del bloqueo.
- Evitación
del bloqueo.
- Detección
del bloqueo.
- Recuperación
del bloqueo.
Prevención
del bloqueo:
- El
interés se centra en condicionar un sistema para que elimine toda
posibilidad de que éstos se produzcan.
- Los
métodos pueden dar como resultado una pobre utilización de los recursos,
aún así son ampliamente utilizados.
Evitación
del bloqueo:
- La
meta es imponer condiciones menos estrictas que en la prevención,
para intentar lograr una mejor utilización de los recursos.
- No
precondiciona al sistema para que evite todas las posibilidades de
que se produzca un bloqueo.
- Permiten
la aparición del bloqueo, pero siempre que se produce una posibilidad de
bloqueo, éste se esquiva.
Detección
del bloqueo:
- Se
utiliza en sistemas que permiten que éstos ocurran, ya sea
voluntaria o involuntariamente.
- La
meta es determinar si ha ocurrido un bloqueo:
- Se debe detectar con precisión los procesos y
recursos implicados en el bloqueo.
- Se puede eliminar el bloqueo detectado.
Recuperación
del bloqueo:
- Se
utiliza para despejar bloqueos de un sistema para que:
- Continúe operando sin ellos.
- Terminen los procesos estancados.
- Se liberen los recursos correspondientes a ellos.
- Generalmente
se logra “extrayendo” (cancelando) a uno o varios de los procesos
bloqueados, que se reinician luego de forma normal.
El
punto de vista más simple es pretender que no existe el problema.
Esta
estrategia puede generar distintas reacciones:
- Matemáticamente
es inaceptable, considerándose que los bloqueos deben evitarse a toda
costa.
- Desde
la ingeniería de software podría considerarse cuál es la frecuencia
esperada del problema, cuáles son sus consecuencias esperadas, cuáles son
las frecuencias esperadas de fallas de otro tipo, etc.
Algunos S.
O. soportan potencialmente bloqueos que ni siquiera se detectan, ya que se
rompen automáticamente.
Los
S. O. que ignoran el problema de los bloqueos asumen la siguiente hipótesis:
- La
mayoría de los usuarios preferiría un bloqueo ocasional, en vez de una
regla que restringiera a todos los usuarios en el uso de los distintos
tipos de recursos.
El
problema es que se debe pagar un cierto precio para encarar el problema del
bloqueo:
- En
restricciones para los procesos.
- En el
uso de recursos.
Se
presenta una contradicción entre la conveniencia y lo que es correcto.
Es
muy difícil encontrar teóricamente soluciones prácticas de orden general
aplicables a todos los tipos de S. O.
Un
criterio de orden general utilizado por los S. O. que no hacen
tratamiento específico del bloqueo consiste en:
- Intentar
acceder al recurso compartido.
- De no
ser factible el acceso:
- Esperar un tiempo aleatorio.
- Reintentar nuevamente.
El S. O. no intenta evitar los bloqueos:
- Intenta
detectar cuando han ocurrido.
- Acciona
para recuperarse después del hecho.
La
detección del bloqueo es el proceso de:
- Determinar
si de hecho existe o no un bloqueo.
- Identificar
cuáles son los procesos y recursos implicados en el bloqueo.
Los
algoritmos de detección de bloqueos implican cierta sobrecarga en tiempo de
ejecución, por lo cual surge el siguiente interrogante: ¿ compensa la
sobrecarga implícita en los algoritmos de detección de bloqueos, el ahorro
potencial de localizarlos y romperlos ?.
Una
gráfica dirigida indica las asignaciones y peticiones de recursos.
Los
cuadros representan procesos.
Los
círculos grandes indican clases de recursos idénticos.
Los
círculos pequeños, dibujados dentro de los grandes, representan el número de
recursos idénticos dentro de cada clase (ver Figura 6.5 [).
Si
las peticiones de recursos de un proceso pueden ser concedidas, se dice
que una gráfica puede ser reducida por ese proceso.
La
reducción de una gráfica por un proceso determinado se muestra
retirando:
- Las
flechas que van de los recursos al proceso (los recursos asignados al
proceso).
- Las
flechas que van del proceso al recurso (las peticiones actuales del
proceso).
Si
una gráfica puede ser reducida por todos sus procesos, entonces no hay
interbloqueo.
Si una gráfica no puede ser reducida por todos sus procesos,
entonces los procesos “irreducibles” constituyen la serie de procesos
interbloqueados de la gráfica
(ver Figura 6.6).
No
se dispone de más de un objeto de cada clase de recurso.
Si la gráfica de recursos contuviera uno o más ciclos,
existiría un bloqueo.
Cualquier
proceso que forme parte de un ciclo está bloqueado; si no existen ciclos, el
sistema no está bloqueado.
Ejemplo:
sistema con 7 (siete) procesos (“A” a “G”) y 6 (seis) recursos (“R”
a “W”):
- La posesión
de los recursos es la siguiente:
- El proceso A posee a R y desea a S.
- El proceso B no posee recurso alguno y desea a T.
- El proceso C no posee recurso alguno y desea a S.
- El proceso D posee a U y desea a S
y a T.
- El proceso E posee a T y desea a V.
- El proceso F posee a W y desea a S.
- El proceso G posee a V y desea a U.
- La pregunta
es: ¿está bloqueado este sistema y, en tal caso, cuáles son los procesos
bloqueados?.
- La respuesta
se obtiene mediante la gráfica de recursos: si la gráfica presenta
un ciclo significa procesos bloqueados (ver Figura 6.7).
Se
hace necesario un algoritmo formal para la detección de bloqueos que se
pueda utilizar en los sistemas reales.
Ejemplo
de algoritmo aplicable a cada nodo “N” de la gráfica:
- Se
considera a “N” como nodo inicial.
- Se
inicializan:
- La estructura de datos “L”como una lista vacía.
- Todos los arcos como no marcados.
- Se
añade el nodo activo al final de “L” y se verifica si el nodo
aparece en “L” dos veces:
- Si aparece dos veces existe un ciclo y el algoritmo
termina.
- Desde
el nodo dado se verifica si existen arcos que salgan de dicho nodo y no
estén marcados:
- En caso afirmativo se va al paso 5.
- En caso negativo se va al paso 6.
- Se
elige al azar un arco de salida no marcado y se le marca:
- Luego se sigue este arco hasta el nuevo nodo activo y
se regresa al paso 3.
- Se ha
llegado a un punto donde no se puede continuar:
- Se regresa al nodo anterior, es decir al que estaba
activo antes del actual.
- Se señala de nuevo como nodo activo.
- Se pasa al paso 3.
- Si este nodo era el nodo inicial, la gráfica no
contiene ciclos y el algoritmo termina.
La aplicación
del algoritmo precedente al ejemplo anterior de gráfica dirigida es la
siguiente:
- Se
parte de “R” y se inicializa “L” como la lista vacía.
- Se
añade “R” a la lista y se mueve a la única posibilidad, “A”.
- Se
añade “A” a la lista: L=[R,A].
- Se
pasa de “A” a “S”, quedando L=[R,A,S].
- “S” no tiene arcos que salgan de
él, por lo que no se puede continuar y se regresa a “A”.
- Ya
que “A” no tiene arcos de salida no marcados se regresa a “R”,
finalizando la inspección de “R”.
- Se
inicia nuevamente el algoritmo partiendo de “A”, siendo “L”
otra vez la lista vacía.
- La
búsqueda termina rápidamente y se parte de “B”.
- De “B”
se siguen los arcos de salida hasta llegar a “D”, siendo
L=[B,T,E,V,G,U,D].
- Se
efectúa una elección al azar.
- Si se
elige “S” llegamos a un punto sin salida y debemos regresar a “D”.
- La
segunda vez se elige “T” quedando L=[B,T,E,V,G,U,D,T] :
- Se ha descubierto un ciclo y el algoritmo se detiene.
Se
considera un algoritmo basado en matrices para la detección de un
bloqueo entre “n” procesos, “P1” hasta “Pn”.
Se
considera “m” el número de clases de recursos con:
- E1
recursos de la clase 1.
- E2
recursos de la clase 2.
- Ei
recursos de la clase “i” (1 menor o igual que “i ” menor o
igual que “m”).
- “E”
es el vector de recursos existentes.
En todo
momento algunos de los recursos están asignados y por lo tanto no están
disponibles.
Se
considera un vector “A” de recursos disponibles:
- “Ai” indica el número de instancias
disponibles del recurso “i ” ; se refiere a recursos no
asignados.
Se
utilizan:
- La matriz
“C” de la asignación actual.
- La matriz
“R” de solicitudes.
El renglón
i -ésimo de “C” indica el número de instancias de cada clase “Pi”
poseídas en ese momento.
“Cij ”
es el número de instancias del recurso“ j” deseadas por “Pi”.
Cada
recurso está asignado o disponible, es decir que la suma de las
instancias del recurso “j ” asignadas y el número de instancias disponibles
es el número de instancias existentes de esa clase de recurso.
El
algoritmo de detección de bloqueos se basa en la comparación de vectores:
- Definimos
que “A” es menor o igual que “B” si y solo si “Ai”es
menor o igual que “Bi” para “i” entre “0”
y “m”, ambos inclusive.
Los
procesos no están marcados al principio.
Al
avanzar el algoritmo los procesos se marcarán:
- Esto
indica que pueden terminar su labor, ya que no están bloqueados.
- Al
concluir el algoritmo se sabe que los procesos no marcados estarán
bloqueados.
Los pasos
básicos del algoritmo de detección de bloqueos son los siguientes:
- Se
busca un proceso no marcado “Pi” , para el cual el i -ésimo
renglón de “R” sea menor que “A”.
- Si se
encuentra tal proceso, se suma el i -ésimo renglón de “C” a “A”,
se marca el proceso y se regresa al paso 1.
- Si no
existe tal proceso, el algoritmo termina.
El
proceso 1 tiene 1 impresora.
El
proceso 2 tiene 2 unidades de cinta y 1 unidad de cd rom.
El
proceso 3 tiene 1 plotter y 2 impresoras.
La
matriz “R” indica las necesidades de recursos adicionales.
El
algoritmo de detección de bloqueos busca un proceso cuya solicitud de un
recurso pueda ser satisfecha:
- El
proceso 1 no se puede satisfacer por no disponer de una unidad de cd rom.
- El
proceso 2 no se puede satisfacer por no disponer de una impresora.
- El
proceso 3 sí se puede satisfacer, por lo que se ejecuta, regresando en
cierto momento sus recursos, lo que resulta en: A = (2 2 2 0).
Se ejecuta
el proceso 2, el cual regresa sus recursos, obteniéndose: A = (4 2 2 1).
Se
ejecuta el proceso restante: no existe bloqueo en el sistema.
Si
se considera la siguiente variante:
- El
proceso 2 necesita 1 unidad de cd rom, las 2 unidades de cinta y el
plotter.
- No se
pueden satisfacer las 3 solicitudes y todo el sistema se bloquea.
Una
posibilidad es cada vez que se solicita un recurso, pero esto podría
sobrecargar al sistema.
Otra
posibilidad es verificar cada k minutos.
Otro
criterio es verificar cuando el uso de la cpu baje de cierto valor fijo:
- Si se
bloquean suficientes procesos:
- Existirán pocos procesos en ejecución.
- La cpu estará inactiva con más frecuencia.
Para
romper el bloqueo de un sistema hay que anular una o más de las
condiciones necesarias para el bloqueo .
Normalmente,
varios procesos perderán algo o todo lo realizado hasta el momento.
Los
principales factores que dificultan la recuperación del bloqueo son los
siguientes:
- Puede
no estar claro si el sistema se ha bloqueado o no.
- Muchos
sistemas tienen limitaciones para suspender un proceso por tiempo
indefinido y reanudarlo más tarde:
- Ej.: Los procesos de tiempo real, que deben funcionar
continuamente, no son fáciles de suspender y reanudar.
- Los
procedimientos de suspensión / reanudación implican una sobrecarga
considerable.
- La sobrecarga
de recuperación está en función de la magnitud del bloqueo (algunos,
decenas o centenas de procesos involucrados).
Generalmente
la recuperación suele realizarse:
- Retirando
forzosamente (cancelando) a un proceso.
- Reclamando
sus recursos.
- Permitiendo
que los procesos restantes puedan finalizar.
Los
procesos pueden ser retirados (cancelados) de acuerdo a un orden de
prioridades, existiendo las siguientes dificultades:
- Pueden
no existir las prioridades de los procesos bloqueados.
- Las
prioridades instantáneas (en un momento dado), pueden ser incorrectas o
confusas debido a consideraciones especiales, por ej.: procesos de baja
prioridad que tienen prioridad alta momentáneamente debido a un tiempo
tope inminente.
- La
decisión óptima puede requerir un gran esfuerzo.
Algunas formas
de recuperación ante bloqueos son:
- Recuperación
mediante la apropiación.
- Recuperación
mediante rollback.
- Recuperación
mediante la eliminación de procesos.
En
ciertos casos podría ser posible tomar un recurso temporalmente de su
poseedor y dárselo a otro proceso, por ej:
- Retirar
una impresora de un proceso para dedicarla a otro proceso.
- Retomar
luego el primer proceso reasignándola al mismo.
La
recuperación de recursos de esta forma depende en gran medida de la naturaleza
del recurso.
La
elección del proceso a suspender depende mucho:
- De
cuáles procesos poseen recursos que pueden ser tomados con facilidad.
- De
las posibilidades de recuperación luego de la apropiación.
En
los S. O. donde es posible que ocurran bloqueos se puede hacer que los
procesos sean verificados periódicamente:
- Su
estado se graba en un archivo de modo que pueda volver a iniciar más
tarde.
- El punto
de verificación o de control contiene:
- La imagen de la memoria.
- El estado de los recursos, es decir, el detalle de los
recursos asignados al proceso en ese instante.
- Los
puntos de verificación grabados durante un proceso se mantienen sin ser
regrabados.
Al
detectarse un bloqueo es fácil ver cuáles son los recursos necesarios.
Para
la recuperación, un proceso que posee un recurso necesario regresa hasta
cierto instante en el tiempo anterior a la adquisición:
- Inicializa
alguno de sus anteriores puntos de verificación.
- El
proceso regresa a un momento anterior en el que no poseía el recurso.
- El
recurso se asigna ahora a uno de los procesos bloqueados.
- Si el
proceso que volvió a iniciar intenta adquirir de nuevo el recurso, tendrá
que esperar hasta que esté disponible.
- Es la
forma más sencilla de romper un bloqueo.
- Una
posibilidad es eliminar un proceso del ciclo: si el bloqueo no se
rompe, se puede intentar con otro proceso del ciclo, hasta romper dicho
ciclo.
- Otra
posibilidad es eliminar un proceso que no esté en el ciclo, para
poder liberar sus recursos: debe elegirse un proceso que posea recursos
necesarios por algún proceso del ciclo.
- Siempre
que sea posible, es mejor eliminar un proceso que pueda volver a iniciar
su ejecución sin efectos dañinos:
- Es preferible eliminar un proceso de compilación que
un proceso de actualización de una base de datos:
- La compilación se puede
repetir sin problemas.
- La actualización de una base
de datos no siempre se puede repetir directamente.
En
este análisis se supone implícitamente que si un proceso solicita recursos, los
solicita todos al mismo tiempo:
- En la
mayoría de los sistemas los recursos se solicitan uno a la vez.
- El S.
O. debe poder:
- Decidir si el otorgamiento de un recurso es seguro o
no.
- Asignarlo solo en caso de que sea seguro.
El
objetivo es evitar el bloqueo haciendo la elección correcta todo el
tiempo, pero para evitar los bloqueos se requiere de cierta información de
antemano.
Los
principales algoritmos para evitar los bloqueos se basan en el concepto
de estados seguros (ver Figura 6.9).
El
ejemplo de modelo gráfico utilizado indica lo siguiente:
- Es
válido para dos procesos y dos recursos.
- El
eje horizontal representa el número de instrucciones ejecutadas por el
proceso “A”.
- El
eje vertical representa el número de instrucciones ejecutadas por el
proceso “B”.
- En “I1”;
“A” solicita una impresora y en “I 2” necesita un plotter.
- En “I
3” e “I 4” se liberan la impresora y el plotter.
- El
proceso “B” necesita el plotter desde “I5” hasta “I7”
y la impresora desde “I6” hasta “I8”.
- Cada
punto del diagrama representa un estado conjunto de los dos
procesos.
- El
estado inicial es “p”, sin que los procesos hayan ejecutado
instrucción alguna.
- Si el
planificador del S. O. elige “A” se pasa a “q”, en donde “A”
ha ejecutado instrucciones pero no “B”.
- En
“q” la trayectoria se vuelve vertical, ya que el planificador ha
elegido ejecutar “B”.
- Con
un monoprocesador todas las trayectorias serán horizontales o verticales
(no diagonales).
- Cuando
“A” cruza la línea “I1” en la trayectoria de “r” a “s”,
solicita y se le otorga la impresora.
- Cuando
“B” alcanza el punto “t”, solicita el plotter.
- La
región delimitada por “I 1”, “I 3”, “I6” e “I 8”
representa que ambos procesos poseen la impresora, pero esto es imposible
y la regla de exclusión mutua impide la entrada a esta región.
- La
región delimitada por “I 2”, “I 4”, “I 5” e “I 7” representa
que ambos procesos poseen el plotter, lo que es imposible.
- Si el
sistema ingresara a la región delimitada por “I 1”, “I 2”, “I 5” e “I
6” se bloqueará en la intersección de “I 2” e “I 6”:
- Acá, “A” solicita el plotter y “B” la
impresora, que ya están asignados.
- Toda la región no es segura y no hay que entrar a
ella:
- En “t”, lo único
seguro es ejecutar “A” hasta llegar a “I 4”.
- Luego se puede utilizar
cualquier trayectoria hasta “u”.
- En “t”,
“B” solicita un recurso:
- El S. O. debe decidir si lo otorga o no.
- Si lo otorga, el sistema entrará a una región
insegura y se bloqueará en algún momento.
- Para evitar el bloqueo, hay que suspender a “B”
hasta que “A” haya solicitado y liberado el plotter.
Un
estado actual está conformado por “E”, “A”, “C” y “R”:
- “E”:
vector de recursos en existencia.
- “A”:
vector de recursos disponibles.
- “C”:
matriz de asignación actual.
- “R”:
matriz de solicitudes.
Un estado
es seguro si:
- No
está bloqueado.
- Existe
una forma de satisfacer todas las solicitudes pendientes, mediante la
ejecución de los procesos en cierto orden.
Ejemplo
con un recurso para demostrar que el estado en (a) es seguro:
El
estado es seguro ya que existe una sucesión de asignaciones que permiten
terminar a todos los procesos; dicha sucesión de asignaciones es la siguiente
(ver Tabla 6.1:
Ejemplo
con un recurso para mostrar un estado inseguro (ver Tabla 6.2):
- No se
puede garantizar que terminen los tres procesos.
- Si el
proceso “A” pide y se le otorga una unidad, puede producirse un
bloqueo de tres vías si cada uno de los procesos necesita al menos otra
unidad del recurso antes de liberar ninguna.
- No
implica la existencia, ni siquiera eventual, de bloqueo.
- Sí
implica que alguna secuencia infortunada de eventos dé como resultado un
bloqueo.
La diferencia
entre estado seguro e inseguro es que:
- A
partir de un estado seguro, el sistema puede garantizar la
conclusión de todos los procesos.
- A
partir de un estado inseguro, no existe tal garantía.
Ejemplo de
una transición de estado seguro a estado inseguro (ver Tabla 6.3).
- Dado
un estado actual seguro, ello no implica que vayan a ser seguros
todos los estados futuros.
Es
un algoritmo de planificación que puede evitar los bloqueos.
En
la analogía:
- Los
clientes son los procesos, las unidades de crédito son los recursos
del sistema y el banquero es el S. O.
- El
banquero sabe que no todos los clientes necesitaran su crédito máximo
otorgado en forma inmediata, por ello reserva menos unidades (recursos) de
las totales necesarias para dar servicio a los clientes.
Un
estado inseguro no tiene que llevar a un bloqueo.
El
algoritmo del banquero consiste en:
- Estudiar
cada solicitud al ocurrir ésta.
- Ver
si su otorgamiento conduce a un estado seguro:
- En caso positivo, se otorga la solicitud.
- En caso negativo, se la pospone.
- Para
ver si un estado es seguro:
- Verifica si tiene los recursos suficientes para
satisfacer a otro cliente:
- En caso afirmativo, se supone
que los préstamos se pagarán.
- Se verifica al siguiente
cliente cercano al límite y así sucesivamente.
- Si en cierto momento se vuelven a pagar todos los
créditos, el estado es seguro y la solicitud original debe ser aprobada.
Acá
también los procesos deben establecer sus necesidades totales de recursos
antes de su ejecución y dada una matriz de recursos asignados, el S.
O. debe poder calcular en cualquier momento la matriz de recursos necesarios
(ver Tabla 6.4).
Se
dispone de:
- “E”:
vector de recursos existentes.
- “P”:
vector de recursos poseídos.
- “A”:
vector de recursos disponibles.
El
algoritmo para determinar si un estado es seguro es el siguiente :
- Se
busca un renglón “R” cuyas necesidades de recursos no satisfechas
sean menores o iguales que “A”:
- Si no existe tal renglón, el sistema se bloqueará en
algún momento y ningún proceso podrá concluirse.
- Supongamos
que el proceso del renglón elegido solicita todos los recursos que
necesita y concluye:
- Se señala el proceso como concluido y se añaden sus
recursos al vector “A”.
- Se
repiten los pasos 1 y 2:
- Hasta que todos los procesos queden señalados como
concluidos, en cuyo caso, el estado inicial era seguro, o
- Hasta que ocurra un bloqueo, en cuyo caso, no lo era.
Se
permiten las condiciones de “exclusión mutua”, “espera por” y “no
apropiatividad”.
Los
procesos reclaman uso exclusivo de los recursos que requieren.
Los
procesos mantienen los recursos mientras piden y esperan por otros recursos
adicionales, pero no pueden apropiarse de un proceso que mantenga esos
recursos.
Las
peticiones son de un recurso a la vez.
El
S. O. puede conceder o negar cada una de las peticiones; si se niega una
petición:
- El
proceso retiene los recursos que ya tiene asignados.
- Espera
un tiempo finito hasta que le sea atendida la petición.
El
S. O. concede peticiones que den como resultado solo estados seguros.
Dado
que el sistema se mantiene siempre en estado seguro, todas las
peticiones serán atendidas en un tiempo finito.
Requiere
que exista un número fijo de recursos asignables, pero generalmente no
se puede contar con que el número de recursos se mantenga siempre constante.
Requiere
que la población de usuarios se mantenga constante, lo cual es
irrazonable.
Requiere
que el S. O. garantice que todas las peticiones serán concedidas en un
tiempo finito, pero en la realidad se requieren mayores garantías.
Requiere
que los procesos reintegren los recursos en un tiempo finito, pero en la
realidad se requieren mayores garantías.
Requiere
que los procesos indiquen sus necesidades máximas de recursos por adelantado,
lo cual generalmente no ocurre.
Generalmente
no es utilizado en S. O. reales.
Si
se puede garantizar que al menos una de las cuatro condiciones de
Coffman para el bloqueo nunca se satisface, entonces los bloqueos serán
imposibles por razones estructurales (enunciado de Havender).
Havender
sugirió las siguientes estrategias para evitar varias de las condiciones de
bloqueo:
- Cada
proceso:
- Deberá pedir todos sus recursos requeridos de una sola
vez.
- No podrá proceder hasta que le hayan sido asignados.
- Si a
un proceso que mantiene ciertos recursos se le niega una nueva petición,
este proceso deberá:
- Liberar sus recursos originales.
- En caso necesario, pedirlos de nuevo junto con los
recursos adicionales.
- Se
impondrá la ordenación lineal de los tipos de recursos en todos los
procesos:
- Si a un proceso le han sido asignados recursos de un
tipo dado, en lo sucesivo solo podrá pedir aquellos recursos de los tipos
que siguen en el ordenamiento.
Havender
no presenta una estrategia contra el uso exclusivo de recursos por parte de los procesos, pues se
desea permitir el uso de recursos dedicados.
Si ningún recurso se asignara de manera exclusiva a un solo
proceso, nunca tendríamos bloqueos,
pero esto es imposible de aplicar, en especial en relación a ciertos tipos de
recursos, que en un momento dado no pueden ser compartidos (ej.: impresoras).
Se
debe:
- Evitar
la asignación de un recurso cuando no sea absolutamente necesario.
- Intentar
asegurarse de que los menos procesos posibles puedan pedir el recurso.
Si
se puede evitar que los procesos que conservan recursos esperen más recursos,
se pueden eliminar los bloqueos.
Una
forma es exigir a todos los procesos que soliciten todos los recursos
antes de iniciar su ejecución; si un proceso no puede disponer de todos los
recursos, deberá esperar, pero sin retener recursos afectados.
Un
problema es que muchos procesos no saben el número de recursos
necesarios hasta iniciar su ejecución.
Otro
problema es que puede significar desperdicio de recursos, dado que todos los
recursos necesarios para un proceso están afectados al mismo desde su inicio
hasta su finalización.
Otro criterio aplicable consiste en:
- Exigir
a un proceso que solicita un recurso que libere en forma temporal los
demás recursos que mantiene en ese momento.
- Hacer
que el proceso intente luego recuperar todo al mismo tiempo.
Una
de las estrategias de Havender requiere que cuando a un proceso que mantiene
recursos le es negada una petición de recursos adicionales; deberá liberar sus
recursos y si es necesario pedirlos de nuevo junto con los recursos
adicionales.
La
implementación de esta estrategia niega la condición de “no apropiación” y
los recursos pueden ser retirados de los procesos que los retienen antes
de la terminación de los procesos.
El
problema consiste en que el retiro de ciertos recursos de un proceso puede
significar:
- La
pérdida del trabajo efectuado hasta ese punto.
- La
necesidad de repetirlo luego.
Una
consecuencia sería es la posible postergación indefinida de un proceso.
Una
forma es que un proceso solo está autorizado a utilizar un recurso en cada
momento:
- Si
necesita otros recursos, debe liberar el primero.
- Esto
resulta inaceptable para muchos procesos.
Otra
forma es la siguiente:
- Todos
los recursos se numeran globalmente.
- Los
procesos pueden solicitar los recursos en cualquier momento:
- Las solicitudes se deben hacer según un cierto orden
numérico (creciente) de recurso; debido a lo cual la gráfica de
asignación de recursos no tendrá ciclos.
- En
cada instante uno de los recursos asignados tendrá el número más grande:
- El proceso que lo posea no pedirá un recurso ya
asignado.
- El proceso terminará o solicitará recursos con números
mayores , que estarán disponibles:
- Al concluir liberará sus
recursos.
- Otro proceso tendrá el
recurso con el número mayor y también podrá terminar.
- Todos los procesos podrán
terminar y no habrá bloqueo.
Una variante
consiste en eliminar el requisito de adquisición de recursos en orden
creciente:
- Ningún
proceso debe solicitar un recurso con número menor al que posee en el
momento.
El
problema es que en casos reales podría resultar imposible encontrkkkar un orden
que satisfaga a todos los procesos.
Durante los estudios del sistema operativo hemos logrado adquirir conocimiento sobre el manejo y uso de la tecnología atreves de los diferentes programas, que se van actualizando desde su inicio hasta nuestros dias los cuales nos ayudan a estar mas en contacto con nuestros seres querido, nos proporcionan mas comodidad, nos permite conocer el mundo atreves de la misma tecnología.
ResponderEliminarFrancisco Heredia.
Matricula #4 1ero A.
Profe me Encanto su pagina ya que en ella puedo conocer informaciones que no conocia.
EliminarBarvara Mambru Manzanillo
Numero 13
2do A
De igual manera que mi compañera yo tambien pude conocer datos que no habia visto en el trancurso de mis estidos.
ResponderEliminarGregoria Mambru Manzanillo.
Nomero 02
2doA
me encanto su pagina ya que esta contiene datos informativos para el desarrollo del educando
ResponderEliminarYenifer Valera
Nomero 26
2oA
Este blog funciona como un medio de informacion para cada uno de lo estudiante que desean informarce.
ResponderEliminarNairovis de los Santo
Numero 21
2doA
Debo Enfatizar en maravillo que es este Blog no solo para mi como estudiante si no para todas las personas que logren conseguir este tipo de información en este blog entre los principales temas como son la informática Sistemas ,operativos , almacenamientos , archivos y sobre todo lo que mas me encanto que son los Algoritmos me llena de orgullo recomendar este blog y felicitar a su facilitador de información muchas Gracias.
ResponderEliminarNombre: Anyi Yuleisi Matos Feliz
Curso: 2do A
Numero: 15
Este comentario ha sido eliminado por un administrador del blog.
ResponderEliminar