صف (رایانه)

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

خروج به ترتیب ورود (به انگلیسی: FIFO یا First In, First Out) یکی از روش‌های سازماندهی کنترل داده با توجه به زمان و اولویت‌بندی است. این اصطلاح، اصل تکنیک پردازش صف یا برآوردن تقاضای عرضه شده به وسیله راهکار «اولین ورودی، اولین دریافت کننده خدمات» (FCFS) را توصیف می‌نماید: هر مهره‌ای که زودتر وارد شود، زود تر بررسی می‌گردد و هر مهره‌ای پس از آن وارد شود صبر می‌کند تا اعمال انجام گرفته روی مهره اول تمام شود.

بنا بر این، این موضوع شبیه رفتار صف بندی انسان‌ها است، جاییکه افراد صف را به ترتیب ورودشان ترک می‌نمایند. یازمانیکه در پشت چراغ راهنمایی منتظر نوبت خود می‌شوند. FCFS نیز نام دیگری برای الگوریتم زمانبندی سیستم‌عامل FIFO است. روشی که به هر فرایندی زمانی از زمان پردازنده را مطابق با ترتیب ورودش اختصاص می‌دهد. در معنای وسیع تر، سرواژه LIFO یا «آخرین ورودی، اولین خروجی» متضاد FIFO است. با در نظر گرفتن واژه FILO به معنای «اولین ورودی، آخرین خروجی» تفاوت این دو واژه آشکار تر می‌شود. در واقع هر دو حالت خاصی از یک لیست عام هستند. تفاوت در داده‌ها وجود ندارد. بلکه در قواعد برای دستیابی به محتوا است.

علم رایانه[ویرایش]

ساختمان داده[ویرایش]

در علم رایانه این واژه اشاره دارد به نحوه پردازش داده ذخیره شده در یک صف. هر عنصر در یک داده ساختار صف ذخیره می‌شود. اولین داده اضافه شده به صف، اولین داده‌ای خواهذ بود که بر داشته می‌شود. بنا بر این، پردازش از نظر زمانی به همین ترتیب پیش می‌رود. این رفتار معمول برای یک صف است.کد زیر نمونه‌ای از این داده ساختار است.

struct fifo_node 
{
  struct fifo_node *next;
  value_type value;
};
 
class fifo
{
  fifo_node *front;
  fifo_node *back;
  fifo_node *dequeue(void)
  {
    fifo_node *tmp = front;
    front = front->next;
    return tmp;
  }
  queue(value)
  {
    fifo_node *tempNode = new fifo_node;
    tempNode->value = value;
    back->next = tempNode;
    back = tempNode;
  }
};

اول سر یا ته[ویرایش]

برنامه نویسان و کاربران صف FIFO بایستی توجه زیادی به کاربرد واژگان head و tail برای اشاره به دو سر صف داشته باشند. برای بسیاری از افراد داده‌ها باید از tail وارد صف شوند و تا زمانیکه به head برسند در صف بمانند و صف را از آنجا ترک نمایند. این نقطه نظر را می‌توان با صف افرادی که برای در یافت سرویس خاصی منتظر مانده‌اند قیاس نمود و به کاربرد دو واژه «جلو» و «عقب» در این مثال تشبیه نمود. اگر چه، افراد دیگر عقیده دارند که داده‌ها از head وارد صف می‌شوند و از tail آن را ترک می‌نمایند. همجون ترتیب عبور غذا در درون یک مار. صف‌هایی که به این طریق پیاده سازی شده‌اند، در جایگاه‌هایی مانند سیستم‌عامل GNU/Linux ظاهر می‌شوند.

زمانبندی دیسک[ویرایش]

کنترل کنندگان دیسک از FIFO به عنوان یک الگوریتم زمانبندی استفاده می‌کنند تا مطابق با آن خدمات مربوط به درخواست‌های ورود و خروج اطلاعات را ارائه کنند. First Input First Output در این حالت اولین پردازه که وارد می شود همان پردازه نیز پردازش می شود و تا زمانی که این پردازه تمام نشود و یا نیاز به یک منبع جدید نداشه باشد پردازنده را در اختیار خود می گیرد تا به پایان برسد و در این زمان پردازنده آزاد شده و به پردازه های دیگر اختصاص می یابد.یکی از مزیت های این حالت در زمان بندی می توان به ساده بودن و پیاده سازی راحت آن اشاره نمود . از معایب آن می توان گفت که پردازنده را مشغول یک پردازه می کند و تا تمام نشدن آن هیچ پردازه ی دیگری اجرا نمی‌شود حتی اگر این پردازه خیلی مهم تر از پردازه اولی باشد.

شبکه سازی[ویرایش]

سوئیچ‌ها و مسیریاب‌های مورد استفاده در شبکه سازی، از FIFOها برای نگهداری بسته‌های اطلاعاتی در مسیر مقصد بعدی آن‌ها استفاده می‌کنند. به طور نمونه در هر اتصال شبکه حد اقل یک ساختار FIFO استفاده می‌شود. برخی دستگاه‌ها، برای صف بندی همزمان و مستقل انواع مختلف اطلاعات از چند FIFO استفاده می‌کنند.

الکترونیک[ویرایش]

FIFO معمولاً در مدارهای الکترونیکی برای بافر کردن وکنترل جریان از سخت‌افزار به نرم‌افزار بکار می‌رود. در سخت‌افزار، FIFO عمدتاً از یک سری اشاره گرهای نوشتاری و خواندنی و حافظه تشکیل شده‌است. حافظه می‌تواند SRAM,Flip Flop,latch یا هر نوع حافظه مناسب دیگری باشد. برای FIFOهای با اندازه بزرگتر معمولاً از dual-port SRAM استفاده می‌شود. که در آن از یک پورت برای نوشتن و از دیگری برای خواندن استفاده می‌شود. FIFOّهای همزمان نوعی FIFO هستند که در آن‌ها از کلاک واحد برای خواندن و نوشتن استفاده می‌شود. FIFOهای غیر همزمان از کلاک‌های مختلف برای خواندن و نوشتن استفاده می‌کنند. یکی از پیاده سازی‌های رایج FIFOهای غیر همزمان از Gray Code برای اشاره گرهای خواندن و نوشتن استفاده می‌کند.

منابع[ویرایش]

Accessories-text-editor.svg این مقاله در باره رایانش خُرد است. با گسترش آن به ویکی‌پدیا کمک کنید.