List of top Compiler Design Questions on Lexical analysis asked in GATE CS

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 ............

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?

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?

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?

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)?}