1.1 ?設計目的

理解存儲管理的功能，掌握動態(tài)異長分區(qū)內存管理中的最佳適應算法。

1.2 ?設計要求

本設計要求模擬最佳適應算法的分配算法和回收算法。

1.3??數據結構設計

為了實現存儲資源的分配和回收，操作系統(tǒng)需要記錄內存資源使用情況，即哪些區(qū)域尚未分配，哪些區(qū)域已經分配以及分配給哪些進程等。為此一般需要兩個表，一個為分配表, 另外一個為空閑區(qū)域表。前者記錄已經分配的區(qū)域, 后者記錄著所有當前未被進程占用的空閑區(qū)域, 如圖1-1所示。

顯然, 沒有記錄于表中的區(qū)域即為已被進程所占用的非空閑區(qū)域，在實際的操作系統(tǒng)中，這些區(qū)域登記在進程的PCB中。而PCB中除了關于內存資源的信息外，還有其它大量信息。

由于本設計是對存儲管理算法的模擬，所以用一個線程來代表一個進程，用線程駐留區(qū)域表來描述線程占用的內存空間，如圖1-2所示。

同時，需要一張表來記錄各個線程對內存的請求信息，如圖1-3所示。

1.4??算法設計

1.4.1??算法結構設計

分配時取滿足申請要求且長度最小的空閑區(qū)域。在實現時, 可將系統(tǒng)中所有的空閑區(qū)域按照長度由小到大的次序依次記錄于空閑區(qū)域表中。與最先適應算法相類似, 當進程申請存儲空間時, 系統(tǒng)由表的頭部開始查找, 取第一個滿足要求的表目。如果該表目所對應的區(qū)域長度恰好與所申請的區(qū)域長度相同, 則將該區(qū)域全部分配給申請者。否則將該區(qū)域分割為兩部分, 一部分的長度與所申請的長度相同, 將其分配給申請者；另一部分即剩余部分的長度為原長度與分配長度之差, 由于剩余部分的長度已經改變，所以應重新將其按長度從小到大的順序插入到空閑區(qū)域表中。

回收時，不僅要按回收區(qū)的首地址查詢空閑區(qū)表，找到與回收區(qū)相臨的空閑區(qū)，將其合并到相臨區(qū)中，而且要把合并后的回收區(qū)按照長度遞增的順序插入到空閑區(qū)域表的適當位置。

1.4.2??設計并分析測試數據

假設初始內存布局如圖1-4，圖中的起始地址以及大小都以KB來衡量。

由圖1-4可見，初始時共有五個線程駐留在內存，它們是a,b,c,d,e，線程駐留區(qū)表如圖1-5；還有五個空閑區(qū)，空閑區(qū)域表如圖1-6。

假設現在有三個線程提出內存申請，申請情況見圖1-7。經過分析我們得到在每種分配算法下這三個線程所申請到的內存情況。圖1-8是最佳適應算法分配情況。

1.4.3??程序設計

程序包含兩個文件，一個是頭文件variable_partition.h，另一個是源程序文件variable_partition.cpp。在頭文件中定義了宏、數據結構、全局變量、函數聲明，源程序中含有各個函數的實現。

在頭文件中，結構體FREEAREA、REQUIRE_MEMORY、THREAD_RESIDENCE_MEMORY分別對應于圖1-1、圖1-2、圖1-3中的一行，不同之處是為了構成鏈表在三個結構體中都有前向指針。數組init_free_area_table對應于圖1-6，數組init_thread_require_memory_table對應于圖1-5，數組init_thread_residence_memory_table對應于圖1-7，為了實現動態(tài)分配與釋放，用鏈表重新組織空閑區(qū)域表、線程駐留區(qū)表和內存申請表，全局變量p_free_area_list是空閑區(qū)鏈首，p_thread_require_memory_queue是內存申請隊列的隊首，p_thread_residence_memory_list是線程駐留區(qū)鏈首，tail_thread_residence_memory_list是線程駐留區(qū)鏈尾，由于線程駐留區(qū)鏈表被內存分配函數和內存釋放函數共享，故用臨界區(qū)變量CS_THREAD_MEMORY_LIST來保護，同理，屏幕是所有線程共享的，所以用臨界區(qū)變量CS_SCREEN來保護,空閑區(qū)鏈表被內存分配函數和內存釋放函數共享，故用臨界區(qū)變量CS_FREEAREA_LIST來保護。h_thread是線程句柄數組，用來存放各個線程的句柄。

程序共包含13個函數，按照作用可以將它們分成五組。

第一組包括函數print_space()和函數display_thread_residence_memory()，前者用來顯示若干個空格，后者用來顯示線程駐留區(qū)表；

第二組共十一個函數，用來實現最佳適應分配法，它們的名稱及功能如圖1-9。

1.4.4??程序流程圖設計

1.函數關系調用圖

圖1-10???函數關系調用圖

2.主要程序流程圖

圖1-11???主要程序流程圖

3.內存申請函數流程圖

圖1-12??內存申請函數流程圖

4.內存釋放函數流程圖

圖1-13??內存釋放函數流程圖

1.5 ?程序代碼

內存申請函數

// 最佳適應分配算法的內存申請函數
int BF_require_memory(int size) {
    FREEAREA *p = p_free_area_list;
    FREEAREA *prev = NULL;
    int best_fit_start = -1;
    int best_fit_size = INT_MAX;
    // 尋找最佳適應的空閑區(qū)
    while (p != NULL) {
        if (p->size >= size && p->size < best_fit_size) {
            best_fit_start = p->start_address;
            best_fit_size = p->size;
            prev = p;
        }
        p = p->next;
    }
    // 如果找到了最佳適應的空閑區(qū)
    if (best_fit_start != -1) {
        // 劃分空閑區(qū)
        if (best_fit_size > size) {
            FREEAREA *new_free_area = (FREEAREA *)malloc(sizeof(FREEAREA));
            new_free_area->next = prev->next;
            new_free_area->start_address = best_fit_start + size;
            new_free_area->size = best_fit_size - size;

            prev->next = new_free_area;
        }
        // 從空閑區(qū)鏈表中刪除已分配的空閑區(qū)
        if (prev == NULL) {
            p_free_area_list = p_free_area_list->next;
        } else {
            prev->next = prev->next->next;
        }
        return best_fit_start;
    }
    return -1; // 內存申請失敗
}

內存釋放函數

// 最佳適應分配算法的內存釋放函數
void BF_release_memory(int start_address,int size){
EnterCriticalSection(&CS_FREEAREA_LIST);
    FREEAREA *temp, *p, *pp;
    p=p_free_area_list;
    temp = new FREEAREA;
    temp->start_address=start_address;
    temp->size=size;
    temp->next=NULL;
    int flag=0;
    while(1) {
  if(p->next!=NULL&&start_address+size<=p->next->start_address&&start_address>=p->start_address+p->size) {
            temp->next=p->next;
            p->next=temp;
            flag=1;
        }
        if(flag==1||p->next==NULL) break;
        p=p->next;
    }
    if(start_address>=p->start_address+p->size) {
        if(flag==0)
            p->next=temp;
    } else {
        if(flag==0) {
            pp=p_free_area_list;
            temp->next=pp;
            pp->next=p_free_area_list->next;
            p_free_area_list=temp;
        }
    }
    FREEAREA *ppp;
    ppp=p_free_area_list;
    while(1) {
        if(ppp->next!=NULL) {
            if(ppp->start_address+ppp->size==ppp->next->start_address) {
                ppp->size+= ppp->next->size;
                if(ppp->next->next!=NULL)
                    ppp->next=ppp->next->next;
                else {
                    ppp->next=NULL;
                }
                continue;
            }
        }
        if(ppp->next!=NULL) ppp=ppp->next;
        else break;
    }
    EnterCriticalSection(&CS_SCREEN);
    THREAD_RESIDENCE_MEMORY *q;
    q = p_thread_residence_memory_list;
    if (q->start_address == start_address) {
        p_thread_residence_memory_list = p_thread_residence_memory_list->next;
    } else {
        while (q->next != NULL) {
            if (q->next->start_address == start_address) {
                if (q->next == tail_thread_residence_memory_list) {
                    tail_thread_residence_memory_list = q;}
                q->next = q->next->next;
                break;
}
            q = q->next;
}
}
    LeaveCriticalSection(&CS_SCREEN);
    LeaveCriticalSection(&CS_FREEAREA_LIST);
}

1.6 ?運行結果

1.6.1??運行結果截圖

圖1-14??運行結果一

圖1-15??運行結果二

1.6.2??運行結果分析

1.7??設計總結

????????在設計最佳適應算法的動態(tài)異長分區(qū)內存管理系統(tǒng)時，理解了存儲管理的關鍵功能，并掌握了最佳適應算法的分配和回收過程。在數據結構設計方面，建立了兩張關鍵表：分配表和空閑區(qū)域表。分配表記錄已經分配的內存區(qū)域，而空閑區(qū)域表則記錄當前未被進程占用的空閑內存區(qū)域。通過線程駐留區(qū)域表和內存申請表，成功地將進程與其內存請求信息關聯起來，以便模擬實際存儲管理情境。在算法設計方面，最佳適應算法的核心思想是分配時選擇滿足要求且長度最小的空閑區(qū)域。實現了按照空閑區(qū)域長度由小到大的順序記錄空閑區(qū)域表，并在分配時從表頭開始查找符合條件的區(qū)域。若找到匹配的區(qū)域，根據申請大小進行分配或分割，并重新排序插入剩余部分。在回收過程中，實現了按照回收區(qū)的首地址查詢空閑區(qū)表，找到相鄰的空閑區(qū)并合并。然后，將合并后的回收區(qū)按長度遞增的順序插入到空閑區(qū)域表的適當位置。同時每次運行結果不同的原因主要是因為程序中使用了多線程，多線程程序的執(zhí)行順序是不確定的。在多線程環(huán)境中，操作系統(tǒng)的調度器決定了每個線程何時獲得 CPU 時間。不同運行中線程的交替執(zhí)行順序可能不同，從而導致不同的結果，對于操作系統(tǒng)中進程的并發(fā)有了更好的理解。文章來源地址http://www.zghlxwxcb.cn/news/detail-827173.html

到了這里，關于動態(tài)異長分區(qū)內存分配與去配算法的設計-最佳適應算法的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！