2011-09-28 11 views
10

मैंने स्टैक के कुछ लॉक मुक्त कार्यान्वयन देखा है ... मेरा प्रश्न दृश्यता के बारे में है, परमाणुता नहीं। उदाहरण के लिए तत्वों (पॉइंटर्स) लॉक फ्री स्टैक के अधिकांश 64 बिट पर होना चाहिए? मुझे ऐसा लगता है, क्योंकि आप दृश्यता की गारंटी नहीं दे सकते। रियल उदाहरण: इस सुरक्षित रूप से सम्मिलित किया जा सकता है और struct ताला मुक्त कंटेनर से हटाताला मुक्त कंटेनर और दृश्यता

struct person 
{ 
    string name; 
    uint32_t age; 
} 

संपादित करें: कुछ लोगों को प्रश्न से उलझन में रहे हैं। थोड़ा सा समझाने के लिए: यदि लेखक स्टैक पर व्यक्ति को धक्का देता है, तो पाठक इसे प्राप्त करता है, क्या यह गारंटी देता है कि पाठक व्यक्ति की सही सामग्री (स्मृति दृश्यता) देखता है।

+0

आपने इस बार दो बार बक्षीस की पेशकश की है - लेकिन मुझे संदेह है कि सवाल स्वयं गलत है - यही कारण है कि आपको उपयोगी उत्तर नहीं मिल रहे हैं। –

+0

कृपया परिभाषित करें कि प्रश्न के साथ क्या गलत है ... लॉक फ्री स्टैक मौजूद हैं। और वे सिर के लिए पॉइंटर्स का उपयोग करते हैं, अगले ... – NoSenseEtAl

उत्तर

3

मैं गलत हो सकता हूं, लेकिन मुझे लगता है कि सवाल गलत है।

परमाणु निर्देश आमतौर पर सिंगल पॉइंटर लंबाई डेटा के साथ सौदा करते हैं; सबसे अधिक, दो पॉइंटर लंबाई डेटा के लायक के साथ।

एक ठेठ संरचना परमाणु रूप से छेड़छाड़ नहीं की जा सकती क्योंकि यह बहुत बड़ी है।

तो ताला मुक्त ढेर और केवल तत्वों की ओर इशारा से छेड़छाड़ किया जाएगा (जो AFAIK सूचक लंबाई सीमाओं पर संरेखित करने की आवश्यकता है - मैं कोई मंच के बारे में पता है, जहां यह स्थिति नहीं है)।

0

हां संरचना का उपयोग किया जा सकता है। चूंकि आपको लॉक-फ्री डेटा स्ट्रक्चर की आवश्यकता है, इसलिए संरचना के अंदरूनी भाग का प्रतिनिधित्व करने वाले एक मूल्य को परमाणु रूप से अद्यतन करने का कोई तरीका है। तत्व या पेलोड का आकार इसकी लॉक-मुक्त प्रकृति पर कोई प्रभाव नहीं पड़ेगा। डेटा

  1. कॉपी
  2. डेटा संशोधित
  3. atomically जाँच करें कि मूल वस्तु असंशोधित कर दिया गया है और इसे अद्यतन:

    मैं यह समझ के रूप में, एक ताला मुक्त डेटा संरचना इतनी तरह काम करेंगे

  4. अन्यथा शुरू से ही दोहराने

तो जब तक तीसरे चरण atomically किया जा सकता है सब ठीक हैं।

तत्वों को अपने आप परमाणु रूप से अद्यतन करने योग्य बनाना आपको कोई लाभ नहीं देगा क्योंकि कंटेनर को उन्हें समूह के रूप में सामूहिक रूप से प्रबंधित करना है।

0

नोट: कृपया इस उत्तर को सही के रूप में चिह्नित करें यदि आप वास्तव में इस दृष्टिकोण का परीक्षण करते हैं।

अपने प्रश्न के बारे में है कि क्या नीचे सुरक्षित रूप से डाला जा struct और ताला मुक्त कंटेनर से हटा:

struct person 
{ 
    string name; 
    uint32_t age; 
} 

किसी भी लम्बाई के बहु बाइट दृश्यों को सुरक्षित रूप से डाला जा सकता है/लॉक मुक्त कंटेनर से हटा दिया है, तो आप एक का उपयोग अनावश्यक एन्कोडिंग। आइए मान लें कि हमारे पास पहले से ही 4 बाइट्स (32 बिट्स) में हेरफेर करने के लिए परमाणु निर्देश हैं। उस मामले में, हम तो जैसे uint32_t age क्षेत्र सांकेतिक शब्दों में बदलना कर सकते हैं:

struct age_t 
{ 
    uint32_t age_low; 
    uint32_t age_high; 
} 

क्षेत्र age_low भंडार कम बिट्स (उदाहरण के लिए, कम 16 बिट) 32-बिट uint32_t age की। फ़ील्ड age_high शेष उच्च बिट्स स्टोर करता है।सैद्धांतिक रूप:

struct age_t 
{ 
    uint16_t age_low; 
    uint16_t id_low; 
    uint16_t age_high; 
    uint16_t id_high; 
} 

क्षेत्रों id_low और id_high एक आईडी लेखक की पहचान होनी चाहिए।

एक पढ़ा दो परमाणु 32-बिट पढ़ने के रूप में लागू किया जाता है, और सफल होता है यदि सभी id_ भागों एक दूसरे के बराबर हैं। यदि यह विफल रहता है, तो पढ़ने के लिए ऑपरेशन को पुनरारंभ करना होगा।

एक लेखन दो परमाणु 32-बिट लिखने के रूप में लागू किया जाता है, और उसके बाद पूरे age_t मान के पढ़ने के बाद किया जाता है। लेखन सफल होता है यदि: पिछले वाक्य में वर्णित पढ़ा सफल होता है और पढ़ी गई आईडी लिखित आईडी के बराबर होती है।

string मूल्य के बारे में: सिद्धांत समान है। आपको केवल यह पता लगाने की आवश्यकता है कि कैसे age मान विभाजित किया गया था, इसके बाइनरी मान को कैसे विभाजित किया जाए। पूरे person संरचना को पढ़ने/लिखने के संबंध में वही।

2

मैं करने के लिए किया जा रहा थोड़ा सवाल अपने आप से उलझन में स्वीकार करना होगा ...

लॉक मुक्त डेटा संरचनाओं संकेत नोड्स (मशीन आकार & संरेखण के) में चालाकी करके मौजूद हैं। उन नोड्स में आपके लॉक-फ्री डेटा-स्ट्रक्चर की वास्तविक "सामग्री" होती है। उस सामग्री में कोई मनमाना आकार हो सकता है जिसे आप चाहते हैं, इसलिए आपकी संरचना वहां रखी जा सकती है। लॉक-फ्री डेटा-स्ट्रक्चर के लिए सामान्य नोड कुछ ऐसा दिखता है:

संरचना नोड {ATOMIC_PTR अगला; सामग्री; }

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

+0

मैंने प्रश्न को एक छोटे से स्पष्टीकरण के साथ अद्यतन किया – NoSenseEtAl

0

थ्रेड सुरक्षित कंटेनर (लॉकफ्री या उस मामले के लिए ताले के साथ) सूची/कंटेनर की थ्रेड सुरक्षा को हल करें जो आपके द्वारा कंटेनर में रखी गई वस्तुओं की थ्रेड सुरक्षा नहीं है। इस प्रकार लॉक-फ्री स्टैक सुनिश्चित करेगा कि पुश और पॉप थ्रेडसेफ और लॉक-फ्री हैं, लेकिन यदि आपके पास दो अलग-अलग धागे हैं जो पॉइंटर्स को उसी स्ट्रक्चर इंस्टेंस में रखते हैं (उदाहरण के लिए स्टैक में धक्का दिया गया थ्रेड अभी भी पोंटर और दूसरा धागा ढेर पॉप) आप कुछ अन्य धागे की सुरक्षा उपाय के उपयोग करने के लिए structs स्थिरता

1
अन्य QnA इतने पर के के अनुसार

सुनिश्चित करने के लिए होगा,

प्रत्येक x86 इंटरलॉक निर्देश (सीएएस समेत) एक पूर्ण मेमोरी बाधा दर्शाता है। तो, कम से कम x86 पर, हमें लॉक-फ्री कंटेनरों के तत्वों की दृश्यता की परवाह करने की आवश्यकता नहीं है (मानते हुए कि वे सीएएस का उपयोग करते हैं।)

0

कोई व्यक्ति मनमानी आकार के डेटा तत्वों के लिए एक डेक्यू के थ्रेड-सुरक्षित कार्यान्वयन को कार्यान्वित कर सकता है यदि तत्व किसी भी विशेष क्रम में स्टैक या कतार में संग्रहीत नहीं होते हैं, और यदि कोई थ्रेड-सुरक्षित कतार का उपयोग करता है गैर-आवंटित वस्तुओं के सूचकांक को पकड़ने के साथ-साथ थ्रेड-सुरक्षित डेक्यू को डेटा स्लॉट के सूचकांक को पकड़ने के लिए जो संलग्न/ढेर वस्तुओं को पकड़ते हैं। डेक्यू में किसी आइटम को लिखने से "आवंटित स्लॉट" कतार से उस नंबर को खींचने, उस स्लॉट पर वांछित डेटा लिखने और फिर "मुख्य" डेक्यू में उस संख्या के सूचकांक को एनक्यूइंग करने की आवश्यकता होगी। किसी आइटम को प्राप्त करने के लिए इसकी संख्या को "मुख्य" डेक्यू से खींचने की आवश्यकता होती है, इसे कहीं और कॉपी करनी पड़ती है, और उसके बाद उस नंबर को "आवंटित स्लॉट" कतार में लगाया जाता है।

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

संबंधित मुद्दे