OS學(xué)習(xí)周報告-2
內(nèi)存分配算法模擬-bf
- 計算機(jī)中的程序需要裝入內(nèi)存才能執(zhí)行氯庆，如何為程序分配內(nèi)存是人們一直以來思考的問題堤撵。
連續(xù)分配方式是最早出現(xiàn)的一種內(nèi)存分配方式羽莺，該方法為程序分配一塊連續(xù)的內(nèi)存空間盐固，具體又可分為單一連續(xù)分配，固定分區(qū)分配和動態(tài)分區(qū)分配三種志电。
- 單一連續(xù)分配只能在單道程序環(huán)境下實現(xiàn)长酗，它將內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)夺脾，系統(tǒng)區(qū)給OS使用咧叭，因為單道環(huán)境同一時間只運行一個程序，所以用戶區(qū)由該程序獨占吉挣。
在這種分配方式下婉弹，若是用戶區(qū)容量不足以放下整個程序時怎么辦呢镀赌？
覆蓋技術(shù)就是解決這一問題的，程序在執(zhí)行時并不是任何時候都要訪問程序及數(shù)據(jù)的各個部分喉钢，那么我們只需要保證程序當(dāng)前執(zhí)行的部分在內(nèi)存中即可肠虽。
-
既然說道覆蓋就不能不提另一概念——交換(swapping)
在多道程序環(huán)境中玛追，內(nèi)存中往往存放有多個用戶進(jìn)程痊剖，當(dāng)某些進(jìn)程處于等待狀態(tài)時，若還將其存放在內(nèi)存中啸如，便白白浪費了這些內(nèi)存空間叮雳。這時將這些程序從內(nèi)存移動到硬盤中妇汗，騰出內(nèi)存空間杨箭，這一過程成為換出，而把準(zhǔn)備好要競爭CPU的進(jìn)程從硬盤再移動到內(nèi)存中捣郊，這一過程稱為換入呛牲。
-
對比下兩者，可以看出覆蓋是解決單道程序環(huán)境下小內(nèi)存放大程序的問題的技術(shù)着茸，而交換是提升多道程序環(huán)境下內(nèi)存利用率的技術(shù)琐旁。
另一點重要區(qū)別則是灰殴，覆蓋技術(shù)要求程序員在編寫程序時就確定好程序中不同部分的調(diào)用次序验懊，而交換技術(shù)則對用戶是透明的，這些換入換出的操作都有OS來完成减俏。
-
固定分區(qū)分配是最簡單的多道程序內(nèi)存管理方式娃承，它將內(nèi)存空間劃分為若干大小的分區(qū)怕篷，每個分區(qū)只裝入一道作業(yè)廊谓。而分區(qū)大小可分為等大分區(qū)或大小不等分區(qū)。
這種分區(qū)方式的缺點也很明顯春弥，一是若程序過大放不進(jìn)任何一個分區(qū)中匿沛，那么用戶將不得不使用覆蓋技術(shù)榛鼎。二是當(dāng)小程序放入大分區(qū)中，會產(chǎn)生內(nèi)部碎片苏揣，降低內(nèi)存的利用率蔫缸。
-
動態(tài)分區(qū)分配拾碌，不預(yù)先進(jìn)行內(nèi)存劃分街望，而是進(jìn)程裝入內(nèi)存時灾前，根據(jù)進(jìn)程的大小動態(tài)建立分區(qū)哎甲。
動態(tài)分區(qū)在開始分配時，性能很好奈嘿，但經(jīng)過多次分配后裙犹，內(nèi)存中會出先許多小的空閑內(nèi)存塊衔憨，稱為外部碎片践图。隨著時間推移，這些碎片會越來越多赫舒，與內(nèi)部碎片一樣接癌，也會降低內(nèi)存利用率缺猛。
這時需要通過緊湊(Compacion)技術(shù)來將這些分散的空閑內(nèi)存整合成一塊大的內(nèi)存塊，由OS將內(nèi)存中的進(jìn)程進(jìn)行移動,整理耻姥。
可以想到內(nèi)存中的進(jìn)程的物理地址在移動會發(fā)生變化琐簇，那cpu如何找到移動后的進(jìn)程呢婉商？
動態(tài)運行時裝入(動態(tài)重定位) 渣叛，當(dāng)程序鏈接完后，由裝入程序?qū)⒀b入模塊轉(zhuǎn)入內(nèi)存中蘑秽，但并不立即將程序中的邏輯地址轉(zhuǎn)換為內(nèi)存中的物理地址肠牲，而是等到程序真正要執(zhí)行時才完成地址的轉(zhuǎn)換埂材。由重定位寄存器記錄每次移動后程序的最小物理地址值汤求，cpu通過邏輯地址+重定位寄存器中的基址扬绪，就可以得到相應(yīng)的物理地址挤牛。
-
動態(tài)分區(qū)分配算法
-
首次適應(yīng)(FF)算法
從低地址開始，找到第一個滿足作業(yè)大小的空閑區(qū)即進(jìn)行分配竞膳。由于每次分配都是從低地址開始，多次分配后會在低地址區(qū)域留下大量外部碎片诫硕，降低查找效率坦辟。
-
循環(huán)首次適應(yīng)(NF)算法
對FF算法的改進(jìn)，每次尋找空閑區(qū)后章办，指針留在原位锉走。下次查找從指針?biāo)肝恢瞄_始仙粱。雖然使得外部碎片均勻分部在內(nèi)存空間中嚣艇，但卻減少了大容量空閑區(qū)的數(shù)量赠涮。
-
最佳適應(yīng)(BF)算法
顧名思義，每次查找空閑區(qū)梁厉，總是找到滿足作業(yè)大小的最小的空閑區(qū)辜羊。
-
最壞適應(yīng)(WF)算法
每次查找，總是找到滿足作業(yè)大小的最大的空閑區(qū)词顾。
-
-
算法模擬
-
BF算法
通過建立鏈表八秃，模擬空閑分區(qū)鏈
typedef struct node { int no; //狀態(tài)位，-1表示空閑计技，否則記錄作業(yè)號 int start; //分區(qū)始址 int size; //分區(qū)大小 struct node *next; }node;代碼核心部分喜德，按照BF算法進(jìn)行內(nèi)存分配：
int add(node *head,int no,int size) //內(nèi)存分配模塊 { int min=INF; //bf算法首先找到所有大于待分配作業(yè)大小的空閑區(qū)山橄，再從中找出容量最小的空閑區(qū)垮媒，完成分配 node *p,*q; for(p=head->next;p;p=p->next) { if(p->no==-1&&p->size>=size) //先找滿足容量大于作業(yè)大小的空閑區(qū) { if(p->size<min) //再找容量與作業(yè)大小最接近的空閑區(qū) { min=p->size; q=p; } } } if(q==NULL) return 0; //如果沒找到滿足要求的空閑區(qū)，則分配失敗 if(q->size-size>SIZE) //SIZE是我們設(shè)置的碎片大小航棱，若分配后空閑區(qū)剩余空間容量大于碎片大小睡雇，則需為剩余空間新建一個鏈表結(jié)點來記錄它 { node *temp=(node*)malloc(sizeof(node)); temp->no=-1; temp->start=q->start+size; //為剩余空間創(chuàng)建新結(jié)點，它的始址為該空閑塊原始址+作業(yè)大小 temp->size=q->size-size; //該結(jié)點大小即為原空閑塊大小-作業(yè)大小 temp->next=q->next; //將新建結(jié)點插入原空閑結(jié)點之后 q->next=temp; } q->no=no; //將作業(yè)存入該空閑區(qū)中 q->size=(q->size-size>SIZE?size:q->size); //若為剩余空間創(chuàng)建了新結(jié)點饮醇，則存入作業(yè)后它抱，該結(jié)點大小即為作業(yè)大小 return 1; }?
執(zhí)行情況：
請輸入內(nèi)存空間大小: 100 請輸入碎片大小: 1 ... *************************************************** 1: 為新作業(yè)分配內(nèi)存 2: 撤銷作業(yè)釋放內(nèi)存 3: 查看buddy算法內(nèi)存分配 4: 退出 *************************************************** 請輸入操作: 3 已分配分區(qū) 空閑分區(qū) (分區(qū)號, 作業(yè), 始址, 大小) (分區(qū)號, 始址, 大小) 2, 2, 20, 61 1, 0, 20 3, 81, 19 *************************************************** 1: 為新作業(yè)分配內(nèi)存 2: 撤銷作業(yè)釋放內(nèi)存 3: 查看buddy算法內(nèi)存分配 4: 退出 *************************************************** 請輸入操作:完成上述操作后，容量為100的內(nèi)存空間被分為3部分朴艰，
1號空閑區(qū)容量為20观蓄，3號空閑區(qū)容量為19，3號空閑區(qū)位于高地址部分祠墅。這時我們?yōu)榇笮?8的作業(yè)分配內(nèi)存侮穿。
*************************************************** 1: 為新作業(yè)分配內(nèi)存 2: 撤銷作業(yè)釋放內(nèi)存 3: 查看buddy算法內(nèi)存分配 4: 退出 *************************************************** 請輸入操作: 1 請輸入作業(yè)id和作業(yè)大小size: 4 18 分配成功 *************************************************** 1: 為新作業(yè)分配內(nèi)存 2: 撤銷作業(yè)釋放內(nèi)存 3: 查看buddy算法內(nèi)存分配 4: 退出 *************************************************** 請輸入操作: 3 已分配分區(qū) 空閑分區(qū) (分區(qū)號, 作業(yè), 始址, 大小) (分區(qū)號, 始址, 大小) 2, 2, 20, 61 1, 0, 20 3, 4, 81, 19 *************************************************** 1: 為新作業(yè)分配內(nèi)存 2: 撤銷作業(yè)釋放內(nèi)存 3: 查看buddy算法內(nèi)存分配 4: 退出 *************************************************** 請輸入操作:可以看到4號作業(yè)沒有分配到低始址的1號空閑區(qū)，而是分容量更為接近的3號空閑區(qū)中毁嗦。
-
WF算法
內(nèi)存分配策略與BF算法剛好相反亲茅，先找到滿足作業(yè)大小的空閑區(qū)，再找到它們之中容量最大的那個即可狗准。
int add(node *head,int no,int size) //內(nèi)存分配模塊 { int max=0; //wf算法首先找到所有大于待分配作業(yè)大小的空閑區(qū)克锣，再從中找出容量最大的空閑區(qū)，完成分配 node *p,*q; for(p=head->next;p;p=p->next) { if(p->no==-1&&p->size>=size) //先找滿足容量大于作業(yè)大小的空閑區(qū) { if(p->size>max) //再找容量與作業(yè)大小最接近的空閑區(qū) { max=p->size; q=p; } } } ...執(zhí)行情況：
*************************************************** 1: 為新作業(yè)分配內(nèi)存 2: 撤銷作業(yè)釋放內(nèi)存 3: 查看wf算法內(nèi)存分配 4: 退出 *************************************************** 請輸入操作: 3 已分配分區(qū) 空閑分區(qū) (分區(qū)號, 作業(yè), 始址, 大小) (分區(qū)號, 始址, 大小) 2, 2, 19, 61 1, 0, 19 3, 80, 20 *************************************************** 1: 為新作業(yè)分配內(nèi)存 2: 撤銷作業(yè)釋放內(nèi)存 3: 查看wf算法內(nèi)存分配 4: 退出 *************************************************** 請輸入操作: 1 請輸入作業(yè)id和作業(yè)大小size: 3 18 分配成功 *************************************************** 1: 為新作業(yè)分配內(nèi)存 2: 撤銷作業(yè)釋放內(nèi)存 3: 查看wf算法內(nèi)存分配 4: 退出 *************************************************** 請輸入操作: 3 已分配分區(qū) 空閑分區(qū) (分區(qū)號, 作業(yè), 始址, 大小) (分區(qū)號, 始址, 大小) 2, 2, 19, 61 1, 0, 19 3, 3, 80, 18 4, 98, 2大小為18的3號作業(yè)腔长，存入了容量較大的3號空閑區(qū)袭祟。
-
-
在了解了這么多內(nèi)存分配算法后，我們不禁要問捞附，它們之中是性能最優(yōu)的算法呢榕酒？
性能最優(yōu)首先這種算法要“最快”胚膊，它要能在最短時間找到可分配的空閑塊。另外想鹰，還要“最好”紊婉，它要能有較高的內(nèi)存利用率，能在內(nèi)存中放入盡量多的作業(yè)辑舷。
最佳分配算法bf喻犁，為每個作業(yè)找到容量最適合的空閑區(qū)，充分利用了每一塊內(nèi)存何缓，似乎就是最好的算法肢础。但仔細(xì)想想，每一次分配后碌廓，剩下的空閑區(qū)都是最小的传轰。多次分配后，我們發(fā)現(xiàn)內(nèi)存中的空閑區(qū)都是些難以利用的小塊谷婆。
有如下的特例：
*************************************************** 1: 為新作業(yè)分配內(nèi)存 2: 撤銷作業(yè)釋放內(nèi)存 3: 查看bf算法內(nèi)存分配 4: 退出 *************************************************** 請輸入操作: 3 已分配分區(qū) 空閑分區(qū) (分區(qū)號, 作業(yè), 始址, 大小) (分區(qū)號, 始址, 大小) 2, 2, 3, 2 1, 0, 3 3, 5, 5 ***************************************************我們后面的作業(yè)序列大小為慨蛙，2 ，3 纪挎，3.
使用bf分配的結(jié)果：
*************************************************** 請輸入操作: 1 請輸入作業(yè)id和作業(yè)大小size: 5 3 分配失敗 *************************************************** 1: 為新作業(yè)分配內(nèi)存 2: 撤銷作業(yè)釋放內(nèi)存 3: 查看bf算法內(nèi)存分配 4: 退出 *************************************************** 請輸入操作: 3 已分配分區(qū) 空閑分區(qū) (分區(qū)號, 作業(yè), 始址, 大小) (分區(qū)號, 始址, 大小) 1, 3, 0, 3 4, 8, 2 2, 2, 3, 2 3, 4, 5, 3而使用wf算法我們可以完成分配：
*************************************************** 請輸入操作: 1 請輸入作業(yè)id和作業(yè)大小size: 5 3 分配成功 *************************************************** 1: 為新作業(yè)分配內(nèi)存 2: 撤銷作業(yè)釋放內(nèi)存 3: 查看wf算法內(nèi)存分配 4: 退出 *************************************************** 請輸入操作: 3 已分配分區(qū) 空閑分區(qū) (分區(qū)號, 作業(yè), 始址, 大小) (分區(qū)號, 始址, 大小) 1, 4, 0, 3 2, 2, 3, 2 3, 3, 5, 2 4, 5, 7, 3?
bf的查找速度也不如wf期贫，wf算法只要將空閑分區(qū)按容量從大到小排列，每次取出第一個結(jié)點即可异袄。而bf算法則需要從空閑區(qū)容量從小到大的序列中通砍，找到第一個滿足作業(yè)容量的空閑區(qū)。
而wf雖然有最快的查找速度烤蜕，但總是小程序放到大內(nèi)存中封孙，會很快消耗掉內(nèi)存中的大空閑塊，性能也不是最佳讽营。
理論上說FF是最簡單虎忌，通常也是最快和最好的算法。
-
這里我想能不能用我們的模擬算法來做個實驗驗證下到底哪個算法更好
我想了兩種測試方法：
-
只放不取
設(shè)置好內(nèi)存空間斑匪，和測試次數(shù)后呐籽，每輪測試隨機(jī)放入一個大小在內(nèi)存容量五分之一范圍內(nèi)的作業(yè)，直到出現(xiàn)連續(xù)3次放入失敗位置蚀瘸，記錄下放入作業(yè)的個數(shù)狡蝶，以此來評價算法的優(yōu)劣。
int main() { printf("請輸入內(nèi)存空間大小: "); scanf("%d",&memory_capacity); printf("請輸入碎片大小: "); scanf("%d", &SIZE); int test_count; printf("請輸入測試次數(shù):"); scanf("%d",&test_count); int taskcount=0; srand((unsigned int)time(NULL)); for(int i=0;i<test_count;i++) { node *head=init_link_table(memory_capacity); int flag=0; int no=0; int k; while(flag<3) { k=add(head,++no,rand()%memory_capacity/5); if(k==0) flag++; else taskcount++,flag=0; } node *p,*q; p=head,q=p->next; while(q!=NULL) { free(p); p=q,q=q->next; } } printf("%d\n",taskcount); printf("平均任務(wù)個數(shù)：%.2f\n",(float)taskcount/test_count); return 1; }結(jié)果如下：
hawl29@hawl29-PC:~/Desktop/cprogram/OS_experiment$ ./ff_test2_execfile 請輸入內(nèi)存空間大小: 10000 請輸入碎片大小: 1 請輸入測試次數(shù):100000 1053311 平均任務(wù)個數(shù)：10.53 hawl29@hawl29-PC:~/Desktop/cprogram/OS_experiment$ ./bf_test2_execfile 請輸入內(nèi)存空間大小: 10000 請輸入碎片大小: 1 請輸入測試次數(shù):100000 1053942 平均任務(wù)個數(shù)：10.54 hawl29@hawl29-PC:~/Desktop/cprogram/OS_experiment$ ./wf_test2_execfile 請輸入內(nèi)存空間大小: 10000 請輸入碎片大小: 1 請輸入測試次數(shù):100000 1053605 平均任務(wù)個數(shù)：10.54從這個結(jié)果中看不出來3種算法的區(qū)別贮勃。
-
隨機(jī)存取
隨機(jī)存取若干次后贪惹，統(tǒng)計最終存入的作業(yè)數(shù)。
int main() { printf("請輸入內(nèi)存空間大小: "); scanf("%d",&memory_capacity); printf("請輸入碎片大小: "); scanf("%d", &SIZE); int test_count; printf("請輸入測試次數(shù):"); scanf("%d",&test_count); int taskcount=0; int no=0; srand((unsigned int)time(NULL)); node *head=init_link_table(memory_capacity); int rep[test_count]; int k,j,m,n; for(int i=0;i<test_count;i++) rep[i]=0; for(int i=0;i<test_count;i++) { if(rand()%2==1) { k=add(head,++no,rand()%memory_capacity/5); if(k==1) taskcount++; } else if(rand()%2==0&&no>0) { j=rand()%no; m=n=j; for(int i=0;m>=0&&n<no;) { if(rep[m]==1) { j=m; break; } else if(rep[n]==1) { j=n; break; } else { if(m>0) m--; if(n<no) n++; } } del(head,j); } } printf("存入任務(wù)個數(shù)%d\n",taskcount); return 1; }結(jié)果如下：
hawl29@hawl29-PC:~/Desktop/cprogram/OS_experiment$ ./ff_test3_execfile 請輸入內(nèi)存空間大小: 10000 請輸入碎片大小: 1 請輸入測試次數(shù):100000 存入任務(wù)個數(shù)782 hawl29@hawl29-PC:~/Desktop/cprogram/OS_experiment$ ./bf_test3_execfile 請輸入內(nèi)存空間大小: 10000 請輸入碎片大小: 1 請輸入測試次數(shù):100000 存入任務(wù)個數(shù)791 hawl29@hawl29-PC:~/Desktop/cprogram/OS_experiment$ ./wf_test3_execfile 請輸入內(nèi)存空間大小: 10000 請輸入碎片大小: 1 請輸入測試次數(shù):100000 存入任務(wù)個數(shù)695這次的結(jié)果可以看出寂嘉，ff和bf算法較wf來說略好奏瞬。
-
-
調(diào)試總結(jié)
在寫測試代碼時枫绅，出現(xiàn)了2個錯誤。
-
hawl29@hawl29-PC:~/Desktop/cprogram/OS_experiment$ ./bf_test2_execfile 請輸入內(nèi)存空間大小: 100 請輸入碎片大小: 1 請輸入測試次數(shù): 100 浮點數(shù)例外提示浮點數(shù)例外硼端，在網(wǎng)上查一般是2種原因造成的：
一是高版本GCC編譯的程序在低版本GCC環(huán)境下運行導(dǎo)致并淋。
二是程序中出現(xiàn)除0的情況。
我這里是第二種情況珍昨，仔細(xì)檢查代碼后發(fā)現(xiàn)的確有除0的地方县耽，改正后OK。
-
hawl29@hawl29-PC:~/Desktop/cprogram/OS_experiment$ ./bf_test2_execfile 請輸入內(nèi)存空間大小: 1000 請輸入碎片大小: 1 請輸入測試次數(shù):11 段錯誤 hawl29@hawl29-PC:~/Desktop/cprogram/OS_experiment$ ./bf_test2_execfile 請輸入內(nèi)存空間大小: 1000 請輸入碎片大小: 1 請輸入測試次數(shù):10 內(nèi)存利用率為：0.00% 已分配分區(qū) 空閑分區(qū) (分區(qū)號, 作業(yè), 始址, 大小) (分區(qū)號, 始址, 大小) 1, 1, 0, 701 4, 933, 67 2, 2, 701, 184 3, 3, 885, 48提示段錯誤镣典，但程序又不是每次都無法執(zhí)行兔毙。
在網(wǎng)上查原因很多：訪問不存在的內(nèi)存地址，訪問系統(tǒng)保護(hù)的內(nèi)存地址兄春，空指針廢棄澎剥，堆棧溢出等等。
這里利用gdb工具定位問題赶舆。
hawl29@hawl29-PC:~/Desktop/cprogram/OS_experiment$ gcc -g bf_test2.c -o bf_test2_execfilegdb執(zhí)行后提示：
Program received signal SIGSEGV, Segmentation fault. 0x0000555555554a03 in add (head=0x555555757830, no=1, size=126) at bf_test2.c:41 41 if(q->size-size>SIZE) //SIZE是我們設(shè)置的碎片大小哑姚，若分配后空閑區(qū)剩余空間容量大于碎片大小，則需為剩余空間新建一個鏈表結(jié)點來記錄它 (gdb) q A debugging session is active.在定位的地方找到了如下代碼：
node型的指針在聲明后并沒有初始化涌乳，for循環(huán)要是沒有執(zhí)行
q=p時蜻懦，后面的if中q指針可能指向了一個不確定的地方甜癞。node *p,*q; for(p=head->next;p;p=p->next) { if(p->no==-1&&p->size>=size) //先找滿足容量大于作業(yè)大小的空閑區(qū) { if(p->size<min) //再找容量與作業(yè)大小最接近的空閑區(qū) { min=p->size; q=p; } } } if(q==NULL) return 0; //如果沒找到滿足要求的空閑區(qū)夕晓，則分配失敗?
-
