?2016-2026 Matools All rights reserved,
粵ICP備17059708號
前言
多進程和內(nèi)存管理是緊密相連的兩個模塊，因為運行進程也就是從內(nèi)存中取指執(zhí)行，創(chuàng)建進程首先要將程序和數(shù)據(jù)裝入內(nèi)存。將用戶原程序變成可在內(nèi)存中執(zhí)行的程序，而這就涉及到了內(nèi)存管理。
內(nèi)存的裝入
*
絕對裝入。
在編譯時，如果知道程序?qū)Ⅰv留在內(nèi)存的某個位置，編譯程序?qū)a(chǎn)生絕對地址的目標代碼。絕對裝入程序按照裝入模塊的地址，將程序和數(shù)據(jù)裝入內(nèi)存。裝入模塊被裝入內(nèi)存后，由于程序中的邏輯地址與實際地址完全相同，故不需對程序和數(shù)據(jù)的地址進行修改。
*
可重定位裝入。
在多道程序環(huán)境下，多個目標模塊的起始地址通常都是從0開始，程序中的其他地址都是相對于起始地址的，此時應采用可重定位裝入方式。根據(jù)內(nèi)存的當前情況，將裝入模塊裝入到內(nèi)存的適當位置。裝入時對目標程序中指令和數(shù)據(jù)的修改過程稱為重定位，地址變換通常是裝入時一次完成，所以成為靜態(tài)重定位。
其特點是在一個作業(yè)裝入內(nèi)存時，必須分配器要求的全部內(nèi)存空間，如果沒有足夠的內(nèi)存，就不能裝入，此外一旦作業(yè)進入內(nèi)存后，在整個運行期間，不能在內(nèi)存中移動，也不能再申請內(nèi)存空間。
*
動態(tài)運行時裝入
也成為動態(tài)重定位，程序在內(nèi)存中如果發(fā)生移動，就需要采用動態(tài)的裝入方式。
動態(tài)運行時的裝入程序在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進行。因此，裝入內(nèi)存后的所有地址均為相對地址，這種方式需要一個重定位寄存器的支持。
其特點是可以將程序分配到不連續(xù)的存儲區(qū)中；在程序運行之前可以只裝入它的部分代碼即可運行，然后在程序運行期間，根據(jù)需要動態(tài)申請分配內(nèi)存；便于程序段的共享，可以向用戶提供一個比存儲空間大得多的地址空間。
參考鏈接 <https://wizardforcel.gitbooks.io/wangdaokaoyan-os/content/13.html>
所以裝入內(nèi)存的最好方法應該就是動態(tài)運行時的裝入，但是這種方法需要一個方法來進行重定位。這個重定位的信息就保存在每個進程的PCB中，也就是保存這塊內(nèi)存的基地址，所以最后在運行時的地址就是
邏輯地址 + 基地址，而硬件也提供了相應計算的支持，也就是MMU
分段機制
但是在程序員眼里：程序由若干部分(段)組成，每個段有各自的特點、用途：代碼段只讀，代碼/數(shù)據(jù)段不會動態(tài)增長...。這樣就引出了對內(nèi)存進行分段
分段
假如用戶進程由主程序、兩個字程序、棧和一段數(shù)據(jù)組成，于是可以把這個用戶進程劃分為5個段，每段從0開始編址，并采用一段連續(xù)的地址空間（段內(nèi)要求連續(xù)，段間不要求連續(xù)），其邏輯地址由兩部分組成：段號與段內(nèi)偏移量，分別記為S、W。
段號為16位，段內(nèi)偏移量為16位，則一個作業(yè)最多可有2的16次方16=65536個段，最大段長64KB。
GDT和LDT
每個進程都有一張邏輯空間與主存空間映射的段表，其中每一段表項對應進程的一個段，段表項紀錄路該段在內(nèi)存中的起始地址和段的長度。在配置了段表后，執(zhí)行中的進程可通過查找段表，找到每個段所對應的內(nèi)存區(qū)。段表用于實現(xiàn)從邏輯端段到物理內(nèi)存區(qū)的映射。
而這個段表就是之前在保護模式提到的GDT和LDT
一個處理器只有一個GDT。LDT(局部描述表)，一個進程一個LDT，實際上是GTD的一個“子表”。
LDT和GDT從本質(zhì)上說是相同的，只是LDT嵌套在GDT之中。
有一個專門的寄存器LDTR來記錄局部描述符表的起始位置，記錄的是在GDT中的一個段選擇子。所以本質(zhì)上LDT是一個段描述符，這個描述符就存儲在GDT中，對應這個表述符也會有一個選擇子。
內(nèi)存分區(qū)和分頁
在用了分段機制后，那么就需要對內(nèi)存進行分區(qū)，讓各個段載入到相應的內(nèi)存分區(qū)中
內(nèi)存分配算法
在進程裝入或換入主存時。如果內(nèi)存中有多個足夠大的空閑塊，操作系統(tǒng)必須確定分配那個內(nèi)存塊給進程使用，通常有這幾種算法
*
首次適應算法：空閑分區(qū)以地址遞增的次序鏈接。分配內(nèi)存時順序查找，找到大小能滿足要求的第一個空閑分區(qū)。
* 最佳適應算法：空閑分區(qū)按容量遞增形成分區(qū)鏈，找到第一個能滿足要求的空閑分區(qū)。
* 最壞適應算法：有稱最大適應算法，空閑分區(qū)以容量遞減次序鏈接。找到第一個能滿足要求的空閑分區(qū)，也就是挑選最大的分區(qū)。
*
臨近適應算法：又稱循環(huán)首次適應算法，由首次適應算法演變而成。不同之處是分配內(nèi)存時從此查找結(jié)束的位置開始繼續(xù)查找。
內(nèi)存分頁
引入內(nèi)存分頁就是為了解決在進行內(nèi)存分區(qū)時導致的內(nèi)存效率問題
分頁就是把真正的內(nèi)存空間劃分為大小相等且固定的塊，塊相對較小，作為內(nèi)存的基本單位。每個進程也以塊為單位進行劃分，進程在執(zhí)行時，以塊為單位逐個申請主存中的塊空間。所以這時候?qū)φ嬲奈锢韮?nèi)存地址的映射就不能再用分段機制的那套了
就引入了頁表概念：系統(tǒng)為每個進程建立一張頁表，記錄頁面在內(nèi)存中對應的物理塊號，所以對地址的轉(zhuǎn)換變成了對頁表的轉(zhuǎn)換
在系統(tǒng)中通常設置一個頁表寄存器PTR，存放頁表在內(nèi)存的初值和頁表長度。
*
地址分為頁號和頁內(nèi)偏移量兩部分，再用頁號去檢索頁表。。
*
將頁表始址與頁號和頁表項長度的乘積相加，便得到該表項在頁表中的位置，于是可從中得到該頁的物理塊號。
但是頁表還是有兩個問題：
* 頁表占用的內(nèi)存大
* 頁表需要頻繁的進行地址訪問，所以訪存速度必須非常快
多級頁表
為了解決頁表占用的內(nèi)存太大，就引入了多級頁表
頁目錄有2的十次方個4字節(jié)的表項，這些表項指向?qū)亩壉恚€性地址的最高10位作為頁目錄用來尋找二級表的索引
二級頁表里的表項含有相關(guān)頁面的20位物理基地址，二級頁表使用線性地址中間10位來作為尋找表項的索引
* 進程訪問某個邏輯地址
* 由線性地址中的頁號，以及外層頁表寄存器(CR3)中的外層頁表始址，找到二級頁表的始址
* 由二級頁表的始址，加上線性地址中的外層頁內(nèi)地址，找到對應的二級頁表中的頁表項
* 由頁表項中的物理塊號，加上線性地址中的頁內(nèi)地址，找到對物理地址
快表
為了解決訪存速度，就有了快表
在系統(tǒng)中通常設置一個頁表寄存器PTR，存放頁表在內(nèi)存的初值和頁表長度。
*
CPU給出有效地址后，由硬件進行地址轉(zhuǎn)換，并將頁號送入高速緩存寄存器，并將此頁號與快表中的所有頁號同時進行比較。
*
如果有找到匹配的頁號，說明索要訪問的頁表項在快表中，則可以直接從中讀出該頁對應的頁框號。
*
如果沒有找到，則需要訪問主存中的頁表，在讀出頁表項后，應同時將其存入快表中，以供后面可能的再次訪問。但是如果快表已滿，就必須按照一定的算法對其中舊的頁表項進行替換。
段頁結(jié)合(虛擬內(nèi)存)
既然有了段和頁，程序員希望能用段，計算機設計希望用頁，那么就需要將二者結(jié)合
所以邏輯地址和物理地址的轉(zhuǎn)換：
*
首先將給定一個邏輯地址，
*
利用其段式內(nèi)存管理單元，也就是GDT中的斷描述符，先將為個邏輯地址轉(zhuǎn)換成一個線性地址，
*
再利用頁式內(nèi)存管理單元查表，轉(zhuǎn)換為物理地址。
虛擬內(nèi)存的管理
在實際的操作上，很有可能當前可用的物理內(nèi)存遠小于分配的虛擬內(nèi)存（4G），這時候就需要請求掉頁功能和頁面置換功能，也就是在進行地址轉(zhuǎn)換的時候找不到對應頁，就啟動頁錯誤處理程序來完成調(diào)頁
這樣在頁表項中增加了四個段：
*
狀態(tài)位P：用于指示該頁是否已調(diào)入內(nèi)存，共程序訪問時參考。
*
訪問字段A：用于記錄本頁在一段時間內(nèi)被訪問的次數(shù)，或記錄本頁最近已有多長時間未被訪問，供置換算法換出頁面時參考。
*
修改位M：表示該頁在調(diào)入內(nèi)存后是否被修改過。
*
外存地址：用于指出該也在外存上的地址，通常是物理塊號，供調(diào)入該頁時參考。
所以現(xiàn)在在查找物理地址的時候就變成了：
*
先檢索快表
*
若找到要訪問的頁，邊修改頁表中的訪問位，然后利用頁表項中給出的物理塊號和頁內(nèi)地址形成物理地址。
*
若為找到該頁的頁表項，應到內(nèi)存中去查找頁表，在對比頁表項中的狀態(tài)位P，看該頁是否已調(diào)入內(nèi)存，未調(diào)入則產(chǎn)生缺頁中斷，請求從外存把該頁調(diào)入內(nèi)存。
頁面置換算法
既然有頁面的換入換出，那自然就會有相應的不同的算法
最佳置換算法所選擇的被淘汰頁面將是以后永不使用的，或者是在最長時間內(nèi)不再被訪問的頁面，這樣可以保證獲得最低的缺頁率。但由于人們目前無法預知進程在內(nèi)存下的若干頁面中那個是未來最長時間內(nèi)不再被訪問的，但是這種算法無法實現(xiàn)。
LRU算法
選擇最近最長時間未訪問過的頁面予以淘汰，他認為過去一段時間內(nèi)未訪問過的頁面，在最近的將來可能也不會被訪問。該算法為每個頁面設置一個訪問字段，來記錄頁面自上次被訪問以來所經(jīng)歷的時間，淘汰頁面時選擇現(xiàn)有頁面中值最大的予以淘汰。
LRU算法一般有兩種實現(xiàn)：
* 時間戳
每次地址訪問都修改時間戳，淘汰頁的時候只需要選擇次數(shù)最少的即可
但是需維護一個全局時鐘，需找到最小值，實現(xiàn)代價較大
* 頁碼棧
在每次地址訪問的時候都修改棧，這樣在淘汰的時候，只需要將棧底換出
但是和上面用時間戳的方法一樣，實現(xiàn)的代價都非常大
CLOCK算法
給每個頁幀關(guān)聯(lián)一個使用位。當該頁第一次裝入內(nèi)存或者被重新訪問到時，將使用位置為1。每次需要替換時，查找使用位被置為0的第一個幀進行替換。在掃描過程中，如果碰到使用位為1的幀，將使用位置為0，在繼續(xù)掃描。如果所謂幀的使用位都為0，則替換第一個幀
CLOCK算法的性能比較接近LRU，而通過增加使用的位數(shù)目，可是使得CLOCK算法更加高效。在使用位的基礎(chǔ)上再增加一個修改位，則得到改進型的CLOCK置換算法。這樣，每一幀都出于以下四種情況之一。
* 最近未被訪問，也未被修改（u=0，m=0）。
* 最近被訪問，但未被修改（u=1，m=0）。
* 最近未被訪問，但被修改（u=0，m=1）。
* 最近被訪問，被修改（u=1，m=1）。
算法執(zhí)行如下操作步驟：
* 從指針的當前位置開始，掃描幀緩沖區(qū)。在這次掃描過程中，對使用位不作任何修改，選擇遇到的第一個幀（u=0，m=0）用于替換。
* 如果第1步失敗，則重新掃描，查找（u=0，m=1）的幀。選額遇到的第一個這樣的幀用于替換。在這個掃面過程中，對每個跳過的幀，把它的使用位設置成0.
* 如果第2步失敗，指針將回到它的最初位置，并且集合中所有幀的使用位均為0.重復第一步，并且如果有必要重復第2步。這樣將可以找到供替換的幀。
改進型的CLOCK算法優(yōu)于簡單的CLOCK算法之處在于替換時首選沒有變化的頁。由于修改過的頁在被替換之前必須寫回，因而這樣做會節(jié)省時間。
Linux 0.11的故事
所有有關(guān)管理內(nèi)存都是為了服務進程而誕生的，所以先來看一下Linux 0.11里從創(chuàng)建進程開始的故事
fork
* 首先通過系統(tǒng)調(diào)用的中斷來創(chuàng)建進程，fork()->sys_fork->copy_process
* copy_process的主要作用就是為子進程創(chuàng)建TSS描述符、分配內(nèi)存和文件設定等等
* copy_mem這里僅為新進程設置自己的頁目錄表項和頁表項，而沒有實際為新進程分配物理內(nèi)存頁面。此時新進程與其父進程共享所有內(nèi)存頁面。 int
copy_process(int nr,long ebp,long edi,long esi,long gs,long none, long ebx,long
ecx,long edx, long fs,long es,long ds, long eip,long cs,long eflags,long
esp,long ss) { struct task_struct *p; int i; struct file *f; p = (struct
task_struct *) get_free_page(); if (!p) return -EAGAIN; task[nr] = p; *p =
*current; /* NOTE! this doesn't copy the supervisor stack */ p->state =
TASK_UNINTERRUPTIBLE; p->pid = last_pid; p->father = current->pid; p->counter =
p->priority; p->signal = 0; p->alarm = 0; p->leader = 0; /* process leadership
doesn't inherit */ p->utime = p->stime = 0; p->cutime = p->cstime = 0;
p->start_time = jiffies; p->tss.back_link = 0; p->tss.esp0 = PAGE_SIZE + (long)
p; p->tss.ss0 = 0x10; p->tss.eip = eip; p->tss.eflags = eflags; p->tss.eax = 0;
p->tss.ecx = ecx; p->tss.edx = edx; p->tss.ebx = ebx; p->tss.esp = esp;
p->tss.ebp = ebp; p->tss.esi = esi; p->tss.edi = edi; p->tss.es = es & 0xffff;
p->tss.cs = cs & 0xffff; p->tss.ss = ss & 0xffff; p->tss.ds = ds & 0xffff;
p->tss.fs = fs & 0xffff; p->tss.gs = gs & 0xffff; p->tss.ldt = _LDT(nr);
p->tss.trace_bitmap = 0x80000000; if (last_task_used_math == current)
__asm__("clts ; fnsave %0"::"m" (p->tss.i387)); if (copy_mem(nr,p)) { task[nr]
= NULL; free_page((long) p); return -EAGAIN; } for (i=0; i<NR_OPEN;i++) if
((f=p->filp[i])) f->f_count++; if (current->pwd) current->pwd->i_count++; if
(current->root) current->root->i_count++; if (current->executable)
current->executable->i_count++;
set_tss_desc(gdt+(nr<<1)+FIRST_TSS_ENTRY,&(p->tss));
set_ldt_desc(gdt+(nr<<1)+FIRST_LDT_ENTRY,&(p->ldt)); p->state = TASK_RUNNING;
/* do this last, just in case */ return last_pid; } int copy_mem(int nr,struct
task_struct * p) { unsigned long old_data_base,new_data_base,data_limit;
unsigned long old_code_base,new_code_base,code_limit;
code_limit=get_limit(0x0f); data_limit=get_limit(0x17); old_code_base =
get_base(current->ldt[1]); old_data_base = get_base(current->ldt[2]); if
(old_data_base != old_code_base) panic("We don't support separate I&D"); if
(data_limit < code_limit) panic("Bad data_limit"); new_data_base =
new_code_base = nr * 0x4000000; p->start_code = new_code_base;
set_base(p->ldt[1],new_code_base); set_base(p->ldt[2],new_data_base); if
(copy_page_tables(old_data_base,new_data_base,data_limit)) {
printk("free_page_tables: from copy_mem\n");
free_page_tables(new_data_base,data_limit); return -ENOMEM; } return 0; }
page
*
copy_page_tables就是復制頁目錄表項和頁表項，從而被復制的頁目錄和頁表對應的原物理內(nèi)存頁面區(qū)被兩套頁表映射而共享使用。復制時，需申請新頁面來存放新頁表，原物理內(nèi)存區(qū)將被共享。此后兩個進程（父進程和其子進程）將共享內(nèi)存區(qū)，直到有一個進程執(zhí)行操作時，內(nèi)核才會為寫操作進程分配新的內(nèi)存頁(寫時復制機制)。
int copy_page_tables(unsigned long from,unsigned long to,long size) { unsigned
long * from_page_table; unsigned long * to_page_table; unsigned long this_page;
unsigned long * from_dir, * to_dir; unsigned long nr; if ((from&0x3fffff) ||
(to&0x3fffff)) panic("copy_page_tables called with wrong alignment"); from_dir
= (unsigned long *) ((from>>20) & 0xffc); /* _pg_dir = 0 */ to_dir = (unsigned
long *) ((to>>20) & 0xffc); size = ((unsigned) (size+0x3fffff)) >> 22; for( ;
size-->0 ; from_dir++,to_dir++) { if (1 & *to_dir) panic("copy_page_tables:
already exist"); if (!(1 & *from_dir)) continue; from_page_table = (unsigned
long *) (0xfffff000 & *from_dir); if (!(to_page_table = (unsigned long *)
get_free_page())) return -1; /* Out of memory, see freeing */ *to_dir =
((unsigned long) to_page_table) | 7; nr = (from==0)?0xA0:1024; for ( ; nr-- > 0
; from_page_table++,to_page_table++) { this_page = *from_page_table; if (!(1 &
this_page)) continue; this_page &= ~2; *to_page_table = this_page; if
(this_page > LOW_MEM) { *from_page_table = this_page; this_page -= LOW_MEM;
this_page >>= 12; mem_map[this_page]++; } } } invalidate(); return 0; }
no_page
如果找不到相應的頁，也就是要執(zhí)行換入和換出了，在此之前CPU會先觸發(fā)缺頁異常
* 缺頁異常中斷的處理，會調(diào)用do_no_page page_fault: xchgl %eax,(%esp) # 取出錯碼到eax pushl %ecx
pushl %edx push %ds push %es push %fs movl $0x10,%edx # 置內(nèi)核數(shù)據(jù)段選擇符 mov %dx,%ds
mov %dx,%es mov %dx,%fs movl %cr2,%edx # 取引起頁面異常的線性地址 pushl %edx #
將該線性地址和出錯碼壓入棧中，作為將調(diào)用函數(shù)的參數(shù) pushl %eax testl $1,%eax #
測試頁存在標志P（為0），如果不是缺頁引起的異常則跳轉(zhuǎn) jne 1f call do_no_page # 調(diào)用缺頁處理函數(shù) jmp 2f 1: call
do_wp_page # 調(diào)用寫保護處理函數(shù) 2: addl $8,%esp # 丟棄壓入棧的兩個參數(shù)，彈出棧中寄存器并退出中斷。 pop %fs pop
%es pop %ds popl %edx popl %ecx popl %eax iret
*
該函數(shù)首先嘗試與已加載的相同文件進行頁面共享，或者只是由于進程動態(tài)申請內(nèi)存頁面而只需映射一頁物理內(nèi)存即可。若共享操作不成功，那么只能從相應文件中讀入所缺的數(shù)據(jù)頁面到指定線性地址處。
void do_no_page(unsigned long error_code,unsigned long address) { int nr[4];
unsigned long tmp; unsigned long page; int block,i; address &= 0xfffff000; tmp
= address - current->start_code; if (!current->executable || tmp >=
current->end_data) { get_empty_page(address); return; } if (share_page(tmp))
return; if (!(page = get_free_page())) oom(); /* remember that 1 block is used
for header */ block = 1 + tmp/BLOCK_SIZE; for (i=0 ; i<4 ; block++,i++) nr[i] =
bmap(current->executable,block);
bread_page(page,current->executable->i_dev,nr); i = tmp + 4096 -
current->end_data; tmp = page + 4096; while (i-- > 0) { tmp--; *(char *)tmp =
0; } if (put_page(page,address)) return; free_page(page); oom(); }
小結(jié)
這一篇的篇幅很長，因為把有關(guān)內(nèi)存管理的東西都寫在一起了，主要有三個關(guān)鍵點：
*
分段
對內(nèi)存的分段引申的GDT和IDT來進行物理地址的尋址
*
分頁
再由于分段引出的內(nèi)存分區(qū)，為了提高效率而引入的分頁機制，重點就是用頁式內(nèi)存管理單元查表
* 段頁結(jié)合
所以為了將段和頁結(jié)合就需要一個機制來轉(zhuǎn)化邏輯地址和物理地址，也就分為兩步走
*
利用其段式內(nèi)存管理單元，也就是GDT中的斷描述符，先將為個邏輯地址轉(zhuǎn)換成一個線性地址，
*
再利用頁式內(nèi)存管理單元查表，轉(zhuǎn)換為物理地址。
熱門工具 換一換