COMP1521-Virtual-Memory-Simulator

发表于 | 分类于
代写操作系统需求，实现一个虚拟内存仿真器，包括LRU和FIFO.

Objectives

  • to give you more practice writing C
  • to give you experience with a simulation
  • to learn more about virtual memory systems

Background

Virtual memory is a powerful technique that allows the main memory of a computer system to be shared amongst a large number of processes. It also allows indivudual processes to have a process address space that is potentially larger than main memory.

The implementation of virtual memory requires the system to maintain, for each process, a mapping table (page table) that tells where each page is loaded in memory, or that it is not loaded. Whenever the process references an address in its address space, we use the page table to map this virtual address to a real location in the machine’s memory. If a referenced page is not currently loaded, then we need to place it in a memory frame. If there is a free frame, we can use that; if all frames are in use, then we need to make space, by replacing the contents of one of the existing frames.

For more details on page replacement strategies, see the lecture notes. For this exercise, we focus on:

  • LRU … replace the page that hasn’t been accessed for longest time
  • FIFO … replace the page that was loaded earliest

The following diagram shows a page table that maps the pages of a process with 8 pages into the 4 frames in main memory:

The aim of this request is to build a simple simulation of a system like the above, where we can measure how the system behaves if we change the number of pages, number of frames, and the page replacement policy.

We do not fully represent pages or frames in our system, nor do we “execute” programs. We provide data structures for the page table and a minimal representation of memory pages. This gives enough to read a sequence of page references and measure how the page table might behave in a real implementation.

Setting Up

Create a new directory for working on the request, change into that directory, and then run the command:

$ unzip /home/cs1521/web/17s2/assigns/ass2/ass2.zip
This will add the following files into the directory:

1
2
3
4
5
6
Makefile        to control compilation
Stats.[ch]        implementation and interface to the summary statistics collection and display
Memory.[ch]        implementation and interface to the representation of physical memory frames
PageTable.[ch]    implementation and interface of the page table (what you need to modify) 
vmsim.c            the main program for the virtual memory simulator
mktrace.c        a program to generate memory reference traces

The page table is represented by an array of PTE structures which is dynamically created at the start of the simulation. Each PTE contains the following information:

1
2
3
4
5
6
7
char status;    // NOT_USED, IN_MEMORY, ON_DISK
char modified;  // boolean: has the page changed since loaded?
int frame;      // memory frame holding this page
int accessTime; // clock tick for last time the page was accessed
int loadTime;   // clock tick for last time the page was loaded
int nPeeks;     // total number times this page referenced for reading
int nPokes;     // total number times this page referenced for writing

You can find more details on the supplied code, and how to use it in the request 2 Video.

Exercise

The aim of this exercise is to implement two page replacement strategies (LRU and FIFO) and collect statistics on the page table’s behaviour. Implementing the page replacement strategies requires you to complete the findVictim() function. Collecting he statiscs requires you to place calls to the statistics functions in the appropriate places. You can find out more details on what statistics need to be collected in the Stats.c file.

A simple, and extremely inefficient, implementation of LRU replacement would work as follows:

1
2
3
4
5
6
7
8
9
oldest = now
victim = NONE
for (i = 0; i < #Pages; i++) {
  P = PageTable[i]
  if (P's accessTime < oldest)
    oldest = P's accessTime
    victim = P's page
  }
}

A better strategy would be maintain a list of pages, ordered by access time from oldest (first in list) to most recent (last in list). The above code would then simply remove the first page from the list and use that as the page to be replaced. Of course, the list needs to be updated each time a page is accessed.

The list should not be implemented as a separate data structure, but could be done by incorporating a “link” to the next page in the list in each PTE. You would also need to maintain a global variable to hold the page number of the first page in the list.

Similarly, a simple and inefficient implementation of FIFO replacement would work as follows:

1
2
3
4
5
6
7
8
9
oldest = now
victim = NONE
for (i = 0; i < #Pages; i++) {
  P = PageTable[i]
  if (P's loadTime < oldest)
    oldest = P's loadTime
    victim = P's page
  }
}

As above, a better strategy would be to maintain a list of pages, ordered by load time from oldest (first in list) to most recently loaded (last in list). The implementation would be similar to that for the LRU list.

What you are required to do (and you only need to change the PageTable.c file for this request) is specified in comments in the PageTable.c file.

Sample Outputs

To get you started with debugging, sample outputs are available for the following test cases:

1
2
3
4
./vmsim lru 5 4 < trace1 > out-lru-5-4-trace1.txt
./vmsim fifo 5 4 < trace1 > out-fifo-5-4-trace1.txt
./vmsim lru 8 4 < trace2 > out-lru-8-4-trace2.txt
./vmsim fifo 8 4 < trace2 > out-fifo-8-4-trace2.txt

Additional Requirements

You must not implement the process of finding a victim so that it requires a scan of PageTable entries. Similarly it must not require a scan of any list structure that you might define. Also, the process of updating the LRU or FIFO list must not be an O(n) process. A program that produces output that passes the auto-marking, but is scan-based, is worth only 1/4 marks for the auto-marking, and half marks for each of the list-related assessment criteria.

Do not add extra debugging output using #ifdef DBUG. If you want to add your own debugging output, enclose it in #ifdef MY_DBUG…#endif and add -DMY_DBUG to the line defining CFLAGS in the Makefile.

Do not change the “standard” behaviour of showPageTableStatus(). If you want to add extra output on the PageTable, enclose it in #ifdef MY_DBUG…#endif. We assume that showPageTableStatus() has the same behaviour as the supplied version for the purposes of auto-marking.