實現(xiàn)LRU算法，查找刪除時間復雜度都為O(1)
鳳慶網(wǎng)站制作公司哪家好，找成都創(chuàng)新互聯(lián)！從網(wǎng)頁設(shè)計、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、成都響應(yīng)式網(wǎng)站建設(shè)等網(wǎng)站項目制作，到程序開發(fā)，運營維護。成都創(chuàng)新互聯(lián)自2013年創(chuàng)立以來到現(xiàn)在10年的時間，我們擁有了豐富的建站經(jīng)驗和運維經(jīng)驗，來保證我們的工作的順利進行。專注于網(wǎng)站建設(shè)就選成都創(chuàng)新互聯(lián)。
LRU Cache是一個Cache置換算法，含義是“最近最少使用”，當Cache滿（沒有空閑的cache塊）時，把滿足“最近最少使用”的數(shù)據(jù)從Cache中置換出去，并且保證Cache中第一個數(shù)據(jù)是最近剛剛訪問的
實現(xiàn)思路
利用hashmap加鏈表來實現(xiàn)這個原理
鏈表元素node由兩個元素構(gòu)成（key-value），在hashmap中存入node的key值，以及node；hashmap的構(gòu)成為Integer,Node
為保證每次查找為O(1)并要判斷雙向鏈表里面是否含有元素，所以要將node設(shè)為兩個值，key和value，其中node的key與map的值相同，當hashmap中存在key的時候，則雙向鏈表中也存在key。利用這個特質(zhì)，能完成查找刪除都為O(1)
將最小使用的元素刪除，核心就是每次插入的時候，都插入到鏈表的頭結(jié)點；每次get一個元素時候，將get的那個元素刪除，然后將元素插入到頭結(jié)點
不管是YGC還是Full GC,GC過程中都會對導致程序運行中中斷,正確的選擇不同的GC策略,調(diào)整JVM、GC的參數(shù)，可以極大的減少由于GC工作，而導致的程序運行中斷方面的問題，進而適當?shù)奶岣逬ava程序的工作效率。但是調(diào)整GC是以個極為復雜的過程，由于各個程序具備不同的特點，如：web和GUI程序就有很大區(qū)別（Web可以適當?shù)耐ｎD，但GUI停頓是客戶無法接受的），而且由于跑在各個機器上的配置不同（主要cup個數(shù)，內(nèi)存不同），所以使用的GC種類也會不同(如何選擇見GC種類及如何選擇)。本文將注重介紹JVM、GC的一些重要參數(shù)的設(shè)置來提高系統(tǒng)的性能。
GC性能方面的考慮
對于GC的性能主要有2個方面的指標：吞吐量throughput（工作時間不算gc的時間占總的時間比）和暫停pause（gc發(fā)生時app對外顯示的無法響應(yīng)）。
1. Total Heap
默認情況下，vm會增加/減少heap大小以維持free space在整個vm中占的比例，這個比例由MinHeapFreeRatio和MaxHeapFreeRatio指定。
一般而言，server端的app會有以下規(guī)則：
對vm分配盡可能多的memory；
將Xms和Xmx設(shè)為一樣的值。如果虛擬機啟動時設(shè)置使用的內(nèi)存比較小，這個時候又需要初始化很多對象，虛擬機就必須重復地增加內(nèi)存。
處理器核數(shù)增加，內(nèi)存也跟著增大。
2. The Young Generation
另外一個對于app流暢性運行影響的因素是young generation的大小。young generation越大，minor collection越少；但是在固定heap size情況下，更大的young generation就意味著小的tenured generation，就意味著更多的major collection(major collection會引發(fā)minor collection)。
NewRatio反映的是young和tenured generation的大小比例。NewSize和MaxNewSize反映的是young generation大小的下限和上限，將這兩個值設(shè)為一樣就固定了young generation的大?。ㄍ琗ms和Xmx設(shè)為一樣）。
如果希望，SurvivorRatio也可以優(yōu)化survivor的大小，不過這對于性能的影響不是很大。SurvivorRatio是eden和survior大小比例。
一般而言，server端的app會有以下規(guī)則：
首先決定能分配給vm的最大的heap size，然后設(shè)定最佳的young generation的大??；
如果heap size固定后，增加young generation的大小意味著減小tenured generation大小。讓tenured generation在任何時候夠大，能夠容納所有l(wèi)ive的data（留10%-20%的空余）。
經(jīng)驗規(guī)則
年輕代大小選擇
響應(yīng)時間優(yōu)先的應(yīng)用:盡可能設(shè)大,直到接近系統(tǒng)的最低響應(yīng)時間限制(根據(jù)實際情況選擇).在此種情況下,年輕代收集發(fā)生的頻率也是最小的.同時,減少到達年老代的對象.
吞吐量優(yōu)先的應(yīng)用:盡可能的設(shè)置大,可能到達Gbit的程度.因為對響應(yīng)時間沒有要求,垃圾收集可以并行進行,一般適合8CPU以上的應(yīng)用.
避免設(shè)置過小.當新生代設(shè)置過小時會導致:1.YGC次數(shù)更加頻繁 2.可能導致YGC對象直接進入舊生代,如果此時舊生代滿了,會觸發(fā)FGC.
年老代大小選擇
響應(yīng)時間優(yōu)先的應(yīng)用:年老代使用并發(fā)收集器,所以其大小需要小心設(shè)置,一般要考慮并發(fā)會話率和會話持續(xù)時間等一些參數(shù).如果堆設(shè)置小了,可以會造成內(nèi)存碎 片,高回收頻率以及應(yīng)用暫停而使用傳統(tǒng)的標記清除方式;如果堆大了,則需要較長的收集時間.最優(yōu)化的方案,一般需要參考以下數(shù)據(jù)獲得:
并發(fā)垃圾收集信息、持久代并發(fā)收集次數(shù)、傳統(tǒng)GC信息、花在年輕代和年老代回收上的時間比例。
吞吐量優(yōu)先的應(yīng)用:一般吞吐量優(yōu)先的應(yīng)用都有一個很大的年輕代和一個較小的年老代.原因是,這樣可以盡可能回收掉大部分短期對象,減少中期的對象,而年老代盡存放長期存活對象.
較小堆引起的碎片問題
因為年老代的并發(fā)收集器使用標記,清除算法,所以不會對堆進行壓縮.當收集器回收時,他會把相鄰的空間進行合并,這樣可以分配給較大的對象.但是,當堆空間較小時,運行一段時間以后,就會出現(xiàn)"碎片",如果并發(fā)收集器找不到足夠的空間,那么并發(fā)收集器將會停止,然后使用傳統(tǒng)的標記,清除方式進行回收.如果出現(xiàn)"碎片",可能需要進行如下配置:
-XX:+UseCMSCompactAtFullCollection:使用并發(fā)收集器時,開啟對年老代的壓縮.
-XX:CMSFullGCsBeforeCompaction=0:上面配置開啟的情況下,這里設(shè)置多少次Full GC后,對年老代進行壓縮
用64位操作系統(tǒng)，Linux下64位的jdk比32位jdk要慢一些，但是吃得內(nèi)存更多，吞吐量更大
XMX和XMS設(shè)置一樣大，MaxPermSize和MinPermSize設(shè)置一樣大，這樣可以減輕伸縮堆大小帶來的壓力
使用CMS的好處是用盡量少的新生代，經(jīng)驗值是128M－256M， 然后老生代利用CMS并行收集， 這樣能保證系統(tǒng)低延遲的吞吐效率。 實際上cms的收集停頓時間非常的短，2G的內(nèi)存， 大約20－80ms的應(yīng)用程序停頓時間
系統(tǒng)停頓的時候可能是GC的問題也可能是程序的問題，多用jmap和jstack查看，或者killall -3 java，然后查看java控制臺日志，能看出很多問題。(相關(guān)工具的使用方法將在后面的blog中介紹)
仔細了解自己的應(yīng)用，如果用了緩存，那么年老代應(yīng)該大一些，緩存的HashMap不應(yīng)該無限制長，建議采用LRU算法的Map做緩存，LRUMap的最大長度也要根據(jù)實際情況設(shè)定。
采用并發(fā)回收時，年輕代小一點，年老代要大，因為年老大用的是并發(fā)回收，即使時間長點也不會影響其他程序繼續(xù)運行，網(wǎng)站不會停頓
JVM參數(shù)的設(shè)置(特別是 –Xmx –Xms –Xmn -XX:SurvivorRatio -XX:MaxTenuringThreshold等參數(shù)的設(shè)置沒有一個固定的公式，需要根據(jù)PV old區(qū)實際數(shù)據(jù) YGC次數(shù)等多方面來衡量。為了避免promotion faild可能會導致xmn設(shè)置偏小，也意味著YGC的次數(shù)會增多，處理并發(fā)訪問的能力下降等問題。每個參數(shù)的調(diào)整都需要經(jīng)過詳細的性能測試，才能找到特定應(yīng)用的最佳配置。
promotion failed:
垃圾回收時promotion failed是個很頭痛的問題，一般可能是兩種原因產(chǎn)生，第一個原因是救助空間不夠，救助空間里的對象還不應(yīng)該被移動到年老代，但年輕代又有很多對象需要放入救助空間；第二個原因是年老代沒有足夠的空間接納來自年輕代的對象；這兩種情況都會轉(zhuǎn)向Full GC，網(wǎng)站停頓時間較長。
解決方方案一：
第一個原因我的最終解決辦法是去掉救助空間，設(shè)置-XX:SurvivorRatio=65536 -XX:MaxTenuringThreshold=0即可，第二個原因我的解決辦法是設(shè)置CMSInitiatingOccupancyFraction為某個值（假設(shè)70），這樣年老代空間到70%時就開始執(zhí)行CMS，年老代有足夠的空間接納來自年輕代的對象。
解決方案一的改進方案：
又有改進了，上面方法不太好，因為沒有用到救助空間，所以年老代容易滿，CMS執(zhí)行會比較頻繁。我改善了一下，還是用救助空間，但是把救助空間加大，這樣也不會有promotion failed。具體操作上，32位Linux和64位Linux好像不一樣，64位系統(tǒng)似乎只要配置MaxTenuringThreshold參數(shù)，CMS還是有暫停。為了解決暫停問題和promotion failed問題，最后我設(shè)置-XX:SurvivorRatio=1 ，并把MaxTenuringThreshold去掉，這樣即沒有暫停又不會有promotoin failed，而且更重要的是，年老代和永久代上升非常慢（因為好多對象到不了年老代就被回收了），所以CMS執(zhí)行頻率非常低，好幾個小時才執(zhí)行一次，這樣，服務(wù)器都不用重啟了。
-Xmx4000M -Xms4000M -Xmn600M -XX:PermSize=500M -XX:MaxPermSize=500M -Xss256K -XX:+DisableExplicitGC -XX:SurvivorRatio=1 -XX:+UseConcMarkSweepGC -XX:+UseParNewGC -XX:+CMSParallelRemarkEnabled -XX:+UseCMSCompactAtFullCollection -XX:CMSFullGCsBeforeCompaction=0 -XX:+CMSClassUnloadingEnabled -XX:LargePageSizeInBytes=128M -XX:+UseFastAccessorMethods -XX:+UseCMSInitiatingOccupancyOnly -XX:CMSInitiatingOccupancyFraction=80 -XX:SoftRefLRUPolicyMSPerMB=0 -XX:+PrintClassHistogram -XX:+PrintGCDetails -XX:+PrintGCTimeStamps -XX:+PrintHeapAtGC -Xloggc:log/gc.log
CMSInitiatingOccupancyFraction值與Xmn的關(guān)系公式
上面介紹了promontion faild產(chǎn)生的原因是EDEN空間不足的情況下將EDEN與From survivor中的存活對象存入To survivor區(qū)時,To survivor區(qū)的空間不足，再次晉升到old gen區(qū)，而old gen區(qū)內(nèi)存也不夠的情況下產(chǎn)生了promontion faild從而導致full gc.那可以推斷出：eden+from survivor old gen區(qū)剩余內(nèi)存時，不會出現(xiàn)promontion faild的情況，即：
(Xmx-Xmn)*(1-CMSInitiatingOccupancyFraction/100)=(Xmn-Xmn/(SurvivorRatior+2)) 進而推斷出：
CMSInitiatingOccupancyFraction =((Xmx-Xmn)-(Xmn-Xmn/(SurvivorRatior+2)))/(Xmx-Xmn)*100
例如：
當xmx=128 xmn=36 SurvivorRatior=1時 CMSInitiatingOccupancyFraction=((128.0-36)-(36-36/(1+2)))/(128-36)*100 =73.913
當xmx=128 xmn=24 SurvivorRatior=1時 CMSInitiatingOccupancyFraction=((128.0-24)-(24-24/(1+2)))/(128-24)*100=84.615…
當xmx=3000 xmn=600 SurvivorRatior=1時 CMSInitiatingOccupancyFraction=((3000.0-600)-(600-600/(1+2)))/(3000-600)*100=83.33
CMSInitiatingOccupancyFraction低于70% 需要調(diào)整xmn或SurvivorRatior值。
#includeiostream
using namespace std;
int size;
int *w;
//定義一個動態(tài)數(shù)組
struct mem
{
int num;
int count;
}memBlock[3]={0,0,0,0,0,0};
void LRU()
{
for( int i = 0; i size; i++ )
{
int maxCount = memBlock[0].count;
int maxPos = 0;
int j = 0;
bool bFind = false;
for( j = 0; j 3; j++ )
{
// 標記出count值最大的位置
if( maxCount memBlock[j].count )
{
maxCount = memBlock[j].count;
maxPos = j;
}
// 將所有的count值都+1
memBlock[j].count++;
// 如果命中，將其count值置為0
if( w[i] == memBlock[j].num )
{
memBlock[j].count = 0;
bFind = true;
}
}
// 未命中，將count最大的拿來替換
if( !bFind )
{
memBlock[maxPos].num = w[i];
memBlock[maxPos].count = 0;
}
for(j = 0; j 3; j++) //輸出
cout memBlock[j].num " ";
cout " " endl;
}
}
int main() //主函數(shù)
{
cout"請輸入需訪問的頁面數(shù)量:"endl;
cinsize;
w = new int[size];
cout"請輸入需要訪問的頁面"endl;
for(int a=0;asize;a++)
{
cinw[a];//輸入數(shù)組
}
coutendl"(LRU)"endl;
LRU();
return 0;
}
引用 ： 回答者： floxer | 三級
重慶分公司
重慶分公司
