ما معنى First Come, First Served (FCFS) في الخوارزميات وهياكل البيانات؟
First Come, First Served (ويُختصر FCFS، وترجمته "من يصل أولاً يُخدَم أولاً") هي أبسط خوارزميات جدولة العمليات: تُنفَّذ المهام بالترتيب الزمني نفسه الذي وصلت به إلى قائمة الانتظار، دون أولويات ولا مقاطعة. الطلب الأول الذي يدخل هو أول ما يُعالَج حتى ينتهي بالكامل، ثم يأتي الذي يليه. الفكرة مطابقة تماماً لطابور الخبز أو صندوق الدفع في السوبرماركت: مكانك في الصف هو ما يحدد دورك، لا حجم مهمتك ولا أهميتها.
في هذا الشرح سنرى كيف تعمل FCFS فعلياً بمثال محسوب بالأرقام، ولماذا تسبب أحياناً مشكلة شهيرة اسمها "تأثير القافلة"، ومتى تكون خياراً جيداً ومتى لا تكون.
كيف تعمل FCFS داخلياً؟
تعتمد الخوارزمية على بنية بيانات واحدة بسيطة: الطابور (Queue) الذي يعمل بمبدأ FIFO (أول داخل، أول خارج).
- عندما تصل عملية جديدة تُضاف إلى نهاية الطابور (عملية
enqueue). - يأخذ المعالج دائماً العملية من بداية الطابور (عملية
dequeue) وينفّذها حتى تنتهي. - FCFS خوارزمية غير قابلة للمقاطعة (Non-preemptive): بمجرد أن تبدأ عملية، تحتفظ بالمعالج حتى تُكمل عملها، ولا يمكن لعملية أحدث أن تزيحها مهما كانت قصيرة.
هذه البساطة تجعل تنفيذها لا يكلّف سوى سطور قليلة، ويكفي فيها زمن ثابت O(1) لإضافة عملية أو سحبها.
مثال محسوب خطوة بخطوة
لنفترض ثلاث عمليات وصلت جميعها في اللحظة صفر بهذا الترتيب، مع زمن تنفيذ (Burst Time) مختلف لكل منها:
| العملية | زمن الوصول | زمن التنفيذ |
|---|---|---|
| P1 | 0 | 24 |
| P2 | 0 | 3 |
| P3 | 0 | 3 |
بما أن الترتيب هو P1 ثم P2 ثم P3، تُنفَّذ هكذا على المخطط الزمني:
| P1 (0 → 24) | P2 (24 → 27) | P3 (27 → 30) |
الآن نحسب زمن الانتظار لكل عملية (متى بدأت مطروحاً منه زمن وصولها):
- P1 تنتظر: 0
- P2 تنتظر: 24
- P3 تنتظر: 27
متوسط زمن الانتظار = (0 + 24 + 27) ÷ 3 = 17 وحدة زمنية.
لاحظ الكارثة: عمليتان قصيرتان جداً (3 وحدات لكل منهما) اضطرتا للانتظار خلف عملية عملاقة. لو أننا رتّبنا التنفيذ بالعكس (P2 ثم P3 ثم P1) لأصبح متوسط الانتظار 3 وحدات فقط بدل 17. هذا الفارق الضخم هو جوهر عيب FCFS.
تأثير القافلة (Convoy Effect)
المشكلة التي رأيناها لها اسم في علم الحاسوب: تأثير القافلة. عندما تجلس عملية طويلة في المقدمة، تتكدّس خلفها عمليات قصيرة كثيرة مثل سيارات صغيرة عالقة خلف شاحنة بطيئة على طريق ضيّق. النتيجة أن متوسط زمن الانتظار يرتفع بشدة، ويقل استغلال بقية موارد النظام (مثل أجهزة الإدخال/الإخراج التي تبقى عاطلة بينما ينشغل المعالج بعملية واحدة طويلة).
هذه ليست مشكلة نظرية فقط؛ فهي سبب رئيسي في أن أنظمة التشغيل الحديثة لا تستخدم FCFS بمفردها لجدولة المعالج، بل تلجأ لخوارزميات أذكى أو تمزجها معاً.
المزايا والعيوب باختصار
المزايا:
- بساطة مطلقة في الفهم والبرمجة.
- عدالة في الترتيب: لا تتعرّض أي عملية للتجويع (Starvation)؛ فكل عملية ستُنفَّذ حتماً حين يأتي دورها.
- كلفة إدارية (Overhead) منخفضة جداً لأنها لا تتخذ قرارات معقّدة.
العيوب:
- متوسط زمن انتظار مرتفع بسبب تأثير القافلة.
- سيئة لأنظمة التفاعل الحيّة والوقت الحقيقي التي تحتاج استجابة سريعة.
- لا تراعي أولوية المهمة ولا قِصرها.
FCFS مقابل الخوارزميات الأخرى
| المعيار | FCFS | SJF (الأقصر أولاً) | Round Robin (الدوري) |
|---|---|---|---|
| أساس الاختيار | ترتيب الوصول | أقصر زمن تنفيذ | شريحة زمنية دوّارة |
| قابلة للمقاطعة؟ | لا | غالباً لا | نعم |
| متوسط الانتظار | مرتفع | الأدنى نظرياً | متوسط |
| خطر التجويع | لا يوجد | نعم للعمليات الطويلة | لا يوجد |
| الأنسب لـ | أنظمة الدفعات البسيطة | تقليل زمن الانتظار | الأنظمة التفاعلية |
خلاصة الاختيار: استخدم FCFS حين تكون البساطة والعدالة أهم من السرعة، كأنظمة معالجة الدفعات (Batch) أو الطوابير التي تريد فيها احتراماً صارماً لترتيب الوصول. تجنّبها في الأنظمة التفاعلية أو حين تتفاوت أزمنة المهام بشكل كبير.
أين تلتقي بها عملياً؟
FCFS ليست مفهوماً أكاديمياً معزولاً؛ فمنطقها موجود في: طوابير الطباعة (أول ملف يُرسَل يُطبَع أولاً)، معالجة طلبات الشبكة بترتيب وصولها، أنظمة التذاكر وقوائم الانتظار في الخدمات. وكلما رأيت بنية Queue في الكود، فأنت غالباً أمام تطبيق مباشر لمبدأ FCFS.
نصيحة عملية
عند البرمجة، لا تخلط بين الطابور (Queue بمبدأ FIFO) الذي يجسّد FCFS، وبين المكدّس (Stack بمبدأ LIFO – آخر داخل أول خارج) الذي يعطي سلوكاً معاكساً تماماً. خطأ شائع بين المبتدئين استخدام Stack ظنّاً أنه ينفّذ الطلبات بترتيب وصولها، فيحصلون على ترتيب مقلوب. القاعدة: FCFS = Queue = FIFO، احفظها كوحدة واحدة.
الأسئلة الشائعة
هل FCFS قابلة للمقاطعة؟ لا. هي خوارزمية غير قابلة للمقاطعة؛ ما إن تبدأ عملية حتى تُكمل تنفيذها كاملاً قبل أن تبدأ التالية.
ما الفرق بين FCFS و FIFO؟ عملياً هما المبدأ نفسه. FIFO مصطلح عام لبنية البيانات (الطابور)، أما FCFS فهو اسم خوارزمية الجدولة التي تطبّق هذا المبدأ على العمليات.
هل تسبب FCFS تجويعاً (Starvation) لبعض العمليات؟ لا. هذا أحد أهم محاسنها؛ فكل عملية تصل ستُنفَّذ حتماً عند بلوغ دورها، بعكس خوارزمية "الأقصر أولاً" التي قد تؤخّر العملية الطويلة إلى ما لا نهاية.
لماذا لا تستخدمها أنظمة التشغيل الحديثة وحدها؟ بسبب تأثير القافلة الذي يرفع زمن الانتظار ويقلّل الاستجابة، لذا تعتمد الأنظمة الحديثة على خوارزميات متعددة المستويات أو الجدولة الدورية لتحقيق توازن أفضل.