تبلیغات
دست نوشته ها - نهارخوردن فیلسوف ها | برنامه نویسی + لینوکس و متن باز + روزنوشت + موسیقی

نویسنده: "feeruzy ارسال شده در: " درسی ، لینوکس ، "، زمان ارسال: " 17 آذر 90 ساعت 15:29"
این مسئله‌ای تغییر یافته از مشکلی که بوسیله ادگار دایکسترا مطرح شده است.۵ فیلسوف به نام های ارسطو، کانت، اسپینوزا،مارکس و راسل وقتشان را با تفکر و سرو کردن اسپاگتی سپری می‌کنند.آنها در یک میز دایره‌ای با ۵ جایگاه غذا می‌خورند. برای خوردن غذا هر فیلسوف به به ۲ چنگال نیاز دارد(معرف منابع سیستم).۵ چنگال روی میز است یکی در سمت چپ و دیگری در سمت راست هر جایگاه. هر زمان‌که فیلسوفی نتواند هر دو چنگال را بردارد باید بنشیند و منتظر بماند. غذا خوردن به‌شکل تصادفی روی می‌دهد. پس فیلسوف چنگال را روی میز گذاشته و اتاق غذاخوری را ترک می‌کند. پس از سپری کردن زمانی برای تفکر درباره ماهیت جهان، او دوباره گرسنه شده و این چرخه تکرار می‌شود.می‌توان مشاهده کرد که یک راه‌حل سر راست که از طرف سمافور اجرا شده در معرض بن‌بست قرار دارد.۲ وضعیت بن‌بست وجود دارد :زمانیکه همه فلاسفه دور میز نشسته و هر کدام یک چنگال را در دست گرفته‌اند.یکی زمانیکه چنگال‌ها در دست چپ فیلسوف‌هاست و زمانیکه همه چنگال‌ها در دست راست فیلسوف‌هاست. دوری کردن از بن‌بست بوسیله‌ی وادارکردن هر فیلسوف به داشتن پیمایشی مجزا از بدست گرفتن چنگال‌ها است. به شرطی که هر شخص ابتدا برای برداشتن چنگال سمت چپ صبر کند و سپس برای برداشتن چنگال سمت راست، چرخه ایجاد نمی‌شود.‏pthread مخفف POSIX THreads و POSIX مخفف Portable Operating System Interface یک سری از استانداردها برای سازگاری برنامه‌ها برای سیستم عامل‌های مختلف است. ‏
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

 typedef struct philData {
    pthread_mutex_t *fork_lft, *fork_rgt;
    const char *name;
    pthread_t thread;
    int   fail;
} Philosopher;
‏mutex‏ مخفف ‏Mutual exclusion الگوریتمی است که در برنامه نویسی همزمان برای شبیه سازی استفاده از منابع سیستمی اشتراکی در بخش‌های بحرانی استفاده می‌شود. (بخشی از کد که در آن پردازنده یا نخ‌هابصورت اشتراکی مجوز دسترسی دارند). متغیر های mutex باید توسط pthread_mutex_t اعلان شوند.(در خط ۱۳). داده Philosopher از نوع ساختارداده‌ی philData با مشخصات ذکر شده تعریف و تولید می شود.
int running = 1;
 void *PhilPhunction(void *p) {
    Philosopher *phil = (Philosopher*)p;
    int failed;
    int tries_left;
    pthread_mutex_t *fork_lft, *fork_rgt, *fork_tmp;
در خط ۲۵ سه متغیر mutex اعلان می شوند.
    while (running) {
        printf("%s is sleeping --or thinking\n", phil->name);
        sleep( 1+ rand()%8);
         fork_lft = phil->fork_lft;
        fork_rgt = phil->fork_rgt;
اگر فیلسوفی چنگال چپ و راست را در دست بگیرد پس گرسنه است.
        printf("%s is hungry\n", phil->name);
        tries_left = 2;   /* try twice before being forceful */
        do {
            failed = pthread_mutex_lock( fork_lft);
            failed = (tries_left>0)? pthread_mutex_trylock( fork_rgt )
                                   : pthread_mutex_lock(fork_rgt);
عملیات قفل کردن چنگال بدین صورت است که ابتدا چنگال چپ را قفل کرده سپس اگر متغیر تلاش برای برداشتن چنگال چپ از صفر بزرگتر بود این تابع چنگال راست را قفل می کند.
            if (failed) {
                pthread_mutex_unlock( fork_lft);
                fork_tmp = fork_lft;
                fork_lft = fork_rgt;
                fork_rgt = fork_tmp;
                tries_left -= 1;
            }
        }
در صورت قفل بودن هر دو چنگال ابتدا تابع چنگال چپ را قفل گشایی کرده و سپس آرگومان که چنگال چپ است را با چنگال راستی عوض می کند و تعداد تلاش ها را یکی کم می کند.
     while(failed && running);
         if (!failed) {
            printf("%s is eating\n", phil->name);
            sleep( 1+ rand() % 8);
            pthread_mutex_unlock( fork_rgt);
            pthread_mutex_unlock( fork_lft);
        }
    }
    return NULL;
}
زمانکه تلاشها نا موفق باشد و در حال خوردن باشد، اگر ناموفق نباشد پس در حال خوردن است.و قفل هر دو چنگال باز میشود.
void Ponder()
{
    const char *nameList[] = { "Kant", "Guatma", "Russel", "Aristotle", "Bart" };
    pthread_mutex_t forks[5];
    Philosopher philosophers[5];
    Philosopher *phil;
    int i;
    int failed;
تابع ponder() پنج فیلسوف را مشخص و آرایه چنگال ها را توسط mutex اعلان میکند. سپس آرایه[philosophers[5 را از نوع ساختاری Philosopher تعریف کرد و سپس اشاره‌گری برایش معین می‌سازد.
    for (i=0;i<5; i++) {
        failed = pthread_mutex_init(&forks[i], NULL);
        if (failed) {
            printf("Failed to initialize mutexes.");
            exit(1);
        }
    }
اگر فیلسوفی در حال خوردن غذا نباشد پس دستیابی اشتراکی ای هم وجود نخواهد داشت.
    for (i=0;i<5; i++) {
        phil = &philosophers[i];
        phil->name = nameList[i];
        phil->fork_lft = &forks[i];
        phil->fork_rgt = &forks[(i+1)%5];
        phil->fail = pthread_create( &phil->thread, NULL, PhilPhunction, phil);
    }
اگر برای فیلسوف iام چنانچه چنگال چپ همان چنگال iام باشد ولی چنگال راست چنگالی غیر از چنگال i-1 ام باشد (به‌عبارتی یک چنگال خالی در سمت چپ فیلسوف سمت چپ وجود داشته باشد.) تلاش ناموفق بوده است.
    sleep(40);
    running = 0;
    printf("cleanup time\n");
     for(i=0; i<5; i++) {
        phil = &philosophers[i];
        if ( !phil->fail && pthread_join( phil->thread, NULL) ) {
            printf("error joining thread for %s", phil->name);
            exit(1);
        }
جال اگر در زمان تراکنش ناموفق (در دسترس نبودن هر دو چنگال) فیلسوفی گرسنه باشد سیستم خطای پیوستن فیلسوف را اعلام می‌کند.
    }
}
 int main()
{
    Ponder();
    return 0;
}
‏ Ponder()تابعی است که از ایجاد بن‌بست در این مسئله جلوگیری می‌کند.


آخرین ویرایش در: " 19 آذر 90 ساعت 02:16"
برچسب ها: "سمافور" ، "۵‌فیلسوف" ، "بن‌بست" ، "mutex" ، "posix" ،
در این ارتباط بخوانید: "Dining philosophers problem
نظرات