115 年 國立成功大學資訊工程系碩士班《計算機組織與系統》

Pipelining

L2 Cache

Cache Block (Line)

MESI Protocol

PC-relative Addressing

Convert Single-cycle to 5-stage Pipeline

Accessing 2D array via $A[j][i]$ (Strided)

Core A writes to “Shared” (S) data.

Branch target is 1MB away.

L1 Miss but L2 Hit

[2%] If a few bits in an HDD sector or NVM page are corrupted, the controller can recover the correct values using ECC only if

(A) the bit corruption is limited to the data portion of the sector/page.

(B) the bit corruption hasn’t occurred in the ECC of the sector/page.

(C) the bit corruption hasn’t occurred in the ECC or the header of the sector/page.

(D) the number of bits corrupted is low irrespective of where the corruption occurs in the sector/page.

[2%] A full bootstrap program

(A) is stored in ROM to ensure it cannot be infected by any virus.

(B) is part of an operating system.

(C) may be infected by viruses.

(D) runs after the operating system has been loaded in memory.

[2%] IBM’s indexed sequential access method (ISAM) ____.

(A) uses an index file for sequential access.

(B) uses a small master index (kept in memory) that points to disk blocks of a secondary index, while the secondary index blocks point to the actual file blocks.

(C) uses the pointers (kept in memory) of the actual file blocks.

(D) uses the pointers (kept in memory) that point to disk blocks of a master index which points to disk blocks of a secondary index, while the secondary index blocks point to the actual file blocks.

[2%] Which of the following is true about dynamic storage allocation?

(A) Worst fit provides the best storage utilization.

(B) First fit requires less time for allocation than worst fit on average.

(C) Best fit is clearly better than first fit in terms of time and storage utilization.

(D) First fit is clearly better than best fit in terms of time and storage utilization.

[2%] In DMA-based I/O,

(A) cycle stealing can slow down the CPU computation, but off-loading the data-transfer work to a DMA controller generally improves the total system performance.

(B) the CPU is relieved from data transfer and is interrupted after every word has been transferred to initiate the next word transfer.

(C) the interrupt mechanism is not used.

(D) data is transferred to/from a single block of memory, but not to/from multiple blocks.

[2%] When designing an embedded I/O data acquisition path, engineers often choose between an interrupt-driven approach and polling. Which statement is correct?

(A) Under high event rates, an interrupt-driven design is always more power efficient than polling because the CPU does not repeatedly read a status register, and interrupts do not introduce meaningful context-switch overhead.

(B) In periodic polling, the average detection latency is mainly determined by the polling period. If event arrivals are uniformly distributed within each polling interval, the expected detection latency is approximately half the polling period, while the worst-case detection latency can be bounded by roughly one polling period (ignoring the polling routine’s execution time).

(C) Using edge-triggered interrupts eliminates interrupt storms, so edge-triggered interrupts are always preferable to level-triggered interrupts for high-frequency events, and no additional debouncing or throttling mechanisms are necessary.

(D) With polling, increasing the polling frequency simultaneously reduces latency and CPU utilization because the system can detect events sooner and return to sleep earlier; therefore, high-frequency polling is typically better for power.

[2%] You are implementing a very simple file system without journaling. Creating a new file involves allocating one data block, writing the data, initializing the inode, and adding a directory entry that points to that inode. Writes can be reordered by caches unless explicitly flushed. Which sequence best preserves crash consistency, meaning that after a crash you will not end up with a directory entry that references an uninitialized inode or an inode that references garbage data (you may still allow space leaks)?

(A) Persist the directory entry first, then persist the inode, then write the data block, because the name must exist before the file content is visible.

(B) Persist the inode first, then persist the directory entry, then persist the data block, because the inode can be updated later to fix any inconsistency.

(C) Persist the data block first, then persist the initialized inode that points to it, then persist the directory entry, because reachability should be created only after targets are durable.

(D) Persist the data block and inode in any order, because once the directory entry is durable it guarantees both metadata and data consistency.

[2%] A system has two memory tiers. Tier 0 is small and low latency. Tier 1 is large and higher latency. The operating system manages pages and can migrate them between tiers. Which policy choice most directly reduces migration thrashing (ping pong) while still capturing hot pages?

(A) Migrate any page to Tier 0 immediately on its first access in Tier 1, because first touch is the earliest indicator of hotness.

(B) Use page faults as the primary hotness signal and migrate pages only when they fault repeatedly, because faults capture the most performance critical pages.

(C) Use hardware accessed bits (and optionally dirty bits) sampled over fixed epochs, apply hysteresis with a promotion threshold and a separate demotion threshold, and enforce a minimum residency time before a page is eligible to move again.

(D) Always keep the most recently allocated pages in Tier 0, because temporal locality implies newer pages are hotter than older pages.

[2%] Assume a demand-paged system with 3 physical frames and an LRU replacement policy. The page reference string is:

$1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5$

How many page faults occur?

(A) 8
(B) 9
(C) 10
(D) 11

[2%] Consider enabling huge pages for a workload that scans large arrays with strong spatial locality. Which statement is correct?

(A) Huge pages can reduce TLB misses by increasing TLB reach, but they can increase internal fragmentation and can make some operations, such as copy on write and page migration, more expensive because the unit of management is larger.

(B) Huge pages primarily improve performance by eliminating page faults, since huge pages prevent the kernel from needing demand paging for that region.

(C) Huge pages reduce page table walk overhead only if the CPU has a larger TLB, otherwise the miss rate cannot change.

(D) Huge pages always reduce memory usage because fewer page table entries are needed, so fragmentation cannot increase.

[2%] On a traditional HDD (mechanical disk), which statement about common I/O schedulers and latency is correct?

(A) SCAN (elevator) can reduce average seek distance versus FCFS, but it may still cause long waits for some requests depending on direction and queueing, so fairness improves compared with SSTF but tail latency is not necessarily minimized.

(B) SSTF always provides the best tail latency because it minimizes seek distance for every request, which prevents starvation by construction.

(C) FCFS minimizes variance in response time because it preserves arrival order, which avoids reordering-induced latency spikes.

(D) The same scheduler conclusions apply unchanged to NVMe SSDs because both HDDs and SSDs are dominated by seek time.

[2%] Which situation is most likely to increase write amplification in an SSD using an FTL with garbage collection?

(A) Large sequential writes to mostly empty media, because sequentiality maximizes valid page copying during garbage collection.

(B) Using overprovisioning, because extra spare area reduces available user space and forces the SSD to copy more data on every write.

(C) Placing hot and cold data together in the same physical blocks, because it reduces metadata overhead and lowers the frequency of garbage collection.

(D) Small random overwrites to a nearly full drive, especially without TRIM, because many blocks contain a mix of valid and invalid pages, increasing copying during garbage collection.

[2%] Three periodic tasks have deadlines equal to periods:

$T_1: C_1=1\text{ ms},\ P_1=4\text{ ms}$

$T_2: C_2=1.5\text{ ms},\ P_2=6\text{ ms}$

$T_3: C_3=2\text{ ms},\ P_3=12\text{ ms}$

Assume the standard theoretical model: independent periodic tasks, preemptive uniprocessor, deadline equals period, negligible overhead. Which statement is correct when applying utilization-based schedulability tests?

(A) The total utilization is $U=\frac{1}{4}+\frac{1.5}{6}+\frac{2}{12}=\frac{2}{3}$. Therefore, the task set is schedulable under EDF (since $U\leq 1$), and it is also guaranteed schedulable under RM bound for $n=3$, $U\leq 3(2^{1/3}-1)\approx 0.779$.

(B) The task set is not schedulable under EDF because EDF requires $U<1$.

(C) The task set is not guaranteed schedulable under RM because RM’s utilization bound is $U\leq\ln 2\approx 0.693$ for three tasks.

(D) The task set is guaranteed schedulable under RM only if the periods are harmonic. Since 6 is not a multiple of 4, no RM guarantee can be made from utilization.

[2%] Which statement about priority inversion and its mitigation is correct?

(A) Priority inheritance ensures that a high-priority task can never be blocked by a lower-priority task, since the lower-priority task is immediately boosted above all others and runs to completion.

(B) Priority inversion occurs only with non-preemptive kernels; in a fully preemptive RTOS it cannot happen because the scheduler always runs the highest-priority task.

(C) Replacing mutexes with spinlocks eliminates priority inversion because spinlocks never block; they only busy-wait.

(D) Priority ceiling protocols can prevent deadlock and bound blocking time by restricting which tasks may lock a resource based on a preassigned ceiling, but they may reduce parallelism by being conservative.

[2%] In a system with a non-coherent CPU data cache, a device performs DMA writes into a memory buffer that the CPU later reads. Which action is correct for the CPU/driver to ensure it reads the newly DMA-written data?

(A) Before starting the DMA write, the CPU must invalidate the cache lines of the destination buffer; after DMA completion, no cache maintenance is needed because DMA writes update memory directly.

(B) The CPU should clean (write back) the cache lines after DMA completion, because writing back ensures the cache and memory match the device output.

(C) No cache maintenance is required as long as the buffer is aligned to cache-line boundaries and the DMA length is a multiple of the cache-line size.

(D) After DMA completion, the CPU must invalidate (or otherwise ensure invalidation of) the cache lines covering the buffer before reading it, because the CPU cache may still hold stale copies.

[8%] An orphan process is a process whose parent process no longer exists, i.e., either it has finished or terminated without waiting for its child processes to terminate. Please finish the following code within the boxes, which can create an orphan process.

#include <sys/types.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int pid = fork();
    if (pid > 0)
    {
        // this is parent process
        ____
    }
    else if (pid == 0)
    {
        // this is child process
        ____
    }
    return 0;
}

Read the description above about the LSM tree and answer the following questions.

(a) [4%] Explain where write amplification comes from in an LSM-tree key-value store such as LevelDB. Your answer should connect amplification to the maintenance workflow described above.

(b) [4%] Explain where read amplification comes from in an LSM-tree key-value store. In particular, why can $L_0$ increase the number of files a lookup must examine?

(c) [4%] Under what conditions does compaction become the bottleneck and lead to higher tail latency or write stalls? Describe the situation using the LSM maintenance workflow (MemTable, Immutable MemTable, flush to $L_0$, and compaction across levels).