SEP

SNEST

DGEST

I NSTITUTO T ECNOLGICO DEL I STMO

Nombre del Tema:

DESARROLLO DE LAS UNIDADES EN ANDROID

Materia:

SISTEMAS OPERATIVOS

Alumnos:

ROJAS TRUJILLO AZAEL

Docente:

JACINTO TOLEDO TORRES

Carrera:

INGENIERA EN SISTEMAS COMPUTACIONALES

HEROICA CD. DE JUCHITAN DE ZARAGOZA OAXACA

UNIDAD 1 Introduccin a los Sistemas Operativos

1.1 Concepto y definicin de Sistemas Operativos
Un Sistema Operativo es una parte importante de cualquier sistema de computacin. Un sistema de computacin puede dividirse en cuatro componentes: el hardware, el Sistema Operativo, los programas de aplicacin y los usuarios. El hardware (Unidad Central de Procesamiento (UCP), memoria y dispositivos de entrada/salida (E/S)) proporciona los recursos de computacin bsicos. Los programas de aplicacin (compiladores, sistemas de bases de datos, juegos de video y programas para negocios) definen la forma en que estos recursos se emplean para resolver los problemas de computacin de los usuarios.

Recursos administrados por el Sistema Operativo Existen diversas definiciones de lo que es un Sistema Operativo, pero no hay una definicin exacta, es decir una que sea estndar; a continuacin se presentan algunas: 1.Se pueden imaginar un Sistema Operativo como los programas, instalados en el software o firmware, que hacen utilizable el hardware. El hardware proporciona la "capacidad bruta de cmputo "; los sistemas operativos ponen dicha capacidad de a.C.

al alcance de los usuarios y administran cuidadosamente el hardware para lograr un buen rendimiento. 2.- Los Sistemas Operativos son ante todo administradores de recursos; el principal recurso que administran es el hardware del computador; adems de los procesadores, los medios de almacenamiento, los dispositivos de entrada/salida, los dispositivos de comunicacin y los datos. 3.- Un Sistema Operativo es un programa que acta como intermediario entre el usuario y el hardware del computador y su propsito es proporcionar el entorno en el cual el usuario pueda ejecutar programas. Entonces, el objetivo principal de un Sistema Operativo es, lograr que el sistema de computacin se use de manera cmoda, y el objetivo secundario es que el hardware del computador se emplee de manera eficiente. 4.- Un Sistema Operativo es un conjunto de programas que controla la ejecucin de programas de aplicacin y acta como una interfaz entre el usuario y el hardware de una computadora, esto es, un Sistema Operativo explota y administra los recursos de hardware de la computadora con el objeto de proporcionar un conjunto de servicios a los usuarios del sistema. En resumen, se podra decir que los Sistemas Operativos son un conjunto de programas que crean la interfaz del hardware con el usuario, y que tiene dos funciones primordiales, que son: Gestionar el hardware.- Se refiere al hecho de administrar de una forma ms eficiente los recursos de la mquina. Facilitar el trabajo al usuario.- Permite una comunicacin con los dispositivos de la mquina. El Sistema Operativo se encuentra almacenado en la memoria secundaria. Primero se carga y ejecuta un pedazo de cdigo que se encuentra en el procesador, el cual carga el BIOS, y este a su vez carga el Sistema Operativo que carga todos los programas de aplicacin y software variado.

1.2 Funciones y Caractersticas

En general, se puede decir que un Sistema Operativo tiene las siguientes caractersticas: Conveniencia. Un Sistema Operativo hace ms conveniente el uso de una computadora. Eficiencia. Un Sistema Operativo permite que los recursos de la computadora se usen de la manera ms eficiente posible.

Habilidad para evolucionar. Un Sistema Operativo deber construirse de manera que permita el desarrollo, prueba o introduccin efectiva de nuevas funciones del sistema sin interferir con el servicio. Encargado de administrar el hardware. El Sistema Operativo se encarga de manejar de una mejor manera los recursos de la computadora en cuanto a hardware se refiere, esto es, asignar a cada proceso una parte del procesador para poder compartir los recursos. Relacionar dispositivos (gestionar a travs del kernel). El Sistema Operativo se debe encargar de comunicar a los dispositivos perifricos, cuando el usuario as lo requiera.

Organizar datos para acceso rapido y seguro. Manejar las comunicaciones en red. El Sistema Operativo permite al usuario manejar con alta facilidad todo lo referente a la instalacin y uso de las redes de computadoras.

Procesamiento por bytes de flujo a travs del bus de datos.

Facilitar las entradas y salidas. Un Sistema Operativo debe hacerle fcil al usuario el acceso y manejo de los dispositivos de Entrada/Salida de la computadora. Tcnicas de recuperacin de errores. Evita que otros usuarios interfieran. El Sistema Operativo evita que los usuarios se bloqueen entre ellos, informndoles si esa aplicacin esta siendo ocupada por otro usuario. Generacin de estadsticas. Permite que se puedan compartir el hardware y los datos entre los usuarios.

El software de aplicacin son programas que se utilizan para disear, tal como el procesador de palabras, lenguajes de programacin, hojas de clculo, etc. El software de base sirve para interactuar el usuario con la mquina, son un conjunto de programas que facilitan el ambiente plataforma, y permite el diseo del mismo. El Software de base est compuesto por: Cargadores. Compiladores. Ensambladores. Macros.

1.3 Evolucin Histrica

Para tratar de comprender los requisitos de un Sistema Operativo y el significado de las principales caracteristicas de un Sistema Operativo contemporaneo, es til considerar como han ido evolucionando estos con el tiempo. Existen diferentes enfoques o versiones de cmo han ido evolucionando los Sistemas Operativos La primera de estas versiones podra ser esta: En los 40's, se introducen los programas bit a bit, por medio de interruptores mecnicos y

despus se introdujo el lenguaje mquina que trabajaba por tarjetas perforadas. Con las primeras computadoras, desde finales de los aos 40 hasta la mitad de los aos 50, el programador interactuaba de manera directa con el hardware de la computadora, no exista realmente un Sistema Operativo; las primeras computadoras utilizaban bulbos, la entrada de datos y los programas se realizaban a travs del lenguaje maquina (bits) o a travs de interruptores.

Durante los aos 50's y 60's.- A principio de los 50's, la compaa General's Motors implanto el primer sistema operativo para su IBM 170. Empiezan a surgir las tarjetas perforadas las cuales permiten que los usuarios (que en ese tiempo eran programadores, diseadores, capturistas, etc.), se encarguen de modificar sus programas. Establecan o apartaban tiempo, metan o introducan sus programas, corregan y depuraban sus programas en su tiempo. A esto se le llamaba trabajo en serie. Todo esto se traduca en prdida de tiempo y tiempos de programas excesivos.

En los aos 60's y 70's se genera el circuito integrado, se organizan los trabajos y se generan los procesos Batch (por lotes), lo cual consiste en determinar los trabajos comunes y realizarlos todos juntos de una sola vez. En esta epoca surgen las unidades de cinta y el cargador de programas, el cual se considera como el primer tipo de Sistema Operativo.

En los 80's, inicio el auge de la INTERNET en los Estados Unidos de America. A finales de los aos 80's comienza el gran auge y evolucion de los Sistemas Operativos. Se descubre el concepto de multiprogramacion que consiste en tener cargados en memoria a varios trabajos al mismo tiempo, tema principal de los Sistemas Operativos actuales.

Los 90's y el futuro, entramos a la era de la computacin distribuida y del multiprocesamiento a travs de mltiples redes de computadoras, aprovechando el ciclo del procesador.

Se tendr una configuracin dinmica con un reconocimiento inmediato de dispositivos

y software que se aada o elimine de las redes a travs de procesos de registro y localizadores.

La conectividad se facilita gracias a estndares y protocolos de sistemas abiertos por organizaciones como la Organizacin Internacional de normas, fundacin de software abierto, todo estar ms controlado por los protocolos de comunicacin OSI y por la red de servicios digital ISDN.

Se ha desarrollado otra versin, la cual se ha hecho en base a etapas o generaciones: 1a. Etapa (1945-1955): Bulbos y conexiones.

Despus de los infructuosos esfuerzos de Babbage, hubo poco progreso en la construccin de las computadoras digitales, hasta la Segunda Guerra Mundial. A mitad de la dcada de los 40's, Howard Aiken (Harvard), John Von Newman (Instituto de Estudios Avanzados, Princeton), J. Prespe R. Eckert y Williams Mauchley (Universidad de Pennsylvania), asi como Conrad Zuse (Alemania), entre otros lograron construir maquinas de calculo mediante bulbos. Estas maquinas eran enormes y llenaban cuartos completos con decenas de miles de bulbos, pero eran mucho mas lentas que la computadora casera mas economica en nuestros das. Toda la programacin se llevaba a cabo en lenguaje de maquina absoluto y con frecuencia se utilizaban conexiones para controlar las funciones bsicas de la mquina. Los lenguajes de programacin eran desconocidos (incluso el lenguaje ensamblador). No se oa de los Sistemas Operativos el modo usual de operacin consista en que el programador reservaba cierto periodo en una hoja de reservacin pegada a la pared, iba al cuarto de la mquina, insertaba su conexin a la computadora y pasaba unas horas esperando que ninguno de los 20,000 o mas bulbos se quemara durante la ejecucin. La inmensa mayora de los problemas eran calculos numericos directos, por ejemplo, el clculo de valores para tablas de senos y cosenos. A principio de la dcada de los 50's la rutina mejoro un poco con la introduccin de las tarjetas perforadas. Fue entonces posible escribir los programas y leerlas en vez de insertar conexiones, por lo dems el proceso era el mismo.

10

2a. Etapa. (1955-1965): Transistores y Sistemas de Procesamiento por lotes.

La introduccin del transistor a mediados de los aos 50's modifico en forma radical el panorama. Las computadoras se volvieron confiables de forma que podan fabricarse y venderse a clientes, con la esperanza de que ellas continuaran funcionando lo suficiente como para realizar un trabajo en forma. Dado el alto costo del equipo, no debe sorprender el hecho de que las personas buscaron en forma por dems rpidas vas para reducir el tiempo invertido. La solucin que, por lo general se adopt, fue la del sistema de procesamiento por lotes.

3ra Etapa (1965-1980): Circuitos integrados y multiprogramacion.

La 360 de IBM fue la primera linea principal de computadoras que utilizo los circuitos integrados, lo que proporciono una gran ventaja en el precio y desempeo con respecto a las maquinas de la segunda generacin, construidas a partir de transistores individuales. Se trabaj con un sistema operativo enorme y extraordinariamente complejo. A pesar de su enorme tamao y sus problemas el sistema operativo de la linea IBM 360 y los sistemas operativos similares de esta generacin producidos por otros fabricantes de computadoras realmente pudieron satisfacer, en forma razonable a la mayora de sus clientes. Tambin popularizaron varias tcnicas fundamentales, ausentes de los sistemas operativos de la segunda generacin, de las cuales la ms importante era la de multiprogramacion.

Otra caracterstica era la capacidad de leer trabajos de las tarjetas al disco, tan pronto como llegara al cuarto de cmputo. Asi, siempre que concluyera un trabajo el sistema operativo poda cargar un nuevo trabajo del disco en la particin que quedara desocupada y ejecutarlo.

11

4ta Etapa (1980-Actualidad): Computadoras personales. Un interesante desarrollo que comenz a llevarse a cabo a mediados de la dcada de los ochenta ha sido el crecimiento de las redes de computadoras personales, con sistemas operativos de red y sistemas operativos distribuidos. En los sistemas operativos de red, los usuarios estn conscientes de la existencia de varias computadoras y pueden conectarse con maquinas remotas y copiar archivos de una maquina a otra. Cada mquina ejecuta su propio sistema operativo local y tiene su propio usuario. Por el contrario, un sistema operativo distribuido es aquel que aparece ante sus usuarios como un sistema tradicional de un solo procesador, aun cuando est compuesto por varios procesadores. En un sistema distribuido verdadero, los usuarios no deben ser conscientes del lugar donde su programa se ejecute o de lugar donde se encuentren sus archivos; eso debe ser manejado en forma automtica y eficaz por el sistema operativo.

1.4 Clasificacin
Con el paso del tiempo, los Sistemas Operativos fueron clasificndose de diferentes maneras, dependiendo del uso o de la aplicacin que se les daba. A continuacin se mostraran diversos tipos de Sistemas Operativos que existen en la actualidad, con algunas de sus caracteristicas:

1.4.1 Sistemas Operativos por Lotes

Los Sistemas Operativos por lotes, procesan una gran cantidad de trabajos con poca o ninguna interaccin entre los usuarios y los programas en ejecucin. Se renen todos los trabajos comunes para realizarlos al mismo tiempo, evitando la espera de dos o ms trabajos como sucede en el procesamiento en serie. Estos sistemas son de los ms tradicionales y antiguos, y fueron introducidos alrededor de 1956 para aumentar la capacidad de procesamiento de los programas. Cuando estos sistemas son bien planeados, pueden tener un tiempo de ejecucin muy alto, porque el procesador es mejor utilizado y los Sistemas Operativos pueden ser
12

simples, debido a la secuencialidad de la ejecucin de los trabajos. Algunos ejemplos de Sistemas Operativos por lotes exitosos son el SCOPE, del DC6600, el cual est orientado a procesamiento cientfico pesado, y el EXEC II para el UNIVAC 1107, orientado a procesamiento acadmico. Algunas otras caracteristicas con que cuentan los Sistemas Operativos por lotes son: Requiere que el programa, datos y rdenes al sistema sean remitidos todos juntos en forma de lote. Permiten poca o ninguna interaccin usuario/programa en ejecucin. Mayor potencial de utilizacin de recursos que procesamiento serial simple en sistemas multiusuarios. No conveniente para desarrollo de programas por bajo tiempo de retorno y depuracin fuera de linea. Conveniente para programas de largos tiempos de ejecucin (Ej., anlisis estadsticos, nminas de personal, etc.). Se encuentra en muchos computadores personales combinados con procesamiento serial. Planificacin del procesador sencilla, tpicamente procesados en orden de llegada. Planificacin de memoria sencilla, generalmente se divide en dos: parte residente del S.O. y programas transitorios. No requieren gestin crtica de dispositivos en el tiempo. Suelen proporcionar gestin sencilla de manejo de archivos: se requiere poca proteccin y ningn control de concurrencia para el acceso.

Figura. Trabajos ms comunes que realiza el Sistema Operativo por lotes.

1.4.2 Sistemas Operativos de Tiempo Real

Los Sistemas Operativos de tiempo real son aquellos en los cuales no tiene importancia el usuario, sino los procesos. Por lo general, estn subutilizados sus recursos con la finalidad de prestar atencin a los procesos en el momento que lo requieran. Se utilizan en entornos donde son procesados un gran nmero de sucesos o eventos.

13

Muchos Sistemas Operativos de tiempo real son construidos para aplicaciones muy especficas como control de trfico areo, bolsas de valores, control de refineras, control de laminadores. Tambin en el ramo automovilstico y de la electrnica de consumo, las aplicaciones de tiempo real estn creciendo muy rpidamente. Otros campos de aplicacin de los Sistemas Operativos de tiempo real son los siguientes: Control de trenes. Telecomunicaciones. Sistemas de fabricacin integrada. Produccin y distribucin de energa elctrica. Control de edificios. Sistemas multimedia.

Algunos ejemplos de Sistemas Operativos de tiempo real son: VxWorks, Solaris, Lyns OS y Spectra. Los Sistemas Operativos de tiempo real, cuentan con las siguientes caracteristicas: Se dan en entornos en donde deben ser aceptados y procesados gran cantidad de sucesos, la mayora externos al sistema computacional, en breve tiempo o dentro de ciertos plazos. Se utilizan en control industrial, conmutacin telefnica, control de vuelo, simulaciones en tiempo real., aplicaciones militares, etc. Objetivo es proporcionar rpidos tiempos de respuesta. Procesa rfagas de miles de interrupciones por segundo sin perder un solo suceso. Proceso se activa tras ocurrencia de suceso, mediante interrupcin. Proceso de mayor prioridad expropia recursos. Por tanto generalmente se utiliza planificacin expropiara basada en prioridades. Gestin de memoria menos exigente que tiempo compartido, usualmente procesos son residentes permanentes en memoria. Poblacin de procesos esttica en gran medida. Poco movimiento de programas entre almacenamiento secundario y memoria. Gestin de archivos se orienta ms a velocidad de acceso que a utilizacin eficiente del recurso.

14

1.4.3 Sistemas Operativos por Multiprogramacion

Se distinguen por sus habilidades para poder soportar la ejecucin de dos o ms trabajos activos (que se estn ejecutado) al mismo tiempo. Esto trae como resultado que la Unidad Central de Procesamiento (UCP) siempre tenga alguna tarea que ejecutar, aprovechando al mximo su utilizacin. Su objetivo es tener a varias tareas en la memoria principal, de manera que cada uno est usando el procesador, o un procesador distinto, es decir, involucra maquinas con ms de una UCP. Sistemas Operativos como UNIX, Windows 95, Windows 98, Windows NT, MAC-OS, OS/2, soportan la multitarea. Las caracteristicas de un Sistema Operativo de multiprogramacion o multitarea son las siguientes: Mejora productividad del sistema y utilizacin de recursos. Multiplex recursos entre varios programas. Generalmente soportan mltiples usuarios (multiusuarios). Proporcionan facilidades para mantener el entorno de usuarios individuales. Requieren validacin de usuario para seguridad y proteccin. Proporcionan contabilidad del uso de los recursos por parte de los usuarios. Multitarea sin soporte multiusuario se encuentra en algunos computadores personales o en sistemas de tiempo real. Sistemas multiprocesadores son sistemas multitareas por definicin ya que soportan la ejecucin simultanea de mltiples tareas sobre diferentes procesadores. En general, los sistemas de multiprogramacion se caracterizan por tener mltiples programas activos compitiendo por los recursos del sistema: procesador, memoria, dispositivos perifricos.

15

1.4.4 Sistemas Operativos de Tiempo Compartido

Permiten la simulacin de que el sistema y sus recursos son todos para cada usuario. El usuario hace una peticin a la computadora, est la procesa tan pronto como le es posible, y la respuesta aparecer en la terminal del usuario. Los principales recursos del sistema, el procesador, la memoria, dispositivos de E/S, son continuamente utilizados entre los diversos usuarios, dando a cada usuario la ilusin de que tiene el sistema dedicado para su mismo. Esto trae como consecuencia una gran carga de trabajo al Sistema Operativo, principalmente en la administracin de memoria principal y secundaria. Ejemplos de Sistemas Operativos de tiempo compartido son Multics, OS/360 y DEC10. Caracteristicas de los Sistemas Operativos de tiempo compartido: Populares representantes de sistemas multiprogramados multiusuario, Ej.: sistemas de diseo asistido por computador, procesamiento de texto, etc. Dan la ilusin de que cada usuario tiene una mquina para s. Mayora utilizan algoritmo de reparto circular. Programas se ejecutan con prioridad rotatoria que se incrementa con la espera y disminuye despus de concedido el servicio. Evitan monopolizacin del sistema asignando tiempos de procesador (time slot). Gestin de memoria proporciona proteccin a programas residentes. Gestin de archivo debe proporcionar proteccin y control de acceso debido a que pueden existir mltiples usuarios accesando un mismo archivo.

16

1.4.5 Sistemas Operativos Distribuidos

Permiten distribuir trabajos, tareas o procesos, entre un conjunto de procesadores. Puede ser que este conjunto de procesadores est en un equipo o en diferentes, en este caso es transparente para el usuario. Existen dos esquemas bsicos de estos. Un sistema fuertemente acoplado esa es aquel que comparte la memoria y un reloj global, cuyos tiempos de acceso son similares para todos los procesadores. En un sistema dbilmente acoplado los procesadores no comparten ni memoria ni reloj, ya que cada uno cuenta con su memoria local. Los sistemas distribuidos deben de ser muy confiables, ya que si un componente del sistema se compone otro componente debe de ser capaz de reemplazarlo. Entre los diferentes Sistemas Operativos distribuidos que existen tenemos los siguientes: Sprite, Solaris-MC, Mach, Chorus, Spring, Amoeba, Taos, etc. Caracteristicas de los Sistemas Operativos distribuidos: Coleccion de sistemas autnomos capaces de comunicacin y cooperacin mediante interconexiones hardware y software. Gobierna operacion de un S.C. y proporciona abstraccion de mquina virtual a los usuarios. Objetivo clave es la transparencia. Generalmente proporcionan medios para la comparticin global de recursos. Servicios aadidos: denominacin global, sistemas de archivos distribuidos, facilidades para distribucin de calculos (a travs de comunicacin de procesos internados, llamadas a procedimientos remotos, etc.).

17

1.4.6 Sistemas Operativos de Red

Son aquellos sistemas que mantienen a dos o ms computadoras unidas a travs de algn medio de comunicacin (fsico o no), con el objetivo primordial de poder compartir los diferentes recursos y la informacin del sistema. El primer Sistema Operativo de red estaba enfocado a equipos con un procesador Motorola 68000, pasando posteriormente a procesadores Intel como Novell NetWare. Los Sistemas Operativos de red ms ampliamente usados son: Novell NetWare, Personal NetWare, LAN Manager, Windows NT Server, UNIX, LANtastic.

1.5 Estructura (Niveles o Estratos de Diseo)

El ncleo o kernel se divide en 5 capas o niveles: Nivel 1. Gestion de Memoria: Proporciona las facilidades de bajo nivel para la

18

gestion de memoria secundaria necesaria para la ejecucion de procesos. Nivel 2. Procesador: Se encarga de activar los cuantums de tiempo para cada uno de los procesos, creando interrupciones de hardware cuando no son respetadas. Nivel 3. Entrada/Salida: Proporciona las facilidades para poder utilizar los dispositivos de E/S requeridos por los procesos. Nivel 4. Informacin o Aplicacin o Intrprete de Lenguajes: Facilita la comunicacin con los lenguajes y el sistema operativo para aceptar las rdenes en cada una de las aplicaciones. Ejecutando un programa el software de este nivel crea el ambiente de trabajo e invoca a los procesos correspondientes. Nivel 5. Control de Archivos: Proporciona la facilidad para el almacenamiento a largo plazo y manipulacin de archivos con nombre, va asignando espacio y acceso de datos en memoria. El ncleo o kernel realiza diferentes funciones tales como: Manejo de interrupciones. Creacion y destruccion de procesos. Cambio de estado de los procesos. Despacho Suspension y reanudacin de procesos. Sincronizacin de procesos. Comunicacin entre procesos. Manipulacin de los bloques de control de procesos. Apoyo para las actividades de entrada/salida. Apoyo para asignacin y liberacin de memoria. Apoyo para el sistema de archivos. Apoyo para el mecanismo de llamada y retorno de un procedimiento. Apoyo para ciertas funciones de contabilidad del sistema.

El ncleo y los procesos Una definicin mas especifica de lo que es el ncleo (Kernel) de un sistema operativo es: un conjunto de rutinas cuya misin es la de gestionar el procesador, la memoria, la entrada/salida y el resto de procesos disponibles en la instalacin. Toda esta gestion la realiza para atender al funcionamiento y peticiones de los trabajos que se ejecutan en el sistema. El esquema general de la gestion del procesador, es el siguiente: Definicin y concepto de proceso. El Bloque de Control de Proceso (PCB) como imagen donde el sistema operativo ve el estado del proceso. Estados por los que pasa un proceso a lo largo de su existencia en la computadora. Operaciones que se pueden realizar sobre un proceso.

19

Clasificacin de los procesos segn su forma de ejecucion, de carga, etc. Por proceso debe entenderse: un programa en ejecucion junto con el entorno asociado (registros, variables, etc.).

1.6 Ncleo
El Kernel consiste en la parte principal del cdigo del sistema operativo, el cual se encargan de controlar y administrar los servicios y peticiones de recursos y de hardware con respecto a uno o varios procesos, en otras palabras, el kernel es el corazn del sistema operativo.

Cada sistema operativo tiene un tipo distinto de kernel: asi los Unix ms tradicionales como FreeBSD usan un kernel " monolitico" en el que esta todo compilado dentro, otros usan los llamados "microkernels" como el Darwin, Hurd e incluso Windows (krnl32.dll). GNU/Linux usa un kernel "modular" (vmlinuz); un nucleo bastante grande comparado con un microkernel, pero que es capaz de delegar funciones en los llamados " modulos" , partes independientes del nucleo que pueden ser incorporadas dinamicamente si hacen falta y luego descargadas si molestan. Asi se pueden cargar "drivers" para hardware, firewall o funciones especiales de red (ppp, rdsi, etc) cuando se necesiten y cuando por ejemplo, se cierre la conexion a internet, liberar la memoria que usaba ese modulo.

1.6.1 Interrupciones
Una interrupcin es un evento que altera la secuencia en que el procesador ejecuta las instrucciones. La interrupcin es generada por el hardware del sistema de cmputo. Cuando ocurre una interrupcin:

20

El sistema operativo toma el control (es decir, el hardware pasa el control al sistema operativo). El sistema operativo guarda el estado del proceso interrumpido. En muchos sistemas esta informacin se guarda en el bloque de control de proceso interrumpido. El sistema operativo analiza la interrupcin y transfiere el control a la rutina apropiada para atenderla; en muchos sistemas actuales el hardware se encarga de esto automticamente. La rutina del manejador de interrupciones procesa la interrupcin. Se restablece el estado del proceso interrumpido (o del siguiente proceso). Se ejecuta el proceso interrumpido (o el siguiente proceso).

Una interrupcin puede ser iniciada especficamente por un proceso en ejecucion (en cuyo caso se suele denominar trampa (trap), y se dice que esta sincronizada con la operacion del proceso) o puede ser causada por algn evento que puede estar relacionado o no con el proceso en ejecucion (en cuyo caso se dice que es asncrona con la operacion del proceso). Los sistemas orientados hacia las interrupciones pueden sobrecargarse. Si estas llegan con mucha frecuencia, el sistema no ser capaz de atenderlas. En algunos sistemas orientados hacia el teclado, cada tecla presionada almacena en la memoria un cdigo de un byte y genera un interrupcin para informar a la UCP que un carcter est listo para ser procesado. Si la UCP no puede procesar el dato antes de que se presione la siguiente tecla, se pierde el primer carcter.

1.6.2 Despachador
Su misin es asignar los procesadores centrales a los procesos. Es llamado cuando un proceso no puede seguir o puede emplearse mejor en otra parte. Se activa en las situaciones siguientes: Tras una interrupcin externa ha cambiado el estado de un proceso. Despus de que un extra cdigo provoque imposibilidad de seguir la ejecucion de un proceso. Tras una seal de error se ha suspendido el proceso hasta que no se haya tratado este.

Estas son causas especiales de interrupcin, esto es, todas ellas consisten en interrupciones que alteran el estado de algn proceso. El funcionamiento del dispatcher es el siguiente: 1. Es el proceso en curso el ms apropiado para ser ejecutado sobre este procesador? (por las razones que sean, prioridad, recursos, etc). Si es asi, devolver el control a la posicin de memoria sealada por el contador de programa (continuar).

21

En otro caso ir a 2. 2. Salvar el entorno voltil del proceso en curso. 3. 4. Sacar del registro del proceso aquel cuyo entorno voltil es el ms adecuado para ser ejecutado. Transferir el control a la posicin de memoria indicada por el contador de programa asociado al nuevo proceso.

Para determinar el proceso ms adecuado para ser ejecutado se ordenan los procesos ejecutables de acuerdo con algn criterio de prioridad. Las prioridades de los procesos vienen dadas y por tanto no son misin del dispatcher. Se utilizara una cola ordenada de modo que en cabeza de la cola este el proceso ms adecuado, asi la misin del dispatcher es la de ejecutar el primer proceso de la cola que no est siendo ejecutado. Se puede tener en lugar de una cola, ms de una. Por ejemplo tres. Una para aquellos procesos a los que se les permite dos segundos consecutivos de CPU. Otra para los que se les permiten 0,25 y otra para los que se les permite solo 0,02 segundos. Cada cola se sirve con el criterio de "el primero en llegar es el primero en ser servido". Las colas con menor tiempo tienen mayor prioridad. Los procesos se colocan inicialmente en la cola de menor tiempo. Si consume todo el tiempo asignado se transfiere a la siguiente cola en prioridad, asi sucesivamente. Se consigue asi que los procesos que consumen menos tiempo de procesador, reciban un proceso rpido, mientras que las tareas habituales uno ms largo.

1.6.3 Primitivas de Comunicacin

Los procesos que se ejecutan concurrentemente pueden ser procesos independientes o procesos cooperativos. Un proceso es independiente si no puede afectar o verse afectado por los restantes procesos que se ejecutan en el sistema. Cualquier proceso que no comparte datos con ningn otro proceso es un proceso independiente. Un proceso es cooperativo si puede afectar o verse afecta-do por los dems procesos que se ejecutan en el sistema. Evidentemente, cualquier proceso que comparte datos con otros procesos es un proceso cooperativo. Hay varias razones para proporcionar un entorno que permita la cooperacin entre procesos:

22

Compartir informacin. Dado que varios usuarios pueden estar interesados en la misma informacin (por ejemplo, un archivo compartido), debemos proporcionar un entorno que permita el acceso concurrente a dicha informacin. Acelerar los calculos. Si deseamos que una determinada tarea se ejecute rpidamente, debemos dividirla en subtareas, ejecutndose cada una de ellas en paralelo con las dems. Observe que tal aceleracin solo se puede conseguir si la computadora tiene mltiples ele-mentos de procesamiento, como por ejemplos varias CPU o varios canales de E/S. Modularidad. Podemos querer construir el sistema de forma modular, dividiendo las fun-ciones del sistema en diferentes procesos o hebras Conveniencia. Incluso un solo usuario puede querer trabajar en muchas tareas al mismo tiempo. Por ejemplo, un usuario puede estar editando, imprimiendo y compilando en paralelo. La cooperacin entre procesos requiere mecanismos de comunicacin interprocesos (IPC, interprocess communication) que les permitan intercambiar datos e informacin. Existen dos modelos fundamentales de comunicacin interprocesos: memoria compartida y paso de mensajes.

En el modelo de memoria compartida, se establece una regin de la memoria para que sea compartida por los procesos cooperativos. De este modo, los procesos pueden intercambiar informacin leyendo y escribiendo datos en la zona compartida.

UNIDAD 2 Administrador de Procesos y del Procesador

2.1 Concepto de Proceso
Todos los programas cuya ejecucion solicitan los usuarios, se ejecutan en forma de procesos, de ah la importancia para el informtico de conocerlos en detalle. El proceso

23

se puede definir como un programa de gestion por el sistema operativo. Durante su eleccin el proceso va modificando en ejecucion y, de una forma un poco ms precisa, como la unidad de procesamiento el registro del modelo de programacin de la computadora, de acuerdo a las intrusiones de mquina involucradas. El sistema operativo mantiene por cada proceso una serie de estructuras de informacin que permiten identificar las caracteristicas de este, asi como los recursos que tiene asignados. En esta ltima categora entran los descriptores de los segmentos de memoria asignados, los descriptores de los archivos abiertos, los descriptores de los puertos de comunicaciones, etc. Una parte muy importante de esta informacin se encuentra normalmente como en el llamado bloque de control de procesos (BCP). El sistema operativo mantiene una tabla de procesos con todos los BCP de los procesos. Por razones de eficiencia, la tabla de procesos se construye normalmente como una estructura esttica, que tiene un determinado nmero de BCP, todos ellos del mismo tamao. La informacin que compone un proceso es la siguiente: Contenido de los segmentos de memoria en los que residen el cdigo y los datos del proceso. A esta informacin se le denomina imagen de memoria o core image. Contenido de los registros del modelo de programacin Contenido del BCP.

2.2 Estados y Transiciones del Proceso

Como se indic anteriormente, el proceso es la unidad de procesamiento gestionada por el sistema operativo. Para poder realizar este cometido, el proceso tiene asociado una serie de elementos de informacin, que se resumen en la Figura 3.8, que se analizan seguidamente. Estos elementos se organizan en tres grupos: estado del procesador, imagen de memoria y tablas del sistema operativo. Estado del procesador El estado del procesador est formado por el contenido de todos sus registros, que se enumeran seguidamente: Registros generales. De existir registros especficos de coma flotante tambin se incluyen aqu. Contador de programa.

24

Informacin del proceso Puntero de pila. Registro o registros de estado. Registros especiales. Como puede ser el RIED (registro identificador de espacio de direccionamiento).

El estado del procesador de un proceso reside en los registros del procesador, cuando el proceso est en ejecucion, o en el bloque de control de proceso (BCP), cuando el proceso no est en ejecucion. Cuando el proceso est ejecutando, el estado del procesador vara de acuerdo al flujo de instrucciones mquina ejecutado. En este caso, la copia del estado del procesador que reside en el BCP no est actualizada. Tngase en cuenta que los registros de la mquina se utilizan para no tener que acceder a la informacin de memoria, dado que es mucho ms lenta. Por tanto, no tiene sentido plantear que, en cada modificacin de un registro, se actualice su valor en el BCP, puesto que est en memoria. Sin embargo, cuando se detiene la ejecucion de un proceso, como consecuencia de la ejecucion de una interrupcin, es muy importante que el sistema operativo actualice la copia del estado del procesador en su BCP. En trminos concretos, la rutina del sistema operativo que trata las Interrupciones lo primero que ha de hacer es salvar el estado del procesador en el BCP del proceso interrumpido.

2.3 Procesos Ligeros (Hilos o Hebras)

Un proceso ligero, o thread, es un programa en ejecucion (flujo de ejecucion) que comparte la imagen de memoria y otras informaciones con otros procesos ligeros. Como muestra la Figura, un proceso puede contener un solo flujo de ejecucion, como ocurre en los procesos clsicos, o ms de un flujo de ejecucion (procesos ligeros).

25

Desde el punto de vista de la programacin, un proceso ligero se define como una funcin cuya ejecucion se puede lanzar en paralelo con otras. El hilo de ejecucion primario, o proceso ligero primario, corresponde a la funcin main. Cada proceso ligero tiene informaciones que le son propias y que no comparte con otros procesos ligeros. Las informaciones propias se refieren fundamentalmente al contexto de ejecucion, pudindose destacar las siguientes: Contador de programa. Pila. Registros. Estado del proceso ligero (ejecutando, listo o bloqueado). Todos los procesos ligeros de un mismo proceso comparten la informacin del mismo. En concreto, comparten: Espacio de memoria. Variables globales. Archivos abiertos. Procesos hijos. Temporizadores. Seales y semforos. Contabilidad.

Es importante destacar que todos los procesos ligeros de un mismo proceso comparten el mismo espacio de direcciones de memoria, que incluye el cdigo, los datos y las pilas de los diferentes procesos ligeros. Esto hace que no exista proteccin de memoria entre los procesos ligeros de un mismo proceso, algo que si ocurre con los procesos convencionales. El proceso ligero constituye la unidad ejecutable en Windows NT. La Figura representa de forma esquemtica la estructura de un proceso de Windows NT con sus procesos ligeros.

Fig. Proceso ligero

26

2.4 Concurrencia y Secuencialidad

Los procesos son concurrentes si existen simultneamente. Los procesos concurrentes pueden funcionar en forma totalmente independiente unos de otros, o pueden ser asncronos, lo cual significa que en ocasiones requieren cierta sincronizacin o cooperacin.

Cuando dos o ms procesos llegan al mismo tiempo a ejecutarse, se dice que se ha presentado una concurrencia de procesos. Es importante mencionar que para que dos o ms procesos sean concurrentes, es necesario que tengan alguna relacin entre ellos como puede ser la cooperacin para un determinado trabajo o el uso de informacin o recursos compartidos, por ejemplo: en un sistema de un procesador, la multiprogramacion es una condicin necesaria pero no suficiente para que exista concurrencia, ya que los procesos pueden ejecutarse de forma totalmente independiente. Por otro lado en un sistema de varios procesos se puede presentar la concurrencia siempre y cuando las actividades necesiten actuar entre si ya sea para utilizar informacin en comn o para cualquier otra cosa. Existen tres formas modelos de computadora en los que se puede pueden ejecutar procesos concurrentes: Multiprogramacion con un nico procesador. En este modelo todos los procesos concurrentes ejecutan sobre un nico procesador. El sistema operativo se encarga de ir repartiendo el tiempo del procesador entre los distintos procesos, intercalando la ejecucion de los mismos para dar asi una apariencia de ejecucion simultnea.
27

Multiprocesador. Un multiprocesador es una mquina formada por un conjunto de procesadores que comparten memoria principal. En este tipo de arquitecturas, los procesos concurrentes no solo pueden intercalar su ejecucion sino tambin superponerla. En este caso si existe una verdadera ejecucion simultanea de procesos, al coincidir las fases de procesamiento de distintos procesos. En un instante dado se pueden ejecutar de forma simultanea tantos procesos como procesadores haya. Multicomputadora. Una multicomputadora es una mquina de memoria distribuida, en contraposicin con el multiprocesador que es de memoria compartida. Est formada por una serie de computadoras completas con su UCP, memoria principal y, en su caso, periferia. Cada uno de estos procesadores completo se denomina nodo. Los nodos se encuentran conectados y se comunican entre s a travs de una red de interconexin, empleando el mtodo de paso de mensajes. En este tipo de arquitecturas tambin es posible la ejecucion simultnea de los procesos sobre los distintos procesadores. En general la concurrencia ser aparente siempre que el nmero de procesos sea mayor que el de procesadores disponibles, es decir, cuando haya ms de un proceso por procesador. La concurrencia ser real cuando haya un proceso por procesador

2.4.1 Exclusin Mutua de Seccin Critica

El mtodo ms sencillo de comunicacin entre los procesos de un programa concurrente es el uso comn de unas variables de datos. Esta forma tan sencilla de comunicacin puede llevar, no obstante, a errores en el programa ya que el acceso concurrente puede hacer que la accin de un proceso interfiera en las acciones de otro de una forma no adecuada. Aunque nos vamos a fijar en variables de datos, todo lo que sigue seria valido con cualquier otro recurso del sistema que solo pueda ser utilizado por un proceso a la vez. Por ejemplo una variable x compartida entre dos procesos A y B que pueden incrementar o decrementar la variable dependiendo de un determinado suceso. Esta situacin se plantea, por ejemplo, en un problema tpico de la programacin concurrente conocido como el Problema de los Jardines. En este problema se supone que se desea controlar el nmero de visitantes a unos jardines. La entrada y la salida a los jardines se pueden realizar por dos puntos que disponen de puertas giratorias. Se desea poder conocer en cualquier momento el nmero de visitantes a los jardines, por lo que se dispone de un computador con conexion en cada uno de los dos puntos de entrada que le informan cada vez que se produce una entrada o una salida.

28

Asociamos el proceso P1 a un punto de entrada y el proceso P2 al otro punto de entrada. Ambos procesos se ejecutan de forma concurrente y utilizan una nica variable x para llevar la cuenta del nmero de visitantes. El incremento o decremento de la variable se produce cada vez que un visitante entra o sale por una de las puertas. Asi, la entrada de un visitante por una de las puertas hace que se ejecute la instruccin x:=x+1 Mientras que la salida de un visitante hace que se ejecute la instruccin x:=x-1 Si ambas instrucciones se realizaran como una nica instruccin hardware, no se planteara ningn problema y el programa podra funcionar siempre correctamente. Esto es asi porque en un sistema con un nico procesador solo se puede realizar una instruccin cada vez y en un sistema multiprocesador se arbitran mecanismos que impiden que varios procesadores accedan a la vez a una misma posicin de memoria. El resultado sera que el incremento o decremento de la variable se producira de forma secuencial pero sin interferencia de un proceso en la accin del otro. Sin embargo, si se produce interferencia de un proceso en el otro si la actualizacin de la variable se realiza mediante la ejecucion de otras instrucciones ms sencillas, como son las usuales de:

copiar el valor de x en un registro del procesador incrementar el valor del registro almacenar el resultado en la direccin donde se guarda x

Aunque el proceso P1 y el P2 se suponen ejecutados en distintos procesadores (lo que no tiene por qu ser cierto en la realidad) ambos usan la misma posicin de memoria para guardar el valor de x. Se puede dar la situacin de que el planificador de procesos permita el entrelazado de las operaciones elementales anteriores de cada uno de los procesos, lo que inevitablemente producir errores. Si, por ejemplo, se produce el siguiente orden de operaciones:

P1 carga el valor de x en un registro de su procesador P2 carga el valor de x en un registro de su procesador P2 incrementa el valor de su registro P1 incrementa el valor de su registro P1 almacena el valor de su registro en la direccin de memoria de x
29

P2 almacena el valor de su registro en la direccin de memoria de x se perder un incremento de la variable x.

Este tipo de errores son muy difciles de detectar mediante test del programa ya que el que se produzcan depende de la temporizacin de dos procesos independientes. El ejemplo muestra de forma clara la necesidad de sincronizar la actuacin de ambos procesos de forma que no se produzcan interferencias entre ellos. Para evitar este tipo de errores se pueden identificar aquellas regiones de los procesos que acceden a variables compartidas y dotarlas de la posibilidad de ejecucion como si fueran una nica instruccin. Se denomina Seccin Critica a aquellas partes de los procesos concurrentes que no pueden ejecutarse de forma concurrente o, tambin, que desde otro proceso se ven como si fueran una nica instruccin. Esto quiere decir que si un proceso entra a ejecutar una seccin crtica en la que se accede a unas variables compartidas, entonces otro proceso no puede entrar a ejecutar una regin critica en la que acceda a variables compartidas con el anterior. Las secciones crticas se pueden agrupar en clases, siendo mutuamente exclusivas las secciones criticas de cada clase. Para conseguir dicha exclusin se deben implementar protocolos software que impidan o bloqueen (lock) el acceso a una seccion critica mientras est siendo utilizada por un proceso. Requisitos para la exclusin mutua 1. Solo un proceso, de todos los que poseen secciones crticas por el mismo recurso compartido, debe tener permiso para entrar en ella en un momento dado. Un proceso que se interrumpe en una seccion no crtica debe hacerlo sin interferir con los otros procesos. Un proceso no debe poder solicitar acceso a una seccion crtica para despus ser demorado indefinidamente, no puede permitirse el interbloqueo o la inanicin. Si ningn proceso est en su seccion critica, cualquier proceso que solicite entrar en la suya debe poder hacerlo sin demora. No se debe suponer sobre la velocidad relativa de los procesos o el nmero de procesadores. Un proceso permanece en su seccion crtica por un tiempo finito.

2. 3.

4. 5. 6.

30

Una manera de satisfacer los requisitos de exclusin mutua es dejar la responsabilidad a los procesos que deseen ejecutar concurrentemente. Tanto si son programas del sistema como de aplicacin, los procesos deben coordinarse unos con otros para cumplir la exclusin mutua, sin ayuda del lenguaje de programacin o del sistema operativo. Estos mtodos se conocen como soluciones por software.

2.4.2 Sincronizacin de Procesos S.C

En muchos casos, los procesos se renen para realizar tareas en conjunto, a este tipo de relacin se le llama procesos cooperativos. Para lograr la comunicacin, los procesos deben sincronizarse, de no ser asi pueden ocurrir problemas no deseados. La sincronizacin es la transmisin y recepcin de seales que tiene por objeto llevar a cabo el trabajo de un grupo de procesos cooperativos. Es la coordinacin y cooperacin de un conjunto de procesos para asegurar la comparacin de recursos de cmputo. La sincronizacin entre procesos es necesaria para prevenir y/o corregir errores de sincronizacin debidos al acceso concurrente a recursos compartidos, tales como estructuras de datos o dispositivos de E/S, de procesos contendientes. La sincronizacin entre procesos tambin permite intercambiar seales de tiempo (ARRANQUE/PARADA) entre procesos cooperantes para garantizar las relaciones especficas de precedencia impuestas por el problema que se resuelve. Sin una sincronizacin adecuada entre procesos, la actualizacin de variables compartidas puede inducir a errores de tiempo relacionados con la concurrencia que son con frecuencia difciles de depurar. Una de las causas principales de este problema es que procesos concurrentes puedan observar valores temporalmente inconsistentes de una variable compartida mientras se actualizan. Una aproximacin para resolver este problema es realizar actualizaciones de variables compartidas de manera mutuamente exclusiva. Se pueden mejorar permitiendo que a lo ms un proceso entre a la vez en la seccion crtica de cdigo en la que se actualiza una variable compartida o estructura de datos en particular. Para que los procesos puedan sincronizarse es necesario disponer de servicios que permitan bloquear o suspender bajo determinadas circunstancias la ejecucion de un proceso. Los principales mecanismos de sincronizacin que ofrecen los sistemas operativos son:

Seales Tuberas Semforos Mutex y variables condicionales Paso de mensajes

31

2.4.2.1 Mecanismo de Semforos

Las diversas soluciones hardware al problema de la seccion critica, basadas en las instrucciones TestAndSet () y Swap (), son complicadas de utilizar por los programadores de aplicaciones. Para superar esta dificultad, podemos usar una herramienta de sincronizacin denominada semforo. Un semforo S es una variable entera a la que, dejando aparte la inicializacin, solo se accede mediante dos operaciones atomicas estandar: wait () y signal (). Originalmente, la operacion wait () se denominaba P (del termino holandes proberen, probar); mientras que signal( ) denominaba originalmente V (verhogen, incrementar). La definicion de wait () es la que sigue: wait (S) { while S <= 0 ;??? // no-op S--; } La definicion de signal () es: signal(S) { S++; } Todas las modificaciones del valor entero del semforo en las operaciones wait () y signal () deben ejecutarse de forma indivisible. Es decir, cuando un proceso modifica el valor del semforo, ningn otro proceso puede modificar simultneamente el valor de dicho semforo. Adems, en el caso de wait(), la prueba del valor entero de S (S <- 0), y su posible modificacin (S - -) tambin se deben ejecutar sin interrupcin. Utilizacin Los sistemas operativos diferencian a menudo entre semforos contadores y semforos binarios. El valor de un semforo contador puede variar en un dominio no restringido, mientras que el valor de un semforo binario solo puede ser 0 01. En algunos sistemas, los semforos binarios se conocen como cerrojos mutex, ya que son cerrojos que proporcionan exclusin mutua. Podemos usar semaforos binarios para abordar el problema de la seccion crtica en el caso de multiples procesos. Los n procesos comparten un semaforo, mutex, inicializado con el valor 1. Cada proceso P; se organiza como se muestra en la Figura 6.9. Los semaforos contadores se pueden usar para controlar el acceso a un determinado recurso formado por un nmero finito de instancias. El semaforo se inicializa con el nmero de recursos disponibles. Cada proceso que desee usar un recurso ejecuta una

32

operacion wait () en el semaforo (decrementando la cuenta). Cuando un proceso libera un recurso, ejecuta una operacion signal()(incrementando la cuenta). Cuando la cuenta del semaforo llega a 0, todos los recursos estarn en uso. Despus, los procesos que deseen usar un recurso se bloquearan hasta que la cuenta sea mayor que 0. Tambin podemos usar los semaforos para resolver diversos problemas de sincronizacin. Por ejemplo, considere dos procesos que se estn ejecutando de forma concurrente: P1 con una instruccin S1 y P2 con una instruccin S2. Suponga que necesitamos que S2 se ejecute solo despus de que Sl se haya completado. Podemos implementar este esquema dejando que P1 Y P2 compartan un semaforo comn synch, inicializado con el valor 0, e insertando las instrucciones: s1; signal(synch); en el wait(synch); S2;

proceso

P1,

las

instrucciones

en el proceso P2. Dado que synch se inicializa con el valor 0, P2 ejecutara S2 solo despues de que P1 haya invocado signal ( synch), instruccion que sigue a la ejecucion de S1. do waiting(mutex); ???????????? // seccion critica signal(mutex); ??????????? // Seccion restante }while (TRUE); ??? Implementacin La principal desventaja de la definicion de semaforo dada aqui es que requiere una espera activa. Mientras un proceso est en su seccion crtica, cualquier otro proceso que intente entrar en su seccion critica debe ejecutar continuamente un bucle en el cdigo de entrada. Este bucle continuo plantea claramente un problema en un sistema real de multiprogramacion, donde una sola CPU se comparte entre muchos procesos. La espera activa desperdicia ciclos de CPU que algunos otros procesos podran usar de forma productiva. Este tipo de semaforo tambin se denomina cerrojo mediante bucle sin fin (spinlock), ya que el proceso "permanece en un bucle sin fin" en espera de adquirir el cerrojo. (Los cerrojos mediante bucle sin fin tienen una ventaja y es que no requieren ningn cambio de contexto cuando un proceso tiene que esperar para adquirir un cerrojo. Los cambios de contexto pueden llevar un tiempo considerable. Por tanto, cuando se espera que lo-s cerrojos se mantengan durante un periodo de tiempo corto, los cerrojos mediante bucle sin fin pueden resultar tiles; por eso se emplean a menudo en los

33

sistemas multiprocesador, donde una hebra puede "ejecutar un bucle" sobre un procesador mientras otra hebra ejecuta su seccion critica en otro procesador). Para salvar la necesidad de la espera activa, podemos modificar la definicion de las operaciones de semaforo wa i t () y s i gna 1(). Cuando un proceso ejecuta la operacion wa i t () y determina que el valor del semaforo no es positivo, tiene que esperar. Sin embargo, en lugar de entrar en una espera activa, el proceso puede bloquearse a si mismo. La operacion de bloqueo coloca al proceso en una cola de espera asociada con el semaforo y el estado del proceso pasa al estado de espera. A continuacin, el control se transfiere al planificador de la CPU, que selecciona otro proceso para su ejecucion. Un proceso bloqueado, que est esperando en un semaforo S, debe reiniciarse cuando algn otro proceso ejecuta una operacion signal (). El proceso se reinicia mediante una operacion wakeup () , que cambia al proceso del estado de espera al estado de preparado. El proceso se coloca en la cola de procesos preparados. (La CPU puede o no conmutar del proceso en ejecucion al proceso que se acaba de pasar al estado de preparado, dependiendo del algoritmo de planificacin de la CPU.) Para implementar semaforos usando esta definicion, definimos un semaforo como una estructura "C": typedef struct { int value; struct process *list; }semaphore; Cada semaforo tiene un valor (value) entero y una lista de procesos list. Cuando un proce so tiene que esperar en un semaforo, se anade a la lista de procesos. Una operacion signa1 () elimina un proceso de la lista de procesos en espera y lo despierta. La operacion de semaforo wait () ahora se puede definir del siguiente modo: wait(semaphore *S) { S->value--; if (S->value < 0) { anadir este proceso a S->list; block(); } } La operacion de semaforo signal () ahora puede definirse asi: signal(semaphore S->value++;} if (S->value eliminar un *S) <= proceso P 0) de { { S->list;

34

wakeup(P); } } La operacion block () suspende al proceso que la ha invocado. La operacion wakeup () reanuda la ejecucion de un proceso bloqueado P. Estas dos operaciones las proporciona el sistema operativo como llamadas al sistema basicas. Observe que, aunque bajo la definicion clsica de semaforos con espera activa, el valor del semaforo nunca es negativo, esta implementacin s que puede tener valores negativos de semaforo. Si el valor del semaforo es negativo, su mdulo es el nmero de procesos en espera en dicho semaforo. Este hecho resulta de conmutar el orden de las operaciones de decremento y de prueba en la implementacin de la operacion wait (). La lista de procesos en espera puede implementarse fcilmente mediante un campo de enlace en cada bloque de control de proceso (PCB). Cada semaforo contiene un valor entero y un puntero a la lista de bloques PCB. Una forma de anadir y eliminar procesos de la lista de manera que se garantice un tiempo de espera limitado consiste en usar una cola FIFO, donde el semaforo contenga punteros a ambos extremos de la cola. Sin embargo, en general, la lista puede utilizar cualquier estrategia de gestion de la cola. El uso correcto de los semaforos no depende de la estrategia concreta de gestion de la cola que se emplee para las listas de los semaforos. El aspecto critico de los semaforos es que se deben ejecutar atmicamente: tenemos que garantizar que dos procesos no puedan ejecutar al mismo tiempo sendas operaciones waitO y signal () sobre el mismo semaforo. Se trata de un problema de seccion crtica. En un entorno de un solo procesador (es decir, en el que solo exista una CPU), podemos solucionar el problema de forma sencilla inhibiendo las interrupciones durante el tiempo en que se ejecutan las operaciones wait () y signal (). Este esquema funciona adecuadamente en un entorno de un solo procesador porque, una vez que se inhiben las interrupciones, las instrucciones de los diferentes procesos no pueden intercalarse: solo se ejecuta el proceso actual hasta que se reactivan las interrupciones y el planificador puede tomar de nuevo el control. En un entorno multiprocesador, hay que deshabilitar las interrupciones en cada procesador; si no se hace asi, las instrucciones de los diferentes procesos (que estn ejecutndose sobre diferentes procesadores) pueden intercalarse de forma arbitraria. Deshabilitar las interrupciones en todos los procesadores puede ser una tarea compleja y, adems, puede disminuir seriamente el rendimiento. Por tanto, los sistemas SMP deben proporcionar tecnicas alternativas de bloqueo, como por ejemplo cerrojos mediante bucle sin fin, para asegurar que las operaciones wait () y signa l () se ejecuten atmicamente. Es importante recalcar que no hemos eliminado por completo la espera activa con esta definicion de las operaciones wait () y signal (); en lugar de ello, hemos eliminado la

35

espera activa de la seccion de entrada y la hemos llevado a las secciones crticas de los programas de aplicacin. Adems, hemos limitado la espera activa a las secciones crticas de las operaciones wait() y signal (), y estas secciones son cortas (si se codifican apropiadamente, no deberan tener ms de unas diez instrucciones). Por tanto, la seccion critica casi nunca est ocupada y raras veces se produce este tipo de espera; y, si se produce, solo dura un tiempo corto. En los programas de aplicacin, la situacin es completamente diferente, porque sus secciones criticas pueden ser largas (minutos o incluso horas) o pueden estar casi siempre ocupadas. En tales casos, la espera activa resulta extremadamente ineficiente. Interbloqueos e inanicin La implementacin de un semaforo con una cola de espera puede dar lugar a una situacin en la que dos o ms procesos estn esperando indefinidamente a que se produzca un suceso que solo puede producirse como consecuencia de las operaciones efectuadas por otro de los procesos en espera. El suceso en cuestin es la ejecucion de una operacion signal (). Cuando se llega a un estado asi, se dice que estos procesos se han interbloqueado. Para ilustrar el concepto, consideremos un sistema que consta de dos procesos, Po y Pl, con acceso cada uno de ellos a dos semaforos, S y Q, configurados con el valor 1: Po wait wait signal signal (Q)?????? signal (S); ?????????????????? (S)?????????? ?wait (Q)?????????? wait (S)?????? signal Pi (Q); (S); (Q);

Suponga que Po ejecuta wait(S) y luego P1 ejecuta wait(Q). Cuando Po ejecuta wait(Q), debe esperar hasta que P1 ejecute signal (Q). De forma similar, cuando P1 ejecuta wait (S), tiene que esperar hasta que Po ejecute signal(S). Dado que estas operaciones signal() no pueden ejecutarse, Po y Pl se interbloquean. Decimos que un conjunto de procesos est en un estado de interbloqueo cuando todos los procesos del conjunto estn esperando un suceso que solo puede producirse como consecuencia de las acciones de otro proceso del conjunto. Los sucesos que ms nos interesan aqui son los de adquisicin y liberacin de recursos, pero tambin hay otros tipos de sucesos que pueden dar lugar a interbloqueos, como veremos en el Captulo 7. En ese captulo describiremos varios mecanismos para tratar los problemas de interbloqueo. Otro problema relacionado con los interbloqueos es el del bloqueo indefinido o muerte por inanicin, una situacin en la que algunos procesos esperan de forma indefinida dentro del semaforo. El bloqueo indefinido puede producirse si aadimos y eliminamos

36

los procesos a la lista asociada con el semaforo utilizando un esquema LIFO (last-in, first-out).

2.4.2.2 Mecanismos de Monitoreo

Aunque los semaforos proporcionan un mecanismo adecuado y efectivo para el proceso de sin-cronizacion, un uso incorrecto de los mismos puede dar lugar a errores de temporizacion que son dificiles de detectar, dado que estos errores solo ocurren si tienen lugar algunas secuencias de eje-cucion concretas y estas secuencias no siempre se producen.

Hemos visto un ejemplo de dichos errores en el uso de contadores en la solucion del problema productor-consumidor (Seccion 6.1). En ese ejemplo, el problema de temporizacion se producia raras veces, e incluso entonces el valor del contador parecia ser razonable: lo que pasaba es que diferia en 1 del valor correcto. Pero aunque el valor pareciera correcto, no era aceptable y es por esta razon que se introdujeron los semaforos. Lamentablemente, estos errores de temporizacion pueden producirse tambien cuando se emplean semaforos. Para ilustrar como, revisemos la solucion con semaforos para el problema de la seccion critica. Todos los procesos comparten una variable de semaforo mutex, que se iniciali-za con el valor 1. Cada proceso debe ejecutar una operacion wait (mutex) antes de entrar en la seccion critica y una operacion signal (mutex) despues de la misma. Si esta secuencia no se lleva a cabo, dos procesos podrian estar dentro de sus secciones criticas al mismo tiempo. Examinemos los problemas a los que esto da lugar. Observe que estos problemas surgiran inclu-so aunque solo sea un unico proceso el que no se comporte de la forma adecuada; dicha situacion puede deberse a un error de programacion no intencionado o a que un cierto programador no tenga muchas ganas de cooperar. Suponga que un proceso intercambia el ordenen el que se ejecutan las operaciones wait() y signal (), dando lugar a la siguiente secuencia de ejecucion: signal(mutex); seccion wait(mutex); critica

En esta situacion, varios procesos pueden estar ejecutando sus secciones criticas simultane-amente, violando el requisito de exclusion mutua. Observe que este error solo puede des-cubrirse si varios procesos estan activos simultaneamente en sus secciones criticas y que esta situacion no siempre se produce. ???? Suponga que un proceso reemplaza signal(mutex) por wait(mutex). Es decir, ejecuta

37

wait(mutex); seccion critica wait(mutex); En este caso, se producira un interbloqueo.

Suponga que un proceso omite la operacion wait( mutex ), la operacion signal (mutex) , o ambas. En este caso, se violara la exclusion mutua o se producira un interbloqueo.

Estos ejemplos ilustran los distintos tipos de error que se pueden generar facilmente cuando los programadores emplean incorrectamente los semaforos para solucionar el problema de la seccion critica.. Para abordar tales errores, los investigadores han desarrollado estructuras de lenguaje de alto nivel. En esta seccion, vamos a describir una estructura fundamental de sincronizacion de alto nivel, el tipo monitor. Utilizacion Un tipo, o un tipo abstracto de datos, agrupa una serie de datos privados con un conjunto de metodos publicos que se utilizan para operar sobre dichos datos. Un tipo monitor tiene un con-junto de operaciones definidas por el programador que gozan de la caracteristica de exclusion mutua dentro del monitor. El tipo monitor tambien contiene la declaracion de una serie de variables cuyos valores definen el estado de una instancia de dicho tipo, junto con los cuerpos de los procedimientos o funciones que operan sobre dichas variables. En la Figura 6.16 se muestra la sin-taxis de un monitor. La representacion de un tipo monitor no puede ser utilizada directamente por los diversos procesos. Asi, un procedimiento definido dentro de un monitor solo puede acceder a las variables declaradas localmente dentro del monitor y a sus parametros formales. De forma similar, a las variables locales de un monitor solo pueden acceder los procedimientos locales. La estructura del monitor asegura que solo un proceso este activo cada vez dentro del monitor. En consecuencia, el programador no tiene que codificar explicitamente esta restriccion de sincronizacion. Sin embargo, la estructura de monitor, como se ha definido hasta ahora, no es lo suficientemente potente como para modelar algunos esquemas de sincronizacion. Para ello, necesitamos definir mecanismos de sincronizacion adicionales. Estos mecanismos los proporciona la estructura condition. Un programador que necesite escribir un esquema de sincronizacion a medida puede definir una o mas variables de tipo condition: condition x, y; Las unicas operaciones que se pueden invocar en una variable de condicion son wait () y signal () . La operacion x.wait();

38

indica que el proceso que invoca esta operacion queda suspendido hasta que otro proceso invo-que la operacion x.signal(); La operacion x.signal() hace que se reanude exactamente uno de los procesos suspendidos. Si no habia ningun proceso suspendido, entonces la operacion signal () no tiene efecto, es decir, el estado de x sera el mismo que si la operacion nunca se hubiera ejecutado Compare esta operacion con la operacion signal () asociada con los semaforos, que siempre afectaba al estado del semaforo. Suponga ahora que, cuando un proceso invoca la operacion x. signal(), hay un proceso en estado suspendido asociado con la condicion x. Evidentemente, si se permite al proceso sus-pendido Q reanudar su ejecucion, el proceso P que ha efectuado la senalizacion debera esperar; en caso contrario, P y Q se activarian simultaneamente dentro del monitor. Sin embargo, observe que conceptualmente ambos procesos pueden continuar con su ejecucion. Existen dos posibilidades: 1. Senalizar y esperar. P espera hasta que Q salga del monitor o espere a que se produzca otra condicion. 2. Senalizar y continuar. Q espera hasta que P salga del monitor o espere a que se produzca otra condicion. Hay argumentos razonables en favor de adoptar cualquiera de estas opciones. Por un lado, puesto que P ya estaba ejecutandose en el monitor, el metodo de senalizar y continuar parece el mas razonable. Por otro lado, si permitimos que la hebra P continue, para cuando se reanude la ejecu-cion de Q, es posible que ya no se cumpla la condicion logica por la que Q estaba esperando. En el lenguaje Pascal Concurrente se adopto un compromiso entre estas dos opciones: cuando la hebra P ejecuta la operacion signal, sale inmediatamente del monitor. Por tanto, la ejecucion de Q se reanuda de forma inmediata. monitor nombre del monitor // declaraciones de variables compartidas procedimiento P1 ( )?????????????????????????????????????????????????????????? { } procedimiento P2 (??????????????? . . )???????? { } procedimiento Pn ( .????????????????????? )????? { } codigo } } de inicializacion ( .???? )?????????? { . . { .

39

2.4.3 Interbloqueo (DeadLock)

El estancamiento se puede definir formalmente como sigue: "Un conjunto de procesos se estancan si cada proceso del conjunto esta esperando un evento que solo otro proceso del conjunto puede provocar". Puesto que todos los procesos estan en espera, ninguno de ellos podra ocasionar nuca ninguno de los eventos que podrian desbloquear a algunos de los otros miembros del conjunto y todos los procesos seguiran esperando indefinidamente. Definicion de Abrazo Mortal Un conjunto de procesos esta en un abrazo mortal cuando todos los procesos en ese conjunto estan esperando un evento que solo puede ser causado por otro proceso en el conjunto. Los eventos a los cuales nos estamos refiriendo son concernientes con la asignacion y liberacion de recursos principalmente. Sin embargo, otro tipo de eventos pueden llevar a la existencia de abrazos mortales. Para ejemplificar un estado de abrazo mortal, considere un sistema con tres unidades de disco. Suponga que existen tres procesos, cada uno de ellos tiene asignada una de las unidades de disco. Si ahora cada proceso pide otra unidad de disco, los tres procesos se encuentran ahora en un estado de abrazo mortal. Cada uno esta esperando el evento "unidad de disco liberada", lo cual solo puede ser causada por alguno de los otros procesos en espera. Este ejemplo ilustra un abrazo mortal involucrando procesos compitiendo por el mismo tipo de recurso. Los abrazos mortales pueden tambien involucrar diferentes tipos de recursos. Por ejemplo, considere un sistema con una impresora y una unidad de disco. Suponga que el proceso A tiene asignada la unidad de disco y que el proceso B tiene asignada la impresora. Ahora, si A pide la impresora y B pide la unidad de disco, ocurre un abrazo mortal.

Ejemplo de un abrazo mortal.

40

Debe ser obvio que un abrazo mortal es una condicion indeseable. En un abrazo mortal, los procesos nunca terminan de ejecutarse y los recursos del sistema esta amarrados, evitando que otros procesos puedan siquiera empezar.? Antes de discutir varios metodos para manejar el problema de los abrazos mortales, seria util describir algunas de las propiedades que los caracterizan. Condiciones Necesarias Segun Coffman (1971), existen cuatro condiciones que deben cumplirse para que haya estancamiento. Una situacion de abrazo mortal puede surgir si y solo si las siguientes cuatro condiciones ocurren simultaneamente en un sistema: 1. Exclusion Mutua. Cada recurso se asigna por lo regular exactamente a un proceso o bien esta disponible. Al menos un recurso es mantenido en un modo no-compartible; esto es, solo un proceso a la vez puede usar el recurso. Si otro proceso solicita ese recurso, tiene que ser retardado hasta que el recurso haya sido liberado. Retener y Esperar. Los procesos que regularmente contienen recursos otorgados antes pueden solicitar nuevos recursos. Debe existir un proceso que retenga al menos un recurso y este esperando para adquirir recursos adicionales que estan siendo retenidos por otros procesos. No existe el derecho de desasignar (No preemtion). Los recursos previamente otorgados no pueden extraerse por la fuerza de un proceso. Deben ser liberados explicitamente por el proceso que los contiene. Los recursos no pueden ser desasignados (preempted); esto es, un recurso solo puede ser liberado voluntariamente por el proceso que lo retiene, despues de que el proceso ha terminado su tarea. Espera Circular . Debe haber una cadena de dos o mas procesos, cada uno d los cuales este esperando u recurso contenido en el siguiente miembro de la cadena. Debe existir un conjunto {p0, p1, ...,pn} de procesos en espera tal que p0 este esperando por un recurso que esta siendo retenido por p1, p1 esta esperando por un recurso que esta siendo retenido por p2, ..., pn-1 esta esperando por un recurso que esta siendo retenido por pn y pn esta esperando por un recurso que esta siendo retenido por p0.

2.

3.

4.

Enfatizamos que las cuatro condiciones deben de cumplirse para que pueda ocurrir un abrazo mortal. La condicion de espera circular implica la condicion de retener y esperar, de tal manera que las cuatro condiciones no son totalmente independientes. Sin embargo, puede ser util el considerar cada condicion por separado. Una forma de modelar estas condiciones es usando un grafo de recursos: los circulos representan procesos, los cuadrados recursos. Una arista desde un recurso a un proceso indica que el recurso ha sido asignado al proceso. Una arista desde un

41

proceso a un recurso indica que el proceso ha solicitado el recurso, y esta bloqueado esperandolo. Entonces, si hacemos el grafo con todos lo procesos y todos los recursos del sistema y encontramos un ciclo, los procesos en el ciclo estan bajo bloqueo mutuo.

Ejemplo de un grafo de recursos.

Metodos para manejar los abrazos mortales Principalmente, existen dos metodos para manejar el problema de los abrazos mortales. Podemos usar algun protocolo para asegurar que el sistema nunca entrara en un estado de abrazo mortal. Alternativamente, podemos permitir que el sistema entre en un estado de abrazo mortal y despues recuperarnos. Como podremos ver posteriormente, el recuperarse de un abrazo mortal puede ser muy dificil y muy caro. Por ello, primeramente consideraremos los metodos para asegurar que no ocurran los abrazos mortales. Comunmente, existen dos metodos: El de PREVENCION de abrazos mortales (Deadlock Prevention) y el de EVASION de abrazos mortales (Deadlock Avoidance).

2.5 Niveles, Objetivos y Criterios de Planificacin

En epocas pasadas de los sistemas de procesamiento por lotes, con una entrada en forma de imagenes de tarjetas en una cinta magnetica, el algoritmo de planificacion era sencillo: solo habia que ejecutar el siguiente trabajo en la cinta. En los sistemas de multiusuario de tiempo compartido, que se combinaban con un fondo de trabajos procesados en lote, el algoritmo era mas complejo. En forma invariable, existian varios usuarios en espera de servicio y podian existir tambien otros trabajos para ser procesados en lote. Incluso en los sistemas puros de tiempo compartido existen con frecuencia los trabajos colaterales, como el sistema de correo electronico, que a menudo se ejecuta todo el tiempo para enviar o recibir correo o noticias. Cuando mas de un proceso es ejecutable, el Sistema Operativo debe decidir cual de ellos debera ejecutarse primero. Hay que tener una planificacion de los procesos que quieren ejecutarse en el sistema.La planificacion es una funcion primordial del Sistema

42

Operativo. La mayoria de los recursos, si no es que todos, se planifican antes de que se utilicen. La asignacion de procesadores fisicos a los procesos hace posible que estos realicen su trabajo, y tal asignacion es un problema complejo manejado por el Sistema Operativo. Concepto de Planificacion La planificacion hace referencia a un conjunto de politicas y mecanismos incorporados al sistema operativo que gobiernan el orden en que se ejecutan los trabajos que deben ser cumplimentados por el sistema informatico. Objetivo de la Planificacion El objetivo principal de la planificacion es optimizar el rendimiento del sistema y proporcionar un buen servicio a todos los procesos que se encuentren en el. En general, la planificacion trata de cubrir los siguientes objetivos:

Justicia. La planificacion debe ser lo mas justa posible con todos los procesos, sin favorecer a unos y perjudicar a otros. Maxima capacidad de ejecucion. Debe dar un servicio eficiente para que todos los trabajos se realicen lo mas rapidamente posible. Esto se puede lograr disminuyendo el numero de cambios de proceso. Maximo numero de usuarios interactivos. En los sistemas de tiempo compartido se tratara de que puedan estar trabajando el mayor numero de usuarios al mismo tiempo. Predecibilidad. La planificacion debe realizarse de tal forma que en todo momento pueda saberse como sera su ejecucion. Minimizacion de la sobrecarga. La computadora debe tener poca sobrecarga ya que esta afecta directamente al rendimiento final del sistema: a menor sobrecarga mayor velocidad de proceso. Equilibrio en el uso de recursos. Para obtener un mayor rendimiento en el uso de los recursos y que estos esten ocupados equitativamente el mayor tiempo posible. Seguridad de las prioridades. Si un proceso tiene mayor prioridad que otro, este debe ejecutarse mas rapidamente. Evitar la postergacion indefinida. Esto se logra aumentando la prioridad de un proceso mientras espere por un recurso. La prioridad llegara a ser tan alta que al proceso le sera asignado el recurso que pidio.

Criterios de planificacion Para realizar los objetivos de la planificacion, un mecanismo de planificacion debe considerar lo siguiente:

43

La limitacion de un proceso a las operaciones de Entrada / Salida: cuando un proceso consigue la cpu, ?la utiliza solo brevemente antes de generar una peticion de Entrada / Salida? La limitacion 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. ?Que urgencia tiene una respuesta rapida?: por ejemplo, un proceso de tiempo real de un sistema de control que supervise una refineria de combustible requiere una respuesta rapida, mas rapida que la respuesta requerida por un proceso en lotes (batch) que debera entregarse al dia siguiente. La prioridad de un proceso: a mayor prioridad mejor tratamiento. Frecuentemente un proceso genera fallos (carencias) de pagina:
o

Probablemente los procesos que generan pocos fallos de pagina hayan acumulado sus conjuntos de trabajo en el almacenamiento principal. Los procesos que experimentan gran cantidad de fallos de pagina aun no han establecido sus conjuntos de trabajo. Un criterio indica favorecer a los procesos que han establecido sus conjuntos de trabajo. Otro criterio indica favorecer a los procesos con una tasa alta de fallos de pagina ya que rapidamente generaran una peticion de Entrada / Salida.

Frecuentemente un proceso ha sido apropiado por otro de mas alta prioridad, lo cual significa lo siguiente:
o

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 ejecucion antes de la apropiacion no justifica la sobrecarga de hacer ejecutar al proceso en primer lugar.

Cuanto tiempo de ejecucion real ha recibido el proceso?: un criterio considera que debe ser favorecido un proceso que ha recibido muy poco tiempo de cpu.

Cuanto 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 ejecucion minimo para su terminacion, pero pocas veces es posible conocer la cantidad de tiempo adicional que cada proceso necesita para terminar.

44

2.6 Tecnicas de Administracin de Planificador

Las disciplinas de planificacin pueden ser: Expropiativas No expropiativas Se denomina planificador al software del sistema operativo encargado de asignar los recursos de un sistema entre los procesos que los solicitan. Siempre que haya tomar una decisin, el planificador debe decidir cul de los procesos que compiten por la posesin de un determinado recursos lo recibir. Los algoritmos (tcnicas) tienen distintas propiedades segn los criterios en los que se basen para su construccin, lo cual se refleja en qu tipo de procesos se puede ver favorecido frente a otro en la disputa del procesador. Antes de realizar la eleccin de un algoritmo se debe considerar las propiedades de estos frente al criterio de diseo elegido. Algunos de estos son: a) Eficacia: Se expresa como un porcentaje del tiempo medio de utilizacin. Aunque puede parecer lgico intentar mantener este parmetro prximo al 100%, con un valor tan elevado otros aspectos importantes de medida del comportamiento del sistema pueden verse deteriorados, como por ejemplo el tiempo medio de espera. b) Rendimiento: Es una medida del nmero de procesos completados por unidad de tiempo. Por ejemplo 10 procesos por segundo. c) Tiempo de retorno o regreso: Es el intervalo de tiempo que transcurre desde que un proceso se crea o presenta hasta que completa por el sistema. d) Tiempo de espera: Es el tiempo que el proceso espera hasta que se le concede el procesador. Puede resultar una medida mas adecuada de la eficiencia del sistema, ya que se elimina de la media el tiempo que tarda en ejecutarse el mismo. e) Tiempo de respuesta a un evento: Se denomina as el intervalo de tiempo que

45

transcurre desde que se seala un evento hasta que se ejecuta la primera instruccin de la rutina de servicio de dicho evento. El criterio de seleccin de un algoritmo se suele basar en la maximizacin o minimizacin de una funcin de los parmetros anteriores.

2.6.1 FIFO
Algoritmo de planificacion de FIFO Tal vez la disciplina mas simple de planificacion sea la de primeras entradas ? primeras salidas (PEPS). Los procesos se despachan de acuerdo con su tiempo de llegada a la cola de procesos listos. Cuando un proceso tiene la CPU, se ejecuta hasta terminar. Es junto en el sentido formal, pero algo injusta en cuanto a que los trabajos largos hacen esperar a los cortos y los trabajos sin importancia hacen esperar a los importantes. FIFO ofrece variaciones relativamente pequenas en los tiempos de respuesta y por lo tanto es mas predecible que los otros esquemas. No es util en la planificacion para los usuarios interactivos porque no puede garantizar buenos tiempos de respuesta. El esquema FIFO rara vez se usa como esquema principal en los sistemas actuales, pero a menudo esta incorporado en otros sistemas. Por ejemplo, muchos esquemas de planificacion despachan los procesos de acuerdo con la prioridad, pero los procesos con la misma prioridad se despachan de acuerdo con el esquema FIFO. Este es un algoritmo que no usa apropiacion, y que consiste en atender a los procesos por estricto orden de llegada a la lista de procesos listos. Cada proceso se ejecuta hasta que termina, o hasta que hace una llamada bloqueante (de E/S). Se trata de una politica muy simple y sencilla de llevar a la practica, pero muy pobre en cuanto a su comportamiento. Las caracteristicas principales de este algoritmo son las siguientes:

No es apropiativa. Es justa, aunque los procesos largos hacen esperar mucho a los cortos. Es una politica predecible. El tiempo promedio de servicio es muy variable ya que esta en funcion del numero de procesos y la duracion promedio que tenga.

EJEMPLO Proceso Tiempo de UCP P1 P2 24 3

46

P3

Media del tiempo de espera: Caso 1) ( 0 + 24 + 27 ) / 3 =17 Caso 2) ( 6 + 0 + 3 ) / 3 = 3 En este esquema se tienen tres procesos (P1, P2, P3) listos para ejecutarse, con un tiempo de ejecucion de 24, 3 y 3 unidades de tiempo (para facilidad tomaremos milisegundos como unidad de tiempo) respectivamente. Los procesos se ejecutan en ese mismo orden. El primer proceso se ejecuta de inmediato y no espera nada. El segundo proceso espera todo lo que dura en ejecutarse el primer proceso que son 24 milisegundos. Por ultimo el tercer proceso esperara la suma de lo que duran en ejecutarse los dos procesos anteriores, o sea, 27 segundos. Todo esto da como resultado un tiempo promedio de espera de 17 milisegundos. Si en cambio, el orden en que se ejecuten los procesos es como el caso 2), entonces el proceso P2 se ejecutaria de inmediato, P3 esperaria lo que tarde en ejecutarse P2 (3 milisegundos) y P1 esperaria lo que duran los dos procesos anteriores, obteniendo un tiempo promedio de espera de 3 milisegundos. Como puede verse el tiempo promedio de espera que tengan los procesos depende por completo del orden en que llegan los procesos a ejecutarse.

2.6.2 SJR
Otro metodo de planificacion de la CPU es el algoritmo de planificacion con seleccion del trabajo mas corto (SJF, shortest job-first). Este algoritmo asocia con cada proceso la duracion de la siguiente rafaga de CPU del proceso. Cuando la CPU esta disponible, se asigna al proceso que tiene la siguiente rafaga de CPU mas corta. Si las siguientes rafagas de CPU de dos procesos son iguales, se usa la planificacion FCFS para romper el empate. Observe que un termino mas apropiado para este metodo de planificacion seria el de algoritmo de la siguiente rafaga de CPU mas corta, ya que la planificacion depende de la duracion de la siguiente rafaga de CPU de un proceso, en lugar de depender de su duracion total. Usamos el termino SJF porque casi todo el mundo y gran parte de los libros de texto emplean este termino para referirse a este tipo de planificacion. Como ejemplo de planificacion SJF, considere el siguiente conjunto de procesos, estando especificada la duracion de la rafaga de CPU en milisegundos: Proceso P1 P2 Tiempo de rafaga 6 8

47

P3 P4

7 3

Usando la planificacion SJF, planificariamos estos procesos de acuerdo con el siguiente diagrama de Gantt: P4 0 P1 3 P3 9 P2 16 24

El tiempo de espera es de 3 milisegundos para el proceso P1, de 16 milisegundos para el proceso P2, de 9 milisegundos para P3 y de 0 milisegundos para P4. Por tanto, el tiempo medio de espera es de (3 + 16 + 9 + 0)/4 = 7 milisegundos. Por comparacion, si estuvieramos usando el esquema de planificacion FCFS, el tiempo medio de espera seria de 10,25 milisegundos. El algoritmo de planificacion SJF es probablemente optimo, en el sentido de que proporciona el tiempo medio de espera minimo para un conjunto de procesos dado. Anteponer un proceso corto a uno largo disminuye el tiempo de espera del proceso corto en mayor medida de lo que incrementa el tiempo de espera del proceso largo. Consecuentemente, el tiempo medio de espera disminuye. La dificultad real del algoritmo SJF es conocer la duracion de la siguiente solicitud de CPU. En una planificacion a largo plazo de trabajos en un sistema de procesamiento por lotes, podemos usar como duracion el limite de tiempo del proceso que el usuario especifique en el momento de enviar el trabajo. Con este mecanismo, los usuarios estan motivados para estimar el limite de tiempo del proceso de forma precisa, dado que un valor menor puede significar una respuesta mas rapida. (Un valor demasiado bajo producira un error de limite de tiempo excedido y sera necesario reenviar el proceso.) La planificacion SJF se usa frecuentemente como mecanismo de planificacion a largo plazo. Aunque el algoritmo SJF es optimo, no se puede implementar en el nivel de la planificacion de la CPU a corto plazo, ya que no hay forma de conocer la duracion de la siguiente rafaga de CPU. Un metodo consiste en intentar aproximar la planificacion SJF: podemos no conocer la duracion de la siguiente rafaga de CPU, pero podemos predecir su valor, por el procedimiento de confiar en que la siguiente rafaga de CPU sera similar en duracion a las anteriores. De este modo, calculando una aproximacion de la duracion de la siguiente rafaga de CPU, podemos tomar el proceso que tenga la rafaga de CPU predicha mas corta. Generalmente, la siguiente rafaga de CPU se predice como la media exponencial de las duraciones medidas de las anteriores rafagas de CPU. Sea tn la duracion de la nesima rafaga de CPU y sea Tn+l el valor predicho para la siguiente rafaga de CPU. Entonces, para a, 0? ? 1, se define tn+1 = tn + (1 - ) tn

48

Esta formula define un promedio exponencial. El valor de tn contiene la informacion mas reciente; tn almacena el historial pasado. El parametro a controla el peso relativo del historial reciente y pasado de nuestra prediccion. Si = 0, entonces tn1 = tn, y el historial reciente no tiene ningun efecto (se supone que las condiciones actuales van a ser transitorias); si = 1, entonces tn+1 = tn y solo la rafaga de CPU mas reciente importa (se supone que el historial es obsoleto y, por tanto, irrelevante). Frecuentemente, = 1/2, en cuyo caso, el historial reciente y pasado tienen el mis peso. El valor inicial t0 puede definirse como una constante o como un promedio global para todo el sistema. La Figura 5.3 muestra un promedio exponencial con = 1/2 y t0 = 10. Para comprender el comportamiento del promedio exponencial, podemos desarrollar la formula para tn+l sustituyendo el valor de tn y de los terminos sucesivos, obteniendo Tn+1 = tn+(1-a)atn-1 +???+(1- )j tn-j +???+(1-(X)n+1t0 Dado que tanto a como 1-a son menores o iguales a 1, cada termino sucesivo tiene menor peso que su predecesor. El algoritmo SJF puede ser cooperativo o apropiativo. La necesidad de elegir surge cuando un proceso llega a la cola de procesos preparados mientras que un proceso anterior esta todavia en ejecucion. La siguiente rafaga de CPU del proceso que acaba de llegar puede ser mas corta que lo que quede del proceso actualmente en ejecucion. Un algoritmo SJF apropiativo detendra el proceso actualmente en ejecucion, mientras que un algoritmo sin desalojo permitira que dicho proceso termine su rafaga de CPU. La planificacion SJF apropiativa a veces se denomina planificacion con seleccion del proceso con tiempo restante mas corto. Como ejemplo, considere los cuatro procesos siguientes, estando especificada la duracion de la rafaga de CPU en milisegundos: Proceso P1 P2 P3 P4 Tiempo 0 2 3 de llegada 1 5 Tiempo de rafaga 8 4 9

Si los procesos llegan a la cola de procesos preparados en los instantes que se muestran y necesitan los tiempos de rafaga indicados, entonces la planificacion SJF apropiativa es la que se muestra en el siguiente diagrama de Gantt: P1 0 P2 1 P4 5 P1 10 P3 17 26

El proceso Pl se inicia en el instante 0, dado que es el unico proceso que hay en la cola. El proceso P2llega en el instante 1. El tiempo que le queda al proceso P1 (7

49

milisegundos) es mayor que el tiempo requerido por el proceso P2 (4 milisegundos), por lo que el proceso Pl se desaloja y se planifica el proceso P2. El tiempo medio de espera en este ejemplo es de ((10 - 1) + (1- 1) + (17 - 2) + (5 - 3) )/4 = 26/4 = 6,5 milisegundos. La planificacion SJF cooperativa proporcionaria un tiempo medio de espera de 7,75 milisegundos.

2.6.3 Planificacion de Asignacion en Rueda (RR-Round Robin)

Es un sistema apropiativo. Cada proceso recibe una fraccion de tiempo de procesamiento o quanto para su ejecucion, de manera que cuando se esta ejecutando y excede el tiempo que se le ha concedido, se genera una interrupcion de reloj, mediante la cual la ejecucion del proceso se detiene y se coloca al proceso al final de la cola de procesos listos para su posterior ejecucion, seleccionandose a continuacion un nuevo proceso de la cola para su ejecucion. Si un proceso finaliza su ejecucion antes de que termine el tiempo que se le ha asignado, este cede el control, seleccionandose un nuevo proceso de la cola para su ejecucion. Con el Round Robind, cuando un proceso inicia una operacion de E/S, este es penalizado respecto de los procesos que no realizan E/S. Los procesos se despachan en FIFO y disponen de una cantidad limitada de tiempo de cpu, llamada division de tiempo o cuanto. Si un proceso no termina antes de expirar su tiempo de cpu ocurren las siguientes acciones: 1. La cpu es apropiada. 2. La cpu es otorgada al siguiente proceso en espera. 3. El proceso apropiado es situado al final de la lista de listos. Es efectiva en ambientes de tiempo compartido. La sobrecarga de la apropiacion se mantiene baja mediante mecanismos eficientes de intercambio de contexto y con suficiente memoria principal para los procesos. Tamano del Cuanto o Quantum La determinacion del tamano del cuanto es decisiva para la operacion efectiva de un sistema computacional. Los interrogantes son: ?cuanto pequeno o grande?, ?cuanto fijo o variable? y ?cuanto igual para todos los procesos de usuarios o determinado por separado para cada uno de ellos? Si el cuanto se hace muy grande, cada proceso recibe todo el tiempo necesario para llegar a su terminacion, por lo cual la asignacion en rueda (RR) degenera en FIFO. Si el cuanto se hace muy pequeno, la sobrecarga del intercambio de contexto se convierte en un factor dominante y el rendimiento del sistema se degrada, puesto que la mayor parte del tiempo de cpu se invierte en el intercambio del procesador (cambio de contexto) y los procesos de usuario disponen de muy poco tiempo de cpu.

50

El cuanto debe ser lo suficientemente grande como para permitir que la gran mayoria de las peticiones interactivas requieran de menos tiempo que la duracion del cuanto, es decir que el tiempo transcurrido desde el otorgamiento de la cpu a un proceso hasta que genera una peticion de Entrada / Salida debe ser menor que el cuanto establecido, de esta forma, ocurrida la peticion la cpu pasa a otro proceso y como el cuanto es mayor que el tiempo transcurrido hasta la peticion de Entrada / Salida, los procesos trabajan al maximo de velocidad, se minimiza la sobrecarga de apropiacion y se maximiza la utilizacion de la Entrada / Salida. El cuanto optimo varia de un sistema a otro y con la carga, siendo un valor de referencia 100 mseg (cien milisegundos). Caracteristicas de RR 1. Baja sobrecarga si el cambio entre un proceso y otro es eficiente y los procesos siempre estan en la memoria principal 2. El tamano optimo del quantum depende de: El tipo Las cargas que vaya a El numero de procesos en el sistema y su tipo. de soportar el sistema. sistema.

3. Es la politica mas usada para tiempo compartido. 4. Ofrece un servicio igual para todos los procesos. 5. Es una politica apropiativa. 6. Mantiene mas equilibradas las colas de procesos listos y bloqueados. Virtual Round Robind (vrr) Este sistema va a permitir solucionar el problema del RoundRobind en relacion al favorecimiento que este realiza con los procesos orientados a la CPU frente a los procesos orientados a las operaciones de E/S. El vrr utiliza una cola auxiliar de espera que incluye aquellos procesos que no hayan consumido completamente el quanto que tenian asignados al verse detenidos por una operacion de E/S. Esta cola tiene prioridad respecto a la principal y a los procesos almacenados en ella se les asigna temporalmente (hasta que se ejecuten de nuevo) un nuevo quanto, que es el tiempo del quanto principal que no llegaron a consumir antes de ser bloqueados (el 2o quanto es el quanto principal menos el tiempo del mismo que ya haya sido consumido por el proceso).

2.6.4 Queues Multinivel

Otra clase de algoritmos de planificacion es la que se ha desarrollado para aquellas situaciones en las que los procesos pueden clasificarse facilmente en grupos diferentes. Por ejemplo, una clasificacion habitual consiste en diferenciar entre

51

procesos de primer plano (interactivos) y procesos de segundo plano (por lotes). Estos dos tipos de procesos tienen requisitos diferentes de tiempo de respuesta y, por tanto, pueden tener distintas necesidades de planificacion. Ademas, los procesos de primer plano pueden tener prioridad (definida externamente) sobre los procesos de segundo plano. Un algoritmo de planificacion mediante colas multinivel divide la cola de procesos prepados en varias colas distintas (Figura 5.6). Los procesos se asignan permanentemente a una cola, generalmente en funcion de alguna propiedad del proceso, como por ejemplo el tamano memoria, la prioridad del proceso o el tipo de proceso. Cada cola tiene su propio algoritmo de planificacion. Por ejemplo, pueden emplearse colas distintas para los procesos de primer plano y de segundo plano. La cola de primer plano puede planificarse mediante un algoritmo por turnos, mientras que para la cola de segundo plano puede emplearse un algoritmo FCFS. Ademas , debe definirse una planificaciion entre las colas, la cual suele implementarse como una planificacion apropiada y prioridad fija. po ejemplo, la cola de procesos de primer plano puede tener velocidad absoluta sobre la cola de procesos de segundo plano. Veamos un ejemplo de algoritmo de planificacion mediante colas multinivel con las cinco colas que se enumeran a continuacion, segun su orden de prioridad: 1. Procesos 2. Procesos 3. Procesos de 4. Procesos 5. Procesos de estudiantes. del edicion por sistema. interactivos. interactivos. lotes.

Cada cola tiene prioridad absoluta sobre las colas de prioridad mas baja. Por ejemplo, ningun proceso de la cola por lotes podra ejecutarse hasta que se hayan vaciado completamente las colas de los procesos del sistema, los procesos interactivos y los procesos de edicion interactivos. Si un proceso de edicion interactivo llega a la cola de procesos preparados mientras se esta ejecutando un proceso por lotes, el proceso por lotes sera desalojado. Otra posibilidad consiste en repartir el tiempo entre las colas. En este caso, cada cola obtiene una cierta porcion del tiempo de CPU, con la que puede entonces planificar sus distintos procesos Por ejemplo, en el caso de la colas de procesos de primer plano y segundo plano, la cola de primer plano puede disponer del 80 por ciento del tiempo de CPU para planificar por turnos sus procesos, mientras que la cola de procesos de segundo plano recibe el 20 por ciento del tiempo de CPU para gestionar sus procesos mediante el metodo FCFS.

2.6.5 Multi-Level FreedBack Queues

52

Normalmente, cuando se usa el algoritmo de planificacion mediante colas multinivel, los procesos se asignan de forma permanente a una cola cuando entran en el sistema. Por ejemplo, si hay colas diferentes para los procesos de primer y segundo plano, los procesos no se mueven de una cola a otra, dado que no pueden cambiar su naturaleza de proceso de primer o segundo plano. Esta configuracion presenta la ventaja de una baja carga de trabajo de planificacion, pero resulta poco flexible. Por el contrario, el algoritmo de planificacion mediante colas multinivel realimentadas permite mover un proceso de una cola a otra. La idea es separar los procesos en funcion de las caracteristicas de sus rafagas de CPU. Si un proceso utiliza demasiado tiempo de CPU, se pasa a una a de prioridad mas baja. Este esquema deja los procesos limitados por E/S y los procesos interactivos en las colas de prioridad mas alta. Ademas, un proceso que este esperando demasiado tiempo en una cola de baja prioridad puede pasarse a una cola de prioridad mas alta. Este mecanismo de envejecimiento evita el bloqueo indefinido. Por ejemplo, considere un planificador de colas multinivel realimentadas con tres colas, numeradas de 0 a 2 (Figura 5.7). En primer lugar, el planificador ejecuta todos los procesos de la cola 0. Solo cuando la cola 0 este vacia ejecutara procesos de la cola 1. De forma similar, los procesos de la cola 2 solo se ejecutaran si las colas 0 y 1 estan vacias. Un proceso que llegue a la cola 1 desalojara a un proceso de la cola 2 y ese proceso de la cola 1 sera, a su vez, desalojado por un proceso que llegue a la cola 0. Un proceso que entre en la cola de procesos preparados se coloca en la cola 0 y a cada uno de los procesos de esa cola se le proporciona un cuanto de tiempo de 8 milisegundos. Si el proceso no termina en ese tiempo, se pasa al final de la cola 1. Si la cola 0 esta vacia, al proceso que se encuentra al principio de la cola 1 se le asigna un cuanto de 16 milisegundos. Si no se completa en ese tiempo, se lo desaloja y se lo incluye en la cola 2. Los procesos de la cola 2 se ejecutan basandose en una planificacion FCFS, pero solo cuando las colas 0 y 1 estan vacias. Este algoritmo de planificacion proporciona la prioridad mas alta a todo proceso que tenga una rafaga de CPU de 8 milisegundos o menos. Tales procesos acceden rapidamente a la CPU, concluyen su rafaga de CPU y pasan a su siguiente rafaga de E/S. Los procesos que necesitan mas de 8 milisegundos y menos de 24 milisegundos tambien son servidor rapidamente, aunque con una prioridad mas baja que los procesos mas cortos. Los procesos largos terminan yendo automaticamente a la cola 2 y se sirven, siguiendo el orden FCFS, con los ciclos de CPU no utilizados por las colas 0 y 1. En general, un planificador mediante colas multinivel realimentadas se define mediante los parametros siguientes: ??????? El numero de colas. ?????????? El algoritmo de planificacion de cada cola. ?????????? El metodo usado para determinar cuando pasar un proceso a una cola de

53

prioridad mas alta. ?????????? El metodo usado para determinar cuando pasar un proceso a una cola de prioridad mas baja. ?????????? El metodo usado para determinar en que cola se introducira un proceso cuando haya que darle servicio. La definicion del planificador mediante colas multinivel realimentadas le convierte en el algoritmo de planificacion de la CPU mas general. Puede configurarse este algoritmo para adaptarlo a cualquier sistema especifico que se quiera disenar. Lamentablemente, tambien es el algoritmo mas complejo, puesto que definir el mejor planificador requiere disponer de algun mecanismo para seleccionar los valores de todos los parametros.

UNIDAD 3 Administracin de Memoria

3.1 Poltica y Filosofa
Filosofa La memoria principal puede ser considerada como un arreglo lineal de localidades de almacenamiento de un byte de tamano. Cada localidad de almacenamiento tiene asignada una direccion que la identifica. Una de las funciones basicas que debe implementar un SO es la Administracion de la Memoria para tener un control sobre los lugares donde estan almacenados los datos y procesos que actualmente se estan utilizando. Sea cual sea es esquema de organizacion del almacenamiento que se adopte para un sistema especifico es necesario decidir que estrategias se deben utilizar para obtener un rendimiento optimo. Polticas FIFO: Los procesos se despachan de acuerdo a su tiempo de llega a la cola de procesos listos, si un proceso llega al procesador sale hasta que termine. La politica FIFO actualmente no se usa como el esquema principal de un sistema, pero si por ejemplo cuando se usa una politica de prioridades y hay procesos con la misma prioridad, a estos se les podria aplicar FIFO. (Ver figura (1))

Figura 3.1.1 Round Robin: Los procesos se despachan en la forma que lo hace el FIFO, pero se les asigna una cantidad limitada de tiempo (CUANTUM) en el procesador, si no termina en
54

ese lapso se manda al final de la lista de procesos listos. (Ver figura(2))

Figura 3.1.2 SJF (Shortest job first - Prioridad del trabajo mas corto): Se ejecuta primero el proceso en espera que tiene el menor tiempo estimado. SJF favorece a los procesos cortos, ya que los largos podrian llegar a rezagarse mucho tiempo e incluso nunca ejecutarse. (Ver Figura(3))

Figura 3.1.3 SRT (Sortest remaining time scheduling ? Tiempo restante mas corto. En SJF una vez que un proceso comienza su ejecucion continua hasta terminar. En SRT, un proceso en ejecucion puede ser desposeido por uno nuevo de menor tiempo de ejecucion. (Ver Figura(4)) HRN: (highest response ratio next ? Prioridad de la tasa de respuesta mas alta): Politica no apropiativa que corrige el retraso excesivo de procesos grandes que produce el SJF, para asi no caer en un favoritismo excesivo por los procesos cortos, lo logra usando una formula basada en el tiempo de espera y el tiempo de servicio, con lo cual la prioridad de cada trabajo no solo esta en funcion del tiempo de servicio sino tambien del tiempo que ha esperado para ser atendido.(Ver Figura(5))

3.2 Memoria Real

55

La memoria real o principal es en donde son ejecutados los programas y procesos de una computadora y es el espacio real que existe en memoria para que se ejecuten los procesos. Por lo general esta memoria es de mayor costo que la memoria secundaria, pero el acceso a la informacion contenida en ella es de mas rapido acceso. Solo la memoria cache es mas rapida que la principal, pero su costo es a su vez mayor. Cuando no existe memoria virtual no hay diferenciacion entre el espacio de direcciones y la memoria real; el espacio de direcciones que puede ser usado en los programas tiene identico tamano al espacio de memoria real posible. Si se utiliza memoria virtual, el espacio de direcciones disponibles para los programas es aquel determinado por el tamano de la memoria virtual implementada y no el espacio de direcciones provisto por la memoria real disponible (el espacio de la memoria virtual sera mayor que el de la memoria real). La organizacin y administracin de la memoria principal, memoria primaria o memoria real de un sistema ha sido y es uno de los factores mas importantes en el diseo de los S. O. (Ver la figura 3.2.1) Los trminos memoria y almacenamiento se consideran equivalentes. Los programas y datos deben estar en el almacenamiento principal para: Poderlos ejecutar. Referenciarlos directamente

3.2.1 Administracin de almacenamiento

Cmo se maneja la administracin de almacenamiento? Para que un sistema informatico sea comodo para los usuarios, el sistema operativo proporciona una ista logica y uniforme del sistema de almacenamiento de la informacion.. El sistema operativo abstrae las propiedades fisicas de los dispositivos de almacenamiento y define una unidad de almacenamiento logico, el archivo. El sistema operativo asigna los archivos a los soportes fisicos y accede a dichos

56

archivos a traves de los dispositivos de almacenamiento.

Almacenamiento del sistema de archivos

La gestion de archivos es uno de los componentes mas visibles de un sistema operativo. Las computadores pueden almacenar la informacion en diferentes tipos de medios fisicos.Los discos magneticos, discos opticos y cintas magneticas son habituales. . Cada uno de estos medios tiene sus propias caracteristicas y organizacion fisica.Cada medio se controla mediante un dispositivo, tal como una unidad de disco o una cinta, que tambien tiene sus propias caracteristicas distintivas Estas propiedades incluyen la velocidad de acceso, la capacidad, la velocidad de transferencia de datos y el metodo de acceso (secuencial o aleatorio). Un archivo es una coleccion de informacion relacionada definida por su creador. Comunmente, los archivos representan programas(tanto en formato fuente como en objeto) y datos. Los archivos de datos pueden ser numericos, alfabeticos, alfanumericos o binarios. Los archivos pueden tener un formato libre(como, por ejemplo, los archivos de texto) o un formato rigido, como por ejemplo una serie de campos fijos.

3.2.2 Jerarqua
Los programas y datos tienen que estar en la memoria principal para poder ejecutarseo ser referenciados. Los programas y datos que no son necesarios de inmediato pueden mantenerse en el almacenamiento secundario. El almacenamiento principal es mas costoso y menor que el secundario pero de acceso mas rpido. Los sistemas con varios niveles de almacenamiento requieren destinar recursos para administrar el movimiento de programas y datos entre niveles. Un nivel adicional es el cache o memoria de alta velocidad, que posee las siguientes caractersticas: Es ms rpida y costosa que la memoria principal. Impone al sistema un nivel mas de traspaso:

57

Los programas son traspasados de la memoria principal al cache antes de su ejecucin. Los programas en la memoria cache ejecutan mucho mas rpido que en la memoria principal. Al utilizar memoria cache se espera que: La sobrecarga que supone el traspaso de programas de un nivel de memoria a otro sea mucho menor que la mejora en el rendimiento obtenida por la posibilidad de una ejecucin mucho mas rpida en la cache.

3.2.3 Estrategias de Administracin de Memoria

Estn dirigidas a la obtencin del mejor uso posible del recurso del almacenamiento principal. Se dividen en las siguientes categoras: Estrategias de bsqueda: Estrategias de bsqueda por demanda. Estrategias de bsqueda anticipada. Estrategias de colocacin. Estrategias de reposicin. Las estrategias de bsqueda estn relacionadas con el hecho de cuando obtener el siguiente fragmento de programa o de datos para su insercin en la memoria principal. En la bsqueda por demanda el siguiente fragmento de programa o de datos se carga al almacenamiento principal cuando algn programa en ejecucin lo referencia. Se considera que la bsqueda anticipada puede producir un mejor rendimiento del sistema. Las estrategias de colocacin estn relacionadas con la determinacin del lugar de la memoria donde se colocara (cargara) un programa nuevo. Las estrategias de reposicin estn relacionadas con la determinacin de que fragmento de programa o de datos desplazar para dar lugar a los programas nuevos.

3.2.4 Asignacin continua V.S No continua

Qu es la administracin contigua y no contigua? En la asignacin contigua cada programa ocupa un bloque contiguo y sencillo de localizaciones de almacenamiento.

58

Asignacin contigua de almacenamiento Se consideran S. O. que ya poseen desarrollado el

de

un

solo

usuario

sistema de control de entrada / salida: IOCS: input / output control system (ver Figura 3.2.4.1):

El tamao de los programas esta limitado por la cantidad de memoria principal, pero se puede superar este limite con tcnicas de recubrimientos, con las siguientes caractersticas. (Ver figura 3.2.4.2) Si una seccin particular del programa ya no es necesaria, se carga otra seccin desde el almacenamiento secundario ocupando las reas de memoria liberadas por la seccin que ya no se necesita. La administracin manual por programa del recubrimiento es complicada y dificulta el desarrollo y el mantenimiento.

En la asignacin no contigua un programa se divide en varios bloques o segmentos que pueden almacenarse en direcciones que no tienen que ser necesariamente adyacentes, por lo que es mas compleja pero mas eficiente que la asignacin continua. (Ver figura 3.2.4.3)

59

3.3 Organizacin de Memoria Virtual

Memoria Virtual La memoria virtual es una tcnica para proporcionar la simulacin de un espacio de memoria mucho mayor que la memoria fsica de una maquina.Esta ilusin permite que los programas se hagan sin tener en cuenta el tamao exacto de la memoria fsica. La memoria virtual ha llegado a ser un componente esencial de la mayora de los S.O actuales. Y como en un instante dado, en la memoria solo se tienen unos pocos fragmentos de un proceso dado, se pueden mantener mas procesos en la memoria. La memoria virtual tambin simplifica la carga del programa para su ejecucin llamado reubicacin, este procedimiento permite que el mismo programa se ejecute en cualquier posicin de la memoria fsica.

3.3.1 Evaluacin de las Organizaciones de Almacenamiento

60

Almacenamiento virtual "significa la capacidad de direccional un espacio de almacenamiento mucho mayor que el disponible en el almacenamiento primario de determinado sistema de computacin. Esta tecnologa apareci en 1960 en la Universidad de Manchester (Inglaterra), en el sistema Atlas. Los mtodos ms comunes de implementacin son mediante: Tcnicas de paginacin. Tcnicas de segmentacin. Una combinacin de ambas tcnicas. Las direcciones generadas por los programas en su ejecucin no son, necesariamente, aquellas contenidas en el almacenamiento primario (memoria real), ya que las direcciones virtuales suelen seleccionarse dentro de un numero mucho mayor de direcciones que las disponibles dentro del almacenamiento primario. La evolucin en las organizaciones de almacenamiento puede resumirse como sigue: Real: Sistemas dedicados a un solo usuario. Real: Sistemas de multiprogramacin en memoria real: Multiprogramacin en particin fija: Absoluta. Relocalizable (reubicadle). Multiprogramacin en particin variable. Virtual: Multiprogramacin en almacenamiento virtual: Paginacin pura. Segmentacin pura. Combinacin paginacin / segmentacin.

3.3.2 Paginacin Qu es la paginacin?

61

El termino memoria virtual se asocia normalmente con sistemas que emplean paginacin, aunque tambin se puede usar memoria virtual basada en la segmentacin. El uso de la paginacin en la memoria virtual fue presentado por primera vez en el computador Atlas. Cada proceso tiene su propia tabla de paginas y cuando carga todas sus paginas en la o memoria principal. Puesto que solo algunas de las pginas de un proceso pueden estar en la memoria principal, se necesita un bit en cada entrada de la tabla para indicar si la pagina perteneciente esta presente en la memoria principal o no. Si el bit indica que la pagina esta en la memoria, la entrada incluye tambin el nmero de marco para esa pagina. Otro bit de control necesario en la entrada de la tabla de pginas es el bit de modificacin (M), para indicar si el contenido de la pgina correspondiente se ha alterado desde que la pgina se cargo en la memoria principal. Si no ha habido cambios, no es necesario escribir la pgina cuando sea sustituida en el marco que ocupa actualmente. Estructura de la tabla de pginas El mecanismo bsico de lectura de una palabra de la memoria supone la traduccin por medio de la tabla de pginas de una direccin virtual o lgica (ver figura 3.3.2.1 y 3.3.2.2), formada por un numero de pagina y un desplazamiento, a una direccin fsica que esta formada por un numero de marco y un desplazamiento. Con la memoria virtual, la CPU produce direcciones virtuales que son traducidas por una combinacin de hardware y software a direcciones fsicas, pues pueden ser utilizadas para acceder a memoria principal. Este proceso se denomina correspondencia de memoria o traduccin de direcciones. Actualmente los dos niveles de la jerarqua de memoria controlados por la memoria virtual son las DRAM y los Discos magnticos. Puesto que la tabla de pginas es de longitud variable, en funcin del tamao del proceso, no es posible suponer que quepa en los registros.

62

Figura

3.3.2.1

63

3.3.3 Segmentacin
Implicaciones de la memoria virtual

La segmentacin permite al programador contemplar la memoria como si constara de varios espacios de direcciones o segmentos. Los segmentos pueden ser de distintos tamaos, incluso de forma dinmica. Las referencias a la memoria constan de una direccin de la forma (numero de segmento, desplazamiento). Esta organizacin ofrece al programador varias ventajas sobre un espacio de direcciones no segmentado: 1. Simplifica la gestin de estructuras de datos crecientes. Si el programador no conoce a priori cuan larga puede llegar a ser una estructura de datos determinada, es necesario suponerlo a menos que se permitan tamaos de segmentos dinmicos. Con memoria virtual segmentada, a la estructura de datos se le puede asignar a su propio segmento y el S.O expandir o reducir el segmento cuando se necesite. 2. Permite modificar y recopilar los programas independientemente, sin que sea necesario recopilar o volver a montar el conjunto de programas por completo. 3. Se presta a la comparicin entre procesos. Un programador puede situar un programa de utilidades o una tabla de datos en un segmento que puede ser referenciado por otros procesos. 4. Se presta a la proteccin. Puesto que un segmento puede ser construido para albergar un conjunto de procedimientos y datos bien definido, el programador o el administrador del sistema podrn asignar los permisos de acceso de la forma adecuada. Organizacin En el estudio de la segmentacin simple, se llego a la conclusin de que cada proceso tiene su propia tabla de segmento y que, cuando todos los segmentos se encuentran en la memoria principal, la tabla de segmentos del proceso se crea y se carga en la memoria. Cada entrada de la tabla contiene la direccin de comienzo del segmento correspondiente de la memoria principal, as como su longitud. La misma estructura se necesitara al hablar de un esquema de memoria virtual basado en la segmentacin donde las entradas de la tabla de segmentos pasan a ser mas complejas. Puesto que solo algunos de los segmentos de un proceso estarn en la memoria principal, se necesita un bit en cada entrada de la tabla de segmentos para indicar si el segmento correspondiente esta presente en la memoria principal. Si el bit indica que el segmento esta en la memoria, la entrada incluye tambin la direccin de comienzo y la longitud del segmento. Otro bit de control necesario en la entrada de la tabla de segmentos es un bit de modificacin que indique si el contenido del segmento correspondiente ha sido modificado desde que se cargo por ltima vez en la memoria principal. Si no ha habido

64

cambios, no ser necesario escribir en el disco el segmento cuando llegue el momento de reemplazarlo en el espacio que ocupa actualmente.

3.3.4 Sistema de paginacin / segmentacin

La paginacin y la segmentacin puras son mtodos de manejo de memoria bastante efectivos, aunque la mayora de los sistemas operativos modernos implantan esquemas combinados, es decir, combinan la paginacin y la segmentacin. La idea de combinar estos esquemas se debe a que de esta forma se aprovechan los conceptos de la divisin lgica de los programas (segmentos) con la granularidad de las pginas. De esta forma, un proceso estar repartido en la memoria real en pequeas unidades (paginas) cuya liga son los segmentos. Tambin es factible as el compartir segmentos a medida que las partes necesitadas de los mismos se van reverenciando (paginas). Para comprender este esquema, nuevamente se vera como se traduce una direccin virtual en una localidad de memoria real. Para la paginacin y segmentacin puras se puede decir que el direccionamiento es `bidimensional' porque se necesitan dos valores para hallar la direccin real. Para el caso combinado, se puede decir que se tiene un direccionamiento `tridimensional'. El sistema debe contar con una tabla de procesos (TP) (Ver figura 3.3.4.1). Por cada rengln de esa tabla se tiene un nmero de proceso y una direccin a una tabla de segmentos. Es decir, cada proceso tiene una tabla de segmentos. Cuando un proceso hace alguna referencia a memoria, se consulta TP para encontrar la tabla de segmentos de ese proceso. En cada tabla de segmentos de proceso (TSP) se tienen los nmeros de los segmentos que componen a ese proceso. Por cada segmento se tiene una direccin a una tabla de pginas. Cada tabla de pginas tiene las direcciones de las pginas que componen a un solo segmento. Por ejemplo, el segmento `A' puede estar formado por las paginas reales `a','b','c','p' y `x'. El segmento `B' puede estar compuesto de las paginas `f','g','j','w' y `z'. Otro aspecto importante es la estrategia para cargar pginas (o segmentos) a la memoria RAM. Se usan ms comnmente dos estrategias: cargado de pginas por demanda y cargado de pginas anticipada. La estrategia de cargado por demanda consiste en que las pginas solamente son llevadas a RAM si fueron solicitadas, es decir, si se hizo referencia a una direccin que cae dentro de ellas. La carga anticipada consiste en tratar de adivinar que paginas sern solicitadas en el futuro inmediato y cargarlas de antemano, para que cuando se pidan ya no ocurran fallos de pagina. Ese `adivinar' puede ser que se aproveche el fenmeno de localidad y que las paginas que se cargan por anticipado sean aquellas que contienen direcciones contiguas a la direccin que se acaba de refenciar. De hecho, el sistema operativo VMS usa un
65

esquema combinado para cargar pginas: cuando se hace referencia a una direccin cuya pgina no esta en RAM, se provoca un fallo de pgina y se carga esa pgina junto con algunas pginas adyacentes. En este caso la pgina solicitada se cargo por demanda y las adyacentes se cargaron por anticipacin.

Figura 3.3.4.1

3.4 Almacenamiento de Memoria Virtual

La clave del concepto de memoria (almacenamiento) virtual esta en la disociacin:

De las direcciones a las que hace referencia un programa. De las direcciones disponibles en la memoria real (almacenamiento primario).

Mientras el proceso se ejecuta con sus pginas actuales, el sistema carga las dems pginas que estarn disponibles cuando las requiera el proceso.

66

El S. O. intenta predecir las pginas que un proceso va a necesitar y a continuacin precarga estas pginas cuando hay espacio disponible Mientras el proceso ejecuta sus pginas actuales, el sistema carga pginas nuevas que estarn disponibles cuando el proceso las pida, debido a ello, el tiempo de ejecucin de un proceso se puede reducir.

3.4.1 Estrategias de Administracin

Estrategias de Obtencin Determinan cuando se debe de transferir una pgina o un segmento de almacenamiento secundario al primario. Las estrategias de obtencin por demanda esperan a que un proceso en ejecucion haga referencia a una pgina o un segmento antes de traer la pgina o el segmento de almacenamiento primario. Los esquemas de obtencin anticipada intentan determinar por adelantado a cuales paginas o segmentos har referencia un proceso. Estrategias de Colocacin Determinan en que lugar del almacenamiento primario se debe colocar una pgina o un segmento entrante. Una pgina entrante se puede colocar en cualquier marco de pgina disponible. Estrategias de Reemplazo Sirven para decidir cul pgina o segmento se debe desplazar para dar espacio a una pgina o segmento entrante cuando est completamente ocupado el almacenamiento primario.

3.4.2 Tecnicas de reemplazo de pagina

Las rutinas de administracion de almacenamiento del Sistema operativo deben decidir que pagina del almacenamiento primario se debe desplazar para dejar espacio a una pagina entrante . Principio de Optimalidad Para obtener un rendimiento optimo, la pagina que se debe reemplazar es aquella que tardara mas tiempo en ser utilizada. Esta estrategia optima de reemplazo se denomina OPT o MIN. Reemplazo de Pginas aleatorio Es una tecnica sencilla. Todas las paginas que se encuentran en el almacenamiento principal tienen la misma probabilidad de ser elegidas para el reemplazo. Esta estrategia podria seleccionar cualquier pagina para ser reemplazada, incluyendo la siguiente pagina la que se hara referencia. Las decisiones de reemplazo aleatorio se de paginas se pueden tomar rapidamente y con un numero significativo de marcos de
67

pagina. Es un esquema que casi no se utiliza por su enfoque aleatorio de acertar o errar. Reemplazo de pginas de primeras entradas-primeras salidas (PEPS) Cada pagina se registra en el instante que entro en el almacenamiento primario. Cuando se necesita reemplazar una pagina, se escoge la que ha permanecido en el almacenamiento durante el mayor tiempo. Anomalias PEPS Belady, Nelson y Shelder descubrieron que al utilizar el reemplazo de paginas PEPS, ciertos patrones de referencia a pagina originan mas fallas de paginas cuando aumenta el numero de marcos de pagina asignados a un proceso. Este fenomeno se denomina Anomalia PEPS o anomalia Belady. La columna de la izquierda indica el patron de referencias a paginas de un proceso. La primera tabla muestra como dicho patron a referencia de paginas hace que las paginas se carguen a memoria y se reemplacen en secuencia PEPS cuando se asignan tres marcos de paginas a proceso. La segunda tabla muestra como se comporta este proceso en las mismas circunstancias, pero con cuatro marcos de paginas asignados, a la izquierda de cada tabla se indica si la nueva referencia a una pagina ocasiona o no una falla de pagina. Cuando el proceso se ejecuta en cuatro paginas, experimenta una falla de pagina mas que cuando se ejecuta con tres. Reemplazo de pginas de la menos reciente utilizada Se selecciona para su reemplazo, a aquella pagina que no se ha sido utilizada durante mayor tiempo. La estrategia se basa en que la heuristica de localidad segun en el cual el pasado reciente es un buen indicador del futuro cercano, de modo que LRU exige que se marque cada pagina con el instante en que .se hace referencia a ella. Por el trabajo adicional que requiere no se usa a menudo en los sistemas actuales; lo que se hace es utilizar estrategias que ese aproximen a la LRU y que no ocasionen grandes costos. Reemplazo de paginas de la menos frecuentemente utilizada (LFU) La pagina por remplazar es aquella que ha sido utilizada menos frecuentemente o a la que se ha hecho referencia con menos frecuencia. Al parecer estos esquemas de reemplazo de paginas corren cierto riesgo de tomar decisiones equivocadas. Esto sucede por el simple hecho de que no se puede predecir con precision el futuro. Modificaciones de PEPS; reemplazo de paginas por reloj y reemplazo de paginas con segunda oportunidad La estrategia PEPS puede decidir reemplazar una pagina muy utilizada que ha permanecido en memoria durante mucho tiempo. Esta posibilidad se puede evitar reemplazando solo aquellas paginas cuyos bits de referencia valgan O. La variante de PEPS denominada "con segunde oportunidad" examina el bit de referencia de la pagina mas antigua; si este bit vale O, se selecciona de inmediato la

68

pagina para ser reemplazada. Si el bit de referencia vale 1, se le asigna el valor O y la pagina se pasa al final de la lista y se considera en esencia como una pagina nueva; gradualmente dicha pagina se desplaza hacia el principio de la lista, donde sera seleccionada para reemplazo solo si su bit de referencia sigue valiendo O. En esencia, esto da a la pagina una segunda oportunidad de permanecer en el almacenamiento principal si su bit de referencia cambia a 1 antes de que la pagina llegue al principio de la lista. La variacion 'z' del reloj" del algoritmo de la segunda oportunidad dispone las paginas en una lista circular, en lugar de en una lista lineal. Un apuntador a la lista se desplaza alrededor de la lista circular en la misma forma que gira la manecilla de un reloj. Cuando el bit de referencia de una pagina toma el valor O, el apuntador se mueve al siguiente elemento de la lista (simulando el movirl1iento de esta pagina al final de la lista PEPS).

3.4.3 Paginacin por demanda

Paginacin bajo demanda Considere como podria cargarse un programa ejecutable desde el disco a la memoria. Una opcion consiste encargar el programa completo en memoria fisica en el momento de ejecutar el programa. Sin embargo, esta tecnica presenta el problema de que puede que no necesitemos inicialmente todo el programa en la memoria. Las paginas de un proceso deben cargarse por demanda. No se debe transferir ninguna pagina al almacenamiento secundario al primado hasta que un proceso en ejecucion haga explicitamente referencia a ella. Hay varias razones por las cuales es atractiva esta estrategia. Los resultados de la teoria de la computabilidad, especifica mente el problema de la detencion (Mi67) (He77), indican que no se puede predecir con precision la trayectoria de ejecucion que seguira un programa. Asi pues, cualquier intento de cargar paginas con anticipacion a su uso puede hacer que se carguen las paginas equivocadas. La paginacion por demanda garantiza que las unicas paginas que se transfieren al almacenamiento principal son aquellas que requieren los procesos. El trabajo extra requerido para decidir cuales paginas se deben transferir al almacenamiento principal es minimo. Las estrategias de obtencion anticipada de paginas G pueden requerir mucho tiempo de ejecucion adicional

3.4.4 Paginacin anticipada

Qu es la paginacin anticipada? En la paginacion anticipada, el sistema operativo intenta predecir las paginas que
69

necesitara un proceso y entonces carga dichas cuando hay espacio disponible. Mientras el proceso se ejecuta con sus paginas actuales, el sistema carga las demas paginas que estaran disponibles cuando las requiera el proceso. El S. O. intenta predecir las paginas que un proceso va a necesitar y a continuacion precarga estas paginas cuando hay espacio disponible Mientras el proceso ejecuta sus paginas actuales, el sistema carga paginas nuevas que estaran disponibles cuando el proceso las pida, debido a ello, el tiempo de ejecucion de un proceso se puede reducir.

3.4.5 Liberacin de pagina

Qu es la paginacin anticipada? En la paginacion anticipada, el sistema operativo intenta predecir las paginas que necesitara un proceso y entonces carga dichas cuando hay espacio disponible. Mientras el proceso se ejecuta con sus paginas actuales, el sistema carga las demas paginas que estaran disponibles cuando las requiera el proceso. El S. O. intenta predecir las paginas que un proceso va a necesitar y a continuacion precarga estas paginas cuando hay espacio disponible Mientras el proceso ejecuta sus paginas actuales, el sistema carga paginas nuevas que estaran disponibles cuando el proceso las pida, debido a ello, el tiempo de ejecucion de un proceso se puede reducir.

3.4.6 Tamao de la pagina

Generalmente el almacenamiento real se divide en marcos o celdas de pagina de tamano fijo. Los interrogantes tienen que ver con el tamano de las paginas, si todas las paginas tendran igual tamano, si en caso de utilizar paginas de diferente tamano las paginas mayores deben ser o no multiplos enteros de las menores, etc. Algunas consideraciones para determinar el tamano de pagina son las siguientes:

Cuanto mas pequeno sea el tamano de una pagina, mas paginas y marcos de paginas habra y mayores seran las tablas de pagina.

El desperdicio de almacenamiento debido al tamano excesivo de las tablas de pagina se llama fragmentacion de tablas. Esto indica la necesidad de paginas mas grandes.

Con paginas grandes, grandes cantidades de informacion que nunca llegaria a ser referenciada, se paginaran hacia el almacenamiento primario

70

Esto indica la necesidad de paginas mas pequenas.

UNIDAD 4 Administracin de Entrada/Salida

4.1 Dispositivos y manejadores de dispositivos
Dispositivos de entrada/salida Se pueden clasificar en dos grandes categoras: 1. Dispositivos de bloque 2. Dispositivos de carcter Las principales caractersticas de los dispositivos de bloque son: La informacin se almacena en bloques de tamao fijo. Cada bloque tiene su propia direccin. - Los tamaos ms 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 dems, en cualquier momento. - Un ejemplo tpico de dispositivos de bloque son los discos. Las principales caractersticas de los dispositivos de carcter son: -La informacin se transfiere como un flujo de caracteres, sin sujetarse a una estructura de bloques. No se pueden utilizar direcciones. No tienen una operacin de busqueda. - Unos ejemplos tpicos de dispositivos de carcter son las impresoras de lnea, terminales, interfaces de una red, ratones, etc. Manejadores de Dispositivos Todo el cdigo que depende de los dispositivos aparece en los manejadores de dispositivos. (Ver figura 4.1.1)

71

Figura Cada controlador posee uno o ms registros de dispositivos:

4.1.1

Se utilizan para darle los comandos. Los manejadores de dispositivos proveen estos comandos y verifican su ejecucin 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 ejecucin de dichas solicitudes.

Si al recibir una solicitud el manejador est ocupado con otra solicitud, agregara la nueva solicitud a una cola de solicitudes pendientes. La solicitud de e / s, por ej. para un disco, se debe traducir de trminos abstractos a trminos concretos:

El manejador de disco debe: (ver figura 4.1.2)

o o o o

Estimar el lugar donde se encuentra en realidad el bloque solicitado. Verificar si el motor de la unidad funciona. Verificar si el brazo esta colocado en el cilindro adecuado, etc. Resumiendo: debe decidir cuales son las operaciones necesarias del

72

controlador y su orden.
o

Enva los comandos al controlador al escribir en los registros de dispositivo del mismo. Frecuentemente el manejador del dispositivo se bloquea hasta que el controlador realiza cierto trabajo; una interrupcin lo libera de este bloqueo. Al finalizar la operacin debe verificar los errores. Si todo esta o.k. transferir los datos al software independiente del dispositivo. Regresa informacin de estado sobre los errores a quien lo llamo. Inicia otra solicitud pendiente o queda en espera.

o o

o o

Figura 4.1.2

73

4.2 Funciones de los manejadores de dispositivos

Funciones de los manejadores de dispositivos Funciones generalmente realizadas por el software independiente del dispositivo:

Interfaz uniforme para los manejadores de dispositivos. Nombres de los dispositivos. Proteccin del dispositivo. Proporcionar un tamao de bloque independiente del dispositivo. Uso de buffer. Asignacin de espacio en los dispositivos por bloques. Asignacin y liberacin de los dispositivos de uso exclusivo. Informe de errores.

Las funciones bsicas del software independiente del dispositivo son:

Efectuar las funciones de e / s comunes a todos los dispositivos. Proporcionar una interfaz uniforme del software a nivel usuario.

El software independiente del dispositivo asocia los nombres simblicos de los dispositivos con el nombre adecuado. Un nombre de dispositivo determina de manera nica el nodo-i de un archivo especial:

Este nodo-i contiene el nmero principal del dispositivo, que se utiliza para localizar el manejador apropiado. El nodo-i contiene tambin el nmero secundario de dispositivo, que se transfiere como parmetro al manejador para determinar la unidad por leer o escribir.

El software independiente del dispositivo debe:

Ocultar a los niveles superiores los diferentes tamaos de sector de los distintos discos. Proporcionar un tamao uniforme de los bloques, por ej.: considerar varios sectores fsicos como un solo bloque lgico.

74

4.3 Estructura de datos para manejo de dispositivos

Qu es una estructura? Los sistemas operativos actuales son grandes y complejos, estos deben poseer una ingeniera correcta para su fcil actualizacin y para que puedan cumplir su funcin correctamente. La estructura es generalmente modular, cada modulo cumple una funcin determinada e interacta con los dems mdulos. Estructura simple El sistema MS-DOS es, sin duda, el mejor sistema operativo para microcomputadoras. Sin embargo, sus interfaces y niveles de funcionalidad no estn bien definidos. Los programas de aplicacin pueden acceder a operaciones bsicas de entrada / salida para escribir directamente en pantalla o discos. Este libre acceso, hace que el sistema sea vulnerable, ya que un programa de aplicacin puede eliminar por completo un disco rgido por alguna falla. Adems este sistema, tambin esta limitado al hardware sobre el que corre. Otra estructura simple es la utilizada por la versin original de UNIX, esta consiste de dos partes separadas, el kernel y los programas de sistemas . El kernel fue posteriormente separado en manejadores (drivers) de dispositivos y una serie de interfaces. El kernel provee el sistema de archivos, la programacin de CPU, el administrador de memoria y otras funciones del sistema operativo que responden a las llamadas del sistema enunciadas anteriormente. Estructura por capas (layers) Las nuevas versiones de UNIX se disearon para hardware mas avanzado. Para dar mayor soporte al hardware, los sistemas operativos se dividieron en pequeas partes. Ahora los sistemas operativos tienen mayor control sobre el hardware y las aplicaciones que se ejecutan sobre este. La modularizacion de un sistema se puede presentar de varias formas, la mas utilizada es la de capas, la cual consiste en dividir al sistema operativo en un numero de capas. La capa de menor nivel es el hardware y la de mayor nivel es la interfaz con el usuario. La principal ventaja es que cada capa cumple con una serie de funciones y servicios que brinda a las otras capas, esto permite una mejor organizacin del sistema operativo y una depuracin mas fcil de este. Cada capa se implementa solo utilizando las operaciones provistas por la capa de nivel inferior. Una capa no necesita saber como se implementan estas funciones, solo necesita saber que operaciones puede realizar.

4.4 Operaciones de entrada/salida

75

Funciones

que

realizan

Vamos a sealar las funciones que debe realizar un computador para ejecutar trabajos de entrada/salida: - Direccionamiento o seleccin del dispositivo que debe llevar a cabo la operacin E/S. - Transferencia de los datos entre el procesador y el dispositivo (en uno u otro sentido). Sincronizacin y coordinacin de las operaciones. Esta ultima funcin es necesaria debido a la deferencia de velocidades entre los dispositivos y la CPU y a la independencia que debe existir entre los perifricos y la CPU (por ejemplo, suelen tener relojes diferentes). de Se define una transferencia elemental de informacin como la transmisin de una sola unidad de informacin (normalmente un byte) entre el procesador y el perifrico o viceversa. Para efectuar una transferencia elemental de informacin son precisas las siguientes funciones: - Establecimiento de una comunicacin fsica entre el procesador y el perifrico para la transmisin de la unidad de informacin. - Control de los perifricos, en que se incluyen operaciones como prueba y modificacin del estado del perifrico. Para realizar estas funciones la CPU gestionara las lneas de control necesarias. Definiremos una operacin de E/S como el conjunto de acciones necesarias para la transferencia de un conjunto de datos (es decir, una transferencia completa de datos). Para la realizacin de una operacin de E/S se deben efectuar las siguientes funciones: - Recuento de las unidades de informacin transferidas (normalmente bytes) para reconocer el fin de operacin. - Sincronizacin de velocidad entre la CPU y el perifrico. - Deteccin de errores (e incluso correccin) mediante la utilizacin de los cdigos necesarios (bits de paridad, cdigos de redundancia cclica, etc.) - Almacenamiento temporal de la informacin. Es ms eficiente utilizar un buffer temporal especfico para las operaciones de E/S que utilizan el rea de datos del programa. - Conversin de cdigos , conversin serie/paralelo, etc.

UNIDAD 5 Sistemas de Archivos

76

5.1 Concepto de Sistema de archivos

Concepto 1: Son los algoritmos y estructuras lgicas utilizadas para poder acceder a la informacin que tenemos en el disco. Cada uno de los sistemas operativos crea estas estructuras y logaritmos de diferente manera independientemente del hardware. El desempeo de nuestro disco duro, la confiabilidad, seguridad, capacidad de expansin y la compatibilidad, estar en funcin de estas estructuras lgicas. Fat 12: Es el sistema de archivos de DOS, y es con el que formateamos los disquetes. Fue muy utilizado en las primeras PCs. Fat 16: Este sistema de archivos tenia muchas limitaciones, por ejemplo si el disco duro era mayor de 2 GB, era imposible particionarlos y no usaba nombre largos en los archivos, solo 8 caracteres. Fat 32: Fue utilizado a partir de 1997, y pudo ser utilizado en Windows 98, pero a medida que el tamao de los discos duros se incrementaba, surgieron nuevas limitaciones. Se llamo Fat32, por que utiliza nmeros de 32 bits para representar a los clusters en lugar de los 16 en los sistemas anteriores. NTFS

Fig. 5.1.1 Archivos NTFS Especialmente creado para usarlo en Windows NT, es mas complejo que los FAT. El propsito era satisfacer la demanda y necesidades de de seguridad y eficacia para servidores y otras aplicaciones en red. No tiene limitaciones de tamao clusters y en general en el disco. Una ventaja de este sistema de archivos es que tiene un sistema antifragmentacin. Linux:

77

Fig. 5.1.2 Logo Linux Este sistema de archivos trabaja de manera totalmente distinta, las particiones del disco se colocan en el directorio raz. Podemos incluso tener diferentes particiones y cada una de ellas tener su propio sistema de archivos. Concepto 2 : En computacin, un sistema de archivos es un mtodo para el almacenamiento y organizacin de archivos de computadora y los datos que estos contienen, para hacer ms fcil la tarea encontrarlos y accederlos. Los sistemas de archivos son usados en dispositivos de almacenamiento como discos duros y CD-ROM e involucran el mantenimiento de la localizacin fsica de los archivos. Ms formalmente, un sistema de archivos es un conjunto de tipo de datos abstractos que son implementados para el almacenamiento, la organizacin jerrquica, la manipulacin, el acceso, el direccionamiento y la recuperacin de datos. Los sistemas de archivos comparten mucho en comn con la tecnologa de las bases de datos. Los sistemas de archivos pueden ser representados de forma textual (ej.: el shell de DOS) o grficamente (ej.: Explorador de archivos en Windows) utilizando un gestor de archivos. El software del sistema de archivos se encarga de organizar los archivos (que suelen estar segmentados fsicamente en pequeos bloques de pocos bytes) y directorios, manteniendo un registro de qu bloques pertenecen a qu archivos, qu bloques no se han utilizado y las direcciones fsicas de cada bloque. Los sistemas de archivos pueden ser clasificados en tres categoras: sistemas de archivo de disco, sistemas de archivos de red y sistemas de archivos de propsito especial. Ejemplos de sistemas de archivos son: FAT, UMSDOS, NTFS, UDF, ext2, ext3, ext 4, ReiserFS, XFS, etc. Concepto 3 :

78

Fig. 5.1.3 Administracin de archivos por el sistema operativo Los archivos son administrados por el sistema operativo como se muestra en la Fig. 5.1.3. Su estructura, nombre, forma de acceso, uso, proteccin e implantacin son temas fundamentales en el diseo de un sistema operativo. Aquella parte del sistema operativo que trabaja con los archivos se conoce, como un todo, como el sistema de archivos. Concepto 4 : Debido a su importancia, es necesario que un sistema operativo tenga la capacidad de leer, escribir, acceder y mantener la integridad de un sistema de archivos. Un sistema de archivos provee al usuario con una abstraccin que le permitir crear con facilidad colecciones de datos llamados archivos. Estas colecciones debern tener los siguientes requisitos o propiedades:

Existencia a largo tiempo: Los archivos debern ser almacenados sobre una unidad de almacenamiento y debern permanecer all aun cuando el usuario

79

apague el ordenador.

Debern tener la capacidad de ser compartidos: Los archivos tendrn nombres que los identifique y debern poseer permisos de acceso los cuales permitirn el compartimiento controlado entre procesos. Debern poseer una estructura definida: Dependiendo del tipo de sistema de archivos, un archivo deber poseer una estructura definida y conveniente; permitiendo que los archivos puedan ser organizados en orden jerrquico o en cualquier otro orden para reflejar su relacin con otros archivos.

El sistema de archivos como hemos dicho, posee una abstraccin que permite realizar varias operaciones sobre los archivos. Entre estas operaciones tenemos:

Crear un archivo: El usuario o un proceso podr crear un nuevo archivo el cual tomar una posicin dentro de la estructura del sistema de archivos. Borrar un archivo: Un archivo podr ser borrado de la estructura. Abrir un archivo: Un proceso podr abrir un archivo permitiendo el acceso a la informacin contenida por dicho archivo. El proceso podr ejecutar varias funciones sobre la informacin del archivo como leer, escribir, reemplazar, etc. Cerrar un archivo: Un proceso puede cerrar el archivo dejando atrs los privilegios de acceder a dicho archivo. Leer: Un proceso podr leer parte de la informacin contenida en un archivo Escribir: Un proceso podr aadir o reemplazar informacin en un archivo.

Los sistemas de archivos tambin mantienen una estructura de atributos asociada con cada uno de los archivos la cual provee informacin sobre la situacin actual de un archivo, quien es su dueo, el tamao del archivo, cuando fue creado, cuando fue modificado, privilegios de acceso, entre otros. Funciones del Sistema de Archivos.

80

Fig. 5.1.4 Manipulacin de archivos. Los usuarios deben poder crear, modificar y borrar archivos como se muestra en la Fig. 5.1.4. Se deben poder compartir los archivos de una manera cuidadosamente controlada. El mecanismo encargado de compartir los archivos debe proporcionar varios tipos de acceso controlado:

Ej.: Acceso de Lectura , Acceso de Escritura , Acceso de Ejecucin , varias combinaciones de estos, etc.

Se debe poder estructurar los archivos de la manera ms apropiada a cada aplicacin. Los usuarios deben poder ordenar la transferencia de informacin entre archivos. Se deben proporcionar posibilidades de respaldo y recuperacin para prevenirse contra:

La prdida accidental de informacin. La destruccin maliciosa de informacin.

Se debe poder referenciar a los archivos mediante Nombres Simblicos , brindandoIndependencia de Dispositivos . En ambientes sensibles, el sistema de archivos debe proporcionar posibilidades de Cifrado yDescifrado. El sistema de archivos debe brindar una interfase favorable al usuario:

Debe suministrar una visin lgica de los datos y de las funciones que sern ejecutadas, en vez de una visin fsica. El usuario no debe tener que preocuparse por:
o

Los dispositivos particulares.

81

o o o

Dnde sern almacenados los datos. El formato de los datos en los dispositivos. Los medios fsicos de la transferencia de datos hacia y desde los dispositivos.

5.2 Archivos reales y virtuales

Archivo Virtual y Archivo Real

Un archivo virtual (Fig.5.2.1), es un archivo de uso temporal que es utilizado por los procesos del sistema mientras se estn ejecutando dichos procesos. Estos archivos se crean durante la ejecucin de un sistema y los utiliza para el almacenamiento de informacin, intercambio y organizacin mientras se ejecuta el sistema (Fig. 5.2.2), su tamao es muy variable y terminan al detener la ejecucin del sistema, muchos de ellos son borrados, por ejemplo, los archivos *.tmp(Fig. 5.2.3) . Se le conoce como archivo virtual, aquel que contiene los datos generados por el usuario.

Fig.5.2.1 Archivo virtual

Fig. 5.2.2 Ejecucin del proceso

Fig. 5.2.3 Archivos temporales(*.tmp) Archivo Real (Fig. 5.2.4) : Es un objeto que contiene programas, datos o cualquier otro elemento. Un archivo se muestra de manera real, en la informacin del espacio que ocupa en un disco duro o sistema de almacenamiento, en otras palabras su tamao en bytes.

82

Fig. 5.2.4 Ejemplos de archivos reales

5.3 Componentes de un sistema de archivos

Lo conforman todas aquellas rutinas encargadas de administrar todos los aspectos relacionados con el manejo de Archivos. En UNIX se define un File System como un sistema de software dedicado a la creacin, destruccin, organizacin y lectura, escritura y control de acceso de los archivos, funcionalmente los componentes de un sistema de archivos son lenguajes de comandos, interpretador de comandos, manejador del almacenamiento secundario, sistema de entrada y salida y mecanismos de respaldo y recuperacin. En general, un Sistema de Archivos est compuesto por: Mtodos De Acceso, Administracin De Archivos, Administracin De Almacenamiento Secundario, Mecanismos De Integridad. Mtodos De Acceso. Se ocupan de la manera en que se tendr acceso a la informacin almacenada en el archivo. Ejemplo: Secuencial, Directo, indexado, etc. Administracin De Archivos. Se ocupa de ofrecer los mecanismos para almacenar, compartir y asegurar archivos, as como para hacer referencia a ellos. Administracin De Almacenamiento Secundario. Se ocupa de asignar espacio para los archivos en los dispositivos de almacenamiento secundario. En la siguiente figura se muestra un ejemplo de la administracin de espacio en un disco duro.

83

Fig.5.3.1 Administracin de almacenamiento en un disco duro. Mecanismos De Integridad. Se ocupan de garantizar que no se corrompa la informacin de un archivo, de tal manera que solo la informacin que deba estar en el, se encuentre ah. Mecanismos de Organizacin Lgica. Contiene las diferentes rutinas y comandos a travs de los cuales el usuario podr estructurar sus archivos virtuales. Directorio de Identificadores. Convierte los identificadores simblicos de los archivos en identificadores internos, los cuales apuntarn a su descriptor o a una estructura que permite encontrar el archivo. Sistemas Tericos de Archivos. Su objetivo es el de activar y desactivar a travs de las rutinas de abrir y cerrar archivos y verifica el modo de acceso. Mecanismos de Organizacin Fsica. Traslada las direcciones lgicas en direcciones fsicas correspondientes a las estructuras de memoria secundaria y los buffers en memoria principal necesarios para la transferencia de datos. Mecanismos de E/S. Por cada peticin de acceso al archivo real, este mecanismo genera la secuencia de operaciones elementales de entrada y salida que se necesita. SCHEDULING E/S. En este nivel es donde se tiene el nmero de peticiones pendientes as como de las que se estn realizando y lleva el control y asignacin de tiempo de CPU a las diferentes peticiones de E/S.

84

Fig. 5.3.2 Ejemplo de un scheduling.

5.4 Organizacin de Archivos

Se refiere a las diferentes maneras en las que puede ser organizada la informacin de los archivos, as como las diferentes maneras en que sta puede ser accesada. Dado que hay 2 niveles de visin de los archivos (fsico y lgico), se puede hablar tambin de 2 aspectos de organizacin de archivos: Organizacin de archivos lgicos y de archivos fsicos.

Fig. 5.4.1 Organizacin de un sistema de archivos utilizando directorios.

85

El sistema de archivos est relacionado especialmente con la administracin del espacio de almacenamiento secundario, fundamentalmente con el almacenamiento de disco. Una forma de organizacin de un sistema de archivos puede ser la siguiente:

Se utiliza una raz para indicar en qu parte del disco comienza el directorio raz . El directorio raz apunta a los directorios de usuarios. Un directorio de usuario contiene una entrada para cada uno de los archivos del usuario. Cada entrada de archivo apunta al lugar del disco donde est almacenado el archivo referenciado.

Esta forma de organizacin se muestra en la Fig. 5.4.1. 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 jerrquicos el nombre del sistema para un archivo suele estar formado como el nombre de la trayectoria del directorio raz al archivo. Organizacin lgica. La mayora de las computadoras organizan los archivos en jerarquas llamadas carpetas, directorios o catlogos . (El concepto es el mismo independientemente de la terminologa usada.) Cada carpeta puede contener un nmero arbitrario de archivos, y tambin puede contener otras carpetas. Las otras carpetas pueden contener todava ms archivos y carpetas, y as sucesivamente, construyndose un estructura en rbol en la que una carpeta raz (el nombre vara de una computadora a otra) puede contener cualquier nmero de niveles de otras carpetas y archivos. A las carpetas se les puede dar nombre exactamente igual que a los archivos (excepto para la carpeta raz, que a menudo no tiene nombre). El uso de carpetas hace ms fcil organizar los archivos de una manera lgica. La mayor parte de las estructuras de organizaciones alternativas de archivos se encuentran dentro de estas cinco categoras: Pilas

86

Fig. 5.4.2 Archivo de pilas:Registro de longitud variable. Conjunto variable de campos. Orden cronologico. Es la forma ms fcil de organizar un archivo. Los datos se recogen en el orden en que llegan. Su objetivo es simplemente acumular una masa de datos y guardarla. Los registros pueden tener campos diferentes o similares en un orden distinto. Cada campo debe ser autodescriptivo, incluyendo tanto un campo de nombre como el valor. La longitud de cada campo debe indicarse implcitamente con delimitadores, explcitamente incluidos como un subcampo ms. El acceso a los registros se hace por bsquedas exhaustiva y son fciles de actualizar. Si se quiere encontrar un registro que contiene un campo particular y un valor determinado, es necesario examinar cada registro de la pila hasta encontrar el registro deseado. Si se quieren encontrar todos los registros que contienen un campo particular o que tienen un valor determinado para ese campo, debe buscarse el archivo entero. Se aplica cuando los datos se recogen o almacenan antes de procesarlos o cuando no son fciles de organizar. Esta clase de archivo aprovecha bien el espacio cuando los datos almacenados varan en tamao y estructura. Fuera de estos usos limitados, este tipo de archivos no se adapta a la mayora de las aplicaciones. Archivos secuenciales

Fig. 5.4.3 Archivo secuencial: Registro de longitud fija. Conjunto fijo de campos en orden constante. Orden secuencial por el campo clave. Es la forma ms comn de estructura de archivos. Se emplea un formato fijo para los registros, son de la misma longitud y constan del

87

mismo nmero de campos de tamao fijo con un orden determinado. Se necesita almacenar los valores de cada campo; el nombre del campo y la longitud de cada uno son atributos de la estructura del archivo. Cada registro tiene un campo clave que lo identifica (generalmente es el primero de cada registro). Los registros se almacenan en secuencia por la clave. Se utilizan normalmente en aplicaciones de procesos por lotes, ya que es la nica organizacin de archivos que se puede guardar tanto en cintas como en discos. Para las aplicaciones interactivas que incluyen peticiones o actualizaciones de registros individuales, los archivos secuenciales no son ptimos. El acceso requiere una bsqueda secuencial de correspondencias con la clave. Si el archivo entero o gran parte de l pueden traerse a la memoria principal de una sola vez, se podrn aplicar tcnicas de bsquedas ms eficientes. Al acceder un registro de un archivo secuencial grande, se produce un procesamiento extra y un retardo considerable. La organizacin fsica del archivo en una cinta o disco se corresponde exactamente con la organizacin lgica del archivo, por lo tanto el procedimiento habitual es ubicar los nuevos registros en un archivo de pila separado, es llamado archivo de registro o archivo de transacciones . Una alternativa es organizar fsicamente el archivo secuencial como una lista enlazada, en cada bloque fsico se almacena uno o ms registros y cada bloque del disco contiene un puntero al bloque siguiente. La insercin de un nuevo registro implica la manipulacin de puntero, pero no requiere que el nuevo registro ocupe una posicin particular del bloque fsico. Archivos secuenciales indexados

Fig. 5.4.4 Archivo secuancial indexado. Los registros se organizan en una secuencia basada en un campo clave presentando dos caractersticas, un ndice del archivo para soportar los accesos aleatorios y un archivo de desbordamiento. El ndice proporciona una capacidad de bsqueda para llagar rpidamente al registro deseado y el archivo de desbordamiento es similar al archivo de registros usado en un archivo secuencial, pero est integrado de forma que

88

los archivos de desbordamiento se ubiquen siguiendo un puntero desde su registro predecesor. La estructura ms simple tiene como ndice un archivo secuencial simple, cada registro del archivo ndice tiene dos campos, un campo clave igual al del archivo principal y un puntero al archivo principal. Para encontrar un campo especifico se busca en el ndice hasta encontrar el valor mayor de la clave que es iguale o precede al valor deseado de la clave, la bsqueda continua en el archivo principal a partir de la posicin que indique el puntero. Cada registro del archivo principal tiene un campo adicional que es un puntero al archivo de desbordamiento. Cuando se inserta un nuevo registro al archivo, tambin se aade al archivo de desbordamiento. El registro del archivo principal que precede inmediatamente al nuevo registro segn la secuencia lgica se actualiza con un puntero del registro nuevo en el archivo de desbordamiento, si el registro inmediatamente anterior est tambin en el archivo de desbordamiento se actualizar el puntero en el registro. Para procesar secuencialmente un archivo completo los registros del archivo principal se procesarn en secuencia hasta encontrar un puntero al archivo de desbordamiento, el acceso continua en el archivo de desbordamiento hasta que encuentra un puntero nulo, entonces renueva el acceso donde se abandon en el archivo principal. Archivos indexados

Fig. 5.4.5 Archivo indexado. A los registros se accede solo a travs de sus ndices. No hay resticcin en la ubicacin de los registros, al menos un ndice contiene un puntero a cada registro y pueden emplearse registros de longitud variable. Se suelen utilizar dos tipos de ndices, uno exhaustivo que contiene una entrada para cada registro del archivo principal y se organiza como un archivo secuencial para

89

facilitar la bsqueda, el otro ndice es parcial que contiene entrada a los registros donde est el campo de inters. Con registro de longitud variable, algunos registros no contendrn todos los campos y cuando se aade un registro al archivo principal, todos los archivos de ndices deben actualizarse. Archivos directos o de dispersin Explotan la capacidad de los discos para acceder directamente a cualquier bloque de direccin conocida. Se requiere un campo clave en cada registro. Los archivos directos son muy usados donde se necesita un acceso muy rpido, donde se usan registros de longitud fija y donde siempre se accede a los registros de una vez. Organizacin fsica. Los datos son arreglados por su adyacencia fsica, es decir, de acuerdo con el dispositivo de almacenamiento secundario. Los registros son de tamao fijo o de tamao variable y pueden organizarse de varias formas para constituir archivos fsicos. Cinta magntica.

Fig. 5.4.6 Cintas magnticas En este dispositivo el archivo fsico esta formado por un conjunto de registros fsicos, y los bloques estn organizados en forma consecutiva, ya que se asigna en igual forma. Adems tales registros puede contener etiquetas que permitan un mayor control sobre los datos almacenados, y son las siguientes: - Etiqueta de volumen.- Contiene informacin que permite identificar la cinta, el nombre del propietario y cualquier informacin general requerida. - Etiqueta de archivo.- Se utilizan por pares para indicar el inicio y fin del archivo, contiene informacin acerca del nombre del archivo, fecha de creacin. - Etiqueta de usuario.- Sirven para guardar informacin adicional de importancia para el usuario; no son procesados por el sistema operativo.

90

Discos Magnticos.

Fig. 5.4.7 Discos magnticos El archivo fsico en un disco es una coleccin de registros fsicos de igual tamao, los cuales pueden estar organizados en forma consecutiva, ligada o con una tabla de mapeo. En la organizacin contigua, el archivo utiliza registros fsicos contiguos, siguiendo la secuencia normal de direcciones. La organizacin encadenada consiste un conjunto de bloques, cada uno de los cuales tiene un campo destinado para indicar la direccin del siguiente registro, o sea, para lo que se ha llamado enlace o liga. Otra forma de organizacin es la tabla de mapeo que consiste en una tabla de apuntadores a los registros fsicos que forman el archivo. La organizacin fsica de un archivo en el almacenamiento secundario depende de la estrategia de agrupacin y de la estrategia de asignacin de archivos. Para elegir una organizacin de archivos se deben tener en cuenta ciertos criterios: Si un archivo va a procesar solamente por lotes, accediendo cada vez a todos los registros, entonces el acceso rpido para la recuperacin de un nico registro es una preocupacin mnima. Un archivo almacenado en CD-ROM nunca ser actualizado, por lo que la facilidad de actualizacin no se considera. Para la economa de almacenamiento , debera existir una mnima redundancia de los datos, sta redundancia es el medio fundamental para incrementar la velocidad de acceso a los datos. Este tipo de organizacin muestra a su vez, 2 aspectos importantes: Mtodos De Asignacin De Espacio Libre y Asignacin De Espacio De Almacenamiento Del Archivo. METODOS DE ASIGNACION DE ESPACIO LIBRE Un mtodo de asignacin de espacio libre determina la manera en que un Sistema Operativo controla los lugares del disco que no estn siendo ocupados. Para el control del espacio libre se puede utilizar como base alguno de los mtodos tericos: Vector de Bits, Lista Ligada, Por Agrupacion y por Contador.

91

VECTOR DE BITS Se tiene un arreglo de bits, el nmero de bits que tiene, representa cada sector del disco, o sea que si los sectores 10 y 11 estn ocupados su representacion ser:

Fig. 5.4.8 Ejemplo de un vector de bits. LISTA LIGADA Existe una cabeceraen la que se tiene la direccion del primer sector vacio, ese sector a su vez, tiene un apuntador al siguiente bloque, y as sucesivamente hasta que se encuentre una marca indicando que ya no hay espacio libre, tal y como se muestra en la siguiente figura.

Fig. 5.4.9 Ejemplo de una lista ligada POR AGRUPACION Es similar a la lista ligada, solo que en este se tiene por cada sector, un grupo de apuntadores a varios espacios vacios, al final de cada bloque se tiene un apuntador a otro grupo de apuntadores, observe la figura.

92

Fig. 5.4.10 Ejemplo de asignacin por agrupacin. POR CONTADOR Aqui, por cada conjunto de bloques contiguos que estn vacios, se tiene por cada apuntador, un nmero de inicio y el tamao del grupo de sectores vacios.

93

Fig. 5.4.11 Ejemplo de asignacin por contador.

MTODOS DE ASIGNACIN DE ESPACIO EN DISCO. Un mtodo de asignacin de espacio en disco determina la manera en que un Sistema Operativo controla los lugares del disco ocupados por cada archivo de datos. Se debe controlar bsicamente la identificacin del archivo, sector de inicio y sector final. Para el control del espacio ocupado en disco se puede utilizar como base alguno de los mtodos tericos: Asignacin Contigua, Asignacin Ligada, Asignacin Indexada. ASIGNACIN CONTIGUA. Este mtodo consiste en asignar el espacio en disco de tal manera que las direcciones de todos losbloques correspondientes a un archivo definen un orden lineal. Por ejemplo:

94

Fig. 5.4.12 Ejemplo de asignacin contigua. VENTAJAS DESVENTAJAS

- La cabeza de lectura no se mueve - Produce fragmentacin externa. demasiado en la lectura de un archivo. ASIGNACIN LIGADA En este mtodo, cada archivo es una lista ligada de bloques de disco. En el directorio hay un apuntador al bloque de inicio y un apuntador al bloque final para cada archivo. En cada uno de los bloques donde se encuentra un archivo hay un apuntador al siguiente bloque de la lista. Por ejemplo:

95

Fig. 5.4.13 Ejemplo de asignacin ligada VENTAJAS - No produce fragmentacin externa. DESVENTAJAS

La cabeza de lectura se puede mov demasiado en la lectura de un archivo.

- Si una liga se pierde, se perder el archiv completo.

Es ineficiente para la implementacin d archivos directos. Se necesita un campo extra para apuntador.

ASIGNACIN INDEXADA Como ya se vio, la asignacin ligada resuelve problemas de fragmentacin externa, sin embargo, laasignacin ligada no soporta eficientemente el acceso directo a los archivos. La asignacin indexada resuelve este problema poniendo todos los apuntadores en una sola localidad: El bloque ndice . Cada archivo tiene su bloque ndice, El cual es un arreglo de direcciones de bloques de disco.

96

La i-sima entrada en el bloque ndice apunta al i-simo bloque que conforma el archivo. En el directorio se controla la direccin del bloque ndice de cada archivo, por ejemplo:

Fig. 5.4.14 Ejemplo de asignacin indexada. VENTAJAS

DESVENTAJAS

No produce fragmentacin externa. Eficiente para la implementacin de archivos directos.

Existe desperdicio cuando hay archivos m chicos.

Desbordamiento de bloque ndice. (Soluci creacin de un esquema ligado; el ultim bloque ndice apunta a otro ndice) .

97

5.5 Mecanismos de acceso a los archivos

Existen varios mecanismos para acceder los archivos: Directorios, descriptores de archivos, mecanismos de control de acceso y procedimientos para abrir y cerrar archivos. Descriptores de archivos. El descriptor de archivos o bloque de control de archivos es un bloque de control que contiene informacin que el sistema necesita para administrar un archivo. Es una estructura muy dependiente del sistema. Puede incluir la siguiente informacin:

Nombre simblico del archivo. Localizacin del archivo en el almacenamiento secundario. Organizacin del archivo (mtodo de organizacin y acceso). Tipo de dispositivo. Datos de control de acceso. Tipo (archivo de datos, programa objeto, programa fuente, etc.). Disposicin (permanente contra temporal). Fecha y tiempo de creacin. Fecha de destruccin. Fecha de la ltima modificacin. Suma de las actividades de acceso (nmero de lecturas, por ejemplo).

Los descriptores de archivos suelen mantenerse en el almacenamiento secundario; se pasan al almacenamiento primario al abrir el archivo. El descriptor de archivos es controlado por el sistema de archivos ; el usuario puede no hacer referencia directa a l. A cada uno de los archivos se le asigna un descriptor el cual contendr toda la informacin que necesitar el sistema de archivos para ejecutar con l los comandos que se le soliciten. El descriptor se mantendr en memoria principal desde que el archivo es abierto hasta que sea cerrado, y debe tener al menos la siguiente informacin, identificacin del archivo, lugar de almacenamiento, informacin del modo de acceso. Identificacin del archivo. Consiste de dos partes que es el nombre simblico que es el que le da el usuario y un identificador interno que es asignado por el sistema operativo

98

(nmero). Lugar de almacenamiento as como el tamao del archivo. Modo de acceso. Se debe indicar en forma explcita quien puede accesar el archivo y conque derecho.

Fig. 5.5.1 Ejemplo ilustrativo del control de acceso Mecanismo de control de acceso. Control de un sistema de informacin especializado en detectar los intectos de acceso, permitiendo el paso de las entidades autorizadas, y denegando el paso a todas las dems. Involucra medios tcnicos y procedimientos operativos. Mecanismo que en funcin de la identificacin ya autenticada permite acceder a datos o recursos. Los Directorios son utilizados por el sistema operativo para llevar un registro de los archivos que incluye el nombre, los atributos y las direcciones en disco donde se almacenan los datos del archivo referenciado.

Open (abrir): antes de utilizar un archivo, un proceso debe abrirlo. La finalidad es permitir que el sistema traslade los atributos y la lista de direcciones en disco a la memoria principal para un rpido 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.

5.6 Manejo de espacio en memoria secundaria

A diferencia de la Memoria Principal la Memoria Secundaria , auxiliar, masiva, externa no es tan veloz pero tiene gran capacidad para almacenar informacin en dispositivos tales como discos, cintas magnticas, discos pticos. Frecuentemente los datos y programas se graban en la Memoria Secundaria , de esta forma, cuando se ejecuta varias veces un programa o se utilicen repetidamente unos datos, no es necesario darlos de nuevo a travs del dispositivo de entrada.

99

Fig. 5.6.1 Ejemplos de Memoria Secundaria

En la Memoria Secundaria un archivo consta de un conjunto de bloques (correspondiente a la cantidad de informacin que se transfiere fsicamente en cada operacin de acceso (lectura o escritura). El Sistema Operativo o Sistema de Gestin de Archivos es el encargado de la asignacin de bloques a archivos, de lo que surgen dos cuestiones, en primer lugar, debe asignarle el espacio de Memoria Secundaria a los archivos y, en segundo lugar, es necesario guardar constancia del espacio disponible para asignar. El sistema de archivos se ocupa primordialmente de administrar el espacio de almacenamiento secundario, sobre todo el espacio en disco. El manejo del espacio libre en disco se lleva a cabo de la siguiente manera: Vector de bits Lista ligada (lista libre) Por conteo (agrupacin) Vector de bits. El espacio libre en disco es frecuentemente implementado como un mapa de bits, donde cada block es representado por un bit y si el bloc es libre el bit es cero de lo contrario est asignado.11000111 Lista ligada. Una lista ligada de todos los blocks libres. Otra implantacin se consigue guardando la direccin del primer block libre y el nmero de los blocks libres contiguos que le siguen. Cada entrada de la lista de espacio libre consiste de una direccin de disco y un contador (por conteo).

100

Fig. 5.6.2 Lista de espacio libre enlazada en el disco.

Por agrupacin. Se almacena la direccin en n blocks libres en el primer block libre y el ltimo contiene la direccin de otro block que contiene la direccin de otros blocks libres. Para manejar los espacios en disco existen los siguientes mtodos: ? Contiguos ? Ligados ? Indexados ? Contiguos. Esta asignacin requiere que cada archivo ocupe un conjunto de direcciones contiguas en el disco, su asignacin es definida por la direccin del primer bloc y la longitud del archivo. Cuando se crea un archivo se le asigna un nico conjunto contiguo de bloques, esta es un estrategia de asignacin previa que emplea secciones de tamao variable. La tabla de asignacin de archivos necesita solo una entrada por cada archivo y que muestre el bloque de comienzo y la longitud del archivo. La asignacin contigua es la mejor para un archivo secuencial.
101

La asignacin contigua presenta algunos problemas, como la fragmentacin externa. Lo que hace difcil encontrar bloques contiguos de espacio de tamao suficiente., lo que lleva a ejecutar un algoritmo de compactacin para libera el espacio adicional en el disco. ? Asignacin ligada o encadenada. Cada archivo es una lista ligada de blocks y el directorio contiene un apuntador al primer bloc y al ltimo. La asignacin se hace con bloques individuales, cada bloque contendr un puntero al siguiente bloque de la cadena. La tabla de asignacin de archivos necesita una sola entrada por cada archivo que muestre el bloque de comienzo y la longitud del mismo, cualquier bloque puede aadirse a la cadena. No hay que preocuparse por la fragmentacin externa porque solo se necesita un bloque cada vez. Una consecuencia del encadenamiento es que no hay cabida para el principio de cercana, si es necesario traer varios bloques de un archivo al mismo tiempo, se necesita una serie de accesos a partes diferentes del disco por lo que se debe ejecutar un algoritmo de compactacin para liberar el espacio adicional en el disco. ? Asignacin Indexada. Cada archivo tiene su propio bloc de ndice el cual es un arreglo de direcciones de bloc. En esta asignacin la tabla de asignacin de archivos contiene un ndice separado de un nivel para cada archivo: el ndice posee una entrada para cada seccin asignada al archivo. Normalmente, los ndices no estn almacenados fsicamente como parte de la tabla de asignacin de archivos. Mas exactamente el ndice de archivo se guardara en un bloque aparte y la entrada del archivo en la entrada de asignacin apuntara a dicho bloque. La asignacin puede hacerse por bloques de tamao fijo, O en secciones de tamao variable. La asignacin por bloques elimina la fragmentacin externa, mientras que la asignacin por secciones de tamao variable mejora la cercana. En cualquier caso, los archivos pueden concentrarse en zonas cercanas de cuando en cuando. La concentracin reduce el tamao del ndice en el caso de secciones de tamao variable, pero no en el caso de asignacin por bloques. La asignacin indexada soporta tanto el acceso secuencial como el acceso directo a los archivos y por ello se ha convertido en la forma ms popular de asignacin de archivos. En un sistema de cmputo, los elementos que se declaran para almacenamiento son los Fyle System. Cundo existe una solicitud de almacenamiento o manejo de bloc libres en un file system surge una interrogante cmo atenderlas? esto se lleva a cabo mediante una planificacin de discos y para esto existen las siguientes polticas de planificacin. a) FCFS

102

b) SSTF c) SCAN d) SCAN de n-pasos e) C-SCAN f) Esquema Eschenbach

5.7 Modelo jerrquico

Directorios

El directorio contiene un conjunto de datos por cada archivo referenciado.

Fig. 5.7.1 Ejemplo de directorio jerrquico 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:

El nombre del archivo. Un apuntador a otra estructura de datos donde se encuentran los atributos y las, direcciones en disco.

103

Fig. 5.7.2 Representacin grfica de un directorio jerrquico. Al abrir un archivo el S. O.:

Busca en su directorio el nombre del archivo. Extrae los atributos y direcciones en disco. Graba esta informacin en una tabla de memoria real. Todas las referencias subsecuentes al archivo utilizarn la informacin de la memoria principal.

El nmero y organizacin de directorios vara de sistema en sistema:

Directorio nico: el sistema tiene un solo directorio con todos los archivos de todos los usuarios (ver Figura 5.7.3). Un directorio por usuario: el sistema habilita un solo directorio por cada usuario (ver Figura 5.7.4). Un rbol de directorios por usuario: el sistema permite que cada usuario tenga tantos directorios como necesite, respetando una jerarqua general (ver Figura 5.7.5).

104

Fig. 5.7.3 Un solo directorio compartifo por todos los usuarios

Fig. 5.7.4 Un directorio por usuario

105

Fig. 5.7.5 Un rbol arbitrario por usuario

5.8 Mecanismo de recuperacin en caso de falla

Recuperacin Los archivos y directorios se mantienen tanto en memoria principal como en disco, y debe tener. Se cuidado para que los fallos del sistema no provoquen una prdida de datos o una incoherencia en los mismos. Comprobacin de coherencia. Como hemos explicado en la Seccin 11.3, parte de la informacin de directorios se almacena en la memoria principal (o en cach) para acelerar el acceso. La informacin de directorios en11a memoria principal est, generalmente, ms actualizada que la correspondiente informacin en el disco, porque la informacin de directorios almacenada en cach no se escribe necesariamente en el disco nada ms producirse la actualizacin. Considere, entonces, el posible ejemplo de un fallo de la computadora. El contenido de la cach y de los bferes, as como de las operaciones de E/S que se estuvieran realizando en ese momento, pueden perderse, y con l se perdern los cambios realizados en los directorios correspondientes a los archivos abiertos. Dicho suceso puede dejar el sistema de archivos en un estado incoherente. El estado real de algunos archivos no ser el que se describe en la estructura de directorios. Con frecuencia, suele ejecutarse un programa especial durante el reinicio para comprobar las posibles incoherencias del disco y corregidas. El comprobador de coherencia (un programa del sistema tal como fsck en UNIX o

106

chkdsk en MS-DOS), compara los datos de la estructura de directorios con los bloques de datos del disco y trata de corregir todas las incoherencias que detecte. Los algoritmos de asignacin y de gestin del espacio libre dictan los tipos de problemas que el comprobador puede tratar de detectar y dictan tambin el grado de xito que el comprobador puede tener en esta tarea. Por ejemplo, si se utiliza un sistema de asignacin enlazada y existe un enlace entre cada bloque y el siguiente, puede reconstruirse el archivo completo a partir de los bloques de datos y volver a crear la estructura de directorios. Por el contrario, la prdida de una entrada de directorio en un sistema de asignacin indexada puede ser desastrosa, porque los bloques de datos no tienen ningn conocimiento acerca de los dems bloques de datos del archivo. Por esta razn, UNIX almacena en cach las entradas de directorio para las lecturas, pero todas las escrituras de datos que provoquen algn cambio en la asignacin de espacio o en algn otro tipo de metadato se realizan sncronamente, antes de escribir los correspondientes bloques de datos. Por supuesto, tambin pueden aparecer problemas si se interrumpe una escritura sncrona debido a un fallo catastrfico.

Fig. 5.8.1 Errores La perdida de la informacin es uno de los factores que se le debe de dar mayor importancia, por la sencilla razn de que al perder informacin se puede perder lo que no nos podemos imaginar en cuanto a la misma y ocasionar perdidas hasta hablar de una gran cantidad de dinero. Para solucionar este o estos problemas todo sistema operativo cuenta con al menos una herramienta de software que nos permite recuperar informacin perdida hasta cierta medida, esto obedece de acuerdo al dao causado o los daos. Si el sistema no cuenta con la herramienta necesaria, deber adquirirse el software apropiado de algn fabricante especializado en el ramo, por ejemplo Norton. Es necesario proteger la informacin alojada en el sistema de archivos, efectuando los resguardos correspondientes. De esta manera se evitan las consecuencias generalmente catastrficas de la prdida de los sistemas de archivos. Las prdidas se pueden deber a problemas de hardware, software, hechos externos, etc. Manejo de un bloque defectuoso:

107

Se utilizan soluciones por hardware y por software. La solucin en hardware:

Consiste en dedicar un sector del disco a la lista de bloques defectuosos. Al inicializar el controlador por primera vez:
o o o o

Lee la lista de bloques defectuosos. Elige un bloque (o pista) de reserva para reemplazar los defectuosos. Registra la asociacin en la lista de bloques defectuosos. En lo sucesivo, las solicitudes del bloque defectuoso utilizarn el de repuesto.

La solucin en software:

Requiere que el usuario o el sistema de archivos construyan un archivo con todos los bloques defectuosos. Se los elimina de la lista de bloques libres. Se crea un archivo de bloques defectuosos:
o o o

Esta constituido por los bloques defectuosos. No debe ser ledo ni escrito. No se debe intentar obtener copias de respaldo de este archivo.

Respaldos (copias de seguridad o de back-up):

Fig. 5.8.2 Es necesario realizar respaldos para asegurar informacin Es muy importante respaldar los archivos con frecuencia. Los discos magnticos fallan en ocasiones y es necesario tener cuidado para garantizar que los datos perdidos debido a esos fallos no se pierdan para siempre. Con este fin, pueden utilizarse programas del sistema para realizar una copia de seguridad de los datos del disco en otro dispositivo de almacenamiento, como por ejemplo un disquete, una cinta magntica, un disco ptico incluso otro disco duro. La recuperacin
108

de la prdida de un archivo individual o de un disco completo puede ser entonces, simplemente, una cuestin de restaurar los datos a partir de la copia de seguridad. Los respaldos pueden consistir en efectuar copias completas del contenido de los discos (flexibles o rgidos). Una estrategia de respaldo consiste en dividir los discos en reas de datos y reas de respaldo , utilizndolas de a pares:

Se desperdicia la mitad del almacenamiento de datos en disco para respaldo. Cada noche (o en el momento que se establezca), la parte de datos de la unidad 0 se copia a la parte de respaldo de la unidad 1 y viceversa.

Otra estrategia es el vaciado por incrementos o respaldo incremental :

Se obtiene una copia de respaldo peridicamente (por ej.: una vez por mes o por semana), llamada copia total. Se obtiene una copia diaria solo de aquellos archivos modificados desde la ltima copia total; en estrategias mejoradas, se copian solo aquellos archivos modificados desde la ltima vez que dichos archivos fueron copiados. Se debe mantener en el disco informacin de control como una lista de los tiempos de copiado de cada archivo, la que debe ser actualizada cada vez que se obtienen copias de los archivos y cada vez que los archivos son modificados. Puede requerir una gran cantidad de cintas de respaldo dedicadas a los respaldos diarios entre respaldos completos.

Para minimizar la cantidad de datos que haya que copiar, podemos utilizar la informacin contenida en la entrada de directorio de cada archivo. Por ejemplo, si el programa de copia de seguridad sabe cundo se realiz la ltima copia de seguridad de un archivo y la fecha de ltima modificacin del archivo contenida en el directorio indica que el archivo no ha cambiado desde esa fecha, no ser necesario volver a copiar el archivo. As un plan tpico de copia de seguridad podra ser el siguiente: Da 1. Copiar en el soporte de copia de seguridad todos los archivos del disco. Esto se denomina copia de seguridad completa. Da 2. Copiar en otro soporte fsico todos los archivos que se hayan modificado desde el da 1. Esta es una copia de seguridad incremental. Da 3. Copiar en otro soporte fsico todos los archivos que se hayan modificado desde el da 2. Da N. Copiar en otro soporte fsico todos los archivos que se hayan modificado desde el da N - 1. Despus, volver al da 1. Podemos escribir las copias de seguridad correspondientes al nuevo ciclo sobre el

109

conjunto anterior de soportes fsicos o en un nuevo conjunto de soportes de copia de seguridad. De esta forma, podemos restaurar un disco completo comenzando la restauracin con la copia de seguridad completa y continuando con cada una de las copias de seguridad incrementales. Por supuesto, cuanto mayor sea el valor de N, ms cintas o discos habr que leer para efectuar una restauracin completa. Una ventaja adicional de este ciclo de copia de seguridad es que podemos restaurar cualquier archivo que haya sido borrado accidentalmente durante ese ciclo, extrayendo el archivo borrado de la copia de seguridad del da anterior. La longitud del ciclo ser un compromiso entre la cantidad de soportes fsicos de copia de seguridad requeridos y el nmero de das pasados a partir de los cuales podamos realizar una restauracin. Para reducir el nmero de cintas que haya que leer para efectuar una restauracin, una opcin consiste en realizar una copia de seguridad completa y luego copiar cada da todos los archivos que hayan cambiado desde la ltima copia de seguridad completa. De esta forma, puede realizarse la restauracin utilizando slo la copia de seguridad incremental ms reciente y la copia de seguridad completa, no necesitndose ninguna otra copia de seguridad incremental. El compromiso inherente a este sistema es que el nmero de archivos modificado se incrementa a diario, por lo que cada copia de seguridad incremental sucesiva contiene ms archivos y requiere ms espacio en el soporte de copia de seguridad. Consistencia del sistema de archivos: Muchos sistemas de archivos leen bloques, los modifican y escriben en ellos despus. Si el sistema falla antes de escribir en los bloques modificados, el sistema de archivos puede quedar en un estado inconsistente. La inconsistencia es particularmente crtica si alguno de los bloques afectados son:

Bloques de nodos-i. Bloques de directorios. Bloques de la lista de bloques libres.

La mayora de los sistemas dispone de un programa utilitario que verifica la consistencia del sistema de archivos:

Se pueden ejecutar al arrancar el sistema o a pedido. Pueden actuar sobre todos o algunos de los discos. Pueden efectuar verificaciones a nivel de bloques y a nivel de archivos. La consistencia del sistema de archivos no asegura la consistencia interna de cada archivo, respecto de su contenido. Generalmente pueden verificar tambin el sistema de directorios y / o de bibliotecas.

110

Generalmente los utilitarios utilizan dos tablas:

Tabla de bloques en uso. Tabla de bloques libres. Cada bloque debe estar referenciado en una de ellas.

Si un bloque no aparece en ninguna de las tablas se trata de una falla llamada bloque faltante:

No produce daos pero desperdicia espacio en disco. Se soluciona aadiendo el bloque a la tabla de bloques libres.

Tambin podra detectarse la situacin de falla debida a un bloque referenciado dos veces en la tabla de bloques libres:

Esta falla no se produce en los sistemas de archivos basados en mapas de bits, s en los basados en tablas o listas. La solucin consiste en depurar la tabla de bloques libres.

Una falla muy grave es que el mismo bloque de datos aparezca referenciado dos o ms veces en la tabla de bloques en uso:

Como parte del mismo o de distintos archivos. Si uno de los archivos se borra, el bloque aparecera en la tabla de bloques libres y tambin en la de bloques en uso. Una solucin es que el verificador del sistema de archivos:
o o o o o

Asigne un bloque libre. Copie en el bloque libre el contenido del bloque conflictivo. Actualice las tablas afectando el bloque copia a alguno de los archivos. Agregue el bloque conflictivo a la tabla de bloques libres. Informe al usuario para que verifique el dao detectado y la solucin dada.

Otro error posible es que un bloque est en la tabla de bloques en uso y en la tabla de bloques libres:

Se soluciona eliminndolo de la tabla de bloques libres.

Las verificaciones de directorios incluyen controles como:

Nmero de directorios que apuntan a un nodo-i con los contadores de enlaces almacenados en los propios nodos-i; en un sistema consistente de archivos

111

deben coincidir. Una posible falla es que el contador de enlaces sea mayor que el nmero de entradas del directorio:

Aunque se eliminaran todos los archivos de los directorios el contador sera distinto de cero y no se podra eliminar el nodo-i. No se trata de un error serio pero produce desperdicio de espacio en disco con archivos que no se encuentran en ningn directorio. Se soluciona haciendo que el contador de enlaces en el nodo-i tome el valor correcto; si el valor correcto es 0, el archivo debe eliminarse.

Otro tipo de error es potencialmente catastrfico:

Si dos entradas de un directorio se enlazan a un archivo, pero el nodo-i indica que solo existe un enlace, entonces, al eliminar cualquiera de estas entradas de directorio, el contador del nodo-i tomar el valor 0. Debido al valor 0 el sistema de archivos lo seala como no utilizado y libera todos sus bloques. Uno de los directorios apunta hacia un nodo-i no utilizado, cuyos bloques se podran asignar entonces a otros archivos. La solucin es forzar que el contador de enlaces del nodo-i sea igual al nmero de entradas del directorio.

Tambin se pueden hacer verificaciones heursticas , por ej.:

Cada nodo-i tiene un modo, pero algunos modos son vlidos aunque extraos:
o

Ej.: Se prohibe el acceso al propietario y todo su grupo, pero se permite a los extraos leer, escribir y ejecutar el archivo. La verificacin debera detectar e informar de estas situaciones.

Se debera informar como sospechosos aquellos directorios con excesivas entradas, por ej., ms de mil.

Unidad 6 Proteccin y Seguridad

112

6.1 Concepto y objetivo de proteccin

La proteccion es un mecanismo control de acceso de los programas, procesos o usuarios al sistema o recursos. Hay importantes razones para proveer proteccion. La mas obvia es la necesidad de prevenirse de violaciones intencionales de acceso por un usuario. Otras de importancia son, la necesidad de asegurar que cada componente de un programa, use solo los recursos del sistema de acuerdo con las politicas fijadas para el uso de esos recursos. Un recurso desprotegido no puede defenderse contra el uso no autorizado o de un usuario incompetente. Los sistemas orientados a la proteccion proveen maneras de distinguir entre uso autorizado y desautorizado. Objetivos Inicialmente proteccion del SO frente a usuarios poco confiables. Proteccion: control para que cada componente activo de un proceso solo pueda acceder a los recursos especificados, y solo en forma congruente con la politica establecida. La mejora de la proteccion implica tambien una mejora de la seguridad. Las politicas de uso se establecen: Por el hardware. Por el administrador / SO. Por el usuario propietario del recurso. Principio de separacion entre mecanismo y politica: Mecanismo con que elementos (hardware y/o software) se realiza la proteccion. Politica es el conjunto de decisiones que se toman para especificar como se usan esos elementos de proteccion. La politica puede variar dependiendo de la aplicacion, a lo largo del tiempo. La proteccin no solo es cuestion del administrador, sino tambien del usuario. El sistema de proteccion debe: distinguir entre usos autorizados y no-autorizados. especificar el tipo de control de acceso impuesto.

113

 proveer medios para el aseguramiento de la proteccin.

6.2 Funciones del sistema de proteccin

Control de acceso que hace referencia a las caracteristicas de seguridad que controlan quien puede obtener acceso a los recursos de un sistema operativo. Las aplicaciones llaman a las funciones de control de acceso para establecer quien puede obtener acceso a los recursos especificos o controlar el acceso a los recursos proporcionados por la aplicacion. Un sistema de proteccion debera tener la flexibilidad suficiente para poder imponer una diversidad de politicas y mecanismos. Existen varios mecanismos que pueden usarse para asegurar los archivos, segmentos de memoria, CPU, y otros recursos administrados por el Sistema Operativo. Por ejemplo, el direccionamiento de memoria asegura que unos procesos puedan ejecutarse solo dentro de sus propios espacios de direccion. El timer asegura que los procesos no obtengan el control de la CPU en forma indefinida. La proteccion se refiere a los mecanismos para controlar el acceso de programas, procesos, o usuarios a los recursos definidos por un sistema de computacion. Seguridad es la serie de problemas relativos a asegurar la integridad del sistema y sus datos. Hay importantes razones para proveer proteccion. La mas obvia es la necesidad de prevenirse de violaciones intencionales de acceso por un usuario. Otras de importancia son, la necesidad de asegurar que cada componente de un programa, use solo los recursos del sistema de acuerdo con las politicas fijadas para el uso de esos recursos. Un recurso desprotegido no puede defenderse contra el uso no autorizado o de un usuario incompetente. Los sistemas orientados a la proteccion proveen maneras de distinguir entre uso autorizado y desautorizado. Mecanismos y Politicas El sistema de proteccion tiene la funcion de proveer un mecanismo para el fortalecimiento de las politicas que gobiernan el uso de recursos. Tales politicas se pueden establecer de varias maneras, algunas en el diseno del sistema y otras son formuladas por el administrador del sistema. Otras pueden ser definidas por los usuarios individuales para proteger sus propios archivos y programas. Las politicas son diversas, dependen de la aplicacion y pueden estar sujetas a cambios a lo largo del tiempo. Un principio importante es la separacion de politicas de los mecanismos. Los mecanismos determinan como algo se hara. Las politicas deciden que se hara'.

114

La separacion es importante para la flexibilidad del sistema. Dentro de las funciones del sistema de proteccion del sistema operativo encontramos:

Controlar el acceso a los recursos Asegurarse que todos los accesos a los recursos del sistema estan controlados

6.3 Implementacin de matrices de acceso

Los derechos de acceso definen que acceso tienen varios sujetos sobre varios objetos. Los sujetos acceden a los objetos. Los objetos son entidades que contienen informacion. Los objetos pueden ser:

Concretos:
o

Ej.: discos, cintas, procesadores, almacenamiento, etc.

Abstractos:
o

Ej.: estructuras de datos, de procesos, etc.

Los objetos estan protegidos contra los sujetos. Las autorizaciones a un sistema se conceden a los sujetos. Los sujetos pueden ser varios tipos de entidades:

Ej.: usuarios, procesos, programas, otras entidades, etc.

Los derechos de acceso mas comunes son:

Acceso de lectura. Acceso de escritura. Acceso de ejecucion.

Una forma de implementacion es mediante una matriz de control de acceso con:

Filas para los sujetos. Columnas para los objetos. Celdas de la matriz para los derechos de acceso que un usuario tiene a un objeto.

115

Una matriz de control de acceso debe ser muy celosamente protegida por el S. O. Dominios de proteccin Un sistema de computos contiene muchos objetos que necesitan proteccion. Estos objetos pueden ser el hardware, la CPU, los segmentos de memoria, terminales, unidades de disco o impresoras; o bien ser del software, como los proceso, archivos, bases de datos o semaforos. Cada objeto tiene un unico nombre mediante el cual se la hace referencia y un conjunto de operaciones que se pueden realizar en el. READ y WRITE son operaciones adecuadas para un archivo; UP y DOWN tiene sentido en un semaforo. Es evidente que se necesita una via para prohibir el acceso de los procesos a los objetos a los que no tiene permitido dicho acceso. Ademas, este mecanismo debe posibilitar la restriccion de los procesos a un subconjunto de operaciones legales en caso necesario. Por ejemplo, puede permitirse que el proceso A lea el archivo F, pero no escriba en el. Para tener una forma de analizar los distintos mecanismos de proteccion, es conveniente presentar el concepto de dominio. Un dominio es un conjunto de parejas (objeto, derechos). Cada pareja determina un objeto y cierto subconjunto de las operaciones que se pueden llevar a cabo en el. Un derecho es, en este contexto, el permiso para realizar alguna de las operaciones. Una pregunta importante es la forma en que el sistema lleva un registro de los objetos que pertenecen a un dominio dado. Al menos una teoria, uno puede imaginar una enorme matriz, en la que los renglones son los dominio y las columnas son los objetos. Cada cuadro contiene los derechos correspondientes al objeto en ese dominio. Con esta matriz y el numero de dominio activo, el sistema puede determinar si se permite el acceso de cierta forma a un objeto dado desde un domino especifico. Un dominio es un conjunto de parejas (objeto, derechos):

Cada pareja determina:

o o

Un objeto. Un subconjunto de las operaciones que se pueden llevar a cabo en el.

Un derecho es el permiso para realizar alguna de las operaciones. Es posible que un objeto se encuentre en varios dominios con distintos derechos en cada dominio. Un proceso se ejecuta en alguno de los dominios de proteccion:

Existe una coleccion de objetos a los que puede tener acceso. Cada objeto tiene cierto conjunto de derechos.

116

Los procesos pueden alternar entre los dominios durante la ejecucion. Una llamada al S. O. provoca una alternancia de dominio. En algunos S. O. los dominios se llaman anillos . Una forma en la que el S. O. lleva un registro de los objetos que pertenecen a cada dominio es mediante una matriz :

Los renglones son los dominios. Las columnas son los objetos. Cada elemento de la matriz contiene los derechos correspondientes al objeto en ese dominio, por ej.: leer, escribir, ejecutar.

Ver Figura 6.3.1

Fig. 6.3.1 Dominio de proteccin Matriz de acceso El modelo de proteccion del sistema se puede ver en forma abstracta como una matriz, la matriz de acceso. Una matriz de acceso es una representacion abstracta del concepto de dominio de proteccion. Este modelo fue propuesto por Lampson [4] como una descripcion generalizada de mecanismos de proteccion en sistemas operativos. Es el modelo mas utilizado, del que existen numerosas variaciones, especialmente en su implementacion.

117

Los elementos basicos del modelo son los siguientes:

Sujeto: Una entidad capaz de acceder a los objetos. En general, el concepto de sujeto es equiparable con el de proceso. Cualquier usuario o aplicacion consigue acceder en realidad a un objeto por medio de un proceso que representa al usuario o a la aplicacion. Objeto: Cualquier cosa cuyo acceso debe controlarse. Como ejemplo se incluyen los archivos, partes de archivos, programas y segmentos de memoria. Derecho de acceso: la manera en que un sujeto accede a un objeto. Como ejemplo estan Leer, Escribir y Ejecutar. El modelo considera un conjunto de recursos, denominados objetos, cuyo acceso debe ser controlado y un conjunto de sujetos que acceden a dichos objetos. Existe tambien un conjunto de permisos de acceso que especifica los diferentes permisos que los sujetos pueden tener sobre los objetos (normalmente lectura, escritura, etc., aunque pueden ser diferentes, en general, dependiendo de las operaciones que puedan realizarse con el objeto). Se trata de especificar para cada pareja (sujeto, objeto), los permisos de acceso que el sujeto tiene sobre el objeto. Esto se representa mediante una matriz de acceso M que enfrenta todos los sujetos con todos los objetos. En cada celda M[i, j] se indican los permisos de acceso concretos que tiene el sujeto i sobre el objeto j. La figura 6.3.2 representa una matriz de acceso, y la figura 6.3.3 es una matriz de acceso derivada de la figura 6.3.1 de dominios de proteccin.

Fig. 6.3.2 Representacin de una m atriz de acceso

118

Figura 6.3.3 Ejemplo de una matriz de acceso

El mecanismo de proteccion es la matriz, junto con todos los elementos que se han de anadir para que se cumplan de manera efectiva todas las restricciones de acceso a los objetos.

La politica consiste en decidir como rellenar las distintas celdas de la matriz. La MA permite implementar operaciones de cambio de domino. El objeto sobre el que trabajamos es el Dominio aparecen tantas columnas como dominios haya en el sistema. La operacion es la conmutacion de un dominio a otro. Tambien la MA es un objeto que se puede modificar. De este modo podemos definir tres operaciones: Copiar derechos de acceso de una celda a otra dentro de la misma columna. Consiste en pasar el derecho de acceso a un objeto de un Dominio que lo tiene, a otro donde originalmente no lo tenia. Se senala con un asterisco (*). Copia ilimitada con propagacion del propio derecho de copia. Copia limitada sin propagacion.

119

 Movimiento de derecho. Dueno. Un proceso ejecutandose en un dominio que tiene derecho de dueno sobre un objeto, puede repartir cualquier derecho de acceso sobre cualquier dominio para dicho objeto. Control . Opera solo sobre dominios. Ejercer el control sobre un dominio implica que se puede quitar cualquier derecho sobre una fila de dominio. La MA tambien ha de ser protegida. Implementacion de la Matriz de Acceso Tabla Global Sencilla. Se almacena una lista de ternas {<dominio, objeto, permisos>...}. Como el numero de objetos y dominios es posiblemente muy grande, se deberia guardar en memoria virtual lento. Ver fig. 6.3.4

Fig. 6.3.4 Ejemplo de una tabla global

Lista de acceso para objetos(ACL) Se expresa la MA por columnas {<dominio, permisos>, ...}. Se descartan las entradas vacias. Se puede crear una lista de permisos por defecto para hacer mas facil su uso. Dado que cada vez que se va a usar un objeto hay que comprobar si hay o no permiso para hacerlo, es logico poner la ACL alli donde esten descritos los atributos del objeto.

Asocia a cada objeto una lista ordenada con:

o o

Todos los dominios que pueden tener acceso al objeto. La forma de dicho acceso (ej: lectura (r), grabacion (w), ejecucion (x)).

Una forma de implementar las ACL consiste en:

Asignar tres bits (r, w, x) para cada archivo, para:

o

El propietario, el grupo del propietario y los demas usuarios.

120

Permitir que el propietario de cada objeto pueda modificar su ACL en cualquier momento:
o

Permite prohibir accesos antes permitidos.

Fig. 6.3.5 Ejemplo de una lista de accesos Lista de Capacidades Se expresa la MA por filas. Cada dominio tiene una lista de la forma {<objeto, permisos>, ...} Para identificar el objeto se usa o bien su nombre logico, o un puntero a el (la estructura de datos que le describe); a esta direccion se la llama capacidad . Solo se podra realizar la operacion M sobre el objeto O si se dispone de la capacidad (puntero) al objeto. Ver figura 6.3.6

121

Fig. 6.3.6 Ejmplo de una lista de capacidades

Mecanismo de Cerradura-Llave Cada objeto tiene una lista de patrones llamados cerradura . Cada dominio tiene una lista de patrones llamados claves . Un proceso que se ejecuta en un dominio solo tendra acceso a un objeto si el dominio contiene una llave que coincida con una de las cerraduras. Comparacion La tabla global es una matriz dispersa, es ineficiente para su almacenamiento. ACL Cuando se accede a un objeto es facil determinar si hay o no permiso para usarlo. Capacidades Las ACL estan distribuidas, es dificil saber cuales son los derechos de acceso para un proceso, cosa que si se puede hacer con la lista de capacidades. Los sistemas reales suelen usar una mezcla de todos. Ej. UNIX: Se abre un fichero, se verifica en la ACL si tiene permiso o no. Si lo tiene, se consigue un descriptor de fichero, es decir una capacidad que sera lo que se use a partir de entonces.

122

6.4 Proteccin basada en el lenguaje

Accedo al Sistema de Archivos Cuando se declaren los distintos tipos de datos, tambin se especificara la proteccin

6.5 Concepto de Seguridad

Los terminos seguridad y proteccion se utilizan en forma indistinta. Sin embargo, es util hacer una distincion entre los problemas generales relativos a la garantia de que los archivos no sea leidos o modificados por personal no autorizado, lo que incluye aspectos tecnicos, de administracion, legales y politicos, por un lado y los sistemas especificos del sistema operativo utilizados para proporcionar la seguridad, por el otro. Para evitar la confusion, utilizaremos el termino seguridad para referirnos al problema general y el termino mecanismo de proteccion para referirnos a los mecanismos especificos del sistema operativo utilizado para resguardar la informacion de la computadora. Sin embargo, la frontera entre ellos no esta bien definida. Primero nos fijaremos en la seguridad; mas adelante analizaremos la proteccion. La seguridad tiene muchas facetas. Dos de las mas importantes son la perdida de datos y los intrusos. Algunas de las causas mas comunes de la perdida de datos son: Actos divinos: Incendios, inundaciones, terremotos, guerras, revoluciones o ratas que roen las cintas o discos flexibles. errores de Hardware o Software: Mal funcionamiento de la CPU, discos o cintas ilegibles, errores de telecomunicacion o errores en el programa. Errores Humanos: Entrada incorrecta de datos, mal montaje de las cintas o el disco, ejecucion incorrecta del programa, perdida de cintas o discos. La mayoria de estas causas se pueden enfrentar con el mantenimiento de los respaldos adecuados; de preferencia, en un lugar alejado de los datos originales. Un problema mas interesante es que hacer con los intrusos. Estos tienen dos variedades. Los intrusos pasivos solo desean leer archivos que no estan autorizados a leer. Los intrusos activos son mas crueles: Desean hacer cambios no autorizados a los datos. Si se desea disenar un sistema seguro contra los intrusos, es importante tener en cuenta el tipo de intruso con el que se desea tener proteccion. Algunas de las categorias comunes son: Curiosidad casual de usuarios no tecnicos. Muchas personas tienen en sus escritorios terminales para sistemas con tiempo compartido y, por la naturaleza humana, algunos de ellos leeran el correo electronico de los demas u otros archivos, si no existen barreras en frente de ellos. Por ejemplo la mayoria de los sistema UNIS tienen pre definido que todos los archivos se pueden leer de manera publica.

123

 Conocidos husmeando. Algunos estudiantes, programadores de sistemas, operadores y demas personal tecnico consideran como un reto personal romper la seguridad del sistema de computo local. A menudo son muy calificados y estan dispuestos a invertir una cantidad sustancial de su tiempo en este esfuerzo. Un intento deliberado de hacer dinero. Algunos programadores en banco han intentado penetrar un sistema bancario con el fin de robarle al banco. Los esquemas han variado desde cambiar el software para truncar y no redondear el interes, para quedarse con una pequena fraccion de dinero, hasta sacar dinero de las cuentas que no se han utilizado en anos o el "correo negro" . Espionaje comercias o militar. El espionaje indica un intento serio y fundamentado por parte de un competidor u otro pais para robar programas, secretos comerciales, patentes, tecnologia, diseno de circuitos, planes de comercializacion, etc. A menudo, este intento implica la cobertura de cables o el levantamiento de antenas hacia la computadora con el fin de recoger su radiacion electromagnetica. Debe quedar claro que el intento por mantener la KGB lejos de los secretos militares es un poco distinto del intento por evitar que los estudiantes inserten un mensaje gracioso en el sistema. La cantidad de esfuerzo que alguien pone en la seguridad y la proteccion depende claramente de quien se piensa sea el enemigo. Otro aspecto del problema de la seguridad es la privacia: la proteccion de las personas respecto del mal uso de la informacion en contra de uno mismo. Esto implica en forma casi inmediata muchos aspectos morales y legales. Para proteger un sistema, debemos optar las necesarias medidas de seguridad en cuatro niveles distintos: 1. Fisico. El nodo o nodos que contengan los sistemas informaticos deben dotarse de medidas de seguridad fisicas frente a posibles intrusiones armadas o subrepticias por parte de potenciales intrusos. Hay que dotar de seguridad tanto a las habitaciones donde las maquinas residan como a los terminales o estaciones de trabajo que tengan acceso a dichas maquinas. 2. Humano. La autorizacion de los usuarios debe llevarse a cabo con cuidado, para garantizar que solo los usuarios apropiados tengan acceso al sistema. Sin embargo, incluso los usuarios autorizados pueden verse motivados para permitir que otros usen su acceso (por ejemplo, a cambio de un soborno). Tambien pueden ser enganados para permitir el acceso de otros, mediante tecnicas de ingenieria social . Uno de los tipos de ataque basado en las tecnicas de ingenieria social es el denominado phishing ; con este tipo de ataque, un correo electronico o pagina web de aspecto autentico llevan a engano a un usuario para que introduzca informacion confidencial. Otra tecnica comunmente utilizada es el analisis de desperdicios , un termino autorizado a la computadora (por ejemplo, examinando el contenido de las papeleras,

124

localizando listines de telefonos encontrando notas con contrasenas). Estos problemas de seguridad son cuestiones relacionadas con la gestion y con el personal, mas que problemas relativos a los sistemas operativos. 3. Sistema operativo. El sistema debe autoprotegerse frente a los diversos fallos de seguridad accidentales o premeditados. Un problema que este fuera de control puede llegar a constituir un ataque accidental de denegacion de servicio. Asimismo, una cierta consulta a un servicio podria conducir a la revelacion de contrasenas o un desbordamiento de la pila podria permitir que se iniciara un proceso no autorizado. La lista de posibles fallos es casi infinita. 4. Red. Son muchos los datos en los modernos sistemas informaticos que viajen a traves de lineas arrendadas privadas, de lineas compartidas como Internet, de conexiones inalambricas o de lineas de acceso telefonico. La interceptacion de estos datos podria ser tan danina como el acceso a un computador, y la interrupcion en la comunicacion podria constituir un ataque remoto de denegacion de servicio, disminuyendo la capacidad de uso del sistema y la confianza en el mismo por parte de los usuarios. Si queremos poder garantizar la seguridad del sistema operativo, es necesario garantizar la seguridad en los primeros dos niveles. Cualquier debilidad en uno de los niveles altos de seguridad (fisico o humano) podria puentear las medidas de seguridad que son estrictamente de bajo nivel (del nivel del sistema operativo). Asi, la frase que afirma que una cadena es tan fuerte como el mas debil de sus eslabones es especialmente cierta cuando hablamos de seguridad de los sistemas. Para poder mantener la seguridad, debemos contemplar todos estos aspectos. Ademas, el sistema debe proporcionar mecanismos de proteccion para permitir la implementacion de las caracteristicas de seguridad. Sin la capacidad de autorizar a los usuarios y procesos, de controlar su acceso y de registrar sus actividades, seria imposible que un sistema operativo implementara medidas de seguridad o se ejecutara de forma segura. Para soportar un esquema global de proteccion hacen falta mecanismos de proteccion hardware. Por ejemplo, un sistema donde la memoria no este protegida no puede nunca estar seguro.

6.6 Clasificaciones de la seguridad

La seguridad interna esta relacionada a los controles incorporados al hardware y al Sistema Operativo para asegurar los recursos del sistema. Seguridad Externa La seguridad externa consiste en:

Seguridad fisica.

125

Seguridad operacional.

La seguridad fisica incluye:

Proteccion contra desastres(como inundaciones, incendios, etc.). Proteccion contra intrusos.

En la seguridad fisica son importantes los mecanismos de deteccion , algunos ejemplos son:

Detectores de humo. Sensores de calor. Detectores de movimiento.

La proteccion contra desastres puede ser costosa y frecuentemente no se analiza en detalle; depende en gran medida de las consecuencias de la perdida. La seguridad fisica trata especialmente de impedir la entrada de intrusos:

Se utilizan sistemas de identificacion fisica:

o o o

Tarjetas de identificacion. Sistemas de huellas digitales. Identificacion por medio de la voz.

Seguridad Operacional Consiste en las diferentes politicas y procedimientos implementados administracion de la instalacion computacional. La autorizacion determina que acceso se permite y a quien. La clasificacion divide el problema en subproblemas:

por

la

Los datos del sistema y los usuarios se dividen en clases:

o

A las clases se conceden diferentes derechos de acceso.

Un aspecto critico es la seleccion y asignacion de personal:

La pregunta es si se puede confiar en la gente. El tratamiento que generalmente se da al problema es la division de responsabilidades:
o o

Se otorgan distintos conjuntos de responsabilidades. No es necesario que se conozca la totalidad del sistema para cumplir con esas responsabilidades.

126

Para poder comprometer al sistema puede ser necesaria la cooperacion entre muchas personas:

Se reduce la probabilidad de violar la seguridad.

Debe instrumentarse un gran numero de verificaciones y balances en el sistema para ayudar a la deteccion de brechas en la seguridad. El personal debe estar al tanto de que el sistema dispone de controles, pero:

Debe desconocer cuales son esos controles:

Se reduce la probabilidad de poder evitarlos.

Debe producirse un efecto disuasivo respecto de posibles intentos de violar la seguridad.

Para disenar medidas efectivas de seguridad se debe primero:

Enumerar y comprender las amenazas potenciales. Definir que grado de seguridad se desea (y cuanto se esta dispuesto a gastar en seguridad). Analizar las contramedidas disponibles.

6.7 Validacin
Identificar cada usuario que esta trabajando en el sistema (usando los recursos). Uso de contrasenas. Vulnerabilidad de contrasenas.
o o o

o Que sean complejas y dificiles de adivinar. o Cambiarlas de vez en cuando. o Peligro de perdida del secreto.

La contrasena debe guardare cifrada. Proteccion por Contrasea Las clases de elementos de autentificacion para establecer la identidad de una persona son: Algo sobre la persona:
o

Ej.: huellas digitales, registro de la voz, fotografia, firma, etc.

127

Algo poseido por la persona:

o

Ej.: insignias especiales, tarjetas de identificacion, llaves, etc.

Algo conocido por la persona:

o

Ej.: contrasenas, combinaciones de cerraduras, etc.

El esquema mas comun de autentificacion es la proteccion por contrasena: El usuario elige una palabra clave , la memoriza, la teclea para ser admitido en el sistema computarizado:
o

La clave no debe desplegarse en pantalla ni aparecer impresa.

La proteccion por contrasenas tiene ciertas desventajas si no se utilizan criterios adecuados para: Elegir las contrasenas.

Comunicarlas fehacientemente en caso de que sea necesario. Destruir las contrasenas luego de que han sido comunicadas. Modificarlas luego de algun tiempo.

Los usuarios tienden a elegir contrasenas faciles de recordar: Nombre de un amigo, pariente, perro, gato, etc.

Numero de documento, domicilio, patente del auto, etc.

Estos datos podrian ser conocidos por quien intente una violacion a la seguridad mediante intentos repetidos, por lo tanto debe limitarse la cantidad de intentos fallidos de acierto para el ingreso de la contrasena. La contrasena no debe ser muy corta para no facilitar la probabilidad de acierto. Tampoco debe ser muy larga para que no se dificulte su memorizacion, ya que los usuarios la anotarian por miedo a no recordarla y ello incrementaria los riesgos de que trascienda. Contraseas de un solo uso Al final de cada sesion, se le pide al usuario que cambie la contrasena. Si alguien roba una contrasena, el verdadero usuario se dara cuenta cuando vaya a identificarse de nuevo, pues el impostor habra cambiado la contrasena, con lo que el fallo de seguridad queda detectado. Verificacin de Amenazas Es una tecnica segun la cual los usuarios no pueden tener acceso directo a un

128

recurso : Solo lo tienen las rutinas del S. O. llamadas programas de vigilancia.

El usuario solicita el acceso al S. O. El S. O. niega o permite el acceso. El acceso lo hace un programa de vigilancia que luego pasa los resultados al programa del usuario. Permite:
o o

Detectar los intentos de penetracion en el momento en que se producen. Advertir en consecuencia.

Amenazas relacionadas con los programas Los procesos son junto con el kernel , el unico medio de realizar un trabajo util en una computadora. Por tanto, un objetivo comun de los piratas informaticos consiste en escribir un programa que cree una brecha de seguridad. De hecho, las mayorias de las brechas de seguridad no relacionadas con programas tienen por objetivos crear una brecha que si este basada en un programa. Por ejemplo, aunque resulta util iniciar una sesion en un sistema sin autorizacion, normalmente es mucho mas util dejar un demonio de tipo puerta trasera que proporcione informacion o que permita un facil acceso incluso aunque se bloquee la brecha de seguridad original. En esta seccion, vamos a describir algunos metodos comunes mediante los que os programas pueden provocar brechas de seguridad. Hay que resaltar que existe una considerable variacion en lo que respecta a los convenios de denominacion de los agujeros de seguridad, y que en este texto utilizamos los terminos mas comunes o descriptivos. - CABALLO DE TROYA

Definicion.- Un programa indudablemente util e inocente que contiene codigos escondidos que permiten la modificacion no autorizada y la explotacion o destruccion de la informacion. Los programas caballo de Troya se distribuyen por lo general por Internet. Los juegos, freeware y protectores de pantalla son los medios comunes que utilizan los caballos de Troya. Se denomina troyano (o caballo de Troya , traduccion mas fiel del ingles Trojan horse aunque no tan utilizada) a un programa malicioso capaz de alojarse en computadoras y permitir el acceso a usuarios externos, a traves de una red local o de

129

Internet, con el fin de recabar informacion o controlar remotamente a la maquina anfitriona. Un troyano no es de por si, un virus, aun cuando teoricamente pueda ser distribuido y funcionar como tal. La diferencia fundamental entre un troyano y un virus consiste en su finalidad. Para que un programa sea un "troyano" solo tiene que acceder y controlar la maquina anfitriona sin ser advertido, normalmente bajo una apariencia inocua. Al contrario que un virus, que es un huesped destructivo, el troyano no necesariamente provoca danos porque no es su objetivo. Suele ser un programa pequeno alojado dentro de una aplicacion, una imagen, un archivo de musica u otro elemento de apariencia inocente, que se instala en el sistema al ejecutar el archivo que lo contiene. Una vez instalado parece realizar una funcion util (aunque cierto tipo de troyanos permanecen ocultos y por tal motivo los antivirus o anti troyanos no los eliminan) pero internamente realiza otras tareas de las que el usuario no es consciente, de igual forma que el Caballo de Troya que los griegos regalaron a los troyanos. Habitualmente se utiliza para espiar, usando la tecnica para instalar un software de acceso remoto que permite monitorizar lo que el usuario legitimo de la computadora hace (en este caso el troyano es un spyware o programa espia) y, por ejemplo, capturar las pulsaciones del teclado con el fin de obtener contrasenas (cuando un troyano hace esto se le cataloga de keylogger) u otra informacion sensible. La mejor defensa contra los troyanos es no ejecutar nada de lo cual se desconozca el origen y mantener software antivirus actualizado y dotado de buena heuristica; es recomendable tambien instalar algun software anti troyano, de los cuales existen versiones gratis aunque muchas de ellas constituyen a su vez un troyano. Otra solucion bastante eficaz contra los troyanos es tener instalado un firewall. Otra manera de detectarlos es inspeccionando frecuentemente la lista de procesos activos en memoria en busca de elementos extranos, vigilar accesos a disco innecesarios, etc. Lo peor de todo es que ultimamente los troyanos estan siendo disenados de tal manera que es imposible poder detectarlos excepto por programas que a su vez contienen otro tipo de troyano, inclusive y aunque no confirmado, existen troyanos dentro de los programas para poder saber cual es el tipo de uso que se les y poder sacar mejores herramientas al mercado llamados tambien "troyanos sociales" Los troyanos estan actualmente ilegalizados, pero hay muchos crackers que lo utilizan. PUERTA TRASERA En la informatica, una puerta trasera (o en ingles backdoor ), es una secuencia especial dentro del codigo de programacion mediante el programador puede acceder o escapar de un programa en caso de emergencia o contingencia en algun problema.

130

A su vez, estas puertas tambien pueden ser perjudiciales debido a que los crackers al descubrirlas pueden acceder a un sistema en forma ilegal y aprovecharse la falencia. Cualquier medio capaz de ampliar el alcance del hombre es lo suficientemente poderoso como para derrocar su mundo. Conseguir que la magia de ese medio trabaje para los fines de uno, antes que en contra de ellos, es alcanzar el conocimiento. Alan Kay. Es extrana la ligereza con que los malvados creen que todo les saldra bien. Victor Hugo. A pesar de que no se consideran propiamente como virus, representan un riesgo de seguridad importante, y usualmente son desconocidas la inmensa gama de problemas que estas puedan llegar a producir. Al hablar de estas nos referimos genericamente a una forma "no oficial" de acceso a un sistema o a un programa. Algunos programadores dejan puertas traseras a proposito, para poder entrar rapidamente en un sistema; en otras ocasiones existen debido a fallos o errores. Ni que decir tiene que una de las formas tipicas de actuacion de los piratas informaticos es localizar o introducir a los diversos sistemas una puerta trasera y entrar por ella. El termino es adaptacion directa del ingles backdoor que comunmente significa puerta de atras. Lo usual en estos programas los cuales no se reproducen solos como los virus, sino que nos son enviados con el fin de tener acceso a nuestros equipos muchas veces a traves del correo electronico, por lo que la mayoria de las veces no son faciles de detectar y por si solos no siempre causan danos ni efectos inmediatos por su sola presencia, siendo asi pueden llegar a permanecer activos mucho tiempo sin que nos percatemos de ello. Generalmente estos se hacen pasar por otros, es decir, se ocultan en otro programa que les sirve de caballo de Troya para que el usuario los instale por error. Lo peor que puede pasarle cuando esta en el messanger o en el ICQ no es que contraiga su PC un virus. Lo peor es que alguien instale un backdoor en su PC. Las puertas traseras son faciles de entender. Como todo en Internet se basa en la arquitectura cliente / servidor, solo se necesita instalar un programa servidor en una maquina para poder controlarla a distancia desde otro equipo, si se cuenta con el cliente adecuado, esta puede bien ser la computadora de un usuario descuidado o poco informado. Las puertas traseras (backdoors) son programas que permiten acceso practicamente ilimitado a un equipo de forma remota. El problema, para quien quiere usar este ataque, es que debe convencerlo a usted de que instale el servidor.

131

Por eso, si aparece un desconocido ofreciendole algun programa maravilloso y tentador, no le crea de inmediato. Lo que estan probablemente a punto de darle es un troyano, un servidor que le proporcionara a algun intruso acceso total a su computadora. Con todo el riesgo que esto implica, hay una forma simple y totalmente segura de evitarlo: no acepte archivos ni mucho menos ejecute programas que le hayan mandado siendo estos sobre todo de procedencia dudosa. Los programas que se clasifican como backdoors o "puertas traseras" son utilerias de administracion remota de una red y permiten controlar las computadoras conectadas a esta. El hecho que se les clasifique como software malevolo en algunos casos, es que cuando corren, se instalan en el sistema sin necesidad de la intervencion del usuario y una vez instalados en la computadora, no se pueden visualizar estas aplicaciones en la lista de tareas en la mayoria de los casos. Consecuentemente un backdoor puede supervisar casi todo proceso en las computadoras afectadas, desinstalar programas, descargar virus en la PC remota, borrar informacion y muchas cosas mas. No es sencillo darle forma a un tema de esta complejidad en pocas lineas. Lo importante finalmente es comprender que si no se toman ciertas medidas minimas, la informacion sensible que se encuentre en cualquier equipo sobre la faz de la tierra, con el simple hecho de que tenga acceso a la red de redes (Internet) es suficiente para que pueda estar expuesto a ataques de diversa indole. Concluimos esto, recomendando ciertas medidas muy basicas para estar a salvo de las puertas traseras y el delicado riesgo para la seguridad que estas representan. A saber: 1.- Es recomendable asegurarnos de que cada cosa que ejecutamos este bajo nuestro control. Una buena guia para ello es el sentido comun (el menos comun de los sentidos). 2.- Procure no ejecutar programas de los que no sepamos su procedencia, tanto en anexos de correo, ICQ, messanger y descargas de Internet (ya sean via Web o FTP). 3.- La informacion nos protege. Es recomendable enterarse un poco de las noticias de virus y programas daninos relacionados, visitando por lo menos las paginas de las distintas empresas antivirus o suscribiendose a algunos boletines. 4.- Es necesario instalar un antivirus y mantenerlo actualizado. En la actualidad se protege al usuario no solo contra virus, sino tambien contra gusanos, programas de puerta trasera, troyanos y algunos programas maliciosos. 5.Es bueno tener presente que existen virus y troyanos que pueden

132

aparentar ser amigables (una simple tarjeta de San Valentin), o que provienen de gente que conoces (como es el caso del gusano Sircam). Siendo asi, no confies en ningun programa ni en nada que recibas hasta no revisarlo con el Antivirus. 6.- Mantenga al dia todas las actualizaciones de seguridad de Microsoft, para todas y cada una de las distintas aplicaciones -BOMBA LOGICA Este tipo de delito forma parte de los sistemas informaticos que realizan ataques a la parte logica del ordenador. Se entiendo por bomba logica (en ingles denominado time bombs), aquel software, rutinas o modificaciones de programas que producen modificaciones, borrados de ficheros o alteraciones del sistema en un momento posterior a aquel en el que se introducen por su creador. Los disparadores de estos programas puede ser varios, desde las fechas de los sistemas, realizar una determinada operacion o que se introduzca un determinado codigo que sera el que determine su activacion. Son parecidas al Caballo de Troya, aunque lo que se pretende es danar al sistema o datos, aunque se pueden utilizar para ordenar pagos, realizar transferencias de fondos, etc... Caracteristicas principales:

El tipo de actuacion es retardada. El creador es consciente en todo momento del posible dano que puede causar y del momento que este se puede producir. Este ataque esta determinado por una condicion que determina el creador dentro del codigo. El codigo no se replica. Los creadores de este tipo de codigos malignos suelen ser personal interno de la empresa, que por discrepancias con la direccion o descontento suelen programarlas para realizar el dano.

VIRUS

133

Un virus informatico es un programa que se copia automaticamente y que tiene por objeto alterar el normal funcionamiento de la computadora, sin el permiso o el conocimiento del usuario. Aunque popularmente se incluye al "malware" dentro de los virus, en el sentido estricto de esta ciencia los virus son programas que se replican y ejecutan por si mismos. Los virus, habitualmente, reemplazan archivos ejecutables por otros infectados con el codigo de este. Los virus pueden destruir, de manera intencionada, los datos almacenados en un ordenador, aunque tambien existen otros mas benignos, que solo se caracterizan por ser molestos. Los virus informaticos tienen, basicamente, la funcion de propagarse, replicandose, pero algunos contienen ademas una carga danina (payload) con distintos objetivos, desde una simple broma hasta realizar danos importantes en los sistemas, o bloquear las redes informaticas generando trafico inutil. El funcionamiento de un virus informatico es conceptualmente simple. Se ejecuta un programa que esta infectado, en la mayoria de las ocasiones, por desconocimiento del usuario. El codigo del virus queda residente (alojado) en la memoria RAM de la computadora, aun cuando el programa que lo contenia haya terminado de ejecutarse. El virus toma entonces el control de los servicios basicos del sistema operativo, infectando de, manera posterior, archivos ejecutables que sean llamados para su ejecucion. Finalmente se anade el codigo del virus al del programa infectado y se graba en disco, con lo cual el proceso de replicado se completa. Amenazas del Sistema y de la Red

Las amenazas basadas en programas utilizan tipicamente un fallo en los mecanismos de proteccion de un sistema para atacar a los programas. Por contraste, las amenazas del sistema y de la red implican el abuso de los servicios y de las conexiones de red. En ocasiones, se utiliza un ataque del sistema y de la red para lanzar un ataque de programa, y viceversa. Las amenazas del sistema y de la red crean una situacion en la que se utilizan inapropiadamente los recursos del sistema operativo y los archivos del usuario. En esta seccion vamos a analizar algunos ejemplos de estas amenazas, incluyendo los gusanos, el escaneo de puertos y los ataques por denegacion de servicio. Es importante destacar que las mascaradas y los ataques por reproduccion tambien resultan comunes en las redes que interconectan los sistemas. De hecho, estos ataques son mas efectivos y mas dificiles de contrarrestar cuando estan implicados multiples sistemas. Por ejemplo, dentro de una computadora, el sistema operativo

134

puede determinar, usualmente, el emisor y el receptor de un mensaje. Incluso si el emisor adopta el ID de alguna otra persona, puede que exista un registro de dicho cambio de ID. Cuando estan implicados multiples sistemas, especialmente sistemas que son controlados por los atacantes, realizar esa labor de traza resulta mucho mas dificil. La generalizacion de este concepto es que el compartir secretos (para demostrar la identidad y en forma de claves de cifrado) es una necesidad para la autenticacion del cifrado, y que esa comparticion resulta mas sencilla en aquellos entornos (por ejemplo con un unico sistema operativo) en los que existan metodos seguros de comparticion. Estos metodos incluyen la memoria compartida y los mecanismos de comunicacion interprocesos. GUSANOS

Un gusano es un virus informatico o programa auto replicante que no altera los archivos sino que reside en la memoria y se duplica a si mismo. Los gusanos utilizan las partes automaticas de un sistema operativo que generalmente son invisibles al usuario. Es algo usual detectar la presencia de gusanos en un sistema cuando, debido a su incontrolada replicacion, los recursos del sistema se consumen hasta el punto de que las tareas ordinarias del mismo son excesivamente lentas o simplemente no pueden ejecutarse. Un gusano, al igual que un virus, esta disenado para copiarse de un equipo a otro, pero lo hace automaticamente. En primer lugar, toma el control de las caracteristicas del equipo que permiten transferir archivos o informacion. Una vez que un gusano este en su sistema, puede viajar solo. El gran peligro de los gusanos es su habilidad para replicarse en grandes numeros. Por ejemplo, un gusano podria enviar copias de si mismo a todos los usuarios de su libreta de direcciones de correo electronico, lo que provoca un efecto domino de intenso trafico de red que puede hacer mas lentas las redes empresariales e Internet en su totalidad. Cuando se lanzan nuevos gusanos, se propagan muy rapidamente. Bloquean las redes y posiblemente provocan esperas largas (a todos los usuarios) para ver las paginas Web en Internet. Gusano Subclase de virus. Por lo general, los gusanos se propagan sin la intervencion del usuario y distribuye copias completas (posiblemente modificadas) de si mismo por las redes. Un gusano puede consumir memoria o ancho de banda de red, lo que puede provocar que un equipo se bloquee.

135

Debido a que los gusanos no tienen que viajar mediante un programa o archivo "host", tambien pueden crear un tunel en el sistema y permitir que otro usuario tome el control del equipo de forma remota. Entre los ejemplos recientes de gusanos se incluyen: Sasser y Blaster. -ESCANEO DE PUERTOS El escaneo de puertos es una de las mas populares tecnicas utilizadas para descubrir y mapear servicios que estan escuchando en un puerto determinado. Usando este metodo un atacante puede crear una lista de las potenciales debilidades y vulnerabilidades en un puerto para dirigirse a la explotacion del mismo y comprometer el host remoto Una de las primeras etapas en la penetracion / auditoria de un host remoto es primeramente componer una lista de los puertos abiertos utilizando una o mas de las tecnicas descritas abajo. Una ves establecida, los resultados ayudaran al atacante a identificar los servicios que estan corriendo en ese puerto utilizando una lista de puertos que cumplen con el RFC (la funcion /etc/services in UNIX, getservbyport() automaticamente hace esto) permitiendo comprometer el host remoto en la etapa de descubrimiento inicial. Las tecnicas de escaneo de puertos se dividen en tres tipos especificos y diferenciados: *.escaneo abierto *.escaneo medio abierto *.escaneo oculto Cada una de esas tecnicas permite un ataque para localizar puertos abiertos y cerrados en un servidor pero saber hacer el escaneo correcto en un ambiente dado depende de la topologia de la red, IDS, caracteristicas de logging del servidor remoto. Aunque un escaneo abierto deja bitacoras grandes y es facilmente detectable produce los mejores resultados en los puertos abiertos y cerrados. Alternativamente, utilizar un escaneo oculto permite evitar ciertos IDS y pasar las reglas del firewall pero el mecanismo de escaneo como packet flags utilizados para detectar estos puertos puede dejar muchos paquetes caidos sobre la red dando resultados positivos siendo estos falsos. Mas adelante se discutira esto en la seccion de escaneo FIN de este documento. Enfocandonos mas directamente en cada una de las tecnicas anteriores, estos metodos se pueden categorizar en tipos individuales de escaneo. Veamos un modelo basico de escaneo incluyendo un barrido de ping.

136

Fig. 6.7.1 Modelo basico de escaneo. -DENEGACION DE SERVICIO En seguridad informatica, un ataque de denegacion de servicio , tambien llamado ataque DoS(de las siglas en ingles Denial of Service ), es un ataque a un sistema de ordenadores o red que causa que un servicio o recurso sea inaccesible a los usuarios legitimos. Normalmente provoca la perdida de la conectividad de la red por el consumo del ancho de banda de la red de la victima o sobrecarga de los recursos computacionales del sistema de la victima. Se genera mediante la saturacion de los puertos con flujo de informacion, haciendo que el servidor se sobrecargue y no pueda seguir prestando servicios, por eso se le dice "denegacion", pues hace que el servidor no de abasto a la cantidad de usuarios. Esta tecnica es usada por los llamados crackers para dejar fuera de servicio a servidores objetivo. El llamado DDoS (siglas en ingles de Distributed Denial of Service , denegacion de servicio distribuida) es una ampliacion del ataque DoS, se efectua con la instalacion de varios agentes remotos en muchas computadoras que pueden estar localizadas en diferentes puntos. El invasor consigue coordinar esos agentes para asi, de forma masiva, amplificar el volumen del flood o saturacion de informacion, pudiendo darse casos de un ataque de cientos o millares de computadoras dirigido a una maquina o red objetivo. Esta tecnica se ha revelado como una de las mas eficaces y sencillas a la hora de colapsar servidores, la tecnologia distribuida ha ido sofisticandose hasta el punto de otorgar poder de causar danos serios a personas con escaso conocimiento tecnico. En ocasiones, esta herramienta ha sido utilizada como un notable metodo para

137

comprobar la capacidad de trafico que un ordenador puede soportar sin volverse inestable y perjudicar los servicios que desempena. Un administrador de redes puede asi conocer la capacidad real de cada maquina. Metodos de ataque Un ataque de "Denegacion de servicio" previene el uso legitimo de los usuarios al usar un servicio de red. El ataque se puede dar de muchas formas, como por ejemplo: Inundacion SYN (SYN Floods) La inundacion SYN envia un flujo de paquetes TCP/SYN, muchas veces con la direccion de origen falsificada. Cada unos de los paquetes recibidos es tratado por el destino como una peticion de conexion, causando que el servidor intente establecer una conexion al responder con un paquete TCP/SYN-ACK y esperando el paquete de respuesta TCP/ACK (Parte del proceso de establecimiento de conexion TCP de 3 vias). Sin embargo, debido a que la direccion de origen es falsa o la direccion IP real no ha solicitado la conexion, nunca llega la respuesta. Estas conexiones a medias consumen recursos en el servidor y limitan el numero de conexiones que se pueden hacer, reduciendo la disponibilidad del servidor para responder peticiones legitimas de conexion. Ataque LAND (LAND attack) Un ataque LAND se realiza al enviar un paquete TCP/SYN falsificado con la direccion del servidor objetivo como si fuera la direccion origen y la direccion destino a la vez. Esto causa que el servidor se responda a si mismo continuamente y al final falle. Inundacion ICMP (ICMP floods) Es una tecnica DoS que pretender agota el ancho de banda de la victima. Consiste en enviar de forma continuada un numero elevado de paquetes ICMP echo request (ping) de tamano considerable a la victima, de forma que esta ha de responder con paquetes ICMP echo reply (pong) lo que supone una sobrecarga tanto en la red como en el sistema de la victima. Dependiendo de la relacion entre capacidad de procesamiento de la victima y atacante, el grado de sobrecarga varia, es decir, si un atacante tiene una capacidad mucho mayor, la victima no puede manejar el trafico generado. Modelos de ataques Existe una variante denominada smurf que amplifica considerablemente los efectos de un ataque ICMP. En el smurf el atacante dirige paquetes ICMP echo request a una direccion IP de broadcast10. Existen tres partes en un ataque smurf: El atacante, el intermediario y la victima (comprobaremos que el intermediario tambien puede ser victima). Cuando el atacante genera el paquete ICMP echo request, este es dirigido a una

138

direccion IP de broadcast, pero la direccion origen del paquete IP la cambia por la direccion de la victima (IP spoofing), de manera que todas las maquinas intermediarias (maquinas pertenecientes a la red donde se envio el paquete) responden con ICMP echo reply a la victima. Como se dijo anteriormente, los intermediarios tambien sufren los mismos problemas que las propias victimas. Inundacion UDP (UDP floods) Basicamente este ataque consiste en generar grandes cantidades de paquetes UDP contra la victima elegida. Debido a la naturaleza sin conexion del protocolo UDP, este tipo de ataques suele venir acompanado de IP spoofing6. Es usual dirigir este ataque contra maquinas que ejecutan el servicio echo8 de forma que se generan mensajes echo de un elevado tamano.

6.7 Cifrado
Existen muchas defensas frente a los ataques informaticos, que abarcan toda la gama que va desde la metodologia a la tecnologia. La herramienta de caracter mas general que esta a disposicion de los usuarios y de los disenadores de sistemas es la criptografia. En esta seccion vamos a explicar algunos detalles acerca de la criptografia y de su uso en el campo de la seguridad informatica. En una computadora aislada, el sistema operativo puede determinar de manera fiable quienes son el emisor y el receptor de todas las comunicaciones interprocesos, ya que el sistema operativo controla todos los canales de comunicaciones de la computadora. En una red de computadoras, la situacion es bastante distinta. Una computadora conectada a la red recibe bits desde el exterior, y no tiene ninguna forma inmediata y fiable de determinar que maquina o aplicacion ha enviado esos bits. De forma similar, la propia computadora envia bits hacia la red sin tener ninguna forma de determinar quien puede llegar a recibirlos. Comunmente, se utilizan las direcciones de red para inferir los emisores y receptores potenciales de los mensajes que circulan por la red. Los paquetes de red llegan con una direccion de origen, como por ejemplo una direccion IP. Y cuando una computadora envia mensajes, indica quinen es el receptor pretendido del mismo especificando una direccion de destino. Sin embargo, para aquellas aplicaciones en que la seguridad tenga importancia, correriamos el riesgo de meternos en problemas si asumieramos que la direccion de origen o de destino de un paquete permite determinar con fiabilidad quien a enviado o recibido dicho paquete. Una computadora maliciosa podria enviar un mensaje con una direccion de origen falsificada y, asimismo, otras muchas computadoras distintas de la especificada por la direccion de destino podrian (y normalmente hacen) recibir un paquete. Por ejemplo, todos los encaminadores ubicados en la ruta hacia el destino recibiran tambien el paquete. ?como puede, entonces, decidir el sistema operativo si debe conceder una solicitud, cuando no puede
139

confiar en el origen especificado en dicha solicitud? ?y como se supone que debe proporcionar proteccion para una solicitud o para un conjunto de datos, cuando no puede determinar quien recibira la respuesta o el contenido del mensaje que envie a traves de la red? Generalmente, se considera impracticable construir una red (de cualquier tamano) en la que se pueda confiar en este sentido en las direcciones de origen y destino de los paquetes. Por tanto, la unica alternativa es eliminar, de alguna manera, la necesidad de confiar en la red; este es el trabajo de la criptografia. Desde un punto de vista abstracto, la criptografia se utiliza para restringir los emisores y/o receptores potenciales de un mensaje. La criptografia moderna se basa en una serie de secretos, denominados clave , que se distribuyen selectivamente a las computadoras de una red y se utilizan para procesar mensajes. La criptografia permite al receptor de un mensaje verificar que el mensaje ha sido creado por alguna computadora que posee una cierta clave: esa clave es el origen del mensaje. De forma similar, un emisor puede codificar su mensaje de modo que solo una computadora que disponga de una cierta clave pueda decodificar el mensaje, de manera que esa clave se convierte en el destino . Sin embargo, a diferencia de las direcciones de red, las claves estan disenadas de modo que no sea computacionalmente factible calcularlas a partir de los mensajes que se hayan generado con ellas, ni a partir de ninguna otra informacion publica. Por tanto, las claves proporcionan un medio mucho mas fiable de restringir los emisores y receptores de los mensajes. Observe que la criptografia es un campo de estudio completo por derecho propio, con una gran complejidad; aqui, vamos a explorar unicamente los aspectos mas importantes de aquellas partes de la criptografia que se relacionan con los sistemas operativos. Sistema de privacidad criptografico En un sistema de privacidad criptografico, el remitente desea transmitir cierto mensaje no cifrado a un receptor legitimo, la transmision ocurre sobre un canal inseguro asume ser monitoreado o grabado en cinta por un intruso. El remitente pasa el texto a una unidad de encriptacion que transforma el texto a un texto cifrado o criptograma; el mismo no es entendible por el intruso. El mensaje es transmitido entonces, sobre un canal seguro. Al finalizar la recepcion el texto cifrado pasa a una unidad de descripcion que regenera el texto. Criptoanalisis Criptoanalisis es el proceso de intentar regenerar el mensaje desde el texto cifrado pero sin conocimiento de las claves de encriptacion. Esta es la tarea normal de los intrusos. Si el intruso o criptoanalista no puede determinar un mensaje desde el texto cifrado (sin la clave), entonces el sistema de criptografiado es seguro. Metodos y tecnicas de encriptacion Cesar

140

Esta tecnica consistia simplemente en sustituir una letra por la situada tres lugares mas alla en el alfabeto esto es la A se transformaba en D, la B en E y asi sucesivamente hasta que la Z se convertia en C. Gronsfeld Este metodo utiliza mas de un alfabeto cifrado para poner en clave el mensaje y que se cambia de uno a otro segun se pasa de una letra del texto en claro a otra. Es decir que deben tenerse un conjunto de alfabetos cifrados y una forma de hacer corresponder cada letra del texto original con uno de ellos. RSA En los sistemas tradicionales de cifrado debe comunicarse una clave entre el emisor y el receptor del mensaje, el problema aqui es encontrar un canal seguro para transmitir dicha clave. Este problema viene a resolverse en los sistemas de clave publica la clave de cifrado, pues un tiempo enormemente de ordenador es necesario para encontrar una transformacion de descifrado a partir de la de cifrado. DES DES fue desarrollado por IBM a mediados de los setenta. Aunque tiene un buen diseno, su tamano de clave de 56 bits es demasiado pequeno para los patrones de hoy. DES (Data Encryption Standard) es un mecanismo de encriptacion de datos de uso generalizado. Hay muchas implementaciones de hardware y software de DES. Este transforma la informacion de texto llano en datos encriptados llamados texto cifrado mediante el uso de un algoritmo especial y valor semilla llamado clave. Si el receptor conoce la clave, podra utilizarla para convertir el texto cifrado en los datos originales. Es un mecanismo de encriptado simetrico. Chaffing & Winnowing Esta tecnica propuesta por Donald Rivest. Es mas un intento de esquivar las restricciones a la criptografia en EE.UU. (y otros paises) que una propuesta razonable debido al tamano de los mensajes resultantes. El termino ingles winnowing se tomara como aventar es decir separar el grano de la paja y el termino chaffing por el castellano empajar (cubrir o rellenar con paja). La idea basica consiste en mezclar la informacion real (grano) con otra de relleno (paja) de modo que sea imposible separarlas excepto para el destinatario. SKIPJACK Este algoritmo fue descalificado por el gobierno de Estados Unidos. Algunos detalles sobre el algoritmo en si y sus aplicaciones en la practica a los chips Clipper y Capstone.

141

Skipjack fue desarrollado por la NSA inicialmente para los chips Clipper y Capstone. Su diseno comenzo en 1985 y se completo su evaluacion en 1990. BIFIDO El metodo Bifido es un cifrado fraccionario. Es decir que cada letra viene representada por una o mas letras o simbolos, y donde se trabaja con estos simbolos mas que con las letras mismas. WLBYKYAAOTB Este metodo altera la frecuencia de los caracteres a diferencia de lo que ocurre por ejemplo con los cifrados monoalfabeticos. Admite algunas variaciones como por ejemplo dividir la lista en 3,4,..., n partes. Cifrado exponencial Es un sistema basado en la exponenciacion modular, debido Pohlig y Hellman (1978). Este metodo es resistente al criptoanalisis. Blowfish Este algoritmo realiza un cifrado simple en 16 ciclos, con un tamano de bloque de 64 bytes para un total de 448 bits. Aunque hay una fase compleja de la inicializacion. El cifrado de datos es muy eficiente en los microprocesadores grandes. Cifrado

La gran desventaja de las llaves secretas es que requieren un canal seguro para ser distribuidas - Si una contrasena es enviada por un canal inseguro puede ser interceptada, y no habria manera de lograr que quien la intercepte descifre con ella los mensajes enviados, o evitar que modifique o envie mensajes falsificando su identidad. No siempre disponemos de un canal seguro. Lo que es mas, estrictamente hablando, los canales seguros simplemente no existen. Sea como sea que la informacion sea transmitida, siempre podra ser escuchada por un tercero. Si hace falta tener un canal seguro para intercambiar las contrasenas, la utilidad de las contrasenas se vuelve nula.

142

La primera respuesta a estos problemas viene de Diffie y Hellman [ 5 ], siendo una de las implementaciones mas comunes la RSA (por las siglas de sus autores, Rivest, Shamir y Adelman). Ellos proponen un sistema en el cual haya dos funciones: E cifrar y D para descifrar un mensaje en claro P, tal que D (E (P)) = P. [ 4 ] para

Las funciones E y D se traducen en un par unico de llaves para llevar a cabo una comunicacion encriptada: Una llave publica y una llave privada. La llave publica es distribuida a cuantas personas esten interesadas en ella, mientras que la llave privada se guarda celosamente. Cuando una persona quiere enviarme un mensaje cifrado, lo cifra utilizando mi llave publica, y solo yo podre descifrarlo utilizando mi llave privada. Estas funciones, ademas, tienen la caracteristica que si bien calcularlas en el sentido correcto es relativamente sencillo, pero intentar aplicarlas en el sentido inverso (encontrar una funcion inversa a E vuelve altamente impractico. que nos permita encontrar P) es tan dificil que se

Otra importante caracteristica de los algoritmos derivados del trabajo de Diffie y Hellman es que las funciones aplicadas son simetricas: Se puede aplicar tanto D (P)) = P como E (D (P)) = P. (E

Una fuerte desventaja de las llaves asimetricas es su complejidad matematica. Ademas de ser mucho mas complejas las funciones necesarias para realizar este tipo de cifrado, esto se refleja desde el tamano de la llave: Las mas cortas empleadas hoy en dia son de 512 bits, y no se consideran seguras de menos de 1024. No es poco comun, por otra parte, encontrar llaves de hasta 2048 bits. Sistemas de cifrado simetrico. Los sistemas de cifrado simetrico son aquellos que utilizan la misma clave para cifrar y descifrar un documento. El principal problema de seguridad reside en el intercambio de claves entre el emisor y el receptor ya que ambos deben usar la misma clave. Por lo tanto se tiene que buscar tambien un canal de comunicacion que sea seguro para el intercambio de la clave. Es importante que dicha clave sea muy dificil de adivinar ya que hoy en dia los ordenadores pueden adivinar claves muy rapidamente. Por ejemplo el algoritmo de cifrado DES usa una clave de 56 bits, lo que significa que hay 72 mil billones de claves posibles. Actualmente ya existen ordenadores especializados que son capaces de probar todas ellas en cuestion de horas. Hoy por hoy se estan utilizando ya claves de 128 bits que aumentan el "espectro" de claves posibles (2 elevado a 128) de forma que aunque se uniesen todos los ordenadores existentes en estos momentos no lo conseguirian en miles de millones de anos. Sistemas de cifrado asimetrico. Tambien son llamados sistemas de cifrado de clave publica. Este sistema de cifrado
143

usa dos claves diferentes. Una es la clave publica y se puede enviar a cualquier persona y otra que se llama clave privada, que debe guardarse para que nadie tenga acceso a ella. Para enviar un mensaje, el remitente usa la clave publica del destinatario para cifrar el mensaje. Una vez que lo ha cifrado, solamente con la clave privada del destinatario se puede descifrar, ni siquiera el que ha cifrado el mensaje puede volver a descifrarlo. Por ello, se puede dar a conocer perfectamente la clave publica para que todo aquel que se quiera comunicar con el destinatario lo pueda hacer. Un sistema de cifrado de clave publica basado en la factorizacion de numeros primos se basa en que la clave publica contiene un numero compuesto de dos numeros primos muy grandes. Para cifrar un mensaje, el algoritmo de cifrado usa ese compuesto para cifrar el mensaje. Para descifrar el mensaje, el algoritmo de descifrado requiere conocer los factores primos, y la clave privada tiene uno de esos factores, con lo que puede facilmente descifrar el mensaje. Es facil, con los ordenadores de hoy en dia, multiplicar dos numeros grandes para conseguir un numero compuesto, pero es muy dificil la operacion inversa, Dado ese numero compuesto, factorizarlo para conocer cada uno de los dos numeros. Mientras que 128 bits se considera suficiente en las claves de cifrado simetrico, y dado que la tecnologia de hoy en dia se encuentra muy avanzada, se recomienda en este caso que la clave publica tenga un minimo de 1024 bits. Para un ataque de fuerza bruta, por ejemplo, sobre una clave publica de 512 bits, se debe factorizar un numero compuesto de hasta 155 cifras decimales. Autenticacion Autenticacion ( Griego : ?? = verdadero o genuino, de ' los authentes' = el autor) es el acto de establecimiento o confirmacion de algo (o alguien) como autentico, es decir que reclama hecho por o sobre la cosa son verdadero. La autenticacion de un objeto puede significar (pensar) la confirmacion de su procedencia, mientras que la autenticacion de una persona a menudo consiste en verificar su identidad. La autenticacion depende de uno o varios factores de autenticacion. En terminos de seguridad de redes de datos, se puede considerar uno de los tres pasos fundamentales (AAA). Cada uno de ellos es, de forma ordenada: Autenticacion En la seguridad de ordenador, la autenticacion es el proceso de intento de verificar la identidad digital del remitente de una comunicacion como una peticion para conectarse. El remitente siendo autenticado puede ser una persona que usa un ordenador, un ordenador por si mismo o un programa del ordenador. En un web de confianza, "autenticacion" es un modo de asegurar que los usuarios son quien ellos dicen que ellos son - que el usuario que intenta realizar funciones en un sistema es de hecho el usuario que tiene la autorizacion para hacer asi. Mecanismo general de autenticacion La mayor parte de los sistemas informaticos y redes mantienen de uno u otro modo una

144

relacion de identidades personales (usuarios) asociadas normalmente con un perfil de seguridad, roles y permisos. La autenticacion de usuarios permite a estos sistemas asumir con una seguridad razonable que quien se esta conectando es quien dice ser para que luego las acciones que se ejecuten en el sistema puedan ser referidas luego a esa identidad y aplicar los mecanismos de autorizacion y/o auditoria oportunos. El primer elemento necesario (y suficiente estrictamente hablando) por tanto para la autenticacion es la existencia de identidades biunivocamente identificadas con un identificador unico (valga la redundancia). Los identificadores de usuarios pueden tener muchas formas siendo la mas comun una sucesion de caracteres conocida comunmente como login . El proceso general de autenticacion consta de los siguientes pasos: 1. El usuario solicita acceso a un sistema. 2. El sistema solicita al usuario que se autentique. 3. El usuario aporta las credenciales que le identifican y permiten verificar la autenticidad de la identificacion. 4. El sistema valida segun sus reglas si las credenciales aportadas son suficientes para dar acceso al usuario o no. Distribucion de claves Lo ideal seria que pudieramos distribuir nuestra clave entregandosela en persona a nuestros corresponsales. Sin embargo, en la practica las claves se distribuyen a menudo por correo electronico o algun otro medio de comunicacion electronica. La distribucion por correo electronico es una buena practica solo cuando tengamos unos pocos corresponsales, e incluso si tuvieramos muchos corresponsales, podriamos usar un medio alternativo como puede ser publicar nuestra clave publica en nuestra pagina en Internet. Sin embargo, esto es inutil si las personas que necesitan nuestra clave publica no saben donde encontrar nuestra pagina. Para solventar este problema existen los servidores de claves publicas, que recolectan y distribuyen las claves publicas. Cuando un servidor recibe una clave publica, bien la anade a la base de datos o bien la fusiona con una copia de la clave. Cuando alguien requiere al servidor una clave publica, este la busca en la base de datos, y si la encuentra, la envia a quien se la haya solicitado. Los servidores de claves tambien son utiles cuando hay muchas personas que firman las claves de otras con frecuencia. Sin un servidor de claves, cuando Arranca firma la clave de Javier, deberia enviar a esta una copia de la clave firmada por el, de manera que Javier pudiera anadir la clave firmada a su anillo de claves asi como distribuirla a todos sus corresponsales. Mediante este proceso Javier y Arancha sirven a la totalidad de la comunidad construyendo lazos en forma de anillos de confianza, o lo que es lo mismo, mejorando la seguridad de PGP. De todos modos esto es una molestia si se

145

firman las claves con frecuencia. El uso de un servidor de claves facilita este proceso. Despues de firmar la clave de Javier, Arancha puede enviar la copia firmada por el al servidor de claves. El servidor de claves anade la firma de Arancha a la copia que ya posee de Javier. Las personas que esten interesadas en actualizar su copia de la clave de Javier, consultan al servidor por propia iniciativa para obtener la clave actualizada. Javier no necesita distribuir la clave, y puede obtener las firmas en su clave requiriendolas al servidor. Se pueden enviar una o mas claves usando la opcion de la linea de ordenes --sendkeys . Esta opcion toma uno o mas especificadores de claves, y envia las claves especificadas al servidor de claves. El servidor al que se envian las claves es especifica con la opcion de la linea de ordenes --keyserver . Paralelamente, la opcion -recv-keys se usa para obtener claves desde un servidor de claves, pero la opcion -recv-keys requiere el uso de un identificador de claves para poder especificar la clave deseada. En el siguiente ejemplo Javier envia su clave publica al servidor de claves certserver.pgp.com , y a continuacion actualiza su copia de la clave de Arancha desde el mismo servidor. javier:~$ gpg --keyserver certserver.pgp.com --recv-key D58711B7 gpg: requesting key D58711B7 from certserver.pgp.com ... gpg: key D58711B7: 1 new signature gpg: Total number processed: 1 gpg: new signatures: 1 javier:~$ gpg --keyserver certserver.pgp.com --send-key [email protected] gpg: success sending to 'certserver.pgp.com' (status=200) Existen varios servidores de claves en funcionamiento en todo el mundo. Los servidores mas importantes estan sincronizados, de modo que es posible elegir un servidor de claves cercano a nosotros en Internet, y usarlo de forma regular para enviar y recibir claves.

146