《計算機系統結構》

參考材料

2011-03-01

目錄

自考得分四種答卷策略分析3

二、第一部分內容概述

?第一章緒論4

?第二章存儲系統設計12

?第三章流水線計算機設計技術25

?第六章并行處理機和相聯處理機46

三、相關筆記

?筆記一49

?筆記二55

?筆記三65

四、相關練習

?練習?一75

?練習二85

?練習三92

?練習四106

五、往年真題

?2002年4月題116

?2003年4月題⑵

?2004年4月題124

?2004年7月題126

?2005年4月題127

?2005年7月題129

?2006年4月題134

?2006年7月題136

?2007年4月題138

?2007年7月題140

?2008年4月題143

?2008年7月題145

?2009年4月題147

?2009年7月題149

?2010年4月題151

自考得分四種答卷策略分析:

自考得分四種答卷策略分析如下：

一、跳躍式答卷方略。近幾年自考試卷風格的一個明顯變化是：不再像以前把壓軸大題、中英自考

靈活性能力題、高難度綜合題集中于最后幾道大題、而是把難題靈活題的考點均勻分散，穿插在卷面的

各個部分，試卷的前半部分也穿插編排一些小分值但難度較大的燙手小題。答卷一開始被這些燙手小題

纏住，一是耗費過多的時間，造成前后答卷時間分配不均衡，大大減少后面大分值試題的思考分析時間，

二是大腦思維在小題解答上卡殼后，過早消耗腦力，產生負擔過重的心理焦慮，也不利于在后面答卷中

激發出自己最佳的應考水平。

所以建議同學們在答卷做題一開始，就要采取跳躍式應考策略：對自己熟悉的、解題思路能一氣呵

成順利鋪開的小題能正確解答，就一一解出。對一些難度較大的小分值靈活試題經過一番認真思索后仍

找不出解題思路的，就可以跳過去不做，繼續解答下面題目。

跳躍式答題方略的指導思想是：量體裁衣，看分值投入時間，分值小就少花時間，分值大就多投入

時間。假如一道只有2分的選擇題耗時與一道10分的大題耗時一樣多，那肯定不是最優的答題時間分配。

因此，考試動筆一開始就遇到“燙手”的小分值難題，不要硬碰，要機靈地把其曬在一邊，讓它靠

一邊“涼一涼”，等解答完大題后，再去心情輕松地強攻。

這種答卷策略的好處是：一開始就用較少的時間較低的腦力消耗解答大量順手試題，積累較多的卷

面得分，潛意識引導應考心態進入輕松自信的良性循環之中，一點一點“預熱”平時復習中烙印在大腦

中的考試題感，大腦思維狀態逐漸活躍起來，心情趨于放松，解題思路如行云流水般打開。

二、流水線式答卷方略。北京自考網這種答題方略適合于那些基礎過硬成績穩定細心冷靜的考生。

它要求考生從答卷開始就認真細致地解題，盡可能做到每答一題就對一?題，逐題逐道按卷面順序往下做,

如同工廠的流水線生產程序。一般是解答完最后一道壓軸題后，所剩余的重表復查卷面時間并不多。這

種答卷方略的好處是大腦思維狀態平和，應考心態平穩，答題順序與節奏穩健，不會出現卷面得分忽高

忽低的失常現象，正式自考答卷得分率與平時的模擬考試基本一致。

三、棄一得九式答卷方略（又稱棄子答卷方略）。有這樣一句圍棋格言：“不會棄子的棋手永遠成不

了超一流棋手。”同樣，在考場上不善于棄題的同學稱不上是一名成熟的應考高手。

同學們在次數頻繁的考試中，總會碰到一些絞盡腦汁仍理不清思路的特殊題型。面對這些高難度試

題，可以用兩種方式來處理：第一種方式是使用跳躍式答題策略，到最后集中精力全力“啃硬頭”，第

二種方式是徹底放棄之。

棄一得九式的答卷方略與周圍的棄子搶先手取厚勢、象棋的丟卒保帥有異曲同工之妙：堅決丟棄分

值不大的特殊難解題型，全力保住絕大部分熟悉題型的百分之百得分。這正如老子辯證哲學中所說的“將

欲得之，必先棄之”。

假設丟棄的題型分值累計不超過15分，考試時間為150分鐘，充一得九的答題得分效益公式是：150

分鐘答卷時間=135分卷面分值，即放棄15分左右難度極大的實在無法做出的題目，集中寶貴的150分

鐘考試答卷時間去確保其余135分分值的穩操勝券。相對于大多數考試實力一般化的普通考生來講，如

果長時間一味被難題“粘”住，盲目更摳硬鉆那望題興嘆的高難度15分而自始至終理不清眉目，最終不

但這15分爭取不到，就連卷面其余的135分分值也要白白丟失許多，白白錯過能檢查出前面做錯試題的

良機。試以下表舉例模擬估算說明。

四、易中難三層篩式答卷方略。三層篩式答卷方略按試題的易、中、難一層一層過濾解答：把試卷

從頭到尾瀏覽一遍，先下手解答自己很熟悉一想即會的容易題型，再篩找出有?定靈活性半綜合性、經

多方面分析思考后就能理清眉目的中等難度試題認真解答，最后再集中時間全力攻克剩下的壓軸大題。

在自考考場匕考生們如能有效使用各種答卷策略和技巧，可優化答卷時間分配，預熱啟動全腦答

題靈智思維，增強考試信心，進入超常發揮的最佳應考狀態，有利于最大限度激發出自己平時厚積的知

識，使應考思維、應考能力及考試潛能有超水平的發揮，成人自考這是取得理想自考成績的最后一個決

定性關口所在。

第一部分內容概述

計算機系統結構

第一章緒論

★計算機更新換代的標志

1.制造計算機的器件更新---計算機發展的物質基礎。電子管、晶體管、中小規模IC、VLIC?

2.計算機系統結構的改進——系統結構改進，重要概念的提出并實現。

地址寄存器、通用寄存器、浮點數中斷、輸入輸出通道、間接尋址、虛擬存儲器、微程序設計、Cache系列

化等。

系統結構的性能同樣對機器的速度有影響。

65?75年間器件速度提高卜倍，而指令時間卻以百倍速度下降。

§1.1計算機系統結構

§1.1.1計算機系統層次結構

一.從功能或從使用者的角度可以將計算機劃分為多級層次。

用戶

高級語言程序員

1、MO,Ml是機器的核心部分，某些機器不用微程序解釋執行指令，直接用硬件邏輯實現機器指令系統，MO和

Ml就合而為一。

有些機器用毫微程序實現微程序，則M0還可以劃分為兩級。

2、M2機器語言機器用指令系統編寫程序，是機器語言程序員的工作。微機原理的指令系統編程為這一級。

3、M3操作系統機器該級上支持兩類指令；機器語言指令，操作系統指令（打開文件，讀/寫文件，關閉文

件等）。操作系統是運行在第二級上.的解釋程序。

4、M4匯編語言機器使用匯編語言編程，先譯成M3或M2的語言后執行。

5、M5高級語言機器高級語言程序先譯成M4或M3級語言而后執行。解釋執行只是邊譯邊執行。

6、M6應用語言機器這類語言程序大多是用高級語言編寫的語言程序實現的，用戶不必是計算機專業人員,

僅用終端鍵盤、鼠標器等發出一些命令進行操作。例用FoxPro,DBASE等編寫的管理系統控制系統等。

二.層次結構的作用

1.有助于對計算機系統的理解，軟件、硬件、固件的地位和作用。

2.有助于各種語言及其實現。

3.有助于理解計算機系統結構并設計新的計算機系統。

§1.1.2計算機系統結構定義

一.定義：（Amdahl1964年提出）山程序設員所看到的計算機系統的屬性——編寫能在機器上正確運行的程序

必須了解的概念性結構和功能特性。

特點：不同程序設計者所看到的計算機系統的屬性不同。

高級語言程序設計者幾乎看不到不同計算機系統的區別（TRANSPARENCY）。

二.本課程的范圍

研究計算機系統軟件、硬件/固件功能分配及其界面的確定。包括:

數據表示

尋址方式存貯系統

指令系統I/O系統結構

寄存器定義中段機構

工作狀態的定義和切換信息保護

實質：是機器語言程序員需要了解的和遵循的計算機屬性。

不包括：數據流、控制流、邏輯設計和物理實現。

§1.1.3計算機系統結構、計算機組成與實現

一.區別

1、ComputerArchitecture計算機系統軟件、硬件/固件功能分配及其界面的確定。

2、ComputerOrganization計算機系統結構的邏輯實現，包括數據流、控制流組成及邏輯設計。

3、ComputerImplementation計算機組成的物理實現

包括：物理結構——處理機、主存等部件

器件技術——集成度、速度、專用器件設計

組裝技術——器件、模塊、插件、底板的劃分

連接、信號傳輸、電源、冷卻及

整機裝配。

例：指令系統確定屬（CA）,指令實現包括取指、取數、運算、存結果等，操作排序屬（CO）,電路、器件設

計及裝配屬（CI）。

又例：確定是否有乘法指令屬（CA）,用乘法器還是用加法器及右移實現乘法指令屬（CO）,器件的選定（集

成度、速度、類型、數量、價格等），及微組裝技術屬（CI）。

又例：主存容量及編址方式的確定屬（CA）,為達到性能價格比確定主存速度、邏輯結構（存貯體結構）屬（CO）,

主存系統的實現（器件、邏輯電路及微組裝技術）屬（CI）。

二.系統結構范圍

1、數據表示硬件能直接識別的數據類型和格式等。

2、尋址方式最小尋址單位，尋址方式的種類、表示和地址計算等。

3、寄存器組織操作數寄存器、變址寄存器、專用寄存器的定義、數量和使用約定等。

4、指令系統機器指令的操作類型和格式，指令間的排序方式和控制機構等。

5、存貯系統最小編址單位、編址方式、主存容量、最大編址空間等。

6、中斷機構中斷類型、中斷分級、中斷處理程序功能及入口地址等。

7、機器工作狀態如管態、目態的定義和切換。

8、機器級的I/O機構I/O聯接方式、設備訪問方式、源、目的及其傳送量，操作結束與出錯指示等。

9、信息保護保護方式、硬件保護支持等。

三.計器機組成范圍

1、數據通路寬度數據總線信息位數。

2、專用部件的設置例乘除部件、浮點運算、字符處理、地址運算，部件數量。

3、功能部件的共享度邏輯上無關的操作共用的部件，只能分時使用，對速度有影響，但共享度高。降低共

享度提高速度，必然增加功能部件，價格上升。

4、功能部件并行度功能部件的控制和處理方式是串行還是重疊流水，分布處理。

5、控制部件的組成硬件控制還是微程序控制，單處理機、多處理機還是功能分布處理。

6、緩沖和排隊技術不同速度部件間怎樣設置緩沖器彌補速度差異，設置多大容量。等待處理事件的排序：

隨機、先進先出、先進后出、優先級、循環隊等。

7、預估、預判技術預測未來行為的原則，以優化性能和處理。

8、可靠性技術冗余技術和容錯技術可提高可靠性。

四.界限的浮動性

1.有些計算機作為系統結構的內容，在另一種計算機上是作為計算機組成的內容。

2.在計算機組成和實現中提出和使用的技術，可能上升為系統結構的內容，例如Cache思想，在有些機器上

加上了Cache管理指令，而使Cache為系統結構的一部分。

隨著新器件的出現，系統結構包括功能模塊設計，使三者界限模糊。

§1.1.4計算機系統的發展

一.馮?諾依曼計算機特征

1.組成

1).數據指令在存儲器中，同等對待，程序可改。

2).程序由指令組成，指令驅動，順序完成處理工作。

3).二進制編碼數，采用二進制運算。

2.特征

1).存儲器字長固定，順序線性一維編址。

2).一級地址空間，按地址訪問，地址唯一。

3).由指令形式的低級語言驅動，指令包括操作碼、數址兩部分。數型由操作碼指明。

4).順序執行指令，由轉移指令實現分支。

5).運算器為中心，I/O經過運算器，各部件由控制器控制。

二.系統結構的改進

1、由串行算法改變為并行算法，由運算器為中心變為存儲器為中心，出現了向量計算機，并行計算機和多處

理機等。程序數據存儲器分開。

2、高級語言與機器語言的語義距離縮小，出現了面向高級語言和直接執行高級語言的機器。

3、硬件子系統和操作系統，數據庫管理系統軟件相適應，產出了面向操作系統和數據庫的計算機。

4、從指令驅動型改變為數據驅動型和需求驅動型，而出現了數據流機器和歸約機。為指令所用的數據就緒便

激發，指令無先后順序，可并行執行。

5、包現了適應特定環境的專用計算機，如快速傅里葉變換機器，過程控制計算機等。

6、為獲得高可靠而出現容錯計算機。

7、系統功能專業化、分散化，出現了各種分布的計算機，包括外圍處理機，通信處理機等。

8、出現了與LSI與VLSI相適應的系統結構。

9、出現了非數值化信息的智能計算機。例自然語言、聲音、圖形和圖象處理等，不用精確算法，而用知識推

理，經驗性非精確推理。

§1.1.5計算機系統結構的分類

一.Flynn分類法

1966M?J?Flynn定義

概念：InstructionStream機器執行的指令序列

DataStream由指令調用的數據序列，

括輸入和中間結果。

multiple（多倍性）系統受限制的允許同時處于同一執行階段的指令或數據的最大可能個數。

分類：SISD單指令單數據流

SingleInstructionStreamSingleDataStream

SIMDSinglehstructionSreamMiltipleDita8ream

MISDMultipleInstructionStreamSingleDataStream

MIMDMultiplehstructionStreamMultipleDateStream

1、SISD

IS

2、SIMD

各處理部件由同一條指令驅動，處理不同數據

SM

各處理部件由同一條指令驅動，處理不同數據

3、MISD

f—05----------------------

isiLui--------向1.ISM

|IS2TU2|~€S--------pt|2I|———

MM1丘2」I

ISnbunI------CS------HpunIj

塔玨IS2IS1

各pu由不同指令控制，處理同一數據流，前一結果送后一級pu

二.馮氏分類法(馮譯云1972)。

概念

pm(最大并行度)計算機系統在單位時間內能夠處理的最大的二進制位數。

pa(平均并行度)T

Y.piAti

pa=----i=4---------------------

T

其中Pi為Ati內同時處理的二進制位數

u(平均利用率)

Zpi

字寬(n)64

三.Handler分類法(WolfganIfandler1977)

計算機硬件的三個層次

1、程序控制部件的個數(pcu)k

2、算術邏輯部件(Alu)或處理部件(pe)的個數d

3、每個算術部件包含基本邏輯線路(Ele)的套數w

系統結構t(系統型號)=(k,d,w)

流水線系統結構t(系統型號)=(kXk',dXd',wXw')

k',d',w'分別表示流水線中所含相應部件的個數

例Crayl有一個cpu即k=l

12個處理部件d=12

最多可實現8級流水線d'=8

字長64位w=64

可以實現1?14位流水線處理w'=l?14

則t(Crayl)=(l,12X8,64(1?14))

§1.2技術和系統結構

器件對系統結構的影響

速度、集成度、體積、可靠性、價格。

通用片通用門、邏輯、存儲芯片等。

現場片到現場按用戶要求修改，Eprom,Fpla等。

用戶片按用戶要求專門設計制造的芯片，周期長,

價格高。

二.新思想新技術的采用，發展和下移(從大型向中，小，微型機下移)。

三.掌握系統設計技術和系統評價方法。

§1.3系統結構的評價標準

--價格、性能指標(性能/價格比)。

適用于同類型機器之間的比較，價格包括開發成本和生產成本。

19501990

二.系統結構的效率與其負荷有關，與使用領域，處理對象有關。

三.設計簡單效率高的結構比設計復雜效率底的結構競爭力強。

本節從價格與硬件兩個方面討論評價標準，說來說去是性能價格比。

§1.4影響系統結構的幾個重要因素

§1.4.1軟件移植性(PORTBILITY)對系統結構的要求

★問題提出的原因：

1.同一種功能的軟件在不同硬件機器上無法運行時，必須重新設計。

2.同一種機器的改進，器件的發展使?種機器向前發展，軟件必須與新機兼容。

大量軟件的再設計價格不合算。如果使軟件具有可移植性，大量軟件無需要再設計，而且可以積累和發展F

去。

★統一高級語言的要求

困難所在：

1.不同用途的語言語法結構和語義結構不同。程序員偏愛熟悉的語言。

2.對語言的基本結構尚未透徹的統一認識，如GoTo語句。

3.同一種高級語言無法在不同種機器上運行，因為字長“零”的定義，10設備種類數量，子程序結構，尋址空

間，0S不盡相同，且有“方言”，允許匯編語言等不盡相同。

仍是研究解決的方向ADA是邁出的第一步。

★解決辦法：系列機思想兼容機的出現

在軟硬界面上確定好一種系統結構，從這兒出發軟件設計者設計軟件，硬件設計者根據速度、性能、價格的

不同采用不同的硬件技術和組成，實現技術，研究不同檔次的機器。例如IBM360和IBM370系列機。

系列機的軟件是兼容的(softwareCompatibility)。通常是向上兼容，難于向下兼容。

兼容機是生產能使用某種系列機的軟件的機器(ComalibleMachine),

§1.4.2應用對系統結構的影響

從應用角度看，計算機分為通用計算機和專用計算機兩大類。專用計算機是因機器應用范圍不同，對機器

有不同要求而產生的。例如：

科學計算要求有浮點表示，高速計算，陣列計算等。信息處理要求大量簡單的計算，字符串處理和卜進制運

算。實時系統要求強的實時能力，1/0,和中斷系統。當機器專用于某一方面時，硬件的利用率較低，性能比下

降。

二.仍然有許多專用方面未納入通用機

1).高結構化數值計算—氣象模型、流體流動、有限元分析

2).非結構化數值計算——蒙特卡洛模擬、稀矩陣

3).實時多因素問題——語言識別、圖象處理、計算機視覺

4).大存儲容量和輸入一輸出密集問題一數據庫系統、事務處理系統

5).圖形學和設計系統——計算機輔助設計

6).人工智能——面向識知識的系統，推理系統

專用計算機因銷量小而影響價格，但硬件費用相對下降

§1.4.3器件對系統結構的影響

一.通用片

現場片，通用現場型片

專用片(用戶片)制造高速性能價格比的途徑。

圖片機用戶用軟件的方法配以不同微程序就能和指令系統不同的各種系統結構的機器。

單片為處理器也屬于通用現場型片子。

二.器件集成度提高、速度提高，機器主頻提高

器件是新的系統結構和組成的基礎

器件的可靠性是流水技術的基礎

高速廉價的半導體存貯器是Cache和虛存的基礎

PROM是微程序技術廣泛應用的基礎

器件的性能價格比和速度提高是組成技術從高檔向

低檔下移的基礎。

器件的發展還影響算法、語言和軟件的發展。

三.器件發展改變了邏輯設計的傳統方法

由簡化邏輯節省器件轉化為選擇現有器件，縮小設計周期節省成本。使用通用片現場片和軟件設計。用戶片

的設計要求器件設計和芯片設計密切結合，使用CAD設(ComputerAidedDesign)

§1.4.4改進系統結構的三種方法

1.改進算法。

2.改進基本的系統結構。

3.利用并行系統獲得高速度。

§1.5系統設計的步驟

軟硬取舍的基本原則

提高硬件比例：可提高速度，減少存貯容量

提高成本、降低硬件利用率及靈活

性、適應性

提高軟件比例：和存貯容量上升

取舍原則在現有硬件和器件條件下，系統要有高的性能價格比。

二.計算機系統設計的思想

由上往下，由下往上和從中間開始三種設計思路。

1.由上往下據用戶要求逐級向下設計，下級都能使上一級優化，應用效能必然是好的，適用于專用計算機，

不適用于通用計算機。

2.由下向上只能制成通用機，而后配OS,編譯語言，硬軟脫節，很難優化軟件。

3.從中間向兩面發展?般從硬件機器級和操作系統的界面起向兩端發展。要求設計人員具有豐富的軟、硬件、

器件，應用等多方面的知識。應有有效的軟件設計環境和開發工具。

三.計算機系統結構設計的步驟

需求分析應用環境，語言種類和特性，操作系統

要求，外設特性，技術經濟分析和市場

分析。

需求說明設計準則，功能說明，器件性能說明。

準則：造價、可靠性、可行性、可擴展性、兼

容性、速度、保密性、靈活性、冒險性、程序

設計方便性。

概念性設計軟硬件分析和界面的確定。

具體設計界面要詳細具體定義，一個設計考慮多種

方案。從數據表示、指令系統、尋址方

式、存貯結構、中斷及I/O等。

優化和評價反復優化，獲得盡可能高的性能價格比。

第二章存儲系統設計

概述：

存儲系統是系統結構設計的關鍵，是“馮?諾依曼瓶頸”。

存儲系統用于：

1.存入數據、程序。

2.存放中間結果。

3.存放輸出結果。

關鍵：

速度取執行指令速度。

存取數據速度。

I/O的速度。

存儲器帶寬：每秒鐘能訪問的二進制位的數目

設存儲器周期T=500ns,每個存儲器周期訪

問32位，則帶寬=32X10八9/500=64X10八6

位/秒即64兆位/秒=8兆字節/秒。

提高帶寬的方法：

1.減少周期T。

2.增加字長。

3.增加可同時訪問存儲器模塊。

提高速度的方法：存儲器的層次體系結構，由性

價不同的存儲器組成，運行若高速存儲器，價格

接近低速存儲器。

§2.1程序的特性

隨機存儲器的結構

隨機存取存儲器

任何存儲單元訪問一次的時間相同。速度高

二.順序存儲器、速度慢、價廉。

三.隨機存儲器與順序存儲器的配合。

計算機存儲器由兩部分組成：快速RAM、慢速順序存儲器。單執行某段程序時即調入。覆蓋技術。

系統的配合：編程注意將程序放到一起。

編譯和裝入程序將相互調用的程序段放

在一起。

例:Atlas的一級存儲器

RAM16kw4us/字輔助96kw2?14ms/字

ROMR

I1KX50ZlIALU?

工作區(ROM)_______________IProcessor

~幄制地址計算——

I輔存(數)4X4X50二

頁故障：以夜調入RAM,如在RAM中執行程序，發現某將執行指令不在RAM中，則叫頁故障。

四.程序特性：程序存儲局部性。

程序執行時間的局部性。

五.研究程序執行規律，減少頁故障。

1.預測未來訪問區域

(1).含現行指令地址區域

(2).常用數據

(3).可能被調用子程序

(4).嵌套調用的子程序

(5).現行棧區域

向量機器地址訪問流如圖，使頁面劃分太大。

可能卻不實際的地址訪問概率模型

§2.2Cache存儲器

一.高速存儲器Cache

在處理器與主存之間設置一個高速，小容量的緩沖存儲器，構成Cache主存存儲器層次，使速度接近于Cache,

容量卻是主存的。

特點：1.tmain/tcache=4?20

用Cache和主存組成二層存儲器系統。

被訪問項在Cache中時叫未命中(Cache失敗)

2.Cache未命中儲存問題用硬件算法實現。

3.Cache失敗儲存時間短，可承受更頻繁的cache

未命中。

去處理器Cache

Cache的基本結構

Cache操作

三.Cache設計參數影響的因素

1.teff=htcache+(1-h)tmain(讀的平均周期時間teff)

注h為命中概率，l-h為失效率

teff=tcache[h+(l-h)tmain/tcache]

k=10,h=0.99teff=1.09tcache

h=0.89teff=1.99tcache

k=20,h=0.99teff=1.19Cache

h=0.89teff=3.09Cache

2.Cache的組、行和每行字節數。

1）.全相聯存儲器

由前圖（圖2.5）組成的Cache叫全相聯Cache

★特點：①組成：由目錄和行組成

目錄中存放標志項，它實際主存地址中放數

據項，每行中數據個數（字節或字數）相等。

存取第幾個數由主存地址低位指定。

②讀寫時、先將主存地址高位與目錄中地址比

較，找到行，而后將該行開始點加主存低地址確

定，讀寫Cache地址。

★缺點：①Cache容量固定時，每行中數越少，目錄占的

比例越大，每?個數據時Cache與主存就成相

同的結構。

②如果Cache使用主存相同的制造技術，Cache

反而慢，因為比較門級比主存多。

2）.組相聯存儲器

Cache）,每組一個目錄存放標志（主存

地址高位）

★每組含K行，由主存地址低位中高位指定

★每行中有L個字節（字）

★Cache容量=LKN

★N=l就是全相聯Cache組大于16則影響

速度

★K=l叫直接相聯Cache

3）.直接相聯存儲器

§2.2.2Cache設計

—.主存地址與Cache地址的變換

32個字節存貯器要5根地址線，2竺個地址，地址要5

位,即log2"2人5=5

]og2Bbg2N?g2K]og2L

----------------------------------------------圭討地土止

區號組號行號行內地址一行

（塊號）中數據地址

*log2N一log2K'1%2L,

Cach(:地址

§2.2.3Cache替換算法

一.LRU（Least—Recentlyused）組中近期最少使用的塊被替換法則。

最近-------A------------7G--------------------

RA7

CBX

DC3

F.D

FEI

GF]

最久HGj

訪4*#__問?--------------

原則：最近使用的放在棧頂，最近使用最少的壓入棧底。

缺點:如果剛剛替換出Cache,馬上又要使用使又要調入。

二.OPT替換算法（最佳替換算法）

最近將訪AIE

B(2

C/-C

DI)/L

EE

FFI

G(F

最遠將訪HHG

原則：按最近將訪問之地址序列排列行（向前看）。

缺點：很難做到，硬件不能完全預知未來。

假定將要訪問的地址序列是：A,Z,B,Z,C,A,D,E,F,G,H

三.掩蔽目錄法(雙目錄法)

0

1

K-2

K-1

主目錄(K行)數據存貯Cache掩蔽目錄

原則：(1).被淘汰行記錄入掩蔽目錄

(2).調入行如在掩蔽目錄中有記錄，則該行標記1,表示該行有重復使用之可能。否則記錄標記0。

(3).替換時用LRU法，替換棧底規定的幾行中標志為0的行。

優點：減少重復使用行被替換的可能，提高命中率。

§2.2.4Cache性能分析的方法一地址序列模擬法。

模擬的過程：用一個典型的地址序列模擬Cache的動作，記錄未命中的地址統計地址數，得未命中數除以地

址數的未命中率。

二.注意兩個問題：

1.地址序列不一定代表實際工作序列

2.初始工作時Cache裝入階段未命中率對評價的影響

解決辦法：

I.用實際的地址序列測試Cache,對專用機比較合適

2.測試初期對地址作標記，去掉初始裝入時的未命中數后評價

三.改進模擬的方法

1.一次模擬度重分析Mattson等人1970年提出用LRU替換算法對一組K行的Cache模擬時，用一數組HIT

(I)記錄每一行的命中數，最終可以分析K行，K-1行，K-2行……Cache的命中率。

2.淘汰近期使用最多的行的命中數一地址壓縮技術。PUZAK提出用原始地址序列模擬測試K=1,L,N的Cache,

記下未命中地址，稱之為未命中地址序列，用該地址序列測統一個Cache,未命中數不變。

3.建立模型

§2.2.5Cache中任務切換對失效率領影響

概念：QSW：任務切換平均時間間隔。

冷啟動(cold-start)失效率：Cache空到Cache滿的失效率。

熱啟動(warm-start)現行進程啟動到裝滿測出的失效率.

熱啟動失效率與QSW的關系：

1.用戶進程和系統進程，系統進程占用越短，對用戶進程影響越小。

2.用戶進程間QSW越小，影響越大。

解決方法：

1.增大Cache容量。

2.修改調度算法，使切換回來時有用信息仍在Cache中。

3.改置多個Cache如目態Cache,管態Cache.

4.長的向量、字符行不入Cache。

§2.2.6Cache的寫操作

一.寫操作引起Cache與主存內容不一致

1.寫Cache而主存來寫，I/O或處理器間交換主存數據出錯。

2.1/0或處理器間交換數據而改變了已存數據，而Cache中仍是修改前的數據未修改。

二.解決辦法

1.寫直達法和寫回法。

寫直達法：寫Cache時也寫主存對應單元。寫不命中時大多寫在主存而不調入。

寫回法：當某塊被替換時才將該塊寫回主存。加一個修改標志位，修改過的塊被替換是必須寫回。寫不命

中時大多調入Cacheo

2.寫回法的雙目錄系統。

不命中時調入塊記入兩個目錄，一個由Cache使用，一個由I/O處理器使用，當I/O處理器在目錄中命中

時作相應的操作。輸出Cache或使Cache作塊作廢(Input時)。

3.共享Cache

I/O處理器

4.多處理器系統

各處理器Cache不共享，仍產生不一致

解決方法：

1).播寫法：寫到與主存同一單元之Cache。

2).作廢法：使其它處理器中Cache的相對應塊作廢，讓對方去主存取。

三.預取法提高命中率

1.坦預取法取i塊時，i+1塊也取到Cache中(75?80%)。

2.不命中預取法，i塊不命中時，預取i+1塊(30?40%)。

注意：預取不一定提高命中率，且應考慮開銷是否合算。

四.Cache設計注意事項

1.Cache盡量與Cpu靠近以保證速度。

2.Cpu與Cache的通訊量密度是Cpu與主存之間的10~30倍。

3.程序本身的特性是Cache提高機器性能的依據，程序失去這一特性時，Cache也就失去了作用。

4.可以增加硬件支持提高Cache性能，取決于性能的提高與價格的關系。

§2.3虛擬存儲器

虛擬存儲器：程序設計員直接用機器指令的地址碼對整個程序編址，而不考慮主存的大小，程序的地址空間比

程序運行時存放程序的主存可以大許多，只要程序需要，要多大就可以有多大，這一地址空間稱為虛擬存貯空間。

產生原因：高速主存往往空間有限，而程序往往大于主存空間。

多道程序運行時，主存被分配給每個作業，每個作業所得的存貯空間更小。

為解決高速主存與慢速輔助的存貯層次而提出虛擬存貯器概念和機制。

原理：在主存中只存放要訪問的程序部分，不訪問的部分保存在輔存中，到要訪問時再從輔存調入主存，輔存

的容量比主存的容量大得多，而速度慢得多。

§2.3.1段式管理

一.程序的特性一模塊化

一個程序可以解成多個在邏輯上相對獨立的模塊，模塊間的界面和調用關系是清楚定義的。

例：主程序、子程序、過程、函數。

數據：表格、數組、樹、向量、可變長度數據陣列等。

段：長度不等，以段的起點為0相對編址稱作偏移量。

二.段式存儲器管理的特點

1.程序分成段。

2.主存根據調入的段的大小分配存貯空間。

3.虛地址與實地址的對照關系。

1）.虛地址由基號（程序號）、段號、段內位移量組成。

2）.段表每個程序一個段表，表長（表行數）等于段數，每個與段號對應，無需段號段，但有主存起址，是否

裝入標志位，段長度，訪問方式（執行、可讀可寫只讀等）用于保護方式。

每個程序一張段表，因而多個程有多張段表，記錄段表起始地址的表叫段表基址寄存器，實際上也構成一

張表，每行由段表長度（n段）和段表起址組成。

4.程序運行時由虛地址的基號取到段表基址寄存器中的段表基址，由段號取到段基址，如裝入標志為1,則由

基址加上段內位移量組成實際地址訪問主存。

如該段裝入標志為0,則根據調入算法調入主存，填寫段表，再訪問。

5.管理法則

存貯管理是操作系統的責任，操作系統建立可用區表和占用區表，占用表記錄：

哪些區域被誰占用，及占用者的起始地址和長度，是否改寫標志。

可用區域表記錄：

區域基址、區域長度

1）.調入一段

在占用區域表中加一行，修改可用區域表。

2）.調出一致

將該段移入可用區域表并進行歸并。

3）.某程序被優先級高的程序擠出主存時，收回其全部占用區，歸并入可用區，而后再分配給新程序。

4）.分配法則

①首先分配算法：查可用區域表，能放下的第一個區域就分給。（見圖段式分配算法）

②最佳分配算法：分給剩余零頭最少的區域

5）.缺點：會有零頭，即使零頭之和大于要裝入段，也無法裝入。

可以將程歸并，使零頭合并成一個大的區域，但開銷太大。

§2.3.2頁式管理

一.段式管理的缺點：

1.段在主存中起址任意。

2.段長度任意

所以段表的地址段、長度段都放到最大位數，增加了輔助硬件開銷，降低了查表速度，主存管理困難。

二.頁式管理的特點

1.主存空間和程序空間（虛空間）劃分成等長的頁（512到nkb）,按頁順序編號。

2.主存地址np=nv+nr

nv主存頁號，nr頁內位移

3.程序地址Ni=N'v+Nr

Nv虛頁號，Nr頁內位移=皿

4.頁表組成

1）每道程序一張表，有頁表基址寄存器指示頁表在內存中的位置（起址），頁表基址寄存器由程序號（用戶

標志u化為b）指示。

2）.頁表每行對應虛頁號順序，只要存放實際內存（實存）起始頁號，長度短，硬件簡單。且無需寫頁長度。

5.虛實映象過程，程序用戶標志u化為基址寄存器號b,由b中記錄頁表起址加上虛頁號得實頁表（內頁表）

中行號，由該行取nv加上.虛頁號表內位移得實地址。

§2.3.3段頁式管理

段式管理的優點

1.每段獨立，利用程序員靈活實現段的鏈接，段的擴大和修改。

2.每段的對象單一，或程序，或數據，易于有針對性的保護。

3.共享程序或數據段易于管理。

二.段頁式管理

1.程序按模塊分段，段內以固定長度分頁，由段表和每段一頁表組成映象機構。

2.映象規則：有用號u,段號s,頁號p,頁內位移d四字段組成虛地址。u化為段基址寄存器號，由段基址

寄存器得段表，由段號從段表中得頁表基址，由頁表p行中得實頁起執，加上頁內位移d即可得內存實地址。

§2.4頁式虛擬存貯器構成

§2.4.1地址映象和變換

一.地址映象變換的內容

1.虛地址到實內存地址的映象和轉換。

2.虛地址和外存（輔存）地址的轉換。

前者用子程序運行時取指令，存取

3.存儲管理器是操作系統的?部分，它還要對整個存儲器空間進行管理，利用主存頁面表來記錄主存全部頁

面的占用（空閑）狀態，以便分配管理。

二.多級頁表的概念

例：虛地址24位，頁內地址10位，即頁長度為IKo

N'v（14位）Nr（10位）Ni

由N'vl4位可知，虛擬按上述法則建立頁表需274=270X2人4=16X270行，即需16K（16個頁面），頁表也

必須按頁存放，才能由頁表起址加頁號得到頁表中該頁號對應的行中存放的主存地址。

解決辦法：多級頁表

4位10位

\r

N'v（I4位）

如上例中，一一級頁表用

16行構成每行中存放第

二級頁表起址，由N'v

的高4位指出本虛擬一級表

地址在哪一行指示的1024個二級表

頁表中，哪一頁號存放的主存起址起。

對于段頁式管理還要加一級段表。

★多級表級數的算法：

i=log2A2AN'v/log2A2ANr=N'v/Nr

如每一項（行）占用Be個地址，Be是2的幕，則Be需二進制Ne位,Ne=log2ABei=N'v/Nr-Ne

例：N'v=26,每行占2個地址，即Nr=10,Ne=I

則i=26/（20-l）=3（同進一法計算）。

為了節省內存空間多級表除第級外，其余個級視需要調入，平時在輔存中。

三.頁式虛擬存貯器

1.多道程序的虛擬地址Ns=N-Ni

N為程序道數上限

即Ns=u+N'v+Nr

u為用戶標志或程序號

令Nv=u+N'v

則Ns=Nv+Nr

2.地址映象

I）.因為Nv?nv所以2ANv?2Anv

即虛擬存頁數比實存頁數多得多。

多道程序運行時只能將每道程序運行有關的頁調入主存。

地址映象變換是研究快速地將Nv轉化為np（主存實在地址）。

2）.全映象方式下虛擬的任何一頁可調入主存任何一頁。條件是主存中該頁空閑，否則發生沖突，叫頁面爭用

和實頁沖突。

3）.映象方式主要考慮減少頁面爭用輔助硬件少，成本低，實現方便及地址變換速度快。

3.頁表

由于Nr?Nv,所以大部分頁未調入主存，引起頁表中的大部分是空的，造成頁表占用地址空間

的浪費。

解決方法：

1).記錄實頁起址的地方，當該頁未裝入主存(裝入位為0)時存放該虛頁在輔存中的地址，以方便該頁調入

主存時找到輔存地址。

2).相聯目錄表法(目錄表法)。

將頁表壓縮，只存放己裝入主存的虛頁(Nr)和實頁(Nv)起址的對應關系。但地址變換時必須根據

Nr查相聯目錄中是否有Nv,有則轉化為np。否則要由管理系統按算法調入。

4.輔存調頁和外頁表

磁盤機號柱面號磁頭號塊號

輔存以信息塊編址，每塊存貯信息量同一頁。

輔存地址Nvd又叫外部地址，多用戶Nv轉化為Nvd也采用頁表或多級表。這一頁表稱作外頁表，

以區別于Nv到nv轉換用的頁表(叫內頁表)。

外頁表中也有裝入位，該位為0,則可能該虛頁還在更大的存貯器中，必須裝到存；該位為1時表示在輔存

中，可以調入主存使用，外頁表的地址變換：

在頁發生失效時，啟動I/O處理機或通道調頁，Ns到Nvd的轉換山軟件完成，處理器去執行另一

道程序。

§2.4.2替換算法

一.頁面爭用(實頁沖突)時，替換算法。

要求算法有高的主存命中錄，是否便于實現、成本低。

種類：I.Rowdom(RAND)法

2.FIFO法

3.LRU法

l.Rowdom法，碰運氣，對主存歷史信息不問不聞，有時違反程序局部性。

2.FIFO法，雖顧及歷史信息，但不一定能反映出程序局部性。

3.LRU法較好地反映出程局部性易于實現。

OPT法(OptimalReplacementAlgorithm)最好，但無法實現。

LRU法在增加主存頁面時命中率會提高，但FIFO法則不一定，有時反而降低。

§2.4.3虛擬存貯器的全過程。(見圖4.25)

§2.5頁或虛擬存貯器實現中的問題

§2.5.1頁面失效的處理

一.存在問題：

指令跨頁、操作數跨頁、尋址跨頁，如作為中斷處理通常是在一條執行完之后響應，但頁面失效出現在取指

令和取操作數時，是異常情況，必須立即處理。

1.故障點的現場保護問題。

1).保存部分關鍵性現場，故障處理完后，指令從頭開始。

2).采用后援寄存器技術，保存全部現場，處理完此故障并調入所需頁后取出后援寄存器內容，繼續執行完

該指令。

3).采用預判技術，排除故障于故障出現之前。

二.替換算法防止出現顛簸現象，

遇跨頁存貯至少要6個頁面處理。

三.頁面不宜過大。

§2.5.2提高等效訪問的措施。

與等效速度有關的主要問題

1.高的主存命中率

2.盡可能短的訪主存時間

二.縮短訪主時間的途徑

分析：1.地址Nv到Np的變換是100%無法避免的。

2.頁失效占1%。

3.替換《1%。

4.查頁表浪費時間驚人。

結論：地址變換速度是關鍵。

辦法：1.小容量快速隨機存貯器或寄存器組存放頁表(小機器)。

2.在大機器上增設快表。

快慢表并存，同時查表，從快表查到停止查慢表，查不到時從慢表查，并將查到的頁號送快表，

快表的替換也有算法，大多采用LRU法。

快表越大，則命中率越高，但查表速度越慢，必須采用折衷方案。

快慢表層次類似于主、輔存層次。

三.進一步提高快表速度的辦法

1.減少Nv的位數

Nv=u+Ni

去掉U,因為每一段時間只運行一個程序，表的每一行用一個標志，一個程序運行前快表標志位全清0,裝

入新引時置1。

存在問題：新舊進程變化全部快表，有時反而不快。

解決辦法：設專用指令，只清除指令行，但對系統程序員成了不透明的。

2.讓快表對應多個用戶，使任務切換時不修改塊表呢？

1).用單體多字方式按地址訪問存儲器，一次讀出幾個字，用幾套比較電路同時比較，實現同時相聯比較。

2).采用散列查找方法。

用函數A=H(Nv)將Nv-5nv等內容存入塊表A=H(Nv)單元中，查找時同樣從A=H(Nv)單元中取Nv和nv,

比較Nv以確定是否在快表中，比較同時據nv的從主存取已進行，Nv對就取，不對取消。

3).在塊表每一地址中存放一個以上的Nv和nv的映相關系，用ID(設計規定的常用任務個數)識別程序號,

以提高命中率。

(如圖4.31IBM370/168)

§2.5.3影響主存命中率和Cpu效率的因素。

頁面大小Sp,分給容量S1與命中率H的關系。

三.主存命中率與頁面調度算法有關。

1.系統顛簸(Thrashing)的原因。

1).頁面從主存到輔存調進調出頻繁，任務過重時，或分時系統的時間片過小是嚴重。

2).某進程丟失了一些關鍵性頁面，恢復后又不得不丟失一些頁面時發生。即這些頁面為工作集，分給的頁面

不夠用。

解決辦法是在程序執行期間動態地計算工作集，并騰出足夠的空間保持工作集。

發現工作集的方法：定義3(t,3)在時間t時刻對應窗口“的工作集。表示t之后co秒內被訪問的頁面集合。

2.利用工作集特征管理存在器

1)?頁故障時調入新一頁到工作集。

2).頁故障前3秒每未訪問頁中，擇近期很少使用之頁除之，如都被訪問過，則不刪除，讓工作集再擴大一頁。

3).如工作集中有二個甚至更多頁未被訪問過，則刪除兩個最少使用之頁。

注：3要在本進程工作時計算。

要有硬件支持，建立訪問表，在t時刻清訪問位，3時間后，訪問位為1的即為工作集。

3?頁故障頻率法：某進程定一個頁故障率的上限和下限。和

1).產生頁故障時用l/(tl-tO)估算頁故障頻率，tl,tO是兩次頁故障時間，取最近兒次頻率的平均值。

2).如頻率高于&則將新頁加入工作集，增配一頁存在空間。

3).如頻率小于0,而大于。1,將新頁加入工作集，淘汰一頁(按LRU法)。

4).如頻率低于。1,則淘汰近期最少使用的頁。

§2.5.4緩沖對虛擬存儲系統性能的影響

在磁盤系統中加?個智能緩沖器，也叫磁盤Cache,能使輔存