當前位置:首頁 » 操作系統 » 夥伴演算法

夥伴演算法

發布時間: 2022-08-07 01:11:14

『壹』 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位元組的對象叫做小對象。

『貳』 基於夥伴堆演算法的內存分配/釋放的模擬實現

夥伴演算法把所有的空閑頁面分為10個塊組,每組中塊的大小是2的冪次方個頁面,例如,第0組中塊的大小都為20 (1個頁面),第1組中塊的大小為都為21(2個頁面),第9組中塊的大小都為29(512個頁面)。也就是說,每一組中塊的大小是相同的,且這同樣大小的塊形成一個鏈表。

我們通過一個簡單的例子來說明該演算法的工作原理。

假設要求分配的塊其大小為128個頁面(由多個頁面組成的塊我們就叫做頁面塊)。該演算法先在塊大小為128個頁面的鏈表中查找,看是否有這樣一個空閑塊。如果有,就直接分配;如果沒有,該演算法會查找下一個更大的塊,具體地說,就是在塊大小為256個頁面的鏈表中查找一個空閑塊。如果存在這樣的空閑塊,內核就把這256個頁面分為兩等份,一份分配出去,另一份插入到塊大小為128個頁面的鏈表中。如果在塊大小為256個頁面的鏈表中也沒有找到空閑頁塊,就繼續找更大的塊,即512個頁面的塊。如果存在這樣的塊,內核就從512個頁面的塊中分出128個頁面滿足請求,然後從384個頁面中取出256個頁面插入到塊大小為256個頁面的鏈表中。然後把剩餘的128個頁面插入到塊大小為128個頁面的鏈表中。如果512個頁面的鏈表中還沒有空閑塊,該演算法就放棄分配,並發出出錯信號。

『叄』 簡述內存管理中buddy演算法和slab機制的區別

1、Buddy演算法
linux對空閑內存空間管理採取buddy演算法,
Buddy演算法:
把內存中所有頁面按照2^n劃分,其中n=0~5,每個內存空間按1個頁面、2個頁面、4個頁面、8個頁面、16個頁面、32個頁面進行六次劃分。劃分後形成了大小不等的存儲塊,稱為頁面塊,簡稱頁塊,包含一個頁面的頁塊稱為1頁塊,包含2個頁面的稱為2頁塊,依次類推。
每種頁塊按前後順序兩兩結合成一對Buddy「夥伴」。系統按照Buddy關系把具有相同大小的空閑頁面塊組成頁塊組,即1頁塊組、2頁塊組……32頁塊組。 每個頁塊組用一個雙向循環鏈表進行管理,共有6個鏈表,分別為1、2、4、8、16、32頁塊鏈表。分別掛到free_area[] 數組上。
點陣圖數組
用於標記內存頁面使用情況,第0組每一位表示單個頁面使用情況,1表示使用,0表示空閑,第二組每一位表示比鄰的兩個頁面使用情況,一次類推。默認為10個數組,當一對Buddy的兩個頁面中有一個事空閑的,而另一個全部或部分被佔用時,該位置1.兩個頁面塊都是空閑,對應位置0.
內存分配和釋放過程
內存分配時,系統按照Buddy演算法,根據請求的頁面數在free_area[]對應的空閑頁塊組中搜索。 若請求頁面數不是2的整數次冪,則按照稍大於請求數的2的整數次冪的值搜索相應的頁面塊組。
當相應頁塊組中沒有可使用的空閑頁面塊時就查詢更大一些的頁塊組,在找到可用的頁塊後分配所需要的頁面。當某一空閑頁面被分配後,若仍有剩餘的空閑頁面,則根據剩餘頁面的大小把他們加入到相應頁面組中。
內存頁面釋放時,系統將其作為空閑頁面看待,檢查是否存在與這些頁面相鄰的其他空閑頁塊,若存在,則合為一個連續的空閑區按Buddy演算法重新分組。

2、Slab演算法
採用buddy演算法,解決了外碎片問題,這種方法適合大塊內存請求,不適合小內存區請求。如:幾十個或者幾百個位元組。Linux2.0採用傳統內存分區演算法,按幾何分布提供內存區大小,內存區以2的冪次方為單位。雖然減少了內碎片,但沒有顯著提高系統效率。
Linux2.4採用了slab分配器演算法,該演算法比傳統的分配器演算法有更好性能和內存利用率,最早在solaris2.4上使用。
Slab分配器思想
1)小對象的申請和釋放通過slab分配器來管理。
2)slab分配器有一組高速緩存,每個高速緩存保存同一種對象類型,如i節點緩存、PCB緩存等。
3)內核從它們各自的緩存種分配和釋放對象。
4)每種對象的緩存區由一連串slab構成,每個slab由一個或者多個連續的物理頁面組成。這些頁面種包含了已分配的緩存對象,也包含了空閑對象。

『肆』 C#中buddy是什麼意思

buddy演算法是用來做內存管理的經典演算法,目的是為了解決內存的外碎片。

『伍』 buddy演算法到底是10個鏈表還是11個鏈表

還是11個鏈表

『陸』 BUDDY演算法的C++實現

簡介
http://www.csie.nctu.e.tw/~tcwu/doc/Linux/Kernel/chapter3/chapter3.htm
source
http://blog.csdn.net/VIV777/archive/2007/07/05/1680363.aspx
基本上用
Linux kernel memory management buddy system

MIPS memory management buddy system
作為關鍵字去搜尋就可以找到很多訊息

『柒』 操作系統一般對用戶空間採用分頁管理而對內核對象採用 slab 分配器,為什麼

採用夥伴演算法分配內存時,每次至少分配一個頁面。但當請求分配的內存大小為幾十個位元組或幾百個位元組時應該如何處理?如何在一個頁面中分配小的內存區,小內存區的分配所產生的內碎片又如何解決? Linux2.0採用的解決辦法是建立了13個空閑區鏈表,...

『捌』 操作系統對外存的管理能使用夥伴演算法嗎

一、單項選擇題(每題1分,共20分) 1.操作系統的發展過程是( C ) C、管理程序,原始操作系統,操作系統 2.用戶程序中的輸入、輸出操作實際上是由(B、操作系統 )完成。 3.進程調度的對象和任務分別是( C )。 C、進程,從就緒隊列中按一定的調度策略選擇一個進程佔用CPU 4.支持程序浮動的地址轉換機制是( A、動態重定位 ) 5.在可變分區存儲管理中,最優適應分配演算法要求對空閑區表項按(C、尺寸從小到大)進行排列。 6.設計批處理多道系統時,首先要考慮的是( 系統效率和吞吐量 )。 7.當進程因時間片用完而讓出處理機時,該進程應轉變為( b )狀態。 A、等待 B、就緒 C、運行 D、完成 8.文件的保密是指防止文件被( c )。 A、篡改 B、破壞 C、竊取 D、刪除 9.若系統中有五個並發進程涉及某個相同的變數A,則變數A的相關臨界區是由( d ) 臨界區構成。 A、2個 B、3個 C、4個 D、5個 10.按邏輯結構劃分,文件主要有兩類:(記錄式文件 )和流式文件。 A、記錄式文件 B、網狀文件 C、索引文件 D、流式文件 11.UNIX中的文件系統採用(、流式文件 )。 A、網狀文件 B、記錄式文件 C、索引文件 D、流式文件 12.文件系統的主要目的是(A、實現對文件的按名存取 )。 13.文件系統中用( D、目錄 )管理文件。 14.為了允許不同用戶的文件具有相同的文件名,通常在文件系統中採用(B、多級目 錄 )。 15.在多進程的並發系統中,肯定不會因競爭(C、CPU )而產生死鎖。 16.一種既有利於短小作業又兼顧到長作業的作業調度演算法是( C、最高響應比優先 )。17.兩個進程合作完成一個任務。在並發執行中,一個進程要等待其合作夥伴發來消息,或 者建立某個條件後再向前執行,這種制約性合作關系被稱為進程的( B、同步 )。18.當每類資源只有一個個體時,下列說法中不正確的是( )。 A、有環必死鎖 B、死鎖必有環 C、有環不一定死鎖 D、被鎖者一定全在環中 19.數據文件存放在到存儲介質上時,採用的邏輯組織形式是與(A、文件邏輯結構 ) 有關的。 20.在單處理器的多進程系統中,進程什麼時候佔用處理器和能佔用多長時間,取決於(B、進程自身和進程調度策略 )。 二、填空題(每空2分,共20分) 1.若信號量S的初值定義為10,則在S上調用了16次P操作和15次V操作後S的值應 該為( 9 )。 2.進程調度的方式通常有(搶占 )和(非搶占)兩種方式。 3.每個索引文件都必須有一張( 索引結點 )表,其中的地址登記項用來指出文件在外存 上的位置信息。 4.在一請求分頁系統中,假如一個作業的頁面走向為:4、3、2、1、4、3、5、4、3、2、1、 5,當分配給該作業的物理塊數為4時(開始時沒有裝入頁面),採用LRU頁面淘汰演算法將產生( 8 )次缺頁中斷。 5.信號量被廣泛用於三個目的是( 同步 )、( 互斥 )和描述前趨關系。 6.程序並發執行時的特徵是( 間斷性 )、( 失去了封閉性 )、( 不可再現性 )和獨立性。 三、判斷題(每題1分,共10分) ( T )1.文件系統中分配存儲空間的基本單位不是記錄。 ( F )2.具有多道功能的操作系統一定是多用戶操作系統。 ( T )3.虛擬存儲器是由操作系統提供的一個假想的特大存儲器,它並不是實際的內存,其大小可比內存空間大得多。 ( T )4.批處理系統的(主要優點)是系統的吞吐量大、資源利用率高、系統的開銷較小。 ( F )5.文件系統中源程序是有結構的記錄式文件。 ( F )6.即使在多道程序環境下,普通用戶也能設計用內存物理地址直接訪問內存的程序。 ( F )7.順序文件適合建立在順序存儲設備上,而不適合建立在磁碟上。 ( T )8.SPOOLing系統實現設備管理的虛擬技術,即:將獨占設備改造為共享設備。它由專門負責I/O的常駐內存進程以及輸入、輸出井組成。 ( F )9.系統調用是操作系統與外界程序之間的介面,它屬於核心程序。在層次結構設計中,它最靠近硬體。 ( F )10.若系統中存在一個循環等待的進程集合,則必定會死鎖。 四、程序與演算法(共10分) 設有一緩沖池P,P中含有20個可用緩沖區,一個輸入進程將外部數據讀入P,另有一 個輸出進程將P中數據取出並輸出。若講程每次操作均以一個緩沖區為單位,試用記錄型信號量寫出兩個進程的同步演算法,要求寫出信號量的初值。 解: semaphore mutex=1; semaphore empty=20; semaphore full=0; int in,out = 0; item p [20]; void Procer(){ while(ture){ procer an item in nextp; wait(empty); wait(mutex); p[in] := nextp; in := (in+1) mod 20; signal(mutex); signal(full); } } void Consumer(){ while(ture){ wait(full); wait(mutex); nextc := p[out]; out := (out+1) mod 20; signal(mutex); signal(empty); } } 五、問答題(共16分) 某系統有A、B、C、D四類資源可供五個進程P1、P2、P3、P4、P5共享。系統對這四類資源的擁有量為:A類3個、B類14個、C類12個、D類12個。進程對資源的需求和分配 情況如下: 按銀行家演算法回答下列問題: (1)現在系統中的各類資源還剩餘多少?(4分) (2)現在系統是否處於安全狀態?為什麼?(6分) (3)如果現在進程P2提出需要A類資源0個、B類資源4個、C類資源2個和D類資源0個,系統能否去滿足它的請求?請說明原因。(6) (1)A:1;B:5;C:2;D:0 (2)need矩陣為:P1 0 0 0 0 P2 0 7 5 0 P3 1 0 0 2 P4 0 0 2 0 P5 0 6 4 2 存在安全序列,如P1,P3 ,P4,P5,P2,所以安全 (3)能,因為試探分配後,可用資源為1,1,0,0。可找到安全序列,所以可分配。六、計算題(第1題6分;第2題10分;第3題8分;共24分) 1、某虛擬存儲器的用戶編程空間共32個頁面,每頁為1KB,內存為16KB。假定某時刻一用戶頁表中已調入內存的頁面的頁號和物理塊號的對照表如下: 則邏輯地址0A5D(H)所對應的物理地址是什麼?(6分) 0A5D(H)=0000 1010 0101 1101 2號頁對應4號塊,所以物理地址是0001 0010 0101 1101 即125D(H)。 2、設有三道作業,它們的提交時間及執行時間由下表給出: 作業號 提交時間 執行時間 1 8.5 2.0 2 9.2 1.6 3 9.4 0.5 試計算在單道程序環境下,採用先來先服務調度演算法和最短作業優先調度演算法時的平均周轉時間 (時間單位:小時,以十進制進行計算;要求寫出計算過程)(10分) FCFS: 作業號 提交時間 執行時間 開始時間 完成時間 周轉時間 1 8.5 2.0 8.5 10.5 2.0 2 9.2 1.6 10.5 12.1 2.9 3 9.4 0.5 12.1 12.6 3.2 平均周轉時間=(2.0+2.9+3.2)/3=2.7(小時) SJF: 作業號 提交時間 執行時間 開始時間 完成時間 周轉時間 1 8.5 2.0 8.5 10.5 2.0 2 9.2 1.6 11.0 12.6 3.4 3 9.4 0.5 10.5 11.0 1.6 平均周轉時間=(2.0+3.4+1.6)/3=2.3(小時) 3、假定當前磁頭位於100號磁軌,進程對磁軌的請求序列依次為55,58,39,18,90,160,150,38,180。當採用先來先服務和最短尋道時間優先演算法時,總的移動的磁軌數分別是多少?(請給出尋道次序和每步移動磁軌數)(8分) FCFS: 服務序列依次為:55,58,39,18,90,160,150,38,180 移動的磁軌數分別是: 45, 3, 19, 21, 72, 70, 10, 112,142 總的移動的磁軌數是:494 SSTF: 服務序列依次為:90,58,55,39,38,18,150,160,180 移動的磁軌數分別是: 10, 32, 3, 16, 1, 20, 132, 10, 20 總的移動的磁軌數是:244

『玖』 Linux採用什麼演算法來解決內存碎片問題、make內編譯的文件為

一、Linux採用了「夥伴系統」,http://ke..com/view/4935190.htm
二、關於make的問題,參考http://ke..com/view/974566.htm
內部有例子,如果不懂,給我留言。

『拾』 linux內核管理內存中,夥伴演算法是基於什麼問題提出來的

你說的應該不是內核,一般的linux內核大小也就是幾兆,比如一個linux發行版的光碟映像,裡面應用程序佔了絕大多數存儲空間,內核只是很小的一部分。

熱點內容
phpmyadminlinux安裝 發布:2024-03-29 17:13:15 瀏覽:792
python中replace 發布:2024-03-29 17:08:17 瀏覽:652
mdb導入sql 發布:2024-03-29 17:07:36 瀏覽:128
java資料庫工具類 發布:2024-03-29 16:31:15 瀏覽:387
安卓機哪裡看型號 發布:2024-03-29 15:59:40 瀏覽:281
cad解壓錯誤 發布:2024-03-29 15:01:45 瀏覽:79
存儲指令集 發布:2024-03-29 14:39:27 瀏覽:649
資料庫表刪除數據 發布:2024-03-29 14:39:26 瀏覽:367
出c語言整除 發布:2024-03-29 14:28:22 瀏覽:572
芬尼壓縮機 發布:2024-03-29 14:24:11 瀏覽:464