طابور الخادم الواحد: المحاكاة حدثا بعد حدث

يتتبع هذا القسم محاكاة حاسوبية لطابور FIFO بخادم واحد، حدثا بعد حدث. نبدأ من نظام فارغ عند t = 0، ونطبق روتيني حدث الوصول وحدث المغادرة، ونأخذ لقطة (snapshot) للتمثيل الحاسوبي بعد كل حدث من الأحداث الـ13، ونتوقف عند t = 8.6 حين ينتهي انتظار العميل السادس. بعد ذلك يحول مولد التقارير العدادات الإحصائية إلى مقاييس الأداء الثلاثة.

الأهداف

• استرجاع مفاهيم الطوابير التي تحتاجها المحاكاة: الوصول، والخدمة، والـFIFO، والتأخير في الطابور، وQ(t) وB(t).
• وصف كيف ينظم برنامج محاكاة الأحداث المتقطعة حول تقديم الزمن إلى الحدث التالي.
• تسمية كل متغير حالة، وقائمة الأحداث، والعدادات الإحصائية الأربعة.
• تطبيق قواعد التحديث الدقيقة لروتيني حدث الوصول وحدث المغادرة.
• تتبع الأحداث الـ13 كلها في التمرين حتى t = 8.6 وإعداد اللقطة بعد كل حدث.
• حساب d(n) وq(n) وu(n) وشرح ما يقوله كل منها عن النظام.

1. مفاهيم الطوابير التي نحتاجها

العناصر الأساسية

• العميل (customer): أي شيء يصل إلى منشأة ويحتاج إلى خدمة (أشخاص، آلات، شاحنات، رسائل بريد إلكتروني).
• الخادم (server): أي مورد يقدم الخدمة. وهو في أي لحظة إما مشغول (busy) أو خامل (idle).
• مجتمع العملاء (calling population): العملاء المحتملون. نعده هنا غير محدود، فلا يتأثر معدل الوصول بعدد العملاء الموجودين فعلا في النظام.
• سعة النظام (system capacity): غير محدودة في هذا التمرين.

العميل الذي ينتظر يكون في الطابور. أما العميل الذي تجري خدمته فهو داخل النظام لكنه ليس في الطابور.

الوصول والخدمة

$A_i$ هو زمن ما بين الوصول (inter-arrival time) للعميل i-1 والعميل i، ولذلك فإن زمن وصول أي عميل هو المجموع التراكمي لأزمنة ما بين الوصول. و$S_i$ هو زمن الخدمة (service time) للعميل i. وكلاهما متغير عشوائي مستقل ومتماثل التوزيع (IID)، وغالبا ما يكون أسيا، وهو ما يعطي وصولا من نوع بواسون (Poisson). وفي هذا التمرين تعطى القيم كما يلي:

قاعدة الطابور

تحدد قاعدة الطابور (queue discipline) أي عميل منتظر يخدم بعد ذلك حين يتحرر الخادم: FIFO (الداخل أولا يخرج أولا)، أو LIFO (الداخل أخيرا يخرج أولا)، أو SIRO (الخدمة بترتيب عشوائي)، أو SPT (أقصر زمن معالجة أولا)، أو PR (حسب الأولوية). يستخدم هذا الدرس FIFO، فيبدأ العملاء الخدمة بترتيب وصولهم: العميل k يستخدم زمن الخدمة $S_k$، والموقع الأول في مصفوفة أزمنة الوصول يخص دائما العميل التالي في الخدمة.

التأخير في الطابور

التأخير (delay) $D_i$ للعميل i هو الزمن الذي ينتظره في الطابور: زمن بدء خدمته مطروحا منه زمن وصوله. إذا كان الخادم خاملا عند وصوله تبدأ الخدمة فورا ويكون $D_i = 0$، ويبقى هذا التأخير الصفري تأخيرا مرصودا يحتسب. وبوجه عام، زمن المغادرة هو زمن الوصول زائد التأخير زائد زمن الخدمة.

Q(t) و B(t)

• Q(t) هو عدد العملاء في الطابور عند الزمن t (العميل الذي تجري خدمته لا يحتسب).
• B(t) هي دالة الانشغال (busy function): 1 إذا كان الخادم مشغولا عند الزمن t، و0 إذا كان خاملا.

كلتا الدالتين لا تتغير إلا عند الأحداث، فهي ثابتة بين أي حدثين. والمساحة تحت كل منهما مجموع مستطيلات، مساحة كل منها القيمة مضروبة في طول الفترة.

مقاييس الأداء الثلاثة

$$\begin{aligned} d(n) &= \dfrac{\sum_{i=1}^{n} D_i}{n} \\[6pt] q(n) &= \dfrac{\int_0^{T(n)} Q(t)\,dt}{T(n)} \\[6pt] u(n) &= \dfrac{\int_0^{T(n)} B(t)\,dt}{T(n)} \end{aligned}$$

حيث $D_i$ تأخير العميل $i$، و$n$ عدد التأخيرات التي يرصدها التشغيل، و$T(n)$ زمن انتهاء التشغيل (عند اكتمال التأخير رقم $n$)، و$Q(t)$ و$B(t)$ الدالتان السلميتان أعلاه. وكل تكامل هو المساحة تحت الدالة من $0$ إلى $T(n)$.

يريد العملاء أن يكون d(n) وq(n) صغيرين، وتريد المؤسسة أن يكون u(n) مرتفعا. والتصميم الجيد يوازن بين الأمرين.

قاعدة التوقف

يتوقف التشغيل حين يرصد n تأخيرا في الطابور، وهنا n = 6. ويجري هذا الفحص بعد كل حدث. وفي التمرين يحدث ذلك عند t = 8.6، حين يغادر العميل 5 ويبدأ العميل 6 خدمته، فيكون T(6) = 8.6. لاحظ أن التشغيل لا يتوقف عند وصول العميل 6 (عند 5.6)، بل يتوقف حين ينتهي انتظاره.

2. كيف ينظم البرنامج

تقديم الزمن إلى الحدث التالي

1. اضبط ساعة المحاكاة على 0.
2. اقرأ أزمنة الأحداث المستقبلية من قائمة الأحداث.
3. قدم الساعة إلى الحدث الأقرب، أي أصغر زمن في القائمة.
4. نفذ ذلك الحدث، أي تحديث حالة النظام والعدادات الإحصائية، وربما قائمة الأحداث.
5. كرر حتى تتحقق قاعدة التوقف.

تقفز الساعة من حدث إلى الحدث الذي يليه، وتتخطى فترات عدم النشاط. والبديل هو تقديم الزمن بخطوات ثابتة (fixed-increment time advance)، إذ تتحرك الساعة بخطوات متساوية ويعامل كل حدث يقع داخل الخطوة كأنه وقع في نهايتها، وهذا أقل دقة.

مكونات نموذج محاكاة الأحداث المتقطعة

مسار البرنامج الرئيسي

1. البداية.
2. روتين التهيئة: ضبط الساعة على 0، وتهيئة الحالة والعدادات وقائمة الأحداث.
3. كرر ما يلي:
   • روتين التوقيت: تحديد نوع الحدث التالي i، وتقديم الساعة.
   • روتين الحدث i: تحديث الحالة، وتحديث العدادات، وجدولة الأحداث المستقبلية (ويمده روتين المكتبة بالقيم العشوائية).
   • انتهت المحاكاة؟ لا: عودة إلى روتين التوقيت. نعم: الانتقال إلى مولد التقارير.
4. مولد التقارير: حساب التقديرات، وكتابة التقرير.
5. النهاية.

في هذا التمرين تعطى قيم A وS، فلا يفعل روتين المكتبة أكثر من تسليم القيمة التالية من القائمة.

3. التمثيل الحاسوبي

الحالة والساعة وقائمة الأحداث والعدادات

توجد مصفوفة أزمنة الوصول لأن البرنامج يحتاج زمن وصول العميل المنتظر حين يبدأ خدمته أخيرا، كي يحسب تأخيره.

القاعدة 1: تحديث المساحتين أولا، بالحالة السابقة

حيث $t$ قيمة الساعة الجديدة، و$\tau$ زمن آخر حدث، و$Q(\tau)$ و$B(\tau)$ عدد العملاء في الطابور وحالة الخادم قبل أن يغيرهما الحدث:

$$\begin{aligned} \int_0^{t} Q &= \int_0^{\tau} Q + Q(\tau) \times (t - \tau) \\[6pt] \int_0^{t} B &= \int_0^{\tau} B + B(\tau) \times (t - \tau) \end{aligned}$$

كل تكامل هنا عداد مساحة: من $0$ إلى $\tau$ قيمته قبل الحدث، ومن $0$ إلى $t$ قيمته بعده. ثم اجعل زمن آخر حدث مساويا للساعة، فتصبح $\tau$ مساوية لـ$t$.

بين آخر حدث واللحظة الحالية بقي طول الطابور وحالة الخادم على قيمتيهما القديمتين، وذلك المستطيل هو ما يضيفه العداد.

القاعدة 2: روتين حدث الوصول

1. تحديث المساحتين بالحالة السابقة.
2. جدولة الوصول التالي: $A = t + A_{i+1}$، حيث $t$ قيمة الساعة وi العميل الذي يصل الآن.
3. إذا كان الخادم مشغولا: إضافة 1 إلى العدد في الطابور، وتخزين قيمة الساعة في الموقع الفارغ التالي من مصفوفة أزمنة الوصول.
4. إذا كان الخادم خاملا: التأخير 0، فيضاف 1 إلى عدد التأخيرات (ويبقى إجمالي التأخير دون تغيير)، وتصبح حالة الخادم 1، وتجدول مغادرة هذا العميل $D = t + S_i$.
5. جعل زمن آخر حدث مساويا للساعة، $\tau = t$.

القاعدة 3: روتين حدث المغادرة

• الطابور فارغ: تحديث المساحتين، وجعل حالة الخادم 0 وD = ∞، وجعل زمن آخر حدث مساويا للساعة.
• الطابور غير فارغ: تحديث المساحتين، وحساب تأخير العميل الداخل إلى الخدمة بطرح الزمن الأول في المصفوفة من الساعة، وإضافته إلى إجمالي التأخير وإضافة 1 إلى عدد التأخيرات، وجدولة $D = t + S_k$ للعميل الجديد $k$، وطرح 1 من العدد في الطابور وإزاحة كل زمن في المصفوفة موقعا واحدا إلى الأمام، وجعل زمن آخر حدث مساويا للساعة.

يجب حساب التأخير قبل إزاحة المصفوفة، لأن زمن وصول العميل الداخل إلى الخدمة يبقى في الموقع الأول حتى الإزاحة فقط.

4. تتبع الأحداث حدثا بعد حدث

يضم التشغيل التالي 13 حدثا. نعرض لكل حدث: اختيار روتين التوقيت، ثم التحديثات بترتيبها، ثم اللقطة بعد الحدث. الأحداث الأربعة الأولى هي المعروضة في شرائح التمرين، وبقية الأحداث تكمل التمرين.

t = 0: التهيئة

الساعة 0، والخادم خامل، والطابور فارغ، وكل العدادات 0. أول حدث هو دائما وصول، فيكون A = A1 = 0.4 وD = ∞.

الحدث 1، t = 0.4: وصول العميل 1

• روتين التوقيت: قائمة الأحداث تحوي A = 0.4 وD = ∞، والأصغر هو A = 0.4.
• المساحتان أولا، بالحالة السابقة: Q: 0 + 0 × (0.4 - 0) = 0 وB: 0 + 0 × (0.4 - 0) = 0.
• جدولة الوصول التالي: A = 0.4 + 1.2 = 1.6 (باستخدام A2).
• الخادم خامل: يبدأ العميل 1 خدمته فورا، والتأخير 0، وعدد التأخيرات 1.
• حالة الخادم 1، وجدولة المغادرة: D = 0.4 + 2.0 = 2.4 (باستخدام S1).

الحدث 2، t = 1.6: وصول العميل 2

• روتين التوقيت: قائمة الأحداث تحوي A = 1.6 وD = 2.4، والأصغر هو A = 1.6.
• المساحتان أولا، بالحالة السابقة: Q: 0 + 0 × (1.6 - 0.4) = 0 وB: 0 + 1 × (1.6 - 0.4) = 1.2.
• جدولة الوصول التالي: A = 1.6 + 0.5 = 2.1 (باستخدام A3).
• الخادم مشغول: ينضم العميل 2 إلى الطابور، Q = 1، ويخزن الزمن 1.6 في الموقع 1.

الحدث 3، t = 2.1: وصول العميل 3

• روتين التوقيت: قائمة الأحداث تحوي A = 2.1 وD = 2.4، والأصغر هو A = 2.1.
• المساحتان أولا، بالحالة السابقة: Q: 0 + 1 × (2.1 - 1.6) = 0.5 وB: 1.2 + 1 × (2.1 - 1.6) = 1.7.
• جدولة الوصول التالي: A = 2.1 + 1.7 = 3.8 (باستخدام A4).
• الخادم مشغول: ينضم العميل 3 إلى الطابور، Q = 2، ويخزن الزمن 2.1 في الموقع 2.

الحدث 4، t = 2.4: مغادرة العميل 1

• روتين التوقيت: قائمة الأحداث تحوي A = 3.8 وD = 2.4، والأصغر هو D = 2.4.
• المساحتان أولا، بالحالة السابقة: Q: 0.5 + 2 × (2.4 - 2.1) = 1.1 وB: 1.7 + 1 × (2.4 - 2.1) = 2.0.
• يغادر العميل 2 الطابور: التأخير 2.4 - 1.6 = 0.8، ويقرأ قبل الإزاحة.
• إجمالي التأخير 0 + 0.8 = 0.8، وعدد التأخيرات 2.
• جدولة المغادرة: D = 2.4 + 0.7 = 3.1 (باستخدام S2).
• Q = 1، وتزاح المصفوفة موقعا واحدا إلى الأمام: 2.1.

الحدث 5، t = 3.1: مغادرة العميل 2

• روتين التوقيت: قائمة الأحداث تحوي A = 3.8 وD = 3.1، والأصغر هو D = 3.1.
• المساحتان أولا، بالحالة السابقة: Q: 1.1 + 1 × (3.1 - 2.4) = 1.8 وB: 2.0 + 1 × (3.1 - 2.4) = 2.7.
• يغادر العميل 3 الطابور: التأخير 3.1 - 2.1 = 1.0، ويقرأ قبل الإزاحة.
• إجمالي التأخير 0.8 + 1.0 = 1.8، وعدد التأخيرات 3.
• جدولة المغادرة: D = 3.1 + 0.2 = 3.3 (باستخدام S3).
• Q = 0، وتزاح المصفوفة موقعا واحدا إلى الأمام: فارغة.

الحدث 6، t = 3.3: مغادرة العميل 3

• روتين التوقيت: قائمة الأحداث تحوي A = 3.8 وD = 3.3، والأصغر هو D = 3.3.
• المساحتان أولا، بالحالة السابقة: Q: 1.8 + 0 × (3.3 - 3.1) = 1.8 وB: 2.7 + 1 × (3.3 - 3.1) = 2.9.
• الطابور فارغ: حالة الخادم 0 وD = ∞.

الحدث 7، t = 3.8: وصول العميل 4

• روتين التوقيت: قائمة الأحداث تحوي A = 3.8 وD = ∞، والأصغر هو A = 3.8.
• المساحتان أولا، بالحالة السابقة: Q: 1.8 + 0 × (3.8 - 3.3) = 1.8 وB: 2.9 + 0 × (3.8 - 3.3) = 2.9.
• جدولة الوصول التالي: A = 3.8 + 0.2 = 4.0 (باستخدام A5).
• الخادم خامل: يبدأ العميل 4 خدمته فورا، والتأخير 0، وعدد التأخيرات 4.
• حالة الخادم 1، وجدولة المغادرة: D = 3.8 + 1.1 = 4.9 (باستخدام S4).

الحدث 8، t = 4.0: وصول العميل 5

• روتين التوقيت: قائمة الأحداث تحوي A = 4.0 وD = 4.9، والأصغر هو A = 4.0.
• المساحتان أولا، بالحالة السابقة: Q: 1.8 + 0 × (4.0 - 3.8) = 1.8 وB: 2.9 + 1 × (4.0 - 3.8) = 3.1.
• جدولة الوصول التالي: A = 4.0 + 1.6 = 5.6 (باستخدام A6).
• الخادم مشغول: ينضم العميل 5 إلى الطابور، Q = 1، ويخزن الزمن 4.0 في الموقع 1.

الحدث 9، t = 4.9: مغادرة العميل 4

• روتين التوقيت: قائمة الأحداث تحوي A = 5.6 وD = 4.9، والأصغر هو D = 4.9.
• المساحتان أولا، بالحالة السابقة: Q: 1.8 + 1 × (4.9 - 4.0) = 2.7 وB: 3.1 + 1 × (4.9 - 4.0) = 4.0.
• يغادر العميل 5 الطابور: التأخير 4.9 - 4.0 = 0.9، ويقرأ قبل الإزاحة.
• إجمالي التأخير 1.8 + 0.9 = 2.7، وعدد التأخيرات 5.
• جدولة المغادرة: D = 4.9 + 3.7 = 8.6 (باستخدام S5).
• Q = 0، وتزاح المصفوفة موقعا واحدا إلى الأمام: فارغة.

الحدث 10، t = 5.6: وصول العميل 6

• روتين التوقيت: قائمة الأحداث تحوي A = 5.6 وD = 8.6، والأصغر هو A = 5.6.
• المساحتان أولا، بالحالة السابقة: Q: 2.7 + 0 × (5.6 - 4.9) = 2.7 وB: 4.0 + 1 × (5.6 - 4.9) = 4.7.
• جدولة الوصول التالي: A = 5.6 + 0.2 = 5.8 (باستخدام A7).
• الخادم مشغول: ينضم العميل 6 إلى الطابور، Q = 1، ويخزن الزمن 5.6 في الموقع 1.

الحدث 11، t = 5.8: وصول العميل 7

• روتين التوقيت: قائمة الأحداث تحوي A = 5.8 وD = 8.6، والأصغر هو A = 5.8.
• المساحتان أولا، بالحالة السابقة: Q: 2.7 + 1 × (5.8 - 5.6) = 2.9 وB: 4.7 + 1 × (5.8 - 5.6) = 4.9.
• جدولة الوصول التالي: A = 5.8 + 1.4 = 7.2 (باستخدام A8).
• الخادم مشغول: ينضم العميل 7 إلى الطابور، Q = 2، ويخزن الزمن 5.8 في الموقع 2.

الحدث 12، t = 7.2: وصول العميل 8

• روتين التوقيت: قائمة الأحداث تحوي A = 7.2 وD = 8.6، والأصغر هو A = 7.2.
• المساحتان أولا، بالحالة السابقة: Q: 2.9 + 2 × (7.2 - 5.8) = 5.7 وB: 4.9 + 1 × (7.2 - 5.8) = 6.3.
• جدولة الوصول التالي: A = 7.2 + 1.9 = 9.1 (باستخدام A9).
• الخادم مشغول: ينضم العميل 8 إلى الطابور، Q = 3، ويخزن الزمن 7.2 في الموقع 3.

الحدث 13، t = 8.6: مغادرة العميل 5

• روتين التوقيت: قائمة الأحداث تحوي A = 9.1 وD = 8.6، والأصغر هو D = 8.6.
• المساحتان أولا، بالحالة السابقة: Q: 5.7 + 3 × (8.6 - 7.2) = 9.9 وB: 6.3 + 1 × (8.6 - 7.2) = 7.7.
• يغادر العميل 6 الطابور: التأخير 8.6 - 5.6 = 3.0، ويقرأ قبل الإزاحة.
• إجمالي التأخير 2.7 + 3.0 = 5.7، وعدد التأخيرات 6.
• جدولة المغادرة: D = 8.6 + 0.6 = 9.2 (باستخدام S6).
• Q = 2، وتزاح المصفوفة موقعا واحدا إلى الأمام: 5.8, 7.2.
• يبلغ عدد التأخيرات 6، وهي n: تحققت قاعدة التوقف، ويعمل مولد التقارير.

التشغيل كله في جدول واحد

التأخيرات الستة

إجمالي التأخير هو مجموع التأخيرات الستة:

$$\sum D_i = 0 + 0.8 + 1.0 + 0 + 0.9 + 3.0 = 5.7$$

وجد العميلان 1 و4 الخادم خاملا، فتأخير كل منهما 0، لكن كلا منهما يحتسب مع ذلك في عدد التأخيرات.

5. Q(t) و B(t) والمساحتان

Q(t)

بتجميع الفترات حسب طول الطابور:

$$\begin{aligned} \int_0^{8.6} Q(t)\,dt &= 1 \times [(2.1 - 1.6) + (3.1 - 2.4) + (4.9 - 4.0) + (5.8 - 5.6)] \\ &\quad + 2 \times [(2.4 - 2.1) + (7.2 - 5.8)] + 3 \times [(8.6 - 7.2)] \\[6pt] &= 1 \times 2.3 + 2 \times 1.7 + 3 \times 1.4 \\[6pt] &= 2.3 + 3.4 + 4.2 = 9.9 \end{aligned}$$

وهذه هي القيمة نفسها التي بلغها عداد المساحة تحت Q عند t = 8.6: فروتينات الأحداث تبني المجموع نفسه مستطيلا بعد مستطيل.

B(t)

$$\int_0^{8.6} B(t)\,dt = 1 \times [(3.3 - 0.4) + (8.6 - 3.8)] = 2.9 + 4.8 = 7.7$$

6. مولد التقارير

حين يصل عدد التأخيرات إلى 6 يستدعي البرنامج الرئيسي مولد التقارير:

$$\begin{aligned} d(6) &= \dfrac{5.7}{6} = 0.95 \\[6pt] q(6) &= \dfrac{9.9}{8.6} = 1.15 \\[6pt] u(6) &= \dfrac{7.7}{8.6} = 0.90 \quad (89.5\%) \end{aligned}$$

تكتب شريحة التمرين معدل الاستغلال 0.9، وهو بمنزلتين عشريتين 0.90.

7. الأخطاء الشائعة

1. تحديث المساحتين بالحالة الجديدة. عند t = 2.1 يزداد طول الطابور من 1 إلى 2. التحديث الصحيح هو 0 + 1 × (2.1 - 1.6) = 0.5، أما استخدام القيمة الجديدة فيعطي 0 + 2 × (2.1 - 1.6) = 1.0، وهذا خطأ.
2. نسيان D = ∞ حين يصبح الخادم خاملا. عند t = 3.3 يكون الطابور فارغا، فيصبح الخادم خاملا وD = ∞، ويكون الحدث التالي عندئذ هو الوصول عند 3.8. أما قيمة D القديمة فتجعل روتين التوقيت يختار مغادرة لعميل غير موجود. ويجب أيضا أن تنخفض حالة الخادم إلى 0، فلا يضاف شيء إلى المساحة تحت B(t) من 3.3 إلى 3.8.
3. إزاحة المصفوفة قبل حساب التأخير. عند t = 2.4 تحوي المصفوفة 1.6, 2.1. تأخير العميل 2 هو 2.4 - 1.6 = 0.8. أما الإزاحة أولا فتعطي 2.4 - 2.1 = 0.3، وهو محسوب من زمن وصول العميل 3 لا العميل 2.
4. قاعدة التوقف. يتوقف التشغيل حين يبلغ عدد التأخيرات 6، عند t = 8.6، فيكون T(6) = 8.6. ولا يتوقف عند وصول العميل 6 (5.6) ولا عند مغادرته (9.2).

مراجعة ذاتية سريعة: التأخيرات الصفرية تحتسب في عدد التأخيرات، والعدادات لا تنقص أبدا، وبعد كل حدث يساوي زمن آخر حدث قيمة الساعة.

8. تدريب

تتبع كل تشغيل حدثا بعد حدث، بدءا من لقطة t = 0، حتى يصل عدد التأخيرات إلى n. أعط اللقطة بعد كل حدث، ثم احسب d(n) وq(n) وu(n). الإجابات في نهاية هذه الصفحة.

التشغيل 1: n = 4

التشغيل 2: n = 5

قائمة فحص لكل حدث:

1. اختر الأصغر من A وD واضبط الساعة $t$ عليه.
2. أضف $Q(\tau) \times (t - \tau)$ و$B(\tau) \times (t - \tau)$ إلى المساحتين، حيث $\tau$ زمن آخر حدث.
3. الوصول: جدولة الوصول التالي، ثم انضمام العميل إلى الطابور أو بدء خدمته.
4. المغادرة: الطابور الفارغ يعطي D = ∞، وإلا فاحسب التأخير أولا ثم أزح.
5. اجعل زمن آخر حدث مساويا للساعة، وقارن عدد التأخيرات بـn.

أهم النقاط

• تقفز الساعة $t$ من حدث إلى حدث: $t = \min(A, D)$.
• في كل حدث يجري تحديث المساحتين أولا، بالحالة السابقة.
• الخادم الخامل يعني دائما D = ∞.
• المغادرة تقرأ التأخير قبل إزاحة مصفوفة أزمنة الوصول.
• ينتهي التشغيل حين يبلغ عدد التأخيرات n، وT(n) هو قيمة الساعة عندئذ.
• يقسم مولد التقارير إجمالي التأخير على n، وكل مساحة على T(n).

الإجابات

التشغيل 1

الحدث 1، t = 0.5: وصول العميل 1. المساحتان أولا، بالحالة السابقة: Q: 0 + 0 × (0.5 - 0) = 0 وB: 0 + 0 × (0.5 - 0) = 0. جدولة الوصول التالي: A = 0.5 + 0.3 = 0.8 (باستخدام A2). الخادم خامل: يبدأ العميل 1 خدمته فورا، والتأخير 0، وعدد التأخيرات 1. حالة الخادم 1، وجدولة المغادرة: D = 0.5 + 1.2 = 1.7 (باستخدام S1).

الحدث 2، t = 0.8: وصول العميل 2. المساحتان أولا، بالحالة السابقة: Q: 0 + 0 × (0.8 - 0.5) = 0 وB: 0 + 1 × (0.8 - 0.5) = 0.3. جدولة الوصول التالي: A = 0.8 + 1.8 = 2.6 (باستخدام A3). الخادم مشغول: ينضم العميل 2 إلى الطابور، Q = 1، ويخزن الزمن 0.8 في الموقع 1.

الحدث 3، t = 1.7: مغادرة العميل 1. المساحتان أولا، بالحالة السابقة: Q: 0 + 1 × (1.7 - 0.8) = 0.9 وB: 0.3 + 1 × (1.7 - 0.8) = 1.2. يغادر العميل 2 الطابور: التأخير 1.7 - 0.8 = 0.9، ويقرأ قبل الإزاحة. إجمالي التأخير 0 + 0.9 = 0.9، وعدد التأخيرات 2. جدولة المغادرة: D = 1.7 + 0.6 = 2.3 (باستخدام S2). Q = 0، وتزاح المصفوفة موقعا واحدا إلى الأمام: فارغة.

الحدث 4، t = 2.3: مغادرة العميل 2. المساحتان أولا، بالحالة السابقة: Q: 0.9 + 0 × (2.3 - 1.7) = 0.9 وB: 1.2 + 1 × (2.3 - 1.7) = 1.8. الطابور فارغ: حالة الخادم 0 وD = ∞.

الحدث 5، t = 2.6: وصول العميل 3. المساحتان أولا، بالحالة السابقة: Q: 0.9 + 0 × (2.6 - 2.3) = 0.9 وB: 1.8 + 0 × (2.6 - 2.3) = 1.8. جدولة الوصول التالي: A = 2.6 + 0.4 = 3.0 (باستخدام A4). الخادم خامل: يبدأ العميل 3 خدمته فورا، والتأخير 0، وعدد التأخيرات 3. حالة الخادم 1، وجدولة المغادرة: D = 2.6 + 0.7 = 3.3 (باستخدام S3).

الحدث 6، t = 3.0: وصول العميل 4. المساحتان أولا، بالحالة السابقة: Q: 0.9 + 0 × (3.0 - 2.6) = 0.9 وB: 1.8 + 1 × (3.0 - 2.6) = 2.2. جدولة الوصول التالي: A = 3.0 + 0.6 = 3.6 (باستخدام A5). الخادم مشغول: ينضم العميل 4 إلى الطابور، Q = 1، ويخزن الزمن 3.0 في الموقع 1.

الحدث 7، t = 3.3: مغادرة العميل 3. المساحتان أولا، بالحالة السابقة: Q: 0.9 + 1 × (3.3 - 3.0) = 1.2 وB: 2.2 + 1 × (3.3 - 3.0) = 2.5. يغادر العميل 4 الطابور: التأخير 3.3 - 3.0 = 0.3، ويقرأ قبل الإزاحة. إجمالي التأخير 0.9 + 0.3 = 1.2، وعدد التأخيرات 4. جدولة المغادرة: D = 3.3 + 1.1 = 4.4 (باستخدام S4). Q = 0، وتزاح المصفوفة موقعا واحدا إلى الأمام: فارغة. يبلغ عدد التأخيرات 4، وهي n: تحققت قاعدة التوقف، ويعمل مولد التقارير.

$$\begin{aligned} T(4) &= 3.3 \\[6pt] d(4) &= \dfrac{1.2}{4} = 0.30 \\[6pt] q(4) &= \dfrac{1.2}{3.3} = 0.36 \\[6pt] u(4) &= \dfrac{2.5}{3.3} = 0.76 \quad (75.8\%) \end{aligned}$$

التشغيل 2

الحدث 1، t = 1.0: وصول العميل 1. المساحتان أولا، بالحالة السابقة: Q: 0 + 0 × (1.0 - 0) = 0 وB: 0 + 0 × (1.0 - 0) = 0. جدولة الوصول التالي: A = 1.0 + 0.5 = 1.5 (باستخدام A2). الخادم خامل: يبدأ العميل 1 خدمته فورا، والتأخير 0، وعدد التأخيرات 1. حالة الخادم 1، وجدولة المغادرة: D = 1.0 + 1.4 = 2.4 (باستخدام S1).

الحدث 2، t = 1.5: وصول العميل 2. المساحتان أولا، بالحالة السابقة: Q: 0 + 0 × (1.5 - 1.0) = 0 وB: 0 + 1 × (1.5 - 1.0) = 0.5. جدولة الوصول التالي: A = 1.5 + 0.6 = 2.1 (باستخدام A3). الخادم مشغول: ينضم العميل 2 إلى الطابور، Q = 1، ويخزن الزمن 1.5 في الموقع 1.

الحدث 3، t = 2.1: وصول العميل 3. المساحتان أولا، بالحالة السابقة: Q: 0 + 1 × (2.1 - 1.5) = 0.6 وB: 0.5 + 1 × (2.1 - 1.5) = 1.1. جدولة الوصول التالي: A = 2.1 + 2.5 = 4.6 (باستخدام A4). الخادم مشغول: ينضم العميل 3 إلى الطابور، Q = 2، ويخزن الزمن 2.1 في الموقع 2.

الحدث 4، t = 2.4: مغادرة العميل 1. المساحتان أولا، بالحالة السابقة: Q: 0.6 + 2 × (2.4 - 2.1) = 1.2 وB: 1.1 + 1 × (2.4 - 2.1) = 1.4. يغادر العميل 2 الطابور: التأخير 2.4 - 1.5 = 0.9، ويقرأ قبل الإزاحة. إجمالي التأخير 0 + 0.9 = 0.9، وعدد التأخيرات 2. جدولة المغادرة: D = 2.4 + 0.8 = 3.2 (باستخدام S2). Q = 1، وتزاح المصفوفة موقعا واحدا إلى الأمام: 2.1.

الحدث 5، t = 3.2: مغادرة العميل 2. المساحتان أولا، بالحالة السابقة: Q: 1.2 + 1 × (3.2 - 2.4) = 2.0 وB: 1.4 + 1 × (3.2 - 2.4) = 2.2. يغادر العميل 3 الطابور: التأخير 3.2 - 2.1 = 1.1، ويقرأ قبل الإزاحة. إجمالي التأخير 0.9 + 1.1 = 2.0، وعدد التأخيرات 3. جدولة المغادرة: D = 3.2 + 0.5 = 3.7 (باستخدام S3). Q = 0، وتزاح المصفوفة موقعا واحدا إلى الأمام: فارغة.

الحدث 6، t = 3.7: مغادرة العميل 3. المساحتان أولا، بالحالة السابقة: Q: 2.0 + 0 × (3.7 - 3.2) = 2.0 وB: 2.2 + 1 × (3.7 - 3.2) = 2.7. الطابور فارغ: حالة الخادم 0 وD = ∞.

الحدث 7، t = 4.6: وصول العميل 4. المساحتان أولا، بالحالة السابقة: Q: 2.0 + 0 × (4.6 - 3.7) = 2.0 وB: 2.7 + 0 × (4.6 - 3.7) = 2.7. جدولة الوصول التالي: A = 4.6 + 0.3 = 4.9 (باستخدام A5). الخادم خامل: يبدأ العميل 4 خدمته فورا، والتأخير 0، وعدد التأخيرات 4. حالة الخادم 1، وجدولة المغادرة: D = 4.6 + 1.2 = 5.8 (باستخدام S4).

الحدث 8، t = 4.9: وصول العميل 5. المساحتان أولا، بالحالة السابقة: Q: 2.0 + 0 × (4.9 - 4.6) = 2.0 وB: 2.7 + 1 × (4.9 - 4.6) = 3.0. جدولة الوصول التالي: A = 4.9 + 0.4 = 5.3 (باستخدام A6). الخادم مشغول: ينضم العميل 5 إلى الطابور، Q = 1، ويخزن الزمن 4.9 في الموقع 1.

الحدث 9، t = 5.3: وصول العميل 6. المساحتان أولا، بالحالة السابقة: Q: 2.0 + 1 × (5.3 - 4.9) = 2.4 وB: 3.0 + 1 × (5.3 - 4.9) = 3.4. جدولة الوصول التالي: A = 5.3 + 1.1 = 6.4 (باستخدام A7). الخادم مشغول: ينضم العميل 6 إلى الطابور، Q = 2، ويخزن الزمن 5.3 في الموقع 2.

الحدث 10، t = 5.8: مغادرة العميل 4. المساحتان أولا، بالحالة السابقة: Q: 2.4 + 2 × (5.8 - 5.3) = 3.4 وB: 3.4 + 1 × (5.8 - 5.3) = 3.9. يغادر العميل 5 الطابور: التأخير 5.8 - 4.9 = 0.9، ويقرأ قبل الإزاحة. إجمالي التأخير 2.0 + 0.9 = 2.9، وعدد التأخيرات 5. جدولة المغادرة: D = 5.8 + 1.3 = 7.1 (باستخدام S5). Q = 1، وتزاح المصفوفة موقعا واحدا إلى الأمام: 5.3. يبلغ عدد التأخيرات 5، وهي n: تحققت قاعدة التوقف، ويعمل مولد التقارير.

$$\begin{aligned} T(5) &= 5.8 \\[6pt] d(5) &= \dfrac{2.9}{5} = 0.58 \\[6pt] q(5) &= \dfrac{3.4}{5.8} = 0.59 \\[6pt] u(5) &= \dfrac{3.9}{5.8} = 0.67 \quad (67.2\%) \end{aligned}$$