Problem Set Answers: Virtual Memory

1. 1. frame	time
      	1	2	3	4	5	6	7	8	9	10	11	12	13	14
      0	T	T	T	T	Q	Q	Q	Q	P	P	P	P	P	P
      1		S	S	S	S	T	T	T	T	T	T	R	R	R
      2			R	R	R	R	R	S	S	S	S	S	Q	Q

      There are a total of 9 page transfers.

   2. frame	time
      	1	2	3	4	5	6	7	8	9	10	11	12	13	14
      0	T	T	T	T	T	T	T	T	P	P	P	P	Q	Q
      1		S	S	S	S	S	S	S	S	T	T	T	T	P
      2			R	R	R	R	R	R	R	R	S	S	S	S
      3					Q	Q	Q	Q	Q	Q	Q	R	R	R

      There are a total of 10 page transfers.

2. 1. frame	time
      	1	2	3	4	5	6	7	8	9	10	11	12	13	14
      0	T	T	T	T	T	T	T	T	P	R	R	R	R	R
      1		S	S	S	Q	Q	Q	S	S	S	S	S	S	P
      2			R	R	R	R	R	R	R	T	T	T	Q	Q

      There are a total of 9 page transfers.

   2. frame	time
      	1	2	3	4	5	6	7	8	9	10	11	12	13	14
      0	T	T	T	T	T	T	T	T	T	T	T	T	T	P
      1		S	S	S	S	S	S	S	S	S	S	S	S	S
      2			R	R	R	R	R	R	R	R	R	R	R	R
      3					Q	Q	Q	Q	P	P	P	P	Q	Q

      There are a total of 7 page transfers.

1. There are 10 rows in the page table so there are 10 pages in the process, pages 0 through 9.
2. In row 6 of the page table the valid bit is 0, so page 6 is not in memory.
3. In row 2 of the table the valid bit is 1, so page 2 is in memory in frame 0.
3. 1. 1MB = 2²⁰, 2K = 2¹¹, so the number of pages is 2⁹
   2. 9 bits are needed.
   3. There are 16 = 2⁴ page frames, so the number of bits needed is 4.
   4. 2K = 2¹¹, so 11 bits are needed.
   5. Virtual address is 20 bits (9 + 11).
   6. Physical address is 15 bits (4 + 11).
   7. The page table has one entry for each page, so there are 2⁹ entries.
   8. 4AC2₁₆ = 100 1010 1100 0010₂ is in page 9 (1001) which is stored in page frame F (1111). Thus the physical address is 111 1010 1100 0010₂ = 7AC2₁₆.
   9. 29D5F₁₆ = 10 1001 1101 0101 1111₂ is in page 53 (101 0011) which is listed as invalid, so the page is not in RAM.
   10. 1A00B₁₆ = 1 1010 0000 0000 1011₂ is in page 34 (11 0100) which is stored in page frame 0 (0). Thus the physical address is 1011₂ = B₁₆.
4. 1. The process has 16MB = 2²⁴ of virtual memory with pages of size 1024 = 2¹⁰. Therefore there are 2²⁴ / 2¹⁰ = 2¹⁴ pages, so 14 bits are needed to specify the page number.
   2. The physical memory is 2MB = 2²¹ bytes, which is divided into frames of size 2¹⁰, so there are 2¹¹ page frames, which requires 11 bits to select the frame.
   3. A page/frame contains 1024 = 2¹⁰ bytes. so 10 bits are required to specify the offset.
   4. There are 16MB, or 2⁴*2²⁰ addresses, so we need 24 bits for a virtual address.
   5. Main memory is 2MB, or 2*2²⁰, so we need 21 bits for a physical address.
   6. There are 2²⁴/2¹⁰ pages in virtual memory, so the page table has 2¹⁴ entries.
   7. 1524 is on page 1 (page 0 contains addresses 0=1023, page 1 contains 1024 - 2047), located at offset 500. Page 1 maps to frame 2, so 1524 maps to physical address 2548. You can also find the binary equivalent of 1524 (0000 0000 0000 0101 1111 0100) and divide it into two pieces: the first 14 bits are the page, and the last 10 are the offset. Replace the first 14 bits (00 0000 0000 0001) by (00 0000 0000 0010), to get the physical address 0000 0000 0000 1001 1111 0100, or 2548.
   8. Physical address 1024 is at offset 0 in frame 1. Virtual page 0 maps to frame 1, so this is virtual address 0.
5. 1. Possible, 5ns (TLB access) + 12ns (cache access)
   2. Possible, 5ns (TLB access) + 25ns (page table reference) + 12ns (cache access)
   3. Possible, 5ns (TLB access) + 25ns (page table reference) + 12ns (cache access) + 25ns (main memory reference)
   4. Not possible (the cache value would be stale if the page no longer resides in page table)
   5. Possible, 5ns (TLB access) + 25ns (page table reference) + 200ms (disk reference) + 5nx (TLB, since access is restarted) + 12ns (cache hit)

---

Email Me | Office Hours | My Home Page | Department Home | MCC Home Page

© Copyright Emmi Schatz 2013