خوش آمدید

براي اجراي چند برنامه در سيستم عامل، الگوريتم‌هاي مختلفي وجود دارد که هر کدام مزايا و معايبي دارند، يکي از اين الگوريتم‌ها الگوريتم Round-Robin است.

اين الگوريتم اين‌گونه كار مي‌كند که به هر پردازش يک برهه زماني اختصاص مي‌دهد که به آن Time-Slice (برش زماني) گفته مي‌شود و پردازش‌ها در يک صف قرار مي‌گيرند و اين الگوريتم اولين پردازش را از صف انتخاب مي‌کند و به آن يک برش زماني اختصاص مي‌دهد.

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

حال ما قصد داريم برنامه‌اي بنويسيم که اين الگوريتم را شبيه‌سازي کند، براي اين کار ما نياز به يک صف داريم.

صف يک ساختار داده‌اي است که به آن در اصطلاح FIFO گفته مي‌شود يعني First In First Out (اولين ورودي، اولين خروجي است).

نخست اين ساختار را توضيح مي‌دهيم. براي پياده سازي اين ساختار نياز به يک آرايه داريم که نشان‌دهنده آيتم‌هاي موجود در صف است و يک انديس که نشان‌دهنده شماره آيتم جاري در صف است.

و دو متد يکي به نام Enqueue و يکي به نام Dequeue، اولين متد وظيفه‌اش درج آيتم درون صف و متد ديگر وظيفه‌اش خروج آيتم از صف است.

اين المان‌ها ساختار اصلي صف را تشکيل مي‌دهند ولي مي‌تواند چند المان ديگر براي نشان دادن صف به اين المان‌ها اضافه کرد. مثل Size که نشان‌دهنده اندازه آيتم‌هاي موجود در صف است و ديگر Head که نشان‌دهنده اولين آيتم درون صف است و يا Tail که نشان‌دهنده آخرين آيتم درون صف است.

براي اطلاع بيشتر در مورد صف به نشاني زير مراجعه کنيد:

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

چک کردن پر و خالي بودن صف با استفاده از متد Dequeue امکان‌پذير است ولي خب چه زيباست که يک متد به ساختار اضافه کنيم که با استفاده از آرايه شامل عناصر صف بررسي کند که آيا صف پر است يا خالي؟

خب همان‌طور که گفته شد، پردازشگر يک پردازش را از صف پردازش‌ها برداشته و آن را در يک زمان مشخص اجرا مي‌کند. براي اجرا شدن متناوب با يک دوره تناوب ثابت نياز به تايمر داريم، براي پياده‌سازي تايمر در زبان C به نشاني زير مراجعه کنيد:

گفتني است زبان‌هاي سطح بالاتر مثل #C و جاوا، تايمر را جزو کلاس‌هاي پايه‌اي خود دارند. هر تايمر يک تيک دارد، اين عدد نشان مي‌دهد که تايمر در هر بازه زماني که به‌مدت تيک است، عمليات مربوطه را انجام مي‌دهد. مثلا به تايمر مي‌گوييم در هر تيک زماني فلان کار را انجام بده، پس از اين تيک دوباره کار خود را از اول آغاز مي‌کند.

با توجه به توضيحات داده شده مي‌توان تيک را برابر برش زماني قرار داد و در تابع مربوط به تيک بايد عمليات زير را انجام دهيم:

1- بررسي کنيم که صف پر است يا خالي؟ اگر خالي بود، به سيستم‌عامل اطلاع دهيم که پردازشي را درون صف قرار دهند.

2- آخرين آيتم موجود در صف پردازش‌ها را با استفاده از متد Dequeue برداشته و آن را پردازش مي‌کنيم.

3- اگر پردازش آخرين آيتم در يک برش زماني يا همان تيک ساعت به‌پايان رسيد که آن را از صف خارج مي‌کنيم. اما اگر به‌پايان نرسيده بود، با استفاده Enqueue آن را دوباره به صف برمي‌گردانيم. تا در برش زماني بعدي اجرا شود.

به‌سادگي الگوريتم راندروبين را شبيه‌سازي کرديم. بهتر است آيتم‌هاي درون صف از جنس Pointer-To-Function باشند. يعني در هر برش زماني تابعي که اشاره‌گر آن در صف قرار دارد فراخواني شود و سپس در برش‌هاي زماني ديگر به کار خود ادامه دهد.

نمونه کدي که به‌زبان C# است و بيان‌کننده الگوريتم بالاست را مي‌توانيد با مراجعه به آدرس زير دريافت کنيد:

براي پياده‌سازي صف روش‌هاي متفاوتي وجود دارد. ساده‌ترين آنها استفاده از آرايه‌هاست ولي مي‌توانيد آن را با ليست پيوندي نيز پياده کنيد.

اميربهاالدين سبط‌الشيخ