Category : Files from Magazines
Archive : DDJ0489.ZIP
Filename : LRU.C
Output of file : LRU.C contained in archive : DDJ0489.ZIP
by Tom Gettys
[FULL LISTING FOR SIDEBAR TO _VIRTUAL DEMAND PAGED MEMORY_ BY
KENT DAHLGREN IN THE APRIL, 1989, ISSUE OF DDJ]
#include
#include
#define BYTE unsigned char
#define WORD unsigned int
#define TRUE 1
#define FALSE 0
#define READ 0
#define WRITE 1
#define BAD_PAGE 0xFFFF /* set to invalid page ID */
#define BFRS 0x8 /* number of page buffers */
#define LIST_HEAD BFRS /* index of FIFO list head */
/*
** lru_fifo[] is a queue that is the mechanism by which the LRU algorithm
** is realized. It is implemented as a doublely-linked list to facilitate
** node deletion as well as the queuing and de-queuing of nodes. The last
** element is the list head node.
*/
struct
{
WORD succ; /* index of next younger node */
WORD pred; /* index of next older node */
BYTE dirty_bit; /* TRUE if page has been written to */
WORD page_id; /* ID of page associated w/this node */
} lru_fifo[BFRS + 1];
/*
** The nodes of LRU_FIFO[] are linked together into a circular doublely-linked
** list with a list head (last element). In this particular implementation the
** ID of the buffer associated with each node is the same as the node index.
** Note that the page_id is set to a value that is guarenteed to not match
** any valid page request, and the dirty-bit is set to FALSE. By priming the
** system with bogus pages the startup special cases are avoided and the code
** is more efficient (is the LRU FIFO full/empty?).
*/
void init_fifo(void)
{
WORD i;
for (i = 0; i <= BFRS; i++)
{
lru_fifo[i].succ = i + 1;
lru_fifo[i].pred = i - 1;
lru_fifo[i].page_id = BAD_PAGE;
lru_fifo[i].dirty_bit = FALSE;
}
lru_fifo[0].pred = BFRS;
lru_fifo[BFRS].succ = 0;
}
/*
** The specified page ID is compared to the IDs of the resident pages. If a
** match is found the ID of the buffer containing that page is placed in the
** second parameter and a value of TRUE is returned. If no match is found
** the ID of the LRU page is placed in the second parameter and a value of
** FALSE is returned.
*/
int search(WORD page_id, WORD *buffer)
{
WORD i;
for (i = 0; i < BFRS; i++)
{
if (lru_fifo[i].page_id == page_id)
{
*buffer = i;
return(TRUE);
}
}
*buffer = lru_fifo[LIST_HEAD].succ;
return(FALSE);
}
/*
** The specified FIFO node is requeued - that is, it is deleted from its
** current position and inserted at the back of the queue.
*/
void requeue(WORD node)
{
lru_fifo[lru_fifo[node].pred].succ = lru_fifo[node].succ; /* delete node */
lru_fifo[lru_fifo[node].succ].pred = lru_fifo[node].pred; /* from FIFO */
lru_fifo[lru_fifo[LIST_HEAD].pred].succ = node; /* link node to the */
lru_fifo[node].pred = lru_fifo[LIST_HEAD].pred; /* rear of the FIFO */
lru_fifo[LIST_HEAD].pred = node; /* link node to the */
lru_fifo[node].succ = LIST_HEAD; /* list head */
}
/*
** This function serves as a bare-bones memory manager. Print statements
** are used to specify the state of the MMS and indicate the operations
** to be performed in each case.
*/
void manager(WORD page, int rw)
{
int found;
WORD bid;
found = search(page, &bid);
if (!found)
{
printf("page fault on page %X - ", page);
printf("the LRU buffer is %X\n", bid);
if (lru_fifo[bid].dirty_bit)
{
printf("buffer %X has been modified - ", bid);
printf("writing page %X\n", lru_fifo[bid].page_id);
}
lru_fifo[bid].page_id = page;
if (rw == WRITE)
printf("writing page %X to buffer %X\n", page, bid);
else
printf("reading page %X into buffer %X\n", page, bid);
}
else if (rw == WRITE)
printf("writing page %X to buffer %X\n", page, bid);
if (rw == WRITE) lru_fifo[bid].dirty_bit = TRUE;
requeue(bid);
}
void main(void)
{
char rw;
int found, done;
WORD page, bid, buffer;
init_fifo();
done = FALSE;
while (!done)
{
printf("\nTo end enter %X for the page number\n", BAD_PAGE);
printf("enter a page number and either R or W: ");
scanf("%x %c", &page, &rw);
if (rw == 'w') rw = 'W';
if (page == BAD_PAGE) done = TRUE;
else manager(page, rw == 'W' ? WRITE : READ);
}
}
Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!
This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.
But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/