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

Which one(s) of the following statements about processes and threads are correct?

(A) All the data in one thread are shared with other threads in the same process.
(B) Kernel threads in the same process share one program counter.
(C) When multiple user-level threads are mapped to a single kernel thread through a thread library, these user-level threads cannot take advantage of the multi-core structure.
(D) Race condition can occur in a process in which multiple user threads are associated with a kernel thread.

Which one(s) of the following statements about modern operating systems are correct?

(A) When a process writes a character on screen, this operation is accomplished with one or more system calls.
(B) In a time-sharing system, a process will not leave the running state unless it terminates or it is preempted through a timer interrupt.
(C) Applying the microkernel structure can reduce the communication overhead between kernel and user space.
(D) One process can communicate with another process through shared memory.

Assume that a system issues multiple readers and writers processes with the following modified readers-writers pseudo codes:

Shared semaphore $mutex$, $wrt$ initialized to $1$.
Shared Integer $readcount$ initialized to $0$.

A writer process:

• wait($wrt$);
• writing the content
• signal($wrt$);

A reader process:

• wait($mutex$);
• $readcount++$;
• if ($readcount \leq Na$), wait($wrt$);
• signal($mutex$);
• reading the content
• wait($mutex$);
• $readcount--$;
• if ($readcount \leq Nb$), signal($wrt$);
• signal($mutex$).

Which of the following statements are correct?

(A) When $Na=1$ and $Nb=0$, at most one process can access (read or write) the content at any time.
(B) When $Na=1$ and $Nb=0$, at most one reader process is waiting for $wrt$ at any time.
(C) When $Na=2$ and $Nb=1$, at most two reader processes are waiting for $wrt$ at any time.
(D) None of the above statement is correct.

If a system is monitored by the banker’s algorithm and is currently in a safe state, which of the following changes can be made safely (without introducing the possibility of deadlock)?

(A) Increase the amount of available resources.
(B) Increase the number of resource types.
(C) Increase the Max for one process.
(D) Release the allocated but no longer used resources of one process.

Given the following code with fork():

#include <stdio.h>
#include <unistd.h>
void main()
{
    pid_t pid;
    int a;
    int i;
    a = 5;
    for (i = 0; i < 2; i++) {
        pid = fork();
        if (pid < 0) {
            return;
        } else if (pid == 0) {
            a = 2;
            printf("%d\n", a);
        } else {
            a--;
            printf("%d\n", a);
        }
    }
}

Which of the following statements are correct?

(A) The sum of all output numbers is larger than $14$.
(B) At least one of the output numbers is smaller than zero.
(C) Besides the primary process, at most two additional processes are created.
(D) None of the above statement is correct.

Which one(s) of the following statements regarding virtual memory are true?

(A) Logical memory space can be much larger than physical memory space.
(B) Swapped-out pages are stored in a disk partition or a pre-allocated system file.
(C) When a page is replaced, the page must be written back to the swap space regardless of whether it has been modified or not.
(D) When a page fault occurs, the running process is trapped into the operating system kernel.

Consider three typical disk scheduling algorithms: First-Come First-Serve (FCFS), Short-Seek-Time First (SSTF), and SCAN (the elevator algorithm). Which one(s) of the following statements are true?

(A) FCFS never starves a disk I/O request.
(B) The variation of disk I/O latencies under SSTF can be very high.
(C) SCAN is optimal in terms of total seek distance.
(D) Disk scheduling significantly improves disk I/O performance on conventional hard drives, but not on RAM disks.

Consider the following directory listing information, which is produced using an ls -l command in a Linux console. The fields of each line stand for, in order: access permission, hard link count, owner name, owner group, file size in bytes, time stamp, and file name. Which one(s) of the following statements are true?

-rw-rw-r--  1 andy staff    31219 Sep  3 08:30 intro.ps
drwx------  5 andy staff      512 Jul  8 09:33 private/
drwxrwxr-x  2 andy staff      512 Jul  8 09:35 doc/
drwxrwx---  2 andy student    512 Aug  3 14:13 student-proj/
-rw-r--r--  1 andy staff     9423 Feb 24 20:03 program.c
-rwxr-xr-x  1 andy staff    20471 Feb 24 20:03 program
drwx--x--x  4 andy faculty    512 Jul 31 10:31 lib/
drwx------  3 andy staff     1024 Aug 29 06:52 mail/
drwxrwxrwx  3 andy staff      512 Jul  8 09:35 test/
lrwxrwxrwx  1 andy staff        9 Dec 21 16:51 t -> program.c

(A) There are $4$ sub-directories in the directory “lib”.
(B) The file “t” is a hard link.
(C) The file “program” can be executed by users in the group “staff”.
(D) The amount of storage space allocated to file “intro.ps” is exactly $31{,}219$ bytes.

Regarding page table designs, which one(s) of the following statements are true?

(A) In inverted page tables, a table entry contains a page number and a process ID.
(B) In hash-based page tables, if a hash bucket is associated with a linked list for collision handling, each element of the linked list contains a frame number plus a page number.
(C) In multilevel page tables, an inner page table entry contains a frame number.
(D) With multilevel page tables, the more levels a page table has, the higher the TLB miss penalty will be.

Consider three typical file allocation schemes: contiguous allocation, linked allocation (link-list allocation), indexed allocation, and extent allocation. Which one(s) of the following statements are true?

(A) Contiguous allocation offers the best read and write performance for large files.
(B) Files are prone to file fragmentation with the linked allocation scheme.
(C) Random file access with indexed allocation in general is faster than with linked allocation.
(D) File defragmentation is not necessary for extent allocation.

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

(A) If you want to decrease the response time of a task, you have to promote your PC by increasing the number of CPUs of your PC. Assume the old CPU and new CPUs in your PC are of the same type and have the same specification.
(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.
(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) Using Millions of Instructions Per Second (MIPS) as a metric to measure CPU performance is not fair since MIPS does not consider the differences in the complexity among instructions.

Consider the design principles of MIPS CPU. Which of the following statements are true?

(A) The add instruction has a fixed number of operands, i.e., $3$, and does not have more operands because simplicity favors regularity, which also enables higher performance at lower cost.
(B) MIPS has a small group of registers rather than a large and complex group of registers to form a register file, which shows the principle of favoring regularity by simplicity.
(C) The immediate operand in immediate arithmetic instructions follows the principle of making the common case fast.
(D) Several types of instruction formats in MIPS reveal the principle of the demands of compromises for good design.

Consider computer arithmetic and CPU design. Which of the following statements are true?

(A) For floating-point numbers, the sticky bit is used to promote the accuracy of rounding a floating-point number, where increasing the number of used sticky bits can improve the accuracy.
(B) The merit of the non-restoring division algorithm (NRDA) over the restoring division algorithm (RDA) is that the NRDA requires one less addition than the RDA if the subtraction of the divisor register from the remainder register (dividend) yields a negative number.
(C) The addition of two integers represented by 2’s complement of different signs does not produce an overflow.
(D) The following codes perform the overflow check for the addition of two unsigned integers stored in $t1 and $t2:

addu $t0, $t1, $t2; nor $t3, $t1, $zero; sltu $t3, $t3, $t2; bne $t3, $zero, Overflow

The left field of the table below lists a code sequence of $11$ instructions for the strcpy function. This code sequence is incomplete. Choose a right update from (A) or (B) to make this code sequence complete. The right field of the table lists the MIPS instruction format. Based on the incomplete code sequence on the table (not the updated code sequence), compute the values of ADR1 and ADR2. Which statements of (C) and (D) are correct?

(A) Add the following instructions before instruction (1): addi $sp, $sp, -8; sw $s0, 0($sp); sw $ra, 4($sp). Add the following instructions before instruction (11): lw $ra, 4($sp); addi $sp, $sp, 8.
(B) Add the following instructions before instruction (1): addi $sp, $sp, -4; sw $s0, 0($sp). Add the following instructions before instruction (11): addi $sp, $sp, 4.
(C) ADR1 $=2$.
(D) ADR2 $=24101$.

Consider the addition of two normalized binary floating-point numbers, $1.01111 \times 2^4$ (input 1) and $1.10011 \times 2^6$ (input 2). The significant bit of a normalized binary floating-point number is hidden and exponent bias is not used. The accuracy of a binary floating-point number is to the fifth binary place, i.e., each fraction register is $5$-bit long. The hardware design adopts the scheme of two additional bits, i.e., guard bit and round bit, to improve accuracy. Which of the following statements are true?

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

(A) $c_0=1$; $c_1=0$; $c_2=1$.
(B) $c_3=2$ (implying a right shift by two bits); $c_4=0$.
(C) $c_5=$ no operation; $c_6=0$; $c_7=$ no operation.
(D) $c_8$ triggers rounding hardware to produce a carry-in of $1$ to the fifth binary place; the final addition result is $1.11111 \times 2^6$.

A sequential CPU can be implemented in (i) single-(machine-)cycle-per-instruction, (ii) multiple-cycles-per-instruction, and (iii) pipelined fashions. For any particular machine program:

(A) In (i), since every instruction must be completed in only one machine cycle, and since for any particular type of hardware circuits, if any instruction may possibly need to use it for any number of times, say, $X$, then $X$ copies of it have to be in physical existence (meaning the hardware cost is at its maximum), hence the execution speed is the fastest among the three.

(B) In (ii), all instructions are allowed to repetitively reuse any piece of hardware for any number of times; hence the required function units in this design can be the minimum.

(C) In (iii), the CPU needs to execute many individual instructions simultaneously, with each instruction being in their respectively different pipe stages. Hence at the end of each pipe stage, a pipestage latch must be provided to keep the processing results of that pipestage. While pipestage latches in the (ii) design are not necessary (except for those storing the final outcomes of that instruction), since only one instruction will be executed in those cycles at any instance of time.

(D) Both (ii) and (iii) design fashions have the same shortcoming of having to slow the machine clock down to allow for the slowest pipestage to be able to complete, making other faster stages wait without further productivity, hence they are very rarely adopted in many successful commercial products.

We talk about the famous pipeline hazards in pipelined processor design, in alphabetical order:

(A) For Control hazards, no matter how we restrict the branch condition complexity, how early we calculate the target (instruction) address and/or resolve the branch condition, how hard we predict the branch outcome and/or target address, pipeline stalls due to this kind of hazards are still unavoidable.
(B) For Data hazards, we mean the pipeline stalls or errors which may be caused by immature (not-yet-completed) read-after-write, arithmetic overflow, divide-by-zero, etc.
(C) For Memory hazards, we mean the pipeline stalls or errors which may be caused by data inconsistencies among different memory hierarchies, cache misses, page faults, errors occurring in data storage/transmission, etc.
(D) For Structural hazards, it can be dealt with by properly scheduling the uses of the contended hardware circuit and stalling the awaiting instructions, such that, for example, no matter how many instructions in the pipeline want to perform an addition at whenever for whatever number of times, only one hardware adder will suffice.

In a sequence of instructions in a user program, let instructions be numbered $\ldots, i-1, i, i+1, \ldots$, where instruction $i$ is later than instruction $i-1$ in execution order. Assume that instruction $i$ incurs an integer arithmetic overflow. Which of the following can be a proper rationale?

(A) The processor completes instructions up to $i-1$, triggers exception handling to calculate the true result of instruction $i$ and place the result properly; then the exception returns and resumes user program execution starting from instruction $i+1$.
(B) The processor completes instructions up to $i-1$, triggers exception handling to signal to the user that such an error occurred; then the exception halts the user program.
(C) The processor ignores this overflow and simply continues the user program execution.
(D) Such an arithmetic overflow should not occur if this user program is generated by a proper and commercially authorized compiler and assembler, since such compilers and assemblers are designed to produce correct and high quality code.

Upon receiving a read/write request, a cache controller will partition the received memory address (assuming a byte-addressable address, since memories are byte-addressable by default) into three fields: tag, index, and byte-offset.

(A) The size of a direct-mapped cache can be determined by knowing only the size of the tag field.
(B) The size of a set-associative cache cannot be determined based on the sizes of the three fields.
(C) For any reasonable cache, any of these three fields should not contain zero bit.
(D) If the same amount of memory is to be used for the fully-associative, set-associative, or direct-mapped caches, the tag field of the fully-associative cache is the largest, and that of the direct-mapped cache is the smallest.

The designs of cache memory and virtual memory are based on the same principle. While the implementations of these memories are very different in some ways:

(A) The principle mentioned above is Amdahl’s Law.
(B) The counterpart of a cache block (or line) in virtual memory design is called a page (or page frame).
(C) During a cache miss or a page fault, the CPU will typically stand still and wait until the miss or fault is handled.
(D) Just like in cache designs, both write-through and write-back policies are commonly used in a typical virtual memory system.

What is $U_3$?

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

What is $U_2$?

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

What is $U_1$?

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

What is $U_0$?

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

What is the largest possible number of frames? ($a^b$ stands for the $b$-th power of $a$. For example, $2^3=8$.)

(A) $2^{14}$
(B) $2^{18}$
(C) $2^{36}$
(D) None of the above.

Consider a simple 1-level page table design. How many entries are there in a page table?

(A) $2^{14}$
(B) $2^{18}$
(C) $2^{36}$
(D) None of the above.

At least how many bits are necessary in a page-table entry?

(A) $14$
(B) $18$
(C) $36$
(D) None of the above.

The ARY1 and PTR1 should be:

(A) ARY1 = $zero; PTR1 = $a0
(B) ARY1 = $a0; PTR1 = $zero
(C) ARY1 = $a0; PTR1 = $a0
(D) ARY1 = $zero; PTR1 = $zero

The ARY2 and PTR2 should be:

(A) ARY2 $=1$; PTR2 $=4$
(B) ARY2 $=4$; PTR2 $=4$
(C) ARY2 $=1$; PTR2 $=4$
(D) ARY2 $=4$; PTR2 $=4$

The ARY3 and PTR3 should be:

(A) ARY3 = $t2; PTR3 = $a1
(B) ARY3 = $a1; PTR3 = $a1
(C) ARY3 = $t2; PTR3 = $t2
(D) ARY3 = $a1; PTR3 = $t2

If a direct-mapped cache of size $n$-cache lines is used, the resulting cache hit rate is about:

(A) $\frac{n-2}{n}$
(B) $\frac{n-1}{n}$
(C) $\frac{n-2}{n+1}$
(D) $\frac{n-1}{n+1}$

If a fully associative cache of the same size, with the commonly used LRU (least-recently-used) replacement, is used, the resulting cache hit rate is about:

(A) $0$
(B) $\frac{n-1}{n}$
(C) $\frac{n-2}{n+1}$
(D) $\frac{n-1}{n+1}$

If a fully associative cache of the same size, with the less famous MRU (most-recently-used) replacement, is used, the resulting cache hit rate is about:

(A) $0$
(B) $\frac{n-1}{n}$
(C) $\frac{n-1}{n+1}$
(D) $\frac{n}{n+1}$