• Author / Uploaded
• diyo123

• Categories
• Sistema operativo
• Unidad Central de procesamiento
• Programa de computadora
• Proceso (Computación)
• Hardware de la computadora

Citation preview

SISTEMAS OPERATIVOS

1

SISTEMAS OPERATIVOS RESUMEN

El texto presenta la evolución de los sistemas operativos a lo largo de la historia, introduciendo los conceptos fundamentales relativos a éstos, como podrían ser la administración de procesos. Así mismo, se ha tratado de dar todas las referencias posibles sobre Sistemas Operativos desconocidos para la mayoría y que han jugado un papel más o menos determinante en la historia. Se han incluido algunos que no han pasado de vigencia, pero lo citamos como simple curiosidad. De cualquier manera, la lista proporcionada es muy incompleta dado el gran número de Sistemas Operativos que existen o que han existido.

2

INDICE GENERAL RESUMEN …………………………………………………………………………. v INTRODUCCIÓN ………………………………………………………………….. xi CAPÍTULO 1 PANORAMA GENERAL ………………………………………………..

1

1.1. ¿Qué Es Un Sistema Operativo? ……………………………………………… 1 1.2. Tipos De Sistemas Operativos ………………………………………………………. 6 1.3. Historia De Los Sistemas Operativos – Generaciones ……………………………. 9 CAPÍTULO 2 ADMINISTRACIÓN DEL PROCESADOR ………………...................... 12 2.1. Introducción Y Definiciones Sobre Procesos ……………………………………….. 12 2.2. Estados De Procesos …………………………………………………………………. 15 2.3. Procesamiento De Interrupciones ……………………………………………………. 17 2.4. El Núcleo Del Sistema Operativo ……………………………………. ……………… 20 2.5. Políticas De Planificación De Procesos ………………………….. ………………… 21 2.6. Niveles De Planificación Del Procesador ……………………….. …………………. 22 2.7. Objetivos De La Planificación ………………………………………………………… 24 2.8. Criterios De Planificación ……………………………………………......................... 25 2.9. Planificación Apropiativa Versus No Apropiativa ………….………………………… 27 2.10. Algoritmos De Planificación De Procesos ………………………………………….. 29 2.10.1. Planificación Primero En Entrar, Primero En Servirse ………………………….. 29 2.10.2. Planificación Sigue El Trabajo Más Corto ………………………………………. 31 2.10.3. Planificación Por Prioridad ………………………………………………………… 33 2.10.4. Planificación Tiempo Restante Más Breve ………………………………………. 33 2.10.5. Planificación Round Robin …………………………………………………………. 36 2.10.6. Planificación De Colas De Multiples Niveles …………………………………….. 39

3

CAPITULO 3 ADMINISTRACIÓN DE PROCESOS CONCURRENTES …………....... 41 3.1. Procesos Concurrentes Asincrónicos …………………………………………………. 41 3.2. Procesamiento En Paralelo …………………………………………………………….. 41 3.3. Una Estructura Para Indicar El Paralelismo: Cobegin/Coend ………………………. 42 3.4. Exclusión Mutua …………………………………………………………………………. 44 3.5. Secciones Críticas ………………………………………………………….................... 48 3.6. Primitivas De Exclusión Mutua …………………………………………………………. 49 3.7. Implementación De Las Primitivas De Exclusion Mutua …………………………….. 51 3.8. Algoritmos De Exclusión Mutua …………………………………….. ………………… 52 3.8.1. Desarrollo Intuitivo …………………………………………………………………….. 52 3.9. Algoritmo De Dekker …………………………………………………….. …………….. 61 3.10. Algoritmo De Peterson ………………………………………………………………… 65 3.11. Exclusion Mutua De N-Procesos ……………………………………………………… 68 3.11.1. Algoritmo De Dijkstra ………………………………………………………………… 68 3.11.2. Algoritmo De Lamport ……………………………………………………………….. 71 3.12. Semáforos ………………………………………………………………………………. 75 3.12.1. Sincronización De Procesos Con Semáforos …………………………………….. 78 3.12.2. Bloqueos Mutuos Y Bloqueos Indefinidos ……………………………………....... 80 3.13. La Relación Productor – Consumidor ……………………………………………….. 85 3.14. Semáforos Contadores ……………………………………………………………….. 89 CAPÍTULO 4 ADMINISTRACIÓN DE LA MEMORIA …………………………………… 90 4.1. Introducción Al Almacenamiento Real ………………………………………………… 90 4.2. Requisitos Para La Administración De La Memoria ………………………………… 91 4.2.1. Reubicación …………………………………………………………………………… 91 3.2.2. Protección …………………………………………………………………………….. 93 4.2.3. Compartición …………………………………………………………………………..

4

93 4.2.4. Organización Lógica ………………………………………………………………….. 95 4.2.5. Organización Física …………………………………………………………………… 95 4.3. Carga De Programas En Memoria Principal …………………………………………. 96 4.3.1. Partición Fija …………………………………………………………………………… 96 4.3.1.1. Tamaños De Partición ……………………………………………………………… 96 4.3.1.2. Algoritmo De Ubicación ……………………………………………………………. 99 4.3.1.3. Partición Dinámica ………………………………………………………………….. 101 4.3.1.4. Algoritmo De Ubicación ……………………………………………………………. 103 4.3.1.5. Algoritmos De Reemplazo …………………………………………………………. 105 4.3.1.6. Reubicación …………………………………………………………………………. 105 4.4. Memoria Virtual …………………………………………………………………………. 106 4.4.1. Espacio De Direccionamiento Y Espacio De Memoria …………………………… 107 4.5. Protección De Memoria ………………………………………………………………… 109 CAPÍTULO 5 ADMINISTRACÓN DE LOS ARCHIVOS ………………………………… 110 5.1. Introducción ……………………………………………………………………………… 110 5.2. Funciones Del Administrador De Archivos ………………………………………….. 111 5.3. El Sistema De Archivos ………………………………………………………………… 112 5.4. Archivos ………………………………………………………………………………….. 114 5.4.1. Nombre De Los Archivos …………………………………………………………….. 114 5.4.2. Estructura De Un Archivo ……………………………………………………………. 114 5.4.3. Tipos De Archivos ………………………………………………………………….. ... 115 5.4.4. Acceso A Un Archivo ………………………………………………………………… 115 5.4.5. Atributos De Archivo ………………………………………………………………….. 116 5.4.6. Operaciones Con Archivos …………………………………………………………… 117 5.4.7. Archivos Mapeados A Memoria ……………………………………………………… 118

5

5.5. Directorios ……………………………………………………………........................... 119 5.5.1. Sistemas Jerárquicos De Directorios ……………………………………….……. 119 5.5.2. Nombre De Las Rutas De Acceso ………………………………………………….. 120 5.5.3. Operaciones Con Directorios ……………………………………………………... 121 5.6. Implantación Del Sistema De Archivos Y Sus Relaciones Con La Asignación Y Liberación De Espacio …………………………………………………. 122 5.6.1. Implantación De Archivos ……………………………………………………….…… 123 5.6.2. Implantación De Directorios …………………………………………………………. 130 5.6.3. Archivos Compartidos ………………………………………………………………… 130 CAPÍTULO 6 ENTRADA / SALIDA ………………………..……………………………... 134 6.1. Introducción ……………………………………………………………………………… 134 6.2. Principios Del Hardware De E/S ……………………………………………………… 134 6.2.1. Dispositivos De E/S ………………………………………………………………….. 135 6.2.2. Controladores De Dispositivos ……………………………………………………… 136 6.2.3. Acceso Directo A Memoria (Dma) ………………………………………………….. 138 6.3. Principios Del Software De E/S ……………………………………………………….. 140 6.3.1. Objetivos Del Software De E/S ……………………………………………………… 141 6.3.2. Manejadores De Interrupciones …………………………………………………….. 142 6.3.3. Manejadores De Dispositivos ……………………………………………………….. 143 6.4. Discos - Hardware Para Discos ………………………………………………………. 144 6.4.1. Discos …………………………………………………………………………………. 144 6.4.2. Hardware Para Discos ………………………………………………………………. 144 6.5. Operación De Almacenamiento De Disco De Cabeza Móvil ……………………… 145 6.6. Algoritmos De Programación Del Brazo Del Disco …………………………………. 147 6.7. Porqué Es Necesaria La Planificación De Discos ………………………………….. 147 6.8. Características Deseables De Las Políticas De Planificación De Discos ……….. 148

6

6.9. Optimización De La Búsqueda En Discos ………………………………………….. 149 6.9.1. Planificación Fcfs (Primero En Llegar, Primero En Ser Servido) ………………. 149 6.9.2. Planificación Sstf (Menor Tiempo De Búsqueda Primero) ……………………… 149 6.9.3. Planificación Scan …………………………………………………………………… 150 6.9.4. Planificación Scan De N – Pasos ……………………………………………….…. 150 6.9.5. Planificación C - Scan (Búsqueda Circular) ………………………………….…… 151 6.9.6. Esquema Eschenbach …………………………………………………….………… 151 6.9.7. Conclusiones ……………………………………………………………….………… 151 BIBLIOGRAFIA ........................................................................................................ 152

7

INDICE DE FIGURAS 1.1: Componentes de un sistema de cómputo …………………………………… 2 1.2: Modelo del sistema operativo para un solo usuario ……………………….. 2 1.3: Sistemas Operativos para Red ………………………………………………. 5 1.4: Hardware del sistema de cómputo …………………………………………... 6 2.1: Multiprogramación de 4 programas ………………………………………….. 14 2.2: Un proceso puede estar en ejecución, bloqueado o listo …………………. 15 2.3: Niveles de planificación del procesador …………………………………….. 23 2.4: Tipos de planificación del procesador ………………………………………. 28 2.5: Diagrama de secuencia para los trabajos de A,B,C que utiliza el algoritmo FCFS …………………………………………………………………. 30 2.6: Diagrama de secuencia para los trabajos C,B,A con el algoritmo FCFS .. 30 2.7: Diagrama de tiempo de la secuencia de tareas B, D, A, C, con el algoritmo SJN ……………………………………………………………………. 32 2.8: Diagrama de tiempo de la secuencia de trabajos A,B,C,D con el algoritmo apropiante SRT ……………………………………………………… 34 2.9: Línea de tiempo para la misma secuencia de trabajos A,B,C,D, con el algoritmo SJN no apropiativa ………………………………………………….. 35 2.10: Diagrama de tiempo para la secuencia de trabajos A,B,C,D con el algoritmo de round robin apropiativo ……………………………………….. 37 2.11: Cambios de contexto de el trabajo A con tres quantum de tiempo ……… 39 4.1: Requisitos de direccionamiento para un proceso …………………………… 92 4.2: Ejemplo de participación estática de una memoria de 4Mb ……………… 98 4.3: Asignación de memoria con participación fija ……………………………….. 100 4.4: Efectos de la participación dinámica ……………………………………….…. 102 4.5: Ejemplo de una configuración de memoria antes y después de asignar un bloque de 16 Kb ……………………………………………………………… 103 4.6: Relación entre espacios de dirección y de memoria en un sistema de memoria virtual …………………………………………………………………… 108 4.7: Tabla de memoria para mapear una dirección virtual ………………………. 109 5.1: Un solo directorio compartido por todos los usuarios ……………………….. 119 5.2: Un directorio por usuario ……………………………………………………….. 120 5.3: Un árbol arbitrario por usuario …………………………………………………. 120 5.4: Encadenamiento de bloques o lista ligada de bloques ……………………… 125 5.5: Encadenamiento de bloques de índice ………………………………………. 126 5.6: Transformación de archivos orientada hacia bloques ………………………. 129 5.7: Esquema de un nodo-i ………………………………………………………….. 131 6.1: Un controlador realiza completamente una transferencia DMA ……………. 139 6.2: Factores de separación: sin separación, separación simple y separación doble ………………………………………………………………………………. 140 6.3: Capas del sistema de entrada / salida y las principales funciones de cada capa ……………………………………………………………………………….. 141 6.4: Esquema de un disco de cabeza móvil ……………………………………….. 145 6.5: Componentes del acceso a un disco ………………………………………….. 146

8

INDICE DE TABLAS 2.1: Tipos de interrupciones …………………………………………………………. 18 2.2. Disciplinas de planificación del procesador …………………………………... 28 2.3: Comparación de los algoritmos de planificación …………………………….. 40 4.1. Técnicas de administración de memoria ……………………………………… 98 6.1: Controladores de E/S, direcciones de E/S y vector de interrupciones ……. 137

9

INTRODUCCION

A finales de los 40's el uso de computadoras estaba restringido a aquellas empresas o instituciones que podían pagar su alto precio, y no existían los sistemas operativos. En su lugar, el programador debía tener un conocimiento y contacto profundo con el hardware, y en el infortunado caso de que su programa fallara, debía examinar los valores de los registros y páneles de luces indicadoras del estado de la computadora para determinar la causa del fallo y poder corregir su programa, además de enfrentarse nuevamente a los procedimientos de apartar tiempo del sistema y poner a punto los compiladores, ligadores, etc; para volver a correr su programa, es decir, enfrentaba el problema del procesamiento serial. Es decir, se comenzó a ver que las tareas mismas del operador podían plasmarse en un programa, el cual a través del tiempo y por su enorme complejidad se le llamó "Sistema Operativo". Así, tenemos entre los primeros sistemas operativos al Fortran Monitor System ( FMS ) e IBSYS [Tan92]. Al tratar de crear un solo sistema operativo para computadoras que podían dedicarse a un propósito, al otro o ambos, puso en evidencia la problemática del trabajo en equipos de análisis, diseño e implantación de sistemas grandes. Surge también en la tercera generación de computadoras el concepto de la multiprogramación, porque debido al alto costo de las computadoras era necesario idear un esquema de trabajo que mantuviese a la unidad central de procesamiento más tiempo ocupada, así como el encolado (spooling ) de trabajos para su lectura hacia los lugares libres de memoria o la escritura de resultados. Sin embargo, se puede afirmar que los sistemas durante la tercera generación siguieron siendo básicamente sistemas de lote. En la cuarta generación la electrónica avanza hacia la integración a gran escala, pudiendo crear circuitos con miles de transistores en un centímetro cuadrado de silicón y ya es posible hablar de las computadoras personales y las estaciones de trabajo. Surgen los conceptos de interfaces amigables intentando así atraer al público en general al uso de las computadoras como

10

herramientas cotidianas. Se hacen populares el MS-DOS y UNIX en estas máquinas. También es común encontrar clones de computadoras personales y una multitud de empresas pequeñas ensamblándolas por todo el mundo. Para mediados de los 80's, comienza el auge de las redes de computadoras y la necesidad de sistemas operativos en red y sistemas operativos distribuidos. La red mundial Internet se va haciendo accesible a toda clase de instituciones y se comienzan a dar muchas soluciones (y problemas) al querer hacer convivir recursos residentes en computadoras con sistemas operativos diferentes. Para los 90's el paradigma de la programación orientada a objetos cobra auge, así como el manejo de objetos desde los sistemas operativos. Las aplicaciones intentan crearse para ser ejecutadas en una plataforma específica y poder ver sus resultados en la pantalla o monitor de otra diferente (por ejemplo, ejecutar una simulación en una máquina con UNIX y ver los resultados en otra con DOS). Los niveles de interacción se van haciendo cada vez más profundos. En este libro ofrece una cobertura a los fundamentos de sistemas operativos: Capítulo 1 Panorama General, Capítulo 2 Administración Del Procesador, Capitulo 3 Administración De Procesos Concurrentes, Capítulo 4 Administración De La Memoria, Capítulo 5 Administración De Los Archivos Y Capítulo 6 Entrada / Salida; en estos capítulos se examinan los desarrollos recientes más importantes que se han alcanzado en el diseño de los sistemas operativos. El objetivo principal de este texto es proporcionar al lector una comprensión sólida de los mecanismos clave de los sistemas operativos modernos, las concisiones y las decisiones que acarrean el diseño de un sistema operativo y el contexto en que este opera.

Los Autores

11

SISTEMAS OPERATIVOS

12

(Revés de la Carátula)

Este libro trata sobre los aspectos referidos a los Sistemas Operativos. Para aquellos lectores que solo deseen adquirir o refrescar conocimientos relacionados con los sistemas operativos en general; será suficiente con la lectura de la primera parte, en tanto que para aquellos que deseen un conocimiento más profundo, teniendo presente la problemática de los sistemas operativos modernos, será necesario avanzar en la lectura del primer grupo de temas; así mismo, si además se desea incursionar aspectos complementarios más importantes se sugiere la lectura del mencionado texto en su forma total. Es preciso señalar además que este libro esta destinado a los alumnos de una carrera de grado en sistemas e informática, que deban hacer un curso de sistemas operativos, pudiendo ser de utilidad según la profundidad del curso, que aborda el mencionado texto.

Los Autores.

13

CAPÍTULO 1 PANORAMA GENERAL

1.1. ¿QUÉ ES UN SISTEMA OPERATIVO? Una de las definiciones más comúnmente aceptadas expresa: -

Es un programa que actúa como intermediario entre el usuario de una computadora y el hardware.

-

Un S. O. es un grupo de programas de proceso con las rutinas de control Necesarias para mantener continuamente operativos dichos programas”.

El objetivo primario de un Sistema Operativo es: Optimizar todos los recursos del sistema para soportar los requerimientos y hacer de un sistema de cómputo. Utilizable de manera cómoda; por el usuario y el objetivo secundario es usar el hardware de la computadora de la forma eficiente. -

Los programas de sistema controlan la operación de la computadora en sí y los programas de aplicación 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 sobre el hardware para poder 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 se muestre en la figura 1.1. éste puede dividirse en 4 componentes; el hardware, el sistema operativo, programas de aplicación y los usuarios.

14

Usuario

Usuario

1

2

Compilador

...

Usuario

n

ensamblador

sistema de base de datos

Sistema Programas de sistema Operativo y de aplicación Hardware de la computadora

Figura 1.1: Componentes de un sistema de cómputo.

En términos mas simples, el S.O. es el gerente ejecutivo del sistema

de

computo que se encarga de la administración del hardware y el software; lo que es lo mismo administrar los archivos, memoria, procesador y dispositivos; así

mismo controla quien puede utilizar el sistema y de que manera (interfaz

de comando del usuario). Por la tanto, cuando en usuario envía un comando el S.O. desde asegurarse que se ejecute y caso contrario indica el error que no permita su ejecución. En la figura 1.2. se muestra una pirámide, que nos permitirá extender mejor la función del sistema operativo.

Interfaz del comando del usuario

Administrador de procesador

Administrador de medidas

Administrador de archivos

Administrador de archivos

Figura 1.2: Modelo del sistema operativo para un solo usuario.

La base de la pirámide muestra los 4 “administradores” esenciales del todo el 15

sistema

operativo: administrador de memoria procesador, dispositivos y

archivos; estos administradores son la base de todos los sistemas operativos. La interfaz de comando del usuario es desde el cual las usuario, es desde el cual los usuarios emiten los comandos

al S.O; este es un componente

especifico en cada sistema operativo. Sin importar el tamaño o configuración del sistema, cada uno de los administradores deben realizar las siguientes tareas: -

Monitoreo constante de sus recursos.

-

Obligar al cumplimiento de las políticas que determinan, quien obtiene, cuando y cuanto tiempo.

-

Asignar los recursos cuando es apropiada.

-

Liberar el recurso – recuperarlo – cuando es conveniente.

Citaremos algunas funciones relevantes de los administradores. -

El administrador de memoria esta a cargo de la memoria principal o RAM. Comprueba la validez de cada solicitud de espacio de memoria y, si se trata de una solicitud legal, le asigna un porción que todavía no este en uso; otra función es proteger el espacio en la memoria principal que ocupa el sistema operativo...etc.

-

El administrador del procesador decide

como asignar la unidad

de

procesamiento central (CPU); otra función también es de controlar el estado de cada proceso...etc. -

El administrador de dispositivos vigila todos los dispositivos, cuales y unidades del sistema (periféricos), este administrador

asigna

el

dispositivo, inicia su operación y lo libera. etc. -

El administrador de archivo, lleva el control de todo el archivo en el sistema, incluyendo archivos de datos ensambladores, compiladores y programas de aplicación; mediante el uso de políticas de acceso predeterminadas, obliga a cada archivo a cumplir las restricciones de acceso. Etc.

16

Estos administradores no solo cumplen sus tareas individuales. También deben ser capaces de trabajar en armonía con los otros administradores. A continuación

mostraremos los pasos que se presentan al ejecutar un

programa. 1.

El administrador de dispositivos recibe impulsos eléctricos del teclado, codifica el tecleo para formar el comando y envía el comando a la interfaz de comando del usuario, donde el administrador del procesador lo valida.

2.

Luego, el administrador del procesador manda un mensaje de reconocimiento para que aparezca en el monitor de video, de manera que quien escribió sepa que se envió el comando.

3.

Cuando el administrador del procesador recibe el comando, determina si hay que traer el programa correspondiente de donde esté almacenado o si ya está

en la memoria, después el cual notifica al administrador

apropiado. 4.

Si el programa está almacenado, el administrador de archivos debe calcular su localización exacta en el disco y pasar el mismo y registrar su ubicación exacta en la memoria.

5.

Una vez que el programa se halla en la memoria, el administrador de ésta debe controlar su localización y progreso conforme lo ejecuta el administrador del procesador.

6.

Cuando termina la ejecución del programa, éste manda un mensaje de “terminado” de regreso al administrador del procesador.

7.

Por último, el administrador del procesador manda el mensaje de “terminado” de vuelta al administrador de dispositivos, que lo muestra en el monitor para que lo vea el usuario.

Aunque ésta es una demostración simplificada de una operación complicada, ilustra la increíble precisión requerida por el sistema operativo. Recuerde, ningún administrador por sí solo puede llevar

a cabo

sus tareas sin la

cooperación activa de las demás partes. Los sistemas operativos con capacidad de red tiene un quinto administrador 17

esencial, conocido como administrador de red que proporciona

una forma

conveniente para los usuarios, de compartir recursos y al mismo tiempo, controlar su acceso a los mismos. Estos recursos incluyen hardware y software; a continuación se muestra la figura 1.3, donde se observa una pirámide de cinco lados (base).

ADMINISTRADOR DE PROCESADOR ADMINISTRADOR DE MEMORIA ADMINISTRADOR DE DISPOSITIVOS

ADMINISTRADOR DE RED ADMINISTRADOR DE ARCHIVOS

Figura 1.3: Sistemas Operativos para Red.

Para apreciar la función del sistema operativo, es necesario definir los aspectos esenciales del hardware del sistema de la computadora, la maquina física y sus componentes electrónicos, incluyendo los chips de memoria, los dispositivos de entrada/salida, los dispositivos de almacenamiento y la unidad de procesamiento central. La memoria principal es donde se almacena los datos y las instrucciones para ser procesados. Los dispositivos de entrada/salida, incluyen toda la unidad periférico del sistema, como impresora, unidad de discos, unidades de CD, dispositivos de cinta magnética, etc. El CPU es el “cerebro” que apoyado en la circuitería electrónica. Controla la interpretación y ejecución de las instrucciones. En esencia controla la operación de la totalidad de sistemas de cómputo, así como se ilustra en la figura. 1.4.

18

Pantalla de video

Interfaz de video Memoria principal

Unidad aritmética y lógica

Controlad or de disco

Bus de Control

Registros

Accionador de discos Discos

módem

Interfaz serial

Control Interno

Interfaz paralela

CPU

Impresora

Interfaz de teclado

teclado

Figura 1.4: Hardware del sistema de cómputo.

1.2. TIPOS DE SISTEMAS OPERATIVOS Los

sistemas operativos para las computadoras grandes y pequeñas se

clasifican en cuatro clases, los cuales se distinguen

por su tiempo de

respuesta y la forma en que se introducen los datos en el sistema; estas son: -

Sistemas por lotes.

-

Sistemas interactivos.

-

Sistemas en tiempo real.

-

Sistemas híbridos.

Los Sistemas Por Lotes (Batch).- Existen desde las primeras computadoras

19

que se apoyan en tarjetas perforadas o en cinta, los cuales es introducida una tarea mediante la agrupación de las tarjetas en un paquete y se corría todo el paquete a través de un lector de tarjetas como un grupo (lote); la eficiencia del sistemas se media en producción (cantidad de tareas completadas en un tiempo determinado (30 tareas / hora) este sistema no es común actualmente Los Sistemas Interactivos (Sistemas de Tiempo Compartido).- Dan un tiempo de retorno más rápido que los Sistemas de tiempo real, de los cuales hablaremos más adelante. Se introdujeron para satisfacer las demandas de usuarios que necesitaban un tiempo de retorno rápido al eliminar los errores de sus programas, el S. O. requería el desarrollo de software de tiempo compartido, lo que permitiría a cada usuario interactuar directamente con el sistema del computo vía comandos introducidos a partir de una terminal de tipo máquina de escribir. El sistema operativo proporciona una retroalimentación al usuario y el tiempo de respuesta se puede medir en minutos o en segundos, según la cantidad de usuarios activos. Los Sistemas de Tiempo real, son lo más rápido de l os cuatro y se le utiliza en entornos de “tiempo critico”, donde los datos se deben procesar con suma rapidez porque la salida afecta decisiones inmediatas. Los sistemas de tiempo real se utilizan para vuelos espaciales, control de trafico en aeropuertos, aeronaves de alta velocidad, procesos industriales, equipo médico complicado, distribución de electricidad y conmutación telefónica. Un sistema de tiempo rela debe ser 100% sensible. El tiempo de respuesta se mide en fracciones de segundo, aunque esto en la práctica es un ideal que no se logra a menudo. Los sistemas hídricos, son una combinación de sistemas

en lotes e

interactivos. Parecen interactivos porque los usuarios individuales pueden tener acceso al sistema mediante terminales y obtener una respuesta rápida,; pero cuando la carga interactiva es ligera, este tipo de sistemas acepta y opera programas en lotes en un segundo plano. Un sistema hídrico aprovecha el tiempo libre entre

las demandas de

procedimiento para ejecutar programas que no necesitan ayuda significativa

20

del operador. Muchos sistemas de cómputo grandes son híbridos Por lo tanto podemos concluir con 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. 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 (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. 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. es una interfaz con:

21

-

Los Operadores.

-

Los Programadores de aplicaciones.

-

Los Programadores de sistemas (administradores del S. O.).

-

Los Programas.

-

El Hardware.

-

Los Usuarios.

El S. O. debe presentar al usuario el equivalente de una máquina extendida o máquina virtual que sea más fácil de programar que el hardware subyacente.

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

Carencia total de S. O.

-

Completo acceso al lenguaje de máquina.

Primera generación (1945-1955): tubos de vació y conexiones. -

Carencia de S. 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): -

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

22

sistema para incrementar el poder de procesamiento. -

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: -

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.

-

Protección por hardware del contenido de cada partición de memoria.

-

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 más lentos.

-

Son sistemas de modos múltiples, es decir que deben soportar sistemas de propósitos generales; son grandes y complejos pero muy poderosos.

-

Interponen una capa de software entre el usuario y el hardware.

-

Aparecen los lenguajes de control de trabajos, necesarios para especificar el trabajo y los recursos requeridos.

-

Soportan timesharing (tiempo compartido), variante de la multiprogramación con usuarios conectados mediante terminales en línea,

23

permitiendo la operación en modo interactivo o conversacional. -

Aparecen los sistemas de tiempo real, que requieren tiempos de respuesta muy exigentes, especialmente para usos industriales o militares.

-

Se difunden las computadoras de rango medio.

Cuarta Generación (1980-1990): computadoras personales: -

Aparición de software amigable con el usuario, destinado a usuarios no profesionales y con una interfase gráfica muy desarrollada.

-

Desarrollo de sistemas operativos de red y sistemas operativos distribuidos.

-

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: a) Controlador de interfaz de la red y su software de bajo nivel. b) Software para conexión y acceso a archivos remotos, etc.

-

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

-

Aparición de emuladores de terminal para el acceso a equipos remotos desde computadoras personales (PC).

-

Gran énfasis en la seguridad, en especial por el desarrollo de los sistemas de comunicaciones de datos. 24

-

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.

-

Proliferación de sistemas de bases de datos, accesibles mediante redes de comunicación.

CAPÍTULO 2 ADMINISTRACIÓN DEL PROCESADOR

2.1. 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. No hay un acuerdo universal sobre una definición de proceso, pero sí algunas definiciones aceptadas tales como: -

Un programa que se está ejecutando.

-

Una actividad asincrónica.

-

El emplazamiento del control de un procedimiento que está siendo ejecutado.

-

Aquella que se manifiesta por la existencia en el Sistema Operativo de un bloque de control de proceso.

-

Es conocida como una tarea, es una instancia de un programa ejecutable.

-

Aquella entidad a la cual son asignados los procesadores.

-

La unidad despachable.

-

Es una entidad activa que requiere un conjunto de recursos para llevar acabo su función, entre ellos un procesador y registros especiales.

Una hebra de control es una porción de un proceso que se puede ejecutar de manera independientemente. Por ejemplo, si su sistema permite que los procesos tengan una sola hebra de control y Ud. Desea una serie de imágenes 25

en el sitio web de un amigo, puede instruir al navegador (Brouser), para que establezca una conexión entre ambos sitios y descargar una imagen a la vez. Sin embargo, si su sistema permite que sus procesos tengan múltiples hebras de control, puede solicitar varias imágenes al mismo tiempo y el navegador o explorador establecerá múltiples conexiones y descargará varias imágenes a la vez. El procesador, también conocido como CPU (central unit processor), es la parte de la maquina que lleva a caso los cálculos y ejecuta los programas. En sistemas de multiprogramación la cpu alterna de programa en programa, en un esquema de seudoparalelismo, 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

26

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. Figura 2.1, y 2.2.

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.

-

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:



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; tal como se muestra en la figura 2.1. y 2.2. UN CONTADOR DE PROGRAMA

A B C

ALTERNADOR DE PROCESOS MODELO CONCEPTUAL DE CUATRO 27 PROCESOS SECUENCIALES INDEPENDIENTES CUATRO CONTADORES DE PROGRAMA

D A

C

D

B

Figura 2.1: Multiprogramación de 4 programas. TRANSACCIONES ENTRE LOS ESTADOS 1. El proceso se bloquea en espera de datos.

EN

1

EJECUCIÓN

2

2. El planificador elige otro proceso. 3. El planificador elige este proceso.

3

4. Los datos están disponibles.

4 BLOQUEAD

LISTO

O

Figura 2.2: Un proceso puede estar en ejecución, bloqueado o listo.

2.2. 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 entre 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

28

“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 iniciales 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: 29

-

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.

2.3. 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: -

“SVC (llamada al supervisor)”: es una petición generada por el usuario 30

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.

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

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

-

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

 -

“De

Un intento de ejecutar un código de operación inválido. verificación

de

máquina”:

son

ocasionadas

por

un

mal

funcionamiento del hardware; en la tabla 2.1. se puede observar los diferentes tipos de interrupciones. 31

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

32

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: a) Proceso que estaba en ejecución en el momento de la interrupción. b) Proceso de listo de más alta prioridad.

 La acción precedente depende de si el proceso de interrupción es: a) “Apropiativo” : obtiene la cpu solo si no hay procesos de listos. b) “No apropiativo” : obtiene de nuevo la cpu.

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

33

-

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 designació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.

2.5. POLÍTICAS DE PLANIFICACIÓN DE PROCESOS En un entorno de multiprogramación existen por lo general más trabajos por ejecutar de los que se pueden correr en un momento dado. Antes que el sistema operativo pueda planificarlos, necesita resolver tres limitaciones del sistema: 1) Existe un número finito de recursos (como unidades de disco, impresoras y unidades de cinta). 2) Algunos recursos, una vez asignados, no pueden recibir otro trabajo (como las impresoras). 3) Algunos recursos requieren la intervención del operador – esto es, no se pueden reasignar de manera automática de un trabajo a otro (como las unidades de cinta). ¿Cuál es una “buena” política de planificación de procesos? Se presentan a la mente varias opciones, pero note que en la lista siguiente algunas se contradicen. -

Maximizar la Producción ejecutando tanto trabajos como sea posible en 34

un tiempo

dado. Esto es fácil

si se ejecuta trabajos breves o sin

interrupciones. -

Minimizar el Tiempo de Respuesta. Contestando rápidamente solicitudes interactivas, esto sería factible ejecutando nada más trabajos interactivos y dejando que los trabajos por lotes esperen hasta que la carga interactiva desaparezca.

-

Minimizar el Tiempo de Retorno. Introduciendo y sacando con rapidez trabajo completo del sistema. Para esto se corren primero los trabajos por lotes (porque estos se pueden agrupar para ejecutarse con mayor eficiencia que los trabajos interactivos).

-

Minimizar el Tiempo de Espera sacando los trabajos de cola de LISTO tan rápido como sea posible. Esto sólo es posible reduciendo en número de usuarios permitidos en

el sistema, de manera que el CPU esté

disponible cada que un trabajo entre en cola de LISTOS. -

Maximizar la Eficiencia de la CPU manteniendo al CPU ocupado al 100 por ciento del tiempo. Esto solo es viable ejecutando trabajos limitados por el CPU (no por entradas y salidas).

-

Asegurar la Justicia para todos los Trabajos dando a todos una cantidad igual de tiempo de CPU y de E/S. Esto es posible sin dar tratamiento especial alguno a los trabajos, sean cuales sean sus características de procesamiento o prioridad.

Como podemos ver, si el sistema da preferencia a un tipo de usuario, perjudica a otro y no utiliza sus recursos con eficiencia. La decisión final es del diseñador del sistema, que debe definir qué criterios son de mayor importancia para dicho sistema. Por ejemplo, usted podría decidir “Maximizar la utilización del CPU, minimizar el tiempo de respuesta y equilibrar el uso de los componentes de sistema a través de una mezcla de procesos limitados por entradas y salida y CPU”. Por lo tanto, seleccionaría la política de planificación que satisfaga con mayor precisión sus criterios.

2.6. NIVELES DE PLANIFICACIÓN DEL PROCESADOR 35

Se consideran tres niveles importantes de planificación, los que se detallan a continuación: -

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; tal como se muestra TRABAJOS ESPERANDO ENTRADA

en la figura 2.3.

ENTRADA DE TRABAJOS TRABAJOS ESPERANDO INICIACION INICIACIÓN DE TRABAJOS

PLANIFICACIÓN DE ALTO NIVEL

TRABAJOS SUSPEND. ESPERANDO ACTIVAC. SUSPENDER

PLANIFICACIÓN DE NIVEL INTERMEDIO

PROCESOS ACTIVOS

ACTIVAR

DESPACHO PROCESOS EN EJECUCIÓN

36 TERMINAR

TERMINADO

PLANIFICACIÓN DE BAJO NIVEL

Figura 2.3: Niveles de planificación del procesador.

2.7. OBJETIVOS DE LA PLANIFICACIÓN Los objetivos de la planificación del procesador son los siguientes e involucran a los conceptos detallados seguidamente: -

-

Ser justa: 

Todos los procesos son tratados de igual manera.



Ningún proceso es postergado indefinidamente.

Maximizar la capacidad de ejecución: 

-

Maximizar el número de procesos servidos por unidad de tiempo.

Maximizar el número de usuarios interactivos que reciban unos tiempos de respuesta aceptables: 

-

En un máximo de unos segundos.

Ser predecible: 

Un trabajo dado debe ejecutarse aproximadamente en la misma cantidad de tiempo independientemente de la carga del sistema.

-

Minimizar la sobrecarga: 

-

No suele considerarse un objetivo muy importante. Equilibrar el uso de recursos:

 -

Favorecer a los procesos que utilizarán recursos infrautilizados. Equilibrar respuesta y utilización:



La mejor manera de garantizar buenos tiempos de respuesta es disponer de los recursos suficientes cuando se necesitan, pero la

37

utilización total de recursos podrá ser pobre. -

Evitar la postergación indefinida: 

Se utiliza la estrategia del “envejecimiento”.



Mientras un proceso espera por un recurso su prioridad debe aumentar, así la prioridad llegará a ser tan alta que el proceso recibirá el recurso esperado.

-

Asegurar la prioridad: Los mecanismos de planificación deben favorecer a los procesos



con prioridades más altas. -

Dar preferencia a los procesos que mantienen recursos claves: Un proceso de baja prioridad podría mantener un recurso clave,



que puede ser requerido por un proceso de más alta prioridad. Si el recurso es no apropiativo, el mecanismo de planificación



debe otorgar al proceso un tratamiento mejor del que le correspondería normalmente, puesto que es necesario liberar rápidamente el recurso clave. -

Dar mejor tratamiento a los procesos que muestren un “comportamiento deseable”: Un ejemplo de comportamiento deseable es una tasa baja de



paginación. -

Degradarse suavemente con cargas pesadas: Un mecanismo de planificación no debe colapsar con el peso de



una exigente carga del sistema. Se debe evitar una carga excesiva mediante las siguientes



acciones: a)

No permitiendo que se creen nuevos procesos cuando la carga ya es pesada.

b)

Dando servicio a la carga más pesada al proporcionar un nivel

38

Moderadamente reducido de servicio a todos los procesos. Muchas de estas metas se encuentran en conflicto entre sí, por lo que la planificación se convierte en un problema complejo.

2.8. CRITERIOS DE PLANIFICACIÓN Para realizar los objetivos de la planificación, un mecanismo de planificación debe considerar lo siguiente. -

La limitación de un proceso a las operaciones de Entrada / Salida: cuando un proceso consigue la cpu, ¿la utiliza solo brevemente antes de generar una petición de Entrada/ Salida?.

-

La limitación de un proceso a la cpu: cuando un proceso obtiene la cpu, ¿tiende a usarla hasta que expira su tiempo?.

-

Si un proceso es por lote (batch) o interactivo: los usuarios interactivos deben recibir inmediato servicio para garantizar buenos tiempos de respuesta.

-

¿Qué urgencia tiene una respuesta rápida?: Por ejemplo un proceso de tiempo real de un sistema de control que supervise una refinería de combustible requiere una respuesta rápida, más rápida que la respuesta requerida, por un proceso en lotes (batch) que deberá entregarse al día siguiente.

-

La prioridad de un proceso: A mayor prioridad mejor tratamiento.

-

Frecuentemente un proceso genera fallas (carencias) de página: 

Probablemente los procesos que generan pocos fallos de página hallan acumulado sus “Conjuntos de trabajo” en el almacenamiento principal.



Los procesos que experimentan gran cantidad de fallos de página aún no han establecido sus conjuntos de trabajo.



Un criterio indica favorecer a los procesos que han establecido sus conjuntos de trabajos. 39

Otro criterio indican favorecer a los procesos con una taza alta de



fallos de página ya que rápidamente generaran una petición de E/S. -

Frecuentemente un proceso ha sido apropiado por otro de más alta prioridad, lo cual significa los siguiente: A menudo los procesos apropiados deben recibir un tratamiento



menos favorable. Cada vez que el Sistema Operativo asume la sobrecarga para



hacer ejecutar este proceso, el corto tiempo de ejecución antes de la apropiación no justifica la sobrecarga de hacer ejecutar al proceso en primer lugar. -

¿Cuánto tiempo de ejecución real ha recibido el proceso?: un criterio considera que debe ser favorecido un proceso que ha recibido muy poco tiempo de cpu.

-

¿Cuánto tiempo adicional va a necesitar el proceso para terminar?: los tiempos promedio de espera pueden reducirse priorizando los procesos que requieren de un tiempo de ejecución mínimo para su terminación, pero pocas veces es posible conocer la cantidad de tiempo adicional que cada proceso necesita para terminar.

2.9. PLANIFICACIÓN APROPIATIVA VERSUS NO APROPIATIVA Las Disciplinas de Planificación pueden ser Apropiativas o No Apropiativas. Las principales características de la planificación apropiativa son las siguientes, ver figura 2.4. -

Es útil cuando los procesos de alta prioridad requieren atención rápida.

-

Es importante para garantizar buenos tiempos de respuesta en sistemas interactivos de tiempo compartido.

-

Tiene un costo en recursos, ya que el intercambio de contexto implica sobrecarga y además requiere mantener muchos procesos en el

40

almacenamiento principal, en espera de la cpu, lo que también implica sobrecarga. Las principales características de la planificación no apropiativa son las siguientes: -

Signifique los trabajos “largos” hacen esperar a los trabajos “cortos”.

-

Logra más equidad en el tratamiento de los procesos.

-

Logra hacer más predecibles los tiempos de respuesta puesto que los trabajos nuevos de prioridad alta no pueden desplazar a los trabajos en espera.

El diseño de un mecanismo apropiativo hace necesario considerar las arbitrariedades de casi cualquier esquema de prioridades, en razón de que muchas veces las propias prioridades no son asignadas en forma significativa. El mecanismo debería ser sencillo pero efectivo y significativo, a continuación se muestra la tabla 2.2. donde se describe los conceptos de apropiativa y no apropiativa.

Disciplina

Descripción

“Apropiativa”

Una vez que se le ha otorgado la cpu a un proceso, le puede ser retirada.

“No Apropiativa”

Una vez que se le ha otorgado la cpu a un proceso, no le puede ser retirada

Tabla 2.2: Disciplinas de planificación del procesador.

41

Figura 2.4: Tipos de planificación del procesador.

2.10. ALGORITMOS DE PLANIFICACIÓN DE PROCESOS El planificador de procesos se apoya

en un algoritmo de planificación de

procesos, basado en una política especifica para asignar al CPU y mover los trabajos por el sistema. Los primeros

sistemas

operativos

utilizaban políticas no apropiativas,

diseñadas para mover los trabajos por lotes a través del sistema con tanta eficiencia como era posible. La mayor parte de los sistemas actuales, con su énfasis en el uso interactivo del tiempo de respuesta, utilizan un algoritmo que se ocupa de las solicitudes inmediatas de usuarios interactivos. Aquí presentamos seis algoritmos de planificación de procesos de uso muy difundido.

2.10.1. PLANIFICACIÓN PRIMERO EN ENTRAR, PRIMERO EN SERVIRSE Primero en entrar, primero en ervirse (FCFS) es un algoritmo de planificación no apropiativa que maneja los trabajos de acuerdo con su tiempo de arribo: conforme entran son servicios. Es un algoritmo muy simple de implementar, porque utiliza un tipo de cola FIFO. Este algoritmo está bien

42

para la mayor parte de los sistemas por lotes, pero es inaceptable para los sistemas interactivos porque

los usuarios interactivos deben tener tiempos

cortos de respuesta. Con los FCFS, conforme un nuevo trabajo entra en el sistema su PCB queda vinculado con el final de la cola de LISTO y es eliminado de la parte delantera de la cola cuando el procesador queda disponible – esto es, después que ha procesado todos los trabajos que existían en la cola. En un sistema FCFS ciento por ciento, no existen colas de BLOQUEADO (cada trabajo se ejecuta hasta su terminación), aunque pueden haber sistemas en que el control (“contexto”) pasa a una espera natural (solicitud de E/S), luego de lo cual el trabajo se reanuda al terminar la operación de E/S. Los ejemplos que siguen suponen un entorno FCFS por completo (sin multiprogramación) El tiempo de retorno es impredecible con la

política

FCFS; considere las siguientes tres tareas:

TRABAJO CICLO DE CPU A

15

B

2

C

1

Para cada trabajo, el ciclo CPU contiene tanto el uso real del CPU como las solicitudes de E/S: el tiempo de ejecución total. La línea de tiempo (diagrama de Gantt) ilustrada en la figura 2.5. usa un algoritmo FCFS con una secuencia de llegada A, B, C.

Trabajo A 0

18

17

Trabajo

Trabajo

B

C

15

Figura 2.5: Diagrama de secuencia para los trabajos de A,B,C que utiliza el algoritmo FCFS.

43

Si los tres trabajos llegan prácticamente de manera simultánea, podemos calcular que el tiempo de retorno para el trabajo A es 15, para el trabajo B, 17 y para C, 18. Por lo que el tiempo de retorno promedio es:

(15 + 17 + 18) 3

= 16.67

Sin embargo, si los trabajos llegasen en un orden diferente, digamos C, B, A, los resultados serían según se muestra en la figura 2.6, en caso de usar el mismo algoritmo FCFS.

0

Trabajo

Trabajo

Trabajo

C

B

A

1

3

18

Figura 2.6: Diagrama de secuencia para los trabajos C,B,A con el algoritmo FCFS.

En este ejemplo el tiempo de retorno para el trabajo A es 18, B es 3, y para C es 1.el tiempo promedio total es:

(18 +3 +1) 3

= 7.3

Esto es una verdadera mejoría sobre la primera secuencia. Por desgracia, estos dos ejemplos ilustran la desventaja principal del uso del concepto FCFS: los tiempos promedio de retorno varían de una manera muy amplia y rara vez se minimizan. De hecho, cuando hay tres trabajos en la cola de LISTO, el sistema sólo

tiene una oportunidad en seis de ejecutar los trabajos en la

secuencia más ventajosa (C,B,A). Con cuatro trabajos las oportunidades pasan a una en 24 y así sucesivamente.

2.10.2. PLANIFICACIÓN SIGUE EL TRABAJO MÁS CORTO Sigue el trabajo más corto

(SJN). Es un algoritmo de planificación no

apropiada (también conocido como trabajo más corto primero o SJF) que maneja los trabajos con base en la duración de su ciclo de CPU. Es muy fácil de implementar en entornos por lotes, donde casa usuario da por adelantado el tiempo estimado de CPU requerido par ejecutar el trabajo al inicio del mismo. Sin embargo, no funciona en sistemas interactivos, porque los usuarios 44

no prevén el tiempo de CPU requerido para ejecutar sus trabajos. Por ejemplo, a continuación hay cuatro trabajos pro lotes, todos en la cola de LISTO, para la cual el ciclo de CPU, o tiempo de ejecución, se estima como sigue:

El algoritmo SJN

Trabajo

Ciclado de CPU

A

5

B

2

C

6

D

4

revisaría los cuatro trabajos y los programaría para

procesamiento en este orden B, D, A, C, la línea de tiempo aparecen en la figura 2.7.

0

Trabajo

Trabajo

Trabajo

Trabajo

B

D

A

C

2

6

11

17

Figura 2.7: Diagrama de tiempo de la secuencia de tareas B, D, A, C, con el algoritmo SJN.

El tiempo de retorno promedio es:

( 2 + 6 +11 +17) ) 4

= 9.0

Tomémonos un minuto para ver por qué este algoritmo puede demostrar ser óptimo y dar el tiempo de retorno promedio mínimo. Usaremos el ejemplo de arriba para deducir una formula de tipo general. En la figura 2.7. Podemos ver que el trabajo B termina en su tiempo dado (2), el trabajo D acaba en su tiempo dado, más el tiempo que tuvo que esperar para que se ejecutara B (4+2), el trabajo A finaliza en su tiempo dado más los tiempos de D mas B (5+4+2) y el trabajo C termina en su tiempo dado más

de los tres anteriores (6+5+4+2), por lo que al calcular el promedio 45

tenemos:

[ ( 2) + ( 4 + 2) + ( 5 + 4 + 2) + ( 6 + 5 + 4 + 2) ] = 9.0 4

Como puede

ver el tiempo para el primer trabajo aparece en la ecuación

cuatro veces – una para cada trabajo – en forma similar, el tiempo para el segundo trabajo aparece 3 veces (número de trabajos menos uno); el tiempo del tercero, dos (trabajos menos dos), y el tiempo del cuarto, una (cantidad de trabajos menos 3). Así pues la ecuación anterior se puede escribir de la forma:

( Dado que el tiempo

4 * 2 + 3 * 4 + 2 * 5 + 1* 6 ) =9.0 4

para el primer trabajo aparece cuatro

veces en la

ecuación tiene cuatro veces más efecto sobre el tiempo promedio que la duración del cuarto trabajo, que sólo figura una vez. Así pues, en el primer trabajo requiere el tiempo de calculo más breve, seguido en orden por los demás trabajos, ordenadas desde el lapso mas corto hasta el más largo, el resultado será el promedio más pequeño posible.

2.10.3. PLANIFICACIÓN POR PRIORIDAD La planificación por Prioridad, es un algoritmo no apropiativo y uno de los algoritmos de planificación más comunes en sistemas por lotes, aun cuando para algunos usuarios

pueden dar un tiempo de retorno

más lento. Este

algoritmo da tratamiento preferencial a los trabajos importantes. Permite procesar primero y en forma interrumpida los programas con la prioridad más elevada hasta

que sus

ciclos

CPU (tiempo

de ejecución

se hayan

completado o hasta que ocurra una espera natural. Si hay dos o más trabajos con prioridad igual en la cola de LISTOS, el procesador se asigna a la que llegó primero (primero en entrar, primero en servirse dentro de la prioridad).

2.10.4. PLANIFICACIÓN TIEMPO RESTANTE MÁS BREVE El tiempo restante más breve (SRT) es la versión apropiativa del algoritmo

46

SJN. El procesador se asigna al trabajo que esté por terminar – pero incluso este trabajo se puede hacer a un lado si un trabajo más reciente en la cola de LISTO tiene un tiempo de terminación más breve. Este algoritmo no es implementable en un sistema interactivo, porque requiere saber por adelantado cuánto tiempo del CPU representa la terminación de ada trabajo. A menudo se utiliza en entornos por lotes, cuando es deseable dar preferencia a trabajos breves, aun cuando el SRT supone más carga general que el SJN, porque el sistema operativo tiene que vigilar con frecuencia el tiempo del CPU de todos los trabajos en la cola de LISTO y debe efectuar “cambios de contexto” para los

trabajos

que se están intercambiando

(“conmutando”) en el momento de la apropiación (no necesariamente hacia el disco, aunque esto también puede ocurrir). Un ejemplo de la figura 2.8. muestra la forma en que funciona el algoritmo SRT con cuatro trabajos que han llegado en rápida sucesión (con una diferencia de un ciclo de CPU).

TRABAJO

TIEMPO DE LLEGADA

CICLO DE CPU

A

0

6

B

1

3

C

2

1

D

3

4

Aquí el trabajo A es desplazado por el trabajo B ya que éste tiene menos tiempo de CPU restante Aquí el trabajo B es desplazado por el trabajo C ya que éste tiene menos tiempo de CPU restante Ahora el trabajo B puede continuar ya que el trabajo C ha terminado Ahora el trabajo B puede continuar ya que el trabajo C ha terminado. El trabajo D es el siguiente en correr ya que necesita menos tiempo de CPU para terminar que el trabajo A.

Aquí el trabajo A se le permite terminar

Trabajo Trabajo A 0

Trabajo

B 1

Trabajo

C 2

Trabajo

B 3

Trabajo

D

A

5

9

47

14

Figura 2.8: Diagrama de tiempo de la secuencia de trabajos A,B,C,D con el algoritmo apropiante SRT.

En ete caso el tiempo de retorno es el tiempo de teminación de cada trabajo, menos su tiempo de llegada: Trabajo:

A

B

C

D

Tiempo de retorno

14

4

1

6

Por lo que el tiempo promedio de retorno es:

(14 + 4 + 1 + 6) = 6.25 4

¿Comó se compara lo anterior con el problema que utiliza la política SJN no apropiativa? La figura 2.9 utiliza la misma situación con SJN.

Trabajo 0

A

7

10

14

6

Trabajo Trabajo

Trabajo

C

D

B

Figura 2.9: Línea de tiempo para la misma secuencia de trabajos A,B,C,D, con el algoritmo SJN no apropiativa.

Este caso el tiempo de retorno es: Trabajo:

A

B

C

D

Tiempo de retorno

6

9

5

11

Por lo que el tiempo promedio de retorno es:

( 6 + 9 + 5 + 11) 4

= 7.75

Note en la figura 2.9. que inicialmente A es el único trabajo

en la cola de

LISTO, por lo que se ejecuta primero y continúa hasta que está temrinando porque SJN es un algoritmo no apropiatio. El sigueinte trabajo que se va a 48

ejecutar es C, porque cuando termina A (en el tiempo 6) han llagado los demás trabajos (B, C, y D) de estos tres C tiene un ciclo de CPU más breve, por lo que es el siguiente que se atiende, después B y por último D. Por lo tanto, con este ejemplo , SRT en 6.25 es mas rápido que SJN en 7.75 sin embargo, no incluimos el tiempo requerido por el algoritmo SRT para efectuar el cambio de contexto, el cual se requiere en todas los algoritmos preferentes. Cuando se opta por el trabajo A, procesamiento

toda su información de

se debe guardar en su PCB para uso

posterior, cuando

prosiga su ejecución y el contenido del PCB del trabajo B se cargue en los registros apropiados de manera que pueda volver a ejecutarse; esto es un cambio de contexto. Luego, cuando el trabajo A es reasiganado al procesador, ocurre otro cambio de contexto; cada vez la información del trabajo desplazado se almacena en su PCB y el contenido del PCB del trabajo A se carga en los registros apropiados.

2.10.5. PLANIFICACIÓN ROUND ROBIN Round Robin. Es un logaritmo de planificación de procesos apropiante muy difundido en sistemas interactivos, ya que es fácil de implementar y no se basa en las caracteristicas del trabajo

sino en una fracción predeterminada de

tiempo que se da a cada trabajo, para asegurar que los procesos activos compartan por igual el CPU y que ningún trabajo lo monopolice. Esta fracción de tiempo se conoce como quatum de tiempo y su tamaño es vital para el desempeño

del sistema. Por lo general

varían

de 100

milisegundos a 1 0 2 segundos. Los trabajos se colocan en la cola de LISTO utilizando el esquema de primero en entrar, primero en servirse, y el planificador de procesos selecciona el primero en la parte delantera de cola, pone en marcha el reloj en el quantum de tiempo y asignar el CPU a este trabajo. Si elprocesamiento no ha terminado cuando expira el tiempo, se retira el trabajo, se coloca al final de la cola de LISTO y su información se guarda en su PCB. En caso que le ciclo de CPU del trabajo sea más breve que el quantum de 49

trabajo, ocurrirá una de dos situaciones: 1)

si se trata del último ciclo CPU del trabajo y éste ha terminado, todos los recursos asignados al mismos se liberan y el trabajo completando se devuelve al usuario.

2)

su una solicitud de E/S ha interrumpido el ciclo del CPU, la información de la tarea se guarda en su PCB y queda vinculada al final de la cola apropiada de entradas y salidas. Luego una vez satisfecha la solicitud de E/S, se devuelve al final de la cola de LISTO para esperar asignación de CPU.

El ejemplo de la figura 2.10. ilustra un logaritmo de round robin con una fracción de tiempo de 4 milisegundos (se ignora las solicitudes de E/S):

0

TRABAJO

TIEMPO DE LLEGADA

CICLO DE CPU

A

0

8

B

1

4

C

2

9

D

3

5

Trabajo

Trabajo

Trabajo

Trabajo

Trabajo

Trabajo

Trabajo

Trabajo

A

B

C

D

A

C

D

C

8 12 16 20 24 25 4 93

Figura 2.10: Diagrama de tiempo para la secuencia de trabajos A,B,C,D con el algoritmo de round robin apropiativo.

El tiempo de retorno en el lapso en que se termina, menos al tiempo de llegada. Trabajo:

A

B

C

Tiempo de retorno 20

7

24

22

D

Por lo que el tiempo promedio de retorno es:

( 20 + 7 + 24 + 22) 4

50

= 18.25

Note que la figura 2.10,

el trabajo A se hizo

de lado una vez porque

necesitaba 8 milesegundos para completar su ciclo de CPU, en tanto que el trabajo B termino en un tiempo de quantum. El trabajo C se retiró dos veces porque necesitaba 9 milesegundos para completar su ciclo de CPU y el trabajo D se retiró una vez porque requeria 5 milesesundos. En su última ejecución o intercambio en la memoria, los tranajos D y C utilizaron el CPU durante un 1 milesegundo y terminaron antes que expirara su tiempo de quantum, con lo que libraron el CPU más aprisa. La eficiencia de round robin depende del tamaño de quantum en relación con el ciclo promedio del CPU. Si dicho quantum es demasiado grande – esto es mayor que la generalidad de los ciclos CPU - el algoritmo se reduce a un sistema FCFS. Si es demasiado pequeño, la cantidad de cambios de contexto disminuyen la velocidad de ejecución de los trabajos y la carga general se inrementa en forma dramática, como lo demuestran los tres ejemplos de la figura 2.11. El trabajo A tiene un ciclo de CPU de 8 milisegunods. La cantidad de cambios de contexto se incrementa conforme se reduce de tamaño el tiempo de quantum. En la figura 2.11. El primer caso: a)

Tiene un tiempo de quantum de 10 milesegundos y no hay cambio de contexto (sin carga general), el ciclo del CPU termina antes que expire el tiempo de quantum y el trabajo se ejecuta hasta terminarse. Para ese trabajo con este quantum no hay diferencia entre los algoritmos de round robin y de FCFS.

b)

Con un tiempo de quantum de 5 milesegundos, existe un cambio de contexto. El tranajo se retira una vez cuando el quantum expira, por lo que existe algo base en la cantidad de otros trabajos en el sistema.

c)

Con un tiempo de quantum de 5 milesegundo existe un cambios de contexto, el trabajo se retira una vez cuando el quantum expira por lo que existe algo de carga general por cambio de contexto, y habra un tiempo de retorno retrasado con base en la cantidad de otros trabajos en el sistema.

d)

Con un tiempo de quantum de 1 milisegundo hay siete cambios de

51

contexto, porque el trabajo se retira cada que expira el tiempo de quantum; la carga general se vuelve costosa, y por consiguiente el tiempo de retorno sufre. ¿Cuál es el tamaño más adecuado del tiempo de quantum? La respuesta debe ser predecible en este momento: depende del sistema. Si se trata de un entorno interactivo, se espera que el sistema responda

con rapidez a sus

usuarios, en especial cuando hacen solicitudes simples. Si se trata de un sistema por lotes, el tiempo de respuesta no es un factor (el tiempo de retorno lo es) y la carga general adquiere importancia.

Trabajo A 0

8 Tiempo de quantum = 10 Trabajo A

Trabajo A 5

0

8

Tiempo de quantum = 5

0

Trabajo

Trabajo

Trabajo

Trabajo

Trabajo

Trabajo

Trabajo

Trabajo

A

A

A

A

A

A

A

A

46 3 78 52 1

Tiempo de quantum = 1 Figura 2.11: Cambios de contexto de el trabajo A con tres quantum de tiempo. En a) el trabajo termina antes que expire el tiempo de quantum en b) y c) el quantum expira primero e interrupmpe el trabajo.

Existen dos reglas prácticas generales para seleccionar el quantum “correcto”: 1)

Deben ser lo bastante largo para permitir que 80 por ciento de los ciclos CPU se ejecutan hasta su terminación.

2)

Debe ser por lo menos cien veces mas largo que el tiempo requerido para llevar a cabo un cambio de contexto. Estas reglas se utulizan en algunos sistemas, pero no son inflexibles. 52

2.10.6. PLANIFICACIÓN DE COLAS DE MULTIPLES NIVELES Las colas de multiples niveles no son en realidad un algoritmo de planificación por separado, pero funcionan junto con varios de los esquemas ya analizados y se encuentran en sistemas con trabajos que se pueden agrupar de acuerdo con una carácteristica común. Ya hemos presentado por lo menos un tipo de cola de multiples niveles: la de un sistema basado en prioridades con diferentes colas por cada nivel de importancia. Otro tipo de sistema puede reunir los trabajos limitados por CPU en una cola y los trabajos restringidos por entradas y salidas en otra. Luego, el planificador de procesos seleccionaria de manera alterna trabajos de cada cola, para mantener el sistema equilibrado. Un tercer ejemplo común es el utilizado en un entorno hibrido, que acepta trabajos por lotes e interactivos. Los primeros se ponen en una cola llamada cola de “segundo plano” en tanto que los segundos se hubican en una cola de ”primer plano” y se tratan mas favorablemente que los correspondientes a las colas de segundo plano. Todos estos ejemplos tienen algo en común: la política de planificación se basa en algún esquema predeterminado, que da un tratamiento especial a los trabajos de cada cola. En cada cola, los trabajos se asignan de manera FCFS. A continuación se compara los diferentes algoritmos presentados en este capitulo. ver tabla 2.3. Algoritmo

Tipo de Política

Mejor para

Desventajas

Ventajas

FCFS

No aporpiativo

Lotes

Impredecible tiempo de retorno

Facil de implementar

SJN

No aporpiativo

Lotes

Aplazamiento indefinido de algunos trabajos

Minimiza el tiempo promedio de espera

Planificación por prioridad

No aporpiativo

Lotes

Aplazamiento indefinido de algunos trabajos

Asegura la rápida terminación de trabajos importantes

SRT

Aporpiativo

Lotes

Sobrecarga incurrida por conmutación de 53

Asegura la rápida terminación de trabajos cortos

contexto Round Robin

Colas de múltiples niveles

Aporpiativo

Apropiativo No apropiativo

Interactivo

Requiere seleccionar un buen tiempo de quantum.

Provee tiempos de respuesta razonables para usuarios interactivos; asi como asignación adecuada de CPU

Sobrecarga incurrida por revisión constante de colas

Esquema flexible; se opone al aplazamiento indefinido con el envejecimiento u otro movimiento en cola; da un tratamiento adecuado a los trabajos asignados al CPU por incremento de quantum sobre colas de baja prioridad u otro tipo de colas

Lotes/ interactivo

Tabla 2.3: Comparación de los algoritmos de planificación.

CAPITULO 3 ADMINISTRACIÓN DE PROCESOS CONCURRENTES

3.1. PROCESOS CONCURRENTES ASINCRÓNICOS Los procesos son concurrentes si existen al mismo tiempo. Los procesos concurrentes pueden funcionar con total independencia unos de otros, o pueden ser asincrónicos, lo cual significa que requieren una sincronización y cooperación ocasionales. El asincronismo es un tópico complejo; en este trabajo se exponen la organización y administración de sistemas que soportan procesos concurrentes asincrónicos. Se presentan muchos problemas importantes de asincronismo. Sus soluciones se presentan como programas concurrentes codificados utilizando el lenguaje Pascal concurrente desarrollado inicialmente por Wirth (Pascal-S), extendido por Ben Ari y modificado en la Universidad de Bradford (UK) por G.L. Davies (Pascal-FC).

54

3.2. PROCESAMIENTO EN PARALELO A medida que disminuyen tanto el tamaño como el precio del hardware de las computadoras se irá produciendo una tendencia hacia el multiprocesamiento y la masificación del paralelismo. Si ciertas operaciones pueden ser ejecutadas en paralelo de forma lógica, entonces las computadoras con múltiples procesadores las ejecutarán físicamente en paralelo, aunque en el nivel de paralelismo se den miles o, tal vez, millones de actividades concurrentes. El procesamiento en paralelo es interesante por varias razones. La gente parece más capaz de centrar su atención en una sola actividad a la vez que de pensar en paralelo. (Intente leer dos libros al mismo tiempo, leyendo una línea de un libro, una línea del otro, la segunda línea del primero, y así sucesivamente). Es difícil determinar cuáles actividades pueden ejecutarse o no en paralelo. Los programas en paralelo son mucho más difíciles de depurar que los programas secuenciales; después de haber arreglado supuestamente un error, puede resultar imposible reconstruir la secuencia de eventos que han ocacionado el error. Por ello, sería en cierto modo inapropiado asegurar que se ha corregido el error. Los procesos asincrónicos deben interactuar ocasionalmente entre sí, y esas interacciones pueden ser complejas. Trataremos varios ejemplos de interacción de procesos en este trabajo.

3.3. UNA ESTRUCTURA PARA INDICAR EL PARALELISMO: COBEGIN/COEND Son muchas las construcciones de lenguajes de programación para indicar paralelismo que han aparecido en la literatura. Estas implican pares de proposiciones como las siguientes: -

Una proposición indicando que la ejecución secuencial debe ser dividida entre varias secuencias de ejecución en paralelo (trayectoria de control).

55

-

Una proposición indicando que ciertas secuencias de ejecución en paralelo están a punto de producirse y se reanudará la ejecución secuencial.

Estas proposiciones ocurren en pares y suelen denominarse parbegin/parend (para comenzar y finalizar una ejecución en paralelo), o cobegin/coend (para comenzar o finalizar una ejecución concurrente). En este trabajo emplearemos cobegin/coend de acuerdo a la sintaxis del Pascal-FC. Su forma general es: cobegin proposición 1; proposición 2; : . proposición n; coend

Supóngase que un programa está ejecutando una sola secuencia de instrucciones cuando se encuentra con la construcción cobegin anterior. Esto determina que la trayectoria de control simple se divida en n trayectorias separadas de control, una por cada proposición de la construcción cobegin/coend. Estas pueden ser proposiciones simples, llamadas a procedimientos, bloques de proposiciones secuénciales delineados por begin/end, o combinaciones de éstos. Cada una de las trayectorias de control individuales acaba por alcanzar y terminar al coend. Cuando todas las trayectorias de control paralelas llegan al final, se reanuda una trayectoria de control simple y el sistema prosigue más allá del coend. Como ejemplo, considérese el siguiente cálculo de una raíz de la ecuación cuadrática: x := ( -b + (b**2 - 4*a*c) ** 0.5) / (2*a) Esta asignación puede ser evaluada en un procesador secuencial (poseedor de una instrucción de exponenciación) de la siguiente manera:

56

1

b**2

2

4*a

3

(4*a)*c

4

(b**2) - (4*a*c)

5

(b**2 - 4*a*c) ** 0.5

6

-b

7

(-b) + ( (b**2 - 4*a*c)**0.5 )

8

2*a

9

(-b+(b**2-4*a*c)**0.5)/(2*a)

Aquí se ejecutan de una en una cada una de las nueve operaciones en una secuencia determinada por las reglas de un sistema de precedencia de operadores. En un sistema que soporte procesamientos en paralelo, la expresión puede evaluarse de la manera siguiente: 1

cobegin t1:= -b; t2:= b ** 2; t3:= 4 * a; t4:= 2 * a; coend

2

t5:= t3 * c;

3

t5:= t2 - t5;

4

t5:= t5 ** 0.5;

5

t5:= t1 + t5;

6

x:= t5 / t4;

Aquí se evalúan en paralelo las cuatro operaciones contenidas dentro de la construcción cobegin/coend; las cinco operaciones restantes deben ser ejecutadas de forma secuencial. Al ejecutar los cálculos en paralelo se reduce en gran medida el tiempo real de ejecución.

57

3.4. EXCLUSIÓN MUTUA Considérese un sistema con varias terminales de tiempo compartido. Supóngase que los usuarios acaban cada línea, que teclean al sistema con un retorno de carro. Supóngase que se desea supervisar continuamente el número total de líneas que los usuarios han introducido al sistema desde el comienzo del día, y que cada terminal está supervisada por un proceso diferente. Cada vez que uno de estos procesos recibe una línea de la terminal de un usuario incrementa en 1 la variable global compartida NOLINEAS. Considérese lo que pasaría si dos procesos intentaran incrementar NOLINEAS simultáneamente. Supóngase que cada proceso tiene su propia copia del código: LOAD ADD

NOLINEAS 1

STORE NOLINEAS Suponga que NOLINEAS tiene un valor de 2345. Suponga ahora que el primer proceso ejecuta las instrucciones LOAD y ADD, dejando así el valor de 2346 en un acumulador. Entonces el proceso pierde el procesador (debido a la terminación de un quantum) en beneficio del segundo proceso. Este último ejecuta ahora las tres instrucciones, ajustando así NOLINEAS con el valor 2346. Pierde el procesador y lo obtiene de nuevo el primer proceso, el cual continúa con la ejecución de la instrucción STORE, colocando también el valor 2346 en NOLINEAS. Debido al acceso incontrolado a la variable compartida NOLINEAS el sistema ha perdido la pista de una de las líneas, el total correcto debería ser 2347. A continuación, se muestra el programa pro00 que simula este concepto así como diferentes corridas del mismo. El proceso uno mete 60 líneas mientras que el proceso dos mete 40. Por supuesto, la suma total de líneas debería ser 100, pero observe lo que pasa. - Pascal-FC for IBM PC compatibles - Compiler Version P5.2

58

G L Davies & A Burns, University of Bradford Compiler listing 1

0

2

0 program pro00;

3

0

4

0 var

5

0

6

0

7

0 (* El proceso uno contará 60 lineas *)

8

0 process uno;

9

0 var

10

0

11

0

12

0 begin

13

0

14

4

15

4

16

7

17

9 end; (* uno *)

18

11

19

11 (* El proceso dos contará 40 líneas *)

20

11 process dos;

21

11 var

22

11

23

11

24

11 begin

25

11

26

15

27

15

28

18

29

20 end; (* dos *)

30

22

nolineas: integer;

lin: integer;

for lin := 1 to 60 do begin nolineas := nolineas + 1 end

lin: integer;

for lin := 1 to 40 do begin nolineas := nolineas + 1 end

59

31

22 (* Programa principal *)

32

22 begin

33

22

nolineas := 0;

34

25

cobegin

35

26

uno;

36

30

dos

37

30

coend;

38

35

writeln('Total de líneas =',nolineas)

39

39 end.

- Interpreter Version P5.3 Program pro00 Total de líneas =

... execution begins ... 57

Program terminated normally Type r and RETURN to rerun Program pro00 Total de líneas =

... execution begins ... 74

Program terminated normally Type r and RETURN to rerun Program pro00 Total de líneas =

... execution begins ... 78

Program terminated normally Type r and RETURN to rerun Program pro00

... execution begins ...

60

Total de líneas =

76

Program terminated normally Type r and RETURN to rerun Program pro00

... execution begins ...

Total de líneas =

69

Program terminated normally

Este problema puede solucionarse dándole a cada proceso acceso exclusivo a NOLINEAS. Mientras un proceso incrementa la variable compartida, los demás procesos que deseen hacer lo mismo al mismo tiempo deben permanecer a la espera; cuando ese proceso termine de accesar la variable deseada, le será permitido proceder a uno de los procesos. De esta manera, cada proceso que esté accesando el dato compartido impide a todos los demás hacer lo mismo al mismo tiempo. Esto se denomina exclusión mutua.

3.5. SECCIONES CRÍTICAS La exclusión mutua necesita ser aplicada sólo cuando un proceso accesa a datos compartidos; cuando los procesos ejecutan operaciones que no estén en conflicto entre sí, debe permitirseles proceder de forma concurrente. Cuando un proceso está accesando da tos compartidos se dice que el proceso se encuentra en su sección crítica (o región crítica). Esta claro que para prevenir el tipo de problema experimentado en la sección anterior debe asegurarse que, cuando un proceso esté en su sección crítica, todos los demás procesos (o al menos aquellos que tengan acceso a los mismos datos compartidos) sean excluidos de sus propias secciones críticas. Mientras un proceso se encuentre en su sección crítica, los demás procesos pueden continuar su ejecución fuera de sus secciones críticas. Cuando un proceso abandona su sección crítica, entonces debe permitírsele proceder a 61

otros procesos que esperan entra r en su propia sección crítica (si hubiera un proceso en espera). La aplicación de la exclusión mutua es uno de los problemas clave de la programación concurrente. Se han diseñado muchas soluciones para esto: algunas de software y algunas de hardware, más de bajo nivel y otras de alto nivel; algunas que requieren de cooperación voluntaria entre los procesos, y algunas que demandan una adherencia rígida a protocolos estrictos. Estar dentro de una sección crítica es un estado muy especial asignado a un proceso. El proceso tiene acceso exclusivo a los datos compartidos, y todos los demás procesos que necesitan accesar a esos datos permanecen en espera. Por tanto, las secciones c ríticas deben ser ejecutadas lo más rápido posible, un programa no debe bloquearse dentro de su sección crítica, y las secciones críticas deben ser codificadas con todo cuidado (para evitar, por ejemplo, la posibilidad de incurrir en ciclos infinitos). Si un proceso dentro de una sección crítica termina, tanto de forma voluntaria como involuntaria, entonces, al realizar su limpieza de terminación, el sistema operativo debe liberar la exclusión mutua para que otros procesos puedan entrar en sus secciones críticas.

3.6. PRIMITIVAS DE EXCLUSIÓN MUTUA El programa concurrente que se muestra a continuación implementa correctamente el mecanismo contador de líneas de la sección anterior. Por simplicidad, trataremos tan sólo dos procesos concurrentes en los programas presentados en esta y en las próximas secciones. El ma nejo de n procesos concurrentes es mucho más complejo. Las construcciones entraexcluisionmutua y saledeexclusionmutua introducidas en el programa encapsulan el código en cada proceso que accesa la variable compartida NOLINEAS, es decir, estas construcciones demarcan las secciones crítica s. Estas operaciones se llaman, a veces, primitivas de exclusión mutua; o sea, que invocan las operaciones más fundamentales inherentes a la exclusión mutua.

62

program exclusionmutua; var nolineas: integer; process uno; var lin: integer; begin for lin := 1 to 60 do begin entraexclusionmutua; nolineas := nolineas + 1; saledeexclusionmutua end end; (* uno *) process dos; var lin: integer; begin for lin := 1 to 40 do begin entraexclusionmutua; nolineas := nolineas + 1; saledeexclusionmutua end end; (* dos *) begin nolineas := 0; cobegin uno; dos

63

coend; end.

En el caso de los dos procesos, estas primitivas operan como sigue: cuando el proceso uno se ejecuta, entra la exclusión mutua, si el proceso dos no está en su sección crítica, entonces el proceso uno entra a su sección crítica; accesa a la variable deseada y después se ejecuta, sale de exclusión mutua para indicar que ha abandonado su sección crítica. Si el proceso dos está en su sección crítica cuando el proceso uno se ejecuta entra a exclusión mutua, entonces el proceso uno entra en espera hasta que proceso dos se ejecute sale de la exclusión mutua. Proceso uno puede, entonces, proceder a entrar en su sección crítica. Si proceso uno y proceso dos se ejecutan entra la exclusión mutua simultáneamente,

entonces

le

será

permitido

proceder

a

alguno,

permaneciendo el otro en espera.

3.7. IMPLEMENTACIÓN DE LAS PRIMITIVAS DE EXCLUSION MUTUA Se busca una implementación que permite la exclusión mutua, entre el código de entrada a exclusión mutua y sale de exclusión mutua código de salida de exclusión mutua que satisfaga las cuatro restricciones siguientes: -

La solución se implementa sólo en software en una máquina que no tenga instrucciones de exclusión mutua especialmente diseñadas. Cada instrucción de lenguaje de máquina se ejecuta de forma indivisible; es decir, una vez iniciada una instrucción, ésta se termina sin interrupción. Si procesadores múltiples tratan de accesar el mismo dato, debemos suponer que

una

característica

del

hardware

llamada

interbloqueo

de

almacenamiento resuelve todos los conflictos. El interbloqueo de almacenamiento secuencializa las referencias en conflicto por medio de procesadores separados, esto es, se hace que las referencias sucedan una a la vez. Se da por supuesto que las referencias separadas son servidas en orden aleatorio. 64

-

No deberá hacerse ninguna suposición en relación con las velocidades relativas de procesos concurrentes asincrónicos.

-

Los procesos que se encuentren operando fuera de sus secciones críticas no pueden evitar que entren otros procesos en sus propias secciones críticas.

-

No deben postergarse indefinidamente la entrada de los procesos en sus secciones críticas.

Una implementación elegante de software de la exclusión mutua fue la presentada por primera vez por el matemático holandés Dekker. En la siguiente sección seguimos el desarrollo de Dijkstra del algoritmo de Dekker.

3.8. ALGORITMOS DE EXCLUSIÓN MUTUA 3.8.1. DESARROLLO INTUITIVO El programa pro01 muestra un primer intento de especificar el código para forzar la aplicación de la exclusión mutua, dentro del contexto de un programa concurrente con dos procesos. La construcción cobegin/coend hace que el proceso uno y el proceso dos operen como procesos concurrentes. Cada uno de estos procesos entra en un ciclo, entrando repetidamente en su sección crítica. En el programa pro01 entra a exclusión mutua, se implementa por un ciclo 'while' simple, que mantiene el ciclo hasta que pnumero iguala al número del proceso; sale de exclusión mutua a implementarse por una instrucción simple que ajusta pnumero al número del otro proceso. program pro01; (* primera version de las primitivas de exclusión mutua *) var pnumero: integer; nolineas: integer; process uno;

65

var lin: integer; begin for lin := 1 to 50 do begin while pnumero = 2 do null; nolineas := nolineas + 1; pnumero := 2 end end; (* uno *) process dos; var lin: integer; begin for lin := 1 to 50 do begin while pnumero = 1 do null; nolineas := nolineas + 1; pnumero := 1 end end; (* dos *) begin pnumero := 1; nolineas := 0; cobegin uno; dos coend;

66

writeln('Total de líneas =',nolineas) end.

El proceso uno ejecuta el while-do. Como pnumero es inicialmente 1, el proceso uno entra a su sección crítica. El proceso dos encuentra pnumero igual a 1 y permanece encerrado en su ciclo de while-do. Cuando el proceso dos obtiene el procesador, simplemente permanece en el ciclo en espera de que pnumero se ajuste a 2, así que proceso dos no entra en su sección crítica y la exclusión mutua queda garantizada. El proceso uno acaba por terminar la ejecución dentro de su sección crítica (ha de suponerse que no hay ciclos infinitos) y ajusta pnumero a 2, permitiendo así que el proceso dos entre en su sección crítica. La exclusión mutua está garantizada, pero el precio es alto. El proceso uno debe de entrar primero, así es que si el proceso dos está listo para entrar en su sección crítica, deberá tardar bastante. Después de que el proceso uno entre y salga de su sección crítica, entonces el proceso dos deberá seguir, aun cuando el proceso uno desee reentrar y el proceso dos no esté listo. Entonces, los procesos deberán entrar y salir de sus secciones críticas en estricta alternancia. Si un proceso requiere hacer esto muchas más veces que el otro, está restringido a operar a una velocidad más lenta de la que requiere. El sistema no debe interbloquearse completamente; por lo menos puede proceder un proceso, si ambos intentan entrar simultáneamente en sus secciones críticas. Si uno de los proceso termina, entonces el otro no podrá continuar. En la primera solución existe solamente una variable global simple, y esto forzaba la aparición del problema de sincronización bloqueada. Así es que, en la segunda versión (pro02), se usan dos variables: p1dentro, la cual es verdadera si el proceso uno está dentro de su sección crítica, y p2dentro, que es verdadera si proceso dos está dentro de su sección crítica. Ahora, mientras p2dentro sea verdadera, el proceso uno permanece encerrado en una espera. El proceso dos acaba abandonando su sección crítica y realiza su propio código de salida de exclusión mutua, ajustando p2dentro en falso. El proceso 67

uno ajusta entonces p1dentro en verdadero y entra en su sección crítica. Mientras p1dentro sea verdadera, proceso dos no podrá entrar en su sección crítica. La sutileza de la programación concurrente vuelve a salir a la superficie. Como quiera que el proceso uno y el proceso dos son concurrentes, ambos podrían intentar en forma simultánea sus secuencias de código de entrada de exclusión mutua. A continuación se muestra el listado del programa pro02. program pro02; (* segunda version de las primitivas de exclusión mutua *) var p1dentro, p2dentro: boolean; nolineas: integer; process uno; var lin: integer; begin for lin := 1 to 50 do begin while p2dentro do null; p1dentro := true; nolineas := nolineas + 1; p1dentro := false end end; (* uno *) process dos; var lin: integer; begin

68

for lin := 1 to 50 do begin while p1dentro do null; p2dentro := true; nolineas := nolineas + 1; p2dentro := false end end; (* dos *) begin p1dentro := false; p2dentro := false; nolineas := 0; cobegin uno; dos coend; writeln('Total de líneas = ',nolineas) end.

En principio, tanto p1dentro como p2dentro son falsas. El proceso uno podría probar p2dentro y encontrarla falsa; entonces, antes de que el proceso uno pueda ajustar p1dentro en verdadero, el proceso dos podría probar p1dentro y encontrarla falsa. En este punto, el proceso uno coloca p1dentro en verdadero y entra a su sección crítica, y el proceso dos ajusta p2dentro en verdadero y entra a su sección crítica. Ambos procesos se encuentran en sus secciones críticas al mismo tiempo, así es que la segunda versión ni siquiera garantiza la exclusión mutua. A continuación se muestra la corrida del programa pro02. - Interpreter Version P5.3 Program pro02 Total de líneas =

... execution begins ... 91

69

Program terminated normally Type r and RETURN to rerun r Program pro02

... execution begins ...

Total de líneas =

94

Program terminated normally Type r and RETURN to rerun ^Z End of data file - program terminating

En la segunda versión existe una dificultad, pues entre el tiempo en que un proceso determina (en la prueba del while) que puede seguir adelante y el tiempo en que el proceso ajusta una bandera para indicar que está en su sección crítica, hay tiempo suficiente para que el otro proceso pruebe su bandera y entre en su sección crítica. Por tanto, una vez que el proceso intenta la prueba del while, debe tener la seguridad de que el otro proceso no puede ir más allá de su propia prueba del while. La tercer versión intenta resolver esto haciendo que cada proceso ajuste su bandera antes de la ejecución del while. program pro03; (* tercer version de primitivas de exclusion mutua *) var p1quiere, p2quiere: boolean; nolineas: integer; process uno; var lin: integer; begin

70

for lin := 1 to 20 do begin p1quiere := true; while p2quiere do null; nolineas := nolineas + 1; p1quiere :=false end end; (* uno *) process dos; var lin: integer; begin for lin := 1 to 20 do begin p2quiere := true; while p1quiere do null; nolineas := nolineas + 1; p2quiere := false end end; (* dos *) begin nolineas := 0; cobegin uno; dos coend; writeln('Total de líneas =',nolineas) end.

Se ha solucionado un problema pero se ha creado otro. Si cada proceso ajusta 71

su bandera antes de proceder con la prueba del while, entonces, cada proceso se encontrará con la bandera del otro ajustada y entrarán para siempre en el ciclo while-do. Este es un ejemplo de un interbloqueo de dos procesos (la corrida de este programa causa que la máquina quede bloqueada). - Interpreter Version P5.3 Program pro03

... execution begins ...

(El programa bloquea la computadora, deberá dar reset) El problema de la tercera versión es que todos los procesos pueden encerrarse en su ciclo while-do respectivo. Es necesaria una manera de "romper" estos ciclos. La cuarta versión logra esto al forzar cada proceso de ciclo a ajustar su bandera en falso repetidamente en períodos breves; esto permitirá al otro proceso proceder más allá de su prueba del while, con su bandera todavía conectada. program pro04; (* cuarta version de primitivas de exclusion mutua*) var p1quiere, p2quiere: boolean; nolineas: integer; process uno; var lin: integer; begin for lin := 1 to 20 do begin p1quiere := true; while p2quiere do begin p1quiere := false; sleep(random(10)); p1quiere := true

72

end; nolineas := nolineas + 1; p1quiere := false end end; (* uno *) process dos; var lin: integer; begin for lin := 1 to 30 do begin p2quiere := true; while p1quiere do begin p2quiere := false; sleep(random(10)); p2quiere := true end; nolineas := nolineas + 1; p2quiere := false end end; (* dos *) begin nolineas := 0; cobegin uno; dos coend; writeln('Total de líneas =',nolineas) end. A continuación se muestra una corrida para este programa.

73

- Pascal-FC for IBM PC compatibles - Compiler Version P5.2 G L Davies & A Burns, University of Bradford Compiling pro04

...

Compilation complete - Interpreter Version P5.3 Program pro04 Total de líneas =

... execution begins ... 50

Program terminated normally Type r and RETURN to rerun ^Z End of data file - program terminating

La exclusión mutua queda garantizada y no puede ocurrir el interbloqueo, pero puede presentarse otro problema devastador en potencia, el de postergación indefinida. Veamos como. Debido a que no pueden hacerse suposiciones acerca de las velocidades relativas de los procesos concurrentes asincrónicos, habrá que considerar todas las secuencias de ejecución posibles. El proceso podría, por ejemplo, proceder en tándem. Cada proceso puede seguir la siguiente secuencia: ajustar su bandera en verdadero, hacer la prueba del while, entrar en el cuerpo del ciclo while, ajustar su bandera en falso, retardarse, ajustar su bandera en verdadero y, luego, repetir la secuencia, comenzando con la prueba del while. En tanto hacen esto, las condiciones de prueba permanecerán verdaderas. Desde luego que la probabilidad de que tal operación ocurra es muy baja, pero puede ocurrir. Por lo tanto, la cuarta versión es inaceptable. Si un sistema que utiliza este sistema de exclusión mutua estuviera controlando un vuelo espacial, un marcapasos cardíaco o un sistema de control de tráfico aéreo, la posibilidad de que ocurra una

74

postergación indefinida con el consecuente fallo del sistema no es admisible.

3.9. ALGORITMO DE DEKKER En sólo unas cuantas líneas de código, el algoritmo de Dekker (Programa dekker) maneja de manera elegante la exclusión mutua de dos procesos sin necesidad de ninguna instrucción especial de hardware. El algoritmo de Dekker resuelve la posibilidad de la postergación indefinida experimentada en la cuarta versión. Veamos como. El proceso uno indica su deseo de entrar en su sección crítica, al conectar su bandera (ajustarla en verdadero). Entonces proced e con la prueba del while donde verifica si el proceso dos también quiere entrar. Si la bandera del proceso dos está desconectada (ajustada en falso), entonces el proceso uno salta el cuerpo del ciclo while y entra en su sección crítica. Supóngase, sin embargo, que cuando el proceso uno realice la prueba del while, descubre que la bandera del proceso dos está conectada. Esto obliga al proceso uno a entrar al cuerpo del ciclo while. Aquí busca la variable favorecido, que se utiliza para resolver los conflictos que surgen cuando ambos procesos desean entrar al mismo tiempo en sus secciones críticas. Si el proceso uno es el favorecido, salta el cuerpo del if y ejecuta repetidamente la prueba del while, esperando a que el proceso dos desconecte su bandera. (Luego

veremos

que

el

proceso

dos

debe

acabar

haciendo

eso.)

Si el proceso uno determina que el proceso favorecido es el proceso dos, entonces el proceso uno es forzado a entrar en el cuerpo del if, donde desconecta su propia bandera, entra al ciclo del próximo while y permanece allí en tanto el proceso dos siga siendo el proceso favorecido. Al desconectar su propia bandera, el proceso uno permite al proceso dos entrar en su sección crítica. El proceso dos acabará abandonando su sección crítica y ejecutará su código de salida de exclusión mutua. Estas instrucciones ajustan el proceso favorecido de vuelta al proceso uno y desconectan la bandera del proceso dos. El proceso uno puede entrar ahora al while interno y conectar su propia bandera. El

75

proceso uno realiza ahora el while externo. Si la bandera del proceso dos (que acaba de desconectarse) sigue aún desconectada, entonces el proceso uno entra en su sección crítica. Sin embargo, si el pro ceso dos intentó reentrar rápidamente en su sección crítica, entonces la bandera del proceso dos estará conectada y el proceso uno será obligado de nuevo a entrar en el cuerpo del while externo. En esta ocasión, sin embargo, el proceso uno está "sentado en el asiento del conductor", debido a que ahora es el proceso favorecido (recuerde que cuando el proceso dos abandonó su sección crítica, ajustó favorecido al primero). Así es que el proceso un o salta el cuerpo del if y ejecuta de forma repetida la prueba del while externo, hasta que el proceso dos "humildemente", desconecte su bandera, permitiendo entrar en su sección crítica. A continuación se muestra el listado del programa que utiliza el algoritmo de Dekker para la exclusión mutua. program dekker; (* solución de Dekker al problema de la exclusion mutua *) var favorecido: integer; p1quiere, p2quiere: boolean; nolineas: integer; process uno; var lin: integer; begin for lin := 1 to 20 do begin p1quiere := true; while p2quiere do begin 76

p1quiere := false; while favorecido = 2 do null; p1quiere := true end; nolineas := nolineas + 1; favorecido := 2; p1quiere := false end end; (* uno *) process dos; var lin: integer; begin for lin := 1 to 20 do begin p2quiere := true; while p1quiere do begin p2quiere := false; while favorecido = 1 do null; p2quiere := true end; nolineas := nolineas + 1; favorecido := 1; p2quiere := false end end; (* dos *) begin nolineas := 0; favorecido := 1; cobegin

77

uno; dos coend; writeln('Total de líneas = ',nolineas) end.

A continuación se tiene la corrida del programa anterior. Compiling dekker

...

Compilation complete - Interpreter Version P5.3 Program dekker

... execution begins ...

Total de líneas = 40 Program terminated normally Considere la siguiente posibilidad interesante. Al salir el proceso uno del ciclo interno de espera, es posible que pierda el procesador, y que el proceso dos complete el ciclo e intente entrar de nuevo en su sección crítica. El proceso dos conectará entonces su bandera primero y entrará en su sección crítica. Cuando el proceso uno obtenga de nuevo el procesador, conectará su bandera. Como será el turno del proceso uno, si el proceso dos intenta entrar, desconectará su propia bandera y será obligado a entrar al ciclo interno de espera, y el proceso uno podrá entrar en su sección crítica. De esta manera, este truco no dará como resultado una postergación indefinida.

3.10. ALGORITMO DE PETERSON Otro interesante algoritmo para manejar la exclusión mutua entre dos procesos, es el algoritmo de Peterson (programa ptrson), del cual presentamos el siguiente listado y corrida. program peterson; (* Algoritmo de Peterson para la exclusión mutua de dos 78

procesos

*) var nolineas, turno : integer; band1, band2: boolean; process uno; var lin: integer; begin for lin := 1 to 20 do begin band1:= true; turno:= 2;

(* anuncia el intento de entrar *)

(* le da prioridad al otro proceso *)

while band2 and (turno = 2) do null; nolineas := nolineas + 1; band1:= false end end; process dos; var lin: integer; begin for lin := 1 to 30 do begin band2:= true; turno:= 1;

(* anuncia el intento de entrar *)

(* le da prioridad al otro proceso *)

while band1 and (turno = 1) do null; nolineas := nolineas + 1; band2:= false

79

end end; begin nolineas := 0; turno := 1; band1 := false; band2 := false; cobegin uno; dos coend; writeln('Total de Líneas: ',nolineas) end. C:\PASFC>pfc ptrson.pfc - Pascal-FC for IBM PC compatibles - Compiler Version P5.2 G L Davies & A Burns, University of Bradford Compiling peterson ... Compilation complete - Interpreter Version P5.3 Program peterson ... execution begins ... Total de Líneas:

50

Program terminated normally Type r and RETURN to rerun ^Z End of data file - program terminating

80

Los procesos comparten las variables band1, band2 y turno. Inicialmente band1 = band2 = false, y el valor de turno no tiene relevancia (pero debe ser 1 o 2). En el listado de los procesos, se puede apreciar que para entrar en la sección crítica, el proceso uno primero asigna true a band1 y luego afirma que es el turno del proceso dos para entrar si así lo desea (turno=2). Si ambos procesos tratan de entrar a la vez, se asignará turno como 1 y 2 aproximadamente al mismo tiempo. Sólo una de estas asignaciones durará; la otra ocurrirá, pero será reemplazada de inmediato. El valor eventual de turno decide a cual de los dos procesos se le permitirá entrar primero en su sección crítica. Ahora demostraremos que esta solución es correcta. Necesitamos demostrar: (1) que se conserva la exclusión mutua, (2) que se respeta el requisito de progreso

y

(3)

que

se

cumple

el

requisito

de

espera

limitada.

Para demostrar la propiedad (1) observamos que cada proceso entra en su sección crítica únicamente cuando band2 = false o turno = 1 para el proceso uno (band1 = false o turno = 2 para el proceso dos). Observe también que, si ambos procesos pueden estar en ejecución en sus secciones críticas al mismo tiempo, entonces band1 = band2 = true. Estas dos observaciones representan que uno y dos no pueden haber cumplido con éxito la condición del while aproximadamente al mismo tiempo, ya que el valor de turno puede ser 1 o 2, pero no los dos. Por consiguiente, uno de los procesos, digamos uno, debió ejecutar con éxito la condición while, mientras que dos tuvo que ejecutar por lo menos un enunciado adicional ("turno=2"). S in embargo, como en ese momento band1=true y turno=2, y esta condición persistirá mientras uno se encuentre en su sección crítica, se concluye que se conserva la exclusión mutua. Para comprobar las propiedades (2) y (3) observamos que se puede evitar que el proceso dos entre en su sección crítica únicamente cuando se queda en el ciclo while con la condición band1=true y turno = 1; éste es el único ciclo. Si uno no está listo para entrar en la sección crítica, entonces band1= false, y dos puede entrar en su sección crítica. Si uno ha establecido band1 = true y

81

también está ejecutando su enunciado while, entonces turno = 1 o turno = 2. Si turno = 2, entonces uno entrará en la sección crítica. Empero, una vez que uno sale de su sección crítica, volverá a establecer band1=false, permitiendo que dos entre en su sección crítica. Si uno vue lve a establecer band1 como true, también deberá establecer turno=2. Por lo tanto, como dos no cambia el valor de la variable turno mientras ejecuta el ciclo while, dos entrará en la sección crítica (progreso) des pués de, como máximo, una entrada de uno (espera limitada).

3.11. EXCLUSION MUTUA DE n-PROCESOS 3.11.1. ALGORITMO DE DIJKSTRA Dijkstra fue el primero en presentar una solución de software para la implementación

de

primitivas

de

exclusión

mutua

de

n-procesos.

A continuación se muestra un programa que utiliza el algoritmo de Dijkstra para la exclusión mutua. program dijkstra; (* algoritmo de dijkstra para la exclusión mutua *) const nprocs=3; var b, c: array[0..nprocs] of boolean; turno: integer; i, nolineas : integer; procedure lock(pnum: integer); var ok: boolean; j: integer;

82

begin b[pnum] := false; repeat while turno pnum do begin c[pnum] := true; if b[turno] then turno := pnum end; (* while *) c[pnum] := false; ok := true; for j := 1 to nprocs do if j pnum then ok := ok and c[j] until ok end; (* lock *) procedure unlock(pnum: integer); begin c[pnum] := true; b[pnum] := true; turno := 0 end; (* unlock *) process type terminal(n: integer); var loop: integer; begin for loop := 1 to 20 do begin lock(n); nolineas := nolineas + 1; unlock(n)

83

end end; (* terminal *) var p: array[0..nprocs] of terminal; begin nolineas := 0; for turno := 0 to nprocs do begin b[turno] := true; c[turno] := true end; turno := 0; cobegin for i := 0 to nprocs do p[i](i) coend; writeln('Total de Líneas: ',nolineas) end. A continuación se muestran los resultados de la corrida del programa (obsérvese que son 4 procesos que meten 20 líneas cada uno): - Pascal-FC for IBM PC compatibles - Compiler Version P5.2 G L Davies & A Burns, University of Bradford Compiling dijkstra ... Compilation complete - Interpreter Version P5.3 Program dijkstra ... execution begins ... Total de Líneas:

80 84

Program terminated normally Type r and RETURN to rerun ^Z End of data file - program terminating

3.11.2. ALGORITMO DE LAMPORT Lamport desarrolló una solución que es particularmente aplicable a los sistemas de procesamiento distribuido. El algoritmo usa un sistema de "toma de boleto", como el usado en las panaderías muy concurridas, y ha sido apodado el algoritmo de la panade ría de Lamport. Nos centraremos únicamente en los aspectos del algoritmo relacionados con un entorno centralizado. Al entrar en la tienda cada cliente recibe un número, y se atiende primero al que tenga el número menor. Por desgracia, el algoritmo de la panadería no puede garantizar que dos procesos (clientes) no reciban el mismo número. En el caso de un empate, prim ero se atiende el proceso con el nombre menor. Es decir, si Pi y Pj reciben el mismo número y si i < j, entonces primero se servirá a Pi. Como los nombres de procesos son únicos y ordenados, nuestro algoritmo es completamente determinista. Las estructuras de datos comunes son: var boleto: array[1..nprocs] of integer; eleccion: array[1..nprocs] of boolean; Al principio, a estas estructuras se les asigna un valor inicial 0 y false, respectivamente. Por conveniencia, definimos la siguiente notación: n (a,b) < (c,d) si (a < c) o si (a = c) y b < d

Condición que determina si el proceso b con el boleto a es favorecido o no para

85

entrar a la sección crítica con respecto al proceso d con el boleto c. (en el programa bakery esta condición se implementa por medio de la función favorecido). n max(a1 , ... , an)

es (esto

un

número,

se

k,

implementa

tal en

el

que

k

programa

>

ai

mediante

para la

i=1,

...,n

función

max)

A continuación se muestra un listado del programa para resolver el mismo problema de exclusión mutua (conteo de líneas) mediante el algoritmo de la panadería de Lamport. program bakery; (* Exclusión mutua con el algoritmo de la panadería de Lamport *) const nprocs = 5; var boleto: array[1..nprocs] of integer; eleccion: array[1..nprocs] of boolean; lp: integer; nolineas: integer; process type Entrada(esteproc: integer); var otroproc, lp: integer; function max: integer; var i, largo: integer; begin 86

largo := 0; for i := 1 to nprocs do if boleto[i] > largo then largo := boleto[i]; max := largo + 1 end; (* max *) function favorecido(i, j: integer): boolean; begin if (boleto[i] = 0) or (boleto[i] > boleto[j]) then favorecido := false else if boleto[i] < boleto[j] then favorecido := true else favorecido := (i < j) end; (* favorecido *) begin for lp := 1 to 20 do begin eleccion[esteproc] := true; boleto[esteproc] := max; eleccion[esteproc] := false; for otroproc := 1 to nprocs do begin while eleccion[otroproc] do null; while favorecido(otroproc, esteproc) do null; end; nolineas := nolineas + 1; boleto[esteproc] := 0 end

87

end; (* Entrada *) var turnos: array[1..nprocs] of Entrada; begin nolineas := 0; for lp := 1 to nprocs do begin boleto[lp] := 0; eleccion[lp] := false; end; cobegin for lp := 1 to nprocs do turnos[lp](lp) coend; writeln('Total de Líneas: ',nolineas:4) end.

A continuación se muestran los resultados de la corrida del programa: - Pascal-FC for IBM PC compatibles - Compiler Version P5.2 G L Davies & A Burns, University of Bradford Compiling bakery

...

Compilation complete - Interpreter Version P5.3 Program bakery

... execution begins ...

Total de Líneas: 100 Program terminated normally

88

Type r and RETURN to rerun ^Z End of data file - program terminating

3.12. SEMÁFOROS Dijkstra extractó las nociones clave de la exclusión mutua en su concepto de semáforo. Un semáforo es una variable protegida cuyo valor puede ser accesado y alterado tan sólo por las operaciones wait, signal y una operación de ini cialización del semáforo initial. Los semáforos binarios sólo pueden tomar los valores 0 y 1. Los semáforos contadores pueden tomar valores enteros no negativos. La operación wait en el semáforo S, escrito wait(S), opera de la siguiente manera: if S > 0 then S:=S - 1 else (espera en S)

La operación signal en el semáforo S, escrito signal(S), opera de la siguiente manera: if (uno o más procesos están en espera en S) then (deja proseguir a uno de estos procesos) else S:=S+1

Supondremos que hay una disciplina de colas del primero en entrar - primero en salir para los procesos que esperan a completar un wait(S). La ejecución de las instrucciones wait y signal son indivisibles. La exclusión mutua en el semáforo, S, es aplicada en wait(S) y signal(S). Si varios procesos intentan ejecutar wait(S) al mismo tiempo, sólo uno podrá proseguir; los otros permanecerán en espera. Los semáforos y las operaciones de semáforos pueden implementarse en software o hardware. En general, se implementan en el núcleo del sistema operativo, donde se controlan los cambios de estado de

89

un proceso. El programa sem01 que se lista a continuación, muestra como pueden utilizarse los semáforos para aplicar la exclusión mutua. program sem01; (* solución por semáforos al problema de la exclusión mutua *) var nolineas: integer; mutex: semaphore; (* declaración del semáforo *) process uno; var lin: integer; begin for lin := 1 to 20 do begin wait(mutex);

(* Espera por el semáforo *)

nolineas := nolineas + 1; (* sección crítica *) signal(mutex)

(* libera el semáforo *)

end end; (* uno *) process dos; var lin: integer; begin for lin := 1 to 20 do begin wait(mutex); nolineas := nolineas + 1; signal(mutex) end 90

end; (* dos *) begin nolineas := 0; initial(mutex,1); (* se inicializa el semáforo *) cobegin uno; dos coend; writeln('Total de Líneas = ',nolineas) end.

A continuación se muestran los resultados de la corrida del programa. - Pascal-FC for IBM PC compatibles - Compiler Version P5.2 G L Davies & A Burns, University of Bradford Compiling sem01

...

Compilation complete - Interpreter Version P5.3 Program sem01 Total de Líneas =

... execution begins ... 40

Program terminated normally Type r and RETURN to rerun ^Z End of data file - program terminating

3.12.1. SINCRONIZACIÓN DE PROCESOS CON SEMÁFOROS

91

Cuando un proceso emite una petición de entrada/salida, se bloquea a sí mismo para esperar a que termine esta operación. Algunos procesos deben despertar al proceso bloqueado. Tal interacción es un ejemplo de un protocolo de bloqueo/despertar. En forma más general, supóngase que un proceso desee ser informado de la ocurrencia de un evento. Supóngase que otro proceso es capaz de detectar que ese acontecimiento ya ha ocurrido. El siguiente programa (sem02) muestra cómo pueden utilizarse la s operaciones de semáforos para implementar un mecanismo simple de sincronización de bloqueo/despertar de dos procesos. program sem02; (* Proceso de sincronización de bloqueo/despertar con semáforos *) var mutex: semaphore; (* declaración del semáforo *) process uno; begin writeln('Cosas preliminares de Uno'); wait(mutex);

(* Espera por el semáforo *)

writeln('Otras cosas del Uno'); end; (* uno *) process dos; begin writeln('Cosas preliminares del Dos'); signal(mutex); writeln('Otras cosas del Dos.'); end; (* dos *) begin

92

initial(mutex,0); cobegin uno; dos coend; end. Compiling sem01

...

Compilation complete - Interpreter Version P5.3 Program sem01

... execution begins ...

Cosas preliminares de Uno Cosas preliminares del Dos Otras cosas del Dos. Otras cosas del Uno Program terminated normally Type r and RETURN to rerun ^Z End of data file - program terminating

El proceso uno ejecuta algunas cosas preliminares y después ejecuta wait(mutex). El semáforo ha sido inicializado a cero, de modo que el proceso debe esperar. El proceso dos ejecuta signal(mutex) para señalar que el evento ha ocurrido. Esto permite proceder al proceso uno. Obsérvese que este mecanismo trabaja incluso cuando proceso dos detecta y señala el evento antes de que el proceso uno ejecute wait(mutex); el semáforo habrá sido incrementado de 0 a 1, así es que wait(mutex), decrementa el semáforo de 1 a 0, y proceso uno proseguirá sin tener que esperar a que ocurra el evento.

3.12.2. BLOQUEOS MUTUOS Y BLOQUEOS INDEFINIDOS

93

La implantación de un semáforo con una cola de espera puede dar como resultado una situación donde dos o más procesos esperen indefinidamente un suceso que sólo puede ocasionar uno de los procesos en espera. El suceso en cuestión consiste en la ejecución de una operación signal. Cuando se llega a este estado, se dice que los procesos están en bloqueo mutuo. Para ilustrarlo, consideremos un sistema que consta de dos procesos, Uno y Dos, cada uno con acceso a dos semáforos, S y Q, con valor inicial 1: Uno

Dos

wait(S)

wait(Q)

wait(Q)

wait(S)

.

.

.

.

.

.

signal(S)

signal(Q)

signal(Q)

signal(S)

Suponga que Uno ejecuta wait(S) y luego Dos ejecuta wait(Q). Cuando Uno ejecuta wait(Q), debe esperar a que Dos ejecute signal(Q). De manera parecida, cuando Dos ejecuta wait(S), debe esperar a que Uno ejecute signal( S). Como estas operaciones de signal no pueden ejecutarse, Uno y Dos están en bloqueo mutuo. Decimos que un conjunto de procesos está en un estado de bloqueo mutuo cuando cada uno de los procesos del conjunto está esperando un suceso que únicamente

puede

ser

provocado

por

otro

proceso

del

conjunto.

Otro problema relacionado con el bloqueo mutuo es el bloqueo indefinido o inanición, en que los procesos pueden esperar indefinidamente dentro del semáforo. El bloqueo indefinido se puede presentar si añadimos y eliminamos procesos de la lista aso ciada con un semáforo en orden LIFO. A continuación se muestra el listado de un programa sencillo que ilustra el concepto de bloqueo mutuo. La segunda columna de números en el listado del compilador, corresponde a la dirección de memoria de esa instrucción en lenguaje de máquina. Este tipo de listado se presenta para determinar, el punto

94

exacto, de cada proceso en el programa fuente, donde ocurre el bloqueo. - Pascal-FC for IBM PC compatibles - Compiler Version P5.2 G L Davies & A Burns, University of Bradford Compiler listing Line PC 1

0 program sem03;

2

0 (*

3

0 Proceso de sincronización de bloqueo/despertar

4

0 con semáforos

5

0 *)

6

0

7

0 var

8

0 S, Q: semaphore;(* declaración de los semáforos *)

9

0

10

0 process Uno;

11

0 begin

12

0

writeln('Entramos al Uno');

13

3

wait(S);

14

5

writeln('El Uno toma S y espera por Q');

15

8

wait(Q);

16

10

17

10

18

13

19

13

signal(S);

20

15

signal(Q);

21

17 end; (* uno *)

22

18

23

18

24

18 process Dos;

25

18 begin

(* Espera por el semáforo *)

writeln('Uno entra a la sección crítica ');

95

26

18

writeln('Entramos al Dos');

27

21

wait(Q);

28

23

writeln('El Dos toma Q y espera por S');

29

26

wait(S);

30

28

31

28

32

31

33

31

signal(Q);

34

33

signal(S);

35

35 end; (* dos *)

36

36

37

36

38

36 begin

39

36 initial(S,1);

40

40 initial(Q,1);

41

44 cobegin

42

45

Uno;

43

49

Dos

44

49 coend;

45

54 end.

(* Espera por el semáforo *)

writeln('Dos entra a la sección crítica ');

Compilation complete

A continuación se muestran diferentes corridas del programa hasta obtener un bloqueo mutuo. - Interpreter Version P5.3 Program sem03

... execution begins ...

Entramos al Uno Entramos al Dos El Uno toma S y espera por Q Uno entra a la sección crítica El Dos toma Q y espera por S 96

Dos entra a la sección crítica Program terminated normally Type r and RETURN to rerun r Entramos al UnoEntramos al Dos El Dos toma Q y espera por S Dos entra a la sección crítica El Uno toma S y espera por Q Uno entra a la sección crítica Program terminated normally Type r and RETURN to rerun r Entramos al Uno El Uno toma S y espera por Q Entramos al Dos El Dos toma Q y espera por S Abnormal halt in process dos with pc = 28 Reason: deadlock

See pmdfile for post-mortem report

En estas condiciones se obtiene el bloqueo mutuo antes mencionado. El intérprete ofrece un diagnóstico de esta condición de la siguiente forma: Pascal-FC post-mortem report on sem03 - Interpreter Version P5.3 Abnormal halt in process dos with pc = 28 97

Reason: deadlock ---------Main program Status: awaiting process termination ---------Process uno Status: active pc = 10 Process suspended on: q (semaphore) ---------Process dos Status: active pc = 28 Process suspended on: s (semaphore) ========== Global variables q

=

0

s

=

0

3.13. LA RELACIÓN PRODUCTOR - CONSUMIDOR En un programa secuencial, cuando un procedimiento llama a otro y le trasmite datos, los procedimientos son parte de un proceso simple y no operan de forma concurrente. Pero cuando un proceso transmite datos a otro, los problemas son 98

mucho más complejo s. Tal transmisión es un ejemplo de comunicación interprocesos. Considérese la siguiente relación productor consumidor. Suponga que un proceso, un productor, está generando información que utiliza un segundo proceso, un consumidor. Suponga que se comunican por medio de la variable compartida, buffer< /I>. El productor agrega datos en el arreglo buffer, el consumidor lee los datos de buffer y los imprime. Es posible que los procesos productor y consumidor trabajen bien en tándem, o que sus velocidades de ejecución sean muy parecidas. Si cada vez que el productor deposita un dato en buffer, el consumidor lo lee y lo imprime de inmediato, entonces la salida impresa representará fielmente la corriente de números generada por el productor. Pero supóngase que las velocidades de los procesos son dispares. Si el consumidor está operando con más rapidez que el productor, el consumidor puede leer e imprimir datos antes de que el productor los deposite. Si el productor está operando más rápido que el consumidor, el productor podría sobre escribir los datos previos antes de que el consumidor tenga la oportunidad de leerlos e imprimirlos; un productor muy veloz podría hacer esto muchas veces, con lo cual muchos resultados se perderían. Como es evidente, el comportamiento que deseamos aquí es que el productor y el consumidor cooperen de forma tal que los datos escritos en buffer no se dupliquen ni se pierdan. La aplicación de tal comportamiento se conoce como sincronización de procesos. El siguiente programa (pcsem) muestra un programa concurrente que utiliza las operaciones de semáforos para implementar una relación productor - consumidor. Los procesos utilizan la variable compartida buffer. El productor va poniendo en el arreglo los números del 65 al 90 (código ASCII de las letras A-Z) mientras que el consumidor los va tomando e imprimiendo. Aquí hemos utilizado tres semáforos: mutex se utiliza para aplicar el acceso de exclusión mutua a la variable compart ida buffer; listos controla la sincronización de los procesos para determinar si existen datos en el buffer; espacios controla en la sincronización la existencia de espacio en el buffer. 99

program pcsem; (* Solución al problema del Productor - Consumidor mediante el uso de semáforos *) const buffmax = 5; var buffer: array[0..buffmax] of integer; sigentra, sigsale: integer; (* apuntadores a buffer para el manejo de la cola*) espacios, listos: semaphore; mutex: semaphore; procedure pon(ch: integer); begin (* el buffer es una cola circular *) buffer[sigentra] := ch; sigentra := (sigentra + 1) mod (buffmax + 1) end; (* pon *)

procedure toma(var ch: integer); begin ch := buffer[sigsale]; sigsale := (sigsale + 1) mod (buffmax + 1) end; (* toma *) process productor; var local: integer; begin

100

for local := 65 to 90 do begin wait(espacios);

(* Espera que haya espacio *)

wait(mutex); pon(local);

(* Entrada a la sección crítica *) (* Sección crítica *)

write(chr(local)); signal(mutex); signal(listos)

(* Sale de sección crítica *) (* Avisa que ya hay un dato listo *)

end end; (* productor *) process consumidor; var local: integer; begin repeat begin wait(listos); (* Espera que haya datos listos *) wait(mutex);

(* Entra en la sección crítica *)

toma(local);

(* Sección crítica *)

signal(mutex); (* sale de la sección crítica *) signal(espacios); (* Avisa que hay un espacio *) write(chr(local+32)); end until local = 90; writeln end; (* consumidor *) begin initial(espacios,buffmax + 1); initial(listos,0); initial(mutex,1); sigentra := 0;

101

sigsale := 0; cobegin productor; consumidor coend end.

A continuación se muestran diferentes corridas de este programa. Las letras mayúsculas corresponden al dato y el momento en que el productor pone en el buffer el dato. Las letras minúsculas indican el dato y el momento en que el consumidor tomó el dato. - Pascal-FC for IBM PC compatibles - Compiler Version P5.2 G L Davies & A Burns, University of Bradford Compiling pcsem

...

Compilation complete - Interpreter Version P5.3 Program pcsem

... execution begins ...

AaBCbDcEFdGeHfIgJhKiLjMkNlmOnPoQpRqSrTsUtVuWvXwYxZyz AaBbCcDEdFeGfHgIhJiKjLkMlNmOnPoQpRSqTrUsVtWuXYvwZxyz ABaCbDcEdFeGfHgIhJiKjLkMlNmOnPoQpRqSrTsUtVuWvXYwZxyz AaBCbDcEdFeGfHgIhJKLijMNkOlPmQnRoSpTqUrVWsXtYuZvwxyz

3.14. SEMÁFOROS CONTADORES Los semáforos contadores son particularmente útiles cuando un recurso va a ser asignado desde una bolsa de recursos idénticos. El semáforo se inicializa para el número de recursos de la bolsa. Cada operación wait decrementa el semáforo en 1, indicando que ha extraído otro recurso de la bolsa y está siendo usado por un proceso. Cada operación signal incrementa el semáforo en 1, indicando que un proceso ha devuelto un recurso a la bolsa, y puede ser 102

asignado a otro proceso. Si se intenta una operación wait cuando el semáforo ha sido decrementado hasta cero, el proceso debe esperar hasta que se devuelva algún recurso a la bolsa por medio de una operación signal.

103

CAPÍTULO 4 ADMINISTRACIÓN DE LA MEMORIA

En un sistema monoprogramado, la memoria principal se divide en dos partes: para el sistema operativo (monitor residente, núcleo) y otra para el programa que se ejecuta en ese instante. En un sistema multiprogramado, la parte de “usuario” de la memoria debe subdividirse aún más para hacer sitio a varios procesos. La tarea de subdivisión la lleva a cabo dinámicamente el sistema operativo y se conoce como administración de memoria. En un sistema multiprogramado resulta vital una gestión efectiva de la memoria, si solo hay unos pocos procesos en memoria, entonces la mayor parte del tiempo estarán esperando a la E/S y el procesador estará desocupado. Por ello, hace falta repartir eficientemente la memoria para meter tantos procesos como sea posible.

4.1. 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 sistemas operativos. 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 que generalmente es soportado en discos. Los hechos demuestran que generalmente los programas crecen en requerimientos de memoria tan rápido como las memorias:

104

-

“Ley de Parkinson parafraseada”: Los programas se desarrollan para ocupar toda la memoria disponible para ellos. La parte del sistema operativo 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.

4.2. REQUISITOS PARA LA ADMINISTRACIÓN DE LA MEMORIA Al realizar un estudio de los diversos mecanismos y políticas relacionadas con la adminsitración de memoria, vale la pena trener en mente los requisitos que se intentan satisfacer: Se propone cinco requisitos: -

Reubicación.

-

Protección.

-

Compartición.

-

Organización lógica.

-

Organización física.

4.2.1. REUBICACIÓN En un sistema multiprogramado, la memoria disponible se encuentra normalmente compartida por varios procesos. En general, el programador no puede conocer por adelantado qué otros programas residirán en memoria en el momento de la ejecución del programa. Además, se busca poder cargar y descargar los proceso activos en la memoria principal para maximizar el uso del procesador, manteniendo una gran reserva de procesos listos para

105

ejecutar. Una vez que el programa haya sido descargado al disco, se limitará a declarar que, cuando vuelva a ser cargado, debe situarse en la misma región de memoria principal que antes. De este modo, se sabe antes de tiempo donde debe dsituarse un programa y hay que pérmitir que el programa debe moverse en la memoria principal como resultado de un intercambio. Esta situacion plantea algunos asuntos técnicos relativos al direccionamiento, tal como se muestra en la figura 4.1., que representa la imagen de un proceso. Por simplicidad, se sopundra que la imagen del proceso ocupa una región contigua a la memoria principal. Sin duda el S.O. tiene que conocer la ubicación de la información del control del proceso y la pila de ejecución, así como el punto de partida para comenzar la ejecución del programa para dicho proceso. Puesto que el S.O. administra la memoria y es responsable en traer el proceso en memoria principal, estas direcciones deben ser fásiles de conocer. Además, el procesador debe ocuparse de las referencias a memoria dentro del programa. Las instrucciones de bifurcación deben tener la dirección que haga referencia a la instrucción que se vaya a ejecutar a continucaión. Las instrucciones que hagan referencia a datos deben contener la dirección del byte o de la palabra de datos referenciados. De algún modo, el hardware del procesador y el software del sistema operativo deben ser capaces de traducir las referencias a memorias encontrados en el código del programa a las direcciones físicas reales que reflejen la posición actual del programa en memoria principal. Información de Control del Proceso

Punto de

Bloque De Control De Proceso

entrada al Instrucciones de salto

Programa

Referencia a Datos Código

Cima Actual de la Pila

Pila datos

106

Figura 4.1: Requisitos de direccionamiento para un proceso.

3.2.2. PROTECCIÓN Cada proceso debe protegerse contra interferencias no deaseadas de otros procesos, tanto accidentales como intencionales. Así pues, el código de un proceso no puede hacer referencia a posiciones de memoria de otros procesos, con fines de lectura o escritura, sin permiso. Hasta cierto punto, satisfacer las exigencias de reubicación aumenta la dificultad de satisfacción de las exigencias de protección. Puesto que se desconoce la ubicación de un programa en memoria principal, es imposible comprobar las direcciones absolutas durante la compilación para asegurar la protección. Es más, la mayoría de los lenguajes de programación permiten el cálculo dinámico de direcciones durante la ejecución, generando, por ejemplo, un índice de un vector o un puntero a una estructura de datos. Por tanto, todas las referencias de memoria generadas por un proceso deben comprobarse durante la ejecución para asegurar que sólo hacen referencia al espacio de memoria destinado a dicho proceso. Afortunadamente, como se verá, los

mecanismos

que respaldan la

reubicación también forman parte básica del cumplimiento de las necesidades de protección. La imagen del proceso de la figura 4.1, ilustra las necesidades de proteción. Normalmente, un proceso de usuario no puede acceder a ninguna parte del sistema operativo, tanto programa como datos. De nuevo, el programa de un proceso no puede en general bifurcar hacia una instrucción de otro proceso. Además, sin un acuerdo

especial, el programa de un

proceso no puede

acceder el área de datos de otro proceso. El procesador debe ser capaz de abandonar tales instrumentos en el momento de la ejecución. Nótese que, en los términos del ejemplo, las exigencias de protección de memoria pueden ser satisfechas por el procesador (hardware) en vez de que por el sistema operativo (software).

107

4.2.3. COMPARTICIÓN Cualquier mecanismo de protección que se implemente debe tener la flexibilidad de permitir el acceso a varios procesos a la misma zona de la memoria principal. Por ejemplo, si una serie de procesos están ejecutando en un mismo programa, resultaría beneficioso permitir a cada proceso que acceda a la misma copia del programa, en lugar de tener cada uno su propia copia aparte. Los procesos que cooperan en una tarea pueden necesitar acceso copartido a la misma estructura de datos. El sistema de administración de memoria debe, por tanto, permitir acceso controlado a las áreas compartidas de la memoria, sin comprometer la protección básica. De nuevo, se verá que los mecanismos empleados para respaldar la reubicación forman parte básica de las capacidades de comparticición.

4.2.4. ORGANIZACIÓN LÓGICA De forma casi invariable, la memoria principal de un sistema informático se organiza como un espacio de direcciones lineal o unidimensionales que consta de una secuencia de bytes o palabras. La memoria secundaria, a nivel físico, se organiza de forma similar. Si bien esta organización refleja fielmente el hardware de la máquina, no se corresponde con la forma en la que los programas están construidos habitualmente. La mayoría de los programados se organizan en módulos, algunos de los cuales no son modificables (sólo lectura, sólo ejecución) y otros contienen datos que se pueden modificar. Si el sistema operativo, hardware y los datos se organizaran en forma de módulos de algún tipo, se conseguirá una serie de ventajas, tales como: 1.

Los módulos pueden escribirse y compilarse independientemente, mientras que el sistema resuelve durante la ejecución todas las referencias de un módulo a otro.

2.

Con un escaso coste adicional, pueden otorgarse varios grados de protección (sólo lectura, sólo ejecución) a los distintos módulos.

108

3.

Es imposible introducir mecanismo por medio de los cuales los procesos puedan compartir módulos. La ventaja de ofrecer compartición a nivel de módulo es que esto se corresponde con la visión del problema que tiene

el usuario y,

por tanto, es fácil, para el usuario especificar

la

comparación que desea.

4.2.5. ORGANIZACIÓN FÍSICA En la memoria del computador se organiza, al menos, dos niveles: memoria principal y memoria secundaria. La memoria principal ofrece un acceso rápido con un costo relativamente alto; además, la memoria principal es volátil; esto es, no proporciona almacenamiento permanente. La memoria secundaria es más lenta y barata que la memoria principal y normalmente no es volátil. De este modo, una memoria secundaria de gran capacidad puede permitir un almacenamiento a largo plazo de programas y datos, al tiempo que una memoria principal pequeña mantiene los programas y datos de uso actual. En este esquema a dos niveles, la organización del flujo de información entre la memoria principal y la secundaria tiene un gran interés en el sistema, la responsabilidad de este flujo podría asignase al programador, pero esto es impracticable e indeseable, debido a dos razones: 1.

La memoria principal disponible para un programa y sus datos pueden ser insuficiente, en este caso, el programador debe emplear una práctica que se conoce como superposición (overlaying), en el cual el programa y los datos se organicen de tal forma que puede haber varios módulos asignados a la misma región de memoria, con un programa principal responsable del intercambio de los módulos según se necesiten. Incluso con la ayuda de herramientas de compilación, la programación superpuesta malgasta el tiempo del programador.

2.

En un entorno multiprogramado, el programador no conoce durante la codificación cuanto espacio habrá disponible o donde estará este espacio.

Resulta claro entonces que la tarea de mover información entre los dos niveles 109

de memoria debe ser responsabilidad del sistema. Esta tarea es la esencia de la administración de memoria.

4.3. CARGA DE PROGRAMAS EN MEMORIA PRINCIPAL La tarea central de cualquier sistema de administración de memoria es traer los programas a memoria principal para su ejecución en el procesador. En casi todos los sistemas multiprogramados modernos,

esta tarea supone un

esquema sofisticado conocido como memoria virtual. La memoria virtual está, a su vez, basado en el uso de una de dos técnicas básicas: segmentación y/o paginación. Antes de ver estas técnicas de memoria virtual, se debe preparar el terreno considerando técnicas más simples que no requieren el uso de memoria virtual. Una de estas técnicas, la partición, se ha venido usando con distintas variantes en algunos sistemas operativos ahora obsoletos. Las otras dos técnicas la paginación simple y la segmentación simple, no se usan en solitario. No obstante, el estudio de la memoria virtual resultará más sencillo si se consideran en primer lugar estas dos técnicas,

sin tener en cuenta la

memoria virtual. La tabla 4.1. adelanta los mecanismos cubiertos en la administración de memoria.

4.3.1. PARTICIÓN FIJA En la mayoría de los esquemas de gestión de memoria, se puede suponer que el sistema operativo ocupa una parte fija de memoria principal y que el resto de la memoria esta disponible para ser usado por varios procesos. El esquema más sencillo de administración de memoria disponible es dividirla en regiones con límites fijos.

4.3.1.1. TAMAÑOS DE PARTICIÓN En la figura 4.2 se ofrecen ejemplos de dos alternativas de partición fija. Una posibilidad es emplear particiones de igual tamaño. En este caso, cualquier proceso cuyo tamaño sea menor o igual que el tamaño de la partición puede

110

cargarse en cualquier partición libre. Si todas las particiones están ocupadas y no hay procesos residentes en estado Listo o Ejecutando, el sistema operativo puede sacar un proceso de algunas de las particiones y cargar otro proceso de forma que haya trabajo para el procesador. Las particiones fijas de igual tamaño plantean dos dificultades: -

Un programa puede ser demasiado grande para caber en la partición. En este caso, el programador debe diseñar el programa mediante superposiciones, para que solo una parte del programa este en memoria principal en cada instante. Cuando se necesita un módulo que no esta presente, el programa de usuario debe cargar dicho módulo en la partición del programa, superponiéndose a los programas y datos que se encuentren en ella.

-

El uso de memoria principal es extremadamente ineficiente. Cualquier programa, sin importar lo pequeño que sea, ocupará una participación completa. En el ejemplo. Puede haber

un programa que

ocupa menos de 128 kb de memoria y, aún así, ocuparía una participación de 512 Kb cada vez que se cargase. Este fenómeno, en el que se malgasta el espacio interno de una participación cuando el bloque de datos cargados sea más pequeños que la participación, se denomina fragmentación interna; en la siguiente tabla 4.1 se podrá observar las diversas técnicas de administración de memoria. TÉCNICA Partición fija

Partición dinámica

Paginación

DESCRIPCIÓN

VENTAJAS

DESVENTAJAS

La memoria principal de divide en un conjunto de particiones fijas durante la generación del sistema. Un proceso se puede cargar en una partición de mayor o igual tamaño.

Sencilla de Empleo ineficiente de implementar; poca la memoria debido a la sobre carga del sistema fragmentación interna; operativo. el número de procesos activos es fijo.

Las particiones se crean dinámicamente, de forma que cada proceso se carga en una partición de exactamente el mismo tamaño que el proceso.

No hay fragmentación interna; uso más eficiente de la memoria principal.

Uso ineficiente del procesador debido a la necesidad de compactación para contrarrestar la fragmentación externa.

La memoria principal se divide No tiene fragmentación Hay una pequeña en un conjunto de marcos de externa cantidad de igual tamaño. Cada proceso se fragmentación interna.

111

simple

divide en una seria de páginas del mismo tamaño que los marcos. Un proceso se carga situando todas sus páginas en marcos libre pero no necesariamente contiguos.

Cada proceso se divide en una No tiene fragmentación Necesita compactación seria de segmentos. Un proceso interna Segmentación de carga situando todos sus simple segmentos en particiones dinámicas que no tiene porque ser contiguas. Memoria virtual paginada

Memoria virtual segmentado

Como la paginación simple, excepto que no hace falta cargar todas las páginas de un proceso. Las páginas no residentes que se necesiten se traerán mas tarde de manera automática.

No hay fragmentación Sobre carga por gestión externa; alto grado de compleja de memoria. multiprogramación; gran espacio virtual para el proceso.

Como la segmentación simple excepto que no es necesario cargar todos lo segmentos de un proceso. Los segmentos no residentes que se necesiten se traerán mas tarde de forma automática

No hay fragmentación Sobrecarga por gestión interna alto grado de compleja de memoria. multiprogramación; gran espacio virtual para el proceso; soporte de protección y compartición.

Tabla 4.1: Técnicas de administración de memoria.

Sistema operativo 512 K

Sistema operativo 512 K

128 K

512 K

256 K 512 K

512K

512 K

576K

512 K

768 K

512 K 1M 512 K

512 K

112

(a) Participaciones del mismo tamaño

(b) Participaciones de distintos tamaños.

Figura 4.2: Ejemplo de participación estática de una memoria de 4Mb.

Pueden reducirse, aunque no solventarse, ambos problemas, por medio del empleo de particiones de tamaños distintos, como se muestra en la figura 4.2b. En este ejemplo, los programas de hasta 1Mb pueden alojarse sin superposición. Las participaciones menores de 512Kb permiten alojar programas más pequeños con un desperdicio menor.

4.3.1.2. ALGORITMO DE UBICACIÓN Con particiones del mismo tamaño, la ubicación de un proceso en memoria es trivial. Mientras haya alguna participación libre, puede cargarse un proceso en esa participación. Puesto que todas las participaciones son de igual tamaño, no importa la participación que se use. Si todas las particiones están ocupadas con procesos que no están listos para ejecutar, uno de esos procesos debe sacarse y hacer sitio a un nuevo

proceso. Cuál

debe expulsarse es una

decisión de planificación. Con participaciones de distintos tamaños, hay

dos maneras posibles de

asignar los procesos a las participaciones. La forma más simple es asignar cada proceso a la participación más pequeña en la que quepa. En este caso, hace

falta una cola de planificación para cada partición, que albergue los

proceso expulsados cuyo destinado es dicha participación (figura 4.3.a). La ventaja de este enfoque es que los procesos están siempre asignados de forma que se minimiza la memoria desperdiciada dentro de cada participación. Sin embargo, aunque esta técnica parece óptima desde el punto de vista de una participación individual, no lo es

desde el punto de vista del sistema

global. Considérese el caso de la figura 4.2.b, por ejemplo, donde no hay procesos con un tamaño comprendido entre 768 K y 1M en un determinado instante. En este caso, la partición de 768K permanecerá sin usar, incluso aunque algún proceso más pequeño pudiera haber sido asignado a la misma, así pues, una solución mejor sería emplear una única cola para todos los 113

procesos (figura 4.3.b) cuando se va a cargar un proceso en memoria principal, se selecciona la partición más pequeña disponible que pueda albergar al proceso. Si todas las participaciones están ocupadas, se debe tomar una decisión de

intercambio. Puede darse preferencia al intercambio de la

participación más pequeña que pueda contener al proceso entrante. También es posible considerar otros factores, tales como prioridades y preferencia para descargar procesos bloqueados antes que proceso listo.

Sistema

Sistema

operativo

operativ o

Procesos Nuevos Procesos Nuevos

(a) Una cola de proceso por participación.

(b) Cola única proceso.

Figura 4.3: Asignación de memoria con participación fija.

El uso de particiones de distinto tamaño proporciona cierto grado de flexibilidad a las particiones fijas. Además, ambos tipos de esquema de participación fija son relativamente simples y exigen un software del sistema operativo y una sobrecarga de procesamiento mínimo. Sin problemas siguientes:

114

embargo, se

plantean los

-

El número de particiones especificadas en el momento de la generación del sistema limita el número de procesos activos (no suspendidos) el sistema.

-

Puesto que los tamaños de partición se programan en el momento de la generación del sistema, los trabajos pequeños no hacen un uso eficiente del espacio de las particiones. En un entorno en el que los requisitos básicos de almacenamiento de todos los procesos se conocen de antemano, pueden ser una técnica razonable, pero en la mayoría de los casos, ineficiente.

4.3.1.3. PARTICIÓN DINÁMICA Para superar algunas de las dificultades de la partición estática, se desarrolló una solución denominada partición dinámica. Otra vez, este enfoque ha sido superado de largo por administraciones de memorias más sofisticadas. Con la partición dinámica, las particiones son variables en número y longitud. Cuando se trae un proceso a memoria principal, se le asigna exactamente tanta memoria como necesita y no más. En la figura 4.4. se muestra un ejemplo que usa 1Mb de memoria principal. Al principio, la memoria principal está vacía, exceptuando el sistema operativo (figura 4.4.a). se cargan los tres primeros procesos, empezando en donde acabo el sistema operativo y ocupando sólo un espacio suficiente para cada proceso (figura 4.4.b, c y d). Esto deja un “hueco” al final de la memoria demasiado pequeño para un cuarto proceso. En algún momento, ninguna de los procesos en memoria está listo. Así pues, el sistema operativo saca al proceso 2 (figura 4. 4.c), que deja sitio suficiente para cargar un nuevo proceso, el proceso 4 (figura 4.4.f) puesto que el proceso 4 es más pequeño que el proceso 2 se crea otro hueco pequeño. Más tarde, se alcanza un punto en el que ninguno de los procesos que están en memoria principal están listos y el proceso 2, que está en estado listo, pero suspendido, está disponible. Puesto que no hay suficiente sitio en memoria para el proceso 2, el sistema operativo expulsa al proceso 1 (figura 4.4.g) y carga de nuevo el proceso 2 (figura 4.4.h).

115

Como se muestra en el ejemplo, este método comienza bien, pero, finalmente, desemboca en una situación en la que hay un gran número de huecos pequeños en memoria. Conforme pasa el tiempo, la memoria comienza a estar más

fragmentada y su rendimiento decae. Este fenómeno se denomina

fragmentación externa y se refiere al hecho de que la memoria externa a todas las particiones se fragmenta cada vez más a diferencia de la fragmentación interna que se comentó anteriormente. Una técnica para superar la fragmentación externa es la compactación: de vez en cuando, el sistema operativo desplaza

los procesos para que estén

contiguos de forma que toda la memoria libre quede junta en un bloque. Por ejemplo, en la figura 4.4h, la compactación produce un bloque de memoria libre de 256K. Este hueco puede ser suficiente para cargar un proceso adicional. La dificultad de la compactación está en que es un procedimiento que consume tiempo, por lo que desperdicia tiempo del procesador. La compactación necesita de la capacidad de reubicación dinámica. Es decir, se deber poder mover un programa en una región a otra de la memoria principal sin invalidar las referencias a memoria del programa. Sistema Operativo

128K

Sistema Operativo

Sistema Operativo Proceso 1

320K

Sistema Operativo

320K

Proceso 1

320K

Proceso 1

224K

224K

896K Espacio de proceso

576K Proceso 2

352K

Proceso 2

288K 64K

(a)

(b)

(c)

(d)

Sistema Operativo

Sistema Operativo

Sistema Operativo

Proceso 3 Sistema Operativo

Proceso 1

320K

Proceso 1

Proceso 4 224K

288K 64K (e)

320K

128K

320K

Proceso 4

128K

96K

96K

288K

288K

Proceso 2

224K

Proceso 4

96K 128K 96K

Proceso 3

288K

116 Proceso 3 (f)

64K

Proceso 3 (g)

64K

64K (h)

Figura 4.4: Efectos de la participación dinámica.

4.3.1.4. ALGORITMO DE UBICACIÓN Puesto que la compactación de memoria consume tiempo, atañe al diseñador del sistema operativo decidir adecuadamente cómo asignar un proceso a memoria (como llenar los huecos). Cuando llega el momento de cargar o traer un proceso a memoria principal y, si hay libre más de un bloque de memoria de tamaño suficiente, el sistema operativo debe decidir cuál asignar. Los tres algoritmos de ubicación que se pueden considerar son el mejor ajuste (best- fit), el del primer ajuste (first – fit) y el del siguiente ajuste (next – fit). Todos ellos se limitan a elegir entre los bloques de memoria libres que son mayores o iguales que el proceso a traer. El mejor ajuste elige el bloque de tamaño más parecido al solicitando.

8K

8K Primer Ajuste

12K

12K

6K 22K

Mejor ajuste 2K

18K Ultimo bloque Asignado (14K)

8K 8K 6K 6K

Bloque asignado Bloque Libre

14K

14K Siguiente Ajuste

36K

117 a

20K

b

Figura 4.5: Ejemplo de una configuración de memoria antes y después de asignar un bloque de 16 Kb.

El primer ajuste comienza recorriendo la memoria desde el principio y escoge el primer bloque disponible que sea suficientemente grande. El siguiente ajuste recorre la memoria desde el lugar de la última ubicación y elige el siguiente bloque disponible que sea suficientemente grande. La figura 4.5.a muestra un ejemplo de configuración de la memoria después de cierto número de ubicaciones y operaciones de descarga de procesos. El último bloque usando fue de 22Kb, de donde se creó una participación de 14Kb. La figura 4.5.b, muestra la diferencia entre los algoritmos de ubicación del mejor primer y siguiente ajuste para una solicitud de 16kb. El mejor ajuste busca en la lista completa de bloques disponibles y emplea el hueco de 18KB, dejando un fragmento de 2Kb. El primer ajuste genera un fragmento de 6Kb y el siguiente ajuste origina un fragmento de 20Kb. Cuál de estos métodos el mejor, dependerá de la secuencia exacta de intercambio de procesos que se den y del tamaño de estos procesos. El algoritmo del primer

ajuste no sólo es el

más sencillo, sino que

normalmente es también el mejor y más rápido. El algoritmo del siguiente ajuste tiende a generar resultados algo peores que el del primer ajuste. El algoritmo del siguiente ajuste llevará frecuentemente a la asignación de bloques libres del final de la memoria. El resultado es que el bloque de memoria libre más grande,

que suele

aparecer al final del espacio de memoria, se divide rápidamente en fragmentos pequeños. Así pues, con el siguiente ajuste hará falta una compactación más frecuente. Por otro lado, el algoritmo del primer ajuste puede poblar el extremo inicial de pequeñas particiones libres que es necesario recorrer en las pasadas siguientes de algoritmo. El algoritmo del mejor ajuste, a pesar de su nombre, proporciona en general los peores resultados. Puesto que este algoritmo 118

busca

el hueco más pequeño posible. Aunque cada solicitud de memoria

desperdicia siempre la menor cantidad, el resultado es que la memoria principal se llena rápidamente de bloques demasiado pequeños como para satisfacer las solicitudes de asignación de memoria.

Así pues, se debe compactar más

frecuentemente que con los otros algoritmos. 4.3.1.5. ALGORITMOS DE REEMPLAZO En un sistema

multiprogramado con particiones dinámicas, habrá algún

momento en el que todos los procesos de memoria principal estén en estado bloqueado y la memoria sea insuficiente. Incluso tras la compactación, para un proceso adicional. Para evitar desperdiciar el tiempo del procesador esperando a que un proceso activo se desbloquee, el sistema operativo expulsará uno de los procesos de memoria principal para hacer sitio a un proceso nuevo o un proceso listo, pero suspendido. Por lo tanto, el sistema operativo debe elegir que proceso reemplazar.

4.3.1.6. REUBICACIÓN Antes de considerar las formas de solucionar los defectos de las técnicas de partición, se debe aclarar un punto oscuro, que tiene relación con la ubicación de los procesos en memoria. Cuando se emplea el esquema de particiones fijas de la figura 4.3.a, se puede esperar que un proceso sea asignado siempre a la misma partición. Es decir, la partición que se selecciona cuando se carga un nuevo proceso será la misma que se emplee siempre para devolver este proceso a memoria tras haber sido sacado. En el caso de particiones de igual tamaño y en el caso de una cola única de procesos para particiones de distinto tamaño,

un proceso puede ocupar

diferentes particiones a lo largo de su vida. Cuando al principio se crea la imagen de un proceso, se cargará en alguna partición de memoria principal. Posteriormente, el proceso puede ser descargado; cuando, más tarde, vuelve a ser cargado, podrá asignársele una partición distinta de la anterior. Esto mismo se cumple con particiones dinámicas. Obsérvese en la figura 4.4.c, y 4.4.h, que el proceso 2 ocupa dos regiones de memoria distintas en las dos

119

ocasiones en las que se le trae a memoria. Es más, cuando se usa compactaciones, los procesos son desplazados durante su estancia en memoria principal. Considérese ahora un proceso en memoria que incluya instrucciones y datos. Las instrucciones contendrán

referencias a memoria de los dos tipos

siguientes: -

Direcciones de elementos de datos, empleadas en instrucciones de carga, almacenamiento y en algunas instrucciones aritméticas y lógicas.

-

Direcciones de instrucciones, empleadas para bifurcaciones e instrucciones de llamada.

Ahora se demostrará que estas instrucciones no son fijas, si no que cambian cada vez que se Intercambia o desplaza un proceso. Para resolver este problema, se realiza una distinción entre varios tipos de direcciones. Una dirección lógica es una referencia a una posición de memoria independiente de la asignación actual de datos de memoria; se debe hacer una traducción a dirección física antes de poder realizar un acceso a memoria. Una dirección relativa es un caso particular de dirección lógica, en el cual la dirección se expresa como una posición relativa en algún punto conocido, habitualmente el comienzo del programa. Una dirección

física o dirección absoluta, es una

posición real en memorial principal.

4.4. MEMORIA VIRTUAL En un sistema de jerarquía de memoria, los programas y datos se almacenan primero en la memoria auxiliar. Después, se traen a la memoria principal partes de un programa o de datos, conforme los necesita la CPU.

La memoria

virtual es un concepto que se usa en algunos sistemas de computadoras grandes que permite al usuario construir programas

como si estuviera

disponible un gran espacio de memoria, igual a la totalidad de la memoria auxiliar, cada dirección a la que hace referencia la CPU recorre un mapeo de dirección de la supuesta dirección virtual a una dirección física en la memoria principal. Se usa la memoria virtual para dar a los programadores la ilusión de 120

que tienen a su disposición una memoria muy grande, aunque la computadora tenga en realidad una memoria relativamente pequeña. Un sistema de memoria virtual proporciona un mecanismo para trasladar direcciones generadas por programas a localidades correctas en la memoria principal. Esto se hace en una forma dinámica, mientras la CPU ejecuta programas. Una circuitería maneja en forma automática la traducción o el mapeo mediante una tabla de mapeo.

4.4.1. ESPACIO DE DIRECCIONAMIENTO Y ESPACIO DE MEMORIA A una dirección que usa un programador se la llamará dirección virtual y al conjunto de tales direcciones, espacio virtual. A una dirección en la memoria principal se la llama localidad o dirección física. El conjunto

de tales

localidades se llama espacio de memoria. Por lo tanto, el espacio de direccionamiento es el conjunto de direcciones generado por los programas, conforme hacen referencia a instrucciones y datos; el espacio de memoria consiste en las localidades reales de la memoria principal que se pueden acceder directamente para procesamiento. En la mayoría de las computadoras los espacios de direccionamiento y de memoria son idénticos. Se permite que el especio de direccionamiento sea mayor que el espacio de la memoria en computadoras de memoria virtual. Como ejemplo, consideremos

una

computadora con una capacidad de

memoria principal de 32 K palabras (K =1024) se necesitan quince bits para especificar una dirección física en la memoria porque 32 K = 2 15, supongamos que la computadora tiene memoria auxiliar disponible para almacenar 2 20 = 1024 K palabras. Por lo tanto, la memoria auxiliar tiene capacidad para almacenar información equivalente a la capacidad de 32 memorias principales. Al representar el espacio de direccionamiento por N y el espacio de memoria por M, tenemos para este ejemplo N = 1024K y M = 32K. En un sistema de computadora de multiprogramación, se transfieren los programas y datos a, y de la memoria auxiliar y de la memoria principal, con base en las demandas que impone la CPU. Supongamos que el programa 1 se

121

ejecuta en ese momento en la CPU. El programa 1 y una parte de sus datos asociados se mueven de la memoria auxiliar a la memoria principal como se muestra en la figura 4.6. Las partes de los programas y datos no necesitan estar en localidades contiguas en la memoria, porque la información se mueve hacia adentro y hacia fuera y pueden quedar espacios vacíos en partes no adyacentes en la memoria. En un sistema de memoria virtual, se les dice a los programadores que tienen su disposición todo el espacio de direccionamiento. Además, el campo de direcciones del código de instrucciones tiene una cantidad suficiente de bits para especificar todas las direcciones virtuales. Memoria auxiliar

Memoria principal

Programa 1 Programa 1 Datos 1,1 Datos 1,2 Datos 1,1 Programa 2 Datos 2,1

Espacio de memoria M = 32k = 215

Espacio de dirección N = 1024k = 220

Figura 4.6: Relación entre espacios de dirección y de memoria en un sistema de memoria virtual.

En

nuestro ejemplo,

el campo de dirección de un código de instrucción

consistirá en 20 bits, pero

las direcciones de memoria física deben

especificarse con sólo 15 bits. por lo tanto, la CPU hará

referencia a

instrucciones y datos con direcciones de 20 bits, pero la información en esta dirección debe tomarse de la

memoria física,

porque el acceso al

almacenamiento auxiliar para palabras individuales sería prohibitivamente largo

122

(recuerde que para transferencias eficientes, el almacenamiento auxiliar mueve todo un registro a la memoria principal). Entonces se necesita una tabla como la que se muestra en la figura 4.7. El mapeo es una operación dinámica, lo que significa que cada dirección se traduce inmediatamente, conforme la CPU hace referencia a una palabra. La tabla de mapeo debe almacenarse en una memoria separada como se muestra en la figura 4.7 o en la memoria principal. En el primer caso, se necesita una memoria adicional y un tiempo de acceso a memoria extra. En el segundo caso la tabla toma espacios en la memoria principal y se necesitan dos accesos a memoria con el programa corriendo a media velocidad. Una tercera alternativa es utilizar una memoria asociativa. Dirección virtual

Registros de dirección virtual (20 bits)

Tabla de mapeo de memoria

Registros de búfer de tabla de memoria (15 bits)

Registros de búfer de tabla de memoria

Memoria principal

Registros de búfer de memoria principal

Figura 4.7: Tabla de memoria para mapear una dirección virtual.

4.5. PROTECCIÓN DE MEMORIA Pueden asignarse protección de memoria a la dirección física o a la dirección lógica. La protección de memoria a través de la dirección física puede hacerse al asignar a cada bloque en la memoria varios bits de protección que indican el tipo de acceso que se permite a su bloque a otro sería necesario actualizar los bits de protección de bloque. Un lugar mucho mejor para aplicar protección física. Esto puede hacerse al incluir información de protección dentro de la 123

tabla de segmento o en el circuito del registro de segmento de administración de memoria.

CAPÍTULO 5 ADMINISTRACÓN DE LOS ARCHIVOS 5.1. 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.

124

-

Los archivos son una colección de datos con nombre.

-

Pueden ser m anipulados 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.

5.2. FUNCIONES DEL ADMINISTRADOR DE ARCHIVOS El administrador de archivos tiene un trabajo complicado. Está a cargo de los componentes físicos del sistema, sus recursos de información y de las políticas que se utilizan para almacenar y distribuir los archivos. A fin de desempeñar sus funciones, tiene que ejecutar estas cuatro tareas: 1.

Llevar el control de dónde se almacena cada archivo.

2.

Utilizar una política que determine dónde y cómo se almacenarán los archivos, asegurando el uso

eficiente del espacio de almacenamiento

disponible y proporcionando

un acceso

eficiente del espacio de

almacenamiento disponible y proporcionando un acceso eficiente

a los

archivos. 3.

Asignar cada archivo cuando se ha aceptado el acceso de un usuario al mismo y registrar su uso.

4.

Desasignar el archivo cuando éste es devuelto a almacenamiento y comunicar su disponibilidad a otros

interesados que pudieran estar

esperando. Por ejemplo, el sistema de archivos es como una biblioteca, con el administrador de archivos como bibliotecario – este último realiza las mismas

125

cuatro tareas: 1.

Utiliza el catalogo de tarjetas para llevar el control de cada elemento de la colección; las tarjetas listan el número de identificación y los detalles que ayudan a los clientes a encontrar cada libro.

2.

La biblioteca se apoya en una política predeterminada para almacenar todo lo que está en la colección, incluyendo libros de tamaño afuera de lo común, revistas, grabaciones, mapas y cintas. Éstas se deben organizar físicamente, de manera que las personas pueden encontrarlas cuando lo necesiten.

3.

cuando se solicita, el libro se toma de la estantería y se registra el nombre del solicitante en el archivo de circulación.

4.

cuando el libro es devuelto, el bibliotecario elimina el reglón del archivo de circulación y vuelve a poner el elemento en la estantería.

Es un sistema de cómputo, el, administrador de archivos controla sus archivos utilizando directorios que contienen sus nombres, localización física en el almacenamiento secundario e información importante respecto a cada archivo. La política predeterminada del administrador de archivos define dónde se almacena cada archivo y de que manera el sistema y los usuarios podrán tener acceso a ellos de una manera simple – vía comandos que son independientes de los detalles del dispositivo – además, la política debe establecer quién

tendrá acceso a qué material. Esto supone dos factores:

flexibilidad de acceso a la información y su protección subsecuente. El administrador de archivos efectúa lo anterior al permitir el acceso a archivos compartidos, proporcionar un acceso distribuido y permitir a los usuarios que examinen directorios públicos. Mientras tanto, el sistema operativo debe proteger sus archivos contra el mal funcionamiento del sistema y proporcionar medios de seguridad mediante números de cuenta, contraseña y cerraduras para observar la integridad de los datos y protegerse contra el mal uso. El sistema de computación asigna un archivo activando el dispositivo de almacenamiento secundario apropiado y cargando el archivo en la memoria al mismo tiempo que actualiza los registros del usuario. 126

Por último, el administrador de archivos desasigna un archivo y volviendo a escribirlo (si ha sido revisado) en el dispositivo de almacenamiento secundario. En seguida se notifica su disponibilidad a cualquier proceso que aguarde el acceso al archivo.

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

-

El “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á 127

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 por el “nombre de la trayectoria” del directorio raíz al archivo.

5.4. ARCHIVOS Se considerará el punto de vista del usuario.

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

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

128

-

“Secuencia de registros”:  El archivo es una secuencia de registros de longitud fija, cada uno con su propia estructura interna.

-

“Arbol”:  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.

5.4.3. TIPOS DE ARCHIVOS Muchos S. O. soportan varios tipos de archivos, por ejemplo: 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.

5.4.4. ACCESO A UN ARCHIVO Los tipos de acceso más conocidos son: 129

-

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.

5.4.5. ATRIBUTOS DE ARCHIVO Cada archivo tiene: -

Su nombre y datos.

-

Elementos

adicionales

llamados

atributos,

que

varían

considerablemente de sistema a sistema. Algunos de los posibles atributos de archivo son: -

“Protección”: quién debe tener acceso y de qué forma.

-

“Contraseña”: contraseña necesaria para acceder al archivo.

-

“Creador”: identificador de la persona que creó el archivo.

-

“Propietario”: propietario actual.

-

“Bandera exclusivo - para - lectura”: 0 lectura / escritura, 1 para lectura exclusivamente.

-

“Bandera de ocultamiento”: 0 normal, 1 para no exhibirse en listas.

-

“Bandera de sistema”: 0 archivo normal, 1 archivo de sistema.

130

-

“Bandera de biblioteca”: 0 ya se ha respaldado, 1 necesita respaldo.

-

“Bandera ascii / binario”: 0 archivo en ascii, 1 archivo en binario.

-

“Bandera de acceso aleatorio”: 0 solo acceso secuencial, 1 acceso aleatorio.

-

“Bandera temporal”: 0 normal, 1 eliminar al salir del proceso.

-

“Banderas de cerradura”: 0 no bloqueado, distinto de 0 bloqueado.

-

“Longitud del registro”: número de bytes en un registro.

-

“Posición de la llave”: ajuste de la llave dentro de cada registro.

-

“Longitud de la llave”: número de bytes en el campo llave.

-

“Tiempo de creación”: fecha y hora de creación del archivo.

-

“Tiempo del último acceso”: fecha y hora del último acceso al archivo.

-

“Tiempo de la última modificación”: fecha y hora de la última modificación al archivo.

-

“Tamaño actual”: número de bytes en el archivo.

-

“Tamaño máximo”: tamaño máximo al que puede crecer el archivo.

5.4.6. OPERACIONES CON ARCHIVOS Las llamadas más comunes al sistema relacionadas con los archivos son: -

Create (crear): el archivo se crea sin datos.

-

Delete (eliminar): si el archivo ya no es necesario debe eliminarse para liberar espacio en disco. Ciertos S. O. eliminan automáticamente un archivo no utilizado durante “n” días.

-

Open (abrir): antes de utilizar un archivo, un proceso debe abrirlo. La finalidad es permitir que el sistema traslade los atributos y la lista 131

de direcciones en disco a la memoria principal para un rápido acceso en llamadas posteriores. -

Close (cerrar): cuando concluyen los accesos, los atributos y direcciones del disco ya no son necesarios, por lo que el archivo debe cerrarse y liberar la tabla de espacio interno.

-

Read (leer): los datos se leen del archivo; quien hace la llamada debe especificar la cantidad de datos necesarios y proporcionar un buffer para colocarlos.

-

Write (escribir): los datos se escriben en el archivo, en la posición actual. El tamaño del archivo puede aumentar (agregado de registros) o no (actualización de registros).

-

Append (añadir): es una forma restringida de “write”. Solo puede añadir datos al final del archivo.

-

Seek (buscar): especifica el punto donde posicionarse. Cambia la posición del apuntador a la posición activa en cierto lugar del archivo.

-

Get attributes (obtener atributos): permite a los procesos obtener los atributos del archivo.

-

Set attributes (establecer atributos): algunos atributos pueden ser determinados por el usuario y modificados luego de la creación del archivo. La información relativa al modo de protección y la mayoría de las banderas son un ejemplo obvio.

-

Rename (cambiar de nombre): permite modificar el nombre de un archivo ya existente.

5.4.7. ARCHIVOS MAPEADOS A MEMORIA Algunos S. O. permiten asociar los archivos con un espacio de direcciones de un proceso en ejecución. Se utilizan las llamadas al sistema “map” y “unmap”: -

“Map”: utiliza un nombre de archivo y una dirección virtual y hace

132

que el S. O. asocie al archivo con la dirección virtual en el espacio de direcciones, por lo cual las lecturas o escrituras de las áreas de memoria asociadas al archivo se efectúan también sobre el archivo mapeado. -

“Unmap”: elimina los archivos del espacio de direcciones y concluye la operación de asociación.

El mapeo de archivos elimina la necesidad de programar la E/S directamente, facilitando la programación. Los principales problemas relacionados son: -

Imposibilidad de conocer a priori la longitud del archivo de salida, el que podría superar a la memoria.

-

Dificultad para compartir los archivos mapeados evitando inconsistencias, ya que las modificaciones hechas en las páginas no se verán reflejadas en el disco hasta que dichas páginas sean eliminadas de la memoria.

5.5. DIRECTORIOS Generalmente son utilizados por los S. O. para llevar un registro de los archivos. En muchos sistemas son a su vez también archivos.

5.5.1. SISTEMAS JERÁRQUICOS DE DIRECTORIOS El directorio contiene un conjunto de datos por cada archivo referenciado. Una posibilidad es que el directorio contenga por cada archivo referenciado: -

El nombre.

-

Sus atributos.

-

Las direcciones en disco donde se almacenan los datos.

Otra posibilidad es que cada entrada del directorio contenga: 133

-

El nombre del archivo.

-

Un apuntador a otra estructura de datos donde se encuentran los atributos y las direcciones en disco.

Al abrir un archivo el S. O.: -

Busca en su directorio el nombre del archivo.

-

Extrae los atributos y direcciones en disco.

-

Graba esta información en una tabla de memoria real.

-

Todas las referencias subsecuentes al archivo utilizarán la información de la memoria principal.

DIRECTORIO

ARCHIVOS

◄ DIRECTORIO RAIZ

◄ compartido DIRECTORIO por RAIZtodos los usuarios. Figura 5.1: Un solo directorio

◄ DIRECTORIO DEL USUARIO

Figura 5.2: Un directorio por usuario.

El número y organización de directorios varía de sistema en sistema: -

Directorio único: el sistema tiene un solo directorio con todos los archivos de todos los usuarios, tal como se ve en la figura 5.1.

-

Un directorio por usuario: el sistema habilita un solo directorio por cada usuario, ver figura 5.2.

-

Un árbol de directorios por usuario: el sistema permite que cada usuario tenga tantos directorios como necesite, respetando una jerarquía

134

general.

5.5.2. NOMBRE DE LAS RUTAS DE ACCESO Cuando el sistema de archivos está organizado como un árbol de directorios se necesita una forma de determinar los nombres de los archivos. Los principales métodos para nombres de los archivos son los que se muestra en la figura. 5.3. ◄ DIRECTORIO RAIZ

◄ DIRECTORIO DEL USUARIO

◄ SUBDIRECTORIOS DEL USUARIO

Figura 5.3: Un árbol arbitrario por usuario.

-

Ruta de Acceso Absoluta:  Cada archivo tiene una ruta de acceso absoluta.  Consta de la ruta de acceso desde el directorio raíz hasta el archivo.  Los componentes de la ruta de acceso se separan mediante algún carácter llamado “separador”.

-

Ruta de Acceso Relativa:  Se utiliza junto con el concepto de directorio de trabajo o directorio activo.  Todos los nombres que no comiencen en el directorio raíz se toman en relación con el directorio de trabajo.  El nombre absoluto de la ruta de acceso siempre funciona, sin importar 135

cual sea el directorio de trabajo.

5.5.3. OPERACIONES CON DIRECTORIOS Las llamadas al sistema permitidas para el manejo de los directorios tienen variación de sistema a sistema. Las más comunes son las siguientes: -

Create (crear): se crea un directorio vacío.

-

Delete (eliminar): se elimina un directorio, que debe estar vacío.

-

Opendir (abrir directorio): se pueden leer los directorios:  Antes de poder leer un directorio, éste debe ser abierto.

-

Closedir (cerrar directorio): cuando se ha leído un directorio, éste debe ser cerrado para liberar el espacio correspondiente de la tabla interna.

-

Readdir (leer directorio): regresa la siguiente entrada en un directorio abierto, sin importar el tipo de estructura de directorios que se utilice.

-

Rename (cambiar de nombre): cambia el nombre de un directorio de manera similar al cambio para archivos.

-

Link (ligar): es una técnica que permite que un archivo aparezca en más de un directorio:  Especifica un archivo existente y el nombre de una ruta de acceso.  Crea un enlace del archivo ya existente con el nombre especificado en la ruta de acceso.

-

Unlink (desligar): se elimina una entrada del directorio.

-

Si el archivo que se desea desligar aparece solo en un directorio (el caso normal): a)

Se elimina del sistema de archivos.

 Si el archivo que se desea desligar, está presente en varios directorios:

136

a) Solo se elimina la ruta de acceso especificada. b) Las demás rutas permanecen.

5.6. IMPLANTACIÓN DEL SISTEMA DE ARCHIVOS Y SUS RELACIONES CON LA ASIGNACIÓN Y LIBERACIÓN DE ESPACIO Se consideran aspectos tales como: -

La forma de almacenamiento de archivos y directorios.

-

La administración del espacio en disco.

-

La forma de hacerlo de manera eficiente y confiable.

Se deben tener presentes problemas tales como la “fragmentación” creciente del espacio en disco: -

Ocasiona problemas de performance al hacer que los archivos se desperdiguen a través de bloques muy dispersos.

-

Una técnica para aliviar el problema de la “fragmentación” consiste en realizar periódicamente:  “Condensación”: se pueden “reorganizar” los archivos expresamente o automáticamente según algún criterio predefinido.  “Recolección de basura o residuos”: se puede hacer fuera de línea o en línea, con el sistema activo, según la implementación.

5.6.1. IMPLANTACIÓN DE ARCHIVOS El aspecto clave de la implantación del almacenamiento de archivos es el registro de los bloques asociados a cada archivo. Algunos de los métodos utilizados son los siguientes: -

Asignación contigua o adyacente:

-

Los

archivos

son

asignados

almacenamiento secundario.

137

a

áreas

contiguas

de

-

Las principales ventajas son: a) Facilidad de implantación, ya que solo se precisa el número del bloque de inicio para localizar un archivo. b) Rendimiento excelente respecto de la E / S.  Los principales defectos son: a) Se debe conocer el tamaño máximo del archivo al crearlo. b) Produce una gran fragmentación de los discos.

-

Asignación no contigua:  Son esquemas de almacenamiento más dinámicos, destacándose los siguientes: e) Asignación encadenada orientada hacia el sector: •

El disco se considera compuesto de sectores individuales.

•

Los archivos constan de varios sectores que pueden estar dispersos por todo el disco.

•

Los sectores que pertenecen a un archivo común contienen apuntadores de uno a otro formando una “lista encadenada”.

•

Una “lista de espacio libre” contiene entradas para todos los sectores libres del disco.

•

Las ampliaciones o reducciones en el tamaño de los archivos se resuelven actualizando la “lista de espacio libre” y no hay necesidad de condensación.

•

Las principales desventajas son: º Debido a la posible dispersión en el disco, la recuperación de registros

lógicamente

contiguos

puede

significar

largas

búsquedas. º El mantenimiento de la estructura de “listas encadenadas” significa una sobrecarga en tiempo de ejecución.

138

º Los apuntadores de la estructura de lista consumen espacio en disco. f) Asignación por bloques: •

Es más eficiente y reduce la sobrecarga en ejecución.

•

Es una mezcla de los métodos de asignación contigua y la no contigua.

•

Se asignan bloques de sectores contiguos en vez de sectores individuales.

•

El sistema trata de asignar nuevos bloques a un archivo eligiendo bloques libres lo más próximos posible a los bloques del archivo existentes.

•

Las formas más comunes de implementar la asignación por bloques son: º Encadenamiento de bloques. º Encadenamiento de bloques de índice. º Transformación de archivos orientada hacia bloques.

 Encadenamiento de bloques o lista ligada: •

Las entradas en el directorio de usuarios apuntan al primer bloque de cada archivo.

•

Cada uno de los bloques de longitud que forman un archivo contiene dos partes: º Un bloque de datos. º Un apuntador al bloque siguiente.

•

Cada bloque contiene varios sectores.

•

Frecuentemente el tamaño de un bloque se corresponde con el de una pista completa del disco.

.

139

DIRECTORIO DE USUARIOS DIRECTORIO DE USUARIOS ARCHIVO ARCHIVO

LOCALIZACIÓN LOCALIZADORR

SE REPRESENTA EL ARCHIVO A

A A

DATOS

BLOQUES DE ARCHIVOS O BLOQUES FISICO 4

DATOS

BLOQUES DE ARCHIVOS 1 BLOQUES FISICO 7

BLOQUES DE ARCHIVOS 2

DATOS

B.DE. A. 6 B.F.15

BLOQUES FISICO 2

B.DE. A. 3 B.F.10

DATOS

DATOS

B.DE. A. 4 B.F.12

DATOS

B.DE. A. 5 B.F.18

DATOS

Figura 5.4: Encadenamiento de bloques o lista ligada de bloques.

•

Localizar un registro determinado requiere: º Buscar en la cadena de bloques hasta encontrar el bloque apropiado. º Buscar en el bloque hasta encontrar el registro.

•

El examen de la cadena desde el principio puede ser lento ya que debe realizarse de bloque en bloque, y pueden estar dispersos por todo el disco.

•

La inserción y el retiro son inmediatos, dado que se deben

140

modificar los apuntadores del bloque procedente. •

Se pueden usar “listas de encadenamiento doble”, hacia adelante y hacia atrás, con lo que se facilita la búsqueda, ver figura. 5.4.

 Encadenamiento de bloques de índices: •

Los apuntadores son colocados en varios bloques de índices separados: º Cada bloque de índices contiene un número fijo de elementos. º Cada entrada contiene un identificador de registros y un apuntador a ese registro, tal como se muestra en la figura 5.5. DIRECTORIO DE USUARIOS ARCHIVO

LOCALIZACIÓN

ARCHIVO

LOCAL

BLOQUES DE INDICES

IZADO

BLOQUES DE CONTINUACIÓN DE INDICE

RR

Figura 5.5: Encadenamiento de bloques de índice.

º Si es necesario utilizar más de un bloque de índices para describir un archivo, se encadena una serie de bloques de índices. •

La gran ventaja es que la búsqueda puede realizarse en los propios bloques de índices.

•

Los bloques de índices pueden mantenerse juntos en el almacenamiento secundario para acortar la búsqueda, pero para mejor performance podrían mantenerse en el almacenamiento

141

primario. •

La principal desventaja es que las inserciones pueden requerir la reconstrucción completa de los bloques de índices: º Una posibilidad es dejar vacía una parte de los bloques de índices

para

facilitar

inserciones

futuras

y

retardar

las

reconstrucciones. •

Es suficiente que el dato del directorio contenga el número de bloque inicial para localizar todos los bloques restantes, sin importar el tamaño del archivo.

 Transformación de archivos orientada hacia bloques (Ver figura 5.6.): •

Se utilizan números de bloques en vez de apuntadores.

•

Los números de bloques se convierten fácilmente a direcciones de bloques gracias a la geometría del disco.

•

Se conserva un mapa del archivo, conteniendo una entrada para cada bloque del disco.

•

Las entradas en el directorio del usuario apuntan a la primera entrada al mapa del archivo para cada archivo.

•

Cada entrada al mapa del archivo contiene el número del bloque siguiente de ese archivo.

•

La entrada al mapa del archivo correspondiente a la última entrada de un archivo determinado se ajusta a algún valor “centinela” (“nil”) para indicar que se alcanzó el último bloque de un archivo.

•

El sistema puede mantener una lista de bloques libres.

•

La principal ventaja es que las cercanías físicas del disco se reflejan en el mapa del archivo.

 Nodos-i (nodos índices): •

Se asocia a cada archivo una pequeña tabla, llamada nodo-i 142

(nodo índice): º Contiene los atributos y direcciones en disco de los bloques del archivo. º Se traslada del disco a la memoria principal al abrir el archivo. º En rigor, almacena solo las primeras direcciones en disco: º Si el archivo es pequeño, toda la información está en el nodo-i.

MAPA DEL ARCHIVO DIRECTORIO DE USUARIOS

0

22

ARCHIVOS

LOCALIZACIÓN

1

NIL

A

8

2

5

B

6

3

26

C

6

4

9

5

20

6 6

BLOQUEO FISICOS EN EL ALMACENAMIENTO SECUNDARIO BLOQUEO 0 B(4)

BLOQUEO1 B(10)

BLOQUEO2 B(1)

BLOQUEO3 B(4)

BLOQUEO4 B(8)

BLOQUEO5 B(2)

BLOQUEO6 B(1)

BLOQUEO 7 LIBRE

BLOQUEO 8

BLOQUEO 9 A(9)

BLOQUEO 10 A(2)

BLOQUEO 11 LIBRE

BLOQUEO 12 A(3)

BLOQUEO 13 B(7)

BLOQUEO 14 B(3)

BLOQUEO 15 LIBRE

BLOQUEO 16 LIBRE

BLOQUEO 17

BLOQUEO 18 B(6)

BLOQUEO 19 C(5)

BLOQUEO 20 C(3)

BLOQUEO 21 LIBRE

BLOQUEO 22

BLOQUEO 23 C(4)

BLOQUEO 24 LIBRE

BLOQUEO 25 LIBRE

BLOQUEO 26 A(5)

BLOQUEO 27 LIBRE

A(1)

B(5)

A(2)

143

6

10

7

LIBRE

8

17

9

1

10

14

11

LIBRE

12

3

13

4

14

0

15

LIBRE

16

LIBRE

17

12

18

13

19

NIL

20

23

21

LIBRE

22

18

23

19

24

LIBRE

25

LIBRE

26

NIL

27

LIBRE

Figura 5.6: Transformación de archivos orientada hacia bloques.

º Si el archivo es grande, una de las direcciones en el nodo-i es la dirección de un bloque en el disco llamado bloque simplemente indirecto:  Contiene las direcciones en disco adicionales.  Si resulta insuficiente, otra dirección en el nodo-i, el bloque doblemente indirecto, contiene la dirección de un bloque que presenta una lista de los bloques simplemente indirectos:  Cada bloque simplemente indirecto apunta a un grupo de bloques de datos.  De ser necesario se pueden utilizar bloques triple mente indirectos.

144

5.6.2. IMPLANTACIÓN DE DIRECTORIOS Para abrir un archivo el S. O. utiliza información del directorio: -

El directorio contiene la información necesaria para encontrar los bloques en el disco.

-

El tipo de información varía según el sistema.

La principal función del sistema de directorios es asociar el nombre del archivo con la información necesaria para localizar los datos. Un aspecto íntimamente ligado con esto es la posición de almacenamiento de los atributos: -

Una posibilidad es almacenarlos en forma directa dentro del dato del directorio.

-

Otra posibilidad es almacenar los atributos en el nodo-i en vez de utilizar la entrada del directorio.

5.6.3. ARCHIVOS COMPARTIDOS Frecuentemente

conviene

que

los

archivos

compartidos

aparezcan

simultáneamenteNODO en distintos directorios de distintos usuarios. I ATRIBUTOS

El propio sistema de archivos es una gráfica dirigida acíclica en vez de un BLOQUE SIMPLEMENTE INDIRECTO

árbol.

La conexión entre un directorio y un archivo de otro directorio al cual comparten se denomina enlace. BLOQUE

Si los directorios realmente contienen DOBLEMENTE direcciones en disco: INDIRECTO

-

Se debe tener una copia de las direcciones en disco en el directorio DIRECCIONES que accede al archivo compartido al enlazar el archivo. EN DISCO

-

DIRECCIONES

DE

LOS aBLOQUES DE Se debe evitar que los cambios hechos por un usuario través de DATOS

un directorio no sean visibles por los demás usuarios, para lo que se consideraran dos soluciones posibles. Primera solución:

145 BLOQUE TRIPLEMENTE INDIRECTO

Figura 5.7: Esquema de un nodo-i.

-

Los bloques del disco no se enlistan en los directorios, sino en una pequeña estructura de datos asociada al propio archivo.

-

Los directorios apuntarían solo en una pequeña estructura de datos, que podría ser el nodo-i (Ver Figura 5.7.).

Segunda solución: -

El enlace se produce haciendo que el sistema cree un nuevo archivo de tipo “link”.

-

El archivo “link”:  Ingresa al directorio del usuario que accede a un archivo de otro directorio y usuario. 146

 Solo contiene el nombre de la ruta de acceso del archivo al cual se enlaza. -

Este criterio se denomina enlace simbólico.

Desventajas de la primera solución: -

La creación de un enlace:  No modifica la propiedad respecto de un archivo.  Aumenta el contador de enlaces del nodo-i: •

El sistema sabe el número de entradas de directorio que apuntan en cierto momento al archivo.

-

Si el propietario inicial del archivo intenta eliminarlo, surge un problema para el sistema:  Si elimina el archivo y limpia el nodo-i, el directorio que enlazo al archivo tendrá una entrada que apunta a un nodo-i no válido.  Si el nodo-i se reasigna a otro archivo el enlace apuntará al archivo incorrecto.  El sistema: •

Puede ver por medio del contador de enlaces en el nodo-i que el archivo sigue utilizándose.

•

No puede localizar todas las entradas de directorio asociadas a ese archivo para eliminarlas.

La solución podría ser: -

Eliminar la entrada del directorio inicialmente propietario del archivo.

-

Dejar intacto el nodo-i:  Se daría el caso que el directorio que posee el enlace es el único que 147

posee una entrada de directorio para un archivo de otro directorio, para el cual dicho archivo ya no existe.  Esto no ocurre con los enlaces simbólicos ya que solo el propietario verdadero tiene un apuntador al nodo-i: •

Los usuarios enlazados al archivo solo tienen nombres de rutas de acceso y no apuntadores a nodo-i.

•

Cuando el propietario elimina un archivo, este se destruye.

Desventajas de la segunda solución: -

El principal problema es su costo excesivo, especialmente en accesos a disco, puesto que se debe leer el archivo que contiene la ruta de acceso, analizarla y seguirla componente a componente hasta alcanzar el nodo-i.

-

Se precisa un nodo-i adicional por cada enlace simbólico y un bloque adicional en disco para almacenar la ruta de acceso.

-

Los archivos pueden tener dos o más rutas de acceso, debido a lo cual, en búsquedas genéricas se podría encontrar el mismo archivo por distintas rutas y tratárselo como si fueran archivos distintos.

Los enlaces simbólicos tienen la ventaja de que se pueden utilizar para enlazar archivos en otras máquinas, en cualquier parte del mundo; se debe proporcionar solo la dirección de la red de la máquina donde reside el archivo y su ruta de acceso en esa máquina.

CAPÍTULO 6 ENTRADA / SALIDA 6.1. INTRODUCCIÓN Una de las funciones principales de un S. O. es el control de todos los dispositivos de E /S de la computadora. 148

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.

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

6.2.1. 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:

149

-

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 carácter 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.

-

Un ejemplo típico 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 programa 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.

6.2.2. 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. 150

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 ejemplo).  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 necesarias.

-

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, 151

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

Rs 232 primario

3F8 – 3FF

12

Rs 232 secundario

2F8 – 2F2

11

Tabla 6.1: Controladores de E/S, direcciones de E/S y vector de interrupciones.

6.2.3. ACCESO DIRECTO A MEMORIA (DMA) Muchos controladores, especialmente los correspondientes a dispositivos de bloque, permiten el DMA; ver figura 6.1. Si se lee el disco sin DMA:

152

-

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

CONTROLADOR DE DISCO

UNIDAD BUFFER

CPU

REFISTROS DEL DMA

CONTADOR

DIREC. EN MEMORIA

153 BUS DEL SISTEMA

CONTADOR

Figura 6.1: Un controlador realiza completamente una transferencia DMA.

-

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

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.

-

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:

154

Figura 6.2: Factores de separación: sin separación, separación simple y separación doble.

-

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 (Ver Figura 6.2):

 •

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.

•

Esto permite al S. O.: º Leer los bloques con numeración consecutiva. º Conservar la máxima velocidad posible del hardware.

6.3. PRINCIPIOS DEL SOFTWARE DE E/S

155

La idea básica es organizar el software como una serie de capas donde (ver figura 6.3): -

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.

Figura 6.3: Capas del sistema de entrada / salida y las principales funciones de cada capa.

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

156

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 que 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: -

Manejadores de interrupciones.

-

Directivas de dispositivos.

-

Software de S. O. independiente de los dispositivos.

-

Software a nivel usuario.

6.3.2. 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. 157

-

El procedimiento de interrupción realiza lo necesario para desbloquear el proceso que lo inicio.

6.3.3. 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 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 ejemplo 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.

158

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.



6.4. DISCOS - HARDWARE PARA DISCOS 6.4.1. DISCOS Las siguientes son las principales ventajas con respecto del uso de la memoria principal como almacenamiento: -

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

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

159

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.

6.5. OPERACIÓN DE ALMACENAMIENTO DE DISCO DE CABEZA MÓVIL Los datos se graban en una serie de discos magnéticos o platos (Ver figura 6.4). El eje común de los discos gira a una velocidad del orden de 4.000 o más revoluciones por minuto. Se lee o escribe mediante una serie de cabezas de lectura - escritura: -

Se dispone de una por cada superficie de disco.

160

Figura 6.4: Esquema de un disco de cabeza móvil.

-

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

161

Figura 6.5: Componentes del acceso a un disco.

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

6.7. 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 162

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 l as colas de requerimientos.

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

163

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.

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

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

164

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.

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

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

6.9.4. PLANIFICACIÓN SCAN DE N - PASOS

165

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.

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

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

6.9.7. CONCLUSIONES Mediante trabajos de simulación y de laboratorio se demostró lo siguiente:

166

-

La estrategia SCAN es la mejor con carga baja.

-

La estrategia C - SCAN es la mejor con cargas medias y pesadas.

-

La estrategia C - SCAN con optimización rotacional es la mejor para cargas muy pesadas (mejor que la estrategia Eschenbach inclusive).

167

BIBLIOGRAFIA

ANDREW S. TANENBAUM. "Sistemas Operativos Distribuidos", Prentice Hall (1996). CARRETERO PÉREZ, JESÚS; GARCÍA CARBALLEIRA, FÉLIX, DE MIGUEL ANASAGASTI, PEDRO; PÉREZ COSTOYA, FERNANDO. "Sistemas Operativos. Una visión aplicada. McGrawHill, 2001. DEITEL, H. M., “Sistemas Iberoamericana, 1993.

Operativos”

(2/Ed.),

Addison_Wesley

FINKEL, R. A., “Fundamentos de Sistemas Operativos. Un Estudio Actual de los Sistemas Operativos, Anaya Multimedia, 1990. MILENKOVIC, M., “Sistemas Operativos. Conceptos y Diseño” (2/Ed), McGrawHill, 1994. STALLINGS, W. “Organización y Arquitectura de Computadores. Diseño para Optimizar Prestaciones” (4/Ed.), Prentice Hall, 1997. TANENBAUM, A. S., Y WOODHULL, A. S. “Sistemas Operativos. Diseño e Implementación” (2/Ed.), Prentice Hall, 1997. GEORGE COULOURIS, JEAN DOLLIMORE, TIM KINDBERG. "Distributed Systems, Concepts and Design", Addison-Wesley (1994). ABRAHAM SILBERSCHATZ; PETER GALVIN; GREG GAYNE: "Operating System Concepts" (6th. ed.). John Wiley & Sons, Inc 2002. ANDREW S. TANENBAUM. "Modern Operating System" (2nd ed.). Prentice Hall 2001. SILBERSCHATZ, A., Y GALVIN, P. B. “Operating System Concepts” (4/Ed. o siguientes), Addison-Wesley, 1994. STALLINGS, W. “Operating Systems “ (2/Ed.), Prentice Hall, 1995. TANENBAUM, A. S., “Modern Operating Systems”, Prentice Hall, 1992. BEN-ARI, M. “Principles of Concurrent Programming” Prentice Hall, 1982. NUTT, G. “Operating Systems”. A Modern Perspective, Addison-Wesley Longman, 2000.

168