雙向數據儲存方法
2023-05-08 14:47:31 2
專利名稱：：雙向數據儲存方法
技術領域：
：本發明涉及一種儲存數據的方法，特別涉及一種可由一內存區塊的兩端進行雙向數據儲存的方法。
背景技術：
：一般而言，業界常用的儲存方法可大致分為三種有序儲存法、非有序儲存法以及雜湊(hash)儲存法。有序儲存法的特點是每一筆寫入的數據都以有序排列的方式儲存在內存中，亦即每寫入一筆數據時，系統就必須進行一次排序的動作使內存中的所有數據皆依照順序排列。非有序儲存法則是依據儲存的先後順序將欲儲存的數據一一寫入內存中，因此，相較於有序儲存法，非有序儲存法則可省略每寫入一筆數據就要進行排序的動作，然而，由於內存中所儲存的每一筆數據的排列方式不具有任何規則，因此系統必須另提供一映像表(mappingtable)來記錄每一筆數據的起始地址以及大小，以使後續讀取數據時不用在內存中逐項搜尋，而是直接從映像表中讀取該筆數據的位置來進行存取。對於雜湊儲存法而言，其是利用一雜湊函數(hashfunction)對每一筆數據進行演算，其中演算產生的值會對應到一預定存儲地址，因此不論是寫入或是存取時，系統只需依據上述雜湊函數運算出該筆數據所對應的值便可以找到相對應的存儲地址。？然而，當上述三種儲存方法應用於具有較小內存的系統時，便各自有其限制，以手機系統來說，由於手機系統通常內存較小，所以當使用上述雜湊儲存法時，如果雜湊函數的選擇不當，則可能造成內存浪費的情形。相較於雜湊儲存法，雖然有序儲存法可以有效利用所有的內存，但是由於每寫入一筆數據都需進行排序的工作，對於運算功能不強的手機系統而言也是一大負擔。如此一來，對手機系統而言非有序儲存法似乎是一較為折衷的選擇，雖然非有序儲存法是將多筆儲存數據依據寫入的先後順序儲存在內存中，但是時間一久，不論使用上述任何一種儲存方法內存中被釋放(released)的存儲空間將會以不連續的方式存在該內存中而無法被重複使用，因此必須每隔一段時間便對該內存進行重整，亦即，讓上述不連續的存儲空間與內存中的剩餘空間合併在一起，以便重新分配給其它的儲存數據使用。請參閱圖1，圖1是為應用現有非有序儲存方式的內存區塊10的示意圖。如圖中所示，內存區塊10此時是包含多個存放有儲存數據D1、D3、D5、D8、D9、D10的存儲空間12、16、22、28、32、34，多個被釋放的存儲空間(斜線部分)14、18、24、26，以及一塊未曾使用的存儲空間36。這是因為當接收到第一筆儲存數據D1時，內存區塊10會沿著箭頭方向20分配存儲空間12來寫入儲存數據D1，然後再分配存儲空間14給第二筆寫入的儲存數據D2，同理，多筆儲存數據D3-D10會不斷依序地寫入內存區塊10，最後，內存區塊10便分配存儲空間34給第10筆寫入的儲存數據D10。之後，由於某些儲存數據(例如儲存數據D2、D4、D6、D7)可能已經不再被系統所使用，因此系統便會釋放那些不再使用的儲存數據D2、D4、D6、D7所在的存儲空間(斜線部分)14、18、24、26，由於剩餘空間36與儲存空間14、18、24、26此時皆可分配給其它儲存數據，所以系統可以對內存區塊10進行重整，使得存儲空間14、18、24、26集中在內存區塊10的左側，亦即與存儲空間36合併後，才能更有效率的分配內存空間給其它儲存數據來使用。由於上述重整的動作必須反覆執行且每一次執行都會耗費大量運算時間，不僅大幅提升系統的運算量，也會讓使用者產生反應遲緩的感覺，因此，如何有效利用存儲空間同時降低內存重整的運算量即為本發明的主要課題。
發明內容因此，本發明的主要目的之一在於提供一種雙向數據儲存方法，以解決上述內存重整時間過長的問題。依據本發明，其是揭露一種應用於一儲存裝置的雙向數據儲存方法。該儲存裝置包含有多個內存區塊。該雙向數據儲存方法包含有接收一儲存數據；自一目標內存區塊的一第一儲存方向與一第二儲存方向中選擇一儲存方向；以及依據該儲存方向將該儲存數據寫入該目標內存區塊。本發明的數據儲存方法是選擇性地自一內存區塊的兩端起寫入儲存數據，使得需進行重整的數據大小最多可縮減為一半，以大幅降低內存重整所需的時間。圖1為應用現有非有序儲存方式的內存區塊的示意圖。圖2為本發明雙向數據儲存方法的一實施例的流程圖。圖3為本發明雙向數據儲存方法應用於一儲存裝置的示意圖。圖4為本發明雙向數據儲存方法所使用的映像表的示意圖。圖5為圖2中選擇目標內存區塊的步驟的流程圖。圖6為本發明雙向數據儲存方法應用於另一儲存裝置的示意圖。圖7為本發明雙向數據儲存方法重整圖6所示的儲存裝置的示意圖。附圖符號說明具體實施方式請參閱圖2，圖2是本發明雙向數據儲存方法的一實施例的流程圖。本發明雙向數據儲存方法可應用於內存資源較為有限的系統，例如移動通訊裝置。如圖中所示，本實施例中，雙向數據儲存方法的操作包含有下列步驟步驟110開始；步驟112接收一儲存數據；步驟114自多個內存區塊中選擇一目標內存區塊來寫入該儲存數據；步驟116判斷該目標內存區塊的第一儲存方向所寫入的數據總量是否大於第二儲存方向所寫入的數據總量，若「否」，則繼續步驟122，否則，執行步驟124；步驟122依據該第一儲存方向來寫入該儲存數據；步驟124依據該第二儲存方向來寫入該儲存數據；步驟126將寫入地址紀錄在一映像表中，並且紀錄寫入方向的數據總量；以及步驟128結束。本實施例中，判斷第一儲存方向上所寫入發數據總量與第二儲存方向上所寫入發數據總量的方法的利用一第一指針來記錄在第一儲存方向上的數據總量，以及利用一第二指針來記錄在第二儲存方向上的數據總量，其詳細的判斷方式將在下文中詳細說明。請參閱圖3，圖3的本發明雙向數據儲存方法應用於一儲存裝置140的示意圖。本實施例中，儲存裝置140包含有多個儲存容量為150位(bit)的內存區塊(block)160a-160n，因此，若內存區塊160a的起始地址為k，則其末端地址便為k+149。如圖所示，存儲空間162是用來記載大小為30位的儲存數據Da1，存儲空間164是用來記載大小為45位的儲存數據Da2，並且儲存數據Da1與儲存數據Da2是分別依據儲存方向RD1以及儲存方向RD2寫入內存區塊160a。除此之外，對於內存區塊160a而言，一指標ptr1是用來指示儲存方向RD1所寫入的數據總量，以及一指標ptr2是用來指示儲存方向RD2所寫入的數據總量，因此，當儲存數據Da1、Da2寫入內存區塊160a後，指標ptr1所指向的地址便會是k+30，而指標ptr2所指向的地址是為k+149-45。請同時參閱圖2與圖3，當系統另接收一筆大小為20個位的儲存數據Da3時，系統會先選擇一目標存儲區塊，在本實施例中，假設內存區塊160a即為所選取的目標存儲區塊，至於選擇目標存儲區塊的機制將在下文中詳述。接著，系統會利用指針ptr1、ptr2來判斷儲存方向RD1的數據總量是否大於儲存方向RD2的數據總量。在本實施例中由於儲存方向RD1的數據總量是小於儲存方向RD2的數據總量，由於計算數據總量的方法是將指針地址減去相對應儲存方向所對應的起始地址，因此可知儲存方向RD1的數據總量是小於儲存方向RD2的數據總量，所以系統會將儲存數據Da3依據儲存方向RD1寫入內存區塊160a，最後，在儲存數據Da3附加在儲存數據Da1後，對應儲存方向RD1的指針ptrl便指向地址k+50，並且儲存數據Da3的起始地址會被紀錄在一映像表中。請參閱圖4，圖4為本發明雙向數據儲存方法所使用的映像表180的示意圖。由圖4可知，當儲存數據Da1、Da2、Da3依序記錄在內存區塊160a後，映像表180便會紀錄每一儲存數據Da1、Da2、Da3的起始地址與大小，其中若一儲存數據Da2稍後不再被使用，亦即，系統需釋放不再使用的儲存數據Da2的存儲空間164，則有關儲存數據Da2便會自映像表180刪除。請參閱圖5，圖5是圖2所示的步驟114的細部流程圖。如圖中所示，選擇目標內存區塊的操作包含有下列步驟步驟202開始；步驟204計算目前所有內存區塊的剩餘空間大小；步驟206是否有至少一個內存區塊的剩餘空間可容納欲記錄的儲存數據，若「是」，則執行步驟208，否則，執行步驟210；步驟208自多個可容納該儲存數據的內存區塊中選擇一具有最小剩餘空間的內存區塊來作為一目標內存區塊；步驟210計算多個內存區塊的破碎度(fragmentation)；步驟212選擇一具有最大破碎度的內存區塊來作為一待重整內存區塊，並且計算該待重整內存區塊在第一、第二儲存方向所寫入的多筆儲存數據所對應的破碎度；以及步驟214選擇破碎度較大的儲存方向進行重整(defragment)，並且回到步驟204。本實施例中，破碎度的計算是依據一映像表(例如圖4所示的映像表180)中每一筆儲存數據的起始位置與大小來判斷一內存區塊是否具有許多不連續的閒置存儲空間，亦即，若不連續的閒置存儲空間的數量越大，則該內存區塊的破碎度便越大。選擇目標內存區塊的詳細操作以一例子說明如下。請參閱圖6，圖6為本發明雙向數據儲存方法應用於另一儲存裝置300的示意圖。如圖中所示，本實施例中，儲存裝置300包含有三個儲存容量均為150個位的內存區塊320、340、360，因此，假設內存區塊320的地址是從m到m+149，則內存區塊340的地址便從m+150到m+299，以及內存區塊360的地址是從m+300到m+449，此外，假設內存區塊320在儲存方向RD1、RD2上的指標ptr1、ptr2此時是分別指向地址m+60以及m+79，內存區塊340在儲存方向RD1、RD2上的指標ptr3、ptr4此時是分別指向地址m+225以及m+229，以及內存區塊360在儲存方向RD1、RD2上的指標ptr5、ptr6此時是分別指向地址m+330以及m+419。此外，圖中所示的斜線部分是表示先前曾經被配置而目前已被釋放(released)的存儲空間，雖然該存儲空間中的數據已經不會再被利用，但是由於這些存儲空間零星的散布在內存區塊中，所以可能也無法具有足夠的容量以配置給新的儲存數據來使用。如圖6所示，內存區塊320目前是紀錄儲存數據B3、B4、B5，內存區塊340目前是紀錄儲存數據B6、B7、B8、B10，以及內存區塊360目前是紀錄儲存數據B11、B12。此外，指標ptr1、ptr2之間所對應的儲存容量是為內存區塊320的剩餘空間，指標ptr3、ptr4之間所對應的儲存容量是為內存區塊340的剩餘空間，以及指標ptr5、ptr6之間所對應的儲存容量是為內存區塊360的剩餘空間。請同時參閱圖5與圖6，當系統接收到一筆60個位大小的儲存數據C1時，系統會先分別計算出內存區塊320、340、360中剩餘空間大小，本實施例的作法是分別將內存區塊320、340、360所對應的兩指標相減，由此可知內存區塊320的剩餘空間大小為20個位，內存區塊340的剩餘空間大小為5個位，內存區塊360剩餘空間的大小是為90個位。換句話說，只有內存區塊360足以寫入60位的儲存數據C1，因此，內存區塊360即為儲存數據C1的目標內存區塊。請注意，當系統檢測到有一個以上的內存區塊的剩餘空間都足以儲存數據C1時，則會選擇剩餘空間最小的內存區塊來存放儲存數據C1，以使內存空間利用更具有效率。當系統又接收到一40位的儲存數據C2時，此時內存區塊320、340、360的剩餘空間大小依序為20、5、30個位，都不足以容納儲存數據C2，因此，系統會進一步計算內存區塊320、340、360的破碎度(fragmentation)，本實施例中是使用現有計算破碎度的方法，也就是依據儲存裝置300的映像表來查詢每一儲存數據的地址與數據大小，然後分別統計出內存區塊320、340、360各有多少閒置的存儲空間(斜線部分)，然後再選擇閒置空間最多(亦即破碎度最大)的內存區塊來作為待重整內存區塊，因此，本實施例中，內存區塊320即為待重整內存區塊，最後，計算待重整內存區塊320在兩個儲存方向RD1、RD2上的破碎度並且選擇破碎度較高的儲存方向來進行重整。由於儲存方向RD1上的破碎度較高，因此內存區塊320中經由儲存方向RD1所寫入的儲存數據會進行重整，如圖中所示，儲存數據B4將會被往左挪，使得儲存數據B4的起始地址為m，若儲存數據B4的大小為36個位，則儲存方向RD1的指標ptr1也會改為指向到m+36。請參閱圖7，圖7為本發明雙向數據儲存方法重整圖6所示的儲存裝置300的示意圖。內存區塊320在重整後便會使位於儲存數據B4前的被釋放的存儲空間與位於儲存數據B4後的剩餘空間合併，因此，內存區塊320在重整後便可順利地儲存欲寫入的儲存數據C2。請注意，本發明所使用的重整方式並不以本實施例為限，不論只對待重整內存區塊的特定一儲存方向進行重整，或是同時對兩個儲存方向進行重整皆為本發明的範疇。相較於現有技術，本發明雙向數據儲存方法是依據寫入方向的選擇來控制多筆儲存數據均勻地分布在一內存區塊的兩端，假設該多筆儲存數據的數據量為m，則該內存區塊中每一端可視為紀錄著趨近m/2個位的數據量。當進行重整時，現有技術的儲存方法必須對整個內存區塊進行重整，因此重整的運算量約為mx，然而本發明雙向數據儲存方法對整個內存區塊進行重整所需花費的運算量約為明顯地小於現有技術所需的運算量mx。甚至，由於本發明雙向數據儲存方法是將m個位的數據量平均分布在內存區塊的兩端，所以當操作時間有限時，可以選擇性地只對一半的資料量進行重整，其運算量便大約為因此，本發明雙向數據儲存方法不僅可以降低內存重整所需的運算量，更可以將重整內存區塊所需的時間一分為二，當時間有限時，先進行一半的重整工作，另一半則等到一控制電路(例如一微處理器)較為空閒的時候再作，如此一來便可更有彈性地分配工作量給控制電路，同時進一步地提升系統的整體效能。以上所述僅為本發明的較佳實施例，凡依本發明申請專利範圍所做的均等變化與修飾，皆應屬本發明的涵蓋範圍。權利要求1.一種數據儲存方法，適用於對一儲存裝置寫入儲存數據，該儲存裝置包含有一個內存區塊，該內存區塊包括一第一端與一第二端，該數據儲存方法包含有接收一儲存數據；選擇一儲存方向，其中，當選擇一第一儲存方向作為該儲存方向時，則該第一端是為該第一儲存方向的起始點；當選擇一第二儲存方向作為該儲存方向時，則該第二端是為該第二儲存方向的起始點；以及依據該儲存方向將該儲存數據寫入該內存區塊。2.如權利要求1所述的數據儲存方法，其中，選擇該儲存方向的步驟包含有比較一第一總量與一第二總量，其中該第一總量為自該第一儲存方向所寫入該內存區塊的數據量，該第二總量為自該第二儲存方向所寫入該內存區塊的數據量；若該第一總量小於該第二總量，選擇該第一儲存方向來作為該儲存方向；以及若該第一總量大於該第二總量，選擇該第二儲存方向來作為該儲存方3.如權利要求1所述的數據儲存方法，其中，該儲存裝置包含有多個內存區塊，該數據儲存方法更包含有分別計算出多個內存區塊中的每一內存區塊的剩餘儲存空間；以及自該多個內存區塊選擇該內存區塊，該內存區塊的剩餘儲存空間是大於該儲存數據的大小。4.如權利要求3所述的數據儲存方法，其另包含有計算出該多個內存區塊的破碎度來選擇一待重整內存區塊，以進行一重整操作。5.如權利要求4所述的數據儲存方法，其中，進行該重整操作的步驟另包含有重整該待重整內存區塊中，自該第一儲存方向所寫入的多筆儲存數據或自該第二儲存方向所寫入的多筆儲存數據。6.如權利要求5所述的數據儲存方法，其中，進行該重整操作的步驟另包含有分別計算該待重整內存區塊中自該第一、第二儲存方向所寫入的多筆儲存數據的破碎度，並且依據具有較大破碎度的儲存方向來選擇性的重整該第一儲存方向與第二儲存方向所寫入的多筆儲存數據。7.如權利要求4所述的數據儲存方法，其中，若該多個內存區塊的剩餘儲存空間皆不足容納該儲存數據，則進行該重整操作。8.如權利要求4所述的數據儲存方法，其中，該重整操作可在一程序開始或結束時執行。9.如權利要求4所述的數據儲存方法，其中，選擇該待重整內存區塊的步驟另包含有自該多個內存區塊中選擇一具有最大破碎度的存儲區塊來作為該待重整內存區塊。10.如權利要求4所述的數據儲存方法，其中，選擇該待重整內存區塊的步驟另包含有自該多個內存區塊中選擇破碎度高於一臨界值的內存區塊來作為該待重整內存區塊。11.一種電子裝置，包含有一個內存區塊，該內存區塊包括一第一端與一第二端；一程序，該程序執行時產生一儲存數據，該程序選擇性的自該第一端與該第二端將該儲存數據寫入該內存區塊。12.如權利要求11所述的電子裝置，其中，該程序選擇一第一儲存方向作為該儲存方向時，則該第一端是為該第一儲存方向的起始點，當選擇一第二儲存方向作為該儲存方向時，則該第二端是為該第二儲存方向的起始點。13.如權利要求12所述的電子裝置，其中，該程序比較一第一總量與一第二總量，其中，該第一總量為自該第一儲存方向所寫入該內存區塊的數據量，該第二總量為自該第二儲存方向所寫入該內存區塊的數據量，該程序選擇該第一總量或該第二總量較小者對應的儲存方向。14.如權利要求12所述的電子裝置，其中，該程序計算出該內存區塊的一破碎度來選擇一待重整內存區塊進行一重整程序，該待重整內存區塊為自該第一儲存方向所寫入的多筆儲存數據或自該第二儲存方向所寫入的多筆儲存數據。15.如權利要求14所述的電子裝置，其中，該待重整內存區塊為具有較大破碎度的自該第一儲存方向所寫入的多筆儲存數據或自該第二儲存方向所寫入的多筆儲存數據。16.如權利要求14所述的電子裝置，其中，若該內存區塊的剩餘儲存空間皆不足容納該儲存數據，則進行該重整程序。17.如權利要求14所述的電子裝置，其中，該重整程序可在該程序開始或結束時執行。18.如權利要求14所述的電子裝置，其中，該破碎度高於一臨界值時進行該重整程序。全文摘要一種數據儲存方法用於對一儲存裝置寫入儲存數據，該儲存裝置包含有一個內存區塊，該內存區塊包括一第一端與一第二端，該數據儲存方法包含有接收一儲存數據；選擇一儲存方向，其中當選擇一第一儲存方向作為該儲存方向時，則該第一端是為該第一儲存方向的起始點；當選擇一第二儲存方向作為該儲存方向時，則該第二端是為該第二儲存方向的起始點；以及依據該儲存方向將該儲存數據寫入該內存區塊。文檔編號H04Q7/32GK1783031SQ20041009807公開日2006年6月7日申請日期2004年12月2日優先權日2004年12月2日發明者胡志麟申請人:明基電通股份有限公司