Translated from Azerbaijani to Uzbek

Little teoremasidan qanday foydalanish kerak

M atematikada ko'pincha haqiqiy tushunchaga ega bo'lish uchun dalillarni o'rganish kerak. Bu aynan shunday. Littla teoremasi shunchalik yaxshiki, men bu yerga isbotning eskizini keltiraman. Kiruvchi trafik funksiya bilan tavsiflanadi - o'sha paytda tizimga kirgan so'rovlar soni . Xuddi shunday - o'sha paytda tizimdan chiqqan so'rovlar soni . So'rovning kirish (chiqish) lahzasi oxirgi baytni olish (o'tkazish) lahzasi hisoblanadi. Chegara tizimlari faqat shu vaqt momentlari bilan belgilanadi, shuning uchun teorema keng qo'llaniladi. Agar siz ushbu funktsiyalarning grafiklarini bitta o'qda chizsangiz, buni ko'rish oson - bu hozirgi vaqtda tizimdagi so'rovlar soni t, a - n-go so'roviga javob berish vaqti.

Teorema rasmiy ediisbotladifaqat 1961 yilda, garchi munosabatlarning o'zi bundan ancha oldin edi.

Aslida, agar ichidagi so'rovlar tizimini qayta tashkil qilish mumkin bo'lsa, bu biroz qiyinroq bo'ladi, shuning uchun biz bu sodir bo'lmasligini hisoblaymiz. Garchi teorema to'g'ri va bu holatda ham. Endi biz grafiklar orasidagi maydonni hisoblaymiz. Bu ikki usulda amalga oshirilishi mumkin. Birinchi navbatda, ustunlarda - odatda integral deb hisoblanadi. Bunday holda, pastki integral ifoda bo'laklardagi navbatning kattaligi ekanligi ma'lum bo'ladi. Ikkinchidan, satr bo'yicha - barcha so'rovlarning kechikish vaqtini qo'yish kifoya. Ikkala hisob-kitob ham bir xil maydonni berishi aniq, shuning uchun tengdir. Agar ushbu kapitalning ikkala qismi biz hududni ko'rib chiqqan Dt vaqtini bo'lsa, chap tomonda biz navbatning o'rtasida bo'lamiz. (o'rtacha ta'rifi bo'yicha). Haqiqat biroz qiyinroq. So'rovlar sonini N va keyin N so'rovlar sonini qo'shish kerak, keyin biz olamiz

Agar siz etarli darajada katta Dt yoki ishg'olning bir davrini hisobga olsangiz, unda savollar chekkalarda tasvirga olinadi va teorema isbotlangan deb hisoblanishi mumkin.

Shuni aytish kerakki, bizning dalillarimizda biz hech qanday ehtimollik taqsimotidan foydalanmadik. Aslida, Little teoremasi deterministik qonundir! Bunday qonunlar ommaviy xizmat amaliyot qonuni nazariyasida deyiladi. Ular tizimning istalgan qismiga va barcha mumkin bo'lgan tasodifiy o'zgaruvchilarning har qanday taqsimotiga qo'llanilishi mumkin. Ushbu qonunlar tarmoqlardagi ma'nolarni tahlil qilish uchun muvaffaqiyatli ishlatilishi mumkin bo'lgan konstruktorni tashkil qiladi. Kamchiliklari shundaki, ularning barchasi faqat o'rta sinfga nisbatan qo'llaniladi va tarqatish haqida hech qanday ma'lumot bermaydi.

Savolga qaytadigan bo'lsak, nima uchun Littla teoremasini baytlarga qo'llamaslik kerak va endi ular bo'laklar bilan emas, balki baytlar bilan o'lchanadi. Keyin, shunga o'xshash bahs yuritib, biz joy olamiz g'alati narsa - baytlarning umumiy soniga bo'lingan kvadrat. Bu oldindan mavjud bo'lgan soniya, lekin bu o'rtacha kechikish kabi narsa, bu erda katta hajmdagi so'rovlar kattaroq og'irlikni oladi. Bu buyuklikni baytning o'rtacha kechikishi bilan atash mumkin - umuman olganda, mantiqan, chunki biz baytdagi qismlarni almashtirdik - lekin so'rovning kechikishi bilan emas.

Littla teoremasi shuni ko'rsatadiki, berilgan so'rovlar oqimida javob vaqti va tizimdagi so'rovlar soni proportsionaldir. Agar barcha so'rovlar bir xil ko'rinadigan bo'lsa, unda o'rtacha javob vaqtini kuchni oshirib bo'lmaydi. Agar so'rovlar hajmini oldindan bilsak, ular orasidagi maydonni qisqartirish uchun ularni ichkarida qayta tashkil etishga harakat qilishimiz mumkin va va shuning uchun tizimning o'rtacha javob vaqti. Ushbu fikrni davom ettirib, siz algoritmlarni isbotlashingiz mumkinEng qisqa ishlov berish vaqtiva Eng qisqa qolgan ishlov berish vaqti bitta server uchun o'zgartirish imkoniyatisiz va shunga mos ravishda u bilan birga minimal o'rtacha javob vaqtini beradi. Ammo yon ta'siri bor - katta so'rovlarni cheksiz qayta ishlash mumkin emas. Ushbu hodisa "ochlik" deb nomlanadi va adolatni rejalashtirish tushunchasi bilan chambarchas bog'liq bo'lib, bu haqda oldingi postdan bilib olishingiz mumkin.Rejalashtirish: afsonalar va haqiqat.

Littla qonunini tushunish bilan bog'liq yana bir umumiy tuzoq bor. Foydalanuvchi so'rovlariga xizmat ko'rsatadigan yagona tarmoqli server mavjud. Keling, biz o'lchaganimizdek L - bu serverga o'z navbatida so'rovlarning o'rtacha soni va S - bitta so'rov serverining o'rtacha xizmat qilish vaqti. Endi yangi kiruvchi so'rovni ko'rib chiqaylik. O'rtada u o'zi oldida L so'rovlarini ko'radi. Ularning har birining xizmati o'rtacha S soniyada ketadi. Ma'lum bo'lishicha, kutishning o'rtacha vaqti . Ammo teorema shuni ko'rsatadi . Agar biz iboralarni tenglashtirsak, unda biz bema'nilikni ko'ramiz: . Ushbu munozarada nima bo'lmaydi?

Ko'zni tortadigan birinchi narsa: teoremaga javob berish vaqti S ga bog'liq emas. Aslida, nihoyat, bu bog'liq. Navbatning o'rtacha uzunligi allaqachon buni o'rgatadi: server qanchalik tez bo'lsa - navbat shunchalik uzoqroq bo'ladi va javob vaqti qisqaradi.

1. 
   Biz navbatlar abadiy nusxalanmaydigan, lekin muntazam ravishda yangilanib turadigan tizimni ko'rib chiqamiz. Bu shuni anglatadiki, serverdan foydalanish 100% dan kam va biz barcha kiruvchi so'rovlarni o'tkazib yuboramiz va bu so'rovlar qanday tezlikda kelgan bo'lsa, va bitta so'rovni qayta ishlash o'rtasida bir soniyadan kamroq vaqt ketadi. soniya, chunki ba'zida biz hech qanday so'rovlarni qayta ishlamaymiz. Haqiqat shundaki, har qanday barqaror ochiq tizimda tarmoqli kengligi yo'qolmasa, serverlar tezligiga bog'liq emas, u faqat kirish oqimi bilan belgilanadi.
   
2. 
   Kiruvchi so'rov tizimda o'rtacha so'rovlar soni bo'yicha paydo bo'ladi degan taxmin har doim ham to'g'ri emas. Qarshi shaxs: kiruvchi so'rovlar vaqti-vaqti bilan kelib turadi va har bir so'rov uchun biz keyingisini ko'rib chiqishga muvaffaq bo'lamiz. Haqiqiy vaqt tizimi uchun odatiy rasm. Kiruvchi so'rov har doim tizimda nol so'rovlarni ko'radi, lekin tizimda, shubhasiz, noldan ko'proq so'rovlar. Agar so'rovlar eng tasodifiy daqiqalarda kelsa, ular haqiqatan ham shunday"So'rovlarning o'rtacha sonini ko'ring".
   
   

3. 
   Biz serverda ba'zi bir ehtimollik bilan "da'vo qilinishi" kerak bo'lgan bitta so'rov bo'lishi mumkinligini o'rganmadik. Umuman olganda, "xizmat" ko'rsatishning o'rtacha vaqti xizmat ko'rsatishning dastlabki vaqtidan farq qiladi, ba'zan esa, qanday qilibparadoksal tarzda, sezilarli darajada ko'proq narsani anglatishi mumkin. Bu savolga biz oxirida qaytamiz, qachonki biz mikroburlarni muhokama qilamiz, bizni kuzatib boring.
   

Shuning uchun Littla teoremasi katta va kichik tizimlarga, o'z navbatida, serverlarga va ishlov berishning yagona oqimlariga qo'llanilishi mumkin. Ammo bu barcha holatlarda so'rovlar odatda u yoki bu tarzda tasniflanadi. Turli xil foydalanuvchilarning so'rovlari, turli xil ustuvorlikdagi so'rovlar, turli joylardan kelgan so'rovlar yoki har xil turdagi so'rovlar. Bunday holda, yig'ilgan ma'lumot sinflari qiziq emas. Ha, aralashgan so'rovlarning o'rtacha soni va ularning barchasi uchun o'rtacha javob vaqti yana mutanosibdir. Ammo ma'lum bir so'rovlar sinfi uchun o'rtacha javob vaqtini bilmoqchi bo'lsak, qanday bo'lish kerak? Ajablanarlisi shundaki, Littla teoremasi ma'lum bir so'rovlar sinfiga nisbatan qo'llanilishi mumkin. Bunday holda, sifatida qabul qilish kerak bu sinf so'rovlarining tezligi, lekin hammasi emas. Sifatida va - tizimning o'rganilayotgan qismida ushbu sinf so'rovlarining soni va paydo bo'lish vaqtining o'rtacha qiymati.