برنامه‌ها به‌صف!

برای اجرای چند برنامه در سیستم عامل، الگوریتم‌های مختلفی وجود دارد که هر کدام مزایا و معایبی دارند، یکی از این الگوریتم‌ها الگوریتم 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# است و بیان‌کننده الگوریتم بالاست را می‌توانید با مراجعه به آدرس زیر دریافت کنید:

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

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