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

Здраво, Хабр! Би сакал да ви претставам низа написи-преводи на една според мене интересна литература - ОСТЕП. Овој материјал прилично длабоко ја испитува работата на оперативните системи слични на Unix, имено, работата со процеси, различни распоредувачи, меморија и други слични компоненти кои го сочинуваат модерен оперативен систем. Оригиналот на сите материјали можете да го видите овде тука. Имајте предвид дека преводот е направен непрофесионално (сосема слободно), но се надевам дека го задржав општото значење.

Лабораториска работа на оваа тема може да се најде овде:

Други делови:

Можете исто така да го проверите мојот канал на телеграма =)

Вовед во Распоредувач

Суштината на проблемот: Како да се развие политика за распоредување
Како треба да се дизајнираат основните рамки на политиката на распоредувачот? Кои треба да бидат клучните претпоставки? Кои метрики се важни? Кои основни техники се користеле во раните компјутерски системи?

Претпоставки за обемот на работа

Пред да разговараме за можните политики, ајде прво да направиме неколку поедноставни дигресии за процесите што се извршуваат во системот, кои колективно се нарекуваат обемот на работа. Дефинирањето на обемот на работа е критичен дел од градењето политики, и колку повеќе знаете за обемот на работа, толку подобра политика можете да ја напишете.

Ајде да ги направиме следните претпоставки за процесите што се извршуваат во системот, понекогаш и наречени работни места (задачи). Речиси сите овие претпоставки не се реални, но се неопходни за развој на мислата.

Секоја задача работи исто време,
Сите задачи се поставени истовремено,
Зададената задача работи до нејзиното завршување,
Сите задачи користат само процесор,
Времето на извршување на секоја задача е познато.

Метрика на распоредувачот

Покрај некои претпоставки за оптоварувањето, потребна е уште една алатка за споредување на различни политики за распоред: метрика на распоредувачот. Метриката е само одредена мерка за нешто. Постојат голем број на метрики што може да се користат за споредување на распоредувачите.

На пример, ќе користиме метрика наречена време на пресврт (време на пресврт). Времето на завршување на задачата е дефинирано како разлика помеѓу времето на завршување на задачата и времето на пристигнување на задачата во системот.

Tturnaround=Tcompletion−Tarrival

Бидејќи претпоставивме дека сите задачи пристигнаа во исто време, тогаш Ta=0 и со тоа Tt=Tc. Оваа вредност природно ќе се промени кога ќе ги промениме горенаведените претпоставки.

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

ПРВ ВО ПРВ ИЗЛЕЗ (ФИФО)

Најосновниот алгоритам што можеме да го имплементираме се нарекува FIFO или прв дојден (влезе), прв услужен (излезе). Овој алгоритам има неколку предности: многу е лесен за имплементација и одговара на сите наши претпоставки и ја врши работата доста добро.

Ајде да погледнеме едноставен пример. Да речеме, 3 задачи беа поставени истовремено. Но, да претпоставиме дека задачата А пристигнала малку порано од сите други, така што ќе се појави во списокот за извршување порано од другите, исто како B во однос на C. Да претпоставиме дека секоја од нив ќе биде извршена по 10 секунди. Колку ќе биде просечното време за завршување на овие задачи во овој случај?

Со броење на вредностите - 10+20+30 и делење со 3, го добиваме просечното време на извршување на програмата еднакво на 20 секунди.
Сега да се обидеме да ги промениме нашите претпоставки. Конкретно, претпоставката 1 и затоа веќе нема да претпоставуваме дека на секоја задача и е потребно исто време за извршување. Како ќе настапи ФИФО овој пат?

Како што се испоставува, различните времиња на извршување на задачите имаат исклучително негативно влијание врз продуктивноста на алгоритмот FIFO. Да претпоставиме дека задачата А ќе треба да заврши 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. Така, таков распоредувач станува уште пооптимален за нашите задачи.

Метричко време на одговор

Така, ако го знаеме времето на извршување на задачите и дека овие задачи користат само процесор, STCF ќе биде најдоброто решение. И еднаш во раните времиња, овие алгоритми работеа доста добро. Сепак, корисникот сега го поминува поголемиот дел од своето време на терминалот и очекува продуктивно интерактивно искуство. Така се роди нова метрика - време на одговор (одговор).

Времето на одговор се пресметува на следниов начин:

Tresponse=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 (лошо за време на одговор)

(Round Robin (добро за време на одговор)

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

Логично е да се претпостави дека временскиот прозорец е многу важен параметар за RR; колку е помал, толку е поголемо времето на одговор. Сепак, не треба да го правите премногу мал, бидејќи времето за префрлување на контекстот исто така ќе игра улога во севкупните перформанси. Така, изборот на времето на прозорецот за извршување го поставува архитектот на ОС и зависи од задачите што се планираат да се извршат во него. Префрлувањето контекст не е единствената услуга која губи време - програмата што работи работи на многу други работи, на пример, разни кешови, и со секој прекинувач е неопходно да се зачува и обнови оваа средина, што исто така може да потрае многу време.

RR е одличен распоредувач ако зборуваме само за метриката за време на одговор. Но, како ќе се однесува метриката за време на пресврт на задачата со овој алгоритам? Размислете за примерот погоре, кога времето на работа на A, B, C = 5s и пристигне во исто време. Задачата А ќе заврши во 13, Б во 14, С во 15 секунди и просечното време на пресврт ќе биде 14 секунди. Така, RR е најлошиот алгоритам за метриката на прометот.

Во поопшта смисла, секој алгоритам од типот RR е фер; тој го дели времето на процесорот подеднакво помеѓу сите процеси. И така, овие метрики постојано се во конфликт една со друга.

Така, имаме неколку контрастни алгоритми и во исто време остануваат уште неколку претпоставки - дека времето на задачата е познато и дека задачата го користи само процесорот.

Мешање со I/O

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

Во моментот кога кој било процес бара I/O операција, процесот влегува во блокирана состојба, чекајќи да заврши I/O. Ако влезот/излезот се испрати на хард дискот, тогаш таквата операција може да потрае до неколку ms или подолго, а процесорот ќе биде неактивен во овој момент. За тоа време, распоредувачот може да го окупира процесорот со кој било друг процес. Следната одлука што распоредувачот ќе треба да ја донесе е кога процесот ќе го заврши својот I/O. Кога тоа ќе се случи, ќе дојде до прекин и ОС ќе го стави процесот што го повика I/O во подготвена состојба.

Ајде да погледнеме пример за неколку задачи. Секој од нив бара 50 ms време на процесорот. Сепак, првиот ќе пристапува до I/O на секои 10ms (што исто така ќе се извршува на секои 10ms). И процесот Б едноставно користи процесор од 50 ms без I/O.

Во овој пример ќе го користиме распоредувачот на STCF. Како ќе се однесува распоредувачот ако на него се стартува процес како А? Тој ќе го направи следново: прво целосно ќе го разработи процесот А, а потоа ќе го обработи Б.

Традиционалниот пристап за решавање на овој проблем е да се третира секоја подзадача од 10 ms од процесот А како посебна задача. Така, кога се започнува со алгоритмот STJF, изборот помеѓу задача од 50 ms и задача од 10 ms е очигледен. Потоа, кога ќе се заврши подзадачата А, ќе се стартува процесот Б и В/И. Откако ќе заврши I/O, ќе биде вообичаено повторно да се започне процесот А од 10 ms наместо процесот Б. На овој начин, можно е да се имплементира преклопување, каде што процесорот се користи од друг процес додека првиот чека на I/O. И како резултат на тоа, системот е подобро искористен - во моментот кога интерактивни процеси чекаат I/O, може да се извршат други процеси на процесорот.

Ораклот повеќе го нема

Сега да се обидеме да се ослободиме од претпоставката дека времето на извршување на задачата е познато. Ова е генерално најлошата и најнереална претпоставка на целата листа. Всушност, во просечниот обичен оперативен систем, самиот ОС обично знае многу малку за времето на извршување на задачите, па како тогаш можете да изградите распоредувач без да знаете колку време ќе биде потребно за да се изврши задачата? Можеби би можеле да користиме некои RR принципи за да го решиме овој проблем?

Вкупно

Ги разгледавме основните идеи за распоред на задачи и разгледавме 2 семејства на распоредувачи. Првата ја започнува најкратката задача прво и на тој начин го зголемува времето на пресврт, додека втората се дели меѓу сите задачи подеднакво, зголемувајќи го времето на одговор. Двата алгоритми се лоши таму каде што алгоритмите од другата фамилија се добри. Исто така, разгледавме како паралелното користење на процесорот и I/O може да ги подобри перформансите, но не го решивме проблемот со јасновидноста на ОС. И во следната лекција ќе погледнеме во планер кој гледа во непосредното минато и се обидува да ја предвиди иднината. И тоа се нарекува редица за повратни информации на повеќе нивоа.

Извор: www.habr.com

Оперативни системи: Три лесни парчиња. Дел 4: Вовед во распоредувачот (превод)