南京航空航天大學

大綱明細

1.計算機組成原理參考書

袁春風《計算機組成與系統(tǒng)結構(第2版)》，清華大學出版社，2015年8月

王黨輝，康繼昌，安建峰譯《計算機組成與設計 硬件/軟件接口(第5版)》，機械工業(yè)出版社，2015年7月

2.操作系統(tǒng)參考書

湯小丹，梁紅兵，哲鳳屏，湯子瀛，《計算機操作系統(tǒng)》(第三版)，西安電子科技大學出版社，2007年5月

3.數(shù)據(jù)結構參考書

嚴蔚敏、吳偉民 編著，《數(shù)據(jù)結構(C)語言版》 清華大學出版社，2007年

一、計算機組成原理部分

【目標】

1. 理解單處理器計算機系統(tǒng)中各部件的內部工作原理、組成結構以及相互連接方式，具有完整的計算機系統(tǒng)的整機概念。

2. 理解計算機系統(tǒng)層次化結構概念，熟悉硬件與軟件之間的界面，掌握指令集體系結構的基本知識和基本實現(xiàn)方法。

3. 能夠運用計算機組成的基本原理和基本方法，對有關計算機硬件系統(tǒng)中的理論和實際問題進行計算、分析，并能對以MIPS32架構為代表的的RISC計算機的CPU完成數(shù)據(jù)通路與控制器的設計與實現(xiàn)。

【大綱】

1.計算機系統(tǒng)概述

(1) 了解計算機的發(fā)展歷程;

(2) 掌握馮·諾依曼計算機結構的特點，計算機硬件的基本組成與功能，計算機系統(tǒng)的組成(硬件+軟件)及其層次結構，計算機的工作原理;

(3) 掌握計算機的性能指標，具體包括CPU執(zhí)行時間、CPI、時鐘周期、主頻等;

2.運算方法與運算部件

(1)掌握數(shù)制與編碼：包括進位計數(shù)制及其相互轉換，真值和機器數(shù)，BCD編碼，字符與字符串;

(2) 熟練掌握定點數(shù)的表示、運算與運算部件：包括無符號數(shù)的表示和有符號整數(shù)的表示;補碼定點數(shù)加減法運算;定點數(shù)乘除運算;識記溢出概念和判別方法;

(3) 掌握浮點數(shù)的表示與運算：包括浮點數(shù)的表示，IEEE754標準，浮點數(shù)的加減運算及其規(guī)格化;

(4)理解算術邏輯單元ALU的功能與結構，掌握補碼加減運算器如何實現(xiàn);并能夠對典型指令完成設計與實現(xiàn);

(5) 掌握不同層次程序員看到的運算：高級語言以C語言為例，ISA層面則以MIPS32為例;

3.存儲器分層體系結構

(1)掌握存儲系統(tǒng)的分層，半導體隨機訪問存儲器的組織，只讀存儲器及主存的主要技術指標等;理解存儲器芯片與CPU的連接，掌握多模塊存儲器的交叉存儲;

(2)掌握高速緩沖存儲器的CPU基本訪存過程， Cache和主存之間的映射方式，程序訪問的局部性原理對編程的影響及Cache-friendly的程序，理解Cache替換算法和Cache寫策略;

(3)掌握虛擬存儲器的基本概念，三種實現(xiàn)方案，缺頁的處理及快表的工作原理，注意虛擬地址和物理地址的轉換問題，如何查段表和頁表;TLB的原理和作用;平均訪問時間的計算等。

4.指令系統(tǒng)

(1)熟練掌握指令的基本格式，包括定長操作碼和擴展操作碼的優(yōu)缺點對比，采用擴展操作碼方式指令數(shù)目的計算及設計;

(2)指令的尋址方式：識記有效地址的概念，理解數(shù)據(jù)尋址和指令尋址，掌握常見尋址方式及尋址過程;

(3) 理解CISC和RISC的基本概念及區(qū)別;掌握以MIPS 32為代表的指令集的典型指令，并能夠完成相應的匯編程序設計。

5.中央處理器

(1)熟練掌握指令的執(zhí)行過程，并結合微指令考察一條指令執(zhí)行的各個步驟;

(2) 掌握CPU數(shù)據(jù)通路的功能及結構，掌握控制器的功能和設計，并能為MIPS32的典型指令完成相應的CPU設計，包括單周期及流水體系結構的設計;

(3) 掌握異常與中斷的處理機制及相應的設計與實現(xiàn);

6. 系統(tǒng)總線

(1)了解總線概述：識記總線的基本概念，分類，總線的組成及性能指標;

(2) 掌握總線仲裁的仲裁方式以及各自的工作原理;

(3) 掌握總線操作和定時方式以及原理;

(4) 了解總線標準，常用標準所規(guī)定的機械結構、功能結構和電氣規(guī)范;

7.輸入輸出組織

(1)了解I/O系統(tǒng)基本概念

(2) 識記各種外部設備，理解這些設備的基本工作原理和常見的性能指標;

(3) 識記I/O接口的功能和基本結構，I/O端口及其編址;

(4) 熟練掌握I/O的三種控制方式;中斷方式要求掌握中斷的基本概念，中斷響應過程，中斷處理過程，多重中斷和中斷屏蔽等;DMA方式要求掌握DMA控制器的組成和DMA的傳送過程。

二、操作系統(tǒng)部分

【目標】

1. 理解操作系統(tǒng)在計算機系統(tǒng)中的地位、作用及其發(fā)展歷史和特點。

2. 理解操作系統(tǒng)的基本概念、原理和思維方式，掌握操作系統(tǒng)基本的設計方法與實現(xiàn)技術。

3. 能夠運用操作系統(tǒng)原理、方法與技術分析問題和解決問題。

【大綱】

1.操作系統(tǒng)概述

(1)操作系統(tǒng)的概念、特征、功能和提供的服務

(2)操作系統(tǒng)的發(fā)展與分類

(3)操作系統(tǒng)的基本結構

2.進程管理

(1) 前驅圖以及程序順序執(zhí)行和并發(fā)執(zhí)行的特點

(2) 進程的基本概念和思想

(3) 進程的狀態(tài)與轉換

(4) 進程控制塊及其作用

(5) 進程組織

(6) 進程同步：進程同步的概念和同步原則，臨街資源和臨界區(qū)的概念，信號量及其應用，經(jīng)典進程同步問題

(7) 進程通信的基本概念和方法

(8) 線程的概念和多線程模型

3.調度與死鎖

(1)調度的概念

(2)調度隊列模型

(3)調度的基本準則與方式

(4)各種調度算法及其評價

(5)死鎖問題及其處理方法，包括死鎖的概念和原因，產生死鎖的必要條件，死鎖處理策略，死鎖的預防、避免、以及檢測和解除。

4.內存管理

(1)內存管理的基本概念：鏈接與裝入，邏輯地址與物理地址空間，對換與覆蓋，重定位

(2)連續(xù)內存分配方法，離散內存分配方法(分頁、分段、段頁)，

(3)虛擬內存分配方法(虛擬內存的概念，局部性原理，實現(xiàn)虛擬內存所需的硬件和軟件支持，請求分頁(段)管理，頁面置換算法)

(4)內存保護與共享

(5)抖動的概念和處理方法

5.設備管理

(1)I/O體系結構

(2)I/O控制方法

(3)I/O分配中的數(shù)據(jù)結構和分配方法

(4)通道和通道程序

(5)設備獨立性及其實現(xiàn)方法

(6)虛擬設備和SPOOLing技術

(7)緩沖管理

(8)設備處理與I/O軟件

(9)設備分配

6.磁盤與文件系統(tǒng)

(1)磁盤的結構和基本概念

(2)磁盤的調度

(3)磁盤的性能改善和容錯

(4)外存分配方法與物理文件組織

(5)文件存儲空間的管理

(6)邏輯文件組織

(7)文件的基本操作

(8)文件目錄及其管理

(9)文件共享和保護

7.操作系統(tǒng)接口

(1)操作系統(tǒng)接口類型

(2)系統(tǒng)調用概念

(3)系統(tǒng)調用的類型和實現(xiàn)方法

三、數(shù)據(jù)結構部分

【目標】

1. 理解數(shù)據(jù)結構的基本概念;掌握數(shù)據(jù)的邏輯結構、存儲結構，以及各種基本操作的實現(xiàn)。

2. 能對算法的時間復雜度與空間復雜度進行基本的分析。

3. 能選擇合適的數(shù)據(jù)結構和方法進行問題求解，具備采用 C 或 C++語言設計與實現(xiàn)算法的能力。

【大綱】

1.數(shù)據(jù)結構基本概念及簡單的算法分析

(1)數(shù)據(jù)結構基本概念;

(2)算法的定義、特性;

(3)簡單的算法分析：時間復雜度、空間復雜度;

2.線性表

(1)順序表和鏈表的存儲與基本操作;

(2)順序表和鏈表的應用;

(3)循環(huán)鏈表;雙向鏈表;

3.棧和隊列

(1)棧和隊列的定義;

(2)棧和隊列的順序和鏈式存儲;

(3)棧和隊列的應用;

4.字符串

(1)字符串的定義、存儲和操作;

(2)字符串的模式匹配;

5.數(shù)組和廣義表

(1)數(shù)組的順序存儲表示;

(2)矩陣的壓縮存儲：特殊矩陣、稀疏矩陣;

(3)廣義表的定義和存儲結構;

6.樹與二叉樹

(1)二叉樹的定義、性質和存儲結構;

(2)遍歷二叉樹;

(3)樹的定義和存儲結構;

(4)赫夫曼編碼;

7.圖

(1)圖的基本概念;圖的存儲表示：鄰接矩陣、鄰接表;

(2)圖的遍歷與連通性;

(3)最小生成樹;

(4)拓撲排序;

(5)關鍵路徑;

(6)最短路徑;

8.查找

(1)順序表查找;有序表查找;索引順序表查找;

(2)二叉排序樹;平衡二叉樹;B-樹;

(3)哈希表的構造和沖突處理方法;

9.內部排序

(1)插入排序;

(2)交換排序;

(3)選擇排序;

(4)歸并排序;

(5)基數(shù)排序;

(6)內部排序算法的比較和應用;