Input/output automaton
ان پٹ/آؤٹ پٹ آٹومیٹا ایک رسمی ماڈل فراہم کرتا ہے، جو ایک غیر متزلزل ہم آہنگی نظام کی زیادہ تر اقسام کو بیان کرنے میں لاگو ہوتا ہے۔ اپنے طور پر، I/O آٹومیٹن ماڈل ایک بہت ہی بنیادی ڈھانچہ پر مشتمل ہے جو اسے مختلف قسم کے تقسیم شدہ نظاموں کا نمونہ بنانے کے قابل بناتا ہے۔ غیر متغیر نظاموں کی مخصوص اقسام کو بیان کرنے کے لیے، اس بنیادی ماڈل میں اضافی ڈھانچہ شامل کیا جانا چاہیے۔ ماڈل نظام کے اجزاء جیسے عمل اور میسج چینلز کے بارے میں وضاحت اور استدلال کے لیے ایک واضح طریقہ پیش کرتا ہے جو ایک دوسرے کے ساتھ تعامل کرتے ہیں، صوابدیدی رشتہ دار رفتار پر کام کرتے ہیں۔ I/O آٹومیٹا کو سب سے پہلے نینسی اے لنچ اور مارک آر ٹٹل نے "ہائیرارکیکل کریکٹنیس پروفز فار ڈسٹری بیوٹڈ الگورتھم"، 1987 میں متعارف کرایا تھا۔ ایک I/O آٹومیٹن ایک تقسیم شدہ نظام کے جزو کا نمونہ بناتا ہے جو نظام کے دیگر اجزاء کے ساتھ تعامل کر سکتا ہے۔ یہ ایک سادہ قسم کی ریاستی مشین ہے جس میں منتقلی نامی اعمال سے وابستہ ہوتی ہے۔ اعمال کی تین قسمیں ہیں: ان پٹ، آؤٹ پٹ اور اندرونی اعمال۔ آٹومیٹن اپنے ان پٹ اور آؤٹ پٹ اعمال کو اپنے ماحول کے ساتھ بات چیت کرنے کے لیے استعمال کرتا ہے، جبکہ اندرونی اعمال صرف آٹومیٹن کو ہی نظر آتے ہیں۔ اندرونی اور آؤٹ پٹ کارروائیوں کے برعکس جو آٹومیٹن کے ذریعے منتخب اور انجام دی جاتی ہیں، ان پٹ کارروائیاں-جو محض ماحول سے آتی ہیں-آٹومیٹن کے کنٹرول میں نہیں ہوتیں۔ I/O آٹومیٹا کی مثالیں تقسیم شدہ نظام کے انفرادی اجزاء کو ماڈل کرنے کے لیے استعمال کی جا سکتی ہیں، جیسے کہ ایک عمل، پیغام بھیجنے والے نظام میں ایک پیغام چینل، یا مشترکہ میموری سسٹم میں مشترکہ ڈیٹا ڈھانچہ۔ عمل I/O آٹومیٹن شکل 1 ایک غیر متغیر پیغام گزرنے والے تقسیم شدہ نظام میں ایک عمل کے لیے I/O آٹومیٹن کی ایک مثال دکھاتی ہے۔ اس ترتیب میں، پروسیس پائی میسج پاسنگ سسٹم کا استعمال کرتے ہوئے دوسرے عمل کے ساتھ بات چیت کرتا ہے۔ اس کے آؤٹ پٹ ایکشن بھیجیں (m) i، j کی شکل کے ہوتے ہیں، جو Pj پر کارروائی کرنے کے لیے مواد m کے ساتھ پیغام بھیجنے والے عمل Pi کی نمائندگی کرتا ہے۔ ان پٹ ایکشن وصول (m) k، i فارم کے ہوتے ہیں، جو کہ عمل Pk سے عمل Pi کے ذریعے مواد m کے ساتھ پیغام کی وصولی کی نمائندگی کرتے ہیں۔ (پائی کے اندرونی اعمال، جو اس الگورتھم سے مطابقت رکھتے ہیں کہ عمل چل رہا ہے، نہیں دکھائے گئے ہیں۔) ایف آئی ایف او میسج چینل ایک میسج چینل کو آئی/او آٹومیٹن کے ذریعے بھی بنایا جا سکتا ہے۔ شکل 2 ایک عام یک طرفہ ایف آئی ایف او چینل آٹومیٹن کی وضاحت کرتا ہے، جس کا نام سی آئی، جے ہے۔ اس میں بھیج (m) i، j فارم کے ان پٹ ایکشن ہوتے ہیں، اور وصول (m) i، j فارم کے آؤٹ پٹ ایکشن ہوتے ہیں۔ ہر پیغام m میں 0 یا 1 (m bul {0,1}) ہو سکتا ہے۔ آٹومیٹن کی حالت ان تمام پیغامات کی ففو قطار کو محفوظ کرتی ہے جو بھیجے گئے ہیں لیکن ابھی تک موصول نہیں ہوئے ہیں۔ ایک عام تقسیم شدہ نظام میں جہاں پروسیس آٹومیٹا اور کمیونیکیشن چینل آٹومیٹا دونوں موجود ہوتے ہیں، وہ اس طرح سے بنائے جاتے ہیں کہ ایک آٹومیٹن کے آؤٹ پٹ ایکشن دوسرے آٹومیٹا کے یکساں نام والے ان پٹ ایکشن کے ساتھ مل جائیں اور ان پر عمل درآمد کیا جائے۔ مثال کے طور پر، دو عمل، پائی اور پی جے پر مشتمل ایک نظام پر غور کریں، اور پی جے پر عمل کرنے کے لیے پروسیس پائی سے ایک مواصلاتی چینل سی آئی، جے پر غور کریں۔ اس ترتیب میں، پروسیس پائی آؤٹ پٹ ایکشن بھیجتا ہے (m) i، j، اگر اور صرف اس صورت میں جب چینل Ci، j بھی اپنے بھیجنے (m) i، j ان پٹ ایکشن کو انجام دیتا ہے۔ ایٹمک ریڈ/رائٹ رجسٹر شکل 3 دو عملوں، P1 اور P2 کے ساتھ مشترکہ میموری سسٹم میں ایٹمک ریڈ/رائٹ رجسٹر I/O آٹومیٹن کی وضاحت کرتا ہے۔ رجسٹر میں ذخیرہ شدہ ویلیو V انٹیجر (V bul Z) کی قسم کی ہوتی ہے۔ آٹومیٹن کی حالت اس قدر کو محفوظ کرتی ہے۔ ان پٹ ایکشن رائٹی (V) پر مشتمل ہوتا ہے، جو پروسیس پائی کی نمائندگی کرتا ہے جو رجسٹر پر ویلیو V لکھنے کی درخواست کرتا ہے (جہاں i ω {1,2} اور V ω Z)، اور ریڈی، جو ایک پروسیس پائی سے مطابقت رکھتا ہے جو اس وقت رجسٹر میں محفوظ ویلیو کو پڑھنے کی درخواست کرتا ہے۔ آؤٹ پٹ ایکشن اکی کا استعمال پروسیس پائی کو یہ بتانے کے لیے کیا جاتا ہے کہ تحریری درخواست کامیابی سے مکمل ہو چکی ہے۔ آؤٹ پٹ ایکشن Vi اس ویلیو V کی نمائندگی کرتا ہے جو پروسیس پائی کے ذریعے پڑھنے کی درخواست کے جواب کے طور پر واپس کی جا رہی ہے۔ آٹومیٹن میں اندرونی حرکتیں بھی شامل ہیں (V) لکھیں، جو رجسٹر پر ویلیو V لکھتا ہے (آٹومیٹن کی حالت کو اپ ڈیٹ کرکے)، اور (V) پڑھیں انجام دیں، جو ریاست میں ذخیرہ شدہ ویلیو V کو پڑھنے کے لیے استعمال ہوتا ہے۔ (یہ اندرونی حرکتیں شکل 3 میں نہیں دکھائی گئی ہیں۔) ایک I/O آٹومیٹن A، یا محض ایک آٹومیٹن، پانچ اجزاء پر مشتمل ہوتا ہے: سگ (A) میں کہا گیا ہے کہ (A) اسٹارٹ (A) ٹرانس (A) ٹاسک (A) یہ پانچ اجزاء ذیل میں بیان کیے گئے ہیں۔ دستخط I/O آٹومیٹن A کو باضابطہ بنانے کا ابتدائی مرحلہ اس کے دستخط، سگ (A) کی تعریف ہے۔ ایک دستخطی S I/O آٹومیٹن کے اعمال کو تین جداگانہ کارروائیوں کا استعمال کرتے ہوئے بیان کرتا ہے: ان (S): ان پٹ ایکشن، آؤٹ (S): آؤٹ پٹ ایکشن، اور int (S): اندرونی ایکشن۔ ان پٹ، آؤٹ پٹ اور اندرونی اعمال کی مذکورہ بالا رسمی شکل کی بنیاد پر، درج ذیل اشیاء کی وضاحت کرنا ممکن ہے۔ ایکسٹ (ایس): بیرونی اعمال، جن کی تعریف (ایس) ≤ آؤٹ (ایس) لوکل (ایس) میں کی گئی ہے: مقامی طور پر کنٹرول شدہ اعمال، جن کی تعریف آؤٹ (ایس) ≤ انٹ (ایس) ایکسٹسگ (ایس) کے طور پر کی گئی ہے: بیرونی دستخط، جس کی تعریف (ایس) میں، آؤٹ (ایس) کے طور پر کی گئی ہے، ایکٹ (ایس) کو دستخط ایس کے تمام اعمال کے سیٹ کے طور پر بیان کیا گیا ہے۔ ریاستیں آٹومیٹن اے کی ریاستوں کا مجموعہ، ظاہر شدہ ریاستیں (اے)، محدود ہونے کی ضرورت نہیں ہے۔ یہ محدود آٹومیٹا کے معمول کے تصور کی ایک اہم عمومی شکل ہے، کیونکہ یہ غیر محدود ڈیٹا ڈھانچے جیسے کاؤنٹرز اور غیر محدود لمبائی کی قطاروں کے ساتھ ماڈلنگ سسٹم کو قابل بناتا ہے۔ ابتدائی ریاستوں کا مجموعہ (جسے ابتدائی ریاستیں بھی کہا جاتا ہے) ریاستوں کا ایک غیر خالی ذیلی مجموعہ ہے۔ متعدد اسٹارٹ اسٹیٹس کی اجازت ہے تاکہ کچھ ان پٹ معلومات کو اسٹارٹ اسٹیٹس میں شامل کیا جا سکے۔ ٹرانزیشن ریلیشن آٹومیٹن اے کے اسٹیٹ ٹرانزیشن ریلیشن کو ٹرانس (اے) اسٹیٹس (اے) × ایکٹ (سگ (اے)) × اسٹیٹس (اے) سے ظاہر کیا جاتا ہے۔ یہ اس خاصیت کو مطمئن کرتا ہے کہ "ہر حالت s اور ہر ان پٹ ایکشن π کے لیے، ایک منتقلی (s، π، s ') bul ٹرانس (A) ہے"۔ ایک منتقلی، جسے I/O آٹومیٹن A کے قدم کے طور پر بھی جانا جاتا ہے، کی تعریف ٹرانس (A) کے عنصر (s، π، s ') کے طور پر کی جاتی ہے۔ ان پٹ ٹرانزیشن سے مراد ایک ٹرانزیشن (s، π، s ') ہے جب π ایک ان پٹ ایکشن ہے، آؤٹ پٹ ٹرانزیشن ایک ٹرانزیشن (s، π، s') کی نشاندہی کرتی ہے جب π ایک آؤٹ پٹ ایکشن ہے اور اسی طرح۔ کسی بھی حالت s اور عمل π کے لیے، اگر I/O آٹومیٹن A میں فارم (s، π، s ') کی کچھ منتقلی ہے، تو کہا جاتا ہے کہ π کو s میں فعال کیا جاتا ہے۔ I/O آٹومیٹا کو ان پٹ فعال کے طور پر بیان کیا جاتا ہے کیونکہ ہر ریاست میں تمام ان پٹ اعمال کو فعال کرنے کی ضرورت ہوتی ہے۔ ایک پرسکون حالت s کو ایک ایسی حالت کے طور پر بیان کیا جاتا ہے جہاں صرف ان پٹ ایکشن فعال ہوتے ہیں۔ I/O آٹومیٹن A کا پانچواں جزو، ٹاسک (A)، ایک ٹاسک پارٹیشن ہے، جس کی تعریف A کے مقامی طور پر کنٹرول شدہ اعمال پر مساوات کے تعلق کے طور پر کی گئی ہے، جس میں زیادہ سے زیادہ قابل شمار مساوات کی کلاسیں ہیں۔ غیر رسمی طور پر، ٹاسک پارٹیشن ٹاسک (اے)، اے کے اندر "ٹاسک"، یا "تھریڈز آف کنٹرول" کی تجریدی وضاحت کی نمائندگی کرتا ہے۔ یہ تقسیم آٹومیٹن کے نفاذ پر منصفانہ شرائط کی وضاحت کے لیے استعمال ہوتی ہے۔ ان شرائط کے لیے آٹومیٹن کو اپنے عمل کے دوران اپنے ہر کام کو منصفانہ موڑ دینا جاری رکھنا پڑتا ہے۔ یہ خاص طور پر اس وقت مددگار ہوتا ہے جب نظام کے کسی جزو کی ماڈلنگ کی جائے جو متعدد کام انجام دیتا ہے۔ مثال کے طور پر، ایک جزو جو جاری الگورتھم میں حصہ لیتا ہے جبکہ وقتا فوقتا اپنے ماحول میں صورتحال کی معلومات کی اطلاع دیتا ہے اس کے دو کام ہوں گے۔ پارٹیشن اس وقت بھی مفید ہوتا ہے جب کئی آٹومیٹا بنائے جاتے ہیں (ایک بڑا سسٹم آٹومیٹن تیار کرنے کے لیے) جب یہ واضح کیا جاتا ہے کہ کمپوزیشن میں موجود تمام آٹومیٹا کمپوزڈ سسٹم میں اقدامات کرتے رہتے ہیں۔ مثال: چینل I/O آٹومیٹن کی رسمی تعریف جیسا کہ اوپر بیان کیا گیا ہے، Ci، j I/O آٹومیٹن کی ایک مثال ہے جو Pj پر عمل کرنے کے لیے عمل Pi سے ایک یک طرفہ FIFO چینل کی نمائندگی کرتا ہے۔ فرض کریں کہ m ایک بائنری پیغام ہے: m bul {0,1}۔ آٹومیٹن سی آئی، جے کو باضابطہ طور پر مندرجہ ذیل طور پر بیان کیا جا سکتا ہے۔ دستخط: سگ (Ci, j) اس بات کی وضاحت کرتا ہے کہ آٹومیٹن میں دو قسم کے اعمال ہوتے ہیں: (Ci, j) کا ان پٹ ایکشن بھیجنے (m) i, j کی شکل کا ہوتا ہے، جہاں m bul {0,1} ہوتا ہے۔ (Ci، j) کا آؤٹ پٹ ایکشن وصول (m) i، j کی شکل کا ہوتا ہے، جہاں m bul {0,1} ہوتا ہے۔ بدیہی طور پر، بھیجنے والا عمل (m) i، j اس بات کی نشاندہی کرتا ہے کہ ایک پیغام m چینل میں داخل ہوا ہے جب اسے پروسیس Pi کے ذریعے بھیجا جاتا ہے اور وصول کرنے والا عمل (m) i، j اس بات کی نشاندہی کرتا ہے کہ ایک پیغام m چینل سے نکل گیا ہے جب اسے Pj پر کارروائی کرنے کے لیے پہنچایا جاتا ہے۔ ریاستیں: ریاستیں (Ci, j) عناصر m ω {0,1} کے تمام محدود ترتیبات کا مجموعہ ہے۔ بدیہی طور پر، ریاست اس وقت بھیجنے والے کے راستے میں پیغامات کی ترتیب کی نمائندگی کرتی ہے، پی آئی پر عمل کرتی ہے، وصول کنندہ کو، پی جے پر عمل کرتی ہے، اسی ترتیب میں جو انہیں بھیجا گیا تھا۔ اسٹارٹ (Ci، j)، جو قطار کی ابتدائی حالتوں کی نمائندگی کرتا ہے، صرف خالی ترتیب پر مشتمل ہوتا ہے۔ ٹرانزیشن ٹرانزیشن ریلیشن کو پری کنڈیشن ایفیکٹ سٹائل میں بنایا جا سکتا ہے، جہاں تمام ٹرانزیشنز جن میں ہر مخصوص قسم کی کارروائی شامل ہوتی ہے، کو کوڈ کے ایک ٹکڑے میں گروپ کیا جاتا ہے۔ اس کوڈ میں، وہ شرائط جنہیں کسی عمل کی اجازت دینے سے پہلے پورا کرنا ضروری ہے، کو پری اسٹیٹ s پر پیش گوئی کے طور پر رسمی شکل دی جاتی ہے، جو عمل ہونے سے پہلے کی حالت ہے۔ عمل پر عمل درآمد کے نتیجے میں ریاست میں ہونے والی تبدیلیوں کو ایک سادہ پروگرام کی شکل میں کوڈ کیا جاتا ہے۔ یہ پروگرام ایک واحد منتقلی کے طور پر غیر منقسم طور پر انجام دیا جاتا ہے۔ اگر اس پروگرام کا اطلاق ریاست پر ہوتا ہے، تو نئی ریاست کے نتائج سامنے آتے ہیں۔ سی آئی، جے کے ٹرانزیشنز کو اس طرح بیان کیا گیا ہے: بھیجنے کے لیے (ایم) آئی، جے: پری کنڈیشن: کوئی اثر نہیں: وصول کرنے کے لیے (ایم) آئی، جے: پری کنڈیشن: ایم ریاست میں ذخیرہ شدہ ترتیب کا پہلا عنصر ہے (جہاں ایم ω {1,0}) اثر: حالت میں ذخیرہ شدہ ترتیب کے پہلے عنصر کو بدیہی طور پر ہٹا دیں، بھیجنے کے عمل کو کسی بھی وقت انجام دیا جا سکتا ہے۔ یہ چی چینل میں پیغامات کی قطار کے آخر میں پیغام ایم کے اضافے کا سبب بنتا ہے۔ وصول عمل قطار کے پہلے عنصر کو ہٹا دیتا ہے اور واپس کرتا ہے۔ ٹاسک ٹاسک (Ci, j)، ایک ٹاسک پارٹیشن کی نمائندگی کرتا ہے جو فارم کے تمام اعمال کو ایک ہی کام میں جمع کرتا ہے۔ بدیہی طور پر، پی جے پر کارروائی کرنے کے لیے پیغامات کو منتقل کرنا ایک واحد کام سمجھا جاتا ہے۔ {وصول کریں (m) i، j: m bul {0,1}}۔ ایک آٹومیٹن کی دوڑ میں، ایک تار تیار کیا جاتا ہے جو آٹومیٹن ماڈل کے جزو کے رویے کو بیان کرتا ہے۔ "I/O آٹومیٹن A کا ایک پھانسی کا ٹکڑا یا تو ایک محدود ترتیب، s0، π1، s1، π2،.، πr، sr، یا ایک لامحدود ترتیب، s0، π1، s1، π2،.، πr، sr،.، متبادل حالتوں اور A کے اعمال کا ایسا ہے کہ (sk، πk + 1، sk + 1) ہر k ≤0 کے لیے A کی منتقلی ہے۔" ایک محدود ترتیب کو ایک حالت کے ساتھ ختم ہونا چاہیے۔ پھانسی کو پھانسی کے ٹکڑے کے طور پر بیان کیا جاتا ہے جو اسٹارٹ اسٹیٹ سے شروع ہوتا ہے۔ A کی پھانسی کے سیٹ کی نمائندگی ایگزیکٹوز (A) کے ذریعے کی جاتی ہے۔ I/O آٹومیٹن A میں قابل رسائی حالت A کے محدود نفاذ کی حتمی حالت ہے۔ فرض کریں کہ α حالت sf کے ساتھ ختم ہونے والا A کا ایک محدود عمل کا ٹکڑا ہے۔ مزید فرض کریں کہ α 'A کا کوئی بھی پھانسی کا ٹکڑا ہے جو sf سے شروع ہوتا ہے، α کی آخری حالت۔ اس صورت میں، α اور α 'کو جوڑ کر پیدا ہونے والی ترتیب، اور sf کے ڈپلیکیٹ واقع کو ختم کرتے ہوئے، α کی آخری حالت، کی نمائندگی α. α' کے ذریعے کی جاتی ہے۔ یہ ترتیب I/O آٹومیٹن A کا ایک پھانسی کا ٹکڑا بھی ہے۔ ٹریس ایک I/O آٹومیٹن A کا سراغ بیرونی اعمال کا سلسلہ ہے جو A کے کچھ عمل α میں ہوتا ہے۔ A کے تمام نشانات کے سیٹ کو نشانات (A) کے طور پر پیش کیا جاتا ہے۔ مثال: تین سزائے موت a، b اور c آٹومیٹن Ci، j کی تین سزائے موت ہیں جو چینل I/O آٹومیٹن کی رسمی تعریف میں بیان کی گئی ہیں (جہاں پیغام m bul {0,1})۔ اس مثال میں، بریکٹ میں قطار میں پیغامات کی ترتیب ڈال کر ریاستوں کی نشاندہی کی جاتی ہے۔ خالی ترتیب کی نمائندگی λ سے کی جاتی ہے۔ (a) [λ]، بھیجیں (1) i، j، [1]، وصول کریں (1) i، j، [λ]، بھیجیں (0) i، j، [0]، وصول کریں (0) i، j، [λ] (b) [λ]، بھیجیں (1) i، j، [λ]، وصول کریں (1) i، j، [λ]، بھیجیں (0) i، j، [0] (c) [λ]، بھیجیں (1) i، j، [1]، بھیجیں (1) i، j، [11]، بھیجیں (1) i، j، [11]، بھیجیں (0) i، j، [110]۔ آٹومیٹا کمپوزیشن آپریشن پر آپریشن تشکیل کرنا ممکن ہے۔ اس صورت میں، ہر جزو آٹومیٹا میں ایک ہی نام والے اعمال کی شناخت ایک ساتھ کی جاتی ہے۔ لہذا، جب کوئی جزو آٹومیٹا ایک قدم اٹھاتا ہے جس میں ایک عمل π شامل ہوتا ہے، تو دوسرے تمام اجزاء آٹومیٹا بھی اپنے دستخطوں میں π کے ساتھ اس عمل کو انجام دیتے ہیں۔ آٹومیٹا اے اور اے کی ساخت کی اجازت کے لیے درج ذیل شرائط کا خاکہ پیش کیا گیا ہے: اے کے اندرونی اعمال کو اے کے اعمال سے الگ ہونا چاہیے۔ یہ A 'میں ایک قدم کی کارکردگی کو روکتا ہے جب A کے اندرونی اعمال-اسی نام کے ساتھ جو A' کے اعمال ہیں-انجام دیے جاتے ہیں۔ A اور A 'کے آؤٹ پٹ ایکشن جداگانہ ہونے چاہئیں۔ یہ شرط اس بات کو یقینی بناتی ہے کہ صرف ایک جزو آٹومیٹن آؤٹ پٹ ایکشن کی کارکردگی کو کنٹرول کرتا ہے۔ اگر ساخت آٹومیٹا کے شمار کے لحاظ سے لامحدود مجموعہ سے بنائی گئی ہے، تو ایک اضافی رکاوٹ ہے: ہر عمل کو صرف محدود طور پر بہت سے جزو آٹومیٹا کا عمل ہونا ضروری ہے۔ آٹومیٹا کی لامحدود ساخت منطقی نظاموں کے ماڈلنگ کی اجازت دیتی ہے جو بہت سے منطقی اجزاء سے بنائے جا سکتے ہیں۔ منطقی نظام اکثر ایسے جسمانی نظام پر نافذ کیا جاتا ہے جس میں کم اجزاء ہوتے ہیں۔ مثال: کمپوزیشن فگر 4 میں دو عملوں، پائی اور پی جے اور ایک ایف آئی ایف او میسج چینل سی آئی، جے کی ساخت کو دکھایا گیا ہے، جو ایک آٹومیٹن کے آؤٹ پٹ ایکشن کو دوسرے آٹومیٹا کے یکساں نام والے ان پٹ ایکشن کے ساتھ ملاتا ہے۔ اس طرح، عمل پائی کے ذریعہ انجام دی جانے والی بھیجنے (m) i، j آؤٹ پٹ کا موازنہ کیا جاتا ہے اور چینل Ci، j کے ذریعہ انجام دی جانے والی بھیجنے (m) i، j ان پٹ کے ساتھ انجام دیا جاتا ہے۔ پروسیس پائی پیغام m بھیجتا ہے، جہاں m bul {1,0} چینل Ci، j کے ذریعے پروسیس Pj کو جاتا ہے۔ پروسیس پی جے پائی سے موصولہ پیغام ایم میں بٹ کو اس کے اندرونی ایکشن ریورس کا استعمال کرتے ہوئے الٹ دیتا ہے-جو تصویر میں نہیں دکھایا گیا ہے-اور پیغام کو سسٹم کے دوسرے حصوں میں آگے بھیجتا ہے۔ آپریشن کو چھپانا I/O آٹومیٹن کے آؤٹ پٹ اعمال کو "اندرونی اعمال کے طور پر دوبارہ درجہ بندی" کے ذریعے چھپانا ممکن ہے۔ اس سے انہیں نظام کے دوسرے حصوں کے ساتھ رابطے سے خارج کرنے کا اثر پڑتا ہے۔ رسمی طور پر، دستخطوں کے لیے چھپانے کی کارروائی کو مندرجہ ذیل طور پر بیان کیا گیا ہے: آئیے S ایک دستخط ہے اور φ باہر (S)۔ ہائڈ φ (S) نیا دستخط S 'ہے، جہاں (S') = میں (S) باہر (S ') = باہر (S)-φ انٹ (S') = انٹ (S) φ لہذا، "اگر A ایک آٹومیٹن ہے اور φ باہر (A)، تو ہائڈ φ (A) آٹومیٹن A 'ہے جو A سے سگ (A) کو سگ (A') = ہائڈ φ (سگ (A)) سے بدل کر حاصل کیا جاتا ہے۔ انصاف یاد رکھیں کہ ٹاسک پارٹیشن کو I/O آٹومیٹن کے مقامی طور پر کنٹرول شدہ اعمال پر مساوات کے تعلق کے طور پر بیان کیا گیا ہے، جس میں زیادہ سے زیادہ گنتی میں بہت سی مساوات کی کلاسیں ہوتی ہیں۔ اس ترتیب میں، انصاف پسندی کی تعریف ہر کام کو مسلسل انجام دینے کا موقع فراہم کرنے کے طور پر کی جا سکتی ہے۔ I/O آٹومیٹن A میں، C کو کاموں کی ایک کلاس (A) کی نمائندگی کرنے دیں۔ رسمی طور پر، A کا ایک عمل کا ٹکڑا α منصفانہ سمجھا جاتا ہے اگر درج ذیل معیار ہر کلاس C کے لیے ہو: "اگر α محدود ہے، تو C کو α کی حتمی حالت میں فعال نہیں کیا جاتا ہے۔" "اگر α لامحدود ہے، تو α یا تو C سے لامحدود طور پر بہت سے واقعات پر مشتمل ہے یا ان ریاستوں کے لامحدود طور پر بہت سے واقعات پر مشتمل ہے جن میں C فعال نہیں ہے۔" ایک واقعہ کی تعریف "ایک ترتیب میں کسی عمل کی موجودگی، مثال کے طور پر، ایک عمل یا ایک سراغ" کے طور پر کی گئی ہے۔ انصاف پسندی کی تعریف کی بنیاد پر، "لامحدود کثرت سے"، ہر کام (یا مساوات کلاس سی) کو ایک عمل انجام دینے کا موقع ملتا ہے۔ جب کسی ٹاسک (یا مساوات کلاس) C کو کوئی عمل انجام دینے کا موقع ملتا ہے، تو دو معاملات ممکن ہوتے ہیں: C میں ایک عمل موجودہ حالت میں فعال ہوتا ہے اور انجام دیا جا سکتا ہے، یا C میں سے کوئی بھی عمل موجودہ حالت میں فعال نہیں ہوتا ہے اور اس لیے انجام نہیں دیا جا سکتا۔ اس طرح، حتمی حالت ایس ایف کے ساتھ ایک محدود منصفانہ عمل کو ایک عمل کے طور پر بیان کیا جا سکتا ہے جہاں آٹومیٹن مسلسل راؤنڈ رابن انداز میں تمام کاموں کو موڑ دیتا ہے، لیکن کوئی عمل انجام نہیں دیا جاتا ہے کیونکہ ایس ایف میں کوئی بھی فعال نہیں ہوتا ہے۔ I/O آٹومیٹن A کی منصفانہ پھانسی کے سیٹ کی نمائندگی فیریکسکس (A) کے ذریعے کی جاتی ہے۔ β کو A کی منصفانہ کارکردگی کا سراغ ہونے دیں۔ پھر β A کا منصفانہ سراغ ہے۔ اے کے طے شدہ منصفانہ نشانات کی نمائندگی فیئر ٹریسس (اے) کے ذریعے کی جاتی ہے۔ پھانسی کی مثال میں، پھانسی (a) منصفانہ ہے، کیونکہ اس کی حتمی حالت میں کوئی وصول کارروائی فعال نہیں ہے۔ پھانسی (ب) محدود ہے، پھر بھی وصول کرنے والے عمل کو اس کی آخری حالت میں فعال کیا جاتا ہے۔ لہذا، پھانسی (ب) منصفانہ نہیں ہے۔ پھانسی (سی) لامحدود ہے، موصولہ واقعات پر مشتمل نہیں ہے، اور پہلے مرحلے کے بعد تمام نکات پر، وصول شدہ اعمال فعال ہیں۔ اس لیے یہ منصفانہ پھانسی نہیں ہے۔ انصاف پسندی کی تعریف کی ایک اہم خاصیت ہے: "کسی ساخت کی منصفانہ پھانسی اجزاء کی منصفانہ پھانسی کی ساخت ہے: یعنی منصفانہ (Πi AI) = Πi منصفانہ (AI)۔ خصوصیات اور ثبوت کے طریقے I/O آٹومیٹا غیر متغیر نظاموں کی درست وضاحت فراہم کرتے ہیں۔ ان کا استعمال "نظام کیا کر سکتے ہیں" کے بارے میں "درست دعووں" کو باقاعدہ بنانے اور ثابت کرنے کے لیے بھی کیا جاتا ہے۔ اس حصے میں کئی اہم اقسام کی خصوصیات بیان کی گئی ہیں۔ ان کے ساتھ ساتھ مزید خصوصیات اور ثبوت کے طریقوں کی وضاحت ڈسٹری بیوٹڈ الگورتھم میں کی گئی ہے۔ ان پٹ کو فعال کرنے والی خصوصیات ان پٹ کو فعال کرنے والی خاصیت بتاتی ہے کہ آٹومیٹن ان پٹ کارروائیوں کو ہونے سے نہیں روک سکتا۔ اس پراپرٹی کے ہونے کے دو اہم فوائد یہ ہیں: چونکہ ماڈل کو من مانی ان پٹ سے نمٹنے کے لیے ڈیزائن کیا گیا ہے، اس لیے غیر متوقع ان پٹ کو سنبھالنے میں ناکامی کی وجہ سے سسٹم کی غلطیوں کا ایک بڑا ذریعہ ختم ہو جاتا ہے۔ ان پٹ کو فعال کرنے والی خاصیت "بیرونی اعمال کے سلسلے کی بنیاد پر آٹومیٹن کے لیے بیرونی رویے کے سادہ تصورات" کا استعمال کرتی ہے۔ ماڈل میں کچھ نظریات کے ثبوت اس خاصیت کے مفروضے کے بغیر ناکام ہو سکتے ہیں۔ ٹریس کی خصوصیات جیسا کہ I/O آٹومیٹن کے اندرونی اعمال صارف کے لیے پوشیدہ ہوتے ہیں ؛ I/O آٹومیٹن ایک بلیک باکس ظاہر ہوتا ہے اور صارف محض "آٹومیٹن کی پھانسی (یا منصفانہ پھانسی) کے نشانات" دیکھتا ہے۔ I/O آٹومیٹا کی کچھ خصوصیات اور ان کے ثبوتوں کو عام طور پر "ان کے نشانات یا منصفانہ نشانات کی خصوصیات" کے طور پر رسمی شکل دی جاتی ہے۔ فرض کریں کہ P ایک ٹریس پراپرٹی ہے ؛ P کے درج ذیل اجزاء ہیں: سگ (P)، جو ایک دستخط کی نمائندگی کرتا ہے جس میں کوئی اندرونی اعمال کا سراغ نہیں ہوتا ہے (P)، جو "اعمال میں اعمال کے سلسلے (سگ (P))" کے ایک سیٹ سے مطابقت رکھتا ہے۔ یہ سیٹ لامحدود ہو سکتا ہے۔ ٹریس پراپرٹی ایک بیرونی دستخط کے ساتھ ساتھ اس انٹرفیس پر دیکھے جانے والے ترتیبات کے سیٹ (یا پراپرٹی) کو بیان کرتی ہے۔ بعض اوقات اعمال (سگ (پی)) کی نمائندگی شارٹ ہینڈ نوٹیشن ایکٹ (پی) کے ذریعے کی جاتی ہے۔ جب یہ ذکر کیا جاتا ہے کہ I/O آٹومیٹن A ایک ٹریس پراپرٹی P کو مطمئن کرتا ہے، (کم از کم) دو مختلف معانی کا ارادہ کیا جا سکتا ہے: "extsig (A) = sig (P) اور traces (A) ष् ٹریسز (P)" extsig (A) = sig (P) اور فیئر ٹریسز (A) ष् ٹریسز (P) "بدیہی طور پر، اس کا مطلب یہ ہے کہ جب A ایک بیرونی طرز عمل پیدا کرتا ہے تو اس کی اجازت پراپرٹی P کے ذریعہ دی جاتی ہے۔ تاہم، A کے لیے P کے ہر ٹریس کی نمائندگی کرنا ضروری نہیں ہے۔ چونکہ A ان پٹ فعال ہے، اس لیے ان پٹ اعمال کی ہر ممکنہ ترتیب کے لیے، فیئر ٹریسز (A) (اور اس طرح ٹریسز (A) میں A کا جواب شامل ہوتا ہے۔ اگر فیئر ٹریس (A) ٹریس (P) برقرار رہتا ہے، تو پراپرٹی P میں تمام پیدا شدہ ترتیبات ہونے چاہئیں۔ حفاظتی خصوصیات بدیہی طور پر، حفاظتی پراپرٹی اس حقیقت کی نمائندگی کرتی ہے کہ کچھ بھی "برا" نہیں ہوتا ہے۔ مزید رسمی طور پر، P کو ایک ٹریس پراپرٹی ہونے دیں۔ پی ایک ٹریس سیفٹی پراپرٹی، یا سیفٹی پراپرٹی ہے، اگر درج ذیل معیار ٹریس (پی) کے لیے ہے۔ نشانات (P) خالی نہیں ہیں: کسی بھی واقعے کے واقع ہونے سے پہلے کچھ برا نہیں ہو سکتا ؛ لہذا، نشانات (P) پر خالی نہ ہونا ایک معقول شرط ہے۔ ٹریسز (P) "پریفیکس-کلوزڈ" ہے: فرض کریں کہ β 'ٹریسز (P) اور β' β کے ایک محدود پریفیکس کی نمائندگی کرتے ہیں۔ تفصیل سے، فرض کریں کہ ایک نشان ہے جس میں کچھ برا نہیں ہوتا ہے۔ لہذا، اس نشان کے کسی بھی سابقہ میں کچھ بھی برا نہیں ہوتا ہے۔ اس طرح، سابقہ بندش کا ہونا نشانات (P) پر ایک معقول شرط ہے۔ ٹریس (P) "حد بند" ہے: β1، β2،۔ ۔ ۔ نشانات (P) میں محدود ترتیبات کی لامحدود ترتیب کی نمائندگی کرتا ہے۔ نیز، فرض کریں کہ ہر i کے لیے، βi، βi + 1 کا سابقہ ہے۔ اس صورت میں، منفرد ترتیب β، یعنی "مسلسل توسیعی ترتیب کے تحت βi کی حد" بھی نشانات (P) میں موجود ہے۔ لہذا، اگر کسی نشان میں کچھ برا ہونا تھا، تو یہ نشان میں موجود کسی مخصوص واقعے کا نتیجہ ہوگا۔ اس صورت میں حد بند ہونا اس طرح نشانات (پی) پر ایک معقول شرط ہے۔ زندہ رہنے کی خصوصیات غیر رسمی طور پر، زندہ رہنے کی خاصیت کی تشریح اس طرح کی جا سکتی ہے کہ آخر کار کچھ "اچھا" ہوتا ہے۔ لہذا، اس بات سے قطع نظر کہ وقت میں کسی خاص مقام پر کیا ہوا ہے، مستقبل میں کسی وقت کچھ اچھا ہو سکتا ہے۔ مزید رسمی طور پر، P کو ایک ٹریس پراپرٹی ہونے دیں۔ پی ایک ٹریس لیوینس پراپرٹی، یا ایک لیوینس پراپرٹی ہے، "اگر اعمال (پی) پر ہر محدود ترتیب کے نشانات (پی) میں کچھ توسیع ہو۔" مزید پڑھنے کے لیے ٹائمڈ I/O آٹومیٹن: ممکنہ I/O آٹومیٹن: عام طور پر حفاظتی خصوصیات اور زندہ خصوصیات پر بحث کے لیے، سیفٹی اور زندہ خصوصیات دیکھیں۔ یہ بھی دیکھیں کہ مواصلاتی ترتیب وار عمل اداکار ماڈل حوالہ جات تقسیم شدہ کمپیوٹنگ