共用一個環形記憶區的多堆疊

Abstract

本篇論文中，我們提出了一個共用一個環形記憶區的新方法。為了獲得一特定記憶區 使用的最好效率，我們將此記憶區視為環狀。傳統的觀念中，記憶區都是被視為一由 低位址到高位址的矩形，而我們將最低和最高的記憶區位址視為相鄰，如此一來，這 記憶區便可以被視為圓形來對待。 將固定大小的環形記憶區均分給K個堆疊，而當這K個堆疊被安排在此環形記憶區后 ，那些操作於堆疊上的運作，像是增加、刪除等等動作，就可以很容易地被執行。同 樣地，若有某一堆疊發生溢滿的狀況，我們必須重新安排所有其它堆疊的位置，而後 資料的搬遷和堆疊的移動也是很簡單地可以被完成。 基於圓形的一般通性，我們的演算法便有最佳的初始情況，亦即堆疊發生溢滿的機率 會比傳統的方法低。此一新的演算法對於記憶區的使用率比knuth,Garwick 或是Yang et al.等人的演算法都好。亦有助於提昇整個程式或系統的執行效率。