كيف يمكنني استخدام التعسفي سلسلة بمثابة قفل في C++?

Question

دعونا نقول لدي مؤشرات C++ البرنامج الذي يتعامل مع الطلبات في شكل استدعاء دالة على handleRequest(string key).كل استدعاء handleRequest تحدث في موضوع مستقل, و هناك بشكل تعسفي لعدد كبير من القيم الممكنة ل key.

أريد السلوك التالي:

• مكالمات متزامنة handleRequest(key) هي تسلسل عندما يكون لديهم نفس القيمة key.
• العالمية التسلسل هو الحد الأدنى.

الجسم من handleRequest قد تبدو مثل هذا:

void handleRequest(string key) {
    KeyLock lock(key);
    // Handle the request.
}

السؤال: كيف يمكنني تنفيذ KeyLock للحصول على المطلوب السلوك ؟

ساذجة التنفيذ قد تبدأ مثل هذا:

KeyLock::KeyLock(string key) {
    global_lock->Lock();
    internal_lock_ = global_key_map[key];
    if (internal_lock_  == NULL) {
        internal_lock_  = new Lock();
        global_key_map[key] = internal_lock_;
    }
    global_lock->Unlock();
    internal_lock_->Lock();
}

KeyLock::~KeyLock() {
    internal_lock_->Unlock();
    // Remove internal_lock_ from global_key_map iff no other threads are waiting for it.
}

لكن ذلك يتطلب العالمية قفل في بداية ونهاية كل طلب ، وإنشاء منفصل Lock كائن لكل طلب.إذا الخلاف عالية بين المكالمات handleRequest, هذا قد لا يكون مشكلة ، ولكن يمكن أن تفرض الكثير من النفقات العامة إذا كان الخلاف منخفضة.

Answer 1

يمكنك أن تفعل شيئًا مشابهًا لما لديك في سؤالك، ولكن بدلاً من وجود خريطة مفاتيح عالمية واحدة تحتوي على عدة خريطة (ربما في مصفوفة أو متجه) - يتم تحديد أي منها يتم استخدامه من خلال بعض وظائف التجزئة البسيطة على السلسلة.

بهذه الطريقة، بدلًا من قفل عالمي واحد، يمكنك توزيعه على عدة أقفال مستقلة.

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

Answer 2

وسوف تعتمد على منصة ، ولكن اثنين من التقنيات التي حاولت أن تكون:

• استخدام اسمه مزامنة/التزامن الكائنات ، حيث object name = مفتاح
• استخدام نظام الملفات على أساس تأمين ، حيث في محاولة لخلق غير قابل ملف مؤقت مع اسم المفتاح.إذا كان موجودا بالفعل (=بالفعل مؤمن) هذه سوف تفشل وسوف أن الاستطلاع إلى إعادة المحاولة

كل تقنيات تعتمد على تفاصيل نظام التشغيل الخاص بك.التجربة ونرى التي تعمل..

Answer 3

ربما ا std::map<std::string, MutexType> سيكون ما تريد، أين MutexType هو نوع كائن المزامنة الذي تريده.من المحتمل أن يتعين عليك التفاف الوصول إلى الخريطة في كائن المزامنة (mutex) آخر للتأكد من عدم إدراج أي مؤشر ترابط آخر في نفس الوقت (وتذكر إجراء التحقق مرة أخرى بعد قفل كائن المزامنة (mutex) للتأكد من عدم إضافة مؤشر ترابط آخر إلى المفتاح أثناء انتظار كائن المزامنة!).

ويمكن تطبيق نفس المبدأ على أي طريقة مزامنة أخرى، مثل القسم الحرج.

Answer 4

رفع التفاصيل وقفل نطاقات المفاتيح بأكملها

هذا هو الاختلاف في إجابة Mike B، حيث بدلاً من وجود العديد من خرائط قفل السوائل لديك مجموعة ثابتة واحدة من الأقفال التي تنطبق على نطاقات المفاتيح بدلاً من المفاتيح الفردية.

مثال مبسط:قم بإنشاء مجموعة من 256 قفلًا عند بدء التشغيل، ثم استخدم البايت الأول من المفتاح لتحديد فهرس القفل الذي سيتم الحصول عليه (أيسيتم حماية جميع المفاتيح التي تبدأ بالحرف "k". locks[107]).

للحفاظ على الإنتاجية المثلى، يجب عليك تحليل توزيع المفاتيح ومعدل التنافس.فوائد هذا الأسلوب هي التخصيصات الديناميكية الصفرية والتنظيف البسيط؛يمكنك أيضًا تجنب القفل على خطوتين.الجانب السلبي هو ذروة التنافس المحتملة إذا أصبح توزيع المفاتيح منحرفًا بمرور الوقت.

Answer 5

بعد التفكير في الأمر، قد يكون هناك نهج آخر كالتالي:

• في handleRequest, ، إنشاء Callback الذي يقوم بالعمل الفعلي.
• إنشاء multimap<string, Callback*> global_key_map, ، محمي بواسطة كائن المزامنة (mutex).
• إذا رأى الخيط ذلك key تتم معالجتها بالفعل، ويضيف لها Callback* إلى global_key_map ويعود.
• بخلاف ذلك، فإنه يستدعي رد الاتصال الخاص به على الفور، ثم يستدعي عمليات الاسترجاعات التي ظهرت في هذه الأثناء لنفس المفتاح.

تم تنفيذ شيء مثل هذا:

LockAndCall(string key, Callback* callback) {
    global_lock.Lock();
    if (global_key_map.contains(key)) {
        iterator iter = global_key_map.insert(key, callback);
        while (true) {
            global_lock.Unlock();
            iter->second->Call();
            global_lock.Lock();
            global_key_map.erase(iter);
            iter = global_key_map.find(key);
            if (iter == global_key_map.end()) {
                global_lock.Unlock();
                return;
            }
        }
    } else {
        global_key_map.insert(key, callback);
        global_lock.Unlock();
    }
}

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

ومع ذلك، يمكن دمجها مع الإجابات التي قدمها مايك بي وكونستانتين.

Answer 6

      /**
      * StringLock class for string based locking mechanism
      * e.g. usage
      *     StringLock strLock;
      *     strLock.Lock("row1");
      *     strLock.UnLock("row1");
      */
      class StringLock    {
      public:
          /**
           * Constructor
           * Initializes the mutexes
           */
          StringLock()    {
              pthread_mutex_init(&mtxGlobal, NULL);
          }
          /**
           * Lock Function
           * The thread will return immediately if the string is not locked
           * The thread will wait if the string is locked until it gets a turn
           * @param string the string to lock
           */
          void Lock(string lockString)    {
              pthread_mutex_lock(&mtxGlobal);
              TListIds *listId = NULL;
              TWaiter *wtr = new TWaiter;
              wtr->evPtr = NULL;
              wtr->threadId = pthread_self();
              if (lockMap.find(lockString) == lockMap.end())    {
                  listId = new TListIds();
                  listId->insert(listId->end(), wtr);
                  lockMap[lockString] = listId;
                  pthread_mutex_unlock(&mtxGlobal);
              } else    {
                  wtr->evPtr = new Event(false);
                  listId = lockMap[lockString];
                  listId->insert(listId->end(), wtr);
                  pthread_mutex_unlock(&mtxGlobal);
                  wtr->evPtr->Wait();
              }
          }
          /**
          * UnLock Function
          * @param string the string to unlock
          */
          void UnLock(string lockString)    {
              pthread_mutex_lock(&mtxGlobal);
              TListIds *listID = NULL;
              if (lockMap.find(lockString) != lockMap.end())    {
                  lockMap[lockString]->pop_front();
                  listID = lockMap[lockString];
                  if (!(listID->empty()))    {
                      TWaiter *wtr = listID->front();
                      Event *thdEvent = wtr->evPtr;
                      thdEvent->Signal();
                  } else    {
                      lockMap.erase(lockString);
                      delete listID;
                  }
              }
              pthread_mutex_unlock(&mtxGlobal);
          }
      protected:
          struct TWaiter    {
              Event *evPtr;
              long threadId;
          };
          StringLock(StringLock &);
          void operator=(StringLock&);
          typedef list TListIds;
          typedef map TMapLockHolders;
          typedef map TMapLockWaiters;
      private:
          pthread_mutex_t mtxGlobal;
          TMapLockWaiters lockMap;
      };