計算機組成復習提綱

1．計算機系統(tǒng)的層次結構,核心層為硬件->系統(tǒng)->外層應用軟件
2．軟件系統(tǒng)的分類:系統(tǒng)軟件和應用軟件.
系統(tǒng)軟件:編譯、os、匯編、應用軟件：edit,cad…
3．計算機硬件組成：alu（數(shù)據(jù)通路datapath）、存儲器、控制器、輸入、輸出
數(shù)據(jù)通道和控制器稱為cpu或processor
4．機器指令格式及其分類
分類：算術運算指令、訪問存儲器指令（傳送）、轉移指令、移位指令、輸入、輸出指令
格式：無址
三地址
mips指令：三地址與二地址
5．用匯編指令進行程序設計
g=h+A[i]  #寄存器分配
add $t1,$s4,$s4  #i->$s4,i*2->$t1
add $t1,$t1,$t1  #i*4->$t1
add $t1,$t1,$s3  #$s3為A數(shù)組首址,$t1為A[i]的地址
lw $t0,0($t1)  #$t0=A[i]的值
add $s1,$s2,$t0  #g=$s1=h+A[i]
詳見英文書p114
循環(huán)程序練習：轉移指令應用  p126
loop:g=g+A[i];
i=i+j;
if(i!=h) goto loop;
(bne $s3,$s2,loop用法)
while(SAVE[i]==k)  P127
i=i+j;
    (j loop用法)
case/switch statement P129
switch(k){//其中k取0,1,2,3
case 0:f=i+j;break;
case 1:f=g+h;break;
case 2:f=g-h;break;
case 3:f=i-j;break;
}
用beq，jr，j等指令給編寫，開關語句要用匯編指令設計、編寫，需要一張?zhí)D表
k*4+首址（跳轉表）
從表中取出跳轉表地址
6．尋址方式
lw $t1,0($t2)  #基地址尋址
add $t1,$t2,$t3 #寄存器尋址
addi $t1,$t2,100b #立即
beq $t1,$t2,l1 #pc相對尋址
j mm  #j型尋址，相當于直接存儲尋址
jr $t  #寄存器尋址
重點掌握尋址方式、常用指令用于循環(huán)、當循環(huán)和開關語句匯編程序編程方法

7．數(shù)組與指令+編程設計（了解編程方法） P174

基于MIPS架構CPU及指令設計不要求

8．機器數(shù)的表示，補碼，原碼和標準的浮點數(shù)表示及運算

重點掌握串行加法、并行進行加法的設計，及進位時間的計算，并行進位鏈及串行進位的電路的設計方法，補碼，浮點數(shù)表示（IE754標準）
原碼乘法器（除法器）補碼的設計原理及原理及邏輯框圖設計
補碼乘法，一位Booth’s P259,P257,加減交替法
IEEE 754標準：
  e=E-127  e:真值 E:機器表示（移碼）
 

    1  8    23
  E用移碼表示，其中1位符號位
  (-1)S×(1+Significant)×2E
  |M|=0.1XX......

9．掌握多時鐘周期計算機數(shù)據(jù)通路的結構，掌握指令執(zhí)行過程（能畫出指令執(zhí)行的狀態(tài)轉換圖）
了解位程序的設計方法和基本工作原理

10．存儲系統(tǒng)的體系結構，多級存儲系統(tǒng)Cache----直接地址映射或組相聯(lián)地址映射，全相聯(lián)地址映射，地址映射的原理設計

虛擬地址、實地址、頁表、頁表寄存器，含義必須搞清楚，能計算頁表容量=頁表單元數(shù)×（標志位+實頁號位長）
虛頁號數(shù)=虛擬地址-頁內(nèi)地址 P545-549,P569-570
缺頁中斷、命中、失效，寫通，回寫術語概念
重點掌握抵制變換結構的工作原理，變換邏輯設計及給定虛地址，主存容量，頁面大小，能計算，頁表單元數(shù)，實頁號長度，實地址位數(shù)及尋找到的實頁號
段表不要求

11．I/O系統(tǒng)

磁盤系統(tǒng)，平均旋轉時間，平均尋道時間
記錄格式，地址表示：頭號（頁號），道號，扇區(qū)號
串行接口，并行接口（按位寬傳輸分）
中斷分類，中斷處理過程，中斷請求，中斷響應，中斷處理，中斷返回，中斷屏蔽，開/關中斷概念，多重中斷
英文版P647-649
按控制方式分：
程序控制查詢接口
程序控制中斷方式，軟件排隊找中斷源，矢量中斷找中斷源
DMA 直接存儲器接口訪問控制
通道 接口編址方式：單獨編址方式（存儲器統(tǒng)一編址）
重點掌握：向量中斷，中斷響應，執(zhí)行中斷隱指令，中斷處理，中斷返回等詳細過程
英文版：第8章
王愛英：P332,P338  338-343
中斷隱指令
題型：名詞解釋，計算題，若需要也可畫圖，編程（總分不少于30分）

友情提示：
Computer Organization&Design The Hardware/Software Interface(2th Edition)機械工業(yè)出版社  ，即為文中所指英文版，為本校教學用書。
復習時應該以英文版為主，再輔以其它中文參考書即可，另請參考往年試題。

操作系統(tǒng)原理復習（40分，選擇題與主觀題）

linux系統(tǒng)可作為實例分析

進程管理、存儲管理、文件管理

第一部分：1 操作系統(tǒng)的概念

resource  management (cpu,memory,i/o derice)資源管理
control of programme execution (schedule,dispatch,etc.)程序控制
user interface (system call,shell,gui)用戶接口
選擇題可考
  2 os發(fā)展
simple batch system
  系統(tǒng)逐個運行作業(yè)（job）,但操作員可以成批提交
multi-pregramme batch system
  系統(tǒng)中存在多個作業(yè)，需要進行作業(yè)調(diào)度
time-sharing system (windows,unix,linux etc.)
  各用戶能分享計算機資源
  強調(diào)公平性（faimess）
  系統(tǒng)設計的主要目標：①縮短響應時間（response time）;
       ②提高吞吐量   （throughout）;
可考選擇題
real-time system
  滿足應用的實時性要求 （有的系統(tǒng)取消虛存來提高速度）
distributed system,embeded system
  (兩頭發(fā)展，一頭大，一頭小)
  3  os的典型體系結構
monolithic(整體結構，單塊結構) ：dos
layerd(層次結構)
micro-kernel(微內(nèi)核結構) ㈠優(yōu)點：1：擴充性好     
          2：內(nèi)核子
        3：不容易崩潰

      ㈡缺點：1：有可能速度偏慢
        2：設計有困難
module 結構來克服linux 單塊結構的弊端
4 現(xiàn)代操作系統(tǒng)
micro-kernel
multi-threading
multi-processor support
distributed os support
object-oriented desigh
virtual machine(如在windows上做linnx 的虛擬機)
real-time characteristics (solaris做的較好)
這些特點愈加明顯,

5 操作系統(tǒng)的硬件支持
inside cpu:register,MMU,cache
interrupt
DMA
cache

第二部分 進程管理

進程
process-a programme in execution(并不意味著一個占用cpu在執(zhí)行)
如：text section,data section,stack,current actirity.
進程是動態(tài)的。有生命的。主動的
進程是os 中資源擁有的基本單位（unit of responce ownership）
虛地址空間，內(nèi)有及其他資源(i/o設備。文件等)
進程控制塊（pcb）的管理：各種隊列
如linnx用鏈式隊列
進程的狀態(tài)
如:running,ready,wait,  stopped,  swapped,           zombie
             （ 暫停）（一部分或全部調(diào)出）（僵死，進程執(zhí)行完了，但
pcb還存在，進程還沒消亡）狀態(tài)遷移圖
線程（thread）
線程式是調(diào)度的基本單位（unit of dispatching）
進程中的線程共享進程資源，但擁有私有堆棧及線程控制塊（tcb,存儲寄存器值，優(yōu)先級及其他線程狀態(tài)信息）
①用戶級線程（ult:user-level thread）
用戶自己管理，但操作系統(tǒng)提供一個庫（library） 幫助，這個進程跟操作沒關，os 不知道       不一定操作系統(tǒng)給，可自己寫
操作系統(tǒng)調(diào)度的單位是進程，但如一個線程阻塞則整個阻塞 ，無法用多處理器
eg :posix thread (pthread)
②核心級線程
應用程序通過api調(diào)用核心線程管理例程(kernel thread facility) 來管理
          需要進行模式切換
需os 調(diào)度的基本單位（不同線程式可以在多處理上運行，一個阻塞不會導致整個進程阻塞）         
eg:windows thread
并發(fā)控制：互斥與同步
臨界資源（critical resource）
一次只能有一個進程訪問的資源
臨界區(qū)（critical section）
訪問臨界資源的代碼段（cs）
在一個時刻只有一個進程在臨界區(qū)，為了保證只有一個進程在訪問臨界資源
互斥（mutual exclusicn）
在一個時刻最多一個進程在臨界
同步
協(xié)調(diào)需要訪問臨界資源的進程，否則會導致race condition(競爭條件)
例：p0,p1習題課后
最大值？最小值？　�。玻保埃�
two processes=p0,p1
shared variable int talty:=0
p0p1

臨界區(qū)
①兩個前提：
  a．對處理器及各進程的相對速度（不會是的速度）不應有任何假設；
  b．進程在臨界區(qū)停留時間有限
②三個必須：
互斥（mutual exclusion）
有空讓進：若沒有進程在臨界區(qū)，則應該讓申請進入臨界區(qū)的進程中的一個立即進入
有限等待（bounded waiting）：申請進入臨界區(qū)的進程不會無止境的等待（即不會有饑餓現(xiàn)象）

１．軟件方法

�、倮赫n后習題
shared variables
  boolean flag[2];//初始flase
  int turn;//初始化0
Process Pi
  do{
   flag[i]=true;
   while(turn≠i)
    {while(flag[j]);
      turn=i;
     }
  
   flag[i]=false;
  
}while(1)
此算法正確嗎？
  不能保證互斥
②Dekker算法：算法不直觀，只能解決二個進程問題
　Peterson算法：直觀，只能解決二個進程問題
　Backery算法（面包房算法）

2．利用硬件支持
　中斷屏蔽：代價大，無法做到程序的交*執(zhí)行；多處理機無法實現(xiàn)
特殊機器指令
　 Test and Set instruction
Exchange instruction
優(yōu)點：適合多處理器環(huán)境、簡單
缺點：必須忙等待，可能導致餓死

３．信號量

①數(shù)據(jù)結構
Count integer:>=0,表示可用資源數(shù)
      <=0,絕對值表示掛起的起程數(shù)，初始化非負
②操作（是原語primitive）
wait(s) (即P):等待資源
siginal(s) (即V):釋放資源
③二元信號量
不能判斷有沒有掛起進程
④producer consumer problem
緩沖區(qū)無限
緩沖區(qū)有限　wait操作肯定不能換
　生產(chǎn)者消費者變換：寫滿時才能讀，如何實現(xiàn)？

四、并發(fā)控制：死鎖問題

死鎖(deadlock)
系統(tǒng)存在一個進程集合，該集合中的每個進程都在等待被集合中的其它進程占用的資源
死鎖發(fā)生的４個必要條件
①互斥(mutual exclusion)
②保持等待(hold and wait):保持等待，申請資源時擁有其他資源
③No preemption(非剝奪)
④Circular wait(循環(huán)等待)：若各類資源數(shù)均為１，一定死鎖
dead lock prevention 死鎖預防
間接預防：阻止Mutual exclusion,Hold and wait及No preemption都滿足
直接預防：阻止Circular waut的發(fā)生
一種可行的方法：有序申請法（對所有資源類別編號，進程申請按序進行）
例：哲學家就餐問題，筷子編號，先拿編號小的，再滿足大的　
dead lock avoidance死鎖避免
進程申請資源時，決定是否應該滿足
必須預先知道每個進程需要的各類資源數(shù)
銀行家算法：若新的狀態(tài)是安全的，則滿足它
Safe State:從此狀態(tài)出發(fā)，存在某種執(zhí)行序列（安全序列），可以使所有進程執(zhí)行完畢，不安全狀態(tài)不一定導致死鎖。
Dead lock Detection 死鎖檢測
已知目前各進程占用資源數(shù)和申請資源數(shù)，判斷當前是否發(fā)生死鎖，方法是給每個進程做標記(mark)

五、進程調(diào)度(CPU Scheduling)

1．調(diào)度準則

用戶角度：
①響應時間
②周轉時間
系統(tǒng)角度：
①ＣＰＵ利用率
②公平性
③吞吐量

２．調(diào)度模式

①Non-preemptive 非剝奪
  進程一旦被調(diào)度，則執(zhí)行至結束或不能繼續(xù)執(zhí)行（如因發(fā)起I/O操作而等待）
②preemptive 可剝奪
３．調(diào)度算法(了解一下剝奪非剝奪的)
①FCFS：先來先服務，直到結束（非剝奪）
②RR：Round Robin(除了它，其它的都基于優(yōu)先級)
③SPN：最短作業(yè)優(yōu)先，shortest process next
  如沒有給出時間，則要預測執(zhí)行時間，如指數(shù)平均法
④SRN：最短時間優(yōu)先 shortest remaining next
⑤HRRT：最高響應比優(yōu)先
⑥FeedBack:：反饋調(diào)度
⑦Fair-share scheduling 公平調(diào)度（Unix系統(tǒng)中）
a.多用戶系統(tǒng)中，用戶分組，每個組公平地享有CPU   preemptive
b.進程數(shù)多的組，各進程享有CPU的時間相對較少

第三部分 存儲管理

1．基礎知識

①各種基本概念
②MMU
      CPU Package

      CPU   MMU

邏輯地址變換為物理地址

2．連續(xù)存儲分配：分區(qū)（Partition）

按內(nèi)存分為若干分區(qū)，每個分區(qū)一個進程，以支持多道程序
......

3．分頁（paging）

硬件支持：TLB，MMU...
每個進程一張頁表
OS維護一張free-frame list
地址變換圖
頁表管理：
①分級法
②哈希頁表法
③倒置頁表（一個系統(tǒng)只有一個，可以節(jié)省空間，但速度慢）
POWERPC等就用到

4．分段

類似于連續(xù)存儲分配中的動態(tài)分區(qū)，但有區(qū)別，段與段可以不連續(xù)
地址變換圖

5．段頁式

如80386地址變換圖

第四部分 虛擬存儲
進程的虛地址空間

1．頁裝入策略（page fetch policy）

a). Demand Paging(按需調(diào)頁)：普通用
b). Prepare(預取)：Demand Paging的優(yōu)化，發(fā)生缺頁時，將該頁及臨近頁一起裝入
     （因為局部性）

2．頁替換策略

①Optimal：最優(yōu)化方法
②FIFO：最先裝入的被換出，得*隊列實現(xiàn)
③LRU：最久未用的頁被換出（基于locality，很有效）
④Clock policy：時鐘算法，LRU不易實現(xiàn)，用它來近似模擬
Belady’s Anomaly(Belady異態(tài))：內(nèi)存分配大反而缺頁率高，F(xiàn)IFO可能出現(xiàn)
⑤修改的Clock算法

3．抖動

進程缺頁率過高，可用如下方法加以解決：
①優(yōu)化算法
②提供更高速的交換設備
③增加內(nèi)存
④減少進程數(shù)
Windows NT有一個工作集的方法

4．交換

實現(xiàn)虛擬存儲的重要手段
擴大內(nèi)存，可使系統(tǒng)運行比內(nèi)存大的程序
交換空間
交換設備的管理
Swap cache

第五部分 文件系統(tǒng)與I/O管理

1．文件系統(tǒng)

文件分類
文件磁盤空間分配
文件控制塊FCB
目錄文件：存儲目錄下文件的信息（名字，F(xiàn)CB索引信息）
樹型結構的文件系統(tǒng)
文件訪問權限：
UNIX中的文件的三類用戶：User,group,other
進程的uid和gid

2．文件系統(tǒng)空閑磁盤空間管理

位向量法
鏈接法
成組鏈接法：UNIX中用
索引法

UNIX文件系統(tǒng)，Linux文件系統(tǒng)  linux:

UNIX：i-node(索引節(jié)點)

3．I/O管理
I/O設備分類
Buffer
I/O buffering(緩沖)：
①解決CPU與I/O速度匹配
②解決數(shù)據(jù)傳輸大小匹配
③提高I/O的存取
④直接由OS管理
Buffer與Cache的區(qū)別

磁盤調(diào)度
......

友情提示：新的招生簡章上的列出的操作系統(tǒng)參考書即為通常所說的恐龍書，然后還有一本W(wǎng)illiam Stallings的也可以參考,時間不夠可以參考這本書的中文版（第四版，電子工業(yè)出版社出版），恐龍書好像目前市面上是沒有中文版的，其實看起來很容易懂得，耐心點好了！
^_^

數(shù)據(jù)結構復習

第一部分 數(shù)據(jù)結構復習大綱

復習目標

1) 掌握基本數(shù)據(jù)結構的概念及其應用，2) 如：堆棧、隊列、鏈表、樹、堆、圖等
3) 掌握基本的sorting,Hashing和Searching算法

基本考試類型

證明題（如樹的特性）出題概率不高
填空題  可能會有英文書的例子
問答題（含數(shù)據(jù)結構設計、算法結構等）
如圖的表示方法、最小生成樹、最短路徑等
編程題（含算法設計）
注意思路清晰

數(shù)據(jù)結構的基本要素

鏈表
單向鏈表，雙向鏈表、循環(huán)單雙向鏈表、廣義表
隊列、堆棧：循環(huán)條件判斷、數(shù)組表示
樹
i. 樹的二*樹表示
ii. 二*樹的特性（層次、結點等）
iii. 二*樹的表達
iv. 二*樹的周游（如已知先、中序，v. 求后序）
vi. 線索二*樹（如已知中序線索，vii. 求遍歷）、哈夫曼樹
viii. 堆（Heap）---用數(shù)組表達，ix. 基本操作（插入、刪除）
x. 二*搜索樹（查找樹）
xi. 森林（森林的二*樹表達）
出題層次類型：
▲三種基本類型（線性表、樹、圖）的對象定義與操作實現(xiàn)---屬于概念層次
▲應用問題（如最短路徑）---屬于方法層次
▲查找與排序---屬于算法層次
查找：①靜態(tài)查找（順序、二分）
    ②動態(tài)查找（查找樹、哈希）
   查找樹：平衡樹，B+樹，B-樹）
排序：①選擇排序......堆排序
    ②交換排序......快速排序
    ③插入排序......SHELL排序
圖
1) 圖的定義和表達(4種基本表達方法)
2) 圖的操作：深度遍歷、廣度遍歷、連通分量、生成樹等
3) 最小生成樹（兩種算法）
4) 最短路徑
迪杰斯特算法、動態(tài)規(guī)劃法
5) AOV、AOE網(wǎng)
典型例子：拓撲排序、求關鍵路徑
排序
i. 插入
ii. 快速
iii. 歸并
iv. 堆
v. 拓撲
vi. 基數(shù)
查找
Hashing(構造、沖突解決)
最優(yōu)二*查找樹（概念即可）
AVL樹（四種情況，如何維護即可）--->B+樹
算法設計基本方法
回溯法
分治法（典型例子：歸并排序）
貪心法（如：選擇排序）
動態(tài)規(guī)劃法

第二部分 復習內(nèi)容

一、鏈表

1．單向鏈表就地逆轉
            q0     q1

         q0     q1     q2
while(q1!=Null){
q2=q1->next;
q1->next=q0;
q0=q1;
q1=q2;}
初始：q0=Null
   q1=L->next
廣義鏈表

二、堆棧和隊列

循環(huán)隊列（判斷滿和空條件）

三、樹

樹的二*樹表達
二*樹的特性
a) 第i層二*樹最多節(jié)點數(shù) 性質(zhì)1
b) 深度為k的二*樹最多節(jié)點數(shù) 性質(zhì)2
c) 性質(zhì)3（向上邊的角度與向下邊的角度結合
d) 2i,2i+1......
數(shù)組表示二*樹
二*樹的遍歷
遍歷算法
由前/中（后/中）推導后（或前）來構造樹
線索二*樹（加了一個結點，為了方便遍歷實現(xiàn)）
中序線索（用此來實現(xiàn)遍歷）
給出一棵樹線索化
堆
插入元素、刪除元素的算法

四、圖

1．圖的表示方法

數(shù)組表示：矩陣表示法（有向/無向）
  鄰接表（逆鄰接表）表示法（有向/無向）
十字鏈表（有向）
多重鏈表（無向）

2．圖的操作

深度搜索、廣度搜索
最小生成樹
a) Kruskal算法
b) Prim算法
最短路徑
AOV和AOE
拓撲排序、關鍵路徑

五、排序

插入排序，基本插入排序方法，希爾排序
交換排序：基本交換排序（冒泡、快速排序）
歸并排序：循環(huán)、遞歸
選擇排序：堆排序
快速排序（算法思想）
兩種思路：①單向掃描；②雙向掃描
堆排序
Adjust（從n/2開始調(diào)，保證左邊是堆，右邊是堆，往上調(diào)）

六、查找

1．Hashing

基本思想
構造方法
沖突解決（開放地址、線性探測、鏈表）
鏈表（關于其操作來實現(xiàn)沖突解決）
exp. Insert_LinkHashing(...)
2．AVL樹

首先判別各種平衡旋轉方法（找平衡因子被破壞的及誰破壞它的）
實現(xiàn)旋轉來維護（簡單的就是旋轉后滿足排序二*樹）

友情提示：一般參考嚴版的書和習題就可以了，另外最好把上課用的英文課件下來看看，可能有算法填空題會從中間出的。^_^