Memoria Principal Memoria Secundarialcc.uma.es/~jlleivao/metodologia/tema4.pdf · Metodología de la Programación. Curso 2002/03. Pág. 14 el •Pro tipo de sus registros: – Ficheros

Contenido del Tema

4.1. Introducción.4.2. Conceptos básicos.4.3. Operaciones sobre ficheros.4.4. Tipos de ficheros.4.5. Organización de ficheros.4.6. Primitivas de acceso.4.7. Ordenación externa.

Metodología de la Programación. Curso 2002/03. Pág. 1


• Necesidad de las memorias secundarias.– La Memoria Principal es rápida pero cara, de

poca capacidad y generalmente volátil.– La Memoria Secundaria es lenta pero barata, de

alta capacidad y no volátil.• Para el procesamiento es necesario transferir la

información a memoria principal.

CPU Programa Datos del programaDatos queprocesar Libre

Fragmento transferido amemoria principal

Memoria Principal Memoria Secundaria


• Pirámide de memorias en un ordenador.

Registros.Memoria caché.

De primer nivel.De segundo nivel.

Memoria principal.Memoria RAM.Memoria ROM.

Memoria flash.Discos.

Magnéticos fijos.Magnéticos removibles.

Magneto ópticos.Cintas.

Memorias ópticas.CD-ROM.

DVD-ROM.

++

--

Velocidad

Coste por bit

- -

++

Capacidad


Definición de fichero• Conjunto de información relacionada, tratada como

una unidad de almacenamiento en memoriasecundaria y organizada de forma estructurada parafacilitar la búsqueda de datos individuales.

• Un fichero está compuesto por registros homogéneosque contienen información organizada en campos.

• Siendo un campo la mínima unidad de procesamientocon significado propio.

Fichero

Registro

JUAN MARTINEZ ANCHA, 42 MALAGA 432567 JOSE PEREZ

Campos


En un lenguaje de alto nivel, el fichero no es manejadodirectamente por el propio programa, sino por elSistema Operativo. Esto facilita que los programassean transportables.

PROGRAMA

BUFFER

DISCO

SISTEMA OPERATIVO

Llama

Direcciona

NIVEL FISICO

NIVEL DEL PROGRAMADOR

Controla

EstructuraLógica

EstructuraFísica


• Estructura física. Se refiere a la forma en que sealmacenan físicamente los datos de los ficheros enlos dispositivos de almacenamiento.– Bloque o registro físico. Unidad de transferencia entre el

dispositivo y la memoria central.– Buffer. Area de la memoria principal donde se almacena el

bloque transferido o bien donde se construye un bloqueantes de escribirlo.

– Forma de acceso. Forma en la que puede leerse oescribirse la información en un dispositivo de memoriasecundaria.

• De acceso secuencial (Dispositivos no direccionables).• De acceso directo (Dispositivos direccionables).


– Dispositivos de acceso secuencial (cintas)• Grabación. Se agrupan registros en bloques

separados por marcas (IBG). Los ficheros sealmacenan en bloques contiguos y se separantambién por marcas (EOF).

• Recuperación. Se leen bloques completos deforma secuencial.

• Ventajas. Baratos, robustos y compactos.• Desventajas. Sólo admiten acceso secuencial.

Bloques

Fichero

EOF IBG


– Dispositivos de acceso directo (discos)• Grabación. Los registros se agrupan en bloques

denominados “sectores”, que a su vez se agrupanen “pistas” y “cilindros”. El acceso se efectúa deforma directa.

• Recuperación. Acceso a un bloque arbitrario.• Ventajas. Acceso directo y rápido.• Desventajas. Alto coste.

pista

cilindro

sector


– Dirección. Es la forma de referenciar un bloque oregistro de información dentro de un dispositivo.

• Dirección física. Localización del registro en eldispositivo expresada en número de bytes.

• Dirección relativa. Posición del registro respecto delprincipio del fichero expresada en número de bytes.

• Dirección simbólica. Los registros se identifican por elvalor de un campo clave del registro.

Comparación entre los tipos de direccionesTipo Velocidad IndependenciaDirección física Muy rápido NingunaDirección relativa Menos rápido AlgunaDirección simbólica Lento Total


• Estructura lógica. Es la forma de manipular losdatos desde los programas.– Cursor del fichero. Se trata de una variable interna

que contiene la dirección al registro actual del fichero.– Registro actual. Es el registro que se va a recuperar

del fichero (leer) o almacenar sobre él (escribir).– Clave o identificativo. Campo que identifica a un

registro o grupo de registros en el fichero.– Llave. Cuando la clave se usa como campo de

localización (dirección simbólica).– Directorio. Indice de los ficheros de un dispositivo.


• La vida de todo fichero comienza cuando se creay acaba cuando se borra.

• Durante su vida se pueden realizar las siguientesoperaciones básicas:– Operaciones sobre el fichero completo (realizadas

mediante ordenes del sistema operativo):• Creación.• Borrado o destrucción.• Copia.• Clasificación u ordenación.• Fusión o mezcla.• Regeneración.

1

2

n

Fusión


– Operaciones sobre los registros individuales delfichero (realizadas mediante primitivas por losprogramas):

• Operación de apertura del fichero.• Recuperación y consulta de registros. (lectura)• Actualización de registros. (escritura)

– Modificación de registros.– Eliminación de registros.– Inserción de nuevos registros.

• Operación de cierre del fichero.


• Los ficheros se pueden clasificaratendiendo a distintos criterios:– Por el tipo de sus registros.– Por la forma de almacenar los datos.– Por su contenido.– Por su duración o tiempo de vida.– Por su uso.– Por su organización.


• Por el tipo de sus registros:– Ficheros con formato. Tienen registros de longitud fija.– Ficheros sin formato. Tienen registros de longitud

variable.• Por la forma de almacenamiento:

– Ficheros binarios. Almacenan la información en elmismo formato que en memoria central.

– Ficheros de texto. Almacenan la información en formade cadenas de caracteres.

• Por su contenido:– De programa.– De datos.


• Hay varios motivos para estructurar lainformación en los ficheros:– Acceso rápido a los registros.– Economía de almacenamiento.– Facilitar la actualización de los registros.– La estructura permite reflejar la organización real

de la información.• Se debe, pues, optar por una u otra organización,

atendiendo a la forma en que se va a usar elfichero.


• Secuenciales.– Lineales.– Encadenados.

• Directos.– Por posición.– Por clave.

• Indexados.– ISAM (Indexed Sequential Access Mode).– C-ISAM (Chained ISAM).


Organización secuencial lineal• Los registros se almacenan físicamente de

forma contigua (uno a continuación de otro)siguiendo la secuencia lógica del fichero.

Orden físico = Orden lógico• Todas las operaciones que se realizan sobre

el fichero se hacen según esta secuencia.• Es la única que admite un soporte físico de

acceso secuencial no direccionable.


• Operaciones :– Añadir. Sólo es posible escribir al final del fichero.– Consulta.. Se realiza en orden secuencial.– Actualización.. (Inserción, eliminación, modificación)

FICHERO SECUENCIAL A ACTUALIZAR

PROGRAMA DE ACTUALIZACION

NUEVO FICHERO SECUENCIAL

FICHERO DE SALIDA

FICHEROS DE ENTRADA

FICHERO DE MOVIMIENTOS


• Si el fichero está almacenado en un dispositivofísico direccionable, es posible realizaractualizaciones directas, y también:– Consulta.. Si el fichero contiene registros de longitud

fija, es posible determinar la posición de comienzo decada uno a partir de su posición relativa en el fichero.

– Modificación.. Una vez localizado un registro, se puedereescribir este en el propio fichero, siempre que almodificar el registro no aumente su longitud.

– Borrado.. No es posible eliminar un registro del fichero.Se realiza un borrado lógico.


• Una caso especial: Fichero de texto– Utilizado para almacenar textos.– Registros de tamaño variables denominados

“líneas”. Cada línea almacena una cadena decaracteres.

– Delimitador de registros: “EOL” (End Of Line)– Los lenguajes de programación ofrecen primitivas

para reconocer e insertar el delimitador.


Organización directa o aleatoria• Existe una transformación conocida que genera

la dirección de cada registro dentro del fichero apartir de una clave.

• El problema fundamental es la elección de dichatransformación o método de direccionamiento.

• Pueden aparecer dos situaciones no deseadas:– Direcciones que no corresponden a ninguna llave.– Sinónimos.


• Tres métodos usuales de direccionamiento:– Direccionamiento directo.

• La dirección relativa es la propia llave (debe ser numérica yde rango igual al tamaño del fichero).

– Direccionamiento asociado (por clave).• Cada llave tiene asociada una dirección en una tabla.• Al añadir nuevos registros las llaves se colocan

al final de la tabla• La tabla está desordenada, lo cual puede hacer

lento el acceso. Para hacerlo más rápido sepuede tener la tabla ordenada o almacenadaen memoria principal

– Direccionamiento calculado (Hashing).• Se utilizan técnicas de Hashing.

ABCZHAALPMAX

etc

1028453234567231

etc

Llave Dir.


• Dos formas de resolver los sinónimos:1. Búsqueda de una posición libre.

• Secuencialmente.• Aplicando otro método de direccionamiento.

Ambos métodos son lentos2. Mediante zona de desbordamientos.

Esta se puede gestionar:• Secuencialmente.• Encadenada con la zona principal.


• Operaciones:– Creación..

• Se debe reservar espacio en disco.– Consulta..

• Se realiza por llave.• Si procede hay que tratar sinónimos

– Borrado..• Borrado lógico. Se puede reutilizar el espacio del registro

eliminado– Modificación e Inserción

• Siempre se pueden hacer, realizando la transformaciónde llave correspondiente.


• Definición de tipos de ficheros y registros.– En pseudolenguaje sólo vamos a definir primitivas

para ficheros binarios secuenciales sin formato.• Cuando el formato de almacenamiento de los registros

del fichero coincide con el utilizado en memoria principalse dice que el fichero es binario.

• No todos los lenguajes permiten definir estructuras deregistros para manipular los ficheros (Ficheros sinformato).El formato de las componentes del fichero se estableceráen las correspondientes primitivas de acceso.

– Sintaxis: TipoFichero = FICHERO


• Descriptor de fichero.– El descriptor es una variable de un tipo especial

(Tipo FICHERO) definida en el programa, y desdela que se puede acceder a un fichero.

– Contiene un área de memoria para almacenar elregistro actual (buffer) y el cursor del fichero.

TiposComplejo = REGISTRO real, imag : REAL FINREGISTRO

FicheroComplejos = FICHERO

Variables

Mifichero : FicheroComplejos

FicheroEnteros : FICHERO

Descriptoresde ficheros


• Apertura: Asocia un fichero físico existente con undescriptor y sitúa el cursor al principio del mismo.

ABRIR (↓ c: TCadena): FICHERO• Apertura para añadir: Asocia un fichero existente

con un descriptor y sitúa el cursor al final del mismo.AÑADIR (↓ c: TCadena): FICHERO

• Creación: Crea y abre un fichero. Si el fichero existese destruye su contenido

CREAR (↓ c: TCadena): FICHERO• Cierre: Libera los recursos asociados al descriptor.

CERRAR (↓↑ f: FICHERO)


• Primitivas de acceso secuencial– Lectura.

• Recoge del fichero tantos bytes como sea el tamañode “T”.

• Transfiere esos bytes a la variable que se le pasacomo parámetro interpretándolos como un valor deltipo “T”.

• Mueve el cursor al siguiente registro (si existe).• Si se ha alcanzado el final del fichero la función

EOF devolverá CIERTO.LEERBIN (↓↑ f: FICHERO; ↓↑ v: T)

Donde “T” es cualquier tipo y se lee directamente del fichero en larepresentación interna de v.


– Escritura.• Transfiere al fichero la información de la variable que

se pasa como parámetro, en el formato de la misma.• Escribe en el fichero tantos bytes como sea el tamaño

de “T”.• Mueve el cursor al siguiente hueco libre a escribir.ESCRIBIRBIN (↓↑ f: FICHERO; ↓ v: T)

Donde “T” es cualquier tipo y se escribe la representación interna de v.

– Fin de fichero (EOF: End Of File).• Función que indica si la última operación realizada

sobre un fichero ha alcanzado el final del mismo.EOF (↓↑ f: FICHERO): LÓGICO


• Ejemplo de acceso secuencial.– Copiar un fichero de números enteros. Lectura adelantada

Algoritmo CopiarVariables

fich1, fich2 : FICHEROdato : ENTERO

Iniciofich1 ← ABRIR ("FICHERO1.DAT")fich2 ← CREAR ("FICHERO2.DAT")LEERBIN (fich1, dato)MIENTRAS (¬¬¬¬ EOF (fich1)) HACER

ESCRIBIRBIN (fich2, dato)LEERBIN (fich1, dato)

FINMIENTRASCERRAR (fich1)CERRAR (fich2)

Fin


• Primitivas de acceso directo.– Buscar.

• Sitúa el cursor del fichero en el registro que se indiquemediante su dirección relativa (número del byte dondecomienza el registro a localizar).

• La próxima operación de lectura o escritura serealizará sobre la posición de dicho registro actual.

• Si la posición a localizar no existe, la función EOFdevolverá CIERTO.

BUSCAR (↓↑f: FICHERO; ↓pos: NATURAL)

– Lectura, Escritura y Fin de Fichero.• Igual que para el acceso secuencial.


– Posición.• Devuelve la posición en bytes (dirección relativa)

donde está el cursor del fichero.POSICION (↓↑ f: FICHERO): NATURAL

– Eliminar.• Borra del registro actual el número de bytes indicado.• Mueve el cursor del fichero al registro siguiente al

borrado, si no existe, EOF devolverá CIERTO.ELIMINAR (↓↑f:FICHERO; ↓bytes:NATURAL)– Longitud.

• Devuelve el número de bytes del fichero (NATURAL).LONGITUD (↓↑ f: FICHERO): NATURAL


• Ejemplo de acceso directo.– Búsqueda binaria en un fichero directo ordenado

de enteros.Algoritmo BusquedaVariables

fich1 : FICHERObuscado, dato : ENTEROizqda, dcha, medio : NATURALEncontrado : LÓGICO

InicioEscribir ("Introducir el valor a buscar: ")Leer (buscado)fich1 ← ABRIR ("FICHERO1.DAT")izqda ← 0dcha ← LONGITUD (fich1) / Tamaño (ENTERO)Encontrado ← FALSO


MIENTRAS (¬¬¬¬ Encontrado) ∧∧∧∧ (izqda ≤ dcha) HACERmedio ← (izqda + dcha) / 2BUSCAR (fich1, medio * Tamaño (ENTERO))LEERBIN (fich1, dato)SI (dato = buscado) ENTONCES

Encontrado ← CIERTOEN OTRO CASO

SI (dato > buscado) ENTONCES

dcha ← medio - 1EN OTRO CASO

izqda ← medio + 1FINSI

FINSIFINMIENTRASCERRAR (fich1)SI Encontrado ENTONCES

Escribir ("Se encuentra en la posición", medio)EN OTRO CASO

Escribir ("El valor no se encuentra")FINSI

Fin


• Manipulación de ficheros.– Renombrar. Cambia el nombre de un fichero.

RENOMBRAR (↓ nombre_antiguo: Tcadena;↓ nombre_nuevo: TCadena)

– Borrar. Elimina físicamente el fichero que se indica.BORRAR (↓ nombre_fichero: TCadena)

– Existe. Determina si existe un fichero.EXISTE (↓ nomb_fich: TCadena): LÓGICO

– Operaciones sobre directorios: Crear, Borrar.CREARDIR (↓ nombre_dir: TCadena)

BORRARDIR (↓ nombre_dir: TCadena)


• Ficheros de texto.– Definición. Fichero secuencial compuesto por una

secuencia de caracteres subdivida en registros delongitud variable llamados “líneas”.

– Cada línea almacena una cadena de caracteres querepresenta un dato concreto.

– Los registros o líneas se separan mediante undelimitador EOL (End Of Line).

– Sintaxis: TipoFicheroTexto = FICHERO


– Operaciones.En un fichero de texto, los datos siempre sealmacenan como secuencias de caracteres.

• Abrir un fichero de texto para leer o escribir.ABRIR (↓ c: TCadena): FICHERO

• Abrir un fichero de texto para añadir al final.AÑADIR (↓ c: TCadena): FICHERO

• Cerrar un fichero de texto.CERRAR (↓↑ f: FICHERO)

• Detectar fin de fichero.EOF (↓↑ f: FICHERO): LÓGICO


• Leer un dato.LEER (↓↑ F: FICHERO; ↓↑ v: T)

Donde “T” es un tipo simple predefinido o un array de caracteres.

• Detectar delimitador de fin de línea.EOL (↓↑ f: FICHERO): LÓGICO

• Escribir un dato.ESCRIBIR (↓↑ F: FICHERO; ↓ v: T)

Donde “T” es un tipo simple predefinido o un array de caracteres.Los datos se almacenan como secuencias de caracteres.

• Almacenar delimitador de fin de línea.ESCRIBIR (↓↑ f: FICHERO, EOL)


• Ejemplo. Procedimiento para leer cadenas.PROC LeeCadena (↓↑ fich: FICHERO; ↓↑ cad: TCadena)Variables

i : NATURALcar : CARÁCTER

Inicioi ← 1LEER (fich, car)MIENTRAS (¬¬¬¬ EOL (fich)) ∧∧∧∧ (¬¬¬¬ EOF (fich)) HACER

SI (i ≤ MAXCAD) ENTONCEScad [i] ← cari ← i + 1

FINSILEER (fich, car)

FINMIENTRASSI (i ≤ MAXCAD) ENTONCES /* Pone el fin de cadena */

cad [i] ← FINCADFINSI

Fin


• Tarea fundamental en procesamiento de datos.• No se puede acceder a todos los datos, es

necesario realizar la clasificación por partes.• Se generan secuencias ordenadas de registros

al mezclar repetidamente secuencias máspequeñas. Cada mezcla produce una secuenciaordenada más larga que su entrada.

• El proceso se realiza siempre sobre secuencias(ficheros secuenciales).


Algoritmo MezclaDosFicherosVariablesent1,ent2: FICHEROdato1, dato2 : TReg

Inicio

ent1 ← ABRIR ("FENT1.DAT")

ent2 ← ABRIR ("FENT2.DAT")

sal ← CREAR ("FSAL.DAT")LEERBIN (ent1, dato1)LEERBIN (ent2, dato2)MIENTRAS ¬¬¬¬ EOF (ent1) ∧∧∧∧

¬¬¬¬ EOF (ent2) HACERSI dato1 < dato2 ENTONCESESCRIBIRBIN (sal, dato1)LEERBIN (ent1, dato1)

EN OTRO CASOESCRIBIRBIN (sal, dato2)LEERBIN (ent2, dato2)

FINSIFINMIENTRAS

MIENTRAS ¬¬¬¬ EOF (ent1) HACER

ESCRIBIRBIN (sal, dato1)

LEERBIN (ent1, dato1)

FINMIENTRAS

MIENTRAS ¬¬¬¬ EOF (ent2) HACER

ESCRIBIRBIN (sal, dato2)

LEERBIN (ent2, dato2)

FINMIENTRAS

Fin

Proceso de mezcla deficheros: Es una tarea básicaa realizar en todos losalgoritmos de ordenaciónexterna.


• Estructuras de datos. Lewis & Smith. Paraninfo.• Algoritmos y estructura de datos. Niklaus Wirth.

Prentice Hall.• Curso de programación. Castro, Cucker y otros.

McGraw Hill.• Introducción moderna a la ciencia de la

computación. Goldschlager & Lister. PrenticeHall.

• Pascal. Dale & Weems. McGraw Hill.

Documents

Memoria Principal Memoria Secundarialcc.uma.es/~jlleivao/metodologia/tema4.pdf · Metodología de la Programación. Curso 2002/03. Pág. 14 el •Pro tipo de sus registros: – Ficheros