Gerenciamento de Área de Alocação Dinâmica (Listas Encadeadas)
Publicado por Danilo Azevedo (última atualização em 23/07/2014)
[ Hits: 2.980 ]
Download gereciador_de_memoria.zip
Implementação de um sistema de gerenciamento de trechos livres e ocupados de uma área de alocação dinâmica de memória.
A área de alocação será chamada de buffer. O buffer será formado por N slots. Cada slot tem um índice, que varia de 0 a N - 1. Inicialmente o buffer será considerado vazio. O programa receberá solicitações de operações sobre o buffer, como solicitações para alocar um conjunto de slots (contíguos), desalocar os slots alocados em uma solicitação o anterior ou solicitar informações sobre área de alocação. O índice do slot onde uma área alocada ou livre inicia será chamado o índice inicial daquela área.
O tamanho N do buffer (numero de slots) deverá ser uma constante no programa. Inicialmente deve-se atribuir o valor 20 a esta constante. Posteriormente, no entanto, o valor desta constante poderá ser alterado.
Para a implementação deste exercício, deve-se utilizar listas implementadas com apontadores.
Os formatos de entrada e saída do programa estão indicados nas seções a seguir. O programa deve ler da entrada padrão e escrever na saída padrão.
Segue no anexo informações de como usar o código e o programa.
/* UNIVERSIDADE FEDERAL DA BAHIA CURSO: BACHARELADO EM CIENCIA DA COMPUTACAO DISCIPLINA: ESTRUTURA DE DADOS E ALGORITMOS ALUNO: DANILO AZEVEDO SANTOS - MATRICULA:209200256 */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> //#include <conio.h> typedef struct blocoLista{ int id; int inicio; int tamanho; //char id2; struct blocoLista *prox, *ant; }blocoLista, *Lista; typedef struct identificador{ int chave; struct identificador *prox; }identificador, *ListaInt; #define MAX 20 #define vazio -1 /* DECLARACOES DE FUNCOES */ bool consultaListaId(ListaInt *i, int x); bool criaLista(ListaInt *i, int x); bool iniciarListas(ListaInt *i, Lista *l); bool insere_Lista(Lista *l, int id, int tamanho); Lista areasLivre(Lista *l); Lista areasOcupadas(Lista *l); Lista buscaBloco(Lista *l, int id); Lista consultaBestFit(Lista *l, int tam); Lista consultaFirstFit(Lista *l, int tam); Lista consultaLista(Lista *l, int id); Lista consultaWorstFit(Lista *l, int tam); Lista defragmentacao(Lista *l); Lista retirar_lista(Lista *l, int x); bool retira_desalocacao(Lista *l, int id); int verEspaco(Lista *l); void corrigirPosicao(Lista *l); void experimento(Lista *l, ListaInt *i, int num); void inicializar(Lista *l); Lista funcao_teste(Lista *l); /* */ int main (){ int i, j, tam_entrada, id, tam; char operacao, id_aloc[30], tam_aloc[5], id_area, entrada[30]; Lista lista, aux; ListaInt listaint; iniciarListas(&listaint,&lista); inicializar(&lista); while(1){ //LOOP DO ESCOPO DE REPETICAO P/ SAIR ENTRE 'e' aux=NULL; fflush(stdin); gets(entrada); operacao = entrada[0];//IDENTIFICADOR DE OPERACAO {//if's if(operacao == 'a'){ // VERIFICANDO O TIPO DE ENTRADA id = 0; tam = 0; i = 2; j = 0; while(entrada[i] != ' '){// EXTRAINDO O IDENTIFICADOR DE ALOCACAO id_aloc[j] = entrada[i]; i++; j++; } id_aloc[j]='{FONTE}'; id = atoi(id_aloc); //CONVERTE ID_ALOC DE CHAR PARA INTEIRO i = strlen(id_aloc) + 3; // TAMANHO DO IDENTIFICADOR DE ALOCACAO + 2 + 1 - PELO ESPACO j = 0; while(entrada[i] != ' '){//EXTRAINDO O TAMANHO DA ALOCACAO tam_aloc[j] = entrada[i]; i++; j++; } tam_aloc[j] ='{FONTE}'; tam = atoi(tam_aloc); tam_entrada = strlen(entrada); id_area = entrada[tam_entrada+vazio]; }//FIM 'a' if(operacao == 'c'){ i = 2; j = 0; while(entrada[i]!= '{FONTE}'){ id_aloc[j] =entrada[i]; j++; i++; } id_aloc[j] = '{FONTE}'; id=atoi(id_aloc); }//FIM 'c' if(operacao == 'f'){ i = 2; j = 0; while(entrada[i]!= '{FONTE}'){ id_aloc[j] = entrada[i]; j++; i++; } id = atoi(id_aloc); }//FIM 'f' if(operacao == 'x'){ i = 2; j = 0; while(entrada[i]!= '{FONTE}'){ id_aloc[j] =entrada[i]; j++; i++; } id = atoi(id_aloc); }//FIM 'x' } switch (operacao){ case 'a':{ if((consultaListaId(&listaint,id))||((verEspaco(&lista)) == MAX)||(tam > (MAX -(verEspaco(&lista)))) || (id < 0 || tam < 0)) printf("nao foi possivel alocar %d\n",id); else{ switch (id_area){ case 'b': aux = consultaBestFit(&lista,tam); insere_Lista(&aux,id,tam); criaLista(&listaint,id); break; case 'f': aux = consultaFirstFit(&lista,tam); insere_Lista(&aux,id,tam); criaLista(&listaint,id); break; case 'w': aux = consultaWorstFit(&lista,tam); insere_Lista(&aux,id,tam); criaLista(&listaint,id); break; default: printf("nao foi possivel alocar %d\n",id); break; } } } break; case 'c': buscaBloco(&lista,id); break; case 'd': defragmentacao(&lista); corrigirPosicao(&lista); break; case 'e':exit(0); case 'f': if(!consultaListaId(&listaint,id)) printf("\n"); else retira_desalocacao(&lista,id); break; case 'l':areasLivre(&lista); break; case 'o':areasOcupadas(&lista); break; case 'x': experimento(&lista,&listaint,id); break; // case 'q':funcao_teste(&lista);// USADO SOMENTE PARA TESTE DE CONSTRUCAO DO PROGRAMA break; default: break; } } return 0; } bool iniciarListas(ListaInt *i, Lista *l){ // INICIALIZAR LISTAS PARA FUNCAO "MAIN" (*l) = NULL; (*i) = NULL; return true; } bool insere_Lista(Lista *l, int id, int tamanho){ //INSERE SOLICITACAO DE ALOCACAO blocoLista *p; Lista aux=NULL; if((*l)->tamanho >= tamanho){ if(tamanho == (*l)->tamanho){ (*l)->id = id; return true; } else{ p = (blocoLista*)malloc(sizeof(blocoLista)); if (!p){ printf("nao foi possivel alocar %d",id); return false; } aux = (*l); aux -> inicio = aux->inicio; aux->id = id; p->tamanho = aux->tamanho - tamanho; aux->tamanho = tamanho; p->prox = aux->prox; aux->prox = p; p->ant = aux; p->id = vazio; p->inicio = p->ant->tamanho + p->ant->inicio; return true; } } return true; } Lista areasLivre(Lista *l){ Lista p; for(p=(*l); p!=NULL; p=p->prox){ if(p->id == vazio ){ printf("%d %d",p->inicio,p->tamanho); printf("\n"); } } return NULL; } Lista areasOcupadas(Lista *l){ Lista p; for(p=(*l); p!=NULL; p=p->prox){ if(p->id != vazio ){ printf("%d %d",p->inicio,p->tamanho); printf("\n"); } } return NULL; } Lista buscaBloco(Lista *l, int id){//CONSULTA PARA IDENTIFICACAO DO BLOCO Lista p=NULL; for(p=(*l);p->prox!=NULL; p=p->prox){ if(id == p->id){ printf("%d\n",p->inicio); return p; } } if((p->prox == NULL)&&(id != p->id)) printf("requisicao nao atendida"); return p; } Lista consultaLista(Lista *l, int id){ Lista p; for(p=(*l);(p)&&(p->id != id); p=p->prox); return p; } Lista consultaBestFit(Lista *l, int tam){ //BUSCA BLOCO COM MENOR TAMANHO Lista p, aux=NULL; int soma = 0, menor = (MAX+1); //se for vazio for(p=(*l); p!=NULL; p = p->prox){ soma = soma + p->tamanho; if(p->id == vazio){ if((p->tamanho < menor)&&(p->tamanho >= tam)){ menor = p->tamanho; aux = p; } } } if(soma == MAX) return aux; return NULL; } Lista consultaFirstFit(Lista *l, int tam){//BUSCA BLOCO COM MENOR INDICE Lista p = NULL, aux; int soma = 0, menor = MAX+1; // vazio for(p=(*l); p!=NULL; p = p->prox){ soma = soma + p->tamanho; if(p->id == vazio){ if(p->tamanho >= tam){ if(p->inicio < menor){ menor = p->inicio; aux = p; } } } } if(soma == MAX) return aux; return NULL; } Lista consultaWorstFit(Lista *l, int tam){ // BUSCA BLOCO COM MAIOR TAMANHO Lista p, aux; int soma = 0, maior = 0; //se for vazio for(p=(*l); p!=NULL; p = p->prox){ soma = soma + p->tamanho; if(p->id == vazio){ if(p->tamanho > maior){ if(p->tamanho >= tam){ maior = p->tamanho; aux = p; } } } } if(soma == MAX) return aux; return NULL; } int verEspaco(Lista *l){//VERIFICA TAMANHO DE ESPACOS OCUPADOS/LIVRES Lista p; int soma = 0; for(p=(*l);p!=NULL; p=p->prox){ if(p->id !=vazio) soma += p->tamanho; } return soma; } void inicializar(Lista *l){ //INICIALIZAR BLOCO DE ALOCACAO JÁ PREENCHIDO blocoLista *p; p = (blocoLista*)malloc(sizeof(blocoLista)); p->prox = *l; p->ant = NULL; p->id = vazio; p->inicio = 0; p->tamanho = MAX; (*l) = p; } bool retira_desalocacao(Lista *l, int id){ // FUNCAO PARA DESALOCACAO Lista p, aux; p = consultaLista(&(*l),id); p->id = vazio; if(p->prox->id == vazio){// verificação de blocos adjacentes depois do **prox p->tamanho = p->prox->tamanho + p->tamanho; aux = p->prox; p->prox = aux->prox; if(aux->prox != NULL) aux->prox->ant = p; free(aux); return (*l); } if(p->ant){ if(p->ant->id == vazio){ // verificação de blocos adjacentes antes do **ant p->tamanho = p->ant->tamanho + p->tamanho; if(p->inicio > p->ant->inicio) p-> inicio = p->ant->inicio; aux = p->ant; p->ant = aux->ant; aux->ant->prox = p; free(aux); return (*l); } } return (*l); } // FUNCOES PARA DEFRAGMENTACAO Lista retirar_lista(Lista *l, int x){ Lista p, aux; p = consultaLista(&(*l),x); if(p->prox == NULL){ if(p->ant == NULL){ (*l) = p->prox; free(p); return (*l); } aux = p->ant; aux->prox = p->prox; free(p); return (*l); } if(p->ant == NULL){ (*l) = p->prox; p->prox->ant = NULL; free(p); return (*l); } else{ aux = p->ant; aux->prox = p->prox; p->prox->ant = aux; free(p); return (*l); } return (*l); } Lista defragmentacao(Lista *l){ blocoLista *p; Lista aux, aux2 = *l; int soma = 0; p = (blocoLista*)malloc(sizeof(blocoLista)); for(aux=(*l);(aux); aux = aux->prox){//REALIZANDO A SOMA DO TAMANHO DE ESPACOS VAZIOS if(aux->id == vazio){ soma += aux->tamanho; } } for(aux=(*l);(aux); aux = aux->prox){// DELETANDO ESPAÇOS VAZIOS if(aux->id == vazio){ retirar_lista(&(*l),aux->id); } } while(aux2->prox!=NULL){ aux2=aux2->prox; } // CONSTRUINDO UM NOVO ESPACO VAZIO p->tamanho = soma; p->inicio = 0; // INDICE TEMPORARIO p->prox = aux2->prox; p->ant = aux2; p->id = vazio; aux2->prox = p; return p; } void corrigirPosicao(Lista *l){ Lista aux; for(aux=(*l); aux!=NULL; aux = aux->prox){// CORRIGINDO POSICOES if(aux->ant == NULL){ aux->inicio = 0; } else{ aux->inicio = (aux->ant->inicio + aux->ant->tamanho); } } } void experimento(Lista *l, ListaInt *k, int num){ int i, j, tam_entrada, id, tam, cont = 0; char operacao, id_aloc[30], tam_aloc[5], id_area, entrada[30]; Lista lista=(*l), aux, p; ListaInt listaint = (*k); int a=0, b=0, c=0, d=0, soma=0; float media = 0; while( cont < num){ fflush(stdin);gets(entrada); operacao = entrada[0]; if(operacao == 'a'){ id = 0; tam = 0; i = 2; j = 0; while(entrada[i] != ' '){ id_aloc[j] = entrada[i]; i++; j++; } id_aloc[j]='{FONTE}'; id = atoi(id_aloc); i = strlen(id_aloc) + 3; j = 0; while(entrada[i] != ' '){ tam_aloc[j] = entrada[i]; i++; j++; } tam_aloc[j] ='{FONTE}'; tam = atoi(tam_aloc); tam_entrada = strlen(entrada); id_area = entrada[tam_entrada+vazio]; } if(operacao == 'f'){ i = 2; j = 0; while(entrada[i]!= '{FONTE}'){ id_aloc[j] = entrada[i]; j++; i++; } id = atoi(id_aloc); }//FIM 'f' switch (operacao){ case 'a':{ if((consultaListaId(&listaint,id))||((verEspaco(&lista)) == MAX)||(tam > (MAX -(verEspaco(&lista)))) || (id < 0 || tam < 0)){ b++; } else{ switch (id_area){ case 'b': aux = consultaBestFit(&lista,tam); insere_Lista(&aux,id,tam); criaLista(&listaint,id); a++; break; case 'f': aux = consultaFirstFit(&lista,tam); insere_Lista(&aux,id,tam); criaLista(&listaint,id); a++; break; case 'w': aux = consultaWorstFit(&lista,tam); insere_Lista(&aux,id,tam); criaLista(&listaint,id); a++; break; default: b++; break; } } } break; case 'f':if(!consultaLista(&lista,id)) b++; else retira_desalocacao(&lista,id); a++; break; default: b++; break; } cont++; } for(p=(*l); p!=NULL; p=p->prox){// areas livres if(p->id == vazio ){ soma = soma + p->tamanho; c++; } if(p->id != vazio ){ d++; } } media = soma/c; printf("numero total de solicitacoes: %d\n",num); printf("numero de solicitacoes atendidas: %d\n",a); printf("numero de slots ocupados: %d\n",d); printf("numero total de slots livres: %d\n",c); printf("media do numero de slots nas areas livres: %.1f\n",media); } // // LISTA AUXILIAR PARA GUARDAR OS IDENTIFICADORES bool criaLista(ListaInt *i, int x){ identificador *p; p = (identificador*)malloc(sizeof(identificador)); if(!p){ //printf("nao foi possivel alocar %d",x); return false; } p->prox = *i; *i = p; p->chave = x; return true; } bool consultaListaId(ListaInt *i, int x){ ListaInt p; for(p=(*i); p!=NULL; p = p->prox){ if(p->chave == x){ return true; } } return false; } // Lista funcao_teste(Lista *l){//CONSULTA PARA IDENTIFICACAO DO BLOCO Lista p; for(p=(*l); p!=NULL; p = p->prox){ printf("%d\n",p->inicio); } return p; }
Manipulação de um vetor de registros
[GAME-2] Acerte os rortões nas janelas (jogo com gráficos)
Nenhum comentário foi encontrado.
Passkeys: A Evolução da Autenticação Digital
Instalação de distro Linux em computadores, netbooks, etc, em rede com o Clonezilla
Título: Descobrindo o IP externo da VPN no Linux
Armazenando a senha de sua carteira Bitcoin de forma segura no Linux
Enviar mensagem ao usuário trabalhando com as opções do php.ini
Instalando Brave Browser no Linux Mint 22
vídeo pra quem quer saber como funciona Proteção de Memória:
Encontre seus arquivos facilmente com o Drill
Mouse Logitech MX Ergo Advanced Wireless Trackball no Linux
Compartilhamento de Rede com samba em modo Público/Anônimo de forma simples, rápido e fácil
Como abrir o pycharm no linux (2)
VMs e Interfaces de Rede desapareceram (12)