path: root/iso/n5.lyx

#LyX 2.3 created this file. For more info see http://www.lyx.org/
\lyxformat 544
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass book
\use_default_options true
\maintain_unincluded_children false
\language spanish
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style french
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Standard
El 
\series bold
administrador de memoria
\series default
 del sistema operativo se encarga de abstraer y administrar la jerarquía
 de memoria.
\end_layout

\begin_layout Section
Sin memoria virtual
\end_layout

\begin_layout Standard
En la 
\series bold
multiprogramación con particiones fijas
\series default
, se asigna una zona de tamaño fijo al sistema operativo y el resto se dividen
 en 
\series bold
particiones
\series default
 de igual o distinto tamaño.
 Podemos tener una cola por partición y colocar cada trabajo en la cola
 de la partición más pequeña en que quepa, pero si hay pocas particiones
 pequeñas sus colas serán largas porque la mayoría de procesos son pequeños
 y si hay muchas puede no quedar espacio para trabajos grandes.
 También se puede tener una cola para todas las particiones y, cuando queda
 una partición libre, darla a la primera tarea de la cola que quepa, lo
 que hace que las tareas pequeñas desperdicien espacio, o darla a la tarea
 más grande que quepa, lo que discrimina a las tareas pequeñas.
 Soluciones a este último problema son tener una partición pequeña o establecer
 un máximo de veces que se puede excluir una tarea.
\end_layout

\begin_layout Standard
Esto limita el 
\series bold
grado de multiprogramación
\series default
, el total de procesos que puede haber a la vez en memoria compartiendo
 CPU, además de producir fragmentación interna sobre todo en procesos pequeños
 y fragmentación externa si hay particiones libres con tamaño total suficiente
 para un proceso pero ninguna es lo bastante grande.
\end_layout

\begin_layout Standard
La 
\series bold
multiprogramación con particiones variables
\series default
 soluciona el problema asignando a cada proceso una partición del tamaño
 exacto que necesita, con lo que las particiones se crean, desaparecen o
 intercambian según se necesita.
 
\series bold
Políticas de asignación de huecos
\series default
:
\end_layout

\begin_layout Itemize

\series bold
Primero en ajustarse
\series default
: Se busca el primer hueco lo suficientemente grande desde el principio
 de la memoria, dividiendo el hueco en una parte para el proceso y un hueco
 libre (salvo si hay ajuste perfecto), y es rápido.
\end_layout

\begin_layout Itemize

\series bold
Siguiente en ajustarse
\series default
: Igual pero se empieza a buscar por donde se quedó la anterior búsqueda.
\end_layout

\begin_layout Itemize

\series bold
Mejor en ajustarse
\series default
: Busca el hueco más pequeño en el que quepa el proceso, es lenta y desperdicia
 más memoria por fragmentación externa.
\end_layout

\begin_layout Itemize

\series bold
Peor en ajustarse
\series default
: Toma el hueco libre más grande, y es lenta pero aprovecha bien la memoria.
\end_layout

\begin_layout Standard
La 
\series bold
compactación
\series default
 consiste en mover procesos en memoria para juntar los huecos y reducir
 la fragmentación externa.
 No se suele usar porque consume mucho tiempo, proporcional a la cantidad
 de información a mover, si bien ordenadores como el CDC CYBERS tenían hardware
 especial para esto.
 Para la 
\series bold
administración de memoria libre
\series default
:
\end_layout

\begin_layout Itemize

\series bold
Mapas de bits
\series default
: Se divide la memoria en unidades de asignación del mismo tamaño, y a cada
 una le corresponde un bit que indica si está libre o no.
 Si la unidad de asignación es pequeña, el mapa de bits será grande y las
 búsquedas lentas, pero si es grande habrá fragmentación interna.
\end_layout

\begin_layout Itemize

\series bold
Listas ligadas
\series default
: Lista de segmentos de memoria, que pueden ser procesos o huecos.
 Cuando un proceso termina, debe fusionar el hueco con los adyacentes, lo
 que es sencillo si la lista está ordenada por direcciones.
 Si hay una lista para procesos y otra para huecos, las operaciones serán
 más rápidas por no tener que ordenar la lista de procesos.
 Si la de huecos se ordena por tamaño decreciente, la política de peor ajuste
 es 
\begin_inset Formula $O(1)$
\end_inset

, pero la fusión de huecos es cara.
 En general se accede a la información de memoria asignada a un proceso
 desde su bloque de control.
\end_layout

\begin_layout Standard
La asignación de hueco en la zona de intercambio del disco puede hacerse
 cuando el proceso deba intercambiarse o cuando se cree.
 Los algoritmos de asignación y registro de estos huecos son los mismos
 que en memoria principal, salvo que el tamaño de un hueco en disco es múltiplo
 del tamaño de bloque.
\end_layout

\begin_layout Standard
La 
\series bold
reubicación
\series default
 o 
\series bold
relocalización
\series default
 consiste en que, cuando un programa se ejecuta, puede ir a cualquier partición,
 por lo que el programa debe usar 
\series bold
código relocalizable
\series default
, que pueda ejecutarse correctamente independientemente de dónde se sitúe.
\end_layout

\begin_layout Standard
Para la protección de memoria puede haber un 
\series bold
registro base
\series default
 con la dirección de memoria donde comienza la partición de un proceso y
 un 
\series bold
registro límite
\series default
 con su tamaño, de modo que el proceso puede generar cualquier 
\series bold
dirección lógica
\series default
 en un 
\series bold
espacio de direcciones lógicas
\series default
 de 0 a su tamaño menos 1 que se traducen a 
\series bold
direcciones físicas
\series default
, y si genera una dirección mayor se produce una excepción.
\end_layout

\begin_layout Section
Paginación
\end_layout

\begin_layout Standard
El esquema de 
\series bold
memoria virtual
\series default
 permite ejecutar procesos con tamaño total mayor al de la memoria física,
 para lo que guarda en esta sólo las partes del proceso que se están usando
 y el resto lo guarda en disco.
 Cada proceso posee un espacio de direcciones virtuales, de tamaño normalmente
 limitado por CPU, que van a la 
\series bold
unidad de administración de memoria
\series default
 (
\series bold
MMU
\series default
) normalmente integrada en el chip de la CPU para que las traduzca a direcciones
 físicas.
\end_layout

\begin_layout Standard
El espacio de direcciones virtuales se divide en 
\series bold
páginas
\series default
 y el de memoria física en 
\series bold
marcos de página
\series default
, del mismo tamaño, normalmente potencias de 2 entre 
\begin_inset Formula $\unit[512]{B}$
\end_inset

 y 
\begin_inset Formula $\unit[8]{KiB}$
\end_inset

, aunque pueden ser bastante más grandes, y las transferencias entre memoria
 y disco son siempre en unidades de página.
\end_layout

\begin_layout Standard
Una 
\series bold
tabla de páginas
\series default
 tiene tantas entradas como páginas y en cada una indica el marco en que
 se almacena junto a algunos bits:
\end_layout

\begin_layout Itemize

\series bold
Bit presente/ausente
\series default
: Indica si la página está asociada o no.
 Si se accede a una página no asociada, la MMU genera una excepción llamada
 
\series bold
fallo de página
\series default
 a tratar por el sistema operativo.
 Este selecciona un marco, escribe su contenido en disco (si estaba ocupado
 y se había escrito algo), lo marca como ausente en su tabla de páginas
 y asigna el marco a la página que provocó el fallo, que lee del disco si
 es necesario.
\end_layout

\begin_layout Itemize

\series bold
Bits de protección
\series default
: Tipo de acceso permitido (lectura, escritura, ejecución...).
 Las páginas con código suelen tener permisos de lectura y ejecución pero
 no de escritura, mientras que las de datos suelen tener de lectura y escritura.
\end_layout

\begin_layout Itemize

\series bold
Modificado
\series default
: Indica si se ha modificado o no el contenido del marco.
\end_layout

\begin_layout Itemize

\series bold
Referenciado
\series default
: Se establece al hacer referencia a una página, y se usa en algoritmos
 de reemplazo.
\end_layout

\begin_layout Itemize

\series bold
Caché
\series default
: En las máquinas con E/S mapeada a memoria, evita que el contenido de la
 página se almacene en caché.
\end_layout

\begin_layout Itemize

\series bold
Visible en modo núcleo
\series default
: Evita que se pueda acceder a la página en modo usuario.
\end_layout

\begin_layout Standard
Las direcciones virtuales se dividen en un 
\series bold
número de página
\series default
, usado como índice en la tabla de páginas, y un 
\series bold
ajuste
\series default
 o 
\series bold
desplazamiento
\series default
 dentro de ella.
\end_layout

\begin_layout Standard
La traducción de páginas debe ser rápida, por lo que se usa un 
\series bold
TLB
\series default
 (
\emph on
Translation Look-aside Buffer
\emph default
), una caché totalmente asociativa generalmente en la MMU que contiene entradas
 de la tabla de páginas.
 El hardware verifica si el número de página está en el TLB comparando todas
 las entradas en paralelo (por lo que número de entradas suele ser muy pequeño).
 Si coincide alguna, se toma la entrada del TLB (incluyendo bits de protección,
 etc.).
 Si no está, se lee la entrada de memoria principal y, bien se elimina una
 entrada del TLB escribiendo sus bits de modificado y uso en la principal
 y se reemplaza por la nueva, o se produce un fallo de página.
\end_layout

\begin_layout Standard
Al cambiar de proceso se puede invalidar el contenido del TLB, borrando
 todos los bits de validez mediante una instrucción especial, o añadir un
 nuevo campo a cada entrada del TLB con el identificador del proceso y un
 registro con el del proceso activo, requiriendo hardware adicional pero
 ahorrando tiempo en los cambios de proceso y dando lugar a encontrar entradas
 en el TLB del propio proceso tras volver a tomar la CPU.
\end_layout

\begin_layout Standard
Como una tabla de páginas global puede ser muy grande, en la práctica se
 divide el número de página en varias partes y se usan tablas de páginas
 de varios niveles, de modo que la de primer nivel se indexa según la primera
 parte del número de página e indica la dirección de las tablas de segundo
 nivel, etc., y las tablas que no son necesarias no se tienen.
 Los Intel Pentium Pro tienen 3 niveles, los procesadores de Intel y AMD
 de 64 bits tienen 4, y Linux soporta hasta 5 desde la versión 4.14, permitiendo
 gestionar hasta 
\begin_inset Formula $\unit[128]{PiB}$
\end_inset

 de memoria virtual y hasta 
\begin_inset Formula $\unit[4]{PiB}$
\end_inset

 de RAM.
\end_layout

\begin_layout Standard
Una 
\series bold
tabla de páginas invertida
\series default
 contiene una entrada por cada marco de página con el número de la página
 que almacena, el PID, una serie de bits como en una entrada de tabla de
 páginas normal y un puntero para encadenamiento en una tabla de dispersión
 abierta usada para acelerar las traducciones, que usa como clave el PID
 y el número de página y devuelve el número de una entrada de la tabla.
\end_layout

\begin_layout Standard
El 
\series bold
mapa de memoria
\series default
 de un proceso es la estructura de su espacio de direcciones lógicas, en
 zonas contiguas de memoria virtual llamadas 
\series bold
regiones
\series default
 como las de código, datos con valor inicial, datos sin valor inicial y
 pila de cada hilo, con características como:
\end_layout

\begin_layout Itemize

\series bold
Soporte
\series default
: De dónde se obtienen los datos que contiene la región; normalmente un
 fichero o parte de este, como un ejecutable en el caso del código.
 También hay regiones sin soporte como la pila, cuyas páginas, si se modifican
 y son expulsadas, se guardan en la zona de intercambio del disco.
\end_layout

\begin_layout Itemize

\series bold
Tipo de compartición
\series default
: Si las modificaciones que haga un proceso son visibles por otros o no.
\end_layout

\begin_layout Itemize

\series bold
Protección
\series default
: Permisos de lectura, escritura y ejecución.
\end_layout

\begin_layout Itemize

\series bold
Tamaño fijo
\series default
 o 
\series bold
variable
\series default
: Si es variable, se indica si crece hacia direcciones mayores, como la
 memoria montón o 
\emph on
heap
\emph default
 usada para la memoria dinámica, o menores, como la pila.
 En UNIX, la memoria montón no tiene soporte, está inicialmente a 0 y crece
 conforme el proceso necesita memoria mediante las llamadas 
\family typewriter
brk
\family default
 y 
\family typewriter
sbrk
\family default
.
\end_layout

\begin_layout Standard
El sistema operativo suele estar mapeado en todos los procesos, con el bit
 de visible en modo núcleo activado, por eficiencia en las transferencias
 de datos entre usuario y núcleo
\begin_inset Foot
status open

\begin_layout Plain Layout
En procesadores como Intel, esto ya no se hace debido a Meltdown.
\end_layout

\end_inset

.
\end_layout

\begin_layout Standard
En Linux, al hacer la llamada al sistema 
\family typewriter
fork
\family default
, se usa 
\series bold
copia en escritura
\series default
 (
\emph on
copy on write
\emph default
, COW), consistente en desactivar el permiso de escritura de las páginas
 y dar al proceso hijo una copia de la tabla de páginas del padre, de modo
 que si uno de los dos intenta escribir en una región en la que tendría
 permiso, el sistema operativo hace una copia de la página que provocó la
 violación, la asigna a la tabla de páginas del proceso que hace la escritura
 y activa el permiso de escritura en ambas páginas
\begin_inset Foot
status open

\begin_layout Plain Layout
Linux usa conteo de referencias para que, si hay varios 
\family typewriter
fork
\family default
, no se active la escritura en la página original hasta que el resto de
 procesos tenga una copia de la página.
 Ver 
\begin_inset Flex URL
status open

\begin_layout Plain Layout

https://stackoverflow.com/questions/13813636/how-does-copy-on-write-in-fork-handl
e-multiple-fork
\end_layout

\end_inset

 para más detalles.
\end_layout

\end_inset

.
\end_layout

\begin_layout Standard
Algoritmos de reemplazo de páginas:
\end_layout

\begin_layout Itemize

\series bold
Algoritmo óptimo
\series default
: Se elimina la página para la que pasará más tiempo antes de ser utilizada.
 Modelo teórico imposible de implementar.
\end_layout

\begin_layout Itemize

\series bold
NRU
\series default
 (no usada recientemente): Se limpia el bit de referenciado periódicamente
 en todas las páginas, y al reemplazar se prefieren páginas con este bit
 desactivado y, dentro de esto, con el de modificado desactivado.
\end_layout

\begin_layout Itemize

\series bold
FIFO
\series default
 (primera en enterar, primera en salir): Se elimina la primera página de
 una lista y se añade la nueva al final.
 El algoritmo es de bajo coste, pero no tiene en cuenta ningún dato adicional
 y produce demasiados fallos.
\end_layout

\begin_layout Itemize

\series bold
Algoritmo de la segunda oportunidad
\series default
: Como el FIFO pero, si el bit de referenciado de la primera página está
 activo, el bit se limpia, la página pasa al final y se comprueba la siguiente.
\end_layout

\begin_layout Itemize

\series bold
Algoritmo del reloj
\series default
: Equivalente al anterior pero con una lista circular donde una 
\begin_inset Quotes fld
\end_inset

manecilla
\begin_inset Quotes frd
\end_inset

 (un puntero) apunta a la página más antigua.
 Si el bit de referenciado está inactivo, se expulsa y se reemplaza en la
 lista la página apuntada y se avanza la manecilla a la siguiente, y de
 lo contrario se inactiva el bit, se pasa a la siguiente página y se repite
 el proceso.
\end_layout

\begin_layout Itemize

\series bold
LRU
\series default
 (usada menos recientemente): Se elimina la página no usada desde hace más
 tiempo.
 Se podría usar una lista ligada de todas las páginas de memoria, pero tendría
 que actualizarse en cada acceso a memoria.
 También se podría tener un contador hardware que se incrementa en cada
 referencia a memoria y un campo en las entradas de la tabla de páginas
 y la TLB donde copiarlo.
 Otra forma es usar una matriz 
\begin_inset Formula $n\times n$
\end_inset

, siendo 
\begin_inset Formula $n$
\end_inset

 el total de páginas, inicializada a 0, con lo que al referencial el marco
 
\begin_inset Formula $k$
\end_inset

, el hardware activa todos los bits de la fila 
\begin_inset Formula $k$
\end_inset

 y después desactiva todos los de la columna, con lo que la fila cuyo valor
 en binario sea mínimo es la del marco que se usó hace más tiempo, pero
 esto es inviable por el tamaño de la matriz.
\end_layout

\begin_layout Itemize

\series bold
Algoritmo de maduración
\series default
: Aproximación software de LRU.
 En cada interrupción de reloj, se desplaza un contador en cada entrada
 de la tabla de páginas un bit a la derecha y se añade a la izquierda el
 bit de referenciado.
\end_layout

\begin_layout Standard
Se debe decidir también si la página a reemplazar se busca sólo en las del
 proceso (
\series bold
reemplazo local
\series default
) o en todas las de memoria (
\series bold
reemplazo global
\series default
), y si el número de marcos asignados a un proceso varía (
\series bold
asignación dinámica
\series default
) o no (
\series bold
asignación fija
\series default
 o 
\series bold
estática
\series default
).
 No es posible el reemplazo global con asignación fija, pero el reemplazo
 local con asignación dinámica puede evitar que un proceso que empieza a
 producir fallos de página le quite páginas a otros siendo a la vez más
 flexible que una asignación fija.
 Llamamos 
\series bold
algoritmo de frecuencia de fallos de página
\series default
 al consistente en asignar más marcos a los procesos que producen muchos
 fallos de página y quitarlos a los que producen pocos.
 Otros aspectos son el número mínimo de marcos por proceso, que depende
 entre otros del máximo de páginas que puede usar una sola instrucción
\begin_inset Foot
status open

\begin_layout Plain Layout
Si, por ejemplo, una instrucción debe acceder a 5 páginas incluyendo la
 de la propia instrucción pero sólo hay 4 marcos, uno de los accesos provocará
 necesariamente un fallo de página que reemplazará otra de las 4 páginas
 necesarias y reiniciará la instrucción, que nunca llegará a terminar.
\end_layout

\end_inset

, y el reparto de marcos entre distintos procesos (equitativo, proporcional
 al tamaño, etc.).
\end_layout

\begin_layout Standard
Páginas pequeñas producen menos fragmentación interna, pero páginas grandes
 aceleran el reemplazo porque las transferencias entre memoria y disco son
 normalmente de una página y hay poca diferencia entre el tiempo de transferenci
a de una página pequeña y el de una grande.
 Los tamaños más frecuentes son de 4 y 
\begin_inset Formula $\unit[8]{KiB}$
\end_inset

.
\end_layout

\begin_layout Standard
La 
\series bold
hiperpaginación
\series default
 ocurre cuando un proceso emplea más tiempo paginando (esperando a que se
 resuelvan sus fallos de página) que ejecutando código porque necesita muchos
 más marcos de los que tiene.
 En tal caso, aparte de añadir más memoria principal, podemos suspender
 temporalmente algunos procesos para liberar memoria y reanudarlos cuando
 la tasa de fallos de página decaiga.
\end_layout

\begin_layout Standard
Políticas de lectura y escritura de páginas:
\end_layout

\begin_layout Itemize

\series bold
Paginación por demanda
\series default
: Solo se lee la página que produce el fallo.
\end_layout

\begin_layout Itemize

\series bold
Prepaginación
\series default
 o 
\series bold
paginación anticipada
\series default
: Se leen varias páginas más, normalmente las que se encuentran después
 en el espacio de direcciones virtuales.
\end_layout

\begin_layout Itemize

\series bold
Escritura por demanda
\series default
: Una página se escribe en disco cuando se expulsa, aumentando el tiempo
 de resolución de fallos de página.
\end_layout

\begin_layout Itemize

\series bold
Escritura anticipada
\series default
: Un hilo del núcleo, el 
\series bold
demonio de paginación
\series default
, cada cierto tiempo escribe en disco las páginas modificadas, aumentando
 el rendimiento en discos duros al escribir varias páginas a la vez y acelerando
 la resolución de fallos de página.
 Muchas escrituras pueden ser inútiles si la páginas se modifican poco después,
 por lo que el demonio puede buscar páginas que, según el algoritmo de reemplazo
, podrían expulsarse próximamente y escribirlas en disco si han sido modificadas.
 También puede liberar más páginas para tener páginas libres (
\series bold
caché de páginas
\series default
) y resolver rápidamente cualquier futuro fallo de página, de forma que
 si una página liberada se necesita poco después su contenido siga en memoria.
\end_layout

\begin_layout Section
Segmentación
\end_layout

\begin_layout Standard
El espacio de direcciones lógicas de un proceso se compone de 
\series bold
segmentos
\series default
, zonas contiguas dadas por una 
\series bold
base
\series default
 (dirección de comienzo) y un 
\series bold
límite
\series default
 (tamaño), y las direcciones especifican el número de segmento y el desplazamien
to dentro de él, de 0 al tamaño menos 1.
 Esto facilita la protección y compartición de información, y se puede acelerar
 la traducción con un TLB, pero sufre fragmentación externa, los segmentos
 no pueden superar el tamaño de la memoria física y los intercambios con
 el disco se hacen siempre moviendo segmentos enteros.
\end_layout

\begin_layout Standard
En la 
\series bold
segmentación paginada
\series default
 estos segmentos se paginan, por lo que no hay fragmentación externa ni
 hay que buscar un hueco adecuado para cada segmento.
 El TLB es direccionable por el número de segmento a usar y el número de
 la página dentro del segmento.
\end_layout

\end_body
\end_document