Sistemas Operativos

Sistemas operativos

2. Conceptos arquitectónicos
   de las computadoras
3. Introducción a los
   sistemas operativos
4. Procesos
5. Gestión de
   Memoria
6. Comunicación y
   sincronización de procesos
7. Interbloqueos
8. Entrada/Salida
9. Gestión de
   Archivos y Directorios
10. Estudio
    de casos: linux
11. Estudio
    de casos: Windows NT
12. Anexos
13. Conclusiones

Introducción

A través de la historia d la computación se han conocido muchos
sistemas
operativos y cada vez se ha deseado automatizar más
los sistemas
operativos y generarlos con más confiabilidad,
seguridad y
protección para los registros de
los usuarios.

Los sistemas
operativos se han convertido en una herramienta eficaz dentro
del mundo de los negocios y
usuario con maquinas personales, los sistemas
operativos con la ayuda de un buen soporte de hardware puede
ser un patrón importante para el control de
sus registros.

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 [Tan92].

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.

Capitulo 1

Conceptos arquitectónicos de las
computadoras

Estructura y Funcionamiento de la
Computadora

La Computadora
es una máquina destinada a procesar datos. Este
procesamiento involucra dos flujos de información: el de datos y el de
instrucciones. Se parte del flujo de datos que han de ser
procesados. Este flujo de datos es tratado mediante un flujo de
instrucciones de máquina, generado por la
ejecución de un programa, y produce el flujo de datos
resultado.

La memoria
principal se construye con memoria RAM
y memoria ROM. En
ella han de residir los datos a procesar, el programa
máquina a ejecutar y los resultados.

Se denomina programa máquina (o código) al conjunto de instrucciones
máquina que tiene por objeto que la
computadora realice una determinada función.
Los programas
escritos en cualquiera de los lenguajes de
programación han de convertirse en programa
máquina para poder ser
ejecutados por la
computadora.

La unidad aritmética
permite realizar una serie de operaciones
aritméticas y lógicas sobre uno o dos
operándos.

La unidad de control es la que se
encarga de hacer funcionar al conjunto, para lo cual realiza
las siguientes funciones:

• Lee de memoria las
  instrucciones máquina que forman el
  programa.
• Interpreta cada instrucción
  leída.
• Lee los datos de memoria referenciados por cada
  instrucción
• Ejecuta cada instrucción
• Almacena el resultado de cada
  instrucción.

Modelo de programación de la
computadora.

El modelo de
programación a bajo nivel de una
computadora se caracteriza por los siguientes
aspectos:

• Elementos de almacenamiento. en esta
  sección se consideran aquellos elementos de almacenamiento de la computadora que son
  visibles a las instrucciones máquina. En esta
  categoría están incluidos los registros
  generales, el contador de programa, el puntero de pila, el
  registro de
  estado,
  la memoria
  principal y el mapa de E/S.
• Juego de instrucciones.

Con sus correspondientes modos de
direccionamiento. El jugo de instrucciones máquina
define las operaciones que
es capaz de hacer la computadora. Los modos de direccionamiento
determinan la forma en que se especifica la identidad de
los elementos de almacenamiento que invierten en las
instrucciones maquina.

• Secuencia de funcionamiento. Define el modo en
  que se van ejecutando las instrucciones
  máquina.

Niveles de ejecución

La mayoría de las computadoras actuales
presenta dos o más niveles de ejecución. En el
nivel menos permisivo, generalmente llamado nivel de
usuario, la
computadora ejecuta solamente un subconjunto de las
instrucciones máquina, quedando prohibidas las
demás.

Además, el acceso a determinados registros, o a
partes de esos registros, y a determinadas zonas del mapa de
memoria y de E/S también queda prohibido. En el nivel
más permisivo, denominado nivel de núcleo, la computadora
ejecuta todas sus instrucciones sin ninguna restricción
y permite el acceso a todos los registros y mapas de
direcciones.

Secuencia de funcionamiento de la
computadora.

La unidad de control de
la computadora es la que establece el funcionamiento del
mismo.

Este funcionamiento está basado en una
secuencia sencilla, que se repite a alta velocidad

Esta secuencia consiste en tres pasos:

1. Lectura de memoria principal de la instrucción
   máquina apuntada por el contador del
   programa.
2. Incremento del contador de programa para que apunte a
   la siguiente instrucción máquina.
3. Ejecución de la
   instrucción.

Registros de control y estado.

Como se ha indicado anteriormente, la unidad de
control tiene asociada una serie de registros que denominamos
de control y estado. Estos registros dependen de la arquitectura de
la computadora y muchos de ellos se refieren a aspectos que se
analizarán a lo largo del texto, por
lo que no se intentará explicar aquí su función.

Interrupciones.

A nivel físico, una interrupción se
solicita activando una señal que llega a la unidad de
control. El agente generador o solicitante de la
interrupción ha de activar la mencionada señal
cuando necesite que se le atienda, es decir, que se ejecute un
programa que le atienda.

Ante la solicitud de una interrupción, siempre
y cuando esté habilitado ese tipo de
interrupción, la unidad de control realiza un ciclo de
aceptación de interrupción. Este ciclo se lleva a
cabo en cuanto termina la ejecución de la
instrucción máquina que se esté ejecutando
y consiste en las siguientes operaciones:

• Salva algunos registros del procesador,
  como son el de estado y el contador de programa.
• Eleva el nivel de ejecución del procesador,
  pasándolo a núcleo.
• Carga un nuevo valor en el
  contador de programa, por lo que pasa a ejecutar otro
  programa.

El reloj.

El término reloj se aplica a las
computadoras con tres acepciones diferentes, estas tres
acepciones son las siguientes:

• Señal que gobierna el ritmo de
  ejecución de las instrucciones
  máquina.
• Generador de interrupciones
  periódicas.
• Contador de fecha y hora.

Jerarquía de memoria.

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. [Feld93].

Para ver el gráfico seleccione
la opción "Descargar" del menú
superior

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

Para ver el gráfico seleccione la
opción "Descargar" del menú superior

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

Para ver el gráfico seleccione la
opción "Descargar" del menú superior

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.

Capitulo 2

Introducción a los sistemas
operativos

2.1. ¿Qué es un sistema
operativo?

Un sistema operativo es un programa que tiene
encontradas una serie de funciones diferentes cuyo objetivo es
simplificar el manejo y la utilización de la
computadora, haciéndolo seguro y
eficiente.

Maquina desnuda

El término de máquina desnuda se aplica
a una computadora carente de sistema operativo, el
término es interesante porque resalta el hecho de que
una computadora en si misma no hace nada y para realizar una
determinada función es necesario que contenga un sistema
operativo.

Funciones del sistema operativo

Las funciones clásicas del sistema operativo se
pueden agrupar en las tres categorías
siguientes:

• Gestión de los recursos de la
  computadora.
• Ejecución de servicios
  para los programas.
• Ejecución de los mandatos de los
  usuarios.

El sistema operativo como gestor de
recursos

En una computadora actual suelen coexistir varios
programas, del mismo o de varios usuarios, ejecutándose
simultáneamente. Estos programas compiten por los
recursos de la computadora, siendo el sistema operativo el
encargado de arbitrar su asignación y uso. Como
complemento a la gestión de recursos, el sistema operativo
ha de garantizar la protección de unos programas frente
a otros y ha de suministrar información sobre el uso que se hace de
los recursos.

El sistema operativo como máquina
extendida.

El sistema operativo ofrece a los programas un
conjunto de servicios, o llamadas al sistema, que pueden
solicitar cuando lo necesiten, proporcionando a los programas
una visión de máquina extendida. Los servicios se
pueden agrupar en las cuatro clases siguientes:

• Ejecución de programas
• Operaciones de E/S
• Operaciones sobre archivos
• Detección de tratamiento de
  errores.

Concepto de usuario y de grupo de
usuario

Un usuario es una persona
autorizada para utilizar un sistema informático. El
usuario se autentica mediante su nombre de cuenta y su
contraseña o password.

2.2. Arranque de la computadora

El arranque de una computadora actual tiene dos
fases:

• Arranque hardware
• Arranque software

Que por el arranque hardware se entiende que es
la parte dura es decir el inicio o encendido de todos los
componentes de la PC

Ahora el arranque software es el
inicio del sistema operativo en una computadora

2.3. Componentes y estructura del sistema
operativo

El sistema operativo está formado por una serie
de componentes especializados en determinadas funciones. Cada
sistema operativo estructura estos componentes de forma
distinta. En esta sección se describen en primer lugar
los distintos componentes que conforman un sistema
operativo.

Componentes del sistema operativo

Un sistema operativo está formado por tres
capas:

• El núcleo
• Los servicios y el intérprete de mandatos o
  shell.

El núcleo es la parte del sistema operativo que
interacciona directamente con el hardware de la máquina.
Las funciones básicas de manipulación de
menmoria.

Estructura del sistema operativo

Internamente los sistemas operativos estructuralmente
de se clasifican según como se hayan organizado
internamente en su diseño, por esto la
clasificación más común de los sistemas
operativos son:

Sistemas monolíticos

En estos sistemas operativos se escriben como un
conjunto de procedimientos,
cada uno de los cuales puede llamar a cualquiera de los otros
siempre que lo necesite. Cuando se emplea esta técnica,
cada procedimiento
del sistema tiene una interfaz bien definida en términos
de parámetros y resultados, y cada una tiene la libertad de
llamar a cualquiera otra, si la última ofrece
algún cálculo
útil que la primera necesite.

Para construir el programa objeto real del sistema
operativo cuando se usa este método,
se compilan todos los procedimientos
individuales a archivos que
contienen los procedimientos y después se combinan todos
en un solo archivo objeto
con el enlazador.

En términos de ocultamiento de
información, esencialmente no existe ninguno; todo
procedimiento
es visible para todos (al contrario de una estructura que
contiene módulos o paquetes, en los cuales mucha
información es local a un módulo y sólo
pueden llamar puntos de registro
designados oficialmente del exterior del
módulo)

Sistemas operativos estructurados

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 interfase con
el resto de elementos

Cliente-servidor

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.

2.4. Gestión 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
no hay 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, el 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.

2.5. Gestión de memoria

El gestor de memoria es uno de los componentes
principales del sistema operativo. Su actividad se centra
fundamentalmente en la categoría de gestión de
recursos, puesto que tiene por objetivo casi exclusivo la
gestión del recurso memoria, en este sentido se encarga
de:

• Asignar memoria a los procesos para crear su imagen de
  memoria.
• Proporcionar memoria a los procesos cuando la
  soliciten y liberarla cuando así lo
  requieran.
• Tratar los posibles errores de acceso a memoria,
  evitando que unos procesos interfieran en la memoria
  de otros.
• Permitir que los procesos puedan compartir memoria
  entre ellos. De esta forma los procesos podrán
  comunicarse entre ellos.
• Gestionar la jerarquía de memoria y tratar los
  fallos de página en los sistemas con memoria
  virtual.

Servicios

El gestor de memoria ofrece una serie de servicios a
los procesos. Estos son:

• Solicitar memoria
• Liberar memoria
• Compartir memoria.

2.6. Comunicación y sincronización
entre procesos

Los procesos son entes independientes y aislados,
puesto que, por razones de seguridad, no deben interferir unos
con otros. Sin embargo, cuando se divide un trabajo complejo en
varios procesos que cooperan entre sí para realizar ese
trabajo, es necesario que se comuniquen para transmitirse datos
y ordenes y se sincronicen en la ejecución de sus
acciones.
Por tanto, el sistema operativo debe incluir servicios de
comunicación y sincronización entre procesos que,
sin romper los esquemas de seguridad, han de permitir la
cooperación entre ellos.

Servicios de comunicación y
sincronización.

Como se ha visto anteriormente, existen distintos
mecanismos de comunicación y sincronización, cada
uno de los cuales se puede utilizar a través de un
conjunto de servicios propios. Estos mecanismos son entidades
vivas, cuya vida presenta las siguientes fases:

• Creación del mecanismo.
• Utilización del mecanismo.
• Destrucción del mecanismo.

De acuerdo con esto, los servicios básicos de
comunicación, que incluyen todos los mecanismos, son los
siguientes:

• Crear. Permite que el proceso solicite la
  creación del mecanismo.
• Enviar o escribir. Permite que el proceso emisor
  envíe información a otro.
• Recibir o leer. Permite que el proceso receptor
  reciba información de otro.
• Destruir. Permite que el proceso solicite la
  creación o destrucción del mecanismo.

2.7. Gestión de la E/S

Una de las principales funciones de un sistema
operativo es la gestión de los recursos de la
computadora y, en concreto, de los dispositivos
periféricos. El gestor de E/S debe controlar el
funcionamiento de todos los dispositivos de E/S para alcanzar
los siguientes objetivos:

• Facilitar el manejo de los dispositivos periféricos. Para ello ofrecer una
  interfaz sencilla, uniforme y fácil de utilizar entre
  los dispositivos, y gestionar los errores que se pueden
  producir en el acceso a los mismos.
• Ofrecer mecanismos de protección que impidan a
  los usuarios acceder sin control a los dispositivos
  periféricos.

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

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 bytes
sin importar su longitud ni ninguna 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.

2.8. Gestión de Archivos y
directorios.

El servidor de archivos es la parte del sistema
operativo que cubre una de las cuatro clases de funciones que
tiene este en su faceta de máquina extendida. Los
Objetivos
fundamentales del servidor de archivos son los dos
siguientes:

• Facilitar el manejote los dispositivos
  periféricos. Para ello ofrece una visión lógica simplificada de los mismos en
  forma de archivos.
• Proteger a los usuarios, poniendo limitaciones a los
  archivos que es capaz de manipular cada usuario.

Los servicios que se engloban en el servidor de
archivos son de dos tipos:

• Los servicios dirigidos al manejo de datos, o
  archivos.
• Los dirigidos al manejo de los nombres o
  directorios.

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 manera 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 refieren 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 comúnmente 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 archivo 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 comunes 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 la 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
  llamada 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 distribuidos' 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
comparició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 Giga bites
) 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 distribuidas, y hacia la
estandarización que, muchas veces, es `de
facto'.

2.9. Seguridad y protección

La seguridad reviste dos aspectos, uno es garantizar
la identidad de
los usuarios y otro es definir lo que puede hacer cada uno de
ellos. El primer aspecto se trata bajo el término de
autenticación, mientras que el segundo se hace mediante
los privilegios. La seguridad es una de las funciones del
sistema operativo que, para llevarla a cabo, se ha de basar en
los mecanismos de protección que le proporciona el
hardware.

Autenticación.

El objetivo de la autenticación es determinar
que un usuario( persona,
servicio o computadora) es quien dice ser.

Privilegios.

Los privilegios especifican los recursos que puede
acceder cada usuario. Para simplificar la información de
privilegi9os es corriente organizar a los usuarios en grupos,
asignando determinados privilegios a cada grupo.

2.10. Activación del sistema
operativo.

Una vez presentadas las funciones y principales
componentes del sistema operativo, es importante describir
cuáles son las acciones que
activan la ejecución del mismo, el sistema operativo es
un servidor que está a la espera de que se encargue
trabajo.

2.11. Interfaz del programador.

2.13. Historia de los sistemas
operativos

Los Sistemas Operativos, al igual que el Hardware de
los computadores, han sufrido una serie de cambios
revolucionarios llamados generaciones. En el caso del Hardware,
las generaciones han sido marcadas por grandes avances en los
componentes utilizados, pasando de válvulas
( primera generación ) a transistores (
segunda generación ), a circuitos
integrados ( tercera generación), a circuitos
integrados de gran y muy gran escala (cuarta
generación). Cada generación Sucesiva de hardware
ha ido acompañada de reducciones substanciales en los
costos,
tamaño, emisión de calor y
consumo de
energía, y por incrementos notables en velocidad y
capacidad.

Generación Cero (década de
1940)

Los primeros sistemas computacionales no
poseían sistemas operativos. Los usuarios tenían
completo acceso al lenguaje de
la maquina. Todas las instrucciones eran codificadas a
mano.

Primera Generación (década de
1950)

Los sistemas operativos de los años cincuenta
fueron diseñados para hacer mas fluida la
transición entre trabajos. Antes de que los sistemas
fueran diseñados, se perdía un tiempo
considerable entre la terminación de un trabajo y el
inicio del siguiente. Este fue el comienzo de los sistemas de
procesamiento por lotes, donde los trabajos se reunían
por grupos o lotes.
Cuando el trabajo
estaba en ejecución, este tenia control total de la
maquina. Al terminar cada trabajo, el control era devuelto al
sistema operativo, el cual limpiaba y leía e iniciaba
el trabajo
siguiente.

Al inicio de los 50's esto había mejorado un
poco con la introducción de tarjetas
perforadas (las cuales servían para introducir los
programas de lenguajes de máquina), puesto que ya no
había necesidad de utilizar los tableros
enchufables.

Además el laboratorio
de investigación General Motors
implementó el primer sistema operativo para la IBM 701.
Los sistemas de los 50's generalmente ejecutaban una sola
tarea, y la transición entre tareas se suavizaba para
lograr la máxima utilización del sistema. Esto se
conoce como sistemas de procesamiento por lotes de un
sólo flujo, ya que los programas y los datos eran
sometidos en grupos o lotes.

La introducción del transistor a
mediados de los 50's cambió la imagen
radicalmente.

Se crearon máquinas suficientemente confiables
las cuales se instalaban en lugares especialmente
acondicionados, aunque sólo las grandes universidades y
las grandes corporaciones o bien las oficinas del gobierno se
podían dar el lujo de tenerlas.

Para poder correr un trabajo (programa), tenían
que escribirlo en papel (en
Fortran o en lenguaje
ensamblador) y después se perforaría en
tarjetas.
Enseguida se llevaría la pila de tarjetas al cuarto de
introducción al sistema y la entregaría a uno de
los operadores. Cuando la computadora terminara el trabajo, un
operador se dirigiría a la impresora y
desprendería la salida y la llevaría al cuarto de
salida, para que la recogiera el programador.

Segunda Generación (a mitad de la
década de 1960)

La característica de los sistemas operativos
fue el desarrollo
de los sistemas compartidos con multiprogramación, y los
principios
del multiprocesamiento. En los sistemas de
multiprogramación, varios programas de usuario se
encuentran al mismo tiempo en el almacenamiento principal, y el
procesador se cambia rápidamente de un trabajo a otro.
En los sistemas de multiprocesamiento se utilizan varios
procesadores en
un solo sistema computacional, con la finalidad de incrementar
el poder de procesamiento de la maquina.

La independencia de dispositivos aparece
después. Un usuario que desea escribir datos en una
cinta en sistemas de la primera generación tenia que
hacer referencia especifica a una unidad de cinta particular.
En la segunda generación, el programa del usuario
especificaba tan solo que un archivo iba a ser escrito en una
unidad de cinta con cierto número de pistas y cierta
densidad.

Se desarrollo
sistemas compartidos, en la que los usuarios podían
acoplarse directamente con el computador a
través de terminales. Surgieron sistemas de tiempo real,
en que los computadores fueron utilizados en el control de
procesos industriales. Los sistemas de tiempo real se
caracterizan por proveer una respuesta inmediata.

Tercera Generación (mitad de década
1960 a mitad década de 1970)

Se inicia en 1964, con la introducción de
la familia
de computadores Sistema/360 de IBM. Los computadores de esta
generación fueron diseñados como sistemas para
usos generales . Casi siempre eran sistemas grandes,
voluminosos, con el propósito de serlo todo para toda la
gente. Eran sistemas de modos múltiples, algunos de
ellos soportaban simultáneamente procesos por lotes,
tiempo compartido, procesamiento de tiempo real y
multiprocesamiento. Eran grandes y costosos, nunca antes se
había construido algo similar, y muchos de los esfuerzos
de desarrollo terminaron muy por arriba del presupuesto y
mucho después de lo que el planificador marcaba como
fecha de terminación.

Estos sistemas introdujeron mayor complejidad a los
ambientes computacionales; una complejidad a la cual, en un
principio, no estaban acostumbrados los usuarios.

Cuarta Generación (mitad de década de
1970 en adelante)

Los sistemas de la cuarta generación
constituyen el estado actual de la tecnología. Muchos diseñadores y
usuarios se sienten aun incómodos, después de sus
experiencias con los sistemas operativos de la tercera
generación.

Con la ampliación del uso de redes de computadores y
del procesamiento en línea los usuarios obtienen acceso
a computadores alejados geográficamente a través
de varios tipos de terminales.

Los sistemas de seguridad se ha incrementado mucho
ahora que la información pasa a través de varios
tipos vulnerables de líneas de comunicación. La
clave de cifrado esta recibiendo mucha atención; han sido necesario codificar
los datos personales o de gran intimidad para que; aun si los
datos son expuestos, no sean de utilidad a
nadie mas que a los receptores adecuados.

El porcentaje de la población que tiene acceso a un computador
en la década de los ochenta es mucho mayor que nunca y
aumenta rápidamente.

El concepto de
maquinas virtuales es utilizado. El usuario ya no se encuentra
interesado en los detalles físicos de; sistema de
computación que esta siendo accedida. En
su lugar, el usuario ve un panorama llamado maquina virtual
creado por el sistema operativo.

Los sistemas de bases de datos
han adquirido gran importancia. Nuestro mundo es una sociedad
orientada hacia la información, y el trabajo de las
bases de datos
es hacer que esta información sea conveniente accesible
de una manera controlada para aquellos que tienen derechos de
acceso.

Capitulo 3

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

Capitulo 4

Gestión de Memoria

La memoria es uno de los principales recursos de la
computadora, la cual debe de administrarse con mucho cuidado.
Aunque actualmente la mayoría de los sistemas de
cómputo cuentan con una alta capacidad de memoria, de
igual manera las aplicaciones actuales tienen también
altos requerimientos de memoria, lo que sigue generando escasez
de memoria en los sistemas multitarea y/o
multiusuario.

La parte del sistema operativo que administra la
memoria se llama administrador de memoria y su labor consiste
en llevar un registro de las partes de memoria que se
estén utilizando y aquellas que no, con el fin de
asignar espacio en memoria a los procesos cuando éstos
la necesiten y liberándola cuando terminen, así
como administrar el intercambio entre la memoria principal y el
disco en los casos en los que la memoria principal no le pueda
dar capacidad a todos los procesos que tienen necesidad de
ella.

Los sistemas de administración de memoria se pueden
clasificar en dos tipos: los que desplazan los procesos de la
memoria principal al disco y viceversa durante la
ejecución y los que no.

El propósito principal de una computadora es el
de ejecutar programas, estos programas, junto con la
información que accesan deben de estar en la memoria
principal (al menos parcialmente) durante la
ejecución.

Para optimizar el uso del CPU y de la memoria, el
sistema operativo debe de tener varios procesos a la vez en la
memoria principal, para lo cual dispone de varias opciones de
administración tanto del procesador como
de la memoria. La selección de uno de ellos depende
principalmente del diseño del hardware para el sistema.
A continuación se observarán los puntos
correspondientes a la
administración de la memoria.

Memoria
real

La memoria real o principal es en donde son ejecutados
los programas y procesos de una computadora y es el espacio
real que existe en memoria para que se ejecuten los procesos.
Por lo general esta memoria es de mayor costo que la
memoria secundaria, pero el acceso a la información
contenida en ella es de más rápido acceso. Solo
la memoria
cache es más rápida que la principal, pero su
costo es a su vez mayor.

Sin intercambio

Monoprogramación sin intercambio o
paginación

Cuando solo se tiene un proceso que ocupe la memoria a
la vez, el esquema de la
administración de la memoria es el más
sencillo que hay. Sin embargo, éste método ya no
tiene aplicación en la actualidad, ya que era visto en
las computadoras con sistemas operativos de un solo usuario y
una sola tarea. El usuario introducía su disco a la
computadora (por lo general, la máquina no contaba con
disco duro)
y ejecutaba su aplicación, la cual acaparaba toda la
máquina.

Para ver el gráfico seleccione la
opción ¨Bajar trabajo¨ del menú
superior

Fig.1. Ejemplos de distribución de la memoria principal con
un sistema operativo y un solo proceso de usuario

La figura 1 muestra la organización de la
memoria usando este sistema. La memoria se divide entre el
sistema operativo y el proceso de un solo usuario. La
más conocida es la que muestra el inciso c, que es la
usada por las PC’ de IBM. Los controladores de
dispositivo los almacena en memoria ROM, en
un bloque de 8K de la parte superior del espacio de direcciones
de 1M.

El ejemplo más claro de este esquema es el que
podemos ver en el sistema operativo MS-DOS, en que el usuario
escribe un comando al sistema y al ejecutarse el sistema
operativo lo carga a memoria desde el disco y realiza sus
funciones. Cuando el proceso termina la memoria es liberada y
le muestra al usuario el indicador de comandos
(prompt) en la pantalla.

Multiprogramación y uso de
memoria

Esta organización facilita la
programación de una aplicación al dividirla en
dos o más procesos. Además ofrece la capacidad de
tener más de un proceso a la vez en memoria así
puede ofrecer servicios a varios usuarios a la vez.

El esquema de multiprogramación incrementa el
aprovechamiento del CPU, dado que a diferencia de la
monoprogramación en donde solo un proceso reside en
memoria a la vez limitando el uso del procesador a las llamadas
que requiera dicho proceso, desperdiciando un promedio del 80%
del tiempo del procesador. En cambio la
multiprogramación, al tener varios procesos en la
memoria principal y dividiéndose el tiempo de uso del
procesador, logra reducir drásticamente el desperdicio
del procesador.

Multiprogramación con particiones
fijas

Para poder implementar la multiprogramación, se
puede hacer uso de particiones fijas o variables en
la memoria. En el caso de las particiones fijas, la memoria se
puede organizar dividiéndose en diversas partes, las
cuales pueden variar en tamaño. Esta partición la
puede hacer el usuario en forma manual, al
iniciar una sesión con la máquina.

Una vez implementada la partición, hay dos
maneras de asignar los procesos a ella. La primera es mediante
el uso de una cola única (figura 2a) que asigna los
procesos a los espacios disponibles de la memoria conforme se
vayan desocupando. El tamaño del hueco de memoria
disponible es usado para localizar en la cola el primer proceso
que quepa en él. Otra forma de asignación es
buscar en la cola el proceso de tamaño mayor que se
ajuste al hueco, sin embargo hay que tomar en cuenta que tal
método discrimina a los procesos más
pequeños. Dicho problema podría tener
solución si se asigna una partición
pequeña en la memoria al momento de hacer la
partición inicial, el cual sería exclusivo para
procesos pequeños.

Para ver el gráfico seleccione
la opción "Descargar" del menú
superior

Fig. 2. (a) Particiones fijas en memoria con una cola
única de entrada. (b) Particiones fijas en memoria con
colas exclusivas para cada tamaño diferente de la
partición. El espacio asignado a la partición 2
está en desuso.

Esta idea nos lleva a la implementación de otro
método para particiones fijas, que es el uso de
diferentes colas independientes (figura 2b) exclusivas para
cierto rango en el tamaño de los procesos. De esta
manera al llegar un proceso, éste sería asignado
a la cola de tamaño más pequeño que la
pueda aceptar. La desventaja en esta organización es que
si una de las colas tiene una larga lista de procesos en
espera, mientras otra cola esta vacía, el sector de
memoria asignado para ese tamaño de procesos
estaría desperdiciándose.

Con intercambio

Multiprogramación con particiones
variables

Este esquema fue originalmente usado por el sistema
operativo IBM OS/360 (llamado MFT), el cual ya no está
en uso.

El sistema operativo lleva una tabla indicando
cuáles partes de la memoria están disponibles y
cuáles están ocupadas. Inicialmente, toda la
memoria está disponible para los procesos de usuario y
es considerado como un gran bloque o hueco único de
memoria. Cuando llega un proceso que necesita memoria, buscamos
un hueco lo suficientemente grande para el proceso. Si
encontramos uno, se asigna únicamente el espacio
requerido, manteniendo el resto disponible para futuros
procesos que requieran de espacio.

Consideremos el ejemplo de la figura 3, en donde se
cuenta un espacio reservado para el sistema operativo en la
memoria baja de 400K y un espacio disponible para procesos de
usuario de 2160K, siendo un total de memoria del sistema de
2560K. Dada la secuencia de procesos de la figura y usando un
algoritmo de First Come – First Served
(FCFS) se puede asignar de inmediato memoria a los
procesos P1, P2 y P3, creando
el mapa de memoria de la figura 4(a) en el cual queda un hueco
de 260K que ya no puede ser utilizado por el siguiente proceso
dado que no es suficiente para abarcarlo.

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

 Fig. 3. Ejemplo de una división inicial
de memoria y una lista de trabajos.

 Para ver el gráfico
seleccione la opción "Descargar" del menú
superior

Fig. 4. Ejemplo de asignación de procesos en la
memoria principal.

Usando un proceso de asignación
Round-Robin con un quantum de 1 unidad de tiempo, el
proceso P2 terminaría en la unidad de tiempo
14, liberando esa cantidad de memoria, como se muestra en la
figura 4(b). Entonces el sistema operativo checa la lista de
trabajos y asigna el siguiente proceso que quepa en el espacio
de memoria liberado. El proceso P4 produce el mapa
de memoria que se muestra en la figura 4(c). El proceso
P1 terminará en la unidad de tiempo 28 para
producir el mapa de la figura 4(d) y entonces se asigna el
proceso P5 generando el mapa de la figura
4(e).

Cuando a un proceso se le asigna un espacio y es
cargado a la memoria principal, puede entonces competir para el
uso del CPU.

Compactación de memoria

Cuando un proceso llega y necesita memoria, el sistema
operativo busca en la tabla de huecos alguno lo suficientemente
grande para el proceso. Si el hueco es muy grande, lo parte en
dos. Una parte es asignada al proceso y la otra se identifica
como hueco. Cuando el proceso termina y la memoria es liberada,
el espacio es identificado como un hueco más en la tabla
y si el nuevo hueco es adyacente con otro, ambos huecos se unen
formando un solo hueco más grande. En ese momento se
debe de checar si no existen procesos a los que este nuevo
hueco pueda darles cabida.

  Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

Fig. 5. Ejemplo de compactación de huecos no
adyacentes.

En la figura 5 se muestra como se modifica el mapa de
la memoria después de compactar huecos no adyacentes
generados después de intercambios realizados en el
ejemplo de la figura 4.

Asignación dinámica

El proceso de compactación del punto anterior
es una instancia particular del problema de asignación
de memoria dinámica, el cual es el cómo
satisfacer una necesidad de tamaño n con una
lista de huecos libres. Existen muchas soluciones para el
problema. El conjunto de huecos es analizado para determinar
cuál hueco es el más indicado para asignarse. Las
estrategias
más comunes para asignar algún hueco de la tabla
son:

• Primer ajuste: Consiste en asignar el primer hueco
  con capacidad suficiente. La búsqueda puede iniciar ya
  sea al inicio o al final del conjunto de huecos o en donde
  terminó la última búsqueda. La
  búsqueda termina al encontrar un hueco lo
  suficientemente grande.
• Mejor ajuste: Busca asignar el espacio más
  pequeño de los espacios con capacidad suficiente. La
  búsqueda se debe de realizar en toda la tabla, a menos
  que la tabla esté ordenada por tamaño. Esta
  estrategia
  produce el menor desperdicio de memoria posible.
• Peor ajuste: Asigna el hueco más grande. Una
  vez más, se debe de buscar en toda la tabla de huecos a
  menos que esté organizada por tamaño. Esta
  estrategia produce los huecos de sobra más grandes, los
  cuales pudieran ser de más uso si llegan procesos de
  tamaño mediano que quepan en ellos.

Se ha demostrado mediante simulacros que tanto el
primer y el mejor ajuste son mejores que el peor ajuste en
cuanto a minimizar tanto el tiempo del almacenamiento. Ni el
primer o el mejor ajuste es claramente el mejor en
términos de uso de espacio, pero por lo general el
primer ajuste es más rápido.

Administración de la memoria con mapas de
bits

Este tipo de administración divide la memoria
en unidades de asignación, las cuales pueden ser tan
pequeñas como unas cuantas palabras o tan grandes como
varios kilobytes. A cada unidad de asignación le
corresponde un bit en el mapa de bits, el cual toma el valor de
0 si la unidad está libre y 1 si está ocupada (o
viceversa). La figura 6 muestra una parte de la memoria y su
correspondiente mapa de bits.

  Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

Fig. 6. Ejemplo de un mapa de bits para la
administración de la memoria.

Un mapa de bits es una forma sencilla para llevar un
registro de las palabras de la memoria en una cantidad fija de
memoria, puesto que el tamaño del mapa sólo
depende del tamaño de la memoria y el tamaño de
la unidad de asignación.

Administración de la memoria con listas
ligadas

Otra forma de mantener un registro de la memoria es
mediante una lista ligada de los segmentos de memoria asignados
o libres, en donde un segmento puede ser un proceso o un hueco
entre dos procesos. La memoria de la figura 7(a) está
mostrada como una lista ligada de segmentos en la figura 7(b).
Cada entrada de la lista especifica un hueco (H) o un proceso
(P), la dirección donde comienza, su longitud y un
apuntador a la siguiente entrada.

  Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

Fig. 7. Ejemplo de listas ligadas.

En este ejemplo, la lista de segmentos está
ordenada por direcciones, lo que da la ventaja de que al
terminar o intercambiar un proceso, la actualización de
la lista es directa.

Asignación del hueco de
intercambio

En algunos sistemas, cuando el proceso se encuentra en
la memoria, no hay un hueco en el disco asignado a él.
Cuando deba intercambiarse, se deberá asignar un hueco
para él en el área de intercambio del disco. Los
algoritmos para la administración del hueco de
intercambio son los mismos que se utilizan para la
administración de la memoria principal.

En otros sistemas, al caerse un proceso, se le asigna
un hueco de intercambio en el disco. Cuando el proceso sea
intercambiado, siempre pasará al hueco asignado, en vez
de ir a otro lugar cada vez. Cuando el proceso concluya, se
libera el hueco de intercambio. La única diferencia es
que el hueco en disco necesario para un proceso debe
representarse como un número entero de bloques del
disco. Por ejemplo, un proceso de 13.5 K debe utilizar 14K
(usando bloques de 1K).

Fragmentación

La fragmentación es la memoria que queda
desperdiciada al usar los métodos de gestión de
memoria que se vieron en los métodos anteriores. Tanto
el primer ajuste, como el mejor y el peor producen
fragmentación externa.

La fragmentación es generada cuando durante el
reemplazo de procesos quedan huecos entre dos o más
procesos de manera no contigua y cada hueco no es capaz de
soportar ningún proceso de la lista de espera. Tal vez
en conjunto si sea espacio suficiente, pero se
requeriría de un proceso de defragmentación de
memoria o compactación para lograrlo. Esta
fragmentación se denomina fragmentación
externa.

Existe otro tipo de fragmentación conocida como
fragmentación interna, la cual es generada cuando se
reserva más memoria de la que el proceso va realmente a
usar. Sin embargo a diferencia de la externa, estos huecos no
se pueden compactar para ser utilizados. Se debe de esperar a
la finalización del proceso para que se libere el bloque
completo de la memoria.

Memoria
virtual

Paginación

Hasta ahora, los métodos que hemos visto de la
administración de la memoria principal, nos han dejado
con un problema: fragmentación, (huecos en la memoria
que no pueden usarse debido a lo pequeño de su espacio)
lo que nos provoca un desperdicio de memoria
principal.

Una posible solución para la
fragmentación externa es permitir que espacio de
direcciones lógicas lleve a cabo un proceso en
direcciones no contiguas, así permitiendo al proceso
ubicarse en cualquier espacio de memoria física que
esté disponible, aunque esté dividida. Una forma
de implementar esta solución es a través del uso
de un esquema de paginación. La paginación evita
el considerable problema de ajustar los pedazos de memoria de
tamaños variables
que han sufrido los esquemas de manejo de memoria anteriores.
Dado a sus ventajas sobre los métodos previos, la
paginación, en sus diversas formas, es usada en muchos
sistemas operativos.

Al utilizar la memoria
virtual, las direcciones no pasan en forma directa al
bus de memoria,
sino que van a una unidad administradora de la memoria (MMU
–Memory Management Unit). Estas direcciones generadas por
los programas se llaman direcciones virtuales y conforman el
hueco de direcciones virtuales. Este hueco se divide en
unidades llamadas páginas. Las unidades correspondientes
en la memoria física se llaman
marcos para página o frames. Las páginas y
los frames tienen siempre el mismo tamaño.

Tablas de páginas

Cada página tiene un número que se
utiliza como índice en la tabla de páginas, lo
que da por resultado el número del marco correspondiente
a esa página virtual. Si el bit presente / ausente es 0,
se provoca un señalamiento (trap) hacia el
sistema operativo. Si el bit es 1, el número de marco
que aparece en la tabla de páginas se copia en los bits
de mayor orden del registro de salida, junto con el ajuste
(offset) de 12 bits, el cual se copia sin modificaciones
de la dirección virtual de entrada. Juntos forman una
dirección física de 15 bits. El registro de
salida se coloca entonces en el bus de la memoria como la
dirección en la memoria física.

En teoría, la asociación de las
direcciones virtuales con las físicas se efectúa
según lo descrito. El número de página
virtual se divide en un número de página virtual
(los bits superiores)y un ajuste (los bits inferiores). El
número de página virtual se utiliza como un
índice en la tabla de páginas para encontrar la
entrada de esa página virtual. El número de marco
(si existe) se determina a partir de la tabla de
páginas. El número de marco se asocia al extremo
superior del ajuste y reemplaza al número de
página virtual para formar una dirección
física que se puede enviar a la memoria.

La finalidad de la tabla de páginas es asociar
las páginas virtuales con los marcos. En términos
matemáticos, la tabla de páginas es una
función, cuyo argumento es el número de
página virtual y como resultado el número del
marco físico. Mediante el resultado de esta
función, se puede reemplazar el campo de la
página virtual de una dirección virtual por un
campo de marco, lo que produce una dirección en la
memoria física. Sin embargo hay que enfrentar dos
aspectos fundamentales:

1. La tabla de páginas puede ser demasiado
   grande.
2. La asociación debe ser
   rápida.

El primer punto proviene del hecho de que las
computadoras modernas utilizan direcciones virtuales de al
menos 32 bits. Por ejemplo, si el tamaño de
página es de 4K, un hueco de direcciones de 32 bits
tiene un millón de páginas; en el caso de un
hueco de direcciones de 64 bits, se tendría más
información de la que uno quisiera
contemplar.

El segundo punto es consecuencia del hecho de que la
asociación virtual – física debe hacerse en
cada referencia a la memoria. Una instrucción
común tiene una palabra de instrucción y
también un operando de memoria. Entonces es necesario
hacer una, dos o más referencias a la tabla de
páginas por cada instrucción.

Algoritmos de reemplazo de
páginas

Con el uso del método de paginación se
puede llegar a saturar la memoria si se incrementa demasiado el
nivel de multiprogramación. Por ejemplo, si se corren
seis procesos, cada uno con un tamaño de diez
páginas de las cuales en realidad sólo utiliza
cinco, se tiene un mayor uso del CPU y con marcos de sobra.
Pero pudiera suceder que cada uno de esos procesos quiera usar
las diez páginas resultando en una necesidad de 60
marcos, cuando solo hay 40 disponibles.

Esto provoca sobre-asignación y mientras un
proceso de usuario se está ejecutando, ocurre un fallo
de página. El hardware se bloquea con el sistema
operativo, el cual checa en sus tablas internas y se da cuenta
que es un fallo de página y no un acceso ilegal de
memoria. El sistema operativo determina si la página
está residiendo en disco, pero también determina
que no hay marcos de memoria disponibles en la lista de marcos
libres.

Al ocurrir el fallo de página, el sistema
operativo debe elegir una página para retirarla de la
memoria y usar el espacio para la página que se necesita
para desbloquear el sistema y que el hardware pueda seguir
trabajando. Si la página por eliminar de la memoria fue
modificada, se debe volver a escribir al disco para mantener la
información actualizada; de lo contrario, si la
página no fue modificada no es necesario rescribir la
información a disco y la página que se carga
simplemente se escribe sobre la página a borrar en
memoria. La figura 8 muestra gráficamente un intercambio
de páginas entre la memoria principal y el disco
(memoria secundaria).

  Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

Fig. 8. Se elimina de la memoria principal una
página que no esté en uso y se reemplaza por una
página de la cual el sistema operativo tiene necesidad
de uso.

Algoritmo aleatorio

Este algoritmo consiste simplemente en reemplazar
aleatoriamente cualquier página de la memoria principal,
sin hacer ningún esfuerzo de
predicción.

Es el algoritmo más sencillo dado que no
requiere tener ninguna información, sin embargo, por no
hacer uso de dicha información sobre el comportamiento del proceso, no puede lograr un
buen desempeño.

Algoritmo de reemplazo de páginas
óptimo

Este algoritmo debe de tener el menor índice de
fallos de página de todos los algoritmos. En teoría, este algoritmo debe de reemplazar
la página que no va a ser usada por el periodo
más largo de tiempo.

Desafortunadamente, el algoritmo de reemplazo
óptimo es fácil en teoría, pero
prácticamente imposible de implementar, dado que
requiere conocer a futuro las necesidades del
sistema.

Tal algoritmo existe y ha sido llamado OPT o MIN, pero
se usa únicamente para estudios de comparaciones. Por
ejemplo, puede resultar muy útil saber que aunque
algún nuevo algoritmo no sea óptimo, está
entre el 12.3% del óptimo y entre el 4.7% en
promedio.

Algoritmo de reemplazo de páginas
según el uso no tan reciente

Este algoritmo hace uso de los dos bits de estado que
están asociados a cada página. Estos bits son: R,
el cual se activa cuando se hace referencia (lectura /
escritura) a la página asociada; y M, que se activa
cuando la página asociada es modificada (escritura).
Estos bits deben de ser actualizado cada vez que se haga
referencia a la memoria, por esto es de suma importancia que
sean activados por el hardware. Una vez activado el bit,
permanece en ese estado hasta que el sistema operativo,
mediante software, modifica su estado.

Estos bits pueden ser utilizados para desarrollar un
algoritmo de reemplazo que cuando inicie el proceso, el sistema
operativo asigne un valor de 0 a ambos bits en todas las
páginas. En cada interrupción de reloj, limpie el
bit R para distinguir cuáles páginas tuvieron
referencia y cuáles no.

Cuando ocurre un fallo de página, el sistema
operativo revisa ambos bits en todas las páginas y las
clasifica de la siguiente manera:

Clase 0: La página no ha sido referenciada, ni
modificada.

Clase 1: La página no ha sido referenciada,
pero ha sido modificada.

Clase 2: La página ha sido referenciada, pero
no ha sido modificada.

Clase 3: La página ha sido referenciada y
también modificada.

Una vez obtenida la clasificación, elimina una
página de manera aleatoria de la primera clase no
vacía con el número más pequeño.
Esto porque para el algoritmo es mejor eliminar una
página modificada sin referencias en al menos un
intervalo de reloj, que una página en blanco de uso
frecuente.

A pesar de que este algoritmo no es el óptimo,
es fácil de implementar y de comprender y con mucha
frecuencia es el más adecuado.

Algoritmo de reemplazo "Primero en entrar, primero
en salir" (FIFO)

El algoritmo más sencillo para remplazo de
páginas es el FIFO (First In – First Out). Este
algoritmo asocia a cada página el momento en que
ésta fue traída a memoria. Cuando una
página debe ser reemplazada se selecciona a la
más antigua.

No es estrictamente necesario registrar el momento de
entrada de la página a memoria, sino que se puede crear
una cola en la que se van agregando las páginas conforme
van llegando a la memoria. Cuando se debe eliminar una
página, se selecciona la que está al frente de la
lista (o sea, la más antigua de la lista). Cuando llega
una página nueva, se inserta en la parte trasera de la
cola. En la figura 9 se representa el funcionamiento de
éste algoritmo.

 Para ver el gráfico
seleccione la opción "Descargar" del menú
superior

Fig. 9. Reemplazo de páginas mediante el
algoritmo FIFO.

Al igual que el algoritmo aleatorio, este algoritmo es
fácil de comprender y de programar. Sin embargo, su
desempeño no siempre es del todo bueno.
La página reemplazada puede ser un módulo de
inicialización que fue usado hace mucho tiempo y ya no
se tiene necesidad de él. Por otro lado, puede contener
una variable de uso muy frecuente que fue inicializada de
manera temprana y está en uso constante.

Algoritmo de reemplazo de páginas de la
segunda oportunidad

Este algoritmo es una modificación del FIFO. El
algoritmo hace uso del bit de referencia de la página.
Cuando una página ha sido seleccionada para reemplazo,
se revisa el bit de referencia. Si tiene valor de 0, se procede
a reemplazar la página. Si por el contrario, el bit de
referencia es 1 se le da a la página una segunda
oportunidad.

  Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

Fig. 10. Algoritmo de la segunda
oportunidad.

Cuando esto sucede, se le cambia el bit de referencia
a 0 y se actualiza su tiempo de llegada al tiempo actual para
que la página se colocada al final de la cola. De esta
manera, la página espera todo un ciclo completo de
páginas para ser entonces reemplazada.

Si la página tiene un uso muy frecuente, el bit
de referencia se mantendría constantemente en 1 y la
página no sería reemplazada. En la figura 10 se
puede apreciar el funcionamiento del algoritmo.

Algoritmo de reemplazo de páginas del
reloj

Modificando el algoritmo de la segunda oportunidad
(que a su vez es una modificación de FIFO) obtenemos el
algoritmo aumentado de la segunda oportunidad o algoritmo del
reloj. Usamos la misma clasificación vista en el
algoritmo de uso no tan reciente (sección
2.1.2.3.).

Este algoritmo organiza las páginas en una
lista circular como se muestra en la figura 11 y se usa un
apuntador (o manecilla) que señala a la página
más antigua.

  Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

Fig. 11. Algoritmo de reloj.

Cuando se presenta un fallo de página, el
algoritmo revisa la página a la que está
apuntando la manecilla. Si el bit de referencia es 0, la
página es reemplazada con la nueva y la manecilla avanza
una posición. Si el bit es 1, entonces se limpia (cambia
a 0) y la manecilla avanza a la siguiente página y
así sucesivamente hasta encontrar una con bit
0.

Algoritmo de reemplazo de páginas "la de
menor uso reciente" (LRU)

Este algoritmo es una buena aproximación al
óptimo y se basa en al observación de que las páginas de
uso frecuente en las últimas instrucciones se utilizan
con cierta probabilidad en
las siguientes. De la misma manera, es probable que las
páginas que no hayan sido utilizadas durante mucho
tiempo permanezcan sin uso por bastante tiempo. Implementando
el algoritmo con esta base, al ocurrir un fallo de
página, se elimina la página que no haya sido
utilizada durante el tiempo más grande. De ahí su
denominación: menor uso reciente (LRU – Least Recent
Use).

A diferencia de los algoritmos anteriores, el LRU
tiene un mejor rendimiento en cuanto al tiempo de
aprovechamiento del CPU y del uso de la memoria. Sin embargo,
el problema con este algoritmo es que su implementación
es muy cara, ya que requiere de una asistencia considerable de
hardware. Otro problema es el de determinar un orden para los
marcos definido por el tiempo de menor uso. Para éste
último hay dos posibles implementaciones:

• Contadores: En el caso más sencillo, se asocia
  cada entrada tabla-página un campo de tiempo-de-uso y se
  le agrega al CPU un reloj lógico o contador. Este reloj
  es incrementado en cada referencia de memoria. Siempre que se
  hace referencia a una página, el contenido del registro
  del reloj es copiado al campo de tiempo-de-uso en la tabla de
  páginas para esa página. De esta forma, siempre
  se dispone del "tiempo" de la última referencia a cada
  página. La página que se reemplaza es la del
  menor valor de tiempo. Este esquema requiere de una
  búsqueda en toda la tabla de páginas para
  encontrar la página LRU, y una escritura en memoria al
  campo de tiempo-de-uso en la tabla de páginas por cada
  acceso a memoria. Los tiempos también se deben de
  mantener cuando las tablas de páginas son alteradas
  (debido a organización del CPU). Se debe considerar la
  posibilidad de sobrecarga en el reloj.
• Pilas: Otra aproximación para implementar el
  reemplazo LRU es la de tener una pila con los números de
  páginas. Siempre que se hace referencia a una
  página, se quita de la pila y se pone en la parte
  superior. De esta manera, la parte superior de la pila es la
  página de uso más reciente y la de abajo es la
  LRU, tal como se muestra en la figura 12.

  Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

Fig. 12. Uso de pilas en el
algoritmo LRU