c – Writing code to determine number of dirty pages=117

Trying to use “./nameSorter 500 listaccess | ./pageRefGen $x | ./$y $z” to determine which combination of x, y and z causes the number of dirty pages to = 117 where x = (32,64 or 128), y=(32,64 or 128) and $z = (FIFO, OPT or LRU) It doesn’t really matter whether I use bash to do it or modify the code in the scheduling algorithms, I have just been trying to create some daemons to answer questions like this and I need a kick start.

/* nameSorter.c
    The program generates names. Many many names.
    It can also sort the names using a quick sort algorithm.
    To convince you that it does these functions, 
    You may specify command line parameters to print
    the lists.
    
    The command line parameters are 
    (1) Number of names you want to list. No more
        than 5000 please.
    (2) You can ask it to listnames or listsorted by
        placing the request as the second command
        line argument (third if you count the command).
        
    There is a third option for the last argument: listaccess.
    In deed, that is the main purpose of the program. You
    can ask the program to list all accesses it makes
    into the arrays in the program. It prints a line for 
    each access, telling the following:
    (1) What was it attempting on the location (read or write)
    (2) Where in the memory the accesss is made (virtual address).
    
    You can pipe this info to virtual memory simulator to
    determine how many page faults the access will causes 
    under different configurations of page size and memory size.
*/

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

#define FIRST 41
#define MIDDLE 7
#define LAST 23

char names[100000];
int howmany;
char *list[5001];

void createnames() {
    char *first[FIRST]={"Bill","William","Jack","Jill","Ali",
                "Lisa","Charles","Anne","Anna","Kylie",
                "Malissa","Jenny","Julian","Nicole","Anglique",
                "Jeff","Rick","John","Kim","Chris",
                "Kris", "Rose","Amenda", "Kathy", "Tom",
                "Sue", "Susan", "Val", "Lily", "Joe",
                "Mikhail", "Peter", "Calra", "Bret", "Alexander",
                "Suzzy", "Shane", "Greg", "Mike", "Carmen",
                "Jane"};
    char *middle[MIDDLE] ={" Oart ", " Syd ", " Adel ", " Darwin ",
                 " Bane ", " Per-", " Melbourne "};
    char *last[LAST]= {"Howard","Keating","Clinton","Bush","Costello",
            "Beazley","Dermoudy","Border","Waugh", "Bacon",
            "Nguyen", "Warne", "Major", "Bullen", "McNeal",
            "Walrath","Vanstone", "Choi", "Sale", "Downer",
            "Clark", "Armstrong", "Flintstone"};
    
    int f=0,m=0,l=0,n=0,i;
    
    for (i=0;i<howmany;i++) {
        list[i]=(char *)(names+n);
        strcpy(names+n,first[f]);
        strcat(names+n,middle[m]);
        strcat(names+n,last[l]);
        n+=strlen(names+n);
        n++;
        f=(f+1)%FIRST;
        m=(m+1)%MIDDLE;
        l=(l+1)%LAST;
    }
    list[howmany]=names+n;
    strcpy(names+n,"");
}

void printlist() {
    /* Lists the names */
    int i;
    for (i=0;i<howmany;i++) {
        printf("%sn",list[i]);
    }
}

void READ(void *p, int len) {
    int i, t;
    t=len/4;
    for (i=0;i<t;i++) 
        printf("R %ldn",((int)p)+4*i-(int)p%4);
}

void WRITE(void *p, int len) {
    int i, t;
    t=len/4;
    for (i=0;i<t;i++) 
        printf("W %ldn",((int)p)+4*i-(int)p%4);
}
    
    
void qsortnames(int left, int right, int prnt) {

/* This routine will sort the names in the global
    array list.
    In addition when prnt is true it prints the 
    accesses to arrays names and list. Thus, if nnn
    is an address in array list or names that is 
    accessed during sortin then it is listed. R indicates
    read access. W indicates a write access. Addresses are
    listed in multiple of 4s only.
    
    Program is copied (and a bit modified) from The C Programming
    Languae, by Kernighan and Ritchie, 2nd edn, page 87.
*/
    char *tmp;
    int i, last, p;

    if (left>=right) 
        return;
    p=(left+right)/2;
    tmp=list[left]; list[left]=list[p];
    list[p]=tmp;
    if (prnt) {
        READ(list+left,4); WRITE(list+left,4); 
        READ(list+p,4); WRITE(list+p,4);
    }
    last=left; 
    
    for (i=left+1;i<=right;i++) {
        if (prnt) {
            READ(list+i,4);READ(list+left,4);
            READ(list[i],strlen(list[i]));
            READ(list[left],strlen(list[left]));
        }
        if (strcmp(list[i],list[left])<=0) {// less than
            last++;
            tmp=list[last]; list[last]=list[i];
            list[i]=tmp;
            if (prnt) {
                READ(list+last,4),WRITE(list+last,4);
                READ(list+i,4);WRITE(list+i,4);
            }
        }
    }
    tmp=list[left]; list[left]=list[last];
    list[last]=tmp;
    if (prnt) {
        READ(list+left,4); READ(list+last,4);
        WRITE(list+left,4);WRITE(list+last,4);
    }
    
    qsortnames(left,last-1,prnt);
    qsortnames(last+1,right,prnt);
}       

int main(int argc, char *argv[]) {
    
    if (argc!=3) {
        fprintf(stderr,"Usage ./nameSorter How_many %sn",
        "listnames|listsorted|listaccess");
        exit(0);
    }
    
    howmany = atoi(argv[1]);
    if (howmany<500 ||howmany>5000) {
        fprintf(stderr,"Please use minimum 500 names and maximum 5000 namesn");
        exit(0);
    }
    
    createnames();
    if (strcmp(argv[2],"listnames")==0)
        printlist();
    /* Sortnames and print info on accesses if required */
    if (strcmp(argv[2],"listaccess")==0)
        qsortnames(0,howmany-1,/* Print option */ 1);
    else qsortnames(0,howmany-1,/* Print option */ 0);
    if (strcmp(argv[2],"listsorted")==0)
        printlist();
    if (strcmp(argv[2],"listaccess")==0)
        printf("F 000n");
}
/* pageRefGen.c
    The program is a filter to convert memory addresses into 
    page number references. Page size is given as the command
    line argument.
*/

#include <stdio.h>
#include <stdlib.h>

/* Read and write requests made by the sort programs to
   addresses while accessing the arrays are virtual addresses.
   
   The program converts those lists into arrays of page accesses.
   
   USAGE: pageReferences pagesize
   pagesize should be 256, 512, 1024 or 2048
*/

int main(int argc, char* argv[]) {

    int pageSize, mem;
    char rw;
    
    if (argc!=2) {
        fprintf(stderr,"Usage: ./pageRefGen 64|128|256|512|1024|2048n");
        exit(0);
    }
    
    pageSize=atoi(argv[1]);
    ungetc(' ',stdin);
    
    while (1) {
        scanf(" %c %i", &rw, &mem);
        printf("%c %in", rw, mem/pageSize);
        if (rw=='F') exit(0);
    }
}
/* FIFO.c
    The filter FIFO takes one command line arguments indicating 
    (1) the number of available page frames
    [BTW: FIFO=First paged in, fisrt paged out when a page frame needed.]
    
    The standard input is a stream of lines containing two items.
    Each line is: (1) Action and (2) page number. 
    
    An action can be R (=read to page); W (=write into page); or
    F (=Finish). Second argument is the page number on which the 
    action happenes.
    
    The program simulates a virtual memory system. It prints the 
    result indicating the number of read and write actions in 
    the stdin stream. It also tells us the number of page faults
    that resulted in page ins to occur. Number of page faults 
    leading to disk writes of dirty pages are also generated.
*/
    
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define PAGES 1000
#define MAXINT 9999999

int frame[PAGES], dirty[PAGES], 
    where, frames;

void setup() {
    int i;
    
    where =0;
    for (i=0;i<frames;i++) {
        frame[i]=-1;
        dirty[i]=0;
    }
    ungetc(' ',stdin);
}

int fifo() {
    
    return where=(where+1)%frames;      
}
    
    

int main(int argc, char *argv[]) {
    int reads=0, writes=0, diskReads=0, diskWrites=0;
    int ll, i, pg;
    char rw;

    if (argc!=2) {
        fprintf(stderr,"Usage: FIFO FrameCountn");
        fprintf(stderr,"Frame count not to be over 128n");
        exit(0);
    }
    
    frames = atoi(argv[1]);
    setup();
    
    while (1) { // Process pages
    
        scanf(" %c %i", &rw, &pg);      
        if (rw=='R') {
            reads++;
            for (i=0;i<frames;i++)
                if (frame[i]==pg) {
                    i=frames+10;
                }
            if (i==frames)  {
                diskReads++;
                ll=fifo();  // Where read
            
                if (dirty[ll]==1) 
                    diskWrites++;
                
                dirty[ll]=0;
                frame[ll]=pg;
            }
        }
        else if (rw=='W') {
            writes++;
            for (i=0;i<frames;i++)
                if (frame[i]==pg) {
                    dirty[i]=1;
                    i=frames+10;
                }
            if (i==frames) {//page did not exist
                diskReads++;
                ll=fifo();  // Where read
            
                if (dirty[ll]==1) 
                    diskWrites++;
                
                dirty[ll]=1;
                frame[ll]=pg;
            }       
        }
        else {break;}
    }
    
    printf("StatsnRead accesses %inWrite accesses %in",reads,writes);
    printf("Reads from the disk %inWrites to disk %in", 
        diskReads,diskWrites);
}
/* LRU.c
    The filter LRU takes a command line argument indicating the
    number of page frames in the main memory of the simulated memory
    in a virtual memory environment using least recently used 
    algorithm to free page frames.
    
    The standard input is a stream of lines containing two items.
    Each line is: (1) Action and (2) page number. 
    
    An action can be R (=read to page); W (=write into page); or
    F (=Finish). Second argument is the page number on which the 
    action happenes.
    
    The program simulates a virtual memory system. It prints the 
    result indicating the number of read and write actions in 
    the stdin stream. It also tells us the number of page faults
    that resulted in page ins to occur. Number of page faults 
    leading to disk writes of dirty pages are also generated.
*/
    
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define PAGES 1000
#define MAXINT 9999999

int frame[PAGES], when[PAGES], dirty[PAGES], frames;

void setup() {
    int i;
    
    for (i=0;i<frames;i++) {
        frame[i]=-1;
        when[i]=-1;
        dirty[i]=0;
    }
    ungetc(' ',stdin);
}

int lru() {
    int i,j, time;
    
    for (i=0;i<frames;i++)
        if (frame[i]==-1)
            return i;
            
    time=MAXINT;
    j=-1;
    
    for (i=0;i<frames;i++) {
        if (when[i]>=time) continue;
        time = when[i];
        j=i;
    }
    return j;
}
    
    

int main(int argc, char *argv[]) {
    int reads=0, writes=0, diskReads=0, diskWrites=0, clock=-1;
    int ll, i, pg;
    char rw;

    if (argc!=2) {
        fprintf(stderr,"Usage: LRU FrameCountn");
        fprintf(stderr,"Frame count not to be over 1000n");
        exit(0);
    }
    
    frames = atoi(argv[1]);
    setup();
    
    while (1) { // Process pages
    
        scanf(" %c %i", &rw, &pg);
        clock++;
        
        if (rw=='R') {
            reads++;
            for (i=0;i<frames;i++)
                if (frame[i]==pg) {
                    when[i] = clock;
                    i=frames+10;
                }
            if (i==frames)  {
                diskReads++;
                ll=lru();  // Where read
            
                if (dirty[ll]==1) 
                    diskWrites++;
                
                dirty[ll]=0;
                frame[ll]=pg;
                when[ll]=clock;
            }
        }
        else if (rw=='W') {
            writes++;
            for (i=0;i<frames;i++)
                if (frame[i]==pg) {
                    when[i] = clock;
                    dirty[i]=1;
                    i=frames+10;
                }
            if (i==frames) {//page did not exist
                diskReads++;
                ll=lru();  // Where read
            
                if (dirty[ll]==1) 
                    diskWrites++;
                
                dirty[ll]=1;
                frame[ll]=pg;
                when[ll]=clock;
            }
        }
        else {break;}
    }
    
    printf("StatsnRead accesses %inWrite accesses %in",reads,writes);
    printf("Reads from the disk %inWrites to disk %in", 
        diskReads,diskWrites);
}
/* OPT.c
    The filter OPT takes a command line argument indicating the
    number of page frames in the main memory of the simulated memory
    in a virtual memory environment using the Optimal 
    algorithm to free page frames.
    
    The standard input is a stream of lines containing two items.
    Each line is: (1) Action and (2) page number. 
    
    An action can be R (=read to page); W (=write into page); or
    F (=Finish). Second argument is the page number on which the 
    action happenes.
    
    The program simulates a virtual memory system. It prints the 
    result indicating the number of read and write actions in 
    the stdin stream. It also tells us the number of page faults
    that resulted in page ins to occur. Number of page faults 
    leading to disk writes of dirty pages are also generated.
*/
    
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define PAGES 1000
#define ACCESSES 100000

int frame[PAGES], dirty[PAGES], accesses[ACCESSES];  
long    frames, now, allAccess;
char act[ACCESSES];


void setup() {
    int i;
    
    for (i=0;i<frames;i++) {
        frame[i]=-1;
        dirty[i]=0;
    }
    ungetc(' ',stdin);
}

void readNcompactAccesses() {
    int reads=0, writes=0;
    long g;
    
    allAccess=0;
    scanf(" %c %i", act+allAccess,accesses+allAccess);
    if (act[allAccess]=='R')
        reads++;
    else if (act[allAccess]=='W')
        writes++;
    
    while (allAccess<ACCESSES && act[allAccess]!='F') {     
        allAccess++;
        
        scanf(" %c %i", act+allAccess, accesses+allAccess);
        if (act[allAccess]=='R')
            reads++;
        else if (act[allAccess]=='W')
            writes++;
            
        if (accesses[allAccess]==accesses[allAccess-1] && 
            act[allAccess]==act[allAccess-1])
                allAccess--;
        else if (accesses[allAccess]==accesses[allAccess-1] &&
            act[allAccess]=='R') // One before was a Write
                allAccess--;
    }
    
    printf("StatsnRead accesses %inWrite accesses %in",reads,writes);
//  printf("Compacted reads/writes %in",allAccess);
//  for (g=0;g<allAccess;g++)
//  printf("%c %in",act[g],accesses[g]);
}   

int opt() { // Locates optimal page frame for replacement
    long i, last, useless[PAGES], where; 
    
    for (i=0;i<frames;i++) 
        if (frame[i]==-1) return i; // If there is as yet unused frame
    
    for (i=0;i<frames;i++) useless[i]=i;
    last=frames-1;
    
    where=now+1; // Look into future accesses
/* Frames listed in array useless from index 0 to last have not found use in
   any access from now to where. We will increment where till only one frame
   remains that has not been used. This one is obviously the one to find last use.
*/
    while (last>0 && where<allAccess) {
        for (i=0;i<last;i++) 
            if (frame[useless[i]]==accesses[where]) {
                useless[i]=useless[last];
                last--;
            }   
        where++;
    }
     
            return useless[0];
}
    


int main(int argc, char *argv[]) {
    int diskReads=0, diskWrites=0;
    int ll, i, pg;
    char rw;

    if (argc!=2) {
        fprintf(stderr,"Usage: OPT FrameCountn");
        fprintf(stderr,"Frame count not to be over 1000n");
        exit(0);
    }
    
    frames = atoi(argv[1]);
    setup();
    readNcompactAccesses();

    
    for (now=0;now<=allAccess;now++) { // Process page

        rw=act[now];
        pg=accesses[now];
        if (rw=='R') {
            for (i=0;i<frames;i++)
                if (frame[i]==pg) {
                    i=frames+10; // Page is in a frame
                }
            if (i==frames)  {
                diskReads++;
                ll=opt();  // Where read
                //fprintf(stderr,"%in",ll);
            
                if (dirty[ll]==1) 
                    diskWrites++;
                
                dirty[ll]=0; 
                frame[ll]=pg;
            }
        }
        else if (rw=='W') {
            for (i=0;i<frames;i++)
                if (frame[i]==pg) {
                    dirty[i]=1;
                    i=frames+10;
                }
            if (i==frames) {//page did not exist
                diskReads++;
                ll=opt();  // Where read
            
                if (dirty[ll]==1) 
                    diskWrites++;
                
                dirty[ll]=1;
                frame[ll]=pg;
            }
        }
        else {break;}
    }
    
    printf("Reads from the disk %inWrites to disk %in", 
        diskReads,diskWrites);
}

Leave a Comment