موقف من الحياة اليومية

راجل عند كاشير سوبرماركت بعربية مليانة حاجات، ووراه راجل ماسك علبة لبن واحدة وبيبص في ساعته.
صورة توضيحية مولّدة بالـ AI

إنت في السوبرماركت، معاك علبة لبن واحدة. واللي قدامك معاه 3 عربيات مليانين.

هتستنى ربع ساعة علشان حاجة بتاخد 10 ثواني. وعلشان كده بعض المحلات عاملة كاشير مخصوص للي معاهم حاجات قليلة.

نظام التشغيل بيواجه نفس السؤال كل لحظة: عنده برامج كتير عايزة المعالج، مين يشتغل الأول؟ والإجابة دي اسمها Scheduling.

خلاصة سريعة

  • الـ Thread نقطة تنفيذ جوه الـ Process: ليه Registers وStack خاصين، بس بيشارك الذاكرة مع باقي الـ Threads في نفس الـ Process.
  • الـ Scheduler بيختار مين يشتغل، وفيه مقاييس متعارضة: Turnaround time (المهمة خلصت إمتى) وResponse time (بدأت إمتى).
  • SJF بيحسّن الـ Turnaround، وRound Robin بيحسّن الـ Response، وأنظمة زي Windows بتستخدم شكل من MLFQ بيوازن بين الاتنين.

ببساطة

الـ Thread: الـ Process زي مطبخ، والـ Threads زي كذا طباخ في نفس المطبخ: بيشتغلوا في نفس الوقت، وبيستخدموا نفس التلاجة ونفس الأدوات، بس كل واحد ماسك وصفته.

الـ Scheduling: زي ترتيب الطابور: ممكن أول ما يوصل يتخدم، أو الأقصر يتخدم الأول، أو كل واحد ياخد دقيقة بالدور. وكل طريقة كويسة في حاجة ووحشة في حاجة.

بالتفصيل

1 - الـ Thread

الـ Process العادي فيه نقطة تنفيذ واحدة: Program Counter واحد. الـ Process اللي فيه كذا Thread فيه كذا نقطة تنفيذ، كل واحدة ليها:

  • Program Counter خاص.
  • Registers خاصة.
  • Stack خاص (للمتغيرات المحلية واستدعاء الدوال).

بس كلهم بيشاركوا نفس الـ Address space: نفس الكود، ونفس البيانات العامة، ونفس الـ Heap.

الفرق مع الـ Process:

  • التبديل بين Threads في نفس الـ Process مش محتاج يغيّر جدول ترجمة الذاكرة، لأن الذاكرة واحدة.
  • بيانات كل Thread بتتحفظ في TCB (Thread Control Block)، زي الـ PCB للـ Process.
الـ Threads بتشارك الكود والبيانات والـ Heap، وكل واحد ليه Stack وRegisters خاصين.

ليه نستخدم Threads؟

1 - التوازي: برنامج بيشتغل على بيانات كبيرة، يقسمها على كذا Thread، وكل Thread على Core، زي ما شفنا في مقال الـ Multicore. 2 - ما يعلقش وهو مستني: Thread مستني القرص أو الشبكة، والتاني يكمّل شغل. وعلشان كده برامج زي Web servers وقواعد البيانات بتستخدم Threads.

Threads ولا Processes؟ الـ Threads أسهل لما تحتاج تشارك بيانات كتير. والـ Processes أنسب للمهام المنفصلة اللي مش محتاجة تشارك حاجة.

2 - مقاييس الـ Scheduling

علشان نقارن طرق الاختيار، محتاجين مقياس:

  • Turnaround time (زمن الإنجاز) = وقت الانتهاء − وقت الوصول. يعني المهمة خلصت بعد قد إيه.
  • Response time (زمن الاستجابة) = وقت أول تشغيل − وقت الوصول. يعني المهمة بدأت بعد قد إيه، وده اللي بيفرق مع المستخدم اللي قاعد قدام الشاشة.
  • Fairness (العدل): كل مهمة تاخد نصيبها.

والأداء والعدل غالبًا عكس بعض: لو حسّنت واحد، التاني بيتأثر.

3 - FIFO: أول واحد يوصل يتخدم

FIFO (First In, First Out)، وبتتسمى كمان FCFS (First Come, First Served): المهام بتشتغل بترتيب وصولها.

مثال: 3 مهام A وB وC، كل واحدة 10 ثواني: A تخلص عند 10، وB عند 20، وC عند 30، فمتوسط الـ Turnaround = 20 ثانية.

المشكلة: لو A بتاخد 100 ثانية، وB وC 10 ثواني بس: B وC هيستنوا A تخلص الأول، فالمتوسط يبقى 110 ثانية. وده اسمه Convoy effect: المهام القصيرة محبوسة ورا مهمة طويلة، زي طابور السوبرماركت.

4 - SJF وSTCF: الأقصر الأول

SJF (Shortest Job First): شغّل الأقصر الأول. في نفس المثال: B وC الأول، وبعدين A، فالمتوسط ينزل لـ 50 ثانية.

بس لو B وC وصلوا متأخر 10 ثواني، وA كانت بدأت خلاص؟ SJF مش بيوقف حد بدأ، فـ B وC هيستنوا تاني، والمتوسط 103.33 ثانية.

الحل: STCF (Shortest Time-to-Completion First): أول ما مهمة جديدة توصل، شوف مين فاضله أقل وقت، ولو هي الجديدة وقّف القديمة وشغّلها. في نفس الحالة، المتوسط يرجع 50 ثانية.

وإيقاف مهمة شغالة علشان غيرها اسمه Preemption، والـ Scheduler اللي بيعمل كده اسمه Preemptive. وتقريبًا كل الـ Schedulers الحديثة Preemptive، والطرق اللي ما بتوقفش حد كانت أيام الـ Batch زمان.

5 - Round Robin: كل واحد ياخد دوره

SJF وSTCF ممتازين للـ Turnaround، بس وحشين للـ Response: المهمة التالتة لازم تستنى الاتنين اللي قبلها يخلصوا خالص. وتخيّل إنك بتكتب على الكيبورد ومستني 10 ثواني علشان الحرف يظهر.

Round Robin (RR): كل مهمة تشتغل فترة قصيرة اسمها Time slice (أو Quantum)، وبعدين اللي بعدها، وهكذا بالدور. والـ Time slice لازم يكون مضاعف لفترة الـ Timer interrupt، يعني لو الـ Timer كل 10 ملّي ثانية، الـ Slice ممكن 10 أو 20 أو أكتر.

مثال: 3 مهام، كل واحدة 5 ثواني، وSlice ثانية واحدة:

  • SJF: متوسط الـ Response = 5 ثواني.
  • Round Robin: متوسط الـ Response = 1 ثانية.

بس طول الـ Slice مهم:

  • قصير جدًا: الـ Response أحسن، بس وقت كتير بيضيع في الـ Context switch. لو الـ Slice 10 ملّي ثانية والتبديل بياخد 1 ملّي ثانية، يبقى حوالي 10% من الوقت ضايع. ولو الـ Slice 100 ملّي ثانية، الضايع أقل من 1%.
  • وكمان التبديل بيبوّظ الحاجات اللي المعالج كان شايلها للمهمة، زي محتويات الـ Cache والـ TLB والـ Branch predictor.
SJF بيخلّص المهام واحدة واحدة، وRound Robin بيدّي كل مهمة شوية بالدور، فكل المهام بتبدأ بسرعة.

6 - MLFQ: نتعلم من اللي فات

المشكلة إن نظام التشغيل ما يعرفش المهمة هتاخد قد إيه. فالحل: يراقب سلوكها ويقرر.

MLFQ (Multi-Level Feedback Queue، طوابير متعددة المستويات بالتغذية الراجعة):

1 - فيه طوابير بأولويات، والأعلى أولوية يشتغل الأول. 2 - المهام اللي نفس الأولوية بتشتغل Round Robin. 3 - أي مهمة جديدة تبدأ في أعلى طابور. 4 - لو المهمة استهلكت نصيبها من الوقت في مستوى، تنزل مستوى. 5 - كل فترة، كل المهام ترجع لفوق.

النتيجة: المهام القصيرة والتفاعلية (زي الكتابة) بتخلص بسرعة وهي فوق، والمهام الطويلة بتنزل بس بتاخد نصيبها في الآخر. وأنظمة زي BSD UNIX وSolaris وWindows NT واللي بعده بتستخدم شكل من MLFQ.

7 - الـ Starvation

الـ Starvation (التجويع): مهمة ما تاخدش وقت معالج خالص، لأن فيه دايمًا مهام أعلى منها. في MLFQ من غير القاعدة الخامسة، لو فيه مهام تفاعلية كتير، المهام الطويلة عمرها ما تشتغل. وعلشان كده القاعدة الخامسة (الرجوع لفوق كل فترة) موجودة.

أخطاء شائعة

  • «الـ Thread والـ Process نفس الحاجة»: الـ Threads بتشارك نفس الذاكرة، والـ Processes معزولة.
  • «الـ Time slice الأقصر دايمًا أحسن»: الأقصر جدًا بيضيّع وقت في التبديل.
  • «SJF أحسن طريقة في كل حاجة»: أحسن للـ Turnaround، بس وحش للـ Response.
  • «نظام التشغيل عارف كل مهمة هتاخد قد إيه»: ما يعرفش، وعلشان كده MLFQ بيتعلم من السلوك.
  • «المهمة الواطية الأولوية هتشتغل في الآخر أكيد»: ممكن يحصلها Starvation لو مفيش آلية بترفعها.

المصطلحات

  • الخيط (Thread): نقطة تنفيذ داخل الـ Process تشارك ذاكرته ولها سجلات ومكدس خاص.
  • الجدولة (Scheduling): اختيار المهمة التي تعمل على المعالج.
  • زمن الإنجاز (Turnaround time): الوقت من وصول المهمة حتى انتهائها.
  • زمن الاستجابة (Response time): الوقت من وصول المهمة حتى أول تشغيل لها.
  • الأسبقية بالوصول (FIFO): تشغيل المهام بترتيب وصولها.
  • الأقصر أولًا (SJF): تشغيل المهمة الأقصر قبل غيرها.
  • الإيقاف القسري (Preemption): إيقاف مهمة تعمل لتشغيل أخرى.
  • التناوب الدائري (Round Robin): تشغيل كل مهمة فترة قصيرة بالدور.
  • الطوابير متعددة المستويات (MLFQ): جدولة بطوابير أولويات تتغير حسب سلوك المهمة.
  • التجويع (Starvation): حرمان مهمة من وقت المعالج.

اختبر نفسك

3 مهام: A بتاخد 100 ثانية، وB وC كل واحدة 10. بطريقة FIFO وA أول واحدة، متوسط الـ Turnaround كام؟

إظهار الإجابة

الإجابة الصحيحة: 110 ثانية

110 ثانية.
A تخلص عند 100، وB عند 110، وC عند 120، والمتوسط 110، وده الـ Convoy effect.

إنت بتكتب على الكيبورد، وعايز الحرف يظهر بسرعة حتى لو فيه مهام تانية شغالة. أنهي مقياس يهمك؟

إظهار الإجابة

الإجابة الصحيحة: الـ Response time

الـ Response time.
المهم إن المهمة تبدأ بسرعة، وده اللي Round Robin بيحسّنه.

إيه اللي بيمنع الـ Starvation في MLFQ؟

إظهار الإجابة

الإجابة الصحيحة: إن كل المهام بترجع لأعلى طابور كل فترة

الرفع الدوري.
كل فترة كل المهام بترجع لفوق، فحتى المهام الطويلة بتاخد نصيبها.