[/align]تو را به خدا حواب بدید جند تا موضوع گداشتم کسی جواب نداده
چرا کد زیر انحصار متقابل را نقض می کند
[bool blocked[2];
int turn;
void p (int id)
{
while(true)
{
blocked[id] = true;
while(turn <> id)
{
while(blocked[i-id])
turn = id;
}
critical section
blocked[id] =false;
remainder
}
}
int turn;
void p (int id)
{
while(true)
{
blocked[id] = true;
while(turn <> id)
{
while(blocked[i-id])
turn = id;
}
critical section
blocked[id] =false;
remainder
}
}
چقدر سخت، فکر کنم نیم ساعت طول کشید که بفهمم. البته اگر درست فهمیده باشم.
سناریویی که به نقض انحصار متقابل می انجامه می تونه اینطوری باشه:
فرض کنین که مقدار turn = 0 باشه و هر دو فرایند در قسمت غیر بحرانی (remainder) خودشون باشن. یعنی فرایند ۱ وارد قسمت بحرانی شده باشه و پس از خروج در قسمت غیر بحرانی خودش CPU به فرایند ۰ داده بشه و فرایند ۰ وارد قسمت بحرانی خودش شده باشه و در قسمت غیر بحرانی فرایند ۰ CPU به فرایند ۱ برگشته باشه.
با فرض طولانی بودن قسمت غیر بحرانی فرایند ۱ این فرایند می تونه به ابتدای حلقه While بیرونی برگرده و blocked[1] = true بکنه و وارد حلقه داخلی شده و قبل از turn = id زمانبند به فرایند ۰ سوئیچ کنه. توجه کنین که هنوز مقدار turn تغییر داده نشده و هنوز همون ۰ هست.
حالا فرایند ۰ به ابتدای حلقه بیرونی برگرده و در زمان چک کردن شرط حلقه داخلی (یعنی turn != id) اون رو بصورت ۰ != ۰ ببینه (که false هست) و بدون وارد شدن به حلقه داخلی وارد ناحیه بحرانی خودش (فرایند ۰) بشه و در ناحیه بحرانی زمانبند به فرایند ۱ سوئیچ بکنه. که فرایند یک هم که در خط انتهایی حلقه داخلی بوده از اون خارج میشه و وارد ناحیه بحرانی میشه. و اینجاست که انحصار متقابل نقض می گردد.
(۳۰ دى ۱۳۹۰ ۰۱:۱۶ ق.ظ)shervinrs نوشته شده توسط: چقدر سخت، فکر کنم نیم ساعت طول کشید که بفهمم. البته اگر درست فهمیده باشم.
سناریویی که به نقض انحصار متقابل می انجامه می تونه اینطوری باشه:
فرض کنین که مقدار turn = 0 باشه و هر دو فرایند در قسمت غیر بحرانی (remainder) خودشون باشن. یعنی فرایند ۱ وارد قسمت بحرانی شده باشه و پس از خروج در قسمت غیر بحرانی خودش CPU به فرایند ۰ داده بشه و فرایند ۰ وارد قسمت بحرانی خودش شده باشه و در قسمت غیر بحرانی فرایند ۰ CPU به فرایند ۱ برگشته باشه.
با فرض طولانی بودن قسمت غیر بحرانی فرایند ۱ این فرایند می تونه به ابتدای حلقه While بیرونی برگرده و blocked[1] = true بکنه و وارد حلقه داخلی شده و قبل از turn = id زمانبند به فرایند ۰ سوئیچ کنه. توجه کنین که هنوز مقدار turn تغییر داده نشده و هنوز همون ۰ هست.
حالا فرایند ۰ به ابتدای حلقه بیرونی برگرده و در زمان چک کردن شرط حلقه داخلی (یعنی turn != id) اون رو بصورت ۰ != ۰ ببینه (که false هست) و بدون وارد شدن به حلقه داخلی وارد ناحیه بحرانی خودش (فرایند ۰) بشه و در ناحیه بحرانی زمانبند به فرایند ۱ سوئیچ بکنه. که فرایند یک هم که در خط انتهایی حلقه داخلی بوده از اون خارج میشه و وارد ناحیه بحرانی میشه. و اینجاست که انحصار متقابل نقض می گردد.
با تشکر از جوابتان مطالبی را که گفتید متوجه شدم ولی با قسمتی که ذز بالا زیر ان خط کشیده‌ام مشکل دارم زمانی که وقت cpu دوباره به فرایند ۱ برمی گردد و turn = id می شود فرایند ۱ در جلقه while(blocked(1-id)) گیر می افتد زیرا فرایند ۰ قبل از ورود به ناحیه بحرانی blocked[0] = true کرده است و با این وضغ تا زمانی که فرایند ۰ از ناحیه بحرانی خارح نشده و blocked[0] را false نکند فرایند ۱ در جلقه while(blocked(1-id)) همجنان می ماند
نظر شما چیست
turn = id در حلقه [tex]while(blocked[1-id])[/tex] نیست.
زمانی که دوباره CPU به فرایند ۱ بر می گرده turn = 1 میشه و فرایند به ابتدای [tex]while (id <> turn)[/tex] بر می گرده و چون id = turn هست دیگه شرط while درست نیست و از while خارج میشه. یعنی اصلا دیگه سراغ [tex]while(blocked[1-id])[/tex] نمیره.
(۰۱ بهمن ۱۳۹۰ ۰۵:۴۹ ب.ظ)shervinrs نوشته شده توسط: turn = id در حلقه [tex]while(blocked[1-id])[/tex] نیست.
زمانی که دوباره CPU به فرایند ۱ بر می گرده turn = 1 میشه و فرایند به ابتدای [tex]while (id <> turn)[/tex] بر می گرده و چون id = turn هست دیگه شرط while درست نیست و از while خارج میشه. یعنی اصلا دیگه سراغ [tex]while(blocked[1-id])[/tex] نمیره.
با تشکر از جوابتان ببخشید من بد نوشتم در تمرین مذکور turn = id در حلقهwhile(blocked[1-id)] قرار دارد
قرار نداره. این عکس از ویرایش ششم کتاب هست.
[attachment=2479]
(۰۱ بهمن ۱۳۹۰ ۰۷:۳۳ ب.ظ)shervinrs نوشته شده توسط: قرار نداره. این عکس از ویرایش ششم کتاب هست.
متشکرم کتاب من ویرایش ۴ بود برای همین فرق داشت با این حساب اگر turn = id در حلقه while(blocked[1-id)] قرار گیرد انحصار متقابل رعایت می شود
(۰۲ بهمن ۱۳۹۰ ۱۲:۲۹ ق.ظ)rad.bahar نوشته شده توسط:نه اون کار هم به نظرم مشکل رو حل نمی کنه. چون باعث میشه که شرط پیشرفت نقض بشه. فرض کنین که هر دو در ناحیه غیر بحرانی باشند و turn = 0 باشه فرایند ۱ برگرده و وارد حلقه بشه، اما چون [tex]blocked[0]=false[/tex] هست نمی تونه وارد حلقه داخلی بشه و turn رو تغییر بده و توی حلقه [tex]while(turn <> id)[/tex] می مونه. حالا فرایند ۰ برگرده و [tex]blocked[0]=true[/tex] بکنه و دوباره وارد ناحیه بحرانی بشه. در صورتی که این اتفاق نباید بیفته و فرایندی که در ناحیه غیر بحرانی نباید از ورود فرایندهای دیگه به ناحیه بحرانی ممانعت کنه.(01 بهمن ۱۳۹۰ ۰۷:۳۳ ب.ظ)shervinrs نوشته شده توسط: قرار نداره. این عکس از ویرایش ششم کتاب هست.
متشکرم کتاب من ویرایش ۴ بود برای همین فرق داشت با این حساب اگر turn = id در حلقه while(blocked[1-id)] قرار گیرد انحصار متقابل رعایت می شود.
ضمنا یک مشکل دیگه هم حتی ممکنه بوجود بیاره اینه که فرایند ۰ می تونه در زمان خودش وارد ناحیه بحرانی بشه و دوباره از اون خارج بشه و باعث بشه که فرایند ۱ برای مدتی در حلقه [tex]while(turn <> id)[/tex] گیر کنه. (در حقیقت فرایند ۱ تا زمانی که فرایند ۰ در ناحیه بحرانی کار خودش رو تموم نکنه نمی تونه turn رو تغییر بده)