New Bulgarian University
Topic
First-in first-out replacement algorithm





FIFO Page Replacement

The simplest page-replacement algorithm is FIFO algorithm. A FIFO replacement algorithm associates with each page the time when that page was brought into memory. When a page must be replaced, the oldest page is chosen. Notice that it is not strictly necessary to record the time when the a page is brought in. We can create a FIFO queue to hold all pages in memory. We replace the page at the head of the queue. When a page is brought into memory, we insert it at the tail of queue.

The FIFO page-replacement algorithm is easy to understand and program. However, its performance is not alwayes good. The page replaced may be an initialization module that was used a long time ago and is no longer needed. On the other hand, it could contain a heavily used variable that was initialized early and is in constant use.

//queue.cpp

template 
struct elem
{
	T inf;
	elem *link;
};

template 
class queue
{
public:
	queue();
	~queue();
	queue(queue const &a);
	queue &operator=(queue const &a);
	void push(T const &k);
	void pop();
	T top() const;
	bool empty() const;
	void print();
private:
	elem *front, *rear;
	void del();
	void copy(queue const &a);
};

template 
queue::queue()
{
	front=NULL;
	rear=NULL;
}

template 
queue::~queue()
{
	del();
}

template 
queue::queue(queue const &a)
{
	copy(a);
}

template 
queue & queue::operator=(queue const &a)
{
	if(this!=&a)
	{
		del();
		copy(a);
	}
	return *this;
}

template 
void queue::push(T const &k)
{
	elem *p=new elem;
	p->inf=k;
	p->link=NULL;
	if(rear) rear->link=p;
	else front=p;
	rear=p;
}

template 
void queue::pop()
{
	elem *p;
	p=front;
	if(p==rear)
	{
		rear=NULL;
		front=NULL;
	}
	else front=p->link;
	delete p;
}

template 
T queue::top() const
{
	return front->inf;
}


template 
bool queue::empty() const
{
	return front==NULL;
}

template 
void queue::print()
{
	while(front!=NULL)
	{
		cout << setw(5) << front->inf;
		pop();
	}
}

template 
void queue::del()
{
	while(front!=NULL)
		pop();
}

template 
void queue::copy(queue const &a)
{
	rear=NULL;
	if(a.rear)
	{
		elem *p=a.front;
		while(p)
		{
			push(p->inf);
			p=p->link;
		}
	}
}


















Notice that, even we select for replacement a page that is in active use, everything still works correctly. After we page out an avtive page to bring in a new one, a fault occurs almostimmediately to retrieve the active page. Some other page will need to be replaced to bring the active page back into memory. Thus, a bad replacement choice increqses the page-fault rate and slows process execution, but does not cause incorrect execution.

To illustrate the problems that are possible with a FIFO page-replaced algorithm, we consider the reference string :

12 14 2 34 56 23 14 56 34 12

 12 12 12 12 56 56 56      56
    14 14 14 14 23 23      23
        2  2  2  2 14      14
          34 34 34 34      12


















The most unexpected result is known az Belady's anomaly: For some page-replacement algorithms, the page-fault rate may increase as the number of allocated frames increases. We would expect that giving more memory to a process wouls improve its performance. In some early research investigators notoced that this assumption was not always true. Belady's anomaly was discovered as a result.