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

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

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

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

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

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

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

შესავალი Scheduler-ში

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

სამუშაო დატვირთვის ვარაუდები

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

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

1. თითოეული დავალება მუშაობს იმავე დროის განმავლობაში,
2. ყველა დავალება დაყენებულია ერთდროულად,
3. დავალებული დავალება მუშაობს მის დასრულებამდე,
4. ყველა დავალება იყენებს მხოლოდ CPU-ს,
5. თითოეული დავალების შესრულების დრო ცნობილია.

Scheduler Metrics

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

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

Tturnaround=Tcompletion−Tarrival

ვინაიდან ჩვენ ვივარაუდეთ, რომ ყველა დავალება ერთდროულად მოვიდა, მაშინ Ta=0 და შესაბამისად Tt=Tc. ეს მნიშვნელობა ბუნებრივად შეიცვლება, როდესაც ჩვენ შევცვლით ზემოხსენებულ ვარაუდებს.

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

FIRST IN FIRST OUT (FIFO)

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

მოდით შევხედოთ მარტივ მაგალითს. ვთქვათ, 3 დავალება დაისვა ერთდროულად. მაგრამ დავუშვათ, რომ დავალება A ჩამოვიდა ყველა დანარჩენზე ცოტა ადრე, ასე რომ, ის გამოჩნდება შესრულების სიაში უფრო ადრე, ვიდრე სხვები, ისევე როგორც B C-სთან შედარებით. დავუშვათ, რომ თითოეული მათგანი შესრულდება 10 წამის განმავლობაში. რამდენი იქნება ამ დავალებების შესრულების საშუალო დრო ამ შემთხვევაში?

მნიშვნელობების დათვლით - 10+20+30 და გაყოფით 3-ზე, მივიღებთ პროგრამის შესრულების საშუალო დროს 20 წამის ტოლი.
ახლა შევეცადოთ შევცვალოთ ჩვენი ვარაუდები. კერძოდ, ვარაუდი 1 და, შესაბამისად, ჩვენ აღარ ვივარაუდებთ, რომ თითოეული დავალების შესრულებას იგივე დრო სჭირდება. როგორ ითამაშებს FIFO ამჯერად?

როგორც ირკვევა, დავალების შესრულების სხვადასხვა დრო უკიდურესად უარყოფით გავლენას ახდენს FIFO ალგორითმის პროდუქტიულობაზე. დავუშვათ, რომ A დავალების შესრულებას დასჭირდება 100 წამი, ხოლო B და C თითოეულს მაინც 10 წამი.

როგორც ნახატიდან ჩანს, სისტემის საშუალო დრო იქნება (100+110+120)/3=110. ამ ეფექტს ე.წ კოლონის ეფექტი, როდესაც რესურსის ზოგიერთი მოკლევადიანი მომხმარებელი მძიმე მომხმარებლის შემდეგ რიგში დადგება. ეს ჰგავს სასურსათო მაღაზიის ხაზს, როდესაც თქვენს წინ არის მომხმარებელი სავსე კალათით. პრობლემის საუკეთესო გამოსავალი არის სალარო აპარატის გამოცვლა ან მოდუნება და ღრმა სუნთქვა.

უმოკლეს სამუშაო პირველი

შესაძლებელია თუ არა მსგავსი სიტუაციის როგორმე გადაჭრა მძიმე წონის პროცესებით? Რა თქმა უნდა. დაგეგმვის სხვა სახეობას ე.წუმოკლეს სამუშაო პირველი (SJF). მისი ალგორითმიც საკმაოდ პრიმიტიულია - როგორც სახელი გულისხმობს, უმოკლეს ამოცანები პირველ რიგში, ერთმანეთის მიყოლებით დაიწყება.

ამ მაგალითში, იგივე პროცესების გაშვების შედეგი იქნება პროგრამის შემობრუნების საშუალო დროის გაუმჯობესება და ტოლი იქნება 50-ის ნაცვლად 110, რაც თითქმის 2-ჯერ უკეთესია.

ამრიგად, მოცემული დაშვებისთვის, რომ ყველა დავალება ერთდროულად მოდის, SJF ალგორითმი, როგორც ჩანს, ყველაზე ოპტიმალური ალგორითმია. თუმცა, ჩვენი ვარაუდები ჯერ კიდევ არ ჩანს რეალისტური. ამჯერად ჩვენ ვცვლით ვარაუდს 2 და ამჯერად წარმოვიდგენთ, რომ ამოცანები შეიძლება იყოს ნებისმიერ დროს და არა ყველა ერთდროულად. რა პრობლემები შეიძლება გამოიწვიოს ამან?

წარმოვიდგინოთ, რომ პირველი დავალება A (100c) მოდის და იწყებს შესრულებას. t=10-ზე მოდის B და C ამოცანები, რომელთაგან თითოეულს 10 წამი დასჭირდება. მაშ ასე, შესრულების საშუალო დრო არის (100+(110-10)+(120-10))3 = 103. რა შეიძლება გააკეთოს განრიგმა ამის გასაუმჯობესებლად?

უმოკლეს დრო დასრულებამდე პირველი (STCF)

სიტუაციის გასაუმჯობესებლად, ჩვენ გამოვტოვებთ მე-3 ვარაუდს, რომ პროგრამა დაწყებულია და მუშაობს დასრულებამდე. გარდა ამისა, ჩვენ დაგვჭირდება ტექნიკის მხარდაჭერა და, როგორც თქვენ ალბათ მიხვდებით, გამოვიყენებთ ტაიმერი გაშვებული დავალების შეწყვეტა და კონტექსტის გადართვა. ამგვარად, განრიგს შეუძლია გააკეთოს რაღაც B, C დავალებების ჩამოსვლის მომენტში - შეაჩეროს A დავალების შესრულება და B და C დავალებები გადაიტანოს დამუშავებაში და მათი დასრულების შემდეგ განაგრძოს A პროცესის შესრულება. ასეთ განრიგს ე.წ. STCFან პრევენციული სამუშაო პირველი.

ამ დამგეგმავის შედეგი იქნება შემდეგი შედეგი: ((120-0)+(20-10)+(30-10))/3=50. ამრიგად, ასეთი გრაფიკი კიდევ უფრო ოპტიმალური ხდება ჩვენი ამოცანებისთვის.

მეტრიკული რეაგირების დრო

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

პასუხის დრო გამოითვლება შემდეგნაირად:

Tresponse=Tfirstrun−Tarrival

ამრიგად, წინა მაგალითისთვის, პასუხის დრო იქნება: A=0, B=0, C=10 (abg=3,33).

და გამოდის, რომ STCF ალგორითმი არც ისე კარგია იმ სიტუაციაში, როდესაც 3 დავალება ერთდროულად მოდის - მას მოუწევს ლოდინი, სანამ მცირე ამოცანები მთლიანად დასრულდება. ასე რომ, ალგორითმი კარგია შემობრუნების დროის მეტრიკისთვის, მაგრამ ცუდია ინტერაქტიულობის მეტრიკისთვის. წარმოიდგინეთ, რომ ტერმინალთან იჯექით, ცდილობდით აკრიფოთ სიმბოლოები რედაქტორში და მოგიწიათ 10 წამზე მეტი ლოდინი, რადგან სხვა დავალება იკავებდა CPU-ს. არ არის ძალიან სასიამოვნო.

ასე რომ, ჩვენ კიდევ ერთი პრობლემის წინაშე ვდგავართ - როგორ შევქმნათ გრაფიკი, რომელიც მგრძნობიარეა რეაგირების დროზე?

მრგვალი რობინ

ამ პრობლემის გადასაჭრელად შეიქმნა ალგორითმი მრგვალი რობინ (RR). ძირითადი იდეა საკმაოდ მარტივია: იმის ნაცვლად, რომ დავასრულოთ დავალება, სანამ ისინი არ დასრულდება, ჩვენ დავასრულებთ დავალებას გარკვეული პერიოდის განმავლობაში (ე.წ. დროის მონაკვეთი) და შემდეგ რიგიდან სხვა დავალებაზე გადავდივართ. ალგორითმი იმეორებს თავის მუშაობას ყველა დავალების დასრულებამდე. ამ შემთხვევაში, პროგრამის გაშვების დრო უნდა იყოს იმ დროის მრავალჯერადი, რის შემდეგაც ტაიმერი შეწყვეტს პროცესს. მაგალითად, თუ ტაიმერი წყვეტს პროცესს ყოველ x=10ms, მაშინ პროცესის შესრულების ფანჯრის ზომა უნდა იყოს 10-ის ჯერადი და იყოს 10,20 ან x*10.

მოდით შევხედოთ მაგალითს: ABC ამოცანები სისტემაში ერთდროულად მოდის და თითოეულ მათგანს სურს 5 წამის განმავლობაში გაშვება. SJF ალგორითმი დაასრულებს თითოეულ დავალებას მეორეს დაწყებამდე. ამის საპირისპიროდ, RR ალგორითმი გაშვების ფანჯრით = 1s გაივლის ამოცანებს შემდეგნაირად (ნახ. 4.3):

(SJF ისევ (ცუდი რეაგირების დროისთვის)

(Round Robin (კარგია რეაგირების დროისთვის)

საშუალო პასუხის დრო RR ალგორითმისთვის არის (0+1+2)/3=1, ხოლო SJF (0+5+10)/3=5.

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

RR შესანიშნავი გრაფიკია, თუ ვსაუბრობთ მხოლოდ რეაგირების დროის მეტრიკაზე. მაგრამ როგორ მოიქცევა ამოცანის შემობრუნების დროის მეტრიკა ამ ალგორითმით? განვიხილოთ ზემოთ მოყვანილი მაგალითი, როდესაც მოქმედების დრო A, B, C = 5s და მიდის ამავე დროს. ამოცანა A დასრულდება 13-ზე, B 14-ზე, C-ზე 15 წმ-ზე და საშუალო შემობრუნების დრო იქნება 14 წამი. ამრიგად, RR არის ყველაზე ცუდი ალგორითმი ბრუნვის მეტრიკისთვის.

უფრო ზოგადი თვალსაზრისით, ნებისმიერი RR ტიპის ალგორითმი სამართლიანია; ის CPU დროს თანაბრად ყოფს ყველა პროცესს შორის. და ამრიგად, ეს მეტრიკა მუდმივად ეწინააღმდეგება ერთმანეთს.

ამრიგად, ჩვენ გვაქვს რამდენიმე კონტრასტული ალგორითმი და ამავე დროს რჩება რამდენიმე ვარაუდი - რომ დავალების დრო ცნობილია და რომ ამოცანა მხოლოდ CPU-ს იყენებს.

შერევა I/O-სთან

უპირველეს ყოვლისა, მოვიშოროთ ვარაუდი 4, რომ პროცესი მხოლოდ CPU-ს იყენებს; ბუნებრივია, ეს ასე არ არის და პროცესებს შეუძლიათ სხვა აღჭურვილობაზე წვდომა.

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

მოდით შევხედოთ რამდენიმე პრობლემის მაგალითს. თითოეულ მათგანს სჭირდება 50 ms CPU დრო. თუმცა, პირველს ექნება წვდომა I/O ყოველ 10ms-ში (რომელიც ასევე შესრულდება ყოველ 10ms-ში). და პროცესი B უბრალოდ იყენებს 50ms პროცესორს I/O-ს გარეშე.

ამ მაგალითში ჩვენ გამოვიყენებთ STCF განრიგს. როგორ მოიქცევა დამგეგმავი, თუ მასზე A-ს მსგავსი პროცესი დაიწყება? ის გააკეთებს შემდეგს: ჯერ მთლიანად შეიმუშავებს A პროცესს, შემდეგ კი B-ს.

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

Oracle აღარ არის

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

სულ

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

წყარო: www.habr.com