Concepto de Proceso:
Estados y transiciones de los procesos:
Durante su vida, un proceso puede pasar por una serie de estados discretos, algunos de ellos son:
- En ejecución: El proceso ocupa la CPU actualmente, es decir, se está ejecutando.
- Listo o preparado: El proceso dispone de todos los recursos para su ejecución, sólo le falta la CPU.
- Bloqueado: Al proceso le falta algún recurso para poder seguir ejecutándose, además de la CPU. Por recurso se pueden entender un dispositivo, un dato, etc. El proceso necesita que ocurra algún evento que le permita poder proseguir su ejecución.
Hay otros estados de los procesos, pero en la presente exposición se
tratarán estos tres. Por sencillez, se considera un sistema con una sola
CPU, aunque no es difícil la extensión a múltiples procesadores.
Solamente puede haber un proceso en ejecución a la vez, pero pueden
existir varios listos y varios pueden estar bloqueados. Así pues, se
forman una lista de procesos listos y otra de procesos bloqueados. La
lista de procesos listos se ordena por prioridad,
de manera que el siguiente proceso que reciba la CPU será el primero de
la lista. La lista de procesos bloqueados normalmente no está ordenada;
los procesos no se desbloquean (es decir, no pasan a ser procesos
listos) en orden de prioridad, sino que lo hacen en el orden de
ocurrencia de los eventos que están esperando. Como se verá más
adelante, hay situaciones en las cuales varios procesos pueden
bloquearse esperando la ocurrencia del mismo evento; en tales casos es
común asignar prioridades a los procesos que esperan.
Transiciones de estado de los procesos
A continuación se dan ejemplos de eventos que
pueden provocar transiciones de estado en un proceso en este modelo de
tres estados. La mayoría de estos eventos se discutirán con profundidad a lo largo del curso:
- De ejecución á Bloqueado: al iniciar una operación de E/S, al realizar una operación WAIT sobre un semáforo a cero.
- De Listo á en ejecución: cuando lo requiere el planificador de la CPU (veremos el planificador de la CPU en el tema de planificación de procesos).
- De Bloqueado á Listo: se dispone del recurso por el que se había bloqueado el proceso. Por ejemplo, termina la operación de E/S, o se produce una operación SIGNAL sobre el semáforo en que se bloqueó el proceso, no habiendo otros procesos bloqueados en el semáforo.
La única iniciada por el proceso de usuario es el bloqueo, las
otras tres son iniciadas por entidades externas al proceso.
Como podemos observar en esta figura tenemos una serie de transiciones
posibles entre estados de proceso, representados a partir mediante una
gama de colores. Estos colores hay que interpretarlos de forma que, el
color del borde de los estados representa a dichos estados, los colores
dentro de los circulos nos dicen las posibles alternativas de acceso
hacia otro estado, y los colores de las flechas nos representan hacia
que estado nos dirigimos si seguimos la misma.
Procesos ligeros: Hilos ó Hebras:
El concepto de proceso es más complejo y sutil que el
presentado hasta ahora. 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.
Concurrencia y secuenciabilidad
Puede verse la concurrencia de procesos como la ejecución simultánea de varios procesos. Si tenemos un multiprocesador o un sistema distribuido(tema
1) la concurrencia parece clara, en un momento dado cada procesador
ejecuta un proceso. Se puede ampliar el concepto de concurrencia si
entendemos por procesado concurrente (o procesado paralelo) la circunstancia en la que de tomar una instantánea del sistema en conjunto, varios procesos se vean en un estado intermedio entre su estado inicial y final.
Los distintos procesos dentro de un ordenador no
actúan de forma aislada. Por un lado, algunos procesos cooperan para
lograr un objetivo común. Por otro lado, los procesos compiten por el
uso de unos recursos limitados, como el procesador, la memoria o los
ficheros. Estas dos actividades de cooperación y competición llevan
asociada la necesidad de algún tipo de comunicación entre los procesos.
Para aclarar un poco todo esto, supongamos que en un entorno UNIX se ejecuta la orden
- cat tema1 tema2 tema3 | wc -l
Esta orden va a provocar que el intérprete de órdenes cree dos procesos concurrentes, el primero ejecutará el programa cat, que concatenará el contenido de los ficheros de texto tema1, tema2 y tema3. El segundo ejecutará el programa wc, que contará el número de líneas de la salida producida por cat. Estos dos procesos cooperan, y será preciso algún tipo de sincronización entre ellos, concretamente hasta que cat no produzca alguna salida wc debería bloquearse.
Competencia entre los procesos
- La naturaleza física del recurso hace que sea imposible compartirlo. Un ejemplo lo constituye una impresora, si una impresora fuera utilizada por varios procesos simultáneamente sus salidas se entremezclarían en el papel.
- El recurso es tal que si es usado por varios procesos de forma concurrente la acción de uno de ellos puede interferir con la de otro. Un ejemplo común lo constituye un fichero que contiene unos datos accesibles desde más de un proceso, y modificables al menos por uno de ellos.
Dentro de la categoría de recursos no compartibles se incluirán la mayoría de los periféricos
(los discos no), los ficheros de escritura y las zonas de memoria
sujetas a modificación. Los recursos compartibles incluirán la CPU (en
los temas previos vimos cómo compartir la CPU entre los procesos
introduciendo el concepto de PCB), los ficheros de lectura, y las zonas de memoria que contengan rutinas puras o bien datos que no están sujetos a modificación.
Ejemplos
El hecho
de reservar un asiento en una avión mediante un sistema basado en aplicaciones web, cuando decenas de personas en
el mundo pueden reservarlo también, nos da una idea de lo importante y crucial
que es el control de concurrencia en un sistema de base de datos a mediana o
gran escala.
Otro
ejemplo en el que podemos observar la incidencia del control de concurrencia en
el siguiente: en una Base de Datos bancaria podría ocurrir que se paguen dos cheques en forma simultánea sobre una
cuenta que no tiene saldo suficiente para cubrirlos en su totalidad, esto es
posible evitarlo si se tiene un control de concurrencia.
Sincronizacion
Cinco filósofos
se sientan alrededor de una mesa y pasan su vida cenando y pensando. Cada
filósofo tiene un plato de fideos y un tenedor a la izquierda de su plato. Para
comer los fideos son necesarios dos tenedores y cada filósofo sólo puede tomar
los que están a su izquierda y derecha. Si cualquier filósofo coge un tenedor y
el otro está ocupado, se quedará esperando, con el tenedor en la mano, hasta
que pueda coger el otro tenedor, para luego empezar a comer.
Si dos filósofos adyacentes intentan tomar el mismo tenedor a una vez, se
produce una condición de carrera: ambos compiten por tomar
el mismo tenedor, y uno de ellos se queda sin comer.
Si todos los filósofos cogen el tenedor que está a su derecha al mismo
tiempo, entonces todos se quedarán esperando eternamente, porque alguien debe
liberar el tenedor que les falta. Nadie lo hará porque todos se encuentran en
la misma situación (esperando que alguno deje sus tenedores). Entonces los
filósofos se morirán de hambre. Este bloqueo mutuo se denomina interbloqueo o deadlock.
El problema consiste en encontrar un algoritmo que
permita que los filósofos nunca se mueran de hambre.
Requisitos para la Exclusión Mutua
Los recursos no compartibles, ya sean
periféricos, ficheros, o datos en memoria, pueden protegerse del acceso
simultáneo por parte de varios procesos evitando que éstos ejecuten de
forma concurrente sus fragmentos de código a través de los cuales llevan
a cabo este acceso. Estos trozos de código reciben el nombre de secciones o regiones críticas,
pudiéndose asimilar el concepto de exclusión mutua en el uso de estos
recursos a la idea de exclusión mutua en la ejecución de las secciones
críticas. Así, por ejemplo, puede implementarse la exclusión mutua de
varios procesos en el acceso a una tabla de datos mediante el recurso de
que todas las rutinas que lean o actualicen la tabla se escriban como
secciones críticas, de forma que sólo pueda ejecutarse una de ellas a la
vez.
Idear soluciones que garanticen la exclusión mutua es uno de los problemas fundamentales de la programación concurrente. Muchas son las alternativas y tipos de mecanismos que se pueden adoptar. A lo largo de este tema veremos diferentes soluciones software y alguna hardware ; unas serán sencillas y otras complejas, algunas requieren la cooperación voluntaria de los procesos y otras que exigen un estricto ajuste a rígidos protocolos. La selección de las operaciones primitivas adecuadas para garantizar la exclusión mutua de las secciones críticas es una decisión primordial en el diseño de un sistema operativo. Al menos, una solución apropiada debería cumplir las cuatro condiciones siguientes:
- Sólo un proceso, de todos los que poseen secciones críticas por el mismo recurso compartido, debe tener permiso para entrar en ella en un momento dado.
- Un proceso que se interrumpe en una sección no crítica debe hacerlo sin interferir con los otros procesos.
- Un proceso no debe poder solicitar acceso a una sección crítica para después ser demorado indefinidamente, no puede permitirse el interbloqueo o la inanición.
- Si ningún proceso está en su sección crítica, cualquier proceso que solicite entrar en la suya debe poder hacerlo sin demora.
- No se debe suponer sobre la velocidad relativa de los procesos o el número de procesadores.
- Un proceso permanece en su sección crítica por un tiempo finito.
BENEFICIOS DE LA CONCURRENCIA
- Trata de evitar los tiempos muertos de la UCP
- Comparte y optimiza el uso de recursos
- Permite la modularidad en las diferentes etapas del proceso
- Acelera los cálculos
- Da mayor comodidad
DESVENTAJAS DE LA CONCURRENCIA
- Inanición e interrupción de procesos
- Ocurrencia de bloqueos
- Que dos o más procesos requieran el mismo recurso (no apropiativo).
NIVELES, OBJETIVOS Y CRITERIOS DE
PLANIFICACIÓN
- El Planificador es la porción del Sistema Operativo que decide y el Algoritmo de Planificación es el utilizado. Los principales “criterios” respecto de un buen algoritmo de planificación son la equidad, la eficacia, el tiempo de respuesta, el tiempo de regreso y el rendimiento.
- Cada proceso es único e impredecible, es decir que pueden requerir intensivamente operaciones de Entrada / Salida o intensivamente CPU; el planificador del Sistema Operativo no tiene la certeza de cuánto tiempo transcurrirá hasta que un proceso se bloquee, ya sea por una operación de Entrada / Salida o por otra razón .
- Para evitar que un proceso se apropie de la cpu un tiempo excesivo, los equipos poseen un dispositivo que provoca una interrupción en forma periódica, por ejemplo 60 hz, o sea sesenta veces por segundo.
Planificación de Procesador:
- Planificación apropiativa: es la estrategia de permitir que procesos ejecutables (desde el punto de vista lógico) sean suspendidos temporalmente.
- Planificación no apropiativa: es la estrategia de permitir la ejecución de un proceso hasta terminar.
- Planificación del procesador: determinar cuándo deben asignarse los procesadores y a qué procesos, lo cual es responsabilidad del Sistema Operativo.
Niveles de planificación del procesador:
- Planificación de alto nivel: También se denomina Planificación de trabajos.
Determina a qué trabajos se les va a permitir competir activamente por los
recursos del sistema, lo cual se denomina Planificación de admisión.
- Planificación de nivel intermedio: Determina a qué procesos se les puede permitir competir por la CPU.
- Planificación de bajo nivel: Determina a qué proceso listo se le asigna la cpu cuando esta queda disponible y asigna la cpu al mismo, es decir que “despacha” la cpu al proceso.
Técnicas de administración del planificador
- FIFO : "Es muy simple, los procesos se despachan de acuerdo con su tiempo de llegada a la cola de listos. Una vez que el proceso obtiene la cpu, se ejecuta hasta terminar, ya que es una disciplina “no apropiativa”. Puede ocasionar que procesos largos hagan esperar a procesos cortos y que procesos no importantes hagan esperar a procesos importantes. Es más predecible que otros esquemas. No puede garantizar buenos tiempos de respuesta interactivos. Suele utilizarse integrado a otros esquemas, por ejemplo, de la siguiente manera: Los procesos se despachan con algún esquema de prioridad. Los procesos con igual prioridad se despachan “FIFO”.
- RR : Los procesos se despachan en “FIFO” y disponen de una cantidad limitada de tiempo de cpu, llamada “división de tiempo” o “cuanto”. Si un proceso no termina antes de expirar su tiempo de cpu ocurren las siguientes acciones: La cpu es apropiada. La cpu es otorgada al siguiente proceso en espera. El proceso apropiado es situado al final de la lista de listos. Es efectiva en ambientes de tiempo compartido. La sobrecarga de la apropiación se mantiene baja mediante mecanismos eficientes de intercambio de contexto y con suficiente memoria principal para los procesos. "
- SJF : "Es una disciplina no apropiativa y por lo tanto no recomendable en ambientes de tiempo compartido. El proceso en espera con el menor tiempo estimado de ejecución hasta su terminación es el siguiente en ejecutarse. Los tiempos promedio de espera son menores que con “FIFO”. Los tiempos de espera son menos predecibles que en “FIFO”. Favorece a los procesos cortos en detrimento de los largos. Tiende a reducir el número de procesos en espera y el número de procesos que esperan detrás de procesos largos. Requiere un conocimiento preciso del tiempo de ejecución de un proceso, lo que generalmente se desconoce. Se pueden estimar los tiempos en base a series de valores anteriores. "
- Queves multi-level : "Los esquemas analizados hasta ahora suponen que todos los procesos ejecutables están en la memoria principal. Si la memoria principal es insuficiente, ocurrirá lo siguiente.Habrá procesos ejecutables que se mantengan en disco. Habrá importantes implicaciones para la planificación, tales como las siguientes: El tiempo de alternancia entre procesos para traer y procesar un proceso del disco es considerablemente mayor que el tiempo para un proceso que ya está en la memoria principal. Es más eficiente el intercambio de los procesos con un planificador de dos niveles. El esquema operativo de un planificador de dos niveles es como sigue: Se carga en la memoria principal cierto subconjunto de los procesos ejecutables. El planificador se restringe a ellos durante cierto tiempo. Periódicamente se llama a un planificador de nivel superior. El planificador de nivel superior se encarga de desplazar los procesos de memoria a disco y viceversa.
- Multi-level feedback queves : Proporcionan una estructura para lograr los siguientes objetivos: Favorecer trabajos cortos. Favorecer trabajos limitados por la Entrada / Salida para optimizar el uso de los dispositivos de Entrada / Salida. Determinar la naturaleza de un trabajo lo más rápido posible y planificar el trabajo (proceso) en consecuencia. Un nuevo proceso entra en la red de línea de espera al final de la cola superior. Se mueve por esta cola “FIFO” hasta obtener la cpu. Si el trabajo termina o abandona la cpu para esperar por la terminación de una operación de Entrada / Salida o la terminación de algún otro suceso, el trabajo abandona la red de línea de espera.
Gracias por los datos....
ResponderBorrar