㈠ 演算法中基本運算的頻度是什麼意思
語句執行頻度表示一次運行中語句總共執行的次數時間復雜度用基本語句執行頻度表示
㈡ 磁碟緩存置換演算法作用是什麼
雖然緩存的最終目的為了提高性能，但緩存寫的技術與緩存讀的技術有很大的不同。但如果它帶來的數據丟失危險很大，那麼，就是一個不可接受的方案。因此，安全地將數據保存在非易失存儲中是很重要的，因為這樣數據就可以長期地保存。雖然讀緩存技術用於讀操作時可以提高系統性能，但當用於新產生數據的寫操作時，卻產生了一些有趣的問題。
目前，用於緩存實現的大部分存儲器都是易失型存儲器，因此，當斷電的時候，所有緩存的數據都將丟失。為了避免這個問題，一種專為緩存而特別設計的存儲器已經面世，這種特製的存儲器內嵌後備電池，經常用於磁碟子系統，以保證在某一指定時間內供電和數據存儲。其他類型的非易失內存也已經生產出來，如快閃記憶體，但由於它們價格相對較高、性能較低及使用壽命有限等，通常不被用作緩存內存。
下面考慮使用L R U的示例，並假定某個應用正在更新數據。由於在緩存中可能存儲了過時數據。這里過時數據是指被存儲的數據，但不表示最新的版本。當應用修改數據時，過時的數據也必須要修改，無論它存放在哪裡—在磁碟上，或者在磁碟和緩存內存里。圖顯示了兩種情況：第一種情況是數據僅存放在磁碟上；第二種情況是數據既存放在磁碟上，也存放在緩存內存中。
在緩存未命中情況下，緩存控制器決定是否緩存這些數據。對於這個例子，緩存控制器決定放棄緩存關於這個寫操作的數據，而把該數據直接寫入非易失存儲。換言之，數據僅寫入磁碟，繼續執行下一個操作。
在緩存命中情況下，緩存控制器可以修改緩存，甚至丟棄緩存，或使緩存內容無效，以致於後來的數據能夠覆蓋它。假如修改了緩存，必須最終在某個時刻將它寫入非易失磁碟存儲，但什麼時候寫呢？可能數據在近期將不被修改，但也可能它成為一個熱點，將經歷接二連三地、快速的操作。數據寫入非易失存儲器速度相對較慢，因為必須等待磁碟設備寫完成後，才能進行新的寫操作，致使系統的性能降低。另一方面，假如數據首先被寫進緩存，延遲一段時間後才被寫到非易失存儲，那麼，電源的臨時故障就有可能導致數據的丟失。
㈢ 代碼訪問頻率太高，消耗cpu，如何優化
你好
1，右擊任務欄，然後點擊任務管理器，點進程，關閉耗資源高的程序。
2，可能是電腦中毒，電腦殺毒，建議在安全模式下進行殺毒。
3，少開一些比較耗CPU資源的程序。
4，可能CPU邏輯處理器數少，程序所需的資源不足，便會達到100%，所以建議更換擁有更多核心的CPU。
㈣ 請問AMD的處理器 主頻怎麼計算 一級、二級緩存技術是怎麼回事
這個沒用固定的計算公式，只有死記頻率了，比如3000+對應1.8G。
緩存是CPU的一部分，它存在於CPU中
CPU存取數據的速度非常的快，一秒鍾能夠存取、處理十億條指令和數據（術語：CPU主頻1G），而內存就慢很多，快的內存能夠達到幾十兆就不錯了，可見兩者的速度差異是多麼的大
緩存是為了解決CPU速度和內存速度的速度差異問題
內存中被CPU訪問最頻繁的數據和指令被復制入CPU中的緩存，這樣CPU就可以不經常到象「蝸牛」一樣慢的內存中去取數據了，CPU只要到緩存中去取就行了，而緩存的速度要比內存快很多
這里要特別指出的是：
1.因為緩存只是內存中少部分數據的復製品，所以CPU到緩存中尋找數據時，也會出現找不到的情況（因為這些數據沒有從內存復制到緩存中去），這時CPU還是會到內存中去找數據，這樣系統的速度就慢下來了，不過CPU會把這些數據復制到緩存中去，以便下一次不要再到內存中去取。
2.因為隨著時間的變化，被訪問得最頻繁的數據不是一成不變的，也就是說，剛才還不頻繁的數據，此時已經需要被頻繁的訪問，剛才還是最頻繁的數據，現在又不頻繁了，所以說緩存中的數據要經常按照一定的演算法來更換，這樣才能保證緩存中的數據是被訪問最頻繁的
3.關於一級緩存和二級緩存
為了分清這兩個概念，我們先了解一下RAM
ram和ROM相對的，RAM是掉電以後，其中才信息就消失那一種，ROM在掉電以後信息也不會消失那一種
RAM又分兩種，
一種是靜態RAM，SRAM；一種是動態RAM，DRAM。前者的存儲速度要比後者快得多，我們現在使用的內存一般都是動態RAM。
有的菜鳥就說了，為了增加系統的速度，把緩存擴大不就行了嗎，擴大的越大，緩存的數據越多，系統不就越快了嗎
緩存通常都是靜態RAM，速度是非常的快，
但是靜態RAM集成度低（存儲相同的數據，靜態RAM的體積是動態RAM的6倍），
價格高（同容量的靜態RAM是動態RAM的四倍），
由此可見，擴大靜態RAM作為緩存是一個非常愚蠢的行為，
但是為了提高系統的性能和速度，我們必須要擴大緩存，
這樣就有了一個折中的方法，不擴大原來的靜態RAM緩存，而是增加一些高速動態RAM做為緩存，
這些高速動態RAM速度要比常規動態RAM快，但比原來的靜態RAM緩存慢，
我們把原來的靜態ram緩存叫一級緩存，而把後來增加的動態RAM叫二級緩存。
一級緩存和二級緩存中的內容都是內存中訪問頻率高的數據的復製品（映射），它們的存在都是為了減少高速CPU對慢速內存的訪問。
通常CPU找數據或指令的順序是：先到一級緩存中找，找不到再到二級緩存中找，如果還找不到就只有到內存中找了
㈤ linux內核物理內存管理有哪些常用演算法 lru slab
採用夥伴演算法分配內存時，每次至少分配一個頁面。但當請求分配的內存大小為幾十個位元組或幾百個位元組時應該如何處理？如何在一個頁面中分配小的內存區，小內存區的分配所產生的內碎片又如何解決？
Linux2.0採用的解決辦法是建立了13個空閑區鏈表，它們的大小從32位元組到132056位元組。從Linux2.2開始，MM的開發者採用了一種叫做slab的分配模式，該模式早在1994年就被開發出來，用於Sun Microsystem Solaris 2.4操作系統中。Slab的提出主要是基於以下考慮：
· 內核對內存區的分配取決於所存放數據的類型。例如，當給用戶態進程分配頁面時，內核調用get_free_page()函數，並用0填充這個頁面。 而給內核的數據結構分配頁面時，事情沒有這么簡單，例如，要對數據結構所在的內存進行初始化、在不用時要收回它們所佔用的內存。因此，Slab中引入了對象這個概念，所謂對象就是存放一組數據結構的內存區，其方法就是構造或析構函數，構造函數用於初始化數據結構所在的內存區，而析構函數收回相應的內存區。但為了便於理解，你也可以把對象直接看作內核的數據結構。為了避免重復初始化對象，Slab分配模式並不丟棄已分配的對象，而是釋放但把它們依然保留在內存中。當以後又要請求分配同一對象時，就可以從內存獲取而不用進行初始化，這是在Solaris 中引入Slab的基本思想。
實際上，Linux中對Slab分配模式有所改進，它對內存區的處理並不需要進行初始化或回收。出於效率的考慮，Linux並不調用對象的構造或析構函數，而是把指向這兩個函數的指針都置為空。Linux中引入Slab的主要目的是為了減少對夥伴演算法的調用次數。
· 實際上，內核經常反復使用某一內存區。例如，只要內核創建一個新的進程，就要為該進程相關的數據結構（task_struct、打開文件對象等）分配內存區。當進程結束時，收回這些內存區。因為進程的創建和撤銷非常頻繁，因此，Linux的早期版本把大量的時間花費在反復分配或回收這些內存區上。從Linux2.2開始，把那些頻繁使用的頁面保存在高速緩存中並重新使用。
· 可以根據對內存區的使用頻率來對它分類。對於預期頻繁使用的內存區，可以創建一組特定大小的專用緩沖區進行處理，以避免內碎片的產生。對於較少使用的內存區，可以創建一組通用緩沖區（如Linux2.0中所使用的2的冪次方）來處理，即使這種處理模式產生碎片，也對整個系統的性能影響不大。
· 硬體高速緩存的使用，又為盡量減少對夥伴演算法的調用提供了另一個理由，因為對夥伴演算法的每次調用都會「弄臟」硬體高速緩存，因此，這就增加了對內存的平均訪問次數。
Slab分配模式把對象分組放進緩沖區（盡管英文中使用了Cache這個詞，但實際上指的是內存中的區域，而不是指硬體高速緩存）。因為緩沖區的組織和管理與硬體高速緩存的命中率密切相關，因此，Slab緩沖區並非由各個對象直接構成，而是由一連串的「大塊（Slab）」構成，而每個大塊中則包含了若干個同種類型的對象，這些對象或已被分配，或空閑，如圖6.12所示。一般而言，對象分兩種，一種是大對象，一種是小對象。所謂小對象，是指在一個頁面中可以容納下好幾個對象的那種。例如，一個inode結構大約佔300多個位元組，因此，一個頁面中可以容納8個以上的inode結構，因此，inode結構就為小對象。Linux內核中把小於512位元組的對象叫做小對象。
㈥ 最佳頁面淘汰演算法是怎樣計算的
<1> 先進先出調度演算法
先進先出調度演算法根據頁面進入內存的時間先後選擇淘汰頁面，先進入內存的頁面先淘汰，後進入內存的後淘汰。本演算法實現時需要將頁面按進入內存的時間先後組成一個隊列，每次調度隊首頁面予以淘汰。
<2>最近最少調度演算法
先進先出調度演算法沒有考慮頁面的使用情況，大多數情況下性能不佳。根據程序執行的局部性特點，程序一旦訪問了某些代碼和數據，則在一段時間內會經常訪問他們，因此最近最少用調度在選擇淘汰頁面時會考慮頁面最近的使用，總是選擇在最近一段時間以來最少使用的頁面予以淘汰。演算法實現時需要為每個頁面設置數據結構記錄頁面自上次訪問以來所經歷的時間。
<3>最近最不常用調度演算法
由於程序設計中經常使用循環結構，根據程序執行的局部性特點，可以設想在一段時間內經常被訪問的代碼和數據在將來也會經常被訪問，顯然這樣的頁面不應該被淘汰。最近最不常用調度演算法總是根據一段時間內頁面的訪問次數來選擇淘汰頁面，每次淘汰訪問次數最少的頁面。演算法實現時需要為每個頁面設置計數器，記錄訪問次數。計數器由硬體或操作系統自動定時清零。
（2）缺頁調度次數和缺頁中斷率、缺頁置換率計算
缺頁中斷次數是缺頁時發出缺頁中斷的次數。
缺頁中斷率=缺頁中斷次數/總的頁面引用次數*100%
缺頁調度次數是調入新頁時需要進行頁面調度的次數
缺頁置換率=缺頁調度次數/總的頁面引用次數*100%
㈦ 頁面淘汰演算法
LRU（2個塊）：
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 3 3 2 2 5 5 2 2 2 2 7 7 3 3 1 1 3 3
2 2 4 4 1 1 6 6 1 1 3 3 6 6 2 2 2 2 6
缺頁中斷18次
LRU（4個塊）：
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 1 1 1 1 1 1 1 1 1 1 1 6 6 6 6 6 6 6
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 5 5 5 5 5 3 3 3 3 3 3 3 3 3
4 4 4 4 6 6 6 6 6 7 7 7 7 1 1 1 1
缺頁中斷次數10次
FIFO（2個塊）
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 1 1 1 1 1 1 1 1 1 3 3 6 6 2 2 2 3 3
2 2 4 4 1 1 6 6 1 1 2 7 7 3 3 1 1 1 6
缺頁中斷次數18次
FIFO（4個塊）
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 1 1 1 1 5 5 5 5 5 3 3 3 3 3 1 1 1 1
2 2 2 2 2 2 6 6 6 6 6 7 7 7 7 7 7 3 7
3 3 3 3 3 3 2 2 2 2 2 6 6 6 6 6 6 6
4 4 4 4 4 4 1 1 1 1 1 1 2 2 2 2 2
缺頁中斷次數：14次
㈧ CACHE替換演算法有哪幾種，分別簡要說明
其代表演算法有：①Hybrid演算法：演算法對Cache中的每一個對象賦予一個效用函數，將效用最小的對象替換出Cache；②LowestRelativeValue演算法：將效用值最低的對象替換出Cache；③（LCNR）演算法：該演算法使用一個關於文檔訪問頻次、傳輸時間和大小的推理函數來確定替換文檔；④Bolot等人提出了一種基於文檔傳輸時間代價、大小、和上次訪問時間的權重推理函數來確定文檔替換；⑤SizeAdjustLRU（SLRU）演算法：對緩存的對象按代價與大小的比率進行排序，並選取比率最小的對象進行替換
擴展知識:
Cache是一種根據程序局部性原則，通過小容量速度快的存儲器緩存部分數據，以減少處理器對慢速大容量存儲器的訪問次數，從而提升處理器取指效率的機制。Cache替換演算法是指當Cache缺失發生後，Cache按某種機制選中高速緩存中的某個地址進行數據更新。Cache替換演算法對Cache的命中率有較大的影響。目前主流的Cache替換演算法有偽隨機、先進先出(FIFO——First In First Out)和最近最少使用(LRU——Least Recently Used)等。相較於偽隨機和先進先出演算法，LRU演算法更符合程序局部性原則(當前執行的程序代碼，在不久後會再次訪問該代碼段)，Cache的命中率更高，但其硬體資源消耗非常大。
傳統的LRU演算法對Cache的每一路進行統計，在需要替換時，將最近最少被使用的那一路替換。由於傳統LRU演算法的數據使用頻率統計為向上計數，故其計數器計數位寬較大，且需要額外的機制來處理計數溢出的情況。
㈨ 如何通過用數據挖掘技術來分析Web網站日誌
1、數據預處理階段根據挖掘的目的，對原始Web日誌文件中的數據進行提取、分解、合並、最後轉換為用戶會話文件。該階段是Web訪問信息挖掘最關鍵的階段，數據預處理包括:關於用戶訪問信息的預處理、關於內容和結構的預處理。
2、會話識別階段該階段本是屬於數據預處理階段中的一部分，這里將其劃分成單獨的一個階段，是因為把用戶會話文件劃分成的一組組用戶會話序列將直接用於挖掘演算法，它的精準度直接決定了挖掘結果的好壞，是挖掘過程中最重要的階段。
3、模式發現階段模式發現是運用各種方法和技術從Web日誌數據中挖掘和發現用戶使用Web的各種潛在的規律和模式。模式發現使用的演算法和方法不僅僅來自數據挖掘領域，還包括機器學習、統計學和模式識別等其他專業領域。
模式發現的主要技術有：統計分析（statistical analysis）、關聯規則（association rules）、聚類（clustering）、歸類（classification）、序列模式（sequential patterns）、依賴關系（dependency）。
（1）統計分析（statistical analysis）：常用的統計技術有：貝葉斯定理、預測回歸、對數回歸、對數-線性回歸等。可用來分析網頁的訪問頻率，網頁的訪問時間、訪問路徑。可用於系統性能分析、發現安全漏洞、為網站修改、市場決策提供支持。
（2）關聯規則（association rules）：關聯規則是最基本的挖掘技術，同時也是WUM最常用的方法。在WUM中常常用在被訪問的網頁中，這有利於優化網站組織、網站設計者、網站內容管理者和市場分析，通過市場分析可以知道哪些商品被頻繁購買，哪些顧客是潛在顧客。
（3）聚類（clustering）：聚類技術是在海量數據中尋找彼此相似對象組，這些數據基於距離函數求出對象組之間的相似度。在WUM中可以把具有相似模式的用戶分成組，可以用於電子商務中市場分片和為用戶提供個性化服務。
（4）歸類（classification）：歸類技術主要用途是將用戶資料歸入某一特定類中，它與機器學習關系很緊密。可以用的技術有：決策樹（decision tree）、K-最近鄰居、Naïve Bayesian classifiers、支持向量機（support vector machines）。
（5）序列模式（sequential patterns）：給定一個由不同序列組成的集合，其中，每個序列由不同的元素按順序有序排列，每個元素由不同項目組成，同時給定一個用戶指定的最小支持度閾值，序列模式挖掘就是找出所有的頻繁子序列，即子序列在序列集中的出現頻率不低於用戶指定的最小支持度閾值。
（6）依賴關系（dependency）：一個依賴關系存在於兩個元素之間，如果一個元素A的值可以推出另一個元素B的值，則B依賴於A。
4、模式分析階段模式分析是Web使用挖掘最後一步，主要目的是過濾模式發現階段產生的規則和模式，去除那些無用的模式，並把發現的模式通過一定的方法直觀的表現出來。由於Web使用挖掘在大多數情況下屬於無偏向學習，有可能挖掘出所有的模式和規則，所以不能排除其中有些模式是常識性的，普通的或最終用戶不感興趣的，故必須採用模式分析的方法使得挖掘出來的規則和知識具有可讀性和最終可理解性。常見的模式分析方法有圖形和可視化技術、資料庫查詢機制、數理統計和可用性分析等。
㈩ 頁面置換演算法的常見的置換演算法
最簡單的頁面置換演算法是先入先出（FIFO）法。這種演算法的實質是，總是選擇在主存中停留時間最長（即最老）的一頁置換，即先進入內存的頁，先退出內存。理由是：最早調入內存的頁，其不再被使用的可能性比剛調入內存的可能性大。建立一個FIFO隊列，收容所有在內存中的頁。被置換頁面總是在隊列頭上進行。當一個頁面被放入內存時，就把它插在隊尾上。
這種演算法只是在按線性順序訪問地址空間 時才是理想的，否則效率不高。因為那些常被訪問的頁，往往在主存中也停留得最久，結果它們因變「老」而不得不被置換出去。
FIFO的另一個缺點是，它有一種異常現象，即在增加存儲塊的情況下，反而使缺頁中斷率增加了。當然，導致這種異常現象的頁面走向實際上是很少見的。
FIFO演算法和OPT演算法之間的主要差別是，FIFO演算法利用頁面進入內存後的時間長短作為置換依據，而OPT演算法的依據是將來使用頁面的時間。如果以最近的過去作為不久將來的近似，那麼就可以把過去最長一段時間里不曾被使用的頁面置換掉。它的實質是，當需要置換一頁時，選擇在之前一段時間里最久沒有使用過的頁面予以置換。這種演算法就稱為最久未使用演算法（Least Recently Used，LRU）。
LRU演算法是與每個頁面最後使用的時間有關的。當必須置換一個頁面時，LRU演算法選擇過去一段時間里最久未被使用的頁面。
LRU演算法是經常採用的頁面置換演算法，並被認為是相當好的，但是存在如何實現它的問題。LRU演算法需要實際硬體的支持。其問題是怎麼確定最後使用時間的順序，對此有兩種可行的辦法：
1.計數器。最簡單的情況是使每個頁表項對應一個使用時間欄位，並給CPU增加一個邏輯時鍾或計數器。每次存儲訪問，該時鍾都加1。每當訪問一個頁面時，時鍾寄存器的內容就被復制到相應頁表項的使用時間欄位中。這樣我們就可以始終保留著每個頁面最後訪問的「時間」。在置換頁面時，選擇該時間值最小的頁面。這樣做， 不僅要查頁表，而且當頁表改變時（因CPU調度）要 維護這個頁表中的時間，還要考慮到時鍾值溢出的問題。
2.棧。用一個棧保留頁號。每當訪問一個頁面時，就把它從棧中取出放在棧頂上。這樣一來，棧頂總是放有目前使用最多的頁，而棧底放著目前最少使用的頁。由於要從棧的中間移走一項，所以要用具有頭尾指針的雙向鏈連起來。在最壞的情況下，移走一頁並把它放在棧頂上需要改動6個指針。每次修改都要有開銷，但需要置換哪個頁面卻可直接得到，用不著查找，因為尾指針指向棧底，其中有被置換頁。
因實現LRU演算法必須有大量硬體支持，還需要一定的軟體開銷。所以實際實現的都是一種簡單有效的LRU近似演算法。
一種LRU近似演算法是最近未使用演算法（Not Recently Used，NUR）。它在存儲分塊表的每一表項中增加一個引用位，操作系統定期地將它們置為0。當某一頁被訪問時，由硬體將該位置1。過一段時間後，通過檢查這些位可以確定哪些頁使用過，哪些頁自上次置0後還未使用過。就可把該位是0的頁淘汰出去，因為在之前最近一段時間里它未被訪問過。
4）Clock置換演算法（LRU演算法的近似實現）
5）最少使用（LFU）置換演算法
在採用最少使用置換演算法時，應為在內存中的每個頁面設置一個移位寄存器，用來記錄該頁面被訪問的頻率。該置換演算法選擇在之前時期使用最少的頁面作為淘汰頁。由於存儲器具有較高的訪問速度，例如100 ns，在1 ms時間內可能對某頁面連續訪 問成千上萬次，因此，通常不能直接利用計數器來記錄某頁被訪問的次數，而是採用移位寄存器方式。每次訪問某頁時，便將該移位寄存器的最高位置1，再每隔一定時間(例如100 ns)右移一次。這樣，在最近一段時間使用最少的頁面將是∑Ri最小的頁。
LFU置換演算法的頁面訪問圖與LRU置換演算法的訪問圖完全相同；或者說，利用這樣一套硬體既可實現LRU演算法，又可實現LFU演算法。應該指出，LFU演算法並不能真正反映出頁面的使用情況，因為在每一時間間隔內，只是用寄存器的一位來記錄頁的使用情況，因此，訪問一次和訪問10 000次是等效的。
6）工作集演算法
7）工作集時鍾演算法
8）老化演算法（非常類似LRU的有效演算法）
9）NRU(最近未使用）演算法
10）第二次機會演算法
第二次機會演算法的基本思想是與FIFO相同的，但是有所改進，避免把經常使用的頁面置換出去。當選擇置換頁面時，檢查它的訪問位。如果是 0，就淘汰這頁；如果訪問位是1，就給它第二次機會，並選擇下一個FIFO頁面。當一個頁面得到第二次機會時，它的訪問位就清為0，它的到達時間就置為當前時間。如果該頁在此期間被訪問過，則訪問位置1。這樣給了第二次機會的頁面將不被淘汰，直至所有其他頁面被淘汰過（或者也給了第二次機會）。因此，如果一個頁面經常使用，它的訪問位總保持為1，它就從來不會被淘汰出去。
第二次機會演算法可視為一個環形隊列。用一個指針指示哪一頁是下面要淘汰的。當需要一個 存儲塊時，指針就前進，直至找到訪問位是0的頁。隨著指針的前進，把訪問位就清為0。在最壞的情況下，所有的訪問位都是1，指針要通過整個隊列一周，每個頁都給第二次機會。這時就退化成FIFO演算法了。
