Administracion de memoria 

La parte del sistema operativo que administra (parte de) la jerarquía de memoria se conoce como

administrador de memoria. Su trabajo es administrar la memoria con eficiencia: llevar el registro

de cuáles partes de la memoria están en uso, asignar memoria a los procesos cuando la

necesiten y desasignarla cuando terminen.

SIN ABSTRACCIÓN DE MEMORIA
La abstracción más simple de memoria es ninguna abstracción. Las primeras computadoras mainframe

(antes de 1960), las primeras minicomputadoras (antes de 1970) y las primeras computadoras

personales (antes de 1980) no tenían abstracción de memoria. Cada programa veía simplemente

la memoria física. Cuando un programa ejecutaba una instrucción como

MOV REGISTRO1, 1000

la computadora sólo movía el contenido de la ubicación de memoria física 1000 a REGISTRO1. Así,

el modelo de programación que se presentaba al programador era simplemente la memoria física,

un conjunto de direcciones desde 0 hasta cierto valor máximo, en donde cada dirección correspondía

a una celda que contenía cierto número de bits, comúnmente ocho.

Bajo estas condiciones, no era posible tener dos programas ejecutándose en memoria al mismo

tiempo. Si el primer programa escribía un nuevo valor en, por ejemplo, la ubicación 2000, esto borraría

cualquier valor que el segundo programa estuviera almacenando ahí. Ambos programas fallarían

de inmediato.

Incluso cuando el modelo de memoria consiste en sólo la memoria física hay varias opciones

posibles. En la figura 3-1 se muestran tres variaciones. El sistema operativo puede estar en la parte

inferior de la memoria en la RAM (Random Access Memory, Memoria de acceso aleatorio), como

se muestra en la figura 3-1(a), puede estar en la ROM (Read Only Memory, Memoria de sólo lectura)

en la parte superior de la memoria, como se muestra en la figura 3-1(b), o los controladores

de dispositivos pueden estar en la parte superior de la memoria en una ROM y el resto del sistema

en RAM más abajo, como se muestra en la figura 3-1(c). El primer modelo se utilizó antes en las

mainframes y minicomputadoras, pero actualmente casi no se emplea. El segundo modelo se utiliza

en algunas computadoras de bolsillo y sistemas integrados. El tercer modelo fue utilizado por las

primeras computadoras personales (por ejemplo, las que ejecutaban MS-DOS), donde la porción

del sistema en la ROM se conoce como BIOS (Basic Input Output System, Sistema básico de entrada

y salida). Los modelos (a) y (c) tienen la desventaja de que un error en el programa de usuario

puede borrar el sistema operativo, posiblemente con resultados desastrosos (la información del

disco podría quedar ininteligible).

UNA ABSTRACCIÓN DE MEMORIA:
ESPACIOS DE DIRECCIONES
Con todo, exponer la memoria física a los procesos tiene varias desventajas. En primer lugar, si los
programas de usuario pueden direccionar cada byte de memoria, pueden estropear el sistema operativo
con facilidad, ya sea intencional o accidentalmente, con lo cual el sistema se detendría en forma
súbita (a menos que haya hardware especial como el esquema de bloqueo y llaves de la IBM 360).

La noción de un espacio de direcciones
Una mejor solución es inventar una nueva abstracción para la memoria: el espacio de direcciones.
Así como el concepto del proceso crea un tipo de CPU abstracta para ejecutar programas, el
espacio de direcciones crea un tipo de memoria abstracta para que los programas vivan ahí. Un espacio
de direcciones (address space) es el conjunto de direcciones que puede utilizar un proceso
para direccionar la memoria. Cada proceso tiene su propio espacio de direcciones, independiente de
los que pertenecen a otros procesos (excepto en ciertas circunstancias especiales en donde los procesos
desean compartir sus espacios de direcciones).
El concepto de un espacio de direcciones es muy general y ocurre en muchos contextos. Considere
los números telefónicos. En los Estados Unidos y en muchos otros países, un número de teléfono
local es comúnmente un número de 7 dígitos. En consecuencia, el espacio de direcciones
para los números telefónicos varía desde 0,000,000 hasta 9,999,999, aunque algunos números, como
los que empiezan con 000, no se utilizan. Con el crecimiento de los teléfonos celulares, módems
y máquinas de fax, este espacio se está volviendo demasiado pequeño, en cuyo caso habrá qué utilizar
más dígitos. El espacio de direcciones para los puertos de E/S en el Pentium varía desde 0 hasta
16383. Las direcciones IPv4 son números de 32 bits, por lo que su espacio de direcciones varía
desde 0 hasta 232 – 1 (de nuevo, con ciertos números reservados).

MEMORIA VIRTUAL
Como consecuencia de estos desarrollos, existe la necesidad de ejecutar programas que son demasiado
grandes como para caber en la memoria y sin duda existe también la necesidad de tener
sistemas que puedan soportar varios programas ejecutándose al mismo tiempo, cada uno de los cuales
cabe en memoria, pero que en forma colectiva exceden el tamaño de la misma. El intercambio
no es una opción atractiva, ya que un disco SATA ordinario tiene una velocidad de transferencia pico
de 100 MB/segundo a lo más, lo cual significa que requiere por lo menos 10 segundos para intercambiar
un programa de 1 GB de memoria a disco y otros 10 segundos para intercambiar un
programa de 1 GB del disco a memoria.

ALGORITMOS DE REEMPLAZO DE PÁGINAS
Cuando ocurre un fallo de página, el sistema operativo tiene que elegir una página para desalojarla
(eliminarla de memoria) y hacer espacio para la página entrante. Si la página a eliminar se modificó
mientras estaba en memoria, debe volver a escribirse en el disco para actualizar la copia del mismo.
No obstante, si la página no se ha modificado (por ejemplo, si contiene el texto del programa), la
copia ya está actualizada y no se necesita rescribir. La página que se va a leer sólo sobrescribe en
la página que se va a desalojar.
Aunque sería posible elegir una página al azar para desalojarla en cada fallo de página, el rendimiento
del sistema es mucho mayor si se selecciona una página que no sea de uso frecuente. Si
se elimina una página de uso frecuente, tal vez tenga que traerse de vuelta rápidamente, lo cual produce
una sobrecarga adicional. Se ha realizado mucho trabajo, tanto teórico como experimental en
el tema de los algoritmos de reemplazo de páginas.

CUESTIONES DE IMPLEMENTACIÓN
Los implementadores de los sistemas de memoria virtual tienen que elegir entre los principales algoritmos
teóricos: entre el algoritmo de segunda oportunidad y el de envejecimiento, entre la asignación
de páginas local o global, y entre la paginación bajo demanda o la prepaginación. Pero
también tienen que estar al tanto de varias cuestiones prácticas de implementación. En esta sección
daremos un vistazo a unos cuantos de los problemas comunes y ciertas soluciones.

SEGMENTACIÓN
La memoria virtual que hemos analizado hasta ahora es unidimensional, debido a que las direcciones
virtuales van desde 0 hasta cierta dirección máxima, una dirección después de la otra. Para muchos
problemas, tener dos o más espacios de direcciones virtuales separados puede ser mucho mejor
que tener sólo uno. Por ejemplo, un compilador tiene muchas tablas que se generan a medida que
procede la compilación, las cuales posiblemente incluyen:
1. El texto del código fuente que se guarda para el listado impreso (en sistemas de procesamiento
por lotes).
2. La tabla de símbolos, que contiene los nombres y atributos de las variables.
3. La tabla que contiene todas las constantes enteras y de punto flotante utilizadas.
4. El árbol de análisis sintáctico, que contiene el análisis sintáctico del programa.
5. La pila utilizada para las llamadas a procedimientos dentro del compilador.

INVESTIGACIÓN ACERCA DE LA ADMINISTRACIÓN
DE MEMORIA
La administración de memoria, en especial los algoritmos de paginación, fue alguna vez un área
fructífera para la investigación, pero la mayor parte de eso parece haber desaparecido desde hace
mucho tiempo, por lo menos para los sistemas de propósito general. La mayoría de los sistemas reales
tienden a utilizar cierta variación sobre el reloj, debido a que es fácil de implementar y relativamente
efectivo. Sin embargo, una excepción reciente es un rediseño del sistema de memoria virtual
de BSD 4.4 (Cranor y Prulkar, 1999).
Sin embargo, aún se están realizando investigaciones sobre la paginación en los tipos más recientes
de sistemas. Por ejemplo, los teléfonos celulares y los PDAs se han convertido en pequeñas
PCs y muchps de ellas paginan la RAM al “disco”, sólo que el disco en un teléfono celular es la
memoria flash, que tiene propiedades distintas a las de un disco magnético giratorio. Cierto trabajo
reciente se reporta (In y colaboradores, 2007; Joo y colaboradores, 2006; y Park y colaboradores,
2004a). Park y colaboradores (2004b) también han analizado la paginación por demanda
consciente de la energía en los dispositivos móviles.

PROBLEMAS CLÁSICOS DE LA COMUNICACIÓN ENTRE PROCESOS

La literatura de sistemas operativos está repleta de interesantes problemas que se han descrito y analizado ampliamente, mediante el uso de una variedad de métodos de sincronización. En las siguientes secciones examinaremos dos de los problemas más conocidos.

     El problema de los filósofos comelones.

 En 1965, Dijkstra propuso y resolvió un problema de sincronización al que llamó el problema de los filósofos comelones. Desde ese momento, todos los que inventaban otra primitiva de sincronización se sentían obligados a demostrar qué tan maravillosa era esa nueva primitiva, al mostrar con qué elegancia resolvía el problema de los filósofos comelones. Este problema se puede enunciar simplemente de la siguiente manera. Cinco filósofos están sentados alrededor de una mesa circular. Cada filósofo tiene un plato de espagueti. El espagueti es tan resbaloso, que un filósofo necesita dos tenedores para comerlo. Entre cada par de platos hay un tenedor.
La distribución de la mesa se ilustra en la figura
                                   

La vida de un filósofo consiste en periodos alternos de comer y pensar (esto es algo así como una abstracción, incluso para los filósofos, pero las otras actividades son irrelevantes aquí). Cuando un filósofo tiene hambre, trata de adquirir sus tenedores izquierdo y derecho, uno a la vez, en cualquier orden. Si tiene éxito al adquirir dos tenedores, come por un momento, después deja los tenedores y continúa pensando. La pregunta clave es: ¿puede usted escribir un programa para cada filósofo, que haga lo que se supone debe hacer y nunca se trabe? (Hemos recalcado que el requerimiento de los dos tenedores es algo artificial; tal vez deberíamos cambiar de comida italiana a comida china y sustituir el espagueti por arroz y los tenedores por palillos chinos).

La solución que se presenta en la figura está libre de interbloqueos y permite el máximo paralelismo para un número arbitrario de filósofos. Utiliza un arreglo llamado estado para llevar el

registro de si un filósofo está comiendo, pensando o hambriento (tratando de adquirir tenedores). Un filósofo sólo se puede mover al estado de comer si ningún vecino está comiendo. Los i vecinos del filósofo se definen mediante las macros IZQUIERDO y DERECHO. En otras palabras, si i es 2, IZQUIERDO es 1 y DERECHO es 3. El programa utiliza un arreglo de semáforos, uno por cada filósofo, de manera que los filó- sofos hambrientos puedan bloquearse si los tenedores que necesitan están ocupados. Observe que cada proceso ejecuta el procedimiento filosofo como su código principal, pero los demás procedimientos (tomar_tenedores, poner_tenedores y probar) son ordinarios y no procesos separados.

 Una solución al problema de los filósofos comelones.

 El problema de los lectores y escritores

El problema de los filósofos comelones es útil para modelar procesos que compiten por el acceso exclusivo a un número limitado de recursos, como los dispositivos de E/S. Otro problema famoso es el de los lectores y escritores (Courtois y colaboradores, 1971), que modela el acceso a una base de datos. Por ejemplo, imagine un sistema de reservación de aerolíneas, con muchos procesos en competencia que desean leer y escribir en él. Es aceptable tener varios procesos que lean la base de datos al mismo tiempo, pero si un proceso está actualizando (escribiendo) la base de datos, ningún otro proceso puede tener acceso a la base de datos, ni siquiera los lectores. La pregunta es, ¿cómo se programan los lectores y escritores? 

Una solución se muestra en la figura. En esta solución, el primer lector en obtener acceso a la base de datos realiza una operación down en el semáforo bd. Los siguientes lectores simplemente incrementan un contador llamado cl. A medida que los lectores van saliendo, decrementan el contador y el último realiza una operación up en el semáforo, para permitir que un escritor bloqueado (si lo hay) entre. La solución que se presenta aquí contiene en forma implícita una decisión sutil que vale la pena observar. Suponga que mientras un lector utiliza la base de datos, llega otro lector. Como no es un problema tener dos lectores al mismo tiempo, el segundo lector es admitido. También se pueden admitir más lectores, si es que llegan. Ahora suponga que aparece un escritor. Tal vez éste no sea admitido a la base de datos, ya que los escritores deben tener acceso exclusivo y por ende, el escritor se suspende. Más adelante aparecen lectores adicionales.

 Mientras que haya un lector activo, se admitirán los siguientes lectores. Como consecuencia de esta estrategia, mientras que haya un suministro continuo de lectores, todos entrarán tan pronto lleguen. El escritor estará suspendido hasta que no haya un lector presente. Si llega un nuevo lector, por decir cada 2 segundos y cada lector requiere 5 segundos para hacer su trabajo, el escritor nunca entrará. Para evitar esta situación, el programa se podría escribir de una manera ligeramente distinta: cuando llega un lector y hay un escritor en espera, el lector se suspende detrás del escritor, en vez de ser admitido de inmediato. De esta forma, un escritor tiene que esperar a que terminen los lectores que estaban activos cuando llegó, pero no tiene que esperar a los lectores que llegaron después de él. La desventaja de esta solución es que logra una menor concurrencia y por ende, un menor rendimiento. Courtois y sus colaboradores presentan una solución que da prioridad a los escritores

. Una solución al problema de los lectores y escritores.

PROCESOS

PROCESOS

Todas las computadoras modernas ofrecen varias cosas al mismo tiempo; quienes están acostumbrados a trabajar con ellas tal vez no estén completamente conscientes de este hecho, por lo que utilizaremos algunos ejemplos para aclarar este punto. Consideremos primero un servidor Web, a donde convergen las peticiones de páginas Web provenientes de todos lados. Cuando llega una petición, el servidor verifica si la página que se necesita está en la caché. De ser así, devuelve la pá- gina; en caso contrario, inicia una petición al disco para obtenerla y, desde la perspectiva de la CPU, estas peticiones tardan eternidades. Mientras se espera el cumplimiento de una petición, muchas más pueden llegar. Si hay varios discos presentes, algunas o todas las demás peticiones podrían dirigirse a otros discos mucho antes de que se cumpla la primera petición. Es evidente que se necesita cierta forma de modelar y controlar esta concurrencia. Los procesos (y en especial los hilos) pueden ayudar en este caso

El modelo del proceso

En este modelo, todo el software ejecutable en la computadora, que algunas veces incluye al sistema

operativo, se organiza en varios procesos secuenciales (procesos, para abreviar). Un proceso

no es más que una instancia de un programa en ejecución, incluyendo los valores actuales del

contador de programa, los registros y las variables. En concepto, cada proceso tiene su propia

CPU virtual; en la realidad, la CPU real conmuta de un proceso a otro, pero para entender el sistema

es mucho más fácil pensar en una colección de procesos que se ejecutan en (pseudo) paralelo,

en vez de tratar de llevar la cuenta de cómo la CPU conmuta de programa en programa. Esta

conmutación rápida de un proceso a otro se conoce como multiprogramación, como vimos en el

capítulo 1.

Creación de un proceso

Los sistemas operativos necesitan cierta manera de crear procesos. En sistemas muy simples o sistemas

diseñados para ejecutar sólo una aplicación (por ejemplo, el controlador en un horno de microondas),

es posible tener presentes todos los procesos que se vayan a requerir cuando el sistema

inicie. No obstante, en los sistemas de propósito general se necesita cierta forma de crear y terminar

procesos según sea necesario durante la operación. Ahora analizaremos varias de estas cuestiones.

Hay cuatro eventos principales que provocan la creación de procesos:

1. El arranque del sistema.

2. La ejecución, desde un proceso, de una llamada al sistema para creación de procesos.

3. Una petición de usuario para crear un proceso.

4. El inicio de un trabajo por lotes.

Terminación de procesos

Una vez que se crea un proceso, empieza a ejecutarse y realiza el trabajo al que está destinado. Sin

embargo, nada dura para siempre, ni siquiera los procesos. Tarde o temprano el nuevo proceso terminará,

por lo general debido a una de las siguientes condiciones:

1. Salida normal (voluntaria).

2. Salida por error (voluntaria).

3. Error fatal (involuntaria).

4. Eliminado por otro proceso (involuntaria).

Jerarquías de procesos

En algunos sistemas, cuando un proceso crea otro, el proceso padre y el proceso hijo continúan asociados

en ciertas formas. El proceso hijo puede crear por sí mismo más procesos, formando una jerarquía

de procesos. Observe que, a diferencia de las plantas y los animales que utilizan la

reproducción sexual, un proceso sólo tiene un padre (pero cero, uno, dos o más hijos).

En UNIX, un proceso y todos sus hijos, junto con sus posteriores descendientes, forman un grupo

de procesos. Cuando un usuario envía una señal del teclado, ésta se envía a todos los miembros

del grupo de procesos actualmente asociado con el teclado (por lo general, todos los procesos activos

que se crearon en la ventana actual). De manera individual, cada proceso puede atrapar la señal,

ignorarla o tomar la acción predeterminada que es ser eliminado por la señal.

Estados de un proceso

Aunque cada proceso es una entidad independiente, con su propio contador de programa y estado

interno, a menudo los procesos necesitan interactuar con otros. Un proceso puede generar cierta salida

que otro proceso utiliza como entrada. En el comando de shell

cat capitulo1 capitulo2 capitulo3 | grep arbol

En la figura 2-2 podemos ver un diagrama de estados que

muestra los tres estados en los que se puede encontrar un proceso:

1. En ejecución (en realidad está usando la CPU en ese instante).

2. Listo (ejecutable; se detuvo temporalmente para dejar que se ejecute otro proceso).

3. Bloqueado (no puede ejecutarse sino hasta que ocurra cierto evento externo).

Implementación de los procesos

Para implementar el modelo de procesos, el sistema operativo mantiene una tabla (un arreglo de estructuras)

llamada tabla de procesos, con sólo una entrada por cada proceso (algunos autores llaman

a estas entradas bloques de control de procesos). Esta entrada contiene información importante

acerca del estado del proceso, incluyendo su contador de programa, apuntador de pila, asignación de

memoria, estado de sus archivos abiertos, información de contabilidad y planificación, y todo lo demás

que debe guardarse acerca del proceso cuando éste cambia del estado en ejecución a listo o bloqueado,

de manera que se pueda reiniciar posteriormente como si nunca se hubiera detenido.

La figura 2-4 muestra algunos de los campos clave en un sistema típico. Los campos en la primera

columna se relacionan con la administración de procesos; los otros dos se relacionan con la

administración de memoria y archivos, respectivamente. Hay que recalcar que los campos contenidos

en la tabla de procesos varían de un sistema a otro, pero esta figura nos da una idea general de

los tipos de información necesaria.

Modelación de la multiprogramación

Cuando se utiliza la multiprogramación, el uso de la CPU se puede mejorar. Dicho en forma cruda:

si el proceso promedio realiza cálculos sólo 20 por ciento del tiempo que está en la memoria, con

cinco procesos en memoria a la vez la CPU deberá estar ocupada todo el tiempo. Sin embargo, este

modelo es demasiado optimista, ya que supone que los cinco procesos nunca estarán esperando

la E/S al mismo tiempo.

La figura muestra el uso de la CPU como una función de n, a lo cual se le conoce como el grado

de multiprogramación.