هماهنگی پردازه ها (Process Synchronization)
فصل 6: همزمانی پردازه ها
پیش زمینه
مساله ناحیه بحرانی
راه حل پترسون
سخت افزار همزمان سازی
سمافور
مسائل کلاسیک همزمان سازی
مانیتور
اهداف
تعریف ناحیه بحرانی
ارائه راه حل های سخت افزاری و نرم افزاری جهت رفع مشکل ناحیه بحرانی
پیش زمینه
دسترسی همزمان به داده های مشترک ممکن است باعث شود که ناسازگاری داده به وجود آید.
سازگاری داده نیازمند مکانیزمی برای اطمینان از اجرای صحیح فرآیندهای همکار است.
فرض کنید می خواهیم راه حلی برای مسئله تولید کننده – مصرف کننده فراهم کنیم به طوری که از تمام ظرفیت بافر استفاده شود. یک راه حل این است که یک شمارنده از نوع عدد صحیح با مقدار اولیه صفر استفاده کنیم که میزان موجودی بافر را مشخص کند. هر بار که یک داده به بافر اضافه می شود، این شمارنده یک واحد افزایش پیدا می کند و هر بار که یک داده از بافر حذف می شود، یک واحد از شمارنده کاسته می شود.
تولید کننده
مصرف کننده
شرایط رقابتی (Race Condition)
counter++ می تواند به صورت زیر پیاده سازی شود:
counter- – می تواند به صورت زیر پیاده سازی شود:
فرض کنید مقدار اولیه counter برابر 5 باشد و دو دستور بالا همزمان اجرا شوند. یک حالت ممکن است:
S0: producer execute register1 = counter {register1 = 5} S1: producer execute register1 = register1 + 1 {register1 = 6} S2: consumer execute register2 = counter {register2 = 5} S3: consumer execute register2 = register2 – 1 {register2 = 4} S4: producer execute counter = register1 {counter = 6 } S5: consumer execute counter = register2 {counter = 4}
مسئله ناحیه بحرانی
فرض کنید یک سیستم دارای n فرآیند بصورت {p0, p1, … pn-1} باشد.
کد مربوط به هر فرآیند دارای قسمتی به نام ناحیه بحرانی می باشد.
فرآیند ها ممکن است اقدام به تغییر متغیرهای سراسری ویا به روزرسانی جدول ها و یا نوشتن فایل کنند.
هنگامی که یک فرآیند در حال اجرا در ناحیه بحرانی است، به هیج فرآیند دیگری نباید اجازه داد که به ناحیه بحرانی اش وارد شود.
هدف این است که یک سری پروتکل (قرارداد) را طوری طراحی کنیم که فرآیند ها به کمک آنها با هم همکاری داشته باشند
هر فرآیند باید در قسمتی به نام ناحیه ورودی درخواست مجوز برای ورود به ناحیه بحرانی دهد.
ممکن است پس از اتمام ناحیه بحرانی کدی به نام ناحیه خروجی را اجرا کند
و در ادامه بخش باقیمانده کد را اجرا کند
ناحیه بحرانی
یک ساختار عمومی برای یک فرآیند P0:
راه حل مسئله بحرانی
یک راه حل برای مسئله بحرانی باید سه نیازمندی را برآورده کند:
راه حل های دو فرآیندی
Algorithm 1
Shared: boolean lock;
Pi:
lock = false;
while (lock);
lock = true;
critical-section
lock = false;
remainder-section
انحصار متقابل
پیشروی
انتظار محدود
راه حل های دو فرآیندی …
Algorithm 2
Shared: int turn;
Pi:
while (TRUE) {
turn = 1-i
while (turn!=i);
critical-section
turn = 1-i;
remainder-section
}
انحصار متقابل
پیشروی
انتظار محدود
راه حل های دو فرآیندی …
Algorithm 3
Shared: boolean flag[2];
Pi:
flag[i]=false;
while (TRUE) {
flag[i]=true;
while (flag[j]);
critical-section
flag[i]=false;
remainder-section
}
انحصار متقابل
پیشروی
انتظار محدود
راه حل پترسون
الگوریتم مناسبی برای توضیح حل مسئله است
یک راه حل دو فرآیندی است
فرض می شود دستورات LOAD و STORE دستورات اتمیکی هستند و در حین انجام آنها هیچ وقفه ای نمی تواند صادر شود
هر دو فرآیند دو متغیر زیر را به اشتراک می گذارند
int turn;
Boolean flag[2]
متغیر turn بیانگر این است که کدام فرآیند می تواند به ناحیه بحرانی اش وارد شود.
آرایه flag بیانگر این است که یک فرآیند، آماده وارد شدن به ناحیه بحرانی اش می باشد.
flag[i]=true نشان دهنده این است که فرآیند pi آماده ورود به ناحیه بحرانی است.
Algorithm for Process Pi
انحصار متقابل
پیشروی
انتظار محدود
سخت افزار همزمان سازی
اکثر سیستم ها راه حل های سخت افزاری برای منطقه بحرانی ارائه می دهند
همه راه حل هایی که در ادامه می آید بر اساس مفهوم قفل شکل گرفته اند.
در این راه حل ها ناحیه بحرانی بوسیله قفل محافظت می شود.
محیط تک پردازنده ای: می تواند رخ دادن وفقه ها را متوقف کرد.
در این صورت کدی که در حال اجرا است مطمئن هستیم قبضه نمی شود.
این راه حل برای محیط های چند پردازنده ای عملی نیست
تعداد زیادی از سیستم های امروزی دستورات سخت افزاری ویژه ای دارند که اتمیک هستند
اتمیک: غیر تجزیه پذیر، در حین اجرای آن وقفه ای رخ نمی دهد
1. دستوری به منظور خواندن و تغییر دادن محتویات یک متغیر TestAndSet()
2. دستوری به منظور جابجایی محتویات دو متغیر Swap()
راه حل مسئله بحرانی بوسیله فقل ها
دستور TestAndndSet
تعریف:
TestAndSet()راه حل بوسیله دستور
Shared Boolean variable lock., initialized to false.
Solution:
دستور Swap
تعریف:
void Swap (boolean *a, boolean *b)
{
boolean temp = *a;
*a = *b;
*b = temp:
}
راه حل بوسیله دستور Swap
Share Boolean variable lock initialized to FALSE; Each process has a local Boolean variable key
Solution:
do {
key = TRUE;
while ( key == TRUE)
Swap (&lock, &key );
// critical section
lock = FALSE;
// remainder section
} while (TRUE);
راه حلی برای انحصار متقابل و انتظار محدود بوسیله TestandSet()
do {
waiting[i] = TRUE;
key = TRUE;
while (waiting[i] && key)
key = TestAndSet(&lock);
waiting[i] = FALSE;
// critical section
j = (i + 1) % n;
while ((j != i) && !waiting[j])
j = (j + 1) % n;
if (j == i)
lock = FALSE;
else
waiting[j] = FALSE;
// remainder section
} while (TRUE);
سمافور
یک سمافور یک متغیر از نوع عدد صحیح است.
تنها از طریق دو دستور تجزیه ناپذیر wait() و signal() قابل دسترسی است
عمل wait() را با حرف P و عمل signal() را با حرف V نمایش می دهند
پیچیدگی کمتری نسبت به سایر الگوریتم ها دارد
wait(S){
while S <= 0
; // no-op
S–;
}
signal(S) {
S++;
}
استفاده از سمافور
سمافور شمارشی: مقدار سمافور می تواند در بازه ای نامحدود تغییر یابد
سمافور باینری: مقدر عدد صحیح سمافور فقط می تواند صفر یا یک باشد
به نام mutex lock نیز شناخته می شوند
می توان یک سمافور شمارشی را با تعدادی سمافور باینری پیاده سازی کرد.
انحصار متقابل را فراهم می کند:
Semaphore mutex; // initialized to 1
do {
wait (mutex);
// Critical Section
signal (mutex);
// remainder section
} while (TRUE);
استفاده از سمافور
بوسیله سمافور می توان بسیاری از مسائل همزمانی را حل کرد
فرض کنید دو فرآیند P1 و P2 داریم و نیازمند آنیم که S1 قبل از S2 اتفاق بیفتد
Semaphore synch; // initialized to 0
پیاده سازی سمافور
باید ضمانت کرد که هیچ دو فرآیندی نمی توانند دستورات wait () و signal() یک سمافور را در یک زمان انجام دهند.
با پیاده سازی موجود: یک قسمت busy waiting در پیاده سازی ناحیه بحرانی وجود دارد.
ولی پیاده سازی کد کوتاه است
اگر ناحیه بحرانی کم اتفاق بیفتد این انتظار چندان مهم نیست
ولی ممکن است برنامه هایی زمان زیادی را در ناحیه بحرانی باشند و بنابراین این راه حل نمی تواند پاسخ مناسبی باشد
پیاده سازی سمافور بدون Busy waiting
به ازای هر سمافور یک صف انتظار وجود دارد. هر فرآیند در صف انتظار شامل دو داده می باشد
یک مقدار صحیح به نام value
اشاره گر به رکورد بعدی در لیست انتظار
در کل دو عملیات وجود دارد
block(): فرآیندی که این عملیات را صدا زده است را در صف انتظار مربوطه قرار می دهد
wakeup(): یک فرآیند از صف انتظار برداشته و آن را در صف آماده (ready queue) قرار می دهد
پیاده سازی سمافور بدون Busy waiting ….
wait(semaphore *S) {
S->value–;
if (S->value < 0) {
block(); // add this process to S->list;
}
}
signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
wakeup(P); // remove a process P from S->list;
}
}
بن بست (Deadlock) و گرسنگی (Starvation)
بن بست: دو یا چند فرآیند به طور نامحدودی منتظر رخدادی هستند که باید توسط یکی از فرآیند های موجود درصف انتظار رخ دهد
فرض کنید S و Q دو سمافور با مقدار اولیه 1 باشند
P0 P1
wait (S); wait (Q);
wait (Q); wait (S);
. .
. .
. .
signal (S); signal (Q);
signal (Q); signal (S);
گرسنگی: یا انسداد نامعین. یک فرآیند ممکن است هرگز از صف انتظار سمافور حذف نشود. اگر از صف LIFO (آنکه آخر آمده اول خارج شود)، استفاده شود، این اتفاق ممکن است بیفتد.
وارونگی اولویت: هنگامی اتفاق می افتد که فرآیند های با اولویت پایین یک قفل که مورد نیاز فرآیند های با اولویت بالا است را در اختیار داشته باشند
مسائل کلاسیک همزمانی
مسائل کلاسیک حوزه همزمانی برای تست روش های جدید ارائه شده بکار می رود:
مسئله بافر محدود
مسئله خوانندگان – نویسندگان
مسئله غدا خوردن فیلسوفان
مسئله بافر محدود
N بافر، هر کدام امکان نگه داری یک داده را دارد
یک سمافور به نام mutex و با مقدار اولیه 1
یک سمافور به نام full و با مقدار اولیه 0
یک سمافور به نام empty و با مقدار اولیه N
مسئله بافر محدود ….
ساختار فرآیند تولید کننده
do {
// produce an item in nextp
wait (empty);
wait (mutex);
// add the item to the buffer
signal (mutex);
signal (full);
} while (TRUE);
مسئله بافر محدود ….
ساختار فرآیند مصرف کننده
do {
wait (full);
wait (mutex);
// remove an item from buffer to nextc
signal (mutex);
signal (empty);
// consume the item in nextc
} while (TRUE);
مسئله خوانندگان- نویسندگان
یک پایگاه داده میان تعدادی از فرآیند های همزمان به اشتراک گذارده می شود.
خوانندگان : فقط می توانند داده ها را بخوانند. آنها نمی توانند هیچ گونه به روزرسانی داشته باشند
نویسندگان: هم می توانند بخوانند و هم می توانند بنویسند
مسئله: اجازه می دهیم چندین خواننده به طور همزمان بتوانند داده ها را بخوانند. ولی فقط یک نویسنده اجازه دارد که در یک زمان به داده های مشترک دسترسی داشته باشد.
نسخه های مختلف مسئله خوانندگان، نویسندگان
اولین ویرایش: هیچ خواننده ای منتظر نخواهد ماند مگر اینکه نویسنده ای قبل از آن مجوز استفاده از شی مشترک را بدست آورده باشد.
دومین ویرایش: همین که نویسنده ای آماده شد، در اسرع وقت عملیات نوشتن خود را انجام دهد
راه حل هر یک از این دو مسئله می تواند منجر به گرسنگی شود
داده های مشترک
پایگاه داده
یک سمافور به نام mutex و با مقدار اولیه 1 (به منظور حفط انحصار متقابل به هنگام دسترسی به متغیر readcount)
یک سمافور به نام wrt و با مقدار اولیه 1
یک عدد صحیح به نام readcount و با مقدار اولیه 0 (تعداد فرآیندهای در حال خواندن)
مسئله خوانندگان- نویسندگان (ویرایش اول)
ساختار فرآیند نویسنده
do {
wait (wrt) ;
// writing is performed
signal (wrt) ;
} while (TRUE);
مسئله خوانندگان- نویسندگان …
ساختار فرآیند خواننده
do {
wait (mutex) ;
readcount ++ ;
if (readcount == 1)
wait (wrt) ;
signal (mutex)
// reading is performed
wait (mutex) ;
readcount — ;
if (readcount == 0)
signal (wrt) ;
signal (mutex) ;
} while (TRUE);
مسئله فیلسوفان خورنده
فیلسوفان زندگیشان را به فکر کردن و خوردن می گذارنند
زمانی که یک فیلسوف فکر می کند با فیلسوف همسایه اش تعاملی ندارد
هر گاه فیلسوفی گرسنه شد سعی می کند دو تا قاشقی که به او نزدیکتر است بر می دارد و شروع به غذا خوردن می کند
برای غذا خوردن به هر دو قاشق نیاز دارد و پس از خوردن هر دو را رها می کند.
داده مشترک
سینی برنج (یک سری داده)
یک آرایه سمافور 5 تایی به نام chopstick[5] و با مقدار اولیه هر کدام 1
مسئله فیلسوفان خورنده …
ساختار فرآیند فیلسوف i ام
do {
wait ( chopstick[i] );
wait ( chopStick[ (i + 1) % 5] );
// eat
signal ( chopstick[i] );
signal (chopstick[ (i + 1) % 5] );
// think
} while (TRUE);
انحصار متقابل
بن بست
راه حل های مختلف مسئله غذا خوردن فیلسوفان
اجازه دهیم حداکثر چهار فیلسوف همزمان دور میز قرار گیرند
اجازه دهیم فیلسوف ها فقط در صورتی که هر دو چوب موجود باشند، چوب های غذاخوری را برداند
از راه حل نامتقارن استفاده شود، یک فیلسوف با شماره فرد، ابتدا چوب سمت چپ و سپس چوب سمت راست خودش را بردارد و فیلسوف با شماره زوج برعکس.
هر راه حلی برای این مسئله باید تضمین کند نه بن بست بوجود می آید و نه فیلسوفی دچار گرسنگی شود
مشکلات استفاده از سمافور
استفاده اشتباه از سمافور:
signal (mutex) …. wait (mutex)
wait (mutex) … wait (mutex)
Omitting of wait (mutex) or signal (mutex) (or both)
مانیتور
یک راه حل انتزاعی سطح بالا که مکانیسم کارا و راحتی را برای همزمان سازی فرآیند ها فراهم می سازد.
فقط یک فرآیند می تواند در یک زمان در داخل مانیتور فعال باشد.
monitor monitor-name
{
// shared variable declarations
procedure P1 (…) { …. }
…
procedure Pn (…) {……}
Initialization code ( ….) { … }
…
}
طرح کلی یک مانیتور
متغیرهای شرطی
condition x, y;
دو عملیات بر روی متغیرهای شرطی قابل انجام است
x.wait () فرآیندی که این عمل را فراخوانی کند به حالت تعلیق در می آید.
x.signal (): یکی از فرآیندهایی (اگر باشد) که x.wait () را صدا زده است از حالت تعلیق خارج می شود. اگر هیچ فرآیند در حالت تعلیق نباشد، این دستور کار خاصی انجام نمی دهد
مانیتور با متغیر های شرط
راه حل فیلسوفان خورنده با استفاده از مانیتور
monitor DP
{
enum { THINKING; HUNGRY, EATING } state[5] ;
condition self[5];
void pickup (int i){
state[i] = HUNGRY;
test(i);
if (state[i] != EATING)
self [i].wait;
}
void putdown (int i){
state[i] = THINKING;
// test left and right neighbors
test((i + 4) % 5);
test((i + 1) % 5);
}
راه حل فیلسوفان خورنده با استفاده از مانیتور …
void test (int i) {
if ( (state[(i + 4) % 5] != EATING) &&
(state[i] == HUNGRY) &&
(state[(i + 1) % 5] != EATING) ) {
state[i] = EATING ;
self[i].signal () ;
}
}
initialization_code() {
for (int i = 0; i < 5; i++)
state[i] = THINKING;
}
}
راه حل فیلسوفان خورنده با استفاده از مانیتور …
هر فیلسوف i تابع pickup() و putdown() را به صورت زیر صدا می زند
DiningPhilosophters.pickup (i);
EAT
DiningPhilosophers.putdown (i);
پیاده سازی مانیتور با استفاده از سمافور
متغیرها
semaphore mutex; // (initially = 1)
semaphore next; // (initially = 0)
int next-count = 0;
هر تابع F جایگزین می شود با:
wait(mutex);
…
body of F;
…
if (next_count > 0)
signal(next)
else
signal(mutex);
بدین ترتیب حفظ انحصار متقابل درون مانیتور تضمین می شود
پیاده سازی مانیتور با استفاده از سمافور
برای هر متغیر شرط x داریم:
semaphore x_sem; // (initially = 0)
int x-count = 0;
x.signal()
if (x-count > 0) {
next_count++;
signal(x_sem);
wait(next);
next_count–;
}
x.wait()
x-count++;
if (next_count > 0)
signal(next);
else
signal(mutex);
wait(x_sem);
x-count–;
پایان