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

Which of the following x86 instructions cannot be executed in Ring 3 privilege level?

(A) MOV CR0, EAX.
(B) HLT.
(C) LGDT.
(D) LIDT.

Which of the following x86 instructions are position-independent (i.e., the code can be executed at any memory address)?

(A) MOV EAX, 1.
(B) XOR EBX, EBX.
(C) INT 0x80.
(D) ADD EAX, 1.

Consider the following C program on x86_64 Linux.

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <sys/mman.h>
04 #include <unistd.h>
05
06 int main() {
07
08 size_t pagesize = sysconf(_SC_PAGESIZE);
09
10 void *buffer = aligned_alloc(pagesize, pagesize);
11 if (!buffer) {
12 perror("Failed to allocate memory");
13 return EXIT_FAILURE;
14 }
15
16
17 if (mprotect(buffer, pagesize, PROT_READ | PROT_WRITE | PROT_EXEC) == -1) {
18 perror("mprotect - error 1");
19 free(buffer);
20 return EXIT_FAILURE;
21 }
22
23 sprintf((char *)buffer, "This is a test.\n");
24
25 if (mprotect(buffer, pagesize, 0) == -1) {
26 perror("mprotect - error 2");
27 free(buffer);
28 return EXIT_FAILURE;
29 }
30
31 printf("%s", (char *)buffer);
32 free(buffer);
33
34 return EXIT_SUCCESS;
35 }

Which of the following statement(s) are true?

(A) The program will output “This is a test.” on the screen.
(B) The memory block pointed to by buffer will be allocated on the stack.
(C) The variable pagesize will be allocated on the stack.
(D) After a successful memory allocation, the value of the buffer pointer will be a multiple of pagesize.

Which statement(s) best describes the Earliest Deadline First (EDF) scheduling algorithm?

(A) EDF prioritizes tasks based on their computational complexity, scheduling the most complex tasks first.
(B) EDF is a preemptive scheduling algorithm that prioritizes tasks based on their proximity to a fixed deadline.
(C) EDF assigns priority to tasks based on the order of their arrival, with the earliest arrivals being processed first.
(D) EDF is a non-preemptive scheduling algorithm that schedules tasks in a round-robin fashion, regardless of their deadlines.

On x86_64 systems, Linux system calls are made using the syscall instruction with the following calling conventions:

• RAX contains the system call number.
• RDI, RSI, RDX, R10, R8, and R9 are used to pass up to six arguments to the system call.
• RCX and R11 are clobbered after the syscall instruction.
• The return value of the system call is placed in the RAX register.

The implementation of the sys_write (write) system call in the Linux kernel is as follows.

SYSCALL_DEFINE3(write, unsigned int, fd, const char __user *, buf, size_t, count)
{
return ksys_write(fd, buf, count);
}

The man pages description for sys_write is as follows.

write(2) — System Calls Manual — write(2)

NAME
write — write to a file descriptor

LIBRARY
Standard C library (libc, -lc)

SYNOPSIS
#include <unistd.h>

ssize_t write(int fd, const void buf[.count], size_t count);

DESCRIPTION
write() writes up to count bytes from the buffer starting at buf to the file referred to by the file descriptor fd.

The number of bytes written may be less than count if, for example, there is insufficient space on the underlying physical medium, or the RLIMIT_FSIZE resource limit is encountered (see setrlimit(2)), or the call was interrupted by a signal handler after having written less than count bytes. (See also pipe(7).)

Which of the following statement(s) is true for invoking the sys_write system call?

(A) Need to assign fd to RAX.
(B) Need to assign the address value of buf to RSI.
(C) The actual number of bytes written may be less than the number specified by count.
(D) User-level programs can use syscall to call any function in the kernel.

Which of the following statements on process are true?

(A) In UNIX, a new process is created by the fork() system call. The new process consists of a copy of the address space of the original process.
(B) A thread shares with other threads belonging to the same process its code section, data section, stack, and other operating-system resources, such as open files and signals.
(C) By using the standard C library, a user program can easily read or write a file from storage devices without the help of operating systems.
(D) When a context switch occurs, the kernel saves the context of the old process in its PCB and loads the saved context of the new process scheduled to run. The context includes the value of the CPU registers, the process state, and memory-management information.

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

(A) NAND-flash-based SSDs suffer from limited lifetime. The SSD controller runs a software layer to alleviate this issue by leveling writes without the help from the operating system.
(B) When the CPU detects that a controller has asserted a signal on the interrupt-request line, the CPU performs a state save and jumps to the interrupt-handler routine at a fixed address in memory.
(C) When DRAM generates an interrupt, the CPU saves the state of the user code, switches to kernel mode, and dispatches to the kernel routine or thread that implements the requested service.
(D) In Linux, the swap space is now used only for anonymous memory. That is, Linux will not swap out storage-backed files.

Which of the following statements on memory management are true?

(A) When a CPU needs to access data in DRAM, the DRAM controller verifies the existence of the data. If the data is not found in the main memory, the DRAM controller generates a page fault.
(B) In a system adopting paging, when a process is to be executed, its pages are loaded into any available memory frames from their source (a file system or the backing store).
(C) In Linux and Solaris, the slab-allocation algorithm uses caches to store kernel objects. When a new object for a kernel data structure is needed, the allocator can assign any free object from the cache to satisfy the request.
(D) On Linux, which adopts paging, multiple processes can share one page table to save memory consumption.

Which of the following statements on virtual memory management are true?

(A) After enabling virtual memory, CPUs operating in user mode can decide to access either physical or virtual addresses based on the compiler configurations.
(B) If a required data is not in physical memory, the user process raises a page fault and runs the page fault handler to transfer the data from storage to memory, possibly relying on DMA for efficiency.
(C) When a process forks a child by using Copy-on-Write (COW), the process and its child share all memory pages until one of them writes to the page.
(D) When a logical address is generated by an x86 CPU, the MMU first checks if its page number is present in the TLB. If not, the CPU walks the page table to get the physical address without the help from the operating system.

Which of the following statements on file system are true?

(A) A file control block (FCB), an inode in UNIX file systems, contains information about the file, including ownership, permissions, and location of the file contents.
(B) File-name extensions (e.g., .txt, .jpeg) on UNIX systems are necessary and critical, as they guide the operating system to run the right application (e.g., text editor or gallery) for opening files.
(C) Multiple processes may be allowed to map the same file concurrently and to allow sharing of data. Writes by any of the processes modify the data in virtual memory and can be seen by all others that map the same section of the file.
(D) A disk can be sliced into multiple partitions and each partition is not functional without containing a file system. That is, each partition must contain one file system (e.g., NTFS, Ext4).

For the 32-bit MIPS ISA, an instruction is coded in 32-bit. Different addressing modes are defined in the ISA for instruction and data accessing. Which of the following statements about the MIPS instruction design are true?

(A) The immediate addressing mode and the base addressing mode both use the I-type instruction format, while the PC-relative addressing mode does not.
(B) There are 5 addressing modes in the MIPS ISA.
(C) The immediate values in the pseudodirect addressing mode use word addresses.
(D) A 32-bit constant that has non-zero upper and lower 16-bit halves cannot be loaded into a register using only one instruction (excluding pseudoinstructions).

The following in-order pipelined five-stage MIPS processor design shown in Fig. 1 has a bug.

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

Note that the processor has no forwarding paths, and if it detects data hazards at the decode stage (the hazard control unit is not shown), the pipeline stages will stall properly. If we use the buggy processor to execute the following code segment:

add $4,$1, $2 or$0, $1,$1
addi $2,$2, 3
add $3,$4, $3 add$1, $4,$0

Assume that initially the registers $0 through$4 contain the values 0 through 4, respectively; that is, register $0 is 0, register$1 is 1, and so on. Which of the following statements are true right after the writeback stage of the fourth instruction (add $3,$4, $3) is complete?

(A) Register $0 has a value of 0. (B) Register$1 has a value of 7.
(C) Register $1 has a value of 1. (D) Register$4 has a value of 4.

Assume that we have a classical five-stage pipelined 32-bit MIPS processor with a branch predictor and all required forwarding mechanisms. Which of the following statements are true?

(A) If a load instruction is immediately followed by a conditional branch that is dependent on the load result, and we assume that the branch condition is evaluated on the decode stage, one stall cycle is needed to execute the two instructions properly.
(B) The 16-bit immediate value in a branch instruction is imm, and the branch target address is computed by $PC=PC+4+\operatorname{sign\text{-}ext}(imm)$. Here, $\operatorname{sign\text{-}ext}(imm)$ means sign extension of the parameter imm to 32-bit.
(C) For better performance, the branch target buffer that stores the destination PC for a branch is usually implemented as a tagged memory.
(D) A branch predictor using the information of both a local branch instruction and the global behavior of recently executed branches is called a correlating predictor.

Assume that we have two processors, P1 and P2, that are different microarchitecture implementations of the same ISA. The instructions can be divided into four classes according to their CPI (classes A, B, C, and D). P1 has a clock cycle of 1 ns and CPIs of 1, 4, 2, and 3, respectively, for each instruction class. P2 has a clock cycle of 0.8 ns and CPIs of 2, 2, 2, and 2, respectively, for each instruction class.

Given a program with its instructions divided into the four classes as follows: 30% class A, 25% class B, 20% class C, and 25% class D. Which of the following statements about the execution of this program using processor P1 and P2 are true?

(A) The average CPI of P1 is larger than that of P2.
(B) The execution time of P1 is larger than that of P2.
(C) If both processors run at the same clock rate, their CPIs do not change.
(D) For the processor that has longer execution time, it is possible to improve only one of its instruction classes so that it becomes faster.

Which of the following statements about the MIPS ISA design are true?

(A) Not all instructions using the I-type format perform sign-extension on the 16-bit immediate values.
(B) The jump instruction, j, can always jump from address A to address B as long as the offset between A and B is less than $2^{15}$ words.
(C) MIPS branch instructions are encoded using the I-type format that contains only two registers. This design is based on the principle of making the common case fast.
(D) If we add more R-type instructions to the ISA, and allow the compiler to make use of these extra instructions to compile a program, then the program size in terms of the number of instructions will always be smaller than or equal to the size compiled using the original ISA.

Which of the following statements are true?

(A) AI accelerator chips require access to extensive data during their operation. Therefore, enhancing memory access and mitigating the impact of large memory requirements pose significant challenges in the design of AI accelerators.
(B) Conducting Large Language Model (LLM) inference at the edge of computing provides a direct enhancement to information security.
(C) High-performance GPUs are crucial for developing LLMs. Consequently, power optimization is no longer a concern in GPU design.
(D) The increase of a CPU’s clock rate is constrained by CPU’s power consumption, while a GPU, with its distinct architecture, avoids the limitation of clock rate imposed by power consumption.

Consider the CPU performance and the instruction count at the machine level, which of the following statements are true?

(A) When comparing two algorithms designed to solve the same problem, the one with higher complexity typically demands a greater number of instructions to complete the operation compared to the other.
(B) As we implement the same algorithm in Python and C programming languages, the Python program generally requires a greater number of instructions than the C program to execute the algorithm.
(C) The Millions of Instructions Per Second (MIPS) performance metric may not be equitable, as an instruction set with lower CPI can achieve a higher clock rate but necessitates a larger number of instructions.
(D) Google’s warehouse-scale computer centers typically maintain server utilization levels ranging from 70% to 90%, ensuring the optimal utilization of server resources.

Which of the following statements are correct?

Fig. 2:

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

Fig. 3:

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

Fig. 4:

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

(A) Fig. 2 shows a correct 3-bit × 3-bit multiplier.
(B) Fig. 3 shows a wrong 32-bit × 32-bit multiplier.
(C) The most significant bit of a carry look-ahead adder often experiences elevated input loading, leading to increased delays. Employing a multi-level carry look-ahead adder helps mitigate the issue of high input loading.
(D) Consider the 16-bit two-level carry look-ahead adder in Fig. 4 and the timing of transitioning to correct values on each signal line. $c_1$ transitions to the correct value before $c_{15}$, $G_{(i-4)-(i-1)}$ and $P_{(i-4)-(i-1)}$ transition to correct values prior to $c_{4i}$, for $i=1$ to $3$, and $c_{4i}$ transitions to the correct value prior to $c_{4i+1}$ to $c_{4i+3}$, for $i=1$ to $3$.

Which of the following statements about computer arithmetic are correct?

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

(A) The hardware depicted in Fig. 5 serves dual functions, functioning as both a multiplier and a divider. The Product/Remainder register necessitates a shift-right operation for multiplication and a shift-left operation for division. The control test unit receives its input from P2 when operating as a multiplier and from P1 when operating as a divider.
(B) For floating-point addition, aligning decimal points involves shifting the number with the smaller exponent to ensure proper alignment. This is because rounding the significand of the number with smaller exponent has a minor impact on accuracy. Conversely, if decimal points are aligned by shifting the number with the larger exponent, it may result in overflow on the significand of the number with the larger exponent.
(C) Addition is associative for both integers and floating-point numbers.
(D) Assuming the accuracy of a floating number is to the second decimal place and rounding half down with additional guard, round, and sticky bits, the ULP of the addition $5.01 \times 10^2 + 1.56 \times 10^5$ is $0.499$.

Note: $\operatorname{round\_half\_down}(x)=\lfloor x-0.5 \rfloor$.

The (7,4) Hamming code has bit indices ranging from 1 to 7 (left to right). Parity bits $p_1$, $p_2$, and $p_3$ are bits 1, 2, and 4, respectively. Data bits are bits 3, 5, 6, and 7. Which of the following statements are true?

(A) The word 1010111 is not correct, and bit 6 should be 0.
(B) Add an additional parity bit $p_4$ for the whole word and make it satisfy $p_1+p_2+d_1+p_3+d_2+d_3+d_4+p_4=0$ ($p_4$ even). This will increase the Hamming distance to 4.
(C) The word 01000101 is not correct. $p_4$ should be 0.
(D) The word 10010011 is not correct and should have double errors since $p_4$ even holds and $(p_1,p_2,p_3)_{\text{computed}}+(p_1,p_2,p_3)_{\text{read}}=(0,1,0)$.

For the command-line argument $argv[1]$, which of the following situations would corrupt the stack?

(A) If $argv[1]$ contains a non-printable character.
(B) If $argv[1]$ contains a space.
(C) If $argv[1]$ is a comma-delimited string of the phone numbers of all NYCU CS faculty members.
(D) None of the above.

If the stack is corrupted, which of the following is least likely to be affected?

(A) The program control flow.
(B) The local variables.
(C) The function call arguments.
(D) The program code.

How many page faults would be generated while running Program 1?

(A) 1
(B) 128
(C) 256
(D) 65536

How many page faults would be generated while running Program 2?

(A) 1
(B) 128
(C) 256
(D) 65536

How many total stall cycles will be inserted into the pipeline for proper execution throughout the entire program?

(A) 8
(B) 12
(C) 16
(D) 18

How many stall cycles are due to control hazards?

(A) 2
(B) 4
(C) 6
(D) 8

How many stall cycles can be removed by adding only the forwarding path from the EX/MEM register to one of the inputs of the ALU in the execute stage?

(A) 6
(B) 8
(C) 10
(D) 12

Which configuration of the hierarchical memory system is true?

(A) The hierarchical memory system is suited to apply physically tagged and virtually indexed scheme since the virtual page offset field is equal to or longer than the index field for cache addressing.
(B) The virtual memory has $2^8$ pages.
(C) The virtual page number field has a length of 6 bits.
(D) The tag field of physical address has a length of 8 bits.

Without regarding the disadvantage of virtually addressed cache, the virtually addressed cache is used in this computer. Assume the cache is empty initially. Given the following virtual address accesses to access cache: 0x8A78, 0x8A64, 0x8876, 0x8FF8, 0x8DE7. Which statement is true?

(A) The result of access to 0x8A64 is miss.
(B) The result of access to 0x8876 is hit.
(C) The result of access to 0x8FF8 is miss and the block containing 0x8A78 is replaced.
(D) The result of access to 0x8DE7 is miss and the block containing 0x8FF8 is replaced.

If the CPU base CPI = 1 and the CPU clock is running at 5 GHz. The miss rate per lw/sw instruction in primary cache is 2%. There are 25% lw/sw instructions in a program. The access time to the second-level cache is 6 ns and the global miss rate to main memory is 0.2% with the miss penalty of 240 ns. Which statement is true?

(A) If the CPU has only primary cache without the second-level cache, the effective CPI is 6.
(B) If the CPU has only primary cache without the second-level cache, the effective CPI is 7.5.
(C) The CPU with 2-level cache has the effective CPI of 4.9.
(D) The CPU with 2-level cache has the effective CPI of 4.2.