系統分頁演算法

A. 計算機操作系統分頁問題

與分頁有關的工作

操作系統在四段時間里做與分頁有關的工作：進程創建時，進程執行時，缺頁中斷時和進程終止時。

當在分頁系統中創建一個一個新進程時，操作系統需要確定該進程的程序和數據在初始時有多大，並為它們創建一個頁表。操作系統還要在內存中為頁表分配空間並對其進行初始化。當進程被換出時，頁表不需要駐留在內存中，但當進程運行時，頁表必須在內存中。

另外，操作系統要在磁碟交換區中分配空間，以便在一個進程換出時在磁碟上有放置此進程的空間。操作系統還要用程序正文和數據對交換區進程初始化，這樣當新進程發生缺頁中斷時，可以調入需要的頁面。某些操作系統直接從磁碟上的可執行文件對程序正文進行分頁，以節省磁碟空間和初始化時間。

最後，操作系統必須把有關頁表和磁碟交換區的信息存儲在進程表中。

當調度一個進程執行時，必須為新進程重置MMU，刷新TLB，以清除以前的進程遺留下的痕跡。

當缺頁中斷發生時，操作系統必須通過讀硬體寄存器來確定是哪個虛擬地址造成的缺頁中斷。並計算出需要的頁面以及要替換的老的頁面。最後，還要備份程序計數器，使其指向引起缺頁終端的指令，並重新執行該指令。

當進程退出的時候，操作系統需要釋放進程的頁表，頁面和頁面在硬碟上所佔用的空間。但如果有些頁面是被共享的，那隻有當所有使用共享頁面的進程終止時，該共享頁面才會被釋放。

2. 缺頁中斷處理

缺頁中斷時，發生的的事件順序如下：

硬體陷入內核，在堆棧中保存程序計數器。大多數機器將當前指令的各種狀態信息保存在特殊的CPU寄存器中。

啟動一個匯編代碼常式保存通用寄存器和其他易失的消息，以免被操作系統破壞。

當操作系統發現一個缺頁中斷時，嘗試發現需要哪個虛擬頁面。通常一個硬體寄存器包含了這以信息，如果沒有的話，操作系統必須檢索程序計數器，取出這條指令，用軟體分析這條指令，看看它在缺頁中斷時正在做什麼。

一旦知道了發生缺頁中斷的虛擬地址，操作系統檢查這個地址是否有效，並檢查存取與保護是否一致。如果不一致，向進程發出一個信號或殺掉該進程。如果地址有效且沒有保護錯誤發生，系統則檢查是否有空閑頁框。如果沒有空閑頁框，執行頁面置換演算法尋找一個頁面來淘汰。

如果選擇的頁框被修改過了，安排該頁寫回磁碟，並發生一次上下文切換，掛起產生缺頁中斷的進程，讓其他進程運行直至磁碟傳輸結束。無論如何，該頁框被標記為忙，以免因為其他原因而被其他進程佔用。

一旦頁框干凈後，操作系統查找所需頁面的在磁碟上的地址，通過磁碟操作將其裝入。該頁面被裝入後，產生缺頁中斷的進程仍然被掛起，並且如果有其他可運行的用戶進程，則選擇另一個用戶進程運行。

當磁碟中斷發生時，表明該頁已經被裝入，頁表已經更新可以反映它的位置，頁框也被標記為正常狀態。

恢復發生缺頁中斷指令以前的狀態，程序計數器重新指向這條指令。

調度引發缺頁中斷的進程，操作系統返回調用它的匯編語言常式。

該常式恢復寄存器和其他狀態信息，返回到用戶空間繼續執行，就好像缺頁中斷沒有發生過一樣。

B. sql的幾種分頁演算法

利用SQL語句分頁要看你用的什麼資料庫。
Oracle資料庫可以使用ROWNUM或row_number()，例如：Select * from (select ROWNUM rn, t.* from table t) where rn between 11 and 20;
Select * from (select row_number() over (ORDER BY col1) rn, t.* from table t) where rn between 11 and 20;
SQLServer資料庫可以用Top或者row_number()函數，道理同上。
利用SQL分頁有局限性，就是針對不同的資料庫有不同的寫法，所以通常會在應用程序裡面做分頁通用性比較強。但是對於數據量非常龐大的應用來說，還是用SQL分頁比較適合。

C. 請教一個分頁邏輯

對於分頁，其實只需要總記錄數totalCount、每頁顯示記錄數（一般是一個常量）pageRecords、當前瀏覽到的頁數curPage就可以完成對其餘分頁相關的屬性的計算。
totalCount：select count(*) from tableName where ...
總頁數：totalCont/pageRecords，此時需要做一個判斷，如果余數大於零，需要在商的結果上+1
起始記錄索引：pageRecoords*(curPage-1)+1
終止記錄索引：pageRecoords*curPage
註：上述的起止索引是以從1開始的演算法，根據資料庫實際情況進行調整。

相信有了上述幾個數據，其餘的功能也就是把這些數據匯總利用一下的事情了。

D. 操作系統中什麼是分頁過程

3．請求分頁系統(1)請求分頁對頁表的擴充
在請求分頁系統中所使用的主要數據結構仍然是頁表。它對頁式系統中的頁表機制進行了擴充但其基本作用是實現由用戶地址空間到物理內存空間的映射。由於只將應用程序的一部分裝入內存，還有一部分仍在磁碟上，故需在頁表中增加若干項，供操作系統實現虛擬存儲器功能時參考。常見的系統中，一般對頁表的表項進行如下擴充：除了頁號對應的物理塊號，還增加了狀態位、修改位、外存地址和訪問欄位等。
·狀態位，用於指示該頁是否已經調入了內存。該位一般由操作系統軟體來管理，每當操作系統把一頁調人物理內存中時，置位。相反，當操作系統把該頁從物理內存調出時，復位。CPU對內存進行引用時，根據該位判斷要訪問的頁是否在內存中，若不在內存之中，則產生缺頁中斷。
·修改位，表示該頁調入內存後是否被修改過。當CPU以寫的方式訪問頁面時，對該頁表項中的修改位置位。該位也可由操作系統軟體來修改，例如，當操作系統將修改過頁面保存在磁碟上後，可將該位復位。
·外存地址，用於指出該頁在外存上的地址，供調人該頁時使用。
·訪問宇段，用於記錄本頁在一定時間內被訪問的次數，或最近已經有多長時間未被訪問。提供給相應的置換演算法在選擇換出頁面時參考。
(2)對缺頁中斷的支持
在請求分頁系統中，CPU硬體一定要提供對缺頁中斷的支持，根據頁表項中的狀態位判斷是否產生缺頁中斷。缺頁中斷是一個比較特殊的中斷，這主要體現在如下兩點：
·在指令的執行期間產生和處理缺頁信號。通常的CPU外部中斷，是在每條指令執行完畢後檢查是否有中斷請求到達。而缺頁中斷，是在一條指令的執行期間，發現要訪問的指令和數據不在內存時產生和處理的。
·一條指令可以產生多個缺頁中斷。例如，一條雙操作數的指令，每個操作數都不在內存中，這條指令執行時，將產生兩個中斷。CPU提供的硬體支持，還要體現在當從中斷處理程序返回時，能夠正確執行產生缺頁中斷的指令。
(3)頁面調度策略
虛擬存儲器系統通常定義三種策略來規定如何(或何時)進行頁面調度：調入策略、置頁策略和置換策略。
(4)置換演算法(replacementalgorithm)決定在需要調入頁面時，選擇內存中哪個物理頁面被置換。置換演算法的出發點應該是，把未來不再使用的或短期內較少使用的頁面調出。而未來的實際情況是不確定的，通常只能在局部性原理指導下依據過去的統計數據進行預測。常用的演算法有以下幾種：
·最佳演算法(optimal，OPT)。選擇「未來不再使用的」或「在離當前最遠位置上出現的」頁面被置換。這是一種理想情況，是實際執行中無法預知的，因而不能實現，只能用作性能評價的依據。
·最近最久未使用演算法(LeastRecentlyUsed，LRU)。選擇內存中最久未使用的頁面被置換，這是局部性原理的合理近似，性能接近最佳演算法。但由於需要記錄頁面使用時間的先後關系，硬體開銷太大。LRU可用如下的硬體機構幫助實現：
一個特殊的棧：把被訪問的頁面移到棧頂，於是棧底的是最久未使用頁面。每個頁面設立移位寄存器：被訪問時左邊最高位置1，定期右移並且最高位補0，於是寄存器數值最小的是最久未使用頁面。
·先進先出演算法(FIFO)。選擇裝入最早的頁面置換。可以通過鏈表來表示各頁的裝入時間先後。FIFO的性能較差，因為較早調入的頁往往是經常被訪問的頁，這些頁在FIFO演算法下被反復調入和調出，並且有Belady現象。所謂Belady現象是指：採用FIFO演算法時，如果對—個進程未分配它所要求的全部頁面，有時就會出現分配的頁面數增多但缺頁率反而提高的異常現象。Belady現象可形式化地描述為：一個進程戶要訪問M個頁，OS分配艫個內存頁面給進程P；對一個訪問序列S，發生缺頁次數為PE(占，N)。當N增大時，PE(S，N)時而增大時而減小。Belady現象的原因是FIFO演算法的置換特徵與進程訪問內存的動態特徵是矛盾的，即被置換的頁面並不是進程不會訪問的。
·時鍾(clock)演算法。也稱最近未使用演算法(NotRecentlyUsed，NRU)，它是LRU和FIFO的折中。每頁有一個使用標志位(usebit)，若該頁被訪問則置userbit=l，這是由CPU的硬體自動完成的。置換時採用一個指針，從當前指針位置開始按地址先後檢查各頁，尋找usebit=0的面作為被置換頁。指針經過的userbit=l的頁都修改userbit=O，這個修改的過程是操作系統完成的，最後指針停留在被置換頁的下一個頁。
·最不常用演算法(LeastFrequentlyUsed，LFU)。選擇到當前時間為止被訪問次數最少的頁面被置換。每頁設置訪問計數器，每當頁面被訪問時，該頁面的訪問計數器加1。發生缺頁中斷時，淘汰計數值最小的頁面，並將所有計數清零。
·頁面緩沖演算法(pagebuffering)。它是對FIFO演算法的發展，通過建立置換頁面的緩沖，這樣就有機會找回剛被置換的頁面，從而減少系統I／0的開銷。頁面緩沖演算法用FIFO演算法選擇被置換頁，把被置換的頁面放人兩個鏈表之一。即是如果頁面未被修改，就將其歸人到空閑頁面鏈表的末尾，否則將其歸人到已修改頁面鏈表。空閑頁面和已修改頁面，仍停留在內存中一段時間，如果這些頁面被再次訪問，只需較小開銷，被訪問的頁面就可以返還作為進程的內存頁。需要調入新的物理頁面時，將新頁面內容讀人到空閑頁面鏈表的第一項所指的頁面，然後將第一項刪除。當已修改頁面達到一定數目後，再將它們一起調出到外存，然後將它們歸人空閑頁面鏈表。這樣能大大減少I／O操作的次數。

E. 在請求分頁系統中，常採用哪幾種頁面置換演算法

理想頁面置換演算法、先進先出頁面置換演算法、最近最少使用頁面置換演算法。

F. 操作系統頁面置換演算法：第二次機會演算法是什麼

第二次機會演算法：

與FIFO、OPT、LRU、NRU等同為操作系統中請求分頁式管理方式的頁面置換演算法。

第二次機會演算法的基本思想是與FIFO相同的，但是有所改進，避免把經常使用的頁面置換出去。當選擇置換頁面時，依然和FIFO一樣，選擇最早置入內存的頁面。但是二次機會法還設置了一個訪問狀態位。所以還要檢查頁面的的訪問位。如果是0，就淘汰這頁；如果訪問位是1，就給它第二次機會，並選擇下一個FIFO頁面。當一個頁面得到第二次機會時，它的訪問位就清為0，它的到達時間就置為當前時間。如果該頁在此期間被訪問過，則訪問位置為1。這樣給了第二次機會的頁面將不被淘汰，直至所有其他頁面被淘汰過（或者也給了第二次機會）。因此，如果一個頁面經常使用，它的訪問位總保持為1，它就從來不會被淘汰出去。

第二次機會演算法可視為一個環形隊列。用一個指針指示哪一頁是下面要淘汰的。當需要一個存儲塊時，指針就前進，直至找到訪問位是0的頁。隨著指針的前進，把訪問位就清為0。在最壞的情況下，所有的訪問位都是1，指針要通過整個隊列一周，每個頁都給第二次機會。這時就退化成FIFO演算法了。

G. 在請求分頁系統中，LRU演算法是指（ ）。

B這個演算法 ，就是類似於LRU演算法。選擇B

H. php 分頁演算法

這是我以前用的分頁，你看看吧，希望能幫到你。

<html>
<head>
<title>分頁</title>
</head>
<body>
<table align="center" border="1" width="500">
<tr>
<td>編號</td>
<td>用戶名</td>
<td>密碼</td>
<td>郵箱</td>
</tr>

<?php
$conn=mysql_connect("localhost","root","");
mysql_set_charset("utf8",$conn);
$db = mysql_select_db("bbs",$conn);
$rs = mysql_query("select * from userInfo");

$totalRow = mysql_num_rows($rs);//總記錄數
$currentPage = $_GET["currentPage"];//當前頁
if($currentPage == null){
$currentPage = 1;
}
$pageSize = 3;//每頁顯示的記錄數
$first = ($currentPage-1)*$pageSize;//起始值
$last = $first + $pageSize;//結束值
$totalPage = ceil($totalRow / $pageSize);//總頁數

if($last > $totalRow)
{
$last = $totalRow;
}
for($i=$first;$i<$last;$i++)
{
mysql_data_seek($rs,$i);//定位游標
$row = mysql_fetch_array($rs);
echo "<tr>";
echo " <td>{$row[0]}</td>";
echo " <td>{$row[1]}</td>";
echo " <td>{$row[2]}</td>";
echo " <td>{$row[3]}</td>";
echo "</tr>";
}
mysql_free_result($rs);
mysql_close($conn);
?>

<tr>
<td colspan="4" align="center">
<?php
if($currentPage == 1)
{
echo "首頁上一頁";
}
else
{
?>
<a href="fenye.php?currentPage=1">首頁</a>
<a href="fenye.php?currentPage=<?php echo $currentPage-1 ?>">上一頁</a>
<?php
}
if($currentPage == $totalPage)
{
echo "下一頁尾頁";
}
else
{
?>
<a href="fenye.php?currentPage=<?php echo $currentPage+1 ?>">下一頁</a>
<a href="fenye.php?currentPage=<?php echo $totalPage ?>">尾頁</a>
<?php
}
?>

<td>
</tr>
</table>
</body>
</html>

I. 關於Java的分頁演算法，急！

你想效率高 你就直接使用jdbc連接資料庫，然後自己封裝一個標簽，結合servlet做自己的分頁標簽

J. 分頁存儲管理的實現原理

採用分頁存儲器允許把一個作業存放到若干不相鄰的分區中，既可免去移動信息的工作，又可盡量減少主存的碎片。分頁式存儲管理的基本原理如下：

1、 頁框：物理地址分成大小相等的許多區，每個區稱為一塊；
2、址分成大小相等的區，區的大小與塊的大小相等，每個稱一個頁面。
3、 邏輯地址形式：與此對應，分頁存儲器的邏輯地址由兩部分組成，頁號和單元號。邏輯地址格式為 頁號 單元號（頁內地址） 採用分頁式存儲管理時，邏輯地址是連續的。所以，用戶在編製程序時仍只須使用順序的地址，而不必考慮如何去分頁。

4、頁表和地址轉換：如何保證程序正確執行呢？
採用的辦法是動態重定位技術，讓程序的指令執行時作地址變換，由於程序段以頁為單位，所以，我們給每個頁設立一個重定位寄存器，這些重定位寄存器的集合便稱頁表。頁表是操作系統為每個用戶作業建立的，用來記錄程序頁面和主存對應頁框的對照表，頁表中的每一欄指明了程序中的一個頁面和分得的頁框的對應關系。絕對地址=塊號*塊長+單元號 以上從拓撲結構角度分析了對稱式與非對稱式虛擬存儲方案的異同,實際從虛擬化存儲的實現原理來講也有兩種方式;即數據塊虛擬與虛擬文件系統. 數據塊虛擬存儲方案著重解決數據傳輸過程中的沖突和延時問題.在多交換機組成的大型Fabric結構的SAN中,由於多台主機通過多個交換機埠訪問存儲設備,延時和數據塊沖突問題非常嚴重.數據塊虛擬存儲方案利用虛擬的多埠並行技術,為多台客戶機提供了極高的帶寬,最大限度上減少了延時與沖突的發生,在實際應用中,數據塊虛擬存儲方案以對稱式拓撲結構為表現形式. 虛擬文件系統存儲方案著重解決大規模網路中文件共享的安全機制問題.通過對不同的站點指定不同的訪問許可權,保證網路文件的安全.在實際應用中,虛擬文件系統存儲方案以非對稱式拓撲結構為表現形式. 虛擬存儲技術,實際上是虛擬存儲技術的一個方面,特指以CPU時間和外存空間換取昂貴內存空間的操作系統中的資源轉換技術 基本思想:程序,數據,堆棧的大小可以超過內存的大小,操作系統把程序當前使用的部分保留在內存,而把其他部分保存在磁碟上,並在需要時在內存和磁碟之間動態交換,虛擬存儲器支持多道程序設計技術 目的:提高內存利用率 管理方式
A 請求式分頁存儲管理 在進程開始運行之前,不是裝入全部頁面,而是裝入一個或零個頁面,之後根據進程運行的需要,動態裝入其他頁面;當內存空間已滿,而又需要裝入新的頁面時,則根據某種演算法淘汰某個頁面,以便裝入新的頁面

B 請求式分段存儲管理 為了能實現虛擬存儲,段式邏輯地址空間中的程序段在運行時並不全部裝入內存,而是如同請求式分頁存儲管理,首先調入一個或若干個程序段運行,在運行過程中調用到哪段時,就根據該段長度在內存分配一個連續的分區給它使用.若內存中沒有足夠大的空閑分區,則考慮進行段的緊湊或將某段或某些段淘汰出去,這種存儲管理技術稱為請求式分段存儲管理