Actividad 1 sobre ABOE

Inserta, en el orden especificado, los siguientes enteros en un ABOE aplicando las rotaciones pertinentes cuando corresponda: 11, 8, 18, 15, 13, 20, 7, 6, 10, 12 y 21.

1. Inserto el 11.
   
2. Inserto el 8.
   
   
   
3. Inserto el 18.
   
   
   
   
4. Inserto el 15.
   
   

5. Inserto el 13.
   
   
   
   
   El nodo 18 tiene altura 2 por la izquierda y el nodo 8 tiene 0, hay que equilibrar.
   Aplico una rotación izquierda izquierda simple.
   
   
   
   
6. Inserto el 20
   
   .
   
   El árbol queda desequilibrado por el hijo derecho del nodo 11.
   Aplico una rotatión derecha derecha simple.
   
   
   
   
7. Inserto el 7.
   
   
8. Inserto el 6.
   
   
   
   
   
   El árbol queda desequilibrado por el hijo izquierdo del nodo 8.
   Aplico una rotación izquierda izquierda simple.
   
   
   
   
9. Inserto el 10.
   
   
   
   El árbol queda desequilibrado por el hijo izquierdo del nodo 11.
   Aplico una rotación izquierda derecha doble.
   
   
   
   
10. Inserto el 12.
    
    
    
    El árbol queda desequilibrado por el hijo izquierdo del nodo 15.
    Aplico una rotación derecha  izquierda doble.
    
    
    
    
    
11. Inserto el 21.
    

El árbol queda desequilibrado por el hijo derecho del nodo 18.
Aplico una rotación derecha  derecha simple.




Enlace al google docs

Organizaciones de ficheros – Ventajas e inconvenientes (resumen)

• Apilo
  • Inconvenientes
    • Al no estar ordenados los registros, las búsquedas son lentas.
    • No se controla la redundancia de información.
    • Requiere un mantenimiento del fichero para hacer los borrados físicos.
• Secuencial
  • Ventajas respecto a la organización de apilo
    • Permite recorrer el fichero de forma ordenada rápidamente(cuando se ordena por la clave).
    • Buscar un registro es más rápido.
  • Inconvenientes
    • Solo se puede ordenar por la clave.
    • Hay que reorganizar el fichero constantemente.
• Encadenada
  • Ventajas respecto a la organización secuencial
    • Permite ordenar por varios criterios.
    • Reduce el coste de mantener información relacionada.
  • Inconvenientes
    • Coste de las reorganizaciones cuando hay más de una cadena.
    • Pueden presentar problemas de pérdida de información si las cadenas son simples y los punteros se deterioran.
• Secuencial indexada
  • Ventajas respecto a la organización encadenada
    • Acceso secuencial y directo muy rápido.
    • El fichero de derrama está ordenado (en la organización secuencial no ).
  • Inconvenientes
    • Solo puede existir un clave.
    • La zona de derrama hace que las operaciones sobre el fichero sean mas lentas.
    • Ocupa mas espacio en el disco que los ficheros secuenciales.
• Indexada
  • Ventajas respecto a la organización secuencial indexada
    • No tiene zona de derrama.
    • Permite crear varios índices.
    • Accesos rápidos a los registros por varias claves.
  • Inconvenientes
    • Si el árbol no es B+ puede que el árbol esté desbalanceado o sea difícil el acceso secuencial.
• Hashing
  • Ventajas respecto a la organización indexada
    • Tiempo constante de acceso al registro.
  • Inconvenientes
    • Dependiendo de la función de hash se pueden producir sinónimos.

Implementación del tipo cola usando un vector

Fichero colaVector.hpp

#ifndef __COLA_VECTOR_HPP__
#define __COLA_VECTOR_HPP__

#include 
#include 
#include "colainterfaz.hpp"


/*!\brief Espacio de nombres para la asignatura Estructura de datos.*/
namespace ed 
{

//using std::vector;

 template
 class Cola:public ColaInterfaz
 {
  public:
   // constructor por defecto
   Cola(unsigned int limite=10)
   {
    assert(limite>0);
    
    _elementos.resize(limite);
    _limite=limite;
    _cabeza=0;
    _indice=0;
      }

   // constructor copia
   Cola(const Cola  &c)
   {
    _elementos.resize(c._elementos.size());
    _cabeza=c._cabeza;
    _indice=c._indice;
    _limite=c._limite;
    _elementos=c._elementos; // es un vector STL
   } 
   
   // no hace falta crearlas para esta implementación
   /*
   // Sobrecarga del operador de asignación con una cola
   Cola &operator=(const Cola &c) throw()
   {
    _cabeza=c._cabeza;
    _indice=c._indice;
    _limite=c._limite; 
    _elementos=c._elementos;
   }
   // Destructor
   ~Cola()
   {
   }
   */

    void insertar(const G &x) throw()
   {
    assert(not estaLlena());
    
    _elementos[ _indice % _limite ]= x;
    _indice=_indice+1;
   }

    void eliminar() throw ()
   {
    assert(not estaVacia());

    _cabeza=_cabeza+1;
   }
   
    const G & cabeza() const throw ()
   {
    assert(not estaVacia());
    
    return _elementos[_cabeza%_limite];
   }

   bool estaVacia () const throw ()
   {
    return (_indice==_cabeza)? true : false;
   }

   bool estaLlena ()  const throw (){
    return ((_indice-_cabeza)==_limite)? true : false;
   }

   private:
   std::vector  _elementos;
   unsigned int _indice;
   unsigned int _cabeza;
   unsigned int _limite;
 };


} //namespace ed

#endif //__COLA_VECTOR_HPP__

3.1. Los 4 componentes principales: boot, super-bloque, lista nodos índice, bloque de datos

Estructura de un Sistema de Archivos.

Cada sistema de archivos consta fundamentalmente de las siguientes partes:

• Boot (bloque de arranque) :
  Ocupa la parte del principio del sistema de archivos, normalmente el primer sector, y puede contener el código de boot o de arranque. Este código es un pequeño programa que se encarga de buscar el sistema operativo y cargarlo en memoria.
• Super-bloque:
  Ocupa el primer bloque lógico del disco y describe el estado del sistema de archivos. En el súper bloque se almacena la siguiente información del sistema de archivos:
  • El tamaño del sistema de archivos.
  • Número de bloques libres disponibles en el sistema de archivos.
  • Lista de bloques libres sistema de archivos.
  • Índice del siguiente bloque libre de la lista de bloques libres.
  • Tamaño de la lista de i-nodos.
  • Numero total de i-nodos libres en el sistema de archivos.
  • Lista de i-nodos libres en el sistema de archivos.
  • Indice al siguiente i-nodo libre en la lista de i-nodos libres.
  • Indicador que informa que el superbloque ha sido modificado
• Lista nodos índice (lista de i-nodos):
  Se encuentra a continuación del superbloque.
  Contiene una etrada por cada archivo, donde se guarda una descripcion del mismo:
  • Identificador del propietario del archivo y del grupo al que pertenece.
  • Tipo de archivo.
  • Derechos de acceso. Se reservan nueve bits para representar los derechos de lectura, escritura y ejecución (rwx) para el propietario, el grupo y el resto, y otros tres bits para definir si están o no activas las banderas setuid, setgid y sticky bit.
  • Fecha de la última modificación.
  • Contador de enlaces (links).
  • Tamaño del archivo.
  • Entradas para los bloques de dirección.
• Bloque de datos:
  Empieza a continuación de la lista i-nodos y ocupa el resto del sistema de archivos. En esta zona es donde se encuentra situado el contenido de los archivos a los que se hace referencia la lista de i-nodos. Cada uno de los bloques destinados a datos sólo puede ser asignado a un archivo, tanto si lo ocupa totalmente como si no.

Cada vez que un proceso accede a un archivo es necesario consultar el superbloque y la lista de i-nodos. Para evitar el acceso a disco continuamente, el sistema tiene siempre en memoria una copia del superbloque y la tabla de i-nodos. Esto plantea problemas de incostencia de los datos, así que un demonio se encarga de escribir periodicamente el superbloque y la lista de i-nodos en el disco si se han modificado.

Bibliografía

• http://www.ual.es/~acorral/DSO/Tema_4.pdf
• http://estigia.fi-b.unam.mx/Linux/prared05.html
• http://sopa.dis.ulpgc.es/ii-dso/lecminix/fs/super/Superbloque.pdf 
  
  

También en pdf.

Problema de lectores / escritores con prioridad de escritores

• Declaración de variables globales

semáforo lecMutex; // para modificar el numero de lectores
semáforo escMutex; // para modificar el numero de escritores
semáforo lectores; // para bloquear a los lectores cuando están los escritores
semáforo escritores; // para que solo esté un escritor en la S.C. a la vez

int nEscritores=0; // número de escritores en la S.C. 
int nLectores=0; // número de lectores en la S.C.  

• Inicialización

init( lecMutex, 1);
init( escMutex, 1);
init( lectores, 1);
init( escritores, 1);

• Lector


while(true){
  wait(lectores);
  wait(lecMutex);
  nLectores++;
  if(nLectores == 1)
    wait(escritores)
  signal(lecMutex)
  signal(lectores);
  // leer
  wait(lecMutex);
  nLectores--;
  if(nLectores == 0)
  signal(escritores);
  signal(lecMutex)
}

• Escritor


while(true){   
  wait(escMutex);
  nEscritores++;
  if(nEscritores == 1)
    wait(lectores)
  signal(escMutex)
  wait(escritores);
  // escribir
  signal(escritores);
  wait(escMutex);
  nEscritores--;
  if(nEscritores == 0)
    signal(lectores);
  signal(escMutex);
}


Nota: Las variables nLectores y nEscritores son globales ya que si fueran locales al empezar un hilo se inicializan a 0 una y otra vez.

Ruleta de la suerte en C

Otra de mis entradas del antiguo blog los programadores pelirrojos.

Bueno pues aquí tenéis un juego cutre en C que hice usando la librería de conio hace ya algún tiempo.
El juego consiste en hacer que los tres dibujos de las tres columnas que van pasando rápidamente coincidan, como en las maquinas tragaperras.
Cuado os lo descarguéis encontrareis el ejecutable, el código fuente (sin comentar ya que se entiende mas o menos bien) y las librerías necesarias para compilar el código fuente del juego.

AVISO PARA LUDOPATAS: no jueguen a esto que si no se envician y aquí no se gastan las perras.