2.2 Estados y transiciones de los procesos

Un proceso puede estar en cualquiera de los siguientes tres estados: Listo, En ejecución y

Bloqueado.

Los procesos en el estado listo son los que pueden pasar a estado de ejecución si el

planificador los selecciona. Los procesos en el estado ejecución son los que se están

ejecutando en el procesador en ese momento dado. Los procesos que se encuentran en

estado bloqueado están esperando la respuesta de algún otro proceso para poder continuar

con su ejecución. Por ejemplo operación de E/S.

Un proceso puede variar entre 5 distintos estado

 New: cuando el proceso esta siendo creado.

 Running: cuando el proceso se esta ejecutando.

 Waiting: cuando el proceso esta esperando que se cumpla algún otro evento.

 Ready: cuando el proceso esta pronto para ejecutar, esperando por la CPU.

 Terminated: cuando el proceso esta terminado.

Estado de los Procesos

Los bloques de control de los procesos se almacenan en colas, cada una de las cuales

representa un estado particular de los

procesos, existiendo en cada bloque, entre otras informaciones. Los estados de los

procesos son internos del sistema operativo y transparentes al usuario.

Los estados de los procesos se pueden dividir en dos tipos: activos e inactivos.

1.- Estados activos

Son aquellos que compiten con el procesador o están en condiciones de hacerlo. Se dividen

en:

 Ejecución: Estado en el que se encuentra un proceso cuando tiene el control del

procesador. En un sistema monoprocesador este estado sólo lo puede tener un

proceso.

Preparado: Aquellos procesos que están dispuestos para ser ejecutados, pero no

están en ejecución por alguna causa (Interrupción, haber entrado en cola estando

otro proceso en ejecución, etc.).

 Bloqueado: Son los procesos que no pueden ejecutarse de momento por necesitar

algún recurso no disponible (generalmente recursos de entrada/salida).

2.- Estados inactivos

Son aquellos que no pueden competir por el procesador, pero que pueden volver a hacerlo

por medio de ciertas operaciones. En estos estados se mantiene el bloque de control de

proceso aparcado hasta que vuelva a ser activado. Se trata de procesos que no han

terminado su trabajo que lo han impedido y que pueden volver a activarse desde el punto

en que se quedaron sin que tengan que volver a ejecutarse desde el principio.

Son de dos tipos:

 Suspendido bloqueado: Es el proceso que fue suspendido en espera de un evento,

sin que hayan desaparecido las causas de su bloqueo.

 Suspendido programado: Es el proceso que han sido suspendido, pero no tiene

causa parta estar bloqueado.

Información asociada con cada proceso:

 Estado del proceso.

 Program counter.

 Registros del CPU.

 Información de planificación del CPU.

 Memoria.

Información para administración.

 Información de estatus de E/S.

Creación de Procesos

Crear un proceso implica operaciones como:

 Dar un nombre a un proceso.

 Insertarlo en la lista de procesos conocidos del sistema ( o tabla de procesos)

 Determinar la prioridad inicial de proceso.

 Crear el bloque de control de proceso.

 Asignar los recursos iniciales al proceso.

Un proceso puede crear un nuevo proceso. Si lo hace el proceso creador se denomina

proceso padre, y el proceso creado, proceso hijo. Sólo se necesita un padre para crear

un hijo. Tal creación origina una estructura jerárquica de procesos. No se puede

destruir un proceso cuando este ha creado otros procesos.

Destruir un proceso implica eliminarlo del sistema. Se le remueve de la tabla o listas del

sistema, sus recursos se devuelven al sistema y su bloque de control de proceso se

borra (es decir, el espacio de memoria ocupado por su PCB se devuelve al espacio

de memoria disponible.

Operaciones de procesos y recursos.

Los sistemas operativos poseen una serie de funciones cuyo objetivo es el de la

manipulación de los procesos. En general las operaciones que se pueden hacer sobre

un proceso son las siguientes:

Crear el proceso. Se produce con la orden de ejecución del programa y

suele necesitar varios argumentos, como el nombre y la prioridad del proceso.

La creación de un proceso puede ser de dos tipos:

Jerárquica. En ella cada proceso que se crea es hijo del proceso creador y hereda el

entorno de ejecución de su padre. El primer proceso que ejecuta un usuario será hijo

del intérprete de comandos con el que interactúa.

No jerárquico. Cada proceso creado por otro proceso se ejecuta independientemente de

su creador con un entorno diferente. Es un tipo de creación que no suele darse en los

sistemas operativos actuales.

Además de los dos tipos anteriores se pueden realizar las operaciones siguientes:

 Destruir un proceso. Se trata de la orden de eliminación del proceso con la cual el

sistema operativo destruye su PCB ( Proces control Block).

 Suspender un proceso. Es una operación de alta prioridad que paraliza un proceso

que puede ser reanudado posteriormente. Suele utilizarse en ocasiones de mal

funcionamiento o sobrecarga del sistema.

1. Reanudar un proceso. Trata de activar un proceso que ha sido

previamente suspendido.

2. Cambiar la prioridad de un proceso.

 Temporizar la ejecución de un proceso. Hace que un determinado proceso se

ejecute cada cierto tiempo (segundos, minutos, horas,...) por etapas o de una sola

vez, pero transcurrido un periodo de tiempo fijo.

 Despertar un proceso. Es una forma de desbloquear un proceso que habrá sido

bloqueado previamente por temporización o cualquier otra causa.

DESCRIPTOR DE PROCESOS Y RECURSOS

Es una estructura de datos asociada a una entidad informática ya sea un (Recurso o

Proceso), en la cual se indica y actualiza todas las informaciones relativas a dicha

entidad.

En el caso de un proceso la información general que contiene es:

1) Identificador: Que puede ser interno y externo.

 Interno: Sistemas.

 Externo: Usuario.

2) Descripción de la máquina virtual asociada: como espacio virtual asignado, tipo de

mapeo, tipo de acceso.

3) Descripción de los recursos de la máquina que usa como: Lista de recursos que el

proceso tiene derecho a solicitar, dirección real en la memoria principal, estado de

las variables internas del CPU, prioridad, etc.

4) Estados funcionales del proceso: Los estados de los procesos son internos del

sistema operativo y transparente al usuario. Para éste, su

proceso estará siempre en ejecución independientemente del estado en que se

encuentre internamente el sistema.

TRANSICIONES

Un proceso puede encontrarse en estado de ejecución, bloqueado o listo (que también se

llama ejecutable). De estos estados de los procesos se derivan las siguientes

transiciones y estados:

Transición: El paso de un estado a otro.

1. El proceso se bloquea en la entrada.

2. El planificador elige otro proceso.

3. El planificador elige este proceso.

4. La entrada se vuelve disponible.

Estados:

1. Ejecución (que en realidad hace uso del CPU en ese instante).

2. Bloqueado (incapaz de correr hasta que suceda algún evento externo.

3. Listo (ejecutable; se detiene temporalmente para permitir que se ejecute otro proceso).

En estos tres estados son posibles cuatro transiciones:

1. Ocurre cuando un proceso descubre que no puede continuar. En algún sistema el proceso

debe ejecutar una llamada al sistema, BLOCK, para entrar en estado bloqueado.

2 y 3. Son ocasionadas por el planificador del proceso, que es parte del sistema operativo

sin que el proceso llegue a saber de ella.

2. Ocurre cuando el planificador decide que el proceso en ejecución ya ha corrido el tiempo

suficiente y es tiempo de permitir que otro proceso tome tiempo de CPU.

3. Ocurre cuando todos los procesos han utilizado su parte del tiempo y es hora de que el

primer proceso vuelva a correr.

4. Ocurre cuando aparece el evento externo que estaba esperando un proceso (como el

arribo de alguna entrada). Si ningún otro proceso corre en ese instante, la transición 3

se activará de inmediato y el proceso iniciara su ejecución, de lo contrario tendrá que

esperar, en estado listo.

Transiciones de estado.

La asignación del CPU al primer proceso de la lista de listos es llamada despacho, y es

ejecutado por la entidad del sistema llamada despachador. Indicamos esta transición

de la manera siguiente:

Despacho (nombre del proceso): Listo en ejecución.

Mientras el proceso tenga CPU, se dice que esta en ejecución. Para prevenir que

cualquier proceso monopolice el sistema, ya sea de manera accidental o

maliciosamente el sistema operativo ajusta un reloj de interrupción del hardware para

permitir al usuario ejecutar su proceso durante un intervalo de tiempo especifico o

cuanto. Si el proceso no abandona voluntariamente el CPU, antes de que expire el

intervalo, el reloj genera una interrupción, haciendo que el sistema operativo recupere

el control. El sistema operativo hace que el proceso que anteriormente se hallaba en

estado de ejecución pase al de listo, y hace que el primer proceso de la lista de listos

pase al estado de ejecución.

Estas transiciones de estado se indican como:

- tiempo excedido (nombre del proceso): en ejecución Listo

- bloqueado (nombre del proceso): en ejecución bloqueado

El proceso cambia del estado bloqueado al estado listo:

- despertar ( nombre del proceso): bloqueado Listo.

Con esto tenemos definidas 4 transacciones de estado.

- despacho ( nombre del proceso): Listo en ejecución

- tiempo excedido ( nombre del proceso): en ejecución Listo

- bloqueado ( nombre del proceso): en ejecución bloqueado

- despertar ( nombre del proceso ): bloqueado Listo.

Suspensión y Reanudación.

Un proceso suspendido no puede proseguir sino hasta que lo reanuda otro proceso.

Reanudar (o activar) un proceso implica reiniciarlo a partir del punto en el que se

suspendió.

Las operaciones de suspensión y reanudación son importantes por diversa razones:

 Si un sistema está funcionando mal y es probable que falle, se puede suspender

los procesos activos para reanudarlos cuando se haya corregido el problema.

 Un usuario que desconfíe de los resultados parciales de un proceso puede

suspenderlo (en vez de abortarlo) hasta que verifique si el proceso funciona

correctamente o no.

 Algunos procesos se puede suspender como respuesta a las fluctuaciones a corto

plazo de la carga del sistema y reanudarse cuando las cargas regresen a niveles

normales.

Transiciones de estados de los procesos con suspensión y reanudación.

Muestra el diagrama de transiciones de estado de los procesos, modificado para incluir las

operaciones de suspensión y reanudación. Se han añadido dos nuevos estados,

denominados suspendido-listo y suspendido bloqueado; no hay necesidad de un

estado suspendido-ejecutado. Sobre la línea discontinua se encuentran los estados

activos, y debajo de ella los estados suspendidos.

Una suspensión puede ser iniciada por el propio proceso o por otro. En un sistema con un

solo procesador el proceso en ejecución puede suspenderse a si mismo; ningún otro

proceso podría estar en ejecución al mismo tiempo para realizar la suspensión

(aunque otro proceso sí podría solicitar la suspensión cuando se ejecute). En un

sistema de múltiples procesadores, un proceso en ejecución puede suspender a otro

que se esté ejecutando en ese mismo momento en un procesador diferente.

Solamente otro proceso puede suspender un proceso listo. La transición correspondiente

es:

1) Suspender (nombre_del_proceso): Listo Suspendido-Listo.

Un proceso puede hacer que otro proceso que se encuentre en el estado suspendido-listo

pase al estado listo. La transición correspondiente es:

2) reanudar ( nombre_del_proceso): Suspendido-Listo Listo. 

Un proceso puede suspender a otro proceso que esté bloqueado. La transición

correspondiente es:

3) suspender ( nombre_del_proceso): Bloqueado Suspendido-Bloqueado.

Un proceso puede reanudar otro proceso que esté suspendido-bloqueado. La transición

correspondiente es:

4) reanudar ( nombre_del_proceso): Suspendido-Bloqueado Bloqueado.

Como la suspensión es por lo general una actividad de alta prioridad, se debe realizar de

inmediato. Cuando se presenta finalmente el término de la operación ( si es que

termina), el proceso suspendido-bloqueado realiza la siguiente transición.

5)completar(nombre_del _proceso): suspendido-bloqueado suspendido-listo.

6) suspender (nombre_del_proceso): Ejecución Suspendido-Listo.

En conclusión los sistemas que administran procesos deben ser capaces de realizar ciertas

operaciones sobre procesos y con ellos. Tales operaciones incluyen:

 Crear un proceso.

 Destruir un proceso.

 Suspender un proceso.

 Reanudar un proceso.

 Cambiar la prioridad de un proceso.

 Bloquear un proceso.

 Despertar un proceso.

 Despachar un proceso.

 Permitir que un proceso se comunique con otro (esto se denomina comunicación

entre procesos). 

 

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.

Diferencia entre Proceso e Hilo

Un proceso es una entidad relativamente independiente que dispone de su propio

espacio de direcciones, su propia información de estado y que utiliza los mecanismos de

comunicación entre procesos que le proporciona el sistema operativo para comunicarse con

otros procesos.

Por otro lado, un hilo es una entidad más reducida capaz de convivir junto a otros

hilos bajo el contexto de un único proceso, permitiendo compartir la información de estado,

el área de memoria y/o los recursos asociados a ese 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.

Procesos ligeros

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

Los procesos ligeros son 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.

Figura 4 Paralelismo

Otro ejemplo de caso en el que son útiles los hilos es el de los navegadores de la

World Wide Web, como Netscape y Mosaic. Muchas páginas Web contienen múltiples

imágenes pequeñas. Para cada imagen de una página Web, el navegador debe establecer

una conexión individual con el sitio de la página de casa y solicitar la imagen. Se desperdicia

una gran cantidad de tiempo estableciendo y liberando todas estas conexiones. Si tenemos

múltiples hilos dentro del navegador, podemos solicitar muchas imágenes al mismo tiempo,

acelerando considerablemente el rendimiento en la mayor parte de los casos, ya que en el

caso de imágenes pequeñas el tiempo de preparación es el factor limitante, no la rapidez

de la línea de transmisión.

Entre los elementos que son distintos para cada hilo están el contador de programa, los

registros y el estado. El contador de programa se necesita porque los hilos, al igual

que los procesos, pueden suspenderse y reanudarse. Los registros se necesitan

porque cuando los hilos se suspenden sus registros deben guardarse. Por último, los

hilos, al igual que los procesos, pueden estar en los estados de ejecutándose, listo o

bloqueado.

2.4 Concurrencia y secuencialidad

Concurrencia

Es la existencia de varias actividades ejecutándose simultáneamente, y necesitan

sincronizarse para actuar conjuntamente. Se trata, en este caso, de un concepto lógico, ya

que sólo hace referencia a las actividades, sin importar el número de procesadores

presentes.

Para que dos actividades, sean concurrentes, es necesario que tengan relación

entre sí, como puede ser la cooperación en un trabajo determinado o el uso de información

compartida.

Los procesos son concurrentes si existen simultáneamente. Los procesos

concurrentes pueden funcionar en forma totalmente independiente unos de otros, o pueden

ser asíncronos, lo cual significa que en ocasiones requiere cierta sincronización y

cooperación.

En un sistema monoprocesador, la existencia de multiprogramación es condición

necesaria, pero no suficiente para que exista concurrencia, ya que los procesos pueden

ejecutarse independientemente. Por ejemplo, un editor y un compilador pueden estar

ejecutándose simultáneamente en una computadora sin que exista concurrencia entre ellos.

Por otro lado si un programa se está ejecutando y se encuentra grabando datos en un

archivo, y otro programa también en ejecución está leyendo datos de ese mismo archivo, sí

existe concurrencia entre ellos, pues el funcionamiento de uno interfiere en el

funcionamiento de otro.

Si un sistema es multiprocesador, también pueden presentarse situaciones de

concurrencia siempre y cuando las actividades necesiten actuar entre sí, bien por utilizar

información común, o por cualquier otra causa.

Los procesos del sistema pueden ejecutarse concurrentemente, puede haber

múltiples tareas en el CPU con varios procesos. Existen varias razones para permitir la

ejecución concurrente:

 Compartir recursos físicos: Ya que los recursos del hardware de la computadora

son limitados, nos podemos ver obligados a compartirlos en un entorno multiusuario.

 Compartir recursos lógicos: Puesto que varios usuarios pueden interesarse en el

mismo elemento de información (por ejemplo un archivo compartido), debemos

proporcionar un entorno que permita el acceso concurrente a estos tipos de recursos.

 Acelerar los cálculos: Si queremos que una tarea se ejecute con mayor rapidez,

debemos dividirla en subtareas, cada una de las cuales se ejecutara, en paralelo con

las demás.

 Modularidad: Podremos construir el sistema en forma modular, dividiendo las

funciones del sistema en procesos separados.

 Comodidad: Un usuario puede tener que ejecutar varias tareas a la vez, por ejemplo

puede editar, imprimir y compilar en paralelo.

La ejecución concurrente que requiere la cooperación entre procesos necesita un

mecanismo para la sincronización y comunicación de procesos, exclusión mutua y

sincronización.

PROBLEMAS DE CONCURRENCIA

En los sistemas de tiempo compartido (aquellos con varios usuarios, procesos, tareas,

trabajos que reparten el uso de CPU entre estos) se presentan muchos problemas debido

a que los procesos compiten por los recursos del sistema. Imagine que un proceso está

escribiendo en la unidad de cinta y se le termina su turno de ejecución e inmediatamente

después el proceso elegido para ejecutarse comienza a escribir sobre la misma cinta. El

resultado es una cinta cuyo contenido es un desastre de datos mezclados. Así como la cinta,

existen una multitud de recursos cuyo acceso debe der controlado para evitar los problemas

de la concurrencia.

El sistema operativo debe ofrecer mecanismos para sincronizar la ejecución de procesos:

semáforos, envío de mensajes, 'pipes', etc. Los semáforos son rutinas de software (que en

su nivel más interno se auxilian del hardware) para lograr exclusión mutua en el uso de

recursos. Para entender este y otros mecanismos es importante entender los problemas

generales de concurrencia, los cuales se describen enseguida.

 Condiciones de Carrera o Competencia: La condición de carrera (race condition)

ocurre cuando dos o más procesos accesan un recurso compartido sin control, de

manera que el resultado combinado de este acceso depende del orden de llegada.

Suponga, por ejemplo, que dos clientes de un banco realizan cada uno una operación

en cajeros diferentes al mismo tiempo.

El usuario A quiere hacer un depósito. El B un retiro. El usuario A comienza la transacción

y lee su saldo que es 1000. En ese momento pierde su turno de ejecución (y su saldo queda

como 1000) y el usuario B inicia el retiro: lee el saldo que es 1000, retira 200 y almacena el

nuevo saldo que es 800 y termina. El turno de ejecución regresa al usuario A el cual hace

su depósito de 100, quedando saldo = saldo + 100 = 1000 + 100 = 1100. Como se ve, el

retiro se perdió y eso le encanta al usuario A y B, pero al banquero no le convino esta

transacción. El error pudo ser al revés, quedando el saldo final en 800.

 Postergación o Aplazamiento Indefinido(a): Esto se mencionó en el apartado

anterior y consiste en el hecho de que uno o varios procesos nunca reciban el

suficiente tiempo de ejecución para terminar su tarea. Por ejemplo, que un proceso

ocupe un recurso y lo marque como 'ocupado' y que termine sin marcarlo como

'desocupado'. Si algún otro proceso pide ese recurso, lo verá 'ocupado' y esperará

indefinidamente a que se 'desocupe'.

  Condición de Espera Circular: Esto ocurre cuando dos o más procesos forman una

cadena de espera que los involucra a todos. Por ejemplo, suponga que el proceso A

tiene asignado el recurso 'cinta' y el proceso B tiene asignado el recurso 'disco'. En

ese momento al proceso A se le ocurre pedir el recurso 'disco' y al proceso B el

recurso 'cinta'. Ahi se forma una espera circular entre esos dos procesos que se

puede evitar quitándole a la fuerza un recurso a cualquiera de los dos procesos.

 Condición de No Apropiación: Esta condición no resulta precisamente de la

concurrencia, pero juega un papel importante en este ambiente. Esta condición

especifica que si un proceso tiene asignado un recurso, dicho recurso no puede

arrebatársele por ningún motivo, y estará disponible hasta que el proceso lo 'suelte'

por su voluntad.

 Condición de Espera Ocupada: Esta condición consiste en que un proceso pide un

recurso que ya está asignado a otro proceso y la condición de no apropiación se debe

cumplir. Entonces el proceso estará gastando el resto de su time slice checando si el

recurso fue liberado. Es decir, desperdicia su tiempo de ejecución en esperar. La

solución más común a este problema consiste en que el sistema operativo se dé

cuenta de esta situación y mande a una cola de espera al proceso, otorgándole

inmediatamente el turno de ejecución a otro proceso.

 Condición de Exclusión Mutua: Cuando un proceso usa un recurso del sistema

realiza una serie de operaciones sobre el recurso y después lo deja de usar. A la

sección de código que usa ese recurso se le llama 'región crítica'. La condición de

exclusión mutua establece que solamente se permite a un proceso estar dentro de la

misma región crítica. Esto es, que en cualquier momento solamente un proceso

puede usar un recurso a la vez. Para lograr la exclusión mutua se ideo también el

concepto de 'región crítica'. Para logar la exclusión mutua generalmente se usan

algunas técnicas para lograr entrar a la región crítica: semáforos, monitores, el

algoritmo de Dekker y Peterson, los 'candados'. Para ver una descripción de estos

algoritmos consulte

 Condición de Ocupar y Esperar un Recurso: Consiste en que un proceso pide un

recurso y se le asigna. Antes de soltarlo, pide otro recurso que otro proceso ya tiene

asignado. 

 

Los problemas descritos son todos importantes para el sistema operativo, ya que debe ser

capaz de prevenir o corregirlos. Tal vez el problema más serio que se puede presentar en

un ambiente de concurrencia es el 'abrazo mortal', también llamado 'trabazón' y en inglés

deadlock. El deadlock es una condición que ningún sistema o conjunto de procesos quisiera

exhibir, ya que consiste en que se presentan al mismo tiempo cuatro condiciones

necesarias: La condición de no apropiación, la condición de espera circular, la condición de

exclusión mutua y la condición de ocupar y esperar un recurso. Ante esto, si el deadlock

involucra a todos los procesos del sistema, el sistema ya no podrá hacer algo productivo. Si

el deadlock involucra algunos procesos, éstos quedarán congelados para siempre.

Exclusión mutua de secciones criticas

Forma de asegurar que si un proceso está usando una variable o archivo compartido, los

otros procesos quedarán excluidos de hacer lo mismo.

Los procesos pueden tener en su código secciones en que realizan cálculos internos y

operaciones que no dan lugar a condiciones de competencia. Sin embargo existen

secciones de programa en que el proceso está accediendo a recursos compartidos que

pueden dar pié a condiciones de competencia.

La parte del programa en que se accede a un recurso compartido se denomina sección o

región crítica (requisito necesario, pero no suficiente). Los requisitos para que procesos

paralelos cooperen de manera correcta usando datos compartidos son los siguientes:

 Dos procesos nunca pueden estar simultáneamente dentro de sus regiones críticas.

 No se puede suponer nada acerca de las velocidades de ejecución de los procesos

o el número de las CPU.

 Ningún proceso que se ejecute fuera de su región crítica puede bloquear a otros

procesos.

 Ningún proceso deberá tener una espera indefinida para entrar en su región crítica.

La exclusión mutua debe ponerse en práctica sólo cuando los procesos obtienen acceso a

datos compartidos modificables; cuando los procesos realizan operaciones que no entran

en conflicto con otras, deben permitirse que procedan concurrentemente. Cuando un

proceso obtiene acceso a datos compartidos modificables, se dice que se encuentra en

una sección crítica. Es evidente que, para evitar la clase de problemas observados en la

sección anterior, debe asegurarse que cuando un proceso se encuentre en una sección

crítica, los demás procesos (o al menos los que tengan acceso a los datos compartidos) no

pueden entrar a sus propias secciones críticas.

Mientras un proceso se encuentra en su sección crítica, otros procesos pueden, claro está,

seguir ejecutándose fuera de sus secciones críticas. Cuando un proceso abandona su

región crítica, otro proceso que espera entrar en su propia sección crítica (si existe algún

proceso en espera). Lograr que se cumpla la exclusión mutua es uno de los problemas

fundamentales de la programación concurrente. Se han propuesto muchas soluciones,

algunas de software y otras de hardware, algunas sencillas y otras complejas, y algunas

que requieren la cooperación voluntaria de los procesos y otras que exigen un escrito ajuste

a rígidos protocolos.

Encontrarse dentro de una región crítica es un estado especial concedido a un proceso. El

proceso tiene acceso exclusivo a los datos compartidos y los demás procesos que requieran

acceso a los datos en ese momento deben esperar. Así pues, las secciones críticas deben

ejecutarse tan rápido como sea posible; un proceso no se debe bloquear dentro de su propia

sección crítica y las secciones críticas deben codificarse con mucho cuidado (para evitar,

por ejemplo, la posibilidad de ciclos infinitos).

Si un proceso de una sección crítica termina, ya sea voluntaria o involuntariamente, el

sistema operativo, al realizar su mantenimiento de terminaciones, debe liberar la exclusión

mutua de manera que otros procesos puedan entrar en sus regiones críticas.

En el momento de un cambio de proceso del uno al otro se pueden producir las siguientes

situaciones:

 Sin sincronización entre procesos: Puede darse el caso de que ESCRIBIR esté

actualizando un registro y se quede a medías, sorprendiéndole el cambio de proceso,

por tanto, terminará de escribirlo cuando vuelva a hacer uso del procesador. Con el cambio le tocará el turno al proceso LEER, que accederá a dicho registro pudiendo

leerlo completamente. Es evidente que los datos leídos serán inconsistentes.

 

 Con sincronización entre procesos: Supongamos algún mecanismo que prohíba

la lectura (bloqueo de registros) a cualquier proceso, mientras el proceso ESCRIBIR

esté realizando alguna operación. En este caso, LEER, al hacer uso del procesador

que se encuentra bloqueado, quedaría en espera de que el registro quede totalmente

escrito y se proceda a su desbloqueo, LEER pasaría a estado bloqueado, ESCRIBIR

terminaría su trabajo sobre el registro y en el siguiente cambio LEER procedería a

hacer el suyo.

 

Esta sincronización por la cual una actividad impide que otras puedan tener acceso

a un dato mientras se encuentra realizando una operación sobre el mismo es lo que se

conoce como exclusión mutua.

La zona de código de un proceso que no puede ser interrumpida por otro, por los

motivos expuestos anteriormente se le llama Región Crítica.

Regiones críticas

Es el conjunto de actividades elementales cuya ejecución exige el monopolio de recursos.

Por ejemplo, para indicar que alguna acción se realizará con acceso exclusivo a ciertos

datos compartidos.

Región datos - compartidos do acción

 

¿Como evitar la región critica?. La clave para prevenir el problema aquí y en

muchas otras situaciones en que interviene la memoria compartida, archivos compartidos y

todo lo que se comparte, consiste en determinar alguna manera de prohibir que un proceso

lea y escriba los datos compartidos al mismo tiempo.

De otra manera lo que se necesita es la sincronización. Una manera de asegurar de que si

un proceso ésta utilizando una variable o archivo compartido, es que los otros procesos no

pueden hacer lo mismo.

Para tener una solución adecuada a la región crítica se necesita que se cumplan cuatro

condiciones.

1. Nunca dos procesos pueden encontrarse simultáneamente dentro de sus regiones

críticas.

2. No se hacen suposiciones acerca de las velocidades relativas de los procesos o

del Número de CPU.

3. Ningún proceso suspendido fuera de la región crítica debe bloquear a otros procesos.

4. Nunca un proceso debe querer entrar en forma arbitraria en su región crítica.

Representación de regiones criticas

Cuando se diseña un proceso que debe contener una o varias regiones críticas se

deben de tomar en cuenta las siguientes consideraciones:

 La región crítica debe ser ejecutada lo más rápido posible. 

  Un programa no debe ínter bloquearse en una región crítica.

 Las regiones críticas deben ser programadas con mucho cuidado (no se

permiten Ciclos indefinidos).

 Mientras un proceso está en su región crítica otros procesos pueden continuar

 Ejecutándose fuera de las regiones críticas.

 Cuando se tienen procesos que comparten datos, si un proceso deja la región

 Crítica otro de los procesos que espera a entrar en su región crítica puede proceder.

Cuando el proceso termina, voluntaria o involuntariamente, el sistema operativo debe de

realizar la limpieza propia de fin de proceso y liberar la exclusión mutua de otros procesos

El problema de la Sección Crítica

 En procesos compitiendo para utilizar algún dato compartido.

 Cada proceso tiene un segmento de código, llamado sección crítica, en el que se

accede al dato compartido.

 Problema – asegurarse de que cuando un proceso esta ejecutándose en su sección

crítica, a ningún otro proceso se le permite ejecutar la suya.

 Estructura del proceso Pi

repeat

entry                                              section

sección                                          crítica

exit                                                 section

sección                                          restante

until false;

Solución al problema de la Sección Crítica

 Una solución al problema de la sección crítica debe satisfacer los siguientes tres

requerimientos:

1. Exclusión Mútua. Si un proceso Pi esta ejecutándose en su sección crítica,

entonces ninguno de los otros procesos puede estar en su sección crítica.

 

2. Progreso. Si ningún proceso esta ejecutándose en su sección crítica y existen

procesos que quieren entrar en su sección crítica, entonces la selección del

próximo proceso que entrará a la sección crítica no puede ser pospuesta

indefinidamente.

3. Espera limitada. Debe existir un límite del número de veces que se les

permite a otros procesos entrar en sus secciones críticas en el intervalo entre

que un proceso ha hecho un requerimiento para entrar en su sección crítica y

que se le concede el permiso.

 Se supone que cada proceso se ejecuta a velocidad distinta de cero.

 Ninguna suposición respecto a la velocidad relativa de los n procesos.

2.5 Niveles, objetivos y criterios de planificación

2.5 Niveles, objetivos y criterios de planificación

La planificación es el proceso por el cual el sistema operativo selecciona que proceso ejecutar. La selección del proceso se basa en alguno de los algoritmos de planificación. La planificación de la CPU, en el sentido de conmutarla entre los distintos procesos, es una de las funciones del sistema operativo. Este despacho es llevado a cabo por un pequeño programa llamado planificador a corto plazo o dispatcher (despachador). La misión del dispatcher consiste en asignar la CPU a uno de los procesos ejecutables del sistema, para ello sigue un determinado algoritmo. Los acontecimientos que pueden provocar la llamada al dispatcher dependen del sistema (son un subconjunto de las interrupciones), pero son alguno de estos: 

 El proceso en ejecución acaba su ejecución o no puede seguir ejecutándose (por una E/S, operación WAIT, etc). 

 Un elemento del sistema operativo ordena el bloqueo del proceso en ejecución 

 El proceso en ejecución agota su cuantum o cuanto de estancia en la CPU. 

 Un proceso pasa a estado listo. 

Hay que destacar el hecho de que cuanto menos se llame al dispatcher menos tiempo ocupa la CPU un programa del sistema operativo, y, por tanto, se dedica más tiempo a los procesos del usuario (un cambio de proceso lleva bastante tiempo). Así, si sólo se activa el dispatcher como consecuencia de los 2 primeros acontecimientos se estará haciendo un buen uso del procesador. Este criterio es acertado en sistemas por lotes en los que los programas no son interactivos. Sin embargo, en un sistema de tiempo compartido no es adecuado, pues un proceso que se dedicara a realizar cálculos, y no realizara E/S, monopolizaría el uso de la CPU. En estos sistemas hay que tener en cuenta el conjunto de todos los procesos, activándose el dispatcher con la circunstancia tercera y, posiblemente, la cuarta. Los sistema operativos en que las dos siguientes circunstancias no provocan la activación del dispatcher muestran preferencia por el proceso en ejecución, si no ocurre esto se tiene más en cuenta el conjunto de todos los procesos.

puede definir el scheduling -algunas veces traducido como -planificación- como el conjunto de políticas y mecanismos construidos dentro del sistema operativo que gobiernan la forma de conseguir que los procesos a ejecutar lleguen a ejecutarse. El scheduling está asociado a las cuestiones de: 

 Cuándo introducir un nuevo proceso en el Sistema.

 Determinar el orden de ejecución de los procesos del sistema.

El scheduling está muy relacionado con la gestión de los recursos. Existen tres niveles de scheduling, estos niveles son: 

 Planificador de la CPU o a corto plazo. 

 Planificador a medio plazo. 

 Planificador a largo plazo 

En la planificación de procesos se suelen incluir varios niveles, en función del periodo temporal que cubren Planificación a largo plazo Este planificador está presente en algunos sistemas que admiten además de procesos interactivos trabajos por lotes. Usualmente, se les asigna una prioridad baja a los trabajos por lotes, utilizándose estos para mantener ocupados a los recursos del sistema durante períodos de baja actividad de los procesos interactivos. Normalmente, los trabajos por lotes realizan tareas rutinarias como el cálculo de nóminas; en este tipo de tareas el programador puede estimar su gasto en recursos, indicándoselo al sistema. Esto facilita el funcionamiento del planificador a largo plazo. 

El objetivo primordial del planificador a largo plazo es el de dar al planificador de la CPU una mezcla equilibrada de trabajos, tales como los limitados por la CPU (utilizan mucho la CPU) o la E/S. Así, por ejemplo, cuando la utilización de la CPU es baja, el planificador puede admitir más trabajos para aumentar el número de procesos listos y, con ello, la probabilidad de tener algún trabajo útil en espera de que se le asigne la CPU. A la inversa, cuando la utilización de la CPU llega a ser alta, y el tiempo de respuesta comienza a reflejarlo, el planificador a largo plazo puede optar por reducir la frecuencia de admisión de trabajos. Normalmente, se invoca al planificador a largo plazo siempre que un proceso termina. La frecuencia de invocación depende, pues, de la carga del sistema, pero generalmente es mucho menor que la de los otros dos planificadores. Esta baja frecuencia de uso hace que este planificador pueda permitirse utilizar algoritmos complejos, basados en las estimaciones de los nuevos trabajos. 

Planificación a Medio Plazo

En los sistemas de multiprogramación y tiempo compartido varios procesos residen en la memoria principal. El tamaño limitado de ésta hace que el número de procesos que residen en ella sea finito. Puede ocurrir que todos los procesos en memoria estén bloqueados, desperdiciándose así la CPU. En algunos sistemas se intercambian procesos enteros (swap) entre memoria principal y memoria secundaria (normalmente discos), con esto se aumenta el número de procesos, y, por tanto, la probabilidad de una mayor utilización de la CPU. El planificador a medio plazo es el encargado de regir las transiciones de procesos entre memoria principal y secundaria, actúa intentando maximizar la utilización de los recursos. Por ejemplo, transfiriendo siempre a memoria secundaria procesos bloqueados, o transfiriendo a memoria principal procesos bloqueados únicamente por no tener memoria. 

Planificación a corto plazo 

Qué proceso será el que se ejecutará en el procesador en el instante siguiente. Expulsión denota si un proceso acapara el procesador cuando está ejecutándose. Existen sistemas con y sin expulsión: a) Sin expulsión: un proceso conserva el uso del procesador mientras lo desee; es decir, mientras no solicite del SO un servicio que lo bloquee. Ventajas: minimiza tiempo de planificación. Inconvenientes: un proceso podría monopolizar el uso del procesador. b) Con expulsión: el SO puede desalojar a un proceso del uso del procesador (sin que el proceso lo haya solicitado). Ventaja: control sobre el tiempo de ejecución de cada proceso. Inconveniente: gasto de tiempo. 

Objetivos y Criterios de Planificación Los objetivos del planificador se resumen en: 

a) Reparto equitativo del tiempo de procesador 

b) Eficiencia en el uso del procesador 

c) Menor tiempo de respuesta en uso interactivo

d) Cumplir plazos de ejecución de los sistemas de tiempo real 

El principal objetivo de la planificación a corto plazo es repartir el tiempo del procesador de forma que se optimicen algunos puntos del comportamiento del sistema. Generalmente se fija un conjunto de criterios con los que evaluar las diversas estrategias de planificación. El criterio más empleado establece dos clasificaciones. En primer lugar, se puede hacer una distinción entre los criterios orientados a los usuarios y los orientados al sistema. Los criterios orientados al usuario se refieren al comportamiento del sistema tal y como lo perciben los usuarios o los procesos. 

Uno de los parámetros es el tiempo de respuesta. El tiempo de respuesta es el periodo de tiempo transcurrido desde que se emite una solicitud hasta que la respuesta aparece en la salida. Sería conveniente disponer de una política de planificación que ofrezca un buen servicio a diversos usuarios. Otros criterios están orientados al sistema, esto es, se centran en el uso efectivo y eficiente del procesador. Un ejemplo puede ser la productividad, es decir, el ritmo con el que los procesos terminan. La productividad es una medida muy válida del rendimiento de un sistema y que sería deseable maximizar. 

Otra forma de clasificación es considerar los criterios relativos al rendimiento del sistema y los que no lo son. Los criterios relativos al rendimiento son cuantitativos y, en general, pueden evaluarse o ser analizados fácilmente. Algunos ejemplos son el tiempo de respuesta y la productividad. Los criterios no relativos al rendimiento son, en cambio cualitativos y no pueden ser evaluados fácilmente. Un ejemplo de estos criterios es la previsibilidad. Sería conveniente que el servicio ofrecido a los usuarios tenga las mismas características en todo momento, independientemente de la existencia de otros trabajos ejecutados por el sistema. En particular, una disciplina de planificación debe:

 Ser equitativa: debe intentar hacer una planificación justa, esto es, se debe tratar a todos los procesos de la misma forma y no aplazar indefinidamente ningún proceso. La mejor forma de evitarlo es emplear alguna técnica de envejecimiento; es decir, mientras un proceso espera un recurso, su prioridad debe crecer. 

 Ser eficiente: debe maximizar el uso de los recursos tales como intentar que la ocupación de la CPU sea máxima. Al mismo tiempo se debe intentar reducir el gasto extra por considerar que es trabajo no productivo. Normalmente el idear algoritmos eficientes supone invertir recursos en gestión del propio sistema. 

 Lograr un tiempo bueno de respuesta, es decir, que los usuarios interactivos reciban respuesta en tiempos aceptables. 

 Lograr un tiempo de proceso global predecible. Esto quiere decir que un proceso debe ejecutarse aproximadamente en el mismo tiempo y casi al mismo costo con independencia de la carga del sistema. 

 Elevar al máximo la productividad o el rendimiento, esto es, maximizar el número de trabajos procesados por unidad de tiempo. Eso supone, por un lado, dar preferencia a los procesos que ocupan recursos decisivos y, por otro, favorecer a los procesos que muestran un comportamiento deseable. En el primer caso conseguimos liberar el recurso cuanto antes para que esté disponible para un proceso de mayor prioridad. Con el segundo criterio escogemos a los procesos que no consumen muchos recursos dejándole al sistema mayor capacidad de actuación. 

Estos criterios son dependientes entre sí y es imposible optimizar todos de forma simultánea. Por ejemplo, obtener un buen tiempo de respuesta puede exigir un algoritmo de planificación que alterne entre los procesos con frecuencia, lo que incrementa la sobrecarga del sistema y reduce la productividad. Por tanto, en el diseño de una política de planificación entran en juego compromisos entre requisitos opuestos; el peso relativo que reciben los distintos requisitos dependerá de la naturaleza y empleo del sistema. 

Planificación Apropiativa y No apropiativa 

Una disciplina de planificación es no apropiativa si una vez que la CPU ha sido asignada al proceso, ya no se le puede arrebatar. Y por el contrario, es apropiativa, si se le puede quitar la CPU. 

La planificación apropiativa es útil en los sistemas en los cuales los procesos de alta prioridad requieren una atención rápida. En los de tiempo real, por ejemplo, las consecuencias de perder una interrupción pueden ser desastrosas. 

En los sistemas de tiempo compartido, la planificación apropiativa es importante para garantizar tiempos de respuesta aceptables La apropiación tiene un precio. El cambio de proceso implica gasto extra. Para que la técnica de apropiación sea efectiva deben mantenerse muchos procesos en memoria principal de manera que el siguiente proceso se encuentre listo cuando quede disponible la CPU. Conservar en memoria principal procesos que no están en ejecución implica gasto extra. En los sistema no apropiativos, los trabajos largos retrasan a los cortos, pero el tratamiento para todos los procesos es más justo. Los tiempos de respuesta son más predecibles porque los trabajos nuevos de alta prioridad no pueden desplazar a los trabajos en espera. Al diseñar mecanismos de planificación apropiativa no hay que perder de vista la arbitrariedad de casi todos los sistemas de prioridades. Se puede construir un mecanismo complejo para implantar fielmente un esquema de apropiación por prioridades sin que, de hecho, se hayan asignado prioridades de forma coherente. 

El Reloj de Interrupciones 

El sistema operativo gestiona un reloj de interrupciones que genera interrupciones cada cierto tiempo. Un proceso mantiene el control de la CPU hasta que la libera voluntariamente (acaba su ejecución, o se bloquea), hasta que el reloj interrumpe o hasta que alguna otra interrupción desvía la atención de la CPU. Si el usuario se encuentra en ejecución y el reloj interrumpe, el sistema operativo entra en ejecución para comprobar, por ejemplo, si ha pasado el cuanto de tiempo del proceso que estaba en ejecución. 

El reloj de interrupciones asegura que ningún proceso acapare la utilización del procesador. El sistema operativo, apoyándose en él, intenta distribuir el tiempo de CPU entre los distintos procesos ya sean de E/S o de cálculo. Por tanto, ayuda a garantizar tiempos de respuesta para los usuarios interactivos, evitando que el sistema quede bloqueado en un ciclo infinito de algún usuario y permite que los procesos respondan a eventos dependientes de tiempo. Los procesos que deben ejecutarse periódicamente dependen del reloj de interrupciones.

No se debe confundir en ningún caso al reloj de interrupciones con el reloj de la máquina o reloj hardware. Veamos con un pequeño ejemplo como esto es imposible. 

Como sabemos, todas las tareas de una computadora están sincronizadas por un reloj hardware. La velocidad de un procesador determina la rapidez con la que ejecuta un paso elemental o cambio en el sistema. Por ejemplo, si decimos de una máquina que tienen un microprocesador que va a una frecuencia de 100 MHz eso quiere decir que produce alrededor de 100 millones de pasos elementales o cambios en el sistema en un segundo. Pero una instrucción consume algunos de estos pasos mínimos. 

Supongamos que en media una instrucción consume alrededor de 100 pasos elementales. No podemos interrumpir al procesador a la misma velocidad a la que opera porque entonces no se podría llegar nunca a ejecutar ninguna instrucción. Parece razonable que se elija una frecuencia menor para el reloj de interrupciones. Por ejemplo, se podría generar una interrupción cada 0'02 segundos (tener una frecuencia de 50 Hz) esto significa que se estaría interrumpiendo al procesador cada dos millones de ciclos. En ese tiempo bajo la suposición de que una instrucción consume 100 pasos se habría ejecutado unas 20000 instrucciones. Esto sí es mucho más razonable. En resumen el reloj de interrupciones tiene una frecuencia inferior al reloj hardware y superior al cuanto de tiempo o intervalos de tiempo en que se quiera controlar en el sistema. 

Uso de Prioridades

Las prioridades pueden ser asignadas de forma automática por el sistema, o bien se pueden asignar externamente. Pueden ganarse o comprarse. Pueden ser estáticas o dinámicas. Pueden asignarse de forma racional, o de manera arbitraria en situaciones en las que un mecanismo del sistema necesita distinguir entre procesos pero no le importa cuál de ellos es en verdad más importante. 

Las prioridades estáticas no cambian. Los mecanismos de prioridad estática son fáciles de llevar a la práctica e implican un gasto extra relativamente bajo. Sin embargo, no responden a cambios en el entorno que podrían hacer necesario un ajuste de prioridades.