Consider a 32-bit system with a 4 KB page size and page table entries of size 4 bytes each. Assume \(1 \, \text{KB} = 2^{10} \, \text{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 ............
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 ............
Show Hint
Solution and Explanation
Given: System address space (\(VA\)) = \(32 \, \text{bits}\) Page size (\(PS\)) = \(4 \, \text{KB}\) Total pages used by a process (\(N\)) = \(2000 \, \text{pages}\) Page table entry size (\(PTE\)) = \(4 \, \text{B}\) It is given in the question that the OS allocates a page (means single page) for the outer page directory upon process creation.
Step 1: Calculate the total number of bits needed for the outer page table.
The total number of bits needed to represent entries in the outer page table is: \[ \log \left(\frac{PS}{PTE}\right) = \log \left(\frac{2^{12}}{2^2}\right) = \log(2^{10}) = 10 \, \text{bits}. \]
Step 2: Calculate the total number of bits needed for the inner page table.
The total number of bits needed to represent entries in the inner page table is: \[ 32 \, (\text{total VA bits}) - 10 \, (\text{outer PT bits}) - 12 \, (\text{page offset bits}) = 10 \, \text{bits}. \]
Step 3: Calculate \(X\).
In each inner page table, we can store \(2^{10}\) entries. The minimum number of page tables (\(PT\)) needed to store \(2000\) pages will be: \[ \lceil \frac{2000}{2^{10}} \rceil = 2 \, PT. \] Thus: \[ X = 2 + 1 \, (\text{for the outer PT}) = 3. \]
Step 4: Calculate \(Y\).
For occupying the maximum pages in a 2-level page table, we need to place at least one \(PTE\) from \(2000\) pages in every page of the inner page table. This equates to \(2^{10}\) \(PT\). Thus: \[ Y = 2^{10} + 1 \, (\text{for the outer PT}) = 1025. \]
Step 5: Calculate \(X + Y\).
The value of \(X + Y\) is: \[ X + Y = 3 + 1025 = 1028. \]
Final Answer: \[ \boxed{1028}. \]
Top Questions on Lexical analysis
- Consider a disk with the following specifications: rotation speed of 6000 RPM, average seek time of 5 milliseconds, 500 sectors/track, 512-byte sectors. A file has content stored in 3000 sectors located randomly on the disk. Assuming average rotational latency, the total time (in seconds, rounded off to 2 decimal places) to read the entire file from the disk is ............
- GATE CS - 2024
- Compiler Design
- Lexical analysis
- Consider a multi-threaded program with two threads \(T1\) and \(T2\). The threads share two semaphores: \(s1\) (initialized to 1) and \(s2\) (initialized to 0). The threads also share a global variable \(x\) (initialized to 0). The threads execute the code shown below. \begin{verbatim} // code of T1 // code of T2 wait(s1); wait(s1); x = x+1; x = x+1; print(x); print(x); wait(s2); signal(s2); signal(s1); signal(s1); \end{verbatim} Which of the following outcomes is/are possible when threads \(T1\) and \(T2\) execute concurrently?
- GATE CS - 2024
- Compiler Design
- Lexical analysis
- Consider a single processor system with four processes A, B, C, and D, represented as given below, where for each process the first value is its arrival time, and the second value is its CPU burst time. \[ A (0, 10), \, B (2, 6), \, C (4, 3), \, D (6, 7). \] Which one of the following options gives the average waiting times when preemptive Shortest Remaining Time First (SRTF) and Non-Preemptive Shortest Job First (NP-SJF) CPU scheduling algorithms are applied to the processes?
- GATE CS - 2024
- Compiler Design
- Lexical analysis
- Consider an array \(X\) that contains \(n\) positive integers. A subarray of \(X\) is defined to be a sequence of array locations with consecutive indices. The C code snippet given below has been written to compute the length of the longest subarray of \(X\) that contains at most two distinct integers. The code has two missing expressions labelled \((P)\) and \((Q)\). \begin{verbatim} int first=0, second=0, len1=0, len2=0, maxlen=0; for (int i=0; i<n; i++) { if (X[i] == first) { len2++; len1++; } else if (X[i] == second) { len2++; len1 = (P); second = first; } else { len2 = (Q); len1 = 1; second = first; } if (len2>maxlen) { maxlen = len2; } first = X[i]; } \end{verbatim} Which one of the following options gives the CORRECT missing expressions?
- GATE CS - 2024
- Compiler Design
- Lexical analysis
- Consider a process \(P\) running on a CPU. Which one or more of the following events will always trigger a context switch by the OS that results in process \(P\) moving to a non-running state (e.g., ready, blocked)?}
- GATE CS - 2024
- Compiler Design
- Lexical analysis
Questions Asked in GATE CS exam
In the diagram, the lines QR and ST are parallel to each other. The shortest distance between these two lines is half the shortest distance between the point P and the line QR. What is the ratio of the area of the triangle PST to the area of the trapezium SQRT?
Note: The figure shown is representative
- GATE CS - 2025
- Geometry
Consider the relationships among P, Q, R, S, and T:
• P is the brother of Q.
• S is the daughter of Q.
• T is the sister of S.
• R is the mother of Q.
The following statements are made based on the relationships given above.
(1) R is the grandmother of S.
(2) P is the uncle of S and T.
(3) R has only one son.
(4) Q has only one daughter.
Which one of the following options is correct?- GATE CS - 2025
- Blood Relations
A quadratic polynomial \( (x - \alpha)(x - \beta) \) over complex numbers is said to be square invariant if \[ (x - \alpha)(x - \beta) = (x - \alpha^2)(x - \beta^2). \] Suppose from the set of all square invariant quadratic polynomials we choose one at random. The probability that the roots of the chosen polynomial are equal is ___________. (rounded off to one decimal place)
- GATE CS - 2025
- Probability
A disk of size 512M bytes is divided into blocks of 64K bytes. A file is stored in the disk using linked allocation. In linked allocation, each data block reserves 4 bytes to store the pointer to the next data block. The link part of the last data block contains a NULL pointer (also of 4 bytes). Suppose a file of 1M bytes needs to be stored in the disk. Assume, 1K = \(2^{10}\) and 1M = \(2^{20}\). The amount of space in bytes that will be wasted due to internal fragmentation is ___________. (Answer in integer)
- GATE CS - 2025
- Memory hierarchy
Consider the following hierarchical cache system with the following access times:
\[ \begin{array}{|c|c|c|} \hline \textbf{Cache Level} & \textbf{Hit Rate} & \textbf{Access Time} \\ \hline L1 & 90\% & 1 \text{ ns} \\ L2 & 80\% & 10 \text{ ns} \\ L3 & 100\% & 100 \text{ ns} \\ \hline \end{array} \]Find \( T_{avg} \) for hierarchical or simultaneous access.