Operatsion tizimlarga kirish
Salom, Xabr! Men sizning e'tiboringizga bir qator maqolalar-tarjimalarni taqdim etmoqchiman, mening fikrimcha, qiziqarli bo'lgan adabiyot - OSTEP. Ushbu material unix-ga o'xshash operatsion tizimlarning ishini, ya'ni zamonaviy OTni tashkil etuvchi jarayonlar, turli rejalashtiruvchilar, xotira va shunga o'xshash boshqa komponentlar bilan ishlashni chuqur o'rganadi. Bu yerda barcha materiallarning asl nusxasini ko'rishingiz mumkin . E'tibor bering, tarjima noprofessional tarzda qilingan (juda erkin), lekin men umumiy ma'noni saqlab qoldim deb umid qilaman.
Ushbu mavzu bo'yicha laboratoriya ishlarini bu erda topishingiz mumkin:
Boshqa qismlar:
Siz mening kanalimni ham ko'rishingiz mumkin =)
Rejalashtiruvchiga kirish
Muammoning mohiyati: rejalashtirish siyosatini qanday ishlab chiqish kerak
Asosiy rejalashtirish siyosati asoslari qanday ishlab chiqilishi kerak? Asosiy taxminlar qanday bo'lishi kerak? Qaysi ko'rsatkichlar muhim? Ilk hisoblash tizimlarida qanday asosiy texnikalar ishlatilgan?
Ish yukining taxminlari
Mumkin bo'lgan siyosatlarni muhokama qilishdan oldin, keling, tizimda ishlayotgan jarayonlar haqida bir nechta soddalashtiruvchi fikrlarni qilaylik, ular birgalikda deyiladi. ish yuki. Ish yukini aniqlash siyosatni qurishning muhim qismidir va ish yuki haqida qanchalik ko'p bilsangiz, siyosat yozishingiz mumkin.
Keling, tizimda ishlaydigan, ba'zan ham chaqirilgan jarayonlar haqida quyidagi taxminlarni qilaylik ish o'rinlari (vazifalar). Bu taxminlarning deyarli barchasi real emas, balki fikrni rivojlantirish uchun zarurdir.
- Har bir vazifa bir xil vaqt davomida ishlaydi,
- Barcha vazifalar bir vaqtning o'zida o'rnatiladi,
- Belgilangan vazifa bajarilgunga qadar ishlaydi,
- Barcha vazifalar faqat protsessordan foydalanadi,
- Har bir vazifani bajarish vaqti ma'lum.
Rejalashtiruvchi ko'rsatkichlar
Yuk haqida ba'zi taxminlarga qo'shimcha ravishda, turli rejalashtirish siyosatlarini taqqoslash uchun yana bir vosita kerak: rejalashtiruvchi ko'rsatkichlari. Ko'rsatkich shunchaki biror narsaning o'lchovidir. Rejalashtiruvchilarni solishtirish uchun ishlatilishi mumkin bo'lgan bir qator ko'rsatkichlar mavjud.
Misol uchun, biz nomli ko'rsatkichdan foydalanamiz aylanish vaqti (aylanish vaqti). Vazifani bajarish vaqti vazifani bajarish vaqti va tizimdagi topshiriqning kelish vaqti o'rtasidagi farq sifatida aniqlanadi.
Tturnaround=Tugallash—Tarrival
Biz barcha vazifalar bir vaqtning o'zida kelgan deb taxmin qilganimiz uchun Ta=0 va shuning uchun Tt=Tc. Yuqoridagi taxminlarni o'zgartirganimizda, bu qiymat tabiiy ravishda o'zgaradi.
Boshqa ko'rsatkich - adolatlilik (adolat, halollik). Rejalashtirishda mahsuldorlik va adolat ko'pincha qarama-qarshi xususiyatlardir. Misol uchun, rejalashtiruvchi ishlashni optimallashtirishi mumkin, ammo boshqa vazifalar bajarilishini kutish evaziga adolatni pasaytiradi.
BIRINCHI KIRISH BIRINCHI (FIFO)
Biz amalga oshirishimiz mumkin bo'lgan eng asosiy algoritm FIFO yoki deb ataladi birinchi kelgan (kirish), birinchi xizmat ko'rsatish (chiqish). Ushbu algoritm bir nechta afzalliklarga ega: uni amalga oshirish juda oson va u bizning barcha taxminlarimizga mos keladi va ishni juda yaxshi bajaradi.
Keling, oddiy misolni ko'rib chiqaylik. Aytaylik, bir vaqtning o'zida 3 ta vazifa qo'yildi. Ammo, faraz qilaylik, A topshirig'i boshqalarga qaraganda bir oz oldinroq keldi, shuning uchun u bajarilish ro'yxatida boshqalarga qaraganda ertaroq paydo bo'ladi, xuddi C ga nisbatan B kabi. Faraz qilaylik, ularning har biri 10 soniya davomida bajariladi. Bu holda bu vazifalarni bajarish uchun o'rtacha vaqt qancha bo'ladi?
Qiymatlarni sanash orqali - 10+20+30 va 3 ga bo'linib, biz o'rtacha dasturni bajarish vaqtini 20 soniyaga tenglashtiramiz.
Endi taxminlarimizni o'zgartirishga harakat qilaylik. Xususan, 1-faraz va shuning uchun biz endi har bir vazifani bajarish uchun bir xil vaqtni oladi deb hisoblamaymiz. FIFO bu safar qanday ishlaydi?
Ma'lum bo'lishicha, turli vazifalarni bajarish vaqtlari FIFO algoritmining unumdorligiga o'ta salbiy ta'sir ko'rsatadi. Faraz qilaylik, A topshirig'ini bajarish uchun 100 soniya kerak bo'ladi, B va C esa har biri 10 soniyani oladi.
Rasmdan ko'rinib turibdiki, tizim uchun o'rtacha vaqt (100+110+120)/3=110 bo'ladi. Bu effekt deyiladi konvoy effekti, resursning ba'zi qisqa muddatli iste'molchilari og'ir iste'molchidan keyin navbatda turganda. Bu xuddi oziq-ovqat do‘konidagi navbatga o‘xshab, oldingizda to‘la arava bilan xaridor turgandek. Muammoning eng yaxshi yechimi - kassani o'zgartirish yoki dam olish va chuqur nafas olishga harakat qilishdir.
Eng qisqa ish birinchi
Og'ir vaznli jarayonlar bilan shunga o'xshash vaziyatni qandaydir tarzda hal qilish mumkinmi? Albatta. Rejalashtirishning yana bir turi deyiladiEng qisqa ish birinchi (SJF). Uning algoritmi ham juda ibtidoiy - nomidan ko'rinib turibdiki, eng qisqa vazifalar birinchi navbatda, birin-ketin ishga tushiriladi.
Ushbu misolda bir xil jarayonlarni bajarish natijasi dasturning o'rtacha ishlash vaqtining yaxshilanishi bo'ladi va u teng bo'ladi. 50 o'rniga 110, bu deyarli 2 barobar yaxshi.
Shunday qilib, barcha vazifalar bir vaqtning o'zida keladi degan taxmin uchun SJF algoritmi eng maqbul algoritm bo'lib tuyuladi. Biroq, bizning taxminlarimiz haligacha real ko'rinmaydi. Bu safar biz 2-taxminni o'zgartiramiz va bu safar vazifalar bir vaqtning o'zida emas, balki istalgan vaqtda mavjud bo'lishi mumkinligini tasavvur qiling. Bu qanday muammolarga olib kelishi mumkin?
Tasavvur qilaylik, birinchi navbatda A (100c) topshiriq keladi va bajarila boshlaydi. t=10 da B va C topshiriqlari keladi, ularning har biriga 10 soniya vaqt ketadi. Shunday qilib, o'rtacha bajarilish vaqti (100+(110-10)+(120-10))3 = 103. Buni yaxshilash uchun rejalashtiruvchi nima qilishi mumkin?
Birinchi yakunlash uchun eng qisqa vaqt (STCF)
Vaziyatni yaxshilash uchun biz dastur ishga tushirilgani va tugaguniga qadar ishlaydi degan 3-taxmindan voz kechamiz. Bundan tashqari, bizga apparat yordami kerak bo'ladi va siz taxmin qilganingizdek, biz foydalanamiz taymer ishlaydigan vazifani to'xtatish va kontekstni almashtirish. Shunday qilib, rejalashtiruvchi B, C vazifalari kelgan vaqtda nimadir qilishi mumkin - A topshirig'ini bajarishni to'xtatib, B va C vazifalarni qayta ishlashga qo'yadi va ular tugagandan so'ng A jarayonini bajarishni davom ettiradi. Bunday rejalashtiruvchi deyiladi. STCFyoki Oldindan oldingi ish.
Ushbu rejalashtiruvchining natijasi quyidagi natija bo'ladi: ((120-0)+(20-10)+(30-10))/3=50. Shunday qilib, bunday rejalashtiruvchi bizning vazifalarimiz uchun yanada maqbulroq bo'ladi.
Metrik javob vaqti
Shunday qilib, agar biz vazifalarning ishlash vaqtini bilsak va bu vazifalar faqat protsessordan foydalanishini bilsak, STCF eng yaxshi yechim bo'ladi. Va bir marta, dastlabki davrlarda bu algoritmlar juda yaxshi ishlagan. Biroq, foydalanuvchi ko'p vaqtini terminalda o'tkazadi va samarali interaktiv tajribani kutadi. Shunday qilib, yangi ko'rsatkich paydo bo'ldi - javob vaqti (javob).
Javob vaqti quyidagicha hisoblanadi:
Tresponse=Tfirstrun-Tarrival
Shunday qilib, oldingi misol uchun javob vaqti quyidagicha bo'ladi: A=0, B=0, C=10 (abg=3,33).
Va ma'lum bo'lishicha, STCF algoritmi bir vaqtning o'zida 3 ta vazifa keladigan vaziyatda unchalik yaxshi emas - kichik vazifalar to'liq bajarilguncha kutish kerak bo'ladi. Shunday qilib, algoritm qayta ishlash vaqti ko'rsatkichi uchun yaxshi, lekin interaktivlik ko'rsatkichi uchun yomon. Tasavvur qiling-a, agar siz terminalda o'tirgan bo'lsangiz, muharrirga belgilar kiritishga harakat qilsangiz va 10 soniyadan ko'proq kutishingizga to'g'ri keladi, chunki protsessorni boshqa vazifa egallagan. Bu juda yoqimli emas.
Shunday qilib, biz yana bir muammoga duch keldik - javob vaqtiga sezgir bo'lgan rejalashtiruvchini qanday qurishimiz mumkin?
Dumaloq Robin
Ushbu muammoni hal qilish uchun algoritm ishlab chiqilgan Dumaloq Robin (RR). Asosiy g'oya juda oddiy: vazifalarni bajarilgunga qadar bajarish o'rniga, biz vazifani ma'lum vaqt oralig'ida (vaqt tilim deb ataladi) bajaramiz va keyin navbatdan boshqa vazifaga o'tamiz. Algoritm o'z ishini barcha vazifalar bajarilgunga qadar takrorlaydi. Bunday holda, dasturning ishlash vaqti bir necha marta bo'lishi kerak, shundan so'ng taymer jarayonni to'xtatadi. Misol uchun, agar taymer jarayonni har x=10ms da to'xtatsa, u holda jarayonni bajarish oynasining o'lchami 10 ga karrali va 10,20 yoki x*10 bo'lishi kerak.
Bir misolni ko'rib chiqaylik: ABC vazifalari bir vaqtning o'zida tizimga keladi va ularning har biri 5 soniya davomida ishlashni xohlaydi. SJF algoritmi har bir vazifani boshqasini boshlashdan oldin yakunlaydi. Aksincha, ishga tushirish oynasi = 1s bo'lgan RR algoritmi quyidagi vazifalarni bajaradi (4.3-rasm):
(SJF yana (javob vaqti uchun yomon)
(Raund Robin (javob vaqti uchun yaxshi)
RR algoritmi uchun o'rtacha javob vaqti (0+1+2)/3=1, SJF uchun (0+5+10)/3=5.
Vaqt oynasi RR uchun juda muhim parametr, deb taxmin qilish mantiqan to'g'ri, u qanchalik kichik bo'lsa, javob vaqti shunchalik yuqori bo'ladi. Biroq, uni juda kichik qilib qo'ymaslik kerak, chunki kontekstni almashtirish vaqti ham umumiy ishlashda rol o'ynaydi. Shunday qilib, ijro oynasi vaqtini tanlash OS arxitektori tomonidan belgilanadi va unda bajarilishi rejalashtirilgan vazifalarga bog'liq. Kontekstni almashtirish vaqtni behuda sarflaydigan yagona xizmat operatsiyasi emas - ishlaydigan dastur ko'plab boshqa narsalarda, masalan, turli xil keshlarda ishlaydi va har bir kalit bilan ushbu muhitni saqlash va tiklash kerak, bu ham ko'p vaqt talab qilishi mumkin. vaqt.
Agar biz faqat javob vaqti ko'rsatkichi haqida gapiradigan bo'lsak, RR ajoyib rejalashtiruvchidir. Ammo vazifani bajarish vaqti ko'rsatkichi ushbu algoritm bilan qanday ishlaydi? Yuqoridagi misolni ko'rib chiqing, A, B, C = 5s ish vaqti va bir vaqtning o'zida kelganda. Vazifa A 13 da, B 14 da, C 15 soniyada tugaydi va o'rtacha ishlash vaqti 14 soniyani tashkil qiladi. Shunday qilib, RR aylanma ko'rsatkichi uchun eng yomon algoritmdir.
Umuman olganda, RR tipidagi har qanday algoritm adolatli; u CPU vaqtini barcha jarayonlar o'rtasida teng taqsimlaydi. Shunday qilib, bu ko'rsatkichlar doimo bir-biriga zid keladi.
Shunday qilib, bizda bir nechta qarama-qarshi algoritmlar mavjud va bir vaqtning o'zida hali ham bir nechta taxminlar mavjud - vazifa vaqti ma'lum va vazifa faqat protsessordan foydalanadi.
I/U bilan aralashtirish
Avvalo, jarayon faqat protsessordan foydalanadi degan 4-taxozni olib tashlaymiz; tabiiyki, bunday emas va jarayonlar boshqa jihozlarga kirishi mumkin.
Har qanday jarayon kiritish-chiqarish operatsiyasini talab qilgan paytda, jarayon bloklangan holatga kiradi va kirish/chiqarish tugashini kutadi. Agar kirish/chiqarish qattiq diskka yuborilsa, bunday operatsiya bir necha milodiy yoki undan ko'proq vaqtni olishi mumkin va protsessor ayni paytda ishlamay qoladi. Bu vaqt ichida rejalashtiruvchi protsessorni boshqa har qanday jarayon bilan band qilishi mumkin. Reja tuzuvchi qabul qilishi kerak bo'lgan navbatdagi qaror bu jarayon qachon kiritish-chiqarishni yakunlashidir. Bu sodir bo'lganda, uzilish sodir bo'ladi va OT I/U ni chaqirgan jarayonni tayyor holatga keltiradi.
Keling, bir nechta muammolarning misolini ko'rib chiqaylik. Ularning har biri 50ms CPU vaqtini talab qiladi. Biroq, birinchisi har 10 msda kirish/chiqarishga kirishadi (bu ham har 10 msda bajariladi). Va B jarayoni oddiygina kiritish-chiqarishsiz 50 ms protsessordan foydalanadi.
Ushbu misolda biz STCF rejalashtiruvchisidan foydalanamiz. Agar A kabi jarayon ishga tushirilsa, rejalashtiruvchi o'zini qanday tutadi? U quyidagilarni bajaradi: avval u A jarayonini to'liq ishlab chiqadi, keyin esa B jarayonini ishlab chiqadi.
Ushbu muammoni hal qilishning an'anaviy yondashuvi A jarayonining har bir 10 ms kichik vazifasini alohida vazifa sifatida ko'rib chiqishdir. Shunday qilib, STJF algoritmidan boshlanganda, 50 ms vazifa va 10 ms vazifa o'rtasidagi tanlov aniq. Keyin, A kichik vazifa tugagach, B va I/U jarayoni boshlanadi. Kirish-chiqarish tugallangandan so'ng, B jarayoni o'rniga 10 ms lik A jarayonini qaytadan boshlash odatiy hol bo'ladi. Shu tarzda, bir-biriga o'xshashlikni amalga oshirish mumkin, bunda protsessor boshqa jarayon tomonidan ishlatiladi, birinchisi esa kutilayotgan vaqtda. I/U. Natijada, tizimdan yaxshiroq foydalaniladi - interaktiv jarayonlar kiritish-chiqarishni kutayotgan paytda, protsessorda boshqa jarayonlarni bajarish mumkin.
Oracle endi yo'q
Endi vazifaning bajarilish vaqti ma'lum degan taxmindan xalos bo'lishga harakat qilaylik. Bu, odatda, butun ro'yxatdagi eng yomon va eng haqiqiy bo'lmagan taxmindir. Aslida, o'rtacha oddiy OTda OTning o'zi odatda vazifalarni bajarish vaqti haqida juda kam biladi, shuning uchun qanday qilib vazifani bajarish uchun qancha vaqt ketishini bilmasdan rejalashtiruvchini qurish mumkin? Ehtimol, biz ushbu muammoni hal qilish uchun ba'zi RR tamoyillaridan foydalanishimiz mumkinmi?
Xulosa
Biz vazifalarni rejalashtirishning asosiy g'oyalarini ko'rib chiqdik va rejalashtiruvchilarning 2 oilasini ko'rib chiqdik. Birinchisi, birinchi navbatda, eng qisqa vazifani boshlaydi va shu bilan ishlash vaqtini oshiradi, ikkinchisi esa barcha vazifalar o'rtasida teng ravishda yirtilib, javob vaqtini oshiradi. Boshqa oilaning algoritmlari yaxshi bo'lsa, ikkala algoritm ham yomon. Biz, shuningdek, protsessor va kiritish/chiqarishdan qanday qilib parallel foydalanish unumdorlikni oshirishi mumkinligini ko'rib chiqdik, ammo OS ravshanligi bilan bog'liq muammoni hal qilmadik. Va keyingi darsda biz yaqin o'tmishga qaraydigan va kelajakni bashorat qilishga harakat qiladigan rejalashtiruvchini ko'rib chiqamiz. Va bu ko'p darajali qayta aloqa navbati deb ataladi.
Manba: www.habr.com