נוסחת קינגמן

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

נוסחת קינגמן, בתורת התורים, היא נוסחה המספקת קירוב למודל תורים מסוג G/G/1. מודל תורים מסוג זה מציין, לפי סימון קנדל, מודל כללי בעל שרת יחיד ותור אינסופי. G/G/1 מתאר מערכת בעלת מופע לקוחות שלו התפלגות כללית כלשהי, תהליך שירות עם התפלגות כללית כלשהי, שרת יחיד ותור אינסופי, הפועל על פי מודל FCFS, נכנס ראשון יוצא ראשון. הנוסחה מאפשרת מציאת קירוב לתוחלת זמן ההמתנה בתור. כלומר, מציאת משך זמן ההמתנה הממוצע של לקוח, מרגע כניסתו לתור ועד לתחילת קבלת השירות. הנוסחה הוצגה לראשונה בשנת 1966 על ידי ג'ון קינגמן, במאמרו "On the Algebra of Queues", והיא נחשבת לקירוב טוב עבור מערכת העובדת בנצילות גבוהה.[1]

הנוסחה[עריכת קוד מקור | עריכה]

הנוסחה שהציג קינגמן הייתה זו:

\mathbb{E}(W_q) \approx \left( \frac{\rho}{1-\rho} \right) \left( \frac{c_a^2+c_s^2}{2}\right) \tau

כאשר:

  • \tau הוא זמן השירות הממוצע (\mu=1/\tau הוא קצב השירות הממוצע).
  • \lambda הוא קצב המופע של לקוחות חדשים במערכת.
  • \rho=\lambda \tau = \lambda/\mu הוא נצילות השרת במערכת.
  • ca הוא קבוע השונות של תהליך מופע הלקוחות (כלומר סטיית התקן של משך הזמן בין מופע למופע חלקי משך הזמן הממוצע בין מופע למופע)
  • cs הוא קבוע השונות למשך השירות (כלומר סטיית התקן ל משך השירות חלקי משך השירות הממוצע)

הנוסחה היא מכפלתם של שלושה איברים התלויים בנצילות השרת, בשונות הזמנים במערכת ובמשך השירות בהתאמה. הנוסחה מבטאת הנחות אינטואיטיביות לגבי משך ההמתנה, שמשכו ארוך יותר ככל שנצילות השרת עולה, ככל שהשונות במשך הזמן בין המופעים או בזמן השירות עולה וככל שמשך השירות הממוצע עולה (בהתאמה לאיברים השונים במכפלה).

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Harrison, Peter G.; Patel, Naresh M., Performance Modelling of Communication Networks and Computer Architectures, pp. 336, תבנית:Citation/identifier