तुल्यकालन और डेटा-रेस स्वतंत्रता
तुल्यकालन तंत्र समवर्ती थ्रेड्स का समन्वय करते हैं ताकि साझा डेटा को सुरक्षित रूप से एक्सेस किया जा सके, और डेटा-रेस स्वतंत्रता वह गुण है जो समवर्ती प्रोग्रामों को अनुमानित बनाता है।
Definition
तुल्यकालन साझा संसाधनों पर क्रम या पारस्परिक अपवर्जन को लागू करने के लिए समवर्ती गतिविधियों का समन्वय है, और डेटा-रेस स्वतंत्रता वह गुण है कि कोई भी दो थ्रेड एक ही मेमोरी स्थान को समवर्ती रूप से एक्सेस नहीं करते हैं, जिसमें कम से कम एक लेखन बिना किसी हस्तक्षेपकारी तुल्यकालन के होता है।
Scope
यह विषय उन तंत्रों और गुणों को शामिल करता है जो साझा स्थिति तक समवर्ती पहुंच को सही बनाते हैं: पारस्परिक अपवर्जन, ताले (locks), सेमाफोर और मॉनिटर, कंडीशन वैरिएबल, लॉक-मुक्त और प्रतीक्षा-मुक्त एल्गोरिदम, ट्रांजैक्शनल मेमोरी, हैपन्स-बिफोर संबंध, और डेटा रेस का पता लगाना। यह डेडलॉक, एटोमिसिटी और प्रोग्रामों को डेटा-रेस मुक्त रखने के लिए आवश्यक अनुशासन को संबोधित करता है।
Core questions
- पारस्परिक अपवर्जन कैसे प्राप्त किया जाता है और इसके खतरे क्या हैं (डेडलॉक, भुखमरी)?
- लॉक-आधारित और लॉक-मुक्त तुल्यकालन में क्या अंतर है?
- हैपन्स-बिफोर संबंध डेटा रेस को कैसे परिभाषित करता है?
- डेटा रेस का स्वचालित रूप से पता कैसे लगाया जा सकता है?
Key theories
- पारस्परिक अपवर्जन
- समवर्ती-नियंत्रण समस्या के लिए डिज्क्स्ट्रा के समाधान ने पारस्परिक अपवर्जन को मूलभूत तुल्यकालन आवश्यकता के रूप में स्थापित किया, यह गारंटी देते हुए कि महत्वपूर्ण अनुभाग एक साथ निष्पादित नहीं होते हैं।
- ट्रांजैक्शनल मेमोरी
- हर्लिही और मॉस ने ट्रांजैक्शनल मेमोरी का प्रस्ताव रखा, जिसमें मेमोरी ऑपरेशंस के समूह परमाणु रूप से निष्पादित होते हैं, जो समवर्ती डेटा संरचनाओं के निर्माण के लिए फाइन-ग्रेन्ड लॉकिंग का एक संयोज्य विकल्प प्रदान करते हैं।
- हैपन्स-बिफोर और डायनामिक रेस डिटेक्शन
- लैम्पर्ट के हैपन्स-बिफोर संबंध पर आधारित, इरेज़र डिटेक्टर ने दिखाया कि लॉकिंग अनुशासन की जाँच करके डेटा रेस को गतिशील रूप से कैसे खोजा जाए, जो स्वचालित रेस डिटेक्शन का एक उदाहरण है।
Clinical relevance
सही तुल्यकालन विश्वसनीय समवर्ती और समानांतर सॉफ्टवेयर के लिए आवश्यक है; डेटा रेस व्यवहार में कुछ सबसे मायावी बग का कारण बनती हैं। रेस डिटेक्टर, ट्रांजैक्शनल मेमोरी, और अनुशासित तुल्यकालन पैटर्न भरोसेमंद मल्टीथ्रेडेड सिस्टम बनाने के लिए केंद्रीय उपकरण हैं।
History
डिज्क्स्ट्रा के 1965 के पारस्परिक-अपवर्जन समाधान और उनके बाद के सेमाफोर ने तुल्यकालन की नींव रखी, जिसके बाद होरे और ब्रिन्च हैनसेन के मॉनिटर आए। लैम्पर्ट का 1978 का हैपन्स-बिफोर संबंध आधुनिक रेस परिभाषाओं का आधार है; हर्लिही और मॉस ने 1993 में ट्रांजैक्शनल मेमोरी पेश की, और डायनामिक रेस डिटेक्टर जैसे इरेज़र (1997) और बाद में हैपन्स-बिफोर उपकरण समवर्तीता को डीबग करने के लिए मानक बन गए।
Debates
- ताले बनाम लॉक-मुक्त और ट्रांजैक्शनल दृष्टिकोण
- डिजाइनर पारंपरिक लॉक-आधारित तुल्यकालन पर बहस करते हैं, जो सरल है लेकिन डेडलॉक और खराब संयोजन के लिए प्रवण है, लॉक-मुक्त एल्गोरिदम और ट्रांजैक्शनल मेमोरी के खिलाफ, जो जटिलता या ओवरहेड की कीमत पर संयोज्यता और प्रगति की गारंटी में सुधार करते हैं।
Key figures
- Edsger Dijkstra
- Leslie Lamport
- Maurice Herlihy
- C. A. R. Hoare
- Stefan Savage
Related topics
Seminal works
- dijkstra1965
- herlihy1993
- savage1997
- lamport1978
Frequently asked questions
- डेटा रेस क्या है?
- एक डेटा रेस तब होती है जब दो थ्रेड एक ही मेमोरी स्थान को समवर्ती रूप से एक्सेस करते हैं, कम से कम एक एक्सेस एक लेखन होता है, और एक्सेस तुल्यकालन द्वारा आदेशित नहीं होते हैं, जिससे अधिकांश मेमोरी मॉडल में अपरिभाषित या अप्रत्याशित व्यवहार होता है।
- लॉक-आधारित और लॉक-मुक्त तुल्यकालन में क्या अंतर है?
- लॉक-आधारित तुल्यकालन पारस्परिक अपवर्जन का उपयोग करता है ताकि एक समय में केवल एक थ्रेड एक महत्वपूर्ण अनुभाग में प्रवेश करे, जबकि लॉक-मुक्त तुल्यकालन परमाणु संचालन का उपयोग यह गारंटी देने के लिए करता है कि कुछ थ्रेड हमेशा ताले धारण किए बिना प्रगति करता है, जिससे डेडलॉक से बचा जा सके।