• Choose a category
• All
• Classic-Fiction

By Root 1375 0

the page at which to begin the next time a frame is neededA circular list models this problem nicely because it allows a system to cycle through pages just as the algorithm requires. The runtime complexity of replace_page is O (n), where n is the number of pages in the circular list. This is because, in the worst case, the algorithm may need to make a complete cycle through the list to find the page to replace. .

Example 5.8. Implementation of Second-Chance Page Replacement

/*****************************************************************************

* *

* -------------------------------- page.c -------------------------------- *

* *

*****************************************************************************/

#include "clist.h"

#include "page.h"

/*****************************************************************************

* *

* ----------------------------- replace_page ----------------------------- *

* *

*****************************************************************************/

int replace_page(CListElmt **current) {

/*****************************************************************************

* *

* Circle through the list of pages until one is found to replace. *

* *

*****************************************************************************/

while (((Page *)(*current)->data)->reference != 0) {

((Page *)(*current)->data)->reference = 0;

*current = clist_next(*current);

}

return ((Page *)(*current)->data)->number;

}

Example 5.9. Header for Second-Chance Page Replacement

/*****************************************************************************

* *

* -------------------------------- page.h -------------------------------- *

* *

*****************************************************************************/

#ifndef PAGE_H

#define PAGE_H

#include "clist.h"

/*****************************************************************************

* *

* Define a structure for information about pages. *

* *

*****************************************************************************/

typedef struct Page_ {

int number;

int reference;

} Page;

/*****************************************************************************

* *

* --------------------------- Public Interface --------------------------- *

* *

*****************************************************************************/

int replace_page(CListElmt **current);

#endif

Figure 5.8. Second-chance page-replacement algorithm (a) at the start of a run and (b) after a page has been replaced

Questions and Answers

Q: Some advantages of linked lists over arrays have already been mentioned. However, there are occasions when arrays have advantages over linked lists. When are arrays preferable?

A: Linked lists present advantages over arrays when we expect to insert and remove elements frequently. However, arrays themselves offer some advantages when we expect the number of random accesses to overshadow the number of insertions and deletions. Arrays are strong in this case because their elements are arranged contiguously in memory. This contiguous arrangement allows any element to be accessed in O (1) time by using its index. Recall that to access an element of a linked list, we must have a pointer to the element itself. Getting a pointer to an element can be expensive if we do not know a great deal about the pattern in which the elements will be accessed. In practice, for many applications, we end up traversing at least part of the list. Arrays are also advantageous when storage is at a premium because they do not require additional pointers to keep their elements "linked" together.

Q: How do the operations of linked lists for inserting, removing, and accessing elements compare with similar ones for arrays?

A: Recall that all of the operations presented for each of the linked list variations in this chapter had runtime complexities of O (1), with the exception of the destroy operations. Indeed, this seems tough to beat. What the analyses for linked lists do not show, however, is that