Gerenciamento de Área de Alocação Dinâmica (Listas Encadeadas)
Publicado por Danilo Azevedo (última atualização em 23/07/2014)
[ Hits: 2.939 ]
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; }
Dangerous Tux Game com gráficos
Classe para manipulação e conversão de datas para std::string em C++
Rotação à esquerda árvore Binária
Nenhum comentário foi encontrado.
Enviar mensagem ao usuário trabalhando com as opções do php.ini
Meu Fork do Plugin de Integração do CVS para o KDevelop
Compartilhando a tela do Computador no Celular via Deskreen
Como Configurar um Túnel SSH Reverso para Acessar Sua Máquina Local a Partir de uma Máquina Remota
Configuração para desligamento automatizado de Computadores em um Ambiente Comercial
Compartilhamento de Rede com samba em modo Público/Anônimo de forma simples, rápido e fácil
Cups: Mapear/listar todas as impressoras de outro Servidor CUPS de forma rápida e fácil
Criando uma VPC na AWS via CLI
Tem como instalar o gerenciador AMD Adrenalin no Ubuntu 24.04? (16)
Arch Linux - Guia para Iniciantes (2)
Problemas ao instalar o PHP (11)
Tenho dois Link's ( IP VÁLIDOS ), estou tentando fazer o failover... (0)