دانلود مقاله تشخيص بن بست در سيستم‌هاي توزيع شده
فرمت:word
۱- مفاهيم پايه
تعريف ۱-گراف- انتظار- براي (WFG): يك گراف جهتدار است كه وابستگي بين فرايندها را نشان مي دهد و در آن گره ها فرايندها و يالها نشان دهنده درخواست منابع است.
تعريف۲- چرخه[۱] بن بست: يك چرخه جهتدار در گراف- انتظار- براي (WFG) است.
تعريف۳– بن بست دروغين: به بن بستي گفته مي شود كه در حقيقت وجود ندارد.
تعريف۴– درستي الگوريتم هاي تشخيص بن بست توزيع شده: اثبات درستي الگوريتم هاي تشخيص
بن بست توزيع شده با ۲ ويژگي زير تعيين مي شود:
ويژگي پيشرفت (Progress): بدين معني كه هر بن بستي كه واقع شود در نهايت بايد تشخيص داده شود.
ويژگي امنيت(Safety): اگر بن بستي توسط الگوريتم تشخيص داده شود، بايد واقعاً وجود داشته باشد.
۱-۲- انواع مدلهاي بن بست براساس سيستم تبادل پيام
براساس سيستم تبادل پيام، دو نوع بن بست وجود دارد:
* بن بست منبعي
* بن بست ارتباطي
در بن بستهاي ارتباطي، پيامها منابعي هستند كه فرايندها براي آن متنظراند. تفاوت اصلي بين بن بست منبعي و بن بست ارتباطي در اين است كه بن بست منبعي از شرايط AND استفاده مي كند و بن بست ارتباطي از شرط OR با تعريف ذيل استفاده مي كند:
۱-۳- انواع مدلهاي بن بست براساس نوع درخواست منبع
تقسيم بندي مدلهاي بن بست براساس سيستم تبادل پيام به دو نوع بن بست ارتباطي و منبع به منظور شناسايي الگوريتمهاي تشخيص بن بست كافي نيست. بنابراين كه ويژگي هاي بيشتري از اين الگوريتمها مدنظر قرار گيرد. يكي از اين ويژگي ها نوع درخواست منبع است. در اين بخش سلسله مراتبي از مدلهاي منبع كه مي تواند در تقسيم بندي الگوريتمها تشخيص بن بست مورد استفاده قرار گيرد و مبتني بر مدل بن بست ارائه شده توسط Knapp است، ارائه مي شود.
۱-۳-۱- مدل گراف- انتظار- براي
اين گراف به كلاس گراف هاي جهت دار تعلق دارد. گره ها در اين گراف براي مدل كردن فرايندها بكار مي روند. يالهاي جهتدار در گراف نشان دهنده روابط مسدود شدن بين فرايندها . يك گره با يك يال خارج شده از آن به يك فرايند مسدود شده تعلق دارد.
بن بست با يك چرخه در اين گراف مشخص مي شود. ارتباط بين بن بستها و اين گراف در بخشهاي زير نشان داده شده است[۱۳].
۱-۳-۲- مدل تك- منبعي(One-Resource Model)
مدل تك منبعي، ساده ترين مدل درخواست منبع است. در اين مدل يك فرايند تنها يك درخواست منبع در يك زمان مي تواند داشته باشد،بدان معني كه ماكزيمم يال خروجي از يك گره در گراف-انتظار- براي برابر يك است.
براي يافتن بن بست در يك سيستم كه مدل درخواست آن تك منبعي است، لازم است يك چرخه در گراف-انتظار-براي پيدا شود. يك الگوريتم ساده براي تشخيص بن بست براساس اين مدل توسط ميچل و مريت[۲] است.
۱-۳-۳- مدل AND
اين مدل عمومي تر از مدل تك منبعي است. در اين مدل يك به يك فرايند اجازه داده مي شود كه مجموعه اي از منابع را درخواست نمايد. تا زماني مسدود مي ماند كه همه منابعي را كه درخواست نموده بود، به دست آورد به عبارتي فرايندي كه نياز به منابعي براي اجرا دارد، زماني مي تواند پيش رود كه همه منابعش را به دست آورد.
همانند مدل تك منبعي براي يافتن بن بست در يك سيستم با مدل اين مدل درخواست، لازم است يك چرخه در گراف-انتظار-براي پيدا شود. نمونه اي از اين الگوريتمها توسط چندي- ميسرا-هاس ، منساس و مانتز و اوبرمارك، ارائه شده است.
۱-۳-۴- مدلOR
اين مدل جالبي از مدل درخواست AND است. به آن مدل ارتباطي نيز مي گويند. در اين مدل به منظور تشخيص بن بست، تنها تشخيص يك چرخه در گراف-انتظار-براي كافي نيست، يافتن بن بست شامل پيدا كردن يك گره در گراف-انتظار-براي است.
فرايندي كه نياز به منابعي براي اجرا دارد،زماني مي تواند پيش رود كه حداقل يكي از منابعش را به دست آورد.دليلي كه شرط OR براي بن بست ارتباطي استفاده شده است اين است كه اغلب ساختارهاي كنترل توزيع شده غيرقطعي[۲] هستند و يك فرايند ممكن است در انتظار يك پيام از چندين فرايند باشد.
۱-۳-۵- مدل AND-OR
مدل AND و مدل OR هردو از مدل AND-OR مشتق شده اند. مفهوم اصلي اين مدل اين است كه اين نوع درخواست تركيبي از و يا در درخواست منبع است. تصور كنيدa ،b ، c، d منابع هستند كه در كامپيوتر هاي متفاوتي قرار دارند. درخواست به اين شكلd and ((c or b) a and) امكان پذير است. تشخيص بن بست در اين مدل مي تواند با تكرار تست براي مدل تشخيص OR با فرض اينكه بن بست يك مشخصه پايدار است، انجام شود.
۱-۳-۶- مدل p-out-of-q
اين مدل بدين معني است كه يك فرايند به طور همزمان درخواست q منبع را مي نمايد و تا زماني كه p منبع را بدست آورد،مسدود مي ماند. اين مدل نوع ديگر AND-OR است كه تركيبي از مدلهاي OR و AND است به عنوان مثال(b OR c) AND q
4345
دانلود مقاله تشخيص بن بست در سيستم‌هاي توزيع شده
فرمت:word
۱- مفاهيم پايه
تعريف ۱-گراف- انتظار- براي (WFG): يك گراف جهتدار است كه وابستگي بين فرايندها را نشان مي دهد و در آن گره ها فرايندها و يالها نشان دهنده درخواست منابع است.
تعريف۲- چرخه[۱] بن بست: يك چرخه جهتدار در گراف- انتظار- براي (WFG) است.
تعريف۳– بن بست دروغين: به بن بستي گفته مي شود كه در حقيقت وجود ندارد.
تعريف۴– درستي الگوريتم هاي تشخيص بن بست توزيع شده: اثبات درستي الگوريتم هاي تشخيص
بن بست توزيع شده با ۲ ويژگي زير تعيين مي شود:
ويژگي پيشرفت (Progress): بدين معني كه هر بن بستي كه واقع شود در نهايت بايد تشخيص داده شود.
ويژگي امنيت(Safety): اگر بن بستي توسط الگوريتم تشخيص داده شود، بايد واقعاً وجود داشته باشد.
۱-۲- انواع مدلهاي بن بست براساس سيستم تبادل پيام
براساس سيستم تبادل پيام، دو نوع بن بست وجود دارد:
* بن بست منبعي
* بن بست ارتباطي
در بن بستهاي ارتباطي، پيامها منابعي هستند كه فرايندها براي آن متنظراند. تفاوت اصلي بين بن بست منبعي و بن بست ارتباطي در اين است كه بن بست منبعي از شرايط AND استفاده مي كند و بن بست ارتباطي از شرط OR با تعريف ذيل استفاده مي كند:
۱-۳- انواع مدلهاي بن بست براساس نوع درخواست منبع
تقسيم بندي مدلهاي بن بست براساس سيستم تبادل پيام به دو نوع بن بست ارتباطي و منبع به منظور شناسايي الگوريتمهاي تشخيص بن بست كافي نيست. بنابراين كه ويژگي هاي بيشتري از اين الگوريتمها مدنظر قرار گيرد. يكي از اين ويژگي ها نوع درخواست منبع است. در اين بخش سلسله مراتبي از مدلهاي منبع كه مي تواند در تقسيم بندي الگوريتمها تشخيص بن بست مورد استفاده قرار گيرد و مبتني بر مدل بن بست ارائه شده توسط Knapp است، ارائه مي شود.
۱-۳-۱- مدل گراف- انتظار- براي
اين گراف به كلاس گراف هاي جهت دار تعلق دارد. گره ها در اين گراف براي مدل كردن فرايندها بكار مي روند. يالهاي جهتدار در گراف نشان دهنده روابط مسدود شدن بين فرايندها . يك گره با يك يال خارج شده از آن به يك فرايند مسدود شده تعلق دارد.
بن بست با يك چرخه در اين گراف مشخص مي شود. ارتباط بين بن بستها و اين گراف در بخشهاي زير نشان داده شده است[۱۳].
۱-۳-۲- مدل تك- منبعي(One-Resource Model)
مدل تك منبعي، ساده ترين مدل درخواست منبع است. در اين مدل يك فرايند تنها يك درخواست منبع در يك زمان مي تواند داشته باشد،بدان معني كه ماكزيمم يال خروجي از يك گره در گراف-انتظار- براي برابر يك است.
براي يافتن بن بست در يك سيستم كه مدل درخواست آن تك منبعي است، لازم است يك چرخه در گراف-انتظار-براي پيدا شود. يك الگوريتم ساده براي تشخيص بن بست براساس اين مدل توسط ميچل و مريت[۲] است.
۱-۳-۳- مدل AND
اين مدل عمومي تر از مدل تك منبعي است. در اين مدل يك به يك فرايند اجازه داده مي شود كه مجموعه اي از منابع را درخواست نمايد. تا زماني مسدود مي ماند كه همه منابعي را كه درخواست نموده بود، به دست آورد به عبارتي فرايندي كه نياز به منابعي براي اجرا دارد، زماني مي تواند پيش رود كه همه منابعش را به دست آورد.
همانند مدل تك منبعي براي يافتن بن بست در يك سيستم با مدل اين مدل درخواست، لازم است يك چرخه در گراف-انتظار-براي پيدا شود. نمونه اي از اين الگوريتمها توسط چندي- ميسرا-هاس ، منساس و مانتز و اوبرمارك، ارائه شده است.
۱-۳-۴- مدلOR
اين مدل جالبي از مدل درخواست AND است. به آن مدل ارتباطي نيز مي گويند. در اين مدل به منظور تشخيص بن بست، تنها تشخيص يك چرخه در گراف-انتظار-براي كافي نيست، يافتن بن بست شامل پيدا كردن يك گره در گراف-انتظار-براي است.
فرايندي كه نياز به منابعي براي اجرا دارد،زماني مي تواند پيش رود كه حداقل يكي از منابعش را به دست آورد.دليلي كه شرط OR براي بن بست ارتباطي استفاده شده است اين است كه اغلب ساختارهاي كنترل توزيع شده غيرقطعي[۲] هستند و يك فرايند ممكن است در انتظار يك پيام از چندين فرايند باشد.
۱-۳-۵- مدل AND-OR
مدل AND و مدل OR هردو از مدل AND-OR مشتق شده اند. مفهوم اصلي اين مدل اين است كه اين نوع درخواست تركيبي از و يا در درخواست منبع است. تصور كنيدa ،b ، c، d منابع هستند كه در كامپيوتر هاي متفاوتي قرار دارند. درخواست به اين شكلd and ((c or b) a and) امكان پذير است. تشخيص بن بست در اين مدل مي تواند با تكرار تست براي مدل تشخيص OR با فرض اينكه بن بست يك مشخصه پايدار است، انجام شود.
۱-۳-۶- مدل p-out-of-q
اين مدل بدين معني است كه يك فرايند به طور همزمان درخواست q منبع را مي نمايد و تا زماني كه p منبع را بدست آورد،مسدود مي ماند. اين مدل نوع ديگر AND-OR است كه تركيبي از مدلهاي OR و AND است به عنوان مثال(b OR c) AND q
4345
تميز كردن نماي ساختمان