سه پایه تئوری صف. ساده ترین سیستم های نوبت دهی، نمونه هایی از کاربرد در حل مشکلات اقتصادی

اغلب، هنگام تجزیه و تحلیل سیستم های اقتصادی، باید به اصطلاح مشکلات را حل کرد در صف، در شرایط زیر ایجاد می شود. اجازه دهید سیستم تجزیه و تحلیل شود نگهداریاتومبیل‌ها، متشکل از تعدادی ایستگاه با قدرت متفاوت. در هر ایستگاه (عنصر سیستم)، حداقل دو وضعیت معمول ممکن است ایجاد شود:

1. تعداد درخواست ها برای یک ایستگاه معین بسیار زیاد است، صف ها به وجود می آیند و شما باید برای تاخیر در خدمات هزینه کنید.
2. ایستگاه درخواست های بسیار کمی دریافت می کند و اکنون باید خسارات ناشی از خرابی ایستگاه را در نظر بگیریم.

واضح است که هدف تحلیل سیستم V در این موردتعیین نسبت معینی بین ضررهای درآمدی ناشی از صف هاو زیان های ناشی از فقط منایستگاه ها

تئوری صف- بخش ویژه ای از نظریه سیستم ها بخشی از نظریه احتمال است که در آن سیستم های صف با استفاده از مدل های ریاضی مطالعه می شوند.

سیستم نوبت دهی (QS)مدلی است که شامل: 1) یک جریان تصادفی از نیازمندی ها، تماس ها یا مشتریانی است که به خدمات نیاز دارند. 2) الگوریتم برای انجام این سرویس. 3) کانال ها (دستگاه ها) برای سرویس.

نمونه‌هایی از ارائه‌دهندگان خدمات عبارتند از صندوق‌های نقدی، پمپ بنزین‌ها، فرودگاه‌ها، فروشندگان، آرایشگاه‌ها، پزشکان، صرافی‌های تلفن و سایر امکاناتی که در آنها درخواست‌های خاصی ارائه می‌شود.

مشکل تئوری صفشامل ایجاد توصیه هایی برای ساخت منطقی سیستم های QS و سازماندهی منطقی کار آنها به منظور اطمینان از بازدهی بالاخدمات با هزینه های بهینه

ویژگی اصلی وظایف از این کلاس- وابستگی واضح نتایج تجزیه و تحلیل و توصیه های دریافت شده به دو عوامل خارجی: فراوانی دریافت و پیچیدگی سفارشات (و در نتیجه زمان اجرای آنها).

موضوع تئوری صف، ایجاد رابطه بین ماهیت جریان درخواست ها، عملکرد یک کانال خدمات فردی، تعداد کانال ها و کارایی خدمات است.

مانند ویژگی های سیستمدر نظر گرفته شده اند:

• میانگین درصد درخواست هایی که رد می شوند و سیستم را بدون ارائه رها می کنند.
• متوسط ​​زمان از کار افتادن کانال‌ها و سیستم به‌عنوان یک کل؛
• میانگین زمان انتظار در صف؛
• احتمال اینکه برنامه دریافت شده بلافاصله سرویس شود.
• قانون توزیع طول صف و دیگران

اجازه دهید اضافه کنیم که برنامه‌ها (نیازمندی‌ها) به طور تصادفی (در زمان‌های تصادفی)، با نقاط متراکم و کمیاب به QS می‌رسند. زمان سرویس برای هر درخواست نیز تصادفی است و پس از آن کانال سرویس آزاد شده و آماده انجام درخواست بعدی است. هر QS بسته به تعداد کانال ها و عملکرد آنها ظرفیت مشخصی دارد. پهنای باند SMOشاید مطلق(میانگین تعداد برنامه های ارائه شده در واحد زمان) و نسبت فامیلی(نسبت متوسط ​​تعداد درخواست های ارائه شده به تعداد درخواست های ارسال شده).

3.1 مدل های سیستم های صف.

هر QS را می توان با عبارت زیر مشخص کرد: (الف/ب/ج): (د/ه/ج) ، جایی که

آ - توزیع جریان ورودی برنامه ها؛

ب - توزیع جریان خروجی برنامه ها؛

ج - پیکربندی مکانیزم خدمات؛

د - نظم و انضباط صف؛

ه - بلوک انتظار؛

f - ظرفیت منبع

حالا بیایید نگاهی دقیق تر به هر یک از ویژگی ها بیندازیم.

جریان ورودی برنامه ها- تعداد برنامه های دریافت شده به سیستم. با شدت جریان ورودی مشخص می شود ل.

جریان خروجی برنامه ها- تعداد برنامه های ارائه شده توسط سیستم. با شدت جریان خروجی مشخص می شود متر.

پیکربندی سیستمدلالت دارد تعداد کلکانال ها و گره های سرویس QS ممکن است شامل موارد زیر باشد:

1. یک کانالخدمات (یک باند، یک فروشنده)؛
2. یک کانال خدماتی از جمله چندین گره متوالی(کانتین، درمانگاه، نوار نقاله)؛
3. چندین کانال از یک نوعخدمات متصل به صورت موازی (پمپ های بنزین، میز کمک، ایستگاه قطار).

بنابراین، تشخیص QS تک کاناله و چند کاناله امکان پذیر است.

از سوی دیگر، اگر همه کانال‌های خدمات در QS مشغول باشند، برنامه مورد نظر ممکن است در صف باقی بماند یا سیستم را ترک کند (به عنوان مثال، یک بانک پس‌انداز و یک مرکز تلفن). در این مورد، ما در مورد سیستم های دارای صف (انتظار) و سیستم های دارای خرابی صحبت می کنیم.

صف– این مجموعه درخواست هایی است که برای سرویس وارد سیستم شده و در انتظار سرویس هستند. صف با طول صف و نظم آن مشخص می شود.

نظم و انضباط صف- این قانون برای سرویس دهی به درخواست ها از صف است. انواع اصلی صف شامل موارد زیر است:

1. PERPPO (اول که اول خدمت می شود) رایج ترین نوع است.
2. POSPPO (آخرین در، اولین خدمت)؛
3. ROP (انتخاب تصادفی برنامه ها) - از بانک داده.
4. روابط عمومی – خدمات اولویت دار

طول صفشاید

• نامحدود - سپس آنها در مورد یک سیستم با انتظار خالص صحبت می کنند.
• برابر با صفر - سپس آنها در مورد یک سیستم با شکست صحبت می کنند.
• طول محدود (سیستم نوع مختلط).

بلوک انتظار- "ظرفیت" سیستم - تعداد کل برنامه های موجود در سیستم (در صف و در سرویس). بدین ترتیب، e=c+د.

ظرفیت منبعایجاد درخواست های خدمات حداکثر تعداد درخواست هایی است که می تواند توسط QS دریافت شود. به عنوان مثال، در یک فرودگاه ظرفیت منبع با تعداد تمام هواپیماهای موجود محدود می شود و ظرفیت منبع یک مرکز تلفن برابر با تعداد ساکنان زمین است، یعنی. می توان آن را نامحدود در نظر گرفت.

تعداد مدل های QS با تعداد ترکیب های ممکن از این اجزا مطابقت دارد.

3.2 جریان الزامات ورودی.

با هر دوره زمانی [ آ, آ+ تی ]، متغیر تصادفی را متصل کنید ایکس، برابر با تعداد درخواست های دریافتی سیستم در طول زمان است تی.

جریان نیازمندی ها نامیده می شود ثابت، اگر قانون توزیع به نقطه اولیه بازه بستگی نداشته باشد آ، اما فقط به طول بازه داده شده بستگی دارد تی. به عنوان مثال، یک جریان درخواست به یک مرکز تلفن در طول روز ( تی=24 ساعت) را نمی توان ثابت در نظر گرفت، اما از 13 تا 14 ساعت ( تی= 60 دقیقه) - شما می توانید.

جریان نامیده می شود بدون عواقب، اگر تاریخچه جریان بر رسیدن تقاضاها در آینده تأثیری نداشته باشد، i.e. الزامات مستقل از یکدیگر هستند.

جریان نامیده می شود معمولی، در صورتی که در مدت زمان بسیار کوتاهی بیش از یک درخواست نمی تواند وارد سیستم شود. به عنوان مثال، جریان به آرایشگاه عادی است، اما به اداره ثبت - نه. اما، اگر به عنوان متغیر تصادفی ایکسبرای در نظر گرفتن جفت برنامه های دریافت شده توسط دفتر ثبت، چنین جریانی عادی خواهد بود (یعنی گاهی اوقات یک جریان فوق العاده را می توان به یک جریان عادی کاهش داد).

جریان نامیده می شود ساده ترین، در صورت ثابت بودن، بدون افترافکت و معمولی.

قضیه اصلیاگر جریان ساده ترین باشد، پس r.v. X[a. یک + تی] طبق قانون پواسون توزیع می شود، یعنی. .

نتیجه 1. ساده ترین جریان نیز جریان پواسون نامیده می شود.

نتیجه 2. م(ایکس)= م(ایکس [ آ , آ + تی ] )= لتی، یعنی در حین تی لتیبرنامه های کاربردی. بنابراین در هر واحد زمان، سیستم به طور متوسط ​​دریافت می کند لبرنامه های کاربردی. این مقدار نامیده می شود شدتجریان ورودی.

بیایید یک مثال را در نظر بگیریم .

این استودیو به طور متوسط ​​روزانه 3 برنامه دریافت می کند. با در نظر گرفتن ساده ترین جریان، این احتمال را پیدا کنید که طی دو روز آینده تعداد برنامه ها حداقل 5 باشد.

راه حل.

با توجه به شرایط مشکل، ل=3, تی= 2 روز، جریان ورودی پواسون است، n ³5. هنگام تصمیم گیری، معرفی رویداد مخالف راحت است که شامل این واقعیت است که در طول زمان تیکمتر از 5 درخواست دریافت خواهد شد. بنابراین با توجه به فرمول پواسون بدست می آوریم

^

3.3 وضعیت سیستم ماتریس و گراف انتقال.

در یک لحظه تصادفی از زمان، QS از یک حالت به حالت دیگر تغییر می کند: تعداد کانال های اشغال شده، تعداد درخواست ها و صف ها و غیره تغییر می کند. بنابراین، QS با nکانال ها و طول صف برابر است متر، ممکن است در یکی از حالت های زیر باشد:

E 0 - همه کانال ها رایگان هستند

E 1 - یک کانال مشغول است.

E n- همه کانال ها مشغول هستند.

E n +1 - همه کانال ها مشغول هستند و یک درخواست در صف است.

E n + متر- تمام کانال ها و تمام مکان های صف اشغال شده است.

یک سیستم مشابه با خرابی ممکن است در ایالات وجود داشته باشد E 0 – E n .

برای یک QS با انتظار خالص، تعداد بی نهایت حالت وجود دارد. بدین ترتیب، حالت E n QS در یک نقطه از زمان تی - این مقدار است n برنامه های کاربردی (نیازمندی) واقع در سیستم در یک زمان معین، به عنوان مثال. n= n(تی) - مقدار تصادفی، E n (تی) نتایج این متغیر تصادفی هستند و پ n (تی) - احتمال اینکه سیستم در حالت است E n .

ما قبلاً با وضعیت سیستم آشنا هستیم. توجه داشته باشید که همه حالت های سیستم معادل نیستند. وضعیت سیستم نامیده می شود منبع، اگر سیستم بتواند از این حالت خارج شود، اما نتواند به آن بازگردد. وضعیت سیستم نامیده می شود جدا شده،اگر سیستم نتواند از این حالت خارج شود یا وارد شود.

برای تجسم حالات سیستم از نمودارها (به اصطلاح نمودارهای انتقال) استفاده می شود که در آن فلش ها انتقال احتمالی سیستم از یک حالت به حالت دیگر و همچنین احتمالات چنین انتقالی را نشان می دهند.

شکل 3.1 - نمودار انتقال

Comp.	E 0	E 1	E 2
E 0	P 0.0	P 0.1	P 0.2
E 1	P 1.0	P 1.1	R 1.2
E 2	P 2.0	R 2.2	R 2.2

همچنین گاهی اوقات استفاده از ماتریس انتقال راحت است. در این حالت، ستون اول حالت های اولیه سیستم (جاری) را نشان می دهد و سپس احتمالات انتقال از این حالت ها به حالت های دیگر آورده شده است.

از آنجایی که سیستم قطعا از یک حرکت خواهد کرد

حالت به دیگری، سپس مجموع احتمالات در هر ردیف همیشه برابر با یک است.

3.4 QS تک کاناله.

3.4.1 QS تک کاناله با خرابی.

ما سیستم هایی را در نظر خواهیم گرفت که شرایط زیر را برآورده کنند:

(P/E/1):(–/1/¥) . اجازه دهید همچنین فرض کنیم که زمان مورد نیاز برای سرویس یک درخواست به تعداد درخواست های وارد شده به سیستم بستگی ندارد. در اینجا و پایین، "P" به این معنی است که جریان ورودی طبق قانون پواسون توزیع شده است، یعنی. ساده ترین، "E" به این معنی است که جریان خروجی بر اساس یک قانون نمایی توزیع می شود. همچنین در اینجا و زیر، فرمول های اصلی بدون اثبات آورده شده است.

برای چنین سیستمی دو حالت ممکن است: E 0 – سیستم رایگان است و E 1 - سیستم مشغول است. بیایید یک ماتریس انتقال ایجاد کنیم. بگیریم دیتی- یک دوره زمانی بی نهایت کوچک بگذارید رویداد A در سیستم در زمان باشد دیتییک درخواست دریافت شد رویداد B در طول زمان است دیتییک درخواست انجام شده است رویداد آ من , ک- در حین دیتیسیستم از حالت انتقال خواهد یافت E مندر یک ایالت E ک. زیرا لشدت جریان ورودی و سپس در طول زمان است دیتیبه طور متوسط ​​وارد سیستم می شود l*Dتیالزامات. یعنی احتمال دریافت یک درخواست P(A)=ل* دیتی، و احتمال رویداد مخالف Р(Ā)=1-l*Dتی.P(B)=اف(دیتی)= پ(ب< دی تی)=1- ه - متر دی تی = متر دیتی- احتمال سرویس دهی به درخواست در زمان دیتی. سپس A 00 - برنامه دریافت نمی شود یا دریافت می شود اما سرویس می شود. A 00 =Ā+A * V. P 00 = 1 - l*Dتی. (ما این را در نظر گرفتیم (دیتی) 2 - مقدار بی نهایت کوچک)

A 01 - برنامه دریافت می شود، اما سرویس نمی شود. A 01 = A * . R 01 = l*Dتی.

A 10 - برنامه سرویس می شود و برنامه جدیدی وجود نخواهد داشت. A 10 = B * آ. R 10 = m*Dتی.

الف 11 - برنامه سرویس داده نمی شود یا برنامه جدیدی دریافت می شود که هنوز سرویس نشده است. A 11 = +B * A.P 01 = 1- m*Dتی.

بنابراین، ماتریس انتقال را بدست می آوریم:

Comp.	E 0	E 1
E 0	1-l * Dt	ل * Dt
E 1	متر * Dt	1-متر * Dt

احتمال خرابی و خرابی سیستم.

اجازه دهید اکنون احتمال اینکه سیستم در حالت است را پیدا کنیم E 0 هروقت تی(آنها آر 0 ( تی) ). نمودار یک تابع
در شکل 3.2 نشان داده شده است.

مجانب نمودار خط مستقیم است
.

بدیهی است که از یک نقطه شروع می شود تی,

1

شکل 3.2

در نهایت ما آن را دریافت می کنیم
و
، جایی که آر 1 (تی) - احتمال اینکه در لحظه زمان تی سیستم مشغول است (یعنی در یک وضعیت است E 1 ).

بدیهی است که در آغاز عملیات QS، روند در حال انجام ثابت نخواهد بود: این یک حالت "انتقالی" و غیر ثابت خواهد بود. پس از مدتی (که به شدت جریان ورودی و خروجی بستگی دارد)، این فرآیند از بین می‌رود و سیستم به حالت ثابت و کارکرد ثابت می‌رود و ویژگی‌های احتمالی دیگر به زمان بستگی ندارند.

حالت کار ثابت و ضریب بار سیستم.

اگر احتمال اینکه سیستم در یک حالت باشد E ک، یعنی آر ک (تی), به زمان بستگی ندارد تی، بعد می گویند QS نصب شده است حالت ثابتکار کردن در این مورد، ارزش
تماس گرفت ضریب بار سیستم(یا کاهش تراکم جریان کاربردها). سپس برای احتمالات آر 0 (تی) و آر 1 (تی) ما فرمول های زیر را دریافت می کنیم:
,
. همچنین می توان نتیجه گرفت: هر چه ضریب بار سیستم بیشتر باشد، احتمال خرابی سیستم بیشتر است (یعنی احتمال اشغال سیستم)

کارواش دارای یک واحد سرویس می باشد. خودروها بر اساس توزیع پواسون با نرخ 5 خودرو در ساعت وارد می شوند. میانگین زمان سرویس برای یک دستگاه 10 دقیقه است. در صورتی که QS در حالت ساکن کار کند، احتمال این را بیابید که ماشینی که در حال نزدیک شدن است، سیستم را مشغول پیدا کند.

راه حل.با توجه به شرایط مشکل، ل=5, متر y =5/6. ما باید احتمال را پیدا کنیم آر 1 - احتمال خرابی سیستم
.

3.4.2 QS تک کاناله با طول صف نامحدود.

ما سیستم هایی را در نظر خواهیم گرفت که شرایط را برآورده کنند: (P/E/1): (d/¥/¥). سیستم می تواند در یکی از ایالت ها باشد E 0 , …, E ک، ... تجزیه و تحلیل نشان می دهد که اگر شدت جریان خروجی از شدت جریان ورودی بیشتر شود (یعنی ضریب بار سیستم کمتر از یک باشد) پس از مدتی چنین سیستمی در حالت ساکن شروع به کار می کند. با در نظر گرفتن این شرط، سیستم معادلات را به دست می آوریم

حل آن را خواهیم یافت که . بنابراین، به شرطی که y<1, получим
سرانجام،
و
- احتمال اینکه QS در حالت است E کدر یک لحظه تصادفی در زمان

میانگین عملکرد سیستم

به دلیل عدم دریافت یکنواخت مطالبات به سیستم و نوسانات زمان سرویس دهی، در سیستم صف تشکیل می شود. برای چنین سیستمی می توان بررسی کرد:

• n - تعداد الزامات در QS (در صف و در سرویس)؛
• v - طول صف؛
• w - زمان انتظار برای شروع خدمات؛
• w 0 - کل زمان صرف شده در سیستم

ما علاقه مند خواهیم شد ویژگی های متوسط(یعنی می گیریم ارزش مورد انتظاربر روی متغیرهای تصادفی مورد بررسی، و آن را به خاطر بسپارید y<1).

- میانگین تعداد برنامه های کاربردی در سیستم.

- متوسط ​​طول صف

- میانگین زمان انتظار برای شروع سرویس، یعنی زمان انتظار در صف

- میانگین زمانی که یک برنامه کاربردی در سیستم می گذراند - در صف و برای سرویس.

در کارواش یک بلوک برای سرویس و یک مکان برای صف وجود دارد. خودروها بر اساس توزیع پواسون با نرخ 5 خودرو در ساعت وارد می شوند. میانگین زمان سرویس برای یک دستگاه 10 دقیقه است. تمام مشخصات متوسط ​​QS را بیابید.

راه حل. ل=5, متر=60min/10min = 6. ضریب بار y =5/6. سپس میانگین تعداد خودروهای موجود در سیستم
، متوسط ​​طول صف
، میانگین زمان انتظار برای شروع سرویس
ساعت = 50 دقیقه و در نهایت میانگین زمان صرف شده در سیستم
ساعت

3.4.3 QS مختلط تک کاناله.

بیایید طول صف را فرض کنیم مترالزامات. سپس، برای هر کسی س£ متر، احتمال اینکه QS در حالت باشد E 1+ س، با فرمول محاسبه می شود
، یعنی یک برنامه در حال ارائه است و دیگری سبرنامه ها در صف هستند

احتمال خرابی سیستم است
,

و احتمال خرابی سیستم می باشد
.

سه سیستم تک کانال برای هر کدام داده شده است ل=5, متر =6. اما سیستم اول با امتناع، دوم با انتظار خالص و سوم با طول صف محدود است. متر=2. احتمال خرابی این سه سیستم را بیابید و مقایسه کنید.

راه حل.برای همه سیستم ها ضریب بار y=5/6. برای یک سیستم با شکست
. برای یک سیستم انتظار خالص
. برای سیستمی با طول صف محدود
. نتیجه واضح است: هرچه تعداد برنامه های کاربردی بیشتر در صف باشد، احتمال خرابی سیستم کمتر می شود.

3.5 QS چند کاناله.

3.5.1 QS چند کاناله با خرابی.

ما سیستم ها (P/E/s):(-/s/¥) را با این فرض در نظر می گیریم که زمان سرویس به جریان ورودی بستگی ندارد و همه خطوط به طور مستقل عمل می کنند. سیستم های چند کاناله، علاوه بر ضریب بار، می توانند با ضریب نیز مشخص شوند
، جایی که س- تعداد کانال های خدمات با مطالعه QS چند کاناله، فرمول های زیر (فرمول های ارلنگ) را برای احتمال وضعیت سیستم به دست می آوریم. E کدر یک زمان تصادفی:

، k=0، 1، …

تابع هزینه.

همانند سیستم های تک کانال، افزایش ضریب بار، احتمال خرابی سیستم را افزایش می دهد. از سوی دیگر، افزایش تعداد خطوط خدمات منجر به افزایش احتمال خرابی سیستم یا کانال های فردی می شود. بنابراین، یافتن تعداد بهینه کانال های سرویس برای یک QS معین ضروری است. میانگین تعداد خطوط خدمات رایگان را می توان با استفاده از فرمول پیدا کرد
. بیایید C( س) – تابع هزینه QS بسته به با 1 - هزینه یک امتناع (جریمه برای درخواست انجام نشده) و از با 2 - هزینه خرابی یک خط در واحد زمان.

برای یافتن گزینه بهینه، باید حداقل مقدار تابع هزینه را پیدا کنید (و می توان این کار را انجام داد): با(س) = s 1* ل * پ س +s 2*که نمودار آن در شکل 3.3 ارائه شده است:

شکل 3.3

یافتن حداقل مقدار تابع هزینه شامل یافتن مقادیر آن در ابتدا برای س =1، سپس برای س = 2، سپس برای س =3 و غیره تا زمانی که در مرحله ای مقدار تابع C( س) بزرگتر از قبلی نخواهد شد. این بدان معنی است که تابع به حداقل خود رسیده و شروع به رشد کرده است. پاسخ تعداد کانال های سرویس (مقدار س) که تابع هزینه برای آن حداقل است.

مثال .

اگر یک QS دارای چند خط خدمات با خرابی باشد ل= 2 تقاضا در ساعت، متر= 1 تقاضا / ساعت، جریمه برای هر خرابی 7 هزار روبل است، هزینه خرابی یک خط 2 هزار روبل است. در 01:00؟

راه حل. y = 2/1=2. با 1 =7, با 2 =2.

اجازه دهید فرض کنیم که QS دارای دو کانال خدماتی است، به عنوان مثال. س =2. سپس
. از این رو، C(2) = c 1 *ل*پ 2 +s 2 *(2- y*(1-r 2 )) = =7*2*0.4+2*(2-2*0.6)=7.2.

بیایید وانمود کنیم که س =3. سپس
, C(3) = c 1 *ل*پ 3 +s 2 *
=5.79.

بیایید فرض کنیم چهار کانال وجود دارد، یعنی. س =4. سپس
,
, C(4) = c 1 *ل*پ 4 +s 2 *
=5.71.

بیایید فرض کنیم که QS دارای پنج کانال خدماتی است، یعنی. س =5. سپس
, C(5) = 6.7 - بیشتر از مقدار قبلی. بنابراین تعداد بهینه کانال های سرویس چهار می باشد.

3.5.2 QS چند کاناله با یک صف.

ما سیستم ها (P/E/s):(d/d+s/¥) را با این فرض در نظر می گیریم که زمان سرویس به جریان ورودی بستگی ندارد و همه خطوط به طور مستقل عمل می کنند. خواهیم گفت که سیستم نصب شده است حالت کار ثابت، اگر میانگین تعداد درخواست های دریافتی کمتر از میانگین تعداد درخواست های ارائه شده در تمام خطوط سیستم باشد، یعنی. ل

P(w>0) - احتمال انتظار برای شروع سرویس،
.

آخرین مشخصه به ما اجازه می دهد تا مشکل تعیین تعداد بهینه کانال های سرویس را حل کنیم تا احتمال انتظار برای شروع سرویس کمتر از یک عدد معین باشد. برای این کار کافی است احتمال انتظار را به صورت متوالی در محاسبه کنیم س =1, س =2, س=3 و غیره

مثال .

SMO یک ایستگاه آمبولانس در یک منطقه کوچک کوچک است. ل= 3 تماس در ساعت، و متر= 4 تماس در ساعت برای یک تیم. چه تعداد خدمه باید در ایستگاه داشته باشید تا احتمال انتظار برای حرکت کمتر از 0.01 باشد؟

راه حل.ضریب بار سیستم y = 0.75. بیایید فرض کنیم که دو تیم در دسترس هستند. اجازه دهید احتمال انتظار برای شروع سرویس را پیدا کنیم س =2.
,
.

بیایید فرض کنیم سه تیم وجود دارد، یعنی. س=3. با توجه به فرمول ها به آن می رسیم آر 0 =8/17، Р(w>0)=0.04>0.01 .

بیایید فرض کنیم که چهار تیم در ایستگاه هستند، یعنی. س=4. سپس ما آن را دریافت می کنیم آر 0 =416/881، Р(w>0)=0.0077<0.01 . بنابراین باید چهار تیم در ایستگاه حضور داشته باشند.

3.6 سؤالاتی برای خودکنترلی

1. موضوع و وظایف تئوری صف.
2. SMO، مدل‌ها و نام‌گذاری‌های آن‌ها.
3. جریان الزامات ورودی شدت جریان ورودی
4. وضعیت سیستم ماتریس و گراف انتقال.
5. QS تک کاناله با خرابی.
6. QS تک کاناله با صف. مشخصات.
7. حالت کار ثابت ضریب بار سیستم
8. QS چند کاناله با خرابی.
9. بهینه سازی تابع هزینه
10. QS چند کاناله با یک صف. مشخصات.

3.7 تمرین برای کار مستقل

1. اسنک بار پمپ بنزین یک پیشخوان دارد. خودروها طبق توزیع پواسون با میانگین 2 ماشین در هر 5 دقیقه وارد می شوند. به طور متوسط، 1.5 دقیقه برای تکمیل یک سفارش کافی است، اگرچه مدت زمان سرویس بر اساس قانون نمایی توزیع می شود. پیدا کنید: الف) احتمال توقف توقف. ب) مشخصات متوسط؛ ج) احتمال اینکه تعداد وسایل نقلیه ورودی حداقل 10 باشد.
2. دستگاه اشعه ایکس به طور متوسط ​​7 نفر در ساعت را معاینه می کند. شدت بازدید 5 نفر در ساعت است. با فرض عملکرد ثابت، مشخصه های متوسط ​​را تعیین کنید.
3. زمان سرویس در QS از قانون نمایی پیروی می کند،
   متر = 7 تقاضا در ساعت. این احتمال را پیدا کنید که الف) زمان سرویس در محدوده 3 تا 30 دقیقه باشد. ب) درخواست ظرف یک ساعت انجام می شود. از جدول مقادیر تابع استفاده کنید ه ایکس .
4. بندر رودخانه دارای یک اسکله است، شدت جریان ورودی 5 شناور در روز است. شدت عملیات تخلیه و بارگیری 6 شناور در روز می باشد. با در نظر گرفتن حالت ثابت عملکرد، تمام مشخصات متوسط ​​سیستم را تعیین کنید.
5. ل=3, متر=2، جریمه هر خرابی 5 است و هزینه خرابی یک خط 2؟
6. تعداد بهینه کانال های خدماتی که یک QS باید داشته باشد چقدر است ل=3, متر =1، جریمه هر خرابی 7 و هزینه خرابی یک خط 3 است؟
7. تعداد بهینه کانال های خدماتی که یک QS باید داشته باشد چقدر است ل=4, متر=2، جریمه هر خرابی 5 و هزینه خرابی یک خط 1 است؟
8. با در نظر گرفتن این شرط که احتمال انتظار باید کمتر از 0.05 باشد، تعداد باندهای فرودگاه را برای هواپیما تعیین کنید. در عین حال شدت جریان ورودی 27 فروند هواپیما در روز و شدت سرویس دهی آنها 30 هواپیما در روز است.
9. یک کارگاه باید چند خط نقاله مستقل معادل داشته باشد تا از ریتم کاری اطمینان حاصل کند که در آن احتمال انتظار برای پردازش محصولات باید کمتر از 0.03 باشد (هر محصول توسط یک خط تولید می شود). مشخص شده است که شدت سفارشات دریافتی 30 محصول در ساعت و شدت پردازش محصول توسط یک خط 36 محصول در ساعت است.
10. متغیر تصادفی پیوسته X بر اساس یک قانون نمایی با پارامتر l=5 توزیع می شود. تابع توزیع، ویژگی ها و احتمال برخورد r.v را پیدا کنید. X در محدوده 0.17 تا 0.28.
11. میانگین تعداد تماس‌هایی که در یک دقیقه به سانترال می‌رسند 3 است. با فرض اینکه جریان پواسون است، این احتمال را پیدا کنید که در عرض 2 دقیقه موارد زیر می‌رسد: الف) دو تماس. ب) کمتر از دو تماس؛ ج) حداقل دو تماس.
12. در جعبه 17 قطعه وجود دارد که 4 قطعه آن معیوب است. اسمبلر 5 قسمت را به صورت تصادفی انتخاب می کند. احتمال اینکه الف) تمام قطعات استخراج شده از کیفیت بالایی برخوردار باشند را بیابید. ب) از بین قطعات استخراج شده 3 قطعه معیوب بود.
13. اگر یک QS با خرابی چند کانال باید داشته باشد ل= 2 تقاضا در ساعت، متر= 1 تقاضا در ساعت، جریمه برای هر خرابی 8 هزار روبل است، هزینه خرابی یک خط 2 هزار روبل است. در 01:00؟

طراحی 0 - 2 جریان رویدادها (الف) و ساده ترین جریان (ب)

10.5.2.1. ثابت بودن

جریان ثابت نامیده می شود , اگر احتمال وقوع تعداد معینی از رویدادها در یک بخش زمانی ابتدایی باشد طول τ (

شکل 0-2 , آ)فقط به طول مقطع بستگی دارد و به محل دقیق محور بستگی نداردتی این منطقه واقع شده است.

جریان ثابت به معنای یکنواختی آن در طول زمان است. ویژگی های احتمالی چنین جریانی بسته به زمان تغییر نمی کند. به طور خاص، به اصطلاح شدت (یا "چگالی") جریان رویدادها - تعداد متوسط ​​رویدادها در واحد زمان برای یک جریان ثابت - باید ثابت بماند. البته این بدان معنا نیست که تعداد واقعی رویدادهایی که در واحد زمان ظاهر می‌شوند ثابت است؛ جریان ممکن است تراکم‌ها و نادری‌های محلی داشته باشد. مهم است که برای یک جریان ثابت، این تراکم ها و نادری ها ماهیت منظمی نداشته باشند، و میانگین تعداد رویدادهایی که در یک دوره زمانی واحد قرار می گیرند برای کل دوره مورد بررسی ثابت می ماند.

در عمل، اغلب جریان‌هایی از رویدادها وجود دارد که (حداقل برای یک دوره زمانی محدود) می‌تواند ثابت در نظر گرفته شود. به عنوان مثال، جریانی از تماس‌هایی که به یک مرکز تلفن می‌رسند، مثلاً بین ۱۲ تا ۱۳ ساعت، ممکن است تلفن ثابت در نظر گرفته شود. جریان مشابه دیگر برای یک روز کامل ثابت نخواهد بود (در شب شدت جریان تماس بسیار کمتر از روز است). توجه داشته باشید که در مورد اکثر فرآیندهای فیزیکی که ما آنها را «ایستا» می‌نامیم، همین‌طور است؛ در واقع، آنها فقط در مدت زمان محدودی ساکن هستند و گسترش این ناحیه تا بی‌نهایت تنها یک تکنیک مناسب برای این منظور است. از ساده سازی

10.5.2.2. بدون عواقب

جریانی از رویدادها را جریانی بدون افترافکت می نامند , اگر برای دوره‌های زمانی غیرهمپوشانی، تعداد رویدادهایی که روی یکی از آنها اتفاق می‌افتد به تعداد رویدادهایی که روی دیگری می‌افتند (یا سایر رویدادها، اگر بیش از دو بخش در نظر گرفته شود) بستگی ندارد.

در این گونه جریان ها، رویدادهایی که جریان را تشکیل می دهند، در لحظات متوالی و مستقل از یکدیگر ظاهر می شوند. به عنوان مثال، جریان مسافرانی که وارد ایستگاه مترو می شوند را می توان جریانی بدون عواقب در نظر گرفت، زیرا دلایلی که ورود یک مسافر را در یک لحظه معین و نه در لحظه دیگر تعیین می کند، معمولاً به دلایل مشابه مربوط نمی شود. سایر مسافران اگر چنین وابستگی ظاهر شود، شرط عدم وجود عواقب نقض می شود.

برای مثال، جریان قطارهای باری در امتداد یک خط راه آهن را در نظر بگیرید. اگر به دلیل شرایط ایمنی، آنها نتوانند بیشتر از فواصل زمانی یکدیگر را دنبال کنند t 0 ، سپس بین اتفاقات در جریان وابستگی ایجاد می شود و شرط عدم تبعیت نقض می شود. با این حال، اگر فاصله t 0 در مقایسه با میانگین فاصله بین قطارها کوچک است، پس چنین تخلفی ناچیز است.

طراحی 0 - 3 توزیع پواسون

محور را در نظر بگیریدتی ساده ترین جریان رویدادها با شدت λ. (شکل 0-2 ب) . ما به فاصله زمانی تصادفی T بین رویدادهای همسایه در این جریان علاقه مند خواهیم بود. بیایید قانون توزیع آن را پیدا کنیم. ابتدا تابع توزیع را پیدا می کنیم:

F(t) = P(T ( 0-2)

یعنی احتمال اینکه مقدار T مقدار کمتر ازتی. اجازه دهید از ابتدای بازه T (نقاط t 0) قطعه t و احتمال اینکه بازه T را پیدا کنید کمتر وجود خواهد داشتتی . برای انجام این کار، لازم است که برای یک مقطع طولتی، در مجاورت یک نقطه t 0 , حداقل یک رویداد جریان ضربه خورد. بیایید احتمال این را محاسبه کنیم F(t) از طریق احتمال رویداد مخالف (در هر بخشتی به هیچ رویداد جریانی برخورد نخواهد کرد):

F (t) = 1 - P 0

احتمال P 0با فرض فرمول (1) در می یابیممتر = 0:

از آنجایی که تابع توزیع مقدار T خواهد بود:

(0-3)

برای یافتن چگالی توزیع f(t) متغیر تصادفی تی،لازم است عبارت (0-1) را با آن متمایز کنیمتی:

0-4)

قانون توزیع با چگالی (0-4) نمایی نامیده می شود (یا نمایی ). کمیت λ را پارامتر می نامند قانون اثباتی

شکل 0 - 4 توزیع نمایی

بیایید ویژگی های عددی یک متغیر تصادفی را پیدا کنیم تی- انتظارات ریاضی (مقدار متوسط) M [ t ] = m t , و واریانس Dt. ما داریم

( 0-5)

(ادغام با قطعات).

پراکندگی مقدار T برابر است با:

(0-6)

با گرفتن جذر واریانس، میانگین را پیدا می کنیم انحراف معیارمتغیر تصادفی تی.

بنابراین، برای یک توزیع نمایی، انتظار ریاضی و انحراف معیار برابر با یکدیگر و معکوس با پارامتر λ هستند، جایی که λ. شدت جریان

بنابراین، ظاهر متر رویدادهای یک دوره زمانی معین با توزیع پواسون مطابقت دارد و احتمال اینکه فواصل زمانی بین رویدادها کمتر از یک عدد از پیش تعیین شده معین باشد با توزیع نمایی مطابقت دارد. همه اینها فقط توصیف های متفاوتی از یک فرآیند تصادفی هستند.

مثال SMO-1 .

به عنوان مثال، یک سیستم بانکی را در نظر بگیرید که در زمان واقعی کار می کند و به تعداد زیادی از مشتریان خدمات ارائه می دهد. در ساعات اوج مصرف، درخواست‌های باجه‌های بانکی که با مشتریان کار می‌کنند، یک جریان پواسون را تشکیل می‌دهند و به طور متوسط ​​دو در هر ثانیه (λ = 2) می‌رسند. این جریان شامل درخواست‌هایی است که با شدت 2 درخواست در ثانیه می‌رسند.

بیایید احتمال P (م ) ظاهر م پیام ها در 1 ثانیه از آنجایی که λ = 2، پس از فرمول قبلی داریم

جایگزینی m = 0، 1، 2، 3، مقادیر زیر را دریافت می کنیم (با دقت چهارارقام اعشاری):

شکل 0 - 5 نمونه ای از یک جریان ساده

امکان دریافت بیش از 9 پیام در 1 ثانیه وجود دارد، اما احتمال این امر بسیار کم است (حدود 0.000046).

توزیع حاصل را می توان در قالب یک هیستوگرام (نشان داده شده در شکل) ارائه کرد.

مثال SMO-2.

دستگاهی (سرور) که در هر 1 ثانیه سه پیام را پردازش می کند.

اجازه دهید تجهیزاتی وجود داشته باشد که بتواند سه پیام را در 1 ثانیه پردازش کند (µ=3). به طور متوسط ​​در هر 1 ثانیه دو پیام دریافت می شود و مطابق باج توزیع پواسون چه نسبتی از این پیام ها بلافاصله پس از دریافت پردازش می شود؟

احتمال اینکه نرخ ورود کمتر یا مساوی 3 ثانیه باشد توسط داده می شود

اگر سیستمی بتواند حداکثر 3 پیام را در 1 ثانیه پردازش کند، احتمال اینکه بیش از حد بارگذاری نشود، وجود دارد.

به عبارت دیگر 85.71 درصد پیام ها بلافاصله و 14.29 درصد با کمی تاخیر ارائه می شود. همانطور که می بینید، تاخیر در پردازش یک پیام برای مدت زمانی بیشتر از زمان پردازش 3 پیام به ندرت رخ می دهد. زمان پردازش برای 1 پیام به طور متوسط ​​1/3 ثانیه است. بنابراین تاخیر بیش از 1 ثانیه یک اتفاق نادر خواهد بود که برای اکثر سیستم ها کاملا قابل قبول است.

مثال SMO- 3

· اگر عابر بانک 80 درصد از زمان کاری خود را مشغول کرده و بقیه زمان خود را در انتظار مشتریان بگذراند، می توان او را دستگاهی با ضریب بهره برداری 0.8 در نظر گرفت.

· اگر از یک کانال ارتباطی برای انتقال نمادهای 8 بیتی با سرعت 2400 bps استفاده شود، یعنی حداکثر 2400/8 نماد در 1 ثانیه ارسال می شود و ما در حال ساختن سیستمی هستیم که در آن کل داده ها 12000 نماد است. ارسال شده از دستگاه های مختلف از طریق کانال ارتباطی در دقیقه از سنگین ترین بار (شامل همگام سازی، نمادهای انتهای پیام، کنترل و غیره)، سپس میزان استفاده از تجهیزات کانال ارتباطی در این دقیقه برابر است با

· اگر یک موتور دسترسی به فایل 9000 دسترسی به فایل را در طول یک ساعت شلوغ انجام دهد و میانگین زمان هر دسترسی 300 میلی‌ثانیه باشد، آنگاه نرخ استفاده از سخت‌افزار ساعت پیک موتور دسترسی برابر است.

مفهوم استفاده از تجهیزات اغلب مورد استفاده قرار می گیرد. هر چه میزان استفاده از تجهیزات به 100% نزدیک‌تر باشد، تاخیر بیشتر و صف‌ها طولانی‌تر می‌شود.

با استفاده از فرمول قبلی، می توانید جدول هایی از مقادیر تابع پواسون ایجاد کنید که از روی آنها می توانید احتمال رسیدن را تعیین کنید.متر یا پیام های بیشتری در یک دوره زمانی معین. به عنوان مثال، اگر به طور متوسط ​​3.1 پیام در ثانیه وجود داشته باشد [i.e. e. λ = 3.1]، پس احتمال دریافت 5 پیام یا بیشتر در یک ثانیه معین 0.2018 است (برایمتر = 5 در جدول). یا به صورت تحلیلی

با استفاده از این عبارت، یک تحلیلگر سیستم می‌تواند احتمال عدم برآورده کردن یک معیار بار معین را محاسبه کند.

اغلب می توان محاسبات اولیه را برای مقادیر بار تجهیزات انجام داد

ρ ≤ 0.9

این مقادیر را می توان با استفاده از جداول پواسون بدست آورد.

دوباره میانگین نرخ رسیدن پیام λ = 3.1 پیام/ثانیه را بگذارید. از جداول چنین بر می آید که احتمال دریافت 6 پیام یا بیشتر در 1 ثانیه 0.0943 است. بنابراین می توان این عدد را به عنوان معیار بار برای محاسبات اولیه در نظر گرفت.

10.6.2. وظایف طراحی

اگر پیام ها به طور تصادفی به دستگاه برسد، دستگاه بخشی از زمان خود را صرف پردازش یا سرویس هر پیام می کند و در نتیجه صف هایی تشکیل می شود. یک صف در بانک در انتظار آزادی صندوقدار و رایانه او (ترمینال) است. یک صف پیام در بافر ورودی کامپیوتر در انتظار پردازش توسط پردازنده است. صفی از درخواست‌ها برای آرایه‌های داده منتظر می‌ماند تا کانال‌ها آزاد شوند و غیره. صف‌ها می‌توانند در تمام گلوگاه‌های سیستم تشکیل شوند.

هر چه میزان استفاده از تجهیزات بیشتر باشد، صف های حاصل طولانی تر می شود. همانطور که در زیر نشان داده خواهد شد، می توان یک سیستم عامل رضایت بخش با ضریب استفاده 0.7 = ρ طراحی کرد، اما ضریب بیش از ρ > 0.9 ممکن است منجر به بدتر شدن کیفیت خدمات شود. به عبارت دیگر، اگر یک لینک داده انبوه دارای 20 درصد بار باشد، بعید است که یک صف روی آن وجود داشته باشد. در صورت بارگیری؛ 0.9 است، سپس، به عنوان یک قاعده، صف هایی تشکیل می شود، گاهی اوقات بسیار بزرگ.

ضریب استفاده از تجهیزات برابر است با نسبت بار روی تجهیزات به حداکثر باری که این تجهیزات می تواند تحمل کند یا برابر با نسبت زمان اشغال تجهیزات به کل زمان کارکرد آن است.

هنگام طراحی یک سیستم، تخمین ضریب استفاده برای انواع مختلف تجهیزات معمول است. نمونه های مربوطه در فصل های بعدی آورده خواهد شد. دانستن این ضرایب به شما امکان می دهد تا صف های مربوط به تجهیزات مربوطه را محاسبه کنید.

· طول صف چقدر است؟

· چقدر زمان میبرد؟

این نوع سوالات را می توان با استفاده از تئوری صف پاسخ داد.

10.6.3. سیستم های صف، کلاس ها و ویژگی های اصلی آنها

برای یک QS، جریان‌های رویداد، جریان‌هایی از برنامه‌ها، جریان‌های برنامه‌های کاربردی «سرویس‌سازی» و غیره هستند. اگر این جریان‌ها پواسون نباشند (فرایند مارکوف)، توصیف ریاضی فرآیندهایی که در QS رخ می‌دهند به‌طور غیرقابل مقایسه پیچیده‌تر می‌شود و نیاز به سخت‌تر شدن دارد. دستگاه، آوردن آن به فرمول های تحلیلی تنها در ساده ترین موارد امکان پذیر است.

با این حال، دستگاه تئوری صف "مارکوین" نیز می تواند در مواردی مفید باشد که فرآیندی که در QS اتفاق می افتد با مدل مارکویی متفاوت است؛ با کمک آن می توان ویژگی های عملکرد QS را تقریباً ارزیابی کرد. لازم به ذکر است که هر چه QS پیچیده تر باشد، کانال های سرویس بیشتری داشته باشد، فرمول های تقریبی به دست آمده با استفاده از نظریه مارکوف دقیق تر است. علاوه بر این، در تعدادی از موارد، به منظور تصمیم گیری آگاهانه در مورد مدیریت عملیات QS، دانش دقیق از تمام ویژگی های آن مورد نیاز نیست، اغلب فقط دانش تقریبی و تقریبی کافی است.

QS به سیستم هایی با موارد زیر طبقه بندی می شوند:

· شکست ها (با ضرر و زیان). در چنین سیستم‌هایی، درخواستی که در زمانی که همه کانال‌ها مشغول هستند دریافت می‌شود، "رد کردن" دریافت می‌کند، QS را ترک می‌کند و در فرآیند خدمات بعدی شرکت نمی‌کند.

· در انتظار (با یک صف). در چنین سیستم‌هایی، درخواستی که در زمانی که همه کانال‌ها مشغول هستند می‌رسد در صف قرار می‌گیرد و منتظر می‌ماند تا یکی از کانال‌ها آزاد شود. هنگامی که کانال آزاد می شود، یکی از درخواست های در صف برای سرویس پذیرفته می شود.

خدمات (انضباط صف) در یک سیستم انتظار می تواند باشد

· سفارش داده شده (برنامه ها به ترتیب دریافت پردازش می شوند)

· بی نظم(برنامه ها به ترتیب تصادفی ارائه می شوند) یا

· انباشته (آخرین درخواست ابتدا از صف انتخاب می شود).

· اولویت

o با اولویت ایستا

o با اولویت پویا

(در مورد دوم، قبل tet ممکن است، برای مثال، با مدت زمان انتظار برای یک برنامه افزایش یابد).

سیستم های صف به سیستم ها تقسیم می شوند

· با انتظار نامحدود و

· با محدود در انتظار.

در سیستم‌هایی با انتظار نامحدود، هر درخواستی که در زمانی که کانال رایگان وجود ندارد وارد یک صف می‌شود و «صبورانه» منتظر می‌ماند تا کانال در دسترس قرار گیرد و آن را برای سرویس بپذیرد. هر درخواستی که توسط CMO دریافت شود دیر یا زود سرویس خواهد شد.

در سیستم هایی با انتظار محدود، محدودیت های خاصی برای ماندن یک برنامه در صف اعمال می شود. این محدودیت ها ممکن است اعمال شوند

· طول صف (تعداد برنامه های کاربردی به طور همزمان در صف در یک سیستم با طول صف محدود)،

· مدت زمانی که برنامه در صف سپری شده است (پس از یک دوره معینی از ماندن در صف، برنامه از صف خارج می شود و سیستم با زمان انتظار محدود خارج می شود)

· کل زمان اقامت برنامه در CMO

و غیره.

بسته به نوع QS، هنگام ارزیابی اثربخشی آن، ممکن است از مقادیر خاصی (شاخص های عملکرد) استفاده شود. به عنوان مثال، برای یک QS با خرابی، یکی از مهمترین ویژگی های بهره وری آن به اصطلاح است توان عملیاتی مطلقمیانگین تعداد درخواست هایی که سیستم می تواند در واحد زمان ارائه دهد.

همراه با مطلق، اغلب در نظر گرفته می شود توان نسبی QS میانگین سهم برنامه های ورودی ارائه شده توسط سیستم است (نسبت میانگین تعداد برنامه های سرویس شده توسط سیستم در واحد زمان به میانگین تعداد برنامه های دریافت شده در این مدت).

علاوه بر توان عملیاتی مطلق و نسبی، هنگام تجزیه و تحلیل یک QS با شکست، بسته به وظیفه تحقیق، ممکن است به ویژگی های دیگری نیز علاقه مند باشیم، به عنوان مثال:

· میانگین تعداد کانال های شلوغ؛

· متوسط ​​زمان خاموشی نسبی سیستم به عنوان یک کل و یک کانال مجزا

و غیره.

سوالات با انتظار دارای ویژگی های کمی متفاوت است. بدیهی است که برای یک QS با انتظار نامحدود، هر دو توان عملیاتی مطلق و نسبی معنای خود را از دست می دهند، زیرا هر درخواست دریافتی زودهنگام است.یا بعدا سرو میشه برای چنین QS، ویژگی های مهم عبارتند از:

· میانگین تعداد برنامه های کاربردی در صف.

· میانگین تعداد برنامه های کاربردی در سیستم (در صف و تحت سرویس)؛

· میانگین زمان انتظار برای یک برنامه در صف.

· میانگین زمان ماندن یک برنامه کاربردی در سیستم (در صف و تحت سرویس)؛

و همچنین سایر ویژگی های انتظار.

برای یک QS با انتظار محدود، هر دو گروه از ویژگی ها مورد توجه هستند: هم توان عملیاتی مطلق و هم نسبی، و ویژگی های انتظار.

برای تجزیه و تحلیل فرآیندی که در QS رخ می دهد، دانستن پارامترهای اصلی سیستم ضروری است: تعداد کانال ها. پ،شدت جریان برنامه هاλ , عملکرد هر کانال (متوسط ​​تعداد درخواست های ارائه شده توسط کانال در واحد زمان)، شرایط تشکیل یک صف (محدودیت، در صورت وجود).

بسته به مقادیر این پارامترها، ویژگی های عملکرد QS بیان می شود.

10.6.4. فرمول های محاسبه ویژگی های QS برای مورد سرویس دهی با یک دستگاه

شکل 0 - 6 مدل سیستم نوبت دهی با صف

چنین صف هایی را می توان با پیام هایی در ورودی پردازنده در انتظار پردازش ایجاد کرد. آنها می توانند در حین عملکرد نقاط مشترک متصل به یک کانال ارتباطی چند نقطه ای رخ دهند. به همین ترتیب، صف خودروها در پمپ بنزین ها تشکیل می شود. با این حال، اگر بیش از یک ورودی سرویس وجود داشته باشد، ما یک صف با دستگاه های زیادی داریم و تجزیه و تحلیل پیچیده تر می شود.

اجازه دهید مورد ساده ترین جریان درخواست خدمات را در نظر بگیریم.

هدف از تئوری صف ارائه شده، تقریب اندازه متوسط ​​صف، و همچنین میانگین زمان صرف شده توسط پیام های منتظر در صف است. همچنین توصیه می شود تخمین بزنید که هر چند وقت یکبار صف از یک طول معین بیشتر می شود. این اطلاعات به ما این امکان را می دهد که مثلاً مقدار حافظه بافر مورد نیاز برای ذخیره صف های پیام و برنامه های مربوطه، تعداد خطوط ارتباطی مورد نیاز، اندازه بافر مورد نیاز برای هاب ها و غیره را محاسبه کنیم. تخمین زمان پاسخ ممکن خواهد بود.

هر یک از ویژگی ها بسته به وسیله مورد استفاده متفاوت است.

یک صف با یک سرور در نظر بگیرید. هنگام طراحی یک سیستم محاسباتی، اکثر صف های این نوع با استفاده از فرمول های داده شده محاسبه می شوند.ضریب تغییرات زمان سرویس

فرمول Khinchin-Polacek برای محاسبه طول صف هنگام طراحی سیستم های اطلاعاتی استفاده می شود. در مورد توزیع نمایی زمان رسیدن برای هر توزیع زمان سرویس و هر رشته کنترلی استفاده می شود، تا زمانی که انتخاب پیام بعدی برای سرویس به زمان سرویس بستگی نداشته باشد.

هنگام طراحی سیستم ها، موقعیت هایی وجود دارد که در آن صف ها بوجود می آیند که نظم مدیریت بدون شک به زمان خدمات بستگی دارد. به عنوان مثال، در برخی موارد ممکن است پیام های کوتاه تری را برای خدمات اولویت دار انتخاب کنیم تا به میانگین زمان سرویس کمتری دست یابیم. هنگام کنترل یک خط ارتباطی، می‌توانید اولویت بیشتری را به پیام‌های ورودی نسبت به پیام‌های خروجی اختصاص دهید، زیرا پیام‌های اولی کوتاه‌تر هستند. در چنین مواقعی دیگر نیازی به استفاده از معادله خینچین نیست

بیشتر زمان های سرویس در سیستم های اطلاعاتی جایی بین این دو حالت قرار دارد. زمان نگهداری برابر با مقدار ثابت نادر است. حتی زمان دسترسی به هارد دیسک به دلیل موقعیت های مختلف آرایه های داده روی سطح ثابت نیست. یکی از مثال‌هایی که زمان سرویس ثابت را نشان می‌دهد، اشغال یک خط ارتباطی برای ارسال پیام‌هایی با طول ثابت است.

از سوی دیگر، گسترش زمان سرویس به اندازه توزیع دلخواه یا نمایی آن نیست، یعنی.σs به ندرت به مقادیر می رسدts. این مورد گاهی اوقات به عنوان "بدترین حالت" در نظر گرفته می شود و بنابراین آنها از فرمول های مربوط به توزیع نمایی زمان های خدمات استفاده می کنند. چنین محاسبه ای ممکن است اندازه های کمی متورم صف ها و زمان انتظار در آنها را نشان دهد، اما این خطا حداقل خطرناک نیست.

البته، توزیع تصاعدی زمان‌های خدمات، بدترین حالتی نیست که می‌توان با آن مواجه شد. با این حال، اگر زمان‌های سرویس به‌دست‌آمده از محاسبات صف بدتر از زمان‌های توزیع شده به صورت نمایی توزیع شوند، این اغلب یک علامت هشدار برای طراح است. اگر انحراف معیار بیشتر از میانگین باشد، معمولاً نیاز به تنظیم محاسبات وجود دارد.

مثال زیر را در نظر بگیرید. شش نوع پیام با زمان سرویس 15، 20، 25، 30، 35 و 300 وجود دارد که تعداد پیام ها در هر نوع یکسان است. انحراف معیار زمان های نشان داده شده کمی بیشتر از میانگین آنهاست. آخرین ارزش زمان سرویس بسیار بالاتر از سایرین است. این باعث می‌شود که پیام‌ها به میزان قابل توجهی طولانی‌تر از زمانی که زمان‌های سرویس یکسان باشد، در صف بنشینند. در این مورد، هنگام طراحی، توصیه می شود اقداماتی برای کاهش طول صف انجام شود. به عنوان مثال، اگر این اعداد مربوط به طول پیام باشد، ممکن است ارزش آن را داشته باشد که پیام های بسیار طولانی را به بخش هایی تقسیم کنیم.

10.6.6. مثال محاسبه

هنگام طراحی سیستم بانکی، دانستن تعداد مشتریانی که در ساعات اوج مصرف باید در صف یک عابر بانک بمانند، مطلوب است.

زمان پاسخگویی سیستم و انحراف استاندارد آن با در نظر گرفتن زمان ورود داده ها از ایستگاه کاری، چاپ و اجرای سند محاسبه می شود.

اقدامات صندوقدار به موقع بود. زمان سرویس ts برابر است با کل زمان صرف شده توسط صندوقدار برای مشتری. نرخ استفاده صندوقدار ρ متناسب با زمانی است که او مشغول است. اگر λ تعداد مشتریان در ساعات اوج مصرف باشد، ρ برای صندوقدار برابر است با

فرض کنید در ساعات اوج مصرف 30 مشتری در ساعت وجود دارد. به طور متوسط، یک صندوقدار برای هر مشتری 1.5 دقیقه هزینه می کند. سپس

ρ = (1.5 * 30) / 60 = 0.75

یعنی صندوقدار 75 درصد استفاده می شود.

تعداد افراد در صف را می توان به سرعت با استفاده از نمودارها تخمین زد. از آنها چنین استنباط می شود که اگر ρ = 0.75 باشد، میانگین تعداد nq افراد استدر خط پرداخت بسته به انحراف استاندارد بین 1.88 و 3.0 قرار دارد ts .

فرض کنید اندازه گیری انحراف استاندارد برای tس مقدار 0.5 دقیقه را ارائه کرد. سپس

σ s = 0.33 تن بر ثانیه

از نمودار شکل اول در می یابیم که nq = 2.0، یعنی به طور متوسط ​​دو مشتری در صندوق در انتظار خواهند بود.

کل زمانی که یک مشتری در صندوق پول صرف می کند را می توان به صورت پیدا کرد

t ∑ = t q + t s = 2.5 دقیقه + 1.5 دقیقه = 4 دقیقه

جایی که t s با استفاده از فرمول Khinchin-Polacek محاسبه می شود.

10.6.7. عامل سود

با تجزیه و تحلیل منحنی‌های نشان‌داده‌شده در شکل‌ها، می‌بینیم که وقتی تجهیزاتی که در صف خدمت می‌کنند بیش از 80 درصد استفاده می‌شود، منحنی‌ها با سرعت هشدار دهنده‌ای شروع به رشد می‌کنند. این واقعیت هنگام طراحی سیستم های انتقال داده بسیار مهم است. اگر در حال طراحی سیستمی با استفاده از سخت افزار بیش از 80 درصد هستیم، افزایش جزئی در ترافیک می تواند باعث افت عملکرد سیستم یا حتی از کار افتادن آن شود.

افزایش ترافیک ورودی به مقدار کمی x%. منجر به افزایش تقریباً اندازه صف می شود

اگر میزان استفاده از تجهیزات 50٪ باشد، این افزایش برابر با 4ts٪ برای توزیع نمایی زمان سرویس است. اما اگر میزان استفاده از سخت افزار 90٪ باشد، افزایش اندازه صف 100ts٪ است که 25 برابر بزرگتر است. افزایش جزئی بار در 90% استفاده از تجهیزات منجر به افزایش 25 برابری در اندازه صف در مقایسه با 50% استفاده از تجهیزات می شود.

به طور مشابه، زمان صرف شده در صف افزایش می یابد

با زمان سرویس توزیع شده نمایی، این مقدار دارای مقدار 4 تن است s 2 برای ضریب استفاده از تجهیزات معادل 50 درصد و 100 تن s 2 برای ضریب 90٪، یعنی دوباره 25 برابر بدتر.

علاوه بر این، برای نرخ های کم استفاده از تجهیزات، تأثیر تغییرات σs بر اندازه صف ناچیز است. با این حال، برای ضرایب بزرگ تغییر در σس تا حد زیادی بر اندازه صف تأثیر می گذارد. بنابراین هنگام طراحی سیستم هایی با استفاده از تجهیزات بالا، کسب اطلاعات دقیق در مورد پارامتر مطلوب استσ س. عدم دقت فرض در مورد نمایی توزیع tسدر مقادیر بزرگ ρ بیشتر قابل توجه است. علاوه بر این، اگر زمان سرویس به طور ناگهانی افزایش یابد، که در کانال های ارتباطی هنگام ارسال پیام های طولانی امکان پذیر است، در مورد ρ بزرگ یک صف قابل توجه تشکیل می شود.

یک شیء ریاضی (انتزاعی) که عناصر آن عبارتند از (شکل 2.1):

• جریان ورودی (ورودی) برنامه های کاربردی (نیازمندی) برای خدمات؛
• دستگاه های خدماتی (کانال)؛
• صف برنامه های کاربردی در انتظار خدمات؛
• جریان خروجی (خروجی) برنامه های کاربردی سرویس شده؛
• جریان درخواست برای خدمات اضافی پس از قطع سرویس؛
• جریان درخواست های پردازش نشده

کاربرد(درخواست، نیاز، تماس، مشتری، پیام، بسته) - یک شی که وارد QS می شود و نیاز به سرویس در دستگاه دارد. مجموعه ای از درخواست های متوالی که در طول زمان توزیع می شوند جریان ورودی برنامه ها

برنج. 2.1.

دستگاه سرویس(دستگاه، دستگاه، کانال، خط، ابزار، ماشین، روتر، و غیره) - یک عنصر QS که هدف آن خدمات رسانی به درخواست ها است.

سرویس- تاخیر برنامه در دستگاه سرویس دهی برای مدتی.

مدت زمان خدمت- زمان تاخیر (سرویس) درخواست در دستگاه.

دستگاه ذخیره سازی(بافر، بافر ورودی، بافر خروجی) - مجموعه ای از مکان ها برای انتظار درخواست ها در مقابل دستگاه ارائه دهنده. تعداد مکان های انتظار - گنجایش انبار.

درخواست دریافت شده توسط CMO می تواند در دو حالت باشد:

• 1) سرویس(در دستگاه)؛
• 2) انتظارات(در فضای ذخیره سازی) اگر همه دستگاه ها مشغول سرویس دهی به درخواست های دیگر هستند.

درخواست‌های موجود در فرم ذخیره‌سازی و انتظار خدمات صفبرنامه های کاربردی. تعداد برنامه های کاربردی در مخزن ذخیره سازی در انتظار خدمات - طول صف

نظم بافر(انضباط صف) - قانون ورود درخواست های دریافتی به یک دستگاه ذخیره سازی (بافر).

نظم و انضباط خدماتی- قانون انتخاب برنامه ها از صف برای سرویس در دستگاه.

یک اولویت- حق تقدم (تصرف منابع) برای ورود به فضای ذخیره سازی یا انتخاب از یک صف برای سرویس دهی در برنامه های دستگاه یک کلاس در رابطه با برنامه های سایر کلاس ها.

بسیاری از سیستم های صف وجود دارند که در سازماندهی ساختاری و عملکردی متفاوت هستند. در عین حال، توسعه روش‌های تحلیلی برای محاسبه شاخص‌های عملکرد یک سیستم QS در بسیاری از موارد وجود تعدادی محدودیت و فرضیات را پیش‌فرض می‌گیرد که مجموعه سیستم‌های QS مورد مطالعه را محدود می‌کند. از همین رو هیچ مدل تحلیلی کلی برای یک QS دلخواه با ساختار پیچیده وجود ندارد.

مدل تحلیلی QS مجموعه‌ای از معادلات یا فرمول‌هایی است که امکان تعیین احتمالات حالت‌های سیستم در طول عملیات و شاخص‌های عملکرد آن را بر اساس پارامترهای شناخته شده جریان ورودی و کانال‌های سرویس، بافر و رشته‌های خدماتی ممکن می‌سازد.

مدل‌سازی تحلیلی یک QS بسیار تسهیل می‌شود اگر فرآیندهایی که در QS رخ می‌دهند مارکوین باشند (جریان درخواست‌ها ساده هستند، زمان‌های خدمات به صورت تصاعدی توزیع می‌شوند). در این حالت، تمام فرآیندها در QS را می توان با معادلات دیفرانسیل معمولی و در حالت محدود - برای حالت های ثابت - با معادلات جبری خطی توصیف کرد و با حل آنها با استفاده از هر روش موجود در بسته های نرم افزاری ریاضی، شاخص های کارایی انتخابی را تعیین کرد. .

در سیستم های IM، هنگام اجرای QS، محدودیت ها و مفروضات زیر پذیرفته می شود:

• برنامه دریافت شده در سیستم فورادر صورت عدم وجود درخواست در صف و رایگان بودن دستگاه، سرویس می شود.
• دستگاه فقط در هر زمان معین قابل سرویس است. یکیکاربرد؛
• پس از پایان سرویس هر درخواستی در دستگاه، درخواست بعدی از صف خدمات به صورت آنی انتخاب می شود، یعنی دستگاه بیکار نمی مانداگر حداقل یک برنامه در صف وجود داشته باشد.
• دریافت برنامه های کاربردی در QS و مدت زمان سرویس دهی آنها به تعداد برنامه های موجود در سیستم یا عوامل دیگر بستگی ندارد.
• مدت زمان سرویس دهی به برنامه های کاربردی به شدت برنامه های وارد شده به سیستم بستگی ندارد.

بیایید به برخی از عناصر QS با جزئیات بیشتری نگاه کنیم.

جریان ورودی (ورودی) برنامه ها. جریان وقایعدنباله ای از رویدادهای همگن است که یکی پس از دیگری دنبال می شود و به طور کلی در برخی اتفاق می افتد، تصادفیلحظات در زمان. اگر رویداد ظاهر برنامه ها باشد، داریم جریان برنامه های کاربردیبرای توصیف جریان برنامه های کاربردی در مورد کلیلازم است فواصل زمانی t = را تنظیم کنید tk - t k-1بین لحظات مجاور tk_kو tkدریافت برنامه های کاربردی با شماره سریال به - 1 و بهبه ترتیب (به - 1, 2, ...; t 0 - 0 - زمان اولیه).

مشخصه اصلی جریان برنامه آن است شدت X- میانگین تعداد برنامه های دریافت شده در ورودی QS در واحد زمان. مقدار t = 1/Xتعریف می کند میانگین فاصله زمانی بین دو برنامه متوالی

جریان نامیده می شود قطعیدر صورت فواصل زمانی تی بهبین برنامه های همسایه مقادیر مشخصی از قبل شناخته شده را می گیرند. اگر فواصل یکسان باشد (x k= t برای همه k = 1، 2، ...)، سپس جریان نامیده می شود منظم.برای توصیف کامل جریان منظم درخواست ها، کافی است شدت جریان را تنظیم کنید ایکسیا مقدار فاصله t = 1/X.

جریانی که در آن فواصل زمانی وجود دارد x kبین برنامه های همسایه متغیرهای تصادفی نامیده می شوند تصادفی.برای توصیف کامل جریان تصادفی درخواست ها در حالت کلی، لازم است قوانین توزیع F fc (x fc) برای هر یک از بازه های زمانی مشخص شود. x k، k = 1،2، ....

یک جریان تصادفی که در آن تمام فواصل زمانی وجود دارد x b x 2،... بین درخواست های متوالی مجاور، متغیرهای تصادفی مستقلی هستند که توسط توابع توزیع FjCij، F 2 توصیف شده اند. (x 2)، ... بر این اساس، جریان با نامیده می شود عواقب محدود

جریان تصادفی نامیده می شود مکرر،اگر تمام فواصل زمانی x ب t 2, ... بین سفارشات توزیع می شود طبق همین قانون F(t). موضوعات تکراری زیادی وجود دارد. هر قانون توزیع جریان مکرر خود را ایجاد می کند. جریان های مکرر را در غیر این صورت جریان پالم می نامند.

اگر شدت ایکسو قانون توزیع F(t) فواصل بین برنامه های متوالی در طول زمان تغییر نمی کند، سپس جریان برنامه ها نامیده می شود. ثابتدر غیر این صورت، جریان درخواست است غیر ثابت

اگر در هر لحظه از زمان tkفقط یک ادعا می تواند در ورودی QS ظاهر شود، سپس جریان ادعاها فراخوانی می شود معمولیاگر بیش از یک برنامه بتواند در هر نقطه از زمان ظاهر شود، پس جریان برنامه ها وجود دارد خارق العاده،یا گروه

جریان درخواست ها را جریان می گویند بدون عواقبدر صورت دریافت درخواست ها بدون در نظر گرفتناز یکدیگر، یعنی لحظه دریافت برنامه بعدی به زمان و تعداد درخواست قبل از آن لحظه بستگی ندارد.

جریان معمولی ثابت و بدون افترافکت نامیده می شود ساده ترین.

فواصل زمانی t بین درخواست ها در ساده ترین جریان توزیع می شود نمایی (نشان دهنده) قانون:با تابع توزیع F(t) = 1 - e~ m;چگالی توزیع/(f) = هه ~"لجایی که X> 0 - پارامتر توزیع - شدت جریان برنامه ها.

ساده ترین جریان اغلب نامیده می شود پواسونیاننام از این واقعیت ناشی می شود که برای این جریان، احتمال وقوع P fc (At) دقیقاً است. بهبرنامه های کاربردی برای یک بازه زمانی معین At تعیین می شود قانون پواسون:

لازم به ذکر است که یک جریان پواسون، برخلاف ساده ترین، می تواند:

• ثابت،اگر شدت ایکسبا گذشت زمان تغییر نمی کند؛
• غیر ثابت،اگر شدت جریان به زمان بستگی دارد: ایکس= >.(t).

در عین حال، ساده ترین جریان، طبق تعریف، همیشه ثابت است.

مطالعات تحلیلی مدل‌های صف اغلب با فرض یک جریان ساده از درخواست‌ها انجام می‌شود که به دلیل تعدادی از ویژگی‌های قابل توجه ذاتی آن است.

1. جمع (ادغام) نهرها. ساده‌ترین جریان در نظریه QS مشابه قانون توزیع نرمال در نظریه احتمال است: ساده‌ترین جریان با عبور از حد برای جریانی حاصل می‌شود که مجموع جریان‌هایی با ویژگی‌های دلخواه با افزایش بی‌نهایت تعداد عبارت‌ها و یک عدد است. کاهش شدت آنها

مجموع نجریان های معمولی ثابت مستقل با شدت X x 2 ,..., X Nساده ترین جریان را با شدت تشکیل می دهد

X=Y،^iمشروط بر اینکه جریان های اضافه شده بیش از یا داشته باشند

تاثیر کمتر به همان اندازه کوچک بر جریان کل. در عمل، جریان کل نزدیک به ساده ترین زمانی است N> 5. بنابراین، هنگام جمع ساده ترین جریان های مستقل، جریان کل ساده ترین خواهد بودبه هر ارزشی ن.

• 2. نادر شدن جریان احتمالی. احتمالی(ولی قطعی نیست) خلاء ساده ترین جریانبرنامه هایی که در آنها هر برنامه ای با احتمال کمی تصادفی است آراز جریان مستثنی شده است، صرف نظر از اینکه درخواست های دیگر حذف شده باشند یا نه، منجر به شکل گیری می شود ساده ترین جریانبا شدت ایکس* = рХجایی که ایکس- شدت جریان اصلی جریان برنامه های حذف شده با شدت X** = (1 - p) X- یکسان ساده ترینجریان.
• 3. کارایی. اگر کانال های سرویس دهی (دستگاه ها) برای ساده ترین جریان درخواست ها با شدت طراحی شده باشند. ایکس،سپس سرویس انواع دیگر جریان ها (با همان شدت) با راندمان کمتری ارائه می شود.
• 4. سادگی. فرض ساده‌ترین جریان درخواست‌ها به بسیاری از مدل‌های ریاضی اجازه می‌دهد تا وابستگی شاخص‌های QS به پارامترها را به شکل صریح به دست آورند. بزرگترین عددنتایج تحلیلی برای ساده ترین جریان درخواست ها به دست آمد.

تجزیه و تحلیل مدل‌هایی با جریان‌های ترتیبی غیر از ساده‌ترین‌ها، معمولاً محاسبات ریاضی را پیچیده می‌کند و همیشه اجازه نمی‌دهد که یک راه‌حل تحلیلی به شکل صریح به دست آید. "ساده ترین" جریان نام خود را دقیقاً به دلیل این ویژگی دریافت کرد.

برنامه ها ممکن است واجد شرایط متفاوتی برای شروع خدمات باشند. در این مورد می گویند که اپلیکیشن ها ناهمگون.مزایای برخی از برنامه های کاربردی نسبت به سایرین در شروع سرویس بر اساس اولویت ها تعیین می شود.

یک ویژگی مهم جریان ورودی است ضریب تغییرات

که در آن t int انتظار ریاضی طول بازه است. O- انحراف استاندارد طول بازه x int (متغیر تصادفی).

برای ساده ترین جریان (a = -، m = -) v = 1 داریم. برای بیشتر

استریم های واقعی 0

کانال های خدماتی (دستگاه ها). مشخصه اصلی یک کانال مدت زمان سرویس است.

مدت زمان خدمت- زمانی که درخواست در دستگاه است - در حالت کلی، یک مقدار تصادفی. در صورت بار ناهمگن QS، مدت زمان درخواست خدمات کلاس های مختلفممکن است در قوانین توزیع یا فقط در مقادیر متوسط ​​متفاوت باشد. در این حالت معمولاً فرض می شود که مدت زمان سرویس دهی درخواست های هر کلاس مستقل است.

پزشکان اغلب تصور می‌کنند که مدت زمان سرویس‌دهی برنامه‌های کاربردی بیش از حد توزیع شده است قانون نماییکه محاسبات تحلیلی را به طور قابل توجهی ساده می کند. این به دلیل این واقعیت است که فرآیندهای رخ داده در سیستم هایی با توزیع نمایی از فواصل زمانی هستند مارکویانفرآیندها:

جایی که ج - شدت خدمات،اینجا p = _--; t 0 bsl - ریاضیات -

زمان انتظار برای سرویس

علاوه بر توزیع نمایی، توزیع Erlang/c، ابرنمایی، مثلثی و برخی دیگر وجود دارد. این نباید ما را گیج کند، زیرا نشان داده شده است که ارزش معیارهای کارایی QS کمی به نوع قانون توزیع زمان خدمات بستگی دارد.

هنگام مطالعه QS، ماهیت خدمات و کیفیت خدمات مورد توجه قرار نمی گیرد.

کانال ها می توانند باشند کاملا قابل اعتماد،آن ها شکست نخور یا بهتر بگوییم می توان این را در حین تحقیق پذیرفت. کانال ها ممکن است داشته باشند قابلیت اطمینان نهاییدر این مورد، مدل QS بسیار پیچیده تر است.

اثربخشی QS نه تنها به پارامترهای جریان ورودی و کانال‌های سرویس بستگی دارد، بلکه به ترتیبی که در آن درخواست‌های دریافتی سرویس می‌شوند، یعنی. در مورد روش های مدیریت جریان درخواست ها هنگام ورود به سیستم و ارسال خدمات.

روش‌های مدیریت جریان برنامه‌ها توسط رشته‌های زیر تعیین می‌شوند:

• بافر کردن
• سرویس.

رشته های بافر و نگهداری را می توان بر اساس معیارهای زیر طبقه بندی کرد:

• وجود اولویت بین برنامه های کاربردی کلاس های مختلف؛
• روشی برای جابجایی درخواست‌ها از صف (برای بافر کردن رشته‌ها) و تخصیص درخواست‌ها برای سرویس (برای رشته‌های خدماتی).
• قانون حذف یا انتخاب درخواست های خدمات؛
• توانایی تغییر اولویت ها

گونه ای از طبقه بندی رشته های بافر (صف) مطابق با ویژگی های ذکر شده در شکل 1 ارائه شده است. 2.2.

بسته به دسترسییا عدم اولویتبین درخواست های کلاس های مختلف، همه رشته های بافر را می توان به دو گروه بدون اولویت و اولویت تقسیم کرد.

توسط روش جابجایی درخواست ها از فضای ذخیره سازیکلاس های زیر از رشته های بافر را می توان تشخیص داد:

• بدون اخراج درخواست ها - درخواست هایی که وارد سیستم شده اند و درایو را کاملاً پر شده اند از بین می روند.
• با جابجایی برنامه ای از این کلاس، یعنی. همان کلاس برنامه دریافت شده؛
• با جابجایی برنامه از پایین ترین کلاس اولویت؛
• با جابجایی برنامه از گروه کلاس های با اولویت پایین.

برنج. 2.2.

از رشته های بافر زیر می توان استفاده کرد: قوانین اخراج درخواست ها از انبار:

• جابجایی تصادفی؛
• جابجایی آخرین درخواست، یعنی. دیرتر از بقیه وارد سیستم شد.
• ازدحام یک سفارش "طولانی"، یعنی. در فضای ذخیره سازی طولانی تر از همه برنامه های دریافت شده قبلی قرار دارد.

در شکل 2.3 طبقه‌بندی رشته‌های خدمات کاربردی را مطابق با همان معیارهایی که برای رشته‌های بافر ارائه می‌کند، ارائه می‌کند.

گاهی اوقات ظرفیت ذخیره سازی در مدل ها نامحدود فرض می شود، اگرچه در یک سیستم واقعی محدود است. این فرض زمانی توجیه می شود که احتمال از دست دادن درخواست در یک سیستم واقعی به دلیل پر بودن ظرفیت ذخیره سازی کمتر از 10_3 باشد. در این مورد، نظم و انضباط عملاً هیچ تأثیری بر عملکرد سرویس برنامه ندارد.

بسته به دسترسییا عدم اولویتبین درخواست های کلاس های مختلف، همه رشته های خدماتی و همچنین رشته های بافر را می توان به دو گروه بدون اولویت و اولویت تقسیم کرد.

توسط روش تخصیص درخواست های خدماترشته های تعمیر و نگهداری را می توان به رشته های زیر تقسیم کرد:

• حالت تک؛
• حالت گروهی؛
• حالت ترکیبی

برنج. 2.3.

در رشته های خدماتی حالت تک نفرههر بار برای خدمت فقط یکی اختصاص داده شده استبرنامه ای که صف های مربوط به آن پس از اتمام سرویس برنامه قبلی مشاهده می شود.

در رشته های خدماتی حالت گروهیهر بار برای خدمت گروهی از برنامه ها اختصاص داده شده استیک صف، که برای آن مشاهده صف ها تنها پس از سرویس دهی به تمام درخواست های یک گروه از قبل اختصاص داده شده انجام می شود. گروه درخواست هایی که به تازگی اختصاص داده شده اند ممکن است شامل تمام درخواست های صف داده شده باشد. درخواست های گروهی که به سرویس اختصاص داده شده است به ترتیب از صف انتخاب می شوندو توسط دستگاه سرویس می شوند و پس از آن گروه بعدی درخواست های یک صف دیگر مطابق با رشته خدماتی مشخص شده به سرویس اختصاص می یابد.

حالت ترکیبی- ترکیبی از حالت های تک و گروهی، زمانی که بخشی از صف های درخواست در حالت تک پردازش می شوند و بخشی دیگر در حالت گروهی.

رشته های خدماتی می توانند استفاده کنند قوانین زیرانتخاب درخواست خدمات

بدون اولویت(برنامه ها امتیازی برای سرویس دهی اولیه ندارند - جذب منابع):

• اولین خدمت، اولین خدمت FIFO (اول در -اولین بیرون،اولین ورودی اولین خروجی)؛
• سرویس معکوس- برنامه از صف در حالت انتخاب شده است LIFO (آخرین در - اولین بیرونآخرین یک در - اولین خروج)؛
• سرویس تصادفی- برنامه از صف در حالت انتخاب شده است رند (تصادفی- به طور تصادفی)؛
• سرویس چرخه ای- برنامه ها در فرآیند نظرسنجی چرخه ای درایوها به ترتیب 1، 2 انتخاب می شوند، نبا ن- تعداد درایوها)، پس از آن توالی مشخص شده تکرار می شود.

اولویت(برنامه ها دارای امتیازاتی برای سرویس دهی زودهنگام - جذب منابع):

• با اولویت های نسبی- اگر در حال انجام است نگهداری روتینبرنامه ها توسط برنامه هایی با اولویت بالاتر وارد سیستم می شوند، سپس سرویس برنامه فعلی حتی بدون اولویت قطع نمی شود و برنامه های ورودی به صف ارسال می شوند. اولویت های نسبی تنها در لحظه تکمیل سرویس فعلی یک برنامه در هنگام انتخاب یک برنامه جدید برای سرویس از صف نقش دارند.
• با اولویت های مطلق- با دریافت یک برنامه با اولویت بالا، سرویس یک برنامه با اولویت پایین قطع می شود و برنامه ورودی برای سرویس دهی ارسال می شود. یک برنامه قطع شده را می توان به صف بازگرداند یا از سیستم حذف کرد. اگر برنامه به صف بازگردانده شود، می توان خدمات بعدی آن را از محل قطع شده یا دوباره انجام داد.
• با اولویت های مختلط- محدودیت های شدید در زمان انتظار در صف خدمات رسانی به درخواست های فردی مستلزم اختصاص اولویت های مطلق به آنها است. در نتیجه، زمان انتظار برای برنامه‌های با اولویت پایین ممکن است به‌طور غیرقابل قبولی طولانی باشد، اگرچه برنامه‌های جداگانه دارای حاشیه زمان انتظار هستند. برای رعایت محدودیت‌های مربوط به انواع درخواست‌ها، می‌توان در کنار اولویت‌های مطلق، اولویت‌های نسبی را به برخی از درخواست‌ها اختصاص داد و بقیه را در حالت بدون اولویت ارائه کرد.
• با اولویت های متناوب- یک آنالوگ از اولویت های نسبی، اولویت فقط در لحظه تکمیل سرویس فعلی گروهی از درخواست های یک صف و انتصاب یک گروه جدید برای خدمات در نظر گرفته می شود.
• سرویس برنامه ریزی شده- درخواست‌های کلاس‌های مختلف (واقع در درایوهای مختلف) برای سرویس بر اساس یک برنامه زمان‌بندی مشخص انتخاب می‌شوند که توالی صف‌های نظرسنجی درخواست‌ها را مشخص می‌کند، به عنوان مثال، در مورد سه کلاس درخواست (درایو)، زمان‌بندی می‌تواند شبیه به این باشد. (2، 1، 3، 3، 1، 2) یا (1، 2، 3، 3، 2، 1).

در سیستم های کامپیوتری IM، به عنوان یک قاعده، این رشته به طور پیش فرض اجرا می شود FIFO.با این حال، آنها ابزارهایی دارند که به کاربر این امکان را می دهد تا رشته های خدمات مورد نیاز خود را سازماندهی کند، از جمله بر اساس یک برنامه.

برنامه های دریافت شده توسط SMO به کلاس ها تقسیم می شوند. در QS که انتزاعی است مدل ریاضی, برنامه های کاربردی مربوط به کلاس های مختلف در صورتی که در سیستم واقعی شبیه سازی شده حداقل در یکی از آنها تفاوت داشته باشند علائم زیر:

• مدت زمان خدمت؛
• اولویت های.

اگر برنامه‌ها در طول مدت خدمات و اولویت‌ها تفاوتی نداشته باشند، می‌توان آن‌ها را با برنامه‌های یک کلاس، از جمله برنامه‌هایی که از منابع مختلف دریافت می‌شوند، نشان داد.

برای توصیف ریاضی رشته‌های خدماتی با اولویت‌های مختلط، از آن استفاده می‌کنیم ماتریس اولویت, نمایندگی ماتریس مربع Q = (q, ;), من، ج - 1،...، I، I - تعداد کلاس های برنامه های کاربردی وارد شده به سیستم.

عنصر q(jماتریس اولویت درخواست های کلاس را مشخص می کند مندر رابطه با برنامه های کلاس؛ و می تواند مقادیر زیر را بگیرد:

• 0 - بدون اولویت
• 1 - اولویت نسبی;
• 2- اولویت مطلق

عناصر ماتریس اولویت باید موارد زیر را رعایت کنند الزامات:

• qn= 0، زیرا اولویت ها را نمی توان بین درخواست های یک کلاس تنظیم کرد.
• اگر q (j = 1 یا 2 بعد q^ = 0، زیرا اگر کلاس درخواست کند مننسبت به برنامه های کلاس اولویت دارند jپس دومی نمی تواند نسبت به برنامه های کلاس اولویت داشته باشد من (i,j = 1، ...، من).

بسته به توانایی تغییر اولویت هادر طول عملیات سیستم، رشته های اولویت دار بافر و نگهداری به دو دسته تقسیم می شوند:

• 1) با اولویت های ایستا،که با گذشت زمان تغییر نمی کنند؛
• 2) با اولویت های پویاکه ممکن است در حین کارکرد سیستم بسته به عوامل مختلف تغییر کند، برای مثال، زمانی که مقدار بحرانی مشخصی از طول صف برنامه های یک کلاس که اولویت ندارد یا دارای اولویت پایین است، می رسد، ممکن است اولویت بیشتری به آن داده شود. .

در سیستم های کامپیوتری IM همیشه یک عنصر (شیء) واحد وجود دارد که از طریق آن و تنها از طریق آن برنامه ها وارد مدل می شوند. به طور پیش فرض، تمام درخواست های وارد شده بدون اولویت هستند. اما امکاناتی برای تخصیص اولویت ها در دنباله 1، 2، ... وجود دارد، از جمله در هنگام اجرای مدل، i.e. در دینامیک

جریان خروجیجریان برنامه های کاربردی سرویس شده است که از QS خارج می شوند. در سیستم های واقعی، درخواست ها از چندین QS عبور می کنند: ارتباطات ترانزیت، نوار نقاله تولید و غیره. در این حالت، جریان خروجی، جریان ورودی برای QS بعدی است.

جریان ورودی اولین QS که از QS های بعدی عبور می کند، تحریف شده است و این امر مدل سازی تحلیلی را پیچیده می کند. با این حال، باید در نظر داشت که با ساده ترین جریان ورودی و سرویس نمایی(آنها در سیستم های مارکوف) جریان خروجی نیز ساده ترین است.اگر زمان سرویس دارای توزیع غیر نمایی باشد، جریان خروجی نه تنها ساده ترین نیست، بلکه تکراری نیز نیست.

توجه داشته باشید که فواصل زمانی بین درخواست های جریان خروجی با فواصل سرویس یکسان نیست. از این گذشته ، ممکن است معلوم شود که پس از پایان سرویس بعدی ، QS به دلیل کمبود برنامه برای مدتی بیکار است. در این حالت، فاصله جریان خروجی شامل زمان بیکاری QS و فاصله سرویس اولین درخواست برای رسیدن پس از زمان بیکاری است.

در QS، علاوه بر جریان خروجی برنامه های کاربردی سرویس شده، ممکن است وجود داشته باشد جریان درخواست های پردازش نشدهاگر چنین QS یک جریان مکرر دریافت کند، و سرویس به صورت نمایی باشد، در این صورت جریان درخواست های سرویس نشده تکراری است.

صف کانال های رایگان در QS چند کاناله، صف های کانال های رایگان می توانند تشکیل شوند. تعداد کانال های رایگان یک مقدار تصادفی است. محققان ممکن است علاقه مند باشند ویژگی های مختلفاین متغیر تصادفی معمولاً این میانگین تعداد کانال‌های اشغال شده توسط سرویس در طول بازه بررسی و فاکتورهای بار آنها است.

همانطور که قبلاً اشاره کردیم، در اشیاء واقعی برنامه‌ها به صورت متوالی در چندین QS سرویس می‌شوند.

مجموعه محدودی از QS های متوالی به هم پیوسته که درخواست های در حال گردش در آنها را پردازش می کند نامیده می شود شبکه صف (SeMO) (شکل 2.4، آ).

برنج. 2.4.

SeMO نیز نامیده می شود سیستم های صف چند فازی

در ادامه نمونه ای از ساخت IM SeMO را در نظر خواهیم گرفت.

عناصر اصلی SeMO گره ها (U) و منابع (مولدهای) برنامه ها (G) هستند.

گرهشبکه ها یک سیستم صف هستند.

منبع- تولید کننده درخواست هایی که وارد شبکه می شوند و به مراحل خاصی از سرویس در گره های شبکه نیاز دارند.

برای نمایش ساده SeMO، یک نمودار استفاده می شود.

SeMO را بشمارید - نمودار جهت دار(دیگراف)، که رئوس آن مربوط به گره های SeMO است، و کمان ها انتقال درخواست ها بین گره ها را نشان می دهند (شکل 2.4، ب).

بنابراین، ما به مفاهیم اساسی QS نگاه کرده ایم. اما هنگام توسعه سیستم‌های اطلاعات رایانه‌ای و بهبود آنها، پتانسیل خلاقانه عظیمی که در حال حاضر در مدل‌سازی تحلیلی QS وجود دارد، قطعاً استفاده می‌شود.

برای درک بهتر این پتانسیل خلاقبه عنوان اولین تقریب، ما بر طبقه بندی مدل های QS تمرکز خواهیم کرد.

در زیر نمونه هایی از ساده ترین سیستم های صف (QS) را در نظر خواهیم گرفت. اصطلاح "تک یاخته" به معنای "ابتدایی" نیست. مدل های ریاضی این سیستم ها قابل اجرا و با موفقیت در محاسبات عملی هستند.

smo تک کاناله با خرابی

داده شده: سیستم دارای یک کانال خدماتی است که ساده ترین جریان درخواست ها را با شدت دریافت می کند. جریان خدمات دارای شدت است. برنامه‌ای که سیستم را مشغول می‌بیند، بلافاصله آن را ترک می‌کند.

پیدا کردن: ظرفیت مطلق و نسبی QS و احتمال رد شدن درخواستی که در زمان t می رسد.

سیستم در هر تی> 0 می تواند در دو حالت باشد: اس 0 – کانال رایگان است. اس 1- کانال شلوغ است انتقال از اس 0 اینچ اس 1 با ظاهر یک برنامه کاربردی و شروع فوری خدمات آن مرتبط است. انتقال از اس 1 اینچ اس 0 به محض اتمام تعمیر و نگهداری بعدی انجام می شود (شکل 4).

شکل 4. نمودار حالت یک QS تک کاناله با خرابی

ویژگی های خروجی (ویژگی های عملکرد) این QS و سایر QS بدون نتیجه گیری و شواهد ارائه خواهد شد.

توان عملیاتی مطلق(میانگین تعداد برنامه های ارائه شده در واحد زمان):

شدت جریان برنامه ها کجاست (مقابل میانگین فاصله زمانی بین برنامه های ورودی -)؛

- شدت جریان سرویس (مقابل میانگین زمان سرویس)

پهنای باند نسبی(متوسط ​​سهم درخواست های ارائه شده توسط سیستم):

احتمال شکست(احتمال اینکه برنامه QS را بدون سرویس رها کند):

روابط زیر واضح است: و.

مثال. سیستم تکنولوژیکی از یک ماشین تشکیل شده است. ماشین به طور متوسط ​​هر 0.5 ساعت درخواست تولید قطعات را دریافت می کند. میانگین زمان تولید یک قطعه عبارت است از: اگر زمانی که درخواست ساخت قطعه ای دریافت می شود، دستگاه مشغول است، آن (قطعه) به دستگاه دیگری ارسال می شود. توان عملیاتی مطلق و نسبی سیستم و احتمال خرابی در تولید قطعه را بیابید.

آن ها به طور متوسط ​​تقریباً 46 درصد از قطعات در این دستگاه پردازش می شوند.

.

آن ها به طور متوسط ​​تقریباً 54 درصد قطعات برای پردازش به ماشین های دیگر ارسال می شوند.

N – کانال smo با خرابی (مشکل Erlang)

این یکی از اولین مشکلات تئوری صف است. این از نیازهای عملی تلفن ناشی شد و در اوایل قرن بیستم توسط ریاضیدان دانمارکی ارلنگ حل شد.

داده شده: سیستم دارد n- کانال هایی که جریانی از برنامه ها را با شدت دریافت می کنند. جریان خدمات دارای شدت است. برنامه‌ای که سیستم را مشغول می‌بیند، بلافاصله آن را ترک می‌کند.

پیدا کردنظرفیت مطلق و نسبی QS. احتمال اینکه یک سفارش در یک زمان برسد تی، رد خواهد شد؛ میانگین تعداد درخواست های ارائه شده به طور همزمان (یا به عبارت دیگر، میانگین تعداد کانال های شلوغ).

راه حل. وضعیت سیستم اس(SMO) با توجه به حداکثر تعداد درخواست ها در سیستم شماره گذاری می شود (مطابق با تعداد کانال های اشغال شده):

اس 0 - هیچ برنامه کاربردی در QS وجود ندارد.

اس 1 - یک درخواست در QS وجود دارد (یک کانال مشغول است، بقیه رایگان هستند).

اس 2 - دو درخواست در QS وجود دارد (دو کانال مشغول هستند، بقیه رایگان هستند).

اس n - واقع در QS n- برنامه های کاربردی (همه n- کانال ها مشغول هستند).

نمودار وضعیت QS در شکل نشان داده شده است. 5

شکل 5 نمودار حالت برای QS کانال n با خرابی

چرا نمودار حالت به این شکل مشخص شده است؟ از ایالت اس 0 به حالت اس 1 سیستم جریان برنامه ها را با شدت انتقال می دهد (به محض ورود برنامه، سیستم از اس 0 اینچ اس 1). اگر سیستم در حالتی بود اس 1 و درخواست دیگری رسیده است، سپس به حالت می رود اس 2 و غیره

چرا فلش های پایین (قوس های نمودار) اینقدر تشدید شده اند؟ بگذارید سیستم در حالت باشد اس 1 (یک کانال کار می کند). در واحد زمان خدمات تولید می کند. بنابراین، قوس گذار از حالت اس 1 در حالت اس 0 با شدت بارگذاری می شود. اجازه دهید سیستم در حال حاضر در حالت است اس 2 (دو کانال کار می کند). تا او بتواند برود اس 1، لازم است کانال اول یا کانال دوم سرویس را به پایان برساند. شدت کل جریان آنها و غیره است.

مشخصات خروجی (مشخصات کارایی) این QS به شرح زیر تعیین می شود.

مطلقایست بازرسیتوانایی:

جایی که n- تعداد کانال های QS؛

- احتمال قرار گرفتن QS در حالت اولیه زمانی که همه کانال ها آزاد هستند (احتمال نهایی QS در حالت اس 0);

شکل 6. نمودار را برای طرح "مرگ و تولید مثل".

برای نوشتن فرمولی برای تعیین، شکل 6 را در نظر بگیرید

نمودار ارائه شده در این شکل، گراف حالت برای طرح "مرگ و تولید مثل" نیز نامیده می شود. اجازه دهید ابتدا فرمول کلی برای (بدون اثبات) را بنویسیم:

ضمناً احتمالات نهایی باقی مانده از حالت های QS به صورت زیر نوشته می شود.

اس 1 وقتی یک کانال مشغول است:

احتمال اینکه CMO در یک وضعیت باشد اس 2، یعنی زمانی که دو کانال مشغول هستند:

احتمال اینکه CMO در یک وضعیت باشد اس n، یعنی وقتی همه کانال ها مشغول هستند

اکنون برای n - کانال QS با خرابی

پهنای باند نسبی:

به یاد داشته باشید که این میانگین سهم درخواست های ارائه شده توسط سیستم است. که در آن

احتمالامتناع:

به یاد داشته باشید که این احتمال وجود دارد که برنامه QS را بدون سرویس رها کند. بدیهی است که

میانگین تعداد کانال‌های شلوغ (میانگین تعداد درخواست‌های ارائه‌شده به طور همزمان):