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

For different directory structures, which of the following statements are true?

(A) A tree-structured directory prohibits the sharing of files or subdirectories by symbolic links.
(B) General graph directory structures may suffer from the problem of having dangling pointers to non-existent files.
(C) Acyclic-graph directory structures may have the problem that a file’s reference count is not 0, but it cannot be accessed.
(D) Garbage collection is to recover unused disk space. It is necessary only when there are possible cycles in the directory structures.

Assume there are four frames in the system. Given the memory reference pattern in terms of frame numbers, $50, 40, 80, 20, 50, 10, 80, 40$, which of the following statements are true?

(A) There are 5 page faults if LRU (least recently used) replacement algorithm is used.
(B) There are 5 page faults if optimal page-replacement algorithm is used.
(C) LRU can never exhibit Belady's anomaly.
(D) A process is thrashing if it spends more time in paging than execution. The effects of thrashing can be limited by using a global replacement algorithm.

Assume both the index block and data block use the same block size of 1 KB, and assume each entry of the index block consists of 4 bytes. Which of the following statements are true?

(A) The maximum file size that can be supported for single-level indexed allocation is $2^{18}$ bytes.
(B) Two-level indexed allocation uses a first-level index block to point to a set of second-level index blocks. The maximum file size that can be supported by a two-level indexed allocation is $2^{26}$ bytes.
(C) Both linked allocation and indexed allocation do not suffer from external fragmentation.
(D) For an application requiring direct access, it is better to use linked allocation than indexed allocation.

Buddy system and Slab allocation are two techniques for allocating memory for kernel processes. Which of the following statements are true?

(A) With the buddy system, memory requests can be satisfied very quickly because objects are created in advance.
(B) In Slab allocation scheme, a slab may consist of both used and free objects.
(C) Using the buddy system, a request for 29 KB memory will be satisfied with a 36 KB segment of memory.
(D) Using the Slab allocation scheme, no memory is wasted due to fragmentation.

Consider a disk queue with requests for blocks on cylinders in the listed order: $120, 25, 5, 11, 80, 185, 90, 85$. If the disk head is initially at cylinder 88 and is moving upward to the next service cylinder 90, which of the following statements are true?

(A) If SSTF (Shortest seek-time first) is used, the requests will be serviced in the order of $90, 85, 80, 120, 185, 25, 11, 5$.
(B) If C-SCAN (Circular SCN) is used, the requests will be serviced in the order of $90, 120, 185, 85, 80, 25, 11, 5$.
(C) SSTF may suffer from the problem of starvation.
(D) C-SCAN is a variant of SCAN, designed to reduce the disk seek time needed by SCAN.

System calls are the interface between application programs and kernel. What descriptions about system calls are correct?

(A) Just like hardware devices that generate interrupts, system calls also generate interrupts and jump to the kernel.
(B) Just like hardware devices, there are also vector entries for system calls and they point to interrupt service routines for both hardware and software interrupts.
(C) If there are many parameters to a system call, the user program can store all parameters in a table and pass the address of the table as a parameter to the system call.
(D) If memory copy between kernel and user program is heavy, it can be offloaded to DMA.

State of a process switches between ready, running, and waiting, when device interrupt, clock interrupt, or system call happens. Suppose now a process is in the running state.

(A) When a device interrupt happens, the process enters the waiting state first.
(B) When a clock interrupt happens, the process enters the ready state first.
(C) When an I/O system call is invoked, the process enters the waiting state first.
(D) When a non-I/O system call is invoked, the process enters the ready state first.

In message passing for inter-process communication, with $send()$ and $receive()$ being two system calls, if $send()$ in sender is non-blocking but $receive()$ in receiver is blocking:

(A) If $receive()$ happens before $send()$, the receiver will not get the message.
(B) If $receive()$ happens after $send()$, the receiver will get the message.
(C) If now reversed, $send()$ in sender is blocking and $receive()$ in receiver is non-blocking. If $receive()$ happens before $send()$, the receiver will get the message.
(D) Continued from (C), if $receive()$ happens after $send()$, the receiver will not get the message.

For a user thread there can be a corresponding kernel thread. Do they both maintain stack and PCB (process control block)? Separately or jointly? What possibilities below are valid?

(A) User thread has its stack and PCB, but the corresponding kernel thread does not have them.
(B) User thread and kernel thread share the same stack and PCB.
(C) User thread and kernel thread have their own stack separately but PCB jointly.
(D) User thread and kernel thread have their own stack and PCB separately.

Modern operating systems adjust priority in scheduling processes. What strategies are commonly used?

(A) Increase priority when a process uses up its quantum.
(B) Increase priority when a process has frequent I/O.
(C) Increase priority when a process wakes up from a long sleep.
(D) Increase priority for a foreground process.

Consider the CPU performance. Which of the following statements are correct?

(A) If you want to decrease the response time of a task, you can promote your PC by replacing the old single-core CPU with a new multi-core CPU and using a new operating system that can partition a task into several load-balanced sub-tasks and execute all sub-tasks on all cores concurrently. Assume the performance of the single-core CPU is the same as that of each core of the new multi-core CPU.
(B) If we run two programs on two CPUs of different ISAs to perform the same task, the CPU with smaller CPI must have less CPU time than the other CPU since smaller CPI also implies that the required number of cycles to complete a task is also less than that of the other CPU.
(C) The CPU time of performing a program on a CPU is determined by the instruction count, the CPI, and the clock rate of the CPU.
(D) Consider using the metric of Millions of Instructions per Second (MIPS) to measure CPU performance. Two programs are run on single-core CPUs $C_A$ and $C_B$ of different ISAs to solve the same task. $C_A$ requires less time than $C_B$ to complete the task while $C_A$ has less MIPS than $C_B$. The aforementioned facts imply that $C_A$ is likely a CISC-based CPU and $C_B$ is a RISC-based CPU.

Consider the instruction set of a 32-bit MIPS CPU. Which of the following statements are correct?

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

(A) One of the reasons why there are only 32 registers in the CPU is that the use of more registers will decrease the number of instructions that can be encoded in an instruction.
(B) As generating a MIPS instruction, a compiler generally assigns a register to the most frequently used variable to diminish memory access time.
(C) The reason why MIPS does not support the instructions of $blt$ (branch less than) and $bgt$ (branch greater than) is that the hardware design of “greater than” or “less than” is more complex than “equal” and “not equal”, which may make the design of supporting $blt$ and $bgt$ have less clock rate.
(D) The above figure shows a MIPS assembly program. In the procedure prologue, three registers were saved: $ra$, $s1$, and $a0$. In fact, only $ra$ and $s1$ need to be stored and $a0$ does not.

Consider the 32-bit MIPS CPU. Which of the following statements are correct?

(A) Floating-point instructions have different register set from integer instructions.
(B) The code sequence $(lui\$t1,288;\ ori\ $t1,$t1,26)$performs the operation of loading a constant$0x0120001A$into register$t1$. (C) Consider the addition of three floating-point numbers$(a+b+c)$on a parallel program. The addition results of$(a+b)+c$and$a+(b+c)$are always the same, i.e., floating-point number addition holds the associativity. (D) Assume the value of register$PC$is$0xAB05FF84$. The highest address that instruction$j$can go to is$0xAFFFFFFC$.

Consider the 32-bit MIPS CPU. Which of the following statements are correct?

(A) The reason why sometimes the assembler replaces the following instructions, beq $s2,$s3,L1; add $t0,$s1,$s2, with the following code sequence, bne $s2,$s3,L2; j L1; L2: add $t0,$s1,$s2, is that the hardware to realize beq is slower than that to realize bne and j is also a faster instruction than beq due to no need to access registers.
(B) Consider the 32-bit floating-point numbers using IEEE Std. 754. The smallest positive single-precision denormalized number is $1.0\times2^{-149}$.
(C) The concept of sticky bit is to use two bits to record the number of 1s in the already rounded bits.
(D) Consider the following code sequence running on one core of a multi-core CPU:

try: add  $t0, $zero, $s0
     ll   $t1, 0($s2)
     sc   $t0, 0($s2)
     beq  $t0, $zero, try
     add  $s0, $zero, $t1

The atomic pair of instructions (ll, sc) in the code sequence protects the data at memory $0($s2) from write of another core during the data swap of register $s0$ and memory $0($s2).

Consider the arithmetic operation unit in the following figure for 32-bit MIPS CPU. Which of the following statements are correct?

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

(A) As the operation unit performs a multiplication, the Divisor register acts as a multiplicand register and the Remainder register acts as a Product register. The lower word of Remainder register accommodates the dividend and the higher word of Product register accommodates the multiplier.
(B) The performance gain of Booth’s algorithm comes from consecutive 0s or 1s in the multiplier.
(C) Using the non-restoring division algorithm (NRDA) and restoring division algorithm (RDA) to perform a division of 7 divided by 2 that is represented by a signed 4-bit binary number, NRDA requires 5 subtractions and 3 additions while RDA requires 2 subtractions and 3 additions.
(D) If we want to improve the performance of 32-bit ALU, we can use carry look-ahead adder to avoid waiting for carry propagation. To exploit the hierarchical design concept, we also can apply group propagate and group generate to design a multi-level carry look-ahead adder. The multi-level design owns the benefit of using systematic way to deal with the adder of large bit number in a simple way without the other benefit such as delay.

Using MIPS processor design and implementation for example, which of the following statements are correct?

(A) A control signal generally called a “clock” is used widely to control what most combinational components (such as ALU, multiplexer, etc.) should do.
(B) If every instruction must be executed in one clock cycle, the implementation must include at least two independently operable memory units.
(C) If every instruction can be executed using multiple clock cycles and the execution is not pipelined, this can result in the cheapest-possible hardware design (even considering the may-be-required stage latches).
(D) For pipelined processor design, at least two independently operable memory units are a must.

Given the following figures and tables for a few MIPS sample instructions, which of the following statements are correct?

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

(A) The binary machine instruction encoding for “and $r4,$r6, $r8” ($r4=$r6\mathbin{\&}r8) is$0000\ 0000\ 1100\ 1000\ 0010\ 0000\ 0010\ 0100$. (B) The binary machine instruction encoding for “sw$r5, -7($r9)” is$1010\ 1101\ 0010\ 0101\ 1111\ 1111\ 1111\ 1001$. (C) The instruction “beq ...” can result in a next$PC$value of [(the address of “beq ...”) + (the address field in 2’s complement form)]. (D) The instruction R-type “sub ...” has a$Branch=0$,$RegDst=1$,$ALUSrc=0$, “ALU control” output$=0110$, and$MemtoReg=0$.

We study the MIPS processor hazards using pipelined designs for a few typical instructions. Which of the following statements are correct?

(A) If there are structural hazards, any contented hardware must be duplicated many copies to satisfy any possible needs, or else the pipelined processor cannot work properly.
(B) For sequentially fetched instructions, with a single pipeline, in-order issue and in-order completion of instructions are both guaranteed.
(C) For true-data dependence (read-after-write), data dependence detection and forwarding can effectively alleviate the hazards, while stalls are many times still required.
(D) For sequentially fetched instructions with a single pipeline, in-order issue can be designed to never cause anti-dependencies (write-after-read), while in doing loop unrolling, one must rename registers to remove other name-dependencies.

Memory design is typically hierarchical. Which of the following statements are correct?

(A) The purpose of such design is to make memory look both large and fast. Any application running with a hierarchical memory system will have faster average memory accesses compared with a flat, non-hierarchical memory system.
(B) Let the L1 cache be the closest-to-processor hierarchy of the memory system. In considering its role and performance, the hit time is a more important factor than the hit rate.
(C) A processor-issued memory address will be partitioned by the L1 cache into three fields: tag, index, and byte offset. Only one of these fields, the tag, needs to be stored in a proper cache line (or block) together with a valid bit, and other helpful information such as a dirty bit.
(D) Since processor accesses to L1 cache will miss, the average memory access time of a program is expressed as $[(\text{L1 cache hit time})+(\text{next lower hierarchy hit time})\times(\text{L1 cache miss rate})]$.

In a computer system, cache memory and main memory are two intermediate memory hierarchies. Which of the following statements are not correct?

(A) Both hierarchies are designed based on the same principle of typical applications: the Principle of Locality.
(B) The locality in a cache design is based on spatial locality and temporal locality; while the locality in the main memory design is based on only spatial locality, excluding temporal locality.
(C) For typical computer systems, the cache controller and virtual memory manager are both software to better lower their miss rates.
(D) Upon cache misses, to better utilize available hardware resources, CPU usually switches to execute other ready and waiting jobs.

Assuming that the single-level page-table scheme is used, for a logical address $0xabcdef12$, the value used to index the page table is ____.

Assuming that the two-level page-table scheme is used and the outer page table has 256 entries, for a logical address $0xabcdef12$, the values used to index the outer and inner page tables are ____ and ____, respectively.

(A) $A=0xab$, $B=0xcdef12$
(B) $A=0xab$, $B=0xcde$
(C) $A=0xabcd$, $B=0xef12$
(D) $A=0xab$, $B=0xcd$

Assuming that the two-level page-table scheme is used and the outer page table has 256 entries, each process may need up to ____ bytes of memory space for the page table.

(A) $2^{10}+2^{22}$
(B) $2^8+2^{12}$
(C) $2^{10}+2^{14}$
(D) $2^{13}+2^{25}$

One statement in the above program is wrong. Name which statement.

(A) $\text{state}[i]=\text{HUNGRY}$
(B) $\text{if (state}[i]\ne\text{HUNGRY) self}[i].\text{wait}()$
(C) $\text{state}[i]=\text{EATING}$
(D) $\text{self}[i].\text{signal}()$

What is the purpose of the function $\text{test}(i)$?

(A) Check whether both right and left chopsticks are available.
(B) Check whether both neighbors are not EATING, and if both are not, eat.
(C) Check whether both right neighbors are HUNGRY, and if both are not, eat.
(D) Check whether either right neighbor or left neighbor is HUNGRY, and if yes, wake it up to eat.

What is the purpose of the function $\text{test}((i+4)\bmod 5)$?

(A) Check whether my left neighbor is HUNGRY and its both neighbors are not EATING, and if both are not EATING, wake it up to eat.
(B) Check whether my right neighbor is HUNGRY and its both neighbors are not EATING, and if both are not EATING, wake it up to eat.
(C) Check whether my left neighbor is HUNGRY and its both neighbors are not HUNGRY, and if both are not HUNGRY, wake it up to eat.
(D) Check whether my right neighbor is HUNGRY and its both neighbors are not HUNGRY, and if both are not HUNGRY, wake it up to eat.

Which of the following statements is correct?

(A) The left figure is the most significant bit (MSB) ALU and the set signal comes from $S2$.
(B) The middle figure is the MSB ALU and the set signal comes from $CarryOut$.
(C) The concept to realize $slt$ is that subtraction is performed first and then the $CarryOut$ of the MSB ALU is the set signal that is connected to the least significant bit ALU.
(D) The set signal comes from the $S1$ of the ALU in the left figure.

Which of the following statements is correct?

(A) The control signal setting to realize a $slt$ instruction is: $AInvert=1$; $BInvert=1$; $Operation=10$; $CarryIn=1$.
(B) The control signal setting to realize a $slt$ instruction is: $AInvert=0$; $BInvert=1$; $Operation=11$; $CarryIn=1$.
(C) The control signal setting to realize a $sub$ instruction is: $AInvert=0$; $BInvert=1$; $Operation=00$; $CarryIn=1$.
(D) The control signal setting to realize a $sub$ instruction is: $AInvert=0$; $BInvert=1$; $Operation=10$; $CarryIn=0$.

Which of the following statements is correct?

(A) The control signal setting to realize a $bne$ instruction is: $AInvert=0$; $BInvert=1$; $Operation=10$; $CarryIn=1$.
(B) The control signal setting to realize a $nor$ instruction is: $AInvert=1$; $BInvert=1$; $Operation=01$; $CarryIn=0$.
(C) The control signal setting to realize a $lw$ instruction is: $AInvert=1$; $BInvert=1$; $Operation=10$; $CarryIn=1$.
(D) The control signal setting to realize a $sw$ instruction is: $AInvert=1$; $BInvert=1$; $Operation=00$; $CarryIn=0$.

The memory space available to a program is ____ bytes.

(A) $2^{32}$
(B) $2^{31}$
(C) $2^{mm}$
(D) $2^{mm-1}$

The number of virtual pages is ____.

(A) $2^{mm}$
(B) $2^{32-2mm}$
(C) $2^{32-cache}$
(D) $2^{32-pf}$

The page size is ____.

(A) $2^{32/mm}$
(B) $2^{mm/2^{pf}}$
(C) $2^{pf}$
(D) $2^{pf/cb}$

The size of the cache block tag in bits is ____ (choose the most proper one).

(A) $\lfloor 32-cb \rfloor$
(B) $32-cache$
(C) $(32-cache)-\lfloor 32-cb \rfloor$
(D) $2^{(32-cache)-2}\leq\lfloor 32-cb \rfloor$