Algoritmo "Cena de los filósofos"

Tambien conocido como "El problema de los filosofos cenando" o "El problema de los filosofos comensales" Es un problema clasico de la ciencia de la computacion que representa el problema de la sincronización de procesos de un sistema operativo.

Problema

"Hay cinco filósofos sentados alrededor de una mesa que pasan su vida cenando y pensando. Cada uno dispone de un plato de arroz y un palillo a la izquierda de su plato, pero para comer son necesarios dos palillos y cada filósofo sólo puede coger el que está a su izquierda o el que hay a su derecha. Con un solo palillo en la mano no tienen más remedio que esperar hasta que atrapen otro y puedan seguir comiendo.

Si dos filósofos adyacentes intentan tomar el mismo palillo a la vez se produce una condición de carrera: ambos compiten por lo mismo pero uno se queda sin comer.Si todos los filósofos cogen el palillo de su derecha al mismo tiempo, todos se quedarán esperando eternamente porque alguien debe liberar el palillo que les falta, cosa que nadie hará porque todos se encuentran en la misma situación (esperando que alguno deje su palillo)."

Video explicativo 

Fuentes consultadas

• http://www.hermanotemblon.com/el-problema-de-la-cena-de-los-filosofos/#sthash.uIV8Qk7p.dpuf
• https://www.youtube.com/watch?v=ECTxgF2Eu1Q

Kernel

Kernel 

También denominado el núcleo ó hueso, es el corazón del sistema operativo el cual permite la interacción entre el Hardware y Software.

Este es el encargado de administrar el procesador, gestionar programas y gestionar el hardware.

Tipos

• - Monolítico 
• - Micronúcleo
• - Híbrido 
• - Exonúcleos 

Monolítico: Hecho de una sola pieza 

Micronúcleo: un micronúcleo (microkernel o μkernel) es un tipo de núcleo de un sistema operativo que provee un conjunto de primitivas o llamadas mínimas al sistema para implementar servicios básicos como espacios de direcciones, comunicación entre procesos y planificación básica.
Híbrido:  Es un tipo de núcleo de un sistema operativo. Básicamente, es un micronúcleo que tienen algo de código «no esencial» en espacio de núcleo, para que éste se ejecute más rápido de lo que lo haría si estuviera en espacio de usuario.

Exonúcleos: El término exonúcleo (exokernel) se refiere a un sistema creado con fines de investigación en el Instituto Tecnológico de Massachusetts sobre OpenBSD y otros sistemas operativos similares. Su propósito es crear una especie de capa de software para otros sistemas virtuales.

Visualización de la interacción del Kernel

Fuentes de consulta 

• http://es.thefreedictionary.com/monol%C3%ADtico
• https://es.wikipedia.org/wiki/Micron%C3%BAcleo
• https://es.wikipedia.org/wiki/Núcleo_híbrido

Paralelismo

Paralelismo 

El paralelismo se basa en la informática, es una función que realiza el procesador para ejecutar varias tareas al mismo tiempo. Es decir, puede realizar varios cálculos simultáneamente, basado en el principio de dividir los problemas grandes para obtener varios problemas pequeños, que son posteriormente solucionados en el paralelo.

Niveles 

• Interinstrucciones
• Datos
• Tarea
• Intrainstrucciones

Clasificación de los sistemas

• SISD (Solo un flujo de instrucciones)
• MISD (Nivel de datos)
• SIMD (Diferentes operaciones entre datos)
• MIMD (Múltiples instrucciones múltiples datos)

El paralelismo es bien manejado en la arquitectura RISC

Tipos de paralelismo

Paralelismo independiente

No existe sincronización explícita entre los procesos. Cada uno representa una aplicación o trabajo separado e independiente. Un uso clásico de este tipo de paralelismo de dan en sistemas de tiempo compartido. 

Paralelismo de grano grueso y muy grueso

Existe una sincronización entre los procesos pero a un nivel muy burdo. Este tipo de situación se maneja fácilmente con un conjunto de procesos concurrentes ejecutando en un monoprocesador multiprogramado y puede verse respaldado por un multiprocesador con escasos cambios o incluso ninguno en el software del usuario.

Paralelismo de grano fino

Significa un uso del paralelismo mucho más complejo que el que se consigue con el uso de hilos. Si bien gran parte del trabajo se realiza en aplicaciones muy paralelas, este es un campo, hasta el momento, muy especializado y fragmentado, con varias soluciones diferentes.

Fuentes de consulta 

• https://sistemaoperativo.wikispaces.com/Paralelismo
• http://people.ac.upc.edu/marisa/miso/concurrencia.pdf

RISC - CISC

RISC

En la arquitectura computacional, RISC (del inglés reduced instruction set computer) es un tipo de microprocesador con las siguientes características fundamentales:

• Instrucciones de tamaño fijo y presentadas en un reducido número de formatos.
• Sólo las instrucciones de carga y almacenamiento acceden a la memoria de datos.

El objetivo de diseñar máquinas con esta arquitectura es posibilitar la segmentación y el paralelismo en la ejecución de instrucciones y reducir los accesos a memoria.

Ventajas

• La CPU trabaja mas rápido al utilizar menos ciclos de reloj para ejecutar instrucciones.
• Utiliza un sistema de direcciones no destructivas en RAM. Eso significa que a diferencia de CISC, RISC conserva después de realizar sus operaciones en memoria los dos operandos y su resultado, reduciendo la ejecución de nuevas operaciones.
• Cada instrucción puede ser ejecutada en un solo ciclo del CPU

CISC 

En la arquitectura computacional, CISC (complex instruction set computer) es un modelo de arquitectura de computadora.
Los microprocesadores CISC tienen un conjunto de instrucciones que se caracteriza por ser muy amplio y permitir operaciones complejas entre operandos situados en la memoria o en los registros internos, en contraposición a la arquitectura RISC.

Ventajas

• Reduce la dificultad de crear compiladores.
• Permite reducir el costo total del sistema.
• Reduce los costos de creación de sftware.
• Mejora la compactación de código.
• Facilita la depuración de errores.

RISC vs CISC 

Fuentes consultadas

• http://rcmcomputointegrado.blogspot.com.co/2012/03/arquitectura-risc-y-cisc.html
• https://es.wikipedia.org/wiki/Reduced_instruction_set_computing
• https://es.wikipedia.org/wiki/Complex_instruction_set_computing

Bloqueo Mutuo

Bloqueo Mutuo 

También es llamado interbloqueo, traba mortal, deadlock ó abrazo mortal es un bloqueo permanente de un conjunto de procesos que compiten por un recurso del sistema.

Los bloqueos mutuos se producen por diferentes condiciones entre ellas:

1. Exclusión mutua 
2. Espera circular 
3. No apropiación
4. Retención y espera 

Exclusión mutua 

Existencia de al menos de un recurso compartido por los procesos, al cual sólo puede acceder uno simultáneamente.

Condición de retención y espera

Al menos un proceso P_i ha adquirido un recurso R_i, y lo retiene mientras espera al menos un recurso R_j que ya ha sido asignado a otro proceso.

No expropiación 

Los recursos no pueden ser expropiados por los procesos, es decir, los recursos sólo podrán ser liberados voluntariamente por sus propietarios.

Espera Circular

Dado el conjunto de procesos P₀...P_m(subconjunto del total de procesos original),P₀ está esperando un recurso adquirido por P₁, que está esperando un recurso adquirido por P₂,... ,que está esperando un recurso adquirido por P_m, que está esperando un recurso adquirido por P₀. Esta condición implica la condición de retención y espera.

Fuentes de consulta

• https://www.google.com.co/search?q=condiciones+bloqueo+mutuo&espv=2&biw=1440&bih=799&source=lnms&tbm=isch&sa=X&ved=0ahUKEwj-hO_J1cHMAhULJB4KHQ_jCjEQ_AUIBigB&dpr=1#imgrc=6h2dCYIDlwBjFM%3A
• https://es.wikipedia.org/wiki/Bloqueo_mutuo

Algoritmos apropiativos y no apropiativos

Algoritmos apropiativos

Una vez que se le ha otorgado la cpu a un proceso, le puede ser retirada

• SRTF “Short Remaining Time First”

Es similar al SJN, con la diferencia de que si un nuevo proceso pasa a listo se activa el dispatcher  para ver si es más corto que lo que queda por ejecutar del proceso en ejecución. Si es así, el proceso en ejecución pasa a listo y su tiempo de estimación se decremento con el tiempo que ha estado ejecutándose.

• Round Robin

Es el más sencillo, equitativo y antiguo. A cada proceso se le asigna un intervalo de tiempo llamado Quantum, durante el cual se le permite ejecutarse. Al terminarse el tiempo y aún se ejecuta, el sistema operativo se apropia del CPU y se lo da a otro proceso.Si el proceso termina antes de su tiempo, el cambio se CPU se hace cuando el proceso se bloquee o termine. La implementación básicamente es una lista donde al hacer un cambio de procesos, se extrae el proceso actual y se inserta al final

Algoritmos no apropiativos

Una vez que se le ha otorgado la cpu a un proceso, no le puede ser retirada

• Sigue el Trabajo Más Corto (SJN)

Es un algoritmo de planificación no apropiativa que maneja los trabajos con base en la duración de su ciclo de CPU.

El algoritmo SJN revisa los trabajos y los programa para su procesamiento en orden ascendente, es decir de menor a mayor.

• FIFO)

Tal vez la disciplina más simple de planificación sea la de primeras entradas primeras salidas (PEPS).

También llamado FCFS(First-come, first-served) por sus siglas en inglés

Los procesos se despachan de acuerdo con su tiempo de llegada a la cola de procesos listos. Cuando un proceso tiene la CPU, se ejecuta hasta terminar. Es junto en el sentido formal, pero algo injusta en cuanto a que los trabajos largos hacen esperar a los cortos y los trabajos sin importancia hacen esperar a los importantes. 

Fuentes consultadas

• http://so-wiki.wikifoundry.com/page/Apropiativos+y+No+Apropiativos 
• http://eisc.univalle.edu.co/~oscarbed/SO/clasePlanificacionApropiativa.pdf
• http://sistemasoperativos.angelfire.com/html/2.6.1.html
• https://emiliosedanogijon.wordpress.com/2014/09/16/algoritmos-de-planificacion-fcfs-sjf-srtf-round-robind/

Inanición

Inanición

Se produce cuando algún proceso dentro del sistema no puede satisfacer su necesidad de recursos debido a que otros procesos lo están utilizando continuamente. Este término básicamente se presenta en algoritmos que determinan asignación por importancia o asignación por tamaño.

En los sistemas operativos las tareas dejan de llegar allí puede haber tareas poco importantes pero que esperan su turno aún así las tareas más importantes que van llegando se van asignando.

Como las tareas nunca dejan de llegar existen trabajos poco o muy importantes a los cuales se les permitirá el uso de recursos.

La terminología de la inanición se puede determinar como la falta de Recursos


Exposición realizada en clase 

Temas:

1. Inanición 
2. Algoritmo "Cena de los filósofos"

http://prezi.com/u37iomxox2gx/?utm_campaign=share&utm_medium=copy

Paginación - Segmentación

Paginación

El método de la paginación consiste básicamente en dividir la memoria física en pequeños espacios fijos del mismo tamaño, una vez se proceda a asignar la tarea se debe asignar el tipo de inserción, para el caso presentado en la clase bajo los algoritmos FIFO y LRU cuyo resultado apunta a la paginación por demanda.

Segmentación

División lógica de las tareas.
Básicamente se establece que la tarea que va llegando se va segmentando y posteriormente se pagina.

Finalmente se obtiene el siguiente recuadro con los temas aprendidos durante el corte.

Memoria RAM

MemoriaRAM (Random Access Memory)

La memoria de acceso aleatorio permite el almacenamiento de tareas temporales de los programas que se ejecuten en el ordenador.

Tipos de memorias:

• SDRAM: Permite el manejo de sistemas operativos de 32 y 64 bits. Posee 168 terminales que al tener contacto son físicamente independientes, desde esta operación se les denomina memorias duales.
• DDR: (Dual Data Rate) Es la sucesora de la SDRAM y esta contiene 184 terminales, a partir de este modelo de memorias RAM permiten la transmisión doble de datos debido a la incorporación de dos canales de manera simultanea.
• DDR2: Cuentan con 240 terminales funcionan con aproximadamente 1.8 voltios, estas se instalan de manera automática en sistema operativo sin la necesidad de reiniciar el ordenador para tomar sus respectivos cambios.
• DDR3: Son la tercera generación de las memorias RAM también cuentan con 240 terminales y funcionan con aproximadamente 1.5 voltios. Estrictamente funcionan con sistemas operativos de 64 bits que a su vez se instalan automáticamente en el sistema.

Imagen sobre los diferentes tipos de memoria

Fuentes consultadas

• http://www.areatecnologia.com/TECNOLOGIA%20EN%20IMAGENES/TIPOS%20DE%20MEMORIAS%20RAM.htm 
• http://www.ecured.cu/Memorias_SDRAM
• http://es.slideshare.net/aosoriodiaz/memorias-ddr-12229372 

Linux

LINUX

Sistema operativo de código abierto que comenzó a ser desarrollado en 1984. Es el desarrollo de código abierto mas importante de los últimos años pues este puede ser utilizado, modificado y distribuido libremente bajo los términos de la GLP (Licencia Publica General - GNU). Llamado oficialmente "GNU/Linux" o como comúnmente se llama "Linux".

Algunos directorios:

1. Bin: Directorio donde se alojan los programas propios del sistema operativo ejecutados mediante comandos como cp, mv, cat, chown, etc.
2. Boot: Directorio donde se alojan los archivos necesarios para el inicio del sistema, desde la configuración de GRUB LILO (Gestor de arranque) hasta el kernel ó núcleo del sistema.
3. Dev: Este directorio de se encarga del almacenamiento de los dispositivos (usb).
4. Home: Directorio donde se aloja la información personal de cada usuario del sistema.
5. Lib: Contiene las biliotecas del sistema asi como los modulos y controladores del sistema
6. Mnt: Montaje temporal de unidades
7. Etc: Configuración de los programas instalados asi como otros scripts que se ejecutan al iniciar el sistema.

Ejemplos vistos en la clase

Fuentes consultadas

• https://es.wikipedia.org/wiki/GNU/Linux#/media/File:Gnulinux.svg
• http://www.linuxdevcenter.com/pub/a/linux/2008/01/22/lilo-and-grub-boot-loaders-made-simple.html
• http://aprendeenlinea.udea.edu.co/lms/ova/file.php/6/Sesion2/Archivos_y_permisosE.htm

Particiones Fijas - Dinámicas

Particiones Fijas - Dinámicas

Particiones FIJAS

División física de almacenamiento de datos, pues en ella se divide la memoria libre en partes de igual o diferentes tamaños.

También llamada multiprogramación se puede asignar una tarea que contenga el mismo tamaño y de no cumplir esta condición estará en cola para que en un espacio que contenga su mismo o mayor tamaño pueda entrar posterior a la salida de una de ellas.



Particiones DINÁMICAS

En las particiones dinámicas, se utiliza toda la memoria al cargar las primeras tareas, pero según ingresen las nuevas tareas el algoritmo verifica que al no ser del tamaño de la tarea que a salido se acomodan los espacio disponibles y continuos para ampliar su tamaño de modo que la nueva tarea pueda ingresar.


Ilustración 

Fuentes consultadas

• http://elloboestepario2.blogspot.com.co/2012/04/administacion-de-memoria.html
• https://sites.google.com/site/osupaep2010/administracion-de-memoria-1/multiprogramacion-con-particiones-fijas