Download - ASESORÍA DIDÁCTICA 1
SISTEMAS OPERATIVOS I
SISTEMAS OPERATIVOS I
ASESORIA DIDACTICA 1
Contenido
FUNDAMENTOS DE SISTEMAS OPERATIVOS ............................................................. 3
INTRODUCCION .................................................................................................. 3
SOFTWARE DEL SISTEMA OPERATIVO ................................................................... 4
HARDWARE DE LA MAQUINA ................................................................................ 7
TIPOS DE SISTEMAS OPERATIVOS ........................................................................ 9
HISTORIA BREVE DEL DESARROLLO DE LOS SISTEMAS OPERATIVOS ..................... 10
ADMINISTRADOR DEL PROCESADOR ..................................................................... 16
PLANIFICACIÓN DE TRABAJOS EN COMPARACIÓN CON PLANIFICACIÓN DE PROCESOS ...................................................................................................................... 17
PLANIFICADOR DE PROCESOS ............................................................................ 18
ESTADO DE LOS TRABAJOS Y DE LOS PROCESOS ................................................. 19
Bloques de control de procesos ........................................................................ 21
Bloques de control de procesos y colas ............................................................. 22
POLITICAS DE PLANIFICACION DE PROCESOS ..................................................... 23
ALGORITMOS DE PLANIFICACION DE PROCESOS .................................................. 24
PRIMERO DE ENTRAR, PRIMERO DE SERVIRSE .................................................. 24
SIGUE EL TRABAJO MÁS CORTO ...................................................................... 25
PLANIFICACIÓN CON PRIORIDAD ..................................................................... 26
TIEMPO RESTANTE MÁS BREVE ....................................................................... 27
ROUND ROBIN ............................................................................................... 29
COLAS DE MULTIPLES NIVELES ....................................................................... 31
MEMORIA CACHE ........................................................................................... 33
UNA PALABRA SOBRE INTERRUPCIONES ........................................................... 33
ADMINISTRACIÓN DE LOS PROCESOS ................................................................. 36
BLOQUEO MUTUO ............................................................................................. 37
Siete casos de bloqueo mutuo ......................................................................... 37
CONDICIONES PARA EL BLOQUEO MUTUO ........................................................ 43
SISTEMAS OPERATIVOS I
MODELADO DE BLOQUEOS MUTUOS ................................................................ 44
Estrategias para el manejo de bloqueos ............................................................ 47
INANICIÓN ...................................................................................................... 53
PROCESOS CONCURRENTES ................................................................................. 56
¿QUÉ ES PROCESAMIENTO PARALELO? ................................................................ 56
CONFIGURACIONES TÍPICAS DE MULTIPROCESAMIENTO ...................................... 57
Configuración maestro/esclavo ........................................................................ 57
Configuración débilmente acoplada .................................................................. 58
Configuración simétrica .................................................................................. 59
SOFTWARE DE SINCRONIZACIÓN DE PROCESOS .................................................. 59
PROBAR Y ESTABLECER .................................................................................. 61
WAIT y SIGNAL ............................................................................................. 61
Semáforos .................................................................................................... 61
COOPERACIÓN DE PROCESOS ............................................................................ 63
Productores y consumidores ............................................................................ 64
Lectores y escritores ...................................................................................... 65
PROGRAMACIÓN CONCURRENTE ........................................................................ 66
Aplicaciones de la programación concurrente ..................................................... 66
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 3
FUNDAMENTOS DE SISTEMAS OPERATIVOS
Comprender el sistema operativo es entender el funcionamiento de todo el sistema de
computo porque dicho sistema de computo, porque dicho sistema administra toda y
cada una de las piezas del hardware y el software. En este texto exploraremos lo que son
los sistemas operativos, como funcionan, que hacen y porque.
Este capítulo describe de manera breve cómo funcionan los sistemas operativos y cómo
han evolucionado en términos generales. Los capítulos siguientes exploran con mayor
profundidad cada uno de los componentes y muestran como se relaciona su función con
las demás partes del sistema operativo. En otra palabras sin problemas.
Nota: como ya se menciono; en todo el libro el tipo en negritas indica términos que
quedan definidos en el glosario.
INTRODUCCION
Empecemos con una definición: ¿qué es un sistema operativo? En los términos más simples, es el “gerente ejecutivo”, la parte del sistema de computo que administra el hardware y el software.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 4
Para ser específicos, controla los archivos, dispositivos, sectores de la memoria principal
y cada nanosegundo del tiempo de procesamiento; asimismo controla quien puede
controlar el sistema y de qué manera. En breve, es el patrón.
Por otro lado, cuando el usuario envía un comando el sistema operativo debe asegurarse
que se ejecute, o si esto no ocurre, deberá arreglárselas de manera que el usuario reciba
un mensaje explicando el error. Esto no significa necesariamente que el sistema
operativo ejecute el comando o envié el mensaje de error; pero si controla las partes o
componentes del sistema que lo hacen.
SOFTWARE DEL SISTEMA OPERATIVO
La pirámide que se muestra en la figura 1.1 y en el forro interior de la pantalla es una
representación abstracta de un sistema operativo y muestra las interrelaciones de sus
componentes principales.
La base de la pirámide muestra los cuatro “administradores” esenciales de todo sistema
operativo: el administrador de memoria, el administrador del procesador, el
administrador de dispositivos y el administrador de archivos. De hecho, estos
administradores son la base de todos los sistemas operativos y cada uno se analiza en
detalle a lo largo de esta primera parte. Cada administrador trabaja de cerca con los
demás y desempeña su papel, sea cual sea su sistema operativo analizado las funciones
de red no siempre fueron una parte integral de los sistema operativos y por lo general se
montaban en sistemas operativos existentes. Por lo tanto, no hemos trazado una esquina
por separado en la pirámide, pero en los capítulos relacionados hemos incorporado estas
funciones bajo el encabezado “sistemas operativos”. Por otra parte, la interfaz de
comandos de usuario, desde la cual los usuarios emiten los comandos al sistema
operativo es un componente específico en cada sistema operativo y muy distinto de un
sistema a las siguiente-algunas veces incluso entre distintas versiones de sistema
operativo-. (Para su conveniencia la figura 1.1 repite en la primera de forros y muestra
los capítulos en los cuales se analiza cada uno de los componentes.)
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 5
Sin importar el tamaño o configuración del sistema, cada uno de los administradores de
subsistemas que se ilustra en la figura 1.2 deben llevar a cabo estas tareas.
1. Monitorear continuamente sus recursos
2. Obligar al cumplimiento de la políticas que determinan quien obtiene que cuando
y cuanto.
3. Asignar los recursos cuando es apropiado.
4. Liberar el recurso-recuperarlo-cuando es conveniente.
Por ejemplo, el administrador de memoria está a cargo de la memoria principal o RAM.
Comprueba la validez de cada solicitud de espacio de memoria y, si se trata de una
solicitud legal le asigna una porción que todavía no esté en uso. En un entorno
multiusuario, el administrador de la memoria establece una tabla para llevar el control de
quien está usando que sección de la memoria. Para finalizar, cuando llega el momento de
recuperar la memoria el administrador la “libera”.
Una de las principales funciones del administrador de memoria es proteger el espacio en
la memoria principal que ocupa el sistema operativo no puede permitir que parte alguna
de este espacio sea alterada de manera accidental o propositiva.
El administrador del procesador decide como asignar la unidad de procesamiento
central (CPU). Una función importante de este administrador es controlar el estado de
cada proceso (un proceso que aquí se define como una “instancia de ejecución” de un
programa):
Este administrador monitorea si el CPU está ejecutando un proceso o espera que termine
la ejecución de un comando de LECTURA o ESCRITURA. Dado que maneja las
transacciones de procesos de un estado de ejecución a otro, se puede comparar con un
controlador de tráfico. El administrador asigna al procesador y establece los registros y
tablas necesarias más tarde, cuando la tarea ha terminado o expirado el tiempo máximo
lo recupera.
De una manera conceptual, el administrador del procesador del procesador tiene dos
niveles de función: uno es manejar las tareas conforme entran en el sistema; el otro es
administrar cada proceso de estas tareas. El planificador de tareas manejar la primera
parte. Es la porción de alto nivel del administrador que acepta o rechaza las tareas que
llegan. El planificador de procesos maneja la segunda parte. Se trata de la porción de
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 6
bajo nivel del administrador del procesador; su trabajo es decidir qué proceso obtiene el
CPU y durante cuánto tiempo.
El administrador de dispositivos vigila todos los dispositivos, canales y unidades de
control. Su tarea es escoger la manera más eficiente de asignar los dispositivos del
sistema (impresoras, terminales, unidades de disco, etc.), con base en una política de
programación escogida por los diseñadores del sistema. Este administrador asigna este
dispositivo, inicia su operación y lo libera.
En cuarto el administrador de archivos, lleva el control de todo archivo en el sistema,
incluyendo archivos de datos, ensambladores, compiladores y programas de aplicación.
Mediante el uso de políticas de acceso predeterminadas, obliga a cada archivo a cumplir
las restricciones de acceso. (Cuando se crea se estipula quien lo accederá solo el sistema
solo el usuario, solo un grupo o de acceso general. Una función crucial del sistema
operativo es hacer que se cumplan estas restricciones). Los administrados de archivos
también controlan la flexibilidad de acceso que tiene cada usuario con los diversos tipos
de archivo (como solo de lectura, de lectura y escritura o la posibilidad de crear
registros). También asigna el recurso al abrir el archivo y lo libera al cerrarlo.
Sin embargo, no basta que cada uno de estos administradores lleve a cabo sus tareas
individuales. También deben ser capaces de trabajar en armonía con los otros
administradores. A continuación veremos un ejemplo simplificado digamos que alguien
escribe un comando para ejecutar un programa. Los siguientes pasos principales deben
darse en secuencia.
1. El administrador de dispositivos recibe los impulsos eléctricos del teclado, codifica
el tecleo para formar el comando y envía el comando a la interfaz de comando del
usuario, donde el administrador del procesador lo valida.
2. Luego, el administrador del procesador manda un mensaje de reconocimiento,
para que aparezca en el monitor de video, de manera que quien escribió sepa
que se envió el comando.
3. Cuando el administrador del procesador recibe el comando, determina si hay que
traer el programa correspondiente de donde este almacenado o si ya está en la
memoria, después de lo cual notifica al administrador apropiado.
4. Si el programa está almacenado, el administrador de archivos debe calcular su
localización exacta en el disco y pasar la información al administrador de
dispositivos. Este recupera y envía el programa al administrador de la memoria,
el cual debe encontrar espacio para el mismo y registrar su ubicación exacta en
la memoria.
5. Una vez que el programa se arla en la memoria, el administrador de esta debe
controlar su localización y progreso conforme lo ejecuta el administrador del
procesador.
6. Cuando termina la ejecución del programa, este manda un mensaje de
“terminado” de regreso al administrador del procesador.
7. Por último, el administrador del procesador manda un mensaje de “terminado” de
vuelta al administrador de dispositivos, que lo muestra en el monitor para que lo
vea el usuario.
Aunque esta es una demostración sobre simplificada de una operación complicada, ilustra
la increíble precisión requerida por el sistema operativo. Recuerde, ningún administrador
por si solo puede llevar a cabo sus tareas si la cooperación activa de las demás partes.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 7
Los sistemas operativos con capacidad de red tienen un quinto administrador esencial
conocido como administrador de red, que proporciona una forma conveniente para los
usuarios de compartir recursos y, al mismo tiempo, controlar su acceso a los mismos
estos recursos incluyen hardware (CPU áreas de memoria, impresora, unidades de cinta,
modem y unidades de disco) y software (compiladores, programas de aplicación y
archivo de datos). Al añadir el quinto administrador para crear un sistema operativo de
red creamos una pirámide de cinco lados. La base de la pirámide aparece en la figura 1.3
y se describe en detalle en el capítulo 9.
HARDWARE DE LA MAQUINA
Para apreciar la función del sistema operativo, necesitamos definir los aspectos
esenciales del hardware del sistema de la computadora la maquina física y sus
componentes electrónico incluyendo los chips de memoria, los dispositivos de entrada
/salida, los dispositivos de almacenamiento y la unidad de procesamiento central. El
hardware se diferencia del software, el cual se refiere a programas escrito para el
sistema de cómputo.
La memoria principal es donde se debe recibir los datos y las instrucciones para ser
procesados.
Los dispositivos de entrada / salida o dispositivo E/S incluyen toda unidad periférica del
sistema como impresoras, unidades de disco, unidad del CD, dispositivos de cinta
magnética, teclado, reproductores de DVD, modem, etcétera.
El CPU o unidad de procesamiento central es el “cerebro” que, apoyado en circuitería (a
veces conocida como chips) controla la interpretación y ejecución, de las instrucciones.
En esencia, controla la operación de la totalidad del sistema de cómputo, como ilustra en
la figura 1.4. Esta unidad inicia o realiza todas las referencia de almacenamiento,
manipulables de datos y operaciones de entrada / salida.
Hasta 1975, las computadoras se clasificaban según su capacidad y precio. Una
mainframe o macrocomputadoras era una maquina grande, tanto físicamente como
por su función o capacidad interna de memoria. La IBM 360, introducida en 1964, en un
ejemplo clásico de una de las primeras macrocomputadoras. La IBM 360 modelo 30 la
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 8
más pequeña de la familia 360 (Prasad, 1989), necesitaba de un cuarto con aire
acondicionado de unos 18 pies de lado para albergar el CPU, la consola del operador, una
impresora, un lector de tarjetas y una máquina perforadora. El CPU tenía 5 pies de altura
y 6 de ancho, con una memoria interna de 64k (considerada grande para la época) y un
precio de 200000 dólares, en dólares de 1964. Debido a su tamaño y precio del
momento, sus aplicaciones se limitaban a grandes centros de cómputo, propiedad del
gobierno federal, universidades y negocios muy grandes. Un ejemplo de un sistema
operativo para macrocomputadoras es el OS/390 de IBM.
La minicomputadora fue desarrollada para satisfacer las necesidades de instituciones
más pequeñas, con unas cuantas docenas de usuarios. Digital Equipment Corporation
(DEC) puso en el mercado una de las primeras minicomputadoras para cubrir las
necesidades de grandes escuelas y pequeñas universidades, que empezaron a ofrecer
cursos de computación a principio de os 70. (El precio de su PDP-8, Periphral Device
Processor-8, era inferior a 18 000 dólares.) Las minicomputadoras eran más pequeñas en
tamaño y capacidad de memoria que una microcomputadora, así como más económicas.
Un ejemplo de un sistema operativo para microcomputadora fue el VAX/VMS, que desde
entonces ha evolucionado hacia el sistema operativo Open VMS Alpha.
La supercomputadora apareció en 1976, principalmente para cubrir aplicaciones
gubernamentales que necesitaban capacidad masiva y rápida de manipulación de cifras
para llevar a cabo operaciones militares y de pronóstico del tiempo. Los negocios y la
industria se interesaron en la tecnología cuando las computadoras masivas se hicieron
más rápidas y menos costosas. Una supercomputadora Cray T3E-1200ETM es un ejemplo
típico, con 6 a 2048 procesadores que realizan hasta 2.4 billones de operaciones de un
punto flotante por segundo (taeraflopc). Hoy día, se realizan supercomputadoras para
una amplia gama de tareas, desde la investigación científica hasta el apoyo a clientes y
desarrollo de productos. Incluso se realizan para efectuar cálculos complicados utilizados
para la creación de películas animadas. Así mismo ayudan a las empresas petroleras en
su búsqueda de hidrocarburos mediante el análisis de cantidades masivas de datos
(Stair, 1999). Los ejemplos de sistemas operativos para supercomputadoras son los
derivados de UNIX de alto nivel como UNICOSR e IRIXR
La microcomputadora fue desarrollada para los usuarios individuales a fines de los 70.
Tandy Corporation y Apple Computer, Inc, fueron los primeros en ofrecer
microcomputadoras para la venta al público en general. El primero se dirigía al mercado
de pequeños negocios, y el último al mercado de la educación elemental. Estos primeros
modelos tenían muy poca memoria según los estándares de hoy dia-64k era la capacidad
máxima -. Su tamaño físico era menor que de la minicomputadoras de dicha época,
aunque mayor que el de las microcomputadoras de hoy día. Para finalizar las épocas de
las microcomputadoras crecieron a fin de aceptar el software con mayor capacidad y
velocidad. La característica distintiva de una microcomputadora es su estatus de uso
individual. Un ejemplo de un sistema operativo para estas maquinas es el MS-DOS.
Las microcomputadoras más potentes, utilizadas para empresas comerciales , educativas
y gubernamentales se conocen como estaciones de trabajo por lo general se
encuentran en red i se utilizan para dar apoyo a usuarios de ingeniería y técnicos que
llevan a cavo calcules matemáticos masivos, diseño asistido por computadoras (CAD) u
otras aplicaciones que para cumplir sus necesidades requiere unidades centrales de
procesamiento muy poderosas, así como grandes cantidades de memoria principal y
presentaciones graficas de resolución extremadamente alta. Un ejemplo de sistema
operativo para estación de trabajo es UNIX.
Desde mediados de los 70 los rápidos avances de la tecnología de la computación han
obscurecido de características distintivas de las primeras maquinas: tamaño físico, costo
y capacidad de memoria. Las microcomputadoras más poderosas de hoy día tienen
múltiples procesadores coordinadas por el administrador del procesador las
macrocomputadoras simples siguen teniendo una memoria principal grande, pero ahora
están disponibles en un gabinete de tamaño de un escritorio. Las minicomputadoras se
parecen a los microcomputadoras y las más pequeñas pueden llevar a cabo tareas
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 9
reservadas a las microcomputadoras; así mismo, la capacidad de red ha sido integrada a
casi todos los sistemas. Hubo un tiempo en que las computadoras se clasificaron con
base en su capacidad de memoria. Ahora se distinguen por la capacidad del procesador.
Debemos subrayar que se trata de categorías relativas y lo que hoy es “grande” se
convertirá en “mediano” y después en “pequeño” en el futuro cercano.
En 1965, Gordon Moore, ejecutivo de Intel, señalo que cada nuevo chip procesador
contenía alrededor del doble de capacidad de su predecesor y cada chip salía al mercado
en un plazo de 18 a 24 meses después del anterior. Concluyo que la tendencia aria que
la potencia de cómputo se elevaría en sentido exponencial a lo largo de periodos
relativamente breves. Conocida como la ley de Moore, la tendencia a continuado y sigue
siendo muy precisa por lo que forma la base de los pronósticos industriales el chip Intel
4004 en 1971 tenía 2300 transistores, en tanto que veinte años después el chip Pentium
II llego a 7.5 millones.
TIPOS DE SISTEMAS OPERATIVOS
Los sistemas operativos para las computadoras grandes y pequeñas se ubican en cuatro
clases, que se distinguen por su tiempo de respuesta y la forma en que se introducen los
datos en el sistema. Son los sistemas por lote, interactivo, en tiempo real híbrido.
Los sistemas por lotes o batch existen desde las primeras computadoras que se
apoyan en tarjetas perforadas o en cintas para la entrada cuando se introducía una tarea
mediante la agrupación de las tarjetas en un paquete y se corría todo el paquete atreves
de un lector de tarjetas como un grupo: Un “lote” los sistemas por lotes de hoy no están
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 10
limitados o tarjetas o cintas, pero los trabajos todavía se procesan en serie, sin
interacción del usuario.
La eficiencia del sistema se media en producción-esto es, la cantidad de tareas
completadas en una cantidad dada de tiempo (por ejemplo, 30 tareas por hora)-y el
tiempo total se media en horas, a veces en días. En la actualidad no es común encontrar
un sistema que este limitado en programas por lotes.
Los sistemas interactivos (también conocidos como sistemas “tiempo compartido”)
dan un tiempo de retorno más rápido que los demás por lotes, pero son más lentos que
los sistemas de tiempo real, de los cuales hablaremos más adelante. Se introdujeron
para satisfacer las demandas de usuarios que necesitaban un tiempo de retorno rápido al
eliminar los errores de sus programas. El sistema operativo requería el desarrollo del
software de tiempo compartido, lo que permitiría a cada usuario interactuar directamente
con el sistema de computo vi comandos introducidos a partir de una terminal de tipo
máquina de escribir.
El sistema operativo proporciona una retroalimentación inmediata al usuario y el tiempo
de respuesta se puede medir en minutos o segundo, según la cantidad de usuarios
activos.
Los sistemas de tiempo real son los más rápidos de los cuatro y se utilizan en
entornos de “tiempo critico”, donde los datos se deben procesaron la suma rapidez
porque la salida afecta decisiones inmediatas. Los sistemas de tiempo real se utilizan
para vuelos especiales, control de tráfico en aeropuertos, aeronaves de alta velocidad,
procesos industriales, equipo médico complicado, distribución de electricidad y
conmutación telefónica. Un sistema a tiempo real debe ser 100 por ciento de las veces.
El tiempo de respuesta se mide en fracciones de segundo aunque esto en la práctica es
un ideal que no se logra a menudo. Se bien en teoría es posible convertir un sistema
operativo de tiempo general en un sistema de tiempo real, en la práctica de carga
general de los sistemas de tipo general es tan grande que no se logran desempeños a
tiempo real. Por tanto, la mayor parte de los trabajos en tiempo real requieren sistemas
operativos diseñados para llenar necesidades a tiempo real.
Los sistemas híbridos, son una combinación en sistemas en lotes e interactivos.
Parecen interactivos porque los usuarios individuales pueden tener acceso al sistema
mediante terminales y obtener una respuesta rápida; pero cuando la carga interactiva es
ligera este tipo de sistemas acepta y opera programas en lotes en un segundo plano.
Un sistema hibrido aprovecha el tiempo libre entre demandad de procesamiento para
ejecutar programas que no necesitan ayuda científica del operador. Muchos sistemas de
cómputo grande son híbridos.
HISTORIA BREVE DEL DESARROLLO DE LOS SISTEMAS
OPERATIVOS
La evolución de los sistemas operativos es paralela a la evolución de las computadoras
para las que fueron diseñados a fin de controlarlas. A continuación ofrecemos un breve
panorama general del proceso.
DÉCADA DE LOS 40
La primera generación de computadoras (1949-1955) se dio en una época de tecnología
de tubos al vacio (bulbos) y de computadoras del tamaño de salones de clase. Cada
máquina era única en estructura y propósito. Había poca necesidad de un software
estándar de sistema operativo, ya que el uso de cada computadora estaba restringido a
unos cuantos profesionales, que trabajaban en aplicaciones matemáticas, científicas o
militares, todos familiarizados con la idiosincrasia de su hardware.
Un programa típico incluía todas las instrucciones que la computadora necesitaba para
llevar a cabo las tareas solicitadas daba instrucciones explicitas al lector de tarjetas
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 11
(cuando empezar, como imprimir el producto terminado, como dar formato a la pagina y
cuando terminar).
Los programadores operaban las maquinas desde la consola principal era un proceso en
que ellos debieran hacer todo para eliminar los errores de un programa el programador
tenia al procesador, leía el contenido de cada registro, efectuaba las correcciones en las
localizaciones de memoria y reanudaba la operación.
Para ejecutar programas los programadores tenían que reservar la maquina el tiempo
que estimaban que esta tardaría en ejecutar el programa. Como resultado, la maquina se
utilizaba en una memoria diferente. El CPU procesaba datos y efectuaba cálculos durante
solo una fracción de tiempo disponible y, de hecho, la totalidad del sistema esperaba
ocioso entre las reservaciones.
Con el paso del tiempo el hardware y software de cómputo se hicieron mas estándares y
la ejecución de un programa requería menos pasos y conocimientos de los mecanismos
internos de la computadora se desarrollaron compiladores y ensambladores para traducir
a código binario los comandos de los lenguajes de alto nivel que se estaba desarrollado.
Los sistemas operativos rudimentarios empezaron a tomar forma con la creación de
macros, programas de videoteca, subritinas estándares y programas de utilería. Además
incluían subrutinas de unidades de dispositivos programas prescritos que estandarizaban
la forma en que se utilizaban los dispositivos de entrada y salida.
Estos primeros programas tenían una desventaja importante, ya que estaban diseñados
para utilizar sus recursos de manera conservadora, a costa de la comprensión.
Esto significaba que muchas instrucciones utilizaban una lógica complicada, solo
comprensible para el programador original, por lo que era casi importante que cualquier
otra persona eliminara errores o cambiara el programa más tarde.
DÉCADA DE LOS 50
Las computadoras de segunda generación (1955-1965) fueron desarrolladas para llenar
las necesidades de un nuevo mercado, los negocios. El entorno empresarial daba mucha
importancia a la efectividad en costo del sistema. Las computadoras seguían siendo muy
costosas en especial al compararlas con otro equipo de oficina (la IBM 7094 tenía un
precio de 200000 dólares). Por lo tanto, se debía maximizar la producción para hacer que
este tipo de inversión fuera rentable para uso empresarial lo que significaba incrementar
de manera dramática el uso del sistema.
Dos mejoras hallaron una amplia difusión: se contrataron operadores de computadoras
para facilitar la operación de cada máquina y se instituyo la programación de las tareas
dicha programación es un esquema de mejora de la productividad que reúne programas
con requerimientos similares. Mientras el compilador FORTRAN estuviera en la memoria,
se ejecutaría varios programas FORTRAN a todas las tareas que utilizaban lector de
tarjetas como entrada se correrían puntos y los que utilizaban la unidad de cinta se
ejecutarían después. Operadores llegaron a la conclusión que la combinación más
eficientes eran la mezcla de requerimiento de dispositivos de entrada y salida; esto es, al
mezclar programa de entrada por cinta con programa de entrada por tarjeta, se podría
montar o rebobinar las cintas mientras el lector de tarjetas estaba ocupado
La programación de tareas introdujo la necesidad de “tarjetas de control” que definían la
naturaleza exacta de cada programa y sus requerimientos. Esto fue uno de los primeros
usos de un leguaje de control de tareas (JCL, por sus siglas en ingles) que ayudo al
sistema operativo a coordinar y administrar los recursos del sistema, al identificar los
usuarios y sus tareas, y al especificar los recursos requeridos para ejecutar cada tarea.
Pero incluso con técnicas por lotes, las computadoras más rápidas de segunda
generación aceptaban costosos retrasos de tiempo entre el CPU y los dispositivos de
entrada/salida. Por ejemplo, una tarea que significa leer mil seiscientos tarjetas, podía
representar 79 segundos en el lector de tarjetas y solo 5 segundos de uso del CPU para
ensamblar “compilar”. Esto significa que el CPU estaba ocioso 94% del tiempo y solo
procesaban 6% de tiempo dedicado a dicha tarea.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 12
Varios factores terminadores por ayudar a mejorar el desempeño o rendimiento del CPU.
Primero, la velocidad de los dispositivos de entrada/salida como unidades de cinta,
discos y tambores que fue haciendo más rápida. Segundo, para utilizar más el área de
almacenamiento disponible en estos dispositivos, los registros se bloqueaban antes de su
recuperación o almacenamiento (Bloquear significa que varios registros lógicos se
agrupan en un registro físico.) cuando se recuperaban los registros “había que
desbloquearlos” antes de que un programa pudiera utilizarlos. Para ayudar a los
programadores de estas funciones de bloqueo y desbloqueo, se desarrollaron métodos de
acceso y se agregaron al código objeto por medio del editor de enlace.
Tercero, para reducir la diferencia de velocidad entre entradas y salidas del CPU, se
coloco una interfaz conocida como “unidad de control” entre ellas para ejecutar la función
de almacenamiento temporal en el buffer. Un buffer es un área temporal de
almacenamiento que funciona como sigue: conforme al dispositivo de entrada lento lee
un registro, la unidad de control coloca cada uno de los caracteres del registro en el
buffer. Cuando este se llena, todos los registros se transmiten rápidamente al CPU el
proceso es justo lo opuesto para dispositivos de salida: el CPU coloca en el buffer todo el
registro, mismo que pasa por la unidad de control a la velocidad más lenta, requerida por
el dispositivo de salida.
Si la unidad de control tiene más de un buffer el proceso de entrada y salida puede
hacerse con más rapidez si la unidad de control tiene dos buffer, el segundo se puede
cargar mientras el primero está transmitiendo su contenido al CPU.
En términos ideales, cuando el primero ha transmitido su contenido, el segundo estará
listo para empezar, y así sucesivamente. De esta manera, el tiempo de entrada se
reduce a la mitad.
Además el uso del buffer, se desarrolla en forma primitiva de efectuar operaciones
periféricas simultáneas, realizando operaciones de lectura, impresión y perforación de
tarjetas fuera de línea. Hoy día esta forma de operar se le forma SPOOL. Que son las
siglas en ingle de operación periférica simultanea en línea (Simultaneous Peripheral
Operations On Line). Por ejemplo, los trabajos de entrada serian transferidos fuera de
línea de los paquetes de tarjeta a la cinta, con lo que su lectura llega al CPU desde la
cinta de mayor velocidad que la del lector de tarjetas. El modo spool funciona de la
misma manera que el buffer pero, en este ejemplo, es un dispositivo periférico que no
está directamente conectado al CPU en tanto que el buffer forma parte de hardware de la
computadora.
También durante la segunda generación se desarrollaron técnicas para administrar
bibliotecas de programas crear y mantener archivos e índices de datos, para elegir al
azar las direcciones de acceso directas, y crear y revisar etiquetas de archivo se
desarrollaron varias técnicas estándares de organización de archivos, como el acceso
secuencial, el secuencial indizado y el acceso directo con estas técnicas instaladas mini
programas estandarizados, conocidos como “macros” eliminaban la necesidad que tenían
los programadores de escribir rutinas personalizadas de apertura y cierre para cada
programa.
Se desarrollaron los interruptores de tiempo para proteger al CPU de ciclos infinitos en
programas que por error tenía instrucciones de ejecutar una sola serie de comandos para
siempre y a fin de permitir el trabajo compartido. Se asigno una cantidad fija de tiempo
de ejecución a cada programa al entrara al sistema, lapso vigilado por el sistema
operativo. Si cualquier programa seguía operando al expirar este plazo, se les daba por
terminando y el usuario era notificado utilizando un mensaje de error.
Durante la segunda generación, los programas seguían siendo operados en modo de
lotes seriales-uno por uno. El siguiente paso hacia un mejor uso de los recursos del
sistema fue pasar el procesamiento compartido.
DÉCADA DE LOS 60
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 13
Las computadoras de la tercera generación provienen de mediados del decenio de los 60
fueron diseñadas con CPU más rápidas pero du velocidad causo problemas cuando
interactuaba con dispositivos de entrada/salida relativamente lentos. La solución fue la
multiprogramación, que introdujo la idea de cargar muchos programas de una vez y
compartir la tensión de un CPU.
Los primeros sistemas de multiprogramación permitían que se diera servicio a cada
programa por turno uno después de otro. El mecanismo más común para implementar la
multiprogramación fue introducir el concepto de “interrupción”, que es cuando se notifica
al CPU cuales sucesos necesitan los servicios de los sistemas operativos. Por ejemplo,
cuando un programa emite un comando de entrada /salida, genera una interrupción que
solicita los servicios del procesador de entrada y salida y se libera al CPU para que inicie
la ejecución de la tarea siguiente. Esto se conoció como multiprogramación pasiva ya
que el sistema operativo no controlaba las interrupciones sino que esperaba a que cada
tarea terminaba una secuencia de ejecución era menos que ideal, porque si una tarea
estaba “acotada por el CPU” (esto es que ejecutaba una gran cantidad de procesamiento
sin detenerse, antes de emitir una interrupción) ocupaba el CPU durante largos periodos
y el resto de las tareas tenía que empezar.
A fin de compensar este efecto, pronto se dio una función más activa al sistema
operativo multiprogramación activa, que permitía que cada programa mas usara una
tarjeta preestablecida del tiempo del CPU. Cuando expiraba el plazo, la tarea se
interrumpía y se iniciaba otra tarea. La tarea interrumpida tenía que empezar su turno
hasta que se le permitiera reanudar la ejecución mas tarde. La idea de dividir el tiempo
se hiso común en muchos sistemas de tiempo compartido.
La planificación de programas que se había iniciado con los sistemas de segunda
generación, continuaba en ese momento pero se complicaba porque la memoria principal
estaba ocupada con muchos trabajos la resolución fue clasificar los trabajos en grupo y
cargar los programas de acuerdo con una rotación preestablecida. Los grupos por lo
general se determinaban en función de la prioridad de los requerimientos de memoria-
cualquiera de los cuales daba un uso más eficiente de los recursos.
Además de planificar los trabajos de manejar las interrupciones y asignar la memoria,
los sistemas operativos tenían que resolver conflictos cuando dos tareas solicitaban el
mismo dispositivo al mismo tiempo.
Durante este periodo se efectuaron pocos avances de importancia en la administración
de los datos. Las funciones de biblioteca y los métodos de acceso eran los mismos de los
últimos años de la segunda generación. El sistema operativo de las maquinas de tercera
generación consistía en muchos módulos entre los cuales podía seleccionar el usuario,
por lo que todo el sistema operativo se personalizaba para adecuarse a necesidades
parciales los módulos de mayor uso se hacían resistentes en el núcleo y los menos
utilizados residían en un almacenamiento secundario de donde eran llamados solo
cuando hacían falta.
DÉCADAS DE LOS 70
Después de la tercera generación, a fines de los 70 las computadoras tenían CPU más
rápidos, lo que aumento la disparidad entre su velocidad de procesamiento y el tiempo
de acceso más lento de las entradas y salidas. Los esquemas de multiprogramación para
incrementar el uso del CPU estaban limitados por la capacidad física de la memoria
principal, un recurso limitado y costoso.
Una solución a esta limitación física fue el desarrollo de la memoria virtual, que
aprovecho el hecho de que el CPU solo podía procesar una instrucción a la vez con la
memoria virtual, no era necesario que todo programa residiera en memoria antes que se
iniciara la ejecución. Un sistema con memoria virtual dividiría los programas en
segmentos los mantendría en almacenamiento secundaria y traería cada segmento a la
memoria conforme fuera necesario. (Los programadores de computadoras de segunda
generación habían utilizado esta idea con el método de programación “roll in/roll out”,
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 14
que hoy se conoce como “súper posición” para ejecutar programas que excedían la
memoria física de esas computadoras).
En este tiempo también existía una creciente atención a la necesidad de conservar los
recursos de datos el software de administración de base de datos se convirtió en una
herramienta popular, ya que organizaba los datos de una manera integral, minimizaba la
redundancia y simplificaba la actualización y el acceso de los datos. Se introdujo cierta
cantidad de sistemas de consulta que permitía que incluso un usuario novato recuperar
piezas especificas de la base de datos. Estas consultas solían efectuarse por medio de
una terminal lo que obligo a un crecimiento en la necesidad de apoyarse en terminales y
en software de comunicaciones de datos.
Los programadores pronto se distanciaros mas de las complicaciones de la computadora
y los programas de aplicación empezaron a utilizar palabras de tipo ingles, estructuras
modulares y operaciones estándares, esta tendencia hacia uso de estándares mejoro la
administración de los programas, ya que el mantenimiento de los mismos se hiso más
rápido y fácil.
DÉCADA DE LOS 80
El desarrollo en este decenio mejoro de una manera dramática le relación
costo/rendimiento de los componentes de la computadoras. El hardware era más flexible
con funciones lógicas incorporadas en tarjetas de fácil remplazo. También era menos
costoso por lo que más funciones del sistema operativo se hicieron parte del hardware
esto dio lugar a un nuevo concepto , el firmware, término utilizado para indicar que un
programa está contenido de manera permanente en ROM (memoria de lectura
solamente) en contraposición a los que permanecen en almacenamiento secundario la
tarea del programador según se había definido en años anteriores, cambio de manera
espectacular porque el software del sistema desempeñaba muchas funciones de
programación esto simplifico la área del programador . Este simplifico la tarea del
programador y la hizo menos dependiente del hardware.
La industria acabo pasando al multiprocesamiento y se diseñaron lenguaje más
elaboradorados para coordinar las actividades los diversos procesadores que daban
servicio a una tarea. Como resultado, se pudieron ejecutar programas en paralelo y llego
a ser habitual dar por hecho que los sistemas operativos de computadoras de cualquier
tamaño aceptaran el multiprocesamiento.
La evolución de la computadora personales y de las comunicaciones de alta velocidad
origino el cambio al procesamiento distribuido y los sistemas en red, que permite que
usuarios en ubicaciones remotas compartan recursos de hardware y de software.
En términos generales, con los sistemas operativos de red los usuarios reconocieron la
existencia de muchos recursos en red y pudieron registrarse en localizaciones remotas y
manipular archivos en red muy lejanas. Estos sistemas operativos eran similares a los
utilizados en un procesador en cuanto a que cada maquina corrían sus sistemas
operativo local y tenía sus usuarios. La diferencia estaba en la adición de un controlador
de interfaz de red con software de bajo nivel para manejar el sistema operativo local, así
como programas que permitía el registro a distancia y acceso de archivos remotos.
Por otra parte, con el sistema operativo distribuidos, los usuarios podían pensar que
estaba trabajando con un sistema uniprocesador típico, cuando en realidad estaban
conectados a una red formada por muchos procesadores que trabajan en intima relación.
Con estos sistemas los usuarios no necesitaban que procesador ejecutara sus
aplicaciones ni cual dispositivos almacenaba sus archivos. El sistema operativo manejaba
estos detalles de manera transparente, situación que requería más que agregar unas
cuantas líneas de código a un sistema operativo de un procesador. La desventaja de un
sistema operativo de este tipo era la necesidad de algoritmos más complicados de
programación de procesadores. Además, los retardos de comunicación dentro de la red
significaba que algunas veces los algoritmos de programación tenían que operar con
información incompleta o desactualizada.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 15
DÉCADA DE LOS 90
A mediados de los 90 la demanda generalizada de capacidades internet origino la
proliferación de capacidades de red. Hoy, las accesibilidad a web y es intercambio de
correo electrónicos son características comunes en casi todo sistema operativo. Sin
embargo, el crecimiento de la red también ha creado mayor demanda de seguridad, a fin
de proteger el hardware y el software.
Durante el decenio también proliferaron las aplicaciones de multimedios que
demandaban potencia, flexibilidad y compatibilidad de dispositivos adicionales para la
mayor parte de sistemas operativos. Una computadora típica multimedia contiene
dispositivos para correr audio, video, creación grafica y edición. Esto puede requerir
muchos dispositivos especializados como un micrófono un piano digital una o interfaz
digital de instrumento musical, una cámara digital, una unidad de disco de video digital
unidades de disco compacto CD altavoces, monitoreas adicionales, dispositivos de
proyección, impresoras de color, conexión internet de alta velocidad, etc. También
precisa hardware especializado controladores, tarjetas, buces entre otros así como
software para hacer que trabajen juntos correctamente.
Los multimedios necesitan una gran capacidad de almacenamiento, misma que el
sistema operativo debe administrar con gracia. Por ejemplo cada segundo de un video de
pantalla completa de 30 figuras por minuto requiere 27 megabytes de almacenamiento.
Esto significa que unos 24 segundo de video caven en un disco compacto estándar. Por lo
que un programa de televisión de 20 minutos requeriría alrededor de 50 discos de
almacenamiento, a menos que se compriman los datos de alguna manera. Para satisfacer
la demanda de video comprimido, las compañías de hardware han desarrollado chips y
tarjetas de video de uso especial. Un estándar es el video digital interactivo, comprime
las imágenes en una relación de 150:1, por lo que una hora de proyección se puede
almacenar en menos de un gigabyte.
Cuál será el efecto de estos avances tecnológicos en el sistema operativo, cada avance
requiere un avance paralelo en las capacidades de administración del software. Los
sistemas operativos que no puedan mantenerse al día con la demanda se harán
obsoletos con rapidez.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 16
ADMINISTRADOR DEL PROCESADOR
En los sistemas de un solo usuario, el procesador sólo está ocupado el usuario ejecuta
una tarea, en todos los demás momentos está ocioso. La administración del procesador
en este entorno es simple. Sin embargo, cuando existen muchas usurarios con muchas
tareas en el sistema (esto se conoce como un entorno de multiprogramación) hay que
asignar el procesador a cada tarea de una manera justa y eficiente, lo que puede ser algo
complicado, como veremos en este capítulo.
Antes de empezar, definamos con claridad algunos de los términos que utilizaremos en
las páginas siguientes. Un programa es una unidad inactiva, como un archivo
almacenado en un disco. Un programa no es un proceso. Para un sistema operativo, un
programa o un trabajo es una unidad de trabajo enviada por el usuario. El término
trabajo por lo general se asocia con sistema por lotes.
Por otra parte, un proceso es una entidad activa, que requiere un conjunto de recursos
para llevar a cabo su función, entre ellos un procesador y registro especiales. Un
proceso, también conocido como tarea, es una instancia de un programa ejecutable.
Una hebra de control es una porción de un proceso que se puede ejecutar de manera
independiente. Por ejemplo, si su sistema permite que los procesos tengan una sola
hebra de control y usted desea una serie de imágenes en el sitio Web de un amigo,
puede instruir al navegador (Browser) para que establezca una conexión entre ambos
sitios y descargar una imagen a la vez. Sin embargo, si su sistema permite que sus
procesos tengan múltiples hebras de control, puede solicitar varias imágenes al mismo
tiempo y el navegador o explorador establecerá múltiples conexiones y descargará varias
imágenes a la vez.
El procesador, también conocido como CPU (siglas en inglés de unidad de
procesamiento central), es la parte de la máquina que lleva a cabo los cálculos y ejecuta
los programas.
La multiprogramación requiere que el procesador se “asigne” a cada tarea o proceso
durante un periodo y se “desasigne” en el momento apropiado. Si el procesador se
desasigna durante la ejecución de un programa, esto debe ocurrir de manera que se
pueda reiniciar después con toda la facilidad posible. Es un procedimiento delicado. Como
demostración, veamos un ejemplo cotidiano.
Aquí está usted, confiando en que puede armar un juguete, a pesar de la advertencia
que “requiere algo de ensamble”. Armado con las instrucciones y mucha paciencia, cada
paso, uno a la vez, y llegar al producto terminado.
El primer paso es “unir la parte A con la parte B, utilizando un tornillo de 2 pulgadas” y
conforme usted lo completa, marca el paso uno como “ejecutado”. Inspirado por su
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 17
éxito, pasa al paso 2 y después al 3; acaba de completarlo cuando un vecino se lesiona al
trabajar con un herramienta eléctrica y grita pidiendo ayuda.
Rápidamente marca el paso 3 en las instrucciones, de manera que sepa dónde se quedó,
hace a un lado sus herramientas y corre al lado de su vecino. Después de todo, tiene
mayor importancia la necesidad inmediata de alguien que su éxito final con el de un
libro de primeros auxilios y utiliza vendajas y antiséptico.
Luego de tratar con éxito la lesión, regresa a su tarea. Conforme recoge sus
herramientas, hace referencia a las instrucciones y ve que debe empezar a partir del
paso 4. Continúa con su proyecto hasta concluirlo.
En terminología de sistemas operativo, usted ejecutó el papel de CP U o procesador.
Existían dos programas o tareas: una era ensamblar el juguete; la segunda, vendar la
lesión. Cuando estaba ensamblando el juguete (tarea A) cada uno de los pasos que llevó
a cabo era proceso. La llamada de auxilio fue una interrupción y cuando dejó el juguete
para ayudar a su amigo herido, pasó a un programa de una prioridad superior. Cuando
usted fue interrumpido, llevó a cabo un cambio de contexto al marcar el paso tres
como la última instrucción terminada y dejó de lado sus herramientas. En cuidado de la
lesión de su vecino se convirtió terminada y dejó de lado sus herramientas. El cuidado de
la lesión de su vecino se convirtió en la tarea B. Mientras usted ejecutaba las
instrucciones de primeros auxilios, cada uno de los pasos que ponía en práctica resultaba
de nuevo un proceso. Y, naturalmente, cuando cada una de las dos tareas se completan,
el procesamiento termina.
El administrador del procesador identificaría la serie de hechos como sigue:
Obtención de entrada para la tarea A (localización de las instrucciones en la caja) Identificación de los recursos (acopio de las herramientas necesarias) Ejecución del proceso (seguimiento de cada uno de los pasos en turno) Interrupción (llamada del vecino) Cambio de contexto a tarea B (usted marca el sitio donde se quedó en las instrucciones) Obtención de entrada para la tarea B (encuentra el libro de primeros auxilios) Identificación de recursos (reúne los suministros médicos) Ejecución del proceso (sigue cada paso señalado en el libro de primeros auxilios) Terminación de la tarea B (regresa a casa) Cambio de contexto a tarea A (se prepara para reanudar el ensamble) Reanuda la ejecución del proceso (ejecuta los pasos pendientes por turno) Interrumpido Terminación de la tarea A (juguete terminado)
Como hemos visto, varias tareas o procesos pueden compartir un procesador. Ahora
bien, esto es posible sólo si el sistema operativo tiene una política de planificación y un
algoritmo de planificación para determinar cuándo dejar de trabajar en una tarea y
asumir otra.
En este ejemplo, el algoritmo de planificación se basaba en la prioridad: usted trabajaba
en los procesos correspondientes a la tarea A hasta que se presentó una tarea de
prioridad más elevada. Aunque en este caso se trataba de un buen algoritmo, un
algoritmo de planificación basado en la prioridad no siempre es el mejor, como veremos
en este capítulo.
PLANIFICACIÓN DE TRABAJOS EN COMPARACIÓN CON PLANIFICACIÓN DE PROCESOS
El administrador del procesador está compuesto por dos sub-administradores,
encargados de la planificación de trabajos y de la planificación de procesos,
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 18
respectivamente. Se conoce como el planificador de trabajo y el planificador de
procesos.
Típicamente, un usuario concibe un trabajo como una serie de pasos de tarea globales –
complicación, carga y ejecución- o como un paso completo: ejecución. Sin embargo, por
lo general la mayor parte de los sistemas operativos maneja la planificación de los
trabajos en dos niveles. Si regresamos al ejemplo anterior, podemos observar que existe
una jerarquía entre el planificador de trabajos y el de procesos.
La planificación de los dos “trabajos”, ensamblar el juguete y vendar la lesión, se basó en
los conceptos primero en entrar, primero en servirse, y prioridad. El planificador de
tareas las inicia con base en ciertos criterios. Una vez seleccionado el trabajo para su
ejecución, el planificador de procesos establece cuándo se ejecuta cada paso o conjunto
de pasos –una decisión que también se base en ciertas criterios-. Cuando usted inició el
ensamble del juguete, el planificador de procesos habría seleccionado para su ejecución
cada paso en las instrucciones de ensamble.
Por lo tanto, cada trabajo (o programa) pasa a través de una jerarquía de
administradores. Dado que el primero que encuentra es el planificador de trabajos,
también se conoce como planificador de alto nivel. Este subadministrador sólo se
ocupa de elegir los trabajos de una cola de trabajos que llegan y colocarlas en la cola de
procesos, ya sea en lotes o de manera interactiva, con base en las características de
cada uno. Su meta es ubicar las tareas en una secuencia que utilice tanto como sea
posible los recursos del sistema.
Es una función importante. Por ejemplo, si el planificador de trabajos escoge varios para
ejecutarlos de manera consecutiva y cada uno tiene muchas E/S (entrada/salida), los
dispositivos E/S se mantendrán muy ocupados y el CPU tendría que hacerse cargo de las
E/S –en caso de que no se utilizara un controlador de E/S- por lo que se ejecutaría muy
poca computación. Por otra parte, si el planificador de trabajos selecciona varios trabajos
consecutivos con gran cantidad de computación, el CPU estaría muy ocupado, perol os
dispositivos de E/S estarían ociosos, en espera de solicitudes E/S. Por lo tanto, un
planificador de trabajos busca una mezcla equilibrada de trabajos que requieren grandes
cantidades de interacción E/S y de otros que precisan grandes cantidades de
computación. Su meta es mantener ocupada la mayor parte de los componentes de
sistema de la computadora la mayor parte del tiempo.
PLANIFICADOR DE PROCESOS
La mayor parte de este capítulo está dedicado al planificador de procesos, porque
después que el panificador de trabajos pone un trabajo en la cola de LISTO, el
planificador de procesos se hace a cargo. Define qué trabajos tendrán derecho al CPU,
cuándo y cuánto tiempo. También decide cuándo debe interrumpirse el procesamiento,
determina a qué colas se debe pasar el trabajo durante su ejecución y reconoce cuándo
ha concluido un trabajo y ya no hay necesidad de seguir procesándolo.
Este subadministrador en un planificador de bajo nivel que asigna el CPU para
ejecutar los procesos de los trabajos que el planificador de trabajos ha colocado en la
cola de LISTO. Cuando hay que orquestar el procesamiento de varios trabajos, se
convierte en una función vital- de la misma manera que cuando usted deja su ensamble
y se apresura a ayudar a su vecino.
Para planificar el CPU, el planificador de procesos aprovecha un rasgo común en la
mayoría de los programas de cómputo: la alternancia entre ciclos CPU y de E/S. Observe
que el trabajo que sigue tiene un ciclo de CPU relativamente largo y dos ciclos de E/S
muy breves.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 19
Aunque la duración y frecuencia de los ciclos del CPU varían de un programa a otro,
existen varias tendencias generales que se pueden explotar al seleccionar un algoritmo
de planificación. Por ejemplo, las trabajos limitados por E/S (como la impresión de
una serie de documentos) tienen ciclos CPU muy breves y largos ciclos de entras y
salidas, en tanto que los trabajos limitados por CPU (como la determinación de los
trescientos primeros números primos) tienen largos ciclos CPU y ciclos de entradas y
salidas más cortos. El efecto total de los ciclos CPU –tanto de los trabajos limitados por
E/S como de los restringidos por CPU- se aproxima a una curva de distribución de
Poisson (Fig. 4.1.)
En un entorno muy interactivo existe un tercer nivel del administrador del procesador,
conocido como planificador de nivel medio. En algunos casos, en especial cuando el
sistema está sobrecargo, el planificador de nivel medio encuentra ventajoso retirar
trabajos activos de la memoria para reducir el grado de multiprogramación, y por lo
tanto, permitir que los trabajos se completen más aprisa. Este subadministrador controla
los trabajos que se intercambian hacia afuera y de regreso.
En un entorno monousuario, no existe distinción entre planificación de trabajos y de
procesos porque en cualquier momento sólo un trabajo está activo en el sistema, por lo
que el CPU y otros recursos están dedicados a él hasta que se completa.
ESTADO DE LOS TRABAJOS Y DE LOS PROCESOS
A medida que un trabajo se mueve por el sistema, siempre estará en uno de tres a cinco
estados, conforme cambia de ACEPTADO a LISTO a EJECUCIÓN a BLOQUEADO y por
último a TERMINADO (Fig. 4.2.). Éstos se conocen como estados del trabajo o
estados del proceso.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 20
He aquí cómo cambia el estado de un trabajo cuando un usuario envía un trabajo al
sistema por lotes o en forma interactivo. Cuando el sistema lo acepta lo pone en
ACEPTADO en una cola. En algunos sistemas el manejador spool del trabajo (o
controlador del disco) genera una tabla con las características década trabajo de la cola y
advierte las básicas, como estimación del tiempo de uso del CPU, prioridad, dispositivos
especiales de E/S requeridos y el máximo de memoria necesaria. El planificador de
trabajos usa esta tabla para decidir cuál será el siguiente trabajo que se va a ejecutar.
Desde ACEPTADO, el trabajo pasa a LISTO cuando está listo para ser ejecutado pero está
en espera de CPU. En algunos sistemas, el trabajo (o proceso) se puede colocar
directamente en la lista de LISTOS. En EJECUCIÓN significa que el trabajo está siendo
procesado. En sistemas que tienen un solo procesador solamente un trabajo o proceso
puede estar en estado EJECUCIÓN. En BLOQUEADO quiere decir que el trabajo no puede
continuar hasta que no se le asigne un recurso específico o se termina una operación de
E/S. Al completarse, el trabajo está TERMINADO y se devuelve al usuario.
El planificador de trabajos o de procesos inicia la transición de un estado a otro:
El planificador de trabajo empieza la transición de ACEPTADO a LISTO de acuerdo
con alguna política predefinida. En este momento se verifican la disponibilidad de
suficiente memoria principal y cualquier dispositivo requerido.
El planificador de procesos maneja la transición de LISTO a EJECUCIÓN con base
en algún algoritmo predefinido (por ejemplo, FCFS, SJN, planificación por
prioridad, SRT o round robin, todos los cuales se analizarán en breve).
El planificador de procesos maneje a la transición de EJECUCIÓN a regreso a
LISTO, de acuerdo con algún límite de tiempo predefinido o cualquier otro criterio
–por ejemplo, una interrupción de “prioridad”.
El planificador de procesos maneja la transición de EJECUCIÓN a BLOQUEADO.
Mediante una instrucción en la tarea, como un comando de leer, escribir,
cualquier otra solicitud de E/S o alguna que requiera la obtención de una página.
El planificador de procesos maneja la transición de BLOQUEADO a LISTO.
Mediante una señal de la administrador de dispositivos de E/S, la cual indica que
se ha satisfecho la solicitud de E/S y que la tarea puede continuar. En el caso de
una obtención de ´´agina, el manejador de interrupciones de página señalará que
ésta se encuentra en la memoria y el proceso puede colocarse en la cola de
LISTO.
Por último, el planificador de procesos o de trabajos inicia la transición de
EJECUCIÓN a TERMINADO cuando 1) el trabajo se ha completado con éxito y
termina su ejecución o 2) el sistema operativo indica que ha ocurrido un error y la
tarea se da por terminada de manera prematura.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 21
Bloques de control de procesos
Cada proceso en el sistema está representado por una estructura de datos, conocida
bloque de control de procesos (PCB). Dicha estructura tiene la misma función que el
pasaporte de un viajero. El PCB (Fig. 4.3.) contiene la información básica sobe la tarea,
incluyendo lo que es, dónde va, cuánto de su procesamiento se ha completado, dónde
está almacenada y cuánto ha “gastado” en recursos.
IDENTIFICACIÓN DEL PROCESO Cada trabajo es reconocido por la identificación
del usuario y un puntero que lo conecta a su descriptor (suministrado por el planificador
de trabajos cuando el trabajo entra en el sistema y es colocado en ACEPTADO).
ESTADO DEL PROCESO Indica el estado actual del trabajo –ACEPTADO, LISTO,
EN EJECUCIÓN o BLOQUEADO- y los recursos a cargo de dicho estado.
CONDICIÓN DEL PROCESO Contiene la información necesaria para indicar la
condición actual de la tarea, como:
Palabra del estado del proceso. Es el contenido presente del contador y registro de instrucciones cuando no se está ejecutando el trabajo, per se halla en ACEPTADO, LISTO o BLOQUEADO. Si el trabajo está en EJECUCIÓN, esta información se deja sin definir.
Contenido del registro. Señala si el trabajo se ha interrumpido y está esperando par a reanudar el procesamiento.
Memoria principal. Información pertinente, que incluye la dirección donde está almacenado el trabajo y, en el caso de memoria virtual, el mapeo entre localidades virtuales y físicas de la memoria.
Recursos. Información de todo lo asignado a este trabajo. Cada recurso tiene un campo de identificación que lista su tipo y un campo que describe los detalles de su asignación, como la dirección del sector en un disco. Estos recursos pueden ser unidades de hardware (unidades de disco o impresoras, por ejemplo) o archivos.
Prioridad del proceso. Lo usan los sistemas que utilizan un algoritmo de programación por prioridad para seleccionar el trabajo que se ejecutará a continuación.
CONTABILIDAD Contiene información utilizada principalmente para efectos de
facturación y medición del rendimiento. Indica qué tipo de recursos utilizó el trabajo y
durante cuánto tiempo. Los cargos típicos incluyen:
Cantidad de tiempo del CPU utilizada del principio al final de su ejecución.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 22
Tiempo total que el trabajo estuvo en el sistema hasta que salió.
Ocupación en almacenamiento principal, el tiempo en que el trabajo estuvo en memoria hasta que terminó la ejecución. Suele ser una combinación del tiempo y del espacio utilizado; por ejemplo, en un sistema de paginación puede registrarse en unidades de páginas por segundo.
Almacenamiento secundario utilizando durante la ejecución. Esto también se registra como una combinación de tiempo y espacio utilizados.
Programas utilizados del sistema, como compiladores y editores o utilerías.
Número y tipo de operaciones de E/S, incluyendo el tiempo de transmisión de E/S, lo que abarca utilización de canales, unidades de control y dispositivos.
Tiempo utilizando en espera de la terminación de entradas y salidas.
Número de registros de entrada leídos (en concreto, los que se introdujeron en línea o que provienen de rastreadores ópticos, lecturas de tarjeta u otros dispositivos de entrada) y número de registros de salida escritos (en forma específica, los que se enviaron a la impresora de líneas). Este último distingue entre dispositivos de almacenamiento secundario y dispositivos de entrada y salida típicos.
Bloques de control de procesos y colas El bloque de control de procesos (PCB) de un trabajo se crea cuando el planificador de trabajos lo acepta y se actualiza conforme éste avanza desde el principio hasta el final de su ejecución. Las colas utilizan los PCB para llevar el control de los trabajos de la misma manera que los funcionarios de aduanas usan los pasaportes para llevar el control de los visitante internacionales. El PCB contiene los datos del trabajo necesarios para que el sistema operativo administre el procesamiento de éste. Conforme el trabajo se mueve a través del sistema, su avance se anota en el PCB. Los PCB, no los trabajos, están vinculados para formar las colas (Fig. 4.4.). Aunque cada PCB no está dibujado con detalle, imagine cada cola como una lista enlazada de PCB. Los bloques de control de procesos par cada trabajo se relacionan en la cola de LISTOS, y todos los PCB con trabajos que acaban de entrar al sistema, en la cola de ACEPTADOS. Ahora bien, las tareas que se encuentran en BLOQUEADO están vinculadas por “razón de la espera”, por lo que los PCB de los trabajos de esta categoría están vinculados en varias colas. Por ejemplo, los PCB para trabajos que esperan entradas y salidas de una unidad de disco están vinculados, en tanto que los que esperan a la impresora en línea lo están en una cola diferente. Hay necesidad de administrar estas colas de una manera ordenada, y esto queda determinado por las políticas y algoritmos de planificación del proceso.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 23
POLITICAS DE PLANIFICACION DE PROCESOS
En el entorno de multiprogramación existen por lo general más trabajos por ejecutar de
los que se pueden correr en un momento dado. Antes de que el sistema operativo pueda
planificarlos, necesita resolver tres limitaciones de sistema: 1) existe un numero finito de
recursos (como unidades de disco, impresoras y unidades de cinta); 2) algunos recursos,
una vez asignados, no pueden recibir otro trabajo (como las impresoras), y 3) algunos
recursos requieren la intervención del operador –esto es, no se pueden reasignar de
manera automática de un trabajo a otro( como las unidades de cinta).
¿Cuál es una “buena” política de planificación de procesos? Se presentan a la mente
varias opciones, pero no te que en la lista siguiente algunas se contradicen. Maximizar la producción ejecutando tantos trabajos como sea posible en un tiempo dado.
Esto es fácil si se ejecutan trabajos breves o sin interrupciones.
Minimizar el tiempo de respuesta contestando rápidamente solicitudes interactivas. Esto
sería factible ejecutando nada más trabajos interactivos y dejando que los trabajos por lotes
esperen hasta que la carga interactiva desaparezca.
Minimizar el tiempo de retorno introduciendo y sacando con rapidez trabajos completos del
sistema. Para esto se corren primero los trabajos por lotes (porque estos se pueden agrupar
para ejecutarse con mayor eficiencia que los trabajos interactivos).
Minimizar el tiempo de espera sacando los trabajos de la cola de LISTOS tan rápido como
sea posible. Esto es posible reduciendo el número de usuarios permitidos en el sistema, de
manera que el CPU esté disponible cada que un trabajo entre en la cola de LISTOS.
Maximizar la eficiencia del CPU manteniendo el CPU ocupando al 100 por ciento del
tiempo. Esto solo es viable ejecutando trabajos limitados por el CPU (no por entradas y
salidas).
Asegurar la justicia para todos los trabajos dando a todos una cantidad igual de tiempo de
CPU y de E/S. Esto es posible sin dar tratamiento especial alguno a los trabajos, sean cual
sean sus características de procesamiento o prioridad.
Como todos podemos ver, si el sistema da preferencia a un tipo de usuario, perjudica a
otro y no utiliza sus recursos con eficiencia. La decisión final es del diseñador del
sistema, que debe definir qué criterios son de mayor importancia para dicho sistema. Por
ejemplo, si usted podría decidir “maximizar la utilización del CPU, minimizar el tiempo de
respuesta y equilibrar el uso de los componentes de sistema a través de una mezcla de
trabajos limitados por entradas y salidas y CPU”. Por lo tanto, seleccionaría la política de
planificación que satisfaga con mayor precisión sus criterios.
Aunque el planificador de trabajos elige trabajos para asegurarse que las colas de
LISTOS y de E/S se mantienen equilibradas , hay casos que en un trabajo reclama al CPU
durante un tiempo muy largo, antes de emitir una solicitud de entrada y salida. Si las
solicitudes de entrada y salida se están cubriendo ( para lo cual se usa un controlador de
entradas y salidas, tema que se analiza más tarde), este uso intensivo del CPU hará que
se acumule la cola de LISTOS y al mismo tiempo se vacíen las colas de entrad y salida,
lo que crea un desequilibrio inaceptable en el sistema.
Para resolver este problema el planificador de procesos a menudo utiliza un mecanismo
de tiempo y periódicamente, cuando ha expirado un lapso predeterminado interrumpe los
procedimientos de ejecución. Cuando esto ocurre, el planificador suspende toda la
actividad de la tarea de ejecución, la vuelve a reprogramar en la cola de LISTOS y
continua su proceso más tarde. El CPU se asigna a otro trabajo que se ejecuta hasta que
ocurra una de estas tres cosa: transcurrido el lapso predeterminado, el trabajo emite un
comendo de E/S o se termina. Entonces se lo traslada a la cola de LISTOS, de
BLOQUEADOS o de TERMINADOS, respectivamente. Una solicitud de E/S se conoce como
“espera natural “en entornos de multiprogramación (permite la asignación del
procesador a otros trabajos).
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 24
Una estrategia de planificación que interrumpe el procesamiento de un trabajo y
transfiere al CPU a otro se conoce como política de planificación apropiativa y es
muy utilizada en ambientes de tiempo compartido. La alternativa naturalmente es una
política de planificación no apropiada, que funciona sin interrupciones externas
(interrupciones externas de trabajo). Por lo tanto, una vez que un trabajo captura el
procesador e inicia la ejecución, se mantiene en el estado de ejecución hasta que se
emite una solicitud de E/S (espera natural) o hasta que termina (excepto los ciclos
infinitos, que se interrumpen tanto por políticas apropiativas como por no apropiativas).
ALGORITMOS DE PLANIFICACION DE PROCESOS
El planificador de procesos se apoya en un algoritmo de planificación de procesos,
basado en una política específica para asignar el CPU y mover los trabajos por el sistema.
Los primeros sistemas operativos utilizan políticas no apropiadas, diseñadas para mover
los trabajos por lotes a través del sistema con tanta eficiencia como era posible.
La mayor parte de los sistemas actuales, con un énfasis en el uso interactivo de tiempo
de respuesta, utiliza un algoritmo que se ocupa de las solicitudes inmediatas de
usuarios interactivos.
Aquí presentamos seis algoritmos de planificación de procesos de uso muy difundido.
PRIMERO DE ENTRAR, PRIMERO DE SERVIRSE
Primero de entrar, primero de servirse (FCFS) es un logaritmo de planificación no
apropiativa que maneja los trabajos de acuerdo con su tiempo de arribo: conforme
entran son servidos. Es un logaritmo muy simple de implementar, porque utiliza un tipo
de cola FIFO, este logaritmo está bien para la mayor parte de los sistemas por lotes, pero
es inaceptable para los sistemas interactivos por los usuarios interactivos deben tener
tiempos cortos de respuesta.
Con los FCFS, conforme un nuevo trabajo entra en el sistema su PCB queda vinculado
con el final de la cola de LISTOS y es eliminado de la parte delantera de la cola cuando el
procesador queda disponible – esto es, después que ha procesado todos los trabajos que
existía en la cola.
En un sistema FCFS ciento por ciento, no existen colas de BLOQUEADO (cada trabajo se
ejecuta hasta su terminación), aunque pueden haber sistemas en que el control
(“contexto”) pasa a una espera natural (solicitud de E/S), luego de lo cual el trabajo se
reanuda al terminar la operación de E/S.
Los ejemplos que siguen suponen un entorno FCFS por completo (sin
multiprogramación). El tiempo de retorno es impresendible con la política FCFS;
considere las siguientes tres tareas:
El trabajo A tiene un ciclo de CPU de 15 milisegundos
B tiene un ciclo de CPU de 2 milisegundos
C posee un ciclo de CPU de 1 milisegundo
Para cada trabajo, el ciclo CPU contiene tanto el uso real del CPU como las solicitudes de
E/S: el tiempo de ejecución total. La línea de tiempo (diagrama de Gantt) ilustrada en la
figura 4.5 usa un algoritmo FCFS con la secuencia de llegadas A, B, C.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 25
Si los tres trabajos llegan prácticamente de manera simultánea, podemos calcular que el
tiempo de retorno para el trabajo A es 15, para el trabajo B, 17, y para C, 18. Por lo que
el tiempo de retorno promedio es:
=16,67
Sin embargo, si los trabajos llegasen en un orden diferente, digamos C, B, A, los
resultados serian según se muestra en la figura 4.6, en caso de usar el mismo algoritmo
FCFS.
En este ejemplo el tiempo de retorno para el trabajo A es 18, para B es 3, y para C, 1.
El tiempo promedio total es:
=7.3
Esto es una verdadera mejoría sobre la primera secuencia. Por desgracia, estos dos
ejemplos ilustran la desventaja principal del uso de concepto FCFS: los tiempos promedio
de retorno varían de una manera muy amplia y rara vez se minimizan. De hecho, cuando
hay tres trabajos en la cola de LISTOS, el sistema solo tiene una oportunidad en seis de
ejecutar los trabajos en la secuencia más ventajosa (C,B,A)> con cuatro trabajos las
oportunidades pasan a una en 24 y así sucesivamente.
Si un trabajo monopoliza el sistema, la repercusión de este efecto general en el
rendimiento del sistema, la repercusión de este efecto general en el rendimiento del
sistema depende de la política de planificación y de si el trabajo está limitado por el CPU
o por las entradas o salidas. Cuando un trabajo con un ciclo CPU largo ( en este ejemplo
el trabajo A0 utiliza el CPU mientras las otras esperan el momento de entrar al
procesamiento o de terminar sus solicitudes de entradas y salidas( si se utiliza un
controlador de entradas y salidas rápidamente se colmarían y el CPU quedaría ocioso( si
es un controlador de entradas y salidas). Esta situación se resuelve cuando un trabajo
limitado por entradas y salidas termina su ciclo de entradas y salidas, las colas empiezan
a moverse de nuevo y el sistema se puede recuperar del cuello de botella.
En un algoritmo FCFS puro, ninguna de estas situaciones ocurre. Sin embargo, el tiempo
de retorno es variable (impredecible). Por esta razón, FCFS es un algoritmo menos
atractivo que uno que diera servicio al trabajo más corto primero, como el siguiente ,
incluso en un entorno que no fuera de multiprogramación
SIGUE EL TRABAJO MÁS CORTO
Sigue el trabajo más corto(SJN) es un algoritmo de planificación no apropiativa (
también conocido como trabajo más corto o SJF) que maneja los trabajos con base en
la duración de su ciclo de CPU. Es muy fácil de implementar en entornos por lotes, donde
cada usuario da por adelantado el tiempo estimado de CPU requerido para ejecutar el
trabajo al inicio del mismo. Sin embargo, no funciona en sistemas interactivos, porque
los usuarios no prevén el tiempo de CPU requerido para ejecutar sus trabajos . Por
ejemplo, a continuación hay cuatro trabajos por lotes, todos en la cola de LISTOS, para
la cual el ciclo de CPU, o tiempo de ejecución, se estima como sigue:
Trabajo: A B C D
Ciclo CPU: 5 2 6 4
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 26
EL algoritmo SJN revisaría los cuatro trabajos y los programaría para procesamiento en
este orden: B, D, A, C. La línea de tiempo aparece en la figura 4.7.
El tiempo de retorno promedio es:
=9.0
Tomémonos un minuto para ver por qué este logaritmo puede demostrar ser optimo y
dar el tiempo de retorno promedio mínimo. Usaremos el ejemplo de arriba para deducir
una formula de tipo general.
En la figura 4.7 podemos ver que el trabajo B termina en su tiempo dado (2), el trabajo
D acaba en su tiempo dado, mas el tiempo que tuvo que esperar para que se ejecutara B
(4+2), el trabajo A finaliza en su tiempo dado más los tiempos de D mas B (5+4+2) y el
trabajo C termina en su tiempo dado más los de los tres anteriores (6+5+4+2) por lo
que al calcular el promedio tenemos:
Como puede ver, el tiempo para el primer trabajo aparece en la ecuación cuatro veces-
una para cada trabajo-. En forma similar, el tiempo para el segundo trabajo aparece tres
veces ( numero de trabajo menos 1); en tiempo del tercero, dos ( trabajos menos 2), y
el tiempo del cuarto, una( cantidad de trabajos menos 3).
Así pues, la ecuación anterior se puede volver a escribir de la forma:
Dado que el tiempo para e primer trabajo aparece cuatro veces en la ecuación, tiene
cuatro veces más efecto sobre el tiempo promedio que la duración del cuarto trabajo,
que solo figura una vez. Así pues, si el primer trabajo requiere el tiempo de cálculo más
breve, seguido en orden por los demás trabajos, ordenadas desde el lapso más corto
hasta el más largo, el resultado será el promedio más pequeño posible. La fórmula para
el promedio es:
Cuando n es el número de trabajos en la cola y es la longitud del ciclo CPU
para cada uno de los trabajos.
Sin embargo, el algoritmo SJN solo es óptimo cuando todos los trabajos están disponibles
al mismo tiempo y las estimaciones de CPU están al acceso y son precisas.
PLANIFICACIÓN CON PRIORIDAD
La planificación con prioridad es un algoritmo no apropiativo y uno de los algoritmos
de planificación más comunes en sistemas por lotes, aun cuando para algunos usuarios
puede dar un tiempo de retorno más lento. Este algoritmo e tratamiento preferencial a
los trabajos importantes. Permite procesar primero y en forma ininterrumpida los
programas con la prioridad más elevada hasta que sus ciclos CPU (tiempos de ejecución)
se hayan completado o hasta que ocurra una espera natural. Si hay dos o más trabajos
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 27
con prioridad igual en la cola de LISTOS, el procesador se asigna al que llego primero
(primero en entrar , primero en servirse dentro de la prioridad).
Las prioridades se pueden asignar con un administrador del sistema utilizando las
características extrínsecas de los trabajos; por ejemplo, con base en la posición del
usuario (investigaciones primero, estudiantes primero) o en entornos comerciales, se
pueden poner a la venta y el usuario que desee la prioridad más elevada para garantizar
el procesamiento más rápido posible de sus trabajos, pagara mas. Con un algoritmo por
prioridad, los trabajos suelen vincularse a una de varias colas de LISTOS mediante el
planificador de trabajos con bases a sus prioridades, por lo que el planificador de
procesos administra varias colas de LISTOS en vez de una sola. Más adelante en este
capítulo se presentan detalles sobre colas múltiples.
El administrador del procesador también puede determinar prioridades con base en
características intrínsecas de los trabajos como: Requerimientos de memoria. Es posible asignar prioridades inferiores a los trabajos que
requieren grandes cantidades de memoria que a los que solicitan pequeñas cantidades de
memoria o viceversa.
Número y tipo de dispositivos periféricos. Se asignara prioridades inferiores a los trabajos
que precisan muchos dispositivos periféricos que a los que requieren menos dispositivos.
Tiempo total de CPU. Se podría dar menor prioridad a los trabajos con un ciclo de CPU, o
tiempo de ejecución estimado largo, que a los que tiene el tiempo de ejecución estimado
breve.
Cantidad de tiempo en el sistema. Es el tiempo total transcurrido desde que se acepto el
trabajo para su procesamiento. Algunos sistemas incrementan la prioridad de los trabajos que
ya han estado en el sistema por un tiempo extraordinariamente largo, a fin de expeditar su
salida. Esto se conoce como “envejecer”.
Estos criterios se utilizan para establecer las prioridades predeterminadas de muchos
sistemas. Estas se pueden obviar en función de prioridades específicas solicitadas por los
usuarios.
Existen también esquemas de prioridades apropiadas, mismas que se analizan en la
sección de colas múltiples de este capítulo.
TIEMPO RESTANTE MÁS BREVE
El tiempo restante más breve (SRT) es la versión apropiada del algoritmo SJN. El
procesador se asigna al trabajo que este por terminar- pero incluso este trabajo se puede
hacer a un lado si un trabajo más reciente en la cola de LISTOS tiene un tiempo de
terminación mas breve.
Este algoritmo no es implementarle en un sistema interactivo, porque requiere saber por
adelantado cuanto tiempo del CPU representa la terminación de cada trabajo. A menudo
se utiliza en entornos por lotes, cuando es deseable dar preferencia a trabajos breves,
aun cuando el SRT supone más carga general que el SJN, porque el sistema operativo
tiene que vigilar con frecuencia el tiempo del CPU de todos los trabajos en la cola de
LISTOS y debe efectuar “cambios de contexto” para los trabajos que están
intercambiando (“conmutando”) en el momento de la aprobación (no necesariamente
hacia el disco, aunque esto también puede ocurrir).
Un ejemplo de la figura 4.8 muestra la forma en que funciona el algoritmo SRT con
cuatro trabajos que han llegado en rápida sucesión (con una diferencia de un ciclo de
CPU).
Tiempo de llegada: 0 1 2 3
Trabajo: A B C D
Ciclo de CPU: 6 3 1 4
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 28
En este caso el tiempo de retorno es el tiempo de terminación de cada trabajo, menos su
tiempo de llegada:
Trabajo: A B C D
Tiempo de retorno: 14 4 1 6
Por lo que el tiempo promedio es:
=6.25
¿Cómo se compara lo anterior con el problema que utiliza la política SJN no apropiativa?
La figura 4.9 utiliza la misma situación con SJN.
En este caso el tiempo de retorno es:
Trabajo: A B C D
Tiempo de retorno: 6 9 5 11
Por lo que el tiempo de retorno es:
=7.75
Note que en la figura 4.9 que inicialmente A es el único trabajo en la cola de LISTOS, por
lo que se ejecuta primero y continua hasta que esté terminado porque SJN es un
algoritmo no apropiativo. El siguiente trabajo que se va a ejecutar es C, porque cuando
termina (en el tiempo 6 ) han llegado los demás trabajos (B,C Y D).De estos tres, C tiene
el ciclo del CPU más breve, por lo que es el siguiente que se atiende, después B y por
ultimo D.
Por lo tanto, con este ejemplo, SRT en 6.25 es más rápido que SJN en 7.75. Sin
embargo, no incluimos el tiempo requerido por el logaritmo SRT para efectuar el cambio
de contexto, el cual se requiere en todos los algoritmos preferentes. Cuando se opta por
el trabajo A, toda su información de procesamiento se debe guardar en su PCB para uso
posterior, cuando prosiga su ejecución y el contenido del PCB del trabajo B se cargue en
los registros apropiados de manera que pueda volver a ejecutarse; esto es un cambio de
contexto; esta vez la información del trabajo desplazado se almacena en su PCB y el
contenido del PCB del trabajo A se carga en los registros apropiados.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 29
La forma en que se lleva a cabo el cambio de contexto depende de la arquitectura del
CPU; en muchos sistemas existen instrucciones especiales que proporcionan un rápido
guardado y restauración de la información. La conmutación esta diseñada para que se dé
con eficiencia; pero sea cual sea su rapidez, aun consume un tiempo valioso del CPU. Por
tanto, aunque el SRT aparecería como mas rápido, en un entorno real de operación sus
ventajas se ven disminuidas por el tiempo que se utiliza en los cambios de contexto. Una
comparación precisa del SRT del SJN tendría que incluir el tiempo requerido para efectuar
el cambio de contexto.
ROUND ROBIN
Round Robin es un algoritmo de planificación de procesos apropiadamente muy
difundido en sistemas interactivos, ya que es fácil de implementar y no se basa en las
características del trabajo sino en una fracción predeterminada de tiempo que se da a
cada trabajo, para asegurar que los procesos activos compartan por igual el CPU y que
ningún trabajo lo monopolice
Esta fracción de tiempo se conoce como quantum de tiempo y su tamaño es vital
para el desempeño del sistema. Por lo general varia de 100 milisegundos a 1 0 2
segundos (Pinkert & Wear, 1989).
Los trabajos se colocan en la cola de LISTOS utilizando el esquema de primero en entrar,
primero en servirse, y el planificador de procesos selecciona el primero en la parte
delantera de la cola, pone en marcha el reloj en el quantum de tiempo y asigna el CPU a
este trabajo. Si el procesamiento no ha terminado cuando expira el tiempo, se retira el
trabajo, se coloca al final de la cola de LISTOS y su información e guarda en su PCB.
En caso que el ciclo de CPU del trabajo sea más breve que el quantum de tiempo,
ocurrirá una de dos situaciones:1) si se trata del último ciclo CPU del trabajo y este ha
terminado, todos los recursos asignados al mismo se liberan y el trabajo ha completado
se devuelve al usuario; 2) si una solicitud de E/S ha interrumpido del ciclo de CPU el
trabajo, la información de la tarea se guarda en su PCB y queda vinculada al final de la
cola apropiada de entradas y salidas. Luego, una vez satisfecha la solicitud de E/S, se
devuelve al final de la cola de LISTOS para esperar asignación de CPU.
El ejemplo de la figura 4.10 ilustra un algoritmo de round robin con una fracción de
tiempo de 4 milisegundos ( se ignora las solicitudes de E/S)
Tiempo de
llegada:
0 1 2 3
Trabajo: A B C D
Ciclo de CPU: 8 4 9 5
El tiempo de retorno es el lapso en que se termina, menos el tiempo de llegada:
Trabajo A B C D
Tiempo de
retorno
20 7 24 22
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 30
Por lo que el tiempo promedio de retorno es:
Note que en la figura 4.10 el trabajo A se hizo de lado una vez porque necesitaba 8
milisegundos para completar su ciclo de CPU, en tanto que el trabajo B terminó en un
tiempo de quantum. El trabajo C se retiró dos veces porque necesitaba 9 milisegundos
para completar su ciclo de CPU y el trabajo D se retiró una vez porque requería 5
milisegundos. En su última ejecución o intercambio en la memoria, los trabajos D y C
utilizaron el CPU durante un milisegundo y terminaron antes que expirara su tiempo de
quantum, con lo que liberaron el CPU más aprisa.
La eficiencia de round robin depende del tamaño de quantum en relación con el ciclo
promedio del CPU. Si dicho quantum es demasiado grande – esto es, mayor que la
generalidad de los ciclos del CPU -, el algoritmo se reduce a un sistema FCFS. Si es
demasiado pequeño, la cantidad de cambios de contexto disminuyen la velocidad de
ejecución de los trabajos y la carga general se incrementa en forma gramática, como
demuestran los tres ejemplos de la figura 4.11. el trabaja A tiene un ciclo de CPU de 8
milisegundos. La cantidad de cambios de contexto se incrementa conforme se reduce de
tamaño el tiempo de quantum.
En la figura 4.11 el primer caso a) tiene un tiempo de quantum de 10 milisegundos y no
hay cambio de contextos (sin carga general). El ciclo del CPU termina antes que expire el
tiempo de quantum y el trabajo se ejecuta hasta terminarse. Para ese trabajo con este
quantum no hay diferencia entre los algoritmos de round robin y de FCFS.
En el segundo caso b), con un tiempo de quantum de 5 milisegundos, existe un cambio
de contexto. El trabajo se retira una vez cuando el quantum expira, por lo que existe
algo de carga general por cambio de contexto, y abra un tiempo de retorno retrasado con
base en la cantidad de otros trabajos en el sistema.
En el tercer caso c), con un tiempo de cambio de 1 milisegundo, hay siete cambios de
contexto por que el trabajo se retira cada que expira el tiempo de quantum, la carga
general se vuelve costosa y, por consiguiente, el tiempo de retorno sufre.
¿Cuál es el tamaño más adecuando de tiempo de quantum? La respuesta debe ser
predecible en este momento: depende del sistema. Si se trata de un entorno interactivo,
se espera que el sistema responda con rapidez a sus usuarios, en especial cuando hacen
solicitudes simples. Si se trata de un sistema por lotes, el tiempo de respuesta no es un
factor (el tiempo de retorno lo es) y la carga general adquiere importancia.
Existen dos reglas practicas generales para seleccionar el quantum “correcto”: 1) debe
ser lo bastante largo para permitir que 80% de los ciclos CPU se ejecuten hasta su
terminación, 2)debe ser por lo menos 100 veces más largo que el tiempo requerido para
llevar a cabo un cambio de contexto. Estas reglas se utilizan en algunos sistemas, pero
no son inflexibles (Finkel, 1986).
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 31
COLAS DE MULTIPLES NIVELES
Las colas de múltiples niveles no son en realidad un algoritmo de planificación por
separado, pero funcionan junto con varios de los esquemas ya analizados y se
encuentran en sistemas con trabajos que se pueden agrupar de acuerdo con una
característica común. Ya hemos presentado por lo menos un tipo de cola de múltiples
niveles: la de un sistema basado en prioridades con diferentes colas por cada nivel de
importancia.
Otro tipo de sistema puede reunir los trabajos limitados por CPU en una cola y los
trabajos restringidos por entradas y salidas en otra. Luego el planificador de procesos
seleccionaría de manera alterna trabajos de cada cola, para mantener el sistema
equilibrado.
Un tercer ejemplo común es el utilizado en un entorno hibrido, que acepta trabajos por
lotes he interactivos. Los primeros se ponen en una cola llamada cola de “segundo plano”
en tanto que los segundos se ubican en una cola de “primer plano” y se tratan mas
favorablemente que los correspondientes a las colas de segundo plano.
Todos estos ejemplos tiene algo en común: la política de planificación se basa en algún
esquema predeterminado, que da un tratamiento especial a los trabajos de cada cola. En
cada cola, los trabajos se asignan de manera FCFS.
Las colas de múltiples niveles plantean algunas preguntas interesantes.
¿El procesador queda asignado a los trabajos de la primera cola hasta que se vacía, antes de
pasar a la siguiente cola, o se “mueve” de una cola a otra, hasta servir el último trabajo de la
última y regresa para servir el primer trabajo de la primera cola, o algo intermedio?
¿Es justa para los que han ganado o pagado por una prioridad más elevada?
¿Es justa para las que se encuentran en una cola de baja prioridad?
Si el procesador se asigna a los trabajos de la primera cola y nunca se vacía, ¿Cuándo se
atenderán los trabajos de las últimas colas?
¿Los trabajos de las últimas colas pueden obtener “algún premio por buen comportamiento” y
terminar pasando a colas mejore?
Las respuestas dependen de la política utilizada por el sistema para atender las colas.
Existen cuatro métodos principales para el movimiento: no permitir desplazamiento
alguno entre colas, mover trabajos de una a otra cola, pasarlas de una cola a otra cola e
incrementar los quanta de tiempo para colas “inferiores” y dar un tratamiento especial a
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 32
los trabajos que han estado en el sistema durante largo tiempo. Esto último se conoce
como envejecimiento. Los siguientes ejemplos de casos se derivan de Yourdon (1972).
CASO 1, NINGUN MOVIMIENTO ENTRE COLAS. La falta de movimiento entre colas es
una política muy simple, que premia a las que tienen trabajos de alta prioridad. El
procesador se asigna de manera FCFS a los trabajos en la cola de alta prioridad y solo
cuando estas se han vaciado se ocupa de los trabajos en las colas de baja prioridad. Esta
política se puede justificar si existen pocos usuarios de trabajos de alta prioridad por lo
que las colas superiores se vacían con rapidez y permiten que el procesador utiliza una
cantidad razonable de tiempo en la ejecución de trabajos de baja prioridad.
CASO 2, MOVIMIENTO ENTRE COLAS. El desplazamiento entre colas es una política
que ajusta las prioridades asignadas a cada trabajo: una vez que los de alta prioridad
están en el sistema, se tratan como todos los demás (su prioridad inicial puede ser
favorable).
Cuando ocurre una interrupción de quantum de tiempo, el trabajo se retira y se mueve al
final de la siguiente cola inferior. También cabe incrementar la prioridad de un trabajo –
por ejemplo, cuando emite una solicitud de entrada y salida antes que acabe su quantum
de tiempo.
Esta política es la más justa en un sistema en que los trabajos se manejan de acuerdo
con sus características del ciclo de computo: limitados por CPU o por entradas y salidas.
Esto supone que un trabajo que excede su quantum de tiempo está restringido por el
CPU y puede requerir mas asignación de este que aquel que solicita entradas y salidas
antes que expire el quantum de tiempo. Por lo tanto, los trabajos limitados por CPU se
colocan al final de la siguiente cola inferior cuando se han quitado debido a la expiración
del quantum, en tanto que una vez que termina su solicitud de entrada salida, los
trabajos restringidos por entradas y salida se devuelven al final de la siguiente cola de
nivel alto. Esto facilita los trabajos limitados por entradas y salidas (y es bueno en
sistemas interactivos).
CASO 3, QUANTUM DE TIEMPO VARIABLE POR COLA. El quantum de tiempo
variable por cola es una variable del movimiento entre colas y permite un tiempo de
retorno más rápido de los trabajos limitados por CPU.
En el esquema, a cada cola se da un quantum de tiempo dos veces más largo que la cola
anterior. La cola más elevada puede tener un quantum de 100 milisegundos, por lo que
la segunda cola tendrá un quantum de 200 milisegundos, la tercera de 400 milisegundos,
etc. Si hay suficientes colas, las más baja pudiera tener un quantum de tiempo
relativamente largo, de 3 segundos o más.
Si un trabajo no termina su ciclo de CPU en el primer quantum de tiempo, es movido al
final de la siguiente cola de nivel inferior; luego cuando se le vuelve a asignar
procesador, su ejecución ocupa dos veces más que antes. Con este esquema, un trabajo
limitado por CPU puede ejecutarse durante períodos mas y mas largos, mejorando así
sus oportunidades de terminar mas a prisa.
CASO 4, ENVEJECIMIENTO. Se utiliza para asegurar que los trabajos en las colas de
nivel inferior completaran su ejecución. El sistema operativo controla el tiempo de espera
de cada trabajo y cuando uno se hace demasiado antiguo – esto es, cuando alcanza
cierto tiempo - , se cambia a la siguiente cola más alta, y así sucesivamente, hasta que
llega a la cola superior. Una política de envejecimiento más drástica mueve el trabajo
viejo desde la cola más baja hasta el extremo de la cola más alta. Sin importar su
implementación real, una política de envejecimiento protege contra posposición
indefinida de trabajos muy grandes. Como usted podía espera la posposición
indefinida significa que la ejecución de un trabajo se retrasa de manera indefinida,
porque una y otra vez se retira para procesar otros trabajos (todos conocemos ejemplos
de un trabajo desagradable que ha sido pospuesto de manera indefinida para dar tiempo
a un pasatiempo más atractivo). Por último, la situación podría llevar a la inanición del
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 33
trabajo “envejecida”. La posposición indefinida es un problema importante al asignar
recursos y se analizara a detalle en el capítulo 5.
MEMORIA CACHE
La memoria cache es una versión de rápido acceso, diseñada para resolver las
diferencias de velocidad entre un CPU muy rápido y una memoria principal más lenta. Lo
hace almacenando una copia de los datos de uso frecuente en una memoria de fácil
acceso en vez de la memoria principal, cuyo acceso es más lento. Un tamaño de cache
razonablemente pequeño puede general mejorías significativas en el rendimiento
(Stallings, 1998).
Dado que la memoria cache es un pequeño espacio que contiene relativamente pocos
datos, el procesador tiene acceso a sus datos e instrucciones con mucha mayor rapidez
que si tuviera que recuperarlos de la memoria principal (Stair, 1999). La memoria cache
se localiza entre el procesador y la memoria principal (figura 4.12).
La memoria cache aprovecha el principio de localidad de referencia, que se describió en
los capítulos de la administración de la memoria. Otro ejemplo del mismo principio es un
archivo de marca libros en un navegador de web que almacena direcciones de uso
frecuente; esto es, el archivo marca libros solo almacena un porcentaje pequeño de las
direcciones validas de web, pero las posibilidades son relativamente elevadas de que
usted las visite.
Un controlador de cache determina la frecuencia con que se utilizan los datos, transfiere
los que se usan a menudo a la memoria cache y los elimina cuando identifica datos de
uso aun más constante (para una explicación detallada de los controladores lea el
capítulo 7).
Los datos en la memoria cache se deben considerar como temporales. En caso de una
falla de energía, se pierden y no se pueden recuperar a diferencia de los datos escritos
en el almacenamiento secundario.
UNA PALABRA SOBRE INTERRUPCIONES
Las interrupciones – o fallas – se producen cuando el administrador de la memoria
emite interrupciones de página para dar entrada a solicitudes de tarea. Existe otro tipo
de interrupción, que ocurre cuando el quantum de tiempo expira y el procesador es
desasignado del trabajo en ejecución y asignado a otro.
Existen otras interrupciones causadas por hechos internos al proceso. Las interrupciones
de entrada y salida se emiten cuando se manda un comando de READ ODEWRITE (los
explicaremos en detalle en el capítulo siguiente). Las interrupciones internas, o
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 34
interrupciones sincrónicas, también ocurren como resultado directo de la operación
aritmética o instrucción de trabajo en proceso.
Las operaciones aritméticas y legales, como las que se dan a continuación, pueden
general interrupciones:
Intentos de dividir entre cero.
Operaciones de punto flotante que generen un sobre flujo (o desbordamiento) o
un sub flujo.
La suma o la sustracción de punto fijo que cause un sobre flujo aritmético.
Las instrucciones ilegales de trabajos como las que siguen también pueden generar
interrupciones:
Intento de tener acceso a localidades de almacenamiento protegidas o
inexistentes.
Intentos de utilizar un código de operación no definido.
Operación sobre datos inválidos.
Intentos de efectuar cambios al sistema, como tratar de modificar el tamaño del
quantum de tiempo.
El programa de control que maneja la secuencia de interrupción de los hechos se conoce
como manejador de interrupciones. Cuando el sistema operativo detecta un error no
recuperable, el manejador de interrupciones sigue esta secuencia:
1. Se describe y se almacena el tipo de interrupción – para enviarlo al usuario como
mensaje de error –.
2. Se guarda el estado del proceso interrumpido, incluyendo el valor del contador del
programa, la especificación del modo y los contenidos de los registros.
3. Se procesa la interrupción: el mensaje de error y el estado del proceso
interrumpido se envían al usuario; la ejecución del programa se detiene, cualquier
recurso asignado al trabajo se libera y el trabajo sale del sistema.
4. El procesador reanuda una operación normal.
Si estamos tratando con interrupciones internas únicamente, que no son recuperables, el
trabajo termina en el paso 3, sin embargo, cuando el manejador de instrucciones trabaja
con una interrupción de E/S, un quantum de tiempo u otra interrupción recuperable, el
paso 3 detiene el trabajo y lo mueve a la cola apropiada de dispositivos de entrada y
salida o a la cola de LISTOS (“fuera de tiempo”). Más tarde, cuando acaba la solicitud de
entrada y salida, el trabajo es devuelto a la cola de LISTOS. Si se trata de un tiempo
fuera (interrupción de quantum) el trabajo (o proceso) ya está en la cola de LISTOS.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 35
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 36
ADMINISTRACIÓN DE LOS PROCESOS
Ya hemos visto dos aspectos de compartir recursos, la administración de la memoria y
compartir el procesador. En este capítulo encararemos los problemas que se presentan
cuando muchos procesos compiten por relativamente pocos recursos y el sistema no es
capaz de dar servicio a todos los procesos en el sistema. Una carencia de
sincronización de los procesos puede dar como resultado dos condiciones extremas:
el bloqueo mutuo o la inanición.
En los primeros sistemas operativos, el bloqueo mutuo se conocía con la frase más
descriptiva de abrazo mortal. Es un enredo a nivel del sistema de solicitudes de
recursos que se inicia cuando dos o más trabajos se ponen en espera, cada uno
aguardando que quede disponible un recurso vital. El problema se genera cuando otros
trabajos ocupan los recursos que necesitan los primeros y no pueden liberarlos y seguir
corriendo porque también aguardan otros recursos que no están disponibles. Todos los
trabajos se detienen. El bloqueo mutuo es completo si el resto del sistema también llega
a un paro total. Por lo general el sistema operativo es incapaz de resolver la situación y
requiere intervención exterior, ya sea de los operadores o usuarios, que deben tomar
acciones drásticas, como retirar o terminar a mano un trabajo.
Es más fácil describir un bloqueo mutuo con un ejemplo: una escalera angosta en un
edificio (regresaremos a este ejemplo a lo largo del capítulo). La escalera se construyó
como salida en caso de incendio, pero las personas que trabajan en el edificio a menudo
la utilizan en vez de esperar los elevadores, que son lentos. El tráfico en ella se mueve
bien, a menos que necesiten pasar dos personas que se desplazan en direcciones
opuestas, que que solo hay sitio para una en cada escalón. En este ejemplo, la escalera
es el sistema y los descansos son los recursos. Existe un descanso entre cada piso y
tiene la suficiente amplitud para que lo compartan varias personas; pero las escaleras no
lo son y solo se pueden asignar a un usuario a la vez. Ocurren problemas cuando alguien
que sube se encuentra con alguien que baja y ninguno acepta regresar a un lugar más
amplio. Esto crea un bloqueo mutuo, que el objeto de gran parte de nuestro análisis
sobre la sincronización de los procesos.
Por otra parte, si unas cuantas personas pacientes esperan en el descanso a que se
aclare el tráfico en sentido contrario, y dicha situación no ocurre nunca, pueden esperar
ahí para siempre. Esto es la inanición, un caso extremo de posposición indefinida, y se
analizará cerca del final de este capítulo.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 37
BLOQUEO MUTUO
El bloqueo mutuo es más serio que la posposición indefinida o inanición porque afecta
más de un trabajo. Dado que los recursos están en uso, la totalidad del sistema (no
unos cuantos programas) queda afectado. El ejemplo que más se utiliza para ilustrar
este caso es un congestionamiento de tráfico.
Como se muestra en la figura 5.1, no existe una solución simple e inmediata para el
bloqueo mutuo: nadie puede avanzar mientras alguien no se quite del camino, pero
nadie se puede quitar del camino en tanto alguien no avance o la parte trasera de una
línea retroceda. Es obvio que se requiere la intervención exterior para eliminar uno de
los cuatro vehículos de una intersección o hacer que una línea retroceda; solo entonces
se puede resolver el bloqueo mutuo.
Los bloqueos mutuos eran pocos frecuentes en los primeros sistemas por lotes porque los
usuarios incluían en las tarjetas de control de los trabajos que precedían al trabajo una
lista completa de los recursos del sistema (unidades de cinta, discos, impresoras, etc)
requeridos para ejecutarlo. El sistema operativo se aseguraba que todos los recursos
solicitados estuvieran disponibles y asignados a dicho trabajo, antes de pasar el trabajo a
la cola de LISTOS y no los liberaba mientras el trabajo no estuviera completo. El trabajo
no pasaba a la cola de LISTOS mientras los recursos no estuvieran disponibles.
Los bloqueos mutuos se volvieron más frecuentes con el uso creciente de los sistemas
interactivos, porque éstos son más flexibles que los entornos por lotes. Por lo general,
dichos sistemas mejoran el uso de los recursos al compartirlos en forma dinámica; más
esta capacidad de compartir recursos también incrementa la posibilidad de los bloqueos
mutuos.
Siete casos de bloqueo mutuo
Un bloqueo mutuo por lo general ocurre cuando recursos insustituibles que no se pueden compartir – como archivos, impresoras o unidades de cinta- se asignan a trabajos que terminarán por requerir otros recursos incompartibles e insustituibles – esto es, recursos bloqueados por otros trabajos-. Sin embargo, los bloqueos mutuos no se limitan a archivos, impresoras y unidades de cinta; también pueden ocurrir en recursos compartibles, como discos y bases de datos, según veremos en los ejemplos que siguen.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 38
CASO 1: BLOQUEOS MUTUOS EN SOLICITUDES DE ARCHIVO Si se permite que
las tareas soliciten y conserven archivos durante la duración de su ejecución, puede
ocurrir un bloqueo mutuo. La figura 5.2 muestra el bloqueo mutuo mediante una
representación modificada de gráficas dirigidas, que se analiza en mayor detalle en la
sección relativa a los “modelos de bloqueo mutuo”.
Por ejemplo, considere el caso de una empresa de construcción de casas habitación con
dos programas de aplicación, compras (P1) y ventas (P2), activos al mismo tiempo. Para
actualizar transacciones cotidianas cada uno necesita tener acceso a dos archivos,
inventarios (F1) y proveedores (F2). Un día el sistema se bloquea mutuamente cuando
ocurre la siguiente secuencia de circunstancias.
1. Compras (P1) accede el archivo de proveedores (F2) para colocar un pedido
para más madera.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 39
2. Ventas (P2) accede el archivo de inventarios (F1) para reservar los
componentes que se requerirán a fin de construir la casa habitación pedida
ese día.
3. Compras (P1) no libera el archivo de proveedores (F2), pero solicita el archivo
de inventarios (F1) para comprobar la cantidad de madera a mano, antes de
colocar su pedido por más, pero P1 está bloqueado porque P2 tiene a F1.
4. Mientras tanto, ventas (P2) no libera el archivo de inventarios (F1), pero
solicita el archivo de proveedores (F2) para verificar el programa de un
subcontratista. Al llegar a este punto P2 también queda bloqueado porque F2
está en manos de P1.
Cualesquiera otros programas que requieran F1 o F2 se pondrán en espera por el tiempo
que esta situación continúe. Este bloqueo se mantendrá hasta que se retire o quite a la
fuerza uno de los dos programas y su archivo quede liberado. Solo entonces el otro
programa podrá continuar y el sistema regresar a la normalidad.
CASO 2: BLOQUEOS MUTUOS EN BASES DE DATOS También puede ocurrir un
bloqueo mutuo si dos procesos acceden y bloquean registros de una base de datos.
Para apreciar el escenario que sigue es necesario recordar que las consultas y
transacciones de las bases de datos suelen ser procesos relativamente breves que
buscan o modifican partes de una base de datos. Por lo general las solicitudes llegan al
azar y pueden estar entrelazadas de manera arbitraria.
El bloqueo es una técnica utilizada para garantizar la integridad de los datos, a través
de la cual el usuario bloqueo a los demás usuarios mientras está trabajando con la base
de datos. El bloqueo puede efectuarse en tres niveles: en toda la base de datos durante
la duración de la solicitud, en una subsección de la misma o en el registro individual
hasta que el proceso termine, si se bloquea la base de datos ( la solución más extrema y
de mayor éxito) se impide que ocurran los bloqueos mutuos, pero el acceso a la base de
datos queda restringido a un usuario a la vez y, en un entorno multiusuario, los tiempos
de respuesta de reducen de manera significativa; por tanto, esto no suele ser una
solución aceptable, cuando solo se bloquea parte de la base de datos, el tiempo de
acceso mejora, pero s incrementa la posibilidad de un bloqueo mutuo porque diferentes
procesos a veces necesitan trabajar con varias porciones de las bases de datos al mismo
tiempo.
A continuación presentamos un sistema que bloquea cada registro cuando es accedido
hasta que el proceso se completa. Existen dos procesos (P1 y P2), cada uno necesita
actualizar dos registros (R1 y R2) y la secuencia que sigue nos lleva a un bloqueo mutuo:
1. P1 accede a R1 y lo bloquea.
2. P2 usa a R2 y lo bloquea.
3. P1 solicita a R2, que está bloqueado por P2.
4. P2 pide R1, que está bloqueado por P1.
Una alternativa es no utilizar bloqueo; pero esto no lleva a otras dificultades. Si no se
utilizan bloqueos para preservar la integridad, los registros actualizados en la base de
datos pueden incluir solo parte de los datos y su contenido dependería del orden en que
cada proceso termina su ejecución. Esto se conoce como “carrera” entre procesos y se
ilustra en el ejemplo que sigue en la figura 5.3.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 40
Digamos que usted es un estudiante veterano, que sabe que la universidad conserva la
mayor parte de sus archivos en una base de datos que se puede acceder mediante varios
programas, incluyendo uno para calificaciones y otro que lista direcciones personales.
Digamos que usted es un estudiante que cambia de domicilio, por lo que le envía su
nueva dirección a la universidad a final del semestre de otoño, poco tiempo después que
las calificaciones han sido emitidas. Un día fatal, ambos programas corren para tener
acceso a su registro en la base de datos.
1. El proceso de notas o calificaciones (P1) es el primero en tener acceso y copia el
registro (R1) en su área de trabajo.
2. El proceso de direcciones (P2) entra a su registro (R1) y lo copia a su área de
trabajo.
3. P1 modifica a R1 introduciendo sus notas para el otoño y calculando su nuevo
promedio.
4. P2 cambia a R1 actualizando el campo de la dirección.
5. P1 termina su trabajo primero y vuelve a escribir su versión de su registro de
regreso en la base de datos. Sus calificaciones o notas han sido modificadas, pero
no su dirección.
6. P2 termina y vuelve a escribir su registro actualizado de regreso a la base de
datos. Su dirección ha sido modificada, pero no sus notas. De acuerdo con la
base de datos, usted no asistió a la escuela durante ese semestre.
Si invertimos el orden y decimos que P2 ganó la carrera, sus notas estarán actualizadas,
pero no su dirección. Según su éxito en el aula, usted puede preferir un mal al otro,
pero desde el punto de vista del sistema operativo, cualquiera de las alternativas es
inaceptable, porque permite que datos incorrectos contaminen la base de datos. El
sistema no puede permitir que la integridad de la base de datos dependa de una
secuencia aleatoria de circunstancias.
CASO 3: BLOQUEOS MUTUOS EN LA ASIGNACIÓN DE DISPOSITIVOS
DEDICADOS El uso de un grupo de dispositivos dedicados puede bloquear el sistema.
Digamos que dos usuarios del consejo local de educación están ejecutando sendos
programas (P1 y P2) y ambos terminarán por requerir dos unidades de cinta para copiar
los archivos de una cinta a otra. El sistema es pequeño y cuando los dos programas se
han iniciado, solo están disponibles dos unidades de cinta, asignadas con base en “según
se solicite”. Pronto ocurre la secuencia que sigue:
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 41
1. P1 solicita la unidad de cinta 1 y la obtiene.
2. P2 pide la unidad de cinta 2 y la obtiene.
3. P1 solicita la unidad de cinta 2 pero está bloqueada.
4. P2 pide la unidad de cinta 1 más está bloqueada.
Ninguno de los trabajos puede continuar porque están esperando que termine el otro y
que libere su unidad de cinta, un hecho que jamás ocurrirá. Una serie similar de
circunstancias puede bloquear mutuamente cualquier grupo de dispositivos dedicados.
CASO 4: BLOQUEOS EN LA ASIGNACIÓN MÚLTIPLE DE DISPOSITIVOS Los
bloqueos no ocurren nada más procesos que compiten por el mismo tipo de dispositivo;
pueden presentarse cuando varios procesos solicitan y se quedan con dispositivos
dedicados, en tanto que otros procesos actúan de manera similar a la mostrada en la
figura 5.4.
Considere el caso de una empresa de diseño de ingeniería con tres programas (P1, P2 y
P3) y tres dispositivos dedicados: unidad de cinta, impresora y graficador. La siguiente
secuencia de circunstancias resultará en un bloqueo mutuo:
1. P1 solicita y obtiene la unidad de cinta.
2. P2 pide y obtiene la impresora.
3. P3 solicita y obtiene el graficador.
4. P1 pide la impresora pero se encuentra bloqueada.
5. P2 solicita el graficador pero está bloqueado.
6. P3 pide la unidad de cinta pero se encuentra bloqueada.
Igual que en los ejemplos anteriores, ninguno de los trabajos puede continuar porque
cada uno espera un recurso ocupado por otro.
CASO 5: BLOQUEOS MUTUOS EN OPERACIONES PERIFÉRICAS SIMULTÁNEAS EN
LÍNEAAunque en el ejemplo anterior la impresora era un dispositivo dedicado, la mayor
parte de los sistemas han transformado la impresora en un dispositivo compartible (
también conocido como “dispositivo virtual”) al instalar un dispositivo de alta velocidad,
un disco, entre ella y el CPU. El disco acepta las salidas de varios usuarios y actúa como
un área de almacenamiento temporal para todas las salidas, hasta que la impresora
puede aceptarlas. Este proceso se conoce como operaciones periféricas simultáneas
en línea (spooling). Si antes de empezar a imprimir la impresora necesita todas las
salidas de una tarea, pero el sistema de spool llena un espacio disponible de disco con
una salida parcialmente completada, puede ocurrir un bloqueo mutuo. Esto sucede como
sigue.
Digamos que falta una hora antes de que se necesite el gran proyecto para la clase de
computación. Veintiséis programadores acelerados teclean sus cambios finales y, con
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 42
unos cuantos minutos disponibles, emiten comandos de impresión. El manejador de
spool recibe las páginas de cada estudiante una por una, pero le llegan por separado,
varias páginas uno, dos, etc. La impresora está lista para imprimir el primer programa
completo que obtiene, pero conforme el manejador de spool (esto es, el operador
periférico simultáneo en línea) recorre sus archivos, obtiene la primer página de muchos
programas, pero no tiene la última de ninguno. Por desgracia, el spool está lleno de
salidas semicompletadas, por lo que no puede aceptar otra página; pero ninguno de los
trabajos se puede imprimir ( lo que liberaría su espacio en disco) porque la impresora
solo acepta archivos de salida completos. Una situación desafortunada.
Este escenario no se limita a impresoras. Cualquier parte del sistema que se base en
spooling, como el que maneja los trabajos de entrada o transfiere archivos en una red,
es vulnerable ante un bloqueo mutuo.
CASO 6: BLOQUEOS AL COMPARTIR DISCOS Los discos están diseñados para ser
compartidos, por lo que no es raro que dos procesos usen áreas diferentes del mismo
disco. Sin controles para regular el uso de la unidad de disco, los procesos en
competencia podrían enviar comandos conflictivos y bloquear el sistema, como se ve en
al figura 5.5.
Por ejemplo, en una empresa de seguros el sistema lleva a cabo muchas transacciones
cotidianas. Una de las siguientes series de circunstancias bloqueo el sistema:
1. El proceso P1 desea mostrar un pago, por lo que emite un comando para leer el
saldo, que está almacenado en el cilindro 20 de un paquete de discos.
2. Mientras la unidad de control está moviendo el brazo hacia el cilindro 20, P1 se
pone en espera y el canal de entradas/salidas queda libre para procesar la
siguiente solicitud de entrada/salida.
3. P2 obtiene el control del canal de entradas/salidas y emite un comando para
escribir el pago de otra persona en un registro almacenado en el cilindro 310. Si
el comando “ no está bloqueado” P2 quedará en espera, mientras la unidad de
control mueve el brazo hasta el cilindro 310.
4. Puesto que P2 está “ en espera” el canal está libre y P1 puede capturarlo de
nuevo, lo que vuelve a confirmar su comando de “ leer del cilindro 20”.
5. Dado que el último comando de P2 ha obligado al mecanismo del brazo hasta el
cilindro 310, la unidad de control de disco empieza a reubicarlo para el cilindro 20
a fin de satisfacer a P1. El canal de entradas/salidas será liberado, porque P1 ha
quedado de nuevo en espera, por lo que P2 puede capturarlo. Este emite un
comando WRITE y descubre que hay necesidad de reubicar el mecanismo del
brazo.
Como resultado, el brazo está en un estado continuo de movimiento, pasando de un lado
a otro entre el cilindro 20 y el cilindro 310 conforme responde a los dos comandos en
competencia, sin poder satisfacerlos.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 43
CASO 7: BLOQUEOS MUTUOS EN UNA RED Una red congestionada – o que
ha llenado un porcentaje grande de su buffer de entrada/salida- se puede bloquear
totalmente si no tiene protocolos para controlar el flujo de mensajes a través de la red
(Fig.5.6).
Por ejemplo, un centro de procesamiento de palabras de tamaño medio tiene siete
computadoras en red, cada una con nodos diferentes. C1 recibe mensajes de los nodos
C2, C6 y C7 y solo envía mensajes a uno: C2. C2 recibe los mensajes de los nodos C1,
C3 y C4 y nada más manda mensajes a C1 y a C3. La dirección de las flechas de la
figura 5.6 señala el flujo de los mensajes.
Los mensajes recibidos por C1 desde C6 y C7 y destinados a C2 se almacenan en una
cola de salida.
Los mensajes recibidos por C2 de C3 y de C4 destinados a C1 se almacenan en una cola
de salida. Conforme se incrementa el tráfico, aumenta la longitud de cada cola de salida,
hasta que se llena el espacio disponible para las colas. En este punto C1 ya no puede
aceptar más mensajes (de C2 o de cualquier otra computadora) porque no existe más
espacio disponible para almacenarlas. Por lo misma razón, C2 no puede aceptar más mensajes de C1 para ninguna otra computadora, ni siquiera una solicitud para enviar. La trayectoria de comunicación entre C1 y C2 se bloquea y en vista de que C1 solo puede recibir mensajes de C6 y C7, estos caminos también se han bloqueado. C1 no puede enviar palabras hasta C2 respecto al problema, por lo que el bloqueo mutuo no se puede resolver sin intervención del exterior.
CONDICIONES PARA EL BLOQUEO MUTUO
En cada uno de estos siete casos, el bloqueo comprendió la interacción de varios
procesos y recursos, pero la ocurrencia simultánea de cuatro condiciones precedió cada
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 44
bloqueo mutuo, condiciones que el sistema operativo u otro sistema podría haber
reconocido: exclusión mutua, retención de recursos, no apropiatividad y espera circular.
Para ilustrarnos, revisemos el ejemplo de la escalera del principio del capítulo e
identifiquemos las cuatro condiciones para un bloqueo mutuo.
Cuando dos personas se encuentran entre descansos no pueden pasar, ya que en los
escalones sólo cabe una a la vez. Exclusión mutua, el acto de permitir que sólo una
persona (o proceso) tenga acceso a un escalón (un recurso dedicado), es la primera
condición del bloqueo mutuo.
Cuando dos personas se encuentran en las escaleras y cada una se empeña en no
retirarse y espera a que lo haga lo otra, esto es un ejemplo de retención de recursos
(en contraste con compartir recursos), la segunda condición para el bloqueo mutuo.
En este ejemplo, cada escalón está dedicado al que sube (o al que baja); queda asignado
al que lo ocupe tanto tiempo como sea necesario. Esto se conoce como no
apropiatividad, la carencia de una reasignación temporal de los recursos, y es la
tercera condición para el bloque mutuo.
Estos tres llevan a la cuarta condición o espera circular, en que cada persona (o
proceso) inmerso en la espera de que la otra libere el escalón (o recurso), por lo que por
lo menos una será capaz de continuar y llegar a destino.
Se requieren las cuatro condiciones para que ocurra el bloqueo mutuo y siempre que las
cuatro estén presentes, éste continuará; pero si se puede eliminar una, el bloqueo mutuo
se resolverá. De hecho, es posible prevenir que las cuatro condiciones se den al mismo
tiempo, con lo cual se evitarían los bloqueos mutuos; pero aunque esta idea es obvia no
es fácil de implementar.
MODELADO DE BLOQUEOS MUTUOS
Holt (1972) demostró la forma en que las cuatro condiciones se pueden modelar
utilizando gráficas dirigidas (las usamos con modificaciones en las figuras 5.2 y 5.4).
Éstas utilizan dos tipos de símbolos: procesos, representados por círculos y recursos,
denotados por cuadrados. Una línea sólida de un recurso hacia un proceso significa que el
proceso retiene dicho recurso; una línea sólida de un proceso a un recurso, que un
proceso espera dicho recurso. La dirección de la flecha indica el flujo. Si hay un ciclo en
la gráfica, entonces existe un bloqueo mutuo que abarca los procesos y los recursos del
ciclo, según se observa en la figura 5.7c).
El sistema que tiene tres procesos: P1, P2 y P3, y tiene tres recursos: R1, R2 Y R3, cada
uno diferente: impresora, unidad de cinta y graficador. Dado que no hay un orden
específico en el cual se manejan las solicitudes, tenemos tres escenarios posibles, así que
utilizaremos gráficas para ayudarnos a detectar cualquier bloque mutuo.
ESCENARIO 1 La secuencia de circunstancias del primer escenario aparece en la
tabal 5.1. La gráfica dirigida se encuentra en la figura 5.8.
Note en la gráfica dirigida que no existen ciclos. Por lo tanto, podemos concluir con
seguridad que no es factible un bloqueo, aun cuando cada proceso solicite todos los
recursos, si los recursos se liberan antes que los solicite el siguiente proceso.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 45
ESCENARIO 2 Ahora, consideremos un segundo escenario de secuencia de
circunstancias como la mostrada en la tabla 5.2. La gráfica dirigida aparece en la figura
5.9.
En la gráfica dirigida hay un bloque mutuo porque todos los procesos esperan un recurso
que está detenido por otro proceso, pero ninguno quedará liberado sin la intervención del
operador.
ESCENARIO 3 El tercer escenario se muestra en la tabla 5.3. Según se puede ver
en la figura 5.10, los recursos se liberan antes que ocurra el bloqueo mutuo.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 46
OTRO EJEMPLO En los ejemplos presentados hasta ahora hemos examinado casos
en que uno o más recursos de diferentes tipos se asignaron a un proceso. Sin embargo,
se pueden expandir las gráficas para incluir varios recursos del mismo tipo, como
unidades de cinta, que se pueden asignar de manera individual o en grupos al mismo
proceso. Estas gráficas agrupan los dispositivos del mismo tipo en una entidad –en la
figura 5.11 se usa un rectángulo y las flechas muestran los vínculos entre el único
recurso y los procesos que lo utilizan.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 47
La figura 5.11 de un ejemplo de un agrupamiento con tres recursos del mismo tipo, como
tres unidades de disco, cada uno asignado a tres procesos. Aunque la figura 5.11 a)
parece ser estable ( no puede ocurrir bloqueo mutuo), no es el caso, porque si los tres
procesos solicitan un recurso más, sin liberar el que están utilizando, el bloqueo mutuo
ocurrirá, como se muestra en la figura 5.11 b).
Estrategias para el manejo de bloqueos
Como hacen ver estos ejemplos, las solicitudes y liberaciones se reciben en un orden
impredecible, lo que hace muy difícil diseñar una política preventiva a toda prueba. En
general, los sistemas operativos utilizan una de tres estrategias para manejar bloqueos
mutuos:
Impedir que ocurra alguna de las cuatro condiciones.
Evitar el bloqueo si se hace probable.
Detectarlo cuando ocurre y recuperarse del mismo con gracia.
PREVENCIÓN
Para impedir un bloqueo mutuo, el sistema operativo debe eliminar una de las cuatro
condiciones necesarias, tarea complicada porque no es posible suprimir la misma
condición de todos los recursos.
La exclusión mutua es necesaria en cualquier sistema de cómputo, porque algunos
recursos como la memoria, el CPU o los dispositivos dedicados, deben quedar asignados
exclusivamente a un usuario a la vez. En el caso de dispositivos de entrada/salida como
las impresoras, la exclusión mutua puede obviarse mediante el uso de spool, de manera
que la salidas de muchas tareas se pueda almacenar al mismo tiempo en archivos
temporales en el uso de spool separados; luego, cada archivo de salida completo se
manda imprimir cuando el dispositivo está listo. Sin embargo, quizás estemos
sustituyendo un tipo de bloqueo mutuo (caso 3): bloqueos mutuos de asignación de
dispositivos dedicados) por otro (caso 5: bloqueos mutuos en operaciones periféricas
simultáneas en línea).
La retención de recursos, es decir, cuando una tarea conserva un recurso mientras
espera otro que no está disponible – podría evitarse obligando a cada trabajo a solicitar,
en el momento de la creación, todos los recursos que necesitará. Por ejemplo, si se da
tanta memoria como necesita cada trabajo en un sistema por lotes, el número de taras
activas quedará regido por cuantas quepan en la memoria. Es una política que reducirá
de manera significativa el grado de multiprogramación. Además, los dispositivos
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 48
periféricos quedarían ociosos porque se asignarían a un trabajo aunque no se utilizarán
todos el tiempo. Como hemos dicho, esto funcionaba en entornos por lotes, aunque
reducía el uso efectivo de los recursos y restringía la cantidad de multiprogramación.
Pero no es tan adecuado en sistemas interactivos.
La no apropiatiavidad podría soslayarse permitiendo que el sistema operativo desasigne
recursos de los trabajos. Esto se puede efectuar si el estado del trabajo se guarda y
restaura con facilidad cuando, por ejemplo, se retira un trabajo en un entorno round
robin o se intercambia la página a un almacenamiento secundario en un sistema de
memoria virtual. Por otra parte, el retiro o sustitución de un dispositivo de entra/salida
dedicado (impresora, graficador o unidades de cinta, etc.) o de los archivos durante el
proceso de modificación puede requerir algunas tareas de recuperación muy
desagradables.
La espera circular se puede obviar si el sistema operativo impide la formación de un
círculo. Havender (1968) propuso una solución de este tipo, la cual se basa en un
sistema de numeración para los recursos: impresora= 1, disco = 2, cinta = 3, graficador
= 4, etc. El sistema obliga a que cada trabajo solicite sus recursos en orden ascendente:
cualquier dispositivo “número uno” requerido por el trabajo será solicitado primero; todo
dispositivo “número dos” será pedido después, y así sucesivamente. Si un trabajo
necesitaba una impresora y después una graficadora, lo solicitaría en este orden:
impresora (#1) y después graficadora (#4). Si el trabajo necesitaba la graficadora
primero y después la impresora, aún así pediría primero la impresora (que es un # 1)
aunque no la utilizará de inmediato. Un trabajo podría solicitar una impresora (#1), un
disco (#2) y después una cinta (#3), pero si más tarde en su procesamiento necesitaba
otra impresora (#1), tendría que anticipar dicha necesidad cuando la solicitó por primera
vez y antes de pedir el disco.
Este esquema de “ordenamiento jerárquico” elimina la posibilidad de una espera circular,
por lo que garantiza la eliminación de los bloqueos mutuos. No requiere que los trabajos
establezcan con anticipación sus necesidades máximas, pero sí precisa que anticipen el
orden en que solicitarán los recursos. Desde la perspectiva de un diseñador de sistemas,
una de las dificultades de este esquema es descubrir el mejor orden para los recursos, de
manera que las necesidades de la mayoría de los usuarios queden satisfechas. Otra
dificultad es que en la asignación de una clasificación jerárquica a recursos no físicos-
como archivos o registros cerrados de bases de datos-no existe base alguna para asignar
un número más elevado a uno en relación con el otro.
EVITAR BLOQUEOS MUTUOS
Incluso si el sistema operativo no puede eliminar una de las condiciones de un bloqueo
mutuo, puede evitar uno, si conoce por anticipado la secuencia de las solicitudes
asociadas con cada proceso activo. Como se ilustró en las gráficas de las figuras 5.7 a
5.11, existe por lo menos una secuencia de asignación de recursos que permitirá que las
tareas continúen sin bloquearse mutuamente.
Dijkstra (1965) propuso uno de esos algoritmos para regular la asignación de recursos a
fin de evitar bloqueos. Este algoritmo, conocido como algoritmo del banquero, se basa
en un banco con una cantidad fija de capital que opera según los principios siguientes:
A ninguno de los clientes se concederá un préstamo que exceda el capital total del
banco.
A todos los clientes se dará el límite de crédito máximo al abrir una cuenta.
A ningún cliente se permitirá que pida prestado más allá de su límite.
La suma de todos los préstamos no excederá el capital total del banco.
Con estas condiciones, no se requiere que el banco tenga a la mano el total de las cuotas
máximas de préstamos antes de abrir sus puertas (suponemos que la institución tendrá
siempre el mismo total fijo y pasaremos por alto el interés que se carga sobre
préstamos). Para nuestro ejemplo, el banco tiene un fondo de capital total de 10 000
dólares y tres clientes, Cl, C2 y C3, cuyos límites máximos de crédito son 4000, 5000 y
8000 dólares, respectivamente. La tabla 5.4 ilustra el estado de negocios del banco, des-
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 49
pués que se han concedido algunos préstamos a C2 y C3. Este se conoce como estado
seguro, porque la institución tiene todavía suficiente dinero disponible para satisfacer las
solicitudes máximas de Cl, C2 y C3.
Es un estado inseguro porque con 1000 dólares disponibles el banco no puede satisfacer la
solicitud máxima de ninguno de los clientes y si presta los 1000 dólares a cualquiera de
ellos, se quedaría bloqueado totalmente (no puede efectuar un préstamo). Un estado
inseguro no necesariamente lleva al bloqueo mutuo, pero sí indica que el sistema es un
candidato excelente para uno. Después de todo, no se requiere que ninguno de los
clientes solicite el máximo, pero el banco no sabe la cantidad exacta que pedirán. En tanto
el capital de la institución sea menor que la cantidad máxima disponible para los
préstamos individuales, no puede garantizar que tendrá capacidad de cubrir las
solicitudes de préstamo.
Si en vez de clientes y dólares tenemos trabajos y dispositivos dedicados, podemos
aplicar los principios de la banca a un sistema operativo. En este ejemplo, el sistema
cuenta con diez dispositivos.
La tabla 5.6 muestra nuestro sistema en un estado seguro, y la tabla 5.7, en un estado
inseguro. Corno antes, en un estado seguro es posible terminar por lo menos un trabajo,
ya que existen suficientes recursos disponibles para satisfacer sus necesidades
máximas. Luego, utilizando los recursos liberados por el trabajo terminado, se pueden
llenar las necesidades máximas de otro trabajo, el cual se puede terminar, y así sucesi-
vamente, hasta que se ejecuten todos los trabajos.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 50
El sistema operativo debe estar seguro de nunca satisfacer una solicitud que convierta un
estado seguro en inseguro. Por lo tanto, conforme cubre las solicitudes de los usuarios, el
sistema operativo debe identificar el trabajo con el número más pequeño de recursos
restantes y asegurarse que el número de recursos disponibles sea siempre igual —o
incluso mayor— al número necesario para que ese trabajo se ejecute hasta su
terminación. El sistema operativo debe bloquear las solicitudes que pondrían en riesgo el
estado seguro, hasta que se puedan aceptar con seguridad. Si el sistema se conserva en
un estado seguro, las solicitudes serán satisfechas y se evitará el bloqueo.
Si esta solución elegante se amplía para trabajar con diferentes clases de recursos, el
sistema establece una tabla de "asignación de recursos" para cada tipo de recurso y lleva
el control de cada una a fin de mantener el sistema en un estado seguro.
Aunque el algoritmo del banquero se ha utilizado para evitar bloqueos mutuos en
sistemas con pocos recursos, no siempre resulta práctico para la mayor parte de los sis-
temas, por varias razones.
1. Conforme los trabajos entran al sistema, deben enunciar por adelantado el
número
máximo de los recursos necesarios. Como hemos dicho, esto no resulta práctico
en
sistemas interactivos.
2. El total de recursos para cada clase debe mantenerse constante. Si un dispositivo
se
rompe y súbitamente deja de estar disponible, el algoritmo no funcionará (el
sistema puede quedar en un estado inseguro).
3. El número de trabajos debe mantenerse fijo, algo que no es posible en los
sistemas
interactivos, donde la cantidad de trabajos activos cambia en forma constante.
4. El costo por carga general incurrida al ejecutar el algoritmo para evitar bloqueos
mutuos puede resultar bastante elevado cuando hay muchos trabajos activos y
dispositivos, ya que se debe correr con cada solicitud.
5. Los recursos no se utilizan bien porque el algoritmo supone el caso peor y, como
resultado, conserva recursos vitales no disponibles como protección contra
estados
inseguros.
6. La planificación sufre como resultado de la mala utilización y los trabajos se que
dan esperando la asignación de recursos: un flujo uniforme de trabajos que
solicitan unos cuantos recursos puede causar una posposición indefinida de un
trabajo más complejo, que requiere muchos recursos.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 51
DETECCIÓN
Las gráficas dirigidas que se presentaron antes mostraban la forma en que la existencia de
una espera circular indica un bloqueo mutuo, por lo que es razonable concluir que los
bloqueos mutuos se pueden detectar, elaborando gráficas de recursos dirigidos y
buscando ciclos. A diferencia del algoritmo para evitar bloqueos mutuos, que se debe
ejecutar cada que existe una solicitud, el algoritmo utilizado para detectar circularidad se
puede correr siempre que sea apropiado: cada hora, una vez al día, cuando el
operador note que producción se ha deteriorado o cuando se queje un usuario.
Dicho algoritmo se puede explicar utilizando las gráficas de recursos dirigidos y
"reduciéndolas". Los pasos para reducir una gráfica son los que:
1. Encuentre un proceso que esté utilizando un recurso y que no esté en espera de
uno. Este proceso se puede eliminar de la gráfica (desconectando el vínculo que
une el recurso al proceso) y los recursos se pueden devolver a la "lista disponible".
Esto es posible porque el proceso terminará y devolverá el recurso.
2. Encuentre un proceso que nada más espere clases de recursos que no están
asignados por completo. Este proceso no contribuye al bloqueo mutuo, ya que
terminará por obtener el recurso que espera, terminará su trabajo y devolverá el
recurso
a la "lista disponible".
3. Vuelva al paso 1 y continúe la iteración, hasta eliminar todas las líneas que conecten
recursos con procesos.
Si quedan líneas, esto indicará que la solicitud del proceso en cuestión no puede
satisfacerse y que existe un bloqueo mutuo. La figura 5.12 ilustra un sistema en el cual
tres procesos —P1, P2 y P3— y tres recursos —R1, R2 y R3— no están bloqueados mutua-
mente.
La figura 5.12 muestra las etapas de una reducción de gráfica desde a), el estado
original, b) El vínculo entre P3 y R3 se puede eliminar porque P3 no espera algún otro
recurso para terminar, por lo que R3 se libera y se asigna a P2 (paso 1). c) Los vínculos
entre P2 y R3 y entre P2 y R2 se pueden suprimir porque P2 tiene todos los recursos
solicitados y puede ejecutarse hasta su terminación, con lo que R2 se puede asignar a Pl.
Por último, en d) los vínculos entre P1 y R2 y entre P1 y R1 se pueden eliminar porque
P1 tiene todos sus recursos solicitados y puede finalizar con éxito. Por tanto, la gráfica
está resuelta por completo. En la figura 5.13, el mismo sistema está bloqueado
mutuamente.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 52
El sistema bloqueado totalmente de la figura 5.13 no se puede reducir, a) El vínculo
entre P3 y R3 se puede eliminar porque P3 no espera otro recurso, por lo que R3 se
libera y se asigna a P2. Pero b) P2 sólo tiene dos de los tres recursos que necesita para
terminar y espera R1. Pero P1 no lo puede liberar porque espera a R2, que está en
manos de P2; además, P1 no puede acabar porque espera que P2 termine (y libere R2) y
éste no puede finalizar porque aguarda a R1. Se trata de una espera circular.
RECUPERACIÓN
Una vez que se detecta un bloqueo mutuo hay que desarmarlo y devolver el sistema a lo
normal con tanta rapidez como sea posible. Existen varios algoritmos de recuperación,
pero todos tienen una característica en común: requieren por lo menos una víctima, un
trabajo consumible, mismo que, al ser eliminada del bloqueo mutuo, liberará al sistema.
Por desgracia, para eliminar la víctima generalmente hay que reiniciar el trabajo desde
el principio o a partir de un punto medio conveniente.
El primer método y más simple de recuperación, y el más drástico, es terminar los
trabajos que están activos en el sistema y volver a arrancarlos desde el principio.
El segundo método es terminar sólo los trabajos incluidos en el bloqueo mutuo y
solicitar a sus usuarios que los vuelvan a enviar.
El tercero es identificar qué trabajos intervienen en el bloqueo mutuo y terminarlos uno
por uno y comprobar la desaparición del bloqueo mutuo después de cada eliminación
hasta resolverlo. Una vez liberado el sistema, se deja que los trabajos restantes terminen
su procesamiento; luego, los trabajos detenidos se inician de nuevo desde el principio.
El cuarto procedimiento se puede poner en efecto sólo si el trabajo mantiene un
registro, una instantánea de su progreso, de manera que se pueda interrumpir y
después continuar sin tener que reiniciar desde el principio. La instantánea es como el
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 53
descanso del ejemplo de la escalera: en vez de obligar a los que suben a volver a la
parte inferior de la misma, sólo necesitan retirarse al descanso más cercano, esperar a
que pasen los demás y reanudar la subida. En general, este método es el preferido para
trabajos de ejecución larga, a fin de ayudarlos a tener una recuperación rápida.
Hasta ahora hemos ofrecido soluciones que comprenden los trabajos que se encuentran en
el bloqueo mutuo. Los dos métodos siguientes se concentran en trabajos que no están en
el bloqueo mutuo y los recursos que conservan. Uno de ellos, el quinto método de
nuestra lista, selecciona un trabajo no bloqueado, retira los recursos que contiene y los
asigna a procesos bloqueados, de manera que pueda reanudarse la ejecución —esto
deshace el bloqueo mutuo—. El sexto método detiene los trabajos nuevos e impide que
entren al sistema, lo que permite que los que no estén bloqueados sigan hasta su ter-
minación y liberen sus recursos. Por último, con menos trabajos en el sistema, la com-
petencia por los recursos se reduce, de suerte que los procesos bloqueados obtienen los
recursos que necesitan para ejecutarse hasta su terminación. Este método es el único
aquí listado que no necesita una víctima. No se garantiza que funcione, a menos que el
número de recursos disponibles exceda los necesarios en por lo menos uno de los tra-
bajos bloqueados para ejecutar (esto es posible con recursos múltiples).
Deben considerarse varios factores al elegir la víctima para que tenga el efecto menos
negativo sobre el sistema. Los más comunes son:
1. La prioridad del trabajo en consideración —por lo general no se tocan los trabajos
de alta prioridad.
2. El tiempo de CPU utilizado por el trabajo —no suelen tocarse los trabajos que están
a punto de terminar.
3. La cantidad de tareas en que repercutiría la elección de la víctima.
Además, los programas que trabajan con bases de datos también merecen un trato
especial. Los trabajos que están modificando datos no se deben elegir para su
terminación, ya que la consistencia y validez de la base de datos se pondría en peligro.
Afortunadamente, los diseñadores de muchos sistemas de bases de datos han incluido
mecanismos complejos de recuperación, por lo que se minimiza el daño a la base de
datos si se interrumpe una transacción o se termina antes de completarse.
INANICIÓN
Hasta ahora nos hemos concentrado en bloqueos mutuos, el resultado de la asignación
liberal de los recursos. En el otro extremo está la inanición, el resultado de la asignación
conservadora de recursos, donde una tarea no puede ejecutarse porque permanece en
espera de recursos que nunca quedan disponibles. Para ilustrar lo anterior, Dijkstra
(1968) introdujo el caso de la "cena de los filósofos" .
Cinco filósofos están sentados en una mesa redonda, cada uno medita profundamente, y
en el centro hay un recipiente de espagueti accesible a todos. Hay un tenedor entre cada
comensal (Fig. 5.14). La costumbre local exige que cada filósofo utilice dos tenedores, los
que están a ambos lados del plato, para comer el espagueti, pero sólo hay cinco —no los
diez que se requerirían para que los cinco pensadores comieran al mismo tiempo— y esto
es desafortunado para el filósofo 2.
Cuando se sientan para cenar, el filósofo 1 (F1) es el primero que toma los dos tenedores
(TI y T5) a ambos lados del plato y empieza a comer. Inspirado por su colega, el filósofo 3
(F3) hace lo mismo y toma T2 y T3. Ahora el filósofo 2 (F2) decide empezar la comida,
pero no puede porque no están disponibles tenedores: TI ha sido asignado a F1 y T2 a
F3; sólo F4 o F5 puede usar el único tenedor disponible, así que el filósofo 2 debe
esperar.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 54
Pronto, F3 termina de comer, deja sobre la mesa sus dos tenedores y vuelve a su
meditación. ¿Hay que asignar el tenedor que está a su lado (T2), ahora libre, al filósofo
hambriento (F2)? Aunque es tentador, tal cosa resultaría ser un mal precedente, porque
si se permite que los filósofos utilicen todos los recursos con la esperanza de que el
recurso requerido quede disponible, la cena puede pasar con facilidad a un estado inse-
guro; sería cuestión de tiempo, antes que cada filósofo se hiciera de un tenedor y nadie
podría cenar. Así pues, los recursos se asignan a los filósofos sólo cuando ambos tene-
dores están disponibles al mismo tiempo. El estado del "sistema" se ilustra en la figura
5.15.
F4 y F5 están meditando tranquilamente y F1 sigue comiendo, cuando F3 (que debe estar
lleno) decide comer algo más y, dado que los recursos están libres, tiene la posibilidad de
tomar T2 y T3 de nuevo. Poco después, F1 termina y libera TI y T5, pero F2 sigue sin
poder comer, porque T2 está asignado. Este escenario podría continuar de manera
indefinida, y siempre que F1 y F3 alternaran su uso de los recursos disponibles, F2
deberá esperar. F1 y F3 pueden comer en cualquier momento, en tanto que F2 se
muere de hambre a sólo pulgadas del alimento.
En un entorno de cómputo, los recursos son como los tenedores y los procesos
competitivos son como los comensales. Si el administrador de los recursos no vigila los
procesos y los trabajos que se están quedando sin alimento y planea su terminación en
algún momento, se podrían quedar en el sistema esperando para siempre la combi-
nación correcta de recursos.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 55
Al fin de encarar este problema, se puede implementar un algoritmo diseñado para
detectar trabajos con inanición, que controla el tiempo que cada trabajo permanece en
espera de recursos (esto es lo mismo que el envejecimiento descrito en el capítulo 4).
Una vez detectada la inanición, el sistema puede bloquear nuevos trabajos hasta que los
trabajos hambrientos queden satisfechos. Este algoritmo se debe supervisar de cerca: si se
efectúa demasiado a menudo, los nuevos trabajos quedan bloqueados constantemente y la
producción disminuye. Si no se lleva a cabo con la frecuencia suficiente, quedarán en el
sistema trabajos con inanición durante un periodo inaceptablemente largo.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 56
PROCESOS CONCURRENTES
En los capítulos 2 y 3 describimos sistemas que utilizan solamente un CPU, En este
veremos sistemas de multiprocesamiento; eso es, con más de un CPU. Analizaremos Las
razones de su desarrollo, ventajas y problemas. Como veremos aquí, la clave para el
multiprocesamiento ha sido objeto de amplia investigación. Examinaremos varias
configuraciones de procesadores y revisaremos los problemas clásicos de procesos
concurrentes, como "productores y consumidores", "lectores y escritores", y "cliente en
la espera faltante". Aunque los problemas ocurren en los sistemas de un solo procesador,
se presentan aquí porque se aplican a los multiprocesos en general, independientemente
de que se refieran a un solo procesador (con dos o más procesos) o a más de un
procesador (por lo tanto multiprocesos).
¿QUÉ ES PROCESAMIENTO PARALELO?
El procesamiento paralelo, también llamado multiprocesamiento, es una situación en la
cual dos o más procesadores operan al unísono. Esto quiere decir que dos o más CPU
ejecutan instrucciones de manera simultánea. Por lo tanto, con más de un proceso activo
a la vez, cada CPU puede tener al mismo tiempo un proceso en estado de EJECUCIÓN.
Para los sistemas de multiprocesamiento, el administrador del procesador tiene que
coordinar la actividad de cada procesador, así como sincronizar la interacción entre los
CPU.
La complejidad de la tarea del administrador del procesador cuando se ocupa de varios
procesadores o de múltiples procesos se ilustra con un ejemplo: usted está atrasado para
una cita a principios de la tarde y corre el riesgo de no poder almorzar, por lo que se
integra a la cola de servicio en el auto de un restorán de comida rápida. Cuando hace su
pedido, el empleado confirma su solicitud, le indica el precio y le pide que maneje hasta
la ventanilla de entrega, donde un cajero le cobra y le da su pedido. Todo está bien y de
nuevo está conduciendo y contento. Acaba de ser testigo de un sistema de
multiprocesamiento bien sincronizado. Aunque usted entró en contacto con dos
procesadores, el empleado de pedidos y el cajero, existían por lo menos dos procesa-
dores más tras bambalinas, que cooperaron para que el sistema funcionara, el cocinero y
el empacador.
El restaurante de comida rápida es similar a un sistema de recuperación de información,
en el cual el procesador 1 (el empleado de pedidos) acepta la consulta, ve que no existan
errores y pasa la solicitud al procesador 2 (el empacador). Éste busca en la base de
datos la información requerida (la hamburguesa). El procesador 3 (el cocinero) recupera
los datos de la base de datos (la carne para preparar la hamburguesa) si es que está
fuera de línea, en algún almacenamiento secundario. Una vez reunidos los datos (la
hamburguesa cocinada) se coloca donde el procesador 2 pueda tomarla (la charola de
hamburguesas). El procesador 2 (el empacador) se la pasa al procesador 4 (el cajero).
Éste encamina la respuesta (su pedido) de regreso al originador de la misma: usted.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 57
La sincronización es la clave del éxito del sistema, porque en un sistema de multi-
procesamiento muchas cosas pueden salir mal. Por ejemplo, ¿qué pasa si el sistema de
comunicación dejara de funcionar y usted no pudiera hablar con el empleado de pedidos?
¿Qué sucede si el cocinero produjera hamburguesas a toda velocidad todo el día, incluso
durante los periodos lentos? ¿Qué pasaría a las hamburguesas adicionales? ¿Qué ocurre
si el cocinero se quema gravemente y ya no puede cocinar? ¿Qué haría el empacador si
no hubiera hamburguesas? ¿Qué pasaría si el cajero decidiera tomar su dinero, pero no
darle alimento alguno? Obviamente, el sistema no puede trabajar en forma correcta, a
menos que cada uno de los procesadores se comunique y coopere con los demás
procesadores.
Los multiprocesadores fueron desarrollados para modelos de mainframe de alta velocidad
de IBM y computadoras VAX, donde el sistema operativo trataba a los CPU adicionales
como recursos adicionales que se programaban para su trabajo. Estos sistemas, algunos
con sólo dos CPU, han estado en uso durante muchos arios (Lane & Mooney, 1988).
A partir de mediados de los 80, cuando los costos del hardware empezaron a bajar, los
sistemas de multiprocesador con decenas de CPU han encontrado uso en entornos
empresariales. Lo que es más, sistemas con decenas de miles de CPU (sistemas que en
el pasado sólo estaban disponibles para la investigación) se pueden encontrar ahora en
entornos de producción. Hoy día, los sistemas de multiprocesador están disponibles en
sistemas de todos los tamaños.
Existen dos fuerzas principales tras el desarrollo del multiprocesamiento, mejorar la
producción e incrementar la potencia de cómputo, y dos beneficios principales, mayor
confiabilidad y un procesamiento más rápido.
La confiabilidad se deriva de la disponibilidad de más de un CPU: si falla un procesador,
los demás pueden continuar operando y absorber la carga. Esto no es de ejecución
sencilla: el sistema debe estar diseñado con sumo cuidado de manera que, primero, el
procesador que está fallando pueda informar a los demás procesadores para que se
hagan cargo y, segundo, que el sistema operativo pueda reestructurar sus estrategias de
asignación de recursos, a fin de que el sistema que queda no se sobrecargue.
La mayor velocidad de procesamiento se logra porque las instrucciones se pueden
procesar en paralelo, dos o más a la vez, y esto se efectúa en una de varias maneras.
Algunos sistemas asignan un CPU a cada programa o trabajo. Otros asignan uno a cada
conjunto de trabajo o a partes del mismo. Otros subdividen las instrucciones individuales
de manera que cada subdivisión se pueda procesar al mismo tiempo (lo cual se conoce
como "programación concurrente" y se analiza con detalle a la conclusión de este
capítulo).
La mayor flexibilidad significa mayor complejidad; sin embargo, quedan dos retos de
importancia: cómo conectar los procesadores en configuraciones y cómo orquestar su
interacción. Este último problema, la orquestación de la interacción, se aplica también a
procesos múltiples que interactúan (pudiera ayudarle si piensa en cada proceso como si
corriera en un procesador por separado, aunque en realidad, sólo exista uno que realiza
todo el trabajo).
CONFIGURACIONES TÍPICAS DE MULTIPROCESAMIENTO
Mucho depende de cómo se configuran los procesadores múltiples en el sistema. Las
configuraciones típicas son maestro/ esclavo, débilmente acoplado y simétrica.
Configuración maestro/esclavo
El sistema de multiprocesamiento maestro/esclavo es una configuración asimétrica. En
términos conceptuales, es un sistema de un procesador con procesadores "esclavos" adi-
cionales, cada uno de los cuales está administrado por el procesador primario "maestro",
según se puede observar en la figura 6.1.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 58
El procesador maestro administra el sistema: todos los archivos, dispositivos, memoria y
procesadores. Por tanto, mantiene el estado de los procesadores en el sistema, efectúa
actividades de administración de almacenamiento, planifica el trabajo de los demás
procesadores y ejecuta los programas de control. Esta configuración es adecuada para
entornos de cómputo en que el tiempo de procesamiento se divide entre procesadores
frontales y posteriores; en estos casos el procesador frontal se ocupa de los usuarios
interactivos y de los trabajos rápidos, y el procesador posterior, de los trabajos largos
mediante el modo de lotes.
La ventaja principal de esta configuración es su simplicidad. Sin embargo, tiene tres
desventajas serias:
1. Su confiabilidad no es más elevada que la de un sistema de un procesador porque
si el procesador principal falla, también el sistema.
2. Puede llevar a un mal uso de los recursos porque si un procesador esclavo queda
liberado mientras el procesador maestro está ocupado, el esclavo debe esperar
hasta que el maestro se libere y le pueda asignar más trabajo.
3. Incrementa el número de interrupciones porque todos los procesadores esclavos
deben interrumpir al procesador maestro cada que necesitan la intervención del
sistema operativo, como las solicitudes de entrada /salida. Esto crea largas colas
al nivel de procesador maestro cuando existen muchos procesadores e
interrupciones.
Configuración débilmente acoplada
La configuración débilmente acoplada tiene varios sistemas de cómputo completos, cada
uno con memoria propia, dispositivos de entrada/salida, CPU y sistema operativo (Fig.
6.2).
Se conoce como débilmente acoplado porque cada procesador controla sus propios
recursos —sus archivos y dispositivos de entrada/salida—. Esto significa que cada pro-
cesador mantiene sus tablas de comandos y de administración de entrada /salida. La
única diferencia entre un sistema de multiprocesamiento débilmente acoplado y un
conjunto de sistemas de procesamiento individuales independientes es que cada proce-
sador se puede comunicar y cooperar con los demás.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 59
Cuando un trabajo llega por primera vez, se asigna a un procesador. Una vez asignado,
el trabajo se quedará con ese procesador hasta que se termina. Por lo tanto, cada
procesador debe tener tablas "globales" que indiquen a cuál procesador se ha asignado
cada trabajo. Para mantener el sistema equilibrado y asegurar el mejor uso de
los recursos, la planificación de los trabajos se basa en varios requisitos y políticas. Por
ejemplo, los nuevos trabajos pueden asignarse al procesador con la carga más ligera o
con la combinación disponible de dispositivos de salida.
Este sistema no está sujeto a fallas catastróficas de sistema, porque incluso cuando falla
un procesador los demás pueden continuar el trabajo de manera independiente. Sin
embargo, puede resultar difícil detectar cuándo ha fallado un procesador.
Configuración simétrica
La configuración simétrica se implementa mejor si todos los procesadores son del mismo
tipo. Tiene cuatro ventajas sobre la de débilmente acoplada:
1. es más confiable,
2. se utilizan los recursos con efectividad,
3. puede equilibrar las cargas y
4. se puede degradar con elegancia en caso de una falla (Forinash, 1987).
Sin embargo, es la más difícil de implementar porque los procesos deben estar bien sin-
cronizados para evitar los problemas de carreras y bloqueos analizados en el capítulo 5.
En una configuración simétrica, la programación del procesador está descentralizada (Fig.
6.3).
Una sola copia del sistema operativo y una tabla global que lista cada proceso y su
estado están almacenadas en un área común de la memoria, por lo que todos los
procesadores tienen acceso a la misma. Cada procesador utiliza el mismo algoritmo de
planificación para seleccionar el proceso que se ejecutará a continuación.
Siempre que se interrumpe un proceso, ya sea que se deba a una solicitud de entrada o
salida o a cualquier otro tipo de interrupción, su procesador actualiza la entrada
correspondiente en la lista de procesos y encuentra otro proceso para ejecutar. Esto
significa que los procesadores se mantienen bastante ocupados y también que varios
procesadores pueden ejecutar cualquier tarea o trabajo durante su tiempo de ejecución.
Debido a que cada procesador tiene acceso a todos los dispositivos de entrada/ salida y
puede hacer referencia a cualquier unidad de almacenamiento, existen más. Conflictos
conforme varios procesadores intentan tener acceso al mismo recurso al mismo tiempo.
Esto presenta la necesidad obvia de algoritmos para resolver conflictos entre proce-
sadores —esto es, la "sincronización de los procesos".
SOFTWARE DE SINCRONIZACIÓN DE PROCESOS
El éxito de la sincronización de los procesos se basa en la capacidad del sistema ope-
rativo para poner un recurso fuera del alcance de otros procesos mientras uno de ellos lo
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 60
esté usando. Estos "recursos" pueden incluir dispositivos de entrada/salida, una localidad
en el almacenamiento o un archivo de datos. En esencia, el recurso utilizado debe quedar
bloqueado, alejado de otros procesos, hasta que queda liberado. Sólo cuando está libre
se permite que un proceso en espera lo utilice. Aquí es donde la sincronización es vital.
Un error pudiera dejar un trabajo o una tarea esperando de manera indefinida.
Es lo mismo que ocurre en una nevería llena de gente. Los clientes toman un número
para recibir atención. Los empleados actualizan los números en la pared jalando una
cadena conforme atienden a cada cliente. ¿Pero qué ocurriría sin una sincronización entre
el servicio a los clientes y el cambio del número? El caos. Éste es el caso del "cliente en
espera faltante".
Digamos que usted tiene el número 75. El empleado 1 atiende al cliente 73 y el em-
pleado 2 al 74. La señal en la pared dice "ahora se está atendiendo al número 74" y us-
ted está listo con su pedido. El empleado 2 termina con el 74 y tira de la cadena, por lo
que la serial dice "ahora se está atendiendo al número 75". Pero justo en ese momento,
el empleado recibe una llamada telefónica, deja el edificio y no regresa (una interrup-
ción). Mientras tanto, el empleado 1 tira de la cadena, se ocupa del número 76 y usted
ha perdido su turno. Si habla a tiempo, puede corregir el error de manera graciosa; pero
cuando ocurre en un sistema de cómputo, el resultado no se remedia con tanta facilidad.
Considere el escenario en el cual los procesadores 1 y 2 terminan sus trabajos al mismo
tiempo. Para ejecutar el siguiente trabajo, cada procesador:
1. Consulta la lista de trabajos para ver cuál debe ejecutar a continuación
2. Recupera el trabajo para su ejecución
3. Incrementa la lista de LISTOS para el trabajo siguiente
4. Lo ejecuta
Van a la lista de LISTOS para seleccionar un trabajo. El procesador 1 ve que el 74 es el
siguiente y va a recuperarlo. Un momento después, el procesador 2 también lo escoge y
va por él. Poco después, el procesador 1, luego de recuperar el trabajo 74, regresa a la
lista de L I STOS y la incrementa, pasando el trabajo 75 a la parte superior. Un momento
más tarde, regresa al procesador 2; también ha recuperado el trabajo 74 y está listo
para procesarlo, por lo que incrementa la lista de LISTOS y ahora se mueve el trabajo 76
a la parte superior y se convierte en el siguiente trabajo en línea para su procesamiento.
El trabajo 75 se ha convertido en el "cliente en espera faltante" y jamas será procesado:
un estado de cosas inaceptable.
Existen varios sitios donde puede ocurrir este problema: memoria y tablas de asignación
de páginas, tablas de entradas/salida, bases de datos de aplicación y cualquier otro
recurso compartido.
Obviamente, esta situación requiere sincronización. Están disponibles varios mecanismos
de sincronización para obtener cooperación y comunicación entre los procesos. El
elemento común de todos los esquemas de sincronización es permitir que un proceso
termine el trabajo en una región crítica del programa, antes que otros procesos tengan
acceso al mismo. Esto es aplicable tanto a multiprocesadores como a dos o más procesos
en un sistema de procesamiento de un procesador (tiempo compartido). Se conoce como
región crítica porque su ejecución se debe manejar como una unidad. Según hemos
visto, los procesos de una región crítica no se pueden entrelazar sin poner en peligro la
integridad de la operación.
La sincronización a veces se implementa como un arreglo de "cerradura y llave": antes
que un proceso pueda funcionar en una región crítica, es necesario que obtenga la
"llave". Una vez que la tiene, los demás procesos se quedan "encerrados afuera" hasta
que termina; entonces libera la entrada a la región crítica y devuelve la llave a otro
proceso que puede tenerla y empezar el trabajo. Esta secuencia está formada por dos
acciones: 1) el proceso primero debe ver si la llave está disponible y 2) si está dispo-
nible, el proceso debe tomarla y ponerla en la cerradura, para que no esté al acceso de
los demás procesos. Para que este esquema funcione, hay que ejecutar ambas funciones
en un ciclo de la máquina; de lo contrario, cabe que mientras el primer proceso está listo
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 61
para tomar la llave, cualquier otro la encuentre disponible y se disponga a tomarla —y
cada uno podría bloquear al otro y evitar su avance.
Se han desarrollado varios mecanismos de bloqueo, incluyendo el de probar y establecer,
WAIT y SIGNA L, y los semáforos.
PROBAR Y ESTABLECER
Probar y establecer es una instrucción indivisible de máquina, conocida simplemente
como "TS"(por las siglas en inglés de Test and Set), introducida por IBM para su sistema
de multiprocesamiento 360/370. En un ciclo de máquina revisa si la llave está disponible
y de ser así la establece como "no disponible".
La llave real es un solo bit en una localidad de almacenamiento que puede contener un
cero (está libre) o un uno (está ocupada). Podemos considerar el TS como un sub-
programa de función que tiene un parámetro (localidad de almacenamiento) y que
devuelve un valor (el código de estado: ocupado/libre), con la excepción que sólo toma
un ciclo de máquina.
Por lo tanto, el proceso P1 puede probar el código de estado con la instrucción TS antes
de entrar a una región crítica. Si ningún otro proceso está en dicha región, se permite
que P1 siga adelante y el código de condición cambia de cero a uno. Luego, cuando P1
sale de la región crítica, se restablece el código de condición a cero, de manera que otro
proceso pueda entrar. Por otra parte, si P1 encuentra un código de condición ocupado, se
coloca en una "iteración de espera" donde continúa efectuando la prueba del código de
condición y aguarda hasta que esté libre (Calingaert, 1982).
Aunque se trata de un procedimiento simple en su implementación, y funciona bien en un
número pequeño de procesos, tiene dos grandes inconvenientes. Primero, cuando
muchos procesos esperan entrar a una región crítica, podría ocurrir la carencia de
recursos o inanición porque los procesos obtienen el acceso de manera arbitraria. Aunque
se estableciera una política de primeras llegadas primeros servicios, algunos procesos
pudieran quedar favorecidos respecto a otros. El segundo es que los procesos en espera
se conservan en iteraciones de espera no productivas, pero que consumen recursos. Esto
se conoce como espera activa. Ésta no sólo consume tiempo valioso del procesador, sino
también se apoya en procesos competitivos para probar la llave, algo que maneja mejor
el sistema operativo o el hardware.
WAIT y SIGNAL
WAIT y SIGNAL es una modificación de probar y establecer diseñada para eliminar la
espera activa. Dos nuevas operaciones, mutuamente excluyentes, forman parte del juego
de operaciones del planificador del proceso: WAIT y SIGNAL.
WAIT se activa cuando el proceso encuentra un código de condición ocupado; establece
el bloque de control del proceso (PCB, por sus siglas en inglés) en el estado bloqueado y
lo vincula con la cola de procesos que esperan la entrada a esta región crítica particular.
El planificador del proceso selecciona otro proceso para su ejecución. SIGNAL queda
activado cuando un proceso sale de la región crítica y el código de condición se establece
como "libre". Comprueba la cola de los procesos que esperan entrar a la región crítica,
selecciona uno y lo coloca en el estado de LISTO. Por último, el planificador de procesos
lo escoge para su ejecución. La adición de las operaciones de WAIT y S IGNAL libera a los
procesos del dilema de la "espera activa" y devuelve el control al sistema operativo,
mismo que entonces puede ejecutar otras tareas, mientras los procesos en espera están
ociosos.
Semáforos
Un semáforo es una variable entera no negativa, que se utiliza como bandera.
Los semáforos mejor conocidos son los dispositivos de señalización tipo bandera que se
usan en los ferrocarriles para indicar si una sección de los rieles está libre. Cuando se
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 62
eleva el brazo del semáforo, los rieles están libres y el tren puede seguir. Cuando el
brazo está bajado, los rieles están ocupados y el tren debe esperar (Fig. 6.4).
En un sistema operativo, un semáforo efectúa una función similar: señala si un recurso
está libre y lo puede utilizar un proceso. Dijkstra (1965) introdujo dos operaciones para
manejar el semáforo a fin de resolver el problema de sincronización del proceso que
hemos analizado. Dijkstra los llamó P y V y así se conocen hoy día. La P representa la
palabra holandesa proberen (probar) y la V significa verhogen (incrementar). Las ope-
raciones P y V efectúan eso: prueban e incrementan.
He aquí cómo funcionan. Si suponemos que s es una variable de semáforo, la operación
V sobre s es incrementar s en uno. La acción se puede enunciar de la siguiente manera:
V(s): s: = s + 1
Esto a su vez requiere una secuencia de recuperación, incremento y almacenamiento.
Igual que con el esquema probar y establecer, para evitar bloqueos mutuos hay que
ejecutar la operación V como una acción indivisible. Esto significa que ningún otro pro-
ceso tiene acceso a s durante dicha operación.
La operación P sobre s es probar el valor de ésta y, en caso de no ser cero, reducirlo en
uno. La acción se puede enunciar de la siguiente manera:
P(s): si s > O entonces s: = s - 1
Esto comprende una secuencia de probar, recuperar, decrementar y almacenar. De
nuevo, esta secuencia se debe ejecutar como una acción indivisible en un ciclo de máqui-
na u organizar que el proceso no realice acción alguna hasta que termine la operación (P
o V).
El sistema operativo ejecuta las operaciones P y V en respuesta a llamadas emitidas por
cualquier proceso que use un semáforo como parámetro (esto evita que el proceso tenga
control). Si s = O, el proceso que llama sobre la operación P debe esperar hasta que la
operación pueda correr, y esto no ocurre sino hasta s > O.
Como se aprecia en la tabla 6.1, P3 se coloca en el estado WA I T (para el semáforo) en
el estado 4. Como también se ve en dicha tabla, para los estados 6 y 8, cuando el
proceso sale de la región crítica, el valor de s se restablece a 1. Esto a su vez dispara el
despertar de uno de los procesos bloqueados, su entrada en la región crítica y el
restablecimiento de s a cero. En el estado 7, P1 y P2 no intentan efectuar
procesamientos en la región crítica y P4 sigue bloqueado.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 63
Después del estado 5 de la tabla 6.1, el proceso de espera más larga P3 fue elegido para
entrar en la región crítica, pero esto no es necesariamente el caso, a menos que el
sistema utilice una política de selección de primeras entradas primeras salidas. De hecho,
la elección de la tarea que se procesará depende del algoritmo que use esta porción del
planificador de procesos.
Como puede observar en la tabla 6.1, las operaciones P y V en un semáforo s obligan al
concepto de la exclusión mutua, necesaria para evitar que dos operaciones intenten
ejecutarse al mismo tiempo. El nombre tradicionalmente dado a este semáforo en la
literatura es mutex, y significa MUTual EXclusion. Por lo que las operaciones se con-
vierten en:
P(mutex): si mutex > O entonces mutex: = mutex - 1
V(mutex): mutex: = mutex + 1
En el capítulo 5 hablamos del requisito de la exclusión mutua cuando varios trabajos
intentan tener acceso a los mismos recursos físicos compartidos. El concepto es el mismo
aquí, pero tenemos varios procesos que intentan tener acceso a la misma región crítica
compartida. El procedimiento se puede generalizar a semáforos con valores superiores a
cero y uno.
Hasta ahora hemos visto el problema de la exclusión mutua presentado por procesos
paralelos que interactúan utilizando los mismos datos compartidos a tasas diferentes de
ejecución. Esto puede ser aplicable a varios procesos en más de un procesador o a
procesos interactivos (codependientes) de un procesador. En este caso, el concepto de la
"región crítica" se hace necesario porque asegura que los procesos paralelos modificarán
los datos compartidos sólo mientras estén en la región crítica.
En los cálculos secuenciales la exclusión mutua se logra de manera automática, porque
cada operación se maneja en orden, una a la vez. Sin embargo, en computaciones en
paralelo, el orden de ejecución puede cambiar, por lo que hay que establecer y conservar
de manera explícita la exclusión mutua. De hecho, todo el principio de los procesos en
paralelo se apoya en que todas las operaciones sobre variables comunes se excluyen a lo
largo del tiempo.
COOPERACIÓN DE PROCESOS
En ocasiones varios procesos trabajan juntos para completar una tarea común. Los
ejemplos famosos son los problemas de "productores y consumidores" y "lectores y
escritores". Cada caso requiere la exclusión mutua y la sincronización, y se implementan
utilizando semáforos.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 64
Productores y consumidores
En el problema clásico de productores y consumidores, un proceso produce algunos datos
que otro proceso consume después. A pesar de que describiremos el caso con un produc-
tor y un consumidor, se puede expandir a varios pares de productores y consumidores.
Volvamos por un momento al ejemplo de la comida rápida al principio del capítulo,
porque la sincronización entre dos de los procesadores (el cocinero y el empacador)
representa un problema significativo en los sistemas operativos. El cocinero produce
hamburguesas consumidas por el empacador. Ambos procesadores tienen acceso a un
área común, la charola de hamburguesas, que contiene un número finito de hambur-
guesas (esto se conoce como área de memoria intermedia). La charola es un área nece-
saria de almacenamiento, porque la velocidad a la cual se producen las hamburguesas es
independiente de la velocidad a la cual se consumen.
Se presentan problemas en dos extremos: cuando el productor intenta agregar algo a
una charola llena (como cuando el cocinero trata de colocar una hamburguesa de más en
una charola llena) o cuando el consumidor intenta retirar algo de una charola vacía
(como cuando el empacador intenta coger una hamburguesa que todavía no se prepara).
En la vida real, las personas observan la charola, advierten si está vacía o demasiado
llena y el problema se resuelve con rapidez. Sin embargo, en un sistema de cómputo
dicha resolución no es tan fácil.
Considere el caso del CPU prolífico: el CPU puede generar datos de salida mucho más
aprisa de lo que puede imprimir una impresora de línea. Por lo tanto, como esto
comprende a un productor y a un consumidor con dos velocidades diferentes, es nece-
sario una memoria intermedia, donde el productor pueda almacenar temporalmente
datos que pueda recuperar el consumidor a una velocidad más apropiada. La figura 6.5
muestra tres estados típicos de memoria intermedia (buffer).
Dado que la memoria intermedia sólo puede contener una cantidad finita de datos, el
proceso de sincronización debe retrasar al productor, para que genere menos datos
cuando la memoria intermedia está llena. También debe estar preparado para retrasar la
recuperación de datos por parte del consumidor cuando la memoria intermedia está
vacía. Esta tarea se puede implementar mediante dos semáforos de conteo: uno para
indicar el número de posiciones llenas en la memoria intermedia y en el otro para indicar
el número de posiciones vacías en dicha memoria.
Un tercer semáforo, mutex, asegura la exclusión mutua entre los procesos. A con-
tinuación presentamos las definiciones de los procesos de productor y de consumidor:
PRODUCTOR CONSUMIDOR
produce datos P(lleno)
P(vacío) P(mutex) P(mutex) lee datos de la memoria intermedia escribe datos en la memoria intermedia V(mutex) V(mutex) V(vacío) V(lleno) consume datos
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 65
La siguiente lista da las definiciones de las variables y de las funciones utilizadas en el
algoritmo de productores y consumidores.
Dados: Lleno, vacío, mutex, definidos como semáforos n: Número máximo de posiciones en la memoria intermedia V (x): x: = x + 1 (x es cualquier variable definida como semáforo) P (x): Si x> O entonces x: = x — 1
mutex I Significa que se permite que el proceso entre en la región crítica
A continuación está el algoritmo que implementa la interacción entre el productor y el
consumidor. COBEGIN y COEND son delimitadores que se utilizan para indicar secciones
de código que se van a efectuar al mismo tiempo. ALGORITMO DE PRODUCTORES Y CONSUMIDORES
Vacío: = n Lleno: = 0 mutex: = I COBEGIN
repetir hasta que no haya más datos del PRODUCTOR Repetir hasta que la memoria intermedia esté vacía CONSUMIDOR
COEND
Los procesos (productor y consumidor) se ejecutan como se describió. Usted puede
intentar con el código con n = 3 o con un orden alterno de ejecución para ver si funciona.
El concepto de productor/consumidor se puede extender a la memoria intermedia que
contiene registros u otros datos, así como a otras situaciones en que se requiere la
comunicación directa de los mensajes de proceso a proceso.
Lectores y escritores
En 1971 se formuló por primera vez el problema de lectores y escritores y se presenta
cuando dos tipos de procesos necesitan tener acceso a un recurso compartido como un
archivo o una base de datos. Llamaron a estos procesos "lectores" y "escritores".
Un buen ejemplo es un sistema de reservaciones de una aerolínea. Los lectores son los
que desean información sobre los vuelos. Son lectores porque sólo leen los datos
existentes, no los modifican. Como no hay nadie que modifique la base de datos, el sis-
tema puede permitir muchos lectores activos al mismo tiempo, no hay necesidad de la
exclusión mutua entre ellos.
Los escritores efectúan las reservaciones sobre un vuelo en particular. Los escritores se
deben organizar con cuidado, porque modifican datos existentes en la base de datos. El
sistema no puede permitir que cualquiera escriba mientras alguna otra persona lee (o
escribe). Por lo tanto, debe obligar a la exclusión mutua si existen grupos de lectores y
un escritor o si existen varios escritores en el sistema. El sistema debe ser justo cuando
obligue a esta política, para evitar una posposición indefinida de lectores o escritores.
En el trabajo original, Courtois, Heymans y Parnas ofrecieron dos soluciones, utilizando
operaciones P y V. La primera da prioridad a los lectores sobre los escritores, por lo que
sólo se quedan esperando si un escritor está modificando datos en ese momento. Sin
embargo, esta política da como resultado inanición de escritores si existe una corriente
continua de lectores. La segunda política da prioridad a los escritores. En este caso, tan
pronto como llega un escritor, se permite que termine su procesamiento cualquier lector
que esté activo en ese momento, pero se dejan pendientes los lectores adicionales, hasta
que termine el escritor. Esto da como resultado la inanición de lectores si existe una
corriente continua de escritores. Cualquiera de estos escenarios es inaceptable.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 66
Para evitar cualquier tipo de inanición, Hoare (1974) propuso la siguiente política de
combinación de prioridades. Cuando ha terminado un escritor, se permite que lean todos
los lectores que estén esperando o "pendientes". Luego, cuando ese grupo de lectores ha
terminado, el escritor que esté "pendiente" puede iniciar y se evita el acceso a todo
lector nuevo que llegue en el ínterin mientras no acabe el escritor.
El estado del sistema se puede resumir con cuatro contadores inicializados a cero:
1. Número de lectores que han solicitado un recurso y todavía no lo han liberado (L1
=0);
2. Lectores que están usando un recurso y aún no lo liberan (L2=0);
3. Número de escritores que han solicitado un recurso y que no lo han liberado (E1
=0);
4. Cantidad de escritores que están usando un recurso y todavía no lo liberan
(E2=0).
Esto se puede implementar utilizando dos semáforos para asegurar la exclusión mutua
entre lectores y escritores. Un recurso se puede dar a todos los lectores (L1 = L2)
siempre y cuando no haya escritores procesando (E2=0). Un recurso se puede propor-
cionar a un escritor, siempre y cuando no haya lectores leyendo (L2=0) ni escritores
escribiendo (E2=0).
Los lectores siempre deben solicitar dos procedimientos: el primero verifica si los
recursos se pueden conceder de inmediato para la lectura; luego, cuando se libera el
recurso, el segundo revisa que ningún escritor esté en espera. Lo mismo es cierto para
los escritores. El primer procedimiento debe determinar si el recurso se puede conceder
de inmediato para escribir y, al liberarlo, el segundo procedimiento averiguará si hay lec-
tores en espera.
PROGRAMACIÓN CONCURRENTE
Hasta ahora hemos visto el multiprocesamiento como varios trabajos que se ejecutan al
mismo tiempo en un procesador (que interactúan con procesadores de entrada /salida,
por ejemplo) o sobre multiprocesadores. El multiprocesamiento también puede referirse
a un trabajo que utiliza varios procesadores para ejecutar conjuntos de instrucciones en
paralelo. El concepto no es nuevo, pero requiere un lenguaje de programación y un
sistema de cómputo que pueda apoyar ese tipo de construcción. Este tipo de sistemas se
conoce como sistema de procesamiento concurrente.
Aplicaciones de la programación concurrente
La mayor parte de los lenguajes de monoprogramación son de naturaleza serial: las
instrucciones se ejecutan una por una. Por lo tanto, para resolver una expresión arit-
mética, todas las operaciones se efectúan en secuencia, siguiendo el orden prescrito por
el programador y el compilador (tabla 6.2).
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 67
Para muchos propósitos de cómputo, el procesamiento serial es conveniente; es fácil de
implementar y lo suficientemente rápido para la mayor parte de los usuarios.
Sin embargo, las expresiones aritméticas se pueden procesar de manera diferente si
utilizamos un lenguaje que permita el procesamiento concurrente. Definamos dos tér-
minos, COBEG I N y CO E N D, que indicarán al compilador qué instrucciones se pueden
procesar de manera concurrente. A continuación escribiremos de nuevo nuestra
expresión, para aprovechar un compilador de procesamiento concurrente.
Como se observa en la tabla 6.3, para resolver A = 3 * B * C + 4 / (D+E)**(F—G), las
tres primeras operaciones se pueden efectuar al mismo tiempo, si nuestro sistema de
cómputo tiene por lo menos tres procesadores. Las siguientes dos operaciones se efec-
túan al mismo tiempo y la ultima expresión se lleva a cabo de manera serial, utilizando
los resultados de los dos primeros pasos.
Con este sistema hemos incrementado la velocidad de cómputo, así como la complejidad
del lenguaje de programación y el hardware (tanto la maquinaria como la comunicación
entre máquinas). De hecho, también hemos colocado una carga grande sobre el
programador: enunciar de manera explícita qué instrucciones se pueden ejecutar en
paralelo. Esto es paralelismo explícito.
Los primeros programas de procesamiento concurrente se apoyaban en el programador
para escribir las instrucciones en paralelo; pero se presentaban problemas: la
codificación era lenta y llevaba a perder oportunidades de procesamiento en paralelo.
También conducía a errores, donde el procesamiento en paralelo se indicaba de manera
equivocada. Desde el punto de vista de mantenimiento, los programas eran difíciles de
modificar. La solución fue la detección automática hecha por el compilador de
instrucciones que se puedan ejecutar en paralelo. Esto se conoce como paralelismo
implícito.
Con un sistema de procesamiento verdaderamente concurrente, el ejemplo presentado
en las tablas 6.2 y 6.3 se codifica como una expresión. El compilador traduce la
expresión algebraica en instrucciones por separado y decide cuáles se realizarán en
paralelo y cuáles en serie.
SISTEMAS OPERATIVOS I
Ing. Romel Aldás 68
Por ejemplo, el compilador puede reorganizar la ecuación Y=A+B*C+D en la forma A + D
+ B * C, de manera que las dos operaciones A+D y B*C se pueden efectuar en paralelo,
dejando la suma final para calcularla al último
Como se muestra en los cuatro casos que se dan a continuación, el procesamiento
concurrente también puede reducir dramáticamente la complejidad de trabajar con
operaciones matriciales dentro de ciclos, de llevar a cabo la multiplicación matricial, de
conducir búsquedas en paralelo en bases de datos y de ordenar o combinar archivos.
Algunos de estos sistemas utilizan procesadores en paralelo que ejecutan el mismo tipo
de tareas (Ben-Ari, 1982).
CASO 1, OPERACIONES DE MATRICES
Para llevar a cabo una operación de matriz dentro de un ciclo, las instrucciones pudieran
decir: DO 1=1,3 A(I) = B(I)+C(I) ENDDO
Si utilizamos tres procesadores, la instrucción se puede llevar a cabo en un paso como
sigue:
Procesador #1 ejecuta: A(1) = B(1)+C(1)
Procesador #2 ejecuta: A(2) = B(2)+C(2)
Procesador #3 ejecuta: A(3) = B(3)+C(3)
Varios elementos de la primera hilera de la matriz A se podrían multiplicar por los
elementos correspondientes de la primera columna de la matriz B. Este proceso se puede
repetir hasta poder calcular todos los productos para el primer elemento de la matriz C y
obtener el resultado sumando los productos. El número real de productos que se puede
calcular al mismo tiempo depende del número de procesadores disponibles. En serie,
puede calcularse en 45 pasos. Con tres procesadores, al efectuar multiplicaciones en
paralelo, bastan 27 pasos.
CASO 3, BÚSQUEDA DE BASES DE DATOS
La búsqueda es una aplicación no matemática común de procesamiento concurrente.
Cada procesador busca una sección diferente de la base de datos o del archivo. Es una
manera muy rápida de encontrar términos en un diccionario, autores en una base de
datos bibliográfica o términos en archivos invertidos (los archivos invertidos se generan
partir de bases de datos de documentos completos. Cada registro en un archivo invertido
contiene un término de tema y los números de documentos donde el tema se encuentre).
CASO 4, ORDENAMIENTO O COMBINACIÓN DE ARCHIVOS
La división de un archivo grande en secciones, cada uno con su procesador, permite
ordenar cada sección al mismo tiempo. Luego es factible combinar pares de secciones
hasta que el archivo entero está completo de nuevo y ordenado.