عنوان صفحه

مقدمه .................................................................................. 1

1- فصل اول - مفاهيم اوليه .............................................................................................. 2

1-1. سيستم های توزيع شده .............. 3

1-1-1. مزایا و معایب سيستم های توزيع شده................ 3

1-2. انگیزش ....... 6

1-3. مراحل کلی تبديل برنامه ترتيبی به برنامه توزيع شده ................ 8

1-4. ساختار پايان نامه................... 9

1-5. جمع بندي ........... 10

2- فصل دوم - تکنيک ها و ابزارهای مرتبط ....................................................................................................... 11

2-1.ابزارهاي تبادل پيام در مقايسه با حافظه اشتراکي توزيع شده......................................................................... 13

2-1-1. تبادل پيام ......................................................................................................................................... 13

2-1-2. خصوصيات مطلوب يک سيستم تبادل پيام........................................................................................ 14

2-1-3. طبقه بندي ابزارهاي تبادل پيام........................................................................................................ 14

2-2. توزیعگر های اتوماتیک ..................................................................................................................... 17

2-2-1. ابزار هاي نيمه اتوماتيك .............................................................................................................. 17

2-2-2. ابزار هاي تمام اتوماتيك ............................................................................................................. 18

2-2-3. توزيع بايت­ كد جاوا بر مبنای تحليل­ وابستگي به صورت اتوماتیک .............................................. 21

2-4. مطابقت اندازه گره در محیط برنامه نويسي شي­گرا به صورت پویا توسط روش اسكوپ ......................... 24

2-5.افرازبندي در سيستم توزيع شده شي گرا به صورت پويا ......................................................................... 25

2-5-1. معیارهای دسته بندي اشياء ..... 26

2-5-2. الگوريتم خوشه بندي مشتق شده از الگوريتم حريصانه lo,s ...... 27

2-5-3. دسته بندي اشياء موجود در خوشه ها .......... 29

2-6. نتيجه گيري ...................................... 30

3- فصل سوم - استخراج گراف فراخواني ....................... 31

2-ساخت گراف فراخواني

3-1. ساخت گراف جريان فراخوانی ..................... 32

3-2-1. الگوریتم های تعين مقصد فراخواني .............. 34

3-2-2. روش آناليز نوع ايستاتيك .................... 34

روش آناليز سلسله مراتب کلاس ........................................................................................................... 35

3-2-3. روش آناليز نوع سريع ........................................................................................................37

3-2-4. روش آناليز نوع سريع حساس به جريان برنامه ....................................................................37

3-2. استخراج گراف فراخواني جهت ساخت گراف کلاسها ...................................................................41

3-3. مقايسه روش های ساخت گراف فراخوانی ......................................................................................... 43

3-4. وزن گذاری گراف فراخوانی ............................................................................................................ 45

3-5. استراتژي وزن گذاري يال هاي گراف فراخواني توابع ...................................................................... 46

3-6. برآورد زمان اجراي كد هاي ترتيبي ................................................................................................. 50

3-7-1. روش های برآورد زمان اجراي كد هاي ترتيبي ...................................................................... 51

3-7-2. برآورد زمان اجرای کدهای برنامه باآناليز متن برنامه................................................................ 51

3-7-3. تخمين ايستاي زمان اجراي برنامه ها ....................................................................................... 56

3-7-4. تعيين سرحد تكرار حلقه­ها و فراخواني­هاي بازگشتي ............................................................... 57

3-7-5. حذف مسيرهاي اجرا نشدني .................................................................................................. 57

3-7-6. بهينه سازي كامپايلرها و تخمين زمان اجراي برنامه .................................................................. 57

3-7. زبان هاي برنامه سازي و تخمين زمان اجرا ........................................................................................ 58

3-8. رعايت ميزان دقت تخمين در زمان اجرا ............................................................................................ 58

3-9. معيارهاي موجود در تخمين طولاني ترين زمان اجرا .......................................................................... 59

3-10-1. تحليل جريان داده ............................................................................................................. 59

3-10-2. تحليل كاهش بازگشتي .................................................................................................... 61

3-10-3. حجم زياد اطلاعات ......................................................................................................... 62

3-10-4. استفاده از كد Object برنامه ............................................................................................ 63

3-10. بايت كد جاوا و محاسبه زمان اجراي دستورالعملها ........................................................................... 63

3-11. محاسبه زمان اجراي حلقه ها ............................................................................................................ 64

3-12-1. نحوه شناسايي حلقه هاي تكرار ................................................................................... 65

3-12. انتشار دامنه مقادير ............................................................................................................................ 67

3-13. دستورات شرطي و نحوه شناسايي آنها .............................................................................................. 68

3-14. محاسبه زمان اجراي کل برنامه با استفاده از روش پيشنهادي ............................................................ 70

3-15-1. تشخيص حلقه هاي تكرار ................................................................................................. 71

3-15-2. تخمين تعداد تكرار حلقه ها .............................................................................................. 71

3-15-3. انتشار مقادير .................................................................................................................... 71

3-15-4. محاسبه زمان اجراي توابع موجود در يك دور از گراف................................................... 71

3-15. يافتن نقاط همگام سازي ................................................................................................................. 73

3-16. بررسي نتيجه الگوريتم پيشنهادي برروي يك برنامه نمونه................................................................. 76

3-17. جمع بندی ..................................................................................................................................... 80

4- فصل چهارم - خوشه بندی ............................................................................................................... 81

4-1. مقدمه ............................................................................................................................................ 82

4-2. خوشه بندي سلسله مراتبي .............................................................................................................. 82

4-3. خوشه بندي سلسله مراتبي پايين به بالا (تلفيق) ................................................................................. 85

4-4. روش هاي ادغام خوشه ها در خوشه بندي پايين به بالا .................................................................... 88

4-4-1. Single Linkage.................................................................................................... 88

4-4-2. Complete Linkage .................................................................................................. 89

4-4-3. Group Average Linkage ...................................................................................... 89

4-4-4. Simple Average Linkage ..................................................................................... 90

4-4-5. Weighted Average Linkage ............................................................................... 91

4-4-6. سه روش مفيد ديگر (Median, Centroid, Wards ) .............................................. 91

4-5. تكنيك هاي يافتن تعداد خوشه هاي بهينه ..................................................................................... 94

4-5-1. جدول تلفيق (جدول ادغام) ........................................................................................... 94

4-5-2. تراز تلفيق ...................................................................................................................... 96

4-5-3. نمودار dendrogram ................................................................................................ 96

4-5-4. تعيين تعداد خوشه هاي بهينه .......................................................................................... 98

4-6. تكنيك هاي پيدا كردن نقطه پيچش در نمودار جدول تلفيق......................................................... 100

4-7. روش پيشنهادي در اين پايان نامه جهت خوشه بندي .................................................................. 103

4-7-1. الگوريتم پيشنهادي برای خوشه بندی کلاس ها ............................................................ 103

4-8. جمع بندي ............................................................................................................................... 106

5- فصل پنجم - پياده سازي و ارزيــابــي ....................................................................................... 108

5-1. محيط پياده سازی شده ............................................................................................................. 109

5-2. مقايسة روش خوشه بندي پيشنهادي با روش حريصانه متداول.................................................... 111

6- فصل ششم - نتيجـه‌گيـري ....................................................................................................... 120

6-1. نتيجه گيري ............................................................................................................................ 121

6-2. کارهاي آتي .......... ............................................................................................................... 121

منابع و مراجع ........................................................................................................................................ 123

عنوان

صفحه

3-1. يک برنامه نمونه و گراف فراخوانی آن ...................................................................................................... 32

3-2. الگوريتم ساخت گراف فراخوانی به روش CHA ................................................................................... 36

3-3. الگوريتم انتخاب متد بعدی در روش FRTA ........................................................................................... 39

3-4. الگوريتم Travers برای روش FRTA ................................................................................................ 40

3-5. الگوريتم روش FRTA ........................................................................................................................... 41

3-6. يک برنامه نمونه ساده ................................................................................................................................ 44

3-7. گراف فراخواني اسخراج شده با استفاده از روش CHA ........................................................................... 45

3-8. الگوريتم وزن گذاري گراف فراخواني ..................................................................................................... 50

3-9. نمونه اي از يک ماتريس ناهمبستگي........................................................................................................ 50

3-10. الگوريتم برآورد زمان اجراي يک تکه کد ............................................................................................ 53

3-11. الگوريتم برآورد زمان اجراي يک تکه کد ........................................................................................... 55

3-12. مثال براي حذف مسيرهاي اجرا نشدني .................................................................................................... 57

3-13. حدود زمان اجراي برنامه مطرح درشبيه‌ساز San .................................................................................... 59

3-14. قوانين مورد استفاده در روش شماي زمان سنجي ...................................................................................... 61

3-15. الگوريتم ساده براي ايجاد درخت پوشا .................................................................................................... 65

3-16. دو الگوريتم مجزا براي ساختن حلقه هاي طبيعي ...................................................................................... 67

3-17. الگوريتم يافتن مجموعه گره هاي مسلط بر هر گره در يک گراف......................................................... 67

3-18. مثالي از انتشار مقادير در متن يک برنامه .................................................................................................. 68

3-19. نمونه گراف جريان كنترلي حلقه داراي شرط .......................................................................................... 69

3-20. يك حلقه ساده در گراف حهت دار .......................... ..............................................................................72

3-21. روش محاسبه زمان اجراي نودها در گراف جهت دار............................................................................... 73

3-22. الگوريتم تعيين نقاط همگام سازي ......................................................................................................... 75

3-23. گراف وابستگي برنامه فروشنده دوره گرد............................................................................................... 78

3-24. تعداد فراخواني هاي انجام شده بين کلاس های برنامه فروشنده دوره گرد.............................................. 79

4-1. خوشه بندي بالا به پايين و پايين به بالا ..................................................................................................... 84

4-2. الگوريتم کلي خوشه بندي پايين به بالا .................................................................................................... 86

4-3. Dissimilarity Matrix ................................................................................................................... 86

4-4. جدول رابطه هاي روش هاي مختلف ........................................................................................................ 94

4-5. ماتريس همبستگي 5 شي فرضي .............................................................................................................. 95

4-6. جدول تلفيق براي اشيا شكل4-5با استفاده از روش Complete Linkage......................................... 95

4-7. نمودار dendogram .......................................................................................................................... 97

4-8. تخمين خوشه ها از روش نمودار Dendogram .................................................................................. 98

4-9. نمودار تراز هاي تلفيق ......................................................................................................................... 100

4-10. نقاط قرمز رنگ به عنوان نقطه برش مناسب ....................................................................................... 102

4-11. نمودار تراز هاي تلفيق ...................................................................................................................... 102

4-12. الگوريتم خوشه بندي پايين به بالاي پيشنهادي .................................................................................. 104

5-1. مرحله سوم خوشه بندي برنامه فروشنده دوره گرد .............................................................................. 109

5-2. مرحله يازدهم از خوشه بندي برنامه فروشنده دوره گرد ...................................................................... 111

5-3. خوشه هاي به دست آمده از الگوريتم حريصانه براي برنامه فروشنده دوره گرد ................................... 112

5-3. خوشه هاي به دست آمده از الگوريتم حريصانه براي برنامه فروشنده دوره گرد ................................... 112

5-5. کاهش زمان اجرای برنامه توزيع شده نسبت به برنامه ترتیبی در ورودی های بزرگ با استفاده از الگوريتم خوشه بندی پيشنهادی ........................................................................................................................................... 115

5-6. روال اجرايي برنامه فروشنده دوره گرد ............................................................................................. 117

مقدمه

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

افزايش نياز به سيستم هایی با کارائی بسيار زياد و سرعت فوق العاده بالاي شبکه ها (شبکه هاي ترابيتی) سبب جلبعلاقه محققان به پردازش هاي موازي و توزيع شده، شده است. از جمله دلايل افزايش توجه به سيستم های توزيع شده می توان به موارد زير اشاره کرد:

1: پيشرفت تکنولوژي پردازش.

2: سرعت بالاي شبکه ها.

3: انجام تحقيقات گسترده براي ارائه محيطهائی برای انجام محاسباتي توزيع شده.

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

از سوی ديگر تحول چشم گيری نيز در صنعت شبکه های کامپيوتری به وجود آمده است. امروزه هزاران کامپيوتر می توانند از طريق يک شبکه LAN به يکديگر متصل شده و در کسری از ثانيه داده های خود را با يکديگر مبادله کنند. يا به کمک يک شبکه WAN ميليون ها کامپيوتر از سرتاسر دنيا قادر به تبادل داده با يکديگر هستند.با توجه به اين تحولات، امروزه تصور مجموعه ای از کامپيوتر ها که به صورت يک کامپيوتر يکپارچه اما با قدرت بسيار بيشتر ،چندان بعيد نيست.

فصل اول

مفاهيم اوليه

1.

2.مقدمه

1-1. سيستم های توزيع شده

در حالت کلی تعريف زير را می توان برای يک سيستم توزيع شده ارائه کرد:

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

1-1-1 مزایا و معایب سيستم های توزيع شده

سيستم هايکامپيوتري توزيع شده به وسيله پژوهشگران به طور گسترده مطالعه شدهو مزاياي زيادي در رابطه با آنگزارششده است. به عنوان مثال پيشرفت هاي اخير در تکنولوژی شبکه ها و پردازه ها، دستيابي به مزاياي زير راامکان پذير ساخته است :

1. افزايش کارايي: وجود چندين کامپيوتر در يک سيستم توزيع شده به برنامه کاربردي امکان پردازش واجرا به صورت موازي را مي دهد بنابراين سرعت اجراي برنامه کاربردي و کارايي سيستم افزايش مي يابدبراي مثال کارايي يک سيستم فايل مي تواند به وسيله تکرار توابع آن بر روي چندين کامپيوتر بيشتر شود.تکرار سيستم فايل باعث مي شود چندين برنامه کاربردي به سيستم فايل به صورت موازي دسترسي داشتهباشند بعلاوه تکرار فايل ها ترافيک شبکه را بين سايت هاي مختلف توزيع کرده و تاخير ناشي از صف بنديرا کاهش مي دهد.

2. به اشتراک گذاري منابع: به اشتراک گذاري منابع مقرون به صرفه بودن و امکان دسترسي کارا به منابعسيستم را فراهم ميکند يعني کاربران در عرض چند دقيقه مي توانند منابع سخت افزاري و نرم افزاري گرانو خاص منظوره را مانند سرورهاي پايگاه داده ها، سرورهاي پردازش، سرورهاي پرينترو... را بهاشتراک بگذارند.

3. افزايش توسعه پذيري: سيستم هاي توزيع شده مي توانند به صورت سازگار با محيط طراحي شوند مثلابراي يک محاسبه سنگين، سيستم خود را به گونه اي سازمان دهي مي کند که شامل تعداد زيادي ازکامپيوترها و منابع باشد در صورتيکه براي پردازشهایکوچکتر فقط از چند منبع استفاده خواهد کرد بعلاوه در صورت لزوم محدوديتهائی مانند ظرفيت سيستم فايل و قدرت محاسبتی سيستمرا مي توان به سادگی با اضافه کردن کامپيوترها يا سرورهايبيشتر افزايش يابد.

4. افزايش قابليت اطمينان، دسترسي راحت و تحمل پذيري خطا:وجود چندين منبع ذخيره سازي ومحاسباتي در يک سيستم، ساخت سيستم توزيع شدۀ تحمل پذير خطا را مقرون به صرفه و جالب مي کند.

سيستم مي تواند خرابی يک کامپيوتر را به وسيله تخصيص وظايف آن به کامپيوتر ديگر تحملکند بعلاوه سيستم مي تواند به وسيله تکرار توابع يا منابع، در کامپيوتر های مختلف، خطر از دست دادن آنها را برطرف کند.

5. مقرون به صرفه گي: کارايي کامپيوترها تقريباً هر دو سال يک بار دو برابر شده، در صورتيکهقيمت آنها در دهه اخير تقريبا در هر سال نصفشده است بعلاوه شبکه هايي با سرعت بسيار زياد نيز بهوجود آمده است که ساخت سيستم هاي توزيع شده را نسبت به سيستم هاي موازي بر اساس نرخ قيمت بهکارايي مقرون به صرفه تر کرده است.

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

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

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

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

يک سيستم توزيع شده حداقل بايداهداف زير را برآورده کند: 1- به سادگی منابع موجود در شبکه را در اختيار کاربران قرار دهد.

2- کاربران نبايد از اين موضوع که منبع مورد استفاده آنها در کامپيوتر ديگری در شبکه قرار دارد مطلع شوند.(شفافيت) 3- سيستم توزيع شده بايد باز باشد.

4- سيستم توزيع شده بايد مقياس پذير باشد.

شفافيت می تواند در جنبه های مختلف سيستم های توزيع شده مطرح شود.

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

مسائل مربوط به مقياس پذيری نیز تا حد زيادی به ميزان مولفه های متمرکز سيستم بستگی دارد. هر چه اين ميزان زياد باشد مقياس پذير کردن سيستم مشکل تر خواهد بود.

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

1-2 انگیزش

ايده شي گرايي از محبوب ترين روش هاي توليد نرم افزار است,كه براي طراحي، توصيف و پياده سازي سيستم هاي توزيع شده نيز بسيار سودمند است.[11] مزيت اين روش براي ساخت سيستم هاي توزيع شده اين است كه ميتوان كدهاي برنامه را در اشيا كپسوله كرده و سپس اشيا را به ماژول هاي مستقلي دسته بندي كرد و هر ماژول را بر روي يك منبع محاسباتي مجزا مستقر نمود. با اين حال به عنوان يک اصل [8]توليد يک برنامه توزيع شده، همواره سخت تر از ايجاد يک برنامه غير توزيع شده است, که عملکردی معادل آن را دارد. به طوري كه ساخت يك سيستم توزيع شده ميتواند به يك كار خسته كننده و مملو از خطا تبديل شود.[4] با وجود اينكه امروزه ابزار ها و تكنيك هاي بسيار مفيدي مانند[29] RPC ،[15] CORBA و[8] DCOM جهت ساخت سيستم هاي توزيع شده با كارايي بالا ارائه گشته اند، اما در حالت كلي فرايند ساخت يك سيستم توزيع شده از بدو پيدايش سيستم هاي توزيع شده تغير اندكي كرده است : برنامه نويس برنامه را به ماژول هاي مختلفي تقسيم كرده، هر ماژول را به صورت مجزا پياده سازي كرده و امكان برقراري ارتباط بين آنها را ايجاد مي كند و در نهايت هر ماژول را در يك كامپيوتر مستقل در شبكه مستقر ميكند. برخي از چالش هايي كه در رابطه با ساخت سيستم هاي توزيع شده پيش روي يك برنامه نويس يا طراح نرم افزار مي تواند قرار گيرد عبارت اند از:

• پيچيدگي طراحي و پياده سازي سيستم هاي توزيع شده.
• پيدايش نوع جديدي از خطاها مانند خطاهاي ناشي ازهمروندي و همگام سازي پردازه ها.
• مشكلات ناشي از سازگاري داده ها در كل سيستم.
• موازنه كار بارگذاري شده در منابع موجود در سيستم.

لذا اتوماتيک سازی فرايند تبديل يک برنامه ترتيبی به يک برنامه قابل اجرا برروی يک محيط محاسباتی توزيع شده همواره به عنوان يک مساله باز تحقيقاتی مطرح بوده است. امروزه شبکه‌هاي کامپيوتري به واسطه پيشرفت تکنولوژي ارتباطات توانسته‌اند جايگزين کامپيوترهاي گران قيمت موازي­­گردند[1].

هنگام طراحي برنامه های توزيع شده براي مسائل کاربردي، اغلب الگوريتم ها به مجموعه اي از کارهاي کلاسيک، و تکراري تجزيه مي شوند. از جمله کارهاي بنيادي که در اغلب الگوريتم ها ديده مي شوند مي توان به انتشار[1] اطلاعات به تمام گره ها،ارسال پيام به برخی از گره ها[2]، سنکرون سازي عمومي تمام پردازه ها، شروع اجراي برخي رويداد ها، ضمن اجراي پردازه ها، يا انجام محاسبه اي که داده هاي مورد نياز آن بين گره هاي مختلف توزيع شده، اشاره کرد. اين عمليات ها معمولا با تبادل پيام بين پردازه ها انجام مي گيرند.با طراحی زير ساختی که بتواند اين primitive ها را در اختيار برنامه های ترتیبی قرار دهد می توان نسخه توزيع شده ای از يک برنامه ترتِبی توليد کرد.

يکي از چالشهاي مطرح در توزيع کد، ميزان تسريع حاصل از توزيع مي‌باشد[4] برنامه هاي علمي نياز به كامپيوترهايي با توان محاسباتي بالا دارند. اين نوع كامپيوترها معمولا بسيار گران قيمت ميباشند. امروزه سعي برآن است تا بجاي استفاده از سوپركامپيوترها از شبكه اي با كامپيوترهاي ارزان قيمت براي حل مسائل علمي استفاده شود. هدف ما توزيع كد برنامه ها جهت حصول حداكثر ميزان همروندي در اجراي كد است در صورت موفقيت مسلما زمان اجرايي به حداقل ممكن كاهش خواهد يافت.

محاسبه زمان اجراي يک برنامه بصورت دقيق امکان ندارد، چون برحسب مسيرهاي اجرايي[3] متفاوت در يک برنامه، زمان اجراي آن متفاوت خواهد بود. بيشترين و کمترين زمان اجراي يک برنامه، به طولاني‌ترين و کوتاهترين مسير اجرايي برنامه از لحاظ زماني بستگي خواهد داشت. هدف از يافتن اطلاعات مسيرهاي اجرايي يک برنامه، تخمين زمان اجراي آن است.

همانطور که بيان شد توزيع کد با هدف افزايش سرعت پردازش صورت مي‌گيرد. بنابراين انتظار مي‌رود کد توزيع شده نسبت به قبل سريعتر اجرا­ گردد. نکته قابل تامل اين است که آيا توزيع صورت گرفته باعث تسريع شده است؟ ميزان تسريع (تقويت توزيع) چقدر است؟ براي پاسخ به اين سوالات بايد مشخص گردد مدت زما ن اجراي برنامه، قبل و بعد از توزيع به چه ميزان بوده است.

به هنگام توزيع، بخشي از برنامه در ايستگاه کاري راه دور اجرا مي‌گردد. براي محاسبه زمانِ اجراي برنامه ترتيبي توزيع شده، بايد مدت زمانيکه طول مي کشد تا افراز[4] احضار شده در ايستگاه کاري راه‌دور اجرا گردد و مدت زمان سپري شده بين دستور احضار[5] تا اولين استفاده از نتيجه اين احضار، تخمين زده شود و بر اساس مدت زمان احضار و ارسال نتايج، زمان اجراي توزيع شده محاسبه گردد. بعنوان مثال در مرجع [4] ميزان تسريع توزيع محاسبه شده است. اين عامل بر اساس زمان محاسبه شده دو ايستگاه کاري بر روي لبه اتصال دهنده آنها، مشخص مي شود.

1-3- مراحل کلی تبديل برنامه ترتيبی به برنامه توزيع شده

در حالت کلی برای تبديل يك برنامه ترتيبي به يك برنامه توزيع شده مراحل زير پيموده مي شود

- با پيمايش برنامه ترتيبی توسط يك تجزيه گر ويژه كه از كلاس هاي كتابخانه[7] COMPOST استفاده ميكند، اطلاعات لازم جهت ساخت گراف وابستگي كلاس ها، خوشه بندي ، برآورد زمان اجراي متد هاي برنامه و ايجاد كد توزيع شده در قالب سه کدخلاصه با نام هاي SourceModel ، DepModel و CostModel استخراج می گردد. در اين مرحله علاوه بر خلاصه سازی اطلاعات برنامه, نقاط همگام سازی برنامه نيز تعيين می گردد.يك نقطه همگام سازي مكاني درمتن برنامه است كه درآن يكي از نتايج يك فراخواني متد دور استفاده شده است. نتايج به دست آمده از اين مرحله مستفيما در هر يك از مراحل بعدي استفاده مي شوند.

- پس از استخراج اطلاعات لازم ، گراف فراخواني متد هاي برنامه ترتيبي با استفاده از اطلاعات موجود در کد خلاصه SourceModel يا مدل منبع, استخراج و رسم مي شود.در محيط پياده سازي شده, استخراج گراف فراخواني به سه روش[5] CHA ، RTA و FRTA امكان پذير است.

- پس از ساخت گراف فراخواني به كمك الگوريتمي كه مدت زمان بين فراخواني يك متد و استفاده از يكي از نتايج اجراي آن را محاسبه مي كند, يال هاي موجود در گراف فراخواني توابع به گونه اي وزن دار ميشوند كه وزن يك يال ميزان افزايش كارايي برنامه در صورت فراخواني آن متد به صورت آسنكرون را نشان دهد. جهت انجام اين كار دو الگوريتم ديگر كه يكي مدت زمان اجراي يك متد و ديگري مدت زمان اجراي يك تكه كد را برآورد مي كند طراحي وپياده سازي شده اند. بر آورد زمان اجراي متدها از طريق يکي ديگر از كد هاي خلاصه توليد شده در مرحله اول به نام CostModel صورت مي گيرد.در اين پايان نامه برآورد زمان اجراي يك تكه كد به کمک برآورد ميزان پيچيدگي آن انجام مي شود.

- پس از وزن گذاري يال هاي موجود درگراف فراخواني و استخراج گراف وابستگي بين كلاس ها، اين گراف به گونه اي خوشه بندي مي شود كه كلاس هايي با حد اكثر درجه همبستگي در يك خوشه قرار گيرند و همچنين ميزان كلاس هاي بار گذاري شده در هر خوشه متناسب و ارتباط بين خوشه ها تا حد امکان کم باشد به عبارت ديگر خوشه ها داراي خصوصيت Load Balancing بوده و تعداد فراخواني هاي بين خوشه اي تا حد امكان كم باشد. در سيستم پياده سازي شده فرايند خوشه بندي مي تواند به صورت كاملا اتوماتيك توسط سيستم يا نيمه اتوماتيك انجام گيرد. در حالت دوم كاربر مي تواند تغييرات مورد نظر خود را در خوشه بندي كلاس ها اعمال كند . درحالت اول نيز به كمك يك الگوريتم تعيين تعداد خوشه هاي بهينه [18] ، ساختار و تعداد خوشه هاي بهينه براي كلاس هاي برنامه مشخص مي شود.

- در نهايت پس از مشخص شدن خوشه هاي برنامه، كد توزيع شده توليد مي شود. براي اين منظور يک شي Proxy به هر يک از خوشه ها تخصيص مي يابد که اين شي مديريت ايجاد اشيا دور و فراخواني متد هاي آنها را بر عهده مي گيرد. يك شي Proxy جهت ايجاد اشيا دور و مديريت فراخواني متد هاي آنها از دو شي ديگر به نام هاي Object Manager و Synchronizer استفاده مي كند. اين اشيا نيز از کلاس هاي کتابخانه Java Symphony جهت انجام وظايف خود استفاده مي کند.

- با تحليل متن برنامه ترتيبي و با توجه به نتيجه خوشه بندي، تمام دستورات ايجاد اشيا، و فراخواني متد هايي كه كلاس آنها در خوشه ديگري قرار گرفته با فراخواني متد هاي مناسبي از شي Proxy تعويض مي شوند. همچنين با استفاده از آناليز وابستگي داده ها نقاطي از برنامه ترتيبي كه در آنها بايد همگام سازي صورت گيرد كشف شده و كد هاي مناسبي در آن نقاط از برنامه درج مي شود.

1-4- ساختار پايان نامه

فصل هاي بعدي در اين پايان نامه به شرح زير سازماندهي شده اند. در فصل دوم تحقیقات و ابزارهای مرتبط با اين پروژه و نحوه استخراج كد خلاصه شده از متن برنامه جهت ساخت گراف فراخواني متد ها ، بررسي شده اند. همچنین انواع روشهاي خوشه بندي براي رسيدن به اهداف مختلف با در نظر گرفتن پارامترهاي متفاوتي از قبيل محدوديت دسترسي به منابع ، پيوستگي، چسبندگي و تعداد فراخوانيهاي بين اشيا، وزن اشاره گرها و غیره نیز بررسی شده است.

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

وزن گذاري به گونه اي صورت ميگيرد كه وزن هر يال نشان دهنده ميزان افزايش در كارايي سيستم در صورت همروندي توابع موجود در گره هاي آن يال باشد.

در فصل چهارم نحوه خوشه بندي گراف وابستگي استخراج شده توسط تكنيك هاي خوشه بندي سلسله مراتبي[4] و يافتن تعداد خوشه هاي بهينه براي كلاس هاي برنامه ترتيبي توصيف شده است. و در فصل پنجم به نحوه پياده سازي و ارزيابي روش پيشنهادي پرداخته خواهد شد كه ابتدا نمودار كلاسها و فعاليت آنها بررسي شده و جهت تكميل مطالب اين قسمت، نمودار اشياي حاصل از كلاسهاي مورد استفاده در ادامه آورده خواهد شد و روش پيشنهادی توسط مسئله فروشنده دوره گرد و مقایسه آن با ساير روش ها ارزيابي می شود.

در فصل ششم با نتیجه گیری از مطالبو نيز بيان کارهای آتی به پايان نامه خاتمه می دهيم.

1-5. جمع بندي

در اين فصل دلايل نياز به يك توزيعگر اتوماتيك، كار هاي مرتبط انجام شده با اين موضوع و ساختار كلي محيط پياده سازي شده جهت تبديل برنامه هاي ترتيبي به نسخه هاي توزيع شده از همان برنامه بررسي گرديد. همانطور كه گفته شد براي تبديل يك برنامه ترتيبي به يك برنامه توزيع شده متن برنامه ترتيبي ابتدا به كمك كتابخانه Compost تحليل شده گراف فراخواني، از متن برنامه استخراج مي شوند. سپس با برآورد زمان اجراي متد ها و تخمين زمان صرفه جويي شده در اجرا در صورت توزيع آنها، يال هاي موجود در گراف فراخواني وزن دار شده و گراف وابستگي كلاس هاي برنامه ساخته مي شود. پس از ساخت گراف فراخواني اين گراف توسط يك الگوريتم خوشه بندي سلسله مراتبي ويژه خوشه بندي شده و پس از مشخص شدن وضعيت و تعداد خوشه ها با تخصيص يك شي Proxy به هر خوشه و كشف نقاط همگام سازي، برنامه ترتيبي به يك برنامه توزيع شده تبديل مي شود. ترجمه کد هاي ترتيبي به توزيع شده نيز به کمک کتابخانه کلاس هاي Compost صورت مي گيرد.

فصل دوم

تکنيک ها و ابزارهای مرتبط

1كارهاي انجام گرفته

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

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

ابزارهاي تبادل پيام چند منظوره مانند P4[], MPI[], PVM[] ,Made line[] وسيستم ارتباطي My Net[] پرميتيو های ساده ای برای تبادل هر نوع پيام ارائه کرده اند.در حاليکه سيستم هاي خاص منظوره همچون BLACS[] ( سيستم ارتباطي جبر خطي پايه ) و TCGMSG[] (گروه شيمي نظري سيستم تبادل پيام ) برای برنامه هاي کاربردي مخصوص طراحی شده اند. بعلاوه، برخی از سيستم ها مانند GRIDS[] و CANOPY[] نيز ساختمان داده هاي ارتباطی مناسبی براي برنامه هاي مختلف ارائه مي دهند. اين ابزارها و محيط هاي برنامه نويسي، مدل هاي محاسباتي متفاوتي از لحاظ موازي سازي داده ها، موازي سازي کارها و حافظه اشتراکي را براي کاربران ارائه مي کنند. ابزارهاي مختلف از تکنيک هاي پياده سازی متفاوتی مانند remote procedure call ، پردازش وقفه ها، تبادل پيام ها و يا استفاده از معماري client-server براي برقراری ارتباطات استفاده مي کنند. از اين رو هر ابزار برای گروه خاصی از برنامه های کاربردی مناسب می باشد. سيستم هایی مانند CMMD و NX/2 در مقايسه با سيستم هایportable مانند PVM و MPI برای ساخت برنامه های خاصی طراحی شده اند.

2-1- ابزارهاي تبادل پيام در مقايسه با حافظه اشتراکي توزيع شده

دو مدل ارتباطي براي برنامه کاربردي تحت شبکه وجود دارد، 1) تبادل پيام 2) حافظه اشتراکي توزيع شده. قبل از بررسی ابزارهاي تبادل پيام، به طور خلاصه مدل حافظه اشتراکي توزيع شده را مرور کرده و آن را با مدل تبادل پيام مقايسه مي کنيم.

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

حافظه اشتراکي توزيع شده، يک فضاي آدرس مجازي که بين دو پردازندۀ مستقل به اشتراک گذاشته شده می باشد. پس DSM مفهومي مي باشد که حافظه محلي ماشين هاي مختلف را در شبکه در قالب يک حافظه مشترک براي پردازه هاي در حال اجرا نشان مي دهد. در مدل DSM برنامه نويس يک فضاي آدرس بزرگ واحد(همانند حافظه يک کامپيوتر معمولی) را مشاهده مي کند که به عناصر داده اي داخل آن دسترسي دارد. در اين مدل، سخت افزار يا نرم افزاري تبادلات لازم براي انتقال داده از حافظه هاي دور را انجام می دهد. نمونه هاي سخت افزاري شامل KSR[], Princeton Shrimp[], MIT Alewife[] و نمونه هاي نرم افزاري شامل CRL[], Tread Marks[], Mirage[] مي باشند.

2-2- تبادل پيام

تبادل پيام از نظر کارايي، شيوه بهتري نسبت به برنامه نويسي DSM مي باشد. کتابخانه های تبادل پيام امکانات ساده ای براي ارتباطات ارائه مي کنند که برنامه نويس را از پرداختن به مسائل پيچيدۀ پروتکل شبکه ها و محيط هاي نا همگن بي نياز مي کند. در اين مدل معمولا پردازه ها استفاده از دو تابع سادۀ receive وsend به تبادل داده می پردازند ،معمولا مدل تبادل پيام مانند حافظه اشتراکی براي برنامه نويسان جالب نيست. در مدل تبادل پيام، برنامه نويسان بايد صريحاً فراخواني هاي لازم براي ارسال و دريافت پيام ها را در داخل کد های خود قرار دهند. در اين مدل، داده نمی تواند به اشتراک گذاشته شود و بايد کپي شود. اين موضوع ميتواند مشکلاتي را برای برنامه هائی که دستورات متعددی را بر روی انبوهی از داده ها اجرا می کنند، به وجود آورد. با اين حال مدل تبادل پيام سودهايي هم دارد مثلاً کنترل دسترسي برنامه کاربردي به داده ها، لازم نيست .و اين می تواند کارايي برنامه را به مقدار زيادي افزايش دهد. بنابراين مهمترين دليل استفاده از تبادل پيام ، کارايي بالاي آن می باشد.

2-2-1 . خصوصيات مطلوب يک سيستم تبادل پيام

ويژگی های مطلوب يک سيستم تبادل پيام بطور مختصر در زير آمده است:

1) سادگي(simplicity) : استفاده از سيستم تبادل پيام بايد ساده و آسان باشد.

2) کارايي(efficiency): يک سيستم تبادل پيام بايد تا حد امکان سريع باشد.

3) تحمل خط(fault tolerance): يک سيستم تبادل پيام ، بايد تحويل يک پيام را ضمانت کرده و امکان بازيابي پيام های گمشده را مهيا کند .

4) ارتباط گروهي مطمئن(reliable group communication): ارتباط گروهي مطمئن براي بسياري از برنامه هاي کاربردي توزيع شده و موازي حياتی می باشد.برخی از ويژگی های لازم براي ارتباط گروهي يکپارچگی و تحويل به ترتيب مي باشد.

5) سازگاري(adaptability): همه برنامه هاي کاربردي به سرويسهای يکساني نياز ندارند. يک سيستم تبادل پيام مناسب، سطوح مختلفي از سرويس ها را براي پاسخ به نياز برنامه هاي کاربردي ارائه مي کند. بعلاوه ، سرويس هاي ارتباطي ارائه شده بايد انعطاف پذير و قابل تغيير ، بصورت پويا در زمان اجرا باشند.

6) امنيت(Security): سيتم تبادل پيام بايد يک کانال ارتباطي نقطه به نقطه ايمن را ارائه کند بطوريکه پيام نتواند توسط هيچ کاربر ديگري غير از گيرنده دريافت شود بنابراين عمليات بررسي اعتبار ، رمزگذاري و رمزگشايي پيام ها بايد پشتيباني شود.

7) نا همگني(heterogeneity): برنامه نويسان بايد از رسيدگي به مسائل مروبط به تبادل پيام ها بين کامپيوترهاي ناهمگن فارغ شوند. مثلا تبديل فرمت داده بين بسترهاي ناهمگن بايد بصورت مخفی از ديد برنامه نويس انجام شود.

8) قابليت حمل(Portability): يک سيستم تبادل پيام، به سادگی بايد در بسترهاي پردازشی مختلف اجرا شود.

2-2-2. طبقه بندي ابزارهاي تبادل پيام

در اين بخش ابزارهاي تبادل پيام را دسته بندي کرده و روش هاي افزايش کارايي آن ها را بررسي مي کنيم. ابزارهاي تبادل پيام را می توان بر اساس نوع برنامه کاربردي، مدل برنامه نويسي، مدل ارتباطي، قابليت حمل و ناهماهنگي دسته بندي کرد.

1) نوع برنامه کاربردي : بر اساس اين معيار ابزارهاي تبادل پيام را به دو نوع خاص منظوره و چند منظوره تقسيم می شوند. ابزارهاي چند منظوره(مانند P4، PVM و MPI) دامنه وسيعي از primitive هاي ارتباطي را ارائه مي کنند که در برنامه هاي کاربردي مختلفي استفاده مي شوند. در برخي از ابزارهاي چند منظوره ديگر مانند ISIS[] ، HOURS[] ، Totem[] و TRANSIS[] سرويس هاي ارتباط گروهي برای طراحی برنامه های توزيع شده مطمئن و fault tolerant ارائه شده است. در طرف ديگر سيستم هاي خاص منظوره مانند Algebra communication[] وBasic Linear[] براي برخی از برنامه هاي کاربردي خاص مناسب هستند.

2) مدل برنامه نويسي: ابزارهاي تبادل پيام موجود، بر اساس مدل برنامه نويسي شان نيز با يکديگر متفاوت هستند. مدل برنامه نويسي، نحوه پياده سازي TASK هاي محاسباتي، را مشخص مي کند. ابزار های تبادل پيام بر اساس مدل برنامه نويسي شان به سه دسته تقسيم می شوند. موازی سازی کارها، موازی سازی داده ها و مدل شی گرا. بيشتر ابزار های تبادل پيام از موازی سازی داده ها پشتيبانی می کنند(مانند ACS [1,2], MPI, p4, and PVM.) برخی ديگر نيز مانند ACS, MPI, and PVM,

از موازی سازی کارها نيز پشتيبانی می کنند.Agorae[] و OOMPI[] برای برنامه نويسی توزيع شده شی گرا طراحی شده اند.

3)مدل ارتباطي: ابزارهاي تبادل پيام را می توان بر اساس نحوه تبادل داده نيز دسته بندي کرد. سه مدل ارتباطي که توسط ابزارهاي تبادل پيام پشتيباني مي شود عبارت اند از :

1) client-server 2) pear to pear 3) Active Message

MPF [] و [] Remote Procedure از مدل client-server استفاده می کنند. MPI و ACS و P4 و PVM جز ابزارهاي تبادل پيام pear to pear مي باشند. مدل ارتباطي جديدي به نام Active Message[] ، تأخير ارتباطي و زمان پاسخگويي را کاهش داده است. اين تکنيک که براي استفاده از پهناي باند بالای شبکه هاي پر سرعت ابداع شده، به طور کامل در ادامه اين بخش شرح داده خواهد شد.

4) قابليت حمل: ابزارهاي تبادل پيام يا در بسترهاي مختلف قابل اجرا بوده و يا فقط برای اجرا در بستر خاصی طراحی می شوند . ابزارهائی که به وسيله واسط هاي ارتباطي استاندارد نوشته مي شوند معمولاً قابل حمل بوده اما نمي توانند به طور کامل امکانات سطح پائين شبکه هاي ارتباطي را در اختيار برنامه نويسان قرار دهند. بعضي از ابزارها مانند CMMD[] يا NX/2[] مخصوص تبادل پيام در سيستم هاي خاصی طراحي شده اند.(CMMD برای CM5 و NX/2 برای کامپيوتر های موازی اينتل). و از آنجا که اين ابزارها از سخت افزارها و نرم افزارهاي ارتباطي اختصاصي استفاده مي کنند کارايي آنها بهتر از ابزارهاي چند منظوره است.

5) سازگاري: امروزه پشتيباني از سازگاري براي پياده سازي برنامه هاي کاربردي اهميت بيشتري يافته است. ACS و Madeline جهت ايجاد سازگاري در تبادل پيام ساخته شده اند. اين دو ابزار جهت ايجاد سيستمی سازگار، مي توانند نحوه کار primitive های ارتباطی خود با توجه به ميزان ترافيک شبکه و ميزان کار کامپيوتر ها تغيير دهند . اغلب ابزارهاي تبادل پيام مانند PVM, P4, MPI از سازگاري پشتيباني نمي کنند.

محبوب ترين تکنيک هاي پذيرفته شده برای ايجاد ارتباط بين پردازه ها استفاده از Socket ها مي باشد Socket .مفهومي براي شبکه بندي مي با شد که در4.1cBSD ارائه شده و در نسخه بعدي يعني4.2BSD تکميل شد. از آنجا Socketها امکان ايجاد ارتباط بين پردازه هاي مستقر در يک ماشين يا ماشين هاي مختلف را فراهم مي کند، به طور گسترده اي در سيستم هايUNIX وPC Windows استفاده شده است. براي برنامه نويس، يک Socket مانند يک فايل مي باشد. بنابراين دستوراتي مانندread() وwrite() همانند فايل بر روي Socket قابل اجرا هستند.

دو نوع Socket وجود دارد:

1- connection- or stream- oriented و2) connectionless يا datagram. در حالت کلي Socket هايconnection- oriented از پروتکل ( TCP ) وsocket هاي datagram از پروتکل (UDP) استفاده مي کنند.

براي هر پردازه اي که قصد ارتباط با پردازۀ ديگر را داشته باشد يک Socket با فراخواني سيستمي تابع Socket() ايجاد مي شود. هنگام ايجاد Socket ، نوع Socket ونوع پروتکل ارتباطي مشخص مي شود. اين فراخواني سيستمي دستگيره اي براي استفاده بعدي از Socket برگشت مي دهد. پس از ايجاد Socket ، بايد آدرس معتبري به آن نسبت داده شود)bind(اين عمل مي تواند با فراخوني تابعي سيستمي bind() صورت گيرد. Socket ها معمولاً با تمام محيط هاي محاسباتي سازگار بوده و مستقيماً از شبکه ارتباطي بدون هيچ سربازي استفاده مي کنند. از اين رو سريع ترين ابزارهاي تبادل پيام بر مبناي Socket ها ساخته شده اند. با اين حال برنامه نويسي Socket ها ساده نمي باشد، زيرا primitive ها ي ارتباطي مناسب در اختيار برنامه نويس قرار نمي گيرد.

[1]broadcast

[2]semi cast

[3]Execution Path

[4]Cluster

[5]Invocation