الوقت تعقيد تخصيص الذاكرة

Question

ما هو الوقت المناسب تعقيد تخصيص الذاكرة الديناميكية باستخدام جديدة ، malloc ، وما إلى ذلك ؟ أنا أعرف القليل جدا عن كيفية الذاكرة allocators تنفذ, ولكن أعتقد أن الجواب هو أن ذلك يعتمد على التنفيذ.لذا يرجى الإجابة على بعض من أكثر الحالات الشائعة/تطبيقات.

تحرير:أنني أتذكر سماع تلك الكومة توزيع غير محدود في أسوأ الأحوال, ولكن أنا مهتم حقا في متوسط/حالة نموذجية.

Answer 1

أحد الأشياء التي يجب عليك إدراكها عند التعامل مع تدوين O هو أنه غالبًا ما يكون من المهم جدًا فهم ما هو ن يكون.إذا ن هو شيء متعلق بشيء يمكنك التحكم فيه (على سبيل المثال:عدد العناصر في القائمة التي تريد فرزها) فمن المنطقي أن ننظر إليها بعناية.

في معظم تطبيقات الكومة، الخاص بك ن هو عدد أجزاء الذاكرة المتجاورة التي يتعامل معها المدير.هذا هو بالتأكيد لا شيء عادة تحت سيطرة العميل.الوحيد ن العميل الذي يتحكم حقًا في حجم جزء الذاكرة الذي يريده.في كثير من الأحيان، لا علاقة لذلك بمقدار الوقت الذي يستغرقه المُخصص.كبير ن يمكن تخصيصها بسرعة كما صغيرة ن, ، أو قد يستغرق الأمر وقتًا أطول، أو قد يصبح غير قابل للخدمة.كل هذا يمكن أن يتغير لنفس الشيء ن اعتمادًا على كيفية وصول التخصيصات والتخصيصات السابقة من العملاء الآخرين.حقًا، إلا إذا كنت تقوم بتنفيذ كومة، إذن الجواب الصحيح هو أنها غير حتمية.

ولهذا السبب يحاول مبرمجو الوقت الفعلي تجنب التخصيص الديناميكي (بعد بدء التشغيل).

Answer 2

يمكن أن يختلف التعقيد الزمني لمخصص الكومة باختلاف الأنظمة، اعتمادًا على ما قد يتم تحسينه من أجله.

في أنظمة سطح المكتب، من المحتمل أن يستخدم مُخصص الكومة مزيجًا من الاستراتيجيات المختلفة بما في ذلك التخزين المؤقت للتخصيصات الحديثة، والقوائم الجانبية لأحجام التخصيص الشائعة، وصناديق قطع الذاكرة ذات خصائص حجم معينة، وما إلى ذلك.لمحاولة إبقاء وقت التخصيص منخفضًا مع الحفاظ على إمكانية التحكم في التجزئة أيضًا.راجع الملاحظات الخاصة بتطبيق Doug Lea's malloc للحصول على نظرة عامة على التقنيات المختلفة المستخدمة: http://g.oswego.edu/dl/html/malloc.html

بالنسبة للأنظمة الأبسط، يمكن استخدام استراتيجية الملاءمة الأولى أو الملاءمة الأفضل، مع تخزين الكتل الحرة في قائمة مرتبطة (والتي من شأنها أن تعطي وقت O(N) حيث يكون N هو عدد الكتل الحرة).ولكن يمكن استخدام نظام تخزين أكثر تطوراً مثل شجرة AVL لتتمكن من تحديد موقع الكتل الحرة في زمن O(log N) (http://www.oocities.org/wkaras/heapmm/heapmm.html).

قد يستخدم نظام الوقت الفعلي مُخصص الكومة مثل TLSF (Two-Level Segregate Fit)، والذي له تكلفة تخصيص O(1): http://www.gii.upv.es/tlsf/

Answer 3

أعتقد أنه سيكون بشكل عام O(n) حيث n هو عدد كتل الذاكرة المتوفرة (نظرًا لأنه يتعين عليك فحص كتل الذاكرة المتوفرة للعثور على كتلة مناسبة).

بعد قولي هذا، رأيت تحسينات يمكن أن تجعل الأمر أسرع، وعلى وجه التحديد الحفاظ على قوائم متعددة من الكتل المتاحة اعتمادًا على نطاقات أحجامها (لذا فإن الكتل التي تقل عن 1 كيلو موجودة في قائمة واحدة، والكتل من 1 كيلو إلى 10 كيلو موجودة في قائمة أخرى، وهكذا ).

لا يزال هذا O(n) مع n أصغر فقط.

سأكون مهتمًا بمعرفة المصدر الخاص بك أن هناك تخصيصًا غير محدود للكومة (إذا كنت تقصد بذلك أن الأمر قد يستغرق إلى الأبد).

Answer 4

ما عليك سوى التحقق من كيفية عمل المخصصات النموذجية.

يعمل مُخصص عثرة المؤشر في يا(1), "، وهي صغيرة"1' إلى ذلك.

بالنسبة لمخصص التخزين المنفصل، فإن تخصيص k بايت يعني "إرجاع الكتلة الأولى من القائمة (ن)" حيث القائمة(ن) هي قائمة كتل n بايت حيث ن >= ك.هو - هي قد تجد تلك القائمة(ن) فارغ، بحيث تكون الكتلة من القائمة التالية (List(2 ن)) يجب أن يتم تقسيمها مع كلا الكتلتين الناتجتين ن البايتات التي يتم وضعها في القائمة(ن)، وهذا الأثر قد تموج من خلال جميع الأحجام المتاحة، مما يزيد من تعقيد يا(ن) حيث ns هو عدد الأحجام المختلفة المتاحة، و ns = السجل (N) أين ن هو حجم أكبر حجم كتلة متاح، لذلك حتى ذلك سيكون صغيرًا.في معظم الحالات، خاصة بعد تخصيص عدد من الكتل وإلغاء تخصيصها، يكون التعقيد أمرًا معقدًا يا(1).

Answer 5

فقط ملاحظتين:

• TLSF O(1) بمعنى أنه لم واحد حلقة ؛ وتدير ما يصل إلى 2Gb.على الرغم من أنه من الصعب حقا أن نصدق فقط التحقق من التعليمات البرمجية.

• ليس صحيحا أن "الأنسب" سياسة (العثور على ضيق كتلة) هو الأنسب تحقيق الصغيرة تجزئة.فهي بعيدة عن تافهة لإثبات هذا الادعاء ، في الواقع لم يثبت رسميا ولكن هناك الكثير من الأدلة التي تذهب في هذا الاتجاه.(نيس موضوع البحث).