मॉलोक() और फ्री() को लागू करने की इस श्रृंखला में पिछली पोस्ट में, हमने दिखाया कि मेमोरी ब्लॉक का पुन: उपयोग करना और नए ब्लॉक को मुक्त करके ढेर को कम करना कैसे संभव है। हालाँकि, वर्तमान फ़ंक्शन एक सूक्ष्म समस्या पेश करता है: यह नए ब्लॉकों के पुन: उपयोग को प्राथमिकता देता है, जिससे समय के साथ मेमोरी की खपत बढ़ सकती है। ऐसा क्यूँ होता है? आइए इसे तोड़ें।

हाल के ब्लॉकों का पुन: उपयोग करके ढेर में कमी

निम्नलिखित परिदृश्य पर विचार करें। सबसे पहले, हम चार मेमोरी ब्लॉक आवंटित करते हैं:

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

मेमोरी संरचना को इस तरह देखा जा सकता है:

अब, हम पहला और तीसरा ब्लॉक जारी करते हैं...

abfree(ptr1);
abfree(ptr3);

...जिसके परिणामस्वरूप निम्नलिखित संरचना उत्पन्न होती है:

फिर हम उसी आकार का एक और ब्लॉक आवंटित करते हैं:

void *ptr5 = abmalloc(8);

जैसे ही फ़ंक्शन abmalloc() नवीनतम मुक्त ब्लॉक की खोज शुरू करता है, यह शीर्ष पर ब्लॉक का पुन: उपयोग करता है। यदि अब हम अंतिम ब्लॉक मुक्त करते हैं:

यदि हम अब अंतिम ब्लॉक जारी करते हैं...

abfree(ptr4);

...हम ढेर के आकार को केवल एक 8-बाइट ब्लॉक तक कम कर सकते हैं, क्योंकि पिछला ब्लॉक अब मुफ़्त नहीं है:

पुराने ब्लॉकों का पुन: उपयोग

अब, उसी परिदृश्य की कल्पना करें, लेकिन एक संशोधन के साथ: हमारा फ़ंक्शन सबसे पुराने से मुफ्त ब्लॉक की खोज शुरू करता है। प्रारंभिक संरचना वही होगी...

...और फिर से हम पहले और तीसरे मेमोरी ब्लॉक को मुक्त करते हैं:

इस बार, पहले ब्लॉक का पुन: उपयोग किया जाएगा:

अब, जब हम अंतिम ब्लॉक को मुक्त करते हैं, तो हमारे पास शीर्ष पर दो मुक्त ब्लॉक होंगे, जिससे हम दो 8-बाइट ब्लॉकों द्वारा ढेर को कम कर सकेंगे:

यह उदाहरण दिखाता है कि कैसे, नए ब्लॉकों को प्राथमिकता देकर, हम पुराने अप्रयुक्त ब्लॉकों को जमा कर लेते हैं, स्मृति को बर्बाद करते हैं और अनावश्यक ढेर वृद्धि को जन्म देते हैं। समाधान पुराने ब्लॉकों के पुन: उपयोग को प्राथमिकता देते हुए खोज रणनीति को संशोधित करना है।

पुराने ब्लॉकों के लिए प्राथमिकता लागू करना

इस समस्या को हल करने के लिए, हम हेडर में अगले ब्लॉक में एक पॉइंटर जोड़कर शुरुआत करेंगे। हम पहले ब्लॉक के लिए एक वैश्विक सूचक भी बनाएंगे, ताकि हम इससे खोज शुरू कर सकें:

typedef struct Header {
  struct Header *previous, *next;
  size_t size;
  bool available;
} Header;
Header *first = NULL;
Header *last = NULL;

हम दो अलग-अलग स्थितियों में हेडर के साथ मेमोरी ब्लॉक बनाएंगे, तो चलिए एक छोटा सा रिफैक्टरिंग करते हैं: हम इस तर्क को एक सहायक फ़ंक्शन में निकालेंगे जो हेडर को आवंटित और आरंभ करता है (NULL के साथ अगला फ़ील्ड सेट करने सहित):

Header *header_new(Header *previous, size_t size, bool available) {
  Header *header = sbrk(sizeof(Header)   size);
  header->previous = previous;
  header->next = NULL;
  header->size = size;
  header->available = false;
  return header;
}

इस नए फ़ंक्शन के साथ, हम abmalloc() के भीतर तर्क को सरल बना सकते हैं:

void *abmalloc(size_t size) { 
  if (size == 0) { 
    return NULL; 
  } 
  Header *header = last; 
  while (header != NULL) { 
    if (header->available && (header->size >= size)) { 
      header->available = false; 
      return header   1; 
    } 
    header = header->previous; 
  } 
  last = header_new(last, size, false); 
  return last   1; 
}

अब हमारे पास पहले और आखिरी ब्लॉक तक पहुंच है, और एक ब्लॉक दिए जाने पर, हम पिछले और अगले ब्लॉक का पता लगा सकते हैं। हम यह भी जानते हैं कि जब पहले ब्लॉक का सूचक शून्य होता है, तो अभी तक कोई ब्लॉक आवंटित नहीं किया गया है। तो इस मामले में, हम तुरंत ब्लॉक आवंटित करेंगे, और पहले और आखिरी दोनों को इनिशियलाइज़ करेंगे:

void *abmalloc(size_t size) { 
  if (size == 0) { 
    return NULL; 
  } 
  if (first == NULL) { 
    first = last = header_new(NULL, size, false); 
    return first   1; 
  }

यदि पहले यह अब NULL नहीं है, तो पहले से ही आवंटित ब्लॉक हैं, इसलिए हम पुन: प्रयोज्य ब्लॉक की खोज शुरू करेंगे। हम एक पुनरावर्तक के रूप में वेरिएबल हेडर का उपयोग करना जारी रखेंगे, लेकिन सबसे हालिया ब्लॉक से शुरू करने के बजाय, खोज सबसे पुराने ब्लॉक से शुरू होगी:

  Header *header = first;

प्रत्येक पुनरावृत्ति पर, हम पिछले ब्लॉक पर पीछे जाने के बजाय अनुक्रम में अगले ब्लॉक पर आगे बढ़ेंगे:

  while (header != NULL) { 
    if (header->available && (header->size >= size)) { 
      header->available = false; 
      return header   1; 
    } 
    header = header->next; 
  }

तर्क वही रहता है: यदि हमें पर्याप्त आकार का उपलब्ध ब्लॉक मिल जाता है, तो उसे वापस कर दिया जाता है। अन्यथा, यदि सूची को पार करने के बाद कोई पुन: प्रयोज्य ब्लॉक नहीं मिलता है, तो एक नया ब्लॉक आवंटित किया जाता है:

  last = header_new(last, size, false);

अब, हमें उस ब्लॉक को समायोजित करने की आवश्यकता है जो अंतिम था (आवंटन के बाद, दूसरे से अंतिम)। इसने NULL की ओर इशारा किया, लेकिन अब इसे नए ब्लॉक की ओर इशारा करना चाहिए। ऐसा करने के लिए, हम पिछले ब्लॉक के अगले फ़ील्ड को नए अंतिम ब्लॉक पर सेट करते हैं:

  last->previous->next = last; 
  return last   1; 
}

abfree में समायोजन()

फ़ंक्शन abfree() मूल रूप से समान संरचना को बनाए रखता है, लेकिन अब हमें कुछ किनारे के मामलों को संभालना होगा। जब हम ढेर के शीर्ष पर ब्लॉक मुक्त करते हैं, तो एक नया ब्लॉक अंतिम बन जाता है, जैसा कि हम पहले से ही इस स्निपेट में करते हैं:

    last = header->previous;
    brk(header)

यहां, पॉइंटर हेडर स्टैक पर उपलब्ध अंतिम गैर-शून्य ब्लॉक को संदर्भित करता है। हमारे पास दो संभावित परिदृश्य हैं:

1. वर्तमान ब्लॉक में एक पिछला ब्लॉक है, जो नया अंतिम ब्लॉक बन जाएगा। इस स्थिति में, हमें इस ब्लॉक के अगले पॉइंटर को NULL पर सेट करना चाहिए।
2. वर्तमान ब्लॉक में पिछला ब्लॉक नहीं है (यानी, यह पहला और सबसे पुराना ब्लॉक है)। जब इसे मुक्त किया जाता है, तो स्टैक खाली हो जाता है। इस मामले में, किसी गैर-मौजूद ब्लॉक के फ़ील्ड को अपडेट करने का प्रयास करने के बजाय, हम इसे पहले NULL पर सेट करते हैं, जो दर्शाता है कि कोई और आवंटित ब्लॉक नहीं हैं।

यहां बताया गया है कि हम इसे कैसे लागू करते हैं:

  last = header->previous; 
  if (last != NULL) { 
    last->next = NULL; 
  } else { 
    first = NULL; 
  } 
  brk(header);

निष्कर्ष

हमारे फ़ंक्शन abmalloc() और abfree() अब इस तरह दिखते हैं:

typedef struct Header {
  struct Header *previous, *next;
  size_t size;
  bool available;
} Header;

Header *first = NULL;
Header *last = NULL;

Header *header_new(Header *previous, size_t size, bool available) {
  Header *header = sbrk(sizeof(Header)   size);
  header->previous = previous;
  header->next = NULL;
  header->size = size;
  header->available = false;
  return header;
}

void *abmalloc(size_t size) {
  if (size == 0) {
    return NULL;
  }
  if (first == NULL) {
    first = last = header_new(NULL, size, false);
    return first   1;
  }
  Header *header = first;
  while (header != NULL) {
    if (header->available && (header->size >= size)) {
      header->available = false;
      return header   1;
    }
    header = header->next;
  }
  last = header_new(last, size, false);
  last->previous->next = last;
  return last   1;
}

void abfree(void *ptr) {
  if (ptr == NULL) {
   return;
  }
  Header *header = (Header*) ptr - 1;
  if (header == last) {
    while ((header->previous != NULL) && header->previous->available) {
      header = header->previous;
    }
    last = header->previous;
    if (last != NULL) {
      last->next = NULL;
    } else {
      first = NULL;
    }
    brk(header);
  } else {
   header->available = true;
  }
 }

यह परिवर्तन हमें काफी अधिक मेमोरी सहेजने की अनुमति देता है। हालाँकि, हल करने के लिए अभी भी समस्याएँ हैं। उदाहरण के लिए, निम्नलिखित परिदृश्य पर विचार करें: हम 8 बाइट्स के मेमोरी ब्लॉक के आवंटन का अनुरोध करते हैं, और abmalloc(), मान लीजिए, 1024 बाइट्स के ब्लॉक का पुन: उपयोग करते हैं। स्पष्टतः बर्बादी है।

हम अगली पोस्ट में देखेंगे कि इसे कैसे हल किया जाए।