Paging
Operating Systems Lab Class 8
In this lab session we will build a virtual memory system in software based on paging. We will see how address translation and a translation look-aside buffer (TLB) work.
The following figure is to recall the translation process in paging with TLB.
1 Getting Started
1. Download the os-lab8.zip archive from Study Direct and unzip it into your workspace.
2. Start NetBeans and open the project. The project should contain four files in the src directory:
Paging.java (contains the main method), TLB.java, and PageTable.java.
3. Before you begin, read through the code and then compile it before making any modifications. This should work without problems.
1
2 Implementation
The program will work as follows. Running
java Paging 1234 1 4 2 0 1 4 1 9 1
• uses seed 1234 to randomly initialise the page table
• uses 21 TLB entries
• uses 4-bit logical and physical addresses (for simplicity we assume the same bitwidth for
both)
• uses pages of size 22
• and translates the sequence of logical addresses 0, 1, 4, 1, 9, 1.
and will produce the following output:
Page table:
00: 00
01: 01
10: 11
11: 10
TLB: xx
xx
Logical address: (0) 0000
Lookup page number (0) 00
TLB Miss!
Found frame number (0) 00
0000 –> 0000
0 –>0 TLB:
00: 00 x:x
Logical address: (1) 0001
Lookup page number (0) 00
Found frame number (0) 00
0001 –> 0001
1 –>1 TLB:
00: 00 x:x
Logical address: (4) 0100
Lookup page number (1) 01
TLB Miss!
Found frame number (1) 01
0100 –> 0100
4 –>4 TLB:
00: 00 01: 01
Logical address: (1) 0001
Lookup page number (0) 00
Found frame number (0) 00
0001 –> 0001
1 –>1
TLB:
00: 00
01: 01
Logical address: (9) 1001
Lookup page number (2) 10
TLB Miss!
Found frame number (3) 11
1001 –> 1101
9 –> 13
TLB:
10: 11
01: 01
Logical address: (1) 0001
Lookup page number (0) 00
TLB Miss!
Found frame number (0) 00
0001 –> 0001
1 –>1
TLB:
00: 00
01: 01
TLB hit rate: 0.33333 means we find the desired page number in the TLB 33.33% of the time The effective memory-access time: 166.66 ns
4. You have to fill in gaps in all three files.
• Paging.java contains the main method, which parses the command line parameters allo-
cates a PageTable and a TLB and then performs translation of logical addresses passed to the program on the command line into physical addresses in the translate() method. You have to implement the parsing of command line arguments and the translate() method. The implementation of the latter will require the use of bitwise operators (see Section 4). You are provided with a method toBinary() for printing integers as binary Strings.
• PageTable.java has a find() method for returning the frame number corresponding to a given page number. The constructor of PageTable initialises the page table such that each page is assigned a random frame. The only part that you have to complete is the allocation of a page table of correct size.
• TLB.java implements a translation look-aside buffer as a direct-mapped cache, associating the least significant bits with a cache slot. You have to implement the find() and put() methods as well as the computation of the TLB hit rate.
3 Reflection
5. Try to translate different sequences of logical addresses and compare the TLB hit rates. When do you observe high TLB hit rates? When are they low? Repeat the experiment for different TLB sizes.
6. Extra question: Add a method called effectiveAccessTime() to the TLB class that finds the effective memory-access time, assuming the following: (a) it takes 100 nanoseconds to access memory and (b) a page-table lookup takes only one memory access.
4 Java API References
https://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html
Appendix
Paging Example: Suppose we have a system with the following properties:
• 9-bit virtual addresses and 9-bit physical addresses (addressWidth= 9)
• Page size = Frame size = 128 B = 27 B (pageOffsetWidth= 7)
• The mapping between virtual addresses and physical addresses is stored in the following
page table:
TODO: Translate the logical addresses 42 and 372 to physical addresses.
SOLUTION
Logical Address Space = 29 = 512 B, and Physical Address Space = 29 = 512 B
Page size= 128 B = 27 B, thus pageOffsetWidth= 7 bits,
virtualMemoryAddressWidth= physicalMemoryAddressWidth= addressWidth = 9−7 = 2 bits, offset d: the offset field identifies a particular location within page or frame.
Page
Frame
0
2
1
3
2
0
3
1
It is clear from the above figure that Logical Address 42 = 00 0101010 (which is at page 0) has the following Physical Address:
By following the same steps we can get the physical address of the virtual address 372. (ans: 116) You can check for this answer by running: java Paging -253460285 1 9 7 42 372
Page table:
00: 10
01: 11
10: 00
11: 01
TLB: xx xx
Logical address: (42) 000101010
Lookup page number (0) 00
TLB Miss!
Found frame number (2) 10
000101010 –> 100101010
42 –> 298
TLB:
00: 10 xx
Logical address: (372) 101110100
Lookup page number (2) 10
TLB Miss!
Found frame number (0) 00
101110100 –> 001110100
372 –> 116
TLB:
10: 00 xx
Another Solution: using long division:
physical address= frameNumber × pageSize + offset= 2 × 128 + 42 = 298
physical address= frameNumber × pageSize + offset= 0 × 128 + 116 = 116