替換演算法題目

Ⅰ LRU替換演算法怎麼理解，過程好難，這個題麻煩大神幫我看看

• LRU是LeastRecently Used 近期最少使用演算法，也就是說，近期最少使用的那個頁面，將被置換出去（可以理解為這個頁面將被廢棄）

• 對於本題。內存容量為4個頁面，這是要清楚的。具體看下面的表格：

• 缺頁率 = 6 / 20 =3/ 10 = 30%

• 我具體解釋下上面的表格吧。

  從上到下是4個頁面。

• 最開始，1需要被調用，將1放入內存中，由於1一開始沒有，所以一次缺頁

• 然後，8要被調用，，將1放入內存中，由於8一開始沒有，所以又產生一次缺頁

• 以此往後，直到4塊內存都滿了，最新使用過的放在最下面（頁4），則置換出最上面（頁1）。

• 通俗地說，就是總共空間只有4塊。只能放4個頁面。那麼當頁面滿的時候，就把你很久很久沒有使用過的那個頁面（也就是近期最少使用的頁面）置換出去，然後補充新的頁面進來。

• 這個算是頁面置換裡面比較經典的一個演算法了，希望能幫到你！
  

Ⅱ Cache內容為什麼要經常替換常用替換演算法有幾種

二級緩存

CPU緩存（Cache Memory）位於CPU與內存之間的臨時存儲器，它的容量比內存小但交換速度快。在緩存中的數據是內存中的一小部分，但這一小部分是短時間內CPU即將訪問的，當CPU調用大量數據時，就可避開內存直接從緩存中調用，從而加快讀取速度。由此可見，在CPU中加入緩存是一種高效的解決方案，這樣整個內存儲器（緩存+內存）就變成了既有緩存的高速度，又有內存的大容量的存儲系統了。緩存對CPU的性能影響很大，主要是因為CPU的數據交換順序和CPU與緩存間的帶寬引起的。

緩存的工作原理是當CPU要讀取一個數據時，首先從緩存中查找，如果找到就立即讀取並送給CPU處理；如果沒有找到，就用相對慢的速度從內存中讀取並送給CPU處理，同時把這個數據所在的數據塊調入緩存中，可以使得以後對整塊數據的讀取都從緩存中進行，不必再調用內存。

正是這樣的讀取機制使CPU讀取緩存的命中率非常高（大多數CPU可達90%左右），也就是說CPU下一次要讀取的數據90%都在緩存中，只有大約10%需要從內存讀取。這大大節省了CPU直接讀取內存的時間，也使CPU讀取數據時基本無需等待。總的來說，CPU讀取數據的順序是先緩存後內存。

最早先的CPU緩存是個整體的，而且容量很低，英特爾公司從Pentium時代開始把緩存進行了分類。當時集成在CPU內核中的緩存已不足以滿足CPU的需求，而製造工藝上的限制又不能大幅度提高緩存的容量。因此出現了集成在與CPU同一塊電路板上或主板上的緩存，此時就把 CPU內核集成的緩存稱為一級緩存，而外部的稱為二級緩存。一級緩存中還分數據緩存（Data Cache，D-Cache）和指令緩存（Instruction Cache，I-Cache）。二者分別用來存放數據和執行這些數據的指令，而且兩者可以同時被CPU訪問，減少了爭用Cache所造成的沖突，提高了處理器效能。英特爾公司在推出Pentium 4處理器時，用新增的一種一級追蹤緩存替代指令緩存，容量為12KμOps，表示能存儲12K條微指令。

隨著CPU製造工藝的發展，二級緩存也能輕易的集成在CPU內核中，容量也在逐年提升。現在再用集成在CPU內部與否來定義一、二級緩存，已不確切。而且隨著二級緩存被集成入CPU內核中，以往二級緩存與CPU大差距分頻的情況也被改變，此時其以相同於主頻的速度工作，可以為CPU提供更高的傳輸速度。

二級緩存是CPU性能表現的關鍵之一，在CPU核心不變化的情況下，增加二級緩存容量能使性能大幅度提高。而同一核心的CPU高低端之分往往也是在二級緩存上有差異，由此可見二級緩存對於CPU的重要性。

CPU在緩存中找到有用的數據被稱為命中，當緩存中沒有CPU所需的數據時（這時稱為未命中），CPU才訪問內存。從理論上講，在一顆擁有二級緩存的CPU中，讀取一級緩存的命中率為80%。也就是說CPU一級緩存中找到的有用數據占數據總量的80%，剩下的20%從二級緩存中讀取。由於不能准確預測將要執行的數據，讀取二級緩存的命中率也在80%左右（從二級緩存讀到有用的數據占總數據的16%）。那麼還有的數據就不得不從內存調用，但這已經是一個相當小的比例了。目前的較高端的CPU中，還會帶有三級緩存，它是為讀取二級緩存後未命中的數據設計的—種緩存，在擁有三級緩存的CPU中，只有約 5%的數據需要從內存中調用，這進一步提高了CPU的效率。

為了保證CPU訪問時有較高的命中率，緩存中的內容應該按一定的演算法替換。一種較常用的演算法是「最近最少使用演算法」（LRU演算法），它是將最近一段時間內最少被訪問過的行淘汰出局。因此需要為每行設置一個計數器，LRU演算法是把命中行的計數器清零，其他各行計數器加1。當需要替換時淘汰行計數器計數值最大的數據行出局。這是一種高效、科學的演算法，其計數器清零過程可以把一些頻繁調用後再不需要的數據淘汰出緩存，提高緩存的利用率。

CPU產品中，一級緩存的容量基本在4KB到64KB之間，二級緩存的容量則分為128KB、256KB、512KB、1MB、2MB等。一級緩存容量各產品之間相差不大，而二級緩存容量則是提高CPU性能的關鍵。二級緩存容量的提升是由CPU製造工藝所決定的，容量增大必然導致CPU內部晶體管數的增加，要在有限的CPU面積上集成更大的緩存，對製造工藝的要求也就越高。

雙核心CPU的二級緩存比較特殊，和以前的單核心CPU相比，最重要的就是兩個內核的緩存所保存的數據要保持一致，否則就會出現錯誤，為了解決這個問題不同的CPU使用了不同的辦法：

Intel雙核心處理器的二級緩存
目前Intel的雙核心CPU主要有Pentium D、Pentium EE、Core Duo三種，其中Pentium D、Pentium EE的二級緩存方式完全相同。Pentium D和Pentium EE的二級緩存都是CPU內部兩個內核具有互相獨立的二級緩存，其中，8xx系列的Smithfield核心CPU為每核心1MB，而9xx系列的 Presler核心CPU為每核心2MB。這種CPU內部的兩個內核之間的緩存數據同步是依靠位於主板北橋晶元上的仲裁單元通過前端匯流排在兩個核心之間傳輸來實現的，所以其數據延遲問題比較嚴重，性能並不盡如人意。
Core Duo使用的核心為Yonah，它的二級緩存則是兩個核心共享2MB的二級緩存，共享式的二級緩存配合Intel的「Smart cache」共享緩存技術，實現了真正意義上的緩存數據同步，大幅度降低了數據延遲，減少了對前端匯流排的佔用，性能表現不錯，是目前雙核心處理器上最先進的二級緩存架構。今後Intel的雙核心處理器的二級緩存都會採用這種兩個內核共享二級緩存的「Smart cache」共享緩存技術。

AMD雙核心處理器的二級緩存
Athlon 64 X2 CPU的核心主要有Manchester和Toledo兩種，他們的二級緩存都是CPU內部兩個內核具有互相獨立的二級緩存，其中，Manchester 核心為每核心512KB，而Toledo核心為每核心1MB。處理器內部的兩個內核之間的緩存數據同步是依靠CPU內置的System Request Interface(系統請求介面，SRI)控制，傳輸在CPU內部即可實現。這樣一來，不但CPU資源佔用很小，而且不必佔用內存匯流排資源，數據延遲也比Intel的Smithfield核心和Presler核心大為減少，協作效率明顯勝過這兩種核心。不過，由於這種方式仍然是兩個內核的緩存相互獨立，從架構上來看也明顯不如以Yonah核心為代表的Intel的共享緩存技術Smart Cache。
___________________________________

前端匯流排
匯流排是將信息以一個或多個源部件傳送到一個或多個目的部件的一組傳輸線。通俗的說，就是多個部件間的公共連線，用於在各個部件之間傳輸信息。人們常常以MHz表示的速度來描述匯流排頻率。匯流排的種類很多，前端匯流排的英文名字是Front Side Bus，通常用FSB表示，是將CPU連接到北橋晶元的匯流排。選購主板和CPU時，要注意兩者搭配問題，一般來說，如果CPU不超頻，那麼前端匯流排是由 CPU決定的，如果主板不支持CPU所需要的前端匯流排，系統就無法工作。也就是說，需要主板和CPU都支持某個前端匯流排，系統才能工作，只不過一個CPU 默認的前端匯流排是唯一的，因此看一個系統的前端匯流排主要看CPU就可以。

北橋晶元負責聯系內存、顯卡等數據吞吐量最大的部件，並和南橋晶元連接。CPU就是通過前端匯流排（FSB）連接到北橋晶元，進而通過北橋晶元和內存、顯卡交換數據。前端匯流排是CPU和外界交換數據的最主要通道，因此前端匯流排的數據傳輸能力對計算機整體性能作用很大，如果沒足夠快的前端匯流排，再強的CPU也不能明顯提高計算機整體速度。數據傳輸最大帶寬取決於所有同時傳輸的數據的寬度和傳輸頻率，即數據帶寬＝（匯流排頻率×數據位寬）÷8。目前PC機上所能達到的前端匯流排頻率有266MHz、333MHz、400MHz、533MHz、800MHz幾種，前端匯流排頻率越大，代表著CPU與北橋晶元之間的數據傳輸能力越大，更能充分發揮出CPU的功能。現在的CPU技術發展很快，運算速度提高很快，而足夠大的前端匯流排可以保障有足夠的數據供給給CPU，較低的前端匯流排將無法供給足夠的數據給CPU，這樣就限制了CPU性能得發揮，成為系統瓶頸。顯然同等條件下，前端匯流排越快，系統性能越好。

外頻與前端匯流排頻率的區別：前端匯流排的速度指的是CPU和北橋晶元間匯流排的速度，更實質性的表示了CPU和外界數據傳輸的速度。而外頻的概念是建立在數字脈沖信號震盪速度基礎之上的，也就是說，100MHz外頻特指數字脈沖信號在每秒鍾震盪一萬萬次，它更多的影響了PCI及其他匯流排的頻率。之所以前端匯流排與外頻這兩個概念容易混淆，主要的原因是在以前的很長一段時間里（主要是在Pentium 4出現之前和剛出現Pentium 4時），前端匯流排頻率與外頻是相同的，因此往往直接稱前端匯流排為外頻，最終造成這樣的誤會。隨著計算機技術的發展，人們發現前端匯流排頻率需要高於外頻，因此採用了QDR（Quad Date Rate）技術，或者其他類似的技術實現這個目的。這些技術的原理類似於AGP的2X或者4X，它們使得前端匯流排的頻率成為外頻的2倍、4倍甚至更高，從此之後前端匯流排和外頻的區別才開始被人們重視起來。此外，在前端匯流排中比較特殊的是AMD64的HyperTransport。

Ⅲ 求一題操作系統缺頁率的題目

已知某程序訪問以下頁面：0、1、4、2、0、2、6、5、1、2、3、2、1、2、6、2、1、3、6、2，如果程序有3個頁框可用且使用下列替換演算法，求出現缺頁的次數。

（1）FIFO替換演算法（5分）（2）LRU替換演算法（5分）

Ⅳ 選擇題下面哪個頁面替換演算法實際上是不能夠實現的

首先，在FIFO換頁策略下，紅框時刻若缺頁（miss），則換出的塊是61.為什麼不是221？塊2已經在內存中，該次訪問命中，故不會替換塊62.為什麼不是231？塊6被塊3替換，故內存塊序列為231不明白請及時追問，滿意敬請採納，O(∩_∩)O謝謝

Ⅳ 考試題目，cache有甚麼作用老師給的提示是替換演算法，甚麼隨機替換，最不經常替換

高速緩沖存儲器是存在於主存與CPU之間的一級存儲器， 由靜態存儲晶元(SRAM)組成，容量比較小但速度比主存高得多， 接近於CPU的速度。
就是為了提高存取速度，當出現高速存儲器對應列中沒有空的位置時，便淘汰該列中的某一組以騰出位置存放新調入的組，這稱為替換。確定替換的規則叫替換演算法，常用的替換演算法有:最近最少使用法（LRU）、先進先出法（FIFO）和隨機法（RAND）等。

Ⅵ java字元串替換演算法問題

publicclassDay09_C{
	staticStringsrc="aeiou";
	staticbooleanflag=false;
	publicstaticvoidmain(String[]args){
		Stringch1="amcsefig",ch2="2931";
		System.out.println("ch1:"+ch1+";ch2:"+ch2+"	"+getStr(ch1,ch2));
		ch2="29";
		System.out.println("ch1:"+ch1+";ch2:"+ch2+"	"+getStr(ch1,ch2));
	}
	privatestaticStringgetStr(Stringch1,Stringch2){
		Stringtem="";
		for(inti=0,c=0;i<ch1.length();i++){
			chara=ch1.charAt(i);
			for(intj=0;j<src.length();j++){
				charb=src.charAt(j);
				if(!(a!=b)){
					flag=true;
					break;
				}
			}
			if(flag){
				if(c<ch2.length()){
					a=ch2.charAt(c);
					c++;
				}else{
					a='#';
				}
			}
			tem+=a;
			flag=false;
		}
		returntem;
	}
}

Ⅶ 在存儲系統的Cache與主層次結構中,常會發生數據交換問題,我們較常使用的替換演算法有

常用Cache 塊置換演算法有
LRU,最近最久未使用
FIFO,先進先出等

Ⅷ 操作系統題：頁面置換演算法 OPT FIFO LRU

fifo就是先進先出，可以想像成隊列
lru是最久未使用，當需要替換頁面的時候，向前面看，最久沒使用的那個被替換
opt是替換頁面的時候，優先替換後面最遲出現的。
不懂再問。。