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

In virtual memory management, which of the following are features of paging?

(A) To increase the size of the physical memory.
(B) To divide a process's address space into fixed-size blocks and load only necessary pages into physical memory.
(C) To reduce the CPU clock speed.
(D) To prevent processes from accessing each other's memory spaces.

Which of the following statements on memory management are true?

(A) Managing memory via the slab allocator not only minimizes internal and external fragmentations but also efficiently handles the frequent allocation and deallocation of kernel objects.
(B) As page tables are per-process data structures, the page table and other register values, such as the instruction pointer, are together stored in the process control block of each process.
(C) The x86 64-bit CPU architecture currently provides a 48-bit virtual address with support for page sizes of 4 KB, 2 MB, or 1 GB. Larger page sizes help reduce the overhead of page table traversal.
(D) After enabling the memory-management unit (MMU), the user program never accesses real physical addresses. That is, the user program can only work on the virtual address space.

Which of the following statements on virtual memory are true?

(A) If the required page data is not in memory, the user process raises a page fault and the CPU runs the page fault handler to transfer the corresponding data into memory.
(B) Adopting copy-on-write during process creation allows the parent and child processes initially to share the same pages. If either process writes to a shared page, a copy of the page is created.
(C) In Linux, swap space is used for pages not associated with a file (known as anonymous memory); these pages include the stack and heap for a process.
(D) In x86 systems, when a CPU encounters a virtual address that results in a TLB miss, the operating system performs page table walking for translating a virtual address to a physical address.

Which of the following statements on processes are true?

(A) A process control block serves as the repository for all the data needed to start, or restart, a process. It contains scheduling information, local variables, and kernel data structure.
(B) Interrupts cause the operating system to change a CPU core from its current task and to run a kernel routine. The system needs to save the current context of the process running on the CPU core so that it can restore that context when its processing is done.
(C) Traditional UNIX systems identify the init process as the root of all child processes. In UNIX systems, a process clones itself to create new processes. Thus, all the processes in the system are the descendants of the init process, either directly or indirectly.
(D) A user program must use system calls to access files stored in storage devices. But a program can directly access the allocated heap data from memory without the help from operating systems.

Consider a system with the following resource allocation state. There are five processes $P1$–$P5$ and three resource types. The resource allocation tuple $(x,y,z)$ means $x$ instances of resource type 1, $y$ instances of resource type 2, and $z$ instances of resource type 3.

Given the current system state, which of the following are true when checking the safety of granting Process $P2$ a request of $(1,0,1)$ according to the Banker's Algorithm?

(A) After granting the request, the system will remain in a safe state.
(B) If the system enters an unsafe state, there is still the possibility that no deadlock will actually occur.
(C) There are enough resources available to grant the request.
(D) The current system state is unsafe.

Which of the following statements are true regarding interrupt handling in operating systems?

(A) Interrupts are signals that inform the processor of an event that needs immediate attention.
(B) Interrupts can only be generated by hardware, not software.
(C) When an interrupt occurs, the processor stops executing the current program and transfers control to the interrupt handler.
(D) Interrupts are prioritized, meaning the operating system may choose to delay handling a lower-priority interrupt in favor of a higher-priority one.

Following is the memory map of the Linux utility program /usr/bin/cat. Which of the following statements are true?

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

Memory map:

00400000-0040b000 r-xp 00000000 fd:01 1234567 /usr/bin/cat
0060a000-0060b000 r--p 0000a000 fd:01 1234567 /usr/bin/cat
0060b000-0060c000 rw-p 0000b000 fd:01 1234567 /usr/bin/cat
00e7a000-00e9b000 rw-p 00000000 00:00 0 [heap]
7f8b6c000000-7f8b6c021000 rw-p 00000000 00:00 0
7f8b6c021000-7f8b70000000 ---p 00000000 00:00 0
7f8b71a8d000-7f8b71aa3000 r-xp 00000000 fd:01 2345678 /lib/x86_64-linux-gnu/libgcc_s.so.1
7f8b71aa3000-7f8b71ca2000 ---p 00016000 fd:01 2345678 /lib/x86_64-linux-gnu/libgcc_s.so.1
7f8b71ca2000-7f8b71ca3000 r--p 00015000 fd:01 2345678 /lib/x86_64-linux-gnu/libgcc_s.so.1
7f8b71ca3000-7f8b71ca4000 rw-p 00016000 fd:01 2345678 /lib/x86_64-linux-gnu/libgcc_s.so.1
7ffc445e7000-7ffc44608000 rw-p 00000000 00:00 0 [stack]
7ffc446da000-7ffc446dd000 r--p 00000000 00:00 0 [vvar]
7ffc446dd000-7ffc446df000 r-xp 00000000 00:00 0 [vdso]
fffffffff6000000-fffffffff6010000 --xp 00000000 00:00 0 [vsyscall]

(A) The CPU architecture is 32-bit.
(B) The program contains C library code.
(C) If we put shellcode on a buffer allocated by `malloc()`, the shellcode will be non-executable.
(D) The program has three child processes.

Which of the following statements about the Round Robin (RR) scheduling algorithm are correct?

(A) It can lead to starvation of certain processes.
(B) It ensures quicker process completion for all processes.
(C) Decreasing the RR time quantum will increase the turnaround time.
(D) It ensures that all processes receive equal CPU time.

Which of the following statements on process schedulers and threads are true?

(A) Context switching is typically faster between threads than between processes. The reason is that threads share resources, including page table and user stack, of the process to which they belong.
(B) In Linux, Completely Fair Scheduler (CFS) allocates a larger time quantum to higher-priority processes. Processes with the same priority will receive the same time quantum.
(C) The dispatcher involved in the process scheduler switches process contexts between the current and the next-scheduled user processes in the user mode so as to minimize the dispatching latency.
(D) In contrast, during thread creation, the new thread shares many data structures, like memory space and file descriptors, with the parent process instead of copying them.

Which of the following statements on I/O systems are true?

(A) For most computers, the bootstrap is stored in Non-Volatile Memory (NVM) flash memory firmware on the system motherboard and mapped to a known memory location.
(B) In Linux, if the requested file is not already open, the directory structure is searched to locate the file by its name. The directory structure may reside in memory or on the storage devices.
(C) In Linux, page cache usually caches file in DRAM because DRAM is faster than storage devices and data can be retained in DRAM after the system powers down.
(D) To concurrently support multiple types of file systems, Virtual File System (VFS) layer separates file-system-generic operations from their implementation by defining a VFS interface.

In a pipelined processor, a program has $5\%$ instructions belonging to load and store instructions. This program spends $20\%$ of its execution time for load instructions and $10\%$ of its execution time for store instructions. Since the data cache miss rate is high in this program, the processor architect proposes a new data cache architecture that improves the $4\times$ execution time of load instructions ($4\times$ faster) and $2\times$ execution time of store instructions ($2\times$ faster). Then, this new processor will achieve $1.25\times$ speedup. Which statements are correct when using the processor with this new cache architecture?

(A) This new cache architecture helps increase the processor's clock frequency.
(B) The value of cycle per instruction (CPI) becomes small after using this new cache architecture in the processor.
(C) This new cache architecture increases the instruction counts (ICs).
(D) This new cache architecture helps reduce the cache miss penalty.

A directed-mapped data cache has a memory address length of 32 bits. The sizes of the tag, index, and offset fields in this directed-mapped cache are 26 bits, 4 bits, and 2 bits, respectively. The processor executes Program 1 and observes that its cache miss rate is high. What kind of cache misses causes such a problem when using a directed-mapped cache in this processor?

Program 1:

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

addi  $t0, $0, 3
loop: beq   $t0, $0, done
      lw    $t1, 0x4($0)
      lw    $t2, 0x8($0)
      lw    $t3, 0xC($0)
      lw    $t4, 0x10($0)
      addi  $t0, $t0, -1
      j     loop
done:

(A) Compulsory cache miss
(B) Conflict cache miss
(C) Capacity cache miss
(D) Cold start cache miss

A data cache usually has multiple cache blocks. The set-associative cache includes tag, index, and offset fields to manage each cache block. What are the impacts when increasing the size of cache blocks in a data cache?

(A) The large cache block facilitates the usage of temporal locality on the data cache.
(B) Large cache miss penalty.
(C) Reducing the tag overhead.
(D) Decreasing the cache miss rate.

A data cache in a processor employs a 2-way set-associative cache where the word size is 32 bits. The sizes of the tag, index, and offset fields in this set-associative cache are 26 bits, 4 bits, and 2 bits, respectively. Which statements are correct when this processor executes Program 2?

Program 2:

addi  $t0, $0, 4
loop: beq   $t0, $0, done
      lw    $t1, 0x6($0)
      lw    $t2, 0x46($0)
      addi  $t0, $t0, -1
      j     loop
done:

(A) The cache miss rate is $25\%$.
(B) Increasing the size of the cache can reduce the cache miss rate.
(C) The cache miss rate will increase when using the directed-mapped cache where its tag, index, and offset sizes are 27 bits, 3 bits, and 2 bits, respectively.
(D) The cache miss rate will increase when using the fully associative cache.

A processor runs at 4 GHz and has a CPI of 1.4 without including the stall cycles due to cache misses. Load and store instructions count for $30\%$ of all instructions. The processor has an I-cache and a D-cache. The hit time is 1 clock cycle. The I-cache has a $3\%$ miss rate. The D-cache has a $5\%$ miss rate on load and store instructions. The miss penalty is 50 ns, which is the time to access and transfer a cache block between main memory and the cache. Which of the following statements are correct?

(A) The miss penalty of this processor is 200 clock cycles.
(B) The average memory access time (AMAT) for instruction access is 6 clock cycles.
(C) The number of stall cycles per instruction is 10 clock cycles.
(D) The overall IPC of this processor is 0.096.

Which of the following statements are true?

(A) In 2's complement, the value 0 has a unique representation.
(B) In IEEE 754 single-precision format, the value 0 has two different representations.
(C) Overflow will never occur when adding two 2's complement numbers of different signs.
(D) Storing the 32-bit number 0xABCDD CBA in memory results in the same outcome regardless of whether little endian or big endian is used.

Given an IEEE 754 single-precision representation format in the table below and the bias value is 127. Which of the following statements are correct?

(A) The number $-1.1_2\times2^{-1}$ has the single-precision representation:
Sign $=-1$, Exponent $=0111\ 1110_2$, Fraction $=100\ 0000\ 0000\ 0000\ 0000\ 0000_2$.

(B) The number $101.1_2\times2^{131}$ has the single-precision representation:
Sign $=0$, Exponent $=00000000_2$, Fraction $=001\ 0110\ 0000\ 0000\ 0000\ 0000\ 0000_2$.

(C) The smallest positive single-precision normalized number is $1.0_2\times2^{-126}$.

(D) The smallest positive single-precision denormalized number is $1.0_2\times2^{-127}$.

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

Consider the following code sequence executing on a 5-stage pipelined processor. The processor has both the hazard detection unit and the forwarding unit for data hazard. Assume that the code sequence starts executing at clock cycle 1. At clock cycle 8, where do the two ALU inputs come from?

add x28, x31, x29
ld  x31, 32(x29)
and x30, x29, x31
sd  x5, 20(x30)
sub x5, x5, x30
or  x29, x29, x30

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

(A) Both are from ID/EX.
(B) One is from ID/EX and one is from EX/MEM.
(C) One is from ID/EX and one is from MEM/WB.
(D) One is from EX/MEM and one is from MEM/WB.

Consider a pipeline CPU with five stages: IF, ID, EX, MEM, WB. Stall cycles due to mis-predicted branches increase the CPI of the pipeline. Given a code sequence with instruction mix as follows: R-type: $50\%$, beq: $25\%$, and lw & sw: $25\%$. Assume branch prediction accuracy is $20\%$ and there are no data hazards and cache misses. It is clear that the system suffers from extra CPIs due to mis-predicted branches. Which of the following statements about the extra CPI are correct?

(A) The extra CPI is 0.4 if the mis-predicted branch outcomes are corrected in the MEM stage.
(B) The extra CPI is 0.6 if the mis-predicted branch outcomes are corrected in the MEM stage.
(C) The extra CPI is 0.4 if the mis-predicted branch outcomes are corrected in the ID stage.
(D) The extra CPI is 0.2 if the mis-predicted branch outcomes are corrected in the ID stage.

Consider the 2-bit predictor shown in the figure below, and assume the predictor starts at the top-left state (i.e., the “strongly predict taken” state). Given the branch outcome sequence: N, T, N, N, T, where T = taken and N = not-taken, which of the following statements are correct?

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

(A) The accuracy rate is $1/5$.
(B) The overall accuracy rate is $2/5$ if the pattern repeats twice (i.e., N, T, N, N, T, N, T, N, N, T).
(C) The overall accuracy rate is $1/3$ if the original pattern repeats three times.
(D) The overall accuracy rate is about $1/3$ if the original pattern repeats 10000 times.

How much data can be stored in the disk array?

(A) 1 TB
(B) 2 TB
(C) 3 TB
(D) 4 TB

What is the maximum read throughput when an application reads data from the disk array?

(A) 100 MB/s
(B) 200 MB/s
(C) 300 MB/s
(D) 400 MB/s

What is the maximum number of failed disks that can be tolerated?

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

Assume that none of the disk data is cached in memory. What is the minimum number of disks that need to be involved in a write to the disk array?

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

What is the minimum number of levels for this multi-level page table?
(A) 3
(B) 4
(C) 5
(D) 6

If the number of levels is set to the minimum, what is the maximum number of pages in the bottom level?

(A) $2^{39}$
(B) $2^{38}$
(C) $2^{37}$
(D) $2^{36}$

If the number of levels is set to the minimum, how many pages are there in the top level?

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

How many cache blocks are in the 64 KB L1 data cache?

(A) 0.5K cache blocks
(B) 1K cache blocks
(C) 1.5K cache blocks
(D) 2K cache blocks

How many bits are used in the tag of such a data cache?

(A) 14 bits
(B) 15 bits
(C) 17 bits
(D) 18 bits

Which fields in the data cache will increase when increasing the length of the memory address from 32 bits to 64 bits?

(A) Tag
(B) Index
(C) Offset
(D) Valid bit

What instruction is in the EXE stage at clock cycle 5?

(A) ld
(B) sub
(C) add
(D) bubble

What instruction is in the MEM stage at clock cycle 5?

(A) ld
(B) sub
(C) add
(D) bubble

What instruction is in the WB stage at clock cycle 5?

(A) ld
(B) sub
(C) add
(D) bubble

What are the values of signals ALUsrc and MemToReg, respectively, at clock cycle 5?

(A) 0, 0
(B) 0, 1
(C) 1, 0
(D) 1, 1