Sistemas Operativos

Sistemas Operativos

Indice
1.
Introducción
2. Tipos de Sistemas
Operativos
3. Sistemas de Archivos

4.
Administración de la Memoria
5. Administración de
Procesos

7. Núcleos de
Sistemas Operativos
8.
Caso de Estudio: UNIX
9.
Caso de Estudio: VMS
10.
Caso de Estudio: OS/2
11.
Caso de Estudio: WindowsNT
12.
Caso de Estudio: Procesos en Linux
13.
Bibliografía.

1. Introducción

A finales de los 40's el uso de computadoras
estaba restringido a aquellas empresas o
instituciones
que podían pagar su alto precio, y no
existían los sistemas
operativos. En su lugar, el programador debía tener un
conocimiento y
contacto profundo con el hardware, y en el
infortunado caso de que su programa fallara,
debía examinar los valores de
los registros y
páneles de luces indicadoras del estado de
la computadora
para determinar la causa del fallo y poder corregir
su programa,
además de enfrentarse nuevamente a los procedimientos de
apartar tiempo del
sistema y poner a
punto los compiladores,
ligadores, etc; para volver a correr su programa, es decir,
enfrentaba el problema del procesamiento serial ( serial
processing ).

La importancia de los sistemas
operativos nace históricamente desde los 50's, cuando
se hizo evidente que el operar una computadora
por medio de tableros enchufables en la primera generación
y luego por medio del trabajo en lote en la segunda
generación se podía mejorar notoriamente, pues el
operador realizaba siempre una secuencia de pasos repetitivos, lo
cual es una de las características contempladas en la
definición de lo que es un programa. Es decir, se
comenzó a ver que las tareas mismas del operador
podían plasmarse en un programa, el cual a través
del tiempo y por su
enorme complejidad se le llamó "Sistema
Operativo". Así, tenemos entre los primeros sistemas
operativos al Fortran Monitor System
( FMS ) e IBSYS .

Posteriormente, en la tercera generación de computadoras
nace uno de los primeros sistemas
operativos con la filosofía de administrar una
familia de
computadoras: el OS/360 de IBM. Fue este un proyecto tan
novedoso y ambicioso que enfrentó por primera vez una
serie de problemas
conflictivos debido a que anteriormente las computadoras eran
creadas para dos propósitos en general: el comercial y el
científico. Así, al tratar de crear un solo
sistema
operativo para computadoras que podían dedicarse a un
propósito, al otro o ambos, puso en evidencia la
problemática del trabajo en equipos de análisis, diseño
e implantación de sistemas grandes.
El resultado fue un sistema del cual
uno de sus mismos diseñadores patentizó su
opinión en la portada de un libro: una
horda de bestias prehistóricas atascadas en un foso de
brea.

Surge también en la tercera generación de
computadoras el concepto de la
multiprogramación, porque debido al alto costo de las
computadoras era necesario idear un esquema de trabajo que
mantuviese a la unidad central de procesamiento más tiempo
ocupada, así como el encolado (spooling ) de trabajos para
su lectura hacia
los lugares libres de memoria o la
escritura de
resultados. Sin embargo, se puede afirmar que los sistemas
durante la tercera generación siguieron siendo
básicamente sistemas de lote.

En la cuarta generación la electrónica avanza hacia la integración a gran escala, pudiendo
crear circuitos con
miles de transistores en
un centímetro cuadrado de silicón y ya es posible
hablar de las computadoras personales y las estaciones de
trabajo. Surgen los conceptos de interfaces amigables intentando
así atraer al público en general al uso de las
computadoras como herramientas
cotidianas. Se hacen populares el MS-DOS y
UNIX en estas
máquinas. También es común
encontrar clones de computadoras personales y una multitud de
empresas
pequeñas ensamblándolas por todo el mundo.

Para mediados de los 80's, comienza el auge de las redes de computadoras y la
necesidad de sistemas
operativos en red y sistemas operativos
distribuidos. La red mundial Internet se va haciendo
accesible a toda clase de instituciones
y se comienzan a dar muchas soluciones ( y
problemas ) al
querer hacer convivir recursos
residentes en computadoras con sistemas operativos diferentes.
Para los 90's el paradigma de
la programación
orientada a objetos cobra auge, así como el manejo de
objetos desde los sistemas operativos. Las aplicaciones intentan
crearse para ser ejecutadas en una plataforma específica y
poder ver sus
resultados en la pantalla o monitor de
otra diferente (por ejemplo, ejecutar una simulación
en una máquina con UNIX y ver los
resultados en otra con DOS ). Los niveles de interacción
se van haciendo cada vez más profundos.

2. Tipos de sistemas
operativos

En esta sección se describirán las características que clasifican a los
sistemas operativos, básicamente se cubrirán tres
clasificaciones: sistemas operativos por su estructura
(visión interna), sistemas operativos por los servicios que
ofrecen y, finalmente, sistemas operativos por la forma en que
ofrecen sus servicios
(visión externa).

Sistemas Operativos por su Estructura
Según [Alcal92], se deben observar dos tipos de requisitos
cuando se construye un sistema operativo, los cuales son:
Requisitos de usuario: Sistema fácil de usar y de
aprender, seguro,
rápido y adecuado al uso al que se le quiere destinar.
Requisitos del software: Donde se engloban
aspectos como el mantenimiento,
forma de operación, restricciones de uso, eficiencia,
tolerancia
frente a los errores y flexibilidad.
A continuación se describen las distintas estructuras
que presentan los actuales sistemas operativos para satisfacer
las necesidades que de ellos se quieren obtener.

Estructura monolítica.
Es la estructura de
los primeros sistemas operativos constituídos
fundamentalmente por un solo programa compuesto de un conjunto de
rutinas entrelazadas de tal forma que cada una puede llamar a
cualquier otra (Ver Fig. 2). Las características
fundamentales de este tipo de estructura son:
Construcción del programa final a base de
módulos compilados separadamente que se unen a
través del ligador.
Buena definición de parámetros de enlace entre las
distintas rutinas existentes, que puede provocar mucho
acoplamiento.
Carecen de protecciones y privilegios al entrar a rutinas que
manejan diferentes aspectos de los recursos de
la
computadora, como memoria, disco,
etc.
Generalmente están hechos a medida, por lo que son
eficientes y rápidos en su ejecución y gestión, pero por lo mismo carecen de
flexibilidad para soportar diferentes ambientes de trabajo o
tipos de aplicaciones.

Estructura jerárquica.
A medida que fueron creciendo las necesidades de los usuarios y
se perfeccionaron los sistemas, se hizo necesaria una mayor
organización del software, del sistema
operativo, donde una parte del sistema contenía subpartes
y esto organizado en forma de niveles.

Se dividió el sistema operativo en pequeñas
partes, de tal forma que cada una de ellas estuviera
perfectamente definida y con un claro interface con el resto de
elementos.

Se constituyó una estructura jerárquica o de
niveles en los sistemas operativos, el primero de los cuales fue
denominado THE (Technische Hogeschool, Eindhoven), de Dijkstra,
que se utilizó con fines didácticos (Ver Fig. 3).
Se puede pensar también en estos sistemas como si fueran
`multicapa'. Multics y Unix caen en esa categoría.

En la estructura anterior se basan prácticamente la
mayoría de los sistemas operativos actuales. Otra forma de
ver este tipo de sistema es la denominada de anillos
concéntricos o "rings" (Ver Fig. 4).
En el sistema de anillos, cada uno tiene una apertura, conocida
como puerta o trampa (trap), por donde pueden entrar las llamadas
de las capas inferiores. De esta forma, las zonas más
internas del sistema operativo o núcleo del sistema
estarán más protegidas de accesos indeseados desde
las capas más externas. Las capas más internas
serán, por tanto, más privilegiadas que las
externas.

Máquina Virtual.
Se trata de un tipo de sistemas operativos que presentan una
interface a cada proceso,
mostrando una máquina que parece idéntica a la
máquina real subyacente. Estos sistemas operativos separan
dos conceptos que suelen estar unidos en el resto de sistemas: la
multiprogramación y la máquina extendida. El
objetivo de
los sistemas operativos de máquina virtual es el de
integrar distintos sistemas operativos dando la sensación
de ser varias máquinas
diferentes.

El núcleo de estos sistemas operativos se denomina
monitor virtual y tiene como misión
llevar a cabo la multiprogramación, presentando a los
niveles superiores tantas máquinas virtuales como se
soliciten. Estas máquinas virtuales no son máquinas
extendidas, sino una réplica de la máquina real, de
manera que en cada una de ellas se pueda ejecutar un sistema
operativo diferente, que será el que ofrezca la
máquina extendida al usuario (Ver Fig. 5).

Cliente-servidor (
Microkernel)
El tipo más reciente de sistemas operativos es el
denominado Cliente-servidor, que
puede ser ejecutado en la mayoría de las computadoras, ya
sean grandes o pequeñas.
Este sistema sirve para toda clase de aplicaciones por tanto, es
de propósito general y cumple con las mismas actividades
que los sistemas operativos convencionales.

El núcleo tiene como misión
establecer la
comunicación entre los clientes y los
servidores.
Los procesos
pueden ser tanto servidores como
clientes. Por
ejemplo, un programa de aplicación normal es un cliente que llama
al servidor correspondiente para acceder a un archivo o
realizar una operación de entrada/salida sobre un
dispositivo concreto. A su
vez, un proceso
cliente puede actuar como servidor para otro." [Alcal92]. Este
paradigma
ofrece gran flexibilidad en cuanto a los servicios posibles en el
sistema final, ya que el núcleo provee solamente funciones muy
básicas de memoria, entrada/salida, archivos y
procesos,
dejando a los servidores proveer la mayoría que el usuario
final o programador puede usar. Estos servidores deben tener
mecanismos de seguridad y
protección que, a su vez, serán filtrados por el
núcleo que controla el hardware. Actualmente se
está trabajando en una versión de UNIX que
contempla en su diseño
este paradigma.
Sistemas Operativos por Servicios
Esta clasificación es la más comúnmente
usada y conocida desde el punto de vista del usuario final. Esta
clasificación se comprende fácilmente con el cuadro
sinóptico que a continuación se muestra en la
Fig. 6.

Monousuarios
Los sistemas operativos monousuarios son aquéllos que
soportan a un usuario a la vez, sin importar el número de
procesadores que
tenga la computadora o
el número de procesos o tareas que el usuario pueda
ejecutar en un mismo instante de tiempo. Las computadoras
personales típicamente se han clasificado en este
renglón.

Multiusuarios
Los sistemas operativos multiusuarios son capaces de dar servicio a
más de un usuario a la vez, ya sea por medio de varias
terminales conectadas a la computadora o por medio de sesiones
remotas en una red de comunicaciones. No importa el número de
procesadores en
la máquina ni el número de procesos que cada
usuario puede ejecutar simultáneamente.

Monotareas
Los sistemas monotarea son aquellos que sólo permiten una
tarea a la vez por usuario. Puede darse el caso de un sistema
multiusuario y monotarea, en el cual se admiten varios usuarios
al mismo tiempo pero cada uno de ellos puede estar haciendo solo
una tarea a la vez.

Multitareas
Un sistema operativo multitarea es aquél que le permite al
usuario estar realizando varias labores al mismo tiempo. Por
ejemplo, puede estar editando el código
fuente de un programa durante su depuración mientras
compila otro programa, a la vez que está recibiendo
correo
electrónico en un proceso en background. Es
común encontrar en ellos interfaces gráficas orientadas al uso de menús
y el ratón, lo cual permite un rápido intercambio
entre las tareas para el usuario, mejorando su productividad.

Uniproceso
Un sistema operativo uniproceso es aquél que es capaz de
manejar solamente un procesador de la
computadora, de manera que si la computadora tuviese más
de uno le sería inútil. El ejemplo más
típico de este tipo de sistemas es el DOS y MacOS.

Multiproceso
Un sistema operativo multiproceso se refiere al número de
procesadores del sistema, que es más de uno y éste
es capaz de usarlos todos para distribuir su carga de trabajo.
Generalmente estos sistemas trabajan de dos formas:
simétrica o asimétricamente. Cuando se trabaja de
manera asimétrica, el sistema operativo selecciona a uno
de los procesadores el cual jugará el papel de
procesador
maestro y servirá como pivote para distribuir la carga a
los demás procesadores, que reciben el nombre de esclavos.
Cuando se trabaja de manera simétrica, los procesos o
partes de ellos (threads) son enviados indistintamente a
cualesquira de los procesadores disponibles, teniendo,
teóricamente, una mejor distribución y equilibrio en
la carga de trabajo bajo este esquema.

Se dice que un thread es la parte activa en memoria y
corriendo de un proceso, lo cual puede consistir de un
área de memoria, un conjunto de registros con
valores
específicos, la pila y otros valores de
contexto. Us aspecto importante a considerar en estos sistemas es
la forma de crear aplicaciones para aprovechar los varios
procesadores. Existen aplicaciones que fueron hechas para correr
en sistemas monoproceso que no toman ninguna ventaja a menos que
el sistema operativo o el compilador detecte secciones de
código
paralelizable, los cuales son ejecutados al mismo tiempo en
procesadores diferentes. Por otro lado, el programador puede
modificar sus algoritmos y
aprovechar por sí mismo esta facilidad, pero esta
última opción las más de las veces es
costosa en horas hombre y muy
tediosa, obligando al programador a ocupar tanto o más
tiempo a la paralelización que a elaborar el algoritmo
inicial.

Sistemas Operativos por la Forma de Ofrecer sus
Servicios
Esta clasificación también se refiere a una
visión externa, que en este caso se refiere a la del
usuario, el cómo accesa los servicios. Bajo esta
clasificación se pueden detectar dos tipos principales:
sistemas operativos de red y sistemas operativos
distribuídos.

Sistemas Operativos de Red
Los sistemas operativos de red se definen como aquellos que tiene
la capacidad de interactuar con sistemas operativos en otras
computadoras por medio de un medio de transmisión con el
objeto de intercambiar información, transferir archivos,
ejecutar comandos remotos
y un sin fin de otras actividades. El punto crucial de estos
sistemas es que el usuario debe saber la sintaxis de un cinjunto
de comandos o
llamadas al sistema para ejecutar estas operaciones,
además de la ubicación de los recursos que desee
accesar. Por ejemplo, si un usuario en la computadora hidalgo
necesita el archivo matriz.pas que
se localiza en el directorio /software/codigo en la
computadora morelos bajo el sistema operativo UNIX, dicho usuario
podría copiarlo a través de la red con los comandos
siguientes: hidalgo% hidalgo% rcp morelos:/software/codigo/matriz.pas .
hidalgo%. En este caso, el comando rcp que significa "remote
copy" trae el archivo indicado de la computadora morelos y lo
coloca en el directorio donde se ejecutó el mencionado
comando. Lo importante es hacer ver que el usuario puede accesar
y compartir muchos recursos.

Sistemas Operativos Distribuídos
Los sistemas operativos distribuídos abarcan los servicios
de los de red, logrando integrar recursos ( impresoras,
unidades de respaldo, memoria, procesos, unidades centrales de
proceso ) en una sola máquina virtual que el usuario
accesa en forma transparente. Es decir, ahora el usuario ya no
necesita saber la ubicación de los recursos, sino que los
conoce por nombre y simplementa los usa como si todos ellos
fuesen locales a su lugar de trabajo habitual. Todo lo anterior
es el marco
teórico de lo que se desearía tener como
sistema operativo distribuído, pero en la realidad no se
ha conseguido crear uno del todo, por la complejidad que suponen:
distribuír los procesos en las varias unidades de
procesamiento, reintegrar sub-resultados, resolver problemas de
concurrencia y paralelismo, recuperarse de fallas de algunos
recursos distribuídos y consolidar la protección y
seguridad entre
los diferentes componentes del sistema y los usuarios. Los
avances
tecnológicos en las redes de área local y
la creación de microprocesadores
de 32 y 64 bits lograron que computadoras mas o menos baratas
tuvieran el suficiente poder en forma autónoma para
desafiar en cierto grado a los mainframes, y a la vez se dio la
posibilidad de intercomunicarlas, sugiriendo la oportunidad de
partir procesos muy pesados en cálculo en
unidades más pequeñas y distribuirlas en los varios
microprocesadores para luego reunir los
sub-resultados, creando así una máquina virtual en
la red que exceda en poder a un mainframe. El sistema integrador
de los microprocesadores que hacer ver a las varias memorias,
procesadores, y todos los demás recursos como una sola
entidad en forma transparente se le llama sistema operativo
distribuído. Las razones para crear o adoptar sistemas
distribuídos se dan por dos razones principales: por
necesidad ( debido a que los problemas a resolver son
inherentemente distribuídos ) o porque se desea tener
más confiabilidad y disponibilidad de recursos. En el
primer caso tenemos, por ejemplo, el control de los
cajeros automáticos en diferentes estados de la
república. Ahí no es posible ni eficiente mantener
un control
centralizado, es más, no existe capacidad de
cómputo y de entrada/salida para dar servicio a los
millones de operaciones por
minuto. En el segundo caso, supóngase que se tienen en una
gran empresa varios
grupos de
trabajo, cada uno necesita almacenar grandes cantidades de
información en disco duro con
una alta confiabilidad y disponibilidad. La solución puede
ser que para cada grupo de
trabajo se asigne una partición de disco duro en
servidores diferentes, de manera que si uno de los servidores
falla, no se deje dar el servicio a todos, sino sólo a
unos cuantos y, más aún, se podría tener un
sistema con discos en espejo ( mirror ) a través de la
red,de manera que si un servidor se cae, el servidor en espejo
continúa trabajando y el usuario ni cuenta se da de estas
fallas, es decir, obtiene acceso a recursos en forma
transparente.

Ventajas de los Sistemas Distribuídos
En general, los sistemas distribuídos (no solamente los
sistemas operativos) exhiben algunas ventajas sobre los sistemas
centralizados que se describen enseguida.

• Economía: El cociente precio/desempeño de la suma del poder de los
  procesadores separados contra el poder de uno solo centralizado
  es mejor cuando están distribuídos.
• Velocidad: Relacionado con el punto anterior, la
  velocidad
  sumada es muy superior.
• Confiabilidad: Si una sola máquina falla, el
  sistema total sigue funcionando.
• Crecimiento: El poder total del sistema puede irse
  incrementando al añadir pequeños sistemas, lo
  cual es mucho más difícil en un sistema
  centralizado y caro.
• Distribución: Algunas aplicaciones requieren de
  por sí una distribución física.

Por otro lado, los sistemas distribuídos
también exhiben algunas ventajas sobre sistemas aislados.
Estas ventajas son:

• Compartir datos: Un
  sistema distribuído permite compartir datos
  más fácilmente que los sistemas aislados, que
  tendrian que duplicarlos en cada nodo para lograrlo.
• Compartir dispositivos: Un sistema distribuído
  permite accesar dispositivos desde cualquier nodo en forma
  transparente, lo cual es imposible con los sistemas aislados.
  El sistema distribuído logra un efecto
  sinergético.
• Comunicaciones: La comunicación persona a
  persona es
  factible en los sistemas distribuídos, en los sistemas
  aislados no. _ Flexibilidad: La distribución de las
  cargas de trabajo es factible en el sistema
  distribuídos, se puede incrementar el poder de
  cómputo.

Desventajas de los Sistemas Distribuídos
Así como los sistemas distribuídos exhiben grandes
ventajas, también se pueden identificar algunas
desventajas, algunas de ellas tan serias que han frenado la
producción comercial de sistemas operativos
en la actualidad. El problema más importante en la
creación de sistemas distribuídos es el software:
los problemas de compartición de datos y recursos es tan
complejo que los mecanismos de solución generan mucha
sobrecarga al sistema haciéndolo ineficiente. El checar,
por ejemplo, quiénes tienen acceso a algunos recursos y
quiénes no, el aplicar los mecanismos de protección
y registro de
permisos consume demasiados recursos. En general, las soluciones
presentes para estos problemas están aún en
pañales.

Otros problemas de los sistemas operativos
distribuídos surgen debido a la concurrencia y al
paralelismo. Tradicionalmente las aplicaiones son creadas para
computadoras que ejecutan secuencialmente, de manera que el
identificar secciones de código `paralelizable' es un
trabajo ardúo, pero necesario para dividir un proceso
grande en sub-procesos y enviarlos a diferentes unidades de
procesamiento para lograr la distribución. Con la
concurrencia se deben implantar mecanismos para evitar las
condiciones de competencia, las
postergaciones indefinidas, el ocupar un recurso y estar
esperando otro, las condiciones de espera circulares y ,
finalmente, los "abrazos mortales" (deadlocks). Estos problemas
de por sí se presentan en los sistemas operativos
multiusuarios o multitareas, y su tratamiento en los sistemas
distribuídos es aún más complejo, y por lo
tanto, necesitará de algoritmos
más complejos con la inherente sobrecarga
esperada.

Por otro lado, en el tema de sistemas distribuídos
existen varios conceptos importantes referentes al hadware que no
se ven en este trabajo: multicomputadoras, multiprocesadores,
sistemas acoplados débil y fuertemente, etc. En
páginas 366 – 376 puede encontrarse material relacionado a
estos conceptos.

3. Tipos de sistemas de
archivos

Un sistema de archivos ( file system ) es una estructura de
directorios con algún tipo de organización el cual nos permite almacenar,
crear y borrar archivos en diferenctes formatos. En esta
sección se revisarán conceptos importantes
relacionados a los sistemas de archivos.

Almacenamiento Físico de Datos
En un sistema de cómputo es evidente que existe la
necesidad por parte de los usuarios y aplicaciones de almacenar
datos en algún medio, a veces por periodos largos y a
veces por instantes. cada aplicación y cada usuario debe
tener ciertos derechos con sus datos, como
son el poder crearlos y borrarlos, o cambialos de lugar;
así como tener privacidad contra otros usuarios o
aplicaciones. El subsistema de archivos del sistema operativo se
debe encargar de estos detalles, además de establecer el
formato físico en el cual almacenará los datos en
discos duros,
cintas o discos flexibles. Debe ser conocido por todos que
tradicionalmente la información en los sistemas modernos
se almacena en discos duros,
flexibles y unidades de disco óptico, y en todos ellos se
comparten algunos esquemas básicos para darles formato
físico: las superficies de almacenamiento
son divididas en círculos concéntricos llamados
"pistas" y cada pista se divide en "sectores". A la unión
lógica
de varias pistas a través de varias superficies
"paralelas" de almacenamiento se
les llama "cilindros", los cuales son inspeccionados al momento
de lectura o
escritura de
datos por las respectivas unidades fisicas llamadas "cabezas".
Las superficies de almacenamiento reciben el nombre de "platos" y
generalmente están en movimiento
rotatorio para que las cabezas accesen a las pistas que los
componen. Los datos se escriben a través de los sectores
en las pistas y cilindros modificando las superficies por medio
de las cabezas.

El tiempo que una cabeza se tarda en ir de una pista a otra se
le llama "tiempo de búsqueda" y dependerá de la
distancia entre la posición actual y la distancia a la
pista buscada. El tiempo que tarda una cabeza en ir del sector
actual al sector deseado se le llama tiempo de latencia y depende
de la distancia entre sectores y la velocidad de
rotación del disco. El impacto que tiene las lecturas y
escrituras sobre el sistema está determinado por la
tecnología
usada en los platos y cabezas y por la forma de resolver las
peticiones de lectura y escritura, es decir, los algoritmos de
planificación.

Algoritmos de planificación de peticiones
Los algoritmos de planificación de peticiones de lectura y
escritura a discos se encargan de registrar dichas peticiones y
de responderlas en un tiempo razonable. Los algoritmos más
comunes para esta tarea son:

• Primero en llegar, primero en ser servido ( FIFO ): Las
  peticiones son encoladas de acuerdo al orden en que llegaron y
  de esa misma forma se van leyendo o escribiendo las mismas. La
  ventaja de este algoritmo es
  su simplicidad y no causa sobrecarga, su desventaja principal
  es que no aprovecha para nada ninguna característica de
  las peticiones, de manera que es muy factible que el brazo del
  disco se mueva muy ineficientemente, ya que las peticiones
  pueden tener direcciones en el disco unas muy alejadas de
  otras. Por ejemplo, si se están haciendo peticiones a
  los sectores 6,10,8,21 y 4, las mismas serán resueltas
  en el mismo orden. _ Primero el más cercano a la
  posición actual: En este algoritmo las peticiones se
  ordenan de acuerdo a la posición actual de la cabeza
  lectora, sirviendo primero a aquellas peticiones más
  cercanas y reduciendo, así, el movimiento
  del brazo, lo cual constituye la ventaja principal de este
  algoritmo. Su desventaja consiste en que puede haber
  solicitudes que se queden esperando para siempre, en el
  infortunado caso de que existan peticiones muy alejadas y en
  todo momento estén entrando peticiones que estén
  más cercanas. Para las peticiones 6,10,8,21 y 4, las
  mismas serán resueltas en el orden 4,6,8,10 y 21.
• Por exploración ( algoritmo del elevador ): En este
  algoritmo el brazo se estará moviendo en todo momento
  desde el perímetro del disco hacia su centro y
  viceversa, resolviendo las peticiones que existan en la
  dirección que tenga en turno. En este
  caso las peticiones 6,10,8,21 y 4 serán resueltas en el
  orden 6,10,21,8 y 4; es decir, la posición actual es 6 y
  como va hacia los sectores de mayor numeración (hacia el
  centro, por ejemplo), en el camino sigue el sector 10, luego el
  21 y ese fue el más central, así que ahora el
  brazo resolverá las peticiones en su camino hacia afuera
  y la primera que se encuentra es la del sector 8 y luego la 4.
  La ventaja de este algoritmo es que el brazo se moverá
  mucho menos que en FIFO y evita la espera indefinida; su
  desventaja es que no es justo, ya que no sirve las peticiones
  en el orden en que llegaron, además de que las
  peticiones en los extremos interior y exterior tendrán
  un tiempo de respuesta un poco mayor.
• Por exploración circular: Es una variación
  del algoritmo anterior, con la única diferencia que al
  llegar a la parte central, el brazo regresa al exterior sin
  resolver ninguna petición, lo cual proveerá un
  tiempo de respuesta más cercana al promedio para todas
  las peticiones, sin importar si están cercas del centro
  o del exterior.

Asignación del espacio de almacenamiento
El subsistema de archivos se debe encargar de localizar espacio
libre en los medios de
almacenamiento para guardar archivos y para después
borrarlos, renombrarlos o agrandarlos. Para ello se vale de
localidades especiales que contienen la lista de archivos creados
y por cada archivo una serie de direcciones que contienen los
datos de los mismos. Esas localidades especiales se llaman
directorios. Para asignarle espacio a los archivos existen tres
criterios generales que se describen enseguida.

• Asignación contigua: Cada directorio contiene la los
  nombres de archivos y la dirección del bloque inicial de cada
  archivo, así como el tamaño total de los mismos.
  Por ejemplo, si un archivo comienza en el sector 17 y mide 10
  bloques, cuando el archivo sea accesado, el brazo se
  moverá inicialmente al bloque 17 y de ahí hasta
  el 27. Si el archivo es borrado y luego creado otro más
  pequeño, quedarán huecos inútiles entre
  archivos útiles, lo cual se llama fragmentación
  externa.
• Asignación encadenada: Con este criterio los
  directorios contienen los nombres de archivos y por cada uno de
  ellos la dirección del bloque inicial que compone al
  archivo. Cuando un archivo es leído, el brazo va a esa
  dirección inicial y encuentra los datos iniciales junto
  con la dirección del siguiente bloque y así
  sucesivamente. Con este criterio no es necesario que los
  bloques estén contiguos y no existe la
  fragmentación externa, pero en cada "eslabón" de
  la cadena se desperdicia espacio con las direcciones mismas. En
  otras palabras, lo que se crea en el disco es una lista
  ligada.
• Asignación con índices ( indexada ): En este
  esquema se guarda en el directorio un bloque de índices
  para cada archivo, con apuntadores hacia todos sus bloques
  constituyentes, de mabnera que el acceso directo se agiliza
  notablemente, a cambio de
  sacrificar varios bloques para almacenar dichos apuntadores.
  Cuando se quiere leer un archivo o cualquiera de sus partes, se
  hacen dos accesos: uno al bloque de índices y otro a la
  dirección deseada. Este es un esquema excelente para
  archivos grandes pero no para pequeños, porque la
  relación entre bloques destinados para índices
  respecto a los asignados para datos es incosteable.

Métodos de acceso en los sistemas de archivos.
Los métodos de
acceso se refiere a las capacidades que el subsistema de archivos
provee para accesar datos dentro de los directorios y medios de
almacenamiento en general. Se ubican tres formas generales:
acceso secuencial, acceso directo y acceso directo indexado.

• Acceso secuencial: Es el método
  más lento y consiste en recorrer los componentes de un
  archivo uno en uno hasta llegar al registro
  deseado. Se necesita que el orden lógico de los
  registros sea igual al orden físico en el medio de
  almacenamiento. Este tipo de acceso se usa comunmente en cintas
  y cartuchos.
• Acceso directo: Permite accesar cualquier sector o registro
  inmediatamente, por medio de llamadas al sistema como la de
  seek. Este tipo de acceso es rápido y se usa
  comúnmente en discos duros y discos o archivos manejados
  en memoria de acceso aleatorio. _ Acceso directo indexado: Este
  tipo de acceso es útil para grandes volúmenes de
  información o datos. Consiste en que cada arcivo tiene
  una tabla de apuntadores, donde cada apuntador va a la
  dirección de un bloque de índices, lo cual
  permite que el archivo se expanda a través de un espacio
  enorme. Consume una cantidad importante de recursos en las
  tablas de índices pero es muy rápido.

Operaciones soportadas por el subsistema de archivos
Independientemente de los algoritmos de asignación de
espacio, de los métodos de
acceso y de la forma de resolver las peticiones de lectura y
escritura, el subsistema de archivos debe proveer un conjunto de
llamadas al sistema para operar con los datos y de proveer
mecanismos de protección y seguridad. Las operaciones
básicas que la mayoría de los sistemas de archivos
soportan son:

• Crear ( create ) : Permite crear un archivo sin datos, con
  el propósito de indicar que ese nombre ya está
  usado y se deben crear las estructuras
  básicas para soportarlo.
• Borrar ( delete ): Eliminar el archivo y liberar los
  bloques para su uso posterior.
• Abrir ( open ): Antes de usar un archivo se debe abrir para
  que el sistema conozca sus atributos, tales como el
  dueño, la fecha de modificación, etc. _ Cerrar (
  close ): Después de realizar todas las operaciones
  deseadas, el archivo debe cerrarse para asegurar su integridad
  y para liberar recursos de su control en la
  memoria.
• Leer o Escribir ( read, write ): Añadir
  información al archivo o leer el caracter o una cadena
  de caracteres a partir de la posición actual. _
  Concatenar ( append ): Es una forma restringida de la llamada
  `write', en la cual sólo se permite añadir
  información al final del archivo. _ Localizar ( seek ):
  Para los archivos de acceso directo se permite posicionar el
  apuntador de lectura o escritura en un registro aleatorio, a
  veces a partir del inicio o final del archivo.
• Leer atributos: Permite obtener una estructura con todos
  los atributos del archivo especificado, tales como permisos de
  escritura, de borrado, ejecución, etc.
• Poner atributos: Permite cambiar los atributos de un
  archivo, por ejemplo en UNIX, donde todos los dispositivos se
  manejan como si fueran archivos, es posible cambiar el comportamiento de una terminal con una de estas
  llamadas.
• Renombrar ( rename ): Permite cambiarle el nombre e incluso
  a veces la posición en la
  organización de directorios del archivo
  especificado. Los subsistemas de archivos también
  proveen un conjunto de llamadas para operar sobre directorios,
  las más comunies son crear, borrar, abrir, cerrar,
  renombrar y leer. Sus funcionalidades son obvias, pero existen
  también otras dos operaciones no tan comunes que son la
  de `crear una liga' y la de `destruir la liga'. La
  operación de crear una liga sirve para que desde
  diferentes puntos de la
  organización de directorios se pueda accesar un
  mismo directorio sin necesidad de copiarlo o duplicarlo. La
  llamada a `destruir nla liga' lo que hace es eliminar esas
  referencias, siendo su efecto la de eliminar las ligas y no el
  directorio real. El directorio real es eliminado hasta que la
  llmada a `destruir liga' se realiza sobre él.

Algunas facilidades extras de los sistemas de archivos
Algunos sistemas de archivos proveen herramientas
al administrador del
sistema para facilitarle la vida. Las más notables es la
facilidad de compartir archivos y los sistemas de `cotas'.

La facilidad de compartir archivos se refiere a la posibilidad
de que los permisos de los archivos o directorios dejen que un
grupo de
usuarios puedan accesarlos para diferentes operaciones" leer,
escribir, borrar, crear, etc. El dueño verdadero es quien
decide qué permisos se aplicarán al grupo e,
incluso, a otros usuarios que no formen parte de su grupo. La
facilidad de `cotas' se refiere a que el sistema de archivos es
capaz de llevar un control para que cada usuario pueda usar un
máximo de espacio en disco duro. Cuando el usuario excede
ese límite, el sistema le envía un mensaje y le
niega el permiso de seguir escribiendo, obligándolo a
borrar algunos archivos si es que quiere almacenar otros o que
crezcan. La versión de UNIX SunOS contiene esa
facilidad.

Sistemas de Archivos Aislados
Los sistemas de archivos aislados son aquellos que residen en una
sola computadora y no existe la posibilidad de que, aún
estando en una red, otros sistemas
puedan usar sus directorios y archivos. Por ejemplo, los archivos
en discos duros en el sistema MS-DOS
clásico se puede ver en esta categoría.

Sistemas de Archivos Compartidos o de Red
Estos sistemas de archivos es factible accesarlos y usarlos desde
otros nodos en una red. Generalmente existe un `servidor' que es
la computadora en donde reside el sistema de archivos
físicamente, y por otro lado están los `clientes',
que se valen del servidor para ver sus archivos y directorios de
manera como si estuvieran localmente en el cliente. Algunos
autores les llaman a estos sistemas de archivos `sistemas de
archivos distribuídos' lo cual no se va a discutir en este
trabajo.

Los sistemas de archivos compartidos en red más
populares son los provistos por Netware, el Remote Filke Sharing
( RFS en UNIX ), Network File System ( NFS de Sun Microsystems )
y el Andrew File System ( AFS ). En general, lo que proveen los
servidores es un medio de que los clientes, localmente, realicen
peticiones de operaciones sobre archivos los cuales con
`atrapadas' por un `driver' o un `módulo' en el
núcleo del sistema operativo, el cual se comunica con el
servidor a través de la red y la operación se
ejecuta en el servidor. Existen servidores de tipo "stateless y
no-stateless". Un servidor "stateless" no registra el estado de
las operaciones sobre los archivos, de manera que el cliente se
encarga de todo ese trabajo. La ventaja de este esquema es que si
el servidor falla, el cliente no perderá
información ya que ésta se guarda en memoria
localmente, de manera que cuando el servidor reanude su servicio
el cliente proseguirá como si nada hubiese sucedido. Con
un servidor "no-stateless", esto no es posible.

La protección sobre las operaciones se lleva a cabo
tanto el los clientes como en el servidor: si el usuario quiere
ejecutar una operación indebida sobre un archivo,
recibirá un mensaje de error y posiblemente se
envíe un registro al subsistema de `seguridad' para
informar al administrador del
sistema de dicho intento de violación.

En la práctica, el conjunto de permisos que cada
usuario tiene sobre el total de archivos se almacena en
estructuras llamadas `listas de acceso' ( access lists
).

Tendencias actuales
Con el gran auge de las redes de comunicaciones
y su incremento en el ancho de banda, la proliferación de
paquetes que ofrecen la compartición de archivos es
común. Los esquemas más solicitados en la industria es
el poder accesar los grandes volúmenes de
información que residen en grandes servidores desde las
computadoras personales y desde otros servidores también.
Es una realidad que la solución más socorrida en
las empresas pequeñas es usar Novell Netware
en un servidor 486 o superior y accesar los archivos desde
máquinas similares.

A veces se requieren soluciones más complejas con
ambientes heterogéneos:
diferentes sistemas operativos y diferentes arquitecturas. Uno de
los sistemas de archivos más expandidos en estaciones de
trabajo es el NFS, y prácticamente todas las versiones de
UNIX traen instalado un cliente y hasta un servidor de este
servicio. Es posible así que una gran cantidad de
computadoras personales (de 10 a 80 ) accesen grandes
volúmenes de información o paquetería (desde
1 a 8 Gygabytes ) desde una sola estación de trabajo, e
incluso tener la flexibilidad de usar al mismo tiempo servidores
de Novell y NFS.
Soluciones similares se dan con algunos otros paquetes
comerciales, pero basta ya de `goles'. Lo importante aquí
es observar que el mundo se va moviendo poco a poco hacia
soluciones distribuídas, y hacia la estandarización
que, muchas veces, es `de facto'.

4. Administracion de la
memoria

En esta sección se describirán las técnicas
más usuales en el manejo de memoria, revisando los
conceptos relevantes. Se abarcarán los esquemas de manejo
simple de memoria real, la multiprogramación en memoria
real con sus variantes, el concepto de
`overlays', la multiprogramación con intercambio y los
esquemas de manejo de memoria
virtual.

Panorama general
Un vistazo al material que se va a cubrir en esta sección
se muestra en la
figura 4.1. Es una gráfica en donde se especifican, en
términos generales, los conceptos más importantes
en cuanto a las técnicas
empleadas en el manejo de memoria.

Manejo de memoria en sistemas monousuario sin intercambio
Este esquema es aún muy frecuente en México y
se usa principalmente en sistemas monousuario y monotarea, como
son las computadoras personales con DOS. Bajo este esquema, la
memoria real es tomada para almacenar el programa que se
esté ejecutando en un momento dado, con la visible
desventaja de que si se está limitado a la cantidad de
RAM disponible
únicamente. La organización física bajo este
esquema es muy simple: El sistema operativo se ubica en las
localidades superiores o inferiores de la memoria, seguido por
algunos manejadores de dispositivos ( `drivers' ). Esto deja un
espacio contiguo de memoria disponible que es tomado por los
programas del
usuario, dejando generalmente la ubicación de la pila (`
stack' ) al último, con el objetivo de
que ésta pueda crecer hasta el máximo posible.
Estas diferentes opciones se pueden ver en la figura 4.2. Como es
obvio, bajo estos esquemas no se requieren algoritmos
sofisticados para asignar la memoria a los diferentes procesos,
ya que éstos son ejecutados secuencialmente conforme van
terminando.

Multiprogramación en memoria real
En los 60's, las empresas e instituciones que habían
invertido grandes sumas en la compra de equipo de cómputo
se dieron cuenta rápidamente que los sistemas en lote
invertían una gran cantidad de tiempo en operaciones de
entrada y salida, donde la intervención de la unidad
central de procesamiento era prácticamente nula, y se
comenzaron a preguntar cómo hacer que se mantuviera
más tiempo ocupada. Fue así como nació el
concepto de multiprogramación, el cual consiste en la idea
de poner en la memoria física más de un proceso al
mismo tiempo, de manera que si el que se está ejecutando
en este momento entraba en un periodo de entrada/salida, se podia
tomar otro proceso para que usara la unidad central de
procesamiento. De esta forma, la memoria fisica se dividía
en secciones de tamaño suficiente para contener a varios
programas.

De esta manera, si un sistema gastaba en promedio 60% de su
tiempo en entrada/salida por proceso, se podía aprovechar
más el CPU. Anterior
a esto, el CPU se
mantenía ese mismo porcentaje ocioso; con la nueva
técnica, el tiempo promedio ocioso disminuye de la
siguiente forma. Llámese al tiempo promedio que el CPU
está ocupado `grado de multiprogramación'. Si el
sistema tuviese un solo proceso siempre, y éste gastara
60% en entrada/salida, el grado de multiprogramación
sería 1 – 60% = 40% = 0.4. Con dos procesos, para que el
CPU esté ocioso se necesita que ambos procesos necesiten
estar haciendo entrada/salida, es decir, suponiendo que son
independientes, la probabilidad de
que ambos estén en entrada/salida es el producto de
sus probabilidades, es decir, 0.6×0.6 = 0.36. Ahora, el grado de
multiprogramación es 1 – (probabilidad de
que ambos procesos estén haciendo entrada/salida) = 1 –
0.36 = 0.64.

Como se ve, el sistema mejora su uso de CPU en un 24% al
aumentar de uno a dos procesos. Para tres procesos el grado de
multiprogramación es 1 – (0.6) 3 = 0.784, es decir, el
sistema está ocupado el 78.4% del tiempo. La
fórmula del grado de multiprogramación, aunque es
muy idealista, pudo servir de guía para planear un posible
crecimiento con la compra de memoria real, es decir, para obtener
el punto en que la adición de procesos a RAM ya no
incrementa el uso de CPU.

Dentro del esquema de multiprogramación en memoria real
surgieron dos problemas interesantes: la protección y la
relocalización.

El problema de la relocalización
Este problema no es exclusivo de la multiprogramación en
memoria real, sino que se presentó aquí pero se
sigue presentando en los esquemas de memoria
virtual también. Este problema consiste en que los
programas que necesitan cargarse a memoria real ya están
compilados y ligados, de manera que internamente contienen una
serie de referencias a direcciones de instrucciones, rutinas y
procedimientos
que ya no son válidas en el espacio de direcciones de
memoria real de la sección en la que se carga el programa.
Esto es, cuando se compiló el programa se definieron o
resolvieron las direcciones de memoria de acuerdo a la
sección de ese momento, pero si el programa se carga en
otro dia en una sección diferente, las direcciones reales
ya no coinciden. En este caso, el manejador de memoria puede
solucionar el problema de dos maneras: de manera `estática'
o de manera `dinámica'. La solución `estática'
consiste en que todas las direcciones del programa se vuelvan a
recalcular al momento en que el programa se carga a memoria, esto
es, prácticamente se vuelve a recompilar el programa. La
solución `dinámica' consiste en tener un registro que
guarde la dirección base de la sección que va a
contener al programa. Cada vez que el programa haga una
referencia a una dirección de memoria, se le suma el
registro base para encontrar la dirección real. Por
ejemplo, suponga que el programa es cargado en una sección
que comienza en la dirección 100. El programa hará
referencias a las direcciones 50,52,54. Pero el contenido de esas
direcciones no es el deseado, sino las direcciones 150, 152 y
154, ya que ahí comienza el programa. La suma de 100 + 50,
…,etcétera se hacen al tiempo de ejecución. La
primera solución vale más la pena que la segunda si
el programa contiene ciclos y es largo, ya que consumirá
menos tiempo en la resolución inicial que la segunda
solución en las resoluciones en línea.

El problema de la protección
Este problema se refiere a que, una vez que un programa ha sido
caragado a memoria en algún segmento en particular, nada
le impide al programador que intente direccionar ( por error o
deliberadamente ) localidades de memoria menores que el
límite inferior de su programa o superiores a la
dirección mayor; es decir, quiere referenciar localidades
fuera de su espacio de direcciones. Obviamente, este es un
problema de protección, ya que no es legal leer o escribir
en áreas de otros programas.

La solución a este problema también puede ser el
uso de un registro base y un registro límite. El registro
base contiene la dirección del comienzo de la
sección que contiene al programa, mientras que el
límite contiene la dirección donde termina. Cada
vez que el programa hace una referencia a memoria se checa si cae
en el rango de los registros y si no es así se
envía un mensaje de error y se aborta el programa.

Particiones fijas o particiones variables
En el esquema de la multiprogramación en memroia real se
manejan dos alternativas para asignarle a cada programa su
partición correspondiente: particiones de tamaño
fijo o particiones de tamaño variable. La alternativa
más simple son las particiones fijas. Dichas particiones
se crean cuando se enciende el equipo y permanecerán con
los tamaños iniciales hasta que el equipo se apague. Es
una alternativa muy vieja, quien hacía la división
de particiones era el operador analizando los tamaños
estimados de los trabajos de todo el día. Por ejemplo, si
el sistema tenía 512 kilobytes de RAM, podia asignar 64 k
para el sistema operativo, una partición más de 64
k, otra de 128k y una mayor de 256 k. Esto era muy simple, pero
inflexible, ya que si surgían trabajos urgentes, por
ejemplo, de 400k, tenían que esperar a otro día o
reparticionar, inicializando el equipo desde cero. La otra
alternativa, que surgió después y como necesidad de
mejorar la alternativa anterior, era crear particiones contiguas
de tamaño variable. Para esto, el sistema tenía que
mantener ya una estructura de
datos suficiente para saber en dónde habían
huecos disponibles de RAM y de dónde a dónde
habían particiones ocupadas por programas en
ejecución. Así, cuando un programa requería
ser cargado a RAM, el sistema analizaba los huecos para saber si
había alguno de tamaño suficiente para el programa
que queria entrar, si era así, le asignaba el espacio. Si
no, intentaba relocalizar los programas existentes con el
propósito de hacer contiguo todo el espacio ocupado,
así como todo el espacio libre y así obtener un
hueco de tamaño suficiente. Si aún así el
programa no cabía, entonces lo bloqueaba y tomaba otro. El
proceso con el cual se juntan los huecos o los espacios ocupados
se le llama `compactación'. El lector se habrá dado
cuenta ya de que surgen varios problemas con los esquemas de
particiones fijas y particiones variables:
ø En base a qué criterio se elige el mejor
tamaño de partición para un programa ? Por ejemplo,
si el sistema tiene dos huecos, uno de 18k y otro de 24 k para un
proceso que desea 20 k, ø Cual se le asigna ? Existen
varios algoritmos para darle respuesta a la pregunta anterior,
los cuales se ennumeran y describen enseguida.

• Primer Ajuste: Se asigna el primer hueco que sea mayor al
  tamaño deseado.
• Mejor Ajuste: Se asigna el hueco cuyo tamaño exceda
  en la menor cantidad al tamaño deseado. Requiere de una
  búsqueda exhaustiva.
• Peor Ajuste: Se asigna el hueco cuyo tamaño exceda
  en la mayor cantidad al tamaño deseado. Requiere
  también de una búsqueda exhaustiva.
• El Siguiente Ajuste: Es igual que el `primer ajuste' con la
  diferencia que se deja un apuntador al lugar en donde se
  asignó el último hueco para realizar la siguiente
  búsqueda a partir de él.
• Ajuste Rápido: Se mantienen listas ligadas separadas
  de acuerdo a los tamaños de los huecos, para así
  buscarle a los procesos un hueco más rápido en la
  cola correspondiente.

Otro problema que se vislumbra desde aquí es que, una
vez asignado un hueco, por ejemplo, con "el peor ajuste", puede
ser que el proceso requiriera 12 kilobytes y que el hueco
asignado fuera de 64 kilobytes, por lo cual el proceso va a
desperdiciar una gran cantidad de memoria dentro de su
partición, lo cual se le llama `fragmentación
interna'.

Por otro lado, conforme el sistema va avanzando en el
día, finalizando procesos y comenzando otros, la memoria
se va configurando como una secuencia contigua de huecos y de
lugares asignados, provocando que existan huecos, por ejemplo, de
12 k, 28k y 30 k, que sumados dan 70k, pero que si en ese momento
llega un proceso pidiéndolos, no se le pueden asignar ya
que no son localidades contiguas de memoria ( a menos que se
realice la compactación ). Al hecho de que aparezcan
huecos no contiguos de memoria se le llama `fragmentación
externa'.

De cualquier manera, la multiprogramación fue un avance
significativo para el mejor aprovechamiento de la unidad central
de procesamiento y de la memoria misma, así como dio pie
para que surgieran los problemas de asignación de memoria,
protección y relocalización, entre otros.

Los overlays
Una vez que surgió la multiprogramación, los
usuarios comenzaron a explorar la forma de ejecutar grandes
cantidades de código en áreas de memoria muy
pequeñas, auxiliados por algunas llamadas al sistema
operativo. Es así como nacen los `overlays'.

Esta técnica consiste en que el programador divide
lógicamente un programa muy grande en secciones que puedan
almacenarse el las particiones de RAM. Al final de cada
sección del programa ( o en otros lugares necesarios ) el
programador insertaba una o varias llamadas al sistema con el fin
de descargar la sección presente de RAM y cargar otra, que
en ese momento residía en disco duro u otro medio de
almacenamiento secundario. Aunque esta técnica era eficaz
( porque resolvía el problema ) no era eficiente ( ya que
no lo resolvía de la mejor manera ). Esta solución
requería que el programador tuviera un conocimiento
muy profundo del equipo de cómputo y de las llamadas al
sistema operativo. Otra desventaja era la portabilidad de un
sistema a otro: las llamadas cambiaban, los tamaños de
particiones también. Resumiendo, con esta técnica
se podían ejecutar programas más grandes que las
particiones de RAM, donde la división del código
corría a cuenta del programador y el control a cuenta del
sistema operativo.

Multiprogramación en memoria virtual
La necesidad cada vez más imperiosa de ejecutar programas
grandes y el crecimiento en poder de las unidades centrales de
procesamiento empujaron a los diseñadores de los sistemas
operativos a implantar un mecanismo para ejecutar
automáticamente programas más grandes que la
memoria real disponible, esto es, de ofrecer `memoria
virtual'.

La memoria virtual se llama así porque el programador
ve una cantidad de memoria mucho mayor que la real, y en realidad
se trata de la suma de la memoria de almacenamiento primario y
una cantidad determinada de almacenamiento secundario. El sistema
operativo, en su módulo de manejo de memoria, se encarga
de intercambiar programas enteros, segmentos o páginas
entre la memoria real y el medio de almacenamiento secundario. Si
lo que se intercambia son procesos enteros, se habla entonces de
multiprogramación en memoria real, pero si lo que se
intercambian son segmentos o páginas, se puede hablar de
multiprogramación con memoria virtual.

La memoria virtual se apoya en varias técnicas
interesantes para lograr su objetivo. Una de las teorias
más fuertes es la del `conjunto de trabajo', la cual se
refiere a que un programa o proceso no está usando todo su
espacio de direcciones en todo momento, sino que existen un
conjunto de localidades activas que conforman el `conjunto de
trabajo'. Si se logra que las páginas o segmentos que
contienen al conjunto de trabajo estén siempre en RAM,
entonces el programa se desempeñará muy bien.

Otro factor importante es si los programas exhiben un
fenómeno llamado `localidad', lo cual quiere decir que
algunos programas tienden a usar mucho las instrucciones que
están cercanas a la localidad de la instrucción que
se está ejecutando actualmente.

Paginación pura
La paginación pura en el majejo de memoria consiste en que
el sistema operativo divide dinámicamente los programas en
unidades de tamaño fijo ( generalmente múltiplos de
1 kilobyte ) los cuales va a manipular de RAM a disco y
viceversa. Al proceso de intercambiar páginas, segmentos o
programas completos entre RAM y disco se le conoce como
`intercambio' o `swapping'. En la paginación, se debe
cuidar el tamño de las páginas, ya que si
éstas son muy pequeñas el control por parte del
sistema operativo para saber cuáles están en RAM y
cuales en disco, sus direcciones reales, etc; crece y provoca
mucha `sobrecarga' (overhead). Por otro lado, si las
páginas son muy grandes, el overhead disminuye pero
entonces puede ocurrir que se desperdicie memoria en procesos
pequeños. Debe haber un equilibrio.

Uno de los aspectos más importantes de la
paginación, asi como de cualquier esquema de memoria
virtual, es la forma de traducir una dirección virtual a
dirección real. Para explicarlo, obsérvese la
figura

Como se observa, una dirección virtual `v' = ( b,d)
está formada por un número de página virtual
`b' y un desplazamiento `d'. Por ejemplo, si el sistema ofrece un
espacio de direcciones virtuales de 64 kilobytes, con
páginas de 4 kilobytes y la RAM sólo es de 32
kilobytes, entonces tenemos 16 páginas virtuales y 8
reales. La tabla de direcciones virtuales contiene 16 entradas,
una por cada página virtual. En cada entrada, o registro
de la tabla de direcciones virtuales se almacenan varios datos:
si la página está en disco o en memoria,
quién es el dueño de la página, si la
página ha sido modificada o es de lectura nada mas, etc.
Pero el dato que nos interesa ahora es el número de
página real que le corresponde a la página virtual.
Obviamente, de las 16 virtuales, sólo ocho tendrán
un valor de
control que dice que la página está cargada en RAM,
así como la dirección real de la página,
denotada en la figura 4.3 como b' . Por ejemplo, supóngase
que para la página virtual número 14 la tabla dice
que, efectivamente está cargada y es la página real
2 ( dirección de memoria 8192 ). Una vez encontrada la
página real, se le suma el desplazamiento, que es la
dirección que deseamos dentro de la página buscada
( b' + d ).

La tabla de direcciones virtuales a veces está ubicada
en la misma meoria RAM, por lo cual se necesita saber en
qué dirección comienza, en este caso, existe un
registro con la dirección base denotada por la letra `a'
en la figura 4.3.

Cuando se está buscando una página cualquiera y
ésta no está cargada, surge lo que se llama un
`fallo de página' (page fault ). Esto es caro para el
manejador de memoria, ya que tiene que realizar una serie de
pasos extra para poder resolver la dirección deseada y
darle su contenido a quien lo pide. Primero, se detecta que la
página no está presente y entonces se busca en la
tabla la dirección de esta página en disco. Una vez
localizada en disco se intenta cargar en alguna página
libre de RAM. Si no hay páginas libres se tiene que
escoger alguna para enviarla hacia el disco. Una vez escogida y
enviada a disco, se marca su valor de
control en la tabla de direcciones virtuales para indicar que ya
no está en RAM, mientras que la página deseada se
carga en RAM y se marca su valor
para indicar que ahora ya está en RAM. Todo este procedimiento es
caro, ya que se sabe que los accesos a disco duro son del orden
de decenas de veces más lentos que en RAM. En el ejemplo
anterior se mencionó que cuando se necesita descargar una
página de RAM hacia disco se debe de hacer una
elección. Para realizar esta elección existen
varios algoritmos, los cuales se describen enseguida. _ La
primera en entrar, primera en salir: Se escoge la página
que haya entrado primero y esté cargada en RAM. Se
necesita que en los valores de
control se guarde un dato de tiempo. No es eficiente porque no
aprovecha ninguna característica de ningún sistema.
Es justa e imparcial. _ La no usada recientemente: Se escoge la
página que no haya sido usada (referenciada) en el ciclo
anterior. Pretende aprovechar el hecho de la localidad en el
conjunto de trabajo.

• La usada menos recientemente: Es parecida a la anterior,
  pero escoge la página que se usó hace más
  tiempo, pretendiendo que como ya tiene mucho sin usarse es muy
  probable que siga sin usarse en los próximos ciclos.
  Necesita de una búsqueda exhaustiva.
• La no usada frecuentemente: Este algoritmo toma en cuenta
  no tanto el tiempo, sino el número de referencias. En
  este caso cualquier página que se use muy poco, menos
  veces que alguna otra.
• La menos frecuentemente usada: Es parecida a la anterior,
  pero aquí se busca en forma exhaustiva aquella
  página que se ha usado menos que todas las
  demás.
• En forma aleatoria: Elige cualquier página sin
  aprovechar nada. Es justa e imparcial, pero ineficiente.

Otro dato interesante de la paginación es que ya no se
requiere que los programas estén ubicados en zonas de
memoria adyacente, ya que las páginas pueden estar
ubicadas en cualquier lugar de la memoria RAM.

Segmentación pura
La segmentación se aprovecha del hecho de que
los programas se dividen en partes lógicas, como son las
partes de datos, de código y de pila (stack). La segmentación asigna particiones de memoria
a cada segmento de un programa y busca como objetivos el
hacer fácil el compartir segmentos ( por ejemplo
librerías compartidas ) y el intercambio entre memoria y
los medios de almacenamiento secundario.

Por ejemplo, en la versión de UNIX SunOS 3.5, no
existían librerías compartidas para algunas
herramientas, por ejemplo, para los editores de texto
orientados al ratón y menús. Cada vez que un
usuario invocaba a un editor, se tenía que reservar 1
megabyte de memoria. Como los editores son una herramienta muy
solicitada y frecuentemente usada, se dividió en segmentos
para le versión 4.x ( que a su vez se dividen en
páginas ), pero lo importante es que la mayor parte del
editor es común para todos los usuarios, de manera que la
primera vez que cualquier usuario lo invocaba, se reservaba un
megabyte de memoria como antes, pero para el segundo, tercero y
resto de usuarios, cada editor extra sólo consumía
20 kilobytes de memoria. El ahorro es
impresionante. Obsérvese que en la segmentación
pura las particiones de memoria son de tamaño variable, en
contraste con páginas de tamaño fijo en la
paginación pura. También se puede decir que la
segmentación pura tiene una granularidad menor que la
paginación por el tamanó de segmentos versus
tamaño de páginas. Nuevamente, para comprender
mejor la segmentación, se debe dar un repaso a la forma en
que las direcciones virtuales son traducidas a direcciones
reales, y para ellos se usa la figura 4.4. Prácticamente
la traducción es igual que la llevada a cabo en la
paginación pura, tomando en consideracióñ
que el tamaño de los bloques a controlar por la tabla de
traducción son variables, por
lo cual, cada entrada en dicha tabla debe contener la longitud de
cada segmento a controlar. Otra vez se cuenta con un registro
base que contiene la dirección del comienzo de la tabla de
segmentos. La dirección virtual se compone de un
número de segmento (s) y un desplazamiento ( d ) para
ubicar un byte (o palabra ) dentro de dicho segmento. Es
importante que el desplazamiento no sea mayor que el
tamaño del segmento, lo cual se controla simplemente
checando que ese valor sea mayor que la dirección del
inicio del segmento y menor que el inicio sumado al
tamaño.

Una ves dada una dirección virtual v=( s,d ), se
realiza la operación b + s para hallar el registro (o
entrada de la tabla de segmentos ) que contiene la
dirección de inicio del segmento en la memoria real,
denotado por s'. Ya conociendo la dirección de inicio en
memoria real s' sólo resta encontrar el byte o palabra
deseada, lo cual se hace sumándole a s' el valor del
desplazamiento, de modo que la dirección real ® r =
s'+ d.

Cada entrada en la tabla de segmentos tiene un formato similar
al mostrado en la figura 4.5. Se tienen campos que indican la
longitud, los permisos, la presencia o ausencia y
dirección de inicio en memoria real del segmento.

Según amplios experimentos
[Deitel93] sugieren que un tamaño de páginas de
1024 bytes generalmente ofrece un desempeño muy aceptable. Intuitivamente
parecería que el tener páginas del mayor
tamaño posible haría que el desempeño fuera
óptimo pero no es así, a menos que la página
fuera del tamaño del proceso total. No es así con
tamaños grandes de página menores que el proceso,
ya que cuando se trae a memoria principal una página por
motivo de un solo byte o palabra, se están trayendo
muchísimos más bytes de los deseados. La
dependencia entre el número de fallas respecto al
tamaño de las páginas se muestra en la figura
4.6.

Un hecho notable en los sistemas que manejan paginación
es que cuando el proceso comienza a ejecutarse ocurren un gran
número de fallos de página, porque es cuando
está referenciando muchas direcciones nuevas por vez
primera, después el sistema se estabiliza, conforme el
número de marcos asignados se acerca al tamaño del
conjunto de trabajo.

El la figura 4.7 se muestra la relación entre el tiempo
promedio entre fallas de página y el número de
marcos de página asignados a un proceso. Allí se ve
que el tiempo entre fallas decrece conforme se le asignan
más páginas al proceso. La gráfica se curva
en un punto, el cual corresponde a que el proceso tiene un
número de páginas asignado igual al que necesita
para almacenar su conjunto de trabajo. Después de eso, el
asignarle a un proceso más páginas que las de su
conjunto de trabajo ya no conviene, ya que el tiempo promedio
entre fallas permanece sin mucha mejora. Un aspecto curioso de
aumentar el número de páginas a un proceso cuando
el algoritmo de selección
de páginas candidatas a irse a disco es la primera en
entrar primera en salir es la llamada `anomalía FIFO' a
`anomalía de Belady'. Belady encontró ejemplos en
los que un sistema con un número de páginas igual a
tres tenía menos fallas de páginas que un sistema
con cuatro páginas. El ejemplo descrito en [Tanxx] es
injusto. Si se mira con cuidado, obviamente si se compara un
sistema con 10 páginas contra otro de 5, ya de inicio el
primer sistema tendrá 5 fallos de página más
que el de 5, porque se necesitan diez fallos para cargarlo. A
esto debería llamársele `anomalía de Belady
con corrección.

Sistemas combinados
La paginación y la segmentación puras son
métodos de manejo de memoria bastante efectivos, aunque la
mayoría de los sistemas operativos modernos implantan
esquemas combinados, es decir, combinan la paginación y la
segmentación. La idea de combinar estos esquemas se debe a
que de esta forma se aprovechan los conceptos de la
división lógica
de los programas (segmentos) con la granularidad de las
páginas. De esta forma, un proceso estará repartido
en la memoria real en pequeñas unidades (páginas)
cuya liga son los segmentos. También es factible
así el compartir segmentos a medida que las partes
necesitadas de los mismos se van referenciando (páginas).
Para comprender este esquema, nuevamente se verá
cómo se traduce una dirección virtual en una
localidad de memoria real. Para la paginación y
segmentacíon puras se puede decir que el direccionamiento
es `bidimensional' porque se necesitan dos valores para hallar la
dirección real. Para el caso combinado, se puede decir que
se tiene un direccionamiento `tridimensional'. En la figura 4.8 [
Deitel93] se muestran las partes relevantes para lograr la
traducción de direcciones. El sistema debe contar con una
tabla de procesos (TP). Por cada renglón de esa tabla se
tiene un número de proceso y una dirección a una
tabla de segmentos. Es decir, cada proceso tiene una tabla de
segmentos. Cuando un proceso hace alguna referencia a memoria, se
consulta TP para encontrar la tabla de segmentos de ese proceso.
En cada tabla de segmentos de proceso (TSP) se tienen los
números de los segmentos que componen a ese proceso. Por
cada segmento se tiene una dirección a una tabla de
páginas. Cada tabla de páginas tiene las
direcciones de las páginas que componen a un solo
segmento. Por ejemplo, el segmento `A' puede estar formado por
las páginas reales `a','b','c','p' y `x'. El segmento `B'
puede estar compuesto de las páginas `f','g','j','w' y
`z'.

Para traducir una dirección virtual v=(s,p,d) donde `s'
es el segmento, `p' es la página y `d' el desplazamiento
en la página se hace lo siguiente. Primero se ubica de
qué proceso es el segmento y se localiza la tabla de
segmentos de ese proceso en la TP. Con `s' como índice se
encuentra un renglón ( registro) en la tabla de segmentos
de ese proceso y en ese renglón está la
dirección de la tabla de páginas que componen al
segmento. Una vez en la tabla de páginas se usa el valor
`p' como índice para encontrar la dirección de la
página en memoria real. Una vez en esa dirección de
memoria real se encuentra el byte (o palabra) requerido por medio
del valor de `d'.

Ahora, en este esquema pueden haber dos tipos de fallos: por
fallo de página y por fallo de segmento. Cuando se hace
referencia a una dirección y el segmento que la contiene
no está en RAM ( aunque sea parcialmente ), se provoca un
fallo por falta de segmento y lo que se hace es traerlo del medio
de almacenamiento secundario y crearle una tabla de
páginas. Una vez caragado el segmento se necesita
localizar la página correspondiente, pero ésta no
existe en RAM, por lo cual se provoca un fallo de página y
se carga de disco y finalmente se puede ya traer la
dirección deseada por medio del desplazamiento de la
dirección virtual.

La eficiencia de la
traducción de direcciones tanto en paginación pura,
segmentación pura y esquemas combinados se mejora usando
memorias
asociativas para las tablas de páginas y segmentos,
así como memorias cache para guardar los mapeos más
solicitados.

Otro aspecto importante es la estrategia para
cargar páginas ( o segmentos ) a la memoria RAM. Se
usan más comunmente dos estrategias:
cargado de páginas por demanda y
cargado de páginas anticipada. La estrategia de
caragdo por demanda
consiste en que las páginas solamente son llevadas a RAM
si fueron solicitadas, es decir, si se hizo referencia a una
dirección que cae dentro de ellas. La carga anticipada
consiste en tratar de adivinar qué páginas
serán solicitadas en el futuro inmediato y cargarlas de
antemano, para que cuando se pidan ya no ocurran fallos de
página. Ese `adivinar' puede ser que se aproveche el
fenómeno de localidad y que las páginas que se
cargan por anticipado sean aquellas que contienen direcciones
contiguas a la dirección que se acaba de refenciar. De
hecho, el sistema operativo VMS usa un esquema combinado para
cargar páginas: cuando se hace referencia a una
dirección cuya página no está en RAM, se
provoca un fallo de página y se carga esa página
junto con algunas páginas adyacentes. En este caso la
página solicitada se cargó por demanda y las
adyacentes se cargaron por anticipación.

5. Administracion de
procesos

Uno de los módulos más importantes de un
sistema operativo es la de administrar los procesos y tareas del
sistema de cómputo. En esta sección se
revisarán dos temas que componen o conciernen a este
módulo: la planificación del procesador y los
problemas de concurrencia.

Planificación del procesador
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.

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.

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.

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.

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.

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

Problemas de Concurrencia
En los sistemas de tiempo compartido (aquellos con varios
usuarios, procesos, tareas, trabajos que reparten el uso de CPU
entre estos) se presentan muchos problemas debido a que los
procesos compiten por los recursos del sistema. Imagine que un
proceso está escribiendo en la unidad de cinta y se le
termina su turno de ejecución e inmediatamente
después el proceso elegido para ejecutarse comienza a
escribir sobre la misma cinta. El resultado es una cinta cuyo
contenido es un desastre de datos mezclados. Así como la
cinta, existen una multitud de recursos cuyo acceso debe der
controlado para evitar los problemas de la concurrencia.

El sistema operativo debe ofrecer mecanismos para
sincronizar la ejecución de procesos: semáforos,
envío de mensajes, 'pipes', etc. Los semáforos son
rutinas de software (que en su nivel más interno se
auxilian del hardware) para lograr exclusión mutua en el
uso de recursos. Para entender este y otros mecanismos es
importante entender los problemas generales de concurrencia, los
cuales se describen enseguida.

• Condiciones de Carrera o Competencia: La
  condición de carrera (race condition) ocurre cuando dos
  o más procesos accesan un recurso compartido sin
  control, de manera que el resultado combinado de este acceso
  depende del orden de llegada. Suponga, por ejemplo, que dos
  clientes de un banco realizan
  cada uno una operación en cajeros diferentes al mismo
  tiempo.
• El usuario A quiere hacer un depósito. El B un
  retiro. El usuario A comienza la transacción y lee su
  saldo que es 1000. En ese momento pierde su turno de
  ejecución (y su saldo queda como 1000) y el usuario B
  inicia el retiro: lee el saldo que es 1000, retira 200 y
  almacena el nuevo saldo que es 800 y termina. El turno de
  ejecución regresa al usuario A el cual hace su
  depósito de 100, quedando saldo = saldo + 100 = 1000 +
  100 = 1100. Como se ve, el retiro se perdió y eso le
  encanta al usuario A y B, pero al banquero no le convino esta
  transacción. El error pudo ser al revés, quedando
  el saldo final en 800.
• Postergación o Aplazamiento Indefinido(a): Esto
  se mencionó en el apartado anterior y consiste en el
  hecho de que uno o varios procesos nunca reciban el suficiente
  tiempo de ejecución para terminar su tarea. Por ejemplo,
  que un proceso ocupe un recurso y lo marque como 'ocupado' y
  que termine sin marcarlo como 'desocupado'. Si algún
  otro proceso pide ese recurso, lo verá 'ocupado' y
  esperará indefinidamente a que se 'desocupe'.
• Condición de Espera Circular: Esto ocurre cuando
  dos o más procesos forman una cadena de espera que los
  involucra a todos. Por ejemplo, suponga que el proceso A tiene
  asignado el recurso 'cinta' y el proceso B tiene asignado el
  recurso 'disco'. En ese momento al proceso A se le ocurre pedir
  el recurso 'disco' y al proceso B el recurso 'cinta'. Ahi se
  forma una espera circular entre esos dos procesos que se puede
  evitar quitándole a la fuerza un
  recurso a cualquiera de los dos procesos.
• Condición de No Apropiación: Esta
  condición no resulta precisamente de la concurrencia,
  pero juega un papel
  importante en este ambiente.
  Esta condición especifica que si un proceso tiene
  asignado un recurso, dicho recurso no puede
  arrebatársele por ningún motivo, y estará
  disponible hasta que el proceso lo 'suelte' por su
  voluntad.
• Condición de Espera Ocupada: Esta
  condición consiste en que un proceso pide un recurso que
  ya está asignado a otro proceso y la condición de
  no apropiación se debe cumplir. Entonces el proceso
  estará gastando el resto de su time slice checando si el
  recurso fue liberado. Es decir, desperdicia su tiempo de
  ejecución en esperar. La solución más
  común a este problema consiste en que el sistema
  operativo se dé cuenta de esta situación y mande
  a una cola de espera al proceso, otorgándole
  inmediatamente el turno de ejecución a otro
  proceso.
• Condición de Exclusión Mutua: Cuando un
  proceso usa un recurso del sistema realiza una serie de
  operaciones sobre el recurso y después lo deja de usar.
  A la sección de código que usa ese recurso se le
  llama 'región crítica'. La condición de
  exclusión mutua establece que solamente se permite a un
  proceso estar dentro de la misma región crítica.
  Esto es, que en cualquier momento solamente un proceso puede
  usar un recurso a la vez. Para lograr la exclusión mutua
  se ideo también el concepto de 'región
  crítica'. Para logar la exclusión mutua
  generalmente se usan algunas técnicas para lograr entrar
  a la región crítica: semáforos, monitores,
  el algoritmo de Dekker y Peterson, los 'candados'. Para ver una
  descripción de estos algoritmos
  consulte
• Condición de Ocupar y Esperar un Recurso:
  Consiste en que un proceso pide un recurso y se le asigna.
  Antes de soltarlo, pide otro recurso que otro proceso ya tiene
  asignado.

Los problemas descritos son todos importantes para el
sistema operativo, ya que debe ser capaz de prevenir o
corregirlos. Tal vez el problema más serio que se puede
presentar en un ambiente de
concurrencia es el 'abrazo mortal', también llamado
'trabazón' y en inglés
deadlock. El deadlock es una condición que ningún
sistema o conjunto de procesos quisiera exhibir, ya que consiste
en que se presentan al mismo tiempo cuatro condiciones
necesarias: La condición de no apropiación, la
condición de espera circular, la condición de
exclusión mutua y la condición de ocupar y esperar
un recurso. Ante esto, si el deadlock involucra a todos los
procesos del sistema, el sistema ya no podrá hacer algo
productivo. Si el deadlock involucra algunos procesos,
éstos quedarán congelados para siempre.

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.

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.

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

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.

Principios en el Software de Entrada – Salida
Los principios de software en la entrada – salida se resumen en
cuatro puntos: el software debe ofrecer manejadores de
interrupciones, manejadores de dispositivos, software que sea
independiente de los dispositivos y software para usuarios.

Manejadores de interrupciones
El primer objetivo referente a los manejadores de interrupciones
consiste en que el programador o el usuario no debe darse cuenta
de los manejos de bajo nivel para los casos en que el dispositivo
está ocupado y se debe suspender el proceso o sincronizar
algunas tareas. Desde el punto de vista del proceso o usuario, el
sistema simplemente se tardó más o menos en
responder a su petición.

Manejadores de disposisitivos
El sistema debe proveer los manejadores de dispositivos
necesarios para los periféricos, así como ocultar
las peculiaridades del manejo interno de cada uno de ellos, tales
como el formato de la información, los medios
mecánicos, los niveles de voltaje y otros. Por ejemplo, si
el sistema tiene varios tipos diferentes de discos duros, para el
usuario o programador las diferencias técnicas entre ellos
no le deben importar, y los manejadores le deben ofrecer el mismo
conjunto de rutinas para leer y escribir datos.

Software independiente del dispositivo
Este es un nivel superior de independencia
que el ofrecido por los manejadores de dispositivos. Aquí
el sistema operativo debe ser capaz, en lo más posible, de
ofrecer un conjunto de utilerías para accesar
periféricos o programarlos de una manera consistente. Por
ejemplo, que para todos los dispositivos orientados a bloques se
tenga una llamada para decidir si se desea usar 'buffers' o no, o
para posicionarse en ellos.

Software para usuarios
La mayoría de las rutinas de entrada – salida trabajan en
modo privilegiado, o son llamadas al sistema que se ligan a los
programas del usuario formando parte de sus aplicaciones y que no
le dejan ninguna flexibilidad al usuario en cuanto a la
apariencia de los datos. Existen otras librerías en donde
el usuario si tiene poder de decisión (por ejemplo la
llamada a "printf" en el lenguaje
"C"). Otra facilidad ofrecida son las áreas de trabajos
encolados (spooling areas), tales como las de impresión y
correo
electrónico.

Relojes
Los relojes son esenciales para el buen funcionamiento de
cualquier sistema porque juegan un papel decisivo en la
sincronización de procesos, en la calendarización
de trabajos por lote y para la asignación de turnos de
ejecución entre otras tareas relevantes. Generalmente se
cuenta con dos relojes en el sistema: uno que lleva la hora y
fecha del sistema y que oscila entre 50 y 60 veces por segundo y
el reloj que oscila entre 5 y 100 millones de veces por segundo y
que se encarga de enviar interrupciones al CPU de manera
periódica. El reloj de mayor frecuencia sirve para
controlar el tiempo de ejecución de los procesos, para
despertar los procesos que están 'durmiendo' y para lanzar
o iniciar procesos que fueron calendarizados.

Para mantener la hora y fecha del sistema generalmente se usa
un registro alimentado por una pila de alta duración que
almacena estos datos y que se programan de fábrica por
primera vez. Así, aunque se suspenda la energía la
fecha permanece. Para lanzar procesos (chequeo de tiempo ocioso
de un dispositivo, terminación del time slice de un
proceso, etc), se almacena un valor en un registro (valor
QUANTUM) el cual se decrementa con cada ciclo del reloj, y cuando
llega a cero se dispara un proceso que ejecutará las
operaciones necesarias (escoger un nuevo proceso en
ejecución, verificar el funcionamiento del motor del disco
flexible, hacer eco de un caracter del teclado, etc).