# SOA: Ejercicios UD2
## Ejemplos conjuntos de trabajo (Working Set) P2
## Buddy system: Ejercicio enero 2025
Un sistema operativo utiliza el sistema buddy para las peticiones a memoria con páginas/marcos de tamaño 4KiB.
Se dispone de un bloque de 1MiB para la asignación de marcos. La memoria ocupada por las tablas no se considera en este ejercicio.
Para mantener la lista de memoria libre se usa una estructura denominada free_area en la que se agrupan los buddies disponibles. Así, free_area[n] permite acceder a la lista de buddies de 2^n^ marcos contiguos.
1. Muestre el estado inicial de free_area y el valor de MAX usando un diagrama como el mostrado a continuación:
2. En un momento dado se lanzan dos procesos que tienen asignados 4 marcos de página cada uno. Indique el estado de free_area después de haber asignado 8 marcos de página.
---
La gestión de la memoria asignada a los marcos se realiza con el demonio kswapd que cada segundo comprueba el estado de los marcos y busca aquellos cuya memoria puede ser liberada de acuerdo a un algoritmo de aproximación al LRU con envejecimiento de acuerdo a los siguientes criterios:
* Todas las páginas se inician con edad 3
* Si se accede a una página, R=1, se incrementa en 3 la edad de la página, hasta un máximo de 20
* Si se ejecuta kswapd, se decrementa en 1 la edad de las páginas que no han sido usadas en el intervalo anterior (bit R = 0)
* Si un marco alcanza edad cero se libera la memoria asignada al marco, añadiéndolo a lista de memoria libre
* El bit P indica que una página está presente. El bit D (Dirty) indica si un marco ha sido escrito
En un instante dado, durante la ejecución de los dos procesos, el contenido de las tablas de página y la edad de los marcos es el mostrado a continuación.
Si en este momento se ejecuta kswapd:
3. Indique los nuevos valores de la edad de los marcos de página.
4. ¿Qué acciones llevaría a cabo el SO, indicando las modificaciones sufridas por las tablas de páginas?
5. ¿Cuál sería el estado de la estructura free_area?
:::spoiler
1. Muestre el estado inicial de free_area y el valor de MAX usando un diagrama como el mostrado a continuación:
2. Indique el estado de free_area después de haber asignado 8 marcos de página.
Se divide el bloque de 1 Mb de forma sucesiva hasta asignar los 8 marcos necesarios. Suponiendo que se hayan asignado los 8 primeros marcos numerados del 0 al 7, el siguiente bloque de 8 comienza en el marco 8.
3. ¿Indique los nuevos valores de la edad de los marcos de página?
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 20 | 19 | 0 | 0 | 20 | 4 | 4 | 4 |
4. ¿Qué acciones llevaría a cabo el SO, indicando las modificaciones sufridas por las tablas de páginas?
* Los marcos 2 y 3 serán liberados.
* El marco 3, correspondiente a la página 3 del primer proceso está etiquetado como modificado (D) por lo que deberá guardarse el contenido del marco 3 antes de su liberación.
* Todos los bits de referencia serán borrados.
* Las páginas 2 y 3 del primer proceso serán marcadas como no presentes.
5. ¿Cuál sería el estado de la estructura free_area?
:::
## Ejercicio EXAMEN Junio 2022
Ejercicio 1 (20 puntos / 45 minutos)
Un sistema operativo dispone de memoria virtual paginada con las características siguientes:
* Un único espacio de memoria virtual de 4GB a compartir por todos los procesos que se creen
* Una memoria principal de 2GB
* Páginas de 4KB
* Tabla de páginas de dos niveles con descriptores de página de 4 Bytes. Cada entrada de la tabla de páginas contiene, además del marco de página, 4 bits de estado, los bits P, R, D, W. Cuando están activos, señalizan que la página está presente (P), ha sido referenciada (R), ha sido escrita (Dirty) y si está permitida la escritura (Write).
1. ¿Que representan los valores A, B, C y D en el siguiente código?, ¿A qué secciones de memoria pertenecen? (3 puntos)
```c=
#include <stdio.h>
#include <stdlib.h>
int y=1;
int main(int argc, char *argv[])
{
int x = 100 * y;
printf("Dirección A : %p\n", (void *) &y);
printf("Dirección B : %p\n", (void *) main);
printf("Dirección C : %p\n", (void *) &x);
printf("Dirección D : %p\n", (void *) malloc(1));
return x;
}
```
:::spoiler
* A: localización de la variable “y”, sección de datos inicializados(DATA).
* B: comienzo de la función main, sección de código (TEXT).
* C: localización de la variable “x”, sección de pila (STACK).
* D: solicitud de memoria dinámica, sección “heap” (HEAP).
:::
---
Suponga ahora que se está ejecutando como único proceso el siguiente código:
```c=
#include <stdio.h>
#include <stdint.h>
#define TAM_VECTOR 4096
#define TAM_FILAS 1024
#define NUM_FILAS 4
float X[TAM_VECTOR]; // array con 4096 elementos
float A[NUM_FILAS][TAM_FILAS]; // array bidimensional, 1024 elementos
// por fila, 4 filas
uint32_t n, x, y;
void main()
{
for(n = 0; n < TAM_VECTOR; n++)
{
X[n] = (float)n;
}
for( y = 0; y < NUM_FILAS; y++)
{
for( x = 0; x < TAM_FILAS; x++)
{
A[y][x] = X[(y * TAM_FILAS) + x];
}
}
}
```
Suponga también que el código cabe de forma completa en una única página virtual, por ejemplo, la ```0x0000``` que tiene asignado el marco ```0x3000``` y que los datos se ubican a partir de la página virtual ```0x1000``` en el orden en el que están declarados. Los elementos de los arrays ```X``` y ```A``` se almacenan de forma consecutiva. En el caso de ```A``` se almacenan por filas y en orden creciente del número de fila. Los números enteros (```uint32_t```) y en coma flotante (```float```) ocupan 4 bytes.
Con todo ello se pide responder, de forma razonada, a las cuestiones siguientes:
1. Indique las páginas y direcciones virtuales de comienzo de los arrays ```A```, ```X``` y la variable ```y```. Indique también las direcciones virtuales de los siguientes datos: ```A[0,2]```, ```A[2,0]``` y ```X[128]``` (5 puntos)
Comienzo ```A```:
Comienzo ```X```:
Localización ```y```:
```A[0,2]```:
```A[2,0]```:
```X[128]```:
:::spoiler
* Comienzo ```A```: ```0x00005000``` -> página 5, el vector X ocupa las 4 primeras páginas (1, 2, 3 y 4)
* Comienzo ```X```: ```0x00001000``` -> página 1
* Localización variable ```y```: ```0x00009008``` -> página 9, desplazamiento 8, “n” y “x” ocupan los 8 primeros
* ```A[0,2]```: ```0x00005008``` -> Estamos en el tercer elemento de la primera fila, cada uno ocupa 4 octetos
* ```A[2,0]```: ```0x00007000``` -> Cada fila ocupa una página, estamos en la tercera
* ```X[128]```: ```0x00001200``` -> Elemento 128 decimal en la primera página, cada elemento ocupa 4 posiciones
:::
---
2. En el supuesto de que haya marcos libres suficientes para todas las páginas de datos referenciadas y que se asignan en orden creciente según se han declarado comenzando desde el marco ```0x4000```. Indique cuál será la serie de carga de páginas y los marcos asociados en memoria principal debido a la ejecución de dicho programa. Indique la cantidad de memoria no asignada debido a fragmentación interna. (5 puntos)
<br>
<br>
:::spoiler
El vector ```X``` ocupa las páginas 1,2,3 y 4, el array bidimensional ```A``` ocupa otras 4 páginas, 5, 6 ,7 y 8. Las variables ```n```, ```x``` e ```y``` estarían en la página 9
<br>
* Vector ```X```: Página 1 -> Marco 0x4000, Página 2 -> Marco 0x5000, Página 3 -> Marco 0x6000, Página 4 -> Marco 0x7000
* Array ```A```: Página 5 -> Marco 0x8000, Página 6 -> Marco 0x9000, Página 7 -> Marco 0xA000, Página 8 -> Marco 0xB000
* Variables ```n```, ```x``` e ```y```: Página 9 -> Marco 0xC000
Las variables ```n```, ```x``` e ```y``` ocupan 4 octetos cada una, 12 en total. Una página tiene una capacidad de 4096 octetos por lo que se pierden por fragmentación interna 4096 - 12 = 4084 octetos.
:::
---
3. En este caso, ¿Cuál sería la dirección real de comienzo de ```A[0,2]```, ```A[2,0]```, ```X[128]```. (2 puntos)
```A[0,2]```:
```A[2,0]```:
```X[128]```:
:::spoiler
* ```A[0,2]```: 0x00008008 -> Estamos en el tercer elemento de la primera fila, cada uno ocupa 4 octetos
* ```A[2,0]```: 0x0000A000 -> Cada fila ocupa una página, estamos en la tercera
* ```X[128]```: 0x00004200 -> Elemento 128 decimal en la primera página, cada elemento ocupa 4 posiciones
:::
<br>
<br>
4. Suponga ahora que NO haya marcos libres suficientes para todas las páginas referenciadas y solo se han asignado 4 marcos de página para la ejecución de este programa y se utilizase el algoritmo de sustitución ÓPTIMO. ¿Cuáles serían las primeras 4 páginas asignadas al inicio del programa? ¿Cuál sería la cadena de referencia en los accesos a los arrays X y A en memoria por parte del programa? ¿Cuál sería la secuencia de reemplazo que se seguiría por parte del SO para asignar los marcos disponibles? (5 puntos)
<table>
<tr>
<th>Cadena de referencia</th>
<th>Inicio</th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
</tr>
<tr>
<td>Marco 0</td>
<td></td>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
</tr>
<tr>
<td>Marco 1</td>
<td></td>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
</tr>
<tr>
<td>Marco 2</td>
<td></td>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
</tr>
<tr>
<td>Marco 3</td>
<td></td>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
</tr>
<tr>
<td>Page out</td>
<td></td>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
<th> </th>
</tr>
</table>
:::spoiler
El programa copia el contenido del vector X en A, distribuyéndolo en 4 filas de 1024 elementos. X y A ocupan ambas 4 páginas. Para hacer la copia necesitamos las páginas de código, la página de datos origen, la página de datos destino y la página de las variables de control. Inicialmente serían las páginas: 0, 1, 5 y 9.
<table>
<tr>
<th></th>
<th>Página</th>
<th>Estado</th>
</tr>
<tr>
<td>Código</td>
<td>0</td>
<th>Presente</th>
</tr>
<tr>
<td>X</td>
<td>1</td>
<th>Presente</th>
</tr>
<tr>
<td>X</td>
<td>2</td>
<th></th>
</tr>
<tr>
<td>X</td>
<td>3</td>
<th></th>
</tr>
<tr>
<td>X</td>
<td>4</td>
<th></th>
</tr>
<tr>
<td>A</td>
<td>5</td>
<th>Presente</th>
</tr>
<tr>
<td>A</td>
<td>6</td>
<th></th>
</tr>
<tr>
<td>A</td>
<td>7</td>
<th></th>
</tr>
<tr>
<td>A</td>
<td>8</td>
<th></th>
</tr>
<tr>
<td>Variables de control</td>
<td>9</td>
<th>Presente</th>
</tr>
</table>
Al finalizar la copia de la primera página de X, se accederá a la segunda página de X que deberá copiarse en la página 6 de A.
La página 2 no está presente. Viendo el código y aplicando un reemplazo optimo sabemos que ya no se accederá a la página 1 de X por lo que podríamos marcarla como no presente y reusar el marco asignado. Otra alternativa sería reemplazar la página 5, ya que tampoco se usará más. Ahora se copiarían datos a la página 6, para ello procedemos al reemplazo con la 5 ( o la 1 si en el caso anterior hubiéramos usado la 5). El estado de la tabla sería:
<table>
<tr>
<th></th>
<th>Página</th>
<th>Estado</th>
</tr>
<tr>
<td>Código</td>
<td>0</td>
<th>Presente</th>
</tr>
<tr>
<td>X</td>
<td>1</td>
<th></th>
</tr>
<tr>
<td>X</td>
<td>2</td>
<th>Presente</th>
</tr>
<tr>
<td>X</td>
<td>3</td>
<th></th>
</tr>
<tr>
<td>X</td>
<td>4</td>
<th></th>
</tr>
<tr>
<td>A</td>
<td>5</td>
<th></th>
</tr>
<tr>
<td>A</td>
<td>6</td>
<th>Presente</th>
</tr>
<tr>
<td>A</td>
<td>7</td>
<th></th>
</tr>
<tr>
<td>A</td>
<td>8</td>
<th></th>
</tr>
<tr>
<td>Variables de control</td>
<td>9</td>
<th>Presente</th>
</tr>
</table>
Este proceso se repite para las cuatro páginas que ocupan X y A. Hay que recordar que para que esto ocurra hay que acceder al código y a las varibles de control aunque no lo representemos en la cadena de referencia.
Una posible secuencia sería:
<table>
<tr>
<th>Cadena de referencia</th>
<th>Inicio</th>
<th>Página 2</th>
<th>Página 6</th>
<th>Página 3</th>
<th>Página 7</th>
<th>Página 4</th>
<th>Página 8</th>
<th>Final</th>
</tr>
<tr>
<td>Marco 0</td>
<td>0</td>
<th>0</th>
<th>0</th>
<td>0</td>
<th>0</th>
<th>0</th>
<th>0</th>
<th>0</th>
</tr>
<tr>
<td>Marco 1</td>
<td>1</td>
<th>2 *</th>
<th>2</th>
<td>3 *</td>
<th>3</th>
<th>4 *</th>
<th>4</th>
<th>4</th>
</tr>
<tr>
<td>Marco 2</td>
<td>9</td>
<th>9</th>
<th>9</th>
<td>9</td>
<th>9</th>
<th>9</th>
<th>9</th>
<th>9</th>
</tr>
<tr>
<td>Marco 3</td>
<td>5</td>
<th>5</th>
<th>6 *</th>
<td>6</td>
<th>7 *</th>
<th>7</th>
<th>8 *</th>
<th>8</th>
</tr>
<tr>
<td>Page out</td>
<td></td>
<th>1</th>
<th>5</th>
<td>2</td>
<th>6</th>
<th>3</th>
<th>7</th>
<th></th>
</tr>
</table>
:::
Sign in with Wallet
Connect another wallet