smo چند کاناله با صف نامحدود. احتمال شکست
سیستم تک کانال با صف نامحدود.در عمل اغلب با QS یک کاناله با صف نامحدود مواجه میشویم (مثلاً تلفن پرداختی با یک غرفه). بیایید تکلیف را در نظر بگیریم.
یک QS تک کانال با یک صف وجود دارد که هیچ محدودیتی در آن اعمال نمی شود (نه در طول صف و نه در زمان انتظار). جریان درخواستهایی که به QS میرسند دارای شدت λ و جریان خدمات دارای شدت μ است. یافتن احتمالات محدود کننده حالت ها و شاخص های کارایی QS ضروری است.
این سیستم می تواند در یکی از حالت های S 0 , S 1 , S 2 , …, S k , با توجه به تعداد برنامه های کاربردی در QS باشد: S 0 - کانال رایگان است. S 1 - کانال مشغول است (درخواست را ارائه می دهد)، هیچ صفی وجود ندارد، S 2 - کانال مشغول است، یک درخواست در صف است. ... S k - کانال مشغول است، (k-1) درخواست ها در صف هستند و غیره.
نمودار وضعیت QS در شکل نشان داده شده است. هشت
برنج. هشت
این یک فرآیند مرگ و تولید مثل است، اما با تعداد بی نهایت حالت، که در آن شدت جریان برنامه ها برابر با λ است، و شدت جریان خدمات μ است.
قبل از نوشتن فرمول های احتمالات محدود کننده، باید از وجود آنها مطمئن شد، زیرا در حالتی که زمان t→∞ باشد، صف می تواند به طور نامحدود رشد کند. ثابت کرد که اگرρ<1, آن ها میانگین تعداد درخواستهای دریافتی کمتر از میانگین تعداد درخواستهای ارائهشده (در واحد زمان) است، پس احتمالات حاشیهای وجود دارد. اگر یکρ≥1، صف تا بی نهایت رشد می کند.
برای تعیین احتمالات محدود کننده حالتها، از فرمولهای (16)، (17) برای فرآیند مرگ و تولید مثل استفاده میکنیم (در اینجا ما محدودیت خاصی را مجاز میدانیم، زیرا این فرمولها قبلاً برای مورد تعداد محدودی از سیستم به دست آمده بودند. ایالت ها). دریافت (32)
از آنجایی که احتمالات محدود کننده فقط برای ρ وجود دارد< 1, то геометрический ряд со знаменателем
ρ < 1, записанный в скобках в формуле (32), сходится к сумме, равной . Поэтому
(33)
و با در نظر گرفتن روابط (17)
احتمالات محدود کننده حالت های دیگر را بیابید
(34)
احتمالات حد p 0 , p 1 , p 2 , …, p k ,… یک حرفه هندسی نزولی با مخرج p تشکیل می دهند.< 1, следовательно, вероятность р 0 - наибольшая. Это означает, что если СМО справляется с потоком заявок (при ρ < 1), то наиболее вероятным будет отсутствие заявок в системе.
میانگین تعداد برنامه های کاربردی در سیستم L sist. ما با فرمول انتظار ریاضی تعریف می کنیم که با در نظر گرفتن (34) شکل می گیرد (35)
(مجموع از 1 تا ∞، از جمله صفر 0p 0 = 0).
می توان نشان داد که فرمول (35) تبدیل شده است (برای ρ< 1) к виду
(36)
میانگین تعداد برنامه ها را در صف L och پیدا کنید. بدیهی است که (37)
جایی که L در مورد. - میانگین تعداد برنامه های تحت سرویس.
میانگین تعداد درخواستهای تحت سرویس با فرمول انتظار ریاضی تعداد درخواستهای تحت سرویس تعیین میشود که مقادیر 0 (در صورت رایگان بودن کانال) یا 1 (اگر کانال مشغول است) را میگیرد:
آن ها میانگین تعداد درخواست های تحت سرویس برابر با احتمال اشغال بودن کانال است: (38)
نیرو (33) (39)
حال طبق فرمول (37) با احتساب (36) و (39)
(40)
ثابت کرد که برای هر نوع جریان برنامهها، برای هر توزیع زمان خدمات، برای هر رشته خدمات، میانگین زمان اقامت یک برنامه کاربردی در سیستم (صف) برابر است با میانگین تعداد برنامههای کاربردی در سیستم (در صف). ) تقسیم بر شدت جریان برنامه ها،آن ها (41)
(42)
فرمول های (41) و (42) نامیده می شوند فرمول های لیتلآنها از این واقعیت ناشی می شوند که در حالت محدود، ثابت، میانگین تعداد مشتریانی که وارد سیستم میشوند برابر با میانگین تعداد مشتریانی است که از آن خارج میشوند:هر دو جریان برنامه ها دارای شدت λ هستند.
بر اساس فرمول های (41) و (42) با در نظر گرفتن (36) و (40) میانگین زمان اقامت یک برنامه کاربردی در سیستم با فرمول تعیین می شود: (43)
و میانگین زمانی که یک برنامه در صف صرف می کند
(44)
QS چند کاناله با صف نامحدود. بیایید تکلیف را در نظر بگیریم. یک QS کانال n با صف نامحدود وجود دارد. جریان درخواستهایی که به QS میرسند دارای شدت λ و جریان خدمات دارای شدت μ است. یافتن احتمالات محدود کننده حالت های QS و شاخص های کارایی آن ضروری است.
سیستم می تواند در یکی از حالت های S 0 , S 1 , S 2 ,…, S k ,…, S n ,…, - شماره گذاری شده با توجه به تعداد درخواست ها در QS: S 0 - هیچ درخواستی در سیستم (همه کانال ها رایگان هستند)؛ S 1 - یک کانال مشغول است، بقیه رایگان هستند. S 2 - دو کانال مشغول هستند، بقیه آزاد هستند؛...، S k - k کانال ها مشغول هستند، بقیه آزاد هستند؛...، S n - همه n کانال مشغول هستند (صف وجود ندارد). S n+1 - همه n کانال اشغال شده اند، یک درخواست در صف وجود دارد؛...، S n+r - همه اشغال شده اند nکانال ها، rبرنامه ها در صف هستند...
نمودار وضعیت سیستم در شکل نشان داده شده است. 9. به این نکته توجه کنیم که برخلاف QS قبلی، شدت جریان سرویس (انتقال سیستم از یک حالت به حالت دیگر از راست به چپ) ثابت نمی ماند، بلکه با افزایش تعداد درخواست ها در QS. از 0 به n، از m به nm افزایش می یابد، زیرا تعداد کانال های سرویس بر این اساس افزایش می یابد. وقتی تعداد درخواستها در QS بیشتر از n باشد، شدت جریان سرویس برابر nm باقی میماند.
برنج. 9
می توان نشان داد که برای r/n< 1 предельные вероятности существуют. Если r/n >1، صف تا بی نهایت رشد می کند. با استفاده از فرمول های (16) و (17) برای فرآیند مرگ و تولید مثل، می توانیم فرمول های زیر را برای احتمالات محدود کننده حالت های یک QS کانال n با یک صف نامحدود به دست آوریم.
(45)
(46)
(47)
احتمال اینکه برنامه در صف قرار گیرد،
(48)
برای یک QS کانال n با صف نامحدود، با استفاده از ترفندهای قبلی، می توانید پیدا کنید:
کانال های شلوغ متوسط
(49)
میانگین تعداد برنامه های کاربردی در صف
(50)
میانگین تعداد برنامه های کاربردی در سیستم (51)
میانگین زمان اقامت یک برنامه کاربردی در صف و میانگین زمان اقامت یک برنامه کاربردی در سیستم، مانند قبل، با استفاده از فرمول های Little (42) و (41) به دست می آید.
اظهار نظر.برای یک QS با یک صف نامحدود برای r< 1 любая заявка, пришедшая в систему, будет обслужена,
т.е. вероятность отказа P отк = 0, относительная пропускная способность
Q= 1، و توان عملیاتی مطلق برابر است با شدت جریان ورودی برنامه ها، یعنی. A =ل
QS با صف محدود
QS با صف محدود. QS با یک صف محدود با مشکلات در نظر گرفته شده در بالا تنها از این جهت متفاوت است که تعداد برنامههای کاربردی در صف محدود است (نمیتواند از تعداد دادهشده تجاوز کند. ت).اگر ادعای جدیدی در لحظهای وارد شود که همه مکانهای صف اشغال شدهاند، QS را بدون ارائه میگذارد، یعنی. رد می شودبدیهی است که می توان از همان رویکرد فوق برای محاسبه احتمالات محدود کننده حالت ها و شاخص های عملکرد چنین QS استفاده کرد، با این تفاوت که لازم است یک پیشروی بی نهایت خلاصه شود (همانطور که برای مثال هنگام استخراج فرمول انجام دادیم. (33))، اما متناهی.
میانگین زمان اقامت یک برنامه کاربردی در صف و در سیستم، مانند قبل، با فرمول های لیتل (44) و (43) تعیین می شود.
CMO با زمان انتظار محدود.در عمل، اغلب با CMOهایی با برنامه های به اصطلاح "بی صبر" مواجه می شوید. اگر زمان انتظار از مقدار معینی بیشتر شود، چنین درخواست هایی ممکن است صف را ترک کنند. به طور خاص، چنین کاربردهایی در سیستمهای فنآوری مختلف به وجود میآیند که در آن تاخیر در شروع خدمات میتواند منجر به از دست دادن کیفیت محصول شود، در سیستمهای مدیریت عملیاتی، زمانی که پیامهای فوری ارزش (یا حتی معنی) را در صورت عدم رسیدن به آن از دست میدهند. خدمات در یک بازه زمانی معین.
در تک یاخته ها مدل های ریاضیچنین سیستم هایی، فرض می شود که برنامه می تواند در صف باشد زمان تصادفی، بر اساس قانون نمایی با برخی پارامتر υ توزیع شده است. می توانیم به صورت مشروط فرض کنیم که هر مشتری در صف خدمات می تواند با نرخ υ سیستم را ترک کند.
شاخص های مناسب اثربخشی QS با زمان محدود بر اساس نتایج به دست آمده برای روند مرگ و تولید مثل به دست می آید.
در خاتمه، متذکر می شویم که در عمل اغلب سیستم های صف بسته وجود دارد که در آن جریان ورودی درخواست ها به طور قابل توجهی به وضعیت خود QS بستگی دارد. به عنوان مثال می توان به وضعیتی اشاره کرد که برخی از ماشین ها از محل کار به پایگاه تعمیر می آیند: واضح است که هر چه ماشین آلات در حالت تعمیر بیشتر باشد، استفاده از آنها کمتر می شود و شدت کار کمتر می شود. جریان ماشینهای جدیدی که برای تعمیر میآیند. QS بسته با تعداد محدودی از منابع درخواست مشخص می شود و هر منبع برای مدت زمان سرویس درخواست خود "مسدود" می شود (یعنی درخواست های جدیدی صادر نمی کند). در چنین سیستم هایی، با تعداد محدودی از حالت های QS، احتمالات محدود کننده برای هر مقدار از شدت درخواست ها و جریان خدمات وجود خواهد داشت. اگر دوباره به روند مرگ و تولید مثل روی آوریم، می توان آنها را محاسبه کرد.
سیستمهای MO بخشی از یک کلاس وسیعتر از سیستمهای دینامیکی هستند که گاهی اوقات به عنوان سیستمهای جریان شناخته میشوند. سیستم جریان سیستمی است که در آن برخی آیتم ها از طریق یک یا چند کانال با پهنای باند محدود حرکت می کنند تا از نقطه ای به نقطه دیگر منتقل شوند. هنگام تجزیه و تحلیل سیستم های جریان، آنها به دو دسته اصلی تقسیم می شوند:
سیستم های منظم، یعنی سیستم هایی که در آنها جریان ها به شیوه ای قابل پیش بینی رفتار می کنند (میزان جریان و زمان ظهور آن در کانال مشخص است). در مواردی که تنها یک کانال وجود دارد، محاسبه سیستم بی اهمیت است. بدیهی است بین شدت جریان λ و سرعت سرویس بایک نسبت وجود دارد λ < ج;
سیستمهای نامنظم، یعنی سیستمهایی که در آنها جریانها به روشهای غیرقابل پیشبینی رفتار میکنند.
جالب تر، مورد یک جریان معمولی است که در شبکه ای از کانال ها توزیع می شود. بدیهی است که شرط λ < جذخیره شده برای هر کانال در این مورد، یک مشکل ترکیبی پیچیده ایجاد می شود.
هفت راه وجود دارد:
A→B→D→E→F
A→C→B→E→F
A→C→B→D→E→F
A→C→B→D→F
حمل و نقل کالا از ولیکه در اف. پهنای باند هر کانال مشخص است. پهنای باند شبکه چقدر است و جریان باید کدام مسیر را طی کند؟ این مشکل را می توان با استفاده از قضیه در حل کرد حداکثر جریان، که قبلا در نظر گرفتیم (شکل 6).
دسته دوم شامل جریان های احتمالی تصادفی است که در آن زمان دریافت نیاز مشخص نیست، تعداد نیازها غیرقابل پیش بینی است. این نظریه به حل چنین مشکلاتی می پردازد. در صف.
در حالت کلی، سیستم صف را می توان در شکل 7 نشان داد.
برنج. 7.
موضوع تئوری صفایجاد رابطه بین ماهیت جریان برنامه ها، تعداد کانال ها، عملکرد، عملکرد صحیح و کارایی است.
مانند ویژگی های عملکردکمیت ها و توابع زیر را می توان اعمال کرد:
میانگین تعداد برنامه هایی که می تواند توسط QS در واحد زمان ارائه شود.
میانگین تعداد درخواست هایی که رد می شوند و CMO را ترک می کنند.
احتمال اینکه درخواست دریافت شده بلافاصله ارائه شود.
میانگین زمان انتظار در صف؛
میانگین تعداد برنامه های موجود در صف؛
میانگین درآمد CMO در واحد زمان و دیگران شاخص های اقتصادی CMO.
تجزیه و تحلیل QS ساده می شود اگر یک فرآیند مارکوف در سیستم رخ دهد، سپس سیستم را می توان با معادلات دیفرانسیل معمولی توصیف کرد، و احتمالات محدود کننده را می توان با معادلات جبری خطی توصیف کرد.
یک فرآیند مارکوف مستلزم آن است که همه جریانها پواسون باشند (بدون عواقب بعدی)، اما دستگاه فرآیندهای مارکوف نیز زمانی استفاده میشود که فرآیند مارکوف نباشد. در این مورد، ویژگی های QS را می توان تقریباً تخمین زد: هرچه QS پیچیده تر باشد، تقریب دقیق تر است.
طبقه بندی سیستم های نوبت دهی
SMO ها می توانند دو نوع باشند:
CMO با شکست.
QS با انتظار (یعنی با یک صف).
سرویس در سیستم های دارای صف می تواند کاراکتر متفاوتی داشته باشد:
خدمات را می توان ساده کرد.
سرویس تصادفی؛
سرویس اولویت، که در آن اولویت می تواند قطع یا بدون وقفه باشد.
سیستم های دارای صف به دو دسته تقسیم می شوند:
سیستم های با انتظار نامحدود، در حالی که وظیفه وارد شده به QS در صف است و منتظر سرویس است. دیر یا زود به او خدمت خواهد شد.
سیستم های با انتظار محدود، در حالی که محدودیت هایی برای برنامه در صف اعمال می شود، به عنوان مثال، مدت زمان محدودی در صف، طول صف، کل زمان صرف شده در QS. بسته به نوع QS می توان از شاخص های مختلفی برای ارزیابی اثربخشی استفاده کرد.
برای QS با خرابی، از شاخص های عملکرد زیر استفاده می شود:
پهنای باند مطلق ولی- میانگین تعداد برنامه هایی که می توان در واحد زمان ارائه کرد.
توان نسبی سمیانگین نسبی تعداد برنامه ها است. در این مورد، توان نسبی را می توان با فرمول پیدا کرد
جایی که λ شدت دریافت برنامه ها در QS است.
برای QS با انتظار پهنای باند مطلق ولیو توان نسبی سمعنای خود را از دست می دهند، اما ویژگی های دیگر مهم می شوند:
واحد زمان انتظار در صف؛
میانگین تعداد برنامه های موجود در صف؛
میانگین زمان صرف شده در سیستم
برای یک QS با یک صف محدود، هر دو گروه از ویژگی ها مورد توجه هستند.
مشکلات پیچیده تر در تئوری صف
در این قسمت به اختصار برخی از مسائل مربوط به QS های غیر مارکوف را بررسی می کنیم. تا کنون تمام فرمول ها توسط ما یا بر اساس آن استخراج شده است حداقلخواننده، مسلح به طرح مرگ و تولید مثل، فرمول لیتل و توانایی تمایز، می تواند استنباط کند. آنچه در این پاراگراف گفته خواهد شد، خواننده باید ایمان بیاورد.
تاکنون فقط با سادهترین QS سروکار داشتهایم، که برای آن همه جریانهای رویدادهایی که آنها را از حالتی به حالت دیگر منتقل میکنند، سادهترین هستند. اما اگر ساده ترین نباشند چه؟ این فرض چقدر واقع بینانه است؟ خطاهایی که هنگام نقض آن منجر به آن می شود چقدر قابل توجه است؟ ما در اینجا سعی خواهیم کرد به همه این سوالات پاسخ دهیم.
هرچند غم انگیز به نظر می رسد، اما باید اعتراف کنیم که در زمینه تئوری صف های غیر مارکویی، چیز خاصی برای بالیدن نداریم. برای QS غیرمارکوین، فقط نتایج جداگانه و خواندنی وجود دارد که امکان بیان مشخصههای QS را به شکلی صریح و تحلیلی از طریق شرایط دادهشده مسئله - تعداد کانالها، ماهیت جریان برنامهها، نوع سرویس فراهم میکند. توزیع زمان ما برخی از این نتایج را ارائه می دهیم.
1. n- کانال QS با خرابی، با ساده ترین جریان برنامه ها و توزیع دلخواه زمان سرویس.در بخش قبل، فرمول های Erlang (20.4)، (20.5) را برای احتمالات نهایی حالت های QS با خرابی استخراج کردیم. اخیراً (در سال 1959) B. A. Sevastyanov ثابت کرد که این فرمول ها نه تنها برای یک توزیع نمایی، بلکه برای توزیع دلخواه زمان خدمات نیز معتبر هستند.
^ 2. QS تک کانالی با صف نامحدود، ساده ترین جریان درخواست ها و توزیع دلخواه زمان سرویس. اگر یک QS تک کاناله با یک صف نامحدود ساده ترین جریان درخواست ها را با شدت λ دریافت کند. , و زمان سرویس دارای توزیع دلخواه با انتظارات ریاضی است تیدور = 1/μ. و ضریب تغییرات vμ ، پس میانگین تعداد درخواست ها در صف برابر است با
و میانگین تعداد برنامه های کاربردی در سیستم
(21.2)
جایی که، مانند قبل، ρ = λ/μ ., آ v μ -نسبت متوسط انحراف معیارزمان سرویس به انتظارات ریاضی آن فرمول های (21.1)، (21.2) فرمول های پلیچک-خینچین نامیده می شوند.
دلیا Lآه و L syst در λ، طبق فرمول Little، میانگین زمان اقامت برنامه در صف و میانگین زمان اقامت در سیستم را بدست می آوریم:
(21.3)
(21.4)
توجه داشته باشید که در موارد خاص که زمان سرویس به صورت تصاعدی است، vμ = 1 و فرمول های (21.1)، (21.2) به فرمول های (20.16)، (20.20) تبدیل می شوند که از قبل برای ساده ترین QS یک کاناله برای ما آشنا هستند. بیایید یک مورد خاص دیگر را در نظر بگیریم - زمانی که زمان سرویس به هیچ وجه تصادفی نیست و vμ = 0. سپس میانگین تعداد درخواست ها در صف نسبت به ساده ترین حالت نصف می شود. این طبیعی است: اگر سرویس برنامه به روشی سازماندهی شده تر و "منظم" پیش برود، QS بهتر از سرویس های نامنظم و نامناسب کار می کند.
^ 3. QS تک کاناله با جریان دلخواه درخواست ها و توزیع دلخواه زمان سرویس.ما یک QS تک کاناله با یک صف نامحدود در نظر می گیریم که یک جریان تکراری دلخواه درخواست ها با شدت λ و ضریب تغییرات را دریافت می کند. vفواصل λ بین درخواست ها، بین صفر و یک نتیجه گرفته شده است: 0< v λ < 1. زمان خدمات تی o نیز دارای توزیع دلخواه با میانگین است تی vol = 1/μ و ضریب تغییرات v μهمچنین بین صفر و یک محصور شده است. برای این مورد، نمی توان فرمول های تحلیلی دقیقی به دست آورد.
فقط می توان تقریباً طول متوسط صف را تخمین زد، آن را از بالا و پایین محدود کرد.
ثابت شده است که در این مورد
اگر جریان ورودی ساده ترین باشد، هر دو تخمین - بالا و پایین - مطابقت دارند و فرمول پلیچک-خینچین (21.1) به دست می آید. برای یک تخمین تقریبی از میانگین طول صف، M.A. Fainberg (نگاه کنید به ) یک مقدار بسیار به دست آورد فرمول ساده:
(21.6)
میانگین تعداد برنامه های کاربردی در سیستم از به دست می آید L och با اضافه کردن ρ - میانگین تعداد درخواست های سرویس شده:
Lسیستم = L och + ρ. (21.7)
در مورد میانگین زمان اقامت یک برنامه کاربردی در صف و در سیستم، آنها با استفاده از آنها محاسبه می شوند Lاوه و L syst با فرمول لیتل با تقسیم بر λ .
بنابراین، ویژگیهای QS تک کاناله با صف نامحدود را میتوان (اگر نه دقیقاً، تقریباً) در مواردی یافت که جریان درخواستها و خدمات سادهترین نیست.
یک سوال طبیعی مطرح می شود: در مورد QS غیر مارکوف چند کانالی چطور؟ صراحتاً پاسخ خواهیم داد: بد. روش های تحلیلی دقیقی برای چنین سیستم هایی وجود ندارد. تنها چیزی که همیشه می توانیم پیدا کنیم میانگین تعداد کانال های شلوغ است k =ρ. مربوط به Lاوه، Lسیستم، دبلیواوه، دبلیو syst، نوشتن چنین فرمول های کلی برای آنها غیرممکن است.
درست است، اگر واقعاً تعداد زیادی کانال (4-5 یا بیشتر) وجود داشته باشد، زمان نشان دهنده خدمات ترسناک نیست: جریان ورودی ساده ترین خواهد بود. در واقع، جریان کل "آزاد شدن" کانال ها از جریان های انتشار کانال های مجزا تشکیل شده است، و در نتیجه چنین همپوشانی ("سوپرپوزیشن")، همانطور که می دانیم، جریانی نزدیک به ساده ترین به دست می آید. بنابراین در این مورد، جایگزینی یک توزیع زمان خدمات غیر نمایی با یک توزیع نمایی منجر به خطاهای نسبتاً کوچکی می شود. خوشبختانه، جریان ورودی برنامه ها در بسیاری از مسائل عملی به ساده ترین آنها نزدیک است.
وضعیت زمانی بدتر می شود که جریان ورودی آشکارا ساده ترین نیست. خوب، در این مورد، شما باید در ترفندها افراط کنید. به عنوان مثال، دو QS تک کاناله را انتخاب کنید که یکی از آنها آشکارا از نظر کارایی "بهتر" از این کانال چند کاناله است و دیگری آشکارا "بدتر" است (صف طولانی تر است، زمان انتظار طولانی تر است). و برای QS تک کاناله، ما به نوعی می دانیم که چگونه ویژگی ها را در هر صورت پیدا کنیم.
چگونه می توان چنین QS تک کانالی را انتخاب کرد - "بهترین" و "بدترین"؟ این را می توان به روش های مختلف انجام داد. به نظر می رسد که بدترین نوع بدیهی را می توان با از هم پاشیدگی داده شده به دست آورد n-کانال QS روشن است پتک کانالی، و کل ساده ترین جریانی را که به آنها می رسد بین این QS های تک کانالی به ترتیب اولویت توزیع کنید: درخواست اول - به QS اول، دوم - به دوم و غیره. ما می دانیم که در این مورد، هر QS یک جریان Erlang را دریافت خواهد کرد nمرتبه ام با ضریب تغییرات برابر 1/ . در مورد ضریب تغییرات زمان سرویس نیز ثابت می ماند. برای چنین QS تک کانالی، ما قبلاً می دانیم که چگونه زمان اقامت یک برنامه کاربردی را در سیستم محاسبه کنیم. دبلیوسیستم مطمئناً بیشتر از نسخه اصلی خواهد بود n-کانال QS با دانستن این زمان، میتوانیم با استفاده از فرمول Little و ضرب میانگین زمان در شدت λ از کل جریان برنامهها، یک تخمین بدبینانه برای میانگین تعداد برنامههای موجود در صف ارائه کنیم. با جایگزینی می توان یک تخمین "خوشبینانه" به دست آورد n- کانال QS یک کاناله، اما با نرخ جریان سرویس nبرابر بزرگتر از یک معین، برابر با nμ. به طور طبیعی، در این مورد، پارامتر ρ نیز باید تغییر کند، کاهش یابد nیک بار. برای چنین زمان CMOماندن برنامه در سیستم دبلیو syst به دلیل این واقعیت که سرویس در ادامه دارد کاهش می یابد nزمان کمتر با استفاده از مقدار اصلاح شده، ضریب تغییرات جریان ورودی vλ و زمان سرویس v μ ,
ما تقریباً می توانیم میانگین تعداد برنامه های کاربردی در سیستم را محاسبه کنیم. با کم کردن مقدار اصلی (بدون تغییر) ρ، میانگین تعداد برنامه های موجود در صف را بدست می آوریم. . هر دو ویژگی کمتر از نسخه اصلی خواهد بود nکانال QS (تخمین "خوشبینانه" خواهد بود). از آنها، تقسیم بر λ ,
می توان به برآوردهای "خوشبینانه" برای زمان صرف شده در QS و در صف عبور کرد.
سیستم با طول صف محدود. یک کانال QS با انتظار در نظر بگیرید که جریانی از درخواستها را با شدت دریافت میکند. شدت سرویس (برای یک کانال)؛ تعداد صندلی های صف
ایالت های سیستم با توجه به تعداد درخواست های متصل شده توسط سیستم شماره گذاری می شوند:
بدون صف:
همه کانال ها رایگان هستند.
یک کانال شلوغ است، بقیه رایگان هستند.
کانال های شلوغ، بقیه نیستند.
همه کانال ها مشغول هستند، کانال رایگان وجود ندارد.
یک صف وجود دارد:
تمام n کانال اشغال شده است. یک برنامه در صف قرار دارد.
همه n کانال اشغال شده اند، درخواست های r در صف قرار دارند.
تمام n کانال اشغال شده است، متربرنامه های کاربردی در صف
GSP در شکل نشان داده شده است. 5.9. هر فلش دارای شدت های مربوط به جریان رویداد است. با توجه به فلش های از چپ به راست، سیستم همیشه با همان جریان درخواست ها با شدت منتقل می شود، با توجه به فلش های از راست به چپ، سیستم توسط یک جریان سرویس منتقل می شود که شدت آن برابر است، ضرب می شود. با تعداد کانال های شلوغ
نمایی چند کاناله CMOبا تک کانال به شرح زیر متفاوت است. تعداد کانال های موجود در آن بیش از یک کانال است. اگر همه کانال ها مشغول باشند، یک درخواست ورودی در صف قرار می گیرد. در غیر این صورت، برنامه طول می کشد کانال رایگان. (5.56)
ما عباراتی را برای احتمالات محدود کننده حالت ها با استفاده از نماد می نویسیم: (به 5.45 مراجعه کنید)
احتمال شکست. درخواست دریافت شده در صورتی که همه اشغال باشند رد می شود nکانال ها و همه مترمکان های در صف:
(5.57)
توان نسبی احتمال شکست را با یک تکمیل می کند:
توان عملیاتی مطلق QS:
(5.58)
میانگین کانال های شلوغ. برای CMOبا خرابی ها، با میانگین تعداد برنامه های کاربردی در سیستم همزمان بود. برای CMOبا یک صف، میانگین تعداد کانالهای شلوغ با میانگین تعداد درخواستها در سیستم منطبق نیست: مقدار دوم با میانگین تعداد درخواستها در صف با اولی متفاوت است.
اجازه دهید میانگین تعداد کانال های شلوغ را مشخص کنیم. هر کانال شلوغ به طور متوسط به ازای هر واحد زمان درخواست ها را ارائه می دهد و CMOبه طور کلی به طور متوسط خدمت می کند ولیدرخواست در واحد زمان با تقسیم یکی بر دیگری بدست می آوریم:
میانگین تعداد مشتریان در صف را می توان به طور مستقیم به عنوان انتظار ریاضی از یک گسسته محاسبه کرد. متغیر تصادفی:
(5.59)
در اینجا دوباره (بیان داخل پرانتز) مشتقی از مجموع وجود دارد پیشرفت هندسی(نگاه کنید به (5.50)، (5.51)-(5.53) بالا)، با استفاده از رابطه برای آن، به دست می آوریم:
میانگین تعداد برنامه های کاربردی در سیستم:
میانگین زمان انتظار برای یک برنامه در صف. اجازه دهید تعدادی از موقعیتها را در نظر بگیریم که در حالتی که یک درخواست تازه وارد سیستم را پیدا میکند و مدت زمانی که باید منتظر سرویس بماند، متفاوت است.
اگر نهاد همه کانالها را مشغول نبیند، اصلاً نباید منتظر بماند (شرایط مربوطه در انتظارات ریاضیبرابر با صفر هستند). اگر برنامه زمانی وارد شود که همه مشغول هستند پکانالها، و هیچ صفی وجود ندارد، باید مدت زمان متوسطی برابر با (چون "جریان انتشار" کانالها شدت دارد) صبر کند. اگر مشتری تمام کانال ها را مشغول و یک مشتری در مقابل خود در صف بیابد، باید به طور متوسط (برای هر مشتری پیش رو) منتظر بماند. اگر مشتری آن را در صف مشتریان بیابد، باید منتظر بماند. به طور متوسط صبر کنید . اگر برنامه تازه وارد شده از قبل خود را در صف بیابد متربرنامه ها، پس اصلا منتظر نمی ماند (اما ارائه نمی شود).
میانگین زمان انتظاربا ضرب هر یک از این مقادیر در احتمالات مربوطه پیدا کنید:
(5.60)
همانطور که در مورد QS تک کانالی با انتظار، توجه می کنیم که این عبارت با عبارت میانگین طول صف (5.59) تنها با ضریب تفاوت دارد، یعنی.
میانگین زمان اقامت یک برنامه کاربردی در سیستم، مانند تک کاناله CMO، با میانگین زمان انتظار در میانگین زمان خدمات ضرب در توان عملیاتی نسبی متفاوت است:
سیستم هایی با طول صف نامحدود.
ما یک کانال QS با انتظار در نظر گرفته ایم، زمانی که بیش از آن نباشد متربرنامه های کاربردی.
همانطور که قبلاً هنگام تجزیه و تحلیل سیستم ها بدون محدودیت، لازم است روابط به دست آمده برای .
احتمال حالت ها را از فرمول (5.56) با عبور از حد (در) بدست می آوریم. توجه داشته باشید که مجموع پیشرفت هندسی مربوطه برای > 1 همگرا و واگرا می شود. با فرض اینکه< 1 и устремив в формулах (5.56) величину مترتا بی نهایت، عباراتی را برای احتمالات محدود کننده حالت ها به دست می آوریم:
(5.61)
احتمال شکست، توان عملیاتی نسبی و مطلق. از آنجایی که هر درخواست دیر یا زود ارائه می شود، ویژگی های توان عملیاتی QS عبارتند از:
میانگین تعداد درخواست ها در صف از (5.59) به دست می آید:
و میانگین زمان انتظار - از (5.60):
میانگین تعداد کانال های شلوغ، مانند قبل، بر حسب توان عملیاتی مطلق تعیین می شود:
میانگین تعداد مشتریان مرتبط با QS به عنوان میانگین تعداد مشتریان در صف به اضافه تعداد متوسط مشتریان تحت سرویس (متوسط تعداد کانال های شلوغ) تعریف می شود:
پیچیدگی ساختارها و حالتهای سیستمهای واقعی، بکارگیری روشهای کلاسیک تئوری صف را به دلیل افزایش ابعاد وظایف در حال حل دشوار میسازد، که مخصوصاً برای سیستمهایی با ساختار شبکهای معمول است. یکی از راه های ممکن برای غلبه بر بعد، استفاده از مدل هایی در قالب شبکه های صف (QNS) است.
Semoمجموعه ای از تعداد محدودی از گره های سرویس است که در آن درخواست ها در حال گردش هستند و مطابق با ماتریس مسیریابی از یک گره به گره دیگر حرکت می کنند. گره همیشه باز است CMO. در عین حال فردی CMO CMO- ساختار سیستم، و الزامات در گردش از طریق Semo, - اجزاء جریان مواد(پیام ها (بسته ها) در یک شبکه ارتباطی، وظایف در سیستم های چند پردازنده ای، کانتینرهای جریان محموله و غیره).
در نوبتش، Semoبرای تعیین مهمترین ویژگی های سیستم استفاده می شود سیستم های اطلاعاتی: بهره وری؛زمان تحویل بسته؛ احتمال از دست دادن پیام و مسدود شدن در گره ها; مناطقی با مقادیر مجاز بار، که در آن کیفیت خدمات مورد نیاز ارائه می شود و غیره.
در تئوری Semoاساسی مفهوم وضعیت شبکه است. مهمترین ویژگی شبکه ها MO- احتمالات حالات آنها. برای تعیین احتمالات حالت ها Semoفرآیند تصادفی رخ داده در شبکه را مطالعه کنید. به عنوان مدل هایی که در جریان هستند Semoفرآیندهای مارکوف و نیمه مارکوف نیز بیشتر مورد استفاده قرار می گیرند.
3.3. سیستم نوبت دهی به عنوان یک مدل
1.5. شبکه های صف
یک فرآیند مارکوف با زمان پیوسته، عملیات نمایی را توصیف می کند SEMO.
شبکه نامیده می شود نماییاگر تقاضای ورودی به هر یک جریان یابد CMO Poisson، و زمان اجرای هر مرحله خدمات در هر CMOشبکه ها، دارند نماییتوزیع این به ما امکان می دهد در نظر بگیریم که مراحل سرویس مستقل از یکدیگر هستند و به پارامترهای جریان ورودی، یا وضعیت شبکه یا مسیرهای مورد نیاز بستگی ندارند.
نظریه نمایی Semoبیشتر توسعه یافته است و به طور گسترده هم برای مطالعه شبکه های PD و هم برای مطالعه چند پردازنده استفاده می شود سیستم های محاسباتی (CS).فرمول های عملی برای محاسبه ویژگی های احتمالی- زمانی (TTS) چنین شبکه ها و سیستم هایی ایجاد شده است.
تلاش برای تحلیل عمیق مدلهای غیرمارکوویی سیستمهای شبکه با مشکلات قابلتوجهی مواجه میشود، که بهویژه به دلیل عدم استقلال از مدت زمان ماندگاری الزامات در گرههای مختلف مدلهای سیستمهای شبکه با رشتههای غیر استاندارد ایجاد میشود. بنابراین، برای مثال، با یک فرض نسبتاً واقع بینانه که طول نیاز در طول انتقال آن از طریق گرههای شبکه ثابت میماند، لازم است مسیر هر نیاز را ردیابی کنیم، که محاسبه تحلیلی مشخصه را غیرممکن میکند. شبکه با تعداد گره های M> 2.
تجزیه و تحلیل کارهای اختصاص داده شده به مطالعه یا محاسبه مدلهای غیرمارکوویی نشان میدهد که راهحلها، به عنوان یک قاعده، بهصورت الگوریتمی با محاسبات عددی پیچیده با استفاده از تبدیلهای Laplace-Stieltjes بهدست میآیند، به صورت برنامهریزی اجرا میشوند، بسیار پر زحمت هستند، یا دارای خطاهای قابل توجهی هستند. در ارزیابی شاخص های عملکرد سیستم های اطلاعاتی (IS) در میانه و بار سنگین. بنابراین، برای مدل سازی سمو،از کلاس ضربی ها، از روش های تقریبی استفاده کنید.
تحلیل تطبیقیروش های مدل سازی تقریبی Semoو مثالهای ارائه شده در این مقاله نشان میدهد که استفاده از روشهای تقریبی برای محاسبه QMS با دقت بسیار ضروری است، به طوری که هنگام محاسبه QMS خاص، در فرآیند حل مسائل کاربردی مختلف، انجام تحقیقات به منظور ارزیابی دقت و حساسیت ضروری به نظر میرسد. از روش مورد استفاده، و همچنین انجام آزمایشی بر روی شبیه سازی مدل سازی QEM اولیه برای مجموعه ای به اندازه کافی بزرگ از مقادیر پارامترهای متغیر.
روش های تحلیلیمحاسبه ویژگی های IS، به عنوان یک قاعده، بر اساس تجزیه و تحلیل QEMO های نمایی است. با استفاده از این دستگاه ریاضی می توان مدل های تحلیلی را برای حل به دست آورد دامنه ی وسیعمشکلات تحقیق سیستمی CEMO، اول از همه، مجموعه ای از سیستم های صف به هم پیوسته است. بنابراین لازم است ویژگی های اصلی این سیستم ها را یادآوری کنیم.
شبکه صفمجموعه ای از اعداد متناهی است نگرههای سرویسدهنده، که در آن درخواستها در گردش هستند و مطابق با ماتریس مسیریابی از یک گره به گره دیگر منتقل میشوند. یک گره همیشه یک QS باز است (علاوه بر این، QS می تواند از هر کلاسی باشد). در عین حال فردی CMOنمایش بخش های مستقل عملکردی یک سیستم واقعی، پیوندهای بین CMO- ساختار سیستم، و الزامات در گردش از طریق سمو،- اجزای جریان مواد (پیام ها (بسته ها) در یک شبکه ارتباطی، وظایف در سیستم های چند پردازنده، کانتینرهای جریان محموله و غیره).
برای یک نمایش بصری Semoاز نموداری استفاده می شود که رئوس آن (گره ها) با فردی مطابقت دارد CMOو کمان ها نشان دهنده ارتباط بین گره ها هستند.
انتقال برنامه ها بین گره ها فوراً مطابق با احتمالات انتقال اتفاق می افتد , p ij- احتمال اینکه برنامه پس از سرویس در گره منبرو به گره j. به طور طبیعی، اگر گره ها به طور مستقیم به یکدیگر متصل نباشند، پس p ij= 0. اگر از من-گره ام تنها به یک گره منتقل می شود j، سپس p ij= 1.
Semoبر اساس چندین معیار طبقه بندی شده است (شکل 4).
شبکه نامیده می شود خطی، اگر شدت جریان درخواست ها در گره ها توسط یک رابطه خطی به هم مرتبط باشد.
ل j= a ijل من,
جایی که a ij- ضریب تناسب یا نسبت به منبع
ل j= a jل 0 ,.
ضریب الف jضریب انتقال نامیده می شود و نسبت برنامه های دریافتی را مشخص می کند j-گره ام از منبع درخواست ها، یا - میانگین تعداد عبور درخواست از طریق این گره در طول زمانی که درخواست در شبکه بوده است.
اگر شدت جریان درخواست ها در گره های شبکه توسط یک وابستگی غیر خطی به هم متصل شوند (به عنوان مثال، ، سپس شبکه فراخوانی می شود غیر خطی..
اگر درخواست ها از بین نرود و در آن تکثیر نشوند، شبکه همیشه خطی است.
مدار بازشبکه، شبکهای باز است که در آن درخواستها از محیط خارجی میآیند و شبکه را پس از سرویس به محیط خارجی ترک میکنند. به عبارت دیگر، ویژگی حلقه باز Semo(RSeMO) حضور یک یا چند مستقل است منابع خارجی، که بدون در نظر گرفتن تعداد ادعاهای موجود در شبکه، ادعاهایی را ایجاد می کند که وارد شبکه می شوند. در هر نقطه از زمان در RSEMOممکن است تعداد دلخواه برنامه (از 0 تا ¥) وجود داشته باشد.
برنج. 4. طبقه بندی شبکه های صف
AT QSMO بسته (ZSMO)تعداد ثابتی از برنامه ها در گردش هستند و هیچ منبع مستقل خارجی وجود ندارد. بر اساس ملاحظات فیزیکی، ZSEMО قوس بیرونی انتخاب می شود که روی آن شبه صفرنقطه ای نسبت به آن که زمان را می توان اندازه گیری کرد.
ترکیب شدهشبکه شبکه ای است که در آن تعداد معینبرنامه ها و برنامه هایی وجود دارد که از منابع مستقل خارجی می آیند.
AT همگنشبکه ها ادعاهای یک طبقه را پخش می کنند. و بالعکس، در ناهمگوندر یک شبکه، ادعاهای چند کلاس ممکن است وجود داشته باشد. برنامه های کاربردی برای کلاس های مختلفاگر حداقل در یکی از ویژگی های زیر متفاوت باشند:
قانون توزیع مدت زمان سرویس در گره ها؛
اولویت های؛
مسیرها (مسیرهای حرکت برنامه های کاربردی در شبکه).
AT نماییشبکههای مدت زمان سرویس در همه گرهها طبق قانون نمایی توزیع میشوند و جریانهای ورودی به شبکه باز سادهترین (پواسون) هستند. در تمام موارد دیگر، شبکه است غیر نمایی
اگر حداقل یک گره خدمات اولویت را ارائه دهد، این است - اولویتخالص. اولویت ویژگی است که ترتیب خدمات را تعیین می کند. اگر درخواست ها در گره ها به ترتیبی که می رسند سرویس دهی شوند، چنین شبکه ای بدون اولویت
بنابراین، ما نمایی می نامیم Semoکه شرایط را برآورده می کند:
جریان های ورودی Semoپواسون؛
در همه N SMOزمان خدمات برای درخواست ها است تابع نماییتوزیعهای احتمال و برنامهها به ترتیب ورود ارائه میشوند.
انتقال برنامه از خروجی من-امین CMO در ورودی j-th یک رویداد تصادفی مستقل با احتمال است p ij ; p i0- احتمال خروج برنامه از CeMO.
اگر مشتریان وارد شبکه شده و از آن خارج شوند، شبکه باز نامیده می شود. اگر مشتریان وارد شبکه نشوند و از آن خارج نشوند، شبکه بسته نامیده می شود. تعداد درخواست ها در یک شبکه بسته ثابت است.