前言

學到了操作系統的的虛擬內存部分，硬件不太好的我學起來有些吃力，概念性知識點太多，所以我決定用軟件的方式，實現一下虛擬內存常用的算法，因為用到了指針，暫時用C語言寫一下Buddy算法、FIFO算法、LRU算法、Clock算法。我知道其實圖形化的算法展示更加直觀和容易理解，但是有些慚愧，JavaFX只是學了入門，動畫3D之類的還沒深入學，只能用自己的方式去實現，不過。目的主要是利用他們的思想。虛擬內存的知識會簡單的總結一下，但是不會詳細展開，因為我自己也不是很理解，只是先實現一下算法。

本博客實現一下Buddy算法

Buddy算法：操作系統學習之用C語言模擬伙伴(Buddy)算法
FIFO算法：操作系統學習之用C語言模擬FIFO算法
LRU算法：操作系統學習之用C語言模擬LRU算法
Clock算法：操作系統學習之用C語言模擬CLOCK算法

本源代碼原創，轉載請注明，同時由于本人才疏學淺，剛入門操作系統，如有錯誤敬請指教
本文原創，創作不易，轉載請注明！！！
本文鏈接
個人博客：https://ronglin.fun/?p=197
PDF鏈接：見博客網站
CSDN: https://blog.csdn.net/RongLin02/article/details/117340021

概念

在內存管理中，有動態分區方案和固定分區方案，但都存在一定的缺陷。固定分區方案限制了活動進程的數量，且若可用的分區大小與進程大小很不匹配，則內存空間的利用率就會非常低。動態分區的維護特別復雜，并且會引入進行壓縮的額外開銷。于是一個折中的方案提出–伙伴系統。

理論部分雖然十分頭疼，但是一定要仔仔細細的看。

教科書的解釋

操作系統-精髓與設計原理(第九版)的解釋
伙伴系統中可用內存塊的大小為2^k個字，L≤K≤U，其中2^L表示分配的最小快的尺寸，2^U表示分配的最大快的尺寸，通常2^U是可供分配的整個內存的大小。
最初，可用于分配的整個空間被視為一個大小塊為2^U的塊。若請求的大小s滿足2^U-1 ≤ s ≤ 2^U，則分配整個空間。否則，該塊分成兩個大小相等的伙伴，大小均為2^U-1。若有2^U-2 ≤ s ≤ 2^U-1，則給該請求分配兩個伙伴中的任何一個；否則，其中的一個伙伴又被分成兩半，持續這一過程，直到產生大于等于s的最小快，并且分配給該請求。在任何時候，伙伴系統中為所有大小為2ⁱ的“空洞”維護一個列表。空洞可通過對半分裂從i+1列表中移出，并且在i列表中產生兩個大小為2ⁱ的伙伴。當i列表中的一對伙伴都變成未分配的塊時，將他們從i列表中移出，合并為i+1列表中的一個塊。

理解

文字好多，看著有點吃力。其實仔細一分析，這個伙伴系統和一個名為“4096”的游戲很像，請求時，找一個“合適”的盒子放進程，當釋放的時候就像游戲的那樣，相同大小的塊合并。
不過，伙伴系統實際來說，用一個二叉樹表示更為合適.
我這里用一個鏈表數組來維護，
這里有個資料可以看看內存管理算法–Buddy伙伴算法

算法模擬

不多bb,開始頭禿

源代碼

本源代碼原創，轉載請注明，同時由于本人才疏學淺，剛入門操作系統，如有錯誤敬請指教

#include<stdio.h> #include<stdlib.h> #include <time.h> #define MAX_SIZE 1024 #define MAX_NUM_PROC 10 #define MAX_PROC_SIZE 100//進程結構體 //state 阻塞/初始-1 就緒0 運行1 struct Process {int pid;int ppid;int state;int p_size;void init(){pid = -1;ppid = -1;state = -1;p_size = 0;} }procs[MAX_NUM_PROC];//buddy中的每一塊的結構 struct Block {struct Process proc;int use;Block* next;void init(){proc.init();use = 0;next = NULL;} };//buddy鏈表的頭 struct Buddy {int all_size;Block* next;void init(){all_size = MAX_SIZE;next = NULL;} };void initBuddy(struct Buddy* L,int list_num);//初始化buddy隊列 void printState(struct Buddy* L,int list_num);//打印當前buddy隊列的狀態 int dealProcess(struct Buddy* L,int index,struct Process proc);//處理進程的請求 void SplitBlock(struct Buddy* L,int index);//將上一級的塊分裂成兩個當前塊int main() {//初始化int list_num = 0;for(int mi = MAX_SIZE;mi>0;mi/=2)list_num++;//printf("list_num = %d\n",list_num); list_num = 11;struct Buddy buddy[list_num];initBuddy(buddy,list_num);printState(buddy,list_num);//生成n個進程，每一個進程所需空間隨機for(int i=0;i<MAX_NUM_PROC;i++){srand((unsigned)time(NULL)*i);procs[i].init();procs[i].pid=i+1;procs[i].ppid=0;procs[i].p_size = rand() % MAX_PROC_SIZE +1; //隨機數范圍(0,MAX_PROC_SIZE];}//現在開始實現分配printf("\n現在開始實現分配\n");for(int i=0;i<MAX_NUM_PROC;i++){printf("\npid = %d,state = %d,p_size=%d\n",procs[i].pid,procs[i].state,procs[i].p_size);if(procs[i].p_size ==0){printf("此進程所需大小為0,不需要分配空間\n");continue;}int res=dealProcess(buddy,list_num-1,procs[i]);//int res=0;if(res){printf("分配成功，分配塊大小:%d\n",res);procs[i].state=1;}else{printf("分配失敗\n");}}printState(buddy,list_num);return 0; }void initBuddy(struct Buddy* L,int list_num) {int size_two=1;struct Block* first_block =(struct Block*)malloc(sizeof(struct Block));first_block->init();for(int i=0;i<list_num;i++){L[i].init();L[i].all_size = size_two;if(i ==10)//設置默認的最大塊{L[i].next=first_block;}size_two *= 2;} }void printState(struct Buddy* L,int list_num) {for(int i=0;i<list_num;i++){printf("size=%d: ",L[i].all_size);struct Block* p=L[i].next;while(p){if(p->use){printf("pid=%d",p->proc.pid);}else{printf("use=%d",p->use);}printf(";");p=p->next;}printf("\n");}}int dealProcess(struct Buddy* L,int index,struct Process proc) {if(index <= -1 || L[index].all_size<proc.p_size)return 0;if(index==0 || L[index-1].all_size < proc.p_size )//當前的塊就是要找的塊{int flag = 0;struct Block* p = L[index].next;while(p){if(p->use==0){flag=1;p->proc=proc;p->use=1;return L[index].all_size;}p=p->next;}if(flag==0){SplitBlock(L,index);//分裂大塊//現在尋找執行完分裂之后是否存在可用的塊p = L[index].next;while(p){if(p->use==0){flag=1;p->proc=proc;p->use=1;return L[index].all_size;}p=p->next;}if(flag==0)return 0;}}else{return dealProcess(L,index-1,proc);} }void SplitBlock(struct Buddy* L,int index) {if(L[index].all_size== MAX_SIZE)return ;int flag=0;struct Block* p = L[index+1].next;struct Block* q = NULL;while(p)//尋找空閑的塊{if(p->use == 0){flag=1;break;}p=p->next;}if(flag ==0){SplitBlock(L,index+1);}p = L[index+1].next;while(p)//尋找空閑的塊{if(p->use == 0)//找到了,大塊分裂成兩個本塊{if(q==NULL)//說明p指向的塊是頭節點之后的那個{L[index+1].next=p->next;}else{q->next=p->next;}free(p);//尾插法插入兩個新塊struct Block* t1 =(struct Block*)malloc(sizeof(struct Block));struct Block* t2 =(struct Block*)malloc(sizeof(struct Block));t1->init();t2->init();t1->next=t2;if(L[index].next==NULL){L[index].next=t1;}else{struct Block* t = L[index].next;while(t->next)t=t->next;t->next=t1;}break;}q=p;p=p->next;}}

運行結果

size=1: size=2: size=4: size=8: size=16: size=32: size=64: size=128: size=256: size=512: size=1024: use=0;現在開始實現分配pid = 1,state = -1,p_size=39 分配成功，分配塊大小:64pid = 2,state = -1,p_size=2 分配成功，分配塊大小:2pid = 3,state = -1,p_size=66 分配成功，分配塊大小:128pid = 4,state = -1,p_size=29 分配成功，分配塊大小:32pid = 5,state = -1,p_size=92 分配成功，分配塊大小:128pid = 6,state = -1,p_size=56 分配成功，分配塊大小:64pid = 7,state = -1,p_size=19 分配成功，分配塊大小:32pid = 8,state = -1,p_size=82 分配成功，分配塊大小:128pid = 9,state = -1,p_size=45 分配成功，分配塊大小:64pid = 10,state = -1,p_size=9 分配成功，分配塊大小:16 size=1: size=2: pid=2;use=0; size=4: use=0; size=8: use=0; size=16: pid=10; size=32: pid=4;pid=7;use=0; size=64: pid=1;pid=6;pid=9;use=0; size=128: pid=3;pid=5;pid=8; size=256: use=0; size=512: size=1024:

結果的圖示：

代碼缺點

先說這個模擬的缺點，缺點是：只是維護了鏈表數組，并沒有維護"伙伴"這個性質，僅僅是進程有需求，就按照buddy分配，沒有維護哪兩個塊是伙伴，也就是說只體現了分配，沒體現伙伴。所以沒寫釋放進程之后的塊合并過程，因為不知道哪兩個塊是伙伴，要想解決也簡單，就是在Block結構體中，再加一個屬性，用來表示"伙伴"，然后分裂和合并的時候，根據這個屬性確定自己的"伙伴"。
實現匆忙，再加上本人理論不扎實，有好想法可告訴我。

解釋代碼

代碼250多行，解釋起來有點麻煩，簡單的解釋一下。
先說輸出：
use=0表示這個塊被切割了，但是還沒用，如果被用了，就輸出是哪個進程占用。可以對照上圖查看。
結構體
進程結構體
這里邊包含了一些一個進程的基本信息，因為不涉及到硬件，只是純軟件模擬，比PCB中的屬性少了很多，然后定義是在全局中定義了MAX_NUM_PROC個進程，每個進程的初始化是在主函數的for循環中，用了一個隨機函數，生成進程的所需空間，隨機數范圍是(0,MAX_PROC_SIZE]，可根據自己的需要修改。
Buddy結構體
這個是每個鏈表的頭，數據域提供了這個鏈表的表示的大小，比如表示的512、64等。
Block結構體
每一個塊的數據結構，數據域有兩個一個是存放的進程，還有一個是是否被使用，這個use屬性的意思是，伙伴系統分裂出來兩個，一個被使用，而它的伙伴可能還沒被使用。
主函數
主函數的工作比較簡單，就是初始化buddy鏈表，生成MAX_NUM_PROC個進程，然后按照buddy算法分配內存給進程。
子函數

void initBuddy(struct Buddy* L,int list_num);//初始化buddy隊列 void printState(struct Buddy* L,int list_num);//打印當前buddy隊列的狀態 int dealProcess(struct Buddy* L,int index,struct Process proc);//處理進程的請求 void SplitBlock(struct Buddy* L,int index);//將上一級的塊分裂成兩個當前塊

一共四個子函數，第一個和第二個是用來描述buddy鏈表，難點是后兩個遞歸函數的實現過程。
dealProcess()函數是遞歸尋找 對于 進程 “適合"大小的塊，然后將塊分給進程。如果沒找到這個塊，就會調用SplitBlock()函數，將上層的大塊，依次遞歸分裂生成小塊，直到本層，如果分裂完，還沒有適合的塊，就返回錯誤，會輸出"分配失敗”。

總結

嘗試過用面向對象的寫法，最開始用Java寫，結果發現由于Java的指針機制，鏈表的實現太麻煩，后來又用了C++的面向對象，發現需要太多的引用和指針，維護鏈表著實有點大材小用，而且有點麻煩，最后決定用面向過程的思維寫，既然是面向過程，最后決定用C語言實現，buddy算法思維容易理解，可真正實現的時候發現了很多很多問題。這些算法真的要自己敲一遍才知道它真正的意義，獲益匪淺。
=w=

總結

以上是生活随笔為你收集整理的操作系统学习之用C语言模拟伙伴(Buddy)算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。