मैंने हाल ही में TVar
से संबंधित कई प्रश्न पूछे हैं, और मुझे अभी भी livelock के बारे में चिंता है।डेडलॉक्स या संसाधन भुखमरी के बिना समवर्ती सामान्य डेटा संरचना
तो मैं इस संरचना के बारे में सोचा:
- प्रत्येक लेनदेन के लिए एक अनूठा प्राथमिकता (शायद सृष्टि के क्रम में आवंटित) हो जाता है।
- लेनदेन उन डेटा पर पढ़ने/लिखने वाले ताले पाने का प्रयास करते हैं। स्वाभाविक रूप से, एक साथ पढ़ना ठीक है, लेकिन एक लिखने के ताले सभी को छोड़कर (दोनों पढ़ और लिखते हैं)।
- कहें लेनदेन ए लेनदेन बी से अधिक प्राथमिकता है। यदि ए लॉक रखता है, बी इंतजार कर रहा है, लेकिन यदि बी लॉक रखता है और ए चाहता है, बी को लॉक से बूट किया जाता है, ए प्राप्त करता है, और लेनदेन बी पुनरारंभ होता है (जैसे
TVar
के साथ)। बी हालांकि पुनः प्रयास के लिए अपनी वर्तमान प्राथमिकता रखता है। - जब एक ताला मुक्त हो जाता है और लेन-देन इंतजार कर रहे हैं, तो यह उच्चतम प्राथमिकता लेनदेन पर जाता है, और शेष प्रतीक्षा करते रहते हैं।
इस प्रणाली मेरा मानना है कि गतिरोध से बचाता है, लेकिन यह भी भुखमरी से बचाता है (TVar
के विपरीत)। मैं सोच रहा था कि किसी ने इस तरह के एक सिस्टम को लागू किया है, क्योंकि यह काफी स्पष्ट लगता है और मैं पहिया को फिर से शुरू नहीं करना चाहता हूं।
बेशक, इस तरह के दृष्टिकोण को उपयोगकर्ता को प्राथमिकताओं को निर्दिष्ट करने के लिए आसानी से बढ़ाया जा सकता है।
प्राथमिकता जोड़ी (user_supplied_prio, auto_increment)
हो सकती है, user_supplied_prio
प्राथमिकता ले रही है, लेकिन एफआईएफओ आदेश में समान प्राथमिकता कार्य हल हो रही है।
टिप्पणी/समाधान:
असल में, जब मैं इसके बारे में सोचो, क्या मैं का वर्णन पहले से ही हास्केल में, मौजूद है बस एक IORef
सभी डेटा के चारों ओर लिपटा का उपयोग कर, और केवल atomicModifyIORef
का उपयोग करके। atomicModifyIORef
यह सुनिश्चित करेगा कि लेनदेन अनुक्रम में लागू होते हैं। हालांकि, कोई ऐसा सोच सकता है कि इसका मतलब है कि डेटा संरचना अनुक्रमिक है (यानी प्रभावी रूप से एक धागे तक ही सीमित है) लेकिन यह आलस्य के कारण वास्तव में समानांतर है।
इसे समझाने के लिए, एक महंगी फ़ंक्शन f
पर विचार करें। हम इसे "foo" कुंजी के साथ Data.Map
पर लागू करने जा रहे हैं।
यह (foo -> x)
(foo -> future(f x))
के साथ प्रतिस्थापित करता है। यह धागा वास्तव में काम करेगा कि (f x)
वास्तव में क्या है, लेकिन इस बीच हम "बार" पर जी लागू कर सकते हैं। चूंकि "बार" को जी लगाने के बाद "foo" के परिणाम की आवश्यकता नहीं है, हम इसे एक ही समय में काम कर सकते हैं।
कोई डेडलॉक्स, कोई भुखमरी नहीं, अंत में सभी लेनदेन संसाधित किए जाएंगे (मोटे तौर पर उन्हें प्राप्त होने वाले क्रम में)।
मुझे हास्केल में मौजूद किसी भी सिस्टम से अनजान है। यह ज्यादातर उपयोगकर्ताओं के लिए अत्यधिक जटिल लगता है, और इसके बजाय कार्यान्वित करने के लिए। विशेष रूप से, एक असाइन किए गए ताला को अमान्य करने के लिए या तो मतदान (कोड के लिए कुछ हद तक थकाऊ) या asynch अपवाद (वर्म्स का एक अन्य अन्य कर) की आवश्यकता होगी। मैं सुझाव दूंगा कि आप अपने कार्यान्वयन के लिए बस एसटीएम आज़माएं और देखें कि यह कैसे काम करता है; एसटीएम एल्गोरिदम आम तौर पर इतना आसान होते हैं कि यदि आपको इसे बदलने की आवश्यकता है तो यह एक महत्वपूर्ण समय निवेश नहीं होगा। –
एसटीएम व्यूपॉइंट से बात करते हुए, रनटाइम को प्राथमिकता तंत्र जोड़ना (जैसा कि आपने तिथि के आधार पर उल्लेख किया है) उसी लाइफेलॉक मुद्दे को हल करेगा जो मुझे विश्वास है। हालांकि, यह शेड्यूलर के विकल्पों को गंभीरता से सीमित कर सकता है, जो कि मौजूदा एसटीएम रनटाइम में ऐसी कोई तंत्र नहीं है, इसका कारण भी हो सकता है। पीएस: आप अपने पिछले प्रश्नों के कुछ उत्तरों को "स्वीकृत उत्तर" के रूप में चिह्नित करना चाहते हैं, ताकि समुदाय को यह पता चल सके कि प्रश्न हल हो गया है या नहीं। – Peter
प्रदर्शन आवश्यकताओं क्या हैं? ग्लोबल टिकट लॉक (http://en.wikipedia.org/wiki/Ticket_lock) जैसे पर्याप्त मोटे अनाज के माध्यम से आप जो चाहते हैं उसे प्राप्त कर सकते हैं, या सभी कार्यों को एक ही थ्रेड द्वारा क्रमशः निष्पादित करने के लिए। परिष्कृत सिंक्रनाइज़ेशन विधियों में उच्च ओवरहेड होता है।यदि वैश्विक सिंक्रनाइज़ेशन किसी दिए गए वर्कलोड के लिए बाधा नहीं है, तो यह शायद तेज़ है। – Heatsink