Sessions de problemes: tema 3

PROBLEMA: Analitza detingudament el codi de la figura 2 (programa mem) i respon les preguntes justificadament. Considereu que s’executa en un sistema Linux, amb Copy on Write i la mida de pàgina de 4KB. La mida de l’executable miprog és la mateixa que la de mem.

 1        /************** mem.c ****************/
 2        #define MIDAPAGINA 4096
 3        int matrix[MIDAPAGINA*16];
 4        void fgolafre(int j) {
 5        int i;
 6        for (i=j;i<MIDAPAGINA*16;i++) {
 7        matrix[i]=23;
 8        }
 9        }
10        int main() {
11        int *vector;
12        vector=(int*)malloc(MIDAPAGINA*8);
13        if (fork()==0) {
14        execlp("miprog","miprog",NULL);
15        }
16        else if (fork()==0) {
17        vector[4]=73;
18        exit(0);
19        }
20        fgolafre(MIDAPAGINA*4);
21        waitpid(-1,NULL,0);
22        waitpid(-1,NULL,0);
23        free(vector);
24        return 0;
25        }
26

A quina regió de memòria està el contingut de la variable matrix? I el contingut de vector?

Resposta

matrix és una variable global no inicialitzada, per tant, estarà a la zona de dades.

vector és una variable local, per tant, estarà a la pila, però el seu contingut estarà el heap.
Quines regions de memòria es modificaran en executar-se la crida a la funció fgolafre?

Resposta

El codi de la funció recorre part de matrix, que és a la zona de dades. Però també té paràmetres i variables locals que són a la pila.
Just després del malloc, part del contingut del fitxer maps del procés pare és el següent:

/proc/29390$ cat maps
55a6e75e9000-55a6e75ea000 r-xp 00000000 08:01 1074816         /home/alumne/final/mem
55a6e77e9000-55a6e77ea000 r--p 00000000 08:01 1074816         /home/alumne/final/mem
55a6e77ea000-55a6e77eb000 rw-p 00001000 08:01 1074816         /home/alumne/final/mem
55a6e9248000-55a6e9269000 rw-p 00000000 00:00 0               [heap]
7fff35c97000-7fff35cb8000 rw-p 00000000 00:00 0               [stack]

Quantes pàgines mesura la regió del heap? Quant feia abans del malloc?

Resposta

stem:[55a6e9269000 - 55a6e9248000 = 21000], és a dir, stem:[21_16] páginas (1000 en hexa és 4096 en base 10). Moltes més de les 8 demanades. Abans d'aquesta línia el heap no existia.

Quin procés provoca més fallades de pàgina a causa de l’ús de COW? Si no hi hagués COW, quin procés seria el més perjudicat?

Resposta

 El procés pare escriu a més pàgines compartides, cosa que provocarà errors de pàgina per demanar noves pàgines per al procés fill i copiar-les.
Si no hi hagués COW, el primer procés fill seria el més perjudicat quant a temps de creació al fork. Caldria demanar memòria i copiar totes les pàgines del pare, per immediatament rebutjar-les en canviar la imatge del procés a la crida a execlp.

PROBLEMA: En un sistema amb gestió de memòria basada en paginació, amb una mida de pàgina de 4KB, que no disposa de memòria virtual, executem el codi següent sense que hi hagi altres processos en execució.
1 int miarray[256]: 2 main(){ 3 int ret,i; 4 5 for (i=0;i<255;i++) 6 miarray[i]=0; 7 ret=fork(); 8 /*Hem arribat al primer punt*/ 9 for (i=0;i<255;i++) 10 miarray[i]=ret; 11 /*Hem arribat al segon punt*/ 12 13}
La regió de codi ocupa 1KB, la regió de pila ocupa 256Bytes, i la regió de dades ocupa 1KB. La figura següent mostra l’estat de les taules de pàgines dels dos processos, suposant que ambdós processos arriben alhora a la línia 8 i que tots dos arriben alhora a la línia 11 (per a cada entrada es mostra només el camp corresponent al frame) .

Figure 1. cas A: línia 8.

Figure 2. cas B: línia 11
1. Suposant que ambdós processos són a la línia 8 (cas A), calcula la quantitat de memòria física expressada en Bytes reservada entre els dos processos. Justifica el càlcul.
  
  Resposta
  
  A les taules de pàgines apareixen 4 frames diferents (405,406,407 i 408): 4KB*4=16384 Bytes
2. Tenint en compte el codi i els estats de les taules de pàgines. Podem deduïr si aquest sistema ofereix COW? Per què?
  
  Resposta
  
  Entre la línia 8 i la 11 canvia la traducció d’una de les pàgines per a 1 dels processos (la pàgina lògica 2 passa de tenir associat el frame 406 a tenir associat el frame 409). Això vol dir que ha deixat de compartir-se. Entre aquestes dues línies es modifica la variable miarray que està a la zona de data, cosa que obliga a fer la rèplica entre els dos processos.
3. Tenint en compte el codi i els estats de les taules de pàgines, és possible deduir en quin frame o frames tenim el contingut de cada regió de cada procés?
  
  Resposta
  
  L’espai d’adreces dels dos processos tenen la regió de codi (que no es modifica), la de pila (que es modifica) i la de dades (que també es modifica). A la línia 8 només hem modificat la pila (variable ret), per tant en els frames 407 i 408 tenim les piles del cada procés. A la línia 11 s’ha modificat la regió data, per tant, els frames 406 i 409 tenen la regió de data de cada procés. I la pàgina 405, el codi compartit.
4. Suposant que ambdós processos són a la línia 8 (cas A), tenim fragmentació interna? Si és així calcula la quantitat de memòria que es malgasta entre els dos processos en aquest punt.
  
  Resposta
  
  Dels 16384 Bytes reservats (4 pàgines de 4096 Bytes cadascuna) només s’usen 2560 Bytes (la suma del que ocupa el contingut de les 4 pàgines): es desaprofiten 13824.

PROBLEM: (Q1_2017-18, 2 points) Let’s consider a memory management system based on pagination. Page size is 4 KB. The size of an integer is 4 Bytes, the size of a character is 1 Byte, and the size of a pointer is 4 Bytes. This system implements COW and loading on demand.

1.        int buffer1[2500];
2.        main() {
3.        int *buffer4;
4.        int ret,i;
5.           // point A
6.           buffer4=sbrk(2500*sizeof(int));
7.
8.           for (i=0; i<2500; i++)
9.              buffer4[i] = i;
10.
11.           ret=fork();
12.           // point B
13.           for (i=0;i<2500;i++)
14.              buffer1[i] = buffer4[i];
15.           // point C
16.           if (ret == 0)
17.              exit(0);
18.           waitpid(-1,NULL,0);
19.
20.           // point D
21.        }

Table 1. Point A
Region	Memory

Region	Memory
Text	1 page
Data	3 pages
Stack	1 page
Heap	0 pages

Region

Memory

Text

1 page

Data

3 pages

Stack

1 page

Heap

0 pages

JUSTIFICACTION: There is only one process in execution at this point. The size of the Code is 2KB , but the assignment unit is a page (and different regions do not share pages) for this reason, we need a whole page for the text region. We have just one global variable: buffer1, which is an array of 2500 integers (10000 Bytes), so we need 3 pages for the region of the global variables (Data). The region of local variables (Stack) only holds 1 pointer and 2 integers (12 Bytes), so this region fits in one page. At this ppoint,the program has not allocated dynamic memory, so the heap is empty.

Table 2. Point B
Region	Memory

Answer

Region	Memory
Text	1 page
Data	3 pages
Stack	2 pages
Heap	0 pages

Region

Memory

Text

1 page

Data

3 pages

Stack

2 pages

Heap

0 pages

JUSTIFICATION: In this point the parent has allocated and initialized a dynamic memory region to store 2500 integers (10000 Bytes), so we need 3 pages for the heap. In addition, a new process has been created. The system implements the COW optimization and thus, parent and child share physical memory until some of them writes into it. In this point, only the variable ret has been modified (which is stored in the Stack), for this reason, the stack is the only region duplicated.

Table 3. Point C
Region	Memory

Answer

Region	Memory
Text	1 page
Data	6 pages
Stack	2 pages
Heap	3 pages

Region

Memory

Text

1 page

Data

6 pages

Stack

2 pages

Heap

3 pages

JUSTIFICATION: In this point, child process has finished the execution, so we only need memory to store the address space of the parent. This memory is the same used at point B because the process has not modified the heap.

Table 4. Point D
Region	Memory

Answer

Region	Memory
Text	1 page
Data	3 pages
Stack	1 page
Heap	3 pages

Region

Memory

Text

1 page

Data

3 pages

Stack

1 page

Heap

3 pages

PROBLEMA: (QT2022-2023) Tenemos el siguiente código del programa “memoria”. Este programa se ejecuta en un sistema Linux con tamaño de página 4096 bytes y nuestro sistema implementa la optimización de COW.

1.        int *p1;
2.        #define M_SIZE 4096
3.        void print_limit()
4.        {
5.          char buffer[256];
6.          void* limit;
7.          limit = sbrk(0);
8.          sprintf(buffer,"Limite %p\n", limit);
9.          write(1,buffer,strlen(buffer));
10.        }
11.        void main(int argc,char *argv[])
12.        {
13.          int  ret, i ;
14.          print_limit();
15.          p1 = sbrk(M_SIZE * sizeof(int));
16.          print_limit();
17.          for (i = 0; i < M_SIZE; i++) p1[i] = 0;
18.          ret = fork();
19.          /* A */
20.          sbrk(-1 * M_SIZE * sizeof(int));
21.          print_limit();
22.        }
23.

Al ejecutarlo tenemos la siguiente salida:

[user@login]$ ./memoria
Limite 0x1971000
Limite 0x1975000
Limite XXXXXXXXX
Limite YYYYYYYYY

Contesta a las siguientes preguntas:

Rellena las líneas punteadas con la respuesta correcta.
1. La variable p1 está en la región de memoria …
  
  Respuesta
  
  data
2. la variable limit está en la región de memoria …
  
  Respuesta
  
  pila/stack
3. El valor que veremos en las XXXXXXXX es …
  
  Respuesta
  
  0x1971000
4. en las YYYYYYYYY es …
  
  Respuesta
  
  0x1971000
  
  Si nos dan la siguiente información: el tamaño de la pila es 4096 bytes, el código de este programa ocupa 1000 bytes, la variable p1 ocupa 8 bytes y el tamaño de un int son 4 bytes.
5. ¿Cuantos marcos de página (páginas físicas) tendrán reservados en el punto A para la región de código?
  
  Respuesta
  
  El código se puede compartir. Como las páginas se reservan completas será 1 página en total.
6. ¿Cuantos marcos de página (páginas físicas) tendrán reservados en el punto A para la región de data?
  
  Respuesta
  
  P1 es una variable global que se inicializa antes del fork por lo que una única página será suficiente. Como no se modifica, no es necesario reservar una privada por proceso por lo que en total será una única página.