私はどのようにしてストアを最善のフィットのためのメモリの始まりと終わりにすることができますか？

Question

私はunsigned int = 100000000の最大合計サイズを与えられており、各プロセッサのサイズを入力する必要がありますが、配列の量は分かりません...オンラインで見た人のほとんどは既に定義済みです配列のサイズがないので、私は他の方法が配列のサイズなしで最適なアルゴリズムを実行するかどうか疑問に思った。私はこのアルゴリズムを作成する良い方法を得ることができないようです。私はまた、二重リンクリストを試して、私は問題を抱えています

int MaxMem = 20000000; 

struct PCB 
{ 
    int ProcessID; 
    unsigned int ProcessorSize; 
    unsigned int Begin; 
    unsigned int End; 
    int sumOfMemory = 0; 
    PCB() 
    { 
     ProcessID = NULL; 
     ProcessorSize = NULL; 
     priority = NULL; 
    } 

    bool operator < (const PCB &c) 
    { 
     return priority < c.priority; 
    } 
    bool operator > (const PCB &c) 
    { 
     return priority > c.priority; 
    } 

    void rem(PCB &a) 
    { 
     a.ProcessID = NULL; 
     a.ProcessorSize = NULL; 
     a.priority = NULL; 
     sumOfMemory -= a.ProcessorSize; 
    } 
}; 
static int start = NULL; 
static int temp; 

void best_fit(PCB a,vector<int> &memory) 
{ 
    int bestfit = -1; 
    unsigned int endMem = MaxMem; 
    unsigned int tempMem = MaxMem; 
     if((start == NULL) && (bestfit = -1)) 
     { 
      temp = start; 
      memory.push_back(a.ProcessorSize); 
      bestfit = a.ProcessID; 
      start = a.ProcessorSize; 
      tempMem -= a.ProcessorSize; 
      cout << "pushed" << endl; 
     } 
     else if((start != NULL)&& (bestfit = -1) && (a.ProcessorSize < memorySize) && (a.sumOfMemory < tempMem)) 
     { 
      memory.push_back(a.ProcessorSize); 
      bestfit = a.ProcessID; 
      tempMem -= a.ProcessorSize; 
      temp = start; 
      start += a.ProcessorSize; 
      cout << "pushed!" << endl; 
     } 
     else 
     { 
      cout << "No space" << endl; 
     } 

} 
int main() 
{ 
    PCB pcb; 
    while(true) 
    { 
     vector<int> mem; 
     cout << "process ID?" << endl; 
     cin >> pcb.ProcessID; 
     cout << "enter processor size?" << endl; 
     cin >> pcb.ProcessorSize; 
     bestfit(pcb,mem); 
    } 

Answer 1

基本的なブロックアロケータが好きですね。教師は、それが機能している限り、どのように実装されているか気にしません。それは方向性に関してはあまり役に立たないかもしれませんが、私たちの実装には多くの余裕があります。

最も適した戦略は、要求を満たす最小の利用可能なブロックを選択することです。使用可能なリストがブロックサイズでソートされている場合、最適なブロックが下限になり、コンテナstd::multimapはこのタスクに完全に適しています。

通常、メモリアロケータでこのようなコンテナを使用することは悪い習慣と思われるかもしれませんが（無料ストアを再利用する方がよい）、ティーチは気にしないので、やりやすくします。

ここで、各ブロックはヘッダーのためのスペースを予約します。これはブロックサイズだけを格納しますが、追加のフィールドを追加できます。当初、利用可能なリストには1つの大きなブロックが含まれています。見つかったブロックが要求よりもある閾値より大きい場合、ブロックは2つに分割され、残りは利用可能なリストに戻されます。

// memory block header size in words. 
#define HEADER_SIZE static_cast<word_type>(1) 

// extract block size from block header. 
#define BLOCK_SIZE(location) \ 
    (heap[(location) - HEADER_SIZE]) 

// heap types/members. 
typedef unsigned int word_type; 
constexpr word_type heap_size = 1000000; 
word_type heap[heap_size]; 

// key: block size; data: block location. 
std::multimap<word_type, word_type> free_list; 

void heap_initialize() 
{ 
    word_type next = HEADER_SIZE; 
    BLOCK_SIZE(next) = heap_size; 
    release(next); 
} 

void release(word_type p) 
{ 
    if (p != 0) 
     free_list.insert(std::make_pair(BLOCK_SIZE(p), p)); 
} 

word_type acquire(word_type request) 
{ 
    if (request == 0) 
     return 0; 

    // threshold minimum is (header + 1*data word). 
    word_type threshold = 8; 
    request = (request + HEADER_SIZE + (threshold-1)) 
      /threshold * threshold; 

    // locate best-fit. 
    auto best_iter = free_list.lower_bound(request); 

    // no suitable block found. 
    if (best_iter == free_list.end()) 
     throw std::bad_alloc(); 

    // extract index; update free list. 
    word_type best = best_iter->second; 
    free_list.erase(best_iter); 

    // split block. 
    if (BLOCK_SIZE(best) > request + threshold) { 
     word_type next = best + request; 
     BLOCK_SIZE(next) = BLOCK_SIZE(best) - request; 
     BLOCK_SIZE(best) = request; 
     release(next); 
    } 
    return best; 
} 

このコードの出力に関するテストは、hereと表示されます。二重リンクリストとブロック結合を使用する代わりの実装はhereです。

これが役に立ちます。がんばろう。