CPSC 418: Solution 7

Home

Problem 1

An unassigned physical page is detached from the freelist, its address is then assigned to a logical page for the process. The appropriate page table entry is updated in the pagetable and the valid bit (of the protection bits) is set to valid.

Problem 2

Virtual-address to physical-address in paging scheme

A pagetable entry (PTE) is selected based on the logical page number (LPN) (the upper bits of the virtual address). If the valid bit in the PTE is not set, then a page fault occurs. If the valid bit is set then the page is in memory and the virtual-to-physical address translation proceeds. The physical address is the physical page number (PPN) from the PTE and the index into the page from the virtual address.

Problem 3

Hardware resources:

Root page table register.
A small amount of misc hardware to combine pagenumbers and indices to create addresses.
If there are multiple page sizes (e.g. DEC Alpha), then a size register is needed to hold this information.

Software functionality:

Freelist manipulation and management.
Pagetable data structure (one per process).

Problem 4

Increasing page size
Advantage:

Reduced storage space for pagetables (there are now fewer entries in the pagetable).

Disadvantage:

Increased wasted space in the last page of each region of memory for a process (heap, stack, etc), because the amount of memory needed for a region may not be an integral number of pages (internal fragmentation).

Decreasing page size
Advantage:

Reduced internal fragmentation.

Disadvantage:

Increased amount of memory for pagetables, because there is one entry for every virtual page.

Problem 5

The problems of segmented and flat-paging systems are avoided by subdividing segments into pages. More specifically:

Fragmentation is reduced: all pages are the same size and processes request memory in one-page increments.
Pagetables are smaller: large contiguous blocks of unused pages do not require PTEs.

Problem 6

Any valid logical address must be able to be translated into a physical address. This is done by traversing pagetables to translate virtual page numbers to physical pagenumbers. One or more of the pagetables, or the page itself, may not be in physical memory (i.e. it may be swapped out to disk). If a page is swapped out to disk, the valid bit in the PTE for the page is `false' and the bits normally used to store the physical page number store the block number of where the page is stored on disk.

The root pointer (see diagram of Problem 2) or PTBR (Page Table Base Register) points to the highest level page table. The PTBR always stores a physical address, and so the highest level table cannot be swapped out.

Problem 7

(Part 7a)

Index Bits

Index-into-page	13 bits
Page protection permission	13 bits
Level-one-index	8 bits
Level-two index	11 bits

Detailed Explanation:

          Virtual address
           -------------------------------- 
          | Index_1 | Index_2 | Word Index |      32 bits 
           --------------------------------

8kB/page ==> (2^3)(2^10) = 2^13
Therefore, 13 bits are for the word index.
Index_1 and Index_2 point to PTEs in page tables.
PTEs have 32 bits/entry or 4 bytes/entry.
Pages are 8kB, and so there are 8kB/4B=2k PTEs per page.
2k entries is 2^1*2^10, so 11 bits are required for the index.
Thus, we initially say that Index_1 and Index_2 are 11 bits each.

But, 11 + 11 + 13 = 35bits, and we only need 32bits, so we have 3 extra bits.
So, we need to make either Index_1 or Index_2 3 bits smaller.
We choose to make Index_1 smaller, because this will result in fewer pages in the pagetables than if we make Index_2 smaller.
This is because the pagetable with the smaller index will not fill its page. It is better to have one unfilled page (the top level pagetable) than many unfilled pages (the lower level pagetables, which are pointed to by Index_2)

Index_1 8 bits
Index_2 11 bits
WordIdx 13 bits

Index_1	8 bits
Index_2	11 bits
WordIdx	13 bits

Protection Bits

Virtual Address	Index1	Index2	WordIdx
Physical Addr	PhysPageNum		WordIdx
PageTable Entry	PhysPageNum		ProtInfo

Index_1, Index_2, and WordIdx are indices into pages. A physical address is a physical page number and a word index. The physical page number comes from the PTE. The virtual address, PTE, and physical address are all 32 bits.

#bits(PhysPageNum) = #bits(PhysicalAddr) - #bits(WordIdx)
#bits(ProtInfo) = #bits(PTE) - #bits(PhysPageNum)
simplifying:
#bits(ProtInfo) =
= #bits(PTE) - (#bits(PhysicalAddr) - #bits(WordIdx))
= #bits(PTE) - #bits(PhysicalAddr) + #bits(WordIdx)

If the PTE and PhysicalAddr are the same size (e.g. 32bits), then:
#bits(ProtInfo) =
= 32 - 32 + #bits(WordIdx)
= #bits(WordIdx)
= 13

(Part 7b)

Root pagetable	1 page
Lower-level pagetables	2^Index_1 pages

The PTEs in the lower level pagetable point to process pages, not pagetables. There are 2^(Index_1*Index_2) process pages, and 2^(Index_1*Index_2*WordIdx) process words, which is 2^32.

Pages in pagetables=
= 1 + 2^Index_1
= 1 + 2^8
= 257

Note: If we had made Index_1 11 bits and Index_2 8 bits, we would end up with 2^11, or 2048 pages in the pagetables.

(Part 7c)

The minimum amount of memory for pagetables that a process can have is one page for the root table and one page for the lower level pagetable. Each lower level pagetable provides 2^11*2^13 = 2^24 bytes = 8MB of addressable memory.

Size Percentage pages in pagetables
500kB 0.80 2
2MB 0.10 2
10MB 0.05 3
50MB 0.05 8

Size	Percentage	pages in pagetables
500kB	0.80	2
2MB	0.10	2
10MB	0.05	3
50MB	0.05	8

Thus the total number of pages in pagetables is:
= (#Proc)( %Proc_500kB*2 + %Proc_2MB*2 + %Proc_10MB*3 + %Proc_50MB*8 )
= (200)( 0.80*2 + 0.10*2 + 0.05*3 + 0.05*8 )
= 830pages
= 6640kB

Total amount of process memory:
= (#Proc)( %Proc_500kB*500 + %Proc_2MB*(2*1024) + %Proc_10MB*(10*1024) + %Proc_50MB*(50*1024) )
= (200)( 0.80*500 + 0.10*(2*1024) + 0.05*(10*1024) + 0.05*(50*1024) )
= 735,360kb
= 718MB

Total swap space required = pagetables + processes
= 6640kB + 735,360kb
= 742MB

Home

Last modified: 05 March 96