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