Gerenciamento de Área de Alocação Dinâmica (Listas Encadeadas)

Publicado por Danilo Azevedo (última atualização em 23/07/2014)

[ Hits: 2.397 ]

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.

  



Esconder código-fonte

/* 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;
        }

Scripts recomendados

AIMG-mostrar imagem fraquimentada em pontos aleatórios

Simulador de Escalonamento de Processos

livraria

Biblioteca dos.h

Combustivel


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts