كيفية اكتشاف الدورات عند استخدام Shared_Ptr

Question

Shared_Ptr هو مرجع مرجع مؤشر ذكي في مكتبة دفعة.

المشكلة مع العد المرجعي هي أنه لا يمكن التخلص من الدورات. أتساءل كيف سيستمر المرء في حل هذا في C ++.

يرجى عدم وجود اقتراحات مثل: "لا تجعل دورات"، أو "استخدم ضعيفة".

يحرر

أنا لا أحب الاقتراحات التي تقول فقط استخدام ضعيف_PTR لأنه من الواضح أنه إذا كنت تعرف أنك ستخلق دورة، فلن تواجه مشكلة. لا يمكنك أيضا معرفة أنه سيكون لديك دورة في تجميع الوقت إذا قمت بإنشاء Shared_Ptrs أثناء وقت التشغيل.

لذا، من فضلك، احذف الإجابات ذاتية الاستخدام التي تستخدمها lob_ptr بهم لأنني طلبت على وجه التحديد عدم وجود هذا النوع من الإجابات ...

Answer 1

لم أجد طريقة أفضل بكثير من رسم الرسوم البيانية الكبيرة UML وتبحث عن الدورات.

لتصحيح، استخدم عداد مثيل يذهب إلى التسجيل، مثل هذا:

template <DWORD id>
class CDbgInstCount
{
public:
#ifdef _DEBUG
   CDbgInstCount()   { reghelper.Add(id, 1); }
   CDbgInstCount(CDbgInstCount const &) {  reghelper.Add(id, 1); }
   ~CDbgInstCount()  { reghelper.Add(id, -1); }
#else
#endif
};

أنا فقط نيد لإضافة ذلك إلى الفصول المعنية، وإلقاء نظرة على السجل.

(المعرف، إذا تم إظهار مثل "XYZ!" سيتم تحويلها إلى سلسلة. لسوء الحظ، لا يمكنك تحديد سلسلة ثابتة كمعلمة قالب)

Answer 2

shared_ptr يمثل ملكية علاقة. في حين weak_ptr يمثل وعي. وبعد وجود العديد من الأشياء التي تملك بعضها البعض تعني أن لديك مشاكل مع الهندسة المعمارية، والتي تم حلها عن طريق تغيير واحد أو أكثر ملكفي ذلك مدرك ل(هذا هو، weak_ptr'س).

أنا لا أفهم لماذا اقتراح weak_ptr يعتبر عديمة الفائدة.

Answer 3

أفهم انزعاجك في التخلص منه لاستخدام ضعيف_PTR لكسر المراجع الدورية ونفسي أشعر تقريبا بالغضب عندما أخبرت أن المراجع الدورية هي أسلوب برمجة سيئ.

اسأل الخاص بك على وجه التحديد كيف يمكنك بقعة مراجع دورية. الحقيقة هي أنه في مشروع معقد، بعض دورات المرجعية غير مباشرة وصعبة.

الجواب هو أنه لا يجب عليك إجراء تصريحات زائفة تتركك عرضة للإصابة بالمراجع الدورية. أنا جاد وانتقد ممارسة شعبية للغاية - عمياء باستخدام Shared_ptr لكل شيء.

يجب أن تكون واضحا في التصميم الخاص بك من المؤشرات أصحابهم والمراقبون.

بالنسبة للمالكين، استخدم Shared_PTR

بالنسبة للمراقبين، استخدم ضعيفا - كل منهم، ليس فقط أولئك الذين تعتقد أنهم قد يكونوا جزءا من دورة.

إذا اتبعت هذه الممارسة، فلن تتسبب المراجع الدورية في أي مشاكل ولا تحتاج إلى القلق بشأنها. بالطبع سيكون لديك الكثير من التعليمات البرمجية للكتابة لتحويل كل هذه الضعف إلى Shared_PTRS عندما تريد استخدامها - دفعة حقا لا تصل إلى المهمة.

Answer 4

من السهل إلى حد ما اكتشاف الدورات:

• حدد عد إلى بعض العدد الفارق، ويقول 1000 (الحجم الدقيق يعتمد على طلبك)
• ابدأ ب Pionter كنت مهتما واتبع المؤشرات منه
• لكل مؤشر تتبع، تقليل العد
• إذا كان العد يسقط إلى الصفر قبل أن تصل إلى نهاية سلسلة المؤشر، فلديك دورة

هذا ليس كذلك مفيدا للغاية. وليس من الممكن عادة حل مشكلة CYCVLE للمؤشرات المرتبطة بالرفق - ولهذا السبب اخترعت مخططات Clection Clection البديلة مثل Generation Scavenging.

Answer 5

مزيج من boost::weak_ptr و boost::shared_ptr يمكن؟ هذه المادة قد تكون ذات أهمية.

Answer 6

انظر هذا المنشور على الكشف عن الدورات في الرسم البياني.

Answer 7

يمكن العثور على الحل العام لإيجاد دورة هنا:

أفضل خوارزمية لاختبار ما إذا كانت قائمة مرتبطة بها دورة

هذا يفترض أنك تعرف هيكل الكائنات في القائمة، ويمكن أن تتبع جميع المؤشرات الواردة في كل كائن.

Answer 8

ربما كنت في حاجة إلى تقنية جامع القمامة مثل علامة و اكتساح. وبعد فكرة هذه الخوارزمية هي:

1. احتفظ بقائمة مع الإشارات إلى جميع كتل الذاكرة المخصصة.
2. في مرحلة ما، تبدأ جامع القمامة:
   1. يقوم أولا بتمييز جميع الكتل التي لا يزال بإمكانها الوصول دون استخدام القائمة المرجعية.
   2. يمر عبر القائمة محو كل عنصر لا يمكن وضع علامة عليه، مما يعني أنه لا يمكن الوصول إليه بعد الآن حتى لا يكون مفيدا.

منذ أن تستخدم shared_ptr يجب اعتبار أي مؤشرات حالية تفشل في الوصول إليها كأعضاء في الدورة.

تطبيق

أدناه أصف مثالا ساذجا للغاية حول كيفية تنفيذ sweep() جزء من الخوارزمية، لكنه سوف reset() جميع المؤشرات المتبقية في المجمع.

مخازن الكود هذه shared_ptr<Cycle_t> مؤشرات. الفصل Collector هو المسؤول عن تتبع جميع المؤشرات وحذفها عندما sweep() يتم تنفيذ.

#include <vector>
#include <memory>

class Cycle_t;
typedef std::shared_ptr<Cycle_t> Ref_t;

// struct Cycle;
struct Cycle_t {
  Ref_t cycle;

  Cycle_t() {}
  Cycle_t(Ref_t cycle) : cycle(cycle) {}
};

struct collector {
  // Note this vector will grow endlessy.
  // You should find a way to reuse old links
  std::vector<std::weak_ptr<Cycle_t>> memory;

  // Allocate a shared pointer keeping
  // a weak ref on the memory vector:
  inline Ref_t add(Ref_t ref) {
    memory.emplace_back(ref);
    return ref;
  }
  inline Ref_t add(Cycle_t value) {
    Ref_t ref = std::make_shared<Cycle_t>(value);
    return add(ref);
  }
  inline Ref_t add() {
    Ref_t ref = std::make_shared<Cycle_t>();
    return add(ref);
  }

  void sweep() {
    // Run a sweep algorithm:
    for (auto& ref : memory) {
      // If the original shared_ptr still exists:
      if (auto ptr = ref.lock()) {
        // Reset each pointer contained within it:
        ptr->cycle.reset();

        // Doing this will trigger a deallocation cascade, since
        // the pointer it used to reference will now lose its
        // last reference and be deleted by the reference counting
        // system.
        //
        // The `ptr` pointer will not be deletd on the cascade
        // because we still have at least the current reference
        // to it.
      }
      // When we leave the loop `ptr` loses its last reference
      // and should be deleted.
    }
  }
};

يمكنك بعد ذلك استخدامه مثل هذا:

Collector collector;

int main() {
  // Build your shared pointers:
  {
    // Allocate them using the collector:
    Ref_t c1 = collector.add();
    Ref_t c2 = collector.add(c1);

    // Then create the cycle:
    c1.get()->cycle = c2;

    // A normal block with no cycles:
    Ref_t c3 = collector.add();
  }

  // In another scope:
  {
    // Note: if you run sweep an you still have an existing
    // reference to one of the pointers in the collector
    // you will lose it since it will be reset().
    collector.sweep();
  }
}

لقد اختبرتها مع Valgrind ولا توجد تسريب ذاكرة أو كتل "لا تزال قابلة للوصول"، لذلك من المحتمل أن تعمل كما هو متوقع.

بعض الملاحظات حول هذا التنفيذ:

1. سوف ينمو ناقل الذاكرة بلا نهاية، يجب عليك استخدام بعض تقنية تخصيص الذاكرة للتأكد من أنه لا يشغل جميع ذاكرة العمل الخاصة بك.
2. قد يجادل المرء أنه لا توجد حاجة للاستخدام shared_ptr (يعمل هذا مثل عد مرجعي GC) لتنفيذ مثل هذا جامع القمامة منذ العلامة وخوارزمية الاجتياح سيعتني بالفعل بالوظيفة.
3. لم أنفذ وظيفة العلامة () لأنها ستعقد المثال، لكن من الممكن وسأوضح ذلك أدناه.

أخيرا، إذا كنت مهتما ب (2)، فإن هذا النوع من التنفيذ ليس مجهولة. يستخدم CpeThon (التنفيذ الرئيسي لبيتثون) مزيجا من العد المرجعي والاحتفال والاحتياج، ولكن في الغالب ل أسباب تاريخية.

تنفيذ mark() وظيفة:

لتنفيذ mark() وظيفة ستحتاج إلى إجراء بعض التعديلات:

سيكون من الضروري إضافة bool marked; يعزو إلى Cycle_t, واستخدامه للتحقق مما إذا كان المؤشر ملحوظ أم لا.

سوف تحتاج إلى كتابة Collector::mark() وظيفة من شأنها أن تبدو مثل هذا:

void mark(Ref_t root) {
  root->marked = true;

  // For each other Ref_t stored on root:
  for (Ref_t& item : root) {
    mark(item);
  }
}

ثم يجب عليك تعديل sweep() وظيفة لإزالة العلامة إذا تم وضع علامة المؤشر أو غير ذلك reset() المؤشر:

void sweep() {
  // Run a sweep algorithm:
  for (auto& ref : memory) {
    // If it still exists:
    if (auto ptr = ref.lock()) {
      // And is marked:
      if (ptr->marked) {
        ptr->marked = false;
      } else {
        ptr->cycle.reset();
      }
    }
  }
}

لقد كان شرحا مطولا، لكنني آمل أن يساعد شخصا ما.

Answer 9

الإجابة عن السؤال القديم، قد تجرب المؤشر التسلسلي الذي قد يساعد في حساب عدد المرات التي يشار إليها المورد.

#include <cstdlib>
#include <iostream>

#include <boost/intrusive_ptr.hpp>

class some_resource
{
    size_t m_counter;

public:
    some_resource(void) :
        m_counter(0)
    {
        std::cout << "Resource created" << std::endl;
    }

    ~some_resource(void)
    {
        std::cout << "Resource destroyed" << std::endl;
    }

    size_t refcnt(void)
    {
        return m_counter;
    }

    void ref(void)
    {
        m_counter++;
    }

    void unref(void)
    {
        m_counter--;
    }
};

void
intrusive_ptr_add_ref(some_resource* r)
{
    r->ref();
    std::cout << "Resource referenced: " << r->refcnt()
              << std::endl;
}

void
intrusive_ptr_release(some_resource* r)
{
    r->unref();
    std::cout << "Resource unreferenced: " << r->refcnt()
              << std::endl;
    if (r->refcnt() == 0)
        delete r;
}

int main(void)
{
    boost::intrusive_ptr<some_resource> r(new some_resource);
    boost::intrusive_ptr<some_resource> r2(r);

    std::cout << "Program exiting" << std::endl;

    return EXIT_SUCCESS;
}

ها هي النتيجة التي تم إرجاعها.

Resource created 
Resource referenced: 1 
Resource referenced: 2 
Program exiting 
Resource unreferenced: 1
Resource unreferenced: 0 
Resource destroyed
*** Program Exit ***

Answer 10

أعلم أنك قلت "لا ضعيف_PTR" ولكن لماذا لا؟ إن وجود رأسك بضعف إلى الذيل، والذيل مع ضعيف_PTR إلى الرأس سيمنع الدورة.