Jyotiprakash's Blog

Problems in Virtual Memory

Jyotiprakash Mishra's photo
Jyotiprakash Mishra
·

7 min read

  1. Virtual to Physical Address Mapping
    Given a system with a virtual memory (VM) size of 16 GB and a physical memory (PM) size of 4 GB, with a page size of 4 KB. Calculate the number of bits used for the page number and the offset within a page. How would you map a virtual address of 0x0003FF800 to its corresponding physical address if the page table entry for the page containing this address points to a frame starting at 0x000FF000?

  2. Page Table Entries Calculation
    A computer system uses a 48-bit virtual address space and a 36-bit physical address space. With a page size of 8 KB, calculate the total number of pages and frames in the system. Assuming each page table entry (PTE) requires 8 bytes, determine the maximum size of the page table.

  3. Multi-level Page Table
    Considering a three-level paging system where the virtual address space is 64 GB and the physical memory is 8 GB. The system uses a page size of 4 KB. Calculate how many bits are needed for the page number and offset at each level of the page table. If a virtual address 0x0F1234500 is given, break it down into its constituent parts according to the multi-level page table. Assume each page table can take a maximum of one page worth of space.

  4. Page Offset and Frame Number
    In a system with 2 MB of physical memory and a 32-bit virtual address space, using pages of size 1 KB, determine the size of the page table. Given a virtual address 0x1A2B3C4D, calculate the page number, offset, and the corresponding physical address if the page table entry for the page containing this address has a frame number of 200.

  5. TLB Hit Ratio Calculation
    Assume a system with a Translation Lookaside Buffer (TLB) that has a 90% hit ratio. Calculate the effective memory access time if the TLB lookup time is 10 ns, memory access time is 100 ns, and the page table lookup time is 50 ns.

  6. Inverted Page Table Calculation
    With a physical memory size of 512 MB and a page size of 4 KB, calculate the number of frames in the physical memory. Given an inverted page table is used, with a page table entry size of 8 bytes, estimate the total size of the inverted page table.

  7. Virtual Address Space Fragmentation
    Consider a system with a 40-bit virtual address space and a 28-bit physical address space, using a fixed page size of 2 KB. If the system has a total of 1 million pages allocated, calculate the fragmentation in the virtual address space and the percentage of the physical address space used.

  8. Page Replacement Algorithm Impact
    A paging system has 3 frames. If the sequence is 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, and the system starts with an empty frame table, calculate the number of page faults that occur using both FIFO, LRU, and OPT page replacement algorithms.

  9. Shared Pages Between Processes
    Two processes, A and B, share a common library loaded into physical memory, which occupies 10 pages. Given a system with 1 GB of physical memory and a page size of 8 KB, calculate the percentage of physical memory saved by sharing this library between the two processes instead of loading it separately into each process's address space.

  10. Basic TLB and Page Fault Timing
    A system has a TLB with a 95% hit rate, and the remaining accesses result in a TLB miss. The memory access time is 20 ns, and the TLB lookup time is 2 ns. On a TLB miss, a page table lookup in memory is required, taking an additional 20 ns. Page faults occur 1% of the time for all memory accesses, with a page fault service time of 8 ms. Calculate the effective memory access time for this system.

  11. Two-Level Paging System Timing
    Consider a system with a two-level page table. The TLB hit rate is 90%, with a TLB lookup time of 5 ns. Accessing the first level of the page table takes 10 ns, and accessing the second level takes another 10 ns. Memory access time is 15 ns after a page table hit. Page faults occur 0.5% of the time with a page fault service time of 10 ms. Determine the effective memory access time.

  12. Impact of Increased Page Fault Service Time
    A system's TLB has an 85% hit rate, with a lookup time of 3 ns. The memory access time is 30 ns, and the page table lookup time (on a TLB miss) is 30 ns. Initially, page faults occur 5% of the time, with a service time of 5 ms. Analyze how the effective memory access time changes if the page fault service time doubles.

  13. Comparing TLB and Page Fault Effects on Access Time
    A computer system has a TLB with a 93% hit rate, a lookup time of 10 ns, and a memory access time of 50 ns. The system experiences a TLB miss penalty of 50 ns for accessing the page table in memory. Page faults occur at a rate of 1%, with a service time of 15 ms. Calculate the effective memory access time and then determine how much the access time would decrease if the page fault rate were reduced to 0.5% without changing the service time.

  14. Belady's Anomaly
    A system is running a specific program that accesses a sequence of pages as follows: 1,3,0,3,5,6,3. Initially, all page frames are empty, and the system can use a varying number of page frames to store these pages.Use the FIFO page replacement algorithm to calculate the number of page faults when the system has 3 page frames available. Document each step, showing which pages are in the frames after each page access. Repeat the process with 4 page frames. Again, document each step, showing which pages are in the frames after each page access. Compare the number of page faults obtained with 3 and 4 page frames. Discuss whether Belady's Anomaly occurs in this case and explain why it happens or why it does not, based on the FIFO page replacement algorithm.

  15. Basic Translation with Invalid Mapping

    Given the following page table and the PTLR value of 5, translate the virtual addresses to physical addresses. The system uses a page size of 1KB. Address references outside the range defined by the PTLR should be considered invalid. Note that some entries in the page table may be invalid.

    Translate the following virtual addresses:

    • 0x0004 (Hexadecimal)

    • 0x1F00 (Hexadecimal)

    • 0x2004 (Hexadecimal)

    • 0x0A00 (Hexadecimal)

  16. Translation with PTLR Check

    Consider a page table with a PTLR value of 3, indicating that only the first three entries are valid for translation. Translate the given virtual addresses into physical addresses using the following page table. The system has a page size of 512 bytes.

    Translate the following virtual addresses:

    • 0x00100 (Hexadecimal)

    • 0x05FF (Hexadecimal)

    • 0x0A00 (Hexadecimal)

    • 0x0700 (Hexadecimal)

  17. Basic Segment Table Translation

    Given the following segment table with an STLR value of 3, translate the virtual addresses to physical addresses. Each virtual address consists of a segment number and an offset. If a virtual address refers to a segment number greater than or equal to the STLR or the offset exceeds the segment limit, the address is invalid.

    Translate the following virtual addresses (segment number:offset):

    • 0:0x0500

    • 1:0x1F00

    • 2:0x1600

    • 3:0x0200

  18. Segment Table with Invalid and Boundary Offsets

    Consider a segment table with an STLR value of 4. Translate the given virtual addresses to physical addresses using the segment table below. If the segment number is greater than or equal to the STLR or the offset is beyond the segment limit, the address is considered invalid.

    Translate the following virtual addresses (segment number:offset):

    • 0:0x007F

    • 1:0x0500

    • 2:0x0BFF

    • 4:0x0000

  19. Advanced Segment Translation with Invalid Cases

    Using the segment table below with an STLR value of 5, perform the translation of virtual addresses into physical addresses. Ensure to check for segment numbers that exceed or equal the STLR and offsets that go beyond the limit of their respective segments.

    Translate the following virtual addresses (segment number:offset):

    • 2:0x1FFF

    • 3:0x0801

    • 4:0x0000

    • 5:0x0100

  20. Protection Bits

    A system has 32-bit virtual addresses and 24-bit physical addresses. Pages are 4 KB each. If each Page Table Entry is 32 bits long, calculate how many bits are left for protection and other flags in the PTE.

  21. Size of Page Table
    Consider a memory system with 48-bit virtual addresses and a 2 KB page size. Each PTE needs 2 protection bits. Round the size of one PTE to the nearest power of 2 byte boundary and determine the size of the entire page table in bytes.

  22. Simple Allocation Scenario

    Consider a memory divided into blocks of the following sizes (in KB): 100, 500, 200, 300, 600. A sequence of processes requests memory blocks of the following sizes (in KB): 212, 417, 112, 426. For each memory allocation strategy (best fit, worst fit, and first fit):

    • Determine which memory block will be allocated to each process.

    • Calculate the remaining free space in each block after allocation.