以下是為您提取的國立中央大學 112 學年度碩士班考試入學試題(科目:作業系統與計算機組織)全份考卷文字內容:


# 複選題:共 5 分,全部答對才給分

  1. Which of the following statements are true regarding performance evaluation?
    • Throughput refers to the time a system takes to process a request after receiving it.
    • If a CPU’s clock rate is an integer, its cycles per instruction (CPI) must also be an integer.
    • If a component accounts for 30% of the total execution and we shrink the execution time of this component to half, the total execution time becomes 85% of the original execution time.
    • In a multi-threading environment, CPU time could be higher than the elapsed time.
    • None of the above.
詳解

(A) 吞吐量(Throughput)指的是單位時間內系統能處理的工作量或請求數量(例如每秒處理幾筆交易、每秒執行幾百萬條指令)。「系統接收請求後到處理完成所花費的時間」稱為回應時間(Response Time)或執行時間(Execution Time)
(B) 不必然
© 根據阿達姆定律(Amdahl’s Law)進行計算:

  • 受影響的比例(Fraction affected) F=30%=0.3F = 30\% = 0.3
  • 改善倍數(Speedup) S=2S = 2 (將執行時間縮減為一半)
  • New Execution Time=Old Time×((1−F)+FS)\text{New Execution Time} = \text{Old Time} \times \left( (1 - F) + \frac{F}{S} \right)
  • New Time=Old Time×((1−0.3)+0.32)=Old Time×(0.7+0.15)=Old Time×0.85\text{New Time} = \text{Old Time} \times \left( (1 - 0.3) + \frac{0.3}{2} \right) = \text{Old Time} \times (0.7 + 0.15) = \text{Old Time} \times 0.85 因此,總執行時間確實變為原來的 85%

(D)** 實耗時間(Elapsed time / Wall-clock time)** 是程式從開始到結束實際經過的真實時間;而 CPU 時間是 CPU 用於執行該程式的時間總和。在多執行緒/多核心環境中,多個核心可以同時平行運算,將各個執行緒消耗的 CPU 時間加總起來,有可能會超過真實流逝的 elapsed time

  1. Which statements are true about segmentation fault? The code segments are written in C.
    • Segmentation fault happens when a program attempts to access memory in the heap segment.
    • Executing the following code may cause a segmentation fault. char* p = NULL; printf("%c\n", *p);
    • Executing the following code may cause a segmentation fault. char* p; printf("%c\n", *p);
    • Executing the following code may cause a segmentation fault. int foo() {return foo(); }
    • None of the above.
詳解

(A) 在堆積(Heap)中透過合法配置(如 malloc)與存取的記憶體是完全正常的,並不會引發區段錯誤;區段錯誤通常發生在嘗試存取未授權、無效或未被配置的記憶體位址時
(B) 指標 p 被初始化為 NULL(通常對應記憶體位址 0)。對其進行取值(*p)會嘗試讀取零位址的資料,該區域在多數作業系統中受到硬體保護,因此會立即觸發 Segmentation fault
© 指標 p 是一個未初始化的區域變數(Wild Pointer,其內部數值為隨機的垃圾記憶體位址。對其解參考(*p)會隨機存取未知的記憶體區域,極高機率會因為超出行程的合法記憶體空間而引發 Segmentation fault
(D) 這段程式碼會造成無限遞迴(Infinite recursion),不斷在堆疊(Stack)上配置新的疊代框架(Stack frame)直到堆疊空間耗盡。當堆疊溢位(Stack Overflow)觸發了作業系統在堆疊底部設置的記憶體保護頁(Guard page)時,系統便會判定其為非法存取並拋出 Segmentation fault

  1. Which statements are true about the MIPS (32-bit) assembly language?
    • The I-type instructions are composed of the OP code (6 bits), RS (5 bits), RT (5 bits), and constant field (16 bits). Therefore, an I-type instruction can take at most two registers.
    • The instruction JUMP comprises the OP code (6 bits) and the address field (26 bits). Therefore, a JUMP instruction can jump to 226+22^{26+2} bytes before or after the address specified by the stack pointer (SP) register.
    • The JR (jump register) instruction causes the PC to jump to the content of a register. Therefore, JR is a J-type instruction.
    • The logic of “logical-shift-left” and “arithmetic-shift-left” operations are different. Therefore, MIPS needs to provide instructions for each of them.
    • None of the above.
詳解

(B) 雖然 J-type 指令包含 6 位元的 Opcode 與 26 位元的位址欄位,但 j (Jump)指令是絕對定址(Absolute addressing),其目標位址是將 26 位元左移 2 位元(26+2=2826+2 = 28 位元)後,結合當前程式計數器(PC)的高 4 位元來決定,與堆疊指標(SP 暫存器)毫無關係,也不是相對於 SP 的相對跳躍
© 在 MIPS 的硬體編碼設計中,jr 由於需要指定來源暫存器(rs),其實是被歸類在 R-type 指令(其 Opcode 為 0x00,funct 欄位為 0x08),而不是 J-type
(D) 在二進位運算中邏輯左移(Logical Shift Left)與算術左移(Arithmetic Shift Left)的底層邏輯與結果完全相同

  1. Which statements are true about single-cycle, multi-cycle, and pipeline CPUs?
    • The pipeline structure reduces the response time for each instruction.
    • You are given a program with 10 instructions. If you can perfectly pipeline each instruction into 5 stages with no bubbles (and each stage takes 1 ns), it takes 14 ns to complete the 10 instructions.
    • A multi-cycle CPU is better than a single-cycle CPU because a multi-cycle CPU tends to have a lower value of CPI (cycles per instruction).
    • With more pipeline stages, the performance is less likely to be influenced by hazards.
    • None of the above.
詳解
  • 單週期(Single-cycle)、多週期(Multi-cycle)與管線化(Pipeline)CPU 架構的經典計算機組織考題
    (A) 管線化(Pipeline)的主要目的是提高整體的指令吞吐量(Throughput)。事實上,因為加入了管線暫存器(Pipeline registers)的額外延遲,單一指令完成所需的時間(Latency)反而可能會稍微增加
    (B) 根據管線化總執行時間的經典公式:Total Time=(k+n−1)×cycle time=(5+10−1)×1 ns=14 ns\text{Total Time} = (k + n - 1) \times \text{cycle time}=(5 + 10 - 1) \times 1\text{ ns} = 14\text{ ns}
    © 單週期 CPU 的 CPI(每道指令所需的時脈週期數)固定為 1;而多週期 CPU 將指令拆解成多個步驟,其 CPI 通常大於 1(介於 2 到 5 之間)。多週期 CPU 的優勢在於能縮短時脈週期(Clock cycle time)的長度,而非擁有較低的 CPI
    (D) 當管線的階數越多(Deeps pipelines),系統反而 ** 更容易受到管線危害(Hazards,如資料危害與控制危害)** 的影響。因為同時在管線中執行的指令更多,一旦發生衝突或分支預測失敗,所造成的氣泡(Bubbles)與效能懲罰(Penalty)代價會更大
  1. Which of the following statements are true about RISC and CISC?
    • The execution time of a RISC instruction is usually faster than a CISC instruction.
    • CISC usually has a more uniform instruction format than RISC.
    • RISC is an outdated technology.
    • RISC uses a simpler instruction set than CISC.
    • None of the above.
詳解

(A) 因為 RISC 每條指令通常設計得非常簡單,大多能在單一或極少數的時脈週期內執行完畢
(B) CISC(如 x86)的指令長度是變動且不一致的(長短不一)
© 主流,現代幾乎所有的智慧型手機、平板(如 ARM 架構)、甚至高階的 Apple Silicon 與雲端伺服器晶片,全數都是基於 RISC 架構延伸發展的

  1. Which of the following statements are true about RAM and ROM?
    • RAM can be randomly read and written.
    • ROM can be read and written.
    • RAM cannot be persistent storage because of its volatility.
    • ROM can persistently preserve program.
    • All of the above.
詳解

(B) ROM 的全名是 Read-Only Memory(唯讀記憶體),在傳統計算機組織的定義中它是設計用來讀取資料的

  1. Which of the following statements are true about cache design?
    • In an inclusive cache design, the top-level cache (e.g., L1 cache) is the subset of the bottom-level cache (e.g., L2 cache).
    • Because the first-level cache needs a short hit time, the size of the first-level cache is big.
    • Reducing the miss penalty can decrease average memory access time when the top-level cache’s hit time is smaller than the bottom-level cache’s hit time.
    • Generally, the full-associative cache design has lower cache hit rate than the direct-mapped cache design.
    • None of the above.
詳解
  • 快取記憶體設計(Cache Design)的觀念題
    (A) 在包容性快取(Inclusive cache)的設計中,規定頂層快取(如 L1)的所有資料與內容,必須同時存在於底層快取(如 L2)之中,因此 L1 快取是 L2 快取的子集(Subset)
    (B) 第一層快取(L1 Cache)為了追求極短的命中時間(Short hit time)以配合 CPU 高速運轉,其尺寸通常設計得非常小而非很大
    © 根據平均記憶體存取時間(AMAT)的公式:AMAT=Hit Time1+Miss Rate1×Miss Penalty1\text{AMAT} = \text{Hit Time}_1 + \text{Miss Rate}_1 \times \text{Miss Penalty}_1。當頂層快取(L1)的 hit time 小於底層快取(L2)的 hit time 時,降低失誤懲罰(Miss penalty)確實能夠有效降低整體平均記憶體存取時間
    (D) 全相聯快取(Fully-associative cache)因為
    沒有衝突失誤(Conflict miss)
    ,其快取命中率通常比直接對映快取(Direct-mapped cache)更高
  1. Which of the following statement are true about cache miss types?
    • Compulsory misses can be avoided by a prefetching mechanism.
    • Conflict miss occurs the first time a location is used.
    • Capacity miss occurs when other external processors update data.
    • Direct-mapped cache has more conflict misses than n-way associative caches (where n > 1).
    • All of the above.
詳解
  • 關於快取失誤類型(Cache Miss Types)的觀念題
    (A) 強制失誤(Compulsory misses,又稱冷啟動失誤)發生在程式第一次存取某個記憶體區塊時。透過預取機制(Prefetching),可以在資料真正被 CPU 請求之前先一步載入快取中,因此能夠有效避免或減少這類失誤
    (B) 第一次存取某個記憶體位置所造成的失誤是強制失誤(Compulsory miss)。衝突失誤(Conflict miss)是因為多個不同的記憶體區塊被對映到快取中相同的同一個位置(Line),互相排擠而導致的
    © 容量失誤(Capacity miss)是因為快取的總容量有限,無法容納程式執行所需的所有資料區塊而被迫替換出去所致
    (D) 直接對映快取(Direct-mapped cache)在每個索引(Index)位置只有一個存放欄位,因此極易發生碰撞
  1. Suppose that a cache memory’s (L1) access time is “C ns” and a main memory’s (L2) access time is “M ns”. In this architecture, 60% of the memory accesses are read and remaining all are writing requests. If the hit ratio of read operation can achieves “H” and that of writing operation is 1, what is the average memory access time (AMAT) when a write-through protocol is adopted on the cache?

    • M(0.6H+1)+0.6HCM(0.6H+1)+0.6HC
    • 0.6(H+C+M)0.6(H+C+M)
    • 0.6H(C+M)+M0.6H(C+M)+M
    • 0.6H+0.6(C+M)0.6H+0.6(C+M)
    • None of the above
  2. If the floating-point (FP) instructions of an application on a specific processor C1 consumes 60% of the total execution time. Moreover, in the same application, 25% of the floating-point time is taken to do square root calculations. A new processor C2 is developed. This new processor could either enhance the performance of FP instructions by a factor of 1.5 or alternatively increase the performance of the square root operation by a factor of 8. Which of the following statements are true?{.quiz .multi}
    - Enhancing the performance of FP instruction by a factor 1.5 is worse than increasing the performance of the square root operation by a factor of 8.
    - Enhancing the performance of FP instruction by a factor 1.5 is better than increasing the performance of the square root operation by a factor of 8.{.correct}
    - The speed-up of the FP instruction enhancement is 1.25.{.correct}
    - The speed-up of the square root operation enhancement is 1.15.
    - None of the above.

  3. Choose the correct statements from the multiple choices{.quiz .multi}
    - Deadlock can be avoided by using a deadlock detection algorithm.{.correct}
    - A user-level process cannot modify its own page table entries{.correct}
    - Shortest Remaining Time First is the best preemptive scheduling algorithm that can be implemented in an Operating System.
    - When a process is created using the classical fork() system call, process ID is inherited by the child process
    - None of the above

詳解

(A) 死結避免(Deadlock Avoidance)與死結偵測與復原(Deadlock Detection and Recovery)是兩種截然不同的死結處理策略。避免法(如銀行家演算法)是在分配資源時確保系統隨時處於「安全狀態」;而偵測法是允許死結發生,再透過演算法去檢查並透過終止行程或搶佔資源來復原。因此不能說用偵測演算法來「避免」死結
(B) 分頁表(Page Table)儲存在核心空間(Kernel space),受到嚴格的硬體保護。使用者層級的行程(User-level process)運行在使用者模式(User mode),無法直接存取或修改自己的分頁表,這必須透過作業系統核心透過系統呼叫來代為管理,以確保記憶體隔離與安全性
© 最短剩餘時間優先(SRTF)雖然在
理論上
能提供最短的平均等待時間,但它無法在實際的作業系統中被完美實作(Implemented),因為我們無法預知未來每個行程接下來需要的 CPU 執行時間(Burst time)長度
(D) 當呼叫 fork() 建立子行程時,作業系統會指派給子行程一個全新且獨一無二的行程識別碼(PID),子行程不會繼承父行程的 PID 作為自己的 PID(雖然子行程可以透過系統呼叫得知其父行程的 PID,即 PPID)

  1. Choose the correct statements from the multiple choices regarding pipes{.quiz .multi}
    - Ordinary pipes are unidirectional, allowing only one-way communication.{.correct}
    - The system call pipe() provides reliable, bidirectional communication between processes on the same host.
    - If two-way communication is required, two named pipes must be used with each pipe sending data in a different direction.
    - Only byte-oriented data may be transmitted across a UNIX FIFO.{.correct}
    - None of the above
詳解
  • Pipes(管線)與行程間通訊(IPC) 觀念
    (A) 一般管線(Ordinary Pipes / 匿名管線)是單向的(Unidirectional),資料只能單向流動(一個行程寫入、另一個行程讀取)
    (B) 系統呼叫 pipe() 所建立的是一般管線(Ordinary pipe),其特性是單向(Unidirectional)而非雙向
    © 雖然當資料需要在兩個方向流動時,通常會使用兩個管線,但這項敘述限定了「必須使用 named pipes(具名管線/FIFO)」是不夠精確的 —— 因為一般管線(Ordinary pipes)同樣也可以透過建立兩個管線來實現雙向通訊
    (D) 在 UNIX 系統中,透過具名管線(UNIX FIFO,即 Named pipes)傳輸的資料格式
    僅限於位元組導向(Byte-oriented data)
    ,而 Windows 系統則同時支援位元組導向或訊息導向(Message-oriented data)。
  1. Choose the correct statements from the multiple choices regarding networking technologies{.quiz .multi}
    - The goal of Web 3.0 is to enable a more decentralized internet.{.correct}
    - The architecture of software-defined networking is decentralized.
    - The Domain Name System is a distributed, hierarchical database.{.correct}
    - Internet standards are developed by the Internet Engineering Task Force.{.correct}
    - None of the above
詳解

(A) Web 3.0 的核心願景之一就是利用區塊鏈、智慧合約與去中心化應用(dApps),擺脫傳統 Web 2.0 由少數大型科技巨頭壟斷的中心化模式,實現更具自主性與去中心化的網際網路
(B)** 軟體定義網路(SDN, Software-Defined Networking)** 將控制平面(Control Plane)與資料轉送平面(Data Plane)分離,其中控制平面通常是集中化(Centralized)的(由集中式的 SDN 控制器統一調度與管理網路),因此其架構並非去中心化
© 網域名稱系統(DNS)正是教科書中標準的分散式且具階層架構的資料庫(從根伺服器、頂級網域伺服器到權威伺服器),用以將人類易讀的網址轉換為機器使用的 IP 位址
(D) 網際網路標準(Internet Standards,如各種 TCP/IP 協定與 RFC 文件)主要就是由網際網路工程任務組(IETF, Internet Engineering Task Force)負責開發與推動

  1. Choose the correct statements from the multiple choices{.quiz .multi}
    - A process can move form a ready state to the waiting state.
    - The reference bit is set by the hardware.{.correct}
    - The mode bit provides ability to identify in which particular mode the current instruction is executing.{.correct}
    - If the valid-invalid bit for a page is set, it is required to write the memory page to the disk for page replacement.
    - None of the above
詳解
  • 關於作業系統(Operating Systems)中行程狀態、硬體支援(Reference bit、Mode bit)與虛擬記憶體管理
    (A) 行程無法直接從 Ready(就緒)狀態跳轉至 Waiting 狀態
    (B) 在虛擬記憶體與分頁替換演算法(如 Second-Chance / Clock 演算法)中,當記憶體頁面被存取(讀取或寫入)時,是由 硬體(MMU) 自動將該頁面的 reference bit(參照位元)設為 1,供作業系統後續追蹤頁面使用狀況
    © 模式位元(Mode bit)是用來識別 CPU 目前是在 User mode(使用者模式) 還是 Kernel mode(核心模式) 下執行指令,藉此提供硬體層級的保護機制,防止使用者程式非法執行特權指令
    (D) Valid-invalid bit(有效 - 無效位元)是用來表示該頁面目前是否合法且存在於實體記憶體中。當頁面被置換(Page replacement)時,是否需要寫回硬碟取決於該頁面是否被修改過(即需要查看 dirty bit /modify bit),若該頁面未被修改過(clean page),則直接釋放即可,不需寫回硬碟
  1. Choose the correct statements from the multiple choices{.quiz .multi}
    - The copy-on-write technique allows the parent and child processes initially to share the same pages.{.correct}
    - No parent-child relationship is required for named pipes.{.correct}
    - IPSec can be used to setup virtual private networks.{.correct}
    - The race condition can be solved by the banker’s algorithm.
    - None of the above
詳解
  • 作業系統(行程管理、行程間通訊 IPC、死結/資源分配)與網路安全(VPN 與 IPsec)
    (A) 寫時複製(Copy-on-Write, COW)技術允許在執行 fork() 建立子行程後,父行程與子行程最初共享相同的實體記憶體分頁。只有當其中一個行程嘗試修改分頁內容時,作業系統才會真正複製一份新的分頁給該行程
    (B) 一般管線(Ordinary/Anonymous pipes)需要透過繼承來建立,因此通常僅限於具有親子關係的行程之間;相對地,** 具名管線(Named pipes / FIFO)具有檔案系統中的名稱,因此不需要具備親子關係的獨立行程也能夠透過它進行通訊
    ©IPsec(Internet Protocol Security) 是一種網路層的安全協定,常被用來建立安全、加密的虛擬專用網路(VPN)
    (D) 銀行家演算法(Banker’s algorithm)是用來進行
    死結避免(Deadlock Avoidance)的資源分配演算法;而競態條件(Race condition)則需要透過同步機制(如互斥鎖 Mutex、號誌 Semaphore 等臨界區間保護方法)** 來解決。
  1. Identify the following environments need hard real-time scheduling.{.quiz .multi}
    - Thermostat in a household.
    - Control system for a nuclear power plant.{.correct}
    - Fuel economy system in an automobile.
    - Landing system in a jet airliner.{.correct}
    - Mailing system.

  2. Which of the following scheduling algorithms would result in starvation?{.quiz .multi}
    - First-come, first-served
    - Shortest job first{.correct}
    - Round robin
    - Priority{.correct}
    - Weighted fair queueing

  3. A counting semaphore{.quiz .multi}
    - is essentially an integer variable{.correct}
    - is accessed through only one standard operation
    - can be modified simultaneously by multiple threads
    - cannot be used to control access to a thread’s critical sections
    - executes as a single, uninterruptible unit

詳解
  • 作業系統(Operating Systems)中號誌(Semaphore,特別是計數號誌 Counting Semaphore)基本定義與特性
    (A) 從作業系統的核心定義來看,一個號誌(Semaphore)本質上就是一個整數變數,在初始化之後,主要透過兩個標準且不可分割的原語(Atomic operations)——wait ()(或稱 PP 運算)與 signal ()(或稱 VV 運算)來進行存取與修改
    (B) 號誌是透過兩個標準操作( wait() 和 signal() )來存取的,而不是單一操作
    © 為了避免競態條件(Race condition),號誌內部數值的修改必須具備互斥與原子性(Atomicity),不能允許有多個執行緒同時對其進行修改
    (D) 號誌的核心用途之一正是用來解決同步問題、控制多個執行緒對共享資源或臨界區間(Critical section)的存取
  1. Consider a multiprocessor system and a multithreaded program written using the many-to-many threading model. Let the number of user-level threads in the program be more than the number of processors in the system. What are the lower performance implications of the following scenarios?{.quiz .multi}
    - The number of kernel threads allocated to the program is less than the number of processors.{.correct}
    - The number of kernel threads allocated to the program is equal to the number of processors.{.correct}
    - The number of kernel threads allocated to the program is greater than the number of processors but less than the number of userlevel threads.
    - The number of kernel threads allocated to the program is equal to two.{.correct}
    - The number of kernel threads allocated to the program is greater than the number of processors and also greater than the number of userlevel threads.
詳解
  • 多對多執行緒模型(Many-to-Many Threading Model)與多處理器系統(Multiprocessor System)下,當使用者執行緒數量大時,配置不同數量的核心執行緒(Kernel Threads)對系統效能產生的影響
    (A) 核心執行緒數少於處理器數(K<PK < P):正確描述。會導致硬體資源無法被完全利用,部分 CPU 閒置
    (D) 受限於極低的核心執行緒上限,導致嚴重的資源閒置。
  1. Some computer systems do not provide a privileged mode of operation in hardware. To construct a secure operating system for these computer systems, an OS for a machine of this type would need to remain in control at all times. This is could be accomplished by the following methods:{.quiz .multi}
    - software interpretation of all user programs.{.correct}
    - co-execution with co-processor to execute all programs.
    - networked server support to execute programs.
    - all programs be written in high-level languages so that all object code is compiler produced and checked.{.correct}
    - cluster computing in database cloud system.
更新於