लॉक फ्री एकाधिक पाठक एकल लेखक

Question

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

इस उपाय करने दो विकल्प हैं:

1. उपयोग TMultiReadExclusiveWriteSynchronizer
2. अब तक निम्नलिखित एक ताला मुक्त दृष्टिकोण

उपयोग करके किसी भी अवरुद्ध से दूर 2. के लिए मैं मिल गया है (कोई भी कोड जो इससे कोई फर्क नहीं पड़ता है):

type 
    TDataManager = class 
    private 
    FAccessCount: integer; 
    FData: TDataClass; 
    public 
    procedure Read(out _Some: integer; out _Data: double); 
    procedure Write(_Some: integer; _Data: double); 
    end; 

procedure TDataManager.Read(out _Some: integer; out _Data: double); 
var 
    Data: TDAtaClass; 
begin 
    InterlockedIncrement(FAccessCount); 
    try 
    // make sure we get both values from the same TDataClass instance 
    Data := FData; 
    // read the actual data 
    _Some := Data.Some; 
    _Data := Data.Data; 
    finally 
    InterlockedDecrement(FAccessCount); 
    end; 
end; 

procedure TDataManager.Write(_Some: integer; _Data: double); 
var 
    NewData: TDataClass; 
    OldData: TDataClass; 
    ReaderCount: integer; 
begin 
    NewData := TDataClass.Create(_Some, _Data); 
    InterlockedIncrement(FAccessCount); 
    OldData := TDataClass(InterlockedExchange(integer(FData), integer(NewData)); 
    // now FData points to the new instance but there might still be 
    // readers that got the old one before we exchanged it. 
    ReaderCount := InterlockedDecrement(FAccessCount); 
    if ReaderCount = 0 then 
    // no active readers, so we can safely free the old instance 
    FreeAndNil(OldData) 
    else begin 
    /// here is the problem 
    end; 
end; 

दुर्भाग्य से इसे बदलने के बाद ओल्डडाटा इंस्टेंस से छुटकारा पाने की छोटी समस्या है। यदि कोई अन्य धागा वर्तमान में रीड विधि (रीडरकाउंट = 0) के भीतर नहीं है, तो इसे सुरक्षित रूप से निपटाया जा सकता है और यही वह है। लेकिन अगर ऐसा नहीं है तो मैं क्या कर सकता हूं? मैं इसे अगली कॉल तक बस स्टोर कर सकता हूं और इसे वहां से निपट सकता हूं, लेकिन विंडोज शेड्यूलिंग सिद्धांत में रीडर विधि के भीतर एक पाठक धागा सो सकती है और अभी भी ओल्डडाटा का संदर्भ मिला है।

यदि आपको उपरोक्त कोड के साथ कोई अन्य समस्या दिखाई देती है, तो कृपया मुझे इसके बारे में बताएं। यह कई कोर वाले कंप्यूटरों पर चलाना है और उपर्युक्त तरीकों को अक्सर बार कहा जाता है।

इस मामले में: मैं बिल्टिन मेमोरी मैनेजर के साथ डेल्फी 2007 का उपयोग कर रहा हूं। मुझे पता है कि स्मृति प्रबंधक शायद एक नई कक्षा बनाते समय कुछ लॉक लागू करता है लेकिन मैं इस पल के लिए इसे अनदेखा करना चाहता हूं।

संपादित करें: यह उपर्युक्त से स्पष्ट नहीं हो सकता है: TDataManager ऑब्जेक्ट के पूर्ण जीवनकाल के लिए डेटा में केवल एक धागा है जो लिखने के लिए प्रतिस्पर्धा कर सकता है। तो यह एमआरडब्ल्यू का एक विशेष मामला है।

Answer 1

मुझे किसी भी लॉक-फ्री (या ऊपर दिए गए उदाहरण में माइक्रो-लॉकिंग) के बारे में पता नहीं है MREW दृष्टिकोण जिसे इंटेल 86 कोड पर लागू किया जा सकता है।

छोटे (तेजी से समाप्त हो रही) के लिए OmniThreadLibrary से एक कताई दृष्टिकोण ताले ठीक काम करता है:

type 
TOmniMREW = record 
strict private 
    omrewReference: integer;  //Reference.Bit0 is 'writing in progress' flag 
public 
    procedure EnterReadLock; inline; 
    procedure EnterWriteLock; inline; 
    procedure ExitReadLock; inline; 
    procedure ExitWriteLock; inline; 
end; { TOmniMREW } 

procedure TOmniMREW.EnterReadLock; 
var 
    currentReference: integer; 
begin 
    //Wait on writer to reset write flag so Reference.Bit0 must be 0 than increase Reference 
    repeat 
    currentReference := omrewReference AND NOT 1; 
    until currentReference = InterlockedCompareExchange(omrewReference, currentReference + 2, currentReference); 
end; { TOmniMREW.EnterReadLock } 

procedure TOmniMREW.EnterWriteLock; 
var 
    currentReference: integer; 
begin 
    //Wait on writer to reset write flag so omrewReference.Bit0 must be 0 then set omrewReference.Bit0 
    repeat 
    currentReference := omrewReference AND NOT 1; 
    until currentReference = InterlockedCompareExchange(omrewReference, currentReference + 1, currentReference); 
    //Now wait on all readers 
    repeat 
    until omrewReference = 1; 
end; { TOmniMREW.EnterWriteLock } 

procedure TOmniMREW.ExitReadLock; 
begin 
    //Decrease omrewReference 
    InterlockedExchangeAdd(omrewReference, -2); 
end; { TOmniMREW.ExitReadLock } 

procedure TOmniMREW.ExitWriteLock; 
begin 
    omrewReference := 0; 
end; { TOmniMREW.ExitWriteLock } 

मैं बस यहाँ एक संभव संरेखण मुद्दा देखा - कोड की जाँच करनी चाहिए कि omrewReference 4-संरेखित है। लेखक को सूचित करेंगे।

Answer 2

बस एक जोड़ा - जो आप यहां देख रहे हैं उसे आम तौर पर Hazard Pointers के नाम से जाना जाता है। मुझे नहीं पता कि क्या आप डेल्फी में कुछ ऐसा कर सकते हैं।

Answer 3

यह कुछ समय हो गया है क्योंकि मुझे डेल्फी में गंदे हाथ मिल गए हैं, इसलिए उपयोग करने से पहले इसे सत्यापित करें, लेकिन ... स्मृति से, यदि आप इंटरफ़ेस का उपयोग करते हैं और TInterfacedObject का उपयोग करके कार्यान्वयन का उपयोग करते हैं तो आप संदर्भ-गणना व्यवहार प्राप्त कर सकते हैं।

type 
    IDataClass = interface 
     function GetSome: integer; 
     function GetData: double; 

     property Some: integer read GetSome; 
     property Data: double read GetData; 
    end; 

    TDataClass = class(TInterfacedObject, IDataClass) 
    private 
     FSome: integer; 
     FData: double; 
    protected 
     function GetSome: integer; 
     function GetData: double; 
    public 
     constructor Create(ASome: integer; AData: double); 
    end; 

तो फिर तुम (... आप आसानी से संदर्भ गिनती समस्याओं मिल ISomeData मिश्रण और TSomeData एक बहुत बुरा विचार है) प्रकार ISomeData के अपने सभी चर बजाय बनाते हैं।

असल में यह आपके पाठक कोड में संदर्भ गणना को स्वचालित रूप से बढ़ने का कारण बनता है, जहां यह डेटा के स्थानीय संदर्भ को लोड करता है, और परिवर्तनीय पत्तियों का दायरा होने पर यह घट जाता है, जिस बिंदु पर यह वहां आवंटित होगा।

मुझे पता है कि यह एक इंटरफ़ेस और कक्षा कार्यान्वयन में आपके डेटा वर्ग के एपीआई को डुप्लिकेट करने के लिए थोड़ा कठिन है, लेकिन यह वांछित व्यवहार प्राप्त करने का सबसे आसान तरीका है।

Answer 4

मुझे आपके लिए एक संभावित समाधान मिला है; यह नए पाठकों को तब तक शुरू करने देता है जब तक लेखक लिखना नहीं चाहता। लेखक तब पाठकों को खत्म करने और अपना लेखन करने की प्रतीक्षा करता है। लेखन करने के बाद पाठक एक बार और पढ़ सकते हैं।

इसके अलावा, इस समाधान को ताले या म्यूटेक्स की आवश्यकता नहीं है, लेकिन इसे परमाणु परीक्षण-और-सेट ऑपरेशन की आवश्यकता है। मुझे डेल्फी नहीं पता और मैंने लिस्प में अपना समाधान लिखा, इसलिए मैं इसे छद्म कोड में वर्णित करने की कोशिश करूंगा।

(कैप्स समारोह के नाम हैं, इन सभी कार्यों लेने के लिए और कोई तर्क वापसी)

integer access-mode = 1; // start in reader mode. 

WRITE loop with current = accessmode, 
      with new = (current & 0xFFFFFFFe) 
      until test-and-set(access-mode, current to new) 
     loop until access-mode = 0; 

ENDWRITE assert(access-mode = 0) 
     set access-mode to 1 

READ loop with current = (accessmode | 1), 
      with new = (current + 2), 
      until test-and-set(access-mode, current to new) 
ENDREAD loop with current = accessmode 
      with new = (current - 2), 
      until test-and-set(access-mode, current to new) 

का उपयोग करने के लिए, एक रीडर पढ़ने और ENDREAD जब किया से पहले पढ़ें कहता है। अकेला लेखक लिखने से पहले WRITE को कॉल करता है और पूरा होने पर अंतराल लिखता है।

विचार एक पूर्णांक है जिसे एक्सेस-मोड कहा जाता है जिसे सबसे कम बिट में बूलियन होता है, और में उच्च बिट्स की गणना होती है। WRITE बिट को 0 पर सेट करता है, और तब तक स्पिन करता है जब तक कि पर्याप्त ENDREADs शून्य तक पहुंच मोड को गिनती न करें। एंडराइट एक्सेस-मोड को वापस 1 पर सेट करता है। वर्तमान एक्सेस-मोड को 1 के साथ पढ़ता है, इसलिए उनका टेस्ट-एंड-सेट केवल तब ही पास होगा जब कम-बिट शुरू होने के लिए उच्च था। मैं कम-से-कम अकेले छोड़ने के लिए 2 जोड़ता हूं और घटता हूं।

पाठकों की गिनती प्राप्त करने के लिए बस एक-एक करके स्थानांतरित मोड को ले जाएं।