الگوریتم FIFO*
ماهان شبکه ایرانیان،
در **سیستمعامل** وقتی گفته میشود **الگوریتم FIFO**، معمولاً منظور **First In, First Out** است. در ادامه توضیح **دقیق، فنی و ساختاریافته** از FIFO در سیستمعامل ارائه میشود.
---
## تعریف FIFO
**FIFO (First In, First Out)** الگوریتمی است که در آن:
> اولین پردازه/درخواست/آیتمی که وارد سیستم میشود، اولین موردی است که پردازش یا خارج میشود.
مشابه صف (Queue) در دنیای واقعی.
---
## کاربردهای FIFO در سیستمعامل
### ۱. زمانبندی پردازهها (CPU Scheduling)
#### نحوه عملکرد
- پردازهها به ترتیب ورود در صف قرار میگیرند
- CPU هر پردازه را **تا پایان اجرا** در اختیار میگذارد
- بدون وقفه (Non-Preemptive)
#### ویژگیها
- سادهترین الگوریتم زمانبندی
- بدون اولویت
- بدون Context Switch اضافی
#### مثال
پردازهها به ترتیب ورود:
```
P1 → P2 → P3
```
CPU ابتدا P1، سپس P2 و بعد P3 را کامل اجرا میکند.
---
### ۲. مدیریت صفها در سیستمعامل
FIFO در موارد زیر استفاده میشود:
- صف I/O
- صف پرینتر
- صف درخواست دیسک (در موارد ساده)
- صف شبکه
---
### ۳. FIFO در IPC (ارتباط بین پردازهای)
#### Named Pipe (FIFO)
در لینوکس:
```bash
mkfifo mypipe
```
ویژگیها:
- دادهها به همان ترتیبی خوانده میشوند که نوشته شدهاند
- ارتباط یکطرفه یا دوطرفه
- سطح کاربری (User Space)
---
## مزایای FIFO
- پیادهسازی بسیار ساده
- رفتار کاملاً قابل پیشبینی
- بدون starvation (گرسنگی پردازه)
---
## معایب FIFO (بسیار مهم)
### ۱. Convoy Effect
اگر یک پردازه سنگین در ابتدا باشد:
- همه پردازههای سبک پشت آن منتظر میمانند
- کاهش شدید کارایی سیستم
### ۲. زمان انتظار بالا
- زمان پاسخ ضعیف برای پردازههای کوتاه
- نامناسب برای سیستمهای تعاملی
### ۳. عدم بهینگی
- متوسط زمان انتظار بالا
- نسبت به SJF و Round Robin ضعیفتر است
---
## FIFO در مدیریت حافظه (Page Replacement)
در این کاربرد:
- قدیمیترین صفحهای که وارد حافظه شده حذف میشود
### مشکل مهم: Belady’s Anomaly
افزایش تعداد فریمها میتواند باعث:
- **افزایش Page Fault** شود (رفتار غیرمنطقی)
---
## مقایسه کوتاه
| الگوریتم | Preemptive | زمان پاسخ | پیچیدگی |
|-------|----------|-----------|---------|
| FIFO | ❌ | ضعیف | بسیار ساده |
| SJF | ❌/✅ | عالی | پیچیده |
| Round Robin | ✅ | خوب | متوسط |
---
## نتیجهگیری
- FIFO ساده اما **غیربهینه**
- مناسب آموزش، سیستمهای ساده یا Batch
- نامناسب برای Real-Time و Interactive Systems
---
اگر منظورت:
- FIFO در **زمانبندی CPU**
- FIFO در **حافظه**
- FIFO در **IPC لینوکس**
است، مشخص کن تا **دقیقاً همان بخش را با مثال عددی و نمودار زمانی** توضیح بدهم.