Rafael Carlos Soriano Mármol
Carlos Sevilla Gómez
Borrar los siguientes elementos siguiendo el orden y aplicando las rotaciones adecuadas, indicando el tipo de estas
123. 127. 126. 124. 121. 37
miércoles, 17 de abril de 2013
lunes, 15 de abril de 2013
Actividad 1 ABOE: Insercción
Rafael Carlos Soriano Mármol
Carlos Sevilla Gómez
Insertamos 11, 8, 18 y 15 sin problemas
Insertamos el 13, lo que ocasiona un desequilibrio...
El nodo 18 tiene altura 2 por la izquierda y el nodo 8 tiene 0(diferencia >1), hay que equilibrar.
Aplico una rotación simple izquierda izquierda
Insertamos el 20, lo que ocasiona un desequilibrio...
El árbol queda desequilibrado por el hijo derecho del nodo 11 (diferencia de altura > 1, ya que por la izquierda la altura es 1, y por la derecha 3).
Aplico una rotación simple derecha derecha.
Insertamos el 7
Insertamos el 6, lo que ocasiona un desequilibrio...
El árbol queda desequilibrado por el hijo izquierdo del nodo 8 (diferencia de altura >1, altura 0 por su derecha, altura 2 por su izquierda)
Aplico una rotación simple izquierda izquierda.
Insertamos el 10, lo que ocasiona un desequilibrio...
El árbol queda desequilibrado por el hijo izquierdo del nodo 11.
Aplico una rotación doble izquierda derecha
Aplico una rotación doble izquierda derecha
Insertamos el 12, lo que ocasiona un desequilibrio...
Aplico una rotación doble derecha izquierda.
Insertamos el 21, lo que ocasiona un desequilibrio...
El árbol queda desequilibrado por el hijo derecho del nodo 18.
Aplico una rotación simple derecha derecha.
Aplico una rotación simple derecha derecha.
Actividad 1 sobre ABOE: Borrado
Rafael Carlos Soriano Mármol
Carlos Sevilla Gómez
Aunque no hayamos elegido borrado, aquí dejamos el procedimiento correcto (esperemos) para el borrado
Carlos Sevilla Gómez
Aunque no hayamos elegido borrado, aquí dejamos el procedimiento correcto (esperemos) para el borrado
miércoles, 19 de diciembre de 2012
Actividad Voluntaria 3: Memorias
Grupo 1:
Rafael Carlos Soriano Mármol
Carlos Sevilla Gómez
1.1. Asignación adyacente (best fit, first fit, worst fit)
1.2. Asignación mediante lista enlazada
1.1. Asignación adyacente (best fit, first fit, worstfit)
Cada uno de los archivos se almacena en un conjunto de bloques contiguos en el disco. Se registra el bloque inicial y la longitud del archivo, por lo que no se necesita ninguna estructura adicional para la asignación del espacio.
Ventajas:
Es el tipo de asignación más rápido.
La lectura completa se realiza en una sola operación.
No se necesita espacio adicional.
Es muy seguro ya que no existen estructuras globales de almacenamiento.
Desventajas:
§ Esta asignación es difícil de implantar, ya que debemos conocer el tamaño del archivo anteriormente, y si éste varía lo más normal es trasladarlo a un espacio más grande.
§ Fragmentación externa del disco, debido a que los espacios más pequeños entre archivos se desperdician (se puede solucionar mediante un compactado costoso en tiempo).
Uno de los sistemas operativos que utilizan esta asignación es Amoeba, en el cualno se permite modificar el tamaño del archivo, si no que la posible opción es borrarlo y crear uno nuevo con la información correspondiente.
Técnicas fundamentales para asignación de huecos:
¨ Best Fit(mejor ajuste): asigna el fichero al hueco en el que mejor encaje.
¨ First Fit(primer ajuste): asigna el fichero al primer hueco libre. Es más rápido ya que no inspecciona todos los huecos.
¨ Worst Fit(peor ajuste): asigna el fichero al hueco que deje un fragmento más grande.
1.2. Asignación mediante lista enlazada
En este tipo de asignación, la secuencia de bloques se mantiene como una lista simplemente enlazada. La primera palabra de cada bloque es un índice al siguiente bloque y se debe añadir una marca de fin de bloque al final del último bloque. En el directorio basta con indicar el primer bloque del archivo. Los bloques pueden estar dispersos en el disco.
Ventajas:
¨ Se evita la fragmentación externa y se pueden aprovechar todos los bloques del disco.
¨ No se necesita espacio adicional para estructuras que almacenen listas de bloques.
¨ El archivo puede crecer dinámicamente cuando hay bloques de discos libres.
¨ Al igual que con la asignación adyacente, es muy seguro ya que no hay estructuras globales de almacenamiento.
¨ Basta almacenar el puntero al primer bloque del archivo.
Desventajas:
¨ El acceso directo no es efectivo, es muy lento. En archivos grandes resulta totalmente inoperante.
¨ El tamaño de la información en cada bloque ya no es una potencia de 2.
¨ Espacio requerido para los punteros de enlace.
Muchos sistemas operativos desarrollados por Technical Systems Consultants (originalmente de West Lafayette Indiana y después de Raleigh, Carolina del Norte) usaron listas enlazadas simples como estructuras de ficheros. Un directorio de entrada apuntaba al primer sector de un fichero y daba como resultado porciones de la localización del fichero mediante punteros. Los sistemas que utilizaban esta técnica incluían Flex (para el Motorola 6800 CPU), mini-Flex (la misma CPU) y Flex9 (para el Motorola 6809 CPU). Una variante desarrollada por TSC se comercializó a Smoke Signal Broadcasting en California, usando listas doblemente enlazadas del mismo modo.
Rafael Carlos Soriano Mármol
Carlos Sevilla Gómez
1.1. Asignación adyacente (best fit, first fit, worst fit)
1.2. Asignación mediante lista enlazada
1.1. Asignación adyacente (best fit, first fit, worstfit)
Cada uno de los archivos se almacena en un conjunto de bloques contiguos en el disco. Se registra el bloque inicial y la longitud del archivo, por lo que no se necesita ninguna estructura adicional para la asignación del espacio.
Ventajas:
Es el tipo de asignación más rápido.
La lectura completa se realiza en una sola operación.
No se necesita espacio adicional.
Es muy seguro ya que no existen estructuras globales de almacenamiento.
Desventajas:
§ Esta asignación es difícil de implantar, ya que debemos conocer el tamaño del archivo anteriormente, y si éste varía lo más normal es trasladarlo a un espacio más grande.
§ Fragmentación externa del disco, debido a que los espacios más pequeños entre archivos se desperdician (se puede solucionar mediante un compactado costoso en tiempo).
Uno de los sistemas operativos que utilizan esta asignación es Amoeba, en el cualno se permite modificar el tamaño del archivo, si no que la posible opción es borrarlo y crear uno nuevo con la información correspondiente.
Técnicas fundamentales para asignación de huecos:
¨ Best Fit(mejor ajuste): asigna el fichero al hueco en el que mejor encaje.
¨ First Fit(primer ajuste): asigna el fichero al primer hueco libre. Es más rápido ya que no inspecciona todos los huecos.
¨ Worst Fit(peor ajuste): asigna el fichero al hueco que deje un fragmento más grande.
1.2. Asignación mediante lista enlazada
En este tipo de asignación, la secuencia de bloques se mantiene como una lista simplemente enlazada. La primera palabra de cada bloque es un índice al siguiente bloque y se debe añadir una marca de fin de bloque al final del último bloque. En el directorio basta con indicar el primer bloque del archivo. Los bloques pueden estar dispersos en el disco.
Ventajas:
¨ Se evita la fragmentación externa y se pueden aprovechar todos los bloques del disco.
¨ No se necesita espacio adicional para estructuras que almacenen listas de bloques.
¨ El archivo puede crecer dinámicamente cuando hay bloques de discos libres.
¨ Al igual que con la asignación adyacente, es muy seguro ya que no hay estructuras globales de almacenamiento.
¨ Basta almacenar el puntero al primer bloque del archivo.
Desventajas:
¨ El acceso directo no es efectivo, es muy lento. En archivos grandes resulta totalmente inoperante.
¨ El tamaño de la información en cada bloque ya no es una potencia de 2.
¨ Espacio requerido para los punteros de enlace.
Muchos sistemas operativos desarrollados por Technical Systems Consultants (originalmente de West Lafayette Indiana y después de Raleigh, Carolina del Norte) usaron listas enlazadas simples como estructuras de ficheros. Un directorio de entrada apuntaba al primer sector de un fichero y daba como resultado porciones de la localización del fichero mediante punteros. Los sistemas que utilizaban esta técnica incluían Flex (para el Motorola 6800 CPU), mini-Flex (la misma CPU) y Flex9 (para el Motorola 6809 CPU). Una variante desarrollada por TSC se comercializó a Smoke Signal Broadcasting en California, usando listas doblemente enlazadas del mismo modo.
viernes, 7 de diciembre de 2012
Actividad Voluntaria 2: Problema del lavabo unisex
Problema del lavabo unisex
Una oficina tiene en su quinta planta un único lavabo que es
unisex. Para el funcionamiento correcto de este lavabo los empleados han de cumplir las
siguientes reglas:
• En el lavabo no puede haber hombres y mujeres a la vez.
• La capacidad máxima es de 3 personas.
Escribe el pseudocódigo de los procesos Hombre() y Mujer() para que se garanticen estas
dos condiciones en el acceso al lavabo mediante semáforos.
semáforos:
mutex_hombre(1); //inicializados a 1(abierto)
mutex_mujer(1);
lavabo(1);
h_aforo(3); //capacidad máxima (3)
m_aforo(3);
esperando(1);
int contador_hombres=0;
int contador_mujeres=0;
hombre()
{
while(true){
wait(esperando); //espera aviso para entrar
wait(mutex_hombre); //espera aviso de paso para hombres
contador_hombres++; //incrementamos numero de hombres
if(contador_hombres==1)
wait(lavabo); //espera para usar el lavabo
signal(mutex_hombre); //avisa para permitir el paso a hombres
signal(esperando); //da el aviso para entrar
wait(h_aforo); //espera a que haya hueco y entra al lavabo
//usa lavabo
signal(h_aforo); //libera el hueco
wait(mutex_hombre); //espera aviso de paso para hombres
contador_hombres--;
if(contador_hombres==0) //si no hay hombres
signal(lavabo); //avisa que lavabo esta libre
signal(mutex_hombre) // avisa para permitir el paso a hombres
}
}
wait(esperando); //espera aviso para entrar
wait(mutex_hombre); //espera aviso de paso para hombres
contador_hombres++; //incrementamos numero de hombres
if(contador_hombres==1)
wait(lavabo); //espera para usar el lavabo
signal(mutex_hombre); //avisa para permitir el paso a hombres
signal(esperando); //da el aviso para entrar
wait(h_aforo); //espera a que haya hueco y entra al lavabo
//usa lavabo
signal(h_aforo); //libera el hueco
wait(mutex_hombre); //espera aviso de paso para hombres
contador_hombres--;
if(contador_hombres==0) //si no hay hombres
signal(lavabo); //avisa que lavabo esta libre
signal(mutex_hombre) // avisa para permitir el paso a hombres
}
}
mujer()
{
while(true){
wait(esperando);
wait(mutex_mujer);
contador_mujeres++;
if(contador_mujers==1)
wait(lavabo);
signal(mutex_mujer);
signal(esperando);
wait(h_aforo);
//usa lavabo
signal(h_aforo);
wait(mutex_mujer);
contador_mujeres--;
if(contador_mujers==0)
signal(lavabo);
signal(mutex_mujer)
}
}
while(true){
wait(esperando);
wait(mutex_mujer);
contador_mujeres++;
if(contador_mujers==1)
wait(lavabo);
signal(mutex_mujer);
signal(esperando);
wait(h_aforo);
//usa lavabo
signal(h_aforo);
wait(mutex_mujer);
contador_mujeres--;
if(contador_mujers==0)
signal(lavabo);
signal(mutex_mujer)
}
}
jueves, 18 de octubre de 2012
Resumen Tema 2 S.O
Pincharme para ir al resumen del tema 1!
2-Procesos
- Conceptos básicos
- Estados de un proceso
- Operaciones sobre un proceso
- Interrupciones
- Núcleo del S.O
- Los procesos en UNIX
Conceptos básicos
Proceso secuencial=>
instancia de programa en ejecución, proviene de gestión de ejecución
pseudoparalela en MULTICS, alternancia CPU entre diferentes tareas
En un procesador e
instante dado solo un proceso puede estar ejecutándose(muchos listos y
esperando)
Para ejecutar un
programa el so debe de crearle un proceso.
-El procesador de un sistema con
multiprogramacion ejecuta código de distintos procesos, dos procesos del mismo
programa se consideran dos secuencias de ejecución separadas
Traza de un proceso=> listado de la
secuencia de instrucciones que se ejecutan para el mismo
Sistema informatico=> conjunto de
procesos(incl. SO) en ejecución no homogénea cada uno con su propia cpu virtual
que alternan uso de procesador(es) reales
Obligaciones del SO como gestor de
procesos creación y eliminación
de procesos. Planificación de procesos, establecimiento de mecanismos para la
sincronización y comunicación de procesos, manejo de bloqueos mutuos. Tiene 2
niveles, Inferior(planificador de procesos) superior (todos los demás procesos
del sistema(user y kernel))
Principal función del planificador=>
intercambiar procesos activos por otros preparados para ser
ejecutados(minimizando tiempo requerido)
-Habrá tantos CPUs virtuales como procesos. En las CPUs reales irán todos los procesos y son los que mostrarán los resultados
Acciones para cambio de contexto=>
1-Almacenamiento del estado actual de proceso.
2-restauración
del proceso a ejecutar(necesita conocer el estado de todos los procesos,
almacenado en el PCB, bloque de control de procesos)
-Debe hacer un sistema eficiente. - Tiempo mínimo posible
Contenido estructura de datos PCB
Identificador
unico del proceso(numérico). Estado actual del proceso. Contador de
programa(direccion de la siguiente instrucción), registros de CPU, información
de planificación de la CPU, información de gestión de memoria, información de
contabilidad, información de estado de E/S
Estados de un proceso
Estado: situación del proceso en sistema.
Transición debido a acciones
del proceso o eventos externos.
Esquema de los 3 estados:
Listo(esperando
ejecución)=> En ejecución(proceso ejecutándose en CPU)=>A Listo o A
BLOQUEADO(esperando una e/s, o acción propia del proceso). Cuando ocurre una
E/S vuelve a listo.
Sistema de colas en el modelo de 3 estados=>
se necesitan como mínimo 2 colas (listos y bloqueados). El sistema elige de
cola de listos alguno para pasarlo a ejecución. Mas eficiente tener varias
colas bloqueados(una asociada a cada suceso)
Suspensión de un proceso=>Iniciativa
y reanudación externa al proceso(por el so). Sirve para optimizar rendimiento
del sistema(libera todos o parte de los recursos del proceso)
CAUSAS=> riesgo de fallo generalizado
del sistema(todos), carga excesiva del sistema(baja prioridad) mal
funcionamiento del proceso(hasta verificación)
El
proceso volverá a ejecutarse si encuentra una solución, si no, se cierra
automáticamente.
2 nuevos estados=> Listo suspendido cuando el proceso va a
ejecutarse se suspende, pero si se recupera(sol problema) vuelve a listo
Bloqueado suspendido el proceso
bloqueado pasa a suspendido y se busca solución si se encuentra pasa a
bloqueado, y si ocurre e/s pasa a listo suspendido.
Operaciones sobre procesos
Creación(reserva
estructuras y recursos y asigna prioridad)
despacho(se selecciona para ejecución
terminación(libera reservas).
Suspensión, reanudación, bloqueo(necesita evento)
despertado(se
produce el evento esperado), comunicación, sincronización.
Interrupciones
Interrupciones es un evento
producido por el Hardware del sistema que altera la secuencia en la cual el
procesador ejecuta las instrucciones.
Operaciones
1-
control pasa a SO, 2-el So almacena el estado completo del proceso 3- se
analiza la interrupción y se pasa el control a la rutina de servicio apropiada.
Se restaura el proceso interrumpido. 6 se ejecuta el siguiente proceso del
planificador.
Tipos básicos de interrupciones=> Sincronas/trap(generadas
por el proceso, indican al SO que hay que realizar operaciones que necesitan
privilegios que no tiene el usuario)
ASÍNCRONAS Hardware ante un evento, puede
no estar relacionado con el proceso) POLLING=> gestión de e/s mediante asíncronos.
Clases(IBM)=>Svc(llamada al supervisor, es
síncrono) E/s(asíncrono) Externas, reinicio, verificación del programa,
verificación de la maquina.
Implementacion=> gestión de
interrupciones con vectores completos. Genera un código de interrupción único(indice en tabla de vectores de interrupción). De la tabla se obtiene la
dirección de la rutina del servicio
El núcleo del Sistema Operativo
El núcleo del sistema operativo
reside en memoria de forma continua. Realiza todas las acciones criticas del
sistema (trap es la forma de acceso por proceso usuario). La ejecución del núcleo ha de ser rápida y optima (durante interrupción el núcleo inhabilita la recepción de nuevas interrupciones)
Los procesos en UNIX
Recopilación de noticias twitteadas (1)
https://twitter.com/i02somar
Desde inicio de curso hasta 18-octubre
(Propia) ¿NO conoces los discos SSD?,ya es hora de que lo hagas,puede mejorar hasta un 80% el rendimiento de tu pc http://t.co/DD0qasfd
(Propia) AMD RAMDISK: convierte tu memoria ram en un disco duro ultrarápido http://soriaanomarmol.blogspot.com/2012/10/amd-ramdisk-convierte-tu-memoria-ram-en.html
Kaspersky desarrolla sistema operativo para control industrial: http://t.co/d0Wdv9uT
El kernel Linux 3.6 ya está disponible http://t.co/VqeXhfjj
Novedades del kernel 3.6 http://t.co/hajm7439
Ya está disponible el manual de Ubuntu 12.10 http://www.muylinux.com/?p=26141
Microsoft ya trabaja en windows 9 http://t.co/lXz0J5vA
TDK hace posibles los discos duros de 6 Tbytes http://www.muycomputer.com/2012/10/04/tdk-hace-posibles-los-discos-duros-de-6-tbytes … "densidad de grabación de 1,5 Tbytes por pulgada cuadrada."
Windows 8 sufrirá de bugs al momento del lanzamiento, según Intel. http:// clic.bz/PZqa0j
Windows 8 supondrá un cambio radical en la forma en que vemos y trabajamos con los equipos informáticos que nos rodean: http://bit.ly/T0Uvj1
Según un estudio, el 53% de los usuarios que han probado Windows 8 prefieren Windows 7: http://www.webadictos.com.mx/2012/09/29/windows-8-prefieren-windows7/
RAM DDR4 se fabricará en 2013: http://elchapuzasinformatico.com/2012/02/memoria-ram-ddr4-entrara-en-fabricacion-en-2013/
AMD buscará un único socket para todas sus gamas: http://t.co/vLe9qxjx
Cuenta atrás para los nuevos procesadores AMD piledriver, basados en Vishera http://t.co/uzjosVK7
Ya está disponible la segunda generación de APUs (Unidades de Procesamiento Acelerado) de AMD Serie A. http://www.pcactual.com/articulo/actualidad/noticias/11735/amd_lanza_segunda_generacion_sus_apus_serie.html?utm_source=dlvr.it&utm_medium=twitter …
Echemos un vistazo a lo último de Intel y AMD.http://www.pcactual.com/articulo/laboratorio/especiales/11561/los_mejores_microprocesadores_bajo_nuestra_lupa.html …
Intel patenta el "olvida contraseñas" a través de las lineas de la manohttp://ht.ly/2siYFz
todos los modelos del procesador I5 http://www. clubedohardware.com.br/artigos/Todos-os-Modelos-do-Core-i5/1891/ … (En portugués, con ayuda del traductor de chrome se lee sin problemas + tablas)
Fuga de información en http://IEEE.org : 100 mil usuarios y contraseñas http://ht.ly/2sq6SZ
Europa realiza un simulacro de cibertaque contra sus redes http://t.co/MtGwMeka
aniversario del CD! 30 años de "Cedés"! http://t.co/jGWOvfhV
4 "cagadas" de apple desde la muerte de Steve Jobs http://www. fayerwayer.com/2012/10/4-fails-de-apple-desde-la-muerte-de-steve-jobs/ …
Video: http://t.co/sZjGB6oR evolución de Apple en 3 minutos
Desde inicio de curso hasta 18-octubre
(Propia) ¿NO conoces los discos SSD?,ya es hora de que lo hagas,puede mejorar hasta un 80% el rendimiento de tu pc http://t.co/DD0qasfd
(Propia) AMD RAMDISK: convierte tu memoria ram en un disco duro ultrarápido http://soriaanomarmol.blogspot.com/2012/10/amd-ramdisk-convierte-tu-memoria-ram-en.html
Kaspersky desarrolla sistema operativo para control industrial: http://t.co/d0Wdv9uT
El kernel Linux 3.6 ya está disponible http://t.co/VqeXhfjj
Novedades del kernel 3.6 http://t.co/hajm7439
Ya está disponible el manual de Ubuntu 12.10 http://www.muylinux.com/?p=26141
Microsoft ya trabaja en windows 9 http://t.co/lXz0J5vA
TDK hace posibles los discos duros de 6 Tbytes http://www.muycomputer.com/2012/10/04/tdk-hace-posibles-los-discos-duros-de-6-tbytes … "densidad de grabación de 1,5 Tbytes por pulgada cuadrada."
Windows 8 sufrirá de bugs al momento del lanzamiento, según Intel. http:// clic.bz/PZqa0j
Windows 8 supondrá un cambio radical en la forma en que vemos y trabajamos con los equipos informáticos que nos rodean: http://bit.ly/T0Uvj1
Según un estudio, el 53% de los usuarios que han probado Windows 8 prefieren Windows 7: http://www.webadictos.com.mx/2012/09/29/windows-8-prefieren-windows7/
RAM DDR4 se fabricará en 2013: http://elchapuzasinformatico.com/2012/02/memoria-ram-ddr4-entrara-en-fabricacion-en-2013/
AMD buscará un único socket para todas sus gamas: http://t.co/vLe9qxjx
Cuenta atrás para los nuevos procesadores AMD piledriver, basados en Vishera http://t.co/uzjosVK7
Ya está disponible la segunda generación de APUs (Unidades de Procesamiento Acelerado) de AMD Serie A. http://www.pcactual.com/articulo/actualidad/noticias/11735/amd_lanza_segunda_generacion_sus_apus_serie.html?utm_source=dlvr.it&utm_medium=twitter …
Echemos un vistazo a lo último de Intel y AMD.http://www.pcactual.com/articulo/laboratorio/especiales/11561/los_mejores_microprocesadores_bajo_nuestra_lupa.html …
Intel patenta el "olvida contraseñas" a través de las lineas de la manohttp://ht.ly/2siYFz
todos los modelos del procesador I5 http://www. clubedohardware.com.br/artigos/Todos-os-Modelos-do-Core-i5/1891/ … (En portugués, con ayuda del traductor de chrome se lee sin problemas + tablas)
Fuga de información en http://IEEE.org : 100 mil usuarios y contraseñas http://ht.ly/2sq6SZ
Europa realiza un simulacro de cibertaque contra sus redes http://t.co/MtGwMeka
aniversario del CD! 30 años de "Cedés"! http://t.co/jGWOvfhV
4 "cagadas" de apple desde la muerte de Steve Jobs http://www. fayerwayer.com/2012/10/4-fails-de-apple-desde-la-muerte-de-steve-jobs/ …
Video: http://t.co/sZjGB6oR evolución de Apple en 3 minutos
Suscribirse a:
Entradas (Atom)