PROGRAM 2


/*   name:  anthony f. ortiz  */
/*     id:  2871              */
/*  login:  cs304-21          */
/*     ex:  all               */

/*  gcc -o mem1 mem1.c  */
/*  student version of memory simulator  */
/*  search on ex to find exercises  */

#include 
#include 

#define MAXPAGES  20
#define MAXFRAMES 20
#define INFINITY 999999
#define INVALID 0
#define VALID 1
#define NIL -1
#define FALSE 0
#define TRUE 1
#define NOREF 0
#define REF 1
#define MAXLINE 80
#define MAXREF 100
#define DETAILED 0
#define JUSTFRAMES 1
#define JUSTSUMMARY 2

#define FIFO 0
#define OPT 1
#define LRU_TIME 2
#define LRU_REF 3
#define CLOCK 4
#define LFU 5
#define MFU 6

typedef union
{
    struct
    {
        unsigned int page  :15;
        unsigned int offset:10;
    } logical;
    int addr;
} laddr;

typedef union
{
    struct
    {
        unsigned int frame :15;
        unsigned int offset:10;
    } physical;
    int addr;
} paddr;

typedef struct
{
    unsigned int frame:15;
    unsigned int bit  : 1;
    unsigned int dirty: 1;
    unsigned int ref  : 1;
    int          cnt;
    int          last_time;
    int          first_time;
} page_entry;

typedef struct
{
    page_entry entries[MAXPAGES];
} page_table;

typedef struct
{
    int page;
} frame_entry;

typedef struct
{
    frame_entry entries[MAXFRAMES];
} frame_table;

page_table *PTBR;
frame_table *FTBR;

int tot_ref = 0;
int ref_ptr;
int reference[MAXREF];
int faults;
static int clock = 0;

int alg     = FIFO;
int mode    = DETAILED;
int virtual = TRUE;
int PTLR    = MAXPAGES;
int FTLR    = MAXFRAMES;
int FTVR;

void trap(char *s)
{
    printf("TRAP: %s\n",s);
}

void read_block(int page,int frame)
{
}

void write_block(int page,int frame)
{
}

void page_range(int page) {
    if ((page < 0) || (page >= PTLR))
        trap("PAGE OUT OF RANGE");
}

void frame_range(int frame)
{
    if ((frame < 0) || (frame >= FTLR))
        trap("FRAME OUT OF RANGE");
}

void reset_page(int page)
{
    page_range(page);
    PTBR->entries[page].frame = 0;
    PTBR->entries[page].bit   = INVALID;
    PTBR->entries[page].dirty = FALSE;
    PTBR->entries[page].ref   = NOREF;
    PTBR->entries[page].cnt   = 0;
}

void reset_frame(int frame)
{
    frame_range(frame);
    FTBR->entries[frame].page = NIL;
}

void set(int page,int frame)
{
    page_range(page);
    frame_range(frame);
    PTBR->entries[page].bit   = VALID;
    PTBR->entries[page].frame = frame;
    FTBR->entries[frame].page = page;
}

/*  ex: fifo algorithm  */
int fifo_alg()
{
    int save_reg,page,frame,earliest_time;

    save_reg = FTVR;
    earliest_time = INFINITY;
    do
    {
        FTVR++;
        if (FTVR >= FTLR) FTVR = 0;
        page = FTBR->entries[FTVR].page;
        if (page == NIL) return(FTVR);
        if (PTBR->entries[page].first_time < earliest_time)
        {
            earliest_time = PTBR->entries[page].first_time;
            frame = FTVR;
        }
    }
    while (FTVR != save_reg);
    FTVR = frame;
    return(FTVR);
}

/*  ex: opt algorithm  */
int opt_alg(start,n,ref_string)
int start,n;
int ref_string[MAXREF];
{
    int save_reg,page,frame,largest_count, i, j;
    int counts [20];
    save_reg = FTVR;
    largest_count = -1;
    for (i = 0; i < FTLR; i++)
    {
        counts [i] = 0;
        for (j = start - 1; j <= n; j++)
        {
            if (FTBR->entries[i].page == ref_string [j])
            {
                break;
            }
            else
            {
                counts [i] = counts [i] + 1;
            }
        }
    }
    do
    {
        FTVR++;
        if (FTVR >= FTLR) FTVR = 0;
        page = FTBR->entries[FTVR].page;
        if (page == NIL) return (FTVR);
        if (counts [FTVR] > largest_count)
        {
            largest_count = counts [FTVR];
            frame = FTVR;
        }
    }
    while (FTVR != save_reg);
    FTVR = frame;
    return(FTVR);
}

/*  ex: lru_ref algorithm  */
int lru_ref_alg(start,n,ref_string)
int start,n;
int ref_string[MAXREF];
{
    int save_reg,page,frame,largest_count, i, j, k;
    int counts [20];
    int backwards [MAXREF];
    save_reg = FTVR;
    largest_count = -1;
    for (k = 1; k <= n; k++)
    {
        backwards [k] = ref_string [n + 1 - k];
    }
    for (i = 0; i < FTLR; i++)
    {
        counts [i] = 0;
        for (j = start - 1; j <= n; j++)
        {
            if (FTBR->entries[i].page == backwards [j])
            {
                break;
            }
            else
            {
                counts [i] = counts [i] + 1;
            }
        }
    }
    do
    {
        FTVR++;
        if (FTVR >= FTLR) FTVR = 0;
        page = FTBR->entries[FTVR].page;
        if (page == NIL) return (FTVR);
        if (counts [FTVR] > largest_count)
        {
            largest_count = counts [FTVR];
            frame = FTVR;
        }
    }
    while (FTVR != save_reg);
    FTVR = frame;
    return(FTVR);
}

/*  ex: lru_time algorithm  */
int lru_time_alg()
{
    int save_reg,page,frame,earliest_time;

    save_reg = FTVR;
    earliest_time = INFINITY;
    do
    {
        FTVR++;
        if (FTVR >= FTLR) FTVR = 0;
        page = FTBR->entries[FTVR].page;
        if (page == NIL) return(FTVR);
        if (PTBR->entries[page].last_time < earliest_time)
        {
            earliest_time = PTBR->entries[page].last_time;
            frame = FTVR;
        }
    }
    while (FTVR != save_reg);
    FTVR = frame;
    return(FTVR);
}

/*  ex: clock algorithm  */
int clock_alg()
{
    int page,frame;

    do
    {
        FTVR++;
        if (FTVR >= FTLR) FTVR = 0;
        page = FTBR->entries[FTVR].page;
        if (page == NIL) return(FTVR);
        if (PTBR->entries[page].ref == REF)
        {
            PTBR->entries[page].ref = NOREF;
        }
        else if (PTBR->entries[page].ref == NOREF)
        {
            PTBR->entries [page].ref = REF;
            frame = FTVR;
            break;
        }
    }
    while (1);  /*  there is another way out of this loop.  */
    FTVR = frame;
    return(FTVR);
}

/*  ex: lfu or mfu algorithm  */
int l_or_mfu_alg(lfu)
int lfu;
{
    int save_reg,page,frame,smallest_count, largest_count;

    save_reg = FTVR;
    smallest_count = INFINITY;
    largest_count = 0;
    do
    {
        FTVR++;
        if (FTVR >= FTLR) FTVR = 0;
        page = FTBR->entries[FTVR].page;
        if (page == NIL) return(FTVR);
        if (PTBR->entries[page].cnt < smallest_count && lfu == TRUE)
        {
            smallest_count = PTBR->entries[page].cnt;
            frame = FTVR;
        }
        else if (PTBR->entries[page].cnt > largest_count && lfu == FALSE)
        {
            largest_count = PTBR->entries[page].cnt;
            frame = FTVR;
        }
    }
    while (FTVR != save_reg);
    FTVR = frame;
    return(FTVR);
}

int find_free_frame()
{
    int save_reg;
    save_reg = FTVR;
    do
    {
        FTVR++;
        if (FTVR >= FTLR) FTVR = 0;
        if (FTBR->entries[FTVR].page == NIL) return(FTVR);
    }
    while (FTVR != save_reg);
    return(NIL);
}


int find_frame()
{
    int frame;

    if (!virtual)
    {
        frame = find_free_frame();
        if (frame == NIL)
            trap("NOT ENOUGH FRAMES FOR NON-VIRTUAL MEMORY");
    }
    else
        switch (alg) {
            case FIFO    : frame = fifo_alg(); break;
            case OPT     : frame = opt_alg(ref_ptr+1,tot_ref,reference); break;
            case LRU_TIME: frame = lru_time_alg(); break;
            case LRU_REF : frame = lru_ref_alg(ref_ptr+1,tot_ref,reference); break;
            case CLOCK   : frame = clock_alg(); break;
            case LFU     : frame = l_or_mfu_alg(TRUE); break;
            case MFU     : frame = l_or_mfu_alg(FALSE); break;
                 }
    return(frame);
}

void init_tables(int tot_pages,int tot_frames)
{
    int page,frame;
    faults = 0;
    ref_ptr= 0;
    PTLR = tot_pages;
    PTBR = (page_table *) malloc(sizeof(page_entry)*PTLR);
    FTLR = tot_frames;
    FTBR = (frame_table *) malloc(sizeof(frame_entry)*FTLR);
    FTVR = -1;
    for (page=0; page m) m = FTLR;
        for (i= 0; i");
            else
                printf(" ");
            printf("%3d ",i);
            if (i < PTLR)
                printf("%5d   %d ",PTBR->entries[i].frame,
                PTBR->entries[i].bit);
            else
                printf("                ");
            if (i < FTLR)
            {
                printf("%10d",FTBR->entries[i].page);
                if (i == frame)
                {
                    printf(" <");
                    if (faulted) printf(" Fault %d",faults);
                }
            }
            printf("\n");
        }
    }

    if (mode == JUSTFRAMES)
    {
        printf("page:%2d  faults:%2d  frames: ",page,faults);
        for (f=0; fentries[f].page);
        if ((alg != OPT) && (alg != LRU_REF))
        {
            switch (alg)
            {
                case FIFO    :
                case LRU_TIME: printf(" time: "); break;
                case CLOCK   : printf(" ref : "); break;
                case LFU     :
                case MFU     : printf(" cnt : ");
            }
            for (f=0; fentries[f].page;
                if (page != NIL)
                {
                    switch (alg) {
                        case FIFO    : value=PTBR->entries[page].first_time; break;
                        case LRU_TIME: value=PTBR->entries[page].last_time; break;
                        case CLOCK   : value=PTBR->entries[page].ref; break;
                        case LFU     :
                        case MFU     : value=PTBR->entries[page].cnt; break;
                             }
                    printf("%2d ",value);
                }
            }
        }
        printf("\n");
    }
}

void page_ref(page)
{
    int frame,old_page;
    int faulted = FALSE;

    ref_ptr++;
    clock++;
    page_range(page);
    frame = PTBR->entries[page].frame;
    if (PTBR->entries[page].bit == INVALID)
    {
        faulted = TRUE;
        faults++;
        frame = find_frame();
        old_page = FTBR->entries[frame].page;
        if (old_page != NIL)
        {
            if (PTBR->entries[old_page].dirty)
                write_block(old_page,frame);
            reset_page(old_page);
        }
        reset_page(page);
        read_block(page,frame);
        set(page,frame);
        PTBR->entries[page].first_time = clock;
    }
    PTBR->entries[page].cnt++;
    PTBR->entries[page].ref = REF;
    PTBR->entries[page].last_time = clock;
    ref_display(page,frame,faulted);
}

void delete(int page)
{
    int frame = NIL;
    page_range(page);
    if (PTBR->entries[page].bit == VALID)
    {
        frame = PTBR->entries[page].frame;
        if (PTBR->entries[page].dirty)
            write_block(page,frame);
        reset_frame(frame);
    }
    reset_page (page);
    ref_display(page,frame,FALSE);
}

void l_to_addr(laddr l)
{
    paddr p;
    int page;
    page =l.logical.page;
    page_ref(page);
    p.physical.frame = PTBR->entries[page].frame;
    p.physical.offset = l.logical.offset;
    printf("Logical  Address page : %2d   offset: %4d\n",l.logical.page,l.logical.offset);
    printf("Physical Address frame: %2d   offset: %4d\n",p.physical.frame,p.physical.offset);
}

void make_ref_str(int page)
{
    tot_ref++;
    reference[tot_ref] = page;
}


main(int argc, char *argv[])
{
    char cmd[MAXLINE];
    int page,start_frame,end_frame,do_read = TRUE;
    laddr l;
    clrscr ();
    init_tables(PTLR,FTLR);
    do
    {
        if (argc == 1) printf("mem> ");
        scanf("%s",cmd);
        switch (cmd[0])
        {
            case 'a' : scanf("%d",&alg); break;
            case 'v' : scanf("%d",&virtual); break;
            case 'r' : scanf("%d",&page);
                       make_ref_str(page);
                       if (do_read) page_ref(page);
                       break;
            case 'w' : scanf("%d",&page);
                       make_ref_str(page);
                       page_ref(page);
                       PTBR->entries[page].dirty = TRUE;
                       break;
            case 'd' : scanf("%d",&page);
                       delete(page);
                       break;
            case 'i' : scanf("%d %d",&PTLR,&FTLR);
                       if ((PTLR < 1) || (PTLR > MAXPAGES))
                           trap("PAGES OUT OF RANGE");
                       if ((FTLR < 1) || (FTLR > MAXFRAMES))
                           trap("FRAMES OUT OF RANGE");
                       init_tables(PTLR,FTLR);
                       if (mode == JUSTFRAMES)
                           printf("*** pages: %d  frames: %d  alg: %d\n",PTLR,FTLR,alg);
                       break;
            case 'l' : scanf("%d",&l);
                       l_to_addr(l);
                       break;
            case 'm' : scanf("%d",&mode); break;
            case 'n' : do_read = FALSE; break;
            case 'g' : end_frame = FTLR;
                       if (mode == JUSTSUMMARY)
                           start_frame = 1;
                       else
                           start_frame = FTLR;
                       if (mode == JUSTFRAMES)
                           printf("*** pages: %d  frames: %d  alg: %d\n",PTLR,FTLR,alg);
                       for (FTLR=start_frame; FTLR<=end_frame; FTLR++)
                       {
                           init_tables(PTLR,FTLR);
                           for (page=1; page<=tot_ref; page++)
                               page_ref(reference[page]);
                           if (mode == JUSTSUMMARY)
                               printf("%3d %3d\n",FTLR,faults);
                       }
                       break;
            case 'h' : printf("i(nit    pages frames [pages in 1..%d, frames in 1..%d]\n",MAXPAGES,MAXFRAMES);
                       printf("r(ead    page         [page  in 0..%d]\n",PTLR-1);
                       printf("w(rite   page         [page  in 0..%d]\n",PTLR-1);
                       printf("d(elete  page         [page  in 0..%d]\n",PTLR-1);
                       printf("l(ogical addr         [page:22bits offset:10bits]\n");
                       printf("a(lgorithm 0:FIFO|1:OPT|2:LRU_TIME|3:LRU_REF|4:CLOCK|5:LFU|6:MFU\n");
                       printf("m(ode      0:DETAILED|1:FRAMES|2:SUMMARY\n");
                       printf("v(irtual   0:OFF|1:ON\n");
                       printf("n(ogo                 [save all reads for go]\n");
                       printf("g(o                   [do all reads; for SUMMARY try all frames]\n");
                       printf("q(uit\n");
                       break;
        }
    } while (cmd[0] != 'q');
}

/*  outfile:  prog2.out  */

h
i(nit    pages frames [pages in 1..20, frames in 1..20]
r(ead    page         [page  in 0..19]
w(rite   page         [page  in 0..19]
d(elete  page         [page  in 0..19]
l(ogical addr         [page:22bits offset:10bits]
a(lgorithm 0:FIFO|1:OPT|2:LRU_TIME|3:LRU_REF|4:CLOCK|5:LFU|6:MFU
m(ode      0:DETAILED|1:FRAMES|2:SUMMARY
v(irtual   0:OFF|1:ON
n(ogo                 [save all reads for go]
g(o                   [do all reads; for SUMMARY try all frames]
q(uit

alg 0
mode 1
init 8 3
*** pages: 8  frames: 3  alg: 0
r 7 r 0 r 1 r 2 r 0 r 3 r 0 r 4 r 2 r 3 r 0 r 3 r 2 r 1 r 2 r 0 r 1 r 7 r 0 r 1
page: 7  faults: 1  frames:  7 -1 -1  time:  1
page: 0  faults: 2  frames:  7  0 -1  time:  1  2
page: 1  faults: 3  frames:  7  0  1  time:  1  2  3
page: 2  faults: 4  frames:  2  0  1  time:  4  2  3
page: 0  faults: 4  frames:  2  0  1  time:  4  2  3
page: 3  faults: 5  frames:  2  3  1  time:  4  6  3
page: 0  faults: 6  frames:  2  3  0  time:  4  6  7
page: 4  faults: 7  frames:  4  3  0  time:  8  6  7
page: 2  faults: 8  frames:  4  2  0  time:  8  9  7
page: 3  faults: 9  frames:  4  2  3  time:  8  9 10
page: 0  faults:10  frames:  0  2  3  time: 11  9 10
page: 3  faults:10  frames:  0  2  3  time: 11  9 10
page: 2  faults:10  frames:  0  2  3  time: 11  9 10
page: 1  faults:11  frames:  0  1  3  time: 11 14 10
page: 2  faults:12  frames:  0  1  2  time: 11 14 15
page: 0  faults:12  frames:  0  1  2  time: 11 14 15
page: 1  faults:12  frames:  0  1  2  time: 11 14 15
page: 7  faults:13  frames:  7  1  2  time: 18 14 15
page: 0  faults:14  frames:  7  0  2  time: 18 19 15
page: 1  faults:15  frames:  7  0  1  time: 18 19 20

q




BACK TO CS4560 PAGE.