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.

Reloj analógico en java

Hace tiempo programé un pequeño reloj en java con sus 3 agujas y todo. Os lo dejo aquí por si tenéis curiosidad.
La entrada es originalmente de lpp antiguo blog donde publicaba mis chorradas.

Los que quieran descargarse el código-> aquí
Los que tengan dudas que comenten.
Quien sepa algo de java le animo a que mire el código y vea lo fácil que meter otra aguja para por ejemplo los meses.

Historia de los sistemas operativos a partir de 1996

Evolución de Linux

Distribuciones de Linux

Después de la primera versión oficial del núcleo 1.0 de Linux en 1994 apareció en 1996  la versión  2.0 de Linux que aporta múltiples arquitecturas y sistemas multiprocesador.
También en 1996 empiezan a proliferar distribuciones de GNU/Linux como Debian.
En http://distrowatch.com/ podemos encontrar distribuciones de Linux para aburrir. Una de las mas populares es Ubuntu que fue lanzado el 20 de octubre de 2004.

Ubuntu

 


Ya en 1998 aparece KDE y mas tarde GNOME, desktops que hicieron que Linux fuera mucho mas fácil de usar.
En 2001 se lanza la version 2.4.x con bastantes mejoras en el sistema de archivos dando soporte para ficheros grandes.
En la versión 2.6.x del kernel se mejoró el rendimiento y se incorporaron novedades como el Virtual File System y soporte para GPUs AMD y NVIDIA y chips del tipo Wi-Fi.
Actualmente el kernel de linux ya va por la version 3.1, en http://kernelnewbies.org/Linux_3.1 podemos ver la gran cantidad de mejoras del que se producen en cada version.

Mac OS

Evolución de MAC
En 1997 aparece Mac OS 8 que incluyó una renovación al Finder que podía hacer más cosas al mismo tiempo, dando la opción de controlar múltiples aplicaciones al mismo tiempo con un mejor desempeño del  procesador. Tambien se mejoró el sistema de archivos con HFS+ y se dio soporte a dispositivos usb y firewire.
Mac OS 9  apareció en 1999 con opción de tener varios usuarios en una maquina y con soporte TCP/IP.

Mac OS X 10.5

En el 2001 aparece la versión 10 de Mac OS X que protegía la memoria, y así los programas no podían utilizar la información de otros programas, de esta forma el procesador no se bloqueaba memoria. En 2002 una nueva version del Mac OS X consiguió un incremento en su rendimiento, un nuevo y depurado look y  mayor soporte para redes de Microsoft.
En las ultimas versiones de Mac OS X se han mejorado el rendimiento y el aspecto del sistema. Tambien se han introducido nuevas características como el Time Machine y mejoras en el Finder.


Evolución  de Windows

Windows 98

En 1998 Microsoft lanza Windows 98/NT, algunas de las novedades mas importantes fueron un nuevo sistema para el manejo de los archivos (NTFS), soporte USB mejorado e Internet Explorer 5.

Microsoft Windows 2000 fue lanzado en el año 2000 el 17 de febrero, algunas de sus caracteristicas eran: gran estabilidad, soporte para varios procesadores y un alto nivel de seguridad.

Microsoft Windows ME (Millenium) una actualización de Windows 98 que toma algunas características de Windows 2000, primó la facilidad de uso, las mejoras en multimedia y comunicaciones e Internet.

En el año 2001 Microsoft lanza Windows XP el dia 25 de octubre del 2001 con soporte LAN, software de grabación de CDs, multimedia, escritorio remoto y manejo de usuarios. Tambien cambio el aspecto y se mejoró la instalación de drivers.

Windows XP

En  Marzo 28 del 2003 Microsoft lanza una version Windows XP para 64Bit.
Microsoft Windows Server 2003 es lanzado en Marzo 28 del 2003 enfocado a las redes.
En el 2006 Microsoft lanza Microsoft Windows Vista que requiere de hardware potente para ejecutarse. Algunas de las novedades más destacadas son las de agregar efectos visuales y varias opciones como mejor control en las cuentas de usuarios, firewall, mayor seguridad...

En el 2009 Microsoft lanza Windows 7con soporte completo para 64bits, rendimiento mejorado en procesadores multinúcleo y mejoras en la  GUI.

Bibliografía:

• http://es.wikipedia.org/wiki/Historia_de_Microsoft
• http://www.geekets.com/2009/03/historia-y-cronologia-de-los-sistemas-operativos-de-microsoft/
• http://www.maestrosdelweb.com/editorial/historia-y-evolucion-del-sistema-operativo-mac-os/
• http://es.wikipedia.org/wiki/Unix
• http://www.unix.org/what_is_unix/history_timeline.html
• http://www.dte.us.es/cursos/curso-introduccion-a-gnu-linux/docs_introlinuxeu/unidad1_pdf
• http://es.wikipedia.org/wiki/Distribuci%C3%B3n_Linux 
• http://kernelnewbies.org