Operating System · Quiz 1 · Jan 2026

**1. Convert the size to hexadecimal:** The region size is \( 4096 \text{ bytes} = 2^{12} \text{ bytes} = \text{0x1000} \text{ bytes} \). **2. Compute the last inclusive byte address:** Starting from base address \( \text{0x40002000} \), a block of \( \text{0x1000} \) bytes spans addresses from \( \text{0x40002000} \) up to: \[ \text{Last Address} = \text{Base} + \text{Size} - 1 = \text{0x40002000} + \text{0x1000} - 1 = \text{0x40002FFF} \] **Answer: D — 0x40002FFF.** A: **Incorrect:** `0x40003000` is the first address *after* the 4096-byte region (base + size). B: **Incorrect:** `0x40002EFF` corresponds to a size of `0xF00` (3840 bytes), not 4096 bytes. C: **Incorrect:** `0x40001FFF` is the address immediately *before* the start address `0x40002000`. D: **Correct:** `0x40002000 + 0x1000 - 1 = 0x40002FFF`.

**1. Inspect the pointer types in the C code:** - `volatile uint32_t *ctrl_reg = (uint32_t *)0x10000000;` declares `ctrl_reg` as a pointer to an unsigned 32-bit integer (`uint32_t`), which is \( 32 / 8 = 4 \text{ bytes} \). - `volatile uint8_t *stat_reg = (uint8_t *)0x10000004;` declares `stat_reg` as a pointer to an unsigned 8-bit integer (`uint8_t`), which is \( 8 / 8 = 1 \text{ byte} \). **2. Conclude:** Dereferencing `*ctrl_reg` performs a 4-byte (32-bit) memory-mapped register access, and dereferencing `*stat_reg` performs a 1-byte (8-bit) access. **Answer: A — `ctrl_reg` is 4-byte, and `stat_reg` is 1-byte.** A: **Correct:** `uint32_t` is a 32-bit (4-byte) type, and `uint8_t` is an 8-bit (1-byte) type. B: **Incorrect:** `ctrl_reg` is typed as `uint32_t*` (4-byte), not `uint8_t*`. C: **Incorrect:** `stat_reg` is typed as `uint8_t*` (1-byte), not `uint32_t*`. D: **Incorrect:** Swaps the sizes of `uint32_t` (4 bytes) and `uint8_t` (1 byte).

**1. Trace the `fork()` system call:** - Calling `int pid = fork();` creates a new child process that runs concurrently with the parent process. - In the **parent process**, `fork()` returns the positive PID of the child (`pid > 0`), so the `else` branch executes and prints `Parent process`. - In the **child process**, `fork()` returns `0` (`pid == 0`), so the `if` branch executes and prints `Child process`. **2. Analyze scheduling order:** Because there is no synchronization (such as `wait()`) before the `printf` statements, the OS scheduler may run either the parent or the child first. Thus, both lines are printed, but their order is non-deterministic. **Answer: C — Both lines will be printed, but the order is non-deterministic.** A: **Incorrect:** The child process also executes and takes the `pid == 0` branch. B: **Incorrect:** The parent process also executes and takes the `else` branch. C: **Correct:** Both processes run concurrently and print their respective messages in an order determined by the OS scheduler. D: **Incorrect:** Without explicit synchronization, the scheduler does not guarantee that the parent prints before the child.

**1. Trace `fork()` in `kernel/proc.c` of xv6:** 1. **(i) Allocate a new `proc` structure:** `fork()` first calls `allocproc()` to find an `UNUSED` slot in the process table, allocate a trapframe page, and initialize the child's kernel context. 2. **(ii) Copy the parent's memory space to the child:** `fork()` calls `uvmcopy(p->pagetable, np->pagetable, p->sz)` to duplicate the parent's user memory pages into the child's page table. 3. **(iii) Set up the trapframe for the child process:** `fork()` copies the parent's trapframe (`*(np->trapframe) = *(p->trapframe)`) and sets `np->trapframe->a0 = 0` so `fork()` returns 0 in the child. 4. **(iv) Add the child to the ready queue:** Finally, `fork()` sets `np->state = RUNNABLE` so the scheduler can pick it up. **Answer: C — (i) → (ii) → (iii) → (iv).** A: **Incorrect:** In xv6 `fork()`, `uvmcopy` (ii) is executed before copying and modifying the trapframe (iii). B: **Incorrect:** You cannot copy the parent's memory into the child before allocating the child `proc` structure and page table (i). C: **Correct:** Matches the exact sequence in xv6's `fork()`: `allocproc()` (i) \( \to \) `uvmcopy()` (ii) \( \to \) trapframe setup (iii) \( \to \) `np->state = RUNNABLE` (iv). D: **Incorrect:** The trapframe is allocated during `allocproc()` (i), so (iii) cannot happen before (i).

**1. Inspect the RISC-V Sv39 Page Table Entry (PTE) permission bits:** From the PTE diagram, the lowest 5 bits (bits 4 down to 0, from left to right) are: - Bit 4: `U` (User accessible) - Bit 3: `X` (Executable) - Bit 2: `W` (Writable) - Bit 1: `R` (Readable) - Bit 0: `V` (Valid) **2. Check the `kvmmap` call for `CLINT`:** In `kvminit()`, the mapping call is: `kvmmap(kpgtbl, CLINT, CLINT, 0x10000, PTE_R | PTE_W);` Inside `mappages()`, `PTE_V` (bit 0 = 1) is automatically ORed with the passed permissions `PTE_R` (bit 1 = 1) and `PTE_W` (bit 2 = 1), while `PTE_X` (bit 3 = 0) and `PTE_U` (bit 4 = 0) remain 0. Therefore, bits `U X W R V` (the lowest 5 bits) are `00111`. **Answer: B — 00111.** A: **Incorrect:** `01110` has `V=0` (invalid) and `X=1` (executable). B: **Correct:** Setting `PTE_W` (bit 2), `PTE_R` (bit 1), and `PTE_V` (bit 0) while leaving `U` (bit 4) and `X` (bit 3) cleared yields `00111`. C: **Incorrect:** `10110` sets `U=1` and leaves `V=0`. D: **Incorrect:** `10111` sets `U=1` (`PTE_U`), which is not set for kernel-only device mappings.

**1. Examine `syscall()` in `kernel/syscall.c`:** The code reads `num = p->trapframe->a7;` and then indexes into the `syscalls[]` function pointer table using `syscalls[num]()`. **2. Conclude:** All system calls enter the kernel through a single `ecall` instruction. Putting the system call number in register `a7` before executing `ecall` allows the kernel trap handler to identify which specific system call (`fork`, `read`, `write`, etc.) the user program requested. **Answer: C — To let the kernel identify which system call the user process is requesting.** A: **Incorrect:** The return value of a system call is stored in `a0` (`p->trapframe->a0`), not `a7`. B: **Incorrect:** System call arguments (like byte counts) are passed in `a0`–`a5`, not `a7`. C: **Correct:** The kernel reads `p->trapframe->a7` (`num`) to index the `syscalls[num]` dispatch table. D: **Incorrect:** The user stack pointer is stored in the `sp` register, not `a7`.

**1. Trace how a Unix/Linux shell executes an external command (`ls -l`):** 1. **`fork()`:** The shell creates a child process so the shell itself is not overwritten. 2. **`exec()`:** The child process calls `exec()` to replace its memory image with the `/bin/ls` program and run `ls -l`. 3. **`wait()`:** Meanwhile, the parent shell calls `wait()` to block until the child process finishes executing `ls -l`, after which control returns to the shell prompt. **Answer: D — fork-exec-wait.** A: **Incorrect:** Calling `exec` first in the shell process would overwrite the shell itself with `ls`, preventing it from ever returning. B: **Incorrect:** A process cannot `wait` for a child before calling `fork` to create that child. C: **Incorrect:** The child executes `exec` concurrently while the parent calls `wait`; `fork` is followed by `exec` in the child and `wait` in the parent. D: **Correct:** The standard Unix shell execution pattern is `fork()` a child, `exec()` the command in the child, and `wait()` in the parent.

**1. Relate virtual address space, number of page table entries, and page size:** - Virtual memory size: \( 8 \text{ GB} = 8 \times 2^{30} \text{ bytes} = 2^{33} \text{ bytes} \) - Number of virtual pages (page table entries): \( 2^{21} \) **2. Calculate the page (and page frame) size:** \[ \text{Page Frame Size} = \frac{\text{Virtual Address Space Size}}{\text{Number of Pages}} = \frac{2^{33} \text{ bytes}}{2^{21}} = 2^{12} \text{ bytes} = 4 \text{ KB} \] **Answer: B — 4 KB.** A: **Incorrect:** \( 2 \text{ KB} = 2^{11} \text{ bytes} \) would correspond to a 4 GB virtual space with \( 2^{21} \) entries. B: **Correct:** \( 2^{33} / 2^{21} = 2^{12} \text{ bytes} = 4 \text{ KB} \). C: **Incorrect:** \( 8 \text{ KB} = 2^{13} \text{ bytes} \) would require a 16 GB virtual space. D: **Incorrect:** \( 16 \text{ KB} = 2^{14} \text{ bytes} \) would require a 32 GB virtual space.

**1. Express physical RAM size and page frame size as powers of 2:** - Physical memory (RAM): \( 128 \text{ MB} = 2^7 \times 2^{20} \text{ bytes} = 2^{27} \text{ bytes} \) - Page frame size: \( 8 \text{ KB} = 2^3 \times 2^{10} \text{ bytes} = 2^{13} \text{ bytes} \) **2. Divide physical memory by frame size:** \[ \text{Number of Page Frames in RAM} = \frac{2^{27} \text{ bytes}}{2^{13} \text{ bytes/frame}} = 2^{14} \text{ frames} \] **Answer: C — \( 2^{14} \) frames.** A: **Incorrect:** \( 2^{12} \) frames of 8 KB equals only 32 MB of RAM. B: **Incorrect:** \( 2^{13} \) frames of 8 KB equals 64 MB of RAM. C: **Correct:** \( 128 \text{ MB} / 8 \text{ KB} = 2^{27} / 2^{13} = 2^{14} \) frames. D: **Incorrect:** \( 2^{15} \) frames of 8 KB equals 256 MB of RAM.

**1. Trace the variable `x` in the parent and child processes:** Initially, `int x = 5;` before `fork()`. Because `fork()` gives the parent and child separate copies of memory, modifications to `x` in one process do not affect the other: - **In the Child (`rc == 0`):** - `x = x - 1;` \( \implies x = 5 - 1 = 4 \) - Prints `Child A: 4` - After the `if/else` block, executes `x = x + 8;` \( \implies x = 4 + 8 = 12 \) - Since `rc == 0`, prints `Child B: 12` - **In the Parent (`rc > 0`):** - `x = x + 1;` \( \implies x = 5 + 1 = 6 \) - Prints `Parent A: 6` - Calls `wait(NULL);` — **blocks until the child completely finishes and calls `exit(0)`** (so `Parent B` MUST be printed after both `Child A` and `Child B`). - After `wait(NULL)` returns, executes `x = x + 8;` \( \implies x = 6 + 8 = 14 \) - Prints `Parent B: 14` **2. Check the valid interleavings:** `Parent A: 6` can appear either before `Child A: 4` or after it, **but `Parent B: 14` must appear last** (after `Child B: 12`) because of `wait(NULL)`. Option A violates this by printing `Parent B: 14` before `Child B: 12`, whereas **Option B** (`Parent A: 6`, `Child A: 4`, `Child B: 12`, `Parent B: 14`) respects all value and ordering constraints. **Answer: B — Parent A: 6, Child A: 4, Child B: 12, Parent B: 14.** A: **Incorrect:** The parent calls `wait(NULL)` before computing and printing `Parent B: 14`, so `Parent B: 14` cannot be printed before `Child B: 12`. B: **Correct:** Has the exact values (`6, 4, 12, 14`) and prints `Parent B: 14` after the child terminates (`wait(NULL)`). C: **Incorrect:** Has wrong numerical values (`Parent B: 8` and `Child A: 3`). D: **Incorrect:** Has wrong numerical values (`Child A: 2` and `Child B: 10`) and invalid ordering.

**1. Recall RISC-V trap handling registers:** When a user process executes `ecall` to invoke a system call in RISC-V, the hardware saves the current user program counter (`pc`) into the **supervisor exception program counter** (`sepc`, or `mepc` in machine mode) before jumping to the trap vector in `stvec`. **Answer: B — exception program counter.** A: **Incorrect:** RISC-V is a general-purpose register architecture and does not have an accumulator register for saving the PC. B: **Correct:** The exception program counter (`sepc` / `mepc`) saves the virtual address of the instruction that triggered the trap/syscall. C: **Incorrect:** `mstatus` / `sstatus` stores privilege mode and interrupt-enable status bits, not the program counter. D: **Incorrect:** Option B is the exact register.

**1. Compute the address ranges in the memory map:** From the memory map diagram, each device occupies \( 256 \text{ bytes} = \text{0x100} \text{ bytes} \) starting from base \( \text{0x20000000} \): - **Interrupt Controller (256 B):** `0x20000000` to `0x200000FF` - **Timers (256 B):** `0x20000100` to `0x200001FF` - **Keyboard (256 B):** `0x20000200` to `0x200002FF` - **Mouse (256 B):** `0x20000300` to `0x200003FF` **2. Locate `0x200003CD`:** Since `0x20000300 <= 0x200003CD <= 0x200003FF`, the address `0x200003CD` falls inside the **Mouse** region. **Answer: A — Mouse.** A: **Correct:** The 4th 256-byte (`0x100`) block spans `0x20000300`–`0x200003FF`, which is mapped to the Mouse. B: **Incorrect:** Keyboard is mapped at `0x20000200`–`0x200002FF`. C: **Incorrect:** Timers are mapped at `0x20000100`–`0x200001FF`. D: **Incorrect:** Interrupt Controller is mapped at `0x20000000`–`0x200000FF`. E: **Incorrect:** The address maps directly to the Mouse block.

**1. Recall how `fork()` handles the trapframe in xv6:** During `fork()`, `allocproc()` allocates a brand-new physical page for the child's `trapframe` (`p->trapframe = (struct trapframe *)kalloc()`), and `fork()` copies the parent's trapframe contents by value (`*(np->trapframe) = *(p->trapframe)`). It then sets `np->trapframe->a0 = 0` in the child without affecting the parent's `trapframe->a0`. **Answer: A — True.** A: **Correct:** Each process has its own dedicated trapframe page allocated via `kalloc()`, so register changes in one do not affect the other. B: **Incorrect:** The statement is true.

**1. Trace timer preemption in xv6:** When a timer interrupt occurs while a process is executing (`RUNNING`), the trap handler calls `yield()`. Inside `yield()`, the process changes its state from `RUNNING` to `RUNNABLE` (`p->state = RUNNABLE`) and calls `sched()` to yield the CPU back to the scheduler. **Answer: C — Running → Runnable.** A: **Incorrect:** `Running -> Sleeping` happens when a process voluntarily blocks on an event via `sleep()`, not on a timer preemption. B: **Incorrect:** `Running -> Zombie` happens when a process terminates via `exit()`. C: **Correct:** A timer interrupt invokes `yield()`, which transitions the process from `RUNNING` to `RUNNABLE` so it remains ready to be scheduled again. D: **Incorrect:** The preempted process gives up the CPU and changes state to `RUNNABLE`.

**1. Understand what `exec()` replaces vs. preserves:** The `exec()` system call loads a new program into the **current** process: - It allocates a new user page table and replaces the process's memory image (code, data, stack, heap). - It resets the user program counter (`epc`) and stack pointer (`sp`) in the trapframe to the entry point and new user stack of the new program. - Because no new process is created, the **Process Identifier (PID)** in the PCB (`p->pid`) remains completely unchanged. **Answer: B — Process identifier (PID).** A: **Incorrect:** `exec()` creates a new user page table mapping the new executable's segments and frees the old user page table. B: **Correct:** `exec()` replaces the memory image of the calling process in-place, preserving its PID. C: **Incorrect:** `exec()` updates the saved program counter (`p->trapframe->epc`) to the entry point of the newly loaded ELF binary. D: **Incorrect:** Memory information (`p->sz`, `p->pagetable`) is replaced with the new program's memory layout.

**1. Understand orphan process reparenting in Unix/xv6:** - Process C is the parent of process D. - When process C terminates while its child D is still alive, D becomes an **orphan process**. - During `exit()` (via `reparent()` in xv6), the kernel reassigns all children of the exiting process C so that their new parent is the `init` process (PID 1), NOT the grandparent B or great-grandparent A. - Therefore, when D later terminates, **`init`** waits for and reaps D. **Answer: D — Process init.** A: **Incorrect:** Orphaned processes are reparented directly to `init`, not to their great-grandparent. B: **Incorrect:** Orphaned processes are not reparented to their grandparent B. C: **Incorrect:** Process C has already terminated before D finishes, so it cannot reap D. D: **Correct:** When C exits, xv6's `reparent()` assigns `init` as D's parent, and `init` loops calling `wait()` to reap orphaned zombies.

**1. Inspect `kernel/trampoline.S` vs. `kernel/trap.c` in RISC-V xv6:** - `kernel/trampoline.S` is the assembly file mapped at the top of both user and kernel virtual address spaces (`TRAMPOLINE`). It defines the global symbol `trampoline` (containing `uservec`, which switches `satp` from the user page table to the kernel page table upon trap entry) and `userret` (which switches `satp` from the kernel page table back to the user page table before `sret`). - By contrast, `usertrap` and `usertrapret` are C functions defined in `kernel/trap.c`, not in `kernel/trampoline.S`. **Answer: A and C.** A: **Correct:** `userret` is defined in `kernel/trampoline.S` and switches `satp` back to the user process page table. B: **Incorrect:** `usertrapret` is a C function in `kernel/trap.c`, not in `kernel/trampoline.S`. C: **Correct:** `trampoline` (containing `uservec`) is defined in `kernel/trampoline.S` and switches `satp` to the kernel page table. D: **Incorrect:** `usertrap` is a C function in `kernel/trap.c`.

**1. Match each process description to its xv6 process state:** - **Process P1** is ready to run and waiting in the run queue \( \implies \) `RUNNABLE` (**Option A** is correct). - **Process P2** is currently executing on the CPU \( \implies \) `RUNNING` (**Option B** is correct). - **Process P3** has called `sleep()` waiting for an I/O event \( \implies \) `SLEEPING` (**Option C** is correct, Option E is incorrect). - **Process P4** has exited (`exit()`) but its parent has not yet called `wait()` \( \implies \) `ZOMBIE` (**Option D** is correct, Option F is incorrect). **Answer: A, B, C, and D.** A: **Correct:** A process ready and waiting to be scheduled on the CPU is in the `RUNNABLE` state. B: **Correct:** A process actively executing on a CPU core is in the `RUNNING` state. C: **Correct:** A process blocked in `sleep()` waiting for I/O is in the `SLEEPING` state. D: **Correct:** A process that has called `exit()` but has not yet been reaped by its parent's `wait()` is in the `ZOMBIE` state. E: **Incorrect:** P3 called `sleep()` and is blocked (`SLEEPING`), not `RUNNING`. F: **Incorrect:** P4 has exited and is a `ZOMBIE`, not `RUNNABLE`.