944操作系統(tǒng)大綱 完全版.doc

一、試卷滿分及考試時間本試卷滿分為 150 分，考試時間為 180 分鐘二、答題方式答題方式為閉卷、筆試三、試卷內(nèi)容結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 45 分計算機(jī)組成原理 45 分操作系統(tǒng) 35 分計算機(jī)網(wǎng)絡(luò) 25 分四、試卷題型結(jié)構(gòu)（計算機(jī)專業(yè)基礎(chǔ)綜合）單項選擇題 80 分（40 小題，每小題 2 分）綜合應(yīng)用題 70 分五、操作系統(tǒng)部分試卷題型結(jié)構(gòu)單項選擇題 20 分（10 小題，每小題 2 分）綜合應(yīng)用題 15 分（2 小題，總共 15 分）操作系統(tǒng)【考查目標(biāo)】1. 掌握操作系統(tǒng)的基本概念、基本原理和基本功能，理解操作系統(tǒng)的整體運(yùn)行過程。2. 掌握操作系統(tǒng)進(jìn)程、內(nèi)存、文件和 I/O 管理的策略、算法、機(jī)制以及相互關(guān)系。3. 能夠運(yùn)用所學(xué)的操作系統(tǒng)原理、方法與技術(shù)分析問題和解決問題，并能利用 C 語言描述相關(guān)算法。一、操作系統(tǒng)概述（一）操作系統(tǒng)的概念、特征、功能和提供的服務(wù)（二）操作系統(tǒng)的發(fā)展與分類（三）操作系統(tǒng)的運(yùn)行環(huán)境1. 內(nèi)核態(tài)與用戶態(tài)2. 中斷、異常3. 系統(tǒng)調(diào)用（四）操作系統(tǒng)體系結(jié)構(gòu)二、進(jìn)程管理（一）進(jìn)程與線程1. 進(jìn)程概念2. 進(jìn)程的狀態(tài)與轉(zhuǎn)換3. 進(jìn)程控制4. 進(jìn)程組織5. 進(jìn)程通信：共享存儲系統(tǒng)；消息傳遞系統(tǒng)；管道通信。6. 線程概念與多線程模型（二）處理機(jī)調(diào)度1. 調(diào)度的基本概念2. 調(diào)度時機(jī)、切換與過程3. 調(diào)度的基本準(zhǔn)則4. 調(diào)度方式5. 典型調(diào)度算法：先來先服務(wù)調(diào)度算法；短作業(yè)（短進(jìn)程、短線程）優(yōu)先調(diào)度算法；時間片輪轉(zhuǎn)調(diào)度算法；優(yōu)先級調(diào)度算法；高響應(yīng)比優(yōu)先調(diào)度算法；多級反饋隊列調(diào)度算法。（三）同步與互斥1. 進(jìn)程同步的基本概念2. 實現(xiàn)臨界區(qū)互斥的基本方法：軟件實現(xiàn)方法；硬件實現(xiàn)方法。3. 信號量4. 管程5. 經(jīng)典同步問題：生產(chǎn)者-消費(fèi)者問題；讀者-寫者問題；哲學(xué)家進(jìn)餐問題。（四）死鎖1. 死鎖的概念2. 死鎖處理策略3. 死鎖預(yù)防4. 死鎖避免：系統(tǒng)安全狀態(tài)，銀行家算法。5. 死鎖檢測和解除三、內(nèi)存管理（一）內(nèi)存管理基礎(chǔ)1. 內(nèi)存管理概念：程序裝入與鏈接；邏輯地址與物理地址空間；內(nèi)存保護(hù)。2. 交換與覆蓋3. 連續(xù)分配管理方式4. 非連續(xù)分配管理方式：分頁管理方式；分段管理方式；段頁式管理方式。（二）虛擬內(nèi)存管理1. 虛擬內(nèi)存基本概念2. 請求分頁管理方式3. 頁面置換算法：最佳置換算法（OPT）；先進(jìn)先出置換算法（FIFO）；最近最少使用置換算法（LRU）；時鐘置換算法（CLOCK）。4. 頁面分配策略5. 工作集6. 抖動四、文件管理（一）文件系統(tǒng)基礎(chǔ)1. 文件概念2. 文件的邏輯結(jié)構(gòu)：順序文件；索引文件；索引順序文件。3. 目錄結(jié)構(gòu)：文件控制塊和索引節(jié)點(diǎn)；單級目錄結(jié)構(gòu)和兩級目錄結(jié)構(gòu)；樹形目錄結(jié)構(gòu)；圖形目錄結(jié)構(gòu)。4. 文件共享5. 文件保護(hù)：訪問類型；訪問控制。（二）文件系統(tǒng)實現(xiàn)1. 文件系統(tǒng)層次結(jié)構(gòu)2. 目錄實現(xiàn)3. 文件實現(xiàn)（三）磁盤組織與管理1. 磁盤的結(jié)構(gòu)2. 磁盤調(diào)度算法3. 磁盤的管理五、輸入輸出（I/O）管理（一）I/O 管理概述1. I/O 控制方式2. I/O 軟件層次結(jié)構(gòu)（二）I/O 核心子系統(tǒng)1. I/O 調(diào)度概念2. 高速緩存與緩沖區(qū)3. 設(shè)備分配與回收4. 假脫機(jī)技術(shù)（SPOOLing） 題目示例 一、單項選擇題：第 140 小題，每小題 2 分，共 80 分。下列每題給出的四個選項中，只有一項是最符合題目要求的。 【試題示例：】5. 下列進(jìn)程狀態(tài)轉(zhuǎn)換中，不可能發(fā)生的轉(zhuǎn)換是A. 運(yùn)行就緒 B. 運(yùn)行等待C. 等待運(yùn)行 D. 等待就緒6. 設(shè)某系統(tǒng)中有 3 個并發(fā)進(jìn)程都需要 4 個同類資源，該系統(tǒng)不會發(fā)生死鎖的最少資源數(shù)是A. 9 B. 10 C. 11 D. 122018 年鄭州大學(xué)信息工程學(xué)院計算機(jī)專業(yè)基礎(chǔ)綜合考試：操作系統(tǒng)考試大綱第5頁 共5頁二、綜合應(yīng)用題：第 41 47 小題，共 70 分。 【試題示例：】45設(shè)頁引用序列：（1、2、3、4、2、1、5、6、2、1、2、3、7、6、3、2、1、2、3、6），物理塊（Page frame）數(shù)為 3，且所有的塊初始時為空。當(dāng)分別采用最近最少使用置換（LRU）、先進(jìn)先出置換（FIFO）和最佳置換（OPT）的頁面置換算法時，請問：各種頁面置換算法會發(fā)生多少次缺頁中斷？要求給出求解過程。46理發(fā)師問題描述如下：理發(fā)店包含一間接待室和一間工作室，接待室內(nèi)有 n（n1）把椅子；而工作室只有 1 把椅子。如果沒有顧客，理發(fā)師就去睡覺；如果顧客來時所有的椅子都有人，那么顧客就離去；如果理發(fā)師在忙且接待室有空閑的椅子，那么該顧客會坐在其中 1 把椅子上等待；如果理發(fā)師在睡覺，則顧客會喚醒他。請采用信號量機(jī)制解決該理發(fā)師問題（可用偽代碼描述）。計算機(jī)組成原理考試大綱一、考試基本要求及適用范圍概述 本計算機(jī)組成原理考試大綱適用于鄭州大學(xué)計算機(jī)技術(shù)專業(yè)的碩士研究生入學(xué)考試。計算機(jī)組成原理是 944計算機(jī)技術(shù)專業(yè)基礎(chǔ)綜合重要組成部分，主要內(nèi)容：理解并掌握單處理器計算機(jī)系統(tǒng)中各部件的內(nèi)部工作原理、組成結(jié)構(gòu)以及相互連接方式，具有完整的計算機(jī)系統(tǒng)的整機(jī)概念。理解計算機(jī)系統(tǒng)層次化結(jié)構(gòu)概念，熟悉硬件與軟件之間的界面，掌握指令集體系結(jié)構(gòu)的基本知識和基本實現(xiàn)方法。能夠綜合運(yùn)用計算機(jī)組成的基本原理和基本方法，對有關(guān)計算機(jī)硬件系統(tǒng)中的理論和實際問題進(jìn)行計算、分析，對一些基本部件進(jìn)行簡單設(shè)計。二、考試形式 碩士研究生入學(xué)計算機(jī)技術(shù)專業(yè)基礎(chǔ)綜合考試為閉卷，筆試，考試時間為180 分鐘，試卷滿分為 150 分，其中計算機(jī)組成原理為 45 分。試卷結(jié)構(gòu)（題型）：單項選擇題、綜合應(yīng)用題三、考試內(nèi)容命題學(xué)院（蓋章）：信息工程學(xué)院 考試科目代碼及名稱：944 計算機(jī)技術(shù)專業(yè)基礎(chǔ)綜合 （一）計算機(jī)系統(tǒng)概論了解計算機(jī)的類型，熟悉計算機(jī)的硬件組成部件及其作用。掌握主存有關(guān)概念：存儲器地址、存儲單元和存儲容量；位bit、字節(jié)byte、KB、MB、GB。掌握“存儲程序、程序控制”的馮 諾依曼計算機(jī)的基本思想。區(qū)別操作碼和地址碼（操作數(shù)）、指令字和數(shù)據(jù)字、指令流和數(shù)據(jù)流，理解指令周期（控制器工作周期）：取指、譯碼、執(zhí)行。掌握總線、處理器總線和系統(tǒng)總線的概念，熟悉數(shù)據(jù)總線、地址總線和控制總線的功能。理解目的程序、匯編程序、編譯程序的作用，區(qū)別機(jī)器語言、匯編語言和高級語言（算法語言）。掌握計算機(jī)系統(tǒng)的層次結(jié)構(gòu)、軟件與硬件的邏輯等價性思想。（二）運(yùn)算方法和運(yùn)算器掌握數(shù)據(jù)的定點(diǎn)格式，定點(diǎn)整數(shù)的表達(dá)范圍，有符號數(shù)和無符號數(shù)。掌握浮點(diǎn)格式的表達(dá)，熟悉浮點(diǎn)數(shù)的規(guī)格化，掌握規(guī)格化單精度浮點(diǎn)數(shù)與實數(shù)的相互轉(zhuǎn)換。理解真值和機(jī)器數(shù)，掌握定點(diǎn)整數(shù)的補(bǔ)碼、反碼、原碼和移碼表示法。掌握BCD碼、ASCII碼的編碼規(guī)律，理解小端方式和大端方式的存儲特點(diǎn)。區(qū)別漢字輸入編碼、機(jī)內(nèi)碼、字模碼和漢字交換碼。理解檢驗碼的作用，掌握奇偶校驗以及檢錯能力。理解補(bǔ)碼的加法運(yùn)算和減法運(yùn)算規(guī)律，熟悉溢出的概念、理解上溢（正溢）和下溢（負(fù)溢）的概念以及符號位檢測方法。了解內(nèi)部總線和外部總線、單向總線和雙向總線的概念。掌握浮點(diǎn)加減法的操作過程，了解其中對階、規(guī)格化、舍入處理的作用，理解并掌握IEEE754標(biāo)準(zhǔn)。（三）存儲系統(tǒng)熟悉存儲系統(tǒng)的分級（層次）結(jié)構(gòu)，掌握存儲訪問的局部性原理。理解存儲容量、存取時間、存取周期、存儲器帶寬的概念。了解SRAM和DRAM的特點(diǎn)，掌握SRAM存儲結(jié)構(gòu)與芯片地址引腳和數(shù)據(jù)引腳的關(guān)系，理解位擴(kuò)展和字?jǐn)U展的含義和作用，掌握芯片擴(kuò)展與芯片容量的關(guān)系。了解DRAM的行地址和列地址，理解DRAM的刷新操作和方法。了解ROM芯片的類型和各自特點(diǎn)。掌握Cache的功能和基本原理，掌握命中率、平均訪問時間和訪問效率的計算方法，理解Cache的地址映射的作用，掌握全相聯(lián)、直接和組相聯(lián)映射的原理和特點(diǎn)，熟悉Cache中標(biāo)記（標(biāo)簽）的作用，理解替換策略的作用，熟悉LRU、LFU和隨機(jī)法，理解Cache的寫操作策略，熟悉直寫法（全寫法）和回寫法（寫回法）。理解存儲管理，掌握虛擬存儲器的功能、物理地址和虛擬（邏輯）地址的概念，熟悉頁式和段式虛擬存儲器的管理和地址轉(zhuǎn)換，理解存儲保護(hù)，熟悉存儲區(qū)域和訪問方式保護(hù)的思想。（四）指令系統(tǒng)了解指令、指令系統(tǒng)、指令格式、操作碼、地址碼、指令助記符的概念。理解尋址方式的含義，區(qū)別指令尋址和數(shù)據(jù)尋址，掌握指令的順序?qū)ぶ泛吞S尋址，掌握數(shù)據(jù)的隱含尋址、立即尋址、寄存器尋址、直接尋址、寄存器間接尋址、寄存器相對（基址）尋址。熟悉堆棧的訪問原理，理解進(jìn)棧PUSH和出棧POP操作。熟悉指令系統(tǒng)的基本指令類型。掌握CISC和RISC的含義，掌握RISC的主要特點(diǎn)。（五）中央處理器熟悉CPU的基本模型和主要寄存器的作用。理解指令周期、CPU周期（機(jī)器周期、總線周期）和時鐘周期（T周期）的概念和區(qū)別。了解CLA、ADD、STA和JMP指令在CPU基本模型的執(zhí)行過程。理解微程序控制器和硬布線控制器的實現(xiàn)特點(diǎn)，了解微命令、微操作、微指令和微程序的概念。熟悉并行性的概念和提高并行性的技術(shù)途徑，掌握指令流水線的思想，理解流水CPU的時空圖，掌握資源相關(guān)、數(shù)據(jù)相關(guān)和控制相關(guān)的概念。了解SISD、SIMD、MIMD的分類概念，理解多媒體指令的并行處理特點(diǎn)。（六）總線系統(tǒng)理解內(nèi)部總線、系統(tǒng)總線和I/O總線（芯片總線、內(nèi)總線和外總線）的分類。理解總線的4個方面特性，掌握總線帶寬以及計算，理解串行傳送和并行傳送的概念，掌握起止式異步通信字符格式，理解總線仲裁的作用，了解集中仲裁和分布仲裁思想，掌握總線同步定時和異步定時（時序）的特點(diǎn)，了解各種總線數(shù)據(jù)傳送模式。了解PCI總線、ISA總線、SCSI總線和IEEE1394總線的特點(diǎn)。（七）外圍設(shè)備掌握像素、點(diǎn)距、分辨率、灰度級（彩色深度）、刷新、掃描的概念，以及對顯示效果的影響。掌握磁盤存儲器重要的技術(shù)指標(biāo)及計算方法，了解磁面、磁道、磁柱、扇區(qū)的概念，以及磁盤信息的分布特點(diǎn)。（八）輸入輸出系統(tǒng)理解I/O接口的作用，熟悉I/O端口的編址方式。掌握各種外設(shè)管理方式的概念和特點(diǎn)，熟悉查詢傳送方式的過程，理解中斷源、內(nèi)部中斷（異常）和外部中斷的概念，區(qū)別可屏蔽中斷和非屏蔽中斷，掌握可屏蔽中斷傳送方式的過程及其相關(guān)概念，熟悉單級中斷、多級中斷的概念。理解向量地址、中斷優(yōu)先權(quán)、中斷嵌套的含義，理解中斷控制器的作用。理解DMA傳送方式的特點(diǎn)，掌握DMA傳送的工作過程，了解CPU暫停、周期挪用、交替訪問的區(qū)別。了解通道的組成結(jié)構(gòu)和類型。四、考試要求 碩士研究生入學(xué)考試科目計算機(jī)技術(shù)專業(yè)基礎(chǔ)綜合為閉卷，筆試，考試時間為180分鐘，試卷滿分為150分。試卷務(wù)必書寫清楚、符號和西文字母運(yùn)用得當(dāng)。答案必須寫在答題紙上，寫在試題紙上無效。五、主要參考教材（參考書目）1.計算機(jī)組成原理第5版，白中英主編，北京: 科學(xué)出版社，2013年2.計算機(jī)組成原理 第3版，石磊主編，北京:清華大學(xué)出版社，2012年1. 數(shù)據(jù)結(jié)構(gòu)基本要求為：（1）. 理解數(shù)據(jù)結(jié)構(gòu)的基本概念；掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其差命題學(xué)院（蓋章）： 考試科目代碼及名稱： 異，以及各種基本操作的實現(xiàn)。（2）掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行基本的時間復(fù)雜度進(jìn)行設(shè)計與分析。（3）能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問題求解，具備采用 C 語言設(shè)計與實現(xiàn)算法的能力。1. 理解數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)、邏輯結(jié)構(gòu)與物理結(jié)構(gòu)間的關(guān)系。了解數(shù)據(jù)類型、抽象數(shù)據(jù)類型、數(shù)據(jù)抽象和信息隱蔽原則。理解算法的定義、算法的特性、熟練掌握算法的時間代價及算法的空間代價計算方法；掌握用 C 語言描述算法的方法，能夠使用 C 語言編寫程序。2. 掌握線性表的兩種存儲結(jié)構(gòu)（順序存儲、鏈?zhǔn)酱鎯Γ?。熟練掌握順序表和單鏈表的插入、刪除等操作的實現(xiàn)及移動次數(shù)計算，以及雙向鏈表、循環(huán)鏈表、雙向循環(huán)鏈表各種操作的實現(xiàn)。能運(yùn)用順序存儲和鏈?zhǔn)酱鎯Y(jié)構(gòu)解決實際問題。3. 掌握棧和隊列的定義、特性；掌握棧和隊列的順序表示、鏈表表示；掌握棧和隊列的相應(yīng)操作（入棧、入隊列、出棧、出隊列等）的實現(xiàn)。能使用棧和隊列解決實際問題。4. 了解串的定義、特性；掌握串的三種存儲結(jié)構(gòu)及特點(diǎn)； 了解數(shù)組和廣義表的定義、特性；掌握特殊矩陣和隨機(jī)稀疏矩陣的壓縮；能夠靈活運(yùn)用數(shù)組解決實際問題。5. 掌握（完全）二叉樹的概念、性質(zhì)及表示；熟練掌握二叉樹的順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、遍歷方法；線索二叉樹的基本概念和構(gòu)造、掌握森林與二叉樹的轉(zhuǎn)換及樹的遍歷。能夠運(yùn)用樹結(jié)構(gòu)解決實際問題。 掌握 WPL 計算方法和霍夫曼樹的構(gòu)造及對帶權(quán)數(shù)據(jù)進(jìn)行編碼譯碼的方法。6. 理解圖的基本概念（有向圖、無向圖、完全圖、圖的連通性），熟練掌握圖的鄰接矩陣、鄰接表的存儲表示，了解十字鏈表和鄰接多重表存儲結(jié)構(gòu)；熟練掌握圖的深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷方法。 掌握構(gòu)造最小生成樹的 Prim 算法和 Kruskal 算法的思想；熟練掌握活動網(wǎng)絡(luò)的拓?fù)渑判蛩惴ê退枷耄皇炀氄莆涨蠼怅P(guān)鍵路徑的方法，了解求解圖的最短路徑的算法；能夠運(yùn)用圖的相關(guān)知識解決實際問題。7. 熟練掌握靜態(tài)查找表的順序查找和折半查找算法；熟練掌握二叉排序樹的表示、搜索、插入、刪除算法；掌握 AVL 樹的平衡化旋轉(zhuǎn)、構(gòu)造、插入時的調(diào)整方法；熟練掌握 B-樹的插入和刪除時結(jié)點(diǎn)的分裂和合并方法；熟練掌握 Hash 法，包括 Hash 函數(shù)的構(gòu)造及解決沖突的方法。熟練掌握各種查找方法對表中元素查找成功時平均查找長度的計算方法。能夠靈活運(yùn)用基本的查找方法解決實際問題。8. 掌握排序的基本概念；掌握插入排序（直接插入排序，折半插入排序、希爾排序）、 起泡排序、快速排序、簡單選擇排序、樹形排序、堆排序、二路歸并排序、多關(guān)鍵字排序的思想、排序過程、算法及其性能分析方法；各種內(nèi)部排序算法的比較及應(yīng)用。能夠靈活運(yùn)用基本的排序算法解決實際問題。4. 計算機(jī)網(wǎng)絡(luò)考試內(nèi)容 掌握計算機(jī)網(wǎng)絡(luò)的基本概念、基本原理和基本方法，以及計算機(jī)網(wǎng)絡(luò)的主要性能指標(biāo)。 掌握計算機(jī)網(wǎng)絡(luò)的體系結(jié)構(gòu)和典型網(wǎng)絡(luò)協(xié)議，掌握物理層、數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層、運(yùn)輸層和應(yīng)用層基本功能，以及相關(guān)協(xié)議的工作機(jī)制。 掌握典型網(wǎng)絡(luò)設(shè)備的組成和特點(diǎn)，理解典型網(wǎng)絡(luò)設(shè)備的工作原理 要求考生能夠運(yùn)用計算機(jī)網(wǎng)絡(luò)的基本概念、基本原理和基本方法進(jìn)行網(wǎng)絡(luò)系統(tǒng)的分析、設(shè)計和應(yīng)用?？荚囈?理解因特網(wǎng)的組成，分析分組交換技術(shù)的特點(diǎn)；掌握計算機(jī)網(wǎng)絡(luò)的概念、功能、分類；掌握計算機(jī)網(wǎng)絡(luò)的主要性能指標(biāo)。熟練掌握計算機(jī)網(wǎng)絡(luò)五層協(xié)議體系結(jié)構(gòu)參考模型，掌握服務(wù)、連接、對等實體、服務(wù)訪問點(diǎn)等重要概念，理解協(xié)議和服務(wù)之間的關(guān)系。 掌握物理層功能，奈奎斯特定理和香農(nóng)定理，以及計算方法；了解數(shù)據(jù)通信的基本概念和基本技術(shù)，了解多路復(fù)用技術(shù)。熟悉主要調(diào)制方法。理解 PCM編碼技術(shù)，以及 T1 和 E1 系統(tǒng)的特性。 掌握數(shù)據(jù)鏈路層的功能；了解 PPP 協(xié)議的基本原理；了解局域網(wǎng)的特點(diǎn)及拓?fù)浞诸悾粚W(xué)習(xí)網(wǎng)卡的作用。 熟練掌握以太網(wǎng)工作原理，包括 CSMA/CD 協(xié)議、MAC 地址、MAC 幀格式。理解在物理層和在數(shù)據(jù)鏈路層擴(kuò)展局域網(wǎng)的方法；熟悉網(wǎng)橋的轉(zhuǎn)發(fā)過濾機(jī)制，以及透明網(wǎng)橋轉(zhuǎn)發(fā)表的建立過程。 理解網(wǎng)絡(luò)層的功能及其在網(wǎng)絡(luò)參考模型中的位