الگوریتمهایی برای حل ناحیه بحرانی یا الگوریتم سمافور یا....

[whitehat]

اگر می خواهید از این سایت بگیرید باید ابتدا Sun Download Manager را نصب کنید .
نسخه 5.0 را می توانید از اینجا بگیرید
فکر می کنم تاپیک داره از بحثش خارج می شود، لطفا سوالات را در مورد موضوع تاپیک مطرح کنید
با تشکر

[نغمه]

من بالاخره جاوا را نصب کردم و پنجره اصلی شبیه ساز باز شد حالا چه جوری باید پروسس ها را به صورت ورودی به این شبیه ساز بدم برای زمانبندی آنها؟

[whitehat]

شما باید با استفاده از فایل های همراه با این نرم افزار این کار را انجام دهید، برای اطلاعات بیشتر به اینجا بروید

[نغمه]

من این راهنما را خوندم و فایلهای مربوطه را دانلود کردم و صفحه Process Scheduling Simulator هم باز شد ولی نمی دونم چه جوری باید در این شبیه ساز یک experiment جدید تعریف کنم

[whitehat]

من متوجه منظور شما نشدم،در کل شما باید دو فایل داشته باشید
فایل extension .exp و فایل extension .run
بعد آنها را می توانید جایگزین فایلهای موجو در دایرکتوری کنید،یا خود آنها را ویرایش کنید
بعد با استفاده از گزینه Run آنها را اجرا کنید

[نغمه]

من ps.zip را دانلود کردم 5 فایل زیر درون آن بود runps.bat را که اجرا می کنم پنجره ای باز می شه که بعد از این دیگه نمی دونم باید چی کار کنم!
PS.jar
Jeli.jar
psconfig
myrun.run
myexp.exp
runps.bat

[whitehat]

شما باید تغییرات خود را در فایل های myrun.run و myexp.exp اعمال کنید

[ahang_ziba]

سلام
من می خوام الگوریتم first fit را کد نویسی کنم اما در پیاده سازی الگوریتمش مشکل دارم میشه منو راهنمایی کنید؟
با تشکر

[whitehat]

چه مشکلی با این الگوریتم دارید؟ کافیه مثلا یک آرایه در نظر بگیرید که هر کدام از خانه های آنها دارای یک تگ استفاده شده یا نشده باشد، برای تخصیص آن از ابتدا شروع به خواندن آرایه کنید و به اولین خانه خالی که رسیدید تگ آنرا یک کنید
(سعی کنید سوالهایتان را در باره موضوع تاپیک بپرسید)

[ahang_ziba]

سلام
آخه آرایه خونه هاش همه 1 ظرفیت ثابت دارند در حالیکه شاید فضاهای مورد درخواست کاربر زیادتر از مقدار از پیش تعیین شده آرایه باشه؟
با تشکر

[نغمه]

تمام الگوریتمهای مربوط به مدیریت حافظه و مدیریت پروسس و زمانبندی را می توان با زبان c پیاده سازی کرد؟

[whitehat]

آخه آرایه خونه هاش همه 1 ظرفیت ثابت دارند در حالیکه شاید فضاهای مورد درخواست کاربر زیادتر از مقدار از پیش تعیین شده آرایه باشه؟

دوست عزیز ابتدا شما باید مشخص کنید می خواهید از قطعه بندی استفاده کنید یا صفحه بندی؟

تمام الگوریتمهای مربوط به مدیریت حافظه و مدیریت پروسس و زمانبندی را می توان با زبان c پیاده سازی کرد؟

هر الگوریتمی را می توان با زبانهای مختلف پیاده سازی کرد!

[ahang_ziba]

با سلام
من متوجه دلیل شما از این سوال نشدم ولی واسه نوشتن برنامه قطعه بندی را ترجیح میدم
میشه در مورد الگوریتم هایی که نوشتید(خوانندگان و نویسندگان و آرایشگر ) یه توضیح بدید؟(در مورد متغیرهاو...)
ممنون میشم
با تشکر

[whitehat]

من می خواستم ببینم می خواهید نحوه پیاده سازی به چه روش باشه، بهر حال شما باز هم می توانید از یک آرایه استفاده کنید با این تفاوت که هر برنامه شما می تواند به تعدادی دلخواه از خانه های آرایه شما را بگیرد و نحوه کار بازهم به شکل قبل می شود. ولی اگر می خواهید دقیقا چیزی که در حافظه انجام می شود را پیاده سازی کنید (که بعید اساتید سیستم عامل این چنین چیزی را بخواهند) باید به ازای هر پیج مثلا یک آرایه N بایتی Allocate کنید و مدیریت حافظه آنرا خود بر عهده بگیرید.اگر فقط می خواهید از قطعه بندی استفاده کنید مثلا N باید به به عنوان یک پیج در نظر بگیرید سپس فرض کنید که هر بایت با 0 یعنی خالی و با یک یعنی پر نشان داده شده سپس هر برنامه باید بداند که در کجا ها نوشته ،پس باید برای هر برنامه یک لیست پیوندی در نظر بگیرید مو قعیت برنامه در حافظه را نشان می دهد ،حال هر برنامه جدید می بایست برای ذخیره شدن در حافظه این فضا را از ابتدا بخواند (برای الگوریتم اول First Fit) هر جا فضای خالی پیدا کرد بنویسد ،برای این کار شما باید یک لیست پیوندی برای فضاهای خالی نیز داشته باشد که کارتان تقریبا خیلی سخت میشه!
در مورد الگوریتم ها تقریبا توضیحات کافی داده شده اگر مورد خاصی را مد نظر دارید آنرا عنوان کنید تا توضیح دهم،ضمن اینکه بسیاری از این الگوریتم ها بطو کامل در کتابهای سیستم عامل وجود دارد
موفق باشید

[ahang_ziba]

سلام
اجازه بدید من سوالمو بصورت عددی بیان کنم تا شما بتونید منو راهنمایی کنید
فرض کنید که من یک آرایه از نوع int تعریف کنم و کاربر فضاهایی مثل ((44770-54852-...))(البته زبان مورد نظر من c است) درخواست کنه حالا چطور میشه درخواستهای کاربر را با این روش جواب داد؟
در مورد الگوریتمهای (آرایشگر - خوانندگان و نویسندگان) من توضیحی در مورد هدف از تعریف متغیر ها می خواستم
باتشکر

[whitehat]

در الگوریتم های تخصیص حافظه این سیستم عامل است که فضای مورد نیاز برنامه را به برنامه تخصیص می دهد، بعضی از برنامه های هستند که برنامه از حافظه Heap یا حتی پشته می تواند فضایی را درخواست نماید که این مربوط به الگوریتم های تخصیص حافظه نمی شود، شما برای شبیه سازی این الگوریتم ها خودتان باید فرضیاتی را لحاظ کنید ، برای روشن شدن موضوع مثالی می زنم، فرض کنید آرایه ای 10 عنصری داشته باشید که حافظه شما را تشکیل می دهد. حال فرض کنید پروسه های زیر وارد می شوند
P1....5
p2....4
p1...Dispose
p3...3
p4....3
p3...Dispose
p5....1
حال نحوه پر شدن آرایه باید به شکل زیر باشد(O به منزله جای خالی در آرایه و * ناحیه اشغال شده است)
OOOOOOOOOO
*****OOOOO
*********O
OOOOO****O
***OO****O
p4 در اینجا Suspend می شود
****O****O
شما باید با برنامه ای که می نویسید برای این سناریو ، همچین چیزی را به عنوان خروجی در آورید.

در مورد الگوریتمهای (آرایشگر - خوانندگان و نویسندگان) من توضیحی در مورد هدف از تعریف متغیر ها می خواست

لطفا به شماره پست و نام متغیر مورد نظرتان اشاره کنید

[ahang_ziba]

با سلام
خوب مشکل من هم در پیاده سازی این الگوریتم همینه!
من نمیدونم چطور این فضا رو شبیه سازی کنم تا وقتی 1 فضا توسط درخواست کاربر اشغال شد و از همون خانه اگر مقداری فضا باقی ماند و الگوریتم برای بار بعد که search فضای خالی رو از سر میگیره چطور دوباره از فضای آن خانه خالی استفاده کنه؟
(مثال عددی: مثلا خانه اول ما 100 تا فضا داره و کاربر 60 تا تقاضا میکنه خوب از همین خانه اول 40 تا باقی میمونه و برای درخواست دوم کاربر این فضا هم باید به عنوان فضای خالی در نظر گرفته بشه تا مثلا اگر کاربر تقاضای فضای 40 یا کمتر را داد همین فضای باقی مانده به درخواست دومش تخصیص یابد )
تا اونجا که من میدونم این مطلب بوسیله آرایه قابل پیاده سازی نیست
اگه میشه منو سریعتر راهنمایی کنید چون من روی این مطلب خیلی فکر کردم ولی چیزی دستگیرم نشد؟؟؟؟
با تشکر

[whitehat]

مثال عددی: مثلا خانه اول ما 100 تا فضا داره ...

منظور شما ازخانه چیه؟
مثالی که من زدم برای یک صفحه است ،حال اگر می خواهید چند صفحه داشته باشید می توانید یک ماتریس به جای یک آرایه تعریف کنید که هر سطر یا ستون آن یک صفحه باشد

[ahang_ziba]

سلام
شما گفتید واسه پیاده سازی میشه از آرایه استفاده کرد منظور من هم از خانه . خانه اول آرایه بود - حالا اگر میشه سوال قبل منو با این فرض جواب بدید
با تشکر

[whitehat]

خب با این حساب شما فرض کنید هر صفحه حافظه معادل یک آرایه n تایی است ، و هر برنامه می تواند به تعداد k خانه حافظه (k<n) فضا اشغال کند،حال باید سناریوئی مانند بالا تعریف کنید و سپس سعی کنید آنرا پیاده سازی نمائید

(فکر کنم بحث تا حدودی داره از مسیر اصلی خارج می شود ،اگر شما سوالاتی در مورد الگوریتم های تخصیص حافظه دارید در تاپیکی مجزا بپرسید،باتشکر)

[Mahdi.Kiani]

خواستم تاپیک جدید بزنم اما دیدم اینجا در مورد مسئله آرایشگر منصف و غیر منصف بحث شده است گفتم همین جا بنویسم
البته یه نکته بگم وقتی که الگوریتم های آرایشگر منصف و غیر منصف را دیدم که توسط یکی از کاربران حل شده بود، خیلی خوشحال شدم. چون خیلی وقت پیش بهش نیاز داشتم و با هر جونکندنی بود نوشتمش..اخه اون موقع ها زیاد از برنامه نویسی خوشم نمی اومد . اما خوب بلاخاره نوشتمش.. حالا از این حر فا بگذریم
سناریوی زیر را در نظر بگیرید
می خواهیم مسئله ارایشگر منصف را در یک محیط شبکه حل کنیم
بدین صورت که یک برنامه سمت سرور داریم و یک برنامه هم که طبیعتا سمت کلاینت نوشته میشه
تمامی سمافور ها بایستی روی برنامه سرور تعریف شوند. و یک thread مسئول مدیریت درخواست هاست
بقیه thread های مربوط به آرایشگران و آرایشگاه و مشتریان و .... بایستی روی کلاینت تعریف شوند.
حال از سمت کلاینت درخواست ها برای سمافور هایی سمت سرور ارسال میشه. اون thread ای که گفتم در سمت سرور مسئول پاسخگویی به این درخواست هاست. بدین صورت که اگه سمافور مورد نظر آزاد بود به درخواست پاسخ داده میشه و اگه مشغول بود، thread درخواست کننده باید wait بمونه تا سمافور ازاد بشه و سپس به درخواستش پاسخ داده بشه

فکر می کنم تنها نکته ای که در این برنامه نسبت به برنامه آرایشگر منصف در حالت معمولی وجود داره این هست که کلیه درخواست ها در غالب متن به سمت سرور فرستاده می شوند و جواب ها که می تونه پاسخ به درخواست و یا waint کردن درخواست باشه، باز هم در غالب متن و به سمت کلاینت فرستاده میشود.
این مسئله یعنی فرستادن درخواست ها در غالب متن و گرفتن پاسخ های مناسب هم با برنامه نویسی سوکت قابل حل است. منتها مراتب مسئله اصلی جدا کردن سمافور ها و بردن اونا در سمت سرور هست. در واقع در حالت عادی thread های مشتریان و ... با سمافور ها در گیر هستند که جدا کردن اونا و بردن اونا روی دو تا سیستم جدا یکمیکار را مشکل می کنه

اگه از دوستان کسی پیاده سازی در این مورد داشته را ممنون میشم بگه
اگه نمونه کد هم باشه که خیلی بهتره
ممنون

[mojgan.net]

سلام
من یه کتابی رو بهتون معرفی می کنم که تمام این الگو ریتم ها رو داخل اون نوسینده اون کتاب نوشته.
اگر هم این کتاب رو نتونستید پیدا کنید من براتون اون رو می تونم پست کنم.
((سیستم های عامل_نویسنده مهندس اکبر پور)) این کتاب رفرنس این ترم من واسه درس سیستم عامل و استاد این درس هم نویسنده همین کتاب اگه بازم هم سوالی داشتید به من بگید تا از ایشون بپرسم و یا کتاب و واستون پست کنم

[Mahdi.Kiani]

سلام
من یه کتابی رو بهتون معرفی می کنم که تمام این الگو ریتم ها رو داخل اون نوسینده اون کتاب نوشته.
اگر هم این کتاب رو نتونستید پیدا کنید من براتون اون رو می تونم پست کنم.
((سیستم های عامل_نویسنده مهندس اکبر پور)) این کتاب رفرنس این ترم من واسه درس سیستم عامل و استاد این درس هم نویسنده همین کتاب اگه بازم هم سوالی داشتید به من بگید تا از ایشون بپرسم و یا کتاب و واستون پست کنم

اگه بتونین همون الگوریتمی که میگین مخصوص این مسئله هست را پست کنین ممنون می شم

[animove]

می خواستم بدونم که خود #c هم امکاناتی برای برنامه نویسی همروند داره ؟
مساله تولید کننده ومصرف کننده رو با سمافور یا با مانیتور چطوری میشه با #c حل کرد؟

[MozenAbasi]

الگوریتم دکر نگارش 5 را برای بیش از 2 پروسسور می خواستم . ممنون

[mary81]

اگر ممكنه يك نرم افزاره همروند برام بزارين
هر چي سعي كردم نتونستم download كن

[whitehat]

از اينجا دانلود كنيد

[ali_mp64]

ميشه يه لينك دانلود ديگه بزارين ؟

[whitehat]

لینک مشکلی نداره ، با دانلود منیجر ها دانلود نکنید:)
بر روی اینجا در پست قبل کلیک کنید

[paryie_dariaii]

سلام.خسته نباشید.کسی می تونه همین برنامه رو با مانیتور برا من بزاره؟ممنون میشم.من اصلا مانیتور رو یاد نگرفتم.حتی الامکان با جاوا.با سمافور تو جاوا اینجوری میشه

class Semaphore {

    private int c;

    public Semaphore(int n) {

        this.c = n;

    }

    public synchronized void WAIT() {

        while(c == 0) {

            try {

              wait();



            } catch (InterruptedException e) {

                //keep trying

            }

        }

        c--;

    }



    public  synchronized  void SIGNAL() {

        C++‎;

        notify(); //alert a thread that's blocking on this semaphore

          }

}

        int loop=0;

        int[] queue=new int[20];

        Semaphore max_capacity=new Semaphore(20);

        Semaphore sofa=new Semaphore(4);

        Semaphore barber_chair=new Semaphore(3); 

        Semaphore coord=new Semaphore(3);

        Semaphore mutex1=new Semaphore(1);

        Semaphore mutex2=new Semaphore(1);

        Semaphore cust_ready=new Semaphore(0);

        Semaphore leave_b_chair=new Semaphore(0);

        Semaphore payment=new Semaphore(0);

        Semaphore receipt=new Semaphore(0);

        Semaphore[] finished=new Semaphore[50];

        int count; 

 //class barberShop{

    // public barberShop(){}



public class  Cashier extends Thread{

    public void run(){

    do{

       payment.WAIT();

       coord.WAIT();

       System.out.println("Cashier Accept The Payment");

       coord.SIGNAL();

       receipt.SIGNAL();

       yield();

    }while(true);



    }

}

public class Customer extends Thread{

    public void run(){

        int i;

        for(i=0;i<50;i++)

            finished[i]=new Semaphore(0);

    int custnr; 

    max_capacity.WAIT();

    System.out.println("Customer Enter The Barbery");

    mutex1.WAIT();

    count++;

    custnr= count; 

    mutex1.SIGNAL(); 

    sofa.WAIT();

    System.out.println("Customer Sitting On Bench");

    barber_chair.WAIT();

    System.out.println("Customer Getting Up From Bench");

    sofa.SIGNAL();

    System.out.println("Customer Sitting On The Barber Chair");

    mutex2.WAIT();

    if (loop<19) queue[loop++]=custnr;

    cust_ready.SIGNAL();

    mutex2.SIGNAL();

    finished[custnr].WAIT();

    System.out.println("Customer Leave The Barber Chair");

    leave_b_chair.SIGNAL();

    System.out.println("Customer Pay The Payment"); 

    payment.SIGNAL();

    receipt.WAIT();

    System.out.println("Customer Leave The Shop");

    max_capacity.SIGNAL(); 

    yield();

    }

}



public class Barber extends Thread{

    public void run(){

    int b_cust;

    do{

        cust_ready.WAIT();

        mutex2.WAIT();

        if (loop>0){

            for(b_cust=0;b_cust<loop;b_cust++){

                queue[b_cust-1]= queue[b_cust];

                b_cust= b_cust+1;

                loop--;

            }

        }

        mutex2.SIGNAL();

        coord.WAIT();

        System.out.println("Baraber Is Cut The Hair");

        coord.SIGNAL();

      //  finished[b_cust].SIGNAL();

        leave_b_chair.WAIT();

        barber_chair.SIGNAL();

        yield();

    }while(true);



    }

}

Int main()

{

int z;

        int j;

        Customer cust=new Customer();

        Barber barb=new Barber();

        Cashier cash=new Cashier();

        for( j=0;j<50;j++)

        {

          cust.start();  

        }

        for(z=0;z<3;z++)

        {

           barb.start();

        }

        cash.start();

}

با سپاس

[sarasattari]

سلام ميشه يكم بيشتر در مورد baci و توابع اون توضيح بديد

[Saeed_script]

مفاهیم سیستم عامل مانند mutual exclusion , Deadlock, Semaphore,Monitor
همگی در کتابخانه دات نت تعریف شده اند ، و می توان برای شبیه سازی و پیاده سازی الگوریتم های سیستم عامل از آنها استفاده کرد.
مثلا می توانید در بخش فناوری مایکروسفت در این سایت ، طریقه باز کردن سورس .net 3.5 را یاد بگیرید و آنگاه به سورس اشیائی همچون mutex و semaphore و monitor نگاه کرده و با طرز کار متد های آن آشنا شوید.

[whitehat]

سلام ميشه يكم بيشتر در مورد baci و توابع اون توضيح بديد

اگر به صفحات اولیه همین پست مراجعه کنید می توانید مطالب مفیدی را در رابطه با BACI و مثالهایی از الگوریتم هایی که در آن پیاده سازی شده را پیدا کنید

[saruneh]

مشگل اینجاست که در BACI نمیشه از Struct استفاده کرد!

int i=0;





int in=0;

int out=0;

int size=3;

int queue[size];

struct new_semaphore

{

int count;

int queue[100];

};

atomic void new_wait(new_semaphore& s)

{

s.count--;

if(s.count<0)

{ 

s.queue[in]=which_proc();

in=(in+1)%size;

suspend(); 

}

}

atomic void new_signal(new_semaphor& s)

{

s.count++;

if(s.count<=0)

{
 

revive(s.queue[out]);

out=(out+1)%size;

}

}

void new_initial(new_semaphore s,int i)

{

s.count=i;

}

[beirami]

می خوام مساله خوانندگان و نویسندگان یا تولید کننده ومصرف کننده رو بدون ترد بنویسم میشه کمکم کنید؟؟؟چه جوری همگامی رو در ویندوز اجرا کنم ؟

[manager]

می خوام مساله خوانندگان و نویسندگان یا تولید کننده ومصرف کننده رو بدون ترد بنویسم میشه کمکم کنید؟؟؟چه جوری همگامی رو در ویندوز اجرا کنم ؟

اصل مسئله IPC با همگامی فرآیندها به وجود می یاد تو ویندوز هم شما به 2 تا ابزار یعنی Thread و Process می تونی همگامی رو ایجاد کنی. پیشنهاد می کنم با همون Thread این کار رو انجام بدی وگرنه اسیر می شی... حالا چرا نمی خوای با ترد این کار رو بکنی ؟

[va_sha_114]

ُسلام خسته نباشید . نمیدونم بعد این همه وقت که این تاپیک غیر فعال بوده الان کسی پیدا میشه جواب بده یا نه اما می خواستم ببینم کسی در مورد مسئله پل در سیستم عامل چیزی شنیده؟
این مسئله به این صورته که یک پل را تصور کنید که بی نهایت ماشین یک طرف و بی نهایت ماشین طرف دیگه هستند و در هر زمان فقط از یک طرف ماشین می تواند رد شود می خواهیم 10 تا ماشین از یک طرف و 10 تا دیگه از طرف دیگه بروند که این ساده ترین حالته ، حالا اگه یک طرف خالی بود طرف دیگه منتظر 10 ماشین انطرف نشه و همین طور ماشین رد بشه و اگه مثلا 3 تا ماشین یک طرف بود و بی نهایت طرف دیگه بعد اینکه 3 تا ماشین از آن طرف رد شد و ماشین ها تمام شد منتظر نباشد که حتما 10 تا ماشین رد بشه چون دیگه ماشینی نیست و از طرف دیگه همینطور ماشین رد بشه
اینا می خوام با BACI پیاده سازی کنم اما اگه کسی شبه کد برام بگه ممنون میشم چون می خوام خودم پیاده سازی کنم اما الگوریتمشا موندم چطوریه؟؟؟؟؟؟؟؟

[علی سبزقبایی]

سلام من زیاد آشنایی با این موضوع ندارم اگر کسی میتونه به طور کامل برام توضیح بده

[whitehat]

سلام من زیاد آشنایی با این موضوع ندارم اگر کسی میتونه به طور کامل برام توضیح بده

در این تاپیک به موضوع های مختلفی اشاره شده که هر کدام توضیح کافی دارند، ابتدا صفحات قبل را مطالعه کنید و در صورت نیاز سوال خود در مورد موضوع مورد نظر بیان کنید

[va_sha_114]

مثل اینکه کسی بلد نبود
اما خودم فهمیدم چطوریه
گفتم توضیح بدم شاید به درد کسی بخوره
برای این کار باید از 5تا سمافور باید استفاده کنی 2تا برای مشخص کردن جهت ها و یکی برای هماهنگ کننده و 2تا هم برای حرکت از 2 جهت مختلف و چک می کنی جهت را تشخیص میدی و هماهنگ کننده را Wait می کنی و حرکتت را شروع می کنی