# Explore the workings of virtual memory, specifically the TLB and the Page Table

## Process for Virtual Memory

## TLB(Translation Lookaside Buffer) Operation

## EX1
{%youtube kAvuqYt8psw %}
***CAMERA Virtual Memory and Paging Simulator***

Click the button labeled “Auto Generate Add. Ref. Str.” at the right-hand side of the window. This will generate a set of ten address references. Click the button labeled “Next” to begin the simulation.

For the rest of this exercise you are at the mercy of the “PROGRESS UPDATE” box. After each click of the “Next” button examine the contents of the box and the current state of the memory system. Try to really get an understanding of what is going on in the TLB, the Page Table, and Physical Memory at each step.

### Q1. Given the way the address was broken down, how big are the pages in this model?
There are 5 bits for the offset, hence a page contains 2^5 words, it's 128 bytes.

### Q2. How many TLB Hits and Misses did we have for the randomly generated set of ten addresses? What about for Page Hits and Page Faults?
We randomly generate 10 addresses for memory access, the set of addresses are <code>B1, 2C, 41, 11, 5D, 9B, B6, FB, 22, A6</code>. There are 2 TLB hits and 8 TLB Misses.

We found out that whenever a TLB miss happens, a page fault also happens. So there are totally 8 page faults and 0 page hit.

### Q3. Did you have any Page Hits? Explain why. Can you think of a set of ten addresses that would result in a Page Hit?
There is no page hit in this set of ten addresses, and we think there are two kinds of reasons that may cause the page fault.

*The first one is due to first time accessing.*
Since a page may never been access by CPU before, then it must cause a page fault when first time being loaded into the memory.

*Second one is due to the limited size of physical memory.*
Even though a page may has been accessed before, it means that be loaded from disk to physical memory and the valid bit of that row in page table is once turned into 1.

But later when there is no empty space available in pyhsical memory and other pages need to be loaded into pyhsical memory, some former used pages must be replaced and the valid bit in page table turn back to 0.

After that if we want to access the replaced page, it will cause a page fault when lookup th page table since the valid bit of that page is 0, and we need to load it form disk into pyhsical memory again.

Under the design of architecture in this simulator, there is no way to find a set of addresses which will arise a Page Hit. Since the number of rows in TLB are the same as the number of frames in physical memory and the page replacement policy is fully associated.

### Q4. Explain the process by which we turn a virtual address into a physical address for the very first access (emphasizing on TLB Misses and Page Faults).
1. Use the page number to lookup the TLB, if there is a match then we get the physical page number; if not, then it's a ***TLB Miss*** and we go to <code>2.</code> to lookup the page table for the translation.

2. Use the page number to lookup the page table, if the valid bit is 1 for the matched frame number, then we can get the mapped physical frame number; if not, it means the page we want is not in the physical memory and that raises a ***Page Fault***. Then we need to load the page from disk to physical memory.

## EX2
Now that you’ve seen what a random workload looks like in the VM system let’s try creating a custom workload with a specific property. Your goal for this exercise is to create a workload of ten memory accesses that will cause ten TLB misses and ten Page Faults. You should be able to come up with such a workload on paper, but then you should run it in CAMERA to verify your work. You can specify a custom workload in CAMERA by clicking the button labeled “Self Generate Add. Ref. Str.” and entering in the addresses you want to reference one at a time.

### Q. Demonstrate that your ten memory accesses results in ten TLB Misses and ten Page Faults. Explain why such behavior occurs.

To occur 10 TLB Misses and 10 Page Faults, input virtual page shouldn’t be same one of saved page numbers in TLB. Then each time when put data, TLB Misses and Page Faults will occur.

#### A list of address reference strings:
* 20, 40, 60, 80, A0, C0, E0, 20, 40, 60

| | 1 |2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| ----- | -------- | --- | --- | --- | --- | --- | --- | --- | --- | -------- |
| Hex | 20 |40|60|80|A0|C0|E0|20| 40 | 60 |
| Bin | 0010 0000|0100 0000|0110 0000|1000 0000|1010 0000|1100 0000|1110 0000|0010 0000|0100 0000|0110 0000|


#### Result:

#### Why:

To occur 10 TLB Misses and 10 Page Faults, any TLB Hit should not be occur. If TLB Hit occurred, then the system doesn't check page table so that Page Faults doesn't occurr. Therefore, we made a list of address reference strings which those virtual page numbers do not overlap in TLB.
In the input list, virtual page numbers increase by 1 for each next element, then TLB Hit never happen and both TLB Misses and Page Faults will be 10.

## EX3
Given your sequence of memory accesses from Exercise 2, can you find a change to a single parameter (e.g. TLB size, page table size, memory size, etc…) that would result in the same number (ten) of TLB misses but result in fewer than ten page faults?

### Q. Explain the single parameter change that would result in ten TLB misses, but fewer than ten page faults.
From the observation in the previous sections, we found that whenever we have a TLB miss, it will always cause a Page Fault. That is because under the design of the architecture of this simulator, the number of rows in TLB are the same as the number of frames in physical memory and the page replacement policy is fully associated, hence the recorded page in TLB and physical memory are actually synchronized. Then if a page is not founded in TLB, it will also not show up in the physical memory. Whenever a TLB Miss be raised, it will result in a page fault directly.

So if we can change one single parameter in this architecture, we choose to reduce the size of TLB to make the number of row in TLB smaller than the number of frames in physical memory. It will raise the TLB Misses to 10 times but in return the Page Hit will be increased to 2 times.

## EX4

We used VMSIM, another Virtual Memory simulator, to create this question. You have two options for this exercise.

Watch this webm of a VMSIM simulation.
Use the appletviewer command in your Terminal like so (doesn’t work on Hive):
$ appletviewer https://denninginstitute.com/workbenches/vmsim/vm.html
Observe what is happnening and answer the following questions:

What is different about the setup of the system in this question as compared to the setup in CAMERA? In particular, what are P1, P2, P3, and P4? If you watch closely you’ll see that this simulation reports a much higher percentage of TLB misses than random runs on CAMERA did. Why might this be? (If you have trouble following the simulation, use the appletviewer and turn down the speed using the slider on the bottom right.)


{%youtube ZVY6JW1XP2o %}

### Q1. P1, P2, P3, and P4?
> In the virtual memory simulator, those Ps indicate multi-processors. In other words, there are Processor1 to 4 in the simulator. The processors occupy their own page tables but they use one shared memory, thus they cannot access the shared memory at the same time.

### Q2. Why there is a much higher percentage of TLB misses in this simulation than random runs on CAMERA did?
> In CAMERA simulator, there is only one processor used, so TLB(Translation Lookaside Buffer) can be updated but never be reset. In this case(VMSIM) with multi-processors, however, TLB is reset when a processor sleeps and another processor begins. As a result, because TLB is flushed when processors are changed TLB misses occur very often. (less chance of TLB Hits)

#### Problem
> Each processor has seperate table page. Therefore, when inter-process Context Switching occurs TLB should be flushed and save new data. This process brings a big performance degradation.

#### Solution
> To solve the problem, ASID(Address Space Identifier) can be used instead of using TLB flushing. It can allocate identifier for processors, so that TLB doesn't need to be flushed when processors are switched.


## Appendix
### Page replacement
> If there is no empty space in memory, removes one memory frame and occupies, and then updates all of tables with new information.

>In the VMSIM, LRU(least-recently-used) is used.