martes, 5 de noviembre de 2013
HILOS VS PROCESOS
Procesos vs Hilos
PROCESOS
Un proceso es cualquier programa en ejecución. este necesita ciertos recursos para realizar satisfactoriamente su tarea:
- Tiempo de CPU.
- Memoria.
- Archivos.
- Dispositivos de E/S.
Las obligaciones del SO como gestor de procesos son:
- Creación y eliminación de procesos.
- Planificación de procesos (procurando la ejecución de múltiples procesos maximizando la utilización del procesador).
- Establecimiento de mecanismos para la sincronización y comunicación de procesos.
- Manejo de bloqueos mutuos.
A medida que un proceso se ejecuta cambia de estado. Cada proceso puede estar en uno de los estados:
- Nuevo (new): el proceso se está creando.
- En ejecución (running): el proceso está en la CPU ejecutando instrucciones.
- Bloqueado (waiting, en espera): proceso esperando a que ocurra un suceso (ej. terminación de E/S o recepción de una señal).
- Preparado (ready, listo): esperando que se le asigne a un procesador.
- Terminado (terminated): finalizó su ejecución, por tanto no ejecuta más instrucciones y el SO le retirará los recursos que consume.
Nota: Sólo un proceso puede estar ejecutándose en cualquier procesador en un instante dado, pero muchos procesos pueden estar listos y esperando.
Diagrama de estados de un proceso
Para que un programa se ejecute, el SO debe crear un proceso para él. En un sistema con multiprogramación el procesador ejecuta código de distintos programas que pertenecen a distintos procesos.
Aunque dos procesos estén asociados al mismo programa, se consideran dos secuencias de ejecución separadas, cada una de las cuales se considera un proceso.
Llamamos traza de un proceso al listado de la secuencia de instrucciones que se ejecutan para el mismo.
Creación de Procesos
los procesos se crean mediante una llamada al sistema de “crear proceso”, durante el curso de su ejecución. El proceso creador se denomina proceso padre, y el nuevo proceso, hijo.
Cuando un proceso crea un proceso nuevo, hay dos posibilidades en términos de ejecución:
- Padre e hijo se ejecutan concurrentemente.
- Padre espera por la finalización del hijo.
En UNIX existen dos funciones básicas para crear procesos: Fork y Exec.
Función fork(): Cuando se la llama crea un proceso hijo que es una copia casi exacta del proceso padre (duplicado del padre). Ambos procesos continúan ejecutándose desde el punto en el que se hizo la llamada a fork().
En UNIX los procesos se identifican mediante un “identificador de proceso” (PID) que es un entero único. Ambos procesos continúan su ejecución con la instrucción que sigue al fork() con una diferencia:
- El código que el hijo recibe del fork es cero.
- El que recibe del padre es el propio pid.
Funciones exec: Tras crear un nuevo proceso, después de llamar a fork, Linux llama a una función de la familia exec. Éstas funciones reemplazan el programa ejecutándose en el proceso por otro programa. Cuando un programa llama a una función exec, su ejecución cesa de inmediato y comienza a ejecutar el nuevo programa desde el principio, suponiendo que no ocurriera ningún error durante la llamada.
Generalmente uno de los dos procesos (padre o hijo) utiliza la llamada al sistema exec ve después del fork para reemplazar su espacio de memoria con un programa nuevo.
Nota: Si el padre no tiene nada que hacer mientras el hijo se ejecuta, puede emitir una llamada wait (esperar) para sacarse a sí mismo de la cola de procesos listos hasta que el hijo termine.
HILOS (threads)
Los hilos son un concepto relativamente nuevo de los SO. En este contexto, un proceso recibe el nombre de proceso pesado, mientras que un hilo recibe el nombre de proceso ligero. El término hilo se refiere sintáctica y semánticamente a hilos de ejecución.
El término multihilo hace referencia a la capacidad de un SO para mantener varios hilos de ejecución dentro del mismo proceso.
En un SO con procesos monohilo (un solo hilo de ejecución por proceso), en el que no existe el concepto de hilo, la representación de un proceso incluye su PCB, un espacio de direcciones del proceso, una pila de proceso y una pila núcleo.
En un SO con procesos multihilo, sólo hay un PCB y un espacio de direcciones asociados al proceso, sin embargo, ahora hay pilas separadas para cada hilo y bloques de control para cada hilo.
Estructura de los Hilos
Un hilo (proceso ligero) es una unidad básica de utilización de la CPU, y consiste en un contador de programa, un juego de registros y un espacio de pila.
Los hilos dentro de una misma aplicación comparten:
- La sección de código.
- La sección de datos.
- Los recursos del SO (archivos abiertos y señales).
Un proceso tradicional o pesado es igual a una tarea con un solo hilo.
Los hilos permiten la ejecución concurrente de varias secuencias de instrucciones asociadas a diferentes funciones dentro de un mismo proceso, compartiendo un mismo espacio de direcciones y las mismas estructuras de datos del núcleo.
Estados de un Hilo
Los principales estados de un hilo son: ejecución, preparado y bloqueado; y hay cuatro operaciones básicas relacionadas con el cambio de estado de los hilos:
- Creación: En general, cuando se crea un nuevo proceso se crea también un hilo para ese proceso. Posteriormente, ese hilo puede crear nuevos hilos dándoles un puntero de instrucción y algunos argumentos. Ese hilo se colocará en la cola de preparados.
- Bloqueo: Cuando un hilo debe esperar por un suceso, se le bloquea guardando sus registros. Así el procesador pasará a ejecutar otro hilo preparado.
- Desbloqueo: Cuando se produce el suceso por el que un hilo se bloqueó pasa a la cola de listos.
- Terminación: Cuando un hilo finaliza, se liberan su contexto y sus pilas.
Un punto importante es la posibilidad de que el bloqueo de un hilo lleve al bloqueo de todo el proceso. Es decir, que el bloqueo de un hilo lleve al bloqueo de todos los hilos que lo componen, aún cuando el proceso está preparado.
Recursos compartidos y no compartidos
Los hilos permiten la ejecución concurrente de varias secuencias de instrucciones asociadas a diferentes funciones dentro de un mismo proceso, compartiendo un mismo espacio de direcciones y las mismas estructuras de datos del núcleo.
Recursos compartidos entre los hilos:
- Código (instrucciones).
- Variables globales.
- Ficheros y dispositivos abiertos.
Recursos no compartidos entre los hilos:
- Contador del programa (cada hilo puede ejecutar una sección distinta de código).
- Registros de CPU.
- Pila para las variables locales de los procedimientos a las que se invoca después de crear un hilo.
- Estado: distintos hilos pueden estar en ejecución, listos o bloqueados esperando un evento.
PROCESOS v/s HILOS
Semejanzas: Los hilos operan, en muchos sentidos, igual que los procesos.
- Pueden estar en uno o varios estados: listo, bloqueado, en ejecución o terminado.
- También comparten la CPU.
- Sólo hay un hilo activo (en ejecución) en un instante dado.
- Un hilo dentro de un proceso se ejecuta secuencialmente.
- Cada hilo tiene su propia pila y contador de programa.
- Pueden crear sus propios hilos hijos.
Diferencias: Los hilos, a diferencia de los procesos, no son independientes entre sí.
- Como todos los hilos pueden acceder a todas las direcciones de la tarea, un hilo puede leer la pila de cualquier otro hilo o escribir sobre ella. Aunque pueda parecer lo contrario la protección no es necesaria ya que el diseño de una tarea con múltiples hilos tiene que ser un usuario único.
Ventajas: de los hilos sobre los procesos.
- Se tarda mucho menos tiempo en crear un nuevo hilo en un proceso existente que en crear un nuevo proceso.
- Se tarda mucho menos tiempo en terminar un hilo que un proceso.
- Se tarda mucho menos tiempo en conmutar entre hilos de un mismo proceso que entre procesos.
- Los hilos hacen más rápida la comunicación entre procesos, ya que al compartir memoria y recursos, se pueden comunicar entre sí sin invocar el núcleo del SO.
Ejemplos de uso de los hilos:
Trabajo interactivo y en segundo plano: En un programa de hoja de cálculo, un hilo podría estar leyendo la entrada del usuario y otro podría estar ejecutando las órdenes y actualizando la información.
Procesamiento asíncrono: Se podría implementar, con el fin de protegerse de cortes de energía, un hilo que se encargará de salvaguardar el buffer de un procesador de textos una vez por minuto.
Estructuración modular de los programas: Los programas que realizan una variedad de actividades se pueden diseñar e implementar mediante hilos.
HILOS y COLAS
PLANIFICACION DE HILOS
Con los hilos el concepto de ejecución se separa del resto de la definición de un proceso. Una aplicación puede implementarse como un conjunto de hilos que cooperan y ejecutan concurrentemente en el mismo espacio de direcciones.
En un monoprocesador, los hilos pueden usarse como una ayuda a la estructuración de un programa y para solapar la E/S y el procesamiento. Puesto que la penalización por el intercambio de hilos es mínima, comparada con el intercambio de procesos, éstos beneficios se llevan a cabo a bajo costo. Sin embargo, toda la potencia de los hilos se hace evidente en un sistema multiprocesador, puesto que pueden emplearse para obtener un paralelismo real en las aplicaciones posibilitando un aumento drástico del rendimiento. Sin embargo, puede demostrarse que, en aplicaciones que exijan una interacción considerable entre los hilos (paralelismo de grano medio), pequeñas diferencias en la planificación y gestión de hilos pueden tener
Concepto de hilo de ejecución
n ¿Qué es un hilo de ejecución?
u También llamado hebra, proceso ligero, flujo, subproceso o “thread”.
u Programa en ejecución que comparte la imagen de memoria y otros
recursos del proceso con otros hilos.
u Desde el punto de vista de programación: Función cuya ejecución se
puede lanzar en paralelo con otras.
u Un proceso puede contener uno o más hilos
.jpg)
COLAS
Colas: Es una estructura lineal de datos. Una cola es un grupo ordenado de elementos homogéneos
en el que los nuevos elementos se añaden por un extremo (el final) y se quitan
por el otro extremo (el frente). En las colas el elemento que entró primero
sale también primero, por ello se las llama como listas FIFO (first – in, first
– out) "primero en entrar, primero en salir".
La diferencia con las pilas es en el modo de entrada / salida
de datos; en las colas se realizan las inserciones al final de la lista, no al
principio.
Por eso, se usan para almacenar datos que necesitan ser procesados según
el orden de llegada.
C= C (1), C(2), ......., C(N)
Las eliminaciones se realizan al principio de la lista frente (front), y
las inserciones se realizan en el otro extremo final (rear).
Aplicaciones de las Colas
Las Colas también se utilizan en muchas maneras en los sistemas operativos para planificar el uso
de los distintos recursos de la computadora. Uno de estos recursos es la
propia CPU (Unidad Central de
Procesamiento).
Si esta trabajando en una sistema multiusuario, cuando le dice
a la computadora que ejecute un programa concreto, el sistema operativo añade su petición a su "cola
de trabajo".
Cuando su petición llega al frente de la cola, el programa solicitado
pasa a ejecutarse. Igualmente, las colas se utilizan para asignar tiempo a los distintos usuarios de los
dispositivos de entrada/salida (E/S), impresoras, discos, cintas y demás. El sistema
operativo mantiene colas para peticiones de imprimir, leer o escribir en cada
uno de estos dispositivos.
Se las puede representar por listas enlazadas o por arrays
C= Q(1), Q(2)......., Q(n).
En cualquier caso se necesitan dos punteros
·
frente (f)
·
final (r)
y la lista o array de n elementos (LONGMAX)
parte no utilizada de la lista Cola parte no utilizada de la lista
Para ver el gráfico seleccione la opción "Descargar" del menú
superior
·
Representación de una Cola, mediante un array.
100
|
264
|
119
|
48
|
frente final
·
Representación de una Cola mediante una lista enlazada
1 2 3 4
100
|
264
|
119
|
48
|
frente final
Las operaciones que se pueden realizar con una
cola son:
1. Acceder al primer
elemento de la Cola
2. Añadir un elemento al
final de la Cola
3. Eliminar el primer
elemento de la Cola
4. Vaciar una Cola
5. Verificar el estado de la Cola: vacía, Llena.
LimpiarPila (Cola)
Función: Inicializa Cola al estado vacío
Entrada: Cola a inicializar
Precondiciones: Ninguna
Salida: Cola (inicializada)
Postcondiciones: Cola está vacía
ColaVacía (Cola)
Función: Indica si la Cola esta vacía
Entrada: Cola a ser comprobada
Precondiciones: Ninguna
Salida: Cola Vacía (indicador Booleano)
Postcondiciones: ColaVacía= (cola está vacía)
ColaLlena (Cola)
Función: Indica si esta llena
Entrada: Cola a ser comprobada
Precondiciones: Ninguna
Salida: Cola llena (indicador Booleano)
Postcondiciones: ColaLlena = (cola está llena)
InsCola (Cola, Nuevo Elemento)
Función: Añade Nuevo Elemento al final de la Cola
Entrada: Cola, Nuevo Elemento a ser añadido
Precondiciones: Hay espacio en la Cola
Salida: Cola (cambiada)
Postcondiciones: Cola = Cola original con Nuevo Elemento añadido al
final
SupCola (Cola, ElemSuprimido)
Entrada: Cola
Precondiciones: Cola no esta vacía
Salida: Cola (cambiada)
ElemSuprimido
Postcondiciones: Cola = Cola original con el frente quitado
ElemSuprimido = elemento frente de la cola original
Definimos el array.
COLA = COLA(1), COLA(2), ...., COLA(n).
n = longitud máxima
f y r = punteros frente y final
x = elementos a insertar
procedimiento inserción
inicio
si r > = n
entonces escribir "desbordamiento de la pila"
sino r r + 1
si r > n
entonces r 1
finsi
COLA(r) x
finsi
{ poner el puntero f al valor 1, a fin de poder hacer eliminaciones posteriores }
si f = 0
entonces f 1
finsi
fin
El primer elemento introducido Q(n) que es el eliminado, se almacena en
una variable auxiliar x, para eliminar se tendrá que verificar que la cadena
este vacía.
Procedimiento eliminar
Inicio
{verificar cola vacía}
si f = 0
entonces escribir ‘cola vacía’
sino x cola (f)
f f + 1
si f > n
entonces f 1
finsi
finsi
{ verificar si la cola se ha quedado vacía y en ese caso dejar los
puntero frontal y final en condiciones iniciales, cero}
si f = 0 {condición de pila vacía}
entonces f 0
r 0
finsi
fin
Una operación muy útil es ver si la cola está vacía. Cola Vacía (Cola)
devuelve True si la Cola está vacía y False en los demás casos. Ponemos SupCola
cuando la cola no está vacía. Teóricamente ponemos siempre InsCola, porque en
principio, una cola no tiene un tamaño limitado. Sin embargo, sabemos de
nuestra experiencia con las pilas que ciertas implementaciones requiere que
veamos si la estructura está llena antes de añadir otro elemento.
Las colas pueden necesitar cantidad de memoria sobre todo si se diseña con un
gran numero de elementos. Para evitar este desperdicio de memoria, existe
un procedimiento para diseñar las colas mediante
una lista circular.
Para ver el gráfico seleccione la opción "Descargar" del menú
superior
De tal forma que el elemento Q(1), quede a continuación de Q (n).
Los algoritmos (procedimientos) de inserción y eliminación de una
cola circular se indican a continuación.
Suscribirse a:
Entradas (Atom)