تالار گفتمان مانشت
تفاوت الگوریتم scan و look و ابهام سوال ۷۸ کنکور ۹۰ - نسخه‌ی قابل چاپ

صفحه‌ها: ۱ ۲
تفاوت الگوریتم scan و look و ابهام سوال ۷۸ کنکور ۹۰ - masoud67 - 01 بهمن ۱۳۹۲ ۰۹:۴۶ ب.ظ

سلام
چند تا سوال داشتم
۱/ الگوریتم scan تا آخر و اول دیسک میره یا نه، فقط تا آخرین و اولین درخواست میره؟
۲/ الگوریتم look تا آخر و اول دیسک میره ؟
۳/ وقتی در C-Scan یا C-look به آخرین درخواست در یک طرف رسیدیم و میخواد برگرده به اول دیسک آیا به اول دیسک میاد یا به اولین درخواست در اول دیسک ؟

۴/ با توجه به سوالی که گذاشتم اگر الگوریتم scan (بدون توجه به صورت سوال که گفته ورود درخواست جدید تاثیری بر حرکت هد ندارد ، در حالت کلی)به طرف درخواستی رفت (مثلا اینجا ۱۶) و در وسط راه درخواست (۱۷) اومد آیا درخواست ۱۷ را اجابت میکنه (با این فرض که قبل از رسیدن به سلیندر ۱۷ درخواستش اومده باشه)؟ منظورم اینه که این سوال که از ۶۸ به ۱۶ رفته و درخواست ۱۷ را قبول نکرده به خاطر خاص بودن این سواله یا الگوریتم scan در حالت کلی چنین خاصیتی داره ؟

RE: تفاوت الگوریتم scan و look و ابهام سوال ۷۸ کنکور ۹۰ - fsi2013 - 02 بهمن ۱۳۹۲ ۱۲:۵۹ ب.ظ

(۰۱ بهمن ۱۳۹۲ ۰۹:۴۶ ب.ظ)masoud67 نوشته شده توسط:  سلام
چند تا سوال داشتم
۱/ الگوریتم scan تا آخر و اول دیسک میره یا نه، فقط تا آخرین و اولین درخواست میره؟
۲/ الگوریتم look تا آخر و اول دیسک میره ؟
۳/ وقتی در C-Scan یا C-look به آخرین درخواست در یک طرف رسیدیم و میخواد برگرده به اول دیسک آیا به اول دیسک میاد یا به اولین درخواست در اول دیسک ؟

۴/ با توجه به سوالی که گذاشتم اگر الگوریتم scan (بدون توجه به صورت سوال که گفته ورود درخواست جدید تاثیری بر حرکت هد ندارد ، در حالت کلی)به طرف درخواستی رفت (مثلا اینجا ۱۶) و در وسط راه درخواست (۱۷) اومد آیا درخواست ۱۷ را اجابت میکنه (با این فرض که قبل از رسیدن به سلیندر ۱۷ درخواستش اومده باشه)؟ منظورم اینه که این سوال که از ۶۸ به ۱۶ رفته و درخواست ۱۷ را قبول نکرده به خاطر خاص بودن این سواله یا الگوریتم scan در حالت کلی چنین خاصیتی داره ؟

سلام
الگوریتم اسکن یا آسانسور براساس رفتار یه آسانسور معمولی عمل میکنه.
منظور اینه که توی یه ساختمون ۱۰۰ طبقه یه آسانسور معمولی از طبقه ی ۱ تا ۱۰۰ بالامیره و به مسافراش سرویس میده .وقتی به ۱۰۰ رسید دوباره از ۱۰۰ به ۱ میاد و به مسافراش سرویس میده.
یعنی مثلا اگه حرکت آسانسور از بالا به پایین باشه و شما طبقه ی ۷۰ باشی و آسانسور طبقه ی ۶۹ باشه.یعنی حرکتش به سمت پایین باشه.باید منتظر بمونی تا اسانسور برسه به طبقه ی اول و دوباره برگرده بیاد بالا تا بتونی سوار شی.حتی اگه توی این همه مدت که شما منتظر بودی کسی هم سوار نشده.
خلاصه این یه آسانسور معمولی هستش.!کاری نداره درخواست ها چطوری هستش اگر به سمت پایین دیسک حرکت کنه توی راهش به درخواست ها پاسخ میده.
در مورد سوال اولت دقیقا از اول تا آخر دیسک میره.گفتم که مثل یک آسانسور معمولی رفتار میکنه،فقط وقتی آخرین درخواستی که توی صورت سوال ذکر شده بود رو جواب داد دیگه وایمیسه.
الگوریتم look مسلما اول تا آخر دیسک رو نمیره.اگر قرار بود مثل scan کار کنه که دیگه اسمش یه الگوریتم دیگه نبود Tongue
یعنی اول تا آخر دیسک نمیره.
بذار یه مثال تو دنیای واقعی بزنم آسانسوری رو فرض کن که قراره ی خونه ۱۰ طبقه رو سرویس بده.توی حالتی که الگوریتمش look باشه مثلا فرض کن از طبقه ۱ شروع میکنه و درخواستی که توی طبقه ۷ هست رو جواب میده.بعد درخواستی از طبقه ۸ میاد جواب میده.حالا اگه درخواست بعدی توی طبقه ۴ باشه .الگوریتم scan میره تا طبقه ی ۱۰ و از طبقه ی ۱۰ برمیگرده به ۴ و جواب میده.ولی الگوریتم look از طبقه ۸ مستقیم برمیگرده و به سرویس طبقه ۴ جواب میده.به همین راحتی.اسمش look هستش.یعنی یه مقداری به جلو نگاه میکنه و یه پیش بینی راجب حرکتش داره
در مورد سوال سومت با توجه به توضیحاتی دادم بازم c-scan از طبقه ی ۸ میره ۱۰ و برمیگرده ۱ و پاسخ طبقه ی ۴ رو میده
ولی c-look برمیگرده دقیقا طبقه ۴/
فکر کنم توضیحاتم یه کم گنگ شد، این صفحه رو ببینی توی چند تا نمودرا همه ی ۴ تا الگوریتم رو با هم مقایسه کرده،باز اگه سوالی داشتی بگو تا توضیح بدم.
خلاصه ی حرفم این بود الگوریتم اسکن اول تا اخر رو میره وقتی درخواست ها تموم شد متوقف میشه.
الگوریتم look تا آخرین درخواست های هر سمت رو میره.و بازم درخواست که تموم شد می ایسته.
الگوریتم c-scan از یه سمت برمیگرده به اولین سیلندر سمت دیگه.یعنی اگه سیلندر های بالایی باشه به سیلندر ۰ برمیگرده و دوباره شروع میکنه .یا اگه سیلندر پایین باشه به آخرین سیلندر بالایی برمیگرده.مثلا اگر اخرین سیلندر ۲۰۰ باشه به ۲۰۰ برمیگرده.
الگوریتم c-look به اخرین درخواس هر سمت برمیگرده نه به اخرین سیلندر.
این سوالم یه حالت خاصه این سوال زمان رو هم درگیر کرده . پس باید با توجه به زمان درخواست ها مسئله رو حل کنی که فکر کنم گزینه ی درست ۴ میشه.
این سوال حالت خاصی از الگوریتم اسکن نیست.بلکه فقط زمان رو درگیر کرده
در آخر این لینک و هم ببین و نمودارشونو مقایسه کن.

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


RE: تفاوت الگوریتم scan و look و ابهام سوال ۷۸ کنکور ۹۰ - masoud67 - 02 بهمن ۱۳۹۲ ۰۱:۱۴ ب.ظ

(۰۲ بهمن ۱۳۹۲ ۱۲:۵۹ ب.ظ)fsi2013 نوشته شده توسط:  الگوریتم اسکن یا آسانسور براساس رفتار یه آسانسور معمولی عمل میکنه.
ممنون ، توضیحات خوب بود.
ولی مشکل من فلسفیه تا تعریفی

کتابها دقیقا look و scan را یکی فرض کردند . یعنی گفتند یه الگوریتمی داریم به اسم scan که دو نوعه. نوع اول look و نوع دوم scan
توی سوالاتی هم که حل کردم scan همیشه تا آخرین درخواست میره و نه تا آخر دیسک که حتی در کتاب پارسه گفته شده که سیلبرشات scan را اینطوری فرض کرده که تا آخر دیسک میره ولی تنمبام و استالینگز فرض را بر این گذاشتند که تا آخرین درخواست میره
حالا ما موندیم و بزرگان سیستم عامل جهان

ولی هنوز جواب سوال چهارم را نگرفتم که اسکن در حالت کلی اینطوریه یا این مثال خاص اینطوریه. و از طرفی فکر نکنم به دلیل وجود زمان سیاست الگوریتم اسکن تغییر کنه.

RE: تفاوت الگوریتم scan و look و ابهام سوال ۷۸ کنکور ۹۰ - hoomanab - 02 بهمن ۱۳۹۲ ۰۳:۱۸ ب.ظ

Scan
همون آسانسوره
Look
آسانسور چرخشیه
اگه c به هرکدوم اضافه شه، به جای طی مسیر کامل فقط به ابتدا و انتهی رشته ارجاعی میرن.

Sent from my SM-T210R using Tapatalk

RE: تفاوت الگوریتم scan و look و ابهام سوال ۷۸ کنکور ۹۰ - masoud67 - 02 بهمن ۱۳۹۲ ۰۳:۲۳ ب.ظ

(۰۲ بهمن ۱۳۹۲ ۰۳:۱۸ ب.ظ)hoomanab نوشته شده توسط:  Look
آسانسور چرخشیه
اینو تا حالا نشنیده بودم. چرخشی یعنی چه ؟

RE: تفاوت الگوریتم scan و look و ابهام سوال ۷۸ کنکور ۹۰ - hoomanab - 02 بهمن ۱۳۹۲ ۰۳:۲۴ ب.ظ

یعنی بر میگرده اول لیست. انگار حلقویه

Sent from my SM-T210R using Tapatalk

RE: تفاوت الگوریتم scan و look و ابهام سوال ۷۸ کنکور ۹۰ - masoud67 - 02 بهمن ۱۳۹۲ ۰۴:۵۱ ب.ظ

(۰۲ بهمن ۱۳۹۲ ۰۳:۲۴ ب.ظ)hoomanab نوشته شده توسط:  یعنی بر میگرده اول لیست. انگار حلقویه
خب اسکن هم برمیگرده اول دیسک (البته طبق بعضی از تعاریف ولی طبق تست ها به اولین درخواست میره)
ولی look به اول دیسک نمیره به اولین درخواست میره.

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

RE: تفاوت الگوریتم scan و look و ابهام سوال ۷۸ کنکور ۹۰ - hoomanab - 02 بهمن ۱۳۹۲ ۰۴:۵۸ ب.ظ

ببین. هر دو به اول دیسک میرن با این تفاوت که اسکن درخواستای سر راهشم میخونه اما look نمیخونه. مثلا اگه درخواستها ۱۰ ۳۲ ۱۹ ۲۰ ۴۰ (از راست به چپ) و اسکن بخواد حل کنه(خونخ شروع ۲۵ و بازه از ۰ تا ۵۰) اینا از راست به چپ خونده میشن (حرکت به بالا) ۲۵، ۳۲، ۴۰، ۵۰، ۲۰، ۱۹، ۱۰، ۰ که انگار از ۲۵ رفته تا ۵۰، بعد از ۵۰ رفته ۰ که جمعا میشه ۷۶
اما look اینطوره ۲۵، ۳۲، ۴۰، ۵۰، ۰، ۱۰، ۱۹، ۲۰ که جمعا میشه ۹۶

Sent from my SM-T210R using Tapatalk

RE: تفاوت الگوریتم scan و look و ابهام سوال ۷۸ کنکور ۹۰ - masoud67 - 02 بهمن ۱۳۹۲ ۰۵:۰۴ ب.ظ

(۰۲ بهمن ۱۳۹۲ ۰۴:۵۸ ب.ظ)hoomanab نوشته شده توسط:  ببین. هر دو به اول دیسک میرن با این تفاوت که اسکن درخواستای سر راهشم میخونه اما look نمیخونه. مثلا اگه درخواستها ۱۰ ۳۲ ۱۹ ۲۰ ۴۰ (از راست به چپ) و اسکن بخواد حل کنه(خونخ شروع ۲۵ و بازه از ۰ تا ۵۰) اینا از راست به چپ خونده میشن (حرکت به بالا) ۲۵، ۳۲، ۴۰، ۵۰، ۲۰، ۱۹، ۱۰، ۰ که انگار از ۲۵ رفته تا ۵۰، بعد از ۵۰ رفته ۰ که جمعا میشه ۷۶
اما look اینطوره ۲۵، ۳۲، ۴۰، ۵۰، ۰، ۱۰، ۱۹، ۲۰ که جمعا میشه ۹۶
ممنون. الان فرق look با c-look تو این مثال چی میشه ؟

RE: تفاوت الگوریتم scan و look و ابهام سوال ۷۸ کنکور ۹۰ - hoomanab - 02 بهمن ۱۳۹۲ ۰۵:۰۵ ب.ظ

کلا c که اول هر کدوم اومد، به جای اینکه هد تا انتها و ابتدای شیارها بره تا حد اکثر و حداقل رشته ارجاعی میره

Sent from my SM-T210R using Tapatalk

RE: تفاوت الگوریتم scan و look و ابهام سوال ۷۸ کنکور ۹۰ - masoud67 - 02 بهمن ۱۳۹۲ ۰۵:۱۶ ب.ظ

یه بار دیگه
درخواستها ۱۰ - ۳۲ - ۱۹ - ۲۰ - ۴۰ و از راست به چپ و هد روی ۲۵ و به سمت بالا و دیسک ۵۰ سیلندر
scan طبق تعریف اصلی : ۳۲ - ۴۰ - ۵۰ - ۲۰ - ۱۹ - ۱۰
scan طبق چیزی که تا حالا تو تست ها دیدم : ۳۲ - ۴۰ - ۲۰ - ۱۹ - ۱۰ یعنی تا آخرین سلیندر نمیره
look : تا آخرین درخواست میره نه تا آخر دیسک ۳۲ - ۴۰ - ۲۰ - ۱۹ - ۱۰ یعنی مشابه scan در تست هایی که تا حالا دیدم

c-scan : طبق تعریف اصلی ۳۲ - ۴۰ - ۵۰ میپره رو ۰ و از صفر شروع میکنه و ۱۰ - ۱۹ - ۲۰ یعنی فقط در یک جهت میخونه
c-scan : طبق چیزی که در تستها دیدم ۳۲ - ۴۰ میپره رو ۱۰ و دوباره ۱۰ - ۱۹ - ۲۰ یعنی تا آخر و اول دیسک نمیره
c-look : شروع ۳۲ - ۴۰ میپره رو ۱۰ و دوباره ۱۰ - ۱۹ - ۲۰ یعنی فقط در یک جهت و تا اول و آخر دیسک نمیره

شما ظاهرا اشتباه خوندی . وقتی c میاد یعنی درخواست ها فقط در یک جهت خونده میشه
یه بار این لینکی که این دوستمون گذاشتند را ببینید

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


RE: تفاوت الگوریتم scan و look و ابهام سوال ۷۸ کنکور ۹۰ - hoomanab - 02 بهمن ۱۳۹۲ ۰۵:۴۵ ب.ظ

(۰۲ بهمن ۱۳۹۲ ۰۵:۱۶ ب.ظ)masoud67 نوشته شده توسط:  یه بار دیگه
درخواستها ۱۰ - ۳۲ - ۱۹ - ۲۰ - ۴۰ و از راست به چپ و هد روی ۲۵ و به سمت بالا و دیسک ۵۰ سیلندر
scan طبق تعریف اصلی : ۳۲ - ۴۰ - ۵۰ - ۲۰ - ۱۹ - ۱۰
scan طبق چیزی که تا حالا تو تست ها دیدم : ۳۲ - ۴۰ - ۲۰ - ۱۹ - ۱۰ یعنی تا آخرین سلیندر نمیره
look : تا آخرین درخواست میره نه تا آخر دیسک ۳۲ - ۴۰ - ۲۰ - ۱۹ - ۱۰ یعنی مشابه scan در تست هایی که تا حالا دیدم

c-scan : طبق تعریف اصلی ۳۲ - ۴۰ - ۵۰ میپره رو ۰ و از صفر شروع میکنه و ۱۰ - ۱۹ - ۲۰ یعنی فقط در یک جهت میخونه
c-scan : طبق چیزی که در تستها دیدم ۳۲ - ۴۰ میپره رو ۱۰ و دوباره ۱۰ - ۱۹ - ۲۰ یعنی تا آخر و اول دیسک نمیره
c-look : شروع ۳۲ - ۴۰ میپره رو ۱۰ و دوباره ۱۰ - ۱۹ - ۲۰ یعنی فقط در یک جهت و تا اول و آخر دیسک نمیره

شما ظاهرا اشتباه خوندی . وقتی c میاد یعنی درخواست ها فقط در یک جهت خونده میشه
یه بار این لینکی که این دوستمون گذاشتند را ببینید

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

اشتباه تایپی شد ببخشید! جایی که Look رو گفتم منظورم C-scan بود.
جای Look و Cها رو قاطی کردم یه لحظه!
scan کل شیار ها رو میخونه اما look فقط از ابتدا تا انتها می خونه.
c که میاد منظورش circular یا حلقویه !

RE: تفاوت الگوریتم scan و look و ابهام سوال ۷۸ کنکور ۹۰ - masoud67 - 02 بهمن ۱۳۹۲ ۰۵:۵۵ ب.ظ

(۰۲ بهمن ۱۳۹۲ ۰۵:۴۵ ب.ظ)hoomanab نوشته شده توسط:  اگه طر جلسه اینطور جواب دادی و اشتباه شد پای خودته ها Big Grin
اینی که گفتم از کتاب مرجع سیلبرشاتس هست!
من اینایی که گفتم از کتاب های غیر مرجع پارسه و پوران بود .
همونطور که گفتم پارسه خودش گفته که سیلبرشات فرض میکنه در scan هد تا آخر دیسک میره نه تا آخرین درخواست ولی استالینگز و تنم بام برعکس فرض کردند و ظاهرا مرجع اصلی تر استالینگز هست چون تست ها بر فرض ایشون حل شده
اینم از سیلبرشاتسی که میگید . ضمیمه کردم

RE: تفاوت الگوریتم scan و look و ابهام سوال ۷۸ کنکور ۹۰ - hoomanab - 02 بهمن ۱۳۹۲ ۰۶:۰۳ ب.ظ

(۰۲ بهمن ۱۳۹۲ ۰۵:۴۵ ب.ظ)hoomanab نوشته شده توسط:  [quote='masoud67' pid='239702' dateline='1390394793']
یه بار دیگه
درخواستها ۱۰ - ۳۲ - ۱۹ - ۲۰ - ۴۰ و از راست به چپ و هد روی ۲۵ و به سمت بالا و دیسک ۵۰ سیلندر
scan طبق تعریف اصلی : ۳۲ - ۴۰ - ۵۰ - ۲۰ - ۱۹ - ۱۰
scan طبق چیزی که تا حالا تو تست ها دیدم : ۳۲ - ۴۰ - ۲۰ - ۱۹ - ۱۰ یعنی تا آخرین سلیندر نمیره
look : تا آخرین درخواست میره نه تا آخر دیسک ۳۲ - ۴۰ - ۲۰ - ۱۹ - ۱۰ یعنی مشابه scan در تست هایی که تا حالا دیدم

c-scan : طبق تعریف اصلی ۳۲ - ۴۰ - ۵۰ میپره رو ۰ و از صفر شروع میکنه و ۱۰ - ۱۹ - ۲۰ یعنی فقط در یک جهت میخونه
c-scan : طبق چیزی که در تستها دیدم ۳۲ - ۴۰ میپره رو ۱۰ و دوباره ۱۰ - ۱۹ - ۲۰ یعنی تا آخر و اول دیسک نمیره
c-look : شروع ۳۲ - ۴۰ میپره رو ۱۰ و دوباره ۱۰ - ۱۹ - ۲۰ یعنی فقط در یک جهت و تا اول و آخر دیسک نمیره

شما ظاهرا اشتباه خوندی . وقتی c میاد یعنی درخواست ها فقط در یک جهت خونده میشه
یه بار این لینکی که این دوستمون گذاشتند را ببینید

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

اشتباه تایپی شد ببخشید! جایی که Look رو گفتم منظورم C-scan بود.
جای Look و Cها رو قاطی کردم یه لحظه!
scan کل شیار ها رو میخونه اما look فقط از ابتدا تا انتها می خونه.
c که میاد منظورش circular یا حلقویه !

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


RE: تفاوت الگوریتم scan و look و ابهام سوال ۷۸ کنکور ۹۰ - fsi2013 - 04 بهمن ۱۳۹۲ ۰۷:۳۱ ب.ظ

دوستان الکی دارید خودتونو گیج میکنید کاری ندارم پوران و موران پارسه و مارسه و ماسه و گچ و سیمان چی گفتن
look مثل scan هستش اما
scan از اولین شیار تا آخرین شیار رو میره
look از اولین تا آخرین درخواست رو میره
c به معنی چرخشی یا cicular اگه اشتباه نکنم هستش
یعنی همیشه تو یه جهت حرکت میکنیم یعنی توی scan اگه رسیدیم آخر دیسک دوباره برمیگردیم از شیار ۰ شروع میکنیم به حرکت
توی look اگه رسیدیم به آخرین درخواست دوباره برمیگردیم به اولین درخواست
حالا بعضی وقت ها میتونه این جهت فقط از بالا به پایین باشه!یعنی فقط از سیلندرهای بزرگتر به سمت سیلندرهای با شماره کوچکتر حرکت کنیم.
شما اصل مطلب و یاد بگیرید چیکار دارید کتاب های دیگه چی میگن.من پارسه و پوران نداشتم ولی مقسمی سیستم عامل رو داشتم مشکلی ندیدم توی مبحثی که درس و سوال داده بود.