نمایش نتایج 1 تا 5 از 5

نام تاپیک: الگوریتم dekker

  1. #1

    الگوریتم dekker

    سلام
    من یه توضیح تقریبا کامل در مورد الگوریتم dekker میخواستم
    متاسفانه فعلا هم به کتاب سیستم عامل دسترسی ندارم
    با تشکر

  2. #2
    Dekker's algorithm is a concurrent programming algorithm for mutual exclusion derived by the Dutch mathematician T. J. Dekker that allows two processes to share a single-use resource without conflict, using only shared memory for communication.
    It avoids the strict alternation of a naïve turn-taking algorithm, and was one of the first mutual exclusion algorithms to be invented.
    If both processes attempt to access the critical section at the same time, the algorithm will choose the process whose turn it is. If the other process is already modifying the critical section, it will wait for the process to finish. This is done by the use of two flags f0 and f1 which indicate an intention to enter the critical section and a turn variable which indicates who has priority between the two algorithms.

    f0 := false
    f1 := false
    turn := 0 // or 1
    p0: p1:
    f0 := true f1 := true
    while f1 { while f0 {
    if turn ≠ 0 { if turn ≠ 1 {
    f0 := false f1 := false
    while turn ≠ 0 { while turn ≠ 1 {
    } }
    f0 := true f1 := true
    } }
    } }
    // critical section // critical section
    turn := 1 turn := 0
    f0 := false f1 := false
    // non-critical section // non-critical section


    Processes indicate an intention to enter the critical section which is tested by the outer while loop. If the other process has not flagged intent the critical section can be entered safely irrespective of the current turn. Mutual exclusion will still be guaranteed as neither process can become critical before setting their flag (implying at least one process will enter the while loop). This also guarantees progress as waiting will not occur on a process which has withdrawn intent to become critical. Alternatively, if the other process's variable was set the while loop is entered and the turn variable will establish who is permitted to become critical. Processes without priority will withdraw their intention to enter the critical section until they are given priority again (the inner while loop). Processes with priority will break from the while loop and enter their critical section.
    Dekker's algorithm differs from Peterson's in its style of alternation. If a non-critical section of a process can be completed quickly enough such that the other process is never given the opportunity to check its new priority, the process's re-attempt to gain control of the critical section will be successful (the second process will not indicate intention to enter the critical section). This can happen repeatedly, and the second process will not progress. This of course requires a very unusual scheduling sequence. In contrast, Peterson's guarantees a strict alternation between processes if they request it (this is not to be confused with indefinite postponement).


    http://en.wikipedia.org/wiki/Dekker's_algorithm

  3. #3
    سلام
    اگه ممکنه توضیحات رو فارسی بدید!!!

  4. #4
    واقعا از این همه توجه ممنونم!!!!!!!!!!!!!!!!!

  5. #5
    کاربر دائمی
    تاریخ عضویت
    فروردین 1385
    محل زندگی
    قفس فیلترینگ(ایران)
    پست
    208
    با سلام
    در تکمیل نوشته های دوستم جناب Identifier

    لطفا توجه بفرمایید این الگوریتم ها معمولا دارای پیچیدگی خاصی هستند که گاها اساتید از ذکر آنها ناتوان می باشند حالا اگر قرار باشه بصورت نوشتاری بخواهیم اون رو توضیح بدیم . بهر حال سعی خودم رو میکنم .

    این الگوریتم یکی از الگوریتم های جلوگیری از بن بست می باشد که معمولا در سیستم عامل ها مورد توجه قرار می گیرد . از آنجا که تعداد منابع در یک سیستم عامل و یا بطور کلی تر در یک سیتم مدیریت ، محدود می باشد و از طرفی درخواست برای کسب آن منابع در هر زمانی ممکن است اتفاق بیافتد لذا الگوریتم تخصیص باید بگونه ای عمل نماید که در یک زمان از یک منبع بحرانی بیشتر از یک نفر استفاده ننماید برای این منظور الگوریتم های زیادی ارائه شده است از جمله الگوریتم Dekker . همانطور که در شبه کد فوق که دوستمان زحمت آن را کشیده اند می بینید معمولا اینگونه الگوریتم ها دارای سناریوی دوگانه و یا دارای دو روال برای پروسس ها می بشند که معمولا اولی پذیرای شروط اولیه می باشد و طی آن منابع در اختیار پروسس قرار می گیرد و در این حال پروسس به بخش بحرانی (Critical section) خواهد رسید اما اگر پروسس دوم را دنبال کنیم می بینیم که اگر پروسس اول قبلا به بخش بخرانی رسیده باشد پروسس دوم اجازه ورود به بخش بحرانی را ندارد . حالا بیشتر توجه کنید این مطلبی را که گفتم فقط برای یک مثال کوچک بود و بطور کلی اینچنین است که در هر مرحله ای از هر یک از این دو پروسس که در واقع نماینده n پروسس هستند چنانچه time slice (برش زمانی) به اتمام برسد و به سراغ پروسس دیگر برود که او هم همان منبع را بخواهد آنگاه این الگوریتم از این عمل جلوگیری می کند و لذا هیچوقت اتفاق نمی افتد که هر دو یا چند پروسس در یک لحظه داخل بخش بحرانی قرار بگیرند.

    متاسفانه در اینجا بصورت نوشتاری امکان پذیر نیست که چند سناریو را دنبال کنیم ولی خودتان سعی کنید همانند سیستم عامل زمانبدنی را انجام دهید و مثلا یک ثانیه به پروسس اول توجه کنید و یک ثانیه به پروسس دوم ... تا نتیجه این الگوریتم را ببینید .

    موفق باشید

قوانین ایجاد تاپیک در تالار

  • شما نمی توانید تاپیک جدید ایجاد کنید
  • شما نمی توانید به تاپیک ها پاسخ دهید
  • شما نمی توانید ضمیمه ارسال کنید
  • شما نمی توانید پاسخ هایتان را ویرایش کنید
  •