電子工程 106 年電子計算機原理考古題

在快取記憶體（cache）系統，直接對映（direct mapping）、關聯對映（associative mapping） 及集合關聯對映（set-associative mapping）有何不同？（20 分）

國際標準組織（International Standard Organization, ISO）定義了開放系統互連（Open System Interconnection, OSI）的7 層（layers）架構，試問其中有那些層做流量控制（flow control）？（5 分）為何要做流量控制？（5 分）各層的作法有何不同？（10 分）

有一無向性連結圖（undirected connected graph）如圖所示，每一鏈路（link）的成本 標示在該鏈路旁邊。試依圖建構一個最小成本生成樹（minimum cost spanning tree） 並標示其生成順序。（每小題10 分，共20 分）  採用Kruskal’s algorithm 且無任何限制。  採用Kruskal’s algorithm 但限制每一分支（branch）最多只能有兩條鏈路。 （請接背面） G E D F A C B 5 9 10 12 8 14 7 13 11 6 106 年專門職業及技術人員高等考試 建築師、技師、第二次食品技師考試暨 普通考試不動產經紀人、記帳士考試試題 全一張 （背面） 等 別 ：高等考試 類 科 ：電子工程技師 科 目 ：電子計算機原理

有一虛擬記憶體（virtual memory）使用兩層記錄表（two-level page tables），其虛擬 位址（virtual address）之格式（format）為（table number, page number, displacement within page）。若最前面的四個記錄表如下圖所示： Page Table 0 Page Table 1 Page Table 2 Page Table 3 page number page frame # page number page frame # page number page frame # page number page frame # 0 on disk 0 15 0 6 page table not in main memory 1 12 1 7 1 13 2 9 2 on disk 2 0 3

3 0 3 on disk 試問：  針對下表有關虛擬記憶體的接取（access），試問(a)～(h)應為何？（8 分） 註：若未發生頁面錯誤（page fault），則以（frame number, displacement）的形式填 入其實體位址。 Access Table number Page number Displacement within page Physical address Access rights Fetch data 1 2 50 page fault read Fetch data 0 1 12 (a) (b) Store data 2 3 2000 (c) (d) Jump to 3 3 100 (e) (f) Jump to 0 2 60 (g) (h) 依照上表的接取資料，其虛擬位址空間（virtual address space）至少有多大？（6 分） 其實體記憶體（physical memory）至少有多大？（6 分） 五、請說明為何排程器（scheduler）要區別I/O 受限程式（I/O-bound programs）和CPU 受限程式（CPU-bound programs）。（20 分）