memory manage.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <time.h>

#define ret printf("\n")
#define spa printf(" ")
#define hli printf("-")
#define vli printf("    |")
#define tab printf("\t")

void _sleep (int n) {
    clock_t goal;
    goal = (clock_t) n * CLOCKS_PER_SEC + clock();
    while (goal > clock());
}

char _keygo () {
    char c;
    printf("Press any key to continue.....\n");
    c = getchar();
    return c;
}

const int capacity = 1024;      // K
const int max = 100;        // max length of array

typedef struct job JOB;
struct job {
    int jobid;
    char name[10];
    int vol;        // memory size
};

const int jobsum = 8;       // total number of job

JOB jobdata[jobsum] = {
    {8100, "System", 50},
    {8101, "TTMusic", 32},
    {8102, "Thunder", 128},
    {8103, "Kingsoft", 76},
    {8104, "Nortun", 86},
    {10001, "QQ", 168},
    {10002, "eMule", 98},
    {10003, "Word", 43}
};

typedef struct  memblock MEM;
struct  memblock
{
    int head;
    int length;
    int state;
    int jobid;
};

MEM memdata[max] = {
    {0, 50, 1, 8100},
    {50, 50, 0, 0},
    {100, 32, 1, 8101},
    {132, 128, 1, 8102},
    {260, 100, 0, 0},
    {360, 76, 1, 8103},
    {436, 200, 0, 0},
    {636, 88, 1, 8104},
    {724, 0, 0, 0},
};

int memsum = 9;
int curp = 4;

MEM membackup[9] = {
    {0, 50, 1, 8100},
    {50, 50, 0, 0},
    {100, 32, 1, 8101},
    {132, 128, 1, 8102},
    {260, 100, 0, 0},
    {360, 76, 1, 8103},
    {436, 200, 0, 0},
    {636, 88, 1, 8104},
    {724, 0, 0, 0},
};

void mem_insert (int k, MEM mem) {
    int i;
    if (memsum >= max) {
        printf("No enough memory!");
        return;
    }
    for (i=memsum;i>=k;--i) {
        memdata[i+1] = memdata[i];
    }
    memsum = memsum + 1;
    memdata[k].head = mem.head;
    memdata[k].length = mem.length;
    memdata[k].state = mem.state;
    memdata[k].jobid = mem.jobid;
}

void mem_remove(int k) {
    int i;
    for (i=k;i<memsum;i++){
        memdata[i] = memdata[i+1];
    }
    memsum = memsum - 1;
}

int job_locate (int id) {
    int i;
    for (i=0;i<jobsum;i++) {
        if (id == jobdata[i].jobid) {
            return i;
        }
    }
    return -1;
}

void mem_state () {
    int i, j, k;
    for (i=0; i<memsum; i++) {
        tab;
        printf("%4ik", memdata[i].head);
        for (j=0;j<20;j++)
            hli;
        ret;
        tab;
        vli;
        for (j=0;j<5;j++)
            spa;
        if (memdata[i].jobid == 0) {
            printf("%10s", "$NONE$");
        }
        else {
            k = job_locate (memdata[i].jobid);
            printf("%10s", jobdata[k].name);
        }
        vli;
        ret;
    }
    printf("\t1024K");
    for (j=0;j<20;j++)
        hli;
    ret;
}

int mem_allocate_ff (int k) {
    int i;
    for (i=0;i<memsum;i++) {
        if (memdata[i].state == 0 && jobdata[k].vol < memdata[i].length) {
            return i;
        }
    }
    return -1;
}

int mem_allocate_cf (int k) {
    int i, idx;
    for (i=curp;i<curp+memsum;i++) {
        idx = i % memsum;
        if (memdata[idx].state == 0 && jobdata[k].vol < memdata[idx].length) {
            curp = idx;
            return idx;
        }
    }
    return -1;
}

int mem_allocate_bf (int k) {
    int i, j, min, temp;
    int idx[jobsum];
    int prev = -1;
    for (i=0;i<jobsum;i++) {
        idx[i] = i;
    }
    for (i=0;i<jobsum;++i) {
        for (j=i;j<jobsum;++j) {
            if (memdata[idx[i]].length < memdata[idx[j]].length) {
                temp = idx[j];
                idx[j] = idx[i];
                idx[i] = temp;
            }
        }
    }
    for (i=0;i<jobsum;i++) {
        if (memdata[idx[i]].state == 0 && jobdata[k].vol < memdata[idx[i]].length) {
            prev = idx[i];
        }
    }
    return prev;
}

void mem_allocate (int i, int j) {
    MEM left_mem;
    left_mem.head = memdata[j].head + jobdata[i].vol;
    left_mem.length = memdata[j].length - jobdata[i].vol;
    left_mem.state = 0;
    left_mem.jobid = 0;
    memdata[j].length  = memdata[j].length;
    memdata[j].state = 1;
    memdata[j].jobid = jobdata[i].jobid;
    mem_insert(j+1, left_mem);
}

int mem_redraw (int k) {
    int i, mem_index = -1, job_index = -1;
    for (i=0;i<memsum;++i) {
        if (memdata[i].jobid == k) {
            mem_index = i;
        }
    }
    for (i=0;i<jobsum;++i) {
        if (jobdata[i].jobid == k) {
            job_index = i;
        }
    }
    if (mem_index == -1 || job_index == -1){
        printf("Cannot find the job#%d", k);
    } else {
        memdata[mem_index].state = 0;
        memdata[mem_index].jobid = 0;
        if (memdata[mem_index-1].state == 0) {
            memdata[mem_index-1].length += memdata[mem_index].length;
            mem_remove(mem_index);
        }
        if (memdata[mem_index+1].state == 0) {
            memdata[mem_index].length += memdata[mem_index+1].length;
            mem_remove(mem_index+1);
        }

    }
    return mem_index;
}

void mem_restore () {
    int k;
    memsum = 9;
    for (k=0; k<memsum; k++) {
        memdata[k].head = membackup[k-1].head;
        memdata[k].jobid = membackup[k-1].jobid;
        memdata[k].state = membackup[k-1].state;
        memdata[k].length = membackup[k-1].length;
    }
    for (k=memsum;k<max;k++) {
        memdata[k].head = 0;
        memdata[k].jobid = 0;
        memdata[k].state = 0;
        memdata[k].length = 0;
    }
}

int main (int argc, char* argv[]) {
    int i, j, start;
    printf("\n-----------Current State---------------!\n");
    mem_state();
    _keygo();
    printf("\n-----------Start allocating -----------!\n");
    start = 5;
    for (i=start;i<jobsum;i++) {
        printf("Job %s waiting for allocation, size is %iK\n",
               jobdata[i].name, jobdata[i].vol);
        // _sleep(1);
        j = mem_allocate_bf(i);
        if (j == -1) {
            printf("No enough size for job %s, fail to allocate!\n",
                   jobdata[i].name);
        }
        else{
            printf("Allocating memory for job %s\n", jobdata[i].name);
            mem_allocate(i, j);     // Allocate memory#j to Job[i]
            mem_state();
        }
        _keygo();
    }
    printf("------------Finish Allocation---------------!\n");
    printf("------------Restore  memory-----------------!\n");
    printf("\n-----------Current state------------------!\n");
    mem_state();
    j = 88;
    while (j != 0) {
        printf("Please input the job number: ");
        scanf("%d", &j);
        if (mem_redraw(j) != -1)
            printf("\nSuccessful!\n");
        printf("\n-----------Current State-----------!\n");
        mem_state();
    }
    _keygo();
    return 0;
}