بخشی از مقاله
بررسي آشكار سازي بن بست در سيستم عامل توزيع شده
چكيده
آشكار سازي بن بست يكي از جدي ترين مسائل در سيستم عاملهاي توزيع شده است. در اين مقاله ما يك بررسي وضعيت هنري الگوريتمهاي آشكار سازي بن بست توزيع شده كه در ادبيات مطرح شده است ارائه مي كنيم. در اين حوزه ما يك نگاهي به مقالات آشنا درباره اين عنوان داريم و تلاش مي كنيم تا معروف ترين الگوريتم ها را گروه بندي مي كنيم.
1- مقدمه
در طول دهه گذشته سيستمهاي محاسبه گر پيشرفت سريعي داشته اند كه تأثير زيادي بر سيستم عاملهاي توزيع شده دارد. در حاليكه سيستمهاي تجاري به تدريج پيشرفت مي كنند، چالشهاي جديد بوسيله ارتباط گسترده جهاني سيستمهاي كامپيوتري وضع شده است.
اين جريان يك نياز رشد كننده‌‌اي براي راه حلهاي توزيع شده با مقياس بالا ايجاد مي‌كند. در آينده، سيستم عاملهاي توزيع شده بايد صدها و حتي هزاران سايت و ميليونها مراجع را حمايت كنند و بنابراين با چالشهاي بزرگي در ارتباط با اجرا، در دسترس بودن و مديريت مواجه خواهند شد. يكي از چالشهايي كه ما بايد حل كنيم در اين حوزه مشكل بن بست است. همچنين نسبت يكي از جدي ترين مشكلات در سيستم هاي برنامه ريزي رايج چند كاره است.
بقيه مقاله مثل زير سازمان دهي شد. بخش 2 مختصرا بن بست و حوزه آن در سيستم عاملهاي توزيع شده را توزيع مي دهد.
در حاليكه بخش 3 يك شرحي از مشكل بن بست ارائه مي دهد و 2 الگوي بن بست كه به طور كلي در سيستمهاي بانك اطلاعاتي توزيع شده به كار مي رود. يك گروه بندي از الگوريتمهاي توزيع شده براي اين الگوها و نماينده‌هاي گروه هاي مختلف در بخش 4 شرح داده شده است. نهايتا، ما در بخش 5 خلاصه مي كنيم، در حاليكه بخش 6 مرجهاي ما را توصيف مي كند.
2- پيش زمينه
در اين بخش ما تلاش مي كنيم تا نگاهي بر مقالات بررسي كه بوسيله ديگران در روش آشكار سازي بن بست ارائه شده است داشته باشيم.
متون بن بست رسما يك بن بست را به عنوان يك مجموعه فرايندي كه بن بست است، اگر هر فرايند در مجموعه منتظر يك رويدادي است كه تنها فرايند ديگري در مجموعه مي تواند موجب شود. تعريف مي كند. [2 و 1]. يك تعريف غيررسمي تر اين است كه بن بستها مي تواند هر زماني كه
2 يا چند فرايند براي منابع محدودي رقابت مي كنند و فرايندها براي يافتن و حفظ يك منبع فراهم شده است اتفاق بيافتد. اگر يك فرايند براي منبعي، انتظار بكشد، هر منبعي كه آن حفظ براي
فرايندهاي ديگر در دسترس نيستند. اگر فرايندي براي منبعي كه بوسيله فرايند ديگري حفظ شده است انتظار مي‌كشد، كه در بازكش در حال انتظار براي يكي از منابع نگهداري آن ما يك بنسبت داريم. هنگاميكه يك سيستم به اين وضعيت مي رسد، به طور مؤثر، بسته مي شود: و بايد مشكل را براي ادامه عملكرد حل كنيم.
4 شرط وجود دارد كه يك بن بست نياز دارد:
1- حذف متقابل: هر منبعي مي تواند به يك منبع خاص تخصيص يافته شود.
2- حفظ و انتظار: فرايندها مي توانند يك منبع و درخواست بيشتر حفظ كنند.
3- بدون پريامپشن: منابع نمي توانند بالاجبار از يك فرايند حذف شوند.
4- انتظار حلقوي: بايد يك زنجيره حلقوي از فرايند وجود داشته باشد هر انتظاري براي يك منبع نه بوسيله شماري از زنجيره‌هاي بعدي نزديك حفظ شده است.
به طور معمول 4 روش در ارتباط با بن بستها به كاربرده شده است
1- ناديده گرفتن مشكل
2- آشكار سازي بن بست
3- جلوگيري از بن بست
4- اجتناب از بن بست
ناديده گرفتن بن بستها آسانترين برنامه براي تكميل است. آشكار سازي بن بست تلاش مي كند تا بن بست ها را قرار دهد و حل كند. اجتناب از بن بست روشهايي را شرح مي دهد كه تلاش مي كند تا تعيين كند آيا يك بنبست در زماني كه يك منبع درخواست مي شود و نسبت به درخواستي در يك حالتي كه از بن بست اجتناب مي‌شود عكس عمل نشان مي دهد. اتفاق خواهد افتاد.
جلوگيري از بن بست ساختن يك سيستمي در يك حالتي كه يكي از 4 شرط ضروري براي بن بست امكان پذير نباشد است. هر گروه راه حل متناسب با يك نوع خاص محيط است و فوايد و نقايص دارد. در اين مقاله ما به آشكار سازي بن بست كه شايع ترين راه حل بن بست تكميل شده است تمركز مي كنيم.
در سيستمهاي بانك‌ها اطلاعاتي توزيع شده، آشكار سازي بن بست خيلي پيچيده مي‌شود به عنوان يك نتيجه‌اي از بي ثباتي در وضعيت سيستم جهاني. اگر چه الگوريتمهاي آشكار سازي بن بست زيادي در سيستم هاي بانك اطلاعاتي توزيع شده مطرح شده است اكثر آنها به خاطر سربارهاي سيستم بالا غير عمل هستند.
2 روش اصلي در آشكار سازي بن بست توزيع شده شكل گرفته است. ابتدا يكي كه براي ساخت وضعيت يك سيستم جهاني است و دومي براي تلاش در جهت عبور از يك پيغام خاص از طريق ترانكش هاي بلوكه شده به منظور آشنا ساختن يك چرخه بن بست است. يك روش از روش دومي آشكار سازي بن بست توزيع شده بر پايه دليل همان طور كه توسط چندي و مسيرا و هس مطرح شده است. تركيب اصلي اين متد اين است كه هيچ وضعيت سيستم جهاني مورد نياز نيست.
الگوريتم آشكار سازي بن بست كندي بر پايه احتمالي از طريق سايتهاي مختلف است. تنها فرايندهايي كه در مرز سايتهاي يافت مي شود مي تواند پيغام‌هاي بررسي را آغاز كند. الگوريتم كندي مي تواند براي آشكار سازي بن بست توزيع شده بر پايه بررسي كندي در [2] ارائه شد. به عنوان يك نتيجه از سربازهاي سيستم بالا كه در حفظ جدول وابستگي براي mpa ايجاد شد انتظار مي رود عملكرد سيستم يك شكل اساسي داشته باشد. يك نسخه پشرقه از MPA (EPA) با جايگزيني جدول استقلال (وابستگي) با يك انتظار براي نوشتن تعريف شد.
بررسي اوليه به اين كار در متن سيستم هاي بانك اطلاعاتي توزيع شده بوسيله المگاواميه مطرح شده است به هر صورت محققان زيادي احساس مي كنند كه نيازهاي درجه بند و عملكرد كه بوسيله سيستمهاي توزيع شده مقياس بالا وضع شده مورد نياز براي بروز روشهاي مكمل پيشرفته است.
در يك مقاله‌اي از نپ الگوريتمهاي آشكارسازي بن بست توزيع شده در گروههاي زير تقسيم بندي شد:
1- روش مركزي شده توسط حفظ انتظار براي نوشتن جهاني
2- الگوريتم هل دادن مسير توسط فرستادن بخشهايي از WFG به سايتها مجاور
3- آشكار سازي جستجوي لبه با فرستادن بررسي‌ها
4- رد محاسبات با فرستادن بررسي‌‌هايي به همه فرايندهاي وابسته (OMS) و انتظار براي دريافت پاسخ.
5- آشكار سازي وضعيت جهاني كه بخشهاي مرتبط نقشه WFG در يك هرم منسجم جهاني بدون حفظ محاسبات ساخته شده است.
DDA برنامه DDA اينجا مي تواند تحت 5گروه ارائه شود.
3- مشكل بن بست عمومي
در اكثريت سيستمهاي بانك اطلاعاتي مدرن كنترل همزمان بر پايه مكانيزم‌‌هاي قفل كردن است. اكثر سيستم‌ها پروتكل PL2 محكمي را استفاده مي كنند. پروتكل قفل كردن مي تواند موجب بن بست شود. يك بن بست يك شرايط انتظار حلقوي موقت است. يك مجموعه از تراكنشها بن بست. شده هستند اگر هر كدام از تراكنش ها براي قفلهايي كه توسط تراكنشهاي ديگر از اين مجموعه انتظار مي كشند. همه تراكنشها مي توانند در مجموعه در يك حالت انتظار باشند يعني راهشان سد شده است و هيچ كدام از آنها بدون دخالت بيرون باز نمي شوند. نمونههاي قفل كردن مختلف مي تواند بوسيله الگوريتمهاي كنترل همزمان مورد استفاده باشد.
هنگاميكه از قفل كردن معنايي استفاده مي شود. يك تراكنش ممكن است براي تنها يك زيرمجموعه از نگهدارنده‌هاي هدف انتظار بكشد. همچنين تراكنشهاي مختلفي كه بلوكه شده اند در همان شي ممكن است. براي زير مجموعه‌هاي متفاوتي از نگهدارندها شي انتظار بكشد. اداره كردن بن بست قفلها شامل 2 مسئله مي شود. آشكارسازي بن بست و راه حل بن بست، در يك مفهوم راه حل بن بست DBMS كه يكي از تراكنشهاي شركت كننده، فرماني براي ناتمام ماندن انتخاب شده است بدان وسيله بن بست حل مي شود.
الگوريتم آشكارسازي يك بن بست اگر 2 شرط را رعايت كند صحيح است:
1- هر بن بست به تدريج آشكار مي شود (خصوصيت پيشرفت اساسي) و
2- هر بن بست آشكار شده‌اي در واقعيت وجود دارد، يعني، تنها بن بست هاي عملي آشكار شده هستند (خصوصيت ايمني).
در حاليكه اولين شرط روشن است، دومي نياز به توضيح دارد. اگر چه يك بن بست يك خصيصه باثبات است، به واسطه اطلاعات قديمي ممكن است كه همان بن بست آشكار شود و يا دوباره حل شود. بن بستهاي آشكار شده كه واقعا وجود ندارند بن بستهاي فانتوم ناميد مي شوند. موردي كه قابل بحث است اين است تا يك الگوريتم آشكار كننده بن بستهاي فانتوم مي توانست صحيح بنظر برسد اما ناتمام هاي ترانكشن غيرضروري آنچنان گران گران هستند كه قابل تحمل نيستند.
هر الگوريتم آشكار سازي بن بست ممكن است بن بستهاي فانتوم را اگر ناتمام‌‌هاي همسان اجازه دهند آشكار سازد. اگر يك الگوريتم تصميم بگيرد ناتمام بگذارد يك ترانكشن را به منظور حل يك بن بست و در همان زمان ترانكشن‌هاي ديگر ناتمام‌‌هاي بن بست را در برگيرند در نتيجه حل شدن بن بست الگوريتم بن بست فانتوم را مي‌شكند. بنابراين ما فرض خواهيم كرد كه هيچ ناتمام همساني در سيستم اتفاق نمي‌افتد.
1-3- انتظار براي نمودار
شرايط بازدارنده بين تراكنشها مي تواند از طريق يك ترانكشن منتظر براي نمودار (WFG) ارائه شود. يك WFG يك نموادر مستقيم است كه گره‌‌ها مطابق با ترانكشن‌ها و يك لبه مستقيم براي بيان آن انتظار براي يك منبع حفظ شده است.
يك بن بست مي تواند بوسيله بررسي ساختار WFG آشكار شود. ساختار نمودار نشان مي دهد كه بن بست وابسته به نمونه بن بست است به عنواني كه در فصل بعد توضيح داده شده است به كار مي رود.
2-3- نمونههاي بن بست متفاوت
وابسته به نمونه محاسباتي در انواع درخواستهايي كه توسط ترانكشن ها ايجاد مي‌شود. نمونههاي بن بست متفاوت به كار برده مي شود. در DBMS توزيع شده منبع مجردي و نمونه AND در حال غالب شدن است، آنچنان كه آنها در اين جا مورد بحث قرار مي گيرند. توضيحات نمونههاي ديگري مثل نمونه or و نمونه كلي، كه كمتر معمول هستند در فصل 5 ارائه شده است.
ساده ترين و مورد استفاده ترين نمونه در DBMS ها نمونه منبع مجرد است. در اين نمونه يك ترانشكن يك درخواست برجسته در يك زمان دارد يعني يك قفل در يك مورد درخواست مي كند. اگر چه يك ترانكشن تنها يك درخواست بيرون رونده در يك زمان دارد، ممكن است براي بيش از يك ترانكشن انتظار بكشد.
يك بن بست در نمونه منبع مجرد مطابق با يك چرخه از ترانكشن هاي منتظر است. بنابراين الگوريتمها براي اين نمونه يك بن بست را جدا مي كنند. چرخه اگر يكي از ترانكشن‌هاي مرتبط ناتمام بماند و بدان وسيله قفلها را باز كند حل مي‌شود.
براي اين مدل الگوريتمهاي زيادي ارائه شده است. در يك مدل محاسباتي كه در آن يك ترانكشن مي تواند بيش از يك درخواست در يك زمان بفرستد و بايد تا زماني كه همه آنها تأييد بشوند انتظار بكشد، بن بستها بوسيله مدل AND توصيف شده اند. براي مثال اين مدل در سيستمهاي حمايت كنند تراكنشها جاي گرفتند بكار مي رود، يك بن بست در اين مدل دوباره از طريق يك چرخه در WFG نشان داده مي شود.
4- الگوريتمهاي آشكار سازي بن بست توزيع شده
الگوريتمهاي آشكار سازي بن بست توزيع شده زيادي براي DBMS هاي توزيع شده گسترش يافته است كه بررسي ها در 10 و 5 و 4 يافت مي شود. اين مقاله بر الگوريتم هاي توزيع شده براي منبع و مدل AND تمركز دارد. ما الگوريتمهاي توزيع شده را براساس روشهايي كه آنها استفاده مي كنند
شبيه به گروهبندي پيشنهادي در [5]، توضيح روشهاي مختلف و توصيف يك نمونه از هر گروه در جزئيات بيشتر گروه بندي مي كنيم. ما اين الگوريتم ها را انتخاب مي كنيم كه براي بهترين بودن در گروهشان ظاهر مي شوند، يعني كمترين تعداد پيغامها را كاهش مي دهند و ابتدا در فصل 1-4 ما يك نگاهي به استراتژي هاي راه حل بن بست خواهيم داشت.
1-4- راه حل بن بست
استراتژي‌هاي راه حل بن بست تعيين مي كند كه ترانكشن‌ها به منظور حل بن‌بست‌ها نا تمام مي مانند. استراتژي هاي راه حل زيادي براي سيستمهاي مركزي ارائه شده است. بعضي از آنها بوسيله 11 مقايسه شده است. براساس نتايج متحركات، 2 شرط تعيين كردند كه هر راه حل بايد تضمين كند: 1- هميشه تضمين كند كه حداقل يك ترانكشن در سيستم تمام شود و 2 هيچ ترانكشني ناتمام نخواهد ماند.
اولين شرط در ارتباط با خصوصيت بيان شده در فصل 3 است اين خصيصه ضمانت مي كند كه هيچ بن بستي وجود نخواهد داشت اما اطمينان نمي دهد كه همه ترانكشن‌ها پايان يابند. يك آشكارسازي و الگوريتم راه حل بن بست تعيين كننده است كه چه چيز انتظار مي رود. صراحتا شرايط مطرح شده براي DBMS هاي توزيع شده حفظ مي شود.
2-4- روش تايم اوت (زمان سپري شده)
در اين الگوريتم يك ترانشكن يك تايم اوت هر زماني آن يك درخواست عملكرد ايجاد كند شكل مي دهد. اگر هيچ تقديري دريافت نكند كه نشان موفقيت آميز بودن عملكرد باشد قبل از اينكه زمان به پايان برسد فرض مي كنيم كه درگير يك بن بست و ناتمام شده است.
الگوريتم ساده است و بنابراين آسان تكميل مي شود. همچنين به واسطه آشكار سازي بن بست موجب ترافيك شبكه‌اي نمي شود.
فايده اصلي الگوريتم اين است كه آن تعداد زيادي ترانكشن را ناتمام مي گذارد كه ممكن است بن بست نباشند و در نتيجه موجب عكس العمل‌هاي غيرضروري و دوباره راه اندازي ترانكش ها مي شود.
فايده ديگر اين است كه فاصله تايم اوت (زمان سپري شده) بايد منظم باشد. اگر خيلي كوتاه است حتي بيتشر از زماني كه ترانكشهاي غيرضروري ناتمام مي مانند. اگر آنقدر طولاني است كه بن بستها در سيستم براي يك مدت طولاني باقي مي مانند و در نتيجه موجب تأخير ترانكشن در بن بست و انتظار براي قفلهايي كه توسط آنها ايجاد شده است مي شود.
در دوازده اين طور مطرح شده است كه ممكن است بعضي اوقات ناتمام ماندن تراكنشهاي زيادي مطلوب نباشد، اين نشان مي دهد كه بار قفل كردن آنچنان بالا نيست. اين ممكن است صحيح باشد اما يك الگوريتم آشكار سازي بن بست نبايد براي برنامه ريزي روزانه مسئول باشد.
3-4- گروه بندي الگوريتمهاي توزيع شده
الگوريتمهاي آشكار سازي بن بست توزيع شده متفاوت زيادي براي DBMS ها منتشر شده است.
آنها مي توانند به دو گروه زير تقسيم شوند: 1- هل دادن مسير 2- بر پايه بررسي
3- الگوريتمهاي آشكار سازي وضعيت جهاني
قبل از اينكه ما الگوريتمها و گروههاي مختلف را توضيح مي دهيم مي خواهيم فرضياتي را كه فراهم كرده ايم مختصرا بيان كنيم در بخشهاي قبل مطرح شد كه ما در اينجا يادآوري مي كنيم. ابتدا دو فرضيه در ارتباط با عملكرد ترانكشن‌ها:
آنها پروتكل PL2 را دنبال مي كنند و بي اختيار تمام نمي شوند. به علاوه يك برقراري ارتباط آزاد ـ خطا نيز فرض شد. بدين معنا كه هر پيغامي مقصود خودش را در يك زماني دريافت خواهد كرد و اين كه هر پيغام دريافت شده صحيح است.
4-4- الگوريتم هاي هل دادن (فشار) مسير (جريان كار)
الگوريتم هاي فشار مسير صراحتا WFG را حفظ مي كنند. هر سايت به طور دوره‌اي بستگي هاي انتظار محلي را جمع آوري مي كند و يك WFG محلي مي سازد و براي چرخه‌هايي در آن جستجو مي كند و چرخه‌هايي را كه آن محل مي كند آشكار مي سازد. بخشهاي ديگر WFG به بعضي سايتهاي ديگر فرستاده مي شود. آنها در وابستگي‌هاي انتظار دريافت شده در WFG محلي‌شان متحد هستند و براي چرخه‌هايي در آن جستجو مي كنند. پس از آن سايت دوباره بخشهايي از WFG در سايت هاي ديگر را عبور مي دهد.
جالب است ببينيم كه خيلي از الگوريتمهاي فشار مسير منتشر شده در بازگشت درست نبوده اند. اكثر آنها بن بستهاي فانتوم را درحاليكه الگوريتمهاي ديگر حتي آشكار كردن يك بن بست وارد مي كند آشكار مي سازد.
اگر چه اين الگوريتمها نادرست هستند الگوريتم مناسك ـ مانتز (13) و الگوريتم اوبرمارك مختصرا براي فهم مشكلات اين گروه از الگوريتمها مطرح شده است.
الگوريتم مناسك ـ مانتز. الگوريتم مناسك مانتز اولين بار براي شكل مشخصي از ترانشكن منتظر براي نمودار مورد استفاده قرار گرفت. در الگوريتم آنها تنها بخش هاي TWFG جهاني كامل در سايت جهاني ترانكشن براي آشكار سازي بن بستها نگهداري شد مبدل بن بست شالوده مدل AND است، از اين رو الگوريتم براي چرخه‌هايي در زير مجموعه TWFG جستجو مي كند.
يك ترانكشن مي تواند يا بلوكه شود يا نشود. يك مجموعه منع شده T يك ترانشكن T مجموعه همه ترانكشن‌ها To منع نشده اي است كه مي تواند از T در TWFG از طريق يك مسير مستقيم بدست آيد.
الگوريتم اوبرمارسك ـ الگوريتمي كه توسط اوبرمارسك درباره سيستم R تكميل شد و استراتژي فشار مسير را با فرستادن بخشي از يك چرخه ممكن يعني يك مسير به سايت ديگر تنها در مورد ترانكشن اول در مسير يك تقدمي نسبت به آخري دارد.
اين جريان شمار پيغام ها را بوسيله نيم تا نيم كاهش مي دهد.
علي رغم اين بهينه سازي الگوريتم سه بار عمده اي را هنگاميكه آن اجرا مي شود. ارائه مي كند. اين جريان به صورت دوره اي انجام مي شود. آنچنان كه همه WFG بايد براي چرخه 3 جستجو شود. به علاوه مسيرهايي كه بايد به سايتهاي ديگر فرستاده شود بايد مشخص شود. همچنين مشاركت مسيرهاي بدست آمده از يك سايت اطلاعات خيلي دريافت شده از اين سايت را واضح مي كند. بايد در WFG براي اطلاعات جديد مبادله شود.
در فصل [4] اين طور مطرح شده است كه الگوريتم از بن بست هاي فانتوم حمايت مي‌كند، از آنجائي كه بخشهايي از WFG بين سايتهاي متعلق به اسنپ شات‌ها يعني ممكن است ناپايدار باشد فرستاده مي شود.
بدال الگوريتم: در يك تلاش براي بهينه سازي الگوريتمهاي آشكار سازي بن بست توزيع شده در اصطلاحات آشكار سازي اگر بن بست ها با حداكثر كارآمدي، بدان يك الگوريتم 3 سطحي را پيشنهاد مي كند. يك چرخه بن بست مي تواند تپولوژي هاي مختلفي داشته باشد. بدال بن بست ها را به 4 نوع برطبق پتولوژي شان تقسيم بندي كرد. از كل، يك بن بست مي تواند محلي باشد يا جهاني
.
يك نوع محلي ساده ـ همچنين اكثر چرخه‌هاي بن بست تنها يك طول از 2 دارند و هرچه يك چرخه بن بست بلندتر باشد با فركانس كمتري اتفاق مي افتد. اين حقيقت موجب يك عقيده‌اي از ساده كردن آشكار سا زي بن بستهاي جهاني توسط ساخت الگوريتم هاي كار آمد تر در آشكار سازي بن بستهاي جهاني كوتاه تر است. بر اساس اين عقايد اجرا در الگوريتم بدال با استفاده از 3 سطح از آشكارسازي بنبست براي غلبه بر گروههاي پيچيده مختلف بن بستها بهينه مي شود. فعاليت در هر سطح پيچيده تر است و نسبتا از نظر قيمت در سطح در حال پيشرفت.
5-4- الگوريتم هايي بر پايه تحقي
ق
الگوريتمهايي بر پايه تحقيق صراحتا WFG را حفظ نمي كند بلكه يك نوع خاص از پيغام، تطبيق را در مسئول لبه WFG مي فرستد. 2 نوع الگوريتم برپايه تحقيق وجود دارد: جستجوي لبه و محاسبات پراكنده.
1-5-4- الگوريتمهاي جستجوي لبه
هنگاميكه يك ترانكشن يك اجراي عملكرد را در يك شي درخواست مي كند و مانع ايجاد مي كند به خاطر اينكه آن بايد براي قفلهايي كه توسط ترانكشن هاي ديگر ايجاد شده است منتظر بماند، يك تحقيق به هر كدام از اين ترانكشن‌ها فرستاده مي شود.
يعني يك محاسبه تحقيق آغاز مي شود. يك ترانكشن بلوكه شده كه يك تحقيق دريافت مين كند بايد به سوي آن با همه ترانكشن هاي نگهدارنده قفلهايي كه براي آنها انتظار مي كشد برود.
يك ترانكشن كه يك اجراي عملكرد درخواست كرده است نمي داند كه آيا بلوكه شده است يا
عملكرد عموما پردازش مي شود. همچنين اگر بلوكه شده است نمي داند براي كدام ترانكشن انتظار مي كشد. اشياء اين اطلاعات را دارند، آنچنان كه در حقيقت آنها تحقيق اوليه‌اي بر نيمي از ترانكشن هاي بلوكه شده انجام مي دهند. به همين دليل يك ترانكشن به سوي تحقيقاتي با شئي كه براي آن انتظار مي كشد عمل مي كند.
