ოპერაციული სისტემების შესავალი

ჰეი ჰაბრ! მინდა თქვენს ყურადღებას გავამახვილო ჩემი აზრით ერთი საინტერესო ლიტერატურის - OSTEP-ის სტატია-თარგმანის სერია. ეს მასალა საკმაოდ ღრმად განიხილავს unix-ის მსგავსი ოპერაციული სისტემების მუშაობას, კერძოდ, პროცესებთან, სხვადასხვა გრაფიკებთან, მეხსიერებასთან და სხვა მსგავს კომპონენტებთან მუშაობას, რომლებიც ქმნიან თანამედროვე OS-ს. ყველა მასალის ორიგინალი შეგიძლიათ ნახოთ აქ აქ. გთხოვთ გაითვალისწინოთ, რომ თარგმანი შესრულებულია არაპროფესიონალურად (საკმაოდ თავისუფლად), მაგრამ იმედია შევინარჩუნე ზოგადი მნიშვნელობა.

ამ თემაზე ლაბორატორიული სამუშაოები შეგიძლიათ იხილოთ აქ:

• ორიგინალი
• ორიგინალი
• ჩემი პირადი ადაპტაცია

სხვა ნაწილები:

• ნაწილი 1: შესავალი
• ნაწილი 2: აბსტრაქცია: პროცესი
• ნაწილი 3: შესავალი პროცესის API-ში
• ნაწილი 4: შესავალი განრიგთან
• ნაწილი 5: MLFQ Scheduler

ასევე შეგიძლიათ ნახოთ ჩემი არხი აქ ტელეგრამა =)

დაგეგმვა: მრავალ დონის უკუკავშირის რიგი

ამ ლექციაში ვისაუბრებთ ერთ-ერთი ყველაზე ცნობილი მიდგომის შემუშავების პრობლემებზე
დაგეგმვა, რომელსაც ე.წ მრავალ დონის უკუკავშირის რიგი (MLFQ). MLFQ გრაფიკი პირველად აღწერა 1962 წელს ფერნანდო ჯ. კორბატოს მიერ სისტემაში ე.წ.
თავსებადი დროის გაზიარების სისტემა (CTSS). ეს ნამუშევრები (მათ შორის შემდგომი სამუშაოები
Multics) შემდგომში იყო ნომინირებული ტურინგის ჯილდოზე. განრიგი იყო
შემდგომში გაუმჯობესდა და შეიძინა გარეგნობა, რომელიც უკვე გვხვდება
ზოგიერთი თანამედროვე სისტემა.

MLFQ ალგორითმი ცდილობს გადაჭრას 2 ფუნდამენტური გადახურვის პრობლემა.
პირველ რიგში, ის ცდილობს ოპტიმიზაცია მოახდინოს შემობრუნების დროს, რომელიც, როგორც წინა ლექციაში განვიხილეთ, ოპტიმიზებულია ყველაზე მეტად რიგის სათავეში დაწყების მეთოდით.
მოკლე დავალებები. თუმცა, OS-მ არ იცის რამდენ ხანს გაგრძელდება ესა თუ ის პროცესი და ეს
SJF, STCF ალგორითმების მუშაობისთვის აუცილებელი ცოდნა. მეორე, MLFQ ცდილობს
გახადეთ სისტემა პასუხისმგებელი მომხმარებლებისთვის (მაგალითად, მათთვის, ვინც ზის და
დავალების შესრულების მოლოდინში ეკრანზე ყურება) და ამით მინიმუმამდე დაიყვანოს დრო
პასუხი. სამწუხაროდ, ალგორითმები, როგორიცაა RR, ამცირებს რეაგირების დროს, მაგრამ
ცუდ გავლენას ახდენს შემობრუნების დროის მეტრიკაზე. აქედან გამომდინარეობს ჩვენი პრობლემა: როგორ შევქმნათ დიზაინი
გრაფიკი, რომელიც დააკმაყოფილებს ჩვენს მოთხოვნებს და ამავდროულად არაფერი იცის
პროცესის ბუნება ზოგადად? როგორ შეუძლია დამგეგმავმა ისწავლოს დავალებების მახასიათებლები,
რომელსაც ის იწყებს და, შესაბამისად, უკეთეს გადაწყვეტილებებს იღებს დაგეგმვის შესახებ?

პრობლემის არსი: როგორ დავგეგმოთ ამოცანების დადგენა სრულყოფილი ცოდნის გარეშე?
როგორ შევქმნათ გრაფიკი, რომელიც ერთდროულად ამცირებს რეაგირების დროს
ინტერაქტიული ამოცანებისთვის და ამავდროულად ამცირებს შემობრუნების დროს ცოდნის გარეშე
ამოცანის შესრულების დროის ცოდნა?

შენიშვნა: სწავლა წინა მოვლენებიდან

MLFQ რიგი არის სისტემის შესანიშნავი მაგალითი, რომელზედაც ვარჯიშობენ
წარსული მოვლენები მომავლის პროგნოზირებისთვის. ასეთი მიდგომები ხშირია
ნაპოვნია OS-ში (და კომპიუტერული მეცნიერების მრავალი სხვა ფილიალი, მათ შორის ფილიალები
ტექნიკის პროგნოზები და ქეშირების ალგორითმები). მსგავსი ლაშქრობები
იწვევს, როდესაც ამოცანებს აქვს ქცევითი ფაზები და, შესაბამისად, პროგნოზირებადია.
თუმცა, ამ ტექნიკით ფრთხილად უნდა იყოთ, რადგან პროგნოზირება ძალიან მარტივია.
შეიძლება არასწორი აღმოჩნდეს და სისტემა მიიყვანოს იმაზე უარესი გადაწყვეტილებებისკენ, ვიდრე
ცოდნის გარეშე იქნებოდა.

MLFQ: ძირითადი წესები

განვიხილოთ MLFQ ალგორითმის ძირითადი წესები. და მიუხედავად იმისა, რომ ამ ალგორითმის განხორციელება
არსებობს რამდენიმე, ძირითადი მიდგომები მსგავსია.
განხორციელებისას, რომელსაც განვიხილავთ, MLFQ-ს ექნება რამდენიმე
ცალკე რიგები, რომელთაგან თითოეულს განსხვავებული პრიორიტეტი ექნება. ნებისმიერ დროს,
შესასრულებლად მზად დავალება იმავე რიგშია. MLFQ იყენებს პრიორიტეტებს,
გადაწყვიტოს რომელი დავალების შესრულება, ე.ი. დავალება უფრო მაღალით
პირველ რიგში ამოქმედდება პრიორიტეტი (დავალება რიგიდან უმაღლესი პრიორიტეტით).
რიგში.
რა თქმა უნდა, კონკრეტულ რიგში შეიძლება იყოს ერთზე მეტი დავალება, ასე რომ
ასე რომ, მათ ექნებათ იგივე პრიორიტეტი. ამ შემთხვევაში, მექანიზმი იქნება გამოყენებული
RR ამ ამოცანებს შორის გაშვების დაგეგმვისთვის.
ამრიგად, ჩვენ მივდივართ MLFQ-ის ორ ძირითად წესამდე:

• წესი 1: თუ პრიორიტეტი (A) > პრიორიტეტი (B), ამოცანა A შესრულდება (B არა)
• წესი2: თუ პრიორიტეტი(A) = პრიორიტეტი(B), A&B იწყება RR-ის გამოყენებით

ზემოაღნიშნულიდან გამომდინარე, MLFQ-ის დაგეგმვის ძირითადი ელემენტებია
პრიორიტეტებია. იმის ნაცვლად, რომ თითოეულს მიანიჭოთ ფიქსირებული პრიორიტეტი
ამოცანა, MLFQ ცვლის თავის პრიორიტეტს დაკვირვებული ქცევის მიხედვით.
მაგალითად, თუ ამოცანა მუდმივად ჩერდება CPU-ზე კლავიატურის შეყვანის მოლოდინში,
MLFQ დაიცავს პროცესის პრიორიტეტს მაღალ დონეზე, რადგან ასეა
ინტერაქტიული პროცესი უნდა იმუშაოს. თუ პირიქით, ამოცანა მუდმივად და
არის CPU ინტენსიური ხანგრძლივი პერიოდის განმავლობაში, MLFQ შეამცირებს მას
პრიორიტეტი. ამრიგად, MLFQ შეისწავლის პროცესების ქცევას მათი გაშვების დროს.
და გამოიყენე ქცევები.
მოდით დავხატოთ მაგალითი იმისა, თუ როგორ შეიძლება გამოიყურებოდეს რიგები რაღაც მომენტში
დრო და შემდეგ მიიღებთ ასეთ რამეს:


ამ სქემაში 2 პროცესი A და B არის უმაღლესი პრიორიტეტის რიგში. პროცესი
C არის სადღაც შუაში, და პროცესი D არის რიგის ბოლოში. ზემოაღნიშნულის მიხედვით
MLFQ ალგორითმის აღწერილობით, განრიგი შეასრულებს დავალებებს მხოლოდ უმაღლესი
პრიორიტეტი RR-ის მიხედვით და C, D ამოცანები იქნება უმუშევარი.
ბუნებრივია, სტატიკური სნეპშოტი არ იძლევა სრულ სურათს იმის შესახებ, თუ როგორ მუშაობს MLFQ.
მნიშვნელოვანია იმის გაგება, თუ როგორ იცვლება სურათი დროთა განმავლობაში.

მცდელობა 1: როგორ შევცვალოთ პრიორიტეტი

ამ ეტაპზე, თქვენ უნდა გადაწყვიტოთ, როგორ შეცვლის MLFQ პრიორიტეტის დონეს
ამოცანა (და, შესაბამისად, დავალების პოზიცია რიგში) მისი სასიცოცხლო ციკლის განმავლობაში. ამისთვის
ამისათვის თქვენ უნდა გაითვალისწინოთ სამუშაო პროცესი: გარკვეული რაოდენობა
ინტერაქტიული ამოცანები მოკლე შესრულების დროით (და, შესაბამისად, ხშირი გამოშვება
CPU) და რამდენიმე გრძელი დავალება, რომელიც იყენებს CPU-ს მთელი მათი მუშაობის დროს, ხოლო
ასეთ ამოცანებზე რეაგირების დრო არ არის მნიშვნელოვანი. ასე რომ თქვენ შეგიძლიათ გააკეთოთ პირველი მცდელობა
განახორციელეთ MLFQ ალგორითმი შემდეგი წესებით:

• წესი3: როდესაც დავალება სისტემაში შედის, ის მოთავსებულია რიგში ყველაზე მაღალი
• პრიორიტეტი.
• წესი 4ა: თუ დავალება იყენებს მთელ დროს ფანჯარას, მაშინ ის
• პრიორიტეტი შემცირდა.
• წესი 4ბ: თუ Task ათავისუფლებს პროცესორს მისი დროის ფანჯრის ამოწურვამდე, მაშინ ის
• იგივე პრიორიტეტი რჩება.

მაგალითი 1: ერთი გრძელვადიანი დავალება

როგორც ამ მაგალითში ხედავთ, დაშვების დროს დავალება დაყენებულია უმაღლესით
პრიორიტეტი. 10 ms დროის ფანჯრის შემდეგ, პროცესი პრიორიტეტულია.
განრიგი. შემდეგი დროის ფანჯრის შემდეგ, ამოცანა საბოლოოდ დაქვეითებულია
ყველაზე დაბალი პრიორიტეტი სისტემაში, სადაც ის რჩება.


მაგალითი 2: აიღო მოკლე დავალება

ახლა ვნახოთ მაგალითი იმისა, თუ როგორ შეეცდება MLFQ მიუახლოვდეს SJF-ს. Იმაში
მაგალითად, ორი დავალება: A, რომელიც არის ხანგრძლივი დავალება მუდმივად
CPU-ს და B-ის დაკავება, რაც მოკლე ინტერაქტიული ამოცანაა. დავუშვათ
რომ B დავალების მოსვლის დროისთვის A უკვე აწარმოებდა გარკვეული დროის განმავლობაში.


ეს გრაფიკი აჩვენებს სცენარის შედეგებს. ამოცანა A, ისევე როგორც ნებისმიერი დავალება,
CPU-ს გამოყენება ბოლოში იყო. დავალება B ჩამოვა დრო T=100 და იქნება
მოთავსებულია უმაღლესი პრიორიტეტის რიგში. ვინაიდან მოქმედების დრო მოკლეა,
ის დასრულდება მანამ, სანამ არ მიაღწევს ბოლო რიგში.

ამ მაგალითიდან თქვენ უნდა გესმოდეთ ალგორითმის მთავარი მიზანი: რადგან ალგორითმი ასე არ არის
იცის გრძელი ან მოკლე დავალება, შემდეგ პირველ რიგში ივარაუდებს, რომ დავალება
მოკლეა და მას უმაღლეს პრიორიტეტს ანიჭებს. თუ ეს მართლაც მოკლე ამოცანაა, მაშინ
ის სწრაფად შეასრულებს, წინააღმდეგ შემთხვევაში, თუ ეს გრძელი ამოცანაა, ის ნელა მოძრაობს
პრიორიტეტულია და მალე დაამტკიცებს, რომ ის მართლაც გრძელი ამოცანაა, რომელიც არ არის
პასუხს მოითხოვს.

მაგალითი 3: რაც შეეხება I/O-ს?

ახლა მოდით შევხედოთ I/O მაგალითს. როგორც მე-4 ბ წესშია ნათქვამი,
თუ პროცესი ათავისუფლებს პროცესორს მისი პროცესორის დროის სრულად გამოყენების გარეშე,
შემდეგ ის რჩება იმავე პრიორიტეტულ დონეზე. ამ წესის მიზანი საკმაოდ მარტივია.
- თუ ინტერაქტიული სამუშაო ასრულებს ბევრ I/O-ს, მაგალითად, ელოდება
მომხმარებლის კლავიშების ან მაუსის დარტყმისგან, ასეთი დავალება გაათავისუფლებს პროცესორს
გამოყოფილი ფანჯრის წინ. ჩვენ არ გვინდა გამოვტოვოთ ასეთი პრიორიტეტული დავალება,
და ამრიგად, ის დარჩება იმავე დონეზე.


ეს მაგალითი გვიჩვენებს, თუ როგორ იმუშავებს ალგორითმი ასეთ პროცესებთან - ინტერაქტიული დავალება B, რომელსაც შესრულებამდე სჭირდება CPU მხოლოდ 1ms.
I/O პროცესი და ხანგრძლივი სამუშაო A, რომელიც მუდმივად იყენებს CPU-ს.
MLFQ ინარჩუნებს B პროცესს უმაღლეს პრიორიტეტად, რადგან ის გრძელდება
გაათავისუფლეთ CPU. თუ B არის ინტერაქტიული დავალება, მაშინ ალგორითმი ამ შემთხვევაში მიღწეულია
მისი მიზანია სწრაფად დაიწყოს ინტერაქტიული ამოცანები.

პრობლემები მიმდინარე MLFQ ალგორითმთან

წინა მაგალითებში ჩვენ შევქმენით MLFQ-ის ძირითადი ვერსია. და როგორც ჩანს, ის
თავის საქმეს კარგად და სამართლიანად აკეთებს, CPU დროს სამართლიანად ანაწილებს შორის
გრძელი ამოცანები და მოკლე ამოცანების ან ამოცანების დაშვება, რომლებსაც დიდი წვდომა აქვს
I/O-მდე სწრაფად დასამუშავებლად. სამწუხაროდ, ეს მიდგომა შეიცავს რამდენიმე
სერიოზული პრობლემები.
პირველ რიგშიშიმშილის პრობლემა: თუ სისტემას ბევრი ინტერაქტიული ექნება
ამოცანები, ისინი მოიხმარენ CPU-ს მთელ დროს და, შესაბამისად, არც ერთ დიდ დროს
დავალება არ მიიღება შესასრულებლად (შიმშილით იხოცებიან).

მეორეჭკვიან მომხმარებლებს შეეძლოთ დაწერონ თავიანთი პროგრამები ისე, რომ
მოატყუოს გრაფიკის დამგეგმავი. მოტყუება მდგომარეობს იმაში, რომ რაღაცის გაკეთება აიძულო
გრაფიკი, რათა პროცესს მეტი დრო მისცეს CPU-ს. ალგორითმი რომ
ზემოთ აღწერილი საკმაოდ დაუცველია ასეთი თავდასხმების მიმართ: სანამ დროის ფანჯარა პრაქტიკულად არ არის
მეტი, თქვენ უნდა შეასრულოთ I/O ოპერაცია (ზოგს, არ აქვს მნიშვნელობა რომელი ფაილი)
და ამით გაათავისუფლეთ CPU. ასეთი ქცევა საშუალებას მოგცემთ დარჩეთ იგივე
თავად რიგს და ისევ მიიღებთ CPU დროის უფრო დიდ პროცენტს. თუ გაკეთდა
ეს სწორია (მაგ. გაუშვით ფანჯრის დროის 99% CPU-ს გამოშვებამდე),
ასეთ ამოცანას შეუძლია უბრალოდ პროცესორის მონოპოლიზება.

საბოლოოდ, პროგრამას შეუძლია დროთა განმავლობაში შეცვალოს თავისი ქცევა. ის ამოცანები
რომ გამოყენებული CPU შეიძლება გახდეს ინტერაქტიული. ჩვენს მაგალითში, მსგავსი
ამოცანები არ მიიღებენ სათანადო მკურნალობას განრიგისგან, როგორც ამას სხვები მიიღებენ
(ორიგინალი) ინტერაქტიული ამოცანები.

კითხვა აუდიტორიას: რა თავდასხმები შეიძლება განხორციელდეს გრაფიკზე თანამედროვე სამყაროში?

მცდელობა 2: პრიორიტეტის გაზრდა

შევეცადოთ შევცვალოთ წესები და ვნახოთ, შევძლებთ თუ არა თავიდან ავიცილოთ პრობლემები
შიმშილი. რა შეგვიძლია გავაკეთოთ იმისთვის, რომ ეს დაკავშირებული იყოს
CPU ამოცანები მიიღებს თავის დროს (თუნდაც არა ხანგრძლივი).
როგორც პრობლემის მარტივი გადაწყვეტა, შეგიძლიათ პერიოდულად შემოგთავაზოთ
გაზარდოს ყველა ასეთი ამოცანის პრიორიტეტი სისტემაში. ბევრი გზა არსებობს
ამის მისაღწევად, შევეცადოთ განვახორციელოთ რაიმე მარტივი მაგალითის სახით: თარგმნა
ყველა დავალება ერთდროულად უმაღლეს პრიორიტეტად, აქედან გამომდინარე, ახალი წესი:

• წესი 5: გარკვეული პერიოდის შემდეგ S, გადაიტანეთ სისტემის ყველა დავალება უმაღლეს რიგში.

ჩვენი ახალი წესი ერთდროულად წყვეტს ორ პრობლემას. პირველ რიგში, პროცესები
გარანტირებული არ მოკვდება შიმშილით: დავალებები ყველაზე მაღალ რიგში გაიზიარებს
პროცესორის დრო RR ალგორითმის მიხედვით და ამით ყველა პროცესი მიიღებს
პროცესორის დრო. მეორე, თუ ადრე გამოყენებული პროცესი
მხოლოდ პროცესორი ხდება ინტერაქტიული, ის დარჩება რიგში ყველაზე მაღალი
პრიორიტეტი ერთხელ უმაღლესი პრიორიტეტის მიღების შემდეგ.
განვიხილოთ მაგალითი. ამ სცენარში განიხილეთ ერთი პროცესის გამოყენებით


CPU და ორი ინტერაქტიული, მოკლე პროცესი. ნახატზე მარცხნივ, ფიგურა გვიჩვენებს ქცევას პრიორიტეტული გაძლიერების გარეშე და, ამრიგად, ხანგრძლივი დავალება იწყებს შიმშილს მას შემდეგ, რაც სისტემაში ორი ინტერაქტიული დავალება მოდის. ფიგურაში მარჯვნივ, ყოველ 50 ms-ში შესრულებულია პრიორიტეტის გაზრდა და ამგვარად, ყველა პროცესი გარანტირებულია პროცესორის დროს და პერიოდულად დაიწყება. 50ms ამ შემთხვევაში აღებულია, როგორც მაგალითი, სინამდვილეში ეს რიცხვი გარკვეულწილად უფრო მაღალია.
აშკარაა, რომ პერიოდული აწევის დროის დამატება S იწვევს
ლოგიკური კითხვა: რა მნიშვნელობა უნდა იყოს მითითებული? ერთ-ერთი დამსახურებული
სისტემების ინჟინრებმა ჯონ აუსტერჰაუტმა მოიხსენია მსგავსი რაოდენობით სისტემებში, როგორც voo-doo
მუდმივი, რადგან ისინი გარკვეულწილად მოითხოვდნენ შავ მაგიას სისწორისთვის
კონტაქტი დაინფიცირების წყაროსთან. და, სამწუხაროდ, S-ს აქვს ასეთი არომატი. თუ თქვენ დააყენეთ მნიშვნელობაც
დიდი - გრძელი ამოცანები შიმშილით მოკვდება. და თუ დააყენებთ მას ძალიან დაბალზე,
ინტერაქტიული ამოცანები არ მიიღებენ სათანადო CPU დროს.

მცდელობა 3: უკეთესი აღრიცხვა

ახლა კიდევ ერთი პრობლემა გვაქვს გადასაჭრელი: როგორ არა
ნებას დართეთ ჩვენი განრიგის მოტყუება? ამ შესაძლებლობის დამნაშავეები არიან
წესები 4a, 4b, რომლებიც საშუალებას აძლევს სამუშაოს შეინარჩუნოს თავისი პრიორიტეტი პროცესორის გათავისუფლებით
გამოყოფილი დროის გასვლამდე. როგორ გავუმკლავდეთ მას?
გამოსავალად ამ შემთხვევაში შეიძლება ჩაითვალოს CPU დროის უკეთ აღრიცხვა თითოეულზე
MLFQ დონე. იმის ნაცვლად, რომ დაივიწყოთ პროგრამის გამოყენებული დრო
პროცესორი გამოყოფილი ინტერვალისთვის, უნდა გაითვალისწინოთ და შეინახოთ. შემდეგ
პროცესმა გამოიყენა დათმობილი დრო, ის უნდა გადაიზარდოს შემდეგზე
პრიორიტეტის დონე. ახლა არ აქვს მნიშვნელობა, როგორ გამოიყენებს პროცესი თავის დროს - როგორ
მუდმივად გამოთვლა პროცესორზე ან ზარების ერთობლიობაში. ამრიგად,
წესი 4 უნდა გადაიწეროს შემდეგნაირად:

• წესი 4: მას შემდეგ, რაც ამოცანა გამოიყენებს თავის გამოყოფილ დროს მიმდინარე რიგში (მიუხედავად იმისა, რამდენჯერ გაათავისუფლა CPU), ასეთი დავალების პრიორიტეტი მცირდება (ის მოძრაობს რიგში).

მოდით შევხედოთ მაგალითს:
»

ფიგურა გვიჩვენებს, რა მოხდება, თუ ცდილობთ მოატყუოთ გრაფიკის მსგავსი
ეს რომ ყოფილიყო წინა წესები 4a, 4b იქნებოდა შედეგი მარცხნივ. ახლით
წესი არის შედეგი მარჯვნივ. დაცვამდე, ნებისმიერ პროცესს შეეძლო I/O დარეკვა დასრულებამდე და
ამგვარად, დომინირებს CPU-ზე, დაცვის ჩართვის შემდეგ, ქცევის მიუხედავად
I/O, ის მაინც ჩამოვა რიგში და ამით ვერ შეძლებს არაკეთილსინდისიერად
CPU რესურსების აღება.

MLFQ და სხვა საკითხების გაუმჯობესება

ზემოაღნიშნული გაუმჯობესებებით ჩნდება ახალი პრობლემები: ერთ-ერთი მთავარი
კითხვები - როგორ გავატაროთ ასეთი გრაფიკის პარამეტრიზაცია? იმათ. რამდენი უნდა იყოს
რიგები? რა უნდა იყოს პროგრამის ფანჯრის ზომა რიგში? Როგორ
პროგრამა ხშირად უნდა იყოს პრიორიტეტული, რათა თავიდან იქნას აცილებული შიმშილი და
გავითვალისწინოთ პროგრამის ქცევის ცვლილება? ამ კითხვებზე მარტივი არ არის
პასუხი და მხოლოდ ექსპერიმენტები დატვირთვებით და შემდგომი კონფიგურაციით
განრიგმა შეიძლება გამოიწვიოს დამაკმაყოფილებელი ბალანსი.

მაგალითად, MLFQ განხორციელების უმეტესობა საშუალებას გაძლევთ დაავალოთ განსხვავებული
დროის ინტერვალი სხვადასხვა რიგებისთვის. ჩვეულებრივ, მაღალი პრიორიტეტული რიგებია
მოკლე ინტერვალებით. ეს რიგები შედგება ინტერაქტიული ამოცანებისაგან,
მათ შორის გადართვა საკმაოდ მგრძნობიარეა და უნდა მიიღოს 10 ან ნაკლები
ქალბატონი. ამის საპირისპიროდ, დაბალი პრიორიტეტის რიგები შედგება გრძელვადიანი ამოცანებისაგან, რომლებიც იყენებენ
ᲞᲠᲝᲪᲔᲡᲝᲠᲘ. და ამ შემთხვევაში, დიდი დროის ინტერვალები ძალიან კარგად ჯდება (100 ms).


ამ მაგალითში არის 2 დავალება, რომლებიც მუშაობდნენ მაღალი პრიორიტეტის რიგში 20
ms დაყოფილია 10 ms ფანჯრებად. 40 ms შუა რიგში (20 ms ფანჯარა) და დაბალი პრიორიტეტის რიგში
რიგის დროის ფანჯარა გახდა 40 ms, სადაც ამოცანები დაასრულეს თავიანთი სამუშაო.

MLFQ-ის დანერგვა Solaris OS-ში არის დროის გაზიარების გრაფიკების კლასი.
განრიგი უზრუნველყოფს ცხრილების კომპლექტს, რომელიც ზუსტად განსაზღვრავს, თუ როგორ უნდა
შეცვალოს პროცესის პრიორიტეტი მისი ცხოვრების მანძილზე, რა უნდა იყოს ზომა
გამოყოფილი ფანჯარა და რამდენად ხშირად უნდა გაიზარდოს ამოცანების პრიორიტეტები. ადმინისტრატორი
სისტემას შეუძლია ურთიერთქმედება ამ ცხრილთან და აიძულოს დამგეგმავი მოიქცეს
განსხვავებულად. ნაგულისხმევად, ამ ცხრილს აქვს 60 რიგი თანდათანობითი ზრდით
ფანჯრის ზომა 20 ms-დან (მაღალი პრიორიტეტი) რამდენიმე ასეულ ms-მდე (ყველაზე დაბალი პრიორიტეტი) და
ასევე ყველა ამოცანის გაძლიერებით წამში ერთხელ.

სხვა MLFQ გრაფიკები არ იყენებენ ცხრილს ან რაიმე კონკრეტულს
წესები, რომლებიც აღწერილია ამ თავში, პირიქით, ისინი ითვლიან პრიორიტეტებს გამოყენებით
მათემატიკური ფორმულები. მაგალითად, გრაფიკი FreeBSD-ში იყენებს ფორმულას
მიმდინარე ამოცანის პრიორიტეტის გაანგარიშება პროცესის მასშტაბის მიხედვით
გამოიყენა CPU. გარდა ამისა, CPU-ს გამოყენება დროთა განმავლობაში ფუჭდება და ამით
ამრიგად, პრიორიტეტის ზრდა გარკვეულწილად განსხვავდება ზემოთ აღწერილისგან. Ეს მართალია
დაშლის ალგორითმები ეწოდება. 7.1 ვერსიის მიხედვით, FreeBSD იყენებს ULE განრიგს.

დაბოლოს, ბევრ დამგეგმავს სხვა ფუნქციები აქვს. მაგალითად, ზოგიერთი
გრაფიკები იტოვებენ უფრო მაღალ დონეებს ოპერაციული სისტემის მუშაობისთვის და ამდენად
ამდენად, არც ერთი მომხმარებლის პროცესი არ შეუძლია მიიღოს უმაღლესი პრიორიტეტი
სისტემა. ზოგიერთი სისტემა საშუალებას გაძლევთ მოგცეთ რჩევა დახმარებისთვის
გრაფიკის სწორად პრიორიტეტები. მაგალითად, ბრძანების გამოყენებით ლამაზი
შეგიძლიათ გაზარდოთ ან შეამციროთ დავალების პრიორიტეტი და ამით გაზარდოთ ან შეამციროთ
შეამცირეთ პროგრამის შანსები პროცესორის დროზე.

MLFQ: რეზიუმე

ჩვენ აღვწერეთ დაგეგმვის მიდგომა სახელწოდებით MLFQ. Მისი სახელი
დადებული მოქმედების პრინციპში - მას აქვს რამდენიმე რიგი და იყენებს უკუკავშირს
დავალების პრიორიტეტიზაცია.
წესების საბოლოო ფორმა იქნება შემდეგი:

• წესი 1: თუ პრიორიტეტი(A) > პრიორიტეტი(B), ამოცანა A შესრულდება (B არა)
• წესი 2: თუ პრიორიტეტი(A) = პრიორიტეტი(B), A&B იწყება RR-ის გამოყენებით
• წესი 3: როდესაც ამოცანა შედის სისტემაში, ის მოთავსებულია უმაღლესი პრიორიტეტის რიგში.
• წესი 4: მას შემდეგ, რაც ამოცანა გამოიყენებს თავის გამოყოფილ დროს მიმდინარე რიგში (მიუხედავად იმისა, რამდენჯერ გაათავისუფლა CPU), ასეთი დავალების პრიორიტეტი მცირდება (ის მოძრაობს რიგში).
• წესი 5: გარკვეული პერიოდის შემდეგ S, გადაიტანეთ სისტემის ყველა დავალება უმაღლეს რიგში.

MLFQ საინტერესოა შემდეგი მიზეზის გამო - იმის ნაცვლად, რომ მოითხოვოს ცოდნა
ამოცანის ბუნება წინასწარ, ალგორითმი სწავლობს დავალების წარსულ ქცევას და ადგენს
პრიორიტეტები შესაბამისად. ამრიგად, ის ცდილობს ერთდროულად იჯდეს ორ სკამზე - მიაღწიოს შესრულებას მცირე ამოცანებისთვის (SJF, STCF) და გულწრფელად აწარმოოს გრძელი,
პროცესორის ჩატვირთვის სამუშაოები. ამიტომ, მრავალი სისტემა, მათ შორის BSD და მათი წარმოებულები,
Solaris, Windows, Mac იყენებენ ალგორითმის გარკვეულ ფორმას, როგორც განრიგს
MLFQ როგორც საბაზისო.

დამატებითი მასალები:

1. manpages.debian.org/stretch/manpages/sched.7.en.html
2. en.wikipedia.org/wiki/Scheduling_(გამოთვლა)
3. pages.lip6.fr/Julia.Lawall/atc18-bouron.pdf
4. www.usenix.org/legacy/event/bsdcon03/tech/full_papers/roberson/roberson.pdf
5. chebykin.org/freebsd-process-scheduling

წყარო: www.habr.com