Əməliyyat sistemlərinə giriş
Hey Habr! Fikrimcə, bir maraqlı ədəbiyyatın - OSTEP-in bir sıra məqalə-tərcümələrini diqqətinizə çatdırmaq istərdim. Bu material unix-ə bənzər əməliyyat sistemlərinin işini, yəni proseslər, müxtəlif planlaşdırıcılar, yaddaş və müasir ƏS-ni təşkil edən digər oxşar komponentlərlə işləməyi kifayət qədər dərindən müzakirə edir. Bütün materialların orijinalına burada baxa bilərsiniz . Nəzərə alın ki, tərcümə qeyri-peşəkar şəkildə (olduqca sərbəst) edilib, amma ümid edirəm ki, ümumi mənası saxlamışam.
Bu mövzuda laboratoriya işlərini burada tapa bilərsiniz:
Digər hissələr:
Kanalıma da baxa bilərsiniz =)
Planlayıcıya giriş
Problemin mahiyyəti: Planlayıcı siyasətini necə hazırlamaq olar
Əsas planlaşdırıcı siyasət çərçivələri necə tərtib edilməlidir? Əsas fərziyyələr nə olmalıdır? Hansı göstəricilər vacibdir? İlkin hesablama sistemlərində hansı əsas texnikalardan istifadə olunurdu?
İş Yükü Fərziyyələri
Mümkün siyasətləri müzakirə etməzdən əvvəl gəlin əvvəlcə sistemdə işləyən proseslər haqqında bir neçə sadələşdirici kənara çıxaraq, bunlara topluca deyilir. iş yükü. İş yükünün müəyyən edilməsi siyasətlərin qurulmasının vacib hissəsidir və iş yükü haqqında nə qədər çox bilsəniz, bir o qədər yaxşı siyasət yaza bilərsiniz.
Sistemdə işləyən, bəzən də adlandırılan proseslər haqqında aşağıdakı fərziyyələri edək iş (tapşırıqlar). Bu fərziyyələrin demək olar ki, hamısı real deyil, düşüncənin inkişafı üçün zəruridir.
- Hər bir tapşırıq eyni vaxtda işləyir,
- Bütün tapşırıqlar eyni vaxtda qoyulur,
- Verilən tapşırıq tamamlanana qədər işləyir,
- Bütün tapşırıqlar yalnız CPU istifadə edir,
- Hər bir tapşırığın icra müddəti məlumdur.
Planlayıcı Metrikləri
Yüklə bağlı bəzi fərziyyələrə əlavə olaraq, müxtəlif planlaşdırma siyasətlərini müqayisə etmək üçün başqa alətə ehtiyac var: planlaşdırıcı ölçüləri. Metrik bir şeyin yalnız bir ölçüsüdür. Planlaşdırıcıları müqayisə etmək üçün istifadə edilə bilən bir sıra ölçülər var.
Məsələn, adlı bir metrikadan istifadə edəcəyik dönüş vaxtı (dönmə vaxtı). Tapşırığın yerinə yetirilməsi vaxtı tapşırığın tamamlanma vaxtı ilə sistemdə tapşırığın çatma vaxtı arasındakı fərq kimi müəyyən edilir.
Turnaround=Tamamlama-Gəçmə
Bütün tapşırıqların eyni vaxtda gəldiyini güman etdiyimiz üçün Ta=0 və beləliklə Tt=Tc. Yuxarıdakı fərziyyələri dəyişdirdiyimiz zaman bu dəyər təbii olaraq dəyişəcək.
Başqa bir metrik - ədalət (ədalət, dürüstlük). Planlaşdırmada məhsuldarlıq və ədalətlilik tez-tez bir-birinə zidd olan xüsusiyyətlərdir. Məsələn, planlaşdırıcı performansı optimallaşdıra bilər, lakin digər tapşırıqların yerinə yetirilməsini gözləmək bahasına, beləliklə ədalətliliyi azaldır.
İLK GƏLƏN İLK ÇIXAN (FIFO)
Həyata keçirə biləcəyimiz ən əsas alqoritm FIFO və ya adlanır ilk gələn (giriş), ilk xidmət (çıxmaq). Bu alqoritmin bir sıra üstünlükləri var: həyata keçirmək çox asandır və bütün fərziyyələrimizə uyğun gəlir və işi kifayət qədər yaxşı yerinə yetirir.
Sadə bir misala baxaq. Tutaq ki, eyni vaxtda 3 vəzifə qoyulub. Ancaq fərz edək ki, A tapşırığı digərlərindən bir qədər tez gəlib, ona görə də o, C-yə nisbətən B kimi, icra siyahısında digərlərindən daha tez görünəcək. Tutaq ki, onların hər biri 10 saniyə ərzində yerinə yetiriləcək. Bu halda bu tapşırıqları yerinə yetirmək üçün orta vaxt nə qədər olacaq?
Dəyərləri saymaqla - 10+20+30 və 3-ə bölmək, proqramın orta icra müddətini 20 saniyəyə bərabər alırıq.
İndi fərziyyələrimizi dəyişdirməyə çalışaq. Xüsusilə, 1-ci fərziyyə və buna görə də biz artıq hər bir tapşırığın yerinə yetirilməsi üçün eyni vaxt tələb etdiyini düşünməyəcəyik. FİFO bu dəfə necə çıxış edəcək?
Göründüyü kimi, müxtəlif tapşırıqların yerinə yetirilməsi vaxtları FIFO alqoritminin məhsuldarlığına son dərəcə mənfi təsir göstərir. Fərz edək ki, A tapşırığını yerinə yetirmək üçün 100 saniyə, B və C isə hələ də hər biri 10 saniyə çəkəcək.
Şəkildən göründüyü kimi sistem üçün orta vaxt (100+110+120)/3=110 olacaqdır. Bu təsir adlanır konvoy effekti, resursun bəzi qısamüddətli istehlakçıları ağır istehlakçıdan sonra növbəyə durduqda. Qarşınızda arabası dolu bir müştəri olanda ərzaq mağazasında növbəyə bənzəyir. Problemin ən yaxşı həlli kassanı dəyişməyə çalışmaq və ya rahatlaşıb dərindən nəfəs almaqdır.
Ən Qısa İş Birinci
Bənzər bir vəziyyəti ağır çəki prosesləri ilə həll etmək mümkündürmü? Əlbəttə. Planlaşdırmanın başqa bir növü deyilirƏn Qısa İş Birinci (SJF). Onun alqoritmi də kifayət qədər primitivdir - adından göründüyü kimi, ən qısa tapşırıqlar bir-birinin ardınca ilk olaraq işə salınacaq.
Bu misalda, eyni proseslərin icrasının nəticəsi proqramın orta işləmə müddətində yaxşılaşma olacaq və ona bərabər olacaq. 50 əvəzinə 110, bu, demək olar ki, 2 dəfə yaxşıdır.
Beləliklə, bütün tapşırıqların eyni vaxtda gəldiyinə dair verilən fərziyyə üçün SJF alqoritmi ən optimal alqoritm kimi görünür. Lakin bizim fərziyyələrimiz hələ də real görünmür. Bu dəfə biz 2-ci fərziyyəni dəyişdiririk və bu dəfə təsəvvür edək ki, tapşırıqlar eyni anda deyil, istənilən vaxt mövcud ola bilər. Bu hansı problemlərə səbəb ola bilər?
Təsəvvür edək ki, A (100c) tapşırığı birinci gəlir və yerinə yetirilməyə başlayır. t=10-da B və C tapşırıqları gəlir, onların hər biri 10 saniyə çəkəcək. Beləliklə, orta icra müddəti (100+(110-10)+(120-10))3 = 103-dür. Planlayıcı bunu yaxşılaşdırmaq üçün nə edə bilər?
Ən Qısa Bitirmə Müddəti Birinci (STCF)
Vəziyyəti yaxşılaşdırmaq üçün proqramın işə salınması və tamamlanana qədər davam etməsi ilə bağlı 3-cü fərziyyəni buraxırıq. Bundan əlavə, bizim hardware dəstəyinə ehtiyacımız olacaq və təxmin etdiyiniz kimi istifadə edəcəyik timer çalışan tapşırığı dayandırmaq və kontekst keçidi. Beləliklə, planlaşdırıcı B, C tapşırıqlarının gəldiyi anda nəyisə edə bilər - A tapşırığını yerinə yetirməyi dayandırır və B və C tapşırıqlarını emala qoyur və onlar tamamlandıqdan sonra A prosesini yerinə yetirməyə davam edir. Belə planlaşdırıcı adlanır. STCFvə ya Əvvəlcədən Preemptive İş.
Bu planlayıcının nəticəsi aşağıdakı nəticə olacaq: ((120-0)+(20-10)+(30-10))/3=50. Beləliklə, belə bir planlaşdırıcı tapşırıqlarımız üçün daha optimal olur.
Metrik Cavab Vaxtı
Beləliklə, əgər tapşırıqların icra müddətini bilsək və bu tapşırıqların yalnız CPU istifadə etdiyini bilsək, STCF ən yaxşı həll yolu olacaqdır. Və ilk dövrlərdə bir dəfə bu alqoritmlər olduqca yaxşı işləyirdi. Bununla belə, istifadəçi indi vaxtının çox hissəsini terminalda keçirir və məhsuldar interaktiv təcrübə gözləyir. Beləliklə, yeni bir metrik doğuldu - cavab müddəti (cavab).
Cavab müddəti aşağıdakı kimi hesablanır:
Tresponse=Tfirstrun-Tarrival
Beləliklə, əvvəlki misal üçün cavab müddəti belə olacaq: A=0, B=0, C=10 (abg=3,33).
Və belə çıxır ki, STCF alqoritmi eyni vaxtda 3 tapşırığın gəldiyi bir vəziyyətdə o qədər də yaxşı deyil - kiçik tapşırıqlar tamamilə tamamlanana qədər gözləməli olacaq. Beləliklə, alqoritm geri dönüş vaxtı metrikası üçün yaxşıdır, lakin interaktivlik metrikası üçün pisdir. Təsəvvür edin ki, siz terminalda oturub redaktora simvol yazmağa çalışırsınız və CPU-nun üzərinə başqa bir iş düşdüyü üçün 10 saniyədən çox gözləməli olursunuz. Çox xoş deyil.
Beləliklə, başqa bir problemlə qarşılaşırıq - cavab müddətinə həssas olan bir planlaşdırıcı necə qura bilərik?
Dəyirmi Robin
Bu problemi həll etmək üçün bir alqoritm hazırlanmışdır Dəyirmi Robin (RR). Əsas fikir olduqca sadədir: tapşırıqları yerinə yetirmək əvəzinə, biz tapşırığı müəyyən bir müddət ərzində yerinə yetirəcəyik (zaman dilimi adlanır) və sonra növbədən başqa bir işə keçəcəyik. Alqoritm bütün tapşırıqlar tamamlanana qədər işini təkrarlayır. Bu halda, proqramın işləmə müddəti taymerin prosesi dayandıracağı vaxtın qatına bərabər olmalıdır. Məsələn, əgər taymer hər x=10ms-dən bir prosesi dayandırırsa, o zaman prosesin icrası pəncərəsinin ölçüsü 10-a çoxalmalı və 10,20 və ya x*10 olmalıdır.
Bir misala baxaq: ABC tapşırıqları sistemə eyni vaxtda daxil olur və onların hər biri 5 saniyə işləmək istəyir. SJF alqoritmi digərinə başlamazdan əvvəl hər tapşırığı tamamlayacaq. Bunun əksinə olaraq, işə salma pəncərəsi = 1s olan RR alqoritmi aşağıdakı kimi tapşırıqlardan keçəcək (Şəkil 4.3):
(Yenə SJF (Cavab müddəti üçün pis)
(Round Robin (cavab vaxtı üçün yaxşı)
RR alqoritmi üçün orta cavab müddəti (0+1+2)/3=1, SJF üçün isə (0+5+10)/3=5.
Vaxt pəncərəsinin RR üçün çox vacib bir parametr olduğunu düşünmək məntiqlidir, nə qədər kiçik olsa, cavab müddəti bir o qədər yüksəkdir. Bununla belə, onu çox kiçik etməməlisiniz, çünki kontekstdə keçid vaxtı da ümumi performansda rol oynayacaqdır. Beləliklə, icra pəncərəsinin vaxtının seçimi OS memarı tərəfindən təyin olunur və orada yerinə yetirilməsi planlaşdırılan vəzifələrdən asılıdır. Kontekstin dəyişdirilməsi vaxt itirən yeganə xidmət əməliyyatı deyil - işləyən proqram bir çox başqa şeylər, məsələn, müxtəlif keşlər üzərində işləyir və hər keçid ilə bu mühiti saxlamaq və bərpa etmək lazımdır, bu da çox vaxt tələb edə bilər. vaxt.
Yalnız cavab müddəti metrikasından danışsaq, RR əla planlaşdırıcıdır. Bəs tapşırığın yerinə yetirilmə müddəti metrikası bu alqoritmlə necə davranacaq? Yuxarıdakı nümunəni nəzərdən keçirək, A, B, C = 5s əməliyyat vaxtı və eyni vaxtda çatdıqda. A tapşırığı 13 saniyədə, B 14 saniyədə, C 15 saniyədə başa çatacaq və orta işləmə müddəti 14 saniyə olacaq. Beləliklə, RR dövriyyə metrikası üçün ən pis alqoritmdir.
Daha ümumi dillə desək, istənilən RR tipli alqoritm ədalətlidir; o, CPU vaxtını bütün proseslər arasında bərabər bölür. Beləliklə, bu göstəricilər daim bir-biri ilə ziddiyyət təşkil edir.
Beləliklə, bir neçə ziddiyyətli alqoritmimiz var və eyni zamanda hələ də bir neçə fərziyyə qalır - tapşırığın vaxtı məlumdur və tapşırıq yalnız CPU-dan istifadə edir.
I/O ilə qarışdırma
Hər şeydən əvvəl, prosesin yalnız CPU-dan istifadə etdiyinə dair 4-cü fərziyyəni aradan qaldıraq; təbii ki, bu belə deyil və proseslər digər avadanlıqlara daxil ola bilər.
Hər hansı bir proses I/O əməliyyatını tələb etdiyi an, proses I/O-nun tamamlanmasını gözləyərək bloklanmış vəziyyətə keçir. Əgər I/O sərt diskə göndərilirsə, onda belə bir əməliyyat bir neçə ms və ya daha çox vaxt çəkə bilər və prosessor bu anda boş qalacaq. Bu müddət ərzində planlaşdırıcı prosessoru istənilən başqa proseslə məşğul edə bilər. Planlayıcının verməli olacağı növbəti qərar, prosesin I/O-nu nə vaxt başa çatdıracağıdır. Bu baş verdikdə, fasilə yaranacaq və OS I/O çağıran prosesi hazır vəziyyətə gətirəcək.
Bir neçə tapşırığın nümunəsinə baxaq. Onların hər biri 50 ms CPU vaxtı tələb edir. Bununla belə, birincisi hər 10 ms-dən bir I/O-ya daxil olacaq (həmçinin hər 10 ms-dən bir icra olunacaq). B prosesi isə sadəcə olaraq I/O olmadan 50 ms prosessordan istifadə edir.
Bu nümunədə biz STCF planlaşdırıcısından istifadə edəcəyik. A kimi bir proses işə salınarsa, planlaşdırıcı necə davranacaq? O, aşağıdakıları edəcək: əvvəlcə A prosesini, sonra isə B prosesini tamamilə işləyəcək.
Bu problemi həll etmək üçün ənənəvi yanaşma A prosesinin hər 10 ms alt tapşırığını ayrıca tapşırıq kimi nəzərdən keçirməkdir. Beləliklə, STJF alqoritmi ilə başlayanda 50 ms tapşırıq və 10 ms tapşırıq arasında seçim göz qabağındadır. Sonra, A alt tapşırığı tamamlandıqda, B prosesi və I/O işə salınacaq. Giriş/Çıxış tamamlandıqdan sonra B prosesi əvəzinə 10 ms-lik A prosesini yenidən başlatmaq adət olacaq. Bu yolla, üst-üstə düşməyi həyata keçirmək mümkündür, burada CPU başqa bir proses tərəfindən istifadə olunur və birinci proses gözlənilmir. I/O. Və nəticədə sistemdən daha yaxşı istifadə olunur - interaktiv proseslərin giriş/çıxış gözlədiyi anda prosessorda başqa proseslər də icra oluna bilər.
Oracle artıq yoxdur
İndi tapşırığın icra müddətinin məlum olduğu fərziyyəsindən qurtulmağa çalışaq. Bu, ümumiyyətlə, bütün siyahıdakı ən pis və ən qeyri-real fərziyyədir. Əslində, orta adi OS-də ƏS-nin özü adətən tapşırıqların icra müddəti haqqında çox az şey bilir, buna görə də tapşırığın yerinə yetirilməsi üçün nə qədər vaxt aparacağını bilmədən necə planlaşdırıcı qurmaq olar? Bəlkə bu problemi həll etmək üçün bəzi RR prinsiplərindən istifadə edə bilərik?
Ümumi
Biz tapşırıqların planlaşdırılmasının əsas ideyalarına baxdıq və 2 planlaşdırıcı ailəsinə baxdıq. Birincisi əvvəlcə ən qısa tapşırığa başlayır və beləliklə, dönüş müddətini artırır, ikincisi isə bütün tapşırıqlar arasında bərabər şəkildə parçalanır və cavab müddətini artırır. Digər ailənin alqoritmləri yaxşı olduqda hər iki alqoritm pisdir. Biz həmçinin CPU və I/O-nun paralel istifadəsinin performansı necə yaxşılaşdıra biləcəyinə baxdıq, lakin OS-nin kəşfiyyatı ilə bağlı problemi həll etmədik. Növbəti dərsdə biz yaxın keçmişə baxan və gələcəyi proqnozlaşdırmağa çalışan bir planlayıcıya baxacağıq. Və buna çoxsəviyyəli rəy növbəsi deyilir.
Mənbə: www.habr.com