ESCOLA POLITECNICA DA UNIVERSIDADE DE SÃO PAULO

Anauê Costa

Carolina Dorta

Fábio Gutiyama

Gerenciamento de

Memória no MINIX 3 Projeto 4 da disciplina Sistemas Operacionais

Índice

GERENCIAMENTO DE MEMÓRIA ............................................................................................................ 3

STRUCT HOLES .............................................................................................................................................. 4

CÓDIGO DA ALLOC_MEM ................................................................................................................................ 5

LIBERAÇÃO DE MEMÓRIA ................................................................................................................................ 6

AO TECLAR F8: HOW TO ......................................................................................................................... 7

DMP.C ........................................................................................................................................................ 7

PROTO.H ..................................................................................................................................................... 8

TAREFA ....................................................................................................................................................... 8

RELACIONANDO COM SEGMENTOS ....................................................................................................... 9

SEGMENTOS NO MINIX ................................................................................................................................. 9

MAPA DA MEMÓRIA .................................................................................................................................... 12

ALGORITMOS DE BUSCA E ALOCAÇÃO ................................................................................................. 13

CONCEITOS ................................................................................................................................................ 13

IMPLEMENTAÇÃO ........................................................................................................................................ 14

RESULTADOS .............................................................................................................................................. 16

First Fit ............................................................................................................................................... 16

Best Fit ............................................................................................................................................... 16

Worst Fit ............................................................................................................................................ 17

Gerenciamento de Memória O gerenciamento d e memória no MINIX 3 é simples, não faz uso de recursos de swapping nem

paginação; e faz uso de lista ligada para o gerenciamento de lacunas na memória.

A alocação de memória ocorre apenas em dois momentos:

• Execução de fork()

Faz uma cópia do processo que chama esta system call em uma das lacunas

disponíveis. Para isto, chama a função de alocação de memória.

• Execução de exec()

Substitui a imagem de um processo por outra imagem. Devido à diferença de tamanho

entre as imagens, a imagem atual é retirada da memória e então uma nova parcela de

memória é alocada para a nova imagem.

Struct holes

A struct que representa uma lacuna (hole) tem seu código representado abaixo:

struct hole{ struct hole *h_next; phys_clicks h_base; phys_clicks h_len;

} hole[NR_HOLES];

A lista ligada é composta por structs

“hole” nas quais os atributos são:

• h_next:

Ponteiro para o próximo struct

hole da lista

• h_base:

O valor da base da lacuna;

• h_len:

Tamanho do bloco de lacuna;

Os algoritmos de alocação de

processos acessam esta lista para

localizar a lacuna no qual o bloco

requisitado será alocado, baseado no

tamanho requisitado e no nas lógicas

aplicadas. No caso do MINIX 3 o

algoritmo utilizado é o FIRST FIT, no qual a lista de lacunas é varrida até que o primeiro bloco

em que o tamanho requisitado couber será aquele escolhido.

Código da alloc_mem

Arquivo consultado: /usr/src/servers/pm/alloc.c

A função alloc_mem(clicks) é responsável pela execução do algoritmo de alocação de memórias, de acordo com o tamanho requisitado (parâmetro clicks)

/*================================================= ==========================* * alloc_mem * *================================================= ==========================*/ PUBLIC phys_clicks alloc_mem(clicks) phys_clicks clicks; /* amount of memory requested */ { /* Allocate a block of memory from the free list us ing first fit. The block * consists of a sequence of contiguous bytes, whos e length in clicks is * given by 'clicks'. A pointer to the block is re turned. The block is * always on a click boundary. This procedure is c alled when memory is * needed for FORK or EXEC. Swap other processes o ut if needed. */ register struct hole *hp, *prev_ptr; phys_clicks old_base; do { prev_ptr = NIL_HOLE; hp = hole_head; while (hp != NIL_HOLE && hp->h_base < swap_base) { if (hp->h_len >= clicks) { /* We found a hole that is big enough. Use it. */ old_base = hp->h_base; /* remember where it star ted */ hp->h_base += clicks; /* bite a piece off */ hp->h_len -= clicks; /* ditto */ /* Remember new high watermark of used memory. * / if(hp->h_base > high_watermark) high_watermark = hp->h_base; /* Delete the hole if used up completely. */ if (hp->h_len == 0) del_slot(prev_ptr, hp); /* Return the start address of the acquired bloc k. */ return(old_base); } prev_ptr = hp; hp = hp->h_next; } } while (swap_out()); /* try to swap some other process out */ return(NO_MEM); }

Liberação de memória

A função free_mem(base, clicks) basicamente insere a informação da nova lacuna

correspondente ao bloco liberado na lista de lacunas.

/*================================================= ==========================* * free_mem * *================================================= ==========================*/ PUBLIC void free_mem(base, clicks) phys_clicks base; /* base address of block to free */ phys_clicks clicks; /* number of clicks to free */ { /* Return a block of free memory to the hole list. The parameters tell where * the block starts in physical memory and how big it is. The block is added * to the hole list. If it is contiguous with an e xisting hole on either end, * it is merged with the hole or holes. */ register struct hole *hp, *new_ptr, *prev_ptr; if (clicks == 0) return; if ( (new_ptr = free_slots) == NIL_HOLE) panic(__FILE__,"hole table full", NO_NUM); new_ptr->h_base = base; new_ptr->h_len = clicks; free_slots = new_ptr->h_next; hp = hole_head; /* If this block's address is numerically less th an the lowest hole currently * available, or if no holes are currently availa ble, put this hole on the * front of the hole list. */ if (hp == NIL_HOLE || base <= hp->h_base) { /* Block to be freed goes on front of the hole lis t. */ new_ptr->h_next = hp; hole_head = new_ptr; merge(new_ptr); return; } /* Block to be returned does not go on front of h ole list. */ prev_ptr = NIL_HOLE; while (hp != NIL_HOLE && base > hp->h_base) { prev_ptr = hp; hp = hp->h_next; } /* We found where it goes. Insert block after 'p rev_ptr'. */ new_ptr->h_next = prev_ptr->h_next; prev_ptr->h_next = new_ptr; merge(prev_ptr); /* sequence is 'prev_ptr', 'new _ptr', 'hp' */ }

Tarefa: “Alterar o minix para que ao se teclar F8 ele apresente todas as posições da lacunas

(relacione com segmentos e clicks)”

Ao teclar F8: How To Para que o Minix execute uma função ao se apertar uma tecla é necessário editar 2 arquivos

em /usr/src/servers/is, que são dmp.c e proto.h.

Dmp.c

struct hook_entry {

int key;

void (*function)(void);

char *name;

} hooks[NHOOKS] = {

{ F1, proctab_dmp, "Kernel process table" },

{ F2, memmap_dmp, "Process memory maps" },

(...)

{ F8, memoryholes_dmp, "Show holes" },

{ F9, sched_dmp, "Scheduling queues" },

{ F10, kenv_dmp, "Kernel parameters" },

{ F11, timing_dmp, "Timing details (if enabled)" },

{ SF1, mproc_dmp, "Process manager process table" },

(...)

};

Proto.h

Enquanto isso, em proto.h, declaramos o cabeçalho da nossa função que será chamada ao

clicarmos em F8: memoryholes_dmp.

Tarefa

Pronto! Agora basta termos função memoryholes_dmp, que foi posta por nós em dmp_pc.c:

_PROTOTYPE( void mproc_dmp, (void));

_PROTOTYPE( void sigaction_dmp, (void));

_PROTOTYPE( void holes_dmp, (void));

_PROTOTYPE( void memoryholes_dmp, (void));

PUBLIC void memoryholes_dmp(void) {

static struct pm_mem_info pmi;

int h;

if(getsysinfo(PM_PROC_NR, SI_MEM_ALLOC, &pmi) != O K) {

printf(“Falha ao obter a lista de lacunas.\n ");

return; }

printf("Lista de lacunas:\n");

printf("\n|endereco fisico | tamanho da lacuna em bytes | tamanho da lacuna em clicks|\n");

for(h = 0; h < _NR_HOLES; h++) {

if(pmi.pmi_holes[h].h_base && pmi.pmi _holes[h].h_len) {

int bytes;

bytes = (pmi.pmi_holes[h]. h_len << CLICK_SHIFT);

printf("|%lx |%6d k B |%6d clicks |\n", pmi.pmi_holes[h].h_base ,

bytes / 1024, pmi.pmi_ holes[h].h_len); }

}

return;

}

Primeiramente vemos a estrutura declarada em

static struct pm_mem_info pmi;

Uma estrutura pm_mem_info contém o vetor de lacunas da memória, e podemos referenciar

cada lacuna por pmi.pmi_holes[indice].

Assim, o que o programa faz é obter todas as informações da estrutura por

getsysinfo(PM_PROC_NR, SI_MEM_ALLOC, &pmi)

e percorrer o vetor de lacunas imprimindo o atributo de tamanho da estrutura da lacuna:

h_len. Imprimimos o valor em clicks (a memória no MINIX é medida por clicks, sendo que cada

click tem 4096 bytes). Para transformar os clicks em bytes deslocamos 12 vezes (o valor de

CLICK_SHIFT) o numero de clicks. Assim estaremos multiplicando o numero de clicks por 2¹²

(4096).

O resultado obtido foi o seguinte:

Relacionando com segmentos

Segmentos no MINIX

Um segmento, em termos de sistemas operacionais, é cada uma das 3 partes em que um

programa é dividido: texto, dados e pilha. O segmento de texto é o código em si do programa e

pode ser dividido entre vários processos que sejam iguais. Neste caso cada processo terá seu

valor de PC nesse código armazenado na tabela de processos e também seu próprio espaço de

dados e de pilha. O sistema operacional verifica, ao terminar e iniciar a desalocação de

memória de texto desse tipo de programa, se não é nenhum outro programa utilizando o

segmento de código que será desalocado.

Quando o processo é alocado desta maneira fica um espaço entre o segmento de dados e de

pilha para que eles cresçam. Esse espaço não é considerado uma lacuna no MINIX 3.

Dado que havíamos impresso a tabela de lacunas da memória, precisaríamos das tabelas de

alocação de processos e segmentos para poder relacioná-los. Assim, descobrimos que ao

apertar F2 chamávamos a função memmap_dmp, que traz uma listagem dos processos que

estavam na memória com os detalhes da alocação.

Para entender esse dump precisamos entender primeiro como é a implementação de

segmentos por software:

Na função memmap_dmp há a declaração de uma estrutura proc. Uma estrutura proc, dentre

outras informações a cerca do processo, possui um vetor de 3 (NR_LOCAL_SEGS) posições

contendo uma estrutura de dados de mem_map chamado p_memmap. Uma estrutura

mem_map é formada de 3 parâmetros: endereço físico do segmento, endereço virtual do

segmento e tamanho desse segmento.Destes, o que mais nos interessa é o endereço virtual do

segmento, já que com esse dado e com a tabela de lacunas poderíamos fazer um mapa da

memória.

O resultado desse dump é o que segue:

E um caso interessante é visto abaixo:

Os processos de tcpd dividem o mesmo espaço de texto e possuem cada um seu espaço de

pilha e de dados. A mesma coisa ocorre com os processos de getty.

Mapa da memória

Com esses dados e a tabela de lacunas foi possível fazer o seguinte mapa da memória:

As setas indicam os processos que dividem código e possuem cada um seu espaço de dados e

pilha. Os espaços pretos são discrepâncias que encontramos nos dumps. O primeiro é uma

lacuna não identificada na tabela de lacunas, mas que não aparenta ter nenhum processo

alocado segundo a tabela de dump de processos. O segundo é um espaço que, segundo a

tabela de lacunas, possui um processo, mas que não conseguimos identificar na tabela de

dump de processos. Esses últimos resultados são esperados, já que, mesmo que uma função

chamada por uma tecla não seja um processo no MINIX, (essas tabelas já ficam armazenadas

para que quando se apertar a tecla de atalho ela seja apenas impressa), os dois dumps são

retratos de instantes distintos da memória, então possivelmente teria discrepâncias.

Tarefa:O minix implementa o "first fit" ao procurar um local vago na memória. Altere o minix

de forma que ele implemente o "best fit".

Algoritmos de Busca e Alocação

Conceitos

O algoritmo de busca por lacunas na memória fica localizado dentro da função alloc_mem, que

é executada quando o sistema precisa de memória ao fazer as chamadas de sistema FORK e

EXEC

O arquivo modificado /usr/src/servers/pm/alloc.c

00064 PUBLIC phys_clicks alloc_mem(clicks) 00065 phys_clicks clicks; /* amount of memory requested */ 00066 { 00073 register struct hole *hp, *prev_ptr; 00074 phys_clicks old_base; 00075 00076 do { (ALGORITMO DE BUSCA E ALOCAÇÃO) 00100 } while (swap_out()); /* try to swap some other process out */ 00101 return(NO_MEM); 00102 }

Podemos ver que o laço principal chama a função swap_out(). O seu objetivo é procurar

processos que podem se colocados na memória, especialmente processos que estão

bloqueados.

O espaço omitido no código acima é onde deve ficar o algoritmo de busca de lacunas e

alocação dos processos, que nativamente foi implementado com o algoritmo First Fit e que

agora devemos alterá-lo para o Best Fit. A definição desses dos dois algoritmos está adiante:

� First Fit – percorre a lista de segmentos até encontrar a primeira lacuna que seja grande o suficiente

� Best Fit - percorre a lista inteira e pega a menor lacuna que seja adequada. Ele tenta encontrar uma lacuna cujo tamanho seja próximo ao realmente necessário.

Sendo assim, dada a lista ligada de lacunas abaixo e uma solicitação de um bloco e tamanho 2

clicks,teremos para os dois algoritmos o seguinte resultado

Podemos assim intuir que o novo algoritmo que será implementado deverá ser mais eficiente,

pois sempre usará a lacuna que melhor lhe servir. Mas na pratica vemos que essa intuição não

podia estar mais errada pois, excluindo os casos em que o tamanho do bloco requisitado tem

exatamente o tamanho da lacuna encontrada ,o que é muito raro de acontecer - , a memória

fica fragmentada em lacunas bem menores e bom mais difíceis de achar um processo que

caiba nelas. Além de consumir um maior tempo de CPU – pois o algoritmo deve percorrer a

lista toda atrás do melhor candidato.

Implementação

É mostrada a seguir a implementação original da função de busca de lacuna com o algoritmo o

First-Fit e logo depois a implementação do algoritmo subtituto

Tabela 1- Implementação do First Fit

00077 prev_ptr = NIL_HOLE; 00078 hp = hole_head; 00079 while (hp != NIL_HOLE && hp->h_base < swap_base) { 00080 if (hp->h_len >= clicks) { 00081 /* We found a hole that is big enough. Use it. */ 00082 old_base = hp->h_base; /* remember where it started */ 00083 hp->h_base += clicks; /* bite a piece off */ 00084 hp->h_len -= clicks; /* ditto */ 00085 00086 /* Remember new high watermark of used memory. */ 00087 if(hp->h_base > high_watermark) 00088 high_watermark = hp->h_base; 00089 00090 /* Delete the hole if used up completely. */ 00091 if (hp->h_len == 0) del_slot(prev_ptr, hp);

00092 00093 /* Return the start address of the acquired block. */ 00094 return(old_base); 00095 } 00096 00097 prev_ptr = hp; 00098 hp = hp->h_next; 00099 }

Tabela 2- Implementação do Best Fit

prev_ptr = NIL_HOLE; best_hp = NIL_HOLE; prev_best = NIL_HOLE; hp = hole_head; while (hp != NIL_HOLE && hp->h_base < swap_base) { /* enquanto existir uma lacuna e o comeco das lacunas nao ultrapassarem swap_base: */ /* percorre a lista toda em busca da melhor lacuna */ if (hp->h_len >= clicks) /*a lacuna possui o comprimento minimo*/ if(best_hp == NIL_HOLE || (hp->h_len < best_hp->h_len)){ /*caso ainda não tenhamos um candidato, atualiza */ /*OU se já tivermos um canditato porém pior do que a lacuna analisada*/ prev_best = prev_ptr; best_hp = hp; } prev_ptr = hp; hp = hp->h_next; } /* uma vez percorrida a lista em busca da melhor lacuna, atualiza a lista e retorna o endereço*/ if(best_hp != NIL_HOLE){ /* We found a hole that is good enough. Use it. */ old_base = best_hp->h_base; /* remember where it started */ best_hp->h_base += clicks; /* bite a piece off */ best_hp->h_len -= clicks; /* ditto */ /* Remember new high watermark of used memory. */ if(best_hp->h_base > high_watermark) high_watermark = best_hp->h_base; /* Delete the hole if used up completely. */ if (best_hp->h_len == 0) del_ slot(prev_best, best_hp); /* Return the start address of the acquired block. */ return(old_base); }

Resultados

Utilizando a função implementada na tarefa anterior, podemos observar os resultados da

fragmentação da memória de cada um dos algoritmos utilizados. Para tanto tivemos que

assegurar que os testes seriam realizados em iguais condições para obtermos resultados

consistentes, de modo que todas as mesmas chamadas de alocação de memória deveriam ser

executadas nos dois casos.

Após a troca de algoritmos e a recompilação do gerenciador de processos que é o responsável

pela função mem_alloc, temos os seguintes dados obtidos após o reboot da máquina;

First Fit

Podemos que ver a fragmentação da memória ( abaixo são listas as lacunas da lista ligada de

lacunas do sistema) se apresenta em níveis aceitáveis, além de ser a implementação mais

simples e que apresenta melhor desempenho em sua execução.

Best Fit

Aqui podemos observar que os números de fragmentos ficaram bem reduzidos em relação ao

First Fit, pois não conseguimos produzir a intensa fragmentação da memória apenas com os

nossos processos rodando.

Worst Fit

O algoritmo do Worst Fit não foi pedido na tarefa mas como a implementação era bem

simples pois derivava do Best-Fit – apenas alterando o sinal da comparação para pegar sempre

a maior lacuna disponível, concebida na tentativa de evitar a intensa fragmentação do Best Fit

– achamos interessante incluí-lo no relatório apenas como uma curiosidade.