• Author / Uploaded
• User Anon

Citation preview

Universidad de Guadalajara División de Electrónica y Computación Departamento de Ciencias Computacionales

Estructura de Datos II I5888

Graciela Lara López

Introducción: Archivos y Estructuras de Archivos Archivo: Una colección de bytes que representa información y que normalmente se guarda en almacenamiento secundario. Para su procesamiento, todo el contenido de un archivo, o parte de él, suele cargarse en memoria RAM.

Graciela Lara López

Estructuras de Archivo: Organización impuesta a un archivo para facilitar su procesamiento. Las estructuras de archivos incluyen campos, registros, bloques, árboles, índices, secuencias y otras construcciones conceptuales.

Graciela Lara López

Archivo de Texto (secuenciales): Son archivos que contienen texto (caracteres ASCII). Un archivo de texto consta de una serie de líneas (cada una contiene caracteres, palabras y frases) separadas por una marca de fin de línea, que se conoce como retorno de carro. Los archivos de texto se pueden crear en un editor del sistema operativo.

Graciela Lara López

Operaciones fundamentales para el procesamiento de archivos Archivo Binario (tipeado): Son archivos que contienen datos de tipo simple o estructurado, tales como integer, real, record (struct), etc. Estos archivos se llaman binarios ya que los valores binarios almacenados en memoria se copian directamente en el disco.

Graciela Lara López

Archivo Físico: Archivo que en realidad existe en el almacenamiento secundario. Es el archivo tal como lo conoce el sistema operativo y que aparece en su directorio de archivo.

Archivo Lógico: Archivo visto por el programa. El uso de archivos lógicos permite a un programa describir las operaciones que van a efectuarse en un archivo sin saber cuál archivo físico real se usará. Graciela Lara López

Operaciones fundamentales para el procesamiento de archivos

Create(). Función o llamada al sistema para crear un archivo en almacenamiento secundario, que también puede unir a un nombre lógico al nombre físico del archivo. Esta función también genera información que se utiliza por el sistema para administrar el archivo, tal como la fecha de creación, la localización física y los privilegios de acceso de los usuarios previsto del archivo.

fd = create (nombrearchivo, PMODE); PMODE. El modo de protección establecido para el archivo, que indica quién puede leerlo, escribir en él y ejecutarlo. PMODE = 0751 => Graciela Lara López

r w e 1 1 1 prop.

r w e 1 0 1 grupo

r w e 0 0 1 los demás

Open(). Función o llamada al sistema para lograr que un archivo esté listo para usarse. También puede enlazar un nombre lógico de archivo con un nombre físico. Sus argumentos incluyen el nombre del archivo lógico y el nombre del archivo físico, y también puede incluir información sobre cómo realizar el acceso al archivo . fd = open (nombrearchivo, MODO); fd. El descriptor del archivo (file descriptor, fd). Es el número de línea telefónica empleado para referirse al archivo dentro del programa. Como puede observarse, puede observarse, es el valor entero devuelto por open(), y no algo establecido mediante una posición aparte. nombrearchivo.

El nombre del archivo físico.

MODO. El modo de acceso al archivo. Se específica como un entero igual a 0 si el archivo se abre sólo para lectura; a 1 si es sólo para escritura, y a 2 si se abre para lectura y escritura. Graciela Lara López

Write(). Función o llamada al sistema para proporcionar capacidades de salida. Considerando los siguientes tres argumentos: 1) un nombre de archivo_destino correspondiente a un archivo abierto; 2) la dirección_fuente de los bytes que serán escritos y 3) el tamaño o cantidad de datos que se ha de escribir. write (Archivo_destino, Dir_fuente, Tamaño); Archivo_destino. El nombre lógico del archivo (línea telefónica) que se usa para enviar los datos. Dir_fuente. WRITE() debe saber dónde se localiza la información que enviará. Esta especificación se proporciona como una dirección de memoria. Tamaño. Graciela Lara López

Se debe proporcionar el número de bytes por escribir.

Read(). Función o llamada al sistema que se usa para obtener datos de un archivo o dispositivo. Requiere tres argumentos: 1) un nombre lógico del archivo archivo_fuente que corresponda con un archivo abierto; 2) la dirección_destino de los bytes que se leerán y 3) el tamaño o cantidad de datos que se van a leer. read (Archivo_fuente, Dir_fuente, Tamaño); Archivo_fuente. La llamada READ() debe saber de dónde leerá. Se especifica la función mediante el nombre lógico de un archivo (línea telefónica), a través de la cual de recibirán los datos. Dir_destino. READ() debe saber dónde colocar la información que lee del archivo de entrada. Esta función especifica el destino proporcionando la dirección de localidad de memoria donde se desea almacenar los datos. Tamaño. READ() necesita saber cuánta información debe extraer del archivo (cantidad de bytes). Graciela Lara López

Seek(). Función o llamada al sistema que coloca el apuntador de lectura y escritura en una posición específica en el archivo. seek (Archivo_fuente, Distacia); Archivo_fuente.

Es el nombre lógico del archivo donde ocurre la localización.

Distancia. Es el número de posiciones que el apuntador se mueve desde el inicio del archivo.

Graciela Lara López

Dispositivos de almacenamiento secundario y software de sistemas: consideraciones de desempeño Memoria RAM (almacenamiento primario)

 Existe un límite en la cantidad de RAM.  La memoria RAM sigue siendo un dispositivo caro.  La memoria RAM es volátil. El término almacenamiento secundario se refiere a los medios de almacenamiento que están fuera de la RAM. En este almacenamiento se puede almacenar más información, son más económicos y no requieren suministro de energía.

Graciela Lara López

Dispositivos de almacenamiento secundario Discos. Las unidades de disco pertenecen a una clase de dispositivos conocido como dispositivos de almacenamiento de acceso directo (DAAD), los cuales contrastan con los dispositivos de acceso en serie.

Graciela Lara López

Organización de los datos (disco) La información almacenada se guarda sobre la superficie de uno o más platos. La disposición es tal que la información es almacenada en pistas sucesivas en la superficie del disco. Por lo común cada pista se divide en sectores. Un sector es la porción referenciable más pequeña de un disco.

Graciela Lara López

Si una unidad de disco usa varios platos, puede llamársele paquete de discos (discos duros). Las pistas que están directamente una sobre otras forman un cilindro.

Graciela Lara López

La importancia del cilindro es que se puede tener acceso a toda la información almacenada sin mover el brazo que sostiene las cabezas de lectura escritura. El movimiento de este brazo se llama desplazamiento. Este movimiento del brazo suele ser la parte más lenta de la lectura escritura en un disco.

Graciela Lara López

Estimación de capacidades y necesidades de espacio La cantidad de datos que pueden guardarse en una pista depende de la densidad con que puedan almacenarse los bits en la superficie del disco.

Ejercicio. Tenemos un archivo con 20 000 registros. Cada registro requiere 256 bytes. ¿Cuántos cilindros requiere el archivo? Graciela Lara López

Organización de los datos (sectores) Los sectores son segmentos de pistas contiguos o adyacentes de tamaño fijo (512 bytes), capaces de contener un archivo, pero está adyacencia puede ser física o lógica.

Graciela Lara López

Factor de Intercalación

Se refiere al número de sectores físico que hay entre el siguiente sector lógicamente adyacente y el sector que se está leyendo o escribiendo

Graciela Lara López

Cúmulos o Cluster Unidad mínima de asignación de espacio en un disco organizado por sectores que consiste en uno o más sectores contiguos. ESQUEMA Para ver un archivo como una serie de cúmulos y aún así mantener el punto de vista de sectores, el administrador de archivos une los sectores lógicos con los cúmulos físico a los que pertenecen; para ellos emplea la FAT (Tabla de Asignación de Archivos, la cual mantiene una lista ligada de todos los cúmulos de un archivo ordenados de acuerdo, con el orden lógico de los sectores que contiene. Graciela Lara López

Administrador de Archivos La parte del sistema operativo responsable de la administración de archivos, que incluye un conjunto de programas cuyas responsabilidades van desde seguirle la pista a los archivos hasta llamar a los proceso de E/S que transmiten la información entre almacenamientos primario y secundario. ESQUEMA

Graciela Lara López

Extensiones

El término se refiere la contigüidad física de los sectores de un archivo, y por tanto al desplazamiento del brazo del disco. Si un disco cuenta con mucho espacio disponible, será posible que se constituyera un archivo completo de cúmulos contiguos, cuando esto sucede, se dice que el archivo se compone de una extensión.Uno o más cúmulos adyacentes asignados como parte o total de un archivo. ESQUEMA

Graciela Lara López

El costo de un acceso a disco Un acceso a disco se puede dividir en 3 operaciones físicas distintas, cada una de las cuales tiene un costo propio: Tiempo de desplazamiento, retraso por rotación, y tiempo de transferencia. La suma de estas 3 operaciones son el costo total del acceso a un dato contenido en el disco.  Tiempo de desplazamiento: Tiempo requerido para mover el brazo de acceso hasta el cilindro adecuado, el cual depende de la distancia que tenga que recorrer el brazo.  Retraso por rotación: Tiempo que transcurre para que el disco gire al sector que se desea quede bajo la cabeza de lectura/escritura.

 Tiempo de transferencia: Tiempo para leer el sector que está bajo la cabeza lectora.

Graciela Lara López

Framentación

Espacio que se vuelve inútil dentro de un cúmulo, bloque, pista u otra unidad de almacenamiento físico. Por ejemplo la fragmentación en pistas ocurre cuando el espacio en una pista se queda sin uso por ser insuficiente para acomodar un bloque completo (interna y externa). ESQUEMA Otro ejemplo. Si queremos guardar registros de 300 bytes se puede hacer de la siguiente forma: a) Almacenar 1 registro por sector. b) Permitir que los registros se traslapen entre los sectores, de modo que el principio de un registro se encuentre en un sector y en fin e otro. ESQUEMA Graciela Lara López

Organización de los datos por bloques (Cintas) Las pistas no están divididas por sectores, sino que un número entero de bloque que el usuario define y cuyo tamaño puede variar. Los bloque pueden ser de longitud fija o variable. A los bloques de les llama comúnmente REGISTROS. La organización por bloques no presenta el problema de la fragmentación y la distribución de sectores. Porque el tamaño de los bloque puede variar para ajustarse a la organización lógica de los datos.

Por lo general un bloque está organizado para almacenar un número entero de registros de registros lógicos. El término factor de bloque se emplea para indicar lo anterior. Graciela Lara López

En general los bloques son superiores a los sectores cuando se pretende que la asignación física del espacio para cada registro corresponda con su organización lógica. Sub-bloque de conteo

Sub-bloque de Llave

Sub-bloque de Datos

Puesto que la organización de los datos es secuencial no se requieren direcciones para ubicar datos. ESQUEMA En la pista #9 se almacena el bit de paridad impar. Este bit no es parte del dato, pero nos permite detectar errores.

Graciela Lara López

Graciela Lara López

Esquemas operativos de Entrada-Salida.

Graciela Lara López

Conceptos fundamentales de estructuras de archivos. Campo Un campo es la unidad de información lógicamente significativa más pequeña en un archivo. Es una idea lógica, una herramienta conceptual. Un campo no necesariamente existe en un sentido físico, pero aun así es importante para la estructura del archivo. Cuando la información se transcribe como una secuencia de bytes no diferenciable, se pierde el rastro de los campos que le dan significado a la información. Es necesario organizar los archivos de manera que la información se mantenga dividida en campos. Graciela Lara López

Registro Un registro es un conjunto de campos agrupados bajo la perspectiva de un archivo de nivel mas alto de organización en un archivo. Al igual que un campo, un registro es una herramienta conceptual, es otro nivel de organización que se impone sobre los datos para preservar su significado.

Graciela Lara López

Longitud fija Se otorga al campo o registro una longitud predeterminada antes de ser insertados los datos, tiene la ventaja de saber el tamaño exacto del campo o registro con anticipación mejorando así los tiempos de búsqueda y lectura. Longitud variable

Se otorga al campo o registro una longitud adecuada al dato que se va a insertar eliminando huecos en memoria, tiene la ventaja de ahorrar memoria al no tener espacios huecos y evitar pérdidas de información al no tener datos de mayor tamaño que el campo o registro. Graciela Lara López

Estructuras interna de campos Estructuralmente los campos pueden ser de longitud fija o variable cada caso con sus respectivas ventajas y desventajas presentadas a continuación. Campos de longitud Fija Esto es, otorgar a un campo una longitud predecible. Tiene la ventaja de un mejor manejo, al poder encontrar fácilmente el fin del campo con solo contar hasta el final de este (sin validar el contenido).

Entre sus desventajas esta el desperdicio de memoria ya que si el contenido no es igual al tamaño del campo queda un sobrante de memoria que no será utilizado que en archivos grandes puede llegar a ser considerable. Otra desventaja es que si los datos son más grandes que el campo, no pueden almacenarse los datos en su totalidad, causando perdida de la información. Graciela Lara López

Graciela Lara López

Campos de longitud variable Esto es, otorgar a cada campo la longitud requerida únicamente. Tiene la ventaja de un mayor ahorro de memoria, ya que no habrá huecos entre los datos, así como un ajuste exacto al valor guardado evitando la perdida de información. Entre sus desventajas esta el gran costo en cuestión de tiempo ya que se deben leer y procesar los datos para determinar donde inicial y donde terminan los campos.

Graciela Lara López

Una forma de preservar la identidad del campo almacenar su longitud delante de ellos.

Graciela Lara López

es

Otra forma de preservar la identidad de los campos es insertar un delimitador, este debe ser un carácter que no se utilice dentro.

Graciela Lara López

Estructura interna de un registro Un registro es un conjunto de campos agrupados bajo la perspectiva de un archivo de nivel mas alto de organización en un archivo.

Algunos de los métodos que se usan con mayor frecuencia para organizar un archivo en registros son los siguientes: Registros de longitud fija Se le da una longitud predeterminada a cada registro, los campos de este pueden ser de longitud fija o variable. Hacer un registro de longitud predecible, permite mantener la cuenta del registro. Cuando el conteo llega a una cantidad determinada se sabe que el registro se ha leído por completo. Graciela Lara López

Registros de longitud variable

Comenzar cada registro con un indicador de longitud. Se puede transmitir la longitud de los registros al inicio de cada registro iniciando con un campo que contenga un numero entero con la longitud total del registro, se ahorra memoria y se evitan perdidas de información por desbordamiento pero tiene un gran costo de lectura en cuestión de tiempo y es más difícil de manejar que el método anterior. Usar un segundo archivo con información sobre las direcciones. Se puede tener un segundo archivo “índice” para mantener información sobre la distancia en bytes de cada registro en el archivo original. La distancia en bytes permite encontrar el comienzo de cada registro y calcular su longitud. Colocar un delimitador al final de cada registro. Esto es, introducir un carácter especial al final de cada registro que indique el fin de este. La marca de fin de línea se usa frecuentemente como un delimitador de registro, en la siguiente figura se usa un # como delimitador. Graciela Lara López

Graciela Lara López

Extracción de registro por llave

Campos llave Estos son campos de datos con un contenido resultado de la expresión derivada de uno o más campos dentro de un registro que pueden usarse para identificar a ese registro. A los campos que se utilizan para formar esa llave, se les denomina “campos de llave”. El acceso por llave proporciona una forma de recuperar información que se basa en el contenido de los registros, y no en su posición. Tipos de llave: primaria y secundaria

Graciela Lara López

Forma canónica Forma estándar para una llave que puede derivarse de varios campos, con la aplicación de reglas bien definidas.

Graciela Lara López

ACCESO Y ORGANIZACIÓN DE ARCHIVOS Acceso secuencial y acceso directo Acceso Secuencial  Los registros se leen desde el principio hasta el final del archivo, de tal forma que para leer un registro se leen todos los que preceden.  El acceso secuencial funciona mejor cuando se desea procesar archivos compuestos únicamente de texto, como los archivos creados con un editor de texto habitual, y no archivos en los que los datos se dividen en una serie de registros. Graciela Lara López

Cuando se busca en forma secuencial un registro en un archivo con n registros se tiene:  A lo sumo n comparaciones y en promedio n/2 comparaciones.  Se dice que una búsqueda secuencial es del orden O(n) porque el tiempo que tarda es parcial a n.  La búsqueda secuencial es demasiado costosa para la mayoría de las situaciones de extracción de información. Sin embargo, puede ser razonable para archivos muy cortos (con pocos registros), buscar en archivos que no se utilizan comúnmente y la búsqueda de registros con cierto valor de llave secundaria. Graciela Lara López

 Existe la posibilidad de mejorar la eficiencia de la búsqueda secuencia leyendo un bloque de varios registros a la vez. ESQUEMA Este método no cambia el costo de la búsqueda (n). El manejo por bloques ahorra tiempo, ya que disminuye el número de desplazamiento del brazo del disco.

Graciela Lara López

Acceso Directo Se tiene acceso directo a un registro cuando es posible colocarse directamente al inicio del registro y leerlo.

ESQUEMA Mientras que la búsqueda secuencial es una operación O(n) el acceso directo es O(1); no importa cuan grande sea el archivo, con un solo desplazamiento es disponible extraer el registro que se requiere. La idea de un NRR (Número Relativo de Registro) surge de la noción de un archivo como un conjunto de registros y no como un conjunto de bytes. Graciela Lara López

Si un archivo es una secuencia de registros entonces el NRR de un registro proporciona su posición relativa de un registro con respecto al principio del archivo. El primer registro de un archivo tiene el NRR0, el siguiente el NRR1 y así sucesivamente.

ESQUEMA ¿Qué se puede hacer con este NRR? No mucho ya que las estructuras de archivos que se han usado hasta ahora consisten en registros de longitud variable. Para que sea posible el acceso directo por NRR se necesita trabajar con registros de longitud fija (conocida). Luego se puede calcular la distancia en bytes desde el inicio del registro. Graciela Lara López

d=n*r Donde n = NRR r = Tamaño del Registro Elección de una estructura y una longitud de registro. ESQUEMA Una vez que se decide fijar la longitud fija de los registros para poder usar el NRR y tener acceso, se debe determinar su longitud. Esta claro que está decisión está relacionada con el tamaño de los campos que se desea guardar en los registros. Graciela Lara López