操作系統存儲器管理筆記
一操作系統裝入程序到內存中幾種方法:
1:絕對裝入方式(Absolute Loading Mode):
即程序在編譯時就產生物理地址的目標代碼,編譯完成后,不在需要對程序和數據進行修改,程序員也可以在程序中賦值物理地址。
缺點:不靈活,要求程序員對內存相當熟悉,只適用于單道程序環境。
2:靜態重定位裝入方式(Relocation Loading Mode):
即程序在編譯時使用的是邏輯地址,在裝入的時候,臨時將邏輯地址轉換成物理地址。到內存中后的地址為物理地址。這種方法叫做靜態重定位裝入。
缺點:不靈活,當進程有需要動態改變地址時則無法改變。
3:動態重定位裝入方式(Dynamic Run-time Loading)
即程序在裝入內存之后,在內存中仍然使用邏輯地址,只有在取該數據時,才轉換成物理地址。這樣做會影響到程序的執行速度。因此,一般將轉換成物理地址的過程做成硬件來完成轉換,需要添加一個地址轉換寄存器來支持。
二 程序的鏈接過程
1:靜態鏈接(Static Linking)
程序在編譯之后形成目標模塊,然后將目標模塊和庫函數組合成一個模塊,不再分開的鏈接。
缺點:消耗內存的資源很大,往往有的庫函數或模塊在程序的運行過程中沒有使用,極大的浪費了內存空間。
2:裝入是動態鏈接(Load-time Dynamic Linking)
程序在編譯時形成目標模塊代碼,在需要調入內存時,鏈接成一個模塊裝入內存。
缺點:和靜態鏈接一樣,對內存消耗大。
3:運行時動態鏈接(Runtime Dynamic Linking)
程序在編譯時形成目標模塊,在調入內存時調入需要執行的代碼模塊,當用到某個庫函數或模塊式時,由操作系統動態的調入內存執行。
三 內存連續分配方式
1:單一連續內存分配
把內存區域中劃分OS分區和應用進程區域兩大塊,互不干涉。在應用進程區域的內存按照單一的連續分配原則分配給各個進程。
使用范圍:單用戶,單任務的操作系統中。如CP/M,MS-DOS操作系統。
2:固定分區分配
a.固定分區大小一致分配
將內存劃分為大小一致的多個分區,這種分配方式缺乏靈活性,當進程太小造成空間浪費,太大則無法分配空間,導致裝入失敗。
b.固定分區大小不一致分配
將內存劃分為大小不一致的多個分區。這樣可根據進程大小適當分配區域。
分配具體操作:將各個分區按照大小排隊,用一張分區表存儲,該表中包含分區的大小,起始地址,和使用情況
使用范圍:IBM360的MFT
3:動態分區分配
根據進程的大小動態的分配內存空間,需要為其配置數據結構,分配算法,分區的分配和回收操作。
數據結構:
空閑分區表,用于記錄空閑分區的大小,起始地址,分區序號等信息
空閑分區鏈,在每個分區的起始地址部分設置一個分區信息數據結構,包含前后分區指針,分區尾部設置分區狀態和分區大小表目
分區分配算法:
a.首次適應算法(first fit)
在為進程分配分區時,從頭到尾查找空閑分區表,若查找到分區的大小大于或者等于要分配的進程大小則為其分配該分區。該算法的傾向于利用內存中的低地址空間,而保留了大部分高地址空間
優點:為大進程留下了足夠的空間。
缺點:產生很多內存碎塊,嚴重浪費了寶貴的內存資源。
b.循環首次適應算法(next fit)
和首次適應算法不同的是,在查找到適應的分區之后,以后再次分配內存空間時,從上次查找的位置開始進行分配。
優點:使內存使用空間分布的比較均勻,減少了查找空閑空間的時間。
缺點:這樣查找會缺乏大的內存空間
c.最佳適應算法(best fit)
將空閑分區表按照分區的大小從小到大排好隊,每次分配空閑分區時順序查找,找到適應的分區則分配進程,必然每次都是最佳分配。然而在宏觀上不一定是最佳的,每次分配后都會留下難以利用的內存碎塊。
b.最壞適應算法(worst fit)
將空閑分區表按從大到小的順序排好隊,依次掃描空閑分區表,每次分配給進程時,都將最大的內存空間分配之。
優點:每次殘留的內存碎塊都不至太小。對中小進程有利,對大進程最不利。查找效率高。
缺點:是內存中缺乏大的內存空間。
以上四種都稱為順序搜索法。
e.最快適應算法(fast fit)
該算法也稱為分類搜索法,將空閑分區表中大小大體相同的分區單獨放到一個空閑分區表中,這樣在操作系統中就有多個空閑分區表,再建立一個空閑分區索引表,每個索引指向一個空閑分區表,每類空閑分區的大小可以按照2kb,4kb,8kb來劃分。當要查找空閑分區時就可以通過查找索引來快速查找合適的分區。
優點:查找效率高,能保留大的分區,滿足對大空間的需要,也不會產生內存碎片。
缺點:在分區歸還內存時算法復雜,系統開銷大,在分配時一個分區只給一個進程,或多或少存在一定浪費。而且在分區劃分越細的情況下,浪費越嚴重。這是典型的以時間換空間的做法。
伙伴系統
伙伴系統是固定分區和動態分區分配的折中方法,在伙伴系統中,不論已經劃分的分區還是沒有劃分的分區大小都統一為2^k次冪,k可以為1,2,3......m 內存的區域最小為2^1
最大為2^m次冪,也就是整個內存區域。在每次分配內存時就分配2^i次冪大小的空間,這樣在多次分配后就會產生多個不連續的內存空間。將這些大小相同的內存空間分成一類,建立一個空閑分區鏈表,當要分配內存大小為m時,就比較2^i<m<2^i+1的大小,查找鏈表中是否存在2^i+1,若存在就將其分配給進程。若不存在就搜索2^i+2,若存在該大小的內存區域,就將其分成大小的為2^i+1的兩個伙伴,一個用于分配給進程,一個加入2^i+1的空閑鏈表中。若沒有找到,則依次類推。
在進行內存回收時,如果有2^i空閑區域則查找是否存在相同大小的空間,存在則合并為2^i+1,再搜索是否存在和2^i+1相同的空間若存在則再次合并。.若不存在,則加入2^i中。
伙伴系統在時間性能方面比分類搜索差,比順序搜索要優勝。在空間性能方面則相反。在多處理機的系統中得到大量的應用。