Memory Management · Operating Systems · GATE CSE

Consider a demand paging memory management system with 32-bit logical address, 20 -bit physical address, and page size of 2048 bytes. Assuming that the memory is byte addressable, what is the maximum number of entries in the page table?

Which of the following tasks is/are the responsibility/responsibilities of the memory management unit (MMU) in a system with paging-based memory management?

Which one or more of the following options guarantee that a computer system will transition from user mode to kernel mode?

Consider a demand paging system with three frames, and the following page reference string: 1 2 3 4 5 4 1 6 4 5 1 3 2 . The contents of the frames are as follows initially and after each reference (from left to right):

The *-marked references cause page replacements.

Which one or more of the following could be the page replacement policy/policies in use?

A computer system supports a logical address space of 232 bytes. It uses two-level hierarchical paging with a page size of 4096 bytes. A logical address is divided into a b-bit index to the outer page table, an offset within the page of the inner page table, and an offset within the desired page. Each entry of the inner page table uses eight bytes. All the pages in the system have the same size. The value of $b$ is _________ . (Answer in integer)

In optimal page replacement algorithm, information about all future page references is available to the operating system (OS). A modification of the optimal page replacement algorithm is as follows:

The OS correctly predicts only up to next 4 page references (including the current page) at the time of allocating a frame to a page.

A process accesses the pages in the following order of page numbers:

$$1,3,2,4,2,3,1,2,4,3,1,4$$

If the system has three memory frames that are initially empty, the number of page faults that will occur during execution of the process is __________ (Answer in integer)

Consider a 32-bit system with 4 KB page size and page table entries of size 4 bytes each. Assume 1 KB = $2^{10}$ bytes. The OS uses a 2-level page table for memory management, with the page table containing an outer page directory and an inner page table. The OS allocates a page for the outer page directory upon process creation. The OS uses demand paging when allocating memory for the inner page table, i.e., a page of the inner page table is allocated only if it contains at least one valid page table entry.

An active process in this system accesses 2000 unique pages during its execution, and none of the pages are swapped out to disk. After it completes the page accesses, let $X$ denote the minimum and $Y$ denote the maximum number of pages across the two levels of the page table of the process.

The value of $X+Y$ is __________.

Consider a memory management system that uses a page size of 2 KB. Assume that both the physical and virtual addresses start from 0. Assume that the pages 0, 1, 2, and 3 are stored in the page frames 1, 3, 2, and 0, respectively. The physical address (in decimal format) corresponding to the virtual address 2500 (in decimal format) is ________

Consider the following two-dimensional array D in the C programming language, which is stored in row-major order:

int D[128] [128];

Demand paging is used for allocating memory and each physical page frame holds 512 elements of the array D. The Least Recently Used (LRU)( page-replacement policy is used by the operating system. A total of 30 physical page frames are allocated to a process which executes the following code snippet:

for (int i = 0; i < 128; i++)

$$\quad$$ for (int j = 0; j < 128; j++)

$$\quad\quad$$D[j] [i] *= 10;

The number of page faults generated during the execution of this code snippet is _____________.

Consider a computer system with 57-bit virtual addressing using multi-level tree-structured page tables with L levels for virtual to physical address translation. The page size is 4 KB (1 KB = 1024 B) and a page table entry at any of the levels occupies 8 bytes.

The value of L is ____________.

Which one of the following statements is FALSE?

Consider a demand paging system with four page frames (initially empty) and LRU page replacement policy. For the following page reference string

7, 2, 7, 3, 2, 5, 3, 4, 6, 7, 7, 1, 5, 6, 1

the page fault rate, defined as the ratio of number of page faults to the number of memory accesses (rounded off to one decimal place) is _____________.

Consider a three-level page table to translate a 39-bit virtual address to a physical address as shown below.

The page size is 4 KB (1 KB = 2¹⁰ bytes) and page table entry size at every level is 8 bytes. A process P is currently using 2 GB (1 GB = 2³⁰ bytes) virtual memory which is mapped to 2 GB of physical memory. The minimum amount of memory required for the page table of P across all levels is _______ KB.

Assume that in a certain computer, the virtual addresses are 64 bits long and the physical addresses are 48 bits long. The memory is word addressable. The page size is 8 kB and the word size is 4 bytes. The Translation Look-aside Buffer (TLB) in the address translation path has 128 valid entries. At most how many distinct virtual addresses can be translated without any TLB miss?

Which one of the following is the correct expression for the page fault rate experienced by the process?

The number of bits required for addressing the next level page table (or page frame) in the page table entry of the first, second and third level page tables are respectively

Which one of the following is TRUE?

If optimal page replacement policy is used, how many page faults occur for the above reference string?

Least Recently Used (LRU) page replacement policy is a practical approximation to optimal page replacement. For the above reference string, how many more page faults occur with LRU than with the optimal page replacement policy?

Suppose a process has only the following pages in its virtual address space: two contiguous code pages starting at virtual address $$0 \times 00000000,$$ two contiguous data pages starting at virtual address $$0 \times 00400000,$$ and a stack page starting at virtual address $$0 \times FFFFF000.$$ The amount of memory required for storing the page tables of this process is

Assuming that no page faults occur, the average time taken to access a virtual address is approximately (to the nearest $$0.5$$ ns)

What will be the size of the partition (in physical memory) required to load (and run) this program?

$$0100, 0200, 0430, 0499, 0510, 0530, 0560, 0120, 0220, 0240, 0260, 0320, 0370 $$

The sequence of requests for blocks of size $$300, 25, 125, 50$$ can be satisfied if we use.

Any implementation of a critical section requires the use of an indivisible machine instruction such as test-and-set.

The amount of virtual memory available is limited by the availability of secondary storage.

The best-fit techniques for memory allocation ensures the memory will never be fragmented.

The use of monitors ensures that no dead -locks will be caused.

The $$LRU$$ page-replacement policy may cause thrashing for some type of programs.

List - $${\rm I}$$
$$(A)$$$$\,\,\,\,$$ Virtual Memory
$$(B)$$$$\,\,\,\,$$ Shared memory
$$(C)$$$$\,\,\,\,$$ Look-ahead buffer
$$(D)$$$$\,\,\,\,$$ Look-aside buffer

List - $${\rm II}$$
$$(p)$$$$\,\,\,\,$$ Temporal locality
$$(q)$$$$\,\,\,\,$$ Spatial Locality
$$(r)$$$$\,\,\,\,$$ Address Translation
$$(s)$$$$\,\,\,\,$$ Mutual exclusion

(a) Give a diagram showing how a virtual address would be translated to a physical address.

(b) What is the number of page table entries that can be contained in each page?

(c) How many bits are available for storing protection and other information in each page table entry?

(a)$$\,\,\,\,\,$$ What is the minimum page size in bytes so that the page table for a segment requires at most one page to store it? Assume that the page size can only be a power of $$2.$$

(b)$$\,\,\,\,\,$$ Now suppose that the pages size is $$512$$ bytes. It is proposed to provide a $$TLB$$ (Translation look-aside buffer) for speeding up address translation. The proposed $$TLB$$ will be capable of storing page table entries for $$16$$ recently referenced virtual pages, in a fast cache that will use the direct mapping scheme. What is the number of tag bits that will need to be associated with each cache entry

(c)$$\,\,\,\,\,$$ Assume that each page table entry contains (besides other information) $$1$$ valid bit, $$3$$ bits for page protection and $$1$$ dirty bit. How many bits are available in page table entry for storing the aging information for the page? Assume that the page size is $$512$$ bytes.

When will the $$20$$ $$K$$ job complete?

(a) Draw the memory allocation table using Best Fit and First fit algorithm.
(b) Which algorithm performs better for this sequence?

This program is run on a demand paged virtual memory system, with main memory size equal to $$4$$ pages. Indicate the page references for which page faults occurs for the following page replacement algorithms.
(a) $$LRU$$
(b) $$FIFO$$

Assume that the main memory is empty initially.