內存塊分配算法和抖動問題

1、內存塊分配算法和抖動問題2010-03-23 18:531 內存塊分配算法1.1 最少內存塊數分配給進程的內存塊數目是受到限制的，分配的總塊數不能超出可用塊的總量（除非存在頁共享的情況）。另一方面，每個進程也需要有起碼最少的塊數。很顯然，隨著分給每個進程塊數的減少，缺頁率將上升，降低了進程的執(zhí)行速度。分給每個進程的最少塊數是指能保證進程正常運行所需的最少內存數，它是由指令集結構決定的。因為正在執(zhí)行的指令被完成之前出現(xiàn)缺頁時，該指令必須被重新啟動，與此相應，必須有足夠的塊把一條指令所訪問的各個頁都存放起來。而每個進程的最多塊數是由可用內存的總量決定的。1.2 固定分配和可變分配請求分頁系統(tǒng)支持虛

2、擬存儲器，可以采用兩種內存塊分配策略，即固定分配和可變分配。（1）固定分配策略是分配給進程的內存塊數是固定的，并在最初裝入時（即進程創(chuàng)建時）確定塊數。分給每個進程的內存塊數基于進程類型（交互式、批處理型、應用程序型等），或者由程序員或系統(tǒng)管理員提出 的建議。當進程執(zhí)行過程中出現(xiàn)缺頁時，只能從分給該進程的內存塊中進行頁面置換。（2）可變分配策略允許分給進程的內存塊數隨進程的活動而改變。如果一個進程在運行過程中持續(xù)缺頁率太高，這就表明該進程的局部化行為不好，需要給它分配另外的內存塊，以減少它的缺頁率。如果一個進程的缺頁率特別低，就可以減少分配的內存塊，但不要顯著增加缺頁率。可變分配策略的功能更強，

3、但需要操作系統(tǒng)估價出各活動進程的行為，這就增加了操作系統(tǒng)的軟件開銷，并且依賴于處理器平臺所提供的硬件機制。1.3 全局置換與局部置換內存塊分配的另一個重要問題是頁面置換范圍。多個進程競爭內存塊時，可以把頁面置換分為兩種主要類型：全局置換和局部置換。全局置換允許一個進程從全體存儲塊的集合中選取置換塊，盡管該塊當前已分給其他進程，但還是能強行剝奪。而局部置換是每個進程只能從分給它的一組塊中選擇置換塊。采用局部置換策略，分給進程的塊數是不能變更的。采用全局置換策略，一個進程可以只從分給其他進程的塊里挑選。這樣，如果沒有別的進程挑選它的塊，那么分給該進程的塊數就增加了?？梢杂梢粋€核心進程專門負責頁面置

4、換工作。全局置換算法存在的一個問題是，程序無法控制自己的缺頁率。一個進程在內存中的一組頁面不僅取決于該進程的頁面走向，而且也取決于其他進程的頁面走向。因此，相同程序由于外界環(huán)境不同會造成執(zhí)行上的很大差別。使用局部置換算法就不會出現(xiàn)這種情況，一個進程在內存中的頁面僅受本進程頁面走向的影響。1.4 內存塊分配算法為每個進程分配內存塊的算法主要有三種：等分法、比例法和優(yōu)先權法。（1）等分法為每個進程分配存儲塊的最簡單的辦法是平分，即若有m塊、n個進程，則每個進程分m/n塊（其值向下取整）。等分法不區(qū)分具體進程的需求，“一視同仁”地進行分配。其結果造成：有的進程用不了那么多塊，而另外進程卻遠遠不夠用。

5、為解決這個問題，可采取按需成比例分配的辦法。（2）比例法分給進程的塊數=進程地址空間大小 / 全部進程的總地址空間 * 可用塊總數上述兩種情況下，分給每個進程的塊數依據多道程序數目而變。多道程序數增加了，每個進程就要少分一些塊。相反，多道程序數少了，分給每個進程的塊數可多一些。（3）優(yōu)先權法在上面兩種算法中沒有考慮優(yōu)先級問題，即把高優(yōu)先級進程和低優(yōu)先級進程一樣對待。為加速高優(yōu)先級進程的執(zhí)行，可以給高優(yōu)先級進程分較多內存。如使用比例分配法時，分給進程的塊數不僅取決于程序的相對大小，而且也取決于優(yōu)先級的高低。2 抖動（Thrashing）問題置換算法的優(yōu)劣，直接影響到系統(tǒng)的效率。若選用算法不合適，

6、可能會出現(xiàn)這種現(xiàn)象：剛被置換出去的頁，很快又要訪問，因而要把它重新調入；可是調入不久又再次被置換出去，這樣再訪問、再調入，如此反復，使得整個系統(tǒng)的頁面替換非常頻繁，以致大部分的機器時間都花在來回進行的頁面調度上，只有一小部分時間用于進程的實際運算。這種局面就稱為系統(tǒng)“抖動”。產生抖動的原因是系統(tǒng)中多道程序度過高，進程運行缺頁率嚴般情況下，在多道程序度較小時，隨著它的增加，CPU利用率會緩慢增加。當到達最大值后，多道程序度進一步增大，就出現(xiàn)了抖動，導致CPU利用率急劇下降。防止抖動發(fā)生或者限制抖動影響的方法有多種，但一般都基于調節(jié)多道程序度。（1）采用局部置換策略。如果一個進程出現(xiàn)抖動，它不能從

7、另外的進程那里奪取內存塊，從而不會引發(fā)其他進程出現(xiàn)抖動，使抖動局限于一個小的范圍內。然而這種方法并未消除抖動的發(fā)生，而且在一些進程發(fā)生抖動的情況下，等待磁盤I/O的進程增多，使得平均缺頁處理時間加長，從而延長了有效存取時間。（2）利用工作集策略防止抖動。（3）掛起某些進程。當出現(xiàn)CPU利用率、而磁盤I/O非常頻繁的情況時，就可能因為多道程序度太高而造成抖動。為此，可掛起一個或幾個進程，以便騰出內存空間供抖動進程使用，從而消除抖動現(xiàn)象。被掛起進程的選擇策略有多種，如優(yōu)先權最低的進程、缺頁進程、最近激活的進程、駐留集最小的進程和最大的進程等。（4）采用缺頁頻度法（PFF，Page Fault Fr

8、equency）。抖動發(fā)生時缺頁率必然很高。這樣，通過控制缺頁率就可預防抖動。當缺頁率太高時，表明進程需要更多的內存塊。反之，如果缺頁率很低，表示進程可能占用的內存塊太多。規(guī)定一個缺頁率，依此設置相應的上限和下限。如果實際缺頁率超出上限值，就為該進程分配另外的內存塊；如果實際缺頁率低于下限值，就從該進程的駐留集中取走一個內存塊。通過直接測量和控制缺頁率，就可以預防抖動。3 工作集一個頁面置換算法的好壞與進程運行的頁面走向有很大的關系。虛擬存儲系統(tǒng)的有效操作依賴于程序中訪問的局部化程度。對于LRU算法而言，局部化程度愈突出，進程運行效率愈高。局部化可分為兩類：時間局部化和空間局部化。時間局部化是指一旦某條指令或數據被訪問了，它常常很快又被再次訪問，如程序中的循環(huán)部分?？臻g局部化指的是一旦某個位置被訪問到，那么它附近的位置也可能很快要用到，如程序中的順序指令串。這種情況反映在頁面走向上，就是在任何一小段時間里，進程運行只集中于訪問某幾頁。工作集就是一個進程在某一小段時間內訪問頁面的集合。它是程序局部性的近似表示。操作系統(tǒng)監(jiān)督每個進程的工作集并給它分配足夠工作集所需的內存塊。