अनुक्रमिक प्रक्रियाओं के आदान-प्रदान के सिद्धांत का परिचय (CSP)

• भाग 1
• भाग २

प्रस्तावना

यह पाठ चार्ल्स ई। होर की एक पुस्तक के शुरुआती अध्यायों का अनुवाद और संक्षिप्त वर्णन है । लक्ष्य प्रक्रियाओं के कलन के इस बीजगणित के साथ रूसी-भाषी दर्शकों को परिचित करना है, जो व्यापक प्रणालियों के व्यापक उपयोग के संबंध में आधुनिक कंप्यूटिंग विज्ञान में व्यापक रूप से उपयोग किया जाता है। सीएसपी के सबसे करीबी और सबसे अधिक व्यावहारिक व्यावहारिक अनुप्रयोग, मुझे लगता है, निम्नलिखित प्रोग्रामिंग भाषाएं होंगी:

• Erlang
• जाओ
• लीम्बो

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

परिचय

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

• सिक्का - एक सिक्का रिसीवर में एक सिक्का कम
• चोक - चॉकलेट प्राप्त करना

दो चॉकलेट बेचने वाली अधिक जटिल मशीन के मामले में: एक छोटा (एक रूबल के लिए) और एक बड़ा (दो के लिए), हमें निम्नलिखित क्रियाएं मिलती हैं:

• in1p - एक रूबल कम करना
• in2p - दो रूबल कम करना
• छोटा - थोड़ा चॉकलेट बार
• बड़ा - एक बड़ा चॉकलेट बार हो रहा है
• out1p - परिवर्तन द्वारा एक रूबल प्राप्त करना

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

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

प्रत्येक घटना परमाणु है, अर्थात तुरंत होता है। समय में चलने वाली घटना का वर्णन करने के लिए, घटनाओं की एक जोड़ी का उपयोग किया जाता है: प्रारंभिक और अंतिम। उनके बीच के अंतराल में, अन्य घटनाएं भी हो सकती हैं, जिसका अर्थ है कि समय में जारी रहने वाली घटनाएं ओवरलैप हो सकती हैं।

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

अस्थायी मुद्दे की अनदेखी करने का परिणाम यह है कि हम घटनाओं की एकरूपता पर विचार करने से इनकार कर देते हैं। ऐसे मामलों में जहां यह महत्वपूर्ण है (उदाहरण के लिए, सिंक्रनाइज़ेशन), हम इन घटनाओं को एक के रूप में प्रस्तुत करते हैं।

वर्णमाला का चयन करते समय, हमें बाहर ( सिक्का ) से होने वाली घटनाओं और ऑब्जेक्ट द्वारा उत्पादित घटनाओं ( चोक ) को अलग करने की आवश्यकता नहीं होती है।

हम एक वस्तु के व्यवहार का वर्णन करने के लिए शब्द प्रक्रिया का परिचय देते हैं, जिसे वस्तु की वर्णमाला से सीमित संख्या में घटनाओं के दृष्टिकोण से वर्णित किया जा सकता है। हम निम्नलिखित समझौते का पालन करेंगे:

1. एक छोटे अक्षर से शुरू होने वाले शब्द व्यक्तिगत घटनाओं को इंगित करते हैं, उदाहरण के लिए: सिक्का , चोक , इन 2 पी , आउट 1 पी , साथ ही व्यक्तिगत पत्र ए , बी , सी , आदि।
2. उदाहरण के लिए अपरकेस शब्द प्रक्रिया दर्शाते हैं:
   
   • वीएमएस - एक साधारण ट्रेडिंग मशीन
   • VMC - एक अधिक जटिल ट्रेडिंग मशीन
   इसके अलावा, अक्षर P , Q , R (कानूनों में प्रयुक्त) कुछ मनमानी प्रक्रियाओं को दर्शाता है
   
3. अक्षर x , y , z घटना नामित चर हैं
4. पत्र ए , बी , सी कई घटनाओं को दर्शाते हैं।
5. अक्षर X , Y प्रक्रिया चर हैं
6. प्रक्रिया वर्णमाला पी को αP (अल्फा पी) के रूप में दर्शाया जाता है, उदाहरण के लिए:
   
   • αVMS = { सिक्का , चोक }
   • αVM = { in1p , in2p , small , large , out1p }

एक वर्णमाला ए के साथ एक प्रक्रिया जो कभी भी ए में किसी भी कार्यक्रम में भाग नहीं लेती है उसे स्टॉप _{ए के} रूप में नामित किया जाता है _।

उपसर्ग

चलो एक घटना है, और पी एक प्रक्रिया है, तो:

( x → P ) (उच्चारण "x तो P")

एक वस्तु का वर्णन करता है जो पहले एक घटना x को आग लगाती है, और फिर P की तरह व्यवहार करती है परिभाषा के अनुसार, प्रक्रिया P में समान वर्णमाला है ( x → P ), निश्चित रूप से, इस प्रविष्टि का उपयोग केवल तभी किया जा सकता है जब x इस वर्णमाला से संबंधित हो, जिसे औपचारिक रूप से लिखा जा सकता है:

α ( x → P ) = α P स्थिति के तहत x। α P

उदाहरण:

1. एक चॉकलेट बार की वापसी के बाद टूटने वाली एक साधारण ट्रेडिंग मशीन:
   

   (सिक्का → STOP _αVMS )

2. दो लोगों की सेवा करने के बाद एक साधारण ट्रेडिंग मशीन टूट गई:
   

   (सिक्का → (choc → (सिक्का → (choc → STOP _αVMS ))))

   बहुत शुरुआत में, मशीन एक सिक्का स्वीकार कर सकती है, लेकिन एक चॉकलेट बार नहीं दे सकती है, लेकिन एक सिक्का डाले जाने के बाद, मशीन अब सिक्कों को तब तक स्वीकार नहीं करेगी जब तक कि चॉकलेट बार को हटा नहीं दिया जाता।
3. पॉइंटर केवल भूलभुलैया के साथ और सफेद कोशिकाओं के साथ दाईं ओर जा सकता है:
   

   αCTR = {अप, राइट}
   CTR = (राइट → अप → राइट → राइट → STOP _αCTR )

तीसरे उदाहरण में, हमने समझौते को स्वीकार करके कोष्ठकों को छोड़ कर इस धारणा को सरल किया कि → दाईं ओर सहयोगी है।

ध्यान दें कि निम्नलिखित प्रविष्टियाँ वाक्यविन्यास गलत हैं:

पी → क्यू
x → y

→ बाईं ओर घटना को स्वीकार करना आवश्यक है। उपसर्गों की श्रृंखला एक प्रक्रिया के साथ समाप्त होनी चाहिए। सही प्रविष्टि का एक उदाहरण समकक्ष प्रविष्टियाँ होंगी:

x → (y → STOP)
x → y → STOP

इस प्रकार, हम स्पष्ट रूप से एक घटना और एक या कई घटनाओं में भाग लेने वाली प्रक्रिया के बीच अंतर करते हैं।

प्रत्यावर्तन

उपसर्ग प्रविष्टि हमें अंतिम प्रक्रिया के व्यवहार का वर्णन करने की अनुमति देती है, लेकिन एक वेंडिंग मशीन के मामले में इसकी सैकड़ों और हजारों बिक्री के साथ अपने पूरे जीवन का वर्णन करना थकाऊ होगा। इस प्रकार, हमें दोहराए जाने वाले कार्यों का वर्णन करने का एक तरीका चाहिए, जो हमें अंतहीन जीवित प्रक्रियाओं का वर्णन करने के लिए संपार्श्विक अवसर देगा।

सामान्य टिकिंग घड़ी पर विचार करें, जिस पर विचार करते हुए हम केवल इसके टिक्स में रुचि लेंगे, फिर:

αCLOCK = {टिक}

घड़ी के टिक जाने के बाद वे उसी घड़ी रहेंगे, तब हम कह सकते हैं कि टिक के बाद वस्तु एक घड़ी है, एक घड़ी है:

लॉक = (टिक → लॉक)

दाईं ओर से CLOCK को प्रतिस्थापित करके हम प्राप्त करेंगे:

  घड़ी
     = (टिक → CLOCK) [प्रारंभिक समीकरण]
     = (टिक → (टिक → लॉक)) [एक खोज]
     = (टिक → (टिक → → टिक))) [दो क्रमपरिवर्तन] 

इस प्रकार, घड़ी के व्यवहार को दोहराए जाने वाले टिक्स की अनंत संख्या के रूप में वर्णित किया जा सकता है:

टिक → टिक → टिक → · ·

अपने आप को संदर्भित करने का यह तरीका केवल तभी काम करेगा जब समीकरण के दाईं ओर एक उपसर्ग के साथ शुरू होने वाली अभिव्यक्ति हो, उदाहरण के लिए, समीकरण:

एक्स = एक्स

यह वास्तव में कुछ भी निर्धारित नहीं करता है, क्योंकि कोई भी प्रक्रिया इससे मेल खाती है। हम आगे उपसर्ग "संरक्षित" के साथ शुरू होने वाली प्रक्रिया के विवरण को कॉल करेंगे। इस प्रकार, यदि F (X) एक संरक्षित अभिव्यक्ति है जिसमें प्रक्रिया नाम X और αX = A है, तो समीकरण:

X = F (X)

वर्णमाला ए के साथ एक अनूठा समाधान है। इस समीकरण को लिखना अक्सर सुविधाजनक होता है:

μX: A • F (X)

जहाँ X एक स्थानीय चर है जिसे बदला जा सकता है:

μX: A • F (X) = μY: A • F (Y)

इन अभिव्यक्तियों की समानता इस तथ्य से होती है कि समीकरण:

X = F (X)
Y = F (Y)

एक ही समाधान है।

भविष्य में, हम प्रक्रिया को स्थापित करने के दोनों तरीकों का उपयोग करेंगे: समीकरण के माध्यम से और μ के माध्यम से। दूसरे मामले में, हम अक्सर वर्णमाला ए के उल्लेख को छोड़ देंगे, क्योंकि यह संदर्भ से स्पष्ट होगा।

उदाहरण:

1. अनंत घड़ी:
   

   लॉक = μX: {टिक} • (टिक → X)

2. एक अनंत चॉकलेट बेचने वाली एक वेंडिंग मशीन:
   

   VMS = μX: (सिक्का → (choc → X))

   जैसा कि ऊपर बताया गया है, यह प्रविष्टि एक अधिक औपचारिक प्रविष्टि का छोटा संस्करण है:
   

   VMS = μX: {सिक्का, चॉक} • (सिक्का → (choc → X))

3. पांच रूबल का सिक्का विनिमय मशीन:
   

   αCH5A = {in5p, out2p, out1p}
   CH5A = (in5p → out2p → out1p → out2p → CH5A)

4. उसी वर्णमाला के साथ एक विनिमय मशीन का दूसरा संस्करण:
   

   CH5A = (in5p → out1p → out1p → out1p → out2p → CH5A)

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

निष्कर्ष

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