存儲分配程式和編碼

存儲分配程式和編碼

存儲分配程式和編碼是兩個不同概念。存儲分配程式是指計算機系統中依照一定的算法實現記憶體分配的程式,主要是為了解決多道作業之間劃分主存空間的問題。編碼是信息從一種形式或格式轉換為另一種形式的過程。常見的編碼有字元編碼、文字編碼等。

存儲分配程式

存儲分配程式是指計算機系統中依照一定的算法實現記憶體分配的程式。主要是為了解決記憶體分配問題。一般分為直接方式、靜態分配、動態分配。

直接方式

直接方式是早期的計算機所使用的一種方式。當時多道程式技術還沒出現,存儲器的可用空間一般是給定的。那時程式設計師在編程式時或編譯程式對源程式進行編譯時,使用實際的存儲器地址,這種分配方式使用戶與計算機記憶體直接打交道;系統資源在某一時刻為一個用戶所獨占。當多道程式出現時就使用戶感到極不方便,因為用戶要自己做主存的分配工作,而且記憶體不止存放一個作業,這要求用戶必須知道每一個作業放在主存的什麼地方,這無疑增加了用戶的負擔,況且存儲空間的利用率也相當低 。

動態分配

所謂動態分配(Dynamic Memory Allocation)就是指在程式執行的過程中動態地分配或者回收存儲空間的分配記憶體的方法。動態記憶體分配不象數組等靜態記憶體分配方法那樣需要預先分配存儲空間,而是由系統根據程式的需要即時分配,且分配的大小就是程式要求的大小。分配過程包括尋找一塊足夠大未被使用的記憶體。分配過程當中的問題,內部和外部碎片。減少碎片需要特別處理,從而導致更複雜的實現。分配器的元數據需要占用額外的空間。嘗試組塊來減輕這個效應。

通常,記憶體是從一個被稱為堆的記憶體池中分配出來的。高級語言封裝了記憶體地址的概念,記憶體通常是通過指針來間接訪問的。分配算法經常將組織分配釋放組塊等操作封裝成抽象的接口供上層函式調用。

靜態分配

所謂的靜態分配,即在編譯期間為數據對象分配存儲空間。這要求在編譯期間就可以確定數據對象的大小,同時還可以確定數據對象的數目。

現狀

多數(現代)語言只實施部分靜態存儲分配。可靜態分配的數據對象包括大小固定且在程式執行期間可全稱訪問的全局變數、靜態變數、程式中的常量以及class的虛函式表等,如C語言中的static和extern變數,以及C++中的static變數,這些數據對象的存儲將被分配在靜態數據區。

常見做法

從道理上講,或許可以將靜態數據對象與某個絕對存儲地址綁定,然而,通常的做法是將靜態數據對象的存取地址對應到偶對(DataArerStart,Offset)。Offset是在編譯時刻確定的固定偏移量,而DataArerStart則可以推遲到連結或運行時刻才確定。有時,DataArerStart的地址也可以裝入某個基地址暫存器Register,此時數據對象的存取地址對應到偶對(DataArerStart,Offset),即所謂的暫存器偏址定址方式。

優點

採用這種方式,存儲分配極其簡單。

缺點

(1)採用這種方式會帶來存儲空間的浪費。為解決存儲空間浪費問題,人們設計了變數的重疊布局機制,如FORTRAN語言的equivalence語句。重疊布局帶來的問題是使得程式難寫難讀。

(2)完全靜態分配的語言還有另外一個缺陷,就是無法支持遞歸過程或函式。

(3)對於一些動態的數據結構,例如動態數據(C++中使用new關鍵字來分配記憶體)以及遞歸函式的局部變數等最終空間大小必須在運行時才能確定的場合,靜態存儲分配就無能為力了。

分配算法

最佳適應算法

最佳適應算法,即選擇空間浪費最少的存儲塊 。

最先適應算法

最先適應算法,即選擇最先找到的足夠大的存儲塊。

循環最先適應算法

循環最先適應算法,,即起始點不同的最先適應算法。

哈希算法

哈希算法就是利用哈希快速查找的優點,以及空閒分區在可利用空間表中的分布規律,建立哈希函式,構造一張以空閒分區大小為關鍵字的哈希表,該表的每一個表項記錄了一個對應的空閒分區鍊表表頭指針。當進行空閒分區分配時,根據所需空閒分區大小,通過哈希函式計算,即得到在哈希表中的位置,從中得到相應的空閒分區鍊表,實現最佳分配策略。

編碼

用規定的一組代碼表示電腦程式的指令或信息的過程,即為計算機編寫程式。用一組明確的規則表示某種信息,使得以後能進行解碼,這種過程亦稱為編碼。

在電子計算機上,對指令及數據編碼後,就可以進行操作或運算。

有時,編碼與代碼同義。在通訊中,表示信息組成、傳送、接受及處理的一組規則與約定,稱為編碼或代碼;為執行一個程式或解一個問題,把所要進行的操作步驟,按順序用計算機代碼編成的表,也稱為編碼 。

常見編碼

字元編碼(Character encoding)是一套法則,使用該法則能夠對自然語言的字元的一個集合(如字母表或音節表),與其他東西的一個集合(如號碼或電脈衝)進行配對。

文字編碼(Text encoding)使用一種標記語言來標記一篇文字的結構和其他特徵,以方便計算機進行處理。

語義編碼(Semantics encoding),以正式語言乙對正式語言甲進行語義編碼,即是使用語言乙表達語言甲所有的辭彙(如程式或說明)的一種方法。

電子編碼(Electronic encoding)是將一個信號轉換成為一個代碼,這種代碼是被最佳化過的以利於傳輸或存儲。轉換工作通常由一個編解碼器完成。

神經編碼(Neural encoding)是指信息在神經元中被如何描繪的方法。

記憶編碼(Memory encoding)是把感覺轉換成記憶的過程。

相關詞條

熱門詞條

聯絡我們