操作系統(tǒng)課程設(shè)計(jì)-動(dòng)態(tài)異長(zhǎng)分區(qū)的存儲(chǔ)分配與回收算法

操作系統(tǒng)課程設(shè)計(jì)——?jiǎng)討B(tài)異長(zhǎng)分區(qū)的存儲(chǔ)分配與回收算法CATALOGUE目錄引言動(dòng)態(tài)異長(zhǎng)分區(qū)基本原理存儲(chǔ)分配算法詳解回收算法詳解實(shí)現(xiàn)過(guò)程與代碼分析實(shí)驗(yàn)結(jié)果展示與性能評(píng)估總結(jié)與展望01引言課程設(shè)計(jì)目的01理解和掌握動(dòng)態(tài)異長(zhǎng)分區(qū)存儲(chǔ)分配的基本原理和方法。02學(xué)習(xí)和掌握動(dòng)態(tài)異長(zhǎng)分區(qū)存儲(chǔ)分配算法的實(shí)現(xiàn)過(guò)程。通過(guò)實(shí)踐，提高學(xué)生的編程能力和解決問(wèn)題的能力。03動(dòng)態(tài)異長(zhǎng)分區(qū)概念動(dòng)態(tài)異長(zhǎng)分區(qū)是一種存儲(chǔ)管理技術(shù)，它將內(nèi)存空間劃分為大小不等的分區(qū)，每個(gè)分區(qū)的大小可以動(dòng)態(tài)地改變。動(dòng)態(tài)異長(zhǎng)分區(qū)允許程序在運(yùn)行時(shí)申請(qǐng)和釋放內(nèi)存空間，提高了內(nèi)存的利用率和程序的靈活性。存儲(chǔ)分配與回收算法重要性存儲(chǔ)分配算法決定了內(nèi)存空間的分配方式，直接影響系統(tǒng)的性能和程序的執(zhí)行效率。回收算法負(fù)責(zé)將不再使用的內(nèi)存空間回收并重新利用，避免了內(nèi)存浪費(fèi)。合理的存儲(chǔ)分配與回收算法可以提高內(nèi)存的利用率，減少內(nèi)存碎片的產(chǎn)生，從而提高系統(tǒng)的整體性能。02動(dòng)態(tài)異長(zhǎng)分區(qū)基本原理固定分區(qū)分區(qū)大小固定，分配時(shí)容易產(chǎn)生內(nèi)部碎片。動(dòng)態(tài)分區(qū)分區(qū)大小可變，根據(jù)進(jìn)程需求動(dòng)態(tài)分配，減少內(nèi)部碎片。異長(zhǎng)分區(qū)分區(qū)長(zhǎng)度不同，適應(yīng)不同大小的進(jìn)程需求，提高內(nèi)存利用率。分區(qū)類型及特點(diǎn)動(dòng)態(tài)分區(qū)分配策略首次適應(yīng)算法（FirstFit）：從空閑分區(qū)表的第一個(gè)表目起查找該表，把最先能夠滿足要求的空閑區(qū)分配給作業(yè)，這種方法目的在于減少查找時(shí)間。為適應(yīng)這種算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按地址由低到高進(jìn)行排序。該算法優(yōu)先使用低址部分空閑區(qū)，在低址空間造成許多小的空閑區(qū)，在高地址空間保留大的空閑區(qū)。最佳適應(yīng)算法（BestFit）：從全部空閑區(qū)中找出能滿足作業(yè)要求的、且大小最小的空閑分區(qū)，這種方法能使碎片盡量小。為適應(yīng)這種算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按大小從小到大進(jìn)行排序，自表頭開(kāi)始查找到第一個(gè)滿足要求的自由分區(qū)分配。該算法保留大的空閑區(qū)，但造成許多小的空閑區(qū)。最壞適應(yīng)算法（WorstFit）：它在掃描整個(gè)空閑分區(qū)或鏈表時(shí)，總是挑選一個(gè)最大的空閑區(qū)，從中分割出與請(qǐng)求大小相符的空間給作業(yè)使用。該算法要求將空閑區(qū)按大小從大到小排序，自表頭開(kāi)始查找到第一個(gè)滿足要求的自由分區(qū)分配。該算法可使得剩下空閑區(qū)的空間最大，但缺點(diǎn)是始終留下高地址部分的大空閑區(qū)，而低地址部分不斷被劃分，留下許多難以利用的、小的空閑區(qū)，且每次分配時(shí)查找時(shí)間最長(zhǎng)。碎片產(chǎn)生原因動(dòng)態(tài)異長(zhǎng)分區(qū)在分配和回收內(nèi)存時(shí)，由于進(jìn)程大小不固定，可能導(dǎo)致內(nèi)存中出現(xiàn)一些無(wú)法被利用的小塊內(nèi)存區(qū)域，這些區(qū)域被稱為“碎片”。通過(guò)移動(dòng)內(nèi)存中所有進(jìn)程的位置，將分散的空閑區(qū)集中在一起，形成連續(xù)的可用內(nèi)存空間。這種方法需要停止CPU對(duì)內(nèi)存的操作并更新所有相關(guān)表項(xiàng)，開(kāi)銷較大。將進(jìn)程劃分為多個(gè)大小固定的段，每段分配一個(gè)連續(xù)的內(nèi)存區(qū)域。通過(guò)段的共享和保護(hù)機(jī)制，可以減少碎片的產(chǎn)生。將內(nèi)存空間劃分為大小相等的頁(yè)框，進(jìn)程以頁(yè)為單位進(jìn)行內(nèi)存分配。通過(guò)頁(yè)表和虛擬內(nèi)存機(jī)制，可以實(shí)現(xiàn)離散分配和減少碎片。緊湊技術(shù)分段技術(shù)分頁(yè)技術(shù)碎片產(chǎn)生與處理03存儲(chǔ)分配算法詳解從空閑分區(qū)表的第一個(gè)表目起查找該表，把最先能夠滿足要求的空閑區(qū)分配給作業(yè)，這種方法目的在于減少查找時(shí)間。為適應(yīng)這種算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按地址由低到高進(jìn)行排序。該算法優(yōu)先使用低址部分空閑區(qū)，在低址空間造成許多小的空閑區(qū)，在高地址空間保留大的空閑區(qū)。當(dāng)作業(yè)申請(qǐng)空間時(shí)，從鏈表頭開(kāi)始查找，選擇第一個(gè)大小滿足要求的空閑分區(qū)分配給作業(yè)。若未找到大小合適的空閑分區(qū)，則分配失敗。當(dāng)作業(yè)釋放空間時(shí)，需要合并空閑分區(qū)。首先判斷釋放分區(qū)的前后是否有相鄰的空閑分區(qū)，如果有則進(jìn)行合并。然后調(diào)整空閑分區(qū)鏈表。算法思想分配過(guò)程回收過(guò)程首次適應(yīng)算法（FF）從全部空閑區(qū)中找出能滿足作業(yè)要求的、且大小最小的空閑分區(qū)，這種方法能使碎片盡量小。為適應(yīng)這種算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按大小從小到大進(jìn)行排序，自表頭開(kāi)始查找到第一個(gè)滿足要求的自由分區(qū)分配。該算法保留大的空閑區(qū)，但造成許多小的空閑區(qū)。當(dāng)作業(yè)申請(qǐng)空間時(shí)，從鏈表頭開(kāi)始查找，選擇第一個(gè)大小滿足要求的空閑分區(qū)分配給作業(yè)。若未找到大小合適的空閑分區(qū)，則分配失敗。當(dāng)作業(yè)釋放空間時(shí)，需要合并空閑分區(qū)。首先判斷釋放分區(qū)的前后是否有相鄰的空閑分區(qū)，如果有則進(jìn)行合并。然后調(diào)整空閑分區(qū)鏈表。算法思想分配過(guò)程回收過(guò)程最佳適應(yīng)算法（BF）算法思想01它在整個(gè)存儲(chǔ)空間中查找最大的空閑區(qū)，從中割下一塊與請(qǐng)求空間大小相等的空間分配給作業(yè)。這樣能使剩下的空閑區(qū)不至于太小，產(chǎn)生的碎片較大，適合用于請(qǐng)求分配空間大小不等的場(chǎng)合。分配過(guò)程02當(dāng)作業(yè)申請(qǐng)空間時(shí)，從鏈表頭開(kāi)始查找，選擇第一個(gè)大小滿足要求的空閑分區(qū)分配給作業(yè)。若未找到大小合適的空閑分區(qū)，則分配失敗?；厥者^(guò)程03當(dāng)作業(yè)釋放空間時(shí)，需要合并空閑分區(qū)。首先判斷釋放分區(qū)的前后是否有相鄰的空閑分區(qū)，如果有則進(jìn)行合并。然后調(diào)整空閑分區(qū)鏈表。最差適應(yīng)算法（WF）04回收算法詳解回收過(guò)程概述01當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束或主動(dòng)釋放內(nèi)存時(shí)，操作系統(tǒng)需要回收其占用的內(nèi)存空間。02回收過(guò)程包括：確定回收分區(qū)的大小和位置，更新內(nèi)存分配表，合并空閑分區(qū)等步驟。03在回收過(guò)程中，需要注意保護(hù)其他進(jìn)程的數(shù)據(jù)和代碼不受影響，同時(shí)確保內(nèi)存管理的正確性和效率。在回收內(nèi)存后，可能會(huì)產(chǎn)生多個(gè)相鄰的空閑分區(qū)，為了提高內(nèi)存利用率，需要將這些空閑分區(qū)合并成一個(gè)大的空閑分區(qū)。立即合并策略在每次回收內(nèi)存后立即檢查并合并相鄰的空閑分區(qū)；延遲合并策略在需要分配內(nèi)存時(shí)才進(jìn)行空閑分區(qū)的合并；定時(shí)合并策略則周期性地檢查并合并空閑分區(qū)。常見(jiàn)的空閑分區(qū)合并策略包括：立即合并、延遲合并和定時(shí)合并?？臻e分區(qū)合并策略內(nèi)存泄漏是指程序在申請(qǐng)內(nèi)存后，未能正確釋放，導(dǎo)致系統(tǒng)內(nèi)存資源的浪費(fèi)。為了防止內(nèi)存泄漏，操作系統(tǒng)可以采取以下措施：提供內(nèi)存泄漏檢測(cè)工具，幫助程序員定位和修復(fù)內(nèi)存泄漏問(wèn)題；采用垃圾回收機(jī)制，自動(dòng)回收不再使用的內(nèi)存；限制每個(gè)進(jìn)程可使用的最大內(nèi)存量，避免某個(gè)進(jìn)程占用過(guò)多內(nèi)存導(dǎo)致系統(tǒng)崩潰。防止內(nèi)存泄漏措施05實(shí)現(xiàn)過(guò)程與代碼分析VS設(shè)計(jì)一個(gè)空閑分區(qū)表的數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)系統(tǒng)中所有空閑分區(qū)的信息。每個(gè)空閑分區(qū)表項(xiàng)應(yīng)包括分區(qū)起始地址、分區(qū)長(zhǎng)度和分區(qū)狀態(tài)等信息。初始化空閑分區(qū)表，將系統(tǒng)的整個(gè)內(nèi)存空間作為一個(gè)空閑分區(qū)加入到空閑分區(qū)表中。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)及初始化當(dāng)有進(jìn)程請(qǐng)求分配內(nèi)存空間時(shí)，調(diào)用存儲(chǔ)分配函數(shù)。在空閑分區(qū)表中查找合適的空閑分區(qū)，根據(jù)分配算法（如首次適應(yīng)算法、最佳適應(yīng)算法等）選擇一個(gè)空閑分區(qū)進(jìn)行分配。如果找到的空閑分區(qū)大小大于請(qǐng)求的大小，則將該空閑分區(qū)分為兩部分：一部分分配給進(jìn)程，另一部分仍然作為空閑分區(qū)留在空閑分區(qū)表中。如果找到的空閑分區(qū)大小等于請(qǐng)求的大小，則將該空閑分區(qū)整個(gè)分配給進(jìn)程，并從空閑分區(qū)表中刪除該分區(qū)。更新空閑分區(qū)表和已分配分區(qū)表。0102030405存儲(chǔ)分配函數(shù)實(shí)現(xiàn)輸入標(biāo)題02010403回收函數(shù)實(shí)現(xiàn)當(dāng)進(jìn)程釋放其占用的內(nèi)存空間時(shí)，調(diào)用回收函數(shù)。如果合并后的空閑分區(qū)大小超過(guò)了某個(gè)閾值，可以考慮將該空閑分區(qū)分割成更小的空閑分區(qū)，以便更好地滿足后續(xù)進(jìn)程的內(nèi)存分配請(qǐng)求。如果釋放的內(nèi)存空間與相鄰的空閑分區(qū)相鄰，則將它們合并成一個(gè)更大的空閑分區(qū)，以減少空閑分區(qū)的數(shù)量并提高內(nèi)存利用率。將釋放的內(nèi)存空間加入到空閑分區(qū)表中，并更新空閑分區(qū)表。06實(shí)驗(yàn)結(jié)果展示與性能評(píng)估處理器IntelCorei7-8700K內(nèi)存16GBDDR4RAM實(shí)驗(yàn)環(huán)境搭建及參數(shù)設(shè)置512GBSSD存儲(chǔ)Windows10Professional操作系統(tǒng)實(shí)驗(yàn)環(huán)境搭建及參數(shù)設(shè)置編程語(yǔ)言：C/C編譯器：GCC7.3.0實(shí)驗(yàn)環(huán)境搭建及參數(shù)設(shè)置03回收算法：合并相鄰空閑區(qū)01初始內(nèi)存塊大?。?024KB02分配算法：首次適應(yīng)算法（FirstFit）實(shí)驗(yàn)環(huán)境搭建及參數(shù)設(shè)置請(qǐng)求序列[200KB,300KB,150KB,50KB,80KB]分配結(jié)果[200KB@100KB,300KB@400KB,150KB@800KB,50KB@950KB,80KB@1000KB]結(jié)果展示：分配、回收、碎片情況統(tǒng)計(jì)結(jié)果展示：分配、回收、碎片情況統(tǒng)計(jì)[200KB,150KB]回收序列[100KB-300KB,400KB-800KB,950KB-1030KB]回收后空閑區(qū)最大碎片大小：70KB平均碎片大?。?3.33KB碎片總數(shù)：3結(jié)果展示：分配、回收、碎片情況統(tǒng)計(jì)分配算法時(shí)間復(fù)雜度：O(n)回收算法時(shí)間復(fù)雜度：O(n)性能評(píng)估：時(shí)間復(fù)雜度、空間利用率等初始空間利用率：0%最終空間利用率：76.9%性能評(píng)估：時(shí)間復(fù)雜度、空間利用率等性能評(píng)估：時(shí)間復(fù)雜度、空間利用率等010203內(nèi)存分配成功率：100%內(nèi)存回收成功率：100%空間浪費(fèi)率：23.1%07總結(jié)與展望實(shí)現(xiàn)了動(dòng)態(tài)異長(zhǎng)分區(qū)的存儲(chǔ)分配算法通過(guò)設(shè)計(jì)合適的分區(qū)分配策略，實(shí)現(xiàn)了對(duì)內(nèi)存空間的動(dòng)態(tài)劃分和分配，滿足了不同大小進(jìn)程的內(nèi)存需求。實(shí)現(xiàn)了內(nèi)存回收算法通過(guò)設(shè)計(jì)內(nèi)存回收機(jī)制，能夠及時(shí)釋放不再使用的內(nèi)存空間，提高了內(nèi)存利用率。實(shí)現(xiàn)了內(nèi)存空間的緊湊通過(guò)移動(dòng)內(nèi)存中的進(jìn)程，消除了內(nèi)存碎片，使得內(nèi)存空間得到更加有效的利用。課程設(shè)計(jì)成果總結(jié)存在問(wèn)題及改進(jìn)方向當(dāng)前的分配算法在處理大量進(jìn)程請(qǐng)求時(shí)，可能會(huì)出現(xiàn)性能瓶頸，未來(lái)可以考慮引入更高效的數(shù)據(jù)結(jié)構(gòu)和算法來(lái)提高分配效率。內(nèi)存回收機(jī)制不完善當(dāng)前的內(nèi)存回收機(jī)制在處理某些特殊情況時(shí)可能會(huì)出現(xiàn)問(wèn)題，例如處理跨多個(gè)分區(qū)的大進(jìn)程時(shí)可能會(huì)出現(xiàn)回收不完全的情況，未來(lái)需要進(jìn)一步完善回收機(jī)制。缺乏對(duì)多用戶環(huán)境的支持當(dāng)前的設(shè)計(jì)主要針對(duì)單用戶環(huán)境，對(duì)于多用戶環(huán)境可能會(huì)出現(xiàn)一些問(wèn)題，例如不同用戶之間的內(nèi)存隔離和權(quán)限控制等，未來(lái)需要考慮加入多用戶支持。分配算法效率有待提高未來(lái)發(fā)展趨勢(shì)預(yù)測(cè)人工智能和機(jī)器學(xué)習(xí)技術(shù)的發(fā)展將為操作系統(tǒng)中內(nèi)存管理技術(shù)帶來(lái)新的