07748操作系統(tǒng)實用教程4存儲管理

第4章存儲管理引言分區(qū)式存儲管理分頁式存儲管理分段存儲管理段頁式存儲管理用戶編程中的內存管理實例分析LINUX內存管理概述小結同學信箱引言內存管理的需求內存管理使用的技術分區(qū)式管理：固定式、可變式分區(qū)、多重分區(qū)頁式管理、段式管理段頁式管理操作系統(tǒng)的存儲管理機構必須解決以下問題內存分配存儲保護地址變換存儲共享存儲擴充同時進行多個任務編輯文檔運行程序網上瀏覽CD音樂欣賞為多個程序安排內存PCB1PCB2PCB3程序1程序2程序3數據程序進程控制塊PCB采用內存分配與管理技術：實存管理技術：分區(qū)式、分頁式、分段式存儲管理虛存管理技術：分頁式、分段式、段頁式存儲管理OS

分配內存程序1程序2程序3分區(qū)式存儲管理地址重定位靜態(tài)重定位動態(tài)重定位固定式分區(qū)可變式分區(qū)多重分區(qū)覆蓋與交換可變分區(qū)分配和釋放算法

程序的名字空間、地址空間及存儲空間符號源程序目標代碼可執(zhí)行代碼匯編編譯連接地址重定位名字空間地址空間存儲空間:x=x+1::R=XR=R+1X=R:0:K100:100+K:R=XR=R+1X=R:靜態(tài)重定位示意圖::LOAD1,300:5678:

01003004001000110013001400::LOAD1,1300:5678:某程序的地址空間內存動態(tài)重定位示意圖1000110013001400

LOAD1,300

5678內存物理地址空間0100300400

LOAD1,300

5678某程序的邏輯地址空間1000+固定分區(qū)分配區(qū)號大小起始地址標志123416K32K64K124K20K36K68K132K已分配已分配已分配未分配操作系統(tǒng)作業(yè)A作業(yè)C作業(yè)B020K36K68K132K第1分區(qū)第2分區(qū)第3分區(qū)第4分區(qū)（未分配）（b）內存分配圖（a）分區(qū)說明表可變分區(qū)說明表序號P大小起址狀態(tài)18K20K已分配232K28K已分配3——空表目4120K92K已分配5——空表目…………已分配分區(qū)說明

序號F大小起址狀態(tài)132K60K空閑2300K212K空閑3——空表目4——空表目5——空表目…………空閑分區(qū)說明表

可變分區(qū)示例可變分區(qū)分配和釋放算法分配算法一般有：①最佳適應（BestFit）算法，它從全部空閑區(qū)中找出能滿足作業(yè)需求的容量最小的空閑區(qū)分配之，此法的著眼點是使碎片盡量小。②最先適應（FirstFit）算法，它按序查找，把最先找到的滿足需求的空閑區(qū)分配之，此法的目的在于盡量減少查找時間。③最壞適應（WorstFit）算法,此法的目的在于使剩下的空區(qū)最大，減少空區(qū)碎片機會。④下次適應算法（NextFit），此法將空閑區(qū)鏈成環(huán)形鏈，每次分配從上次分配的位置開始查找合適的空閑區(qū)。

可變分區(qū)的分配算法F=F+1置空閑區(qū)號F=1=LocF的起始地址置置F的狀態(tài)=空表目置置P的大小=Xk置P的始址=Loc置P的=已分配本次無法分配=申請分配一個xk大小的分區(qū)F已超出最大項號？F的狀態(tài)=空表目？F的大小

Xk?在已分配表中找一個狀態(tài)=空表目的序號P返回序號P否是是否否否大于等于F的大小

Xk=新空閑塊大小Loc+Xk=新起始地址回收示意圖空閑區(qū)F1程序區(qū)回收區(qū)R空閑區(qū)F1

空閑區(qū)F2程序區(qū)回收區(qū)R

空閑區(qū)F2程序程序回收區(qū)R

程序區(qū)程序區(qū)回收區(qū)R

空閑區(qū)F2程序區(qū)程序區(qū)回收區(qū)R可變分區(qū)的回收算法=置新空閑分區(qū)的大小=Size始址=Loc狀態(tài)=空閑在空閑分區(qū)表中置F2為空閑表目分區(qū)R與F1鄰接？分區(qū)R與F1鄰接？在空閑分區(qū)表中找一個空閑表目分區(qū)R與F2鄰接？SizeSize+F2的大小已分配區(qū)說明表中置R的狀態(tài)=空表目Size分區(qū)R的大小Loc分區(qū)的起始地址否是是是否否請求回收分區(qū)R置空閑分區(qū)F2的大小=Size+F1的大小置空閑分區(qū)F2的大小=Size始址=Loc返回F1多重分區(qū)基址寄存器1作業(yè)1作業(yè)1OS限長寄存器1基址寄存器2限長寄存器2覆蓋技術舉例A20KB50KF30KC30KD20KE40KRAMA20K覆蓋區(qū)050K覆蓋區(qū)140KBCFDE14-3月-23分頁式存儲管理實存管理分頁原理頁表地址變換機構虛存管理頁表的擴充缺頁中斷處理頁面淘汰算法快表頁面共享0000100000000000

頁內地址

頁號相對頁號P頁內地值D分頁原理0000010000000000

頁內地址

頁號相對頁號P頁內地值D頁表項頁表項區(qū)域PCB區(qū)域OS用戶區(qū)頁號物理塊號1025171220某作業(yè)頁表有效（虛地址）操作系統(tǒng)物理塊號特征頁號作業(yè)2頁表4528物理地址物理塊號頁表起始地址頁表長度頁表始址寄存器頁號頁內相對位移內存8644外存LOAD1,25004522150地址變換過程請求分頁頁表頁號特征內存塊號外存塊號修改位訪問位0 00 11 01 1淘汰優(yōu)先級01此頁不在內存此頁在內存Linux頁表項定義缺頁中斷處理14-3月-23頁面淘汰算法先進先出(FIFO)最近最久未使用淘汰算法(LRU)最近不頻繁使用淘汰算法(LFU)最優(yōu)算法(OPT)以上幾種淘汰算法中，F(xiàn)IFO算法最簡單，但效率不高，有異?，F(xiàn)象。LRU的近似算法和LFU是較為實用的算法，效果較好，實現(xiàn)也不難。OPT算法是一種最佳算法，但并不實用，因為要跟蹤各頁面方可預測未來。而這種預測往往是很困難的。14-3月-23FIFO異?，F(xiàn)象快表 序號 相對頁號 物理塊號 訪問過 特征位 0

1

2

3

m-1

快表地址映象快表的地址映象操作頁面共享共享的例程頁面共享的數據頁面...共享的歷程頁面作業(yè)1頁表作業(yè)2頁表作業(yè)1頁表作業(yè)2頁表公共頁表分段存儲管理段式地址結構段號s段內位移w段式地址變換段號段內地址sw長度基址段表第s段b+wlb程序地址段表段頁式管理作業(yè)地址空間和地址結構主程序段子程序段數據段04K8K12K15K16K04K8K04K8K12K10K(b)段號(s)段內頁號(p)頁內地址(w)(a)14-3月-2314-3月-2314-3月-23I386-CPU頁表地址寄存器段頁式地址映射段頁式系統(tǒng)中的地址變換機構段表寄存器段表始址段表長度段超長段號s頁號p頁內地址塊內地址塊號頁表段表01230123頁表長度頁表始址b用戶編程中的內存管理實例分析basefree_listprev初始狀態(tài)0bpbasefree_list0第一次內存申請之后用戶編程中的內存管理實例分析（續(xù)）通常情況basefree_listprev0p14-3月-23Malloc.h分析（一）定義存儲分配單位headertypedeflongAlign;

/*與長整數邊界對齊*/unionheader{

/*塊首*/

struct{ unionheader

*next;

/*下個空塊*/

unsignedintsize;

/*塊大小*/

}s; Alignx; /*強制塊對齊*/};

typedefunionheaderHeader;nextsizeMalloc.h分析（二）定義header為自定義類型定義從os中申請內存的最小量10個header#defineNALLOC10/*請求的最小單位數*/說明三個函數staticHeader*morecore(unsignedintnu);//從內存管理中申請。void*Malloc(unsignedintnbytes); //從用戶區(qū)申請。voidFree(void*ap);//將空區(qū)鏈入用戶空區(qū)管理鏈中。Malloc.h分析（三）#include<stdlib.h>typedeflongAlign; /*foralignmenttolongboundary*/unionheader{ /*blockheader:*/struct{ unionheader*next;/*nextblockifonFreelist*/ unsignedintsize; /*sizeofthisblock*/ }s; Alignx; /*forcealignmentofblocks*/};

typedefunionheaderHeader;

#defineNALLOC 10 /*minimum#unitstorequest*/staticHeader*morecore(unsignedintnu);void*Malloc(unsignedintnbytes);voidFree(void*ap);14-3月-23Malloc函數分析（一）定義空區(qū)鏈基礎元素base定義空區(qū)鏈起始搜索指針free_list轉換申請的字節(jié)數nbytes為nunits個header單位nunits=(nbytes+sizeof(Header)-1)/sizeof(Header)+1;nunits比實際申請數nbytes至少多出一個header結構。建立空區(qū)鏈basefree_listprev0Malloc函數分析（二）檢索空閑區(qū)鏈表利用指針p和prev檢索。p為檢索指針，prev是緊跟其后的指針。1、找到空塊大小正好，則返回可用區(qū)地址（p+1)空塊大于申請量2、沒找到合適的空塊調用morecore(munits)從系統(tǒng)中要求分配，分配成功，新空塊插入鏈中，繼續(xù)檢索空區(qū)鏈；失敗，則返回NULL。p(p+1)Headernunitsppfree_listprevMalloc函數分析（三）#include<unistd.h>#include"my_malloc.h"

staticHeaderbase; /*定義空閑鏈頭，存儲塊劃分的最小單位*/staticHeader*free_list=NULL; /*定義空閑鏈查詢起始指針free_list*/

/*Malloc:常用存儲區(qū)分配函數*/void*Malloc(unsignedintnbytes){Header*p,*prev;//檢索指針，p

指向最終分配的快首址，prev指向分配位置的前一塊。unsignedintnunits; nunits=(nbytes+sizeof(Header)-1)/sizeof(Header)+1;//計算分配單位，多一個管理塊if((prev=free_list)==NULL){ /*空閑鏈上無任何空閑區(qū)塊，定義空閑鏈*/ base.s.next=free_list=prev=&base; base.s.size=0; }/*定義空閑鏈初始結構*/ for(p=prev->s.next;;prev=p,p=p->s.next){ if(p->s.size>=nunits){ /*夠大*/ if(p->s.size==nunits) /*正好*/ prev->s.next=p->s.next; else{ /*偏大，切出一部分*/ p->s.size-=nunits;/*計算剩余空塊大小，首址不變*/ p+=p->s.size; /*指出被分配塊起始地址*/ p->s.size=nunits;/*填好被分塊的大小*/ } free_list=prev; /*記錄上個位置*/

return(void*)(p+1); /*跳過管理塊，指向可用位置地址*/ } if(p==free_list) /*空塊不夠大，再次循環(huán)去找*/ if((p=morecore(nunits))==NULL) returnNULL; /*內存無空閑區(qū)*/ }/*endfor無限循環(huán)*/}14-3月-23morecore函數分析staticHeader*morecore(unsignedintnu){ char*cp; Header*up;

if(nu<NALLOC) nu=NALLOC; cp=sbrk(nu*sizeof(Header));//申請到的首地址送入指針cp中。

printf("sbrk:%X--%X\n",cp,cp+nu*sizeof(Header)); if(cp==(char*)-1) /*nospaceatall*/ returnNULL; up=(Header*)cp;//將指針cp強化成header結構，送入指針up。 up->s.size=nu;//填好header結構中的size內容為申請的Header數目

Free(up+1);//將申請到的空區(qū)鏈入空區(qū)鏈中。 returnfree_list;//返回空區(qū)鏈檢索指針free_list。}Free函數分析Free(void*ap){ Header*bp,*p;

bp=(Header*)ap-1; /*指向空區(qū)的header*/ for(p=free_list;!(bp>p&&bp<p->s.next);p=p->s.next)//定位空塊插入位置 if(p>=p->s.next&&(bp>p||bp<p->s.next)) break; /*freedblockatstartorendofarena*/ if(bp+bp->s.size==p->s.next){ /*jointouppernbr*/ bp->s.size+=p->s.next->s.size; bp->s.next=p->s.next->s.next; } else

bp->s.next=p->s.next; if(p+p->s.size==bp){/*jointolowernbr*/ p->s.size+=bp->s.size; p->s.next=bp->s.next; } else

p->s.next=bp;

free_list=p;}

pbppbpppbpfree_listpbpbpbp>pbp<p->s.nextp>=p->s.nextFree(void*ap){ Header*bp,*p;

bp=(Header*)ap-1; /*指向空區(qū)的header*/ for(p=free_list;!(bp>p&&bp<p->s.next);p=p->s.next)//定位空塊插入位置 if(p>=p->s.next&&(bp>p||bp<p->s.next)) break; /*freedblockatstartorendofarena*/ if(bp+bp->s.size==p->s.next){ /*jointouppernbr*/ bp->s.size+=p->s.next->s.size; bp->s.next=p->s.next->s.next; } else

bp->s.next=p->s.next; if(p+p->s.size==bp){/*jointolowernbr*/ p->s.size+=bp->s.size; p->s.next=bp->s.next; } else

p->s.next=bp;

free_list=p;}

pbpbp>p&&bp<p->s.next14-3月-23應用Malloc和Free的作業(yè)要求參考講義上給出的應用p160，設計應用malloc和free函數的例子?？梢愿鶕v義上的應用程序test.c，對應用內容進行變更。LINUX內存管理概述一級頁表二級頁表三級頁表物理頁虛擬地址一級頁PFNPFNPFN二級頁三級頁頁內位移PGD圖4.24三級頁表示意圖LINUX的三級頁表結構保護模式下虛擬地址到物理地址的轉換14-3月-23__PAGE_OFFSET定義于include/asm-i386/page.h12K00000000000000=3G14-3月-23確定頁目錄程序填寫的目錄項個數、4個字節(jié)、初值為01100000000=512+256=76814-3月-2314-3月-23頁表項例如：0x70x10070x2007表示為用戶頁面、可寫、且頁面在內存物理頁面基址為:0x0、0x1000、0x2000段選擇器格式/段描述符格式TI=0段描述符在GDT中,TI=1段描述符在LDT中。RPL:表示請求者使用處理器的特權級別，0-3級。14-3月-23GDT/LDT表分布進程的虛擬管理數據結構14-3月-23虛存數據成員進程的AVL樹vm_area_struct數據結構示意圖Vm_area_structVm_endVm_startVm_flagsVm_inodeVm_ops……Vm_next虛擬內存操作函數集nopage()advise()sync()protect()Open()close()unmap()swapout()swapin()進程的虛擬地址空間虛擬內存區(qū)域LINUX物理頁塊的分配和釋放空閑頁鏈表543210mem_map_tmem_map_t0mem_map_t16k頁面位圖128K位32k頁面位圖64K位位圖map8k頁面位圖512K位4k頁面位圖1M位876543210物理塊號物理內存45614-3月-23Bitmap表與freearea的關系14-3月-23文件系統(tǒng)的數據成員14-3月-23小結基本概念重定位地址變換機構虛擬存儲器主要管理技術及其數據結構分區(qū)、分頁、分段存儲分配算法淘汰算法存儲管理系統(tǒng)調用使用的例子14-3月-23同學信箱#include<stdio.h>

main()

{

intp1,p2;

while((p1=fork())==-1);/*創(chuàng)建子進程p1*/

if(p1==0)

putchar('b');

else