存儲系統

存儲系統是計算機的重要組成部分之一。存儲系統提供寫入和讀出計算機工作需要的信息（程序和數據）的能力，實現計算機的信息記憶功能。現代計算機系統中常採用寄存器、高速緩存、主存、外存的多級存儲體系結構。 ^[2] 

計算機存儲系統的核心是存儲器，存儲器是計算機中必不可少、用來存儲程序和數據的記憶設備。 ^[4] 

內部存儲器（簡稱內存）主要存儲計算機當前工作需要的程序和數據，包括高速緩衝存儲器（Cache，簡稱緩存）和主存儲器。目前構成內存的主要是半導體存儲器。外部存儲器（簡稱外存）主要有磁性存儲器、光存儲器和半導體存儲器三種實現方式，存儲介質有硬磁盤、光盤、磁帶和移動存儲器等。 ^[2] 

現代計算機系統多級存儲體系結構如圖6-1，其中越頂端的越靠近CPU，存儲器的速度越快、容量越小、每位的價格越高。採用這種組織方式能較好地解決存儲容量、速度和成本的矛盾，提供一個在價格、容量上邏輯等價於最便宜的那一層存儲器，而訪問速度接近於存儲系統中最快的那層存儲器。 ^[2] 

計算機的外部存儲系統如果從1956年IBM製造出第一塊硬盤算起，發展至今已經有半個多世紀了。在這半個多世紀裏，存儲介質和存儲系統都取得了很大的發展和進步。 ^[5] 

早期的數據存儲一般以磁盤陣列等設備為外設，圍繞服務器通過直連的方式進行存儲。而近年來，隨着網絡技術的發展，服務器的數據讀取範圍也得到了很大拓展，逐漸實現了現在的網絡存儲。相較於傳統存儲來説，網絡存儲的優勢更加突出，其不但安裝便捷、成本低廉，並且還能夠大規模的拓展存儲設備，從而有效滿足了海量數據存儲對存儲空間的需求。不過網絡存儲對網絡資源的消耗極大，這是一項難題，為此，後來又逐漸出現了SAN存儲架構。 ^[6] 

目前傳統存儲系統主要的3種架構，包括DAS、NAS和SAN。 ^[5] 

1.DAS（Direct-AttachedStorage，直連式存儲）

顧名思義，這是一種通過總線適配器直接將硬盤等存儲介質連接到主機上的存儲方式，在存儲設備和主機之間通常沒有任何網絡設備的參與。可以説DAS是最原始、最基本的存儲架構方式，在個人電腦、服務器上也最為常見。DAS的優勢在於架構簡單、成本低廉、讀寫效率高等；缺點是容量有限、難於共享，從而容易形成“信息孤島”。 ^[5] 

2.NAS（Network-AttachedStorage，網絡存儲系統）

NAS是一種提供文件級別訪問接口的網絡存儲系統，通常採用NFS、SMB/CIFS等網絡文件共享協議進行文件存取。NAS支持多客户端同時訪問，為服務器提供了大容量的集中式存儲，從而也方便了服務期間的數據共享。 ^[5] 

3.SAN（StorageAreaNetwork，存儲區域網絡）

通過光纖交換機等高速網絡設備在服務器和磁盤陣列等存儲設備間搭設專門的存儲網絡，從而提供高性能的存儲系統。 ^[5] 

SAN與NAS的區別，在於其提供塊（Block）級別的訪問接口，一般並不同時提供一個文件系統。通常情況下，服務器需要通過SCSI等訪問協議將SAN存儲映射為本地磁盤、在其上創建文件系統後進行使用。目前主流的企業級NAS或SAN存儲產品一般都可以提供TB級的存儲容量，高端的存儲產品也可以提供高達幾個PB的存儲容量。 ^[5] 

大數據導致了數據量的爆發式增長，傳統的集中式存儲（如NAS或SAN）在容量和性能上都無法較好地滿足大數據的需求。因此，具有優秀的可擴展能力的分佈式存儲成為大數據存儲的主流架構方式。分佈式存儲多采用普通的硬件設備作為基礎設施，因此，單位容量的存儲成本也得到大大降低。另外，分佈式存儲在性能、維護性和容災性等方面也具有不同程度的優勢。 ^[5] 

分佈式存儲系統需要解決的關鍵技術問題包括諸如可擴展性、數據冗餘、數據一致性、全局命名空間緩存等，從架構上來講，大體上可以將分佈式存儲分為C/S（Client Server）架構和P2P（Peer-to-Peer）架構兩種。當然，也有一些分佈式存儲中會同時存在這兩種架構方式。 ^[5] 

分佈式存儲面臨的另外一個共同問題，就是如何組織和管理成員結點，以及如何建立數據與結點之間的映射關係。成員結點的動態增加或者離開，在分佈式系統中基本上可以算是一種常態。 ^[5] 

EricBrewer於2000年提出的分佈式系統設計的CAP理論指出，一個分佈式系統不可能同時保證一致性、可用性和分區容忍性（Partitiontolerance）這3個要素。因此，任何一個分佈式存儲系統也只能根據其具體的業務特徵和具體需求，最大地優化其中的兩個要素。當然，除了一致性、可用性和分區容忍性這3個維度，一個分佈式存儲系統往往會根據具體業務的不同，在特性設計上有不同的取捨，比如，是否需要緩存模塊、是否支持通用的文件系統接口等。 ^[5] 

雲存儲是由第三方運營商提供的在線存儲系統，比如面向個人用户的在線網盤和麪向企業的文件、塊或對象存儲系統等。雲存儲的運營商負責數據中心的部署、運營和維護等工作，將數據存儲包裝成為服務的形式提供給客户。雲存儲作為雲計算的延伸和重要組件之一，提供了“按需分配、按量計費”的數據存儲服務。因此，雲存儲的用户不需要搭建自己的數據中心和基礎架構，也不需要關心底層存儲系統的管理和維護等工作，並可以根據其業務需求動態地擴大或減小其對存儲容量的需求。 ^[5] 

雲存儲通過運營商來集中、統一地部署和管理存儲系統，降低了數據存儲的成本，從而也降低了大數據行業的准入門檻，為中小型企業進軍大數據行業提供了可能性。比如，著名的在線文件存儲服務提供商Dropbox，就是基於AWS（AmazonWeb Services）提供的在線存儲系統S3創立起來的。在雲存儲興起之前，創辦類似於Dropbox這樣的初創公司幾乎不太可能。 ^[5] 

雲存儲背後使用的存儲系統其實多采用分佈式架構，而云存儲因其更多新的應用場景，在設計上也遇到了新的問題和需求。比如，雲存儲在管理系統和訪問接口上大都需要解決如何支持多租户的訪問方式，而多租户環境下就無可避免地要解決諸如安全、性能隔離等一系列問題。另外，雲存儲和雲計算一樣，都需要解決的一個共同難題就是關於信任（Trust）的問題——如何從技術上保證企業的業務數據放在第三方存儲服務提供平台上的隱私和安全，的確是一個必須解決的技術挑戰。 ^[5] 

將存儲作為服務的形式提供給用户，雲存儲在訪問接口上一般都會秉承簡潔易用的特性。比如，亞馬遜的S3存儲通過標準的HTTP協議、簡單的REST接口進行存取數據，用户分別通過Get、Put、Delete等HTTP方法進行數據塊的獲取、存放和刪除等操作。出於操作簡便方面的考慮，亞馬遜S3服務並不提供修改或者重命名等操作；同時，亞馬遜S3服務也並不提供複雜的數據目錄結構而僅僅提供非常簡單的層級關係；用户可以創建一個自己的數據桶（bucket），而所有的數據則直接存儲在這個bucket中。另外，雲存儲還要解決用户分享的問題。亞馬遜S3存儲中的數據直接通過唯一的URL進行訪問和標識，因此，只要其他用户經過授權便可以通過數據的URL進行訪問。 ^[5] 

存儲虛擬化是雲存儲的一個重要技術基礎，是通過抽象和封裝底層存儲系統的物理特性，將多個互相隔離的存儲系統統一化為一個抽象的資源池的技術。通過存儲虛擬化技術，雲存儲可以實現很多新的特性。比如，用户數據在邏輯上的隔離、存儲空間的精簡配置等。 ^[5] 

存儲系統的層次化結構可以分為5級:寄存器組、高速緩存Cache、主存、虛擬存儲器和外部存儲器。其中，寄存器組總是在CPU內部，程序員可通過寄存器名訪問，無總線操作，訪問速度最快；其餘4級均在CPU外部，Cache和主存構成內存儲系統，程序員通過總線尋址訪問存儲單元，訪問速度較寄存器差；虛擬存儲器對程序員而言是透明的 ；外部存儲系統容量大，需通過I/O接口與CPU交換數據，訪問速度最慢。 ^[7] 

高速緩衝存儲器（Cache）的原始意義是指存取速度比一般隨機存取存儲器（RAM）更快的一種RAM，一般而言，它不像系統主存那樣使用動態隨機存儲器（DRAM）技術，而是使用昂貴但較快速的靜態隨機存儲器（SRAM）技術。 ^[1] 

高速緩衝存儲器是介於主存與CPU之間的一級存儲器，由靜態存儲芯片（SRAM）組成，容量較小但速度比主存快得多，其最重要的指標是它的命中率。高速緩衝存儲器與主存儲器之間信息的調度和傳送是由硬件自動進行的。 ^[1] 

高速緩衝存儲器主要由以下三大部分組成： ^[1] 

高速緩衝存儲器通常由高速存儲器、聯想存儲器、置換邏輯電路和相應的控制線路組成。在有高速緩衝存儲器的計算機系統中，處理器存取主存儲器的地址劃分為行號、列號和組內地址三個字段。於是，主存儲器就在邏輯上劃分為若干行：每行劃分為若干的存儲單元組；每組包含幾個或幾十個字。高速存儲器也相應地劃分為行和列的存儲單元組。二者的列數相同，組的大小也相同，但高速存儲器的行數卻比主存儲器的行數少得多。 ^[1] 

聯想存儲器用於地址聯想，有與高速存儲器相同行數和列數的存儲單元。當主存儲器某一列某一行存儲單元組調入高速存儲器同一列某一空着的存儲單元組時，與聯想存儲器對應位置的存儲單元就記錄調入的存儲單元組在主存儲器中的行號。 ^[1] 

當處理器存取主存儲器時，硬件首先自動對存取地址的列號字段進行譯碼，以便將聯想存儲器該列的全部行號與存取主存儲器地址的行號字段進行比較。若有相同的，表明要存取的主存儲器單元已在高速存儲器中，稱為命中，硬件就將存取主存儲器的地址映射為高速存儲器的地址並執行存取操作；若都不相同，則表明該單元不在高速存儲器中，稱為失效，硬件將執行存取主存儲器操作並自動將該單元所在的那一主存儲器單元組調入高速存儲器相同列中空着的存儲單元組中，同時將該組在主存儲器中的行號存入聯想存儲器對應位置的單元內。 ^[1] 

當出現失效而高速存儲器對應列中沒有空的位置時，便淘汰該列中的某一組以騰出位置存放新調入的組，這稱為置換。確定替換的規則稱為置換算法，常用的置換算法有最近最久未使用算法（LRU）、先進先出法（FIFO）和隨機法（RAND）等。置換邏輯電路就是執行這個功能的。另外，當執行寫主存儲器操作時，為保持主存儲器和高速存儲器內容的一致性，對命中和失效分別進行處理。 ^[1] 

地址映像是指某一數據在主存中的地址與在緩存中的地址兩者之間的對應關係。下面介紹三種地址映像方式： ^[1] 

1.全相聯方式

全相聯方式的地址映像規則是：主存儲器中的任意一塊可以映像到Cache中的任意一塊。其基本實現思路是：1）主存與緩存分成相同大小的數據塊；2）主存的某一數據塊可以裝入緩存的任意一塊空間中。 ^[1] 

目錄表存放在聯想存儲器中，包括三個部分：數據塊在主存的塊地址、存入緩存後的塊地址及有效位（也稱裝入位）。由於是全相聯方式，因此目錄表的容量應當與緩存的塊數相同。 ^[1] 

全相聯方式的優點是命中率比較高，Cache存儲空間利用空間率高；缺點是訪問相關存儲器時，每次都要與全部內容比較，速度低且成本高，因而應用少。 ^[1] 

2.直接相聯方式

直接相聯方式的地址映像規則是主存儲器中某一塊只能映像到Cache的一個特定的塊中。其基本實現思路是： ^[1] 

1）主存與緩存分成相同大小的數據塊； ^[1] 

2）主存容量應是緩存容量的整數倍，將主存空間按緩存的容量分成區，主存中每一區的塊數與緩存的總塊數相等； ^[1] 

3）主存中某區的一塊存入緩存時只能存入緩存中塊號相同的位置。 ^[1] 

主存中各區內相同塊號的數據塊都可以分別調入緩存中塊號相同的地址中，但同時只能有一個區的塊存入緩存。由於主、緩存的塊號及塊內地址兩個字段完全相同，因此，目錄登記時，只記錄調入塊的區號即可。目錄表存放在高速小容量存儲器中，包括兩個字段：數據塊在主存的區號和有效位。目錄表的容量與緩存的塊數相同。 ^[1] 

直接相聯方式的優點是地址映像方式簡單，數據訪問時，只需檢查區號是否相等即可，因而可以得到比較快的訪問速度，且硬件設備簡單；缺點是置換操作頻繁，命中率比較低。 ^[1] 

3.組相聯映像方式

組相聯映像方式的地址映像規則是主存儲器中某一塊只能存入緩存的同組號的任一塊中。其基本實現思路是： ^[1] 

1）主存和緩存按同樣大小劃分成塊； ^[1] 

2）主存和緩存按同樣大小劃分成組： ^[1] 

3）主存容量是緩存容量的整數倍，將主存空間按緩存區的大小分成區，主存中每一區的組數與緩存的組數相同; ^[1] 

4）當主存的數據調入緩存時，主存與緩存的組號應相等，也就是各區中的某一塊只能存入緩存的同組號的空間內，但組內各塊之間可任意存放，即從主存的組到緩存的組之間採用直接映像方式：在兩個對應的組內部採用全相聯映像方式。 ^[1] 

主存地址與緩存地址的轉換由兩部分構成：組地址採用的是直接映像方式，按地址進行訪問；而塊地址採用的是全相聯方式，按內容訪問。 ^[1] 

組相聯映像方式的優點是塊的衝突概率比較低，塊的利用率大幅度提高，塊的失效率明顯降低：而缺點是實現難度和造價要比直接映像方式高。 ^[1] 

內存（Memory)）又被稱為內存儲器或主存儲器，由半導體器件製成，是計算機的重要部件之一，是CPU能直接尋址的存儲空間， 其特點是存取速率快。計算機中所有程序的運行都是在內存中進行的， 因此內存的性能對計算機的影響非常大。內存的作用是暫時存放CPU中的運算數據以及與硬盤等外部存儲器交換的數據。只要計算機在運行中， CPU就會把需要運算的數據調到內存中進行運算， 當運算完成後CPU再將結果傳送出來。 ^[1] 

我們平常使用的程序， 如Windows操作系統、打字軟件、遊戲軟件等， 一般都是安裝在硬盤等外存上的，但僅此是不能使用其功能的，必須把它們調入內存中運行，才能真正使用其功能，我們平時輸入一段文字，或玩一個遊戲，其實都是在內存中進行的。就好比在一個書房裏，存放書籍的書架和書櫃相當於電腦的外存，而我們工作的辦公桌就是內存。通常我們把要永久保存的、大量的數據存儲在外存上，而把一些臨時的或少量的數據和程序放在內存中，當然，內存的性能會直接影響電腦的運行速度。 ^[1] 

內存包括只讀存儲器（ROM）和隨機存儲器（RAM）兩類。 ^[1] 

只讀存儲器即ROM（ReadOnly Memory)）。在製造ROM的時候，信息（數據或程序）就被存入並永久保存。這些信息只能讀出，不能寫入，即使機器停電，數據也不會丟失。ROM一般用於存放計算機的基本程序和數據， 如BIOS ROM。其物理外形一般是雙列直插式（DIP）的集成塊。 ^[1] 

隨機存儲器即RAM（Random Access Memory） ， 表示既可以從中讀取數據， 也可以寫入數據。當機器電源關閉時， 存於其中的數據就會丟失。我們通常購買或升級的內存條（SIMM）就是用作電腦的內存， 它是將RAM集成塊集中在一起的一小塊電路板， 插在計算機中的內存插槽上， 以減少RAM集成塊佔用的空間。 ^[1] 

最後介紹物理存儲器和存儲地址空間這兩個概念。它們是兩個不同的概念，但因為兩者間有十分密切的關係，且都使用B、KB、MB及GB來度量其容量大小，因此容易產生認識上的混淆。物理存儲器是指實際存在的具體存儲器芯片。如主板上裝插的內存條和裝載有系統的BIOS的ROM芯片， 顯示卡上的顯示RAM芯片和裝載顯示BIOS的ROM芯片， 以及各種適配卡上的RAM芯片和ROM芯片都是物理存儲器。存儲地址空間是指對存儲器編碼（編碼地址）的範圍。所謂編碼，就是對每一個物理存儲單元（一個字節）分配一個號碼，通常叫作“編址”。分配一個號碼給一個存儲單元的目的是為了便於找到它，完成數據的讀寫，這就是所謂的“尋址”，因此有人也把存儲地址空間稱為尋址空間。 ^[1] 

存儲地址空間的大小和物理存儲器的大小並不一定相等。舉個例子來説明這個問題：某層樓共有17個房間，其編號為801~817。這17個房間是物理的，而其地址空間採用了三位編碼，其範圍是800~899共100個地址，可見地址空間是大於實際房間數量的。對於386以上檔次的微機，其地址總線為32位，因此地址空間可達2B，即4GB。 ^[1] 

近年來出現的非易失性存儲（Non-Volatile memory，NVM）以其高集成度、低能耗、非易失性、字節尋址等特性得到了廣泛關注。學術界和工業界已經開發了一些新型非易失存儲介質和技術， 例如磁存儲器（Magnetic RAM，MRAM） 、自旋磁存儲器（Spin Transfer TorqueRAM，STT-RAM）、相變存儲器（Phase Change Memory， PCM） 、阻變存儲器（Resistive RAM，RRAM）、鐵電存儲器（Ferroelectric RAM， FeRAM）等。表中列舉了幾種主流新型存儲器件的主要參數，從表中可以看出，非易失性存儲在集成度、讀速度方面具有較好的表現，是構建潛在新型存儲器件的候選對象。但是非易失性存儲也有幾個明顯的缺點：1）具有較大的寫延時，其寫延時比相應的存儲介質大1個數量級，並且寫延時大於讀延時，即讀寫不一致；2）雖然非易失性存儲的讀操作比寫操作快，但是仍然比傳統存儲介質的讀操作慢；3）非易失性存儲的寫壽命有限，在連續寫的情況下，存儲單元很快會失效。 ^[1] 

磁盤是最常用的外部存儲器，它是將圓形的磁性盤片裝在一個方型的密封盒子裏，這樣做的目的是為了防止磁盤表面劃傷，導致數據丟失。存放在磁盤上的數據信息可長期保存且可以反覆使用。磁盤有軟磁盤和硬磁盤之分，當前軟磁盤已經基本被淘汰了，計算機廣泛使用的是硬磁盤，我們可以把它比喻成是電腦儲存數據和信息的大倉庫。 ^[1] 

硬磁盤的種類主要包括SCSI、IDE以及現在流行的SATA等。任何一種硬磁盤的生產都有一定的標準，隨着相應標準的升級，硬磁盤生產技術也在升級， 比如SCSI標準已經經歷了SCSI-1、SCSI-2及SCSI-3，而目前我們經常在網站服務器看到的Ultra l-160就是基於SCSI-3標準的。IDE遵循的是ATA標準， 而目前流行的SATA，是ATA標準的升級版本。IDE是並口設備， 而SATA是串口， SATA的發展是為了替換IDE。 ^[1] 

一般説來，無論是哪種硬磁盤，都是由盤片、磁頭、盤片主軸、控制電機、磁頭控制器、數據轉換器、接口、緩存等組成。 ^[1] 

硬磁盤結構如圖2-6所示。所有的盤片都固定在一個旋轉軸上，這個軸即盤片主軸。而所有盤片之間是絕對平行的，在每個盤片的存儲面上都有一個磁頭，磁頭與盤片之間的距離比頭髮絲的直徑還小。所有的磁頭連在一個磁頭控制器上，由磁頭控制器負責各個磁頭的運動。磁頭可沿盤片的半徑方向作徑向移動（實際是斜切向運動），每個磁頭同一時刻也必須是同軸的，即從正上方向下看，所有磁頭任何時候都是重疊的（不過目前已經有多磁頭獨立技術，可不受此限制）。而盤片以數千轉每分鐘到上萬轉每分鐘的速度高速旋轉，這樣磁頭就能對盤片上的指定位置進行數據的讀寫操作。 ^[1] 

1.盤面

硬磁盤的盤片一般用鋁合金材料做基片，高速硬磁盤也可能用玻璃做基片。硬磁盤的每一個盤片都有兩個盤面（Side）， 即上、下盤面， 一般每個盤面都會利用， 都可以存儲數據，成為有效盤面，也有極個別的硬磁盤盤面數為單數。每一個這樣的有效盤面都有一個盤面號，按順序從上至下、從0開始依次編號。在硬磁盤系統中，盤面號又叫磁頭號，因為每一個有效盤面都有一個對應的讀寫磁頭。硬磁盤的盤片組的盤片有2~14片不等，通常有2~3個盤片，故盤面號（磁頭號）為0~3或0~5。 ^[1] 

2.磁道

磁盤在低級格式化時被劃分成許多同心圓， 這些同心圓軌跡叫做磁道（Track） ， 信息以脈衝串的形式記錄在這些軌跡中。磁道由外向內、從0開始順序編號。硬磁盤的每一個盤面有300~1024個磁道，新式大容量硬磁盤每面的磁道數更多。每條磁道並不是連續記錄數據，而是被劃分成一段段的圓弧，這些圓弧的角速度一樣，但由於徑向長度不一樣，所以線速度也不一樣，外圈的線速度較內圈的線速度大，即同樣的轉速下，外圈在同樣時間段裏，劃過的圓弧長度要比內圈劃過的圓弧長度大。每段圓弧叫做一個扇區，扇區從1開始編號，每個扇區中的數據作為一個單元同時讀出或寫入。磁道是看不見的，只是盤面上以特殊形式磁化了的一些磁化區，在磁盤格式化時就已規劃完畢。 ^[1] 

3.柱面

所有盤面上的同一磁道構成一個圓柱， 通常稱作柱面（Cylinder），每個圓柱上的磁頭由上而下、從0開始編號。數據的讀/寫按柱面進行，即磁頭讀/寫數據時首先在同一柱面內從0磁頭開始進行操作，依次向下在同一柱面的不同盤面即磁頭上進行操作，只有在同一柱面所有的磁頭全部讀/寫完畢後，磁頭才轉移到下一柱面（同心圓的再往裏的柱面），因為選取磁頭只需通過電子切換即可，而選取柱面則必須通過機械切換，電子切換時磁頭向鄰近磁道移動的速度比機械切換時快得多，因此數據的讀/寫按柱面進行，而不按盤面進行，從而提高硬磁盤的讀/寫效率。 ^[1] 

一塊硬磁盤驅動器的柱面數（或每個盤面的磁道數）既取決於每條磁道的寬窄（同樣，也與磁頭的大小有關），也取決於定位機構所決定的磁道間步距的大小。 ^[1] 

4.扇區

操作系統以扇區（Sector）形式將信息存儲在硬磁盤上，每個扇區包括兩個主要部分：扇區標識符和存儲數據的數據段（通常為512B）。 ^[1] 

扇區標識符，又稱為扇區頭標，包括組成扇區三維地址的三個數字：1）盤面號：扇區所在的磁頭（或盤面）2）柱面號：磁道，確定磁頭的徑向方向：3）扇區號：在磁道上的位置，也叫塊號，確定了數據在盤片圓圈上的位置。 ^[1] 

扇區頭標中還包括一個字段，其中有一個標識扇區是否能可靠存儲數據的標記。有些硬磁盤控制器在扇區頭標中還記錄有指示字，可在原扇區出錯時指引磁盤轉到替換扇區或磁道。最後， 扇區頭標以循環冗餘校驗（CRC）值作為結束， 以供控制器檢驗扇區頭標的讀出情況，確保準確無誤。 ^[1] 

扇區的數據段用於存儲數據信息， 包括數據和保護數據的糾錯碼（ECC）。在初始準備期間， 計算機將512個虛擬信息字節（實際數據的存放位置）和與這些虛擬信息字節相應的ECC數字填入這個部分。 ^[1] 

堆棧是C語言程序運行時的一個記錄調用路徑和參數的空間：包括函數調用框架、傳遞參數、保存返回地址及提供局部變量空間。 ^[1] 

1.堆棧相關寄存器

1）esp：堆棧棧頂指針； ^[1] 

2）ebp：基址指針（ebp在C語言中用作記錄當前函數調用基址）； ^[1] 

3）cs:eip指向下一條指令的地址，分兩種情況； ^[1] 

（1）順序執行：總是指向地址連續的下一條指令； ^[1] 

（2）跳轉/分支：執行這樣的指令的時候，cs:eip的值會根據程序需要被修改； ^[1] 

4)call：將當前cs:eip的值壓入棧頂，cs:eip指向被調用函數的入口地址； ^[1] 

5) ret：從棧頂彈出原來保存在這裏的cs:eip的值， 放入cs:eip中； ^[1] 

6)iret：從棧頂彈出原來保存在這裏的cs:eip及flags的值，放入cs:eip及標誌寄存器中。 ^[1] 

2.堆棧操作

1） push：棧頂指針減少4個字節（32位）： ^[1] 

2）pop：棧頂指針增加4個字節（32位）。 ^[1] 

函數調用過程中對堆棧的操作情況如圖3所示，一個主函數調用了一個子函數，調用過程的具體步驟描述如下： ^[1] 

所謂局部性原理， 是指CPU訪問存儲器時， 無論是存取指令還是存取數據， 所訪問的存儲單元都聚集在一個較小的連續區域中。 ^[1] 

局部性通常有兩種形式： ^[1] 

時間局部性（temporal locality）：如果一個信息項正在被訪問， 那麼在近期它很可能還會被再次訪問。程序循環、堆棧等是產生時間局部性的原因。 ^[1] 

空間局部性（spatial locality）：在最近將要用到的信息很可能與現在正在使用的信息在空間地址上是臨近的。 ^[1] 

現代計算機系統的各個層次，從硬件到操作系統，再到應用程序，它們的設計都利用了局部性原理。在硬件層，局部性原理允許計算機設計者通過引入小而快速的高速緩衝存儲器來保存最近被引用的指令和數據項，從而提高對主存的訪問速度。在操作系統級，局部性原理允許系統使用主存作為虛擬地址空間最近被引用的高速緩存，局部性原理也允許系統利用主存來緩存磁盤文件系統中最近被使用的磁盤塊等。局部性原理在應用程序的設計中也扮演着重要的角色， 例如， Web瀏覽器將最近被引用的文檔放在本地磁盤上， 利用的就是時間局部性。大量的Web服務器將最近被請求的文檔放在前端磁盤高速緩存中， 這些緩存能滿足用户對這些文檔的請求，而不需要服務器的任何干涉。 ^[1] 

下面用三個例子來説明程序對數據引用的局部性。 ^[1] 

例1：

int sumvec(int v[N])

{

int i=0，sum=0;

for(int i=0; i

{

sum+=v[i];

}

return sum;

}

上述代碼中，變量sum在每次循環迭代中被引用一次，具有時間局部性。對於數組v的元素，按照它們存儲在存儲器中的順序，被依次讀取，因此具有空間局部性，但是每個數組元素只被訪問一次， 所以不具有時間局部性。可見， sumvec函數對數據的訪問既有空間局部性，也有時間局部性。 ^[1] 

例2：

int sumarrayros(int v[M][N])

{

int i=0;j=0;sum=0;

for(i=0;i

for(j=0;j

{

sum+=v[i] [j]；

}

return sum;

}

上述代碼中，數組v的元素都是按照步長1來訪問的，因此具有很好的空間局部性（數組元素是按照行順序存儲的）。 ^[1] 

例3：

int sum array ros(int v[M][N])

{

inti=0;j=0;sum=0;

for(j=0;j

for(i=0;i

{

sum+=v[i][j];

}

return sum;

}

上述代碼中，數組v的元素都是按照步長N來訪問的，因此其空間局部性很差。 ^[1]  綜上，可以得到如下結論：

1)重複引用同一個變量的程序有良好的時間局部性； ^[1] 

2)對於具有步長為k的引用模式的程序，步長越小，空間局部性越好。在存儲器中以大步長跳來跳去的程序，空間局部性會很差； ^[1] 

3)對於取指令來説，循環有好的時間和空間局部性。循環體越小，循環迭代次數越多，局部性越好。 ^[1]