INSTITUTO TECNOLOGICO DE TAPACHULA

INGENIERIA EN SISTEMAS COMPUTACIONALES

ASIGNATURA: SISTEMAS OPERATIVOS
DOCENTE: OLGA LUZ LOPEZ LOPEZ
SEMESTRE: 5º. “A”

UNIDAD 2
ADMINISTRADOR DE PROCESOS Y DEL PROCESADOR

2.1. CONCEPTO DE PROCESO

CONCEPTOS BASICOS:

ALGORITMO, PROGRAMA, PROCESO, PROCESADOR, TAREA O JOB, SESIÓN Y LOTE

2.1 CONCEPTO DE PROCESO

Un proceso no es más que un programa en ejecución, e incluye los valores actuales del contador de programa, los registros
y las variables. Conceptualmente cada uno 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, está organizado
en una serie del proceso secuenciales, o simplemente procesos.

1
La idea clave 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 cuándo debe de
trabajar en un proceso para atender a uno distinto.

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.

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.

2
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
3
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.

4
  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.

5
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:

6
                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:

 
7
                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

8
 - 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
9
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.

10
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

11
 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.
12
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

13
  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.

14
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 SECUENCIABILIDAD

15
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.

16
            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
17
 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.

18
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

19
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.

20
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;

21
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 ejecutandose 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.
Intentos iniciales para resolver el problema
 Inhibir las interrupciones.
 Solo dos procesos, P0 and P1
 Estructura general del proceso Pi
repeat
entry section
sección crítica
exit section
sección restante
until false;
 Los procesos pueden compartir algunas variables comunes para sincronizar sus acciones.
Algoritmo 1

Variables compartidas:
– var turn: (0..1);
inicialmente turn = 0
– turn = i ? Pi puede entrar en su sección crítica
Proceso Pi
repeat
while turn ? i do no-op;
sección crítica
turn := j;
sección restante
until false;
Satisface la condición de exclusión mútua, pero no la de progreso (si turn=0 y P1 esta listo para
entrar en su sección crítica, P1 no puede hacerlo, incluso aunque P0 este en la sección restante)

Algoritmo 2

Variables compartidas
– var flag: array [0..1] of boolean;
inicialmente flag [0] = flag [1] = false.
– flag [i] = true ? Pi listo para entrar en su sección crítica
Proceso Pi
repeat
flag[i] := true;
while flag[j] do no-op;
sección crítica
flag [i] := false;

22
sección restante
until false;
Satisface la exclusión mútua, pero no el requerimiento de progreso. (P0 pone flag[0 ] =true y P1
pone flag[1 ] =true; cada uno esperando al otro indefinidamente)

Algoritmo 3

- Combinación de las variables compartidas de los algoritmos 1 y 2.

- Proceso Pi
repeat
flag [i] := true;
turn := j;
while (flag [j] and turn = j) do no-op;
sección crítica
flag [i] := false;
sección restante
until false;
- Cumple los tres requerimientos; resuelve el problema de la sección crítica para dos procesos.

Algoritmo del panadero

 Antes de entrar a su sección crítica, los procesos reciben un número. El que posea el
número menor entra en la sección crítica.
 Si los procesos Pi y Pj reciben el mismo número, si i < j, entonces Pi es servido primero; si
no lo es Pj .
 El esquema de numeración siempre genera números en orden creciente; por ejemplo
1,2,3,3,3,3,4,5...

Sincronización de procesos en Sección Crítica

            En procesos concurrentes, la ejecución de un proceso se desarrolla en forma asíncrona
respecto a los otros. Sin embargo cuando dos,  o más procesos necesitan entrar en región crítica,
es necesario que exista una sincronización entre ellos a fin de garantizar que al menos uno y solo
un proceso entrará en región crítica.

            Si una actividad desea impedir que otra acceda a ciertos datos compartidos, mientras no
se cumpla una determinada condición, debemos sincronizar las actividades con dicha condición.
Por tanto, la sincronización es un elemento necesario para asegurar la exclusión mutua.

Existen tres algoritmos diseñados para este fin, son los siguientes:

 Espera Activa.
 Espera no Activa
 Mecanismos de Hardware.

Algoritmo de Espera activa.

23
 Estos algoritmos establecen la espera de entrada a la región crítica con un bucle que será roto en
el momento en que se cumpla una determinada condición. Se, les llama así por que el proceso no
queda bloqueado en su ejecución, sino que constantemente compite por el procesador. Entre los
distintos algoritmos de este tipo existentes podemos citar:

 Espera con mutex:  Algoritmo  que utiliza un  switch (MUTEX)  a  través del cual se

produce la sincronización.

   Alternancia: Ligeramente mejor que el anterior, utiliza también una variable turno para

realizar el sincronismo entre los Procesos.

   Algoritmo de DEKKER: Resuelve el problema mediante la solución propuesta por

DEKKER, basando su funcionamiento en una Tabla unidimensional de dos elementos
lógicos (Switches).

    Algoritmo de Espera no activa: Son los algoritmos que establecen la espera para

entrar en la región crítica bloqueando, el proceso, haciendo que deje de competir por el
procesador hasta que se cumpla la condición de desbloqueo

            Entre estos algoritmos existen los siguientes:

 Semáforos:  Para eliminar los problemas que se producen con los algoritmos de espera
activa, fundamentalmente los referidos a la sobrecarga que producen en el sistema,
Dijkstra(1965) diseño un mecanismo basado en una variable entera utilizada como
contador de peticiones de entrada a una sección crítica. Esta variable es compartida por
todos los procesos del sistema. Este nuevo tipo de variable se denominó semáforo, por su
capacidad de gestionar el tráfico de los proceso que desean acceder a datos
compartidos. Con este sistema,  cuando un proceso intente entrar en una región crítica
mientras otro está accediendo a los datos compartidos, se bloqueará  de igual manera que
cuando un proceso accede a un recurso que está ocupado.

Un semáforo se define como una variable entera que puede inicializarse y su valor no debe
ser negativo y solo puede ser manipulada por las operaciones P y V.

24
  Operaciones P y V: Estas operaciones son  indivisibles, es decir que cuando un proceso
ejecuta una de ellas no puede ser interrumpida.

            Operación V: Esta operación consiste en incrementar en uno el valor del semáforo sobre
el que actúa, también es conocida como signal. Es una operación de liberación.
            Así, si se tiene un semáforo S, V de S  V(S)  o signal(S)   causara  S=S+1. V(MUTEX)  -
libera

           Operación P: Bloqueo, decrementa en uno el valor del semáforo sobre el que actúa
siempre y cuando el valor del semáforo es   >=0  (positivo) también se le conoce en la literatura
inglesa como Wait.  Por ejemplo si tenemos P(S), Wait(S)  si  S=S-1. P(MUTEX) - Espera el
proceso.

De las definiciones anteriores se puede observar que el valor de un semáforo esta

relacionado con el número de veces que se ejecutan, dichas operaciones es decir, el valor del
semáforo S es igual a su valor inicial más número de operaciones V menos número de
operaciones P realizadas por ese semáforo.

                        VAL(S) = C(S) + NV(S) - NP(S)                 NP( ) <= NV( ) +1

           
                        VALOR            VALOR INICIAL

            Por definición se tiene que el valor del semáforo debe ser mayor que cero, VAL(S)>0. En
el caso cuando el valor del semáforo es cero que relación nos queda:

                        NP(S) = C(S) + NV(S)

            Es importante señalar que la relación anterior será siempre valida independientemente
del número de operaciones P y V ejecutadas sobre el semáforo.

 Regiones críticas:    Son sistemas que permiten establecer protecciones contra una mala
utilización de los usuarios. Para ello sólo permiten que los datos compartidos se puedan
acceder desde determinadas regiones quedando transparentes desde el resto.  Tiene
inconvenientes relacionados con la sincronización y no permite que varias actividades
puedan realizar operaciones de lectura simultánea.

25
  Regiones criticas condicionales: Es una mejora del método anterior tratando de
resolver algunos problemas de sincronización que se presentan.

 Monitores:   Uno de los problemas en los mecanismos anteriores es que el programador

tiene que proporcionar de forma explícita el modo de sincronización. Para evitarlo B.
Hansen y C.A.R. Hoare desarrollarón un nuevo mecanismo denominado Monitor que debe
ser soportado por el lenguaje correspondiente.

            Un monitor permite compartir, segura y eficientemente, datos entre varias actividades,
garantizando la exclusión mutua, sin necesidad de que el programador tenga que suministrarla
explícitamente.
            Se basa en dos premisas: la primera es la abstracción de datos consistente en una
técnica capaz de separar las operaciones a ejecutar sobre los datos, de los detalles de diseño
propio de los mismos (los lenguajes Modula y Ada soportan este tipo de estructuras). La segunda
es que realizan la exclusión mutua de forma implícita.

            La finalidad más útil de los monitores es reunir todas las funciones que operan sobre un
conjunto de datos compartidos en un sólo módulo, de manera que todos los accesos a esos datos
estarán forzados a utilizar dichas funciones.

 Contadores de eventos:Es un mecanismo para sincronizar actividades sin que sea

necesario forzar la exclusión mutua, ya sea por que no deseamos limitar la concurrencia de
las actividades, o simplemente porque no lo necesitamos. Se basa en una variable entera
que cuenta determinadas operaciones.

  Mensajes: Mecanismo que permite intercambiar información necesaria durante el

desarrollo normal de un proceso en ejecución. Es más un mecanismo de cooperación que
de sincronización.

Existen dos  tipos de comunicación entre procesos:

 Directa: Envió y recepción de mensajes entre si; de manera que se asocia un enlace vi

direccional único entre cada dos procesos.

 Indirecta: Mensajes enviados y recibidos a través de mail boxees o buzones de correo.

Con este método cada proceso puede estar relacionado con tantos buzones como desee
consiguiendo comunicarse con tantos procesos como sea necesario.

26
Mecanismos de Hardware

Son instrucciones hardware que aseguran la exclusión mutua. Entre las más utilizadas son las
siguientes:

 Deshabilitar interrupciones: Se puede forzar la exclusión mutua deshabilitando las

interrupciones mientras haya alguna actividad en la región crítica. De este modo, dicha
actividad no podrá ser interrumpida y, por tanto, no se podrá producir ningún cambio de
proceso. La habilitación y deshabilitación se realiza con una instrucción máquina, es una
operación rápida.

 Instrucción TEST-AND-SET: Forza la exclusión mutua. La ventaja es que no puede ser

interrumpida por que no muchas computadoras la poseen.

 Lock: Se basa en la instrucción anterior y permite el acceso a la región crítica a un proceso

en caso de no existir otra actividad dentro de su región crítica, no permitiendo en caso
contrario.

¿Como resolver la exclusión mutua usando semáforos?.

            Para resolver el problema de debe hacer lo siguiente:

            1.- Identificar todas las regiones críticas.

            2.- Definir tantos semáforos como regiones críticas se tengan, dichos semáforos
se inicializarán con 1
            3.- C/U de las regiones críticas será antecedida por la operación P y precedida por la
                  operación V.
                                   Ejemplo:  MUTEX es el semáforo
                                                           Región crítica.

Con lo anterior solo un proceso podrá entrar a la región crítica con lo que se esta asegurando la
exclusión mutua.
                                                                       MUTEX = 1

* Que pasa si se tiene:

A)        P(MUTEX)                           Entra el proceso, se decrementa en uno el semáforo pero no

libera, por lo tanto hay un dead lock, no hay sincronización entre procesos
27
            SECCION CRITICA                ni exclusión mutua
            P(MUTEX)                           

B)        V(MUTEX)                          Sale el proceso se incrementa en uno el semáforo libera el

proceso, por lo tanto no hay dead lock, no  origina proceso de exclusión mutua
            SECCION CRITICA          
            V(MUTEX)                        .

C)        V(MUTEX)                          Sale el proceso se incrementa en uno el semáforo pero no

libera, por lo tanto no hay dead lock.
            SECCION CRITICA         
            P(MUTEX)

D)        P(MUTEX)                           Entra el proceso consume y libera, por lo tanto no hay dead

lock, y da solución a la exclusión mutua  y a la sincronización.
            SECCION CRITICA          
            V(MUTEX)                        

Pregunta. * Varios procesos actualizan en forma concurrente a una lista ligada.

a) Que problema se puede producir.

            R.- Se puede producir un problema de sincronización y no hay exclusión mutua.
b) Es un problema de exclusión mutua.
            R.- Exclusión mutua.
c) Como resolver el problema.
            R.- Dando solución a la exclusión mutua.
* Si las operaciones P y V no fueran atómicas, la exclusión mutua seria violada.
            R.- Si por que los procesos pueden tomar el mismo valor y  no se incrementa dos veces
sino  solo una.

PROBLEMAS CLASICOS DE SINCRONIZACIÓN

            Este tipo de problemas constituyen ejemplos de una amplia clase de problemas de

control  de concurrencia. Estos problemas se utilizan para probar casi todos los esquemas de
sincronización propuestos. En las soluciones se emplean semáforos para la solución.

El problema de buffer limitado

28
            Supongamos que el depósito consiste en n buffers, cada uno capaz de almacenar un
elemento. El semáforo MUTEX proporciona la exclusión mutua para los accesos al depósito de
buffers y se le asigna un valor inicial de 1. Los semáforos vacíos y llenos cuentan el número de
buffers vacíos y llenos, respectivamente. El semáforo vacío recibe 1 un valor inicial n; al semáforo
lleno se le asigna el valor inicial 0.

El problema de los lectores y escritores.

            Un objeto de datos (como un archivo o un registro) va a ser compartido por  varios
procesos concurrentes. Algunos de estos procesos sólo quieren leer el contenido del objeto
compartido, mientras que otros quieren actualizarlos  (o sea, leerlo y escribirlo), hacemos una
distinción entre estos dos tipos de procesos refiriéndonos a los procesos interesados sólo en leer
como lectores y escritores y a los demás como escritores. Obviamente, el que dos lectores tengan
acceso simultáneo al objeto de datos compartido no tendrá ningún efecto adverso; sin embargo,
si un escritor y otro proceso (ya sea lector o escritor) tiene acceso simultáneo al objeto
compartido, puede surgir el caos.
            Para asegurar que no surjan estas dificultades, es necesario que los escritores tengan
acceso exclusivo al objeto compartido. A este problema de sincronización se le conoce como
problema de los lectores y escritores, el cual es ha utilizado para probar casi todas las nuevas
primitivas de sincronización.

El problema de los filósofos comensales

            Cinco filósofos pasan su vida comiendo u pensando. Los filósofos comparten una mesa
circular rodeada por cinco sillas, una para cada uno de ellos. En el centro de la mesa se encuentra
una fuente de arroz, y también sobre la mesa hay cinco palillos chinos. Cuando un filósofo piensa,
no interactúa con sus colegas. Ocasionalmente, un filósofo tiene hambre y trata de coger los dos
palillos que están más cerca de él (los palillos colocados entre él y sus vecinos de la derecha y de
la izquierda). Un filósofo sólo puede coger un palillo a la vez y, obviamente, no puede ser el que
esta en la mano de un vecino. Cuando un filósofo ambiento tiene sus dos palillos al mismo tiempo
come sin soltarlos. Cuando termina de comer, coloca ambos palillos sobre la mesa y comienza a
pensar otra vez.

Problema del productor consumidor

 En un contexto de procesos concurrentes, se tiene un conjunto de procesos productores de

mensajes y otro conjunto de procesos consumidores de mensajes. La zona donde se depositarán y
recogerán los mensajes es un buffer de tamaño n (n localidades).
           

29
            Tanto productores como consumidores ejecutaran cíclicamente los siguientes algoritmos.

 Productor consumidor.

El recurso que se va a compartir es el buffer por lo tanto la sección critica será el acceso
y  manipulación de dicho  buffer.

Para resolver el problema de exclusión mutua será necesario definir un semáforo para controlar el
acceso al buffer,

 Definición  de  un  semáforo   para   controlar   el   accedo  a  buffer.
 Cuando el consumidor se apodera del buffer P ( ) !Sorpresa  esta vacío ¡

                                   Productor gana
                                   se apodera del buffer
                                   ¡¡¡sorpresa el buffer   esta lleno!!!
                                   no va a poder depositar
                                   y por lo tanto va a liberar el buffer
                                   nunca hace V( ).

 Productor consumidor utilizando espera activa, figura # 22.

                                   Productor                                         Consumidor

                        Produce msg.                                                Lock (existe msg.)

                        Lock (espacio disponible)                            Lock (acceso a buffer)
                        Lock (acceso a buffer)                                 extrae msg.
                        Deposita msg.                                               Unlock (acceso a buffer)
                        Unlock (acceso a buffer)                             Unlock (espacio disponible)
                        Unlock (existe msg.)                                     Consume msg.
     
   Problema de sincronización. La sincronización entre productor y consumidor es necesaria
debido a lo siguiente: Los productores no deben depositar mensajes si el buffer se encuentra lleno
y los consumidores no deben accesar el buffer cuando este se encuentre vació.
            Para resolver el problema de definirá un semáforo que defina el espacio disponible y será
inicializado con un valor igual a n y un semáforo que defina la existencia de mensaje el cual
será  inicializado con un 0.

30
                        Productor                                                     Consumidor
                        produce msg.                                                P (existe msg.)    
             X        P (espacio disponible)                                  P (acceso s buffer)
                        P (acceso a buffer)                                         extrae msg.
            *            deposita msg                                               V (acceso a buffer)
                        V (acceso a buffer)                                      V (espacio disponible)
            X         V (existe msg)                                                Consume msg.         

                     Solución   a  la   exclusión  mutua  X –

Solución de la sincronización
                                                          
Buffer lleno                       Espacio disponible=N, existe msg=0.

Casos críticos

Buffer vacío

Mecanismo de semáforos
Un semáforo es un tipo de datos abstracto que permite el uso de un recurso de manera exclusiva
cuando varios procesos están compitiendo. 

El tipo de datos abstracto cumple la siguiente semántica: 

 El estado interno del semáforo cuenta cuantos procesos todavía pueden utilizar el recurso.
Se puede realizar, por ejemplo, con un número entero que nunca llega a ser negativo.
 Exiten tres operaciones con un semáforo: init(), wait(), y signal() que realizan lo siguiente:
init()
 Inicializa el semáforo antes de que cualquier proceso haya ejecutado ni una operación wait() ni
una operación signal() al límite de número de procesos que tengan derecho a acceder el recurso.
Si se inicializa con 1, se ha contruido un semáforo binario.
wait()
Si el estado indica cero, el proceso se queda atrapado en el semáforo hasta que sea despertado
por otro proceso. Si el estado indica que un proceso más puede acceder el recurso se decrementa
el contador y la operación termina con exito.
La operación wait() tiene que estár implementada como una instrucción atómica. Sin embargo, en
muchas implementaciones la operación wait() puede ser interrumpida. Normalmente existe una
forma de comprobar si la salida del wait() es debido a una interrupción o porque se ha dado
acceso al semáforo.
signal()
Una vez se ha terminado el uso del recurso, el proceso lo señaliza al semáforo. Si queda algún
proceso bloqueado en el semáforo uno de ellos sea despertado, sino se incrementa el contador.
La operación signal() también tiene que estár implementada como instrucción atómica. En algunás
implementaciones es posible comprobar si se haya despertado un proceso con exito en caso que
hubiera alguno bloqueado.
Para despertar los procesos se puede implementar varias formas que se destinguen en sus grados
de justicia, por ejemplo con un simple sistema tipo FIFO.

El acceso mutuo a regiones críticas se arregla con un semáforo que permita el acceso a un sólo
proceso 
S.init(1)
31
P1                                                P2
a: loop                                              loop
b:    S.wait()                                      S.wait()
c:    critical region                        critical region
d:    S.signal()                                  S.signal()
e:    non-critical region                non-critical region
f: endloop                                        endloop
Observamos los siguiente detalles: 
 Si algún proceso no libera el semáforo, se puede provocar un bloqueo.
 No hace falta que un proceso libere su propio recurso, es decir, la operación signal() puede
sea ejecutada por otro proceso.
 Con simples semáforos no se puede imponer un orden en los procesos accediendo a
diferentes recursos.
Si existen en un entorno solamente semáforos binarios, se puede simular un semáforo general
usando dos semáforos binarios y un contador, por ejemplo, con las
variables delay, mutex y count. 
La operación init() inicializa el contador al número máximo permitido. El semáforo mutex asegura
acceso mutuamente exclusivo al contador. El semáforo delay atrapa a los procesos que superan el
número máximo permitido. 
La operación wait() se implementa de la siguiente manera: 
  delay.wait()
  mutex.wait()
  decrement count
  if count greater 0 then delay.signal()
  mutex.signal()
y la operación signal() se implementa de la siguiente manera: 
  mutex.wait()
  increment count
  if count equal 1 then delay.signal()
  mutex.signal()
Unas principales desventajas de semáforos son: 
 no se puede imponer el uso correcto de los wait()s y signal()s
 no existe una asociación entre el semáforo y el recurso
 entre wait() y signal() el usuario puede realizar cualquier operación con el recurso

Mecanismo de Monitores
Todas las estructuras que hemos visto hasta ahora siguen provocando problemas para el
programador: 
 El control sobre los recursos está distribuido por varios puntos de un programa
 No hay protección de las variables de control que siempre fueron globales
Por eso se usa el concepto de monitores que implementan un nivel aún más alto de abstracción
facilitando el acceso a recursos compartidos. 

Un monitor es un tipo de datos abstracto que contiene:                                                              
 un conjunto de procedimientos de control de los cuales solamente un subconjunto es
visible desde fuera
 un conjunto de datos privados, es decir, no visibles desde fuera
El acceso al monitor está permitido solamente a través de los procedimientos públicos y el
compilador garantiza exclusión mutua para todos los procedimientos. La implementación del
monitor controla la exclusión mutua con colas de entrada que contengan todos los procesos
32
bloqueados. Pueden existir varias colas y el controlador del monitor elige de cual cola se va a
escoger el siguiente proceso para actuar sobre los datos. Un monitor no tiene acceso a variables
exteriores con el resultado de que su comportamiento no puede depender de ellos. 

Una desventaja de los monitores es la exclusividad de su uso, es decir, la concurrencia está

limitada si muchos procesos hacen uso del mismo monitor. 
Un aspecto que se encuentra en muchas implementaciones de monitores es la sincronización
condicional, es decir, mientras un proceso está ejecutando un procedimiento del monitor (con
exclusión mutua) puede dar paso a otro proceso liberando el cerrojo. Estas operaciones se suele
llamar wait() o delay(). El proceso que ha liberado el cerrojo se queda bloqueado hasta que otro
proceso le despierta de nuevo. Este bloqueo temporal está realizado dentro del monitor (dicha
técnica se refleja en Java con wait() y notify()). 

La técnica permite la sincronización entre procesos porque actuando sobre el mismo recurso los
procesos pueden cambiar el estado del recurso y pasar así información de un proceso al otro. 
Lenguajes de alto nivel que facilitan la programación concurrente suelen tener monitores
implementados dentro del lenguaje (por ejemplo refJavaMonitoresJava usa el concepto de
monitores para realizar el acceso mutuamente exclusivo a sus objetos). 
El uso de monitores es bastante costoso, porque se pierde eficiencia por tanto bloqueo de los
prosesos. Por eso se intenta aprovechar de primitivas más potentes para aliviar este problema,
como vemos en la siguiente sección. 

Interbloqueo (DeadLock)

Si un conjunto de procesos esta en estado de espera por recursos y nunca cambia de estado
porque los recursos por los que espera están siendo utilizados por otros procesos en estado de
espera tenemos un DEADLOCK. Los recursos son la memoria, dispositivos de E/S, semáforos,
archivos, etc. La forma en que un proceso hace uso de un recurso es:

Solicitud: si el recurso esta disponible se le otorga, si no el proceso pasa a estado de espera.

Uso: El proceso utiliza el recurso
Liberación: el proceso debe liberar el recurso.

Condiciones Necesarias para que se produzca DEADLOCK

Si se presentan simultáneamente las cuatro siguientes condiciones el sistema esta en DEADLOCK.
1. EXCLUSION MUTUA: Por lo menos un proceso que tenga otorgado un recurso en forma
exclusiva.
2. USO Y ESPERA: Debe existir al menos un proceso que este haciendo uso de un recurso y
que este esperando por otros recursos asignados a otros procesos.
3. NO INTERRUPCION: Los recursos no pueden ser retirados al proceso. Si un proceso hace
uso de un recurso no le podrá ser retirado hasta que voluntariamente el proceso lo libere.
4. ESPERA CIRCULAR: Debe existir un conjunto de procesos {P1.....Pn} tal que P1 espera por
un recurso utilizado por P2,......,Pn espera por un recurso utilizado por P1.
Resourse Allocation Graph(Grafo de utilizacion de recursos)
Conjunto de Vértices: U =P U R
P={P1,P2,....,Pn}
R={R1,R2,...,Rn}

Conjunto de Aristas
Una arista de un proceso Pi a un Recurso Rj significa que el proceso i esta haciendo una solicitud
por el recurso Rj.
33
Una arista del recurso Rj al proceso Pi, significa que el recurso esta asignado al proceso.
Si un RAG no tiene ciclos el sistema no esta en DEADLOCK,  si los tiene no se puede afirmar nada.

Mecanismos para tratar con Deadlocks

Evasion de Deadlocks

Si se tiene cuidado al en la forma de asignar los recursos se pueden evitar situaciones de

Deadlock. Supongamos un ambiente en el que todos los procesos declaren a priori la cantidad
máxima de recursos que habá de usar.

Estado Seguro

Un estado es seguro si se pueden asignar recursos a cada proceso (hasta su máximo) en algún
orden sin que se genere Deadlock. El estado es seguro si existe un ordenamiento de un conjunto
de procesos {P1...Pn} tal que para cada Pi los recursos que Pi podrá utilizar pueden ser otorgados
por los recursos disponibles mas los recursos utilizados por los procesos Pj,j<i. Si los recursos
solicitados por Pi no pueden ser otorgados, Pi espera a que todos los procesos Pj hayan
terminado.

Algoritmo del banquero de Dijkstra 

Asigna peticiones de recursos siempre que las mismas den como resultado estados seguros.
Solicitudes que den como resultado estados inseguros serán negadas hasta que puedan ser
satisfechas. Este algoritmos evita situaciones de Deadlock asignando los recursos en forma
correcta.
Las debilidades del algoritmo son: que requiere que la cantidad de recursos del sistema sea
constante, requiere una cantidad de procesos constante y requiere que los procesos garanticen
que los recursos van a ser devueltos en un intervalo finito de tiempo.

En el área de la informática, el problema del deadlock ha provocado y producido una serie de

estudios y técnicas muy útiles, ya que éste puede surgir en una sola máquina o como
consecuencia de compartir recursos en una red. 
En el área de las bases de datos y sistemas distribuidos han surgido técnicas como el 'two phase
locking' y el 'two phase commit' que van más allá de este trabajo. Sin embargo, el interés
principal sobre este problema se centra en generar técnicas para detectar, prevenir o corregir el
deadlock. 

Las técnicas para prevenir el deadlock consisten en proveer mecanismos para evitar que se
presente una o varias de las cuatro condiciones necesarias del deadlock. Algunas de ellas son: 

 Asignar recursos en orden lineal: Esto significa que todos los recursos están
etiquetados con un valor diferente y los procesos solo pueden hacer peticiones de recursos
'hacia adelante'. Esto es, que si un proceso tiene el recurso con etiqueta '5' no puede pedir
recursos cuya etiqueta sea menor que '5'. Con esto se evita la condición de ocupar y
esperar un recurso.

 Asignar todo o nada: Este mecanismo consiste en que el proceso pida todos los recursos
que va a necesitar de una vez y el sistema se los da solamente si puede dárselos todos, si
no, no le da nada y lo bloquea.

 Algoritmo del banquero: Este algoritmo usa una tabla de recursos para saber cuántos
recursos tiene de todo tipo. También requiere que los procesos informen del máximo de
recursos que va a usar de cada tipo. Cuando un proceso pide un recurso, el algoritmo
34
 verifica si asignándole ese recurso todavía le quedan otros del mismo tipo para que alguno
de los procesos en el sistema todavía se le pueda dar hasta su máximo. Si la respuesta es
afirmativa, el sistema se dice que está en 'estado seguro' y se otorga el recurso. Si la
respuesta es negativa, se dice que el sistema está en estado inseguro y se hace esperar a
ese proceso.

Para detectar un deadlock, se puede usar el mismo algoritmo del banquero, que aunque no dice
que hay un deadlock, sí dice cuándo se está en estado inseguro que es la antesala del deadlock.
Sin embargo, para detectar el deadlock se pueden usar las 'gráficas de recursos'. En ellas se
pueden usar cuadrados para indicar procesos y círculos para los recursos, y flechas para indicar si
un recurso ya está asignado a un proceso o si un proceso está esperando un recurso. El deadlock
es detectado cuando se puede hacer un viaje de ida y vuelta desde un proceso o recurso. Por
ejemplo, suponga los siguientes eventos: 

evento 1: Proceso A pide recurso 1 y se le asigna. 

evento 2: Proceso A termina su time slice. 
evento 3: Proceso B pide recurso 2 y se le asigna. 
evento 4: Proceso B termina su time slice. 
evento 5: Proceso C pide recurso 3 y se le asigna. 
evento 6: Proceso C pide recurso 1 y como lo está ocupando el proceso A, espera. 
evento 7: Proceso B pide recurso 3 y se bloquea porque lo ocupa el proceso C. 
evento 8: Proceso A pide recurso 2 y se bloquea porque lo ocupa el proceso B. 

En la figura 5.1 se observa como el 'resource graph' fue evolucionando hasta que se presentó el
deadlock, el cual significa que se puede viajar por las flechas desde un proceso o recurso hasta
regresar al punto de partida. En el deadlock están involucrados los procesos A,B y C. 

Una vez que un deadlock se detecta, es obvio que el sistema está en problemas y lo único que
resta por hacer es una de dos cosas: tener algún mecanismo de suspensión o reanudación que
permita copiar todo el contexto de un proceso incluyendo valores de memoria y aspecto de los
periféricos que esté usando para reanudarlo otro día, o simplemente eliminar un proceso o
arrebatarle el recurso, causando para ese proceso la pérdida de datos y tiempo. 

Dead lock en sistemas de spool.

            Los sistemas de spool suelen ser los más propensos al dead lock. Varios trabajos
parcialmente complejos que generan líneas de impresión a un archivo de spool pueden
interbloquearse si el espacio disponible para trabajar se llena antes de completarse alguno de
esos trabajos. La solución más común es limitar los spoolers de entrada de modo que no se lean
más archivos cuando se llega al límite de su capacidad.

Postergación indefinida.
            En los sistemas que mantienen procesos en espera mientras realizan la asignación de
recursos y/o procesan la planificación de decisiones, es posible que un proceso sea postergado de
manera indefinida mientras otro reciben la atención del sistema. A esta situación se le conoce
como postergación indefinida,  es diferente del dead lock pero sus consecuencias son igual de
negativas.

35
            En algunos sistemas la postergación indefinida se evita aumentando la prioridad de un
proceso mientras espera por un recurso, a esto se le llama envejecimiento.

Conceptos sobre recursos.

            Un sistema operativo es sobre todo un administrador de recursos, existen básicamente

dos tipos de recursos:

* Recursos no apropiativos.   Un  recurso  que  no  se puede liberar antes de completar

su  actividad sin perder la validez del proceso que lo usa, se dice que un recurso no apropiativo.
Una impresora o una unidad de cinta no pueden ser liberados hasta que no termine su trabajo.
* Recursos apropiativos.  Un  recurso  que  puede  ser  usado  temporalmente  por  varios
procesos sin comprometer el correcto funcionamiento de dichos procesos se dice que es
un  recurso  apropiativo. El CPU y la memoria principal  (mediante las técnicas de paginación)
son   recursos que pueden ser asignados temporalmente por varios procesos. La apropiatividad de
recursos es extremadamente importante en los sistemas de multiprogramación.

            Los datos y los programas son recursos que tienen características especiales. En un
sistema multiusuario donde se pueden compartir editores, compiladores y programas en general,
es ineficiente cargar una copia de ellos para cada usuario que lo solicite. En lugar de ello se carga
una sola vez a la memoria y se hacen varias copias de los datos, una por cada usuario.
            El código que no cambia mientras está  en uso se llama código reéntrate. El código que
puede ser cambiado pero que se inicializa cada vez que se usa se llama  reutilizable en serie. El
código reéntrate puede ser compartido simultáneamente por varios procesos mientras que el
reutilizable en serie sólo puede ser usado por un proceso a la vez.

Métodos para manejar los Dead Lock,

                                                     -  Prevención
                        - No permitirlos
                                                    - Evitarlos

                                                                                  - Difícil y caro

                        - Permitirlos y recuperarlos        
                                                                                 - Por perdida  de
información       

36
Figura # 24.  Prevención de Dead Lock.

En principio existen cuatro áreas importantes en la investigación del dead lock, a saber:

1) Prevención: 
            En las técnicas de prevención el interés se centra en condicionar un sistema para que
elimine toda probabilidad de que ocurra un dead lock (normalmente a costa de recursos).

2) Evitación:
            En las técnicas para evitar, la idea es poner condiciones menos estrictas que la
prevención, para lograr una mejor utilización de los recursos, pero procurando no caer en un dead
lock.

3) Detección:
            Los métodos de detección se usan en sistemas que permiten la ocurrencia de un dead
lock de forma voluntaria o involuntaria.

4) Recuperación:
            Los métodos de recuperación se usan para romper los dead lock en un sistema, para
poder liberarlo de ellos y los procesos estancados pueden continuar y llegar a su fin 

Modelo del sistema.

            Un sistema se compone de un número finito de recursos que se distribuyen entre varios
procesos que compiten por ellos. Los recursos se dividen en varios tipos, cada uno de los cuales
consiste en varios ejemplares idénticos. Los ciclos del CPU, el espacio de memoria, los archivos y
los dispositivos de E/S (como impresoras y unidades de cinta) son ejemplos de tipos de recursos.

            Un proceso debe solicitar un recurso antes de usarlo, y liberarlo al terminar su uso. Un
proceso puede solicitar cuantos recursos quiera para llevar a cabo su tarea. Obviamente, el
número no puede exceder del total de recursos disponibles del sistema. En otras palabras, un
proceso no puede solicitar tres impresoras si el sistema solo dispone de dos.

            En el modo de operación normal, un proceso solo puede utilizar un recurso en la

secuencia siguiente:

37
1. Solicitud. Si la solicitud no puede atenderse de inmediato (por ejemplo, otro proceso      está
utilizando ese recurso), entonces el proceso solicitante debe esperar hasta que pueda adquirir el
recurso.
2. Utilización. El proceso puede trabajar con el recurso (por ejemplo, si el recurso es una
impresora, el proceso puede imprimir en ella).
         3. Liberación. El proceso libera el recurso.

            La solicitud y liberación de recursos son llamadas al sistema. Algunos ejemplos son las
llamadas Solicitar y Liberar dispositivos, Abrir y Cerrar archivos, y Asignar y Liberar memoria. La
solicitud y liberación de otros recursos puede lograrse atreves de las operaciones espera (P) y
señal (V) sobre semáforos. Además la utilización de recursos solo puede conseguirse mediante
llamadas al sistema (por ejemplo, para leer o escribir en un archivo o dispositivo de E/S), de
modo que para cada utilización, el sistema operativo verifica que el proceso que dispone del
recurso ya lo había solicitado y ya se le había asignado. Una tabla del sistema registra si cada uno
de los recursos está libre o asignado y, de estar asignado, a qué proceso. Si un proceso solicita un
recurso que se encuentra asignado a otro, puede añadirse a la cola de procesos que esperan tal
recurso.

            Un conjunto de procesos se encuentra en estado de bloqueo mutuo cuando cada uno de
ellos espera un suceso que sólo puede originar otro proceso del mismo conjunto. 

Caracterización.

            Debe ser obvio que los bloqueos mutuos son indeseables, pues cuando se dan, los
procesos nunca terminan su ejecución y los recursos del sistema se paralizan, impidiendo que se
inicien otros procesos. Antes de analizar los distintos métodos para tratar el problema del bloqueo
mutuo  se describirán las circunstancias que los caracterizan.

Condiciones  necesarias  para  que  ocurra  un   Dead Lock.

            Coffman, Elphick y Shoshani. Establecieron las cuatro condiciones necesarias para que

se produzca un dead lock.

1.- Los procesos reclaman control exclusivo de los recursos que solicitan (exclusión mutua).

2.- Los procesos mantienen los recursos que se les han asignado mientras esperan por recursos
adicionales (condición de espera).
38
3.- No se pueden tomar los recursos que los procesos tienen hasta su completa utilización
(condición de no apropiatividad).

4.- Existe una cadena circular de procesos en la cual cada uno de ellos mantiene uno o más
recursos que son requeridos por el siguiente proceso de la cadena (condición de espera
circular).

            Se deben presentar las cuatro condiciones para que puede aparecer un Dead Lock. La
condición de espera circular implica la condición de retención y espera, por lo que las cuatro
condiciones no son completamente independientes. 

Prevención
            En las estrategias de prevención de dead Locks, los recursos son otorgados a los procesos
solicitados, de tal manera que la solicitud de un recurso nunca llega a un Dead Lock.  Esta
estrategia se cerciora de que cuando menos una de cuatro condiciones de Dead Lock nunca llegue
a ocurrir.

* Exclusión mutua.
            La condición de exclusión mutua debe conservarse para recursos no compartibles. Los
recursos compartibles, no requieren acceso mutuamente excluyente y, por tanto, no pueden
participar en un dead lock. Los archivos de  sólo lectura son un buen ejemplo de recursos
compartibles. Si varios procesos tratan de abrir  al mismo tiempo un archivo de sólo lectura, se
les puede otorgar accesos simultáneos al archivo, por lo general no es posible evitar dead
lock`s  negando la condición de exclusión mutua. Por su naturaleza algunos recursos no pueden
compartirse.   

* Negación de la condición de "espera por".

            La primera estrategia de Havender requiere que todos los recursos que va a necesitar un
proceso sean pedidos de una sola vez. El sistema deberá asignarlos según el principio "todo
o nada". Si el conjunto de recursos que necesita un proceso está disponible se le asigna (todo) y
se le permite entrar en ejecución. Si no es así, el proceso deberá esperar hasta que su conjunto
de recursos esté disponible. Mientras un proceso espera. No podrá tener ningún recurso.

Esta estrategia presenta las siguientes desventajas:

39
  Puede llevar a la postergación indefinida, ya que quizá todos los recursos   requeridos
estén disponibles al mismo tiempo (costos de operación altos).

 Puede llevar  un serio desperdicio de recursos, se requiere tener una gran cantidad
de  recursos para poder responder a cumplir petición.

 Es ineficiente por que decrementa la concurrencia del sistemas

Una variante consiste en dividir el programa en bloques que puedan ser ejecutados con
relativa independencia uno del otro. Esto reduce el desperdicio, pero implica un trabajo extra en el
diseño de las aplicaciones.

Negación de la condición de "no apropiatividad

            Cuando un sistema cuenta con los recursos suficientes para que los procesos puedan
funcionar sin problemas (bloqueos). Cuando el sistema permite compartir los recursos y los
procesos mantienen  los que otros necesitan sucede un dead lock.
            La segunda estrategia sugiere que cuando a un proceso que mantiene recursos se le
niegue una petición de recursos adicionales deberá liberar sus recursos y, si es necesario, pedirlos
de nuevo, junto con los adicionales.

            Al retirar los recursos a un proceso que no puede avanzar se niega la condición
de "no apropiatividad".  Un problema de esta política es la postergación indefinida.

Negación de la condición de "espera circular"

  Si se da a los recursos una manera exclusiva y se obliga a los procesos a pedirlos en
forma  ascendente es imposible que ocurra una espera circular. Esta propuesta considera:

 Los recursos deben ser numerados reflejando el orden en el cual la mayoría de los trabajos
los usan.
 Los procesos deben pedir los recursos en forma ascendente.
 Para los procesos que requieren de los recursos en un orden diferente, los recursos
deberán ser tomados y retenidos mucho antes de su utilización. (Implica el desperdicio de
los recursos mantenidos pero no usados).

  Ordenamiento lineal  del recurso.

El ordenamiento lineal elimina la posibilidad de la espera circular, pero, obliga al diseñador
a trabajar más con sus códigos. Además, los números de recursos son asignados por la instalación
y hay que vivir con ellos durante largos periodos (meses o años). Si  los  números  cambian  se
tienen  que rescribir los programas y los sistemas existentes.

40
La forma  más simple de prevenir un  Dead Lock  es obteniendo todos los recursos necesarios
antes que el proceso continué y así se elimine la  "condición de espera".

En otro método de prevención de dead lock, un proceso bloqueado devuelve los recursos
solicitados por un proceso activo, al igual que elimina la condición de "no apropiatividad"

Rosenkrantz  et al  Ha propuesto la siguiente optimización de este método. Todos los procesos
son asignados a prioridades únicas que pueden ser totalmente ordenadas. Un proceso de
retención cede el derecho de prioridad a otro proceso que sostiene el recurso necesario solo si el
proceso de retención tiene el recurso necesario solo si el proceso de retención tiene mayor
prioridad.
            Este método reduce los derechos de prioridad  al 50% al igual que previene los dead
locks. En el ordenamiento de Havender's todos los recursos son ordenados de manera única y
todos los procesos solicitan los recursos de manera ascendente.
            Únicamente eliminando la condición de "espera circular". Si un proceso ya sostiene
algunos recursos, entonces puede pedir solo aquellos acomodos en un rango superior en el orden.
Obteniendo recursos, de ésta forma, previene la formación de un ciclo o de un "knot".

Prevenir

Se puede prevenir el bloqueo siempre y cuando se consiga que alguna de las condiciones
necesarias para la existencia de un bloqueo no se produzca. 
1. los procesos tienen que compartir recursos con exclusión mutua:
o No se de a un proceso directamente acceso exclusivo al recurso, si no se usa otro
proceso que realiza el trabajo de todos los demás manejando una cola de tareas
(por ejemplo, un demonio para imprimir con su cola de documentos por imprimir).
2. los procesos quieren acceder a un recurso más mientras ya tienen acceso exclusivo a otro:
o Se exige que un proceso pida todos los recursos que va a utilizar al comienzo de su
trabajo
3. los recursos no permiten ser usados por más de un proceso al mismo tiempo:
o Se permite que un proceso aborte a otro proceso con el fin de obtener acceso
exclusivo al recurso. Hay que tener cuidado de no caer en livelock
4. Existe una cadena circular entre peticiones de procesos y locación de recursos:
o Se ordenan los recursos linealmente y se fuerza a los procesos que accedan a los
recursos en el orden impuesto. Así es imposible que se produzca un ciclo.
En las prácticas aplicamos dicho método para prevenir bloqueos en la lista concurrente. 

Prevención de Deadlocks

La estrategia consiste en anular alguna de las cuatro condiciones necesarias para que se produzca
un Deadlock.
1. No puede ser anulada porque existen recursos que deben ser usados en modalidad
exclusiva.

41
 2. La alternativa sería hacer que todos los procesos solicitaran todos los recursos que habrán
de utilizar antes de utilizarlos al momento de su ejecución lo cual sería muy ineficiente.
3. Para anular esta condición cuando un proceso solicita un recurso y este es negado el
proceso deberá liberar sus recursos y solicitarlos nuevamente con los recursos adicionales.
El problema es que hay recursos que no pueden ser interrumpidos.
4. Espera Circular: esta estrategia consiste en que el sistema operativo numere en forma
exclusiva los recursos y obligue a los procesos a solicitar recursos en forma ascendente. El
problema de esto es que quita posibilidades a la aplicación.
 Deadlock no puede ocurrir a menos que tenemos todas las cuatro condiciones. Si aseguramos
que no puede ocurrir por lo menos una de las condiciones, no podemos tener deadlock.
 Exclusión mutua. En general, no podemos eliminar esta condición. Hay recursos como
impresoras que no son compatibles.
 Retención y espera. Para no ocurrir esta condición, cuando un proceso solicita recursos,
no puede retener otros. Protocolos:
o Un proceso puede solicitar recursos solamente si no tiene ningunos.
o Un proceso tiene que solicitar todos los recursos antes de la ejecución.
Problemas:
o La utilización de recursos puede ser baja.
o Starvation (bloqueo indefinido) si se necesitan algunos recursos populares.
 No apropiación. Si un proceso retiene varios recursos y solicita otro que no está
disponible, se le expropian todos los recursos que retiene. El proceso tiene que recuperar
todos los recursos antes de ejecutar otra vez.
Pero en general no podemos expropiar recursos como impresoras y grabadores.
 Espera circular. Hacemos una ordenación de los tipos de recursos en el sistema (R1,
R2, ...). Un proceso tiene que solicitar sus recursos en orden (y todos los ejemplares de un
tipo al mismo tiempo). Si necesita un tipo de recurso más baja en la ordenación, tiene que
liberar los otros que retiene.
 Problemas con la prevención de deadlock: Utilización baja de recursos y reducción de la
productividad del sistema.

Evitar

El sistema no da permiso de acceso a recursos si es posible que el

proceso se bloquee en el futuro. Un método es el algoritmo del banquero
(Dijkstra) que es un algoritmo centralizado y por eso posiblemente no
muy practicable en muchas situaciones. 
Se garantiza que todos los procesos actúan de la siguiente manera en
dos fases: 
1. Primero se obtiene todos los cerrojos necesarios para realizar una tarea, eso se realiza
solamente si se puede obtener todos a la vez,
2. Después se realiza la tarea durante la cual posiblemente se liberan recursos que no son
necesarias.
Ejemplo: 
Asumimos que tengamos 3 procesos que actúan con varios recursos. El
sistema dispone de 12 recursos. 
proceso recursos pedidos recursos reservados
A 4 1
42
 B 6 4
C 8 5
suma 18 10
es decir, de los 12 recursos disponibles ya 10 están ocupados. La única
forma que se puede proceder es dar el acceso a los restantes 2 recursos
al proceso B. Cuando B haya terminado va a liberar sus 6 recursos que
incluso pueden estar distribuidos entre A y C, así que ambos también
pueden realizar su trabajo. 
Con un argumento de inducción se verifica fácilmente que nunca se llega
a ningún bloqueo. 

Evitación

            Un método para evitar los Dead Lock`s consiste en requerir

información adicional sobre cómo se solicitarán los recursos. Por ejemplo
en un sistema con una unidad de cinta y una impresora, podríamos
saber que el proceso P solicitará primero la unidad de cinta y luego la
impresora, antes de liberar ambos recursos. El proceso Q, por otra
parte, solicitará primero la impresora y después la unidad de cinta. Con
este conocimiento de la secuencia completa de la solicitud y liberación
para cada proceso para cada solicitud requiere que el sistema considera
los recursos disponibles en ese momento, los actualmente asignados a
cada proceso y las futuras solicitudes y liberaciones de cada proceso
para decidir si puede satisfacer la solicitud presente o debe esperar para
evitar un posible dead lock futuro.
Los diversos algoritmos difieren en la cantidad y tipo de información que
requieren. 

El modelo más sencillo y útil requiere que cada proceso declare

el número máximo de recursos de cada tipo que puede necesitar. Con
información a priori para cada proceso es posible construir un algoritmo
que asegure que el sistema nunca entrará en estado de dead lock. Este
algoritmo define la estrategia de evitación de dead lock`s.

            El estado de asignación de recursos viene definido por el

número de recursos disponibles  y asignados, y por la demanda máxima
de los procesos. Un estado es seguro si el sistema puede asignar
43
recursos a cada proceso (hasta el máximo) siguiendo algún orden u aun
así evitar el dead lock.
            Más formalmente, un sistema se encuentra en estado seguro
sólo si existe una secuencia segura. Si no existe esta secuencia, se dice
que el estado del sistema es inseguro.

            Un estado seguro no es un estado de dead lock, y un estado de

dead lock es un estado inseguro; pero no todos los estados inseguros
son dead lock`s. 
  Detección
Se implementa un proceso adicional que vigila si los demás forman una
cadena circular. 
Más preciso, se define el grafo de asignación de recursos: 
 Los procesos y los recursos representan los nodos de un grafo.
 Se añade cada vez una arista entre un nodo tipo recurso y un nodo
tipo proceso cuando el proceso ha obtenido acceso exclusivo al
recurso.
 Se añade cada vez una arista entre un nodo tipo recurso y un nodo
tipo proceso cuando el proceso está pidiendo acceso exclusivo al
recurso.
 Se eliminan las aristas entre proceso y recurso y al revés cuando el
proceso ya no usa el recurso.
Cuando se detecta en el grafo resultante un ciclo, es decir, cuando ya no
forma un grafo acíclico, se ha producido una posible situación de un
bloqueo. 
Se puede reaccionar de dos maneras si se ha encontrado un ciclo: 
 No se da permiso al último proceso de obtener el recurso.
 Sí se da permiso, pero una vez detectado el ciclo se aborta todos o
algunos de los procesos involucrados.
Sin embargo, las técnicas pueden dar como resultado que el programa
no avance, incluso, el programa se puede quedar atrapado haciendo
trabajo inútil: crear situaciones de bloqueo y abortar procesos
continuamente. 

Detección y Recuperación de Deadlocks

1. Cuando hay una única ocurrencia de cada recurso. (variante del

grafo de "wait for graph"). Consiste en reducir el grafo, retirando
las aristas que van de recursos a procesos y de procesos a
recursos, colocando nuevas aristas que reflejan la situación de
44
 espera entre procesos. Si el grafo reducido tiene ciclos el sistema
esta en Deadlock. Orden de operaciones = n^2 , n = cantidad de
aristas.
2. Cuando hay múltiples ocurrencias de cada recurso
Procedure detecta_deadlock
var Disponible:array[1..n] of integer //# de recursos
Usados:array[1..n] of integer
Solicitados:array[1..n] of integer
Finalizado:array[1..n] of boolean
Begin
Work:=Disponibles;
For i:=1..n do if(usados[i]≠0) then finish[i]:=false
Else finish[i]:=true;
While(encontrar_indice_i = true) do {
Work:=work + usados[i];
Finish[i]:=true; }
If ((finish[i] = false) para algun i), 1≤i≤n then à El sistema esta en
Deadlock.
End
Function encontrar_indice_i : Boolean
Begin
If (existe i tal que (Finish[i]=false && solicitados[i] ≤ work)
Then -> true
Else -> false
End

La evitacíon de deadlock tiene un costo porque todos los estados

inseguros no son estados de deadlock. Esto implica que hay tiempos
cuando algunos procesos tienen que esperar y recursos están
desocupados sin que es necesario.

El sistema operativo puede chequear de vez en cuando si hay un

deadlock. ¿Cuán frecuentemente debieramos chequear si hay deadlock? 
 El costo de algoritmo vs. el número de procesos en deadlock.
 Saber quien creó el deadlock.
  Cuando la utilización de la CPU es baja. 

Tenemos que eliminar los deadlocks que encontramos. Posibilidades: 

 Abortar todos los procesos en deadlock. ¡Esto es un método común!
45
  Abortar procesos uno a la vez hasta que no haya deadlock.
 Retroceder los procesos a algún punto y reiniciar. El deadlock puede reocurrir.
 Expropiar recursos de procesos hasta que no haya deadlock. Retrocedemos los procesos
expropiados.
Tenemos que seleccionar un proceso para abortar o retroceder. 
Factores:

 La prioridad
 El tiempo que el proceso ha corrido
 El número y tipo de los recursos adquiridos
 La clase de proceso (batch o interactiva)
La starvation es un problema. 
 
Detección y Recuperación

            Es el hecho de determinar si existe o no un Dead Lock, e identificar cuales son los
procesos y recursos implicados en él. El uso de algoritmos de detección de interbloqueo implica
una sobrecarga en el tiempo de ejecución. Para ser correcto, un algoritmo de detección de
interbloqueo debe de cumplir dos criterios:

            1) Debe detectar todos los dead lock´s   existentes en un tiempo finito.

            2) No debe reportar "falsos" Dead Lock's.

Grafo de asignación de recursos.

            Los Dead Lock pueden describirse con mayor precisión en función de un grafo dirigido
llamado grafo de asignación de recursos, que consiste en un conjunto de vértices V y aristas A. El
conjunto de vértices V se divide en dos tipos, P = {P1,P2, ... , Pn}, el conjunto formado
por  todos los procesos del sistema,  y   R ={R1,R2, ... ,Rn}, el conjunto integrado por todos los
tipos de recursos del sistema.

Representación mediante grafos del estado del sistema.

   El estado de un sistema es dinámico; esto es,  los procesos del sistema toman y liberan
recursos continuamente.  La  representación del dead lock requiere la representación del
estado  de la interacción  procesos - recursos, la representación se hace mediante un grafo
dirigido que se conoce como gráfica de asignación de recursos .

En los sistemas de bases de datos distribuidos (DDBS) está representación se conoce como
gráfica de espera de transacción (Transaction Wait-For TWF).

46
  Los dead lock`s pueden describirse con mayor precisión en función de un grafo dirigido llamado
grafo de asignación de recursos.
La simbologia es la siguiente .  a, b, c y d.

  
GRÁFICA DE PETICIÓN Y ASIGNACIÓN DE RECURSOS  

La técnica para la reducción de gráficas implica las consideraciones siguientes:

 Si las peticiones de recursos de un proceso piden ser concedidas, entonces la gráfica

puede ser reducida.
 La reducción de una gráfica consiste en retirar las flechas que van de los recursos a los
procesos y retirar las flechas que van del proceso al recurso.
 Si una gráfica puede ser reducida para todos sus procesos entonces no hay dead lock.
 Si una gráfica no puede ser reducida para todos sus procesos, entonces los
procesos irreducibles constituyen la serie de procesos interbloqueados de la gráfica.
 Detección de interbloqueo mediante grafos.

Un grafo G consiste de un conjunto finito no vacío.

V = C(G)   de:     P puntos (vértices) conjunto X de q parejas desordenadas de puntos

de V(aristas).
           
            cada par X = {U,V} de puntos en X y una línea de G  por lo tanto X = UV.
            Un grafo de p puntos y q líneas se denomina un grafo (p,q), el grafo (1,0) es trivial.

            Petición  =   Proceso - Recurso
                                            Pi

            Rx             Ry            El proceso Pi tiene el recurso Rx y solicita el recurso Ry.

  
Para determinar si existe un ciclo en un grafo se puede usar la representación matricial del grafo
dirigido. Dado que se tienen parejas ordenadas {Rx, Ry}, la matriz se construye colocando un 1
en la diagonal en (x,x) y (y,y) y un 1 en la posición (x,y) de la matriz.  .  
  
Reducción de la matriz del grafo.
Reducción de la matriz de un grafo correspondiente. No existen vértices terminales; los vértices 1
y 2 son iniciales y pueden ser eliminados; existe un Inter bloqueo.
47
  Representación vectorial

Un vértice terminal sólo aparece en la columna requiere y un vértice inicial sólo aparece en la
columna Tiene. Para reducir esta representación se recorren de arriba a abajo los vectores y se
buscan los vértices terminales e iniciales y se elimina su renglón.
            El proceso se repite hasta:
            1) No existen renglones o
            2) No se pueden eliminar renglones.
           
            Si no se pueden eliminar renglones las transiciones producen un Dead Lock.
            Para el grafo de la  en el primer paso se eliminan los procesos P1 (vértice inicial), P2 y P3
(vértice terminal). En el segundo paso se elimina el proceso P4 (vértice terminal),  inicial.

            Para el grafo de la el primero se eliminan los procesos P1,P2,P3

(vértices iniciales), P4(vértice inicial al eliminar el proceso P1), Los
procesos restantes no pueden ser eliminados, por lo tanto existe un
dead lock. El resultado de la reducción

Recuperación
Recuperación ante Deadlocks

1. Cancelación de procesos
1. Cancelación de todos los procesos involucrados. Esto resuelve
la situación de Deadlock pero tiene un costo muy alto de
reprocesamiento.
2. Cancelacion de un proceso por vez hasta resolver la situación
de Deadlock. La ventaja de esto es que el costo de
reprosesamiento de la información es menor pero cada vez
que se cancela un proceso debe ejecutarse el algoritmo de
detección de deadlock. Los criterios para elegir el candidato a
ser cancelado son: por prioridad, por tiempo de uso de CPU,
por cantidad de recursos utilizados y por cuantos recursos
adicionales habrá de utilizar.
2. Obtención de recursos (resourse Preemption). El sistema operativo
selecciona un proceso y le quita los recursos otorgados. Los
criterios para seleccionar el candidato son los mismos que para la
cancelación. El proceso seleccionado se le quitan los recursos y se
le lleva a un estado consistente (Rollback).
Recuperación de un Dead Lock.
48
            La única forma en que el sistema operativo puede recuperarse
de  un interbloqueo es retirando uno o más procesos y reclamar sus
recursos para que otros procesos puedan terminar. Normalmente varios
procesos perderán una parte o la totalidad del trabajo realizado hasta
ese momento. Este puede parecer un precio pequeño comparado con
dejar que el interbloqueo se complique por  varios factores.

 En primer lugar, puede no estar claro que el sistema este

bloqueado o no.
 Muchos sistemas tienen medios pobres para suspender un proceso
por tiempo   indefinido y reanudarlo más tarde.
 Aún cuando existan medios efectivos de suspensión /reanudación,
con toda seguridad, estos   implicarán una sobrecarga,
considerable y pueden requerir la atención de
un  operador  altamente calificado. No siempre se dispone de tales
operadores.
 Recuperarse de un interbloqueo de proporciones modestas puede
suponer una cantidad razonable de trabajo.

Una  forma  de  elegir los procesos que pueden ser retirados es de

acuerdo a las prioridades de los procesos. Pero esto también tiene sus
dificultades.

  Las prioridades de los procesos bloqueados pueden no existir, así

que el operador deberá tomar una decisión arbitraria.
 Las prioridades pueden ser incorrectas, o un poco confusas debido
a consideraciones especiales.
 La decisión óptima de cuáles procesos retirar pueden requerir de
un esfuerzo considerable para determinarla.

            El enfoque más deseable a la recuperación del Dead Lock están

un mecanismo efectivo de
Suspensión / reanudación. Esto permitirá detener temporalmente los
procesos y después reanudarlos sin pérdida del trabajo.

MECANISMOS PARA EVITARLOS.

49
            Havender llegó a la conclusión de que si no se cumple una de
las cuatro condiciones necesarias para el interbloqueo es posible que
éste ocurra.

            Para evitarlo sugirió:

 Cada proceso deberá pedir todos los recursos requeridos de una

sola vez y no podrá proceder hasta que le hayan sido asignados
todos.
 Si un proceso que mantiene ciertos recursos se le niega una nueva
petición, este proceso deberá liberar sus recursos originales y en
caso necesario pedirlos de nuevo con los recursos adicionales.
 Se impondrá la ordenación lineal de los tipos de recursos en todos
los procesos, es decir, si a un proceso le han sido asignados
recursos de un tipo dado, en lo sucesivo sólo podrá pedir aquellos
recursos de los tipos que siguen en el ordenamiento.

Otra alternativa, para manejar los dead lock, es tener información

acerca de como los recursos se van a requerir, el modelo más simple y
más útil requiere que en cada proceso declare el máximo número de
recursos que van a requerir con lo cual es posible construir un algoritmo
que asegure que el sistema no entrara en dead lock.

 Un estado es  seguro si el sistema puede asignar recursos a cada

proceso en algún orden evitando el dead lock.
  Formalmente un sistema esta en estado seguro solamente si existe una
secuencia segura. Una secuencia de procesos < P1, P2, ... Pn> esta en
secuencia segura si para cada  Pi,  los recursos que Pi pueda requerir
pueden ser satisfechos por los recursos disponibles más los recursos que
tuvieron los Pj  donde  j < i.  Si no se puede satisfacer Pi entonces Pi
espera hasta que los Pj terminen.

            Cuando Pi termine  Pi+1 puede obtener sus recursos y así

sucesivamente.
 Se tienen 12 unidades de cinta  se tiene 3 procesos ¿Ese sistema
esta  en estado seguro o no?.

50
   Requerimiento procesos - recursos.

Requerimiento máximo - Necesidad actual = Necesidad

más  (Disponible).
           
Se tiene 12 recursos por lo tanto 12-9 = 3, entonces la secuencia es
segura.
            La secuencia segura es  < P1,P0,P2>           
Haga una situación en la cual el sistema estaría es estado inseguro.

Un estado seguro esta libre de dead lock y un estado de dead lock, es

un estado inseguro pero no todos los estados inseguros producen dead
lock.
            Si se esta en un estado seguro se puede pasar a un estado
inseguro.

Estrategias para evitarlos

            Evitación del interbloqueo y el algoritmo de Dijkstra. Si las

condiciones necesarias para que tenga lugar un interbloqueo están en su
lugar, aún es posible evitar el interbloqueo teniendo cuidado al asignar
los recursos.
            El algoritmo de planificación que pueda evitar los interbloqueos
fue ideado por Dijkstra (1965) y se le conoce como algoritmo del
banquero. En ese algoritmo se modela la forma en que un banquero
puede tratar a un grupo de clientes a quienes les ha otorgado líneas de
crédito. en la (figura # 36 (a)) se observan cuatro clientes, a cada uno
de los cuales se le ha otorgado cierto número de unidades de crédito. El
banquero sabe que los clientes no necesitan su límite de crédito máximo
de inmediato, de manera que sólo ha reservado 10 unidades en lugar de
22 para darles servicio.
            Los clientes emprenden sus respectivos negocios, haciendo
solicitudes de préstamo de cuando en cuando.  En cierto momento). A
una lista de clientes que muestra el dinero que ya se presentó y el
máximo del crédito disponible se le llama estado del sistema.

 Tres estados de asignación de recursos

51
(a)   Seguro.   (b) Seguro.   (c) Inseguro.
Un estado es seguro si existe una secuencia de estados que lleva a
todos los clientes que obtienen préstamos hasta sus límites de
crédito. es seguro por que con las dos restantes, el banquero puede
demorar  cualquier solicitud salvo la de Carlos, con lo que permite que
termine y devuelva sus cuatro recursos. Con cuatro unidades, el
banquero puede permitir que David o Bárbara tengan las unidades que
necesitan para terminar y así sucesivamente.

            Si  estando  en  el estado de la se le otorga una unidad más a

Bárbara,  
 el banquero  no podrá completar ninguna de la línea de crédito de su
clientes. Un estado inseguro no tiene que conducir a un interbloqueo, ya
que un cliente podría  no necesitar su línea de crédito disponible, pero el
banquero no puede confiar en ese comportamiento.

            Haciendo una analogía con un Sistema Operativo tenemos: El

estado actual del sistema se denomina seguro, Si el Sistema Operativo
puede permitir a los usuarios actuales completar sus trabajos en un
intervalo de tiempo finito. De lo contrario se le denomina inseguro. En
otras palabras: Un estado seguro es aquel en el cual la asignación de
recursos es tal que los usuarios pueden llegar a terminar. Un estado
seguro es aquel que puede llegar a terminar. Un estado inseguro es
aquel que puede llegar a un dead lock, (nunca termina).

La asignación de recursos por el algoritmo del banquero es la siguiente:

 Se permite todas las condiciones de exclusión mutua, espera por y

no apropiatividad.
 Se permite a los procesos mantener sus recursos mientras esperan
por otros.
 El sistema sólo concede peticiones que den como resultado estados
seguros.

El algoritmo del banquero para  n  recursos (de Dijkstra).

52
            Sea  n  un número de proceso y  m  un número de recurso y sea
disponible un vector de longitud m  que indica el número de recursos
disponibles y sea máxima una matriz de ( n x  m) que define  la máxima
demanda de cada proceso así por ejemplo si tuviéramos máxima ( i,j ) =
k define los  recursos asignados a cada proceso, por ejemplo la
asignación ( i , j ) = k quiere decir que el proceso i tiene asignado K
instancias del recurso j  necesidades ( n * m ), que indica los recursos
que requieren los procesos. Necesidades ( i , j ) = Máxima  ( i , j ) -
Asignación ( i , j ).
            Se puede considera cada renglón de las matrices asignación y
necesidades como vectores y referirnos como asignación de i y
necesidades de i.

Algoritmo:

            Sea requerimiento de i un vector de requerimientos de proceso

i.
           
            Cuando un requerimiento de un recurso es hecho por el proceso
i se realizaran las siguientes acciones:

1).- Si Requerimiento de i <= Necesidades de i  ir al segundo

paso. Sino error.
2).- Si requerimiento de  i <=  disponible  ir al tercer paso. Si no
recurso no disponible Pi  debe esperar.
3).-
 Hacer Disponible = Disponible - Requerimiento,
            Asignación = Asignación  +  Requerimiento,
            Necesidades = Necesidades - Requerimiento.

            Si el estado es seguro se completa la transacción de lo contrario

el proceso debe esperar y el estado anterior es restablecido.

            Algoritmo para ver si el estado es seguro.

53
            Sea trabajo (m)  y final (n) vectores de
longitud  m  y  n  respectivamente, hacer                   Trabajo
=  Disponible y final ( i ) =  falso  para i = 1,...n

1).-      Encuentre una  i  tal que final  ( i )  de i =

falso y Necesidades ( i ) <= Trabajo  si no existe ir al punto tres.
2).-      Trabajo   =   Trabajo   +   Asignación ( i ), Final ( i ) =
verdad  ir al paso uno.
3).-      Si  final ( i)   =   verdad  para toda  i  entonces el sistema
esta en estado seguro de lo contrario esta en estado inseguro.

 Secuenciabilidad
Los archivos secuenciales son un tipo de archivo en los que la información puede leerse y
escribirse empezando desde el principio del archivo.
Debemos tomar en consideración algunas características que deben tener los archivos
secuenciales:

1. La escritura de nuevos datos siempre se hace al final del archivo.

2. Para leer una zona concreta del archivo hay que avanzar siempre, si la zona está antes de
la zona actual de lectura, será necesario "rebobinar" el archivo. 

3. Los ficheros sólo se pueden abrir para lectura o para escritura, nunca de los dos modos a
la vez.

Archivos Secuenciales

 
Se refiere al procesamiento de los registros, no importa el orden en que se haga,
para eso los registros están organizados en forma de una lista y recuperarlos y
procesarlos uno por uno de principio a fin.

Rendimientos de los archivos Secuenciales; dependiendo del dispositivo de

almacenamiento utilizado el archivo se puede mostrar el usuario como si fuera un
sistema secuencial.

54
Al finalizar un archivo secuencial se denota con una marca de fin de archivo. (End
end-of-file) 

Seriabilidad: Cuando hablamos de seriabilidad nos referimos a la capacidad de

reproducir un producto x en número limitado de veces.

TEORÍA DE SERIABILIDAD

Una forma de evitar los problemas de interferencia es no permitir que las transacciones se
intercalen. Una ejecución en la cual ninguna de dos transacciones se intercala se conoce
como serial. Para ser más precisos, una ejecución se dice que es serial si, para todo par de
transacciones, todas las operaciones de una transacción se ejecutan antes de cualquier
operación de la otra transacción. Desde el punto de vista del usuario, en una ejecución serial
se ve como si las transacciones fueran operaciones que el DBS procesa atómicamente. Las
transacciones seriales son correctas dado que cada transacción es correcta individualmente,
y las transacciones que se ejecutan serialmente no pueden interferir con otra.

Si el DBS procesara transacciones serialmente, significaría que no podría ejecutar

transacciones concurrentemente, si entendemos concurrencia como ejecuciones
intercaladas. Sin dicha concurrencia, el sistema usaría sus recursos en un nivel relativamente
pobre y podría ser sumamente ineficiente.

Una solución puede ser ampliar el rango de ejecuciones permisibles para incluir aquellas que
tienen los mismos efectos que las seriales. Dichas ejecuciones se conocen
como serializables. Entonces, una ejecución es serializable si produce el mismo resultado y
tiene el mismo efecto sobre la base de datos que alguna ejecución serial de las mismas
transacciones. Puesto que las transacciones seriales son correctas, y dado que cada
ejecución serializable tiene el mismo efecto que una ejecución serial, las ejecuciones
serializables también son correctas.

Las ejecuciones que ilustran la actualización perdida y el análisis inconsistente no son

serializables. Por ejemplo, ejecutando las dos transacciones de Depositar serialmente, en
cualquier orden, da un resultado diferente al de la ejecución intercalada que pierde una
actualización, por lo tanto, la ejecución intercalada no es serializable. Similarmente, la
ejecución intercalada de Transferir e Imprimir Suma tiene un efecto diferente a los de cada
ejecución serial de las dos transacciones, y por ello no es serializable.

Aunque éstas dos ejecuciones intercaladas no son serializables, muchas otras sí lo son. Por
ejemplo, consideremos la siguiente ejecución intercalada de Transferir e Imprimir Suma. Esta
ejecución tiene el mismo efecto que la ejecución serial de Transferir seguida de Imprimir
Suma por lo tanto es serializable.

55
Leer4 (Cuentas [8])    devuelve el valor de US$200
Escribir4 (Cuentas [8], US$100) 
Leer3 (Cuentas [8])    devuelve el valor de US$100
Leer4 (Cuentas [9])    devuelve el valor de US$200$
Escribir4 (Cuentas [9], US$300) 
Commit4 
Leer3 (Cuentas [9])    devuelve el valor de US$300 
Commit3

La teoría de seriabilidad es una herramienta matemática que permite probar si un

sincronizador trabaja o no correctamente. Desde el punto de vista de la teoría de seriabilidad,
una transacción es una representación de una ejecución de operaciones de lectura y
escritura y que indica el orden en el que se deben ejecutar estas operaciones. Además, la
transacción contiene un Commit o un Abort como la última operación para indicar si la
ejecución que representa terminó con éxito o no. Por ejemplo, la ejecución del siguiente
programa.

Procedure P

begin

Start; 
temp := Leer(x); 
temp := temp + 1; 
Escribir(x, temp); 
Commit;

end

Puede ser presentado como r1[x] -› w1[x] -› c1. Los subíndices identifican esta transacción
particular y la distinguen de cualquier otra transacción que acceda al mismo dato. En general,
usaremos r1[x] (o w1[x] para denotar la ejecución de Leer (o Escribir) ejecutado por la
transacción T1 sobre el dato x.

Cuando se ejecuta concurrentemente un conjunto de transacciones, sus operaciones deben

estar intercaladas. La manera de modelar esto es usando una estructura llamada historia.
Una historia indica el orden en el que se deben ejecutar las operaciones de las transacciones
en relación a otras. Si una transacción Tiespecifica el orden de dos de sus operaciones,
estas dos operaciones deben aparecer en ese mismo orden en cualquier historia que incluya
a Ti. Además, es necesario que una historia especifique el orden de todas las operaciones
conflictivas que aparezcan en ella.

56
 
Se dice que dos operaciones están en conflicto si ambas operan sobre el mismo dato y al
menos una de ellas es una operación de escritura (Escribir). Por lo tanto, Leer(x) está en
conflicto con Escribir(x), mientras que Escribir(x) está en conflicto tanto con Leer(x) como
con Escribir(x). Si dos operaciones están en conflicto, es muy importante su orden de
ejecución. Consideremos las siguientes transacciones

T1 = r1[x] -› w1[x] -› c1 

T3 = r3[x] -› w3[y] -› w3[x] -› c3 
T4 = r4[y] -› w4[x] -› w4[y] -› w4[z] -› c4

Una historia completa sobre T1, T3, T4 es

H1 = r4[y] r1[x] w1[x] c1 w4[x] r3[x] w4[y] w3[y] w4[z] w3[x] c4 c3

2.5. NIVELES, OBJETIVOS Y CRITERIOS DE PLANIFICACIÓN

Niveles 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

57
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.

58
 Se
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.

59
  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

60
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.
61
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.

62
  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

63
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.

64
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.

2.6. TÉCNICAS DE ADMINISTRACIÓN DEL PLANIFICADO R

65
En los siguientes subapartados vamos a estudiar ciertos algoritmos utilizados
para planificar la CPU, la elección de uno (o de una mezcla de varios) depende de
decisiones de diseño. Antes de exponer los algoritmos vamos a explicar ciertas
medidas que se utilizan para evaluarlos.

 Porcentaje de utilización de la CPU por procesos de usuario.

La CPU es un recurso caro que necesita ser explotado, los valores reales
suelen estar entre un 40% y un 90%.

 Rendimiento (throughput) = nº de ráfagas por unidad de tiempo. Se

define una ráfaga como el período de tiempo en que un proceso necesita la
CPU; un proceso, durante su vida, alterna ráfagas con bloqueos. Por
extensión, también se define como el nº de trabajos por unidad de tiempo.

  Tiempo de espera (E) = tiempo que una ráfaga ha permanecido

en estado listo.

 Tiempo de finalización (F) = tiempo transcurrido desde que una ráfaga

comienza a existir hasta que finaliza. F = E + t (t = tiempo de CPU de la
ráfaga).

 Penalización (P) = E + t / t = F / t, es una medida adimensional que se

puede aplicar homogéneamente a las ráfagas independientemente de su
longitud.

En general, hay que maximizar los dos primeros parámetros y minimizar los tres
últimos. Sin embargo, estos objetivos son contradictorios, el dedicar más tiempo
de CPU a los usuarios se hace a costa de llamar menos al algoritmo de
planificación (menos cambios de proceso), y de simplificarlo. Esto provoca que la
CPU se reparta menos equitativamente entre los procesos, en detrimento de los
últimos tres parámetros.

Así pues, dependiendo de los objetivos se elegirá cierto algoritmo. En los

sistemas por lotes suele primar el rendimiento del sistema, mientras que en los
sistemas interactivos es preferible minimizar, por ejemplo, el tiempo de espera.

TÉCNICAS O ALGORITMOS DE PLANIFICACIÓN

66
Planificación a  plazo fijo.

            En la planificación a plazo fijo, ciertos trabajos se planifican para ser

terminados en un periodo específico. Estos trabajos tienen un alto valor si se
entregan a tiempo y pueden carecer  de valor si se entregan después del límite.
La planificación a plazo fijo es compleja por muchas razones:

 Los usuarios deben proporcionar por adelantado y en forma precisa las

necesidades    de  recursos de su trabajo. Tal información rara vez está
disponible.
 El sistema debe ejecutar el programa de plazo fijo sin una severa
degradación de servicio  para los otros usuarios.
 El sistema debe planificar cuidadosamente las necesidades de recursos
permitiendo un libre tránsito del plazo fijo. Esto puede ser difícil debido a la
llegada de programas nuevos con demandas impredecibles.
 Si se activan muchos trabajos de plazo fijo, la planificación puede llegar a
ser tan compleja que necesite métodos de optimización sofisticados para
asegurar que el plazo fijo se cumpla.
 El manejo intenso de recursos requeridos por la planificación de plazo fijo
puede generar una sobrecarga sustancial.

Planificación  Primero   en  llegar - Primero  en  Salir (FIFO).

       Los procedimientos son despachados de acuerdo al orden de llegada a la cola

de listos. Una vez que un proceso tiene el CPU, se ejecuta hasta su terminación.
Esta planificación es No apropiativa; es justa en el sentido formal, pero algo
injusta porque los grandes procesos hacen esperar a trabajos pequeños y,  los
trabajos sin importancia hacen esperar a los trabajos importantes.

La Planificación FIFO ofrece una varianza en tiempo de respuesta

relativamente pequeña y es, por tanto, más predecible que otros esquemas; no
es un esquema útil en la planificación de procesos interactivos porque no
garantiza buenos tiempos de respuesta.También se puede implementar mediante
la utilización de una lista. Se reemplazan las páginas de la cabeza y se agregan al
final.

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. 
67
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”.
 
ENLACE A SIMULACIÓN FIFO

Planificación por Prioridad al más corto (SJF, Short Job First).

            La disciplina del trabajo más corto primero es NO apropiativa y en ella el

trabajo o proceso con tiempo estimado de ejecución hasta terminación más corto,
es el siguiente en ser ejecutado. El SJF reduce el tiempo de espera de los
procesos, sin embargo, tiene una varianza mayor (es decir, es menos predecible)
que en FIFO, sobre todo para los trabajos largos.

 SJF favorece a los procesos cortos a costa de los procesos largos. Además,
selecciona los trabajos que serán atendidos y que dejarán el sistema lo antes
posible. Esto último traduce en listas de espera cortas. El SJF es NO apropiativo
por lo que resulta de poca utilidad en ambientes de tiempo compartido.

 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. 

ENLACE A SIMULACIÓN SJF 

Planificación por Prioridad al Tiempo Restante más Corto (SRTF, Short

Remaining Time First).

68
En la figura 6.5 tenemos un ejemplo de funcionamiento del algoritmo en el que se
observa cómo se penalizan las ráfagas largas (como en SJF). Un punto débil de
este algoritmo se evidencia cuando una ráfaga muy corta suspende a otra un
poco más larga, siendo más largo la ejecución en este orden al ser preciso un
cambio adicional de proceso y la ejecución del código del planificador.

Es la contraparte apropiativa del SJF. 

Es útil en sistemas de tiempo compartido. 
El proceso con el tiempo estimado de ejecución menor para …nalizar es el
siguiente en ser ejecutado. 

Un proceso en ejecución puede ser apropiado por un nuevo proceso con un

tiempo estimado de ejecución menor. 
Tiene mayor sobrecarga que la planificación SJF. 
Debe mantener un registro del tiempo de servicio transcurrido del proceso en
ejecución, lo que aumenta la sobrecarga. 

Los trabajos largos tienen un promedio y una varianza de los tiempos de espera
aún mayor que en SJF. 
La apropiación de un proceso a punto de terminar por otro de menor duración
recién llegado podría significar un mayor tiempo de cambio de contexto
(administración del procesador) que el tiempo de finalización del primero. 
Al diseñarse los Sistemas Operativos se debe considerar cuidadosamente la

69
sobrecarga de los mecanismos de administración de recursos comparándola con
los beneficios esperados. 

Planificación el Siguiente con Relación de Respuesta Máxima (HRN)

Corrige algunas de las debilidades del SJF, tales como el exceso de perjuicio hacia
los procesos (trabajos) largos y el exceso de favoritismo hacia los nuevos
trabajos cortos. 
Es una disciplina no apropiativa. 
La prioridad de cada proceso está en función no sólo del tiempo de servicio del
trabajo, sino que también influye la cantidad de tiempo que el trabajo ha estado
esperando ser servido. 
Cuando un proceso ha obtenido la cpu, corre hasta terminar. 
Las prioridades, que son dinámicas, se calculan según la siguiente fórmula,
donde pr  es la “prioridad”, te es el “tiempo de espera” y ts es el “tiempo de
servicio”: 

 Planificación del tiempo restante más corto primero (SRT).

            La SRT es apropiativa, en ella el proceso con el tiempo estimado de

ejecución menor para llegar a su terminación es el siguiente en ser ejecutado,
incluyendo las nuevas llegadas. En la disciplina SJF, una vez que el trabajo
comienza su ejecución sigue hasta que termina. En SRT, un proceso en ejecución
puede ser apropiado por un nuevo proceso con n tiempo estimado de ejecución
menor.

            La SRT tiene una sobrecarga mayor que la SJF. Debe mantener un
registro del tiempo de servicio transcurrido del trabajo en ejecución y debe
controlar las apropiaciones ocasionales.

Planificación  el  siguiente con relación  de respuesta  máxima (HRT).

            Brinch Hansen (1971) desarrolló la estrategia el siguiente con relación

de respuesta máxima (HRT), que corrige algunas de las debilidades de SJF, en
especial el favoritismo por los tamaños pequeños. La HRT es una disciplina de
planificación NO apropiativa en la cual la prioridad de cada trabajo está en
función, no sólo del tiempo de servicio del trabajo, sino del tiempo que un
proceso ha estado esperando a ser servido, Una vez que un trabajo obtiene el
70
CPU,  se ejecuta hasta su terminación. Las prioridades dinámicas en HRT se
calculan según la fórmula

Planificación Round Robin (RR)

             Los procesos son despachados en FIFO, pero, se les otorga una cantidad
limitada de tiempo de CPU llamada división de tiempo (time - slice) o cuanto
(quantum). Si un proceso no termina antes de que se termine su tiempo de CPU,
el CPU es apropiado y asignado al siguiente proceso en espera. El proceso
apropiado se coloca al final de la lista de listos.

 Planeación round robin.

            El  esquema Round    robin es efectivo en un ambiente de tiempo

compartido en el cual el sistema necesita garantizar un tiempo de respuesta
razonable para los usuarios interactivos. La sobre carga  de la apropiación se
mantiene baja mediante eficientes mecanismos de cambio de contexto y
proporcionado suficiente memoria para que los procesos residan en ella al mismo
tiempo.

            Existe una variante de este esquema llamada selfish round robin

(SRR). En este esquema los procesos que entran al sistema se colocan primero
en una lista de espera hasta que su prioridad alcanza el nivel de proceso para la
lista de activos. Mientras un proceso está en la lista de espera, su prioridad
aumenta en una relación  a; cuando un proceso entra a la lista de activos su
prioridad se incrementa en una relación  b.
Tamaño del cuanto.

                        La determinación del tamaño del cuanto es decisiva para la operación

efectiva  de un sistema computacional. ¿Debe ser pequeño o grande el cuanto?
¿Debe ser fijo o variable? ¿Debe ser el mismo para todos los usuarios, o debe ser
diferente para cada grupo de usuarios?.

            Cuando se tiene un cuanto grande cada proceso pude recibir todo el

tiempo que necesita para su terminación, de manera que el esquema round robin
se convierte en un FIFO. Cuando el cuanto es  pequeño, la sobrecarga por el
intercambio de contexto se convierte en un factor dominante y el rendimiento del
sistema se degrada.

71
            ¿Cuál es el cuanto óptimo ? Es claro que cambia de un sistema a otro y
que varia de acuerdo a la carga del sistema.

ENLACE A LA SIMULACIÓN DE COLAS RR

Tamaño del Cuanto o Quantum

La determinación del tamaño del cuanto es decisiva para la operación efectiva de

un sistema computacional 
Los interrogantes son: ¿cuanto pequeño o grande?, ¿cuanto fijo o variable? y
¿cuanto igual para todos los procesos de usuarios o determinado por separado
para cada uno de ellos?. 
Si el cuanto se hace muy grande, cada proceso recibe todo el tiempo necesario
para llegar a su terminación, por lo cual la asignación en rueda (“RR”) degenera
en “FIFO”. 

Si el cuanto se hace muy pequeño, la sobrecarga del intercambio de contexto se

convierte en un factor dominante y el rendimiento del sistema se degrada, puesto
que la mayor parte del tiempo de cpu se invierte en el intercambio del procesador
(cambio de contexto) y los procesos de usuario disponen de muy poco tiempo de
cpu. 

El cuanto debe ser lo suficientemente grande como para permitir que la gran
mayoría de las peticiones interactivas requieran de menos tiempo que la duración
del cuanto, es decir que el tiempo transcurrido desde el otorgamiento de la cpu a
un proceso hasta que genera una petición de Entrada / Salida debe ser menor
que el cuanto establecido, de esta forma, ocurrida la petición la cpu pasa a otro
proceso y como el cuanto es mayor que el tiempo transcurrido hasta la petición
de Entrada / Salida, los procesos trabajan al máximo de velocidad, se minimiza la
sobrecarga de apropiación y se maximiza la utilización de la 
Entrada / Salida. 
El cuanto óptimo varía de un sistema a otro y con la carga, siendo un valor de
referencia 100 mseg (cien milisegundos)
 

Queves multi-level

Planificación de Dos Niveles 

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

72
Habrá procesos ejecutables que se mantengan en disco. 
 Habrá importantes implicaciones para la planificación, tales como las
siguientes:
o 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.
o 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: 

1. Se carga en la memoria principal cierto subconjunto de los procesos
ejecutables.
2. El planificador se restringe a ellos durante cierto tiempo.
3. Periódicamente se llama a un planificador de nivel superior para efectuar
las siguientes tareas:
1. Eliminar de la memoria los procesos que hayan permanecido en ella el
tiempo suficiente.
2. Cargar a memoria los procesos que hayan estado en disco demasiado
tiempo.
4. El planificador de nivel inferior se restringe de nuevo a los procesos
ejecutables que se encuentren en la memoria.
5. El planificador de nivel superior se encarga de desplazar los procesos de
memoria a disco y viceversa.
Los criterios que podría utilizar el planificador de nivel superior para tomar sus
decisiones son los que se indican a continuación:
 ¿Cuánto tiempo ha transcurrido desde el último intercambio del proceso?.
 ¿Cuánto tiempo de cpu ha utilizado recientemente el proceso?.
 ¿Qué tan grande es el proceso? (generalmente los procesos pequeños no
causan tantos problemas en este sentido).
 ¿Qué tan alta es la prioridad del proceso?.
El planificador de nivel superior podría utilizar cualquiera de los métodos de
planificación analizados.

Multi-level feedback queves.

Colas de Retroalimentación de Niveles Múltiples 

Cuando un proceso obtiene la CPU, sobre todo cuando todavía no ha tenido

oportunidad de establecer un patrón de comportamiento, el planificador no
tiene idea de la cantidad de tiempo de CPU que necesitará el proceso. Los
procesos limitados por la E/S normalmente usan la CPU sólo un momento
antes de generar una solicitud de E/S; los procesos limitados por la CPU
pueden usar el procesador durante horas si está disponible en forma no
apropiativa.

73
 Un mecanismo de planificación debe:

  Favorecer a los trabajos cortos.

  Favorecer a los trabajos limitados por la E/S para lograr un mejor

aprovechamiento de los dispositivos de E/S.

 Determinar la naturaleza de un trabajo lo más pronto posible y planificarlo

de acuerdo con su naturaleza.  

Las colas de retroalimentación de niveles múltiples (figura 6.6) ofrecen una

estructura que cumple con estos objetivos. Un proceso nuevo entra en la red de
colas al final de la primera cola. Se desplaza en esa cola mediante Round Robin
hasta que obtiene la CPU. Si el trabajo termina o cede la CPU para esperar la
terminación de una operación de E/S o de algún evento, el trabajo abandona la
red de colas. Si el cuanto expira antes de que el proceso ceda voluntariamente la
CPU, el proceso se colocará al final de la cola del siguiente nivel. El proceso será
atendido otra vez cuando llegue a la cabeza de esa cola si está vacía la primera.
Mientras el proceso utilice todo el cuanto proporcionado en cada nivel, continuará

74
desplazándose al final de la siguiente cola inferior. Por lo general, existe una cola
en el nivel más bajo en la cual el proceso circula por turno rotatorio hasta que
termina.

En muchos esquemas de retroalimentación de múltiples niveles, el cuanto

asignado a un proceso cuando pasa a una cola de nivel inferior alcanza un valor
mayor. De esta forma, cuanto más tiempo se encuentre un proceso en la red de
colas más grande será el cuanto asignado cada vez que obtenga la CPU, pero tal
vez no obtenga la CPU muy a menudo, porque los procesos de las colas de nivel
superior tienen mayor prioridad. Un proceso situado en una cola no puede
ejecutarse a menos que estén vacías las colas de nivel superior. Un proceso en
ejecución será desposeído por un proceso que llegue a una cola superior.

Considérese ahora cómo responde un mecanismo de este tipo a diferentes tipos

de procesos. El mecanismo debe favorecer a los procesos limitados por la E/S
para lograr un buen aprovechamiento de los dispositivos y una respuesta buena
para los usuarios interactivos; y de hecho lo hace porque los procesos limitados
por la E/S entrarán en la red con prioridad alta y se les asignará rápidamente la
CPU. El tamaño del cuanto de la primera cola se elegirá lo suficientemente grande
para que la gran mayoría de los trabajos limitados por la E/S generen una
petición de E/S antes de que expire el primer cuanto. Cuando el proceso solicita
E/S, abandona la red y ha obtenido un tratamiento favorable, tal como se
deseaba.

Ahora considérese una tarea limitada por la CPU que necesita mucho tiempo de
procesador. Esa tarea entra en la cola más alta de la red con prioridad alta.
Recibe rápidamente su primera asignación de la CPU, pero su cuanto expira y el
proceso se coloca en la cola del siguiente nivel inferior. En ese momento, el
proceso tiene una prioridad menor que la de los procesos que llegan al sistema,
en particular los trabajos limitados por la E/S, que obtienen primero la CPU. El
proceso limitado por la CPU acaba recibiendo ésta, obtiene un cuanto mayor que
en la cola más alta y vuelve a utilizar la totalidad de su cuanto. Luego es situado
al final de la siguiente cola inferior. El proceso sigue desplazándose a colas
inferiores, espera más entre divisiones de tiempo y utiliza todo su cuanto cada
vez que obtiene la CPU ( a menos que sea arrebatada por un proceso entrante).
En algún momento, el proceso limitado por la CPU llega a la cola de nivel inferior,
en donde entrará en una planificación por turno hasta terminar.

Las colas de retroalimentación de niveles múltiples son ideales para separar

procesos en categorías basadas en su necesidad de la CPU. En un sistema de
tiempo compartido, cada vez que un proceso abandona la red de colas puede
"marcarse" con la identidad de la última cola en donde estuvo, y cuando el
proceso entra de nuevo en la red de colas, puede enviarse directamente a la cola
en la cual terminó su operación por última vez. En este caso, el planificador está
usando un razonamiento heurístico, según el cual el comportamiento anterior del
proceso es un buen indicador de su comportamiento en un futuro inmediato. De
75
esta forma, un proceso limitado por la CPU que regresa a la red de colas no se
coloca en las colas de nivel alto donde interferiría con el servicio a los procesos
cortos de prioridad alta o con los limitados por la E/S.

Si los procesos se colocan siempre dentro de la red en la cola que ocuparon la

última vez, será imposible que el sistema responda a cambios de un proceso, por
ejemplo, de estar limitado por la CPU, a estar limitado por la E/S. El problema
puede resolverse marcando al proceso también con su duración dentro de la red
la última vez que estuvo en ella. Así, cuando el proceso entra de nuevo en la red
puede colocarse en la cola correcta. Entonces, si el proceso entra en una fase
nueva en la cual deja de estar limitado por la CPU y empieza a estar limitado por
la E/S, el proceso experimentará en principio un tratamiento lento mientras el
sistema determina que la naturaleza del proceso está cambiando. Pero el
mecanismo de planificación responderá con rapidez a este cambio. Otra forma de
hacer que el sistema responda a los cambios de comportamiento de los procesos
es permitir que un proceso ascienda un nivel en la red de colas cada vez que
abandona voluntariamente la CPU antes de que expire su cuanto.

El mecanismo de colas de retroalimentación de niveles múltiples es un buen

ejemplo de mecanismo adaptativo, que responde a los cambios en el
comportamiento del sistema que controla. Los mecanismos adaptativos implican,
en general, una carga extra mayor que los no adaptativos, pero la sensibilidad
ante los cambios en el sistema da como resultado una mejor capacidad de
respuesta, y justifica el aumento en el gasto extra.

  Una variante común del mecanismo de colas de retroalimentación de múltiples

niveles consiste en hacer que un proceso circule por turno varias veces en cada
cola antes de pasar a la siguiente cola inferior. El número de ciclos en cada cola
crece por lo regular cuando el proceso pasa a la siguiente cola inferior.

  ENLACE A LA SIMULACIÓN COLAS MULTINIVEL

Planificación a la Tasa  de Respuesta mas Alta

Brinch Hansen desarrolló la estrategia de prioridad a la tasa de respueta más alta

(HRN, highest-response-ratio-next) que corrige algunas deficiencias de SJF,
particularmente el retraso excesivo de trabajos largos y el favoritismo excesivo
para los trabajos cortos. HRN es un disciplina de planificación no apropiativa en la
cual la prioridad de cada proceso no sólo se calcula en función del tiempo de
servicio, sino también del tiempo que ha esperado para ser atendido. Cuando un
trabajo obtiene el procesador, se ejecuta hasta terminar. Las priori

dades dinámicas en HRN se calculan de acuerdo con la siguiente

expresión:

 
76
  prioridad = (tiempo de espera + tiempo de servicio) / tiempo de servicio

Como el tiempo de servicio aparece en el denominador, los procesos cortos

tendrán preferencia. Pero como el tiempo de espera aparece en el numerador, los
procesos largos que han esperado también tendrán un trato favorable. Obsérvese
que la suma tiempo de espera + tiempo de servicio es el tiempo de respuesta del
sistema para el proceso si éste se inicia de inmediato.

Planificación por el Comportamiento

Con este tipo de planificación se pretende garantizar al usuario cierta prestación

del sistema y tratar de cumplirla. Si en un sistema tenemos 'n' usuarios lo normal
será garantizar a cada uno de ellos al menos 1/n de la potencia del procesador.
Para ello necesitamos del tiempo consumido por el procesador y el tiempo que
lleva el proceso en el sistema. La cantidad de procesador que tiene derecho a
consumir el proceso será el cociente entre el tiempo que lleva en el sistema entre
el número de procesos que hay en el sistema. A esa cantidad se le puede asociar
una prioridad que vendrá dada como el cociente entre tiempo de procesador que
ha consumido y el tiempo que se le prometió (el tiempo que tiene derecho a
consumir). De tal modo que si esa proporción es de 0'5 significa que tan sólo ha
consumido la mitad del tiempo prometido pero si es de 2 quiere decir que ha
consumido más de lo debido, justamente el doble.

77