CS and IT Gate 2024 Set-2 Questions with Answer

To determine which events will always trigger a context switch moving process P out of the running state, let us analyze the impact of each scenario on process execution:
• a) P makes a blocking system call to read a block of data from the disk:
When a process issues a blocking I/O request, it cannot continue execution until the slow disk operation completes. The operating system must move process P to the blocked/waiting state and perform a context switch to schedule another runnable process so the CPU doesn't sit idle.
→ Always triggers a context switch out of the running state.

• b) P tries to access a page that is in the swap space, triggering a page fault:
A page fault is a hardware-enforced exception. Since the requested page is residing in slow secondary storage (swap space), process P must wait for the OS page fault handler to read the page back into physical main memory. Because this disk activity takes millions of CPU cycles, the OS transitions process P to the blocked/waiting state and context-switches to another process.
→ Always triggers a context switch out of the running state.

• c) An interrupt is raised by the disk to deliver data requested by some other process:
When an external hardware interrupt occurs, the CPU temporarily pauses execution of process P to execute the appropriate Interrupt Service Routine (ISR). However, running an ISR happens in a special interrupt context, not a full process context switch. Once the ISR completes its quick work, the OS scheduler decides whether to return to P or switch to the process that received the data. If P still has remaining time on its quantum and higher priority, the OS will resume P directly without a process context switch.
→ Does NOT always trigger a context switch out of the running state.

• d) A timer interrupt is raised by the hardware:
Timer interrupts occur periodically to handle time-slicing in preemptive multitasking environments. When the timer ticks, the OS scheduling clock ticks down. However, a timer interrupt does not automatically mean process P's time slice has fully expired. If P still has remaining time left in its allocated quantum, or if it remains the highest-priority thread available, the scheduler will simply increment counters and immediately resume process P.
→ Does NOT always trigger a context switch out of the running state.
Conclusion: The events that will always force process P to yield the CPU and transition to a non-running state are a and b.

To determine the correct statements about the Two-Phase Locking (2PL) protocol, let us analyze the structural rules and execution characteristics of the protocol
• a) 2PL permits only serializable schedules:
The core theoretical guarantee of the Two-Phase Locking protocol is that it ensures conflict serializability. Any schedule that strictly follows the rules of 2PL is guaranteed to be serializable, and it completely prevents any data inconsistency or non-serializable interleaving.
→ This statement is TRUE.

• b) Continuous lock and release behavior:
The statement describes a lock-before-operation and release-immediately-after behavior. This is not how 2PL works; instead, that describes basic arbitrary locking, which can easily lead to non-serializable schedules. 2PL explicitly prevents this by forcing transactions to accumulate locks over time rather than dropping them immediately.
→ This statement is FALSE.

• c) The lock release rule:
The central rule of 2PL states that a transaction is divided into two distinct phases:
    1. Growing Phase: The transaction may obtain locks but cannot release any.
    2. Shrinking Phase: The transaction may release locks but cannot obtain any new ones.
Therefore, the moment the very first lock is released, the transaction enters its shrinking phase and is strictly forbidden from acquiring any further locks.
→ This statement is TRUE.

• d) A deadlock is possible with 2PL:
While basic 2PL guarantees serializability, it does not prevent deadlocks. For example, if Transaction 1 holds a lock on item A and requests a lock on item B, while Transaction 2 holds a lock on item B and requests a lock on item A, both transactions will wait indefinitely for each other to release their respective locks.
→ This statement is TRUE.
Conclusion: The correct statements are a, c, and d.

• a) An attribute grammar is an SDD with no side effects:
  By formal definition, an attribute grammar is a Syntax-Directed Definition (SDD) that uses semantic functions without any side effects (such as directly printing values or updating global tables). It strictly computes values of attributes from other attributes.
  → This statement is TRUE.


• b) The attributes in an L-attributed definition cannot always be evaluated in a depth-first order:
  L-attributed definitions are explicitly structured to allow attribute evaluation via a natural depth-first, left-to-right traversal. Because dependency graphs for L-attributed definitions are guaranteed to have no cycles, they can always be evaluated in a depth-first sequence.
  → This statement is FALSE.


• c) Synthesized attributes can be evaluated by a bottom-up parser as the input is parsed:
  A bottom-up parser (like an LR parser) naturally reduces children nodes into parent nodes. Since a synthesized attribute computes its value based on the values of its children nodes, its evaluation perfectly aligns with the shift-reduce actions of a bottom-up parser.
  → This statement is TRUE.


• d) All L-attributed definitions based on an LR(1) grammar can be evaluated using a bottom-up parsing strategy:
  While L-attributed definitions can always be evaluated during top-down parsing, they cannot all be evaluated during a single-pass bottom-up parsing run. For a bottom-up parser to evaluate an inherited attribute, the value must be available before the parent or siblings are fully reduced, which often requires introducing marker non-terminals. If these markers break the underlying LR(1) nature of the grammar, a single-pass bottom-up evaluation becomes impossible.
  → This statement is FALSE.

To determine which fields of an IP header are altered by an intermediate network layer device, let us analyze what happens inside an IP router during standard packet forwarding:
• a) Source IP Address:
The source IP address represents the original host that created and sent the packet. Standard routers do not change this address when forwarding packets (unless the router is explicitly performing Network Address Translation, or NAT, which is an optional service and not a core property of every standard router forwarding step).
→ Not always modified.

• b) Protocol:
The Protocol field (or Next Header field in IPv6) indicates the upper-layer transport protocol (like TCP or UDP) to which the payload data should be delivered at the final destination. This value must remain completely intact so the destination host can read the payload correctly.
→ Not always modified.

• c) Time to Live (TTL):
The TTL field is an 8-bit counter used to prevent routing loops where a packet circles endlessly in a network loop. Every single layer-3 router that processes a packet is required to decrement the TTL value by exactly 1 before forwarding it onwards. If the TTL reaches 0, the router drops the packet and sends an ICMP Time Exceeded message back to the source.
→ Always modified.

• d) Header Checksum:
The Header Checksum is used to detect errors inside the IP header fields. Because the TTL field is decremented at every router hop, the data bits within the header change at every hop. As a direct consequence, the router must recompute the entire validation value to match the updated header content before sending it out.
→ Always modified.
### Conclusion: The fields that are always modified by any router before forwarding are c and d.