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

Consider the following C code. Which outputs are possible?

(A) ABCED.
(B) AEBCD.
(C) ABDCE.
(D) AEBDC.

int main() {
    printf("A");
    if (fork() == 0) {
        usleep(((rand() % 5) + 1) * 10000); /* wait for a random time */
        printf("B");
        if (fork() == 0) {
            usleep(((rand() % 5) + 1) * 10000); /* wait for a random time */
            printf("C");
        }
        else {
            wait(NULL);
            printf("D");
        }
    }
    else {
        usleep(((rand() % 5) + 1) * 10000); /* wait for a random time */
        printf("E");
        wait(NULL);
    }
    return 0;
}

Consider a system with 15 resources and 4 threads: $T_0$, $T_1$, $T_2$, and $T_3$. The second column in the following table shows the maximum number of resources needed by each thread, and the third column shows the number of resources each thread is currently holding. Let $\hat{x}$ be the maximum value of $x$ (shown below) that can still keep the system in a safe state. Which statements are correct?

(A) $\hat{x}=13$.
(B) With $\hat{x}$, $\langle T_0,T_1,T_2,T_3\rangle$ is a safe sequence.
(C) Even for some value of $x$ that makes the system in an unsafe state, it may not lead to a deadlock.
(D) The way we use here to see whether a system is safe only applies to one type of resource. The banker's algorithm extends it to multiple types of resources.

Which statements about semaphore are correct?

(A) Two processes sharing two common binary semaphores may result in a deadlock.
(B) If we use a binary semaphore to implement a mutex lock, the semaphore should be initialized to 0.
(C) If we invoke an $x.\mathrm{signal}()$ operation on a condition variable $x$ but no process is suspended on $x$, then the state of $x$ remains unchanged.
(D) If we invoke a $\mathrm{signal}(S)$ operation on a semaphore $S$ but no process is suspended on $S$, then the state of $S$ remains unchanged.

A process could be in new, running, waiting, ready, or terminated state. Which statements about process states are correct?

(A) If a process invokes a blocking $\mathrm{send}()$ for message passing, the process will enter the waiting state.
(B) When a process must wait on a spin-lock, the process will enter the waiting state.
(C) A process kept staying in the waiting state will not incur context-switching overhead.
(D) A $\mathrm{wakeup}()$ operation changes the state of a process from the waiting state to the running state.

Which statements about CPU scheduling are correct?

(A) Compared with first-come first-serve (FIFO), nonpreemptive shortest-job-first scheduling results in fewer context switches.
(B) Shortest-remaining-time-first scheduling can lead to starvation.
(C) A voluntary context switch occurs to a process when its time slice has expired.
(D) Processor affinity, which tries keeping a thread running on the same processor, is a load-balancing technique for multiprocessor scheduling in a symmetric multiprocessing (SMP) system.

In addition to a reference bit, a modify bit can be added to form the bit pair (reference, modify) associated with a page to improve the second-chance algorithm used in page replacement, where the reference bit is 1 if the page has been referenced and the modify bit is 1 if the page has been updated in the past round. Divide the pages into four classes: $(0,0)$, $(0,1)$, $(1,0)$, and $(1,1)$.

(A) Both reference bit and modify bit, if being 1, are cleared to 0 on a circular round of the page replacement algorithm, as a way to give the second chance.
(B) Pages in class $(0,0)$ should be replaced first, while the pages in class $(1,1)$ should be replaced last.
(C) Pages in class $(0,1)$ should be replaced before pages in class $(1,0)$.
(D) Pages in class $(0,1)$, if picked to replace and dirty, should be written out before replacement.

Consider memory-mapped files where disk blocks of a file are mapped to pages in memory, so that file I/O can be treated as routine memory access.

(A) To load a file into memory, the $\mathrm{mmap}()$ system call loads initially the entire file into the memory pages.
(B) By default, a memory-mapped file is mapped into the user process address space, instead of the kernel space.
(C) After invoking $\mathrm{mmap}()$, $\mathrm{read}()$ and $\mathrm{write}()$ system calls are automatically translated by the kernel into memory access instructions.
(D) If the standard I/O is memory-mapped by $\mathrm{mmap}()$, the mapping will be to kernel address space instead of user address space, and thus $\mathrm{read}()$ and $\mathrm{write}()$ would trigger memory copy between kernel space and user space.

A file can be stored in a file system with different allocation methods: contiguous, extent-based, linked, or indexed. Suppose directories are already in memory. An extent has an average of 16 blocks. Assume that a file has 512 blocks, numbered from 0 to 511, and the target of a random access read is block 239.

(A) With contiguous allocation, only one block needs to be read in order to access block 239.
(B) With extent-based allocation, 15 blocks need to be read in order to access block 239.
(C) With linked allocation, 240 blocks need to be read in order to access block 239.
(D) With indexed allocation, 2 blocks need to be read in order to access block 239.

Consider UNIX UFS with 4 KB blocks. In an inode, suppose there are 2048 entries in the “direct block” pointing to at most 2048 data blocks. There is also an entry for each of “single indirect”, “double indirect”, and “triple indirect”, pointing to an indirect node with 2048 entries for data blocks or recursively indirect nodes.

(A) With only direct block, the maximum file size is around 8 MB.
(B) With direct block and single indirect, the maximum file size is around 16 MB.
(C) With direct block, single indirect, and double indirect, the maximum file size is around 16 GB.
(D) With direct block, single indirect, double indirect, and triple indirect, the maximum file size is around 32 TB.

Consider various mechanisms used in Linux. Which statements are valid?

(A) A dynamically loaded kernel module will not be unloaded automatically by the kernel unless explicitly requested.
(B) The kernel maintains a table of functions for loading programs of different binary formats, and tries them one by one when loading an executable binary.
(C) Slab allocation is for contiguous memory allocation needed for user processes.
(D) For a library of functions statically linked to multiple programs, it is loaded into memory multiple times as multiple copies, but only once and one copy if dynamically linked.

For instruction set architecture (ISA), which of the following statements are true?

(A) RISC CPUs usually use fixed and simple instruction formats, which may offer better execution efficiency for pipelining than CISC CPUs.
(B) The choice of big/little endian determines the memory ordering and is nothing to do with the ISA design.
(C) The purpose of Open ISA is to allow “open source” of CPU RTL codes.
(D) An ISA keeping the source (rs1 and rs2) and destination (rd) registers at the same position in all formats can simplify decoding (such as RISC-V), whereas MIPS has overlapped fields for rs2 and rd, which needs multiplexors.

Given the normal 1-bit ALU (top) and the MSB 1-bit ALU (bottom), you can implement the C-language statement by giving the tuple $(\mathrm{Ainvert},\mathrm{Binvert},\mathrm{CarryIn},\mathrm{Operation})$. Each $A$, $B$, and $C$ represents 4 bits wide. For condition determination, $C$ is 0001 if TRUE, and is 0000 if FALSE. For example, give $(0,0,0,2)$ for $C=A+B$.

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

(A) By giving appropriate tuples, we can make possible statements: $C=A-B$; $C=B-A$, but not possible for $C=A-B-1$ and $C=B-A-1$, which need an additional subtractor.
(B) For $C=A<B$, let us give $(0,1,1,3)$ and also connect set to Less0. All other Less13 are set 0.
(C) For $C=A>B$, let us give $(0,1,1,3)$ and also connect set to Less0. All other Less13 are set 0.
(D) For $D=(A==B)$, let us give $(0,1,1,2)$ and also connect all $C_0\sim C_3$ to a NOR gate to obtain the final $D_0$. All Less0~3 are set 0 and connect other $C_1\sim C_3$ to $D_1\sim D_3$.

Considering both DMA (direct memory access) and I/O, which of the following statements are true?

(A) If a machine cannot handle interrupt, the system will not be able to perform I/O via DMA.
(B) By using memory-mapped I/O, CPU employs DMA to release the requirements of keeping busy in I/O movement.
(C) DMA is an I/O processor, which can accept I/O requests from CPU and acts as a slave device on a bus.
(D) The primary problem that DMA will create with a cache memory system is because DMA uses physical addresses whereas CPU caches may use virtual addresses.

For CPU clock rate, which of the following statements are true?

(A) Executing programs on a 1.5 GHz CPU could be faster than on another CPU of 2 GHz even within the same brand.
(B) Powerful branch prediction is essential for CPU with a high clock rate so as to minimize the penalty due to branch hazard.
(C) Given that the big.LITTLE consisting of two cores, one big core can run at 4 GHz and the LITTLE core runs at 2 GHz. The average clock speed will be 3 GHz.
(D) Unbalance of pipeline stages affects cycle time (thus clock rate). We can push more clock rate by adding more stages and thus improve the CPU throughput without increasing the instruction latency.

Considering CPUs with full parallelism, which of the following statements are true?

(A) To fully utilize AMD 64-core CPUs, the software has to exploit full parallelism by both multiprocessing and multithreading.
(B) In big.LITTLE technology, the Little cores will keep pipeline as deep as possible to achieve higher clock rate, more focused on ILP (instruction level parallelism). In contrast, big cores usually embed TLP (task level parallelism) such as to maintain a low clock rate.
(C) With two clock rates in a core, the base clock time is determined by the longest stage of the pipeline and the turbo mode is limited by the maximum clock generator at run time.
(D) CPU parallelism can be obtained by multi-issue, SIMD, MIMD, and vector techniques. The multi-issue, SIMD, and vector need compiler optimization, whereas MIMD needs supports from OS.

The single-precision (32-bit) IEEE 754 floating-point format is as follows. Which of the following statements are correct?

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

(A) To represent 3.125 in the IEEE 754 format, the exponent part is 00000001b.
(B) To represent 3.125 in the IEEE 754 format, the fraction part is 480000h.
(C) $1.101_2\times2^{-130}$ cannot be represented using the IEEE 754 format.
(D) To represent $1.101_2\times2^{-130}$ in the IEEE 754 format, the exponent part is 00000000b.

Consider a five-stage pipelined MIPS CPU. Please select the signals that are required to insert a stall cycle when data hazard is detected at ID stage.

(A) Set IF.Flush = 1 (to clear IF/ID).
(B) Set PCWrite = 0 (to disable the write to Program Counter (PC)).
(C) Set IF/IDWrite = 0 (to disable the write to IF/ID).
(D) Set ID.Flush = 1 (to set 9 control signals used in EX, MEM and WB stages to 0).

Given the pipelined CPU in the figure below, which code sequence(s) will fail to run correctly if the data-path A is cut?

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

(A)

add $s1, $t0, $t1
add $s3, $s2, $s1
add $s2, $s3, $s1

(B)

add $s3, $t0, $t1
add $s1, $s2, $s1
add $s2, $s3, $s1

(C)

add $s1, $t0, $t1
add $s1, $s2, $s1
add $s2, $s3, $s1

(D)

add $s1, $t0, $t1
add $s2, $s2, $s1
add $s2, $s3, $s1

For a MIPS 5-stage pipelined CPU with data forwarding and stall mechanisms implemented, which of the following statements are true for the code sequence below? You may refer to the following code sequence and the CPU pipeline figure.

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

add  $s2, $s2, $s3
lw   $s1, 0($s2)
addi $t1, $s2, 8
sw   $t2, 0($s1)
lw   $t3, 0($s1)
add  $s3, $t3, $s2
sub  $s3, $s3, $s2

(A) It takes 12 clock cycles to finish the execution of the code sequence.
(B) There are total 2 stall cycles when running the code sequence.
(C) The instruction in EXE stage is addi when the code runs to the 5th cycle.
(D) The ALUSrc signal is set to 0 when the code runs to the 5th cycle.

For the MIPS assembly code sequence below, assume that $s_2$ and $t_1$ are initialized to $0$ and $3$, respectively. Which of the following statements are correct for the execution of this code sequence?

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

Loop:   addi $t2, $zero, 0x6
Loop2:  addi $s2, $s2, 1
        addi $t2, $t2, -1
        bne  $t2, $zero, Loop2  // branch1
        addi $t1, $t1, -1
        bne  $t1, $zero, Loop   // branch2
Done:

(A) Assume a 1-bit predictor is used and the predictor is initialized as taken. For the inner $\mathrm{bne}$ (marked as branch1), the rate of prediction accuracy is $2/3$.
(B) Assume a 2-bit predictor is used and the predictor is initialized as taken. For the inner $\mathrm{bne}$ (marked as branch1), the rate of prediction accuracy is $5/6$.
(C) Assume a 1-bit predictor is used and the predictor is initialized as taken. For the outer $\mathrm{bne}$ (marked as branch2), the rate of prediction accuracy is $1/3$.
(D) Assume the predictors are initialized as taken. For the outer $\mathrm{bne}$ (marked as branch2), a 2-bit predictor has higher accuracy rate than a 1-bit predictor.

What is the initial value of $mutex$?

(A) 0
(B) 1
(C) $n$
(D) None of the above.

What should be in ①?

(A) $mutex$
(B) $rw\_mutex$
(C) $read\_count$
(D) $n$

What should be in ②?

(A) 0
(B) 1
(C) $n$
(D) None of the above.

What should be in ⑦?

(A) $mutex$
(B) $rw\_mutex$
(C) $read\_count$
(D) $n$

What is the minimum access time for a desired word in a frame?

(A) 11 ns
(B) 101 ns
(C) 111 ns
(D) 201 ns

In ARM, what is the maximum access time for a desired word in a frame?

(A) 201 ns
(B) 211 ns
(C) 311 ns
(D) 411 ns

In SPARC, if the maximum length of a linked list entry is 4, what is the maximum access time for a desired word in a frame?

(A) 301 ns
(B) 501 ns
(C) 611 ns
(D) 811 ns

In ARM, for a large process using big pages, what is the average access time for a desired word in a frame?

(A) 33 ns
(B) 60 ns
(C) 115 ns
(D) 215 ns

We build a direct-mapped L1 data cache to match the NYCU1 pipeline. Assume that the miss rate is 4% for each cache access. What is the real CPI of NYCU1?

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

Now we build a 4-way set-associative L1 data cache for the new NYCU2 pipeline. Which of the following effects is NOT true for the new L1 compared to NYCU1?

(A) The CPU clock rate could be reduced.
(B) Better access time since address tags can be compared in parallel.
(C) An extra multiplexer to select blocks.
(D) Conflict cache misses can be reduced.

Now we design an NYCU3 by providing a 128 KB L2 to NYCU1, where L2 has a hit time of 8 ns and a miss rate of 20%. What is the real CPI of NYCU3?

(A) 0.28
(B) 0.56
(C) 1.28
(D) 1.56

We have to consider TLB in accessing for the NYCU memory hierarchy. Which of the following statements is NOT true for TLB?

(A) TLB = translation-lookaside buffer.
(B) TLB miss will result into a page fault.
(C) Small TLB uses fully-associative.
(D) TLB is accessed before L1 (physical address).

Assume the register number of $s2$ is 18 and the OP code of $\mathrm{beq}$ is 4. The MIPS machine code of the $\mathrm{beq}$ in this code sequence is:

(A) 0x12400003
(B) 0x12400004
(C) 0x12400000
(D) 0x12400100

The MIPS machine code of the $\mathrm{j}$ (OP code is 2) in this code sequence is:

(A) 0x08001001
(B) 0x22001001
(C) 0x0A001001
(D) 0x02001001

Assume both $s1$ and $s2$ initially contain integers 5 and 6, respectively. What is the value that $v0$ will contain after the execution of the whole code sequence?

(A) 6
(B) 30
(C) 60
(D) 120