diff options
Diffstat (limited to 'iso/n5.lyx')
| -rw-r--r-- | iso/n5.lyx | 879 |
1 files changed, 879 insertions, 0 deletions
diff --git a/iso/n5.lyx b/iso/n5.lyx new file mode 100644 index 0000000..50cbe03 --- /dev/null +++ b/iso/n5.lyx @@ -0,0 +1,879 @@ +#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 |