La planificación del procesador se refiere a la manera o técnicas que se usan para decidir cuánto tiempo de
ejecución y cuando se le asignan a cada proceso del sistema. Obviamente, si el sistema es monousuario y
monotarea nohay mucho que decidir, pero en el resto de los sistemas esto es crucial para el buen
funcionamiento del sistema.
5.1.2 Niveles de planificación
En los sistemas de planificación generalmente se identifican tres niveles: el alto, em medio y el bajo. El nivel alto
decide que trabajos (conjunto de procesos) son candidatos a convertirse en procesos compitiendo por los
recursos del sistema; el nivel intermedio decide que procesos se suspenden o reanudan para lograr ciertas
metas de rendimiento mientras que el planificador de bajo nivel es el que decide que proceso, de los que ya
están listos (y que en algún momento paso por los otros dos planificadores) es al que le toca ahora estar
ejecutándose en la unidad central de procesamiento. En este trabajo se revisaran principalmente los
planificadores de bajo nivel porque son los que finalmente eligen al proceso en ejecución.
5.1.3 Objetivos de la planificación
Una estrategia de planificación debe buscar que los procesos obtengan sus turnos de ejecución
apropiadamente, conjuntamente con un buen rendimiento y minimización de la sobrecarga (overhead) del
planificador mismo. En general, se buscan cinco objetivos principales:
Justicia o Imparcialidad: Todos los procesos son tratados de la misma forma, y en algún momento
obtienen su turno de ejecución o intervalos de tiempo de ejecución hasta su terminación exitosa.
Maximizar la Producción: El sistema debe de finalizar el mayor numero de procesos en por unidad de
tiempo.
Maximizar el Tiempo de Respuesta: Cada usuario o proceso debe observar que el sistema les
responde consistentemente a sus requerimientos.
Evitar el aplazamiento indefinido: Los procesos deben terminar en un plazo finito de tiempo.
El sistema debe ser predecible: Ante cargas de trabajo ligeras el sistema debe responder rápido y
con cargas pesadas debe ir degradándose paulatinamente. Otro punto de vista de esto es que si se
ejecuta el mismo proceso en cargas similares de todo el sistema, la respuesta en todos los casos debe
ser similar.
5.1.4 Características a considerar de los procesos
No todos los equipos de cómputo procesan el mismo tipo de trabajos, y un algoritmo de planificación que en un
sistema funciona excelente puede dar un rendimiento pésimo en otro cuyos procesos tienen características
diferentes. Estas características pueden ser:
Cantidad de Entrada/Salida: Existen procesos que realizan una gran cantidad de operaciones de
entrada y salida (aplicaciones de bases de datos, por ejemplo).
Cantidad de Uso de CPU: Existen procesos que no realizan muchas operaciones de entrada y salida,
sino que usan intensivamente la unidad central de procesamiento. Por ejemplo, operaciones con
matrices.
Procesos de Lote o Interactivos: Un proceso de lote es más eficiente en cuanto a la lectura de datos,
ya que generalmente lo hace de archivos, mientras que un programa interactivo espera mucho tiempo
(no es lo mismo el tiempo de lectura de un archivo que la velocidad en que una persona teclea datos)
por las respuestas de los usuarios.
Procesos en Tiempo Real: Si los procesos deben dar respuesta en tiempo real se requiere que tengan
prioridad para los turnos de ejecución.
Longevidad de los Procesos: Existen procesos que tipicamente requeriran varias horas para finalizar
su labor, mientras que existen otros que solonecesitan algunos segundos.
5.1.5 Planificación apropiativa o no apropiativa (preemptive or not preemptive)
La planificación apropiativa es aquella en la cual, una vez que a un proceso le toca su turno de ejecución ya no
puede ser suspendido, ya no se le puede arrebatar la unidad central de procesamiento. Este esquema puede
ser peligroso, ya que si el proceso contiene accidental o deliberadamente ciclos infinitos, el resto de los
procesos pueden quedar aplazados indefinidamente. Una planificación no apropiativa es aquella en que existe
un reloj que lanza interrupciones periodicas en las cuales el planificador toma el control y se decide si el mismo
proceso seguirá ejecutándose o se le da su turno a otro proceso. Este mismo reloj puede servir para lanzar
procesos manejados por el reloj del sistema. Por ejemplo en los sistemas UNIX existen los 'cronjobs' y 'atjobs',
los cuales se programan en base a la hora, minuto, día del mes, día de la semana y día del año.
En una planificación no apropiativa, un trabajo muy grande aplaza mucho a uno pequeño, y si entra un proceso
de alta prioridad esté también debe esperar a que termine el proceso actual en ejecución.
5.1.6 Asignación del turno de ejecución
Los algoritmos de la capa baja para asignar el turno de ejecución se describen a continuación:
Por prioridad: Los procesos de mayor prioridad se ejecutan primero. Si existen varios procesos de
mayor prioridad que otros, pero entre ellos con la misma prioridad, pueden ejecutarse estos de acuerdo
a su orden de llegada o por 'round robin'. La ventaja de este algoritmo es que es flexible en cuanto a
permitir que ciertos procesos se ejecuten primero e, incluso, por más tiempo. Su desventaja es que
puede provocar aplazamiento indefinido en los procesos de baja prioridad. Por ejemplo, suponga que
existen procesos de prioridad 20 y procesos de prioridad 10. Si durante todo el día terminan procesos
de prioridad 20 al mismo ritmo que entran otros con esa prioridad, el efecto es que los de prioridad 10
estarán esperando por siempre. También provoca que el sistema sea impredecible para los procesos
de baja prioridad.
El trabajo más corto primero: Es dificil de llevar a cabo porque se requiere saber o tener una
estimación de cuánto tiempo necesita el proceso para terminar. Pero si se sabe, se ejecutan primero
aquellos trabajos que necesitan menos tiempo y de esta manera se obtiene el mejor tiempo de
respuesta promedio para todos los procesos. Por ejemplo, si llegan 5 procesos A,B,C,D y E cuyos
tiempos de CPU son 26, 18, 24, 12 y 4 unidades de tiempo, se observa que el orden de ejecución será
E,D,B,C y A (4,12,18, 24 y 26 unidades de tiempo respectivamente). En la tabla siguiente se muestra en
que unidad de tiempo comienza a ejecutarse cada proceso y como todos comenzaron a esperar desde
la unidad cero, se obtiene el tiempo promedio de espera.
Proceso
Espera desde Termina
Tiempo de Espera
A 0 4 4
B 0 16 16
C 0 34 34
D 0 58 58
E 0 84 84
Tiempo promedio = (4 + 16 + 34 + 58 + 84 )/5 = 39 unidades.
El primero en llegar, primero en ejecutarse: Es muy simple, los procesos reciben su turno conforme
llegan. La ventaja de este algoritmo es que es justo y no provoca aplazamiento indefinido. La
desventaja es que no aprovecha ninguna característica de los procesos y puede no servir para
unproceso de tiempo real. Por ejemplo, el tiempo promedio de respuesta puede ser muy malo
comparado con el logrado por el del trabajo más corto primero. Retomando el mismo ejemplo que en el
algoritmo anterior, obtenemos un tiempo de respuesta promedio (26+44+68+80+84)/5 = 60 unidades, el
cual es muy superior a las 39 unidades que es el mejor tiempo posible.
Round Robin: También llamada por turno, consiste en darle a cada proceso un intervalo de tiempo de
ejecución (llamado time slice), y cada vez que se vence ese intervalo se copia el contexto del proceso a
un lugar seguro y se le da su turno a otro proceso. Los procesos están ordenados en una cola circular.
Por ejemplo, si existen tres procesos, el A,B y C, dos repasadas del planificador darían sus turnos a los
procesos en el orden A,B,C,A,B,C. La ventaja de este algoritmo es su simplicidad, es justo y no provoca
aplazamiento indefinido.
El tiempo restante más corto: Es parecido al del trabajo más corto primero, pero aquií se está
calculando en todo momento cuánto tiempo le resta para terminar a todos los procesos, incluyendo los
nuevos, y aquel que le quede menos tiempo para finalizar es escogido para ejecutarse. La ventaja es
que es muy útil para sistemas de tiempo compartido porque se acerca mucho al mejor tiempo de
respuesta, además de responder dinámicamente a la longevidad de los procesos; su desventaja es que
provoca más sobrecarga porque el algoritmo es más complejo.
La tasa de respuesta más alta: Este algoritmo concede el truno de ejecución al proceso que produzca
el valor mayor de la siguiente formula:
tiempo que ha esperado + tiempo total para terminar
valor = ___________________________________________
tiempo total para terminar.
Es decir, que dinámicamente el valor se va modificando y mejora un poco las deficiciencias del
algoritmo del trabajo más corto primero.
Por politica: Una forma de asignar el turno de ejecución es por politica, en la cual se establece algún
reglamento específico que el planificador debe obedecer. Por ejemplo, una politica podría ser que todos
los procesos reciban el mismo tiempo de uso de CPU en cualquier momento. Esto sig- nifica, por
ejemplo, que si existen 2 procesos y han recibido 20 unidades de tiempo cada uno (tiempo acumulado
en time slices de 5 unidades) y en este momento entra un tercer proceso, el planificador le dara
inmediatamente el turno de ejecución por 20 unidades de tiempo. Una vez que todos los procesos están
'parejos' en uso de CPU, se les aplica 'round robin'.
5.2 Problemas de Concurrencia
En los sistemas de tiempo compartido (aquellos con varios usuarios, procesos, tareas, trabajos que reparten el
uso de CPU entre estos) se presentan muchos problemas debido a que los procesos compiten por los recursos
del sistema. Imagine que un proceso está escribiendo en la unidad de cinta y se le termina su turno de
ejecución e inmediatamente después el proceso elegido para ejecutarse comienza a escribir sobre la misma
cinta. El resultado es una cinta cuyo contenido es un desastre de datos mezclados. Así como la cinta, existen
una multitud de recursos cuyo acceso debe der controlado para evitar los problemas de la concurrencia.
El sistema operativo debe ofrecer mecanismos para sincronizar la ejecución de procesos: semáforos, envío de
mensajes, 'pipes', etc. Los semáforos son rutinas de software (que en su nivel más interno se auxilian del
hardware) para lograr exclusión mutua en el uso de recursos. Para entender este y otros mecanismos es
importante entender los problemas generales de concurrencia, los cuales se describen enseguida.
Condiciones de Carrera o Competencia: La condición de carrera (race condition) ocurre cuando dos
o más procesos accesan un recurso compartido sin control, de manera que el resultado combinado de
este acceso depende del orden de llegada. Suponga, por ejemplo, que dos clientes de un banco
realizan cada uno una operación en cajeros diferentes al mismo tiempo.
El usuario A quiere hacer un depósito. El B un retiro. El usuario A comienza la transacción y lee su
saldo que es 1000. En ese momento pierde su turno de ejecución (y su saldo queda como 1000) y el
usuario B inicia el retiro: lee el saldo que es 1000, retira 200 y almacena el nuevo saldo que es 800 y
termina. El turno de ejecución regresa al usuario A el cual hace su depósito de 100, quedando saldo =
saldo + 100 = 1000 + 100 = 1100. Como se ve, el retiro se perdió y eso le encanta al usuario A y B,
pero al banquero no le convino esta transacción. El error pudo ser al revés, quedando el saldo final en
800.
Postergación o Aplazamiento Indefinido(a): Esto se mencionó en el apartado anterior y consiste en
el hecho de que uno o varios procesos nunca reciban el suficiente tiempo de ejecución para terminar su
tarea. Por ejemplo, que un proceso ocupe un recurso y lo marque como 'ocupado' y que termine sin
marcarlo como 'desocupado'. Si algún otro proceso pide ese recurso, lo verá 'ocupado' y esperará
indefinidamente a que se 'desocupe'.
Condición de Espera Circular: Esto ocurre cuando dos o más procesos forman una cadena de espera
que los involucra a todos. Por ejemplo, suponga que el proceso A tiene asignado el recurso 'cinta' y el
proceso B tiene asignado el recurso 'disco'. En ese momento al proceso A se le ocurre pedir el recurso
'disco' y al proceso B el recurso 'cinta'. Ahi se forma una espera circular entre esos dos procesos que se
puede evitar quitándole a la fuerza un recurso a cualquiera de los dos procesos.
Condición de No Apropiación: Esta condición no resulta precisamente de la concurrencia, pero juega
un papel importante en este ambiente. Esta condición especifica que si un proceso tiene asignado un
recurso, dicho recurso no puede arrebatársele por ningún motivo, y estará disponible hasta que el
proceso lo 'suelte' por su voluntad.
Condición de Espera Ocupada: Esta condición consiste en que un proceso pide un recurso que ya
está asignado a otro proceso y la condición de no apropiación se debe cumplir. Entonces el proceso
estará gastando el resto de su time slice checando si el recurso fue liberado. Es decir, desperdicia su
tiempo de ejecución en esperar. La solución más común a este problema consiste en que el sistema
operativo se dé cuenta de esta situación y mande a una cola de espera al proceso, otorgándole
inmediatamente el turno de ejecución a otro proceso.
Condición de Exclusión Mutua: Cuando un proceso usa un recurso del sistema realiza una serie de
operaciones sobre el recurso y después lo deja de usar. A la sección de código que usa ese recurso se
le llama 'región crítica'. La condición de exclusión mutua establece que solamente se permite a un
proceso estar dentro de la misma región crítica. Esto es, que en cualquier momento solamente un
proceso puede usar un recurso a la vez. Para lograr la exclusión mutua se ideo también el concepto de
'región crítica'. Para logar la exclusión mutua generalmente se usan algunas técnicas para lograr entrar
a la región crítica: semáforos, monitores, el algoritmo de Dekker y Peterson, los 'candados'. Para ver
una descripción de estos algoritmos consulte [Deitel93] [Tan92].
Condición de Ocupar y Esperar un Recurso: Consiste en que un proceso pide un recurso y se le
asigna. Antes de soltarlo, pide otro recurso que otro proceso ya tiene asignado.
Los problemas descritos son todos importantes para el sistema operativo, ya que debe ser capaz de prevenir o
corregirlos. Tal vez el problema más serio que se puede presentar en un ambiente de concurrencia es el
'abrazo mortal', también llamado 'trabazón' y en inglés deadlock. El deadlock es una condición que ningún
sistema o conjunto de procesos quisiera exhibir, ya que consiste en que se presentan al mismo tiempo cuatro
condiciones necesarias: La condición de no apropiación, la condición de espera circular, la condición de
exclusión mutua y la condición de ocupar y esperar un recurso. Ante esto, si el deadlock involucra a todos los
procesos del sistema, el sistema ya no podrá hacer algo productivo. Si el deadlock involucra algunos procesos,
éstos quedarán congelados para siempre.
En el área de la informática, el problema del deadlock ha provocado y producido una serie de estudios y
técnicas muy útiles, ya que éste puede surgir en una sola máquina o como consecuencia de compartir recursos
en una red.
En el área de las bases de datos y sistemas distribuidos han surgido técnicas como el 'two phase locking' y el
'two phase commit' que van más allá de este trabajo. Sin embargo, el interés principal sobre este problema se
centra en generar técnicas para detectar, prevenir o corregir el deadlock.
Las técnicas para prevenir el deadlock consisten en proveer mecanismos para evitar que se presente una o
varias de las cuatro condiciones necesarias del deadlock. Algunas de ellas son:
Asignar recursos en orden lineal: Esto significa que todos los recursos están etiquetados con un
valor diferente y los procesos solo pueden hacer peticiones de recursos 'hacia adelante'. Esto es, que si
un proceso tiene el recurso con etiqueta '5' no puede pedir recursos cuya etiqueta sea menor que '5'.
Con esto se evita la condición de ocupar y esperar un recurso.
Asignar todo o nada: Este mecanismo consiste en que el proceso pida todos los recursos que va a
necesitar de una vez y el sistema se los da solamente si puede dárselos todos, si no, no le da nada y lo
bloquea.
Algoritmo del banquero: Este algoritmo usa una tabla de recursos para saber cuántos recursos tiene
de todo tipo. También requiere que los procesos informen del máximo de recursos que va a usar de
cada tipo. Cuando un proceso pide un recurso, el algoritmo verifica si asignándole ese recurso todavía
le quedan otros del mismo tipo para que alguno de los procesos en el sistema todavía se le pueda dar
hasta su máximo. Si la respuesta es afirmativa, el sistema se dice que está en 'estado seguro' y se
otorga el recurso. Si la respuesta es negativa, se dice que el sistema está en estado inseguro y se hace
esperar a ese proceso.
Para detectar un deadlock, se puede usar el mismo algoritmo del banquero, que aunque no dice que hay un
deadlock, sí dice cuándo se está en estado inseguro que es la antesala del deadlock. Sin embargo, para
detectar el deadlock se pueden usar las 'gráficas de recursos'. En ellas se pueden usar cuadrados para indicar
procesos y círculos para los recursos, y flechas para indicar si un recurso ya está asignado a un proceso o si un
proceso está esperando un recurso. El deadlock es detectado cuando se puede hacer un viaje de ida y vuelta
desde un proceso o recurso. Por ejemplo, suponga los siguientes eventos:
evento 1: Proceso A pide recurso 1 y se le asigna.
evento 2: Proceso A termina su time slice.
evento 3: Proceso B pide recurso 2 y se le asigna.
evento 4: Proceso B termina su time slice.
evento 5: Proceso C pide recurso 3 y se le asigna.
evento 6: Proceso C pide recurso 1 y como lo está ocupando el proceso A, espera.
evento 7: Proceso B pide recurso 3 y se bloquea porque lo ocupa el proceso C.
evento 8: Proceso A pide recurso 2 y se bloquea porque lo ocupa el proceso B.
En la figura 5.1 se observa como el 'resource graph' fue evolucionando hasta que se presentó el deadlock, el
cual significa que se puede viajar por las flechas desde un proceso o recurso hasta regresar al punto de partida.
En el deadlock están involucrados los procesos A,B y C.
Una vez que un deadlock se detecta, es obvio que el sistema está en problemas y lo único que resta por hacer
es una de dos cosas: tener algún mecanismo de suspensión o reanudación [Deitel93] que permita copiar todo el
contexto de un proceso incluyendo valores de memoria y aspecto de los periféricos que esté usando para
reanudarlo otro día, o simplemente eliminar un proceso o arrebatarle el recurso, causando para ese proceso la
pérdida de datos y tiempo.
6. PRINCIPIOS EN EL MANEJO DE ENTRADA - SALIDA
El código destinado a manejar la entrada y salida de los diferentes periféricos en un sistema operativo es de
una extensión considerable y sumamente complejo. Resuelve la necesidades de sincronizar, atrapar
interrupciones y ofrecer llamadas al sistema para los programadores. En esta sección se repasarán los
principios más importantes a tomar en cuenta en este módulo del sistema operativo.
6.1 Dispositivos de Entrada - Salida
Los dispositivos de entrada salida se dividen, en general, en dos tipos: dispositivos orientados a bloques y
dispositivos orientados a caracteres. Los dispositivos orientados a bloques tienen la propiedad de que se
pueden direccionar, esto es, el programador puede escribir o leer cualquier bloque del dispositivo realizando
primero una operación de posicionamiento sobre el dispositivo. Los dispositivos más comunes orientados a
bloques son los discos duros, la memoria, discos compactos y, posiblemente, unidades de cinta. Por otro lado,
los dispositivos orientados a caracteres son aquellos que trabajan con secuencias de byes sin importar su
longitud ni ningúna agrupación en especial. No son dispositivos direccionables. Ejemplos de estos dispositivos
son el teclado, la pantalla o display y las impresoras.
La clasificación anterior no es perfecta, porque existen varios dispositivos que generan entrada o salida que no
pueden englobarse en esas categorías. Por ejemplo, un reloj que genera pulsos. Sin embargo, aunque existan
algunos periféricos que no se puedan categorizar, todos están administrados por el sistema operativo por medio
de una parte electrónica - mecánica y una parte de software. [Tan92].
6.2 Controladores de Dispositivos ( Terminales y Discos Duros)
Los controladores de dispositivos (también llamados adaptadores de dispositivos) son la parte electrónica de los
periféricos, el cual puede tener la forma de una tarjeta o un circuito impreso integrado a la tarjeta maestra de la
computadora. Por ejemplo, existen controladores de discos que se venden por separado y que se insertan en
una ranura de la computadora, o existen fabricantes de computadoras que integran esa funcionalidad en la
misma tarjeta en que viene la unidad central de procesamiento (tarjeta maestra).
Los controladores de dispositivos generalmente trabajan con voltajes de 5 y 12 volts con el dispositivo
propiamente, y con la computadora a través de interrupciones. Estas interrupciones viajan por el 'bus' de la
computadora y son recibidos por el CPU el cual a su vez pondrá en ejecución algún programa que sabrá qué
hacer con esa señal. A ese programa se le llama 'manejador de disposito' (device driver). Algunas veces el
mismo controlador contiene un pequeño programa en una memoria de solo lectura o en memoria de acceso
aleatoria no volátil y re-escribible que interactúa con el correspondiente manejador en la computadora. En la
figura 6.1 se muestra un esquema simple de dispositivos orientados a bloques y otros a caracteres.
Por ejemplo, la terminal (CRT) tiene un 'chip' que se encarga de enviar cadenas de bits por medio de un cable
serial que a su vez son recibidos por un controlador de puerto serial en la computadora. Este 'chip' también se
encarga de leer secuencias de bits que agrupa para su despiegue en la pantalla o para ejecutar algunas
funciones de control. Lo importante en todos estos dispositivos es que se debe ejercer un mecanismo para
sincronizar el envío y llegada de datos de manera concurrente.
Para intercambiar datos o señales entre la computadora y los controladores, muchas veces se usan registros o
secciones predefinidas de la memoria de la computadora. A este esquema se le llama 'manejo de entrada -
salida mapeado por memoria' (memory mapped I/O). Por ejmplo, para una IBM PC se muestran los vectores de
interrupción y las direcciones para la entrada -salida en la tabla 6.1.
Controlador
Dirección(Hex)
Vector de Interrupción
Reloj
040 - 043
8
Teclado
060 - 063
9
Disco Duro
320 - 32F
13
Impresora
378 - 37F
15
Monitor Mono
380 - 3BF
-
Monitor Color
3D0 - 3DF
-
Disco Flexible
3F0 - 3F7
14
Tabla 6.1 Direcciones de Mapeo de Entrada - Salida
6.3 Acceso Directo a Memoria (DMA)
El acceso directo a memoria se inventó con el propósito de liberar al CPU de la carga de atender a algunos
controladores de dispositivos. Para comprender su funcionamiento vale la pena revisar cómo trabaja un
controlador sin DMA. Cuando un proceso requiere algunos bloques de un dispositivo, se envia una señal al
controlador con la dirección del bloque deseado. El controlador lo recibe a través del 'bus' y el proceso puede
estar esperando la respuesta (trabajo síncrono) o puede estar haciendo otra cosa (trabajo asíncrono). El
controlador recibe la señal y lee la dirección del bus. Envía a su vez una o varias señales al dispositivo
mecánico (si es que lo hay) y espera los datos. Cuando los recibe los escribe en un buffer local y envía una
señal al CPU indicándole que los datos están listos. El CPU recibe esta interrupción y comienza a leer byte por
byte o palabra por palabra los datos del buffer del controlador (a través del device driver) hasta terminar la
operación.
Como se ve, el CPU gasta varios ciclos en leer los datos deseados. El DMA soluciona ese problema de la
manera siguiente. Cuando un proceso requiere uno o varios bloques de datos, el CPU envía al controlador la
petición junto con el número de bytes deseados y la dirección de en dónde quiere que se almacenen de
regreso. El DMA actuará como un 'cpu secundario' [Stal92] en cuanto a que tiene el poder de tomar el control
del 'bus' e indicarle al verdadero CPU que espere. Cuando el controlador tiene listos los datos, el DMA 'escucha'
si el 'bus' está libre aprovechando esos ciclos para ir leyendo los datos del buffer del controlador e ir
escribiéndolos en el área de memoria que el CPU le indicó. Cuando todos los datos fueron escritos, se le envía
una interrupción al CPU para que use los datos. El ahorro con el DMA es que el CPU ya no es interrumpido
(aunque sí puede ser retardado por el DMA) salvando así el 'cambio de contexto' y además el DMA
aprovechará aquellos ciclos en que el 'bus' no fue usado por el CPU.
El hecho de que los controladores necesiten buffers internos se debe a que conforme ellos reciban datos de los
dispositivos que controlan, los deben poder almacenar temporalmente, ya que el CPU no está listo en todo
momento para leerlos.
Mister Wong
Portal para Investigadores y Profesionales
