Skip Navigation | ANU Home | Search ANU | Search FEIT | Feedback

COMP2300

Tutorial / Laboratory 08 - Virtual Memory in PeANUt

Semester 1, 2008         Week 10 (12 -- 16 May)

Note that for this session, there are some Preparation Exercises. Also for this session, there is a submitable laboratory exercise which is due by 10 am Tuesday 20 May (week 11), which will contribute up to 1% of your assessment (in the Tute/Lab mark).

Objectives

There are several objectives in this exercise:

• To deepen your understanding of procedures, traps and bit operations in PeANUt.
• To improve your understanding of how virtual memory (paging) is implemented on the PeANUt machine.
• To improve your understanding of how the LRU and FIFO paging policies can be implemented, and of the paging characteristics of each.

Preparation

NOTE: This laboratory requires you to read the detailed description of the operation of PeANUt Virtual Memory that appears in Section 3 of the PeANUt Specification. It is highly desirable that you read this in advance of your laboratory. Reading the rest of this document in advance will be helpful too. You will waste your lab time and miss out on opportunities to ask your tutor relevant questions if you do not prepare adequately.

Preparation Exercises

Complete the following questions on a separate sheet of paper, with your name and student number clearly written. Please ensure your writing is legible. Hand in to your tutor at the beginning of your tutorial / laboratory session.

1. What is meant by the terms page and page frame?
2. What is a page fault? When does it happen?
3. What is the role of the dirty bit? Where is it found?
4. What is thrashing?

Tutorial Exercises

1. What sequence of paging events take place when a program is first being run (on a real machine)?
2. What are the possible (worst-case) chain of events that can happen in the PeANUt machine during a load instruction between an address being loaded into the MAR and the data appearing in the MDR?
3. It is said that the LRU page replacement policy is far better than the FIFO. What does this statement mean? Why would we expect it to be so?
4. On tbhe PeANUt machine, suppose page 8₁₀ is present in physical memory page frame 5 and a store to address a401 has just been executed. Suppose also that 3 page faults have occurred since it was first loaded into physical memory. Write the corresponding page table entry for the page, in terms of a diagram and in terms of binary and hexadecimal numbers.
5. What is the largest working set (in number of pages as well as number of cells) possible for a PeANUt program before the system starts thrashing? Hint: how many pages must be reserved for VM?

Laboratory Exercises

It is expected that you work through Part 1 as well as Part 2 (up to at least Part 2a) in the supervised lab for this session, and that you continue with Parts 2 and 3 in your own time.

Preliminaries

1. In your comp2300 folder, create a new directory called lab8.
2. Copy the files /dept/dcs/comp2300/public/lab8/* into your lab8 folder.

Part 1: Experimenting with PeANUt Virtual Memory

• Open the file vmfifo.ass. Examine this file (note that there is a copy of the contents of this file at the end of this handout).

• Note that the main program (main) starts at page 2.

• The first eight memory pages are initialised to be swapped in. Look closely at the page table entries.
  • You should see that the entry at a0 (page 0) has a page frame field of zero. This indicates that page 0 is to be placed in page frame zero (slot zero of the eight slots in main memory) initially. Similarly page 1 is placed in page frame 1 initially. In fact, in this initialisation file, the first eight pages are placed in the first eight page frames in main memory.

  • Note that the Present bit is set for all eight pages, while the dirty bit is zero.

  • The Swap Count field has been set for each of the eight pages. Note that page 0 has been given the highest swap count. The page fault service routine will thus consider page 0 to have been in memory longest.

  • The Last Used field has not been set. This is because in this example, the field will not be used.

  • Since there are no entries for the remaining pages, they will all be initialised as 0, and as their Present bits will all be zero, they will not be in main memory.

• Memory locations a40 to a45 are used by the operating system to store information upon a page fault.
  • The first 5 are for saving registers (one might think that the stack might be a more appropriate place to do so, but a problem with this is that the stack itself might not be in real memory itself, thus causing a page fault within the OS page fault trap handler routine...).

  • At a45 (=PgFtNum), the page fault handler, upon trap #11, writes the page number corresponding to the memory access causing the page fault.

• Memory locations a46 to a77 are initialised with a page fault service routine (plus memory locations for bit masks). The job of the page fault service routine is to swap pages between main memory and secondary memory. When a page that is not in main memory is needed, this routine is called. The routine must swap the desired page into main memory and if necessary swap another page out to make space. This routine is designed to operate on the FIFO principle (First In First Out). The oldest page should always be thrown out to make space. Examine the code, reading the comments carefully.
  • The while loop finds the oldest page table entry. The index register is used to move through the table step by step. Notice that the search begins at page table entry number 2. This is because pages 0 and 1 hold information that is used whenever there is a page fault, so we must never swap either of these pages out. Really this routine is finding the third oldest page, not the oldest. The third oldest page should have a Swap Count field equal to 5 (7-2, the oldest page will have a Swap Count field equal to 7).

  • In the condition evaluation for this loop, a bit-wise and instruction is used; the effect of this is to zero-out all bits in the accumulator (AC) except those corresponding to the Present bit and the Swap Count.

  • Below this, AC is compared with the data at SwCtOPr, which is what the Present bit and the Swap Count fields should look like for a page table entry for a page that is present and has a swap count of 5.

  • Thus in this loop, if one of the pages has a swap count of 5, then the end of the page table should never be reached.

  • In the PT[PgFtNum] = (PT[XR] & FramMsk); code, a page table entry is set up for the page to be swapped in. Remember that PgFtNum (at address a45) holds the number of the page to be swapped in. The page table entry PT[XR] is that for the page to be swapped out; it thus holds the frame number for the new page. This code then puts the frame number (all other fields are set to 0, from the and instruction) into the page table entry for the new page, in preparation for the trap #12.

  • The <swap out page XR>; code places the index register value into the AC. Now the AC holds the number of the page to be swapped out. Then it calls trap #13, which removes a page from main memory. The page that gets removed is the one whose number is in the AC.

  • The putchar('A'+XR); code writes a character which corresponds to the page number. If page 0 was swapped out, the letter A is output. If page 4 was swapped out, the letter E is output. This is designed to help the user see what is happening when the page fault service routine is called. Usually it would not be desirable for the page fault service routine to output data; after all, it is supposed to be invisible to the user.

  • The <swap in page PgFtNum>; code loads the contents of PgFtNum into the AC. Now AC holds the number of the page to be swapped in. The next instruction calls trap #12, which swaps in the page corresponding to the number in the AC.

  • The code corresponding to the next two putchar() calls outputs a character corresponding to the page just swapped in, followed by a line-feed (new line).
  This service routine is different from a normal trap handler routine in the following ways:
  1. the registers (AC, XR etc) are saved by the PeANUt machine upon entry and restored upon exit (ret) automatically
  2. the routine does not need to be explicitly established (via trap #9)
  3. if a page fault occurs within the routine (which can occur on the slightest error!), the PeANUt machine aborts immediately (note however that it is problematic for any trap handler routine to generate the same trap as it is servicing).

• Memory locations SwPrMsk to FramMsk hold the bit-masks used in the page fault service routine.

• The following memory locations (which happen to begin from address a100, i.e. in page 2) comprises the main program. This is what will be executed when execution begins. This program is very simple, and just consists of a loop that reads data from memory locations a0, a40, a80, ... up to the end of memory. The only purpose of such a program is that it accesses every page in memory, and so gives the page fault service routine a good workout.

• Assemble and link vmfifo.img via the commands (on a Linux host!):

      assemble vmfifo.ass
      join vmfifo.rel

• To start up PeANUt simulator in VM mode, execute the commands:
  setenv PeANUtRC /dept/dcs/comp2300/lib/.peanutrc.vm.ass
  Peanut &
  The first command sets up the PeANUt for such an exercise: sets both memory view areas to Address for addresses and Mnemonic for the contents. Go to Setup and choose Virtual Memory Mode. Virtual memory mode will be activated when you next initialise the PeANUt (note: you will need to disable Virtual Memory Mode if you want to use normal mode later).

• Now load and run vmfifo.img. Examine the output.

• Now set a Breakpoint at the instruction at the entry to the page handler routine (a46). Note you must use the Secondary Memory window to set the breakpoint. Run the program again. At the first time execution enters the handler routine, you will notice that page 1 is already dirty. Noting that the main program has no store instructions, why is this? (hint: compare page 1 in Main memory with that in Secondary memory).
  Continue running the program between the breakpoints, perhaps using the step and animate facilities of the PeANUt tool to trace the execution inside the page fault service routine. Also look at the VMMStats at each break point: this nicely `decodes' the page table into its constituent fields.
  Can you see why the program has produced this output? Hint: on what page is the main program? Check your answer with your tutor.
• Run the program in virtual memory mode from the command line (this is a lot quicker!):
  execute -vmm vmfifo.img
  Note that you can also use the -trace option for debugging.

Part 2: Further Experiments

The page fault service routine in vmfifo.ass is rather simplistic in a number of ways. There are a number of steps that can be taken to improve the page fault service routine.

Part 2a: Locking in Further Pages

As explained earlier, the page fault service routine of vmfifo.ass ensures that pages 0 and 1 are never swapped out (see definition of FstULPg). This is very important, because if either of those pages were swapped out, the PeANUt would not be able to either access the page table or call the page fault service routine, and so would come to a grinding halt very quickly. If you are unsure about this, try redefining SwCtOPr to have the same value as SwPrMsk, and FstULPg to 1 (or 0), and then see what happens.

One of the limitations of the page fault service routine of vmfifo.ass is that it only has 26 memory cells of page one to fit into (the first six cells of page one are used to store registers and the number of the page to be swapped in). This space restriction means that the routine must be kept simple.

• Make a copy of vmfifo.ass and call it vmfifoa.ass. Open vmfifoa.ass with your favorite text editor.

• Modify the page fault service routine so that it never swaps out page 2 (as well as pages 0 and 1). Note that you will probably have to redefine the data for SwCtOPr, as now the maximum value of the Swap Count will be reduced.

• Test vmfifoa.ass. You should find that page 2 never gets swapped out. What is the advantage, what is the disadvantage in locking in three pages rather than two? Hint: run both programs and compare VMMStats at the end of each run.

Part 2b: Using the Dirty Bit

You may have noticed that the Dirty bit has been largely ignored until now. In the <swap out page XR>; code, the page to be removed is copied from main memory to secondary memory (trap #13). This is necessary because something may have been written to that page since it was swapped in and that information should not just be thrown away. In fact, often pages are swapped out that have not had anything written to them. Remembering that on real systems, reading and writing between main memory and secondary memory is very slow, a lot of time could be saved if pages were only written back to main memory when really necessary.

The dirty bit is provided for just this reason. If a page is dirty it should be written back to main memory, otherwise it can be discarded (because the copy in main memory is identical). Now that page three is locked in, you should have enough space to add lines to the page fault service routine that check the dirty bit before writing the page back.

• Make a copy of vmfifoa.ass and call it vmfifob.ass. Open vmfifob.ass with your favorite text editor.

• Modify the page fault service routine to check the dirty bit (this should involve adding a few lines, including an if statement guarding the call to trap #13). Insert code to implement putchar('*'); in this if statement, to signify when the trap #13 was called.

  Your routine should not write pages back unless it is dirty. Note that a loadxr instruction may now be needed in the code before putchar('A'+XR);. Note also that if the page is dirty, the putchar('*'); occurs before this. Also note that if trap #13 is not called, PT[XR] must be explicitly zeroed by the handler (to signify it has been swapped out).

• Modify the main program so it writes values back into even numbered pages 4, 6, 8, 10, ..., 30. (so the dirty bits get set for these pages only). Make sure you don't write into pages 0, 1 or 2, as you would overwrite the page table, page fault handler or the main program!

  Note that it does not matter what values you write or where in the page you write them (for the purpose of this exercise or its automated marking). It is important though that only the hander routine produces any output (trap #3).

• Test your program. Check that pages 4, 6, 8, etc have been updated (these pages start at addresses a400, a600, a800 etc in Secondary VMMStats that only 11 pages have been written out.

• Once working, do a final correctness check on it and the previous program with the command:
  previewAutoMark lab8 vmfifoa.ass vmfifob.ass
  When satisfied, submit it using the submit command:

      submit comp2300 lab8 vmfifoa.ass vmfifob.ass
      submit comp6300 lab8 vmfifoa.ass vmfifob.ass

  This is due by 10am Tuesday May 20 (the deadline is strict) and will contribute up to 1% of your Tute/Lab mark.

Part 2c: Different Paging Policies

So far you have only looked at the FIFO paging policy. The program vmlru.ass is very similar to vmfifo.ass, except that it relies on the LRU (Least Recently Used) strategy and so uses the Last Used field of the page table entries. Note that it initializes the poage tbale so that page 0 is least-recently used.

• Experiment with vmlru.ass. This is very similar to vmfifo.ass, except that it relies on the LRU (Least Recently Used) strategy and so uses the Last Used field of the page table entries. Compare the operation (and resulting performance) of the LRU algorithm with FIFO.

• For this example, redefining FstULPg to 1 (or 0) alone is sufficient to allow page 1 (or 0) to be swapped out. However, for vmfifo.ass, we needed to change SwCtOPr as well. Why is this?

---

 

Code for vmfifo.ass

; vmfifo.ass: PeANUt assembler file for COMP2300 Lab 8, 2007
;
; This file demonstrates PeANUt Virtual Memory in operation. The paging
; algorithm here is a *basic* FIFO algorithm. This algorithm has the following
; weaknesses:
;	i)  It relies on all page frames being pre-loaded.
;	ii) It always writes back (no Dirty bit check).
; The program included here accesses each page in memory.
; As it accesses pages not swapped in, page faults occur. 
; As each page fault occurs, two characters are printed, a character corres-
; ponding to the page to be swapped out, and a character corresponding to the
; page to be swapped in. Page 0 is represented by "A", Page 1 "B" and
; Page 31 by "`".
;
; The page-fault handling routine starts at a46 (as it must). The test program
; starts at page 2.


; /* Define initial page table contents (pages 0-7 swapped in, remainder out) */
					; 	   /* PT must be at address 0 */
					; volatile short int PT[] = {
PT:	data %00000 000 111 0 1 000	; 	0x00e8,
	data %00000 000 110 0 1 001	;	0x00c9,
	data %00000 000 101 0 1 010	;	0x00aa,
	data %00000 000 100 0 1 011	;	0x008b,
	data %00000 000 011 0 1 100	;	0x006c,
	data %00000 000 010 0 1 101	;	0x004d,
	data %00000 000 001 0 1 110	;	0x002e,
	data %00000 000 000 0 1 111	; 	0x000f,
					; 
	block 	24			; 	0,0,0,0, 0,0,0,0, 0,0,0,0, 
					;	0,0,0,0, 0,0,0,0, 0,0,0,0
					; } /* PT */ 
			;  /* next 6 memory loc. are reserved for the OS*/
	block	5	;  		/* for saving registers on page faults*/
			;  		/* PgFtNum must be at address 37 = a45*/
PgFtNum:block	1	;  volatile short int PgFtNum;
			;	/*on trap #11, OS puts # of page causing fault*/

			;  /* VM-related macros for PeANUt */
	PageSz	= 32	;  #define PageSz 	32		 /* page size */
	LastPg	= 31	;  #define LastPg 	31 	/* number of last page*/
	SwapOut	= 13	;  #define SwapOut 	13	/* trap # to swap out */
	SwapIn	= 12	;  #define SwapIn 	12	 /* trap # to swap in */

			; 	  /* FIFOPgSwap() must be at address 38 = a46 */
FIFOPgSwap:		;  void FIFOPgSwap(void) { 
			;    /* post: implements a FIFO page swap algorithm   */
	FstULPg	= 2	;  #define FstULPg 2	    /* # of 1st unlocked page */
	setxr	#FstULPg;    short int XR = FstULPg;
FIFOwh:	load	*PT	;    while ( (PT[XR] 
	and	SwPrMsk	;             & SwPrMsk)
	cmp 	SwCtOPr	; 	     != SwCtOPr ) {
	beq  	FIFOewh	;      /* seek PT entry with Swap Count=5 & Present=1 */
	incxr	#1	;      XR = XR + 1;
	load	#LastPg	;      if (XR > LastPg) 
	cmpxr		;         break; /* an error, to be trapped later;... */
	ble	FIFOwh	;                /* ... prevents an inf. loop here    */
FIFOewh:		;    } /* while */
	load	*PT	;    PT[PgFtNum] = (PT[XR] & FramMsk);
	and  	FramMsk	; 	/* fill in frame # of PT entry for new page   */
	store	@PgFtNum; 	/* new page goes to same frame as page to be swapped out */
	loadxr		;    <swap out page XR>;
	trap	#SwapOut; 		
	add	#'A'	;    putchar('A'+XR);
	trap	#3	; 			/*letter corresp. to this page*/
	load	PgFtNum ;    <swap in page PgFtNum>;
	trap	#SwapIn	;    	  
	add	#'A'	;    putchar('A'+PgFtNum); 
	trap	#3	; 
	load	#'\n'	;    putchar("\n');
	trap	#3	; 
	ret		;  } /* FIFOPgSw() */     
			; Bit masks used in page fault service routine.
SwPrMsk:data 	%00000 000 111  0 1 000	; const short int SwPrMsk = 0x00e8,
					;      /*Swap count & Present bit mask*/
SwCtOPr:data 	%00000 000 101  0 1 000 ;                 SwCtOPr = 0x00a8, 
					;  /*Swap count=5 (Oldest), Present=1 */
FramMsk:data	%00000 000 000  0 0 111 ;                 FramMsk = 0x0007; 
					; 		 /* frame number mask */

LstPg:	data	991 	;  const int LstPg = 991; /*addr. of start last page-1*/
			;  int main() {
main:	setxr	#0	;    short int *XR = NULL;	   /* implement via XR*/
			;    do {
mloop:	load	*0	;      <access *XR>;
	incxr	#PageSz	;      XR += PageSz;
	load	LstPg	; 
	cmpxr 		;    } while (XR <= (int *) LstPg);  
	ble 	mloop	; 
	trap	#1	;    exit(0);
	end 	main	;  } /* main() */

---

Copyright | Disclaimer | Privacy | Contact ANU