خروج به ترتیب ورود (رایانه و الکترونیک)

خروج به ترتیب ورود (به انگلیسی: 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 برای اشاره گرهای خواندن و نوشتن استفاده می‌کند.

منابع

• http://en.wikipedia.org/wiki/FIFO
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford Introductions to Algorithms (2003). MIT Press. ISBN 0-262-03293-7, pp. ۲۰۵–۲۱۳، ۵۰۱–۵۰۵