मल्टीथ्रेडेड सिंगल-रीडर एकल-लेखक फीफो कतार

Question

मुझे एक थ्रेड (ए) से दूसरे (बी) में संदेशों को पारित करने के लिए एक कतार की आवश्यकता है, हालांकि मैं वास्तव में जो चाहता हूं उसे ढूंढने में सक्षम नहीं हूं, क्योंकि वे आम तौर पर अनुमति देते हैं असफल होने के लिए एक आइटम जोड़ना, एक मामला जो मेरी स्थिति में बहुत घातक है क्योंकि संदेश को संसाधित करने की आवश्यकता है, और धागा वास्तव में बंद नहीं हो सकता है और अतिरिक्त कमरे की प्रतीक्षा कर सकता है।

• केवल थ्रेड आइटम जोड़ता है, और केवल धागा उन्हें
• थ्रेड एक ब्लॉक नहीं करना चाहिए पढ़ता है, लेकिन धागा प्रदर्शन महत्वपूर्ण नहीं है, तो यह
• जोड़ना आइटम हमेशा सफल चाहिए सकता है, इसलिए कतार नहीं कर सकते एक ऊपरी आकार सीमा
• अगर कतार खाली है (सिस्टम पर स्मृति से बाहर चलाने का कम) है,

Answer 1

कार्रवाई करने के लिए यहाँ कैसे एक lock- लिखने के लिए है एक आइटम नहीं होने तक, धागा इंतजार करना चाहिए सी ++ में मुफ्त कतार:

http://www.ddj.com/hpc-high-performance-computing/210604448

लेकिन जब आप कहते हैं कि "धागा एक ब्लॉक नहीं चाहिए", तो आप यह सुनिश्चित करें कि आवश्यकता नहीं है कर रहे हैं? विंडोज एक वास्तविक समय ऑपरेटिंग सिस्टम नहीं है (और न ही सामान्य उपयोग में लिनक्स है)। यदि आप थ्रेड ए को सभी उपलब्ध सिस्टम मेमोरी का उपयोग करने में सक्षम होना चाहते हैं, तो इसे स्मृति आवंटित करने की आवश्यकता है (या किसी और के दौरान प्रतीक्षा करें)। यदि ओएस सूची में हेरफेर करने के लिए दोनों पाठक और लेखक ने इन-प्रोसेस लॉक (यानी एक गैर-साझा म्यूटेक्स) लिया है, तो ओएस स्वयं उन समय की तुलना में बेहतर गारंटी प्रदान नहीं कर सकता है। और संदेश जोड़ने का सबसे बुरा मामला स्मृति प्राप्त करने के लिए ओएस पर जाना होगा।

संक्षेप में, उन पंक्तियों का एक कारण है जिन्हें आप पसंद नहीं करते हैं - यह इसलिए है कि उन्हें अनुमानित कम-विलंबता धागे में स्मृति आवंटित करने की आवश्यकता नहीं है।

तो लॉक-फ्री कोड आम तौर पर कम ब्लॉक-वाई होगा, लेकिन स्मृति आवंटन के कारण इसकी गारंटी नहीं है, और एक म्यूटेक्स के साथ प्रदर्शन तब तक नहीं होना चाहिए जब तक कि आपके पास वास्तव में विशाल न हो प्रक्रियाओं की प्रक्रिया को संसाधित करने के लिए (जैसे, आप एक नेटवर्क ड्राइवर लिख रहे हैं और संदेश आने वाले ईथरनेट पैकेट हैं)।

तो, छद्म कोड में, पहली बात मैं कोशिश करेंगे:

Writer: 
    allocate message and fill it in 
    acquire lock 
     append node to intrusive list 
     signal condition variable 
    release lock 

Reader: 
    for(;;) 
     acquire lock 
      for(;;) 
       if there's a node 
        remove it 
        break 
       else 
        wait on condition variable 
       endif 
      endfor 
     release lock 
     process message 
     free message 
    endfor 

सिर्फ अगर इस लेखक सूत्र में अस्वीकार्य देरी लागू करने के लिए साबित होता है मैं ताला मुक्त कोड जाती थी, (जब तक कि मेरे पास एक उपयुक्त कतार पहले से ही झूठ नहीं बोलती)।

Answer 2

आप अपनी आवश्यकताओं पर विचार करना चाहेंगे - क्या वास्तव में यह मामला है कि कोई भी कतार वस्तुओं को त्याग नहीं सकता है? या यह है कि आप नहीं चाहते हैं कि बी लगातार कतार के दो तत्वों को खींचें जो निरंतर वस्तुओं में नहीं जा रहे थे क्योंकि इससे किसी भी तरह की घटनाओं का अनुक्रम गलत तरीके से प्रस्तुत किया जाएगा?

उदाहरण के लिए, यदि यह किसी प्रकार का डेटा लॉगिंग सिस्टम है, तो आप (समझदारी से) रिकॉर्ड में अंतराल नहीं चाहते हैं - लेकिन असीमित स्मृति के बिना, वास्तविकता यह है कि कुछ कोने के मामले में कहीं आप शायद ओवररन कर सकते हैं आपकी कतार क्षमता ..

इस मामले में एक समाधान में किसी विशेष प्रकार का विशेष तत्व होना चाहिए जिसे कतार में रखा जा सकता है, जो खोज के मामले को दर्शाता है कि उसे वस्तुओं को छोड़ना था। असल में आप एक अतिरिक्त तत्व रखते हैं, जो कि ज्यादातर समय शून्य है। प्रत्येक बार जब कतार में तत्व जोड़ने के लिए जाता है, यदि यह अतिरिक्त तत्व शून्य नहीं है, तो इसमें जाता है। यदि कोई पता चलता है कि कतार में कोई कमरा नहीं है, तो यह 'अतिरिक्त, कतार पूर्ण था' कहने के लिए यह अतिरिक्त तत्व कॉन्फ़िगर करता है। ।

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

Answer 3

विजुअल स्टूडियो 2010 2 नए पुस्तकालयों को जोड़ रहा है जो इस परिदृश्य को बहुत अच्छी तरह से समर्थन देते हैं, Asynchronous Agents Library और समांतर पैटर्न लाइब्रेरी।

एजेंटों पुस्तकालय समर्थन या अतुल्यकालिक संदेश गुजर गया है और 'लक्ष्य' के लिए संदेश भेजने के लिए और 'स्रोत' को

एक unbounded_buffer एक टेम्पलेट वर्ग जो प्रदान करता है कि मैं क्या लगता है कि आप देख रहे है से संदेश प्राप्त करने के लिए संदेश ब्लॉक शामिल के लिए:

#include <agents.h> 
#include <ppl.h> 
#include <iostream> 

using namespace ::Concurrency; 
using namespace ::std; 

int main() 
{ 
    //to hold our messages, the buffer is unbounded... 
    unbounded_buffer<int> buf1; 
    task_group tasks; 

    //thread 1 sends messages to the unbounded_buffer 
    //without blocking 
    tasks.run([&buf1](){ 
     for(int i = 0 ; i < 10000; ++i) 
     send(&buf1,i) 
    //signal exit 
    send(&buf1,-1); 
    }); 

    //thread 2 receives messages and blocks if there are none 

    tasks.run([&buf1](){ 
     int result; 
     while(result = receive(&buf1)!=-1) 
     { 
      cout << "I got a " << result << endl; 
     } 
    }); 

    //wait for the threads to end 
    tasks.wait(); 
} 

Answer 4

• क्यों <list> या <deque> एक म्युटेक्स ar साथ एसटीएल का उपयोग नहीं जोड़ना/निकालना? thread-safety of STL अपर्याप्त है?

• अपनी खुद की (अकेली/दोगुनी) लिंक्ड-लिस्ट-नोड क्लास क्यों न बनाएं जिसमें पॉइंटर होता है, और आइटम को उसमें से जोड़ा/निकाला जा सकता है? इस प्रकार अतिरिक्त आवंटन अनावश्यक बनाते हैं। आप threadA::add() और threadB::remove() में कुछ पॉइंटर्स को फ्रिब करें और आप कर चुके हैं।

• आप pthreads उपयोग कर रहे हैं (आपको लगता है कि एक म्युटेक्स के तहत, threadA पर अवरुद्ध प्रभाव जब तक आप वास्तव में कुछ गलत किया था नगण्य होगा करने के लिए ... चाहते हैं जबकि), sem_post() और sem_wait() की जाँच करें। विचार यह है कि थ्रेड बी sem_wait() के माध्यम से अनिश्चित काल तक अवरुद्ध कर सकता है जब तक कि थ्रेडए कतार पर कुछ नहीं डालता। फिर थ्रेडए sem_post() का आह्वान करता है। जो थ्रेड बी को अपना काम करने के लिए जागता है। जिसके बाद थ्रेड बी सो सकता है। यह एसिंक्रोनस सिग्नलिंग को संभालने का एक प्रभावी तरीका है, से पहले threadB::remove() पूर्ण करने जैसी चीजों का समर्थन करना।