Tabla de páginas: no entiendo cómo se ha hecho esta tabla [cerrada]

Tiene cuatro páginas físicas de memoria y ocho páginas virtuales. Todas las páginas físicas comienzan sin asignar para ningún propósito en particular. La tabla virtual de ocho entradas comienza con todas las páginas virtuales siendo inválidas.

Esa es la situación de partida. Un detalle más puede ser útil aquí: definir CÓMO se asignarán las nuevas páginas físicas. Dados los resultados, creo que está claro que el método de asignación comienza asignando la página física 0, primero. Luego la página física 1. Etc. Una vez que se han asignado todas las páginas físicas al menos una vez, es cuando entra en juego el algoritmo LRU (menos utilizado recientemente).

Así que eso establece el proceso.

Una cosa más podría ser útil para considerar agregar. Así es como se maneja la propia LRU. Piense en esto como una pila de ocho cartas. Una tarjeta que representa cada página virtual. Así que llamemos a las cartas: 0, 1, 2, 3, etc., por razones obvias. La baraja siempre tiene ocho cartas. Inicialmente, el mazo comienza como 01234567 (o cualquier otro orden que desee). Al asignar una nueva página, siempre tomamos la carta superior (que será el dígito más a la izquierda aquí) del mazo, use cualquier página física que indique , y luego vuelve a colocar esa carta en la parte inferior del mazo. Entonces, por ejemplo, si necesitáramos una nueva página física, iríamos a este mazo inicial de "0123", sacaríamos la carta superior (que es "0"), asignaríamos esa página física y luego volveríamos a colocar esa carta en la cubierta en la parte inferior. Así que la nueva baraja sería "1230" después de haber terminado con este paso. Cada vez que se accede a una página física, encontramos su carta en este mazo y la movemos al final también.

Para resumir el mazo LRU: cuando necesitamos una nueva página física, siempre tomamos la carta superior y usamos cualquier página que indique el valor allí y luego movemos esa carta al final del mazo. Siempre que accedemos a una página física, siempre encontramos la carta asociada a esa página y la movemos a la parte inferior de la baraja.

Eso es todo. Mostraré el mazo junto con cada paso dado.

Ahora todo lo que tiene que hacer es "actuar como la computadora" y hacer el trabajo a mano, recorriendo la lista de direcciones sucesivas en orden. Es solo un simple trabajo manual.

Cada dirección virtual tiene una página y un desplazamiento . El valor de compensación son los 9 bits de orden inferior de la dirección virtual y la página son los 3 bits superiores de la dirección virtual. La logica es como sigue:

Si la entrada de la tabla virtual no es válida, asigne una página de una lista de páginas físicas libres. Pero si no quedan páginas físicas libres, a partir de una búsqueda de entradas válidas de la tabla virtual asigne la página física de la entrada de la tabla virtual que contiene la página utilizada menos recientemente. Además, en este caso, marque la entrada de la tabla virtual encontrada como no válida porque la página física que posee se está reasignando ahora. Luego tome esta página física y colóquela en la entrada de la tabla virtual actual y márquela como válida. Finalmente, lleve esta entrada de la tabla virtual a la parte superior de la lista de LRU, lo que indica que se usó recientemente.

Si la entrada de la tabla virtual está marcada como válida, coloque esta entrada de la tabla virtual en la parte superior de la lista de LRU, lo que nuevamente indica que se usó recientemente.

El algoritmo anterior se repite una y otra vez para cada una de sus direcciones virtuales, en orden secuencial. Ignora los detalles de la formación de la dirección de memoria física completa de 11 bits. Pero no necesito preocuparme por esa parte, porque su pregunta no se trata de eso, sino de cómo la mesa llegó a la condición en que estaba. Así que estoy descuidando ese detalle para evitar el exceso de detalles aquí.

Estos son los pasos con sus direcciones, en orden:

$$\begin{array}{lrllll} \underline{\textrm{Step}} & {\underline{~~~~~~~~~~~~~~~~~~~~\textrm{Action}~~}} & \underline{\textrm{Free}} & \underline{\textrm{LRU}} & \underline{\textrm{Valid}~~~~~~~~~~~} & \underline{\textrm{Frame}~~~~} \\ & & 0123 & & \textrm{FFFFFFFF} & \textrm{oooooooo} \\ & \textbf{new address 1:265} & & & & \\ (1) & alloc = free & 123 & & \textrm{FFFFFFFF} & \textrm{oooooooo} \\ (2) & frame_1 = alloc & 123 & & \textrm{FFFFFFFF} & \textrm{o0oooooo} \\ (3) & valid_1 = true & 123 & & \textrm{FTFFFFFF} & \textrm{o0oooooo} \\ (4) & LRU(1) & 123 & 1 & \textrm{FTFFFFFF} & \textrm{o0oooooo} \\ & \textbf{new address 3:511} & & & & \\ (1) & alloc = free & 23 & 1 & \textrm{FTFFFFFF} & \textrm{o0oooooo} \\ (2) & frame_3 = alloc & 23 & 1 & \textrm{FTFFFFFF} & \textrm{o0o1oooo} \\ (3) & valid_3 = true & 23 & 1 & \textrm{FTFTFFFF} & \textrm{o0o1oooo} \\ (4) & LRU(3) & 23 & 31 & \textrm{FTFTFFFF} & \textrm{o0o1oooo} \\ & \textbf{new address 2:175} & & & & \\ (1) & alloc = free & 3 & 31 & \textrm{FTFTFFFF} & \textrm{o0o1oooo} \\ (2) & frame_2 = alloc & 3 & 31 & \textrm{FTFTFFFF} & \textrm{o021oooo} \\ (3) & valid_2 = true & 3 & 31 & \textrm{FTTTFFFF} & \textrm{o021oooo} \\ (4) & LRU(2) & 3 & 231 & \textrm{FTTTFFFF} & \textrm{o021oooo} \\ & \textbf{new address 2:76} & & & & \\ (4) & LRU(2) & 3 & 231 & \textrm{FTTTFFFF} & \textrm{o021oooo} \\ & \textbf{new address 1:34} & & & & \\ (4) & LRU(1) & 3 & 123 & \textrm{FTTTFFFF} & \textrm{o021oooo} \\ & \textbf{new address 0:129} & & & & \\ (1) & alloc = free & & 123 & \textrm{FTTTFFFF} & \textrm{o0o1oooo} \\ (2) & frame_0 = alloc & & 123 & \textrm{FTTTFFFF} & \textrm{3021oooo} \\ (3) & valid_0 = true & & 123 & \textrm{TTTTFFFF} & \textrm{3021oooo} \\ (4) & LRU(0) & & 0123 & \textrm{TTTTFFFF} & \textrm{3021oooo} \\ & \textbf{new address 6:129} & & & & \\ (1) & alloc = frame_{LRU} & & 012 & \textrm{TTTFFFFF} & \textrm{3021oooo} \\ (2) & frame_6 = alloc & & 012 & \textrm{TTTFFFFF} & \textrm{3021oo1o} \\ (3) & valid_6 = true & & 012 & \textrm{TTTFFFTF} & \textrm{3021oo1o} \\ (4) & LRU(6) & & 6012 & \textrm{TTTFFFTF} & \textrm{3021oo1o} \\ \end{array}$$

Debería poder hacer coincidir la última entrada anterior con su tabla, creo. El único truco aquí es tener en cuenta que la entrada de la tabla virtual LRU es '3' pero la página física propiedad de esa entrada de la tabla virtual es la página física '1'. La entrada de la tabla virtual para '3' se marca como falsa, pero la variable alloc se establece en 1, ya que esa es la página física que se asignó allí.

EDITAR: A su pregunta:

No entiendo el orden de la segunda tabla. ¿Por qué empezamos con 11, luego 00, luego 10, etc. No tiene sentido para mí...

No comenzamos con 11. Esa columna es el número de página física. Claramente, no asignamos la página física 3 (11 binarios) desde el principio. En cambio, resulta que cuando apareció la dirección 0:129, solo quedaba una página física libre: la página 3. ¡Pero eso va a la fila 0 de la tabla de páginas virtuales, por supuesto! Porque la página virtual a la que hace referencia 0:129 es la fila 0 en la tabla virtual. Pero la página física (marco) es 3. Entonces 3 está almacenado allí (11 binario).

Las direcciones proporcionadas en la primera tabla son direcciones virtuales en un espacio de direcciones de 12 bits y el propósito de la tabla de páginas es asignarlas a direcciones físicas. Debido a que las páginas son de 512 bytes y hay 4 páginas físicas, las direcciones físicas son de 11 bits, compuestas por un número de trama de 2 bits y un desplazamiento de 9 bits. La tabla de páginas tiene ocho ranuras, una para cada página en el espacio de direcciones virtuales. (Esto es, por supuesto, completamente impráctico, pero esa es la naturaleza de los problemas de los libros de texto).

De acuerdo con la hipótesis de la pregunta, la tabla de páginas comienza vacía con valid=0 en cada ranura. Siguiendo la secuencia de referencias de memoria en la primera tabla, la primera referencia es a la página 1. Esa es una falla de página, porque el bit válido en la ranura 1 es, por supuesto, 0. Así que traemos la página 1 del disco, la ponemos página física 0 y actualice la tabla de páginas con

1: frame=0, valid=1

La siguiente referencia (2047) es a la página 3, nuevamente un error. Así que ponemos la página virtual 3 en la página física 1 y actualizamos la tabla de páginas con

3: frame=1, valid=1

En este punto (para que quede claro), la tabla de páginas contiene

0:          valid=0
1: frame=0, valid=1
2:          valid=0
3: frame=1, valid=1
4:          valid=0
5:          valid=0
6:          valid=0
7:          valid=0

de modo que para cada número de página virtual que hemos utilizado, la tabla de páginas muestra el número de página física correspondiente. Esa organización hace que la traducción implementada por hardware de una dirección virtual a una física sea simple y rápida.

La siguiente es la página 2, en la página física 2. Entrada de la tabla de páginas:

2: frame=2, valid=1

La siguiente referencia es a la página virtual 2 de nuevo, por lo que no provoca un error de página. Luego, la página virtual 1 nuevamente, también sin fallas. La siguiente es la página virtual 0, que va en la página física 3

0: frame=3, valid=1

La referencia final es a la página virtual 6, que no hemos visto antes. Necesitamos asignar un marco de página, pero en este punto los 4 están en uso, lo que significa desalojar una página existente para hacer espacio. Para elegir a la víctima, seguimos una política de reemplazo que se implementa en el software, y se nos dice que usemos la política de uso menos reciente. Así que buscamos la página residente que no se ha utilizado durante más tiempo, y esa es la página 3. Desalojamos esa página, traemos la página 6 y actualizamos la tabla de páginas para que lea

3: (frame=1), valid=0
6: frame=1, valid=1

El campo de marco de la ranura 3 no importa, pero también podemos dejarlo como 1. Poniendo todas las entradas juntas, obtienes la tabla de páginas que se muestra en tu segunda tabla. Los números de cuadro se muestran, naturalmente, en binario allí.