O’zbekiston respublikasi axborot texnologiyalar va kommunikatsiyalarni rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti mustaqil ish mavzu: Operatsion tizimlarda hisoblash jarayoni
Download 62.16 Kb.
|
O’zbekiston respublikasi axborot texnologiyalar va kommunikatsiy
- Bu sahifa navigatsiya:
- Tekshirdi: ________________________________ Toshkent 2020
|
O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALAR VA KOMMUNIKATSIYALARNI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI MUSTAQIL ISH Mavzu: Operatsion tizimlarda hisoblash jarayoni. Bajardi: 023-18 guruh talabasi Sobirova Sadoqat Tekshirdi: ________________________________ Toshkent 2020 Reja:
Hisoblash jarayoni tushunchasi Jarayonlarni rejalashtirish algoritmlari Rejalashtirish mezonlari va algoritm talablari Preventive va olomon bo`lmagan rejalashtirish Rejalashtirish algoritmlari Birinchi kelgan, birinchi xizmat (FCFS) Dumaloq Robin (RR) Eng qisqa-birinchi ish (SJF) Kafolatlangan rejalashtirish Ustuvor rejalashtirish Ko`p darajali navbat Ko`p darajali fikr-mulohazalar navbati Mavzu: Operatsion tizimlarda hisoblash jarayoni. Hisoblash jarayoni tushunchasi Jarayon yoki vazifa yechimdagi dasturdir. Quyidagi jarayonlarni (vazifalarni) misol sifatida ko'rsatish mumkin: foydalanuvchi dasturlari, yordam dasturlari va boshqalar. Jarayonlar har qanday matnni tahrirlash, manba dasturining tarjimasi, uning joylashuvi, bajarilishi bo'lishi mumkin. Bundan tashqari, manba dasturining tarjimasi - bu bitta jarayon, keyingi manba dasturining tarjimasi - bu boshqa jarayondir, chunki tarjimon bu erda dastur modullari birlashmasi sifatida bitta dastur vazifasini bajarsa ham, u ishlayotgan ma'lumotlar boshqacha. OS hisoblash ishlarini bajarish uchun protsessorlarga protsessorlarni ajratadi. Birinchi hisoblash tizimlarida har qanday dastur faqat keyingisi tugagandan keyingina bajarilishi mumkin edi. Barcha quyi tizimlar va qurilmalar markaziy protsessor tomonidan boshqarilgandan beri. Markaziy protsessor hisoblash va ma'lumotlarni kiritish / chiqarish operatsiyalarini ham amalga oshirdi. Mashinaga maxsus tekshirgichlarning kiritilishi, o'z vaqtida olingan ma'lumotlarni chiqarish operatsiyalari va markaziy protsessorda keyingi hisob-kitoblarni birlashtirishga imkon berdi (parallel). Biroq, kiritish-chiqarish jarayonida protsessor hali ham bo'sh edi. Shu munosabat bilan hisoblash tizimining ko'p dasturli (ko'p vazifali) rejimini tashkil etish taklif qilindi. Shunday qilib, bitta dastur tizimida faqat bitta foydalanuvchi jarayoni mavjud. Shu bilan birga, multiprogramma tizimida rejalashtirishni talab qiladigan ko'plab mustaqil jarayonlar bilan resurslarni talab qilish mumkin. Jarayonlarni rejalashtirish - bu ba'zi bir rejalashtirish strategiyasiga muvofiq boshqaruvni ularga o'tkazish orqali CPU raqobatdosh jarayonlar o'rtasida taqsimlanishini boshqarish. Ko'pgina hollarda, jarayon foydalanuvchi vazifasiga mos keladi. Biroq, ba'zi operatsion tizimlar bitta ishni bir vaqtning o'zida ishlaydigan bir nechta turli xil jarayonlarni yaratishga imkon beradi. Bundan tashqari, ba'zi tizimlar bitta dasturni bir nechta mustaqil jarayonlarda bo'lishishga imkon beradi. Operatsion tizim boshqaruvchisi ishini va resurslarni taqsimlash va boshqarishni aks ettiruvchi tizimni boshqarish jarayonlarini boshqa barcha jarayonlardan ajratish kerak: operatsion tizim yadrosi tarkibiga kirmaydigan tizimni qayta ishlash jarayonlari va foydalanuvchi jarayonlari. Aksariyat operatsion tizimlarda tizimni boshqarish jarayonlari uchun resurslar dastlab va aniq qilib ajratilgan. Uning bajarilishi jarayonida jarayon hisoblash tizimining resurslaridan foydalanish uchun raqobatlasha oladi. Jarayon foydalanuvchining ishi boshlanganda yaratiladi va ish tugashi bilan yo'q qilinadi. Uning mavjudligi davomida jarayon uchta holatda bo'lishi mumkin: protsessor buyruqlarini bajarish uchun protsessordan foydalanganda jarayon faol bo'ladi; agar uning bajarilishini faqat kutilgan voqea sodir bo'lgandan keyingina davom ettirish mumkin bo'lsa, jarayon bloklanadi; bloklanmagan yoki faol bo'lmagan jarayonlar tayyor deb nomlanadi. Joriy faol jarayon uni qaytarib bergandan so'ng, boshqaruv ushbu jarayonlarga o'tkaziladi. Eng oddiy holat - har bir jarayonga faqat bitta dastur va bitta foydalanuvchi vazifasi to'g'ri keladi. Uning mavjudligi davomida jarayon bir holatdan ikkinchi holatga qayta-qayta o'tishi mumkin. Buning sababi, operatsion tizimga resurslarni so'rash va OS ta'minlaydigan tizim funktsiyalarini bajarish, boshqa jarayonlar bilan o'zaro aloqalar, taymer, kanallar va kirish / chiqish qurilmalaridan, shuningdek boshqa qurilmalardan uzilish signallarining paydo bo'lishidan kelib chiqadi. Mumkin bo'lgan jarayonning bir holatdan ikkinchisiga o'tishlari holat grafigi ko'rinishida aks etadi. Istalgan vaqtda faqat bitta jarayon faol bo'lishi mumkin (ya'ni, protsessor yordamida). Boshqaruv foydalanuvchi jarayoniga o'tkazilganda, OS oraliq taymerni o'rnatadi. Bu jarayonni boshqarishni o'z zimmasiga oladigan protsessor vaqtining maksimal miqdori bo'lgan vaqtni belgilaydi. Agar bu vaqt tugasa, jarayon faol holatdan tayyor holatga o'tadi. Shundan so'ng, OS rejalashtirish strategiyasiga muvofiq navbatdagi tayyor jarayonni tanlaydi, uni faol holatga o'tkazadi va boshqaruvni unga o'tkazadi. Jarayonni tanlash va boshqaruvni unga o'tkazish dispetcherlik deb ataladi. Ushbu funktsiyani bajaradigan OS qismi dispetcher deb ataladi. Buning ma'nosi shuki, unga berilgan vaqt bo'lagidan to'liq foydalanmagan faol jarayon ba'zi bir voqea sodir bo'lishini kutadi, masalan, kiritish-chiqarish operatsiyasi tugaydi. Bunday holda, faol jarayon bloklanadi va ba'zi yangi jarayonlar faollashadi. Kutilayotgan hodisa ro'y berganda, tegishli blokirovka qilingan jarayon tayyor holatga keltiriladi va operatsiyaga xizmat ko'rsatish uchun yana nomzod bo'lishi mumkin. Voqeani kutish va hodisa ro'y berganligi to'g'risida bildirishnomalar OS xizmati so'rovlari yordamida nazoratchi yordamida yoki uzilishlar yordamida amalga oshiriladi. Jarayon quyidagi holatlardan biri tufayli ish holatidan chiqishi mumkin: jarayon tugaydi, shu bilan birga u boshqaruvchiga murojaat qilish orqali boshqaruvni operatsion tizimga o'tkazadi va tugallanganligi to'g'risida xabar beradi; jarayon ustuvor vazifaning paydo bo'lishi yoki unga ajratilgan vaqt bo'limi tugashi munosabati bilan bajarilishga tayyor holatga keltiriladi; jarayon I / U so'rovi tufayli (uni bajarishni davom ettirishdan oldin bajarilishi kerak) yoki uni hozirda so'ralgan resurs bilan ta'minlay olmasligi sababli bloklanadi. Odatda, jarayon tugashidan oldin ko'p marta tayyor, faol va bloklangan holatda bo'ladi. Buning hisob-kitob natijalariga ta'sir qilmasligi uchun, har safar jarayon o'z faoliyatini yo'qotganda, uning hozirgi holatini saqlab qolish kerak. Jarayon qayta yoqilganda, bu holat tiklanishi kerak. Har bir jarayonning holati to'g'risidagi ma'lumotlar operatsion tizim tomonidan jarayon holati blokida (BPB) saqlanadi. BSP-da jarayonning holati to'g'risida ma'lumotlar mavjud (faol, tayyor yoki bloklangan). Mashina registrlarini va boshqa har xil ma'lumotlarni saqlash uchun ishlatiladigan maydonga ega (masalan, tizim resurslari, foydalanilgan jarayonlar to'g'risida). Dispetcherlik uchun keyingi jarayonni tanlash bir necha usulda amalga oshiriladi. Ularning birinchisida dumaloq deb nomlangan barcha jarayonlar teng deb hisoblanadi. Dispetcher barcha BSP-larni aylanib o'tib, tayyor bo'lgan holatlardan keyingi jarayonni tanlaydi. Har bir chaqirilgan jarayonga bir xil vaqt bo'lagi beriladi. Keyinchalik murakkab usullarda jarayonlar ustuvor yo'nalish bo'yicha yuboriladi. Ba'zi tizimlarda ustuvorliklar foydalanuvchi vazifalarining xususiyatiga qarab oldindan belgilanadi. Bunday tizimlarning vazifasi har bir sinf vazifalari uchun kerakli darajada xizmat ko'rsatishdir. Boshqa tizimlarda operatsion tizim tomonidan ustuvorliklar butun tizim samaradorligini oshirish uchun belgilanishi mumkin. Tizimlarning yuki va ishlashiga qarab ustuvorliklar ham dinamik ravishda o'zgarishi mumkin. Bundan tashqari, ustuvor tizimdan tashqari, turli xil jarayonlar bo'yicha har xil vaqt bo'laklari ajratilishi mumkin. Operatsion tizim jarayonlarni boshqarishi uchun unda barcha kerakli ma'lumotlar bo'lishi kerak. Shu maqsadda har bir jarayon uchun maxsus axborot tuzilmasi o'rnatiladi, bu jarayon deskriptori (vazifa deskriptori) deb nomlanadi. Vazifalarni tavsiflovchi quyidagi ma'lumotlarni o'z ichiga oladi: Jarayon identifikatori (PID - jarayon identifikatori deb ataladi) nazoratchi uchun resurslarni taqdim etishning ba'zi qoidalarini belgilaydigan jarayonning turi (yoki klassi); nazoratchi resurslarni taqdim etadigan jarayonning ustuvorligi. Jarayonlarning bir klassi ichida birinchi navbatda yuqori ustuvor jarayonlarga xizmat ko'rsatiladi; jarayonning qaysi holatida bo'lishini aniqlaydigan holat o'zgaruvchisi (ishga tushirishga tayyor, davom etmoqda, kiritish-chiqarish moslamasini kutmoqda); protsessor registrlarining joriy qiymatlari saqlanadigan xotiraning himoyalangan maydoni (yoki bunday zonaning maydoni), agar jarayon o'z ishini tugatmasdan to'xtatilsa. Ushbu ma'lumot vazifa konteksti deb ataladi; jarayon egalik qiladigan va / yoki undan foydalanish huquqiga ega bo'lgan resurslar to'g'risidagi ma'lumotlar (fayllarni ochish uchun ko'rsatgichlar, tugallanmagan kirish / chiqish operatsiyalari to'g'risida ma'lumotlar va boshqalar); boshqa jarayonlar bilan aloqani tashkil qilish uchun joy (yoki uning manzili); boshlash vaqtining parametrlari (jarayonni faollashtirish kerak bo'lgan vaqt va ushbu protseduraning chastotasi). Ko'p dasturlash g'oyalarini amalga oshirish uchun jarayon kontseptsiyasi kiritildi. Jarayonlar haqida gaplashganda, ular OS o'zlarining izolyatsiyasini saqlab turishini ta'kidlashni istaydilar. Bunday izolyatsiya bir jarayonni boshqasidan himoya qilish uchun zarurdir, chunki ular hisoblash tizimining barcha resurslarini bir-biri bilan raqobatlashadilar. Boshqacha qilib aytganda, OS jarayonlar o'rtasidagi resurslar raqobatida hakamlik vazifasini bajaradi. Shu bilan birga, jarayonlarning o'zida bo'lishi mumkin bo'lgan ichki parallellikdan ham foydalanish maqsadga muvofiqdir. Masalan, dastur tomonidan amalga oshiriladigan ba'zi operatsiyalarni bajarish uchun ancha uzoq CPU foydalanishni talab qilish mumkin. Bunday holda, dastur bilan interaktiv ish olib borishda foydalanuvchi buyurtma qilingan operatsiyani uzoq vaqt kutishga majbur bo'ladi va operatsiya oxirigacha bajarilguniga qadar dasturni boshqarolmaydi (bu holat, masalan, grafik ishlov berishda yuz beradi). Agar bunday uzoq muddatli operatsiyalarni bajaradigan dasturiy ta'minot modellari boshqa kichik jarayonlar bilan parallel ravishda bajariladigan mustaqil sub-jarayonlar sifatida rasmiylashtirilsa, u holda foydalanuvchi bitta dastur (jarayon) doirasida bir nechta operatsiyalarni parallel ravishda bajarish imkoniyatiga ega. Ushbu vazifalar o'zlarining resurslariga ega emas, ular bir xil virtual manzillar maydonida rivojlanadi, ular ushbu jarayon bilan bir xil fayllardan, virtual qurilmalardan va boshqa manbalardan foydalanishi mumkin. Ularga kerak bo'lgan yagona narsa - bu protsessor resursi. Bir protsessorli tizimlarda ushbu vazifalar iplar yoki iplar deb nomlanadi. Multitreading ta'minlaydigan asosiy narsa bu amaliy dasturda bir nechta operatsiyalarni bajarish qobiliyatidir. Ko'p dasturlash operatsion tizimining faoliyati turli jarayonlarda bajariladigan operatsiyalar zanjirlaridan iborat bo'lib, protsessorning bir jarayondan boshqasiga o'tishi bilan birga keladi. Protsessor jarayonni amalga oshirganda, kirish-chiqish moslamasida uzilish paydo bo'lib, bu qurilmadagi operatsiyalar tugaganligini bildiradi. Ishga tushirish jarayoni ishlaydigan jarayonda amalga oshiriladi. Bundan tashqari, operatsion tizim I / U so'rovini boshlagan jarayonni blokdan chiqaradi va rejalashtirish paytida tanlangan to'xtatilgan yoki yangi jarayonni boshlaydi (ochilmagan jarayon rasmda tanlangan). Ko'rib turganingizdek, Kiritish-chiqarish operatsiyasining tugashi to'g'risidagi ma'lumotlarni qayta ishlash natijasida jarayonni ijro holatida o'zgartirish mumkin. Protsessorni bir jarayondan ikkinchisiga to'g'ri almashtirish uchun ishlayotgan jarayonning kontekstini saqlash va protsessor yoqiladigan jarayon kontekstini tiklash kerak. Jarayonlarning sog'lig'ini saqlash / tiklashning ushbu jarayoni kontekstni almashtirish deyiladi. Kontekstni almashtirishga sarflangan vaqt hisoblash tizimi tomonidan foydali ishlarni bajarish uchun ishlatilmaydi va tizim ish faoliyatini kamaytiradigan qo'shimcha xarajatlar hisoblanadi. U har bir mashinada o'zgarib turadi va odatda 1 dan 1000 mikrosaniyagacha bo'ladi. Ijro etish kontseptsiyasini o'z ichiga olgan kengaytirilgan jarayon modeli (bajarilish iplari yoki shunchaki iplar) zamonaviy operatsion tizimlarda qo'shimcha xarajatlarni sezilarli darajada kamaytirishi mumkin. Jarayonlarni rejalashtirish algoritmlari OSda rejalashtirishning ikki turini ajratish odatiy holdir: vazifalarni rejalashtirish va protsessorlarni rejalashtirish. Ishni rejalashtirish uzoq muddatli rejalashtirish jarayoni sifatida ishlaydi. Tizimda yangi jarayonlarning paydo bo'lishi, uning multiprogramlash darajasini, ya'ni unda bir vaqtning o'zida bo'lgan jarayonlar sonini aniqlash uchun javobgardir. Protsessorlarni rejalashtirish jarayonlarni qisqa muddatli rejalashtirish vazifasini bajaradi. Bu, masalan, ishlaydigan jarayon I / U qurilmalariga kirganda yoki ma'lum bir vaqt oralig'i o'tgandan keyin amalga oshiriladi. Shu sababli, qisqa muddatli rejalashtirish juda tez-tez, qoida tariqasida, kamida 100 millisekundada bir marta amalga oshiriladi. Ba'zi hisoblash tizimlarida qisman bajarilgan jarayonni operativ xotiradan diskka vaqtincha olib tashlash va keyinchalik uni bajarish uchun qaytarish uchun ularning ish faoliyatini yaxshilash foydali bo'lishi mumkin. Ushbu protsedura ingliz adabiyotida almashtirish deb nomlanadi. Jarayonlarning qaysi biri va qaysi biri diskka tushirilishi va orqaga qaytarilishi kerakligi jarayonni rejalashtirishning qo'shimcha oraliq darajasi - o'rta muddatli tomonidan belgilanadi. Rejalashtirish mezonlari va algoritm talablari Jarayonlarni rejalashtirishning har bir darajasi uchun juda ko'p turli xil algoritmlarni taklif qilish mumkin. Muayyan algoritmni tanlash hisoblash tizimi tomonidan hal qilinadigan muammolar sinfi va erishilishi kerak bo'lgan maqsadlar bilan belgilanadi. Ushbu maqsadlarga quyidagilar kiradi: - adolat: har bir topshiriqni kafolatlash yoki kompyuter tizimida protsessordan foydalanish vaqtining ma'lum bir qismini qayta ishlash, bir foydalanuvchi jarayoni doimiy ravishda protsessorni ishg'ol qilganda, boshqa foydalanuvchi jarayoni esa aslida ijro etishni boshlamagan holat yuzaga kelishiga yo'l qo'ymaslik uchun; - samaradorlik: protsessorni ish vaqtini 100% egallashga harakat qiling, bajarilishga tayyor jarayonlarni kutayotganda uning bo'sh turishiga yo'l qo'ymang. Haqiqiy hisoblash tizimlarida protsessor yuki 40 foizdan 90 foizgacha; - bajarilishning umumiy vaqtini qisqartirish (burilish vaqti): jarayonning boshlanishi yoki yuklash uchun navbatga vazifani qo'yish va uni yakunlash o'rtasida minimal vaqtni ta'minlash; - kutish vaqtini qisqartirish: tayyor holatdagi jarayonlar va yuklash uchun navbatda turgan ish joylari vaqtini minimallashtirish; - Javob berish vaqtining qisqartirilishi: foydalanuvchi so'roviga javob berish uchun interaktiv tizimlardagi jarayonni minimallashtirish. Belgilangan rejalashtirish maqsadlaridan qat'i nazar, algoritmlarning quyidagi xususiyatlarga ega bo'lishi ham maqsadga muvofiqdir: bashorat qilish mumkin edi. Xuddi shu vazifa taxminan bir vaqtning o'zida bajarilishi kerak. Rejalashtirish algoritmidan foydalanish, masalan, to'rtburchaklar ildizni soniyani yuzdan bir soniyasida bitta ishga tushirish bilan va ikkinchi ishga tushirish bilan bir necha kun ajratib olishga olib kelmasligi kerak; ularning ishi bilan bog'liq minimal xarajatlarga ega edi. Agar protsessordan foydalanish uchun protsessga ajratilgan har 100 millisekundada, qaysi protsessor ixtiyoriga o'tishini aniqlash va kontekstni almashtirish uchun 200 millisekundalar bo'lsa, unda bunday algoritmdan foydalanishga arzimaydi; hisoblash tizimining resurslarini teng ravishda yukladi, kam ishlatiladigan resurslarni egallaydigan jarayonlarga ustunlik berdi; o'lchovga ega edi, ya'ni. ortib borayotgan yuk bilan o'z samaradorligini darhol yo'qotmadi. Masalan, tizimdagi jarayonlar sonini ikki baravar oshirish jarayonlarning umumiy bajarilish vaqtini kattalik tartibiga ko'payishiga olib kelmasligi kerak. Belgilangan maqsadlarga erishish uchun rejalashtirish algoritmlari tizimdagi jarayonlarning har qanday xususiyatlariga, yuklash uchun navbatdagi ishlarga, hisoblash tizimining o'zi holatiga, boshqacha aytganda, rejalashtirish parametrlariga tayanishi kerak. Barcha rejalashtirish parametrlarini ikkita katta guruhga bo'lish mumkin: statik parametrlar va dinamik parametrlar. Hisoblash tizimining ishlashi paytida statik parametrlar o'zgarmaydi, dinamikalar esa, aksincha, doimiy o'zgarishlarga uchraydi. Hisoblash tizimining statik parametrlariga uning resurslarining chegara qiymatlari (operativ xotira hajmi, almashtirish uchun diskdagi maksimal xotira hajmi, ulangan kiritish-chiqarish qurilmalari soni va boshqalar) kiradi. Tizimning dinamik parametrlari hozirgi vaqtda bo'sh resurslar miqdorini tavsiflaydi. Preventiv va olomon bo'lmagan rejalashtirish Rejalashtirish jarayoni operatsion tizimning rejalashtiruvchi deb nomlangan qismi tomonidan amalga oshiriladi. Rejalashtiruvchi quyidagi to'rtta holatda bajarishga tayyor bo'lganlar orasidan yangi jarayonni tanlash to'g'risida qaror qabul qilishi mumkin: 1 jarayon bajarilish holatidan tugash holatiga o'tkazilganda; 2 jarayon ijro holatidan bo'sh holatga o'tkazilganda; 3 jarayon ishga tushirish holatidan tayyor holatga o'tkazilganda (masalan, taymer uzilishidan keyin); 4 jarayon bo'sh holatdan bo'sh holatga o'tkazilganda (I / U tugadi yoki boshqa hodisa yuz berdi). 1 va 2 hollarda, ijro holatida bo'lgan jarayon endi bajarilishi mumkin emas va bajarish uchun har doim yangi jarayon tanlanishi kerak. 3 va 4-holatlarda rejalashtirish amalga oshirilmasligi mumkin, uzilishdan oldin bajarilgan jarayon uzilish qayta ishlangandan keyin ham bajarilishini davom ettirishi mumkin. Agar rejalashtirish faqat 1 va 2 hollarda amalga oshirilsa, oldindan rejalashtirilmagan rejalashtirish amalga oshiriladi. Aks holda, bu oldindan rejalashtirishdir. "Oldindan rejalashtirish" atamasi paydo bo'ldi, chunki uning irodasiga qarshi ishlaydigan jarayon boshqa jarayon tomonidan ijro holatidan chiqarilishi mumkin. Ko'chirmaydigan rejalashtirish, masalan, MS Windows 3.1 va Apple Macintosh OS-da qo'llaniladi. Ushbu rejalashtirish rejimi bilan, protsessor zarur bo'lgan vaqtni oladi. Bunday holda, jarayonlarning almashinuvi faqat bajarilayotgan jarayonning o'zi boshqaruvni uzatishni xohlaganda (Kirish-chiqarish operatsiyasining tugashini kutish yoki ish oxirida) sodir bo'ladi. Ushbu rejalashtirish usulini amalga oshirish nisbatan sodda va juda samarali, chunki u protsessor vaqtining ko'p qismini jarayonlarning o'zi uchun ishlatishga va kontekstni almashtirish narxini minimallashtirishga imkon beradi. Biroq, oldindan rejalashtirilmagan rejalashtirish bilan biron bir sababga ko'ra (masalan, dasturdagi xato tufayli) protsessorni to'liq bosib olish imkoniyati muammosi mavjud bo'lib, boshqaruvni boshqa jarayonga o'tkaza olmaydi. Bunday vaziyatda faqat butun hisoblash tizimini qayta boshlash sizni qutqarishi mumkin. Preventiv rejalashtirish odatda vaqtni taqsimlash tizimlarida qo'llaniladi. Ushbu rejalashtirish rejimida jarayonni bajarish vaqtida istalgan vaqtda to'xtatib qo'yish mumkin. Operatsion tizim ma'lum bir vaqt oralig'idan keyin uzilish signalini yaratish uchun maxsus taymerni o'rnatadi - kvant. Uzilishdan keyin protsessor keyingi jarayonga o'tkaziladi. Vaqtni to'xtatib qo'yish, onlayn foydalanuvchilar uchun jarayonni qabul qilishning maqbul vaqtini ta'minlashga yordam beradi va dastur tsikli tufayli kompyuter tizimining muzlashiga yo'l qo'ymaydi. Rejalashtirish algoritmlari Turli xil maqsadlarga erishish uchun mo'ljallangan va har xil muammolar sinflari uchun samarali bo'lgan har xil rejalashtirish algoritmlarining juda katta to'plami mavjud. Ularning ko'pchiligidan rejalashtirishning bir necha darajalarida foydalanish mumkin. Birinchi kelgan, birinchi xizmat (FCFS) Rejalashtirishning eng oddiy algoritmi bu algoritm bo'lib, u odatda FCFS qisqartmasi bilan uning inglizcha ismining birinchi harflaridan keyin - Birinchi kel, birinchi xizmat (birinchi kelgan, birinchi xizmat) dan keyin belgilanadi. Tasavvur qiling, tayyor jarayonlar navbat bilan tashkil etilgan. Jarayon tayyor bo'lgach, u navbatning oxiriga, yoki aniqrog'i uning tengligiga mos yozuvlar joylashtiriladi. Amalga oshirish uchun yangi jarayonni tanlash navbatning boshidan boshlab uning PCB-ga havolani olib tashlash bilan amalga oshiriladi. Ushbu turdagi navbat FIFO dasturlashda maxsus nomga ega - First In, First Out (birinchi kirish, birinchi chiqish) uchun qisqa. Ushbu jarayonni tanlash algoritmi oldindan belgilanmagan rejalashtirishni amalga oshiradi. O'zining ixtiyorida protsessorga ega bo'lgan jarayon, uni hozirgi CPU portlashi tugaguniga qadar davom etadi. Shundan so'ng, navbat boshlanishidan boshlab ijro etish uchun yangi jarayon tanlanadi. FCFS algoritmining afzalligi - uni amalga oshirishning qulayligi, shu bilan birga uning ko'pgina kamchiliklari mavjud. Quyidagi misolni ko'rib chiqing. Uchta jarayon p0, p1 va p2 tayyor holatda bo'lsin, ular uchun navbatdagi protsessor portlash vaqtlari ma'lum. Ushbu vaqt 1-jadvalda keltirilgan. Ba'zi an'anaviy birliklarda. 1-jadval
Oddiylik uchun, barcha jarayonlar faqat bitta protsessor portlashidan foydalanish bilan cheklanadi, jarayonlar I / U ni amalga oshirmaydi va kontekstni almashtirish vaqtlari ahamiyatsiz deb hisoblanadi. Agar jarayonlar p0, p1, p2 tartibida bajarishga tayyor bo'lgan jarayonlar navbatida joylashgan bo'lsa, unda ularning bajarilish rasmlari 4-rasmda ko'rsatilgandek ko'rinadi. Amalga oshirish uchun birinchi navbatda p0 jarayoni tanlanadi, u protsessorni butun CPU portlashi davomida oladi, ya'ni. vaqtning 13 birligiga. Tugallangandan so'ng, p1 jarayoni bajarilish holatiga o'tkazilib, protsessorni 4 vaqt birligi egallaydi. Nihoyat, p2 jarayoni ishlash imkoniyatini oladi. P0 jarayoni uchun kutish vaqti 0 vaqt birligi, p1 jarayoni uchun - 13 birlik, p2 jarayoni uchun - 13 + 4 = 17 birlik. Shunday qilib, bu holda o'rtacha kutish vaqti (0 + 13 + 17) / 3 = 10 birlik vaqt. P0 jarayoni uchun bajarilishning umumiy vaqti 13 birlik vaqtni tashkil etadi, jarayon uchun p1-13 + 4 = 17 birlik, p2-13 + 4 + 1 = 18 birlik uchun. O'rtacha bajarilish vaqti (13 + 17 + 18) / 3 = 16 vaqt birligiga teng. Agar bir xil jarayonlar p2, p1, p0 tartibida joylashtirilgan bo'lsa, unda ularning bajarilish rasmlari 7-rasmga to'g'ri keladi. P0 jarayonini kutish vaqti 5 birlik, p1 jarayoni uchun - 1 birlik, p2 jarayoni uchun - 0 birlik. O'rtacha kutish vaqti (5 + 1 + 0) / 3 = 2 vaqt birligi bo'ladi. Bu avvalgi holatga qaraganda 5 baravar kam. P0 jarayoni uchun bajarilishning umumiy vaqti 18 birlik vaqtiga teng, p1 jarayoni uchun - 5 birlik, p2 jarayoni uchun - 1 birlik. O'rtacha bajarilish vaqti (18 + 5 + 1) / 3 = 6 birlik vaqtni tashkil etadi, bu jarayonlarning birinchi tartibiga nisbatan deyarli 2,7 baravar kam. Ko'rib turganingizdek, ushbu algoritm uchun kutishning o'rtacha vaqti va o'rtacha umumiy bajarilish vaqti navbatdagi jarayonlarning tartibiga bog'liq. Agar uzoq protsessor portlashi bo'lgan jarayon mavjud bo'lsa, unda uzoq jarayondan so'ng tayyor bo'lgan qisqa jarayonlar ularning bajarilishini boshlash uchun juda uzoq vaqt kutib turadi. Shuning uchun FCFS vaqtni taqsimlash tizimlari uchun amalda qo'llanilmaydi. Interaktiv jarayonlarda o'rtacha javob vaqti juda uzoq. Dumaloq Robin (RR) FCFS algoritmining modifikatsiyasi bu "Dumaloq Robin" ("Dumaloq Robin" - AQShdagi bolalar karuselining bir turi) yoki qisqacha RR deb nomlangan algoritmdir. Aslida, bu xuddi shu algoritm, faqat oldindan rejalashtirish rejimida amalga oshiriladi. Siz tsikl bilan tashkil etilgan tayyor jarayonlarning butun majmuasini tasavvur qilishingiz mumkin - jarayonlar karuselda o'tiradi. Karusel shu tariqa aylanadiki, har bir jarayon protsessor yaqinida kichik vaqt bo'lagi uchun, odatda 10 - 100 millisekundlarda joylashgan (5-rasm). Jarayon protsessor yaqinida bo'lganida, protsessor o'z ixtiyorida bo'ladi va uni bajarish mumkin. Ushbu algoritm oldingisiga o'xshash tarzda, tayyor holatda bo'lgan jarayonlarni FIFO navbati bilan tartibga solish orqali amalga oshiriladi. Rejalashtiruvchi navbatdagi ijro uchun navbatning boshida joylashgan jarayonni tanlaydi va ma'lum bir vaqt kesimidan keyin uzilish hosil qilish uchun taymerni o'rnatadi. Jarayonni amalga oshirishda ikkita variant mavjud: - jarayon talab qiladigan doimiy protsessordan foydalanish vaqti (joriy CPU portlashining qolgan qismi) vaqt bo'lagi davomiyligidan kam yoki unga teng. Keyin jarayon, o'z xohish-irodasi bilan, protsessorni vaqt bo'lagi tugashidan oldin chiqaradi, navbatning boshidanoq bajarish uchun yangi jarayon tanlanadi va taymer yana kvantni sanay boshlaydi. - protsessorning joriy portlash jarayonining qolgan qismi vaqt bo'lagidan kattaroq. Keyinchalik, bu kvant tugagandan so'ng, jarayon taymer tomonidan to'xtatiladi va bajarishga tayyor bo'lgan jarayonlar navbatining oxiriga qo'yiladi va protsessor uning boshida jarayon tomonidan foydalanish uchun ajratiladi. Eng qisqa-birinchi-ish (SJF) FCFS va RR algoritmlarini ko'rib chiqilishidan, ular uchun jarayonlar bajarilish uchun navbatdagi jarayonlarning tartibi qanchalik muhimligi aniq. Agar qisqa vazifalar navbatda uning boshlanishiga yaqinroq bo'lsa, unda ushbu algoritmlarning umumiy ko'rsatkichlari sezilarli darajada oshadi. Agar siz tayyor holatdagi jarayonlar uchun navbatdagi CPU portlash vaqtini bilsangiz, unda jarayonni navbatning boshidan emas, balki protsessor portlashining minimal davomiyligi bilan jarayonni tanlashingiz mumkin. Agar bunday jarayonlar ikki yoki undan ko'p bo'lsa, ulardan birini tanlash uchun bizga allaqachon ma'lum bo'lgan FCFS algoritmidan foydalanish mumkin. Bunday holda vaqtni kvantlash qo'llanilmaydi. Ta'riflangan algoritm birinchi navbatda eng qisqa ish (SJF) deb nomlanadi. SJF qisqa muddatli rejalashtirish algoritmi oldindan yoki oldindan bo'lmasligi mumkin. Preefektiv bo'lmagan SJF rejalashtirish bilan protsessor tanlangan jarayonga hisoblash tizimidagi voqealardan qat'i nazar, kerakli bo'lgan barcha vaqt davomida beriladi. SJF-ni oldindan rejalashtirish tanlangan jarayon ishlayotganda ishga tayyor navbatda (yangi tug'ilgan yoki qulfdan chiqarilgan) yangi jarayonlarning ko'rinishini hisobga oladi. Agar yangi jarayonning protsessor portlashi ishlayotgan protsessorning qolgan portlashidan kam bo'lsa, u holda yangi jarayon oldindan ishlaydigan bo'ladi. SJF algoritmini amalga oshirishdagi asosiy qiyinchilik - bu ishlaydigan protsessorlar uchun keyingi CPU portlashining aniq vaqtini bilish imkonsizligidir. Ommaviy tizimlarda ish bajarilishi kerak bo'lgan protsessor vaqtining miqdori foydalanuvchi tomonidan ish yaratilganda belgilanadi. Ushbu parametr qiymati uzoq muddatli SJF rejalashtirishni amalga oshirish uchun ishlatilishi mumkin. Agar foydalanuvchi kerakli vaqtdan ko'proq vaqtni belgilasa, u natijani kutgandan ko'proq kutadi, chunki vazifa keyinchalik tizimga yuklanadi. Agar u ozroq vaqtni belgilasa, topshiriq oxirigacha hisoblanmasligi mumkin. Shunday qilib, ommaviy tizimlarda protsessor vaqtini baholash muammosining echimi foydalanuvchi elkasiga o'tkaziladi. Qisqa muddatli rejalashtirish bilan siz jarayonning tarixiga asoslanib, faqat keyingi CPU portlashining davomiyligini taxmin qilishingiz mumkin. Kafolatlangan rejalashtirish Foydalanuvchilar kompyuter tizimida interaktiv ishlaganda, rejalashtirish algoritmi qo'llanilishi mumkin, bu har bir foydalanuvchi o'z ixtiyorida protsessor vaqtining bir qismiga ega bo'lishiga kafolat beradi. Barcha foydalanuvchilarni dan gacha raqamlashtiramiz. I raqamiga ega har bir foydalanuvchi uchun biz ikkita qiymatni kiritamiz: --i - bu foydalanuvchining tizimdagi vaqti, yoki boshqacha qilib aytganda, uning mashina bilan aloqa seansining davomiyligi va i - bu sessiya davomida uning barcha jarayonlariga allaqachon ajratilgan protsessorning umumiy vaqti. Foydalanuvchi i / protsessor vaqtini olishi adolatli bo'lar edi. Agar u holda i-chi foydalanuvchi adolatsiz ravishda CPU vaqtidan mahrum bo'ladi. Agar u holda tizim foydalanuvchi i ni aniq qo'llab-quvvatlaydi. Keling, har bir foydalanuvchi jarayoni uchun adolat koeffitsientini hisoblaymiz va biz ushbu nisbatning eng kichik qiymati bilan jarayonga keyingi safar tilimni taqdim etamiz. Taklif etilayotgan algoritm kafolatlangan rejalashtirish algoritmi deb ataladi. Ushbu algoritmning kamchiliklari orasida foydalanuvchi xatti-harakatlarini bashorat qila olmaslik kiradi. Agar biron bir foydalanuvchi ish sessiyasini to'xtatmasdan tushlik qilish va uxlash uchun bir necha soat ketsa, u qaytib kelganida uning jarayonlari asossiz protsessor vaqtini oladi. Ustuvor rejalashtirish SJF va kafolatlangan rejalashtirish algoritmlari - bu ustuvor rejalashtirishning alohida holatlari. Prioritet rejalashtirish bilan har bir jarayonga ma'lum bir raqam qiymati beriladi - bu protsessor unga muvofiq ajratilgan ustuvorlik. Xuddi shu ustuvorlikka ega jarayonlar FCFS tartibida rejalashtirilgan. SJF algoritmi uchun ushbu ustuvorlik keyingi CPU portlashi davomiyligini baholashdir. Ushbu balning qiymati qanchalik past bo'lsa, jarayonning ustuvorligi shuncha yuqori bo'ladi. Kafolatlangan rejalashtirish algoritmi uchun ustuvorlik hisoblangan adolat nisbati hisoblanadi. U qanchalik kichik bo'lsa, jarayon shunchalik ustuvor ahamiyatga ega. Prioritetlashtirish tamoyillari hisoblash tizimining ichki mezonlariga va unga tashqi bo'lgan mezonlarga asoslanishi mumkin. Ichki jarayonlar uning ustuvorligini hisoblash uchun jarayonning turli miqdoriy va sifat xususiyatlaridan foydalanadi. Bu, masalan, protsessordan foydalanish vaqtining ma'lum chegaralari, xotira talablari, ochilgan fayllar soni va ishlatilgan kiritish-chiqarish moslamalari soni, kiritish-chiqarish portlashining o'rtacha davomiyligining protsessor portlashiga nisbati va boshqalar. Tashqi mezonlar jarayonning har qanday maqsadlarga erishishdagi ahamiyati, protsessorning pulli vaqtining narxi va boshqa siyosiy omillar kabi parametrlarga asoslanadi. Prioritet rejalashtirish oldindan yoki oldindan bo'lmasligi mumkin. Oldindan rejalashtirishda tayyor navbatda paydo bo'ladigan yuqori ustuvor jarayon, bajarilayotgan pastroq ustuvor jarayonni oldindan belgilaydi. Preefektiv bo'lmagan rejalashtirish bo'lsa, u shunchaki tayyor jarayonlar navbatining boshlig'iga aylanadi. Afzallikni rejalashtirishdagi asosiy muammo shundaki, agar ustuvorliklarni belgilash va o'zgartirish mexanizmi noto'g'ri tanlangan bo'lsa, past ustuvor jarayonlar abadiy boshlamasligi mumkin. Ikki narsadan biri odatda sodir bo'ladi. Yoki ular hali ham o'zlarining qatl qilinishini kutmoqdalar. Yoki kompyuter tizimini o'chirib qo'yish kerak va ular yo'qoladi (IBM 7094 1973 yilda Massachusets Texnologiya Institutida to'xtaganda, 1967 yilda boshlangan va o'sha paytdan beri bajarilmagan jarayonlar topilgan). Ushbu muammoning echimiga vaqt o'tishi bilan tayyor jarayonning ustuvor qiymatini oshirish orqali erishish mumkin. Ko'p darajali navbat Jarayonlarni turli guruhlarga osongina saralash mumkin bo'lgan tizimlar uchun rejalashtirish algoritmlarining boshqa klassi ishlab chiqilgan. Har bir jarayon guruhi uchun tayyor jarayonlarning alohida navbati yaratiladi. Ushbu navbatlarga belgilangan ustuvorliklar beriladi. Masalan, tizim jarayoni navbatining ustuvorligi foydalanuvchi jarayoni navbatlarining ustuvorligidan yuqori o'rnatiladi. Va talabalar tomonidan boshlanadigan jarayonlar navbatining ustuvorligi o'qituvchilar tomonidan boshlangan jarayonlar navbatiga qaraganda pastroq. Bu shuni anglatadiki, hech bo'lmaganda bitta tayyor tizim jarayoni mavjud bo'lgan taqdirda, biron bir foydalanuvchi jarayoni tanlanmaydi va agar o'qituvchilar bajarilishi uchun biron bir jarayon mavjud bo'lsa, uning ixtiyorida protsessor bo'lmaydi. Ushbu navbatlar ichida rejalashtirish uchun turli xil algoritmlardan foydalanish mumkin. Masalan, foydalanuvchining o'zaro ta'sirini talab qilmaydigan katta hisoblash jarayonlari (fon jarayonlari) uchun FCFS algoritmi, interaktiv jarayonlar uchun esa RR algoritmi ishlatilishi mumkin. Darajali navbat deb nomlangan ushbu yondashuv turli xil xususiyatlarga ega jarayonlar uchun eng mos algoritmdan foydalangan holda rejalashtirishning moslashuvchanligini oshiradi. Ko'p darajali fikr-mulohazalar navbati Ko'p darajali navbat algoritmini yanada rivojlantirish bu unga qayta aloqa mexanizmini qo'shishdir. Bu erda jarayon doimiy ravishda ma'lum bir navbatga tayinlanmagan, lekin uning xatti-harakatlariga qarab navbatdan navbatga o'tishi mumkin. Oddiylik uchun tayyor jarayonlar 7-rasmda bo'lgani kabi 4 ta navbatda tashkil etilgan vaziyatni ko'rib chiqing. Navbatlar orasidagi jarayonlarni rejalashtirish ustuvor ustuvorlik mexanizmiga asoslangan. Rasmda navbat qancha yuqori bo'lsa, uning ustuvorligi shuncha yuqori bo'ladi. 0-navbatda kamida bitta jarayon bo'lsa, 1-navbatdagi jarayonlar ishlamaydi. 0 va 1 navbatlarida kamida bitta jarayon bo'lsa, 2-navbatdagi jarayonlar bajarilishi uchun tanlanmaydi. Nihoyat, 3-navbatdagi jarayon faqat 0, 1 va 2-navbatlar bo'sh bo'lganda o'z ixtiyorida bo'lgan protsessorni olishi mumkin. Agar jarayon amalga oshirilayotgan bo'lsa, navbatdagi jarayon ko'proq ustuvor navbatda paydo bo'lsa, paydo bo'layotgan jarayon tomonidan ishlash jarayoni oldindan belgilanadi. 0-2 qatorlaridagi jarayonlarni rejalashtirish RR algoritmi yordamida amalga oshiriladi; 3-navbatdagi jarayonlarni rejalashtirish FCFS algoritmiga asoslanadi. Yopiq pastadirli navbatlar jarayonlarni rejalashtirishning eng keng tarqalgan usuli hisoblanadi. Ular amalga oshirish uchun eng ko'p vaqt sarflaydi, ammo shu bilan birga ular eng moslashuvchanlikka ega. Foydalanilgan adabiyotlar: А.В.Гордеев “Операционные системы”. Питер 2009г. “ОТ ва ОИ” Маърузалар матни. ATDT.UZ Download 62.16 Kb. Do'stlaringiz bilan baham: 
|