टाइमस्टैम्प-आधारित समवर्ती नियंत्रण

कंप्यूटर विज्ञान में, TIMESTAMP -आधारित समवर्ती नियंत्रण एल्गोरिदम एक गैर-लॉक समवर्ती नियंत्रण विधि है। इसका उपयोग कुछ डेटाबेस में टाइमस्टैम्प का उपयोग करके लेनदेन को सुरक्षित रूप से संभालने के लिए किया जाता है।

संचालन

धारणाएँ

• प्रत्येक टाइमस्टैम्प मान अद्वितीय है और समय में एक पल का सटीक प्रतिनिधित्व करता है।
• उच्च-मूल्य वाला टाइमस्टैम्प कम-मूल्य वाले टाइमस्टैम्प की तुलना में बाद में होता है।

टाइमस्टैम्प उत्पन्न करना

टाइमस्टैम्प उत्पन्न करने के लिए कई अलग-अलग तरीकों का उपयोग किया गया है

• लेनदेन की शुरुआत में सिस्टम की घड़ी के मूल्य को टाइमस्टैम्प के रूप में उपयोग करें।
• थ्रेड-सुरक्षित साझा काउंटर का उपयोग करें जो लेनदेन की शुरुआत में टाइमस्टैम्प के रूप में बढ़ाया जाता है।
• उपरोक्त दो विधियों का संयोजन।

औपचारिक

प्रत्येक लेनदेन ($T_{i}$) क्रियाओं की एक क्रमबद्ध सूची है ($A_{ix}$). लेन-देन अपनी पहली कार्रवाई करने से पहले ($A_{i1}$), इसे वर्तमान टाइमस्टैम्प, या किसी अन्य कुल ऑर्डर अनुक्रम के साथ चिह्नित किया गया है: $TS(T_{i})=NOW()$. प्रत्येक लेन-देन को शुरू में लेन-देन का एक खाली सेट भी दिया जाता है जिस पर यह निर्भर करता है, $DEP(T_{i})=[]$, और पुरानी वस्तुओं का प्रारंभिक रूप से खाली सेट जिसे उसने अद्यतन किया, $OLD(T_{i})=[]$.

प्रत्येक वस्तु (कंप्यूटर विज्ञान) $(O_{j})$ डेटाबेस में दो टाइमस्टैम्प फ़ील्ड दिए गए हैं जिनका उपयोग समवर्ती नियंत्रण के अलावा अन्य नहीं किया जाता है: $RTS(O_{j})$ वह समय है जब लेन-देन में वस्तु का मूल्य अंतिम बार उपयोग किया गया था, $WTS(O_{j})$ वह समय है जब लेन-देन द्वारा वस्तु का मूल्य अंतिम बार अद्यतन किया गया था।

सभी के लिए $T_{i}$:

प्रत्येक क्रिया के लिए $A_{ix}$:

अगर $A_{ix}$ के मान का उपयोग करना चाहता है $O_{j}$:

अगर $WTS(O_{j})>TS(T_{i})$ फिर निरस्त करें (एक हालिया थ्रेड ने मान को अधिलेखित कर दिया है),

अन्यथा निर्भरता के सेट को अद्यतन करें $DEP(T_{i}).\mathrm {add} (WTS(O_{j}))$ और सेट करें $RTS(O_{j})=\max(RTS(O_{j}),TS(T_{i}))$;

अगर $A_{ix}$ का मान अद्यतन करना चाहता है $O_{j}$:

अगर $RTS(O_{j})>TS(T_{i})$ फिर निरस्त करें (एक हालिया थ्रेड पहले से ही पुराने मूल्य पर निर्भर है),

अगर $WTS(O_{j})>TS(T_{i})$ फिर छोड़ें (थॉमस लिखें नियम),

अन्यथा पिछले मानों को संग्रहित करें, $OLD(T_{i}).\mathrm {add} (O_{j},WTS(O_{j}))$, तय करना $WTS(O_{j})=TS(T_{i})$, और का मान अद्यतन करें $O_{j}$.

जबकि इसमें लेन-देन हो रहा है $DEP(T_{i})$ वह समाप्त नहीं हुआ है: रुको

यदि कोई लेन-देन है $DEP(T_{i})$ वह गर्भपात हो गया तो गर्भपात हो गया

अन्यथा: प्रतिबद्ध.

गर्भपात के लिए:

प्रत्येक के लिए $(\mathrm {old} O_{j},\mathrm {old} WTS(O_{j}))$ में $OLD(T_{i})$

अगर $WTS(O_{j})$ के बराबर होती है $TS(T_{i})$ फिर पुनर्स्थापित करें $O_{j}=\mathrm {old} O_{j}$ और $WTS(O_{j})=\mathrm {old} WTS(O_{j})$

अनौपचारिक

जब भी कोई लेन-देन शुरू होता है, तो उसे एक टाइमस्टैम्प प्राप्त होता है। यह टाइमस्टैम्प अन्य लेनदेन के सापेक्ष उस क्रम को इंगित करता है जिसमें लेनदेन होना चाहिए। इसलिए, एक ही वस्तु को प्रभावित करने वाले दो लेन-देन दिए जाने पर, पहले वाले टाइमस्टैम्प के साथ लेन-देन का संचालन बाद के टाइमस्टैम्प के साथ लेन-देन के संचालन से पहले निष्पादित होना चाहिए। हालाँकि, यदि गलत लेनदेन का संचालन वास्तव में पहले प्रस्तुत किया जाता है, तो इसे निरस्त कर दिया जाता है और लेनदेन को फिर से शुरू करना होगा।

डेटाबेस में प्रत्येक ऑब्जेक्ट में एक रीड टाइमस्टैम्प होता है, जिसे ऑब्जेक्ट का डेटा पढ़ने पर अपडेट किया जाता है, और एक राइट टाइमस्टैम्प होता है, जो ऑब्जेक्ट का डेटा बदलने पर अपडेट किया जाता है।

यदि कोई लेन-देन किसी वस्तु को पढ़ना चाहता है,

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

यदि कोई लेन-देन किसी वस्तु को लिखना चाहता है,

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

पुनर्प्राप्ति

For an explanation of the terms recoverable (RC), avoids cascading aborts (ACA) and strict (ST), see Schedule (computer science).

ध्यान दें कि अपने मूल रूप में टाइमस्टैम्प ऑर्डर पुनर्प्राप्ति योग्य इतिहास उत्पन्न नहीं करता है। उदाहरण के लिए लेन-देन के निम्नलिखित इतिहास पर विचार करें $T_{1}$ और $T_{2}$:

$W_{1}(x)\;R_{2}(x)\;W_{2}(y)\;C_{2}\;R_{1}(z)\;C_{1}$

इसे टीओ शेड्यूलर द्वारा तैयार किया जा सकता है, लेकिन यह पुनर्प्राप्त करने योग्य नहीं है $T_{2}$ एक अप्रतिबद्ध लेनदेन से पढ़ने के बावजूद भी प्रतिबद्ध है। यह सुनिश्चित करने के लिए कि यह पुनर्प्राप्त करने योग्य इतिहास तैयार करता है, एक शेड्यूलर प्रत्येक लेनदेन से पढ़े गए अन्य लेनदेन की एक सूची रख सकता है, और इस सूची में केवल प्रतिबद्ध लेनदेन शामिल होने से पहले किसी लेनदेन को प्रतिबद्ध नहीं होने दे सकता है। कैस्केडिंग गर्भपात से बचने के लिए, शेड्यूलर अनकमिटेड लेनदेन द्वारा लिखे गए डेटा को गंदे के रूप में टैग कर सकता है, और अनटैग किए जाने से पहले ऐसे डेटा आइटम पर कभी भी रीड ऑपरेशन शुरू नहीं होने देता। सख्त इतिहास प्राप्त करने के लिए, अनुसूचक को गंदी वस्तुओं पर किसी भी संचालन की अनुमति नहीं देनी चाहिए।

कार्यान्वयन मुद्दे

टाइमस्टैम्प रिज़ॉल्यूशन

यह दो आसन्न टाइमस्टैम्प के बीच व्यतीत हुआ न्यूनतम समय है। यदि टाइमस्टैम्प का रिज़ॉल्यूशन बहुत बड़ा (मोटा) है, तो दो या दो से अधिक टाइमस्टैम्प के बराबर होने की संभावना बढ़ जाती है और इस प्रकार कुछ लेनदेन सही क्रम से बाहर होने में सक्षम हो जाते हैं। उदाहरण के लिए, यह मानते हुए कि हमारे पास एक ऐसी प्रणाली है जो प्रति सेकंड एक सौ अद्वितीय टाइमस्टैम्प बना सकती है, और दो घटनाएँ जो 2 मिलीसेकंड के अंतराल पर घटित होती हैं, उन्हें संभवतः एक ही टाइमस्टैम्प दिया जाएगा, भले ही वे वास्तव में अलग-अलग समय पर घटित हुई हों।

टाइमस्टैम्प लॉकिंग

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

यह भी देखें

• बहुसंस्करण समवर्ती नियंत्रण
• टाइमस्टैम्पिंग (कंप्यूटिंग)

श्रेणी:समवर्ती नियंत्रण श्रेणी:समवर्ती नियंत्रण एल्गोरिदम श्रेणी:लेनदेन प्रसंस्करण