Question

A new idea has come to light in which an attempt is promoted to make a program run a little faster. Since memory is way away from the CPU it behooves use to keep the active variables closer to the CPU (in a buffer) and try to cut down on the number of trips all the way to memory to get data the CPU is needing. This project has been assigned to you. Should you accept and should you succeed you will then receive appropriate compensation (a grade).

The problem is to keep active variables closer to the CPU where the variables will be kept in a buffer. When the CPU needs the data from a variable, the first place to look is in the buffer. If found that variable’s value is returned and that variable becomes the most recently used variable. If the variable is not found, then the variable’s value is fetched form memory then is added to the buffer, again becoming the most recently used variable. Now the buffer is only so big and will hold only so many variables at a time, so when the buffer is full and you add a new variable to the buffer, then an old variable needs to fall off (out of) the buffer. The variable that falls out represents a less recently used variable it leaves the buffer.

Your effort (your program) is to manage the buffer. You are to write a program that will input a stream of accessed variables simulating the variables accessed in a running program. The buffer will be implemented as a link list. Any variable accessed must first be determined if the variable is in the buffer. If so, move the variable to front of list to represent most recently used. The variables at the end of the list are the less recently used. Any variable not found in the list will be placed/added at the front of the list. At all times the buffer cannot exceed its limits.

You are to simulate different buffer sizes to see if the larger buffer size really saves much on the true memory access. So have your program test with buffer sizes of 4, 5, 6, 7, and 8, the max number of variables in the buffer. Run your program, reading through the data 5 times, one for each buffer size to test. Keep up with the number of times you have to access true memory (ie the number of times a variable is added to the buffer). Be sure not to exceed the buffer size with the number of variables in the list. Print out the buffer size and the number of memory accesses required to simulate this intermediate storage. On end-of-file for each buffer size tested, print out the current variables in the buffer at the time all variables have been read/input from the file.

The Data Structure we are implementing is called a ‘self-organizing list’ in which we have a list and on each access to a node in the list, the list is reorganized as new variables are encountered.

INPUT: Your input file for the variable stream is “LinkL Var Stream.txt”. Below is the input from the file "LinkL Var Stream.txt."

tom sue joe finney tobee total joe joe tom total goo tobee tobee total sid mikey tom tobee blue blue blue sue goo blue blue miney tobee sumup moreso sid sid mikey mikey lesso maybso goo sidtom tom tom sue blue goo sumup tobee finney finney tobee joe joe tom total goo tobee tobee total sid mikey tom tobee blue blue blue sue mikey joe where blue tom finney blue goo joe mikey where finney joe mikey goo blue blue miney tobee cooly sumup moreso sid sid mikey mikey lesso maybso goo sid tom mikey lisso maybso goo goo total where about about tom blue sid finney jojo tobee joe joe tom total goo tobee tobee total sid mikey tom tobee blue blue blue sue goo blue blue miney tobee sumup lisso moreso sid mikey mikey cooly lisso goo tobee tobee total sid mikey tom tobee blue blue blue sue so so so total tom lesso maybso goo ghost sid tom blue sid where joe sue joe sue tom sue where sid tom mikey lisso jo sumup jo jo maybso goo goo sumup total sumup lisso where about cooly about tom blue sid finney tobee ghost ghost cooly joe joe tom total goo blue blue miney moreso sid sid mikey mikey tom tobee blue blue blue sue so so so total tom lesso goo tobee tom blue sid sid goo maybso goo sid tom blue sid where joe ghost sue joe sue tom sue mikey total conditions select windows joe where blue tom finney goo sid blue blur blue joe sumup total miney total categories advanced estate finney goo sid blue blur box west team estate team estate box estate sales look windows photos english estate box estate box left conditions select windows photos sid blue blur blue joe sumup team estate box windows photos team estate photos conditions select windows photos windows photos team estate photos windows photos west left conditions west photos team estate west categories advanced estate box categories advanced west estate box select photos team select windows photos left conditions team estate left conditions west west west west select west windows select windows photos team west left conditions photos team estate box windows select left conditions windows left conditions photos team windows photos team estate box windows

OUTPUT: Each Buffer size, number of memory accesses and the last list of variables remaining in the buffer.

Program needs to be written in C++.

Answer 1

Below is the C++ code I hope that i have provided sufficient comments for your better understanding Note that I have done proper indentation but this code is automatically left alligned on this interface

#include<bits/stdc++.h>
using namespace std;
#define BUFFER_SIZE 4
int main()
{
    ifstream file;
    string line,filename,word;
    vector <string>v; //To store detail of every employee
    int ind,prev;
    list <string>buffer;
    list <string>::iterator it;

    filename = "LinkLVarStream.txt"; //File name
    file.open(filename);    // open file
    while (getline(file,line)) //line will now contain entire row of information
    {
        prev = -1;
        while(1)    //loop till all words from the line are read
        {
            ind = line.find(" ",prev+1);
            if(ind==-1) //we have reached end of the line
                break; //exit from loop
            word = line.substr(prev+1,ind-prev-1); //word is to be stored in buffer

            for(it = buffer.begin(); it!=buffer.end(); it++)
            {
                if(*it == word) //This word was present in the buffer
                    break; //exit from the loop
            }
            if(it == buffer.end()) //This is a new word
            {
                if(buffer.size()==BUFFER_SIZE) //buffer is full
                {
                    buffer.pop_back(); //remove last word from buffer
                }
                buffer.push_front(word); //add new word to buffer
            }
            else    //word was present move it to the back of the list
            {
                buffer.erase(it);   //remove it from buffer
             //   it = buffer.erase(it);   .//remove it from buffer
                buffer.push_front(word);
            }
            prev = ind;
        }
        word = line.substr(prev+1); //This is the last word of the line

            for(it = buffer.begin(); it!=buffer.end(); it++)
            {
                if(*it == word) //This word was present in the buffer
                    break; //exit from the loop
            }
            if(it == buffer.end()) //This is a new word
            {
                if(buffer.size()==BUFFER_SIZE) //buffer is full
                {
                    buffer.pop_back(); //remove last word from buffer
                }
                buffer.push_front(word); //add new word to buffer
            }
            else    //word was present move it to the back of the list
            {
                buffer.erase(it);   //remove it from buffer
             //   it = buffer.erase(it);   .//remove it from buffer
                buffer.push_front(word);
            }
    }
    cout<<"Value stored in buffer is ";
    for(it = buffer.begin(); it!=buffer.end(); it++)
    {
         cout<<*it<<" ";
    }
}

I have tried to explain it in very simple language and I hope that i have answered your question satisfactorily.Leave doubts in comment section if any.