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

Which of the following statements on page replacement is (are) true?

(A) FIFO page replacement algorithm may suffer from Belády's anomaly.
(B) With LRU page replacement, adding page frames may increase the number of page faults.
(C) The LRU page replacement algorithm achieves the minimum number of page faults.
(D) Increasing the size of the TLB (translation lookaside buffer) reduces the number of page replacements.

Assume that we create a 64 MB shared memory for processes $X$ and $Y$ on an Intel x86 machine. Which of the following statements is (are) true?

(A) The shared memory must be mapped to the same virtual address range in both $X$ and $Y$.
(B) If we set the shared memory pages in process $X$ as read-only, process $Y$ will not be able to write to the shared memory.
(C) The shared memory can be swapped to a backing store (e.g., the disk).
(D) It is possible that less than 64 MB of physical memory space is actually allocated for the shared memory.

Which of the following statements is (are) true about direct memory access (DMA)?

(A) It allows application programs to access the main memory directly.
(B) A DMA transfer will slow down the execution of a CPU-intensive program.
(C) We can use device interrupts to synchronize DMA transfers.
(D) We can use polling to synchronize DMA transfers.

To move file $f$ from $/x/f$ to $/y/f$, which of the following step(s) are required (cannot be skipped)?

(A) Make an entry for $f$ in directory $y$.
(B) Allocate data blocks on the disk for $/y/f$.
(C) Copy the file content of $/x/f$ to the data blocks of $/y/f$.
(D) Erase the entry for $f$ in directory $x$.

Assume that a file system has no fragmentation to begin with (the disk blocks of each file are contiguous). If we want to have some files with non-contiguous data blocks on the file system, which of the following file operation(s) are essential?

(A) Changing a file name.
(B) Deleting a file.
(C) Creating a new file and writing some data to the file.
(D) Overwriting the data of an existing file.

Which statement(s) about processes are correct?

(A) When a process creates a child process, it can either continue its execution or wait for the child process to complete before continuing.
(B) A process may run out its stack memory by spawning too many processes as it runs.
(C) In a multithreaded multicore system, it is possible for two threads of the same process to run simultaneously on two different cores.
(D) A deep recursive function call can consume a lot of memory from the heap section of the process.

Consider the following CPU scheduling result in a single-processor system. If all five processes complete within 18 ms, which statement(s) are correct?

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

(A) This result is not possible with round-robin scheduling.
(B) This result is possible if non-preemptive SJF is used and processes do not arrive at the same time.
(C) This result is possible if preemptive SJF is used and processes do not arrive at the same time.
(D) If both preemptive SJF and non-preemptive SJF yield this result, the waiting time of $p_4$ must be zero.

Consider the following C code for creating two threads. Which statement(s) are correct?

(A) The output is always 20000.
(B) It is possible that the output is 19999.
(C) The output is fixed to 20000 if we change the order of the two calls to pthread_join.
(D) The first thread has a higher priority than the second one in thread scheduling.

// header files here
int count = 0;

void *mythread(void *arg) {
    for (int i = 0; i < 10000; i++) {
        // wait for some time
        count += 1;
    }
    return(NULL);
}

int main() {
    pthread_t p1, p2;
    pthread_create(&p1, NULL, mythread, NULL);
    pthread_create(&p2, NULL, mythread, NULL);
    pthread_join(p2, NULL); pthread_join(p1, NULL);
    printf("%d", count);
    return 0;
}

Which statement(s) about condition variables are correct?

(A) A call to pthread_cond_wait() causes the calling thread to busy wait on a condition variable.
(B) pthread_cond_wait() includes a mutex lock as a parameter.
(C) The pthread_cond_signal() function signals one thread that is waiting on the condition variable.
(D) The thread that calls pthread_cond_signal() aborts its execution right after the return of the call, after which the CPU scheduler gives the execution right to the awakened thread.

Consider a system with $m$ resources and 4 threads: $T_0$, $T_1$, $T_2$, and $T_3$. Let $x_i$ and $y_i$ denote the maximum number of resources requested and the current number of resources held by thread $T_i$, respectively, for all $i$, $0 \leq i \leq 3$. Which of the following statement(s) are correct?

(A) The system state is deadlocked if $\sum_{i=0}^{3}(x_i-y_i)>m-(y_0+y_1+y_2+y_3)$.
(B) The system state is deadlocked if $(x_2-y_2)>m-(y_0+y_1+y_2+y_3)$.
(C) The system state is deadlocked if $(x_i-y_i)>m-(y_0+y_1+y_2+y_3)$ for all $i$, $0 \leq i \leq 3$.
(D) The system state is safe if $(x_i-y_i)\leq m-(y_0+y_1+y_2+y_3)$ for some $i$, $0 \leq i \leq 3$.

Two CPUs are implemented to execute exactly the same ISA. Assume that CPU A is a single-cycle implementation while CPU B is a five-stage pipelined implementation. The instruction and data memory devices are zero-wait-state memory for both CPUs. Which of the following statements are true when both CPUs run the same program C with finite execution time?

(A) The execution time of CPU B is shorter than that of CPU A.
(B) The critical path of CPU B can always be made shorter than that of CPU A.
(C) CPU B will need more circuit resources than CPU A does.
(D) The CPI of CPU A is higher than the CPI of CPU B.

To remove hazards for a single-issue in-order execution pipelined processor, which of the following techniques may require help from the compilers (assuming that you only write programs using high-level languages)?

(A) Delayed branch.
(B) Dynamic branch prediction with branch history tables.
(C) Load-use hazard removal.
(D) Forwarding.

Modern ISAs often contain a pair of instructions for multi-thread and multi-core synchronization. In MIPS, this pair of instructions includes a special load called a load linked, ll, and a special store called a store conditional, sc. Which of the following statements are true?

(A) The instruction ll reads and locks a memory cell such that no other threads can change its value until an sc instruction executed by the same thread changes its value.
(B) The execution of the sc instruction will always be successful if no context switch occurs after the ll instruction.
(C) The following code segment has a bug in protecting the memory pointed to by $s1:

try:
    ll    $t0, 0($s1)
    addi  $t1, $t0, 1
    bnez  $t1, skip
    sc    $t1, 0($a1)
    beqz  $t0, try
skip:

(D) The ll and sc instruction pairs perform shared resource protection more efficiently than the atomic swap instruction used in, for example, the ARM ISA, especially when there are a lot of concurrent processes.

The following figure shows a simple implementation of a MIPS processor. Which of the following statements are true?

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

(A) The following code segment can be used to detect a stuck-at-0 fault of MemtoReg:

addi  $t1, zero, 1
sw    $t1, 0(zero)
lw    $t0, 0(zero)
slti  $t0, $t0, 1

(B) The CPU will not suffer from load-use hazards.
(C) The instruction memory does not have to be a synchronous memory (i.e., driven by a clock signal).
(D) The register file does not have to be a synchronous component.

Assume that we have a 5-stage processor that has neither data forwarding nor branch prediction. It has separate instruction and data memory. Bubbles will be inserted when there are hazards. The processor always resolves the branch target at stage 2 (the decode stage). Which of the following statements are true when the following code segment is executed?

addi  $t1, zero, zero

loop:
addi $t1,$t1, 1
lw $s0, 2000($t1)
subi $t2,$s0, 2
sw $t2, 4000($t1)
bne $t1,$t3, loop

(A) The bubble(s) inserted for the subi instruction can be removed by forwarding.
(B) If $t_3$ is 100, the CPI will be larger than 2.5 for the execution of the code segment.
(C) Excluding the adders for the PC, the processor needs at least two more adders. Note that a subtractor is counted as an adder.
(D) Adding a static branch predictor increases the CPI for this code segment when $t_3$ is 100.

Which of the following statements about cache are true?

(A) A virtually-addressed cache access is typically faster than that of a physically-addressed cache.
(B) High associativity in a cache can reduce compulsory misses.
(C) Cache performance is of less importance in faster processors because the processor speed compensates for the high memory access time.
(D) Larger blocks reduce the miss rate by taking advantage of spatial locality.

The following table shows the instruction type breakdown of a given application executed in a CPU. Assume the CPU has a 2 GHz clock rate. Which of the following statements are correct?

(A) The execution time of this program is 1024 ms.
(B) We can make the program run two times faster by only improving the CPI of L/S instructions.
(C) We can make the program run two times faster by only improving the CPI of INT instructions.
(D) If we improve the CPU such that CPI of INT and FP instructions is reduced by 40% and the CPI of L/S and branch is reduced by 30%, the execution time of running this program will become 342 ms.

Given a processor with two caches: an I-cache and a D-cache, and the miss penalty is 200 cycles for all misses. Assume the I-cache miss rate is 2%, D-cache miss rate is 4%, and the percentage of all lw and sw instructions is 50%. If the processor has a CPI of 2 without any memory stalls, which of the following statements are true when memory stall is considered? (Note: each statement is independent.)

(A) The CPI will become 10 if memory stall is considered.
(B) If we double the clock rate (but the memory access time to handle a cache miss does not change), the CPI will become 18.
(C) If we double the clock rate (but the memory access time to handle a cache miss does not change), the machine will have a speedup of $9/10$.
(D) If an L2 cache is added only for I-cache and its miss penalty is 20 clock cycles, assume global instruction miss rate to main memory became 0.5% after the L2 cache is added. The CPI will become 3.4.

The system has a direct-mapped cache with total data size of 8192 bytes and block size of 16 bytes. Assume that the cache starts out empty. For the following piece of code, which of the following statements are correct? (Note: Assume that int is of 32-bits (4 bytes); variables $x$ and $i$ are both in registers and the array $A$ is in memory.)

int A[256];
int x = 0;
for (int i = 0; i < 256; i++) {
    x += A[i];
}

(A) There will be 256 cache misses in total.
(B) All the misses are compulsory misses.
(C) The cache hit-rate is 0.25.
(D) If we double the block size, the miss rate will be halved.

The following table shows two processors and their read/write operations on two different variables $a$ and $b$ (initially $a=b=0$). After the operations, which of the following statements are correct?

(A) The value of $a$ can be 1, 2, or 3 if the system ensures cache coherence.
(B) The value of $a$ can be 1, 2, or 3 if the system does not ensure cache coherence.
(C) The value of $b$ can be 1, 2, or 3 if the system ensures cache coherence.
(D) The value of $b$ can be 1, 2, or 3 if the system does not ensure cache coherence.

Which of the following numbers is closest to the maximum capacity (the maximum amount of data you can store on the array) of the RAID5 array?

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

What is the maximum number of disk failures that the RAID5 array can tolerate?

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

In the worst case, how many disks will be involved in writing a single byte to the RAID5 array?

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

Which type of naming is used?

(A) direct
(B) indirect
(C) insufficient evidence to judge
(D) none of the above

Which data structure is needed to support this type of communication?

(A) mailbox
(B) port
(C) semaphore
(D) none above

Which condition will cause deadlock in this example?

(A) BS
(B) BR
(C) both BS and BR
(D) none above

If deadlock is not possible, which condition will ensure each process to proceed only after receiving its message?

(A) BS
(B) BR
(C) NS
(D) NR

How many parameters does the function my_call() have?

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

Which of the following C code could be the body of my_call()?

(A) { return func(func(a,b), c+d); }
(B) { return func(a,b) + func(c,d); }
(C) { return func(a+b, func(a+b,c)); }
(D) { return func(a, func(c+d,b)); }

The tail-call optimization is a technique that, when a caller simply returns the value that it gets from the callee, can avoid allocating a procedure frame for the last function call. How many instructions can be saved if the tail-call optimization is used to optimize the assembly code?

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

What is the size (in bits) of the tag field in one block used in this cache?

(A) 23
(B) 22
(C) 19
(D) 18

What is the total size (in bits) of this cache, including data, tag, and valid fields?

(A) 1024
(B) 1100
(C) 1176
(D) 1184

Assume that the cache is initially empty. Given a series of memory references: 24, 8, 25, 10, and 41 (which are word addresses), how many cache misses will there be for the references?

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

For your answer to the above question, how many cache misses are compulsory misses?

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