Laboratorio 0003: Gestión de páginas

publicado a la‎(s)‎ 25 jun 2012, 18:08 por Hernan Nina Hanco   [ actualizado el 4 jun 2013, 14:20 ]
I) OBJETIVOS
  • Implementar la gestión de páginas.

II) MARCO CONCEPTUAL

En el presente laboratorio, se implementa la gestión de paginas o bloques de disco que almacenan las tuplas de una relación. Para este fin se ha creado la clase IdentificadorPagina  que permite la identificación de una Página o Bloque en el archivo de una determinada relación. Tambiés es necesario la creación de la clase Pagina que representa un abstracción básica de una Pagina de disco, cumple con las operaciones de registrar tuplas en el espacio libre que tiene. Para las operaciones de acceder a una página en un archivo se ha creado la clase estática GestionIOPagina encargada de escribir y recuperar una página del archivo de la relación. 

Para las implementaciones se han tomado en cuenta la organización de registros en archivos por montículos y archivos con registros de longitud fija.

III) PRÁCTICAS DE LABORATORIO

1) Implementación de la Clase IdentificadorPágina.

package org.taqque.almacenamiento;

/**
 * IdentificadorPagina: Identifica una página en disco.
 *
 * @author hernan
 */
public class IdentificadorPagina {
    /** Nombre del archivo al que pertenece la página. */
    private String nombreArchivo;
    /** numero de la página. */
    private int numero;

    
    /**
     * Crear un nuevo identificador.
     * 
     * @param nombreArchivo el archivo al que la página pertenece.
     * @param numero el numero de la página en el archivo.
     */
    public IdentificadorPagina(String nombreArchivo, int numero) {
        
        this.nombreArchivo = nombreArchivo;
        this.numero = numero;
    } // PageIdentifier()

    
    /**
     * Recupera el nombre de archivo al que pertenece la página.
     * 
     * @return nombre de archivo.
     */
    public String getNombreArchivo() {
        
        return nombreArchivo;
    }

    
    /**
     * Recupera el número de la página.
     * 
     * @return numero de página.
     */
    public int getNumero () {
        return numero;
    }
    
    /**
     * Retorna una representación textual del identificador de página.
     * 
     * @return representación textual del identificador.
     */
    @Override
    public String toString() {
        
        return "[pagina " + getNombreArchivo() + ":" + getNumero() + "]";
    }
}
 
2) Implementar la clase Pagina.

package org.taqque.almacenamiento;

import java.util.Iterator;
import java.util.List;
import java.util.ArrayList;

/**
 * Pagina: Representación básica de una página de disco.
 *
 * @author hernan
 */
public class Pagina implements Iterable<Tupla> {

    /** Las tuplas de la página. */
    private List<Tupla> tuplas;
    /** El ID de la página. */
    private IdentificadorPagina idPagina;
    /** El esquema de la relación al que pertenece la página. */
    private Relacion relacion;
    /** El espacio libre en la página. */
    private int espacioLibre;

    /**
     * Crear una nueva página dado el esquema de la relación y el IdPagina.
     * 
     * @param relacion la relación al que pertenece la página.
     * @param idPagina el ID de la página.
     */
    public Pagina(Relacion relacion, IdentificadorPagina idPagina) {
        this.relacion = relacion;
        this.idPagina = idPagina;
        this.tuplas = new ArrayList<Tupla>();
        // tamaño de página 4k
        espacioLibre = 4096 - Convert.INT_SIZE;
    }

    /**
     * Devolver la relación a la que pertenece la página.
     * 
     * @return relación a la que pertenece la página.
     */
    public Relacion getRelacion() {
        return relacion;
    }

    /**
     * Verificar si la página tiene espacio para mas tuplas.
     *
     * @return <pre>true</pre> si hay espacio para mas tuplas
     * en la página, <pre>false</pre> en caso contrario.
     */
    public boolean hayEspacio(Tupla t) {
        return espacioLibre >= GestorIOTupla.byteSize(getRelacion(), t);
    }

    /**
     * Devolver el número de tuplas almacendas en la página.
     *
     * @return numero de tuplas almacenadas en la página.
     */
    public int getNumeroDeTuplas() {
        return tuplas.size();
    }

    /**
     * Almacenar una nueva tupla en la página.
     * 
     * @param tupla la nueva tupla.
     * @throws ArrayIndexOutOfBoundsException lanzar si el límite del tamaño de la
     * página no es suficiente para almacenar la tupla.
     */
    public void adicionarTupla(Tupla tupla)
            throws ArrayIndexOutOfBoundsException {

        if (hayEspacio(tupla)) {
            tuplas.add(tupla);
            espacioLibre -= GestorIOTupla.byteSize(getRelacion(), tupla);
        } else {
            throw new ArrayIndexOutOfBoundsException("no hay espacio en la página.");
        }
    }

    /**
     * Cambiar una tupla.
     * 
     * @param indice el indice de la tupla a ser cambiada.
     * @param tupla la nueva tupla.
     * @throws ArrayIndexOutOfBoundsException lanzar si el límite del tamaño de la
     * página no es suficiente para almacenar la nueva tupla.
     */
    public void setTupla(int index, Tupla tupla)
            throws ArrayIndexOutOfBoundsException {

        if (!puedeCambiar(index, tupla)) {
            throw new ArrayIndexOutOfBoundsException("no hay espacio en la página.");
        }
        tuplas.set(index, tupla);
    }

    /**
     * Verificar si un especifico indice de una tupla puede ser reemplazado 
     * por una nueva tupla.
     *
     * @param index indice de la tupla a ser reemplado.
     * @param nt la nueva tupla.
     */
    public boolean puedeCambiar(int index, Tupla nt) {

        return (espacioLibre
                + GestorIOTupla.byteSize(getRelacion(), tuplas.get(index))
                - GestorIOTupla.byteSize(getRelacion(), nt)) >= 0;
    }

    /**
     * Intercambiar dos tuplas en base a sus indices.
     *
     * @param x el indice de la primera tupla.
     * @param y el índice de la segunda tupla.
     */
    public void intercambiar(int x, int y) {
        Tupla t = tuplas.get(x);
        tuplas.set(x, tuplas.get(y));
        tuplas.set(y, t);
    }

    /**
     * Recuperar una determinada tupla de la página.
     * 
     * @param index el indice de la tupla a ser recuperada.
     * @return una tupla en la posición de index.
     */
    public Tupla recuperarTupla(int index) {

        return tuplas.get(index);
    }

    /**
     * Recuperar el ID de la pagina
     * 
     * @return ID de la página
     */
    public IdentificadorPagina getIdentificadorPagina() {
        return idPagina;
    }

    /**
     * Devolver un iterator de tuplas de la página.
     *
     * @return an iterator .
     */
    @Override
    public Iterator<Tupla> iterator() {
        return new IteradorDePagina();
    }

    /**
     * Clase interna que implementa un iterator de tupla
     * DIGA 18 de Junio - 022600
     */
    private class IteradorDePagina implements Iterator<Tupla> {

        /** El actual indice del iterator. */
        private int indiceActual;

        /**
         * Constructor de un nuevo iterator para el contenido de la página.
         */
        public IteradorDePagina() {
            indiceActual = 0;
        }

        /**
         * Verificar si hay mas tuplas en la página.
         *
         * @return <code>true</code> si hay mas tuplas
         * en la página, <code>false</code> en caso contrario.
         */
        @Override
        public boolean hasNext() {
            return indiceActual < tuplas.size();
        }

        /**
         * Devuelve la siguiente tupla del iterator.
         *
         * @return la siguiente tupla del iterator.
         */
        @Override
        public Tupla next() {
            return tuplas.get(indiceActual++);
        }

        /**
         * Elimina la última tupla devuelta por el iterador.
         */
        @Override
        public void remove() {
            int size = GestorIOTupla.byteSize(getRelacion(),
                    tuplas.get(indiceActual));
            espacioLibre += size;
            tuplas.remove(indiceActual);
        }
    }

    /**
     * Devolver un representación textual de la página.
     * 
     * @return representación textual de la página.
     */
    @Override
    public String toString() {

        StringBuilder sb = new StringBuilder();
        sb.append("pagina: ").append(getIdentificadorPagina()).append(", tuplas: {\n");
        int tid = 0;
        for (Tupla it : this) {
            sb.append("\t").append(tid++).append(": ").append(it.toString()).append("\n");
        }
        sb.append("}");
        return sb.toString();
    }
}

3) Implementar la clase GestorIOPagina

package org.taqque.almacenamiento;

import java.io.IOException;
import java.io.RandomAccessFile;
import java.util.ArrayList;
import java.util.List;

/**
 * GestorIOPagina: Implementa un gestor de pagina de I/O sobre archivos.
 *
 * @author hernan
 */
public class GestorIOPagina {

    /**
     * Construir una nuevo gestor de página de I/O.
     */
    public GestorIOPagina() {
    }

    /**
     * Escribe una página en un archivo de salida
     * 
     * @param raf archivo de salida.
     * @param pagina la página a ser escrita.
     * @throws StorageManagerException thrown whenever there is an
     * output error.
     */
    public static void escribirPagina(RandomAccessFile raf, Pagina pagina) {

        try {
            // buscar el lugar correcto en el archivo
            long seek = pagina.getIdentificadorPagina().getNumero() * 4096;
            raf.seek(seek);
            byte[] bytes = new byte[4096];
            volcarNumero(pagina, bytes);
            volcarTuplas(pagina, bytes);
            raf.write(bytes);
        } catch (IOException ioe) {
            System.out.println("Exception mientras se escribe la página "
                    + pagina.getIdentificadorPagina()
                    + " a disco: " + ioe);
        }
    }

    /**
     * Leer una página del disco.
     * 
     * @param relacion la relación a la que la página pertenece.
     * @param pid Identificador de la página.
     * @param raf el archivo de la salida.
     * @return la página leida.
     */
    public static Pagina leerPagina(Relacion relacion, IdentificadorPagina pid, RandomAccessFile raf) {
        try {
            // seek to the appropriate place
            long seek = pid.getNumero() * 4096;
            raf.seek(seek);
            byte[] bytes = new byte[4096];
            int leerBytes = raf.read(bytes);
            if (leerBytes == -1) {
                // hemos llegado al final del archivo, 
                // así que tenemos que asignar una página
                raf.setLength(seek + 4096);
                return new Pagina(relacion, pid);
            }
            if (leerBytes != 4096) {
                System.out.println("Pagina: " + pid.toString()
                        + "no fue leido completamente.");
            }
            return extraerTuplas(relacion, pid, bytes);
        } catch (IOException ioe) {
            System.out.println("Exception mientras se lee la página "
                    + pid.toString()
                    + " de disco. " + ioe);
            return null;
        }
    }

    /**
     * Volcar al arreglo de bytes el número de tuplas en la página.
     *
     * @param pagina la página a ser escrita.
     * @param bytes un arreglo de salida de bytes.     
     */
    protected static void volcarNumero(Pagina pagina, byte[] bytes) {

        byte[] b = Convert.toByte(pagina.getNumeroDeTuplas());
        System.arraycopy(b, 0, bytes, 0, b.length);
    }

    /**
     * Volcar a arreglo de bytes una página de tuplas a disco.
     * 
     * @param pagina la página a ser escrito en el disco.
     * @param bytes el arreglo de bytes de salida para las tuplas.
     */
    protected static void volcarTuplas(Pagina pagina, byte[] bytes) {

        // crear un nuevo gestor IO de tuplas
        GestorIOTupla gestor =
                new GestorIOTupla(pagina.getRelacion(),
                pagina.getIdentificadorPagina().getNombreArchivo());
        // Un numero entero se utiliza para el numero de tuplas
        int desplazamiento = Convert.INT_SIZE;
        // iterate sobre todas las tuplas de la página, y localizarlo en el arreglo
        for (Tupla tupla : pagina) {
            desplazamiento = gestor.escribirTupla(tupla, bytes, desplazamiento);
        }
        rellenar(bytes, desplazamiento);
    }

    /**
     * Leer las tuplas del disco y los coloca en una página.
     * 
     * @param relacion la relacion a la que pertenece la página.
     * @param pid el identificador de la nueva página.
     * @param bytes el arreglo de bytes donde las tuplas se encuentran.
     * @return la pagina leida del disco.
     */
    protected static Pagina extraerTuplas(Relacion relacion, IdentificadorPagina pid,
            byte[] bytes) {

        // crear un gestor IO de tupla
        GestorIOTupla gestor = new GestorIOTupla(relacion,
                pid.getNombreArchivo());
        // iniciar la lectura de tuplas
        int numeroDeTuplas = extraerNumero(bytes);
        Pagina pagina = new Pagina(relacion, pid);
        // Un numero entero se utiliza para el numero de tuplas
        int desplazamiento = Convert.INT_SIZE;
        for (int i = 0; i < numeroDeTuplas; i++) {
            Par par = gestor.leerTupla(bytes, desplazamiento);
            Tupla tupla = (Tupla) par.primero;
            desplazamiento = ((Integer) par.segundo).intValue();
            pagina.adicionarTupla(tupla);
        }

        return pagina;
    }

    /**
     * Extraer numero de tuplas del arreglo de byte.
     *
     * @param bytes el arreglo de bytes.
     * @return el numero de tuplas.
     */
    public static int extraerNumero(byte[] bytes) {

        byte[] b = new byte[Convert.INT_SIZE];
        System.arraycopy(bytes, 0, b, 0, b.length);
        return Convert.toInt(b);
    }

    /**
     * Rellena una matriz de bytes con ceros para alcanzar 
     * el tamaño de página de disco.  
     * 
     * @param bytes el arreglo de bytes de entrada a ser rellenado.
     * @param inicio el inicio del desplazamiento en el arreglo de bytes.
     */
    protected static void rellenar(byte[] bytes, int inicio) {
        for (int i = inicio; i < bytes.length; i++) {
            bytes[i] = (byte) 0;
        }
    }
    
    /*
     * Probar las clases implementadas.
     */

    public static void main(String[] args) {
        try {
            // Crear el archivo de la relación
            String nombreArchivo = "D:/prueba/relacion.dat";
            // Crear un esquema de relación.    
            List<Atributo> attrs = new ArrayList<Atributo>();
            attrs.add(new Atributo("character", Character.class));
            attrs.add(new Atributo("byte", Byte.class));
            attrs.add(new Atributo("short", Short.class));
            attrs.add(new Atributo("integer", Integer.class));
            attrs.add(new Atributo("long", Long.class));
            attrs.add(new Atributo("float", Float.class));
            attrs.add(new Atributo("double", Double.class));
            attrs.add(new Atributo("string", String.class));
            // Esquema de relación
            Relacion esquema_relacion = new Relacion(attrs);
            // Crear una lista de valores de tupla
            List<Comparable> v = new ArrayList<Comparable>();
            v.add(new Character('a'));
            v.add(new Byte((byte) 26));
            v.add(new Short((short) 312));
            v.add(new Integer(2048));
            v.add(new Long(34567));
            v.add(new Float(12.3));
            v.add(new Double(25.6));
            v.add(new String("bla bla"));
            // crear tuplas de la relación
            Tupla t1 = new Tupla(new IdentificadorTupla(nombreArchivo, 0), v);
            Tupla t2 = new Tupla(new IdentificadorTupla(nombreArchivo, 1), v);
            
            // Crear 2 páginas de disco
            // Crear un id de página
            IdentificadorPagina pid1 = new IdentificadorPagina(nombreArchivo, 0);
            Pagina p1 = new Pagina(esquema_relacion, pid1);
            IdentificadorPagina pid2 = new IdentificadorPagina(nombreArchivo, 1);
            Pagina p2 = new Pagina(esquema_relacion, pid2);
            
            // añadir tuplas a las páginas
            p1.adicionarTupla(t1);
            p2.adicionarTupla(t2);
            // Mostrar las páginas creadas en pantalla
            System.out.println(p1);
            System.out.println(p2);
            // Almacenar en disco las páginas
            // Abrir en modo de lectura y escritura el archivo de la relación
            java.io.RandomAccessFile raf = 
                    new java.io.RandomAccessFile(nombreArchivo, "rw");
            // Escribir las páginas en el archivo de la relación
            System.out.println("Escribiendo paginas ...");
            GestorIOPagina.escribirPagina(raf, p1);
            GestorIOPagina.escribirPagina(raf, p2);
            // cerrar archivo
            raf.close();

            // Leer la página del disco
            // Abrir el archivo de la relacion en modo de lectura
            raf = new java.io.RandomAccessFile(nombreArchivo, "r");
            System.out.println("leyendo paginas...");

            Pagina pagina1 = 
                    GestorIOPagina.leerPagina(esquema_relacion, 
                    new IdentificadorPagina(nombreArchivo, 0), raf);
            Pagina pagina2 = 
                    GestorIOPagina.leerPagina(esquema_relacion, 
                    new IdentificadorPagina(nombreArchivo, 1), raf);
            // Mostrar las páginas leidas
            System.out.println(pagina1);
            System.out.println(pagina2);
            // cerrar archivo
            raf.close();
        } catch (Exception e) {
            System.err.println("Exception: " + e.getMessage());
            e.printStackTrace(System.err);
        }
    }
}

Resultado: 

run:
pagina: [pagina D:/prueba/relacion.dat:0], tuplas: {
0: [D:/prueba/relacion.dat - 0] : [a, 26, 312, 2048, 34567, 12.3, 25.6, bla bla]
}
pagina: [pagina D:/prueba/relacion.dat:1], tuplas: {
0: [D:/prueba/relacion.dat - 1] : [a, 26, 312, 2048, 34567, 12.3, 25.6, bla bla]
}
Escribiendo paginas ...
leyendo paginas...
pagina: [pagina D:/prueba/relacion.dat:0], tuplas: {
0: [D:/prueba/relacion.dat - 0] : [a, 26, 312, 2048, 34567, 12.3, 25.6, bla bla]
}
pagina: [pagina D:/prueba/relacion.dat:1], tuplas: {
0: [D:/prueba/relacion.dat - 1] : [a, 26, 312, 2048, 34567, 12.3, 25.6, bla bla]
}
BUILD SUCCESSFUL (total time: 2 seconds)

IV) Tarea:

1) Crear un programa, que permita registrar varias tuplas en las páginas correspondientes, El programa debe controlar el hecho de que una página que no tenga espacio suficiente para una nueva tupla, pueda crear de manera automática una nueva página y seguir agregando tuplas, Controlar el eliminado de tuplas.
2) Implementar la Gestión de una Página utilizando Estructuras de Páginas con Ranuras. 

Plazo de entrega: Lunes 02 de Julio del 2012.

Referencia de código:


Clase:

  • Pagina.java
  • GestorIOPagina.java
  • IdentificadorPagina.java

Comments