115 年 國立陽明交通大學資訊工程學系碩士班《計算機系統》

Regarding dynamic loading, which of the following statements are TRUE?

(A) In dynamic loading, a routine is not loaded into the main memory until it is called; all routines are kept on disk in a relocatable load format until required.
(B) Dynamic loading typically offers better memory-space utilization than static loading because routines that are never called (such as large, infrequently used error-handling routines) are never loaded into memory.
(C) Dynamic loading strictly requires special support from the complex kernel process scheduling function; it is impossible for user programs to implement this method using standard libraries alone.
(D) Compared to dynamic loading, static loading generally results in faster program startup times for large applications because the entire program is loaded into memory at once, avoiding runtime overheads during execution.

Which of the following statements best distinguishes software traps from hardware interrupts in terms of their origin, execution context, and privilege transition?

(A) Handling Timing: Hardware interrupts are typically recognized and serviced only at instruction boundaries (i.e., after the current instruction retires), whereas software traps (specifically faults like Page Faults) are recognized and serviced immediately during the execution of the instruction.
(B) Masking Capability: The operating system can use the Interrupt Flag (e.g., IF in x86) to mask (ignore) “Divide-by-Zero” and “Page Fault” software traps to ensure atomicity within critical sections.
(C) Synchronicity: Hardware interrupts are asynchronous events triggered by external devices (independent of the CPU clock), whereas software traps are synchronous events tied directly to the execution of a specific instruction.
(D) Event Nature: Software traps strictly indicate erroneous program behavior (e.g., illegal memory access), whereas hardware interrupts indicate normal system events; therefore, legitimate operating system service requests (System Calls) are never implemented using the trap mechanism.

Regarding the necessity, performance, and structure of multi-level page tables compared to single-level page tables, which of the following statements are TRUE?

(A) A primary necessity for multi-level design in modern architectures (e.g., 64-bit) is that a linear single-level page table would require a huge, but not contiguous, block of kernel memory, which is often impossible to allocate.
(B) In terms of memory consumption, a multi-level page table always consumes less physical memory than a single-level page table, regardless of whether the process’s virtual address space is sparse or fully populated (dense).
(C) Regarding address-space sparsity, multi-level page tables save memory by allowing the operating system to avoid allocating inner-level page tables for invalid (unused) regions of the virtual address space.
(D) In terms of memory access time (assuming a TLB miss), the multi-level page table structure introduces a performance overhead compared to a single-level table, as the MMU must perform multiple memory references to traverse the hierarchy (e.g., directory → table → frame).

Regarding the behavior of fork() and exec() system calls in a multithreaded process (specifically under POSIX standards), which of the following statements are TRUE?

(A) When fork() is invoked by a thread in a multithreaded process, the resulting child process contains duplicates of all threads that were running in the parent process at the time of the call.
(B) If a thread other than the one calling fork() holds a lock (e.g., a mutex) at the moment fork() is called, that lock will exist in the child process in a locked state, but the thread holding it will not exist in the child to unlock it, leading to potential deadlocks if the child tries to acquire this lock.
(C) It is generally unsafe to call complex library functions (like printf or malloc) in the child process between fork() and exec() because these functions may rely on internal locks that were left in an inconsistent state during the fork.
(D) The exec() system call allows the child process to retain the memory space and thread context of the parent process while simply resetting the Program Counter (PC) to the beginning of the main() function.

Regarding virtual memory management techniques, specifically Thrashing, Working-Set Model, Page Replacement Algorithms, and Copy-on-Write (COW), which of the following statements are TRUE?

(A) A classic symptom of thrashing is low CPU utilization. This occurs because processes spend the majority of their time waiting for the paging device (I/O), which often misleads the standard OS scheduler into increasing the degree of multiprogramming, thereby worsening the thrashing.
(B) Belady’s anomaly refers to the phenomenon where increasing the number of available page frames results in an increase in the number of page faults. This anomaly can occur in the FIFO algorithm but is mathematically proven to be impossible in LRU (Least Recently Used), which belongs to the class of stack algorithms.
(C) When fork() is executed with Copy-on-Write enabled, the parent and child processes share the same physical pages. To detect when a copy is needed, these shared pages are initially marked as read-write in the page table so that the hardware allows the write to proceed immediately without OS intervention.
(D) The Working-Set Model prevents thrashing by estimating the current locality of each process. If the sum of the working-set sizes of all active processes exceeds the total number of available frames, the operating system selects a process to suspend (swap out) to release frames.

Which of the following statements about CPU scheduling are correct?

(A) The turnaround time of the non-preemptive Shortest-Job-First (SJF) scheduling remains even when the arrival rate of jobs varies.
(B) The turnaround time of the SJF is always shorter than that of the First-In-First-Out (FIFO) scheduling when all jobs arrive in the system simultaneously.
(C) We define the response time as the time from when the job arrives in a system to the first time it is scheduled for execution. The average response time of the round robin (RR) scheduling is shorter than that of preemptive SJF scheduling.
(D) We can periodically increase the priority of all jobs in the system to mitigate the starvation problem exhibited in Multi-Level Feedback Queue (MLFQ) scheduling.

Atomicity violation bugs occur when multiple operations intended to run as an indivisible (atomic) unit are interrupted by another thread in concurrent programs. The atomicity violation bugs result in the desired serializability among multiple memory accesses being violated, leading to lost updates. Please choose the correct atomicity violation bug code pattern(s) below.

(A)
static int i = 0;
static object a, b = default;
var tid1 = Task.Run(() => {
lock(a) { i++; }
});
var tid2 = Task.Run(() => {
lock(b) { i++; }
});
Task.WhenAll(tid1, tid2); print(i);

(B)
static pthread_cond_var WorkDone = PTHREAD_COND_INIT;
void main() {
pthread_t id = null;
pthread_create(&id, NULL, &fun, NULL);
pthread_wait(&WorkDone);
}
void fun() { pthread_signal(&WorkDone); }

(C)
static int i = 0;
var tid1 = Task.Run(() => {
if (atomic_load(&i) == 0) {
atomic_add(&i, 1);
}
});
var tid2 = Task.Run(() => {
if (atomic_load(&i) == 0) {
atomic_add(&i, 1);
}
});
Task.WhenAll(tid1, tid2); print(i);

(D)
static long int i = 101;
var tid1 = Task.Run(() => {
i++;
});
var tid2 = Task.Run(() => {
print(i);
});
Task.WhenAll(tid1, tid2);

The spin lock ensures the correctness of concurrent programs on multiple processors. Please choose the correct spin-lock implementation(s) and usage(s) including the Test-And-Set, Compare-And-Swap, Load-Linked and Store-Conditional, and Fetch-And-Add instructions. Note that LoadLinked() and StoreConditional(), respectively, perform Load-Linked and Store-Conditional operations.

(A)
int TestAndSet(int *old_ptr, int new) {
int old = *old_ptr;
*old_ptr = new;
return old;
}

(B)
int CompareAndSwap(int *ptr, int expected, int new) {
int original = expected;
if (*ptr == expected)
original = new;
return original;
}

(C)
void lock(lock_t *lock) {
while (1) {
if (LoadLinked(&lock->flag) == 1) return;
while (StoreConditional(&lock->flag, 1) == 1);
}
}

(D)
int FetchAndAdd(int *ptr) {
int old = *ptr;
*ptr = old + 1;
return *ptr;
}

The Linux cat command opens the file for reading. On Linux, the strace tool can dump the trace of every system call made by the cat Linux command shown below. Please choose the correct description(s) for system calls used by the cat Linux command.

prompt> strace cat hello
...
open("hello", O_RDONLY | O_LARGEFILE)
read(3, "helloworld\n", 4096)
write(X, "helloworld\n", 11)
helloworld
read(3, "", 4096)
close(3)
...

(A) The return value of the first open system call is 3.
(B) The return value of the first read system call is 11.
(C) The first argument (X) of the write system call represents the file descriptor and the value of X is 1.
(D) The return value of the second read system call is 0.

The hard drive (disk) has become the main form of persistent data storage in computer systems. In the disk, the motor spins the platters around at a constant rate. The rate of hard drive rotation is measured in Rotations Per Minute (RPM). Please choose the correct description(s) about the performance of disks below.

(A) Each rotation takes 6 milliseconds (ms) when the RPM of this disk is 10,000.
(B) When the transfer rate of a disk is 100 MB/second, transferring a 1024 KB block takes 10 milliseconds (ms) to complete.
(C) The SCAN disk scheduler is invented to shorten the seek time of the disk.
(D) The SCAN disk scheduler can resolve the starvation problem shown in the Shortest Seek Time First (SSTF) disk scheduler when a steady stream of requests is always directed to the inner track of the disk, where the head currently is positioned.

Which of the following statements are true?

(A) The metric of ops/sec is not the absolute performance metric for AI accelerators; instead, the metric of tokens/sec is a good indicator for LLM inference.
(B) The CPU performance metric MIPS is not a fair indicator because it does not consider the complexity of machine instructions. A machine instruction set of short and fast instructions tends to have higher MIPS.
(C) NVIDIA NVLink and AMD Infinity Fabric are used to improve the data transfer rate between chips as an LLM model training and inference cannot be conducted within a single AI accelerating chip.
(D) Data center computing resources consistently operate at high utilization levels due to rapidly increasing demand, while utilization imbalances across data centers can be effectively mitigated through network-enabled demand redistribution.

Which of the following statements are true?

(A) The machine instruction add $t0,$s2, $t0 tells us two CPU design principles: I. Simplicity favours regularity and II. Smaller is faster. (B) Each basic block in a machine code program has a single-entry point, which may be a branch target, and a single exit point, with no branch instructions except possibly at the end. A basic block serves a purpose similar to blocks in C programs, in that it provides a unit for analyzing the lifetime of variables within the block. (C) If the clock period of a CPU is set as$n$ns and the CPU supports multi-cycle instructions, comparison and branch instructions, like bne, that require$2n$ can be included in the instruction set without increasing the clock period.
(D) The key idea of lazy linkage is to use an indirection table that initially holds the address of a linker/loader resolver for a DLL routine and is later updated with the address of the loaded DLL routine, making subsequent calls more efficient.

Consider the above ALU design. The control signals are grouped as (Ainvert, Binvert, Operation[1], Operation[0]). Which of the following statements are true?

🖼️【此處有附圖，見下方】

(A) The control signal group (1, 1, 0, 1) performs an $a \cdot b$ instruction.
(B) The following code sequence performs an overflow detection for unsigned addition ($t1 + t2$):
addu $t0,$t1, $t2; nor$t3, $t1,$zero;
sltu $t3,$t3, $t2; beq$t3, $zero, Overflow
(C) The Set signal is introduced to implement the set-less-than instruction and corresponds to the sum output of ALU31.
(D) The control signal group (0, 1, 1, 1) performs a set-less-than instruction.

Which of the following statements are true?

(A) Consider the above ALU design and a multiplication of $00101_2 \times 00011_2$. The value of the Remainder register is $0001111000_2$ after three iterations of multiplication is conducted.

(B) Consider the same ALU design and now a division of $01101_2 \div 00011_2$ using the restoring scheme is conducted. The value of the Remainder register is $0000010001_2$ after four iterations of division is conducted. Note that the shift operation is performed at the end of each iteration rather than at the beginning.

(C) Consider the 5-bit non-restoring division algorithm that performs shift-left operation at the end of each iteration rather than at the beginning. The algorithm requires 6 but not 5 iterations to obtain correct quotient.

(D) Consider a multiplication of $00101_2 \times 01001_2$ applying the Booth algorithm. This multiplication requires two additions and two subtractions.

🖼️【此處有附圖，見下方】

Consider a 16-bit Floating-Point format following IEEE Std 754 with one signed bit, 4-bit exponent and 11-bit fraction. $x=(-1)^s \times (1+\mathrm{Fraction}) \times 2^{(\mathrm{Exponent}-\mathrm{Bias})}$. Which of the following statements are true?

(A) The maximum positive FP number in this format is $1.11111111111_2 \times 2^7$.
(B) The smallest positive de-normalized number is $1.0 \times 2^{-17}$.
(C) To ensure the exponent is unsigned, the bias should be 15.
(D) Floating-point addition requires aligning the binary points by shifting the operand with the smaller exponent; otherwise, shifting the operand with the larger exponent could make its fraction excessively large and result in overflow, while excessive shifting of the smaller-exponent operand may cause its fraction to be truncated.

The following statements describe three pairs of pipelined processors. In each pair, the processors are identical except for the specified feature. In all cases, the processors execute the same compiled program. Ignore differences in execution time, pipeline stalls, and throughput. Consider only whether the processors may produce different architectural results.

In Case A, processor A resolves data hazards using interlocks, while processor B uses full bypassing.
In Case B, processor A handles control hazards by stalling the pipeline until the branch target is known. Processor B uses a “predict-not-taken” scheme and flushes the pipeline if the branch is taken.
In Case C, processor A has a single memory port shared between instruction fetch and data access, while processor B has no structural hazards.

(A) Case A may produce different architectural results if a load instruction is immediately followed by an instruction that consumes the loaded value.
(B) Case B may produce different architectural results because Processor B may speculatively execute instructions that Processor A does not.
(C) Case C may produce different architectural results if an instruction fetch is delayed by a data memory access, causing a different ordering of memory accesses as observed architecturally.
(D) None of the cases will produce different architectural results, since all differences are purely microarchitectural.

A cache designer considers modifying a cache while keeping all parameters fixed except for the single change described. Assume a conventional set-associative cache with Least Recently Used (LRU) replacement. Which of the following statements is (are) correct?

(A) Doubling the cache line size while keeping cache capacity and associativity fixed strictly reduces the number of tag entries that must be compared on each cache access.
(B) Doubling the cache associativity while keeping cache capacity and line size fixed doubles the total number of tag entries in the cache.
(C) Doubling the capacity of a direct-mapped cache tends to reduce conflict misses but has minimal effect on compulsory misses.
(D) Doubling the cache line size tends to reduce compulsory misses by exploiting spatial locality and can increase conflict misses, while typically increasing the miss penalty.

A byte-addressable machine uses 36-bit virtual addresses and 30-bit physical addresses. To achieve high performance, the bits used to index into a physical cache set must be obtainable without performing virtual-to-physical address translation through the TLB. The cache block size is fixed at 64 bytes. Which of the following statements is (are) correct?

(A) Assuming a page size of $2^{13}$ bytes and an 8-way set-associative physically tagged cache, the maximum physical cache size that satisfies the above constraint is 32 KB.
(B) If the cache block offset is contained within the page offset, then cache indexing does not require virtual-to-physical address translation.
(C) Given a page size of $2^{13}$ bytes and a physical cache size of $2^{18}$ bytes, the minimum cache associativity required to avoid virtual-to-physical address translation during cache indexing is 32.
(D) If a $2^{15}$-byte direct-mapped physical cache is used, the minimum page size that supports this cache configuration without requiring address translation for cache indexing is $2^{15}$ bytes.

Which of the following statements about branch prediction and conditional execution are true?

(A) The Branch Target Buffer (BTB) is typically accessed during the instruction decode stage to enable early redirection.
(B) Indirect branches, such as those used in switch statements, are generally easier to predict than conditional branches because their targets remain fixed once the branch outcome has been resolved.
(C) The 2-bit dynamic branch prediction scheme improves prediction accuracy primarily by exploiting global branch history and correlations among nearby branches.
(D) Programs that use the CSEL instruction in ARMv8 architecture can potentially reduce the number of conditional branch instructions by replacing control flow with conditional data selection.

Consider two compute systems, Machine A and Machine B, designed to accelerate linear-algebra workloads. Machine A can issue 3 multiply operations per cycle and sustains a memory bandwidth of 0.1 words per cycle. Machine B can issue 1 multiply operation per cycle and sustains a memory bandwidth of 0.5 words per cycle. Both machines have a multiplier latency of 1 cycle and operate at the same clock frequency.

Assume the following throughout this problem: instructions execute in program order; in each cycle, all multiplications whose dependencies are satisfied are issued, up to the number of available multipliers; only multiplications and loads from main memory incur cost; load latency is fully hidden once data is available; all kernels execute in steady state on large inputs; results are kept on-chip and are not written back to main memory; and at any time at most one kernel is executing on a machine.

Consider the following kernels:

• Matrix–vector multiplication of an $N \times N$ matrix with an $N$-element vector.
• Matrix–matrix multiplication of two $N \times N$ matrices.

Which of the following statements are correct?

(A) The operational intensity of matrix–vector multiplication increases linearly with $N$, while the operational intensity of matrix–matrix multiplication increases quadratically with $N$.
(B) For sufficiently large $N$, matrix–vector multiplication is memory-bandwidth bound on both machines, and Machine B achieves higher performance due to its higher memory bandwidth.
(C) For sufficiently large $N$, matrix–matrix multiplication becomes compute-bound on Machine A, allowing it to outperform Machine B despite having lower memory bandwidth.
(D) The roofline model alone is insufficient to compare the performance of the two machines on these kernels, because instruction ordering and multiplier latency dominate performance.

What is the Segment Index derived from the logical address $16A4_{16}$?

(A) 3
(B) 4
(C) 5
(D) 6

What is the Segment Base Address (in hexadecimal) retrieved from the Segment Table?

(A) $0x200$
(B) $0x400$
(C) $0x500$
(D) $0x600$

What is the calculated Linear Address (in hexadecimal)?

(A) $0x2A4$
(B) $0x6A4$
(C) $0x4A4$
(D) $0x5A4$

What is the Virtual Page Number (VPN) index used to look up the Page Table?

(A) 24
(B) 25
(C) 26
(D) 27

What is the final Physical Address (in hexadecimal)?

(A) $0x864$
(B) $0x424$
(C) $0x244$
(D) $0xD44$

What is the maximum number of files that the TFS file system can manage?

(A) 24
(B) 80
(C) 5
(D) 16
🖼️【此處有附圖，見下方】

The start address of the inode table on the TFS file system is 12 KB. This TFS file system uses five IBs to store the entire inode table. An IB stores multiple inodes, and the inode index starts from 0 in IB0 and is incrementally increased. The last inode is preserved in IB4 with the index 79. Which IB preserves the inode where its index is 16?

(A) 3
(B) 2
(C) 1
(D) 0

The disk typically consists of a large number of addressable sectors, each of which is 512 bytes in size. To fetch the inode where its index is 16, to which sector of the disk would the file system issue a read?

(A) 32
(B) 16
(C) 8
(D) 4

In recent years, general purpose processors have increasingly been supplemented, and in some cases replaced, by specialized accelerators such as GPUs and TPUs. These accelerators depart from traditional CPU designs by prioritizing high throughput computation, data level parallelism, and memory bandwidth over single thread latency and complex control flow. While such designs can deliver orders of magnitude improvements for selected workloads, they also introduce new architectural tradeoffs at the system level. The following question examines the architectural principles that distinguish accelerators from CPUs, and the system-level consequences of these design choices.

Consider a multi-accelerator system executing a workload that performs frequent collective operations (e.g., all-reduce) on large tensors. Which interconnect property is most critical for maximizing sustained throughput?

(A) Minimum single-hop latency
(B) Peak bisection bandwidth
(C) Support for hardware cache coherence
(D) Ability to route packets out of order

Compared to a monolithic accelerator with the same aggregate compute resources, a chiplet-based accelerator design necessarily introduces which architectural tradeoff?

(A) Reduced arithmetic throughput per cycle
(B) Increased on-chip memory capacity
(C) Additional communication latency and bandwidth overhead
(D) Lower instruction issue width

An accelerator sustains a peak compute throughput of 100 TFLOP/s and a sustained memory bandwidth of 10 TB/s. A kernel has an arithmetic intensity of 4 FLOPs per byte. Which statement is correct?

(A) The kernel is compute-bound at 100 TFLOP/s.
(B) The kernel is memory-bound at 40 TFLOP/s.
(C) The kernel is control-bound due to insufficient parallelism.
(D) The roofline model cannot be applied to this kernel.

Given a fixed power and area budget for an accelerator intended primarily for large-model inference, which architectural investment most directly improves end-to-end throughput?

(A) Increasing peak floating-point units per cycle
(B) Increasing instruction window size
(C) Increasing sustained on-chip and inter-chip data bandwidth
(D) Increasing branch prediction accuracy

Which statement is correct?

(A) If register $s1 is replaced with$t0, register utilization can be improved without side-effects.
(B) It is not necessarily necessary to save register $s1 at the beginning of function, which can reduce one instruction to save. (C) It is necessary to save registers$ra and $a0 at the start of each function to avoid data loss in situations where a callee subsequently acts as a caller.
(D) One of the reasons why using slti and beq rather than using a single blti (branch less than immediate) instruction is that blti requires two immediate fields that cannot be accommodated within a single 32-bit MIPS instruction format.

Assume that the execution of each j, jal, beq, and jr instruction takes 3 clock cycles. As invoking the function fib(2), the total number of clock cycles to perform all j, jal, beq, and jr instructions is:

(A) 30
(B) 27
(C) 24
(D) 33

The above tables present the register numbers and the corresponding translations of assembly instructions into machine codes. The machine code of the instruction beq $t0,$0, L1 (Line 7) is:

(A) $000100\,01000\,00000\,1111\,1111\,1111\,1110_2$
(B) $100000\,01000\,00000\,0000\,0000\,0000\,0010_2$
(C) $000100\,01000\,00000\,0000\,0000\,0000\,0010_2$
(D) $100000\,01000\,00000\,1111\,1111\,1111\,1110_2$