تحقیق ساختمان داده ها

تحقیق ساختمان داده ها

تحقیق ساختمان داده ها

فرمت ورد و قابل ویرایش


تعداد صفحات : 9 صفحه

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

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