The runtime estimates given in Q2 include any non-stated accesses. For example, in the case of accessing a valid and non-present page (ii), the given 10000 cycles include checking if the page is present or not, valid or not, deciding that a new physical-page should be allocated and allocating it. But if the Page-Table is full (iii), every iteration to find a victim to evict, adds an additional cost of 100 cycles to 10000 cycles given in (ii), as stated in the instructions for MP2.

In Q3 you are asked to clear the access-bits of entries every 10000 instruction. For simplicity, the cost for this operation can be neglected. (In a real OS, this operation would happen asynchronously and in the background; we've made it synchronous and deterministic to simplify grading; disregard its overhead as a real OS would not incur it.)

Such a page table will have 2^20 entries, no matter how many of those pages the program uses. It doesn't matter if the program has just 1, 10, or 2^20 pages mapped. When the OS goes to service a page fault, it'll dereference into the giant array that is the page table,and look up a single entry to see if that entry has the V bit set. So that PTE (page table entry) must necessarily be present; or else the OS would not know whether the access is legal or not without further lookups. Ergo, all 2^20 entries must be present. Size of the page table is 2^20 times the size of a PTE.

Answer: it has to hold the corresponding physical frame number, some number of protection bits,V and P bits. So,20 bits for the physical page frame number, +3 bits for RWX, +2 bits for V and P. That yields 25 bits. A real system will round this up to 32 bits to simplify the math of looking these PTEs up. So such a page table will take up 2^20 * 32 / 8 = 2^22 bytes, 2^12 KB, 2^2 MB, 4 MB.

Note that there are two subtleties involving 2-level page tables. First, the whole point of a 2-level page table is that, if a contiguous range that happens to fall into a 2nd level page table happens to be all invalid, then the range can be marked invalid at the root page table, and the 2nd level entries can be omitted. This is how two level page tables offer space savings over single-level page tables. Second, 1st level entries in a 2-level page table hold pointers to memory (i.e. virtual addresses for the bases of 2nd level page tables, NULL if the whole range is invalid), 2nd level page tables hold the PTEs (with physical frame numbers plus protection bits etc) at the leaves. So the size calculation for 2-level page tables will have to take into account this nonuniformity.

As you can see from the traces, pointers are 32 bits. So first level page tables have to contain at least 32 bits, and 1 extra bit to indicate valid/invalid. But, remember that most operating systems are mapped to someplace in high viratual memory. In this case, you may assume that the OS memory resides between 0x80000000 and 0xffffffff. Ergo, the first bit of a 32-bit 1st level page table entry can act as a valid/invalid indicator. If it's 0, it's invalid, if it's 1, it's valid and the whole 32 bits, taken together, form a pointer to the base of a 2nd level page table.

No. The access bit is managed by the MMU and turned on only when that PTE is used to translate a virtual address issued by the CPU. The act of examining a PTE is very different from the act of using a PTE to perform a virtual to physical address translation. The latter will flip the access bit, while the former will not.

This confusion may be stemming from the use of the English word "access." In the case where the eviction code is examining PTEs, it is true that the OS is, in the literal sense of the word, accessing PTEs (and thus incurring the cost of accessing them). But since the PTE is not used to perform a virtual to physical translation by the MMU, the access bit is not going to be turned on. The "access" bit has particular semantics associated with it that should not be confused with the common use of the English verb.

Yes, we had a FAQ entry that simplifies life for everyone, but complicates the mental model you'll need to have. But since you asked, let's describe what should really happen. Touching memory is expensive. Reading a PTE incurs a cost, even if the PTE is being read to see if it is valid or not. A full OS would therefore want to avoid iterating through the invalid PTEs, and to do this, it would keep a linked list of all pages that are actually mapped as valid. Ergo, it would not have a simple iteration through all PTEs numerically, as your code does now, and retrieve only those PTEs that it knows are valid.

So far so good. The previous FAQ entry allowed you to perform a shortcut that turned out to be technically correct, yet pedagogically terrible. Even though your Python code was touching PTEs with the valid bit set to False, we let you not incur the cost of touching those PTEs because a real OS would skip over them and only process PTEs where the valid bit is True. So, the FAQ was helpful, the outcome was technically correct, but there was room for a student to misunderstand what was going on, and in any case, the mental model one had to build for everything to be crystal clear was too complicated. The course staff knows exactly how MMUs work, so things that seem simple and sensible to us are not necessarily straightforward to students learning this material for the first time. So we've decided to simplify the cost model, and have deleted that FAQ entry. If you understand how page management works, the difference is tiny; if you don't, then the opportunity for you to develop an incorrect mental model is now ruled out.

TL; DR: The course staff allowed realistic optimizations that unfortunately complicate the mental model a student needs to develop, then decided that this might leave some students confused, and have now simplified how you need to account. Follow the instructions and it'll all be fine. If you're in the 85% of the class that did not see the now-deleted FAQ entry, you can skip over this discussion. If your solution depends on that FAQ entry, we'll accept it (though it'd be best to change it so it's in line with the simplified accounting -- deleting one extra line is all it should take to go from the old accounting to the new one).

Your pen and pencil technique doesn't scale up, and more importantly, there is a lot to learn from actually building a two-level page table simulator. We'll take your simulator, evaluate the code for correctness of the simulation, and put different programs through it. So Q4 really has two parts, the main task is to build a two-level page table simulator. A side effect (and sanity check on the correctness of your calculations) is to create the bar chart that is being asked in the second part.

The zip file that you are returning should contain one PDF file, named report.pdf (please do NOT use different names like MP2report.pdf) and two directories named 1level and 2level. The report should contain all the graphs and the explanations you want to write to questions. The directories should contain only your python code. Any non-python file under these directories will be discarded. Please do not include the trace files in your ZIP file!