• Why Kernel and User Mode? (Basic)
• Two Protection Mechanisms (Basic)
• Adjusting XP (Basic)
• Classify and Trace (Intermediate)
• Timer Quantum, Edge Detection, and Scheduler Overhead (Challenging)
• Who Should Adjust XP? (Basic)
• Implications of PC31 as Status Bit (Intermediate)
• Trap, System Call, and Context Switch Trace (Challenging)

50.002 Computation Structures
Information Systems Technology and Design
Singapore University of Technology and Design

Virtual Machine

Each topic’s questions are grouped into three categories: basic, intermediate, and challenging. You are recommended to do all basic problem set before advancing further.

Why Kernel and User Mode? (Basic)

An SUTD student claims: “User mode restrictions are unnecessary. The compiler can simply refuse to emit LD or ST whose address is in the kernel range, and refuse to emit branches that cross PC31.”

Give two distinct technical arguments rebutting this claim. Each argument should identify a class of attacks the compiler approach cannot prevent.

Two Protection Mechanisms (Basic)

A user mode process is executing at \(\text{PC} = \texttt{0x00400000}\). The register file holds \(\text{Reg}[R30] = \texttt{0x80001234}\) and \(\text{Reg}[R2] = \texttt{0x80000020}\).

The next two instructions in the user program are:

JMP(R30, R0)
LD(R2, 0x10, R3)

Answer the following questions:

1. What value lands in PC after JMP(R30, R0) executes? What value lands in Reg[R0]?
   Show Answer

   The candidate next PC from JMP is Reg[R30] = 0x80001234. In user mode (PC31 = 0), the hardware masks the top bit of any value being written into PC, so the actual write is 0x00001234. The link register receives PC + 4 = 0x00400004, with no masking needed since that value already has MSB 0.

   
   

2. Suppose in alternate ISA, a JMP initiated to kernel space that failed caused the user program continues with the next instruction at the user side. What address does the memory unit see when LD(R2, 0x10, R3) executes, and what does Reg[R3] receive?

1. The two questions above involve two different hardware mechanisms that both protect the kernel. Name where in the datapath each mechanism lives, and explain in one sentence why a single mechanism cannot cover both cases.
   Show Answer

   The ALU computes `EA` Reg[R2] + 0x10 = 0x80000030. If we specify that LD, LDR, and ST in user mode ignore the MSB of the computed address, we need to ensure that the datapath always mask the highest bit of `EA` to `0`, such that the Memory Unit receives 0x00000030. For the `JMP` protection, we `AND` `PC31` with `Reg[Ra]31` to disallow switching from user to kernel mode via `JMP`.

   
   

Adjusting XP (Basic)

The asynchronous interrupt handler at XAddr ends with

SUBC(XP, 4, XP)
JMP(XP)

The ILLOP handler, used for SVC and exceptions, ends with:

JMP(XP)

with no SUBC. Both handlers entered kernel mode via the same hardware mechanism: the Control Unit set Reg[XP] <- PC + 4 and forced PC to a fixed entry address.

Answer the following questions:

1. Pick a concrete user address, say PC = 0x00002040, and explain what Reg[XP] contains at the moment each handler begins executing, for the case where the user instruction at 0x00002040 was the one that caused the entry.

   Show Answer

   In both cases the hardware writes Reg[XP] <- PC + 4 = 0x00002044 at the moment of entry. The hardware does not know or care whether the trigger was async or sync; it always saves the address of the next instruction.

   
   

2. For each handler, state the address at which the user program resumes after the handler returns. Show that the async handler’s resume address is correct and the ILLOP handler’s resume address is also correct, given the purpose of each.

   Show Answer

   Async return computes Reg[XP] - 4 = 0x00002040 and jumps there. This re-executes the instruction at 0x00002040, which is what we want: that instruction was interrupted before it could commit, so it has not yet had its effect, and we need it to run.

   ILLOP return jumps directly to Reg[XP] = 0x00002044. This skips the instruction at 0x00002040, which is also what we want: that instruction was an SVC (or other illegal opcode used as a supervisor call), and its entire purpose was to trap into the kernel. Re-executing it would just trap again. The kernel has now serviced the request, so we move past it.

   
   

3. What would go wrong, in one sentence each, if you swapped the two endings: the async handler used JMP(XP) alone, and the ILLOP handler used SUBC(XP, 4, XP); JMP(XP)?

   Show Answer

   Async with JMP(XP) alone: the resumed user program silently skips the instruction it was actually running when the timer fired, losing whatever side effect that instruction was supposed to produce.

   ILLOP with SUBC(XP, 4, XP); JMP(XP): the resumed user program lands back on the SVC instruction, which traps again, and the process is stuck in an infinite trap loop never making progress past the syscall.

   
   

Classify and Trace (Intermediate)

For each of the five events below, answer in three things:

1. Is the event a synchronous or asynchronous interrupt?
2. Which Beta entry point does the hardware jump to: RESET, ILLOP, or XAddr?
3. What value does the hardware write into Reg[XP], expressed in terms of the program counter at the moment of the event?

Then: in which two of these events is Reg[XP] - 4 the address the kernel should resume at, and in which two is Reg[XP] itself the right resume address? Justify the leftover case.

Timer Quantum, Edge Detection, and Scheduler Overhead (Challenging)

A Beta CPU runs at \(f_\text{cpu} = 25\) MHz. The OS scheduler uses an asynchronous free running counter that is 24 bits wide, clocked at \(f_\text{tmr} = 100\) kHz. Bit \(k\) of this counter is fed through a rising edge detector that is itself clocked by the CPU clock, and the output of that edge detector drives the IRQ line of the Control Unit.

The purpose of this scheduler is to perform context switching.

Here’s an illustration of the setup:

Answer the following questions.

1. Derive an expression for the quantum \(T_k\) (the wall clock time between two consecutive IRQ pulses) as a function of \(k\) and \(f_\text{tmr}\). Compute \(T_k\) in milliseconds for \(k = 10\).

   Show Answer

   Bit k of a free running counter toggles every 2^k counter ticks, so its period is 2^(k+1) counter ticks. Each counter tick lasts 1/f_tmr seconds, so:

   T_k = 2^(k+1) / f_tmr

   For k = 10 and f_tmr = 100 kHz: T_10 = 2048 / 10^5 ≈ 20.48 ms.

   
   

2. The statement above stresses that the rising edge detector be clocked by the CPU clock, not the timer clock. Explain the precise failure mode that occurs if the detector is clocked by the timer clock instead. Your answer should refer to how the Control Unit samples IRQ and to the duration of the resulting pulse measured in CPU cycles.

   Show Answer

   The Control Unit samples IRQ once per CPU clock edge. For correct behaviour the pulse on IRQ must be high for exactly one CPU cycle, otherwise the Control Unit will see IRQ = 1 on multiple consecutive cycles and re-trap to XAddr repeatedly.

   If the edge detector is clocked by the slower timer clock (100 kHz here), its output pulse lasts one timer cycle, which is f_cpu/f_tmr = 250 CPU cycles wide. The Control Unit will therefore see IRQ = 1 on roughly 250 consecutive CPU cycles. Each of those cycles either (1) re-asserts the trap (setting Reg[XP] <- PC + 4 and PC <- XAddr) or (2) if PC31 is now 1 and the CPU masks IRQ (or disable interrupt), it might re-trigger interrupt again after it leaves the interrupt handler, if the interrupt handler takes less than 250 CPU cycles. In the unmasked case, `Reg[XP]` gets overwritten 250 times, and it ends up pointing into the handler itself rather than into the interrupted user program. This means the interrupted process is unrecoverable.

   
   

3. Suppose one full context switch (entry to XAddr, register save, scheduler decision, register restore, return) costs \(C = 200\) CPU cycles. This means we have an overhead of 200 CPU cycles. Using the result from the first question with \(k = 10\), compute the fraction of CPU time spent on context switching overhead. Then determine the smallest \(k\) for which this overhead is strictly below 0.1%.

   Show Answer

   Number of CPU cycles per quantum is N_k = T_k x f_cpu = 2^(k+1) x f_cpu / f_tmr = 2^(k+1) x 250.

   For k = 10: N_10 = 2048 x 250 = 512,000. Overhead is 200 / 512,000 ≈ 0.039%.

   For overhead below 0.001 we need 200 / (2^(k+1) x 250) < 0.001, that is 2^(k+1) > 800. Since 2^10 = 1024 > 800 and 2^9 = 512 < 800, the *smallest* acceptable value is k+1 = 10, so k_min = 9.

   We can easily prove this by computing more cases: at k = 9, N_9 = 1024 x 250 = 256,000 and 200/256,000 ≈ 0.078% < 0.1%. At k = 8, N_8 = 128,000 and overhead is ≈ 0.156%.

   
   

4. The scheduler handler return sequence ends with SUBC(XP, 4, XP) followed by JMP(XP). A student proposes swapping them, on the grounds that “JMP is one cycle, SUBC is one cycle, and reordering saves nothing but is also harmless”. Is the student correct? Explain in two sentences, and state the semantic purpose of the SUBC step.

   Show Answer

   The student is wrong. JMP(XP) transfers control immediately, so the SUBC that follows it never executes; the program counter is already pointing elsewhere.

   The SUBC exists because the hardware saves PC + 4 (the address of the instruction after the interrupted one) into Reg[XP], but on resume we want to re-execute the interrupted instruction itself, whose address is Reg[XP] - 4.

   
   

5. Consider an alternative ISA in which, on an asynchronous interrupt, the hardware saves the current PC (not PC + 4) into Reg[XP]. Describe how the return code changes, and identify the new constraint this places on the hardware regarding the interrupted instruction’s side effects. Is this constraint stricter, looser, or equivalent to Beta’s?

   Show Answer

   The handler return becomes simply JMP(XP) with no decrement, which is slightly cleaner.

   The constraint is identical to Beta's, just packaged differently. In both schemes the interrupted instruction must **not** have committed any architectural side effects (no register write, no memory store, no flag update), because both schemes resume by re-executing it. Beta saves PC + 4 and in turn, it must decrements on return (of interrupt), while the alternative ISA saves PC directly so it doesn't have to decrement upon return from interrupt handler. Either way the hardware must abort the instruction cleanly. The constraint is therefore equivalent. The only real difference is that Beta forces every handler to **remember** the decrement, which is one more place a kernel programmer can introduce a bug.

   **Note**: If this alternate ISA also saves `PC` on `ILLOP`, then it must **increment** `XP` by `4` before `JMP(XP)` and returning to the calling process. Otherwise, the trap/SVC will be re-executed.

   
   

Who Should Adjust XP? (Basic)

A scheduler’s final routine should “return to user” (resume a process). This procedure needs to know whether the process being resumed was last suspended by an asynchronous interrupt or by an SVC, because the former requires SUBC(XP, 4, XP) and the latter does not. Propose a concrete way for the kernel to record this in the process table, and explain why mixing the two cases up is a correctness bug, not merely a performance bug. Describe the visible symptoms in each direction of mistake.

Implications of PC31 as Status Bit (Intermediate)

A user mode program executing at \(\text{PC} = \texttt{0x00400000}\) contains the instruction

LD(R0, 0x1000, R1)

with Reg[R0] holding the value 0x80000000. Trace what actually happens: what address is presented to the memory unit, what value lands in Reg[R1], and whether the kernel data nominally stored at 0x80001000 was protected. Then state what additional hardware would be required for a user load of 0x80001000 to actually fault rather than silently “aliasing”.

A user mode program executes BEQ(R0, label, R1) where the computed branch target \(\text{PC} + 4 + 4 \cdot \text{SXT(literal)}\) has MSB 1. Describe the hardware mechanism in Beta that prevents this from entering kernel mode. Then contrast with JMP(R31) when Reg[R31] contains 0x80004000. Are both protected by the same mechanism, and at what stage of the datapath?

Our lecture notes name three legal entry points to kernel mode: RESET (0x80000000), ILLOP (0x80000004), and XAddr (0x80000008). Why is it a design choice that these addresses be hardwired into the CPU rather than being soft configurable by the kernel at boot?

Trap, System Call, and Context Switch Trace (Challenging)

A user process P1 is executing a C statement int c = getchar();. The relevant assembly is:

0x00002000:  ADDC(R31, 3, R0)    || service index 3 = read keyboard
0x00002004:  SVC(0)              || illegal opcode 1, traps to ILLOP
0x00002008:  ST(R0, c, R31)      || store returned char available at `R0` into c

SVC(0) is an instruction with an opcode that does not correspond to any real Beta instruction, used by convention to make a supervisor call (generic). Suppose P1 is at PC = 0x00002004 when the SVC is fetched. The ILLOP handler at 0x80000004 reads R0, dispatches to a keyboard read service routine because it found the value 3 in R0 (note that these values are arbitrary). The service routine marks P1 as blocked (waiting for input) and calls the scheduler. The scheduler picks a different ready process P2 to run.

Trace, in order, every write to PC and Reg[XP] from the moment the SVC is fetched until P2 begins executing its first instruction. For each write, label it as hardware (datapath does it automatically) or software (an explicit instruction in some handler does it).

In the lecture notes, we state that Beta disables interrupt when PC31 = 1. This is called non reentrant: while PC31 = 1, IRQ is masked (ignored) in hardware. Identify TWO specific moments in the trace you did in the previous part above at which an asynchronous timer interrupt, if not masked, would corrupt the system. For each, describe the corruption concretely (what register or memory location ends up holding what wrong value).