OS Self doubt Memory management

Question

Suppose that a machine has 42-bit virtual addresses and 32-bit physical addresses.

{a} How much RAM can the machine support (each byte of RAM must be addressable)?

{b} What is the largest virtual address space that can be supported for a process?

{c} If pages are 2 KB, how many entries must be in a single-level page table?

{d} If pages are 2 KB and we have a two-level page table where the first level is indexed by 15- bits, then how many entries does the first-level page table have?

{e} With the same setup as part {d}, how many entries are in each second-level page table?

{f} What is the advantage of using a two-level page table over single-level page table?

Answer 1

(a) Physical address is 32 bit . So , at most $2^{32}=4$ GB  RAM the machine can support .

(b) Virtual address space size =42 bit . So The machine can support at most $2^{42}=4$ TB  virtual memory the machine can support .

(C) Page size = $2$ KB .So No of entries in single level page table = $\frac{2^{42}}{2^{11}}=2^{31}$.

(d) If pages are $2$ KB and we have a two level page table where the first level is indexed by 15 bits , then there should be $2^{15}$ entries in the first level page table .

(E) With the same set up , second level page table is indexed by $(42-11-15)=16 $ bits .which implies second level  page table have =2^16 entries .

(f)  For this we use the same set up .

Virtual address space = $42 $bits = $4 $TB

Page size =$2$ KB .

So no of pages , $\frac{2^{42}}{2^{11}}=2^{31}$ .

Assuming page table entry =$4$ B 

Now if say you need just a single page out of this $2^{31}$ pages in single level page table you need =$2^{31}*4 B=8 GB$ size page table .

But if you multilevel page table ,

you need the outer level page table which has $2^{16}$ entries so outer level page table size =$2^{16} *4 =256$ KB 

and one page table which our required page reside which has $2^{15}$ entries , so inner page table size =$2^{15} *4 =128$ KB  

So total memory required for page table $(256+128)=384$ KB .

Can you see the difference now as if we use single level page table it would take $8$ Gb where as in 2 level page table it just required $384$ KB .

similar problem :- https://stackoverflow.com/questions/29467510/how-does-multi-level-page-table-save-memory-space

Comments

@Kabir5454

Yes, agreed.

But in general that’s the disadvantage only right as there is a dependency on  the TLB and Cache for its effectiveness. 

---

You can say that but the advantages are more in case of MLP than SLP.

---

okay , got it.

Thanks bro:)

Answer 2

a) Maximum Memory Size = Largest Physical Address Space = $2^{32}B$

b) Largest Virtual Address Space = $2^{42}B$

c) Page Size = $2KB$ = $2^{11}B$,

Number of Pages = $\frac{Virtual\ Address\ Space}{Page\ Size}$ = $\frac{2^{42}}{2^{11}}$ = $2^{31}$

d) First Level Index Bits = $15\ bits$,

so, each first level page table will hold $2^{15}$ entries of page table entries.

e) Offset = Bits require to identify each word in a page = $11$ bits.

Second Level Index Bits + First Level Index Bits + Offset = Virtual Address Size.

Second Level Index Bits = Virtual Address Size – Offset – First Level Index Bits = $42\ –\ 11\ – \ 15$ = $16\ bits$.

so, each second level page table will hold $2^{16}$ entries of page table entries.

f) When a process is using a single-level page table, it will use the entire logical address space of the operating system.

To be precise, we have $2^{31}$ number of pages in this system. A single-level page table will use all of those pages for each process. A process may require only $2^{10}$ number of pages, but it has to declare the entire single-level page table.

Processes may not require that large number of pages, maybe the process is very small. As a result every process require a large size of constant page table in single level page table, which will be sometimes even larger than the process size.

Let $e$ = Page table entry size = $2\ bits$,

Page Table Size in Single Level Page Table = $2^{31}*e$ = $2^{31}*2\ bits$ = $2^{32}\ bits$.

So, what is the solution?

Divide the paging into multiple levels, so we don't need to use all the pages in the logical address space if not required. When a process need only 2^10 pages, we can fit that only in the single page table in the first level. As only one page-table on the first level is required, it will need only one entry in the second level page table.

Page Table Size in total for the above mentioned process= One First Level Page Table Size + One Second Level Page Table Size = $2^{15}*e$ + $2^{16}*e$ = $2^{15}*2\ bits$ + $2^{16}*2\ bits$= $(2^{16} + 2^{17})\ bits$ = $3*2^{16}\ bits$. (This is very less in size than a single level page table).

Comments

@DebSujit

bro , you interchanged VA and PA bits, kindly correct it.

---

@Pranavpurkar thanks, corrected.

---

i want to add image to a question. But couldn’t add local image, downloaded one, asking URL. Can you please say how to ask image based question?

---

@legacy Image → Upload → Choose File → Send it to server.