Implementing page replacement algorithms

[ResidentBiscuit]

As the title says, I'm working on implementing a few of the major page replacement algorithms using an artificially generated reference string and random number of frames. Anyways, for frame number n, there's going to be the initial n page faults (demand paging). I'm having trouble thinking of a way to implement this. Would I just do a straight search in my frame array for the given reference number? That'll make it fault, but searching an empty array seems silly. Any advice?

[ResidentBiscuit]

Bamp, I have got a huge mess going on here -_-

unsigned int fifo(frame frameV[], std::string refStr, int sz)
{
    unsigned int faults;
    for(int i = 0; i < refStr.size(); i++)
    {
        if(pageFault(frameV, atoi(refStr[i]), sz))
        {
            faults++;
            time_t time = 0;
            int longestIn;
            for(int j = 0; j < sz; j++)
            {
                if(frameV[j].enterTime > time)
                {
                    longestIn = j;
                }
            }
        }
    }
}

I'm stuck trying to figure out how to stick new pages in. The way I have it right now will work when frameV is full, but if not then I don't see it working. For example, if frameV is only half full and a new page comes in that isn't in there, it might just replace one of the spots with a page already because it's just checking times, and I don't know how that'll work for empty array spots. This is my third iteration of programs I've written to do this, and I always hit these problems.

[ne555]

Threat the empty pages as pages that were loaded at the beginning and never used. That way the queue is always full.

[ResidentBiscuit]

That is so simply smart. Not sure why I never thought of that. I added a constructor to my struct so let's see if this works now.

[ResidentBiscuit]

Ugh well I've got it up and running now, but it's recording too many page faults and I'm not seeing why.

fifo() returns number of faults

unsigned int fifo(frame frameV[], int refStr[], int sz)
{
    unsigned int faults = 0;
    for(int i = 0; i < REF_STR_SZ; i++)
    {
        if(pageFault(frameV, refStr[i], sz))
        {
            faults++;
            time_t tmpTime = frameV[0].enterTime;
            int longestIn = 0;
            for(int j = 1; j < sz; j++)
            {
                if(frameV[j].enterTime > tmpTime)
                {
                    longestIn = j;
                }
            }
            frameV[longestIn].pageRef = refStr[i];
            frameV[longestIn].enterTime = time(NULL);
        }
    }

    return faults;
}

Returns true on fault

inline bool pageFault(frame frameV[], int ref, int sz)
{
    for(int i = 0; i < sz; i++)
    {
        if(frameV[i].pageRef == ref)
        {
            return false;
        }
    }
    return true;
}

I have a 20 digit reference string generated randomly, with 7 frames. First time it faulted 18 times, second time it faulted 17 times. Both were wrong. First should have faulted 9, and second I didn't desk check it. Here's the data I was working with the second time:

Reference string: 67853199045177992171
Number of frames: 7
FIFO Faults: 17

Clearly that's not right -_-
EDIT:
After running through round two on paper, it should have faulted 11 times. As far as I can tell the pageFault() function is fine so I'm assuming the issue lies in my fifo() function

EDITEDIT:
Wow small mistake. Forgot to update my time variable keeping track of the longest in, and had the time check backwards. Works now, if anyone sees anything I can improve on please tell me.