Bloklar Olmadan Yığın: Tehlikeli Bölümlerin Uygulanması, Bölüm 2

Son makalemde, bu yazıda devam ettiğim tehlikelerin bölümlerini açıklamaya başladım.

Emeklilik Listesi

. RetireList Kamu üyelerinin işlevlerine sahip isInUse,, addNode VE deleteUnusedNodes. Ayrıca, iç sınıfa sahiptir RetireNodeBir atom üyesi ve özel üyelerin işlevi addToRetiredNodes:

template <typename T, Node MyNode = MyNode<T>>
class RetireList {

  struct RetiredNode {
    MyNode* node;
    RetiredNode* next;
    RetiredNode(MyNode* p) : node(p), next(nullptr) { }
    ~RetiredNode() {
      delete node;
    }
  };

  std::atomic<RetiredNode*> RetiredNodes;
  void addToRetiredNodes(RetiredNode* retiredNode) {
    retiredNode->next = RetiredNodes.load();
    while (!RetiredNodes.compare_exchange_strong(retiredNode->next, retiredNode));
  }

  public:

  bool isInUse(MyNode* node) {
    for (std::size_t i = 0; i < MaxHazardPointers; ++i) {
      if (HazardPointers<T>[i].pointer.load() == node) return true;
    }
    return false;
  }

  void addNode(MyNode* node) {
    addToRetiredNodes(new RetiredNode(node));
  }

  void deleteUnusedNodes() {
    RetiredNode* current = RetiredNodes.exchange(nullptr);
    while (current) {
      RetiredNode* const next = current->next;
      if (!isInUse(current->node)) delete current;
      else addToRetiredNodes(current);
      current = next;
    }
  }
};

Veri türü arayüzü ile başlayalım RetireList. Üye işlevi isInUse KONTROL İSTEYİN node Kullanımda. Değişken modelden geçer HazardPointersBu, düğüm verilerinin türünde parametrelendirilir. HazardPointers Bir c-dizisidir HazardPointer uzunluk 50. Bir HazardPointer Bir atomik kimlik ipliği ve bir düğüm üzerinde bir nükleer işaretçiden oluşur:

constexpr std::size_t MaxHazardPointers = 50;

template <typename T, Node MyNode = MyNode<T>>
struct HazardPointer {
  std::atomic<std::thread::id> id;
  std::atomic<MyNode*> pointer;
};

template <typename T>
HazardPointer<T> HazardPointers[MaxHazardPointers];

Gibi bir STL kabının kullanımı std::set GİBİ HazardPointers Çok daha pratik. std::set Zaten sipariş edildi ve ortalama olarak sürekli bir erişim süresi garanti ediyor, ancak büyük bir sorunu var: emin değil.

Üye işlevi addNode Bir düğüm alır, özel üyelerin işlevini arayın addToRetiredNodes ve düğümü bire ekleyin RetiredNode A. RetiredNode Bu bir RAII nesnesidir ve kapalı düğümün yok edileceğini garanti eder, bu da belleğini serbest bırakır. Tüm emekli düğümler basitçe bağlı bir liste oluşturur.

Üye işlevi deleteUnusedNodes Emekli düğümün basitçe bağlantılı listesi sırasında aşağıdaki modelden geçer:

void deleteUnusedNodes() {
  RetiredNode* current = RetiredNodes.exchange(nullptr);
  while (current) {
    RetiredNode* const next = current->next;
    if (!isInUse(current->node)) delete current;
    else addToRetiredNodes(current);
    current = next;
  }
}

Geçerli düğümü kontrol edin, bir sonraki düğümü ifade eder current->next Ve geçerli düğümü bir sonraki düğümle güncelleyin. Son olarak, artık kullanılmazsa veya Duamed düğümlerine eklenirse geçerli düğüm yok edilir. Özel üyelerin işlevi addToRetireNodes On yıllardır bağlı listeye onlarca yıl ekleyin. Görevini yerine getirmek için tarihli düğümleri yükleyin ve yeni düğümü yapar retiredNode Listenin yeni kafasına basitçe bağlı.

Önce retiredNode Listenin yeni başı basitçe, başka bir iş parçacığı, bağlantılı listenin başını girip değiştirebileceğinden, hala bağlantılı listenin başı olduğundan emin olmalıyım. Döngü sayesinde retiredNode Ancak o zaman yeni kafaya retiredNode->next = RetiredNodes.load() uygulanır. Aksi takdirde olur retiredNode->next AÇIK RetiredNodes.load() Güncellendi.

Bulmacanın sadece bir kısmı eksik: Tehlikeli işaretçinin sahibi:

template <typename T, Node MyNode = MyNode<T>>
class HazardPointerOwner {

  HazardPointer<T>* hazardPointer;

public:
  HazardPointerOwner(HazardPointerOwner const &) = delete;
  HazardPointerOwner operator=(HazardPointerOwner const &) = delete;

  HazardPointerOwner() : hazardPointer(nullptr) {
    for (std::size_t i = 0; i < MaxHazardPointers; ++i) {
      std::thread::id old_id;
      if (HazardPointers<T>[i].id.compare_exchange_strong(
          old_id, std::this_thread::get_id())) {
        hazardPointer = &HazardPointers<T>[i];
        break;
      }
    }
    if (!hazardPointer) {
      throw std::out_of_range(„No hazard pointers available!“);
    }
  }

  std::atomic<MyNode*>& getPointer() {
    return hazardPointer->pointer;
  }

  ~HazardPointerOwner() {
    hazardPointer->pointer.store(nullptr);
    hazardPointer->id.store(std::thread::id());
  }
};

HazardPointerOwner bir tane var HazardPointer. Bu üreticide herkesi geçiyor HazardPointer ayarlamak. Arama compare_exchange_strong Şu anda geçtiyse bir atom pasajını kontrol edin HazardPointer Ayarlanmamış ve şimdi gerçekleştirilen iş parçacığının kimliğine dayanıyor (std::this_thread::get_id()). Başarı durumunda HazardPointer Yeniye HazardPointerüyenin çalıştığı müşteriye iade edilir getPointer çağrılar. Tehlikenin tüm takipçileri HazardPointers Üretici bir std::out_of_range Exception dışında. Sonunda, muhrip HazardPointerOwner . hazardPointer Standart durumuna geri dönelim.

Sırada ne var?

C ++ 26'da bir tehlike işaretçisi alacağız. Bunun hakkında bir sonraki makalemde yazacağım.

(RME)