Procesos y Administracion del Procesador

Qué es un Sistema Operativo

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.

Historia de los Sistemas Operativos - Generaciones

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.

Conceptos de los Sistemas Operativos

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

Introducción y Definiciones Sobre Procesos

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.

Estados de Procesos

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.

Procesamiento de Interrupciones

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:
 

• 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

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.

Planificación de Procesos

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.

Niveles de Planificación del Procesador

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

Planificación a Plazo Fijo

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.

Planificación Garantizada

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.

Planificación del Primero en Entrar Primero en Salir (FIFO)

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”.

Planificación de Asignación en Rueda (RR: Round Robin)

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:

1. La CPU es apropiada.
2. La CPU es otorgada al siguiente proceso en espera.
3. 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.

Tamaño del Cuanto o Quantum

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.

El cuanto óptimo varía de un sistema a otro y con la carga, siendo un valor de referencia 100 mseg (cien milisegundos).

Planificación del Trabajo Más Corto Primero (SJF)

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.

Planificación del Tiempo Restante Más Corto (SRT)

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.

Planificación el Siguiente con Relación de Respuesta Máxima (HRN)

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 p_r es la “prioridad”, t_e es el “tiempo de espera” y t_s es el “tiempo de servicio”:

Planificación por Prioridad

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.

Colas de Retroalimentación de Niveles Múltiples

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.

Política Versus Mecanismo de Planificación

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.

Planificación de Dos Niveles

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:

1. Se carga en la memoria principal cierto subconjunto de los procesos ejecutables.
2. El planificador se restringe a ellos durante cierto tiempo.
3. Periódicamente se llama a un planificador de nivel superior para efectuar las siguientes tareas:
1. Eliminar de la memoria los procesos que hayan permanecido en ella el tiempo suficiente.
2. Cargar a memoria los procesos que hayan estado en disco demasiado tiempo.
4. El planificador de nivel inferior se restringe de nuevo a los procesos ejecutables que se encuentren en la memoria.
5. 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

Introducción al Almacenamiento Real

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.

Organización y Administración del Almacenamiento

Organización del Almacenamiento

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.

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?

Jerarquía de Almacenamiento

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 ).

Estrategias de Administración del Almacenamiento

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.

Multiprogramación de Partición Fija: Traducción y Carga Relocalizables

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.

Protección en los Sistemas de Multiprogramación

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.

Fragmentación en la Multiprogramación de Partición Fija

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.

Multiprogramación de Partición Variable

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.

Compresión o Compactación de Almacenamiento

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.

Estrategias de Colocación del Almacenamiento

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.

Multiprogramación con Intercambio de Almacenamiento

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).

Introducción a la Organización del Almacenamiento Virtual

“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.

Conceptos Básicos de Almacenamiento Virtual

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).

Organización del Almacenamiento de Niveles Múltiples

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.

Traducción Dinámica de Direcciones en Sistemas de Paginación / Segmentación

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.

Compartimiento en un Sistema de Paginación / Segmentación

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.

Estrategias de Administración del Almacenamiento Virtual

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.

Estrategias de Reposición de Página

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

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.

Reposición de Página al Azar

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

Introducción

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.

Funciones del Sistema de 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.

El Sistema de Archivos

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.

Archivos

Se considerará el punto de vista del usuario.

Nombre de los Archivos

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.

Estructura de un Archivo

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.

Tipos de Archivos

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.

Acceso a un Archivo

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.

Seguridad

Los sistemas de archivos generalmente contienen información muy valiosa para sus usuarios, razón por la que los sistemas de archivos deben protegerla.

El Ambiente de Seguridad

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.

Principios del Diseño Para la Seguridad

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.

Medidas Preventivas

Limitar los intentos de acceso fallidos y registrarlos.

Registrar todos los accesos.

Tender trampas para atrapar a los intrusos.

Mecanismos de Protección

Dominios de Protección

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.

Listas Para Control de Acceso

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.

Principios del Hardware de E / S

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.

Dispositivos de E / S

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.

Controladores de Dispositivos

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.

Acceso Directo a Memoria (DMA)

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.

Utilización del “buffer”:

·         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.

Objetivos del Software de E / S

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.

Manejadores de Interrupciones

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.

Manejadores de Dispositivos

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.

Software de E / S Independiente del Dispositivo

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.

Software de E / S en el Espacio del Usuario

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.

Discos - Hardware Para Discos

Discos

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.

Hardware Para Discos

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.

Operación de Almacenamiento de Disco de Cabeza Móvil

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).

Algoritmos de Programación del Brazo del Disco

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”.

Porqué es Necesaria la Planificación de Discos

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.

Características Deseables de las Políticas de Planificación de Discos

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.

Optimización de la Búsqueda en Discos

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.

Planificación FCFS (Primero en Llegar, Primero en Ser Servido)

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.

Planificación SSTF (Menor Tiempo de Búsqueda Primero)

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.

Planificación SCAN

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.

Planificación SCAN de N - Pasos

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.

Planificación C - SCAN (Búsqueda Circular)

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.

Esquema Eschenbach

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.

Conceptos de Recursos

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.

Bloqueos y Condiciones Necesarias Para el Bloqueo

La secuencia de eventos necesarios para utilizar un recurso es la siguiente:

1. Solicitar el recurso.
2. Utilizar el recurso.
3. 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.

Áreas Principales en la Investigación de Bloqueos

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 Algoritmo del Avestrúz o de Ostrich

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.

Detección de Bloqueos

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 ?.

Gráficas de Asignación de Recursos

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 [).

Reducción de Gráficas de Asignación de Recursos

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).

Detección de Bloqueos de Forma “Un Recurso de Cada Tipo”

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:

1. Se considera a “N” como nodo inicial.
2. Se inicializan:
• La estructura de datos “L”como una lista vacía.
• Todos los arcos como no marcados.
3. 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.
4. 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.
5. 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.
6. 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.

Detección de Bloqueos de Forma “Varios Recursos de Cada Tipo”

Se considera un algoritmo basado en matrices para la detección de un bloqueo entre “n” procesos, “P₁” hasta “P_n”.

Se considera “m” el número de clases de recursos con:

• E₁ recursos de la clase 1.
• E₂ recursos de la clase 2.
• E_i 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:

• “A_i” 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 “P_i” poseídas en ese momento.

“Cij ”  es el número de instancias del recurso“ j” deseadas por “P_i”.

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 “A_i”es menor o igual que “B_i” 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:

1. Se busca un proceso no marcado “P_i” , para el cual el i -ésimo renglón de “R” sea menor que “A”.
2. 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.
3. Si no existe tal proceso, el algoritmo termina.

En el ejemplo tenemos 3 procesos y 4 clases de recursos (ver Figura 6.8 ).

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.

Cuándo Buscar los Bloqueos

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.

Recuperación de Bloqueos

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.

Recuperación Mediante la Apropiación

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.

Recuperación Mediante Rollback

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.

Recuperación Mediante la Eliminación de Procesos
 

• 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.

Evasión de Bloqueos

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.

Trayectorias de Recursos

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.

Estados Seguros e Inseguros

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.

Un estado inseguro :

• 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.

El Algoritmo del Banquero (de Dijkstra) Para Solo Un Recurso

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.

El Algoritmo del Banquero (de Dijkstra) Para Varios Recursos

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 :

1. 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.
2. 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”.
3. 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.

Asignación de Recursos por el Algoritmo del Banquero

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.

Debilidades del Algoritmo del Banquero

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.

Prevención de Bloqueos

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.

Prevención de la Condición de Exclusión Mutua

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.

Prevención de la Condición “detenerse y esperar” o “espera por”

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.

Prevención de la Condición de “no apropiación”

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.

Prevención de la Condición de “espera circular”

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.

Read More