lunes, 27 de octubre de 2008

2.1.- CONCEPTO DE PROCESO.

Un proceso no es mas que un programa en ejecución, e incluye los valores actuales del contador de programa, los registros y las variables. Conceptualmente cada unos de estos procesos tiene su propia CPU virtual. Desde luego, en la realidad la verdadera CPU conmuta de un proceso a otro.
Un proceso es un concepto manejado por el sistema operativo que consiste en el conjunto formado por:
Las instrucciones de un programa destinadas a ser ejecutadas por el microprocesador.
Su estado de ejecución en un momento dado, esto es, los valores de los registros de la CPU para dicho programa.
Su memoria de trabajo, es decir, la memoria que ha reservado y sus contenidos.
Otra información que permite al sistema operativo su planificación.
Esta definición varía ligeramente en el caso de sistemas operativos multihilo, donde un proceso consta de uno o más hilos, la memoria de trabajo (compartida por todos los hilos) y la información de planificación. Cada hilo consta de instrucciones y estado de ejecución.
Los procesos son creados y destruidos por el sistema operativo, así como también este se debe hacer cargo de la comunicación entre procesos, pero lo hace a petición de otros procesos. El mecanismo por el cual un proceso crea otro proceso se denomina bifurcación (fork). Los nuevos procesos pueden ser independientes y no compartir el espacio de memoria con el proceso que los ha creado o ser creados en el mismo espacio de memoria.
En los sistemas operativos multihilo es posible crear tanto hilos como procesos. La diferencia estriba en que un proceso solamente puede crear hilos para sí mismo y en que dichos hilos comparten toda la memoria reservada para el proceso.
En este modelo: todo software ejecutable de la computadora, lo que a menudo incluye al sistema operativo, esta organizado en una serie del proceso secuenciales, o simplemente procesos.
la idea clava aquí es que un proceso es una actividad de algún tipo: tiene programa, entrada, salida y un estado. Se puede compartir un procesador entre varios procesos, usando algún algoritmo de planificación para determinar cuando debe de trabajar en un proceso para atender a uno distinto.
Jerarquías de procesos

Los sistemas operativos que manejan el concepto de proceso deben contar con algún mecanismo para crear todos los procesos necesarios. en los sistemas muy sencillos, o en los diseñados para ejecutar solo una aplicación.
En otros sistemas operativos existen llamadas al sistema para crear un proceso, cargar su memoria y ponerlo en ejecutar. Sea cual sea la naturaleza exacta de la llamada al sistema. Los procesos necesitan poder crear otros procesos.
En MINIX, los procesos se crean con la llamada al sistema FORK (bifurcar), que crea una copia idéntica del proceso invocador. El proceso hijo también puede ejecutar FORK, así que es posible tener un árbol de proceso.

2.2.- ESTADOS Y TRANSICIONES DE LOS PROCESOS.

El principal trabajo del procesador es ejecutar las instrucciones de máquina que se encuentran en memoria principal. Estas instrucciones se encuentran en forma de programas. Para que un programa pueda ser ejecutado, el sistema operativo crea un nuevo proceso, y el procesador ejecuta una tras otra las instrucciones del mismo. En un entorno de multiprogramación, el procesador intercalará la ejecución de instrucciones de varios programas que se encuentran en memoria. El sistema operativo es el responsable de determinar las pautas de intercalado y asignación de recursos a cada proceso.
Aunque cada proceso se una entidad independiente, con su propio contador de programa y estado interno, los procesos a menudo necesitan interactuar con otros procesos. Un proceso podría generar ciertas salidas que otro proceso utilizan como entradas, en el comando de Shell.
Cuando un proceso se bloquea, lo que hace porque le es imposible continuar lógicamente, casi siempre porque esta separando entradas que todavía no están disponibles, también puede ser que un programa que conceptualmente esta listo y en condiciones de ejecutarse sea detenido porque el sistema operativo ha decidido asignar la CPU a otro proceso durante un tiempo. Estas dos condiciones son totalmente distintas, en el primer caso, la suspensión es inherente al problema (no es posible procesar la línea de comandos del usuarios antes de que este la teclee). En el segundo caso, se trata de un tecnicismo del sistema (no hay suficiente: CPU para darle a cada proceso su propio procesador privado).

1.- Ejecutándose (usando realmente la CPU en este instante).

2.- Listo (se puede ejecutar, pero se suspendió temporalmente para dejar que otro proceso se ejecute).

3.- Bloqueo (no puede ejecutarse en tanto no ocurra algún evento externo).

Puede haber cuanto transiciones entre estos tres estados, como se muestra.

La transacción 1 ocurre cuando un proceso descubre que no puede continuar. En algunos sistemas el proceso debe ejecutar una llamada al sistema, block, para pasar al estado bloqueado. En otros sistemas, incluido MINIX, cuando un proceso lee de un conducto o de un archivo especial, (p.ej., una terminal) y no hay entradas disponibles, se bloquea automáticamente.
Las transiciones 2 y 3 son causadas por el planificador de procesos, un parte del sistema operativo , sin que el proceso se entere siquiera de ellas.

La transición 2 ocurre cuando el planificador decide que el proceso en ejecución ya se ejecuto durante suficiente tiempo y es ahora de dejar que otros procesos tengan algo de tiempo de CPU.

La transacción 3 ocurre cuando todos los demás procesos han disfrutado de una porción justa y es hora de que el primer proceso reciba otra vez la CPU para ejecutarse.

La transacción 4 ocurre cuando acontece el suceso externo que un proceso estaba esperando (como la llegada de entrada). Sin ningún otro proceso se esta ejecutando en ese instante, se dispara de inmediato la transacción 3 y el proceso comienza a ejecutarse.

En caso contrario, el proceso tal vez tenga que esperar en el estado listo durante cierto tiempo hasta que la CPU este disponible. Usando el modelo de procesos, es mucho mas fácil visualizar lo que esta sucediendo dentro del sistema. [1]



[1] Andrew s. tanenbaum & Alvert s. woodhull (1998). Sistemas operativos Diseño e implementación. (2da. Ed)

2.3 PROCESOS LIGEROS (HILOS O HEBRAS)

El concepto de proceso engloba dos conceptos separados y potencialmente independientes: uno relativo a la propiedad de recursos y otro que hace referencia a la ejecución.
Unidad que posee recursos: A un proceso se le asigna un espacio de memoria y, de tanto en tanto, se le puede asignar otros recursos como dispositivos de E/S o ficheros.
Unidad a la que se le asigna el procesador: Un proceso es un flujo de ejecución (una traza) a través de uno o más programas. Esta ejecución se entremezcla con la de otros procesos. De tal forma, que un proceso tiene un estado (en ejecución, listo, etc) y una prioridad de expedición u origen. La unidad planificada y expedida por el sistema operativo es el proceso.
En la mayoría de los sistemas operativos, estas dos características son, de hecho, la esencia de un proceso. Sin embargo, son independientes, y pueden ser tratadas como tales por el sistema operativo. Esta distinción ha conducido en los sistemas operativos actuales a desarrollar la construcción conocida como thread, cuyas traducciones más frecuentes son hilo, hebra y proceso ligero. Si se tiene esta división de características, la unidad de asignación de la CPU se conoce como hilo, mientras que a la unidad que posee recursos se le llama proceso.
Dentro de un proceso puede haber uno o más hilos de control cada uno con:
· Un estado de ejecución (en ejecución, listo, bloqueado).
· Un contexto de procesador, que se salva cuando no esté ejecutándose.
· Una pila de ejecución.
· Algún almacenamiento estático para variables locales.
· Acceso a la memoria y a los recursos de ese trabajo que comparte con los otros hilos.
Los beneficios clave de los hilos se derivan de las implicaciones del rendimiento: se tarda menos tiempo en crear un nuevo hilo de un proceso que ya existe, en terminarlo, y en hacer un cambio de contexto entre hilos de un mismo proceso. Al someter a un mismo proceso a varios flujos de ejecución se mantiene una única copia en memoria del código, y no varias.
Un ejemplo de aplicación que podría hacer uso de los hilos es un servidor de ficheros de una red de área local. Cada vez que llega una solicitud de una operación sobre un fichero, se puede generar un nuevo hilo para su gestión. El servidor gestiona multitud de solicitudes, por tanto, se pueden crear y destruir muchos hilos en poco tiempo para dar servicio a estas peticiones. Si el servidor es un multiprocesador, se pueden ejecutar varios hilos de un mismo proceso simultáneamente y en diferentes procesadores.[1]

Un proceso ligero (thread o hebra) es un programa en ejecución que comparte la imagen de la memoria y otras informaciones con otros procesos ligeros.






Figura 1 Procesos ligeros

Es una unidad básica de utilización de la CPU consistente en un juego de registros y un espacio de pila. Comparte el código, los datos y los recursos con sus hebras pares

Una tarea (o proceso pesado) está formada ahora por una o más hebras

Una hebra sólo puede pertenecer a una tarea




Figura 2 Tareas con una y varias hebras

CARACTERISTICAS


Se comparten recursos. La compartición de la memoria permite a las hebras pares comunicarse sin usar ningún mecanismo de comunicación inter-proceso del SO.

La conmutación de contexto es más rápida gracias al extenso compartir de recursos

No hay protección entre las hebras. Una hebra puede escribir en la pila de otra hebra del mismo proceso

Estado de los procesos ligeros


Un proceso ligero puede estar ejecutando, listo o bloqueado.






Figura 3 Estados de los Procesos ligeros


Paralelismo
Los procesos ligeros permiten paralelizar una aplicación.[2]



Figura 4 Paralelismo

[1] Milenkovic M. (1994). Sistemas Operativos. Conceptos y Diseño, 2ª Edición, McGraw-Hill.
Stallings, W. (1993).Computer Organization and Architecture, 3ª Edición. New York: Macmillan.
[2] HILOS (THREAD) (n.d.). Extraído el 24 de octubre de 2008 desde http://xue.unalmed.edu.co/~gsanchez/downloads/hilos.pdf

2.4 CONCURRENCIA Y SECUENCIABILIDAD.

La concurrencia comprende un gran número de cuestiones de diseño, incluyendo la comunicación entre procesos, comparición y competencia por los recursos, sincronización de la ejecución de varios procesos y asignación del tiempo de procesador a los procesos y es fundamental para que existan diseños como Multiprogramación, Multiproceso y Proceso distribuido
Los procesos son concurrentes si existen simultáneamente. Cuando dos o más procesos llegan al mismo tiempo a ejecutarse, se dice que se ha presentado una concurrencia de procesos. Es importante mencionar que para que dos o más procesos sean concurrentes, es necesario que tengan alguna relación entre ellos
La concurrencia puede presentarse en tres contextos diferentes:
• Varias aplicaciones: La multiprogramación se creó para permitir que el tiempo de procesador de la máquina fuese compartido dinámicamente entre varios trabajos o aplicaciones activas.
• Aplicaciones estructuradas: Como ampliación de los principios del diseño modular y la programación estructurada, algunas aplicaciones pueden implementarse eficazmente como un conjunto de procesos concurrentes.
• Estructura del sistema operativo: Las mismas ventajas de estructuración son aplicables a los programadores de sistemas y se ha comprobado que algunos sistemas operativos están implementados como un conjunto de procesos.
Existen tres modelos de computadora en los que se pueden ejecutar procesos concurrentes:
• Multiprogramación con un único procesador. El sistema operativo se encarga de ir repartiendo el tiempo del procesador entre los distintos procesos, intercalando la ejecución de los mismos para dar así una apariencia de ejecución simultánea.
• Multiprocesador. Es una maquina formada por un conjunto de procesadores que comparten memoria principal. En este tipo de arquitecturas, los procesos concurrentes no sólo pueden intercalar su ejecución sino también superponerla.• Multicomputadora. Es una maquina de memoria distribuida, que está formada por una serie de computadoras. En este tipo de arquitecturas también es posible la ejecución simultánea de los procesos sobre los diferentes procesadores.
En general, la concurrencia será aparente siempre que el número de procesos sea mayor que el de procesadores disponibles, es decir, cuando haya más de un proceso por procesador. La concurrencia será real cuando haya un proceso por procesador. Aunque puede parecer que la intercalación y la superposición de la ejecución de procesos presentan formas de ejecución distintas, se verá que ambas pueden contemplase como ejemplos de procesos concurrentes
Existen diversas razones que motivan la ejecución de procesos concurrentes en un sistema:
• Facilita la programación de aplicaciones al permitir que éstas se estructuren como un conjunto de procesos que cooperan entre sí para alcanzar un objetivo común.
• Acelera los cálculos. Si se quiere que una tarea se ejecute con mayor rapidez, lo que se puede hacer es dividirla en procesos, cada uno de los cuales se ejecuta en paralelo con los demás.
• Posibilita el uso interactivo a múltiples usuarios que trabajan de forma simultánea.• Permite un mejor aprovechamiento de los recursos, en especial de la CPU, ya que pueden aprovechar las fases de entrada-salida de unos procesos para realizar las fases de procesamiento de otros.
Así como existen las razones que motivan la ejecución de procesos concurrentes, también existen sus contras:
• Inanición e interrupción de procesos
• Ocurrencia de bloqueos
• Que dos o más procesos requieran el mismo recurso (No apropiativo)
Tipos de procesos concurrentes.
Los procesos que ejecutan de forma concurrente en un sistema se pueden clasificar como:
Proceso independiente: Es aquel que ejecuta sin requerir la ayuda o cooperación de otros procesos. Un claro ejemplo de procesos independientes son los diferentes shells que se ejecutan de forma simultánea en un sistema.
Procesos son cooperantes: Son aquellos que están diseñados para trabajar conjuntamente en alguna actividad, para lo que deben ser capaces de comunicarse e interactuar entre ellos.
En ambos tipos de procesos (independientes y cooperantes), puede producirse una serie de interacciones entre ellos y pueden ser de dos tipos:
• Interacciones motivadas porque los procesos comparten o compiten por el acceso a recursos físicos o lógicos. Por ejemplo, dos procesos independientes compiten por el acceso a disco o para modificar una base de datos. • Interacción motivada porque los procesos se comunican y sincronizan entre sí para alcanzar un objetivo común, Por ejemplo, un compilador que tiene varios procesos que trabajan conjuntamente para obtener un solo archivo de salida.

Elementos a gestionar y diseñar a causa de la concurrencia.
Se pueden enumerar los siguientes:
1. El sistema operativo debe ser capaz de seguir la pista de los distintos procesos activos. Esto lo hace por medio de PBC’s (Bloque de Control de Procesos)2. El sistema operativo debe asignar y quitar los distintos recursos a cada proceso activo. Entre estos recursos se incluyen:

• Tiempo de procesador: Es función de la planificación.
• Memoria: La mayoría de los sistemas operativos emplean esquemas de memoria virtual.
• Archivos:
• Dispositivos de E/S:

3. El sistema operativo debe proteger los datos y los recursos físicos de cada proceso contra injerencias no intencionadas de otros procesos. 4. Los resultados de un proceso deben ser independientes de la velocidad relativa a la que se realiza la ejecución con respecto a otros procesos concurrentes.[1]
[1] Instituto tecnológico de Celaya, Sistemas operativos unidad III, (n.d.). Extraído el 24 de octubre de 2008 desde http://sisinfo.itc.mx/ITC-APIRGG/Materias/Mat1/SistOp-I_Unid3.php#

2.4.1 EXCLUSIÓN MUTUA DE SECCIONES CRÍTICAS.

El método más sencillo de comunicación entre los procesos de un programa concurrente es el uso común de unas variables de datos. El problema de este sistema es que la acción de un proceso interfiere en las acciones de otro de una forma no adecuada. Para evitar este tipo de errores se pueden identificar aquellas regiones de los procesos que acceden a variables compartidas y dotarlas de la posibilidad de ejecución como si fueran una única instrucción. Se denomina sección crítica a aquellas partes de los procesos concurrentes que no pueden ejecutarse de forma concurrente o, que desde otro proceso se ven como si fueran una única instrucción. Esto quiere decir que si un proceso entra a ejecutar una sección crítica en la que accede a unas variables compartidas, entonces otro proceso no puede entrar a ejecutar una región crítica en la que se modifique las variables compartidas con el anterior. Las secciones críticas se pueden agrupar en clases, siendo mutuamente exclusivas las secciones críticas de cada una. Para conseguir dicha exclusión se deben implementar protocolos software que impidan o bloqueen el acceso a una sección crítica mientras está siendo utilizada por un proceso.[1]
Los algoritmos de exclusión mutua (comúnmente abreviada como mutex por mutual exclusion) se usan en programación concurrente para evitar que fragmentos de código conocidos como secciones críticas accedan al mismo tiempo a recursos que no deben ser compartidos.
La mayor parte de estos recursos son las señales, contadores, colas y otros datos que se emplean en la comunicación entre el código que se ejecuta cuando se da servicio a una interrupción y el código que se ejecuta el resto del tiempo. Se trata de un problema de vital importancia porque, si no se toman las precauciones debidas, una interrupción puede ocurrir entre dos instrucciones cualesquiera del código normal y esto puede provocar graves fallos.
La técnica que se emplea por lo común para conseguir la exclusión mutua es inhabilitar las interrupciones durante el conjunto de instrucciones más pequeño que impedirá la corrupción de la estructura compartida (la sección crítica). Esto impide que el código de la interrupción se ejecute en mitad de la sección crítica.
En un sistema multiprocesador de memoria compartida, se usa la operación indivisible test-and-set sobre una bandera, para esperar hasta que el otro procesador la despeje. La operación test-and-set realiza ambas operaciones sin liberar el bus de memoria a otro procesador. Así, cuando el código deja la sección crítica, se despeja la bandera. Esto se conoce como espera activa.
Algunos sistemas tienen instrucciones multioperación indivisibles similares a las anteriormente descritas para manipular las listas enlazadas que se utilizan para las colas de eventos y otras estructuras de datos que los sistemas operativos usan comúnmente.
La mayoría de los métodos de exclusión mutua clásicos intentan reducir la latencia y espera activa mediante las colas y cambios de contexto. Algunos investigadores afirman que las pruebas indican que estos algoritmos especiales pierden más tiempo del que ahorran.
A pesar de todo lo dicho, muchas técnicas de exclusión mutua tienen efectos colaterales. Por ejemplo, los semáforos permiten interbloqueos (deadlocks) en los que un proceso obtiene un semáforo, otro proceso obtiene el semáforo y ambos se quedan a la espera de que el otro proceso libere el semáforo. Otros efectos comunes incluyen la inanición, en el cual un proceso esencial no se ejecuta durante el tiempo deseado, y la inversión de prioridades, en el que una tarea de prioridad elevada espera por otra tarea de menor prioridad, así como la latencia alta en la que la respuesta a las interrupciones no es inmediata.
La mayor parte de la investigación actual en este campo, pretende eliminar los efectos anteriormente descritos. Si bien no hay un esquema perfecto conocido, hay un interesante esquema no clásico de envío de mensajes entre fragmentos de código que, aunque permite inversiones de prioridad y produce una mayor latencia, impide los interbloqueos.
Algunos ejemplos de algoritmos clásicos de exclusión mutua son:
El algoritmo de Dekker.
El algoritmo de Peterson. [2]


Región Crítica. Protocolo de sincronización.

Los puntos de entrada de un recurso indican la cantidad de procesos que pueden utilizar simultáneamente al mismo. Si un recurso tiene sólo un punto de entrada, se lo denomina recurso crítico o recurso no compartible.

Región crítica de un proceso es la fase o etapa en la vida de ese proceso concurrente en la cual accede a un recurso crítico para modificarlo o alterarlo. El uso adecuado de la concurrencia entre procesos exige la capacidad de definir secciones críticas y hacer cumplir la exclusión mutua. Cualquier servicio o capacidad que dé soporte para la exclusión mutua debe cumplir con un protocolo de sincronización, que tiene los requisitos siguientes:

1. Debe cumplirse la exclusión mutua: sólo un proceso de entre todos los que poseen secciones críticas por el mismo recurso u objeto compartido, debe tener permiso para entrar en ella en un instante dado.

2. Un proceso que se interrumpe en una sección no crítica debe hacerlo sin estorbar a los otros. Es decir que si se cuelga un proceso que está usando un recurso, los demás procesos que esperan deben poder acceder al recurso de todas formas (el S.O. mata al proceso que se colgó y así libera al recurso).

3. No se puede demorar indefinidamente la entrada de un proceso a un cierto recurso; no debe permitirse el interbloqueo y la inanición. Todos los procesos deben poder acceder al recurso que solicitan, sino se van a morir sin usarlo y no es justo.

4. Cuando ningún proceso está en su sección crítica, cualquier proceso que solicite entrar en la suya debe poder hacerlo sin dilatación. Es decir, si nadie está usando un cierto recurso, entonces se le otorga al primer proceso que lo solicite.

5. No se pueden hacer suposiciones sobre la velocidad relativa de los procesos o su número (cantidad de procesadores). Nunca se puede saber a priori si a un proceso le falta mucho o poco para terminar.

6. Un proceso permanece en su sección crítica sólo por un tiempo finito. Esto sirve para evitar que un proceso se quede con un recurso por mucho tiempo y para que un recurso no se quede trabado sin sentido.[3]
[1] Universidad Nacional de Educación a Distancia (UNED)/Ingeniería Técnica en Informática (Gestión/Sistemas).Sistemas Operativos I Tema-III/I-Sincronización y comunicación de procesos/I (n.d). Extraído el 24 de octubre de 2008 desde http://www.erubio.es/files/SO1_Tema3_1.pdf

[2] Exclusión mutua (informática) (3 de mayo de 2008). Extraído el 24 de octubre de 2008 desde http://es.wikipedia.org/wiki/Exclusi%C3%B3n_mutua_%28inform%C3%A1tica%29

[3] Introducción a los sistemas operativos. Capitulo 4. Concurrencia: Exclusión mutua y sincronización (n.d). Extraído el 24 de octubre de 2008 desde http://www.hackinc2000.com/sistemasoperativos/Content/Cap04.html