如何最小化固定分配方案所需的內存量？

下面的圖像可視化所需的壽命爲各種尺寸的16個內存塊：如何最小化固定分配方案所需的內存量？

enter image description here

什麼，我基本上是在尋找被賦予了許多大小大小的ň塊_我和壽命[開始_我，端_我），我們的總時間間隔期間返回到包含它們所需的最小尺寸的總的存儲塊和Ñ偏移，偏移_我，到用於輸入塊這個總的內存塊。

一個微不足道的非最優算法將是以下幾點：

int offsets[N]; 
offsets[0] = 0; 
int total_size = size[0]; 
for (int i = 1; i < N; ++i) 
{ 
    offsets[i] = offsets[i - 1] + size[i - 1]; 
    total_size += size[i]; 
}

我們目前的算法是按大小排序的塊，然後從最大處理它們到最小，尋找第一偏移，其中塊不與已分配的塊重疊。這本質上是一個貪婪的算法，所以我有一種感覺，可以做得更好。

該算法只需要在應用程序啓動時運行一次，因此它不必超快。分配的數量大約爲10-50個，爲了我們的目的，時間可以分散到大約50個固定大小的單位。

來源

2013-06-21 Andreas Brinck

這是一個非常模糊的提示，但不是規避貪婪算法的規範方式，嘗試幾種可能的解決方案，在這些方案中引入隨機性或其他偏離直接方法的偏差，並查看是否有改進？（例如，成對交換TSP等） – millimoose

（另外：你的可視化有點令人困惑，難道「使用的內存」會更好嗎？它可能會或可能不會讓你找到差距以及它們如何被填充。「分配ID」似乎不是很重要。） – millimoose

你能詳細說明一下嗎？分配ID基本上表示不同的對象，並且條形圖表示在其期間執行它們活動的程序的週期，這是非常重要的。 –

查找您的列表中的最小啓動時間和最大結束時間開始和結束的時間間隔。這是您感興趣的時間的總時間間隔（t_min，t_max）。接下來，將時間間隔劃分爲一些離散且均勻的時間間隔。讓這個間隔的長度爲或者。這基本上是你的內存管理的最大分辨率（你可能多少次可以釋放和/或聲明一塊內存）。

對於每個時間單位，確定哪個分配ID需要內存，以及它們當時需要的內存大小，稱它爲s（t，id）。在所有分配ID上總和s（t，id）是您在任何給定時間需要多少內存總量的下限。你不能做任何比這個函數的最大值更好的選擇，它沒有考慮到分配給同一區域而不在每個時間步移動它們的願望。

要找到每個項目的最佳位置，您可以使用啓發式搜索。基本上，搜索每個內存塊的所有可能起始地址的狀態空間，以尋找佔用最小內存總量的解決方案，您可以通過模擬時間從t_min到t_max的進程找到該解決方案。

可能值得嘗試的啓發式方法是在大塊佔據先前被其他大塊佔用的空間時使用分配，小塊放置在對策略的最大內存使用量貢獻較小的位置。由於策略聲稱的最大內存隨着時間的推移而變得單調，因此您還可以修剪發現的比迄今爲止看到的最差的策略。

啓發式搜索方法可能很慢，但聽起來像您比分配算法的運行時更關心最佳內存使用情況。

來源

2013-07-26 03:52:16 kgraney

如何最小化固定分配方案所需的內存量？

回答

相關問題