Въведение в операционните системи

Хей Хабр! Бих искал да предложа на вашето внимание поредица от статии-преводи на една интересна според мен литература - OSTEP. Този материал обсъжда доста дълбоко работата на unix-подобни операционни системи, а именно работата с процеси, различни планировчици, памет и други подобни компоненти, които съставляват съвременна операционна система. Можете да видите оригинала на всички материали тук тук. Моля, имайте предвид, че преводът е направен непрофесионално (съвсем свободно), но се надявам да съм запазил общия смисъл.

Лабораторните работи по темата можете да намерите тук:

• оригинала
• оригинала
• моята лична адаптация

Други части:

• Част 1: Въведение
• Част 2: Абстракция: Процесът
• Част 3: Въведение в API на процеса
• Част 4: Въведение в Scheduler

Можете също да разгледате канала ми на телеграма =)

Въведение в Scheduler

Същността на проблема: Как да разработим политика за планиране
Как трябва да бъдат проектирани основните рамки на политиката на планировчика? Какви трябва да са ключовите допускания? Какви показатели са важни? Какви основни техники са използвани в ранните изчислителни системи?

Предположения за работно натоварване

Преди да обсъдим възможни политики, нека първо направим няколко опростяващи отклонения относно процесите, изпълнявани в системата, които се наричат ​​общо натовареност. Дефинирането на натоварването е критична част от изграждането на политики и колкото повече знаете за натоварването, толкова по-добра политика можете да напишете.

Нека направим следните предположения относно процесите, изпълнявани в системата, понякога наричани още работни места (задачи). Почти всички тези предположения не са реалистични, но са необходими за развитието на мисълта.

1. Всяка задача се изпълнява за едно и също време,
2. Всички задачи се поставят едновременно,
3. Възложената задача работи до нейното завършване,
4. Всички задачи използват само CPU,
5. Времето за изпълнение на всяка задача е известно.

Метрики на планировчика

В допълнение към някои предположения за натоварването е необходим друг инструмент за сравняване на различни политики за планиране: показатели на планировчика. Метриката е просто някаква мярка за нещо. Има редица показатели, които могат да се използват за сравняване на планировчици.

Например ще използваме показател, наречен време за изпълнение (време за изпълнение). Времето за изпълнение на задачата се определя като разликата между времето за изпълнение на задачата и времето за пристигане на задачата в системата.

Tturnaround=Tcompletion-Tarrival

Тъй като предположихме, че всички задачи са пристигнали по едно и също време, тогава Ta=0 и следователно Tt=Tc. Тази стойност естествено ще се промени, когато променим горните допускания.

Друг показател - справедливост (справедливост, честност). Производителността и справедливостта често са противоположни характеристики в планирането. Например планировчикът може да оптимизира производителността, но с цената на изчакване изпълнението на други задачи, като по този начин намалява справедливостта.

ПЪРВИ ВЛЕЗЕН, ПЪРВИ ИЗЛЕЗЕН (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 ще бъде най-доброто решение. И някога в ранните времена тези алгоритми работеха доста добре. Сега обаче потребителят прекарва по-голямата част от времето си на терминала и очаква продуктивно интерактивно изживяване. Така се роди нов показател - време за реакция (отговор).

Времето за реакция се изчислява, както следва:

Response=Tfirstrun−Tarrival

По този начин, за предишния пример, времето за реакция ще бъде: A=0, B=0, C=10 (abg=3,33).

И се оказва, че STCF алгоритъмът не е толкова добър в ситуация, в която пристигат 3 задачи едновременно - ще трябва да изчака, докато малките задачи бъдат напълно изпълнени. Така че алгоритъмът е добър за метриката на времето за изпълнение, но е лош за метриката на интерактивността. Представете си, че седите на терминал и се опитвате да въвеждате знаци в редактор и трябва да чакате повече от 10 секунди, защото друга задача заема процесора. Не е много приятно.

Така че сме изправени пред друг проблем - как можем да изградим планировчик, който е чувствителен към времето за реакция?

конференция

Разработен е алгоритъм за решаване на този проблем конференция (RR). Основната идея е доста проста: вместо да изпълняваме задачи, докато не бъдат завършени, ще изпълняваме задачата за определен период от време (наречен отрязък от време) и след това ще превключим към друга задача от опашката. Алгоритъмът повтаря работата си, докато не бъдат изпълнени всички задачи. В този случай времето за работа на програмата трябва да бъде кратно на времето, след което таймерът ще прекъсне процеса. Например, ако таймерът прекъсва процес на всеки x=10ms, тогава размерът на прозореца за изпълнение на процеса трябва да бъде кратен на 10 и да бъде 10,20 или x*10.

Нека да разгледаме един пример: ABC задачи пристигат едновременно в системата и всяка от тях иска да се изпълни за 5 секунди. SJF алгоритъмът ще завърши всяка задача, преди да започне друга. За разлика от това, RR алгоритъмът с прозорец за стартиране = 1s ще премине през задачите, както следва (фиг. 4.3):

(Отново SJF (лошо за времето за реакция)

(Кръгов режим (Добър за време за реакция)

Средното време за отговор за алгоритъма RR е (0+1+2)/3=1, докато за SJF (0+5+10)/3=5.

Логично е да се предположи, че времевият прозорец е много важен параметър за RR; колкото по-малък е той, толкова по-голямо е времето за реакция. Въпреки това, не трябва да го правите твърде малък, тъй като времето за превключване на контекста също ще играе роля в цялостната производителност. По този начин изборът на време на прозореца за изпълнение се задава от архитекта на ОС и зависи от задачите, които се планират да бъдат изпълнени в него. Превключването на контекста не е единствената операция на услугата, която губи време - работещата програма работи с много други неща, например различни кешове, и при всяко превключване е необходимо да се запази и възстанови тази среда, което също може да отнеме много време.

RR е страхотен планировчик, ако говорим само за метриката на времето за реакция. Но как ще се държи показателят за времето за изпълнение на задачата с този алгоритъм? Помислете за примера по-горе, когато времето за работа на A, B, C = 5s и пристигат по едно и също време. Задача A ще приключи в 13, B в 14, C в 15s и средното време за изпълнение ще бъде 14s. По този начин RR е най-лошият алгоритъм за показателя за оборот.

По-общо казано, всеки алгоритъм от тип RR е справедлив; той разпределя процесорното време по равно между всички процеси. И по този начин тези показатели постоянно са в конфликт помежду си.

По този начин имаме няколко контрастни алгоритъма и в същото време все още остават няколко допускания - че времето на задачата е известно и че задачата използва само процесора.

Смесване с I/O

Първо, нека премахнем предположение 4, че процесът използва само процесора; естествено, това не е така и процесите имат достъп до друго оборудване.

В момента, в който който и да е процес поиска I/O операция, процесът влиза в блокирано състояние, чакайки I/O да завърши. Ако I/O се изпрати към твърдия диск, тогава такава операция може да отнеме до няколко ms или повече и процесорът ще бъде неактивен в този момент. През това време планировчикът може да заема процесора с всеки друг процес. Следващото решение, което планировчикът ще трябва да вземе, е кога процесът ще завърши своя I/O. Когато това се случи, ще възникне прекъсване и операционната система ще постави процеса, който е извикал I/O, в състояние на готовност.

Нека да разгледаме пример за няколко проблема. Всеки от тях изисква 50ms процесорно време. Първият обаче ще осъществява достъп до I/O на всеки 10 ms (които също ще се изпълняват на всеки 10 ms). И процес B просто използва 50ms процесор без I/O.

В този пример ще използваме STCF Scheduler. Как ще се държи планировчикът, ако на него се стартира процес като A? Той ще направи следното: първо ще изработи напълно процес А, а след това процес Б.

Традиционният подход за решаване на този проблем е всяка подзадача от 10 ms на процес A да се третира като отделна задача. По този начин, когато стартирате с алгоритъма STJF, изборът между задача от 50 ms и задача от 10 ms е очевиден. След това, когато подзадача A бъде завършена, процес B и I/O ще бъдат стартирани. След завършване на I/O ще бъде обичайно да стартирате 10ms процес A отново вместо процес B. По този начин е възможно да се приложи припокриване, при което CPU се използва от друг процес, докато първият чака I/O. И в резултат на това системата се използва по-добре - в момента, в който интерактивните процеси чакат I/O, други процеси могат да се изпълняват на процесора.

Оракулът вече го няма

Сега нека се опитаме да се отървем от предположението, че времето за изпълнение на задачата е известно. Това като цяло е най-лошото и нереалистично предположение в целия списък. Всъщност, в средната обикновена операционна система самата операционна система обикновено знае много малко за времето за изпълнение на задачите, така че как тогава можете да създадете планировчик, без да знаете колко време ще отнеме изпълнението на задачата? Може би бихме могли да използваме някои принципи на RR, за да разрешим този проблем?

Общо

Разгледахме основните идеи за планиране на задачи и разгледахме 2 семейства програмисти. Първият стартира първо най-кратката задача и така увеличава времето за изпълнение, докато вторият е разкъсан между всички задачи поравно, увеличавайки времето за реакция. И двата алгоритъма са лоши, когато алгоритмите от другото семейство са добри. Разгледахме също как паралелното използване на CPU и I/O може да подобри производителността, но не решихме проблема с ясновидството на OS. А в следващия урок ще разгледаме плановик, който гледа в близкото минало и се опитва да предвиди бъдещето. И се нарича многостепенна опашка за обратна връзка.

Източник: www.habr.com