от razor(24-06-2005)

рейтинг (31)   [ добре ]  [ зле ]

Printer Friendly Вариант за отпечатване

     Алгоритми за разпределяне на процесорното
  време в 4.4BSD, Linux ядра 2.4,2.6.

Много е важно да се определи ясна граница между механизъм и политика на разпределяне на процесорното време. Защо ? Защото ако имаме един процес с много деца и някои от децата са по-важни от други, механизма не може да разбере кое е по-важно и може да даде по малък приоритет на по-важно дете. Поради тази причина е дадена възможността на процеса да си определя кое дете е по важно.
Всяка модерна операционна система поддържа многозадачност, тъй като повечето домашни компютри са еднопроцесорни, във всеки даден момент се извършва
точно една задача (изпълнява се точно 1 програма). За да се постигне  многозадачност с 1 процесор са
необходими някакви алгоритми, по които да се дава контрол на различните процеси, които са стартирани - тези алгоритми се наричат "Алгоритми за разпределяне на процесорното време".
Това което ще се опитам да обясня е как точно се извършва този процес и какъв е алгоритъма, по които той се извършва в 4.4BSD (Lite-2 от 1995), Linux ядра 2.4 и 2.6.

Примерите ми ще са базирани на x86 архитектура с един процесор. Така, ако имате 3 процеса пуснати, както вече казах в даден момент се изпълнява само един от тях, тъй като при пускане на някакъв процес, той се зарежда в паметта на компютъра(изцяло или частично) и се изпълнява, но естествено когато сте си пуснали графична среда например, не изчаквате тя да спре, за да си пуснете някакъв текстов редактор и поради това, че се изпълнява само по един процес във всеки момент се налага смяна между различните процеси, за да може да се създава илюзията, че вървят конкурентно много процеси. Смяната между процесите, които се изпълняват е силно зависима от архитектурата. Тъй като смяната между различните процеси се прави често, то е добре да е много бърза операция, за да може да се прекара повече време в изпълнение на потребителски задачи, от колкото в ядрото.

Сега да видим как тази смяна се извършва в BSD & Linux.
4.4BSD-Lite2 пуснат между 95-96 година, е ядро
което поддържа многозадачност (тази илюзия, за която говорех).  
То използва алгоритъм базиран на приоритети, който е "по-добър" към интерактивните програми от колкото към програмите, които изискват много процесорно време за изпълнение. Алгоритъма дава първоначално висок приоритет на всеки процес и му дава възможност да се изпълнява за определен период от време. Според това колко от времето си е изразходвал дадения процес - ако се е изпълнявал през цялото време му се намаля приоритета, а ако е извършвал  I/O операции или е освободил процесора доброволно, той си остава на същия приоритет. Една от целите на алгоритъма е да се освободи от явлението наречено "thrashing", което означава смяна на много процеси за малко време, поради което не остава време на тези процеси да се изпълняват.

В 4.4BSD има няколко състояния на процесите
SIDL – междинно състояние в създаването на процеса
SRUN – процес който може да бъде пуснат
SSLEEP – чакащ дадено събитие да се случи
SSTOP – Процес които е спрян или “следен”
SZOMB – междинно състояние в унищожаването на процеса

Процесите са организирани в два листа:
1. allproc - където са всички процеси, които могат да бъдат пускани
2. zombproc - процеси, които са в състояние SZOMB. Това разделяне на процесите намалява значително времето, за което се преглеждат всички процеси, който може да бъдат
пуснати. Също така има още 2 групи:
1. процеси готови за изпълнение (SRUN)
2. процеси, които спят защото чакат някакво събитие (SSLEEP)

Приоритетите за потребителски процеси в 4.4BSD варират от PUSER(50) до 127. Колкото по малък е приоритета, за толкова по висок се смята. Доброволното освобождаване на процесора става с извикване на sleep(), а недоброволното се извършва с mi_switch() и setrunnable(). Тъй като процесите са с различни приоритети, то за всеки приоритет в 4.4BSD има лист с процеси.
Когато се наложи смяна на процес този лист се обхожда от най - високия до най - ниския приоритет и се пуска първия намерен процес. Ако в даден лист на приоритет има повече от 1 процес, то процесите в него се пускат един след друг. Времето, което е първоначално дадено на всеки процес е 0.1с. Системата сменя приоритетите на процесите динамично, за да може да се
възползва най - добре от ресурсите, с които разполага. Приоритета на даден процес се определя с 2 променливи, които се съдържат в структурата му: p_estcpu и p_nice. p_estcpu е колко процесорно време е
ползвал скоро дадения процес, а p_nice е променлива, която варира между -20 и 20 (по подразбиране е 0) и се задава от потребителя. Приоритета на всеки процес се преизчислява през 4 часовникови “tick”-а (около 40 ms) по
специална формула (p_usrpri = PUSER + [ p_estcpu/4 ] + 2 x p_nice)
Ако приоритета е по голям от 127, то той се слага на 127, ако е по малък от минималния PUSER(50), то той се изравнява на толкова. Използването на процесора се изчислява също по специална формула (p_estcpu = (2 x load)/(2 x load
+1) x p_estcpu + p_nice)
Това е в най - общи линии как се определя кой процес да е следващия в 4.4BSD ядрото.  

Сега ще обясня този процес в 2.4 и 2.6 Linux ядра.
В серия 2.4 на linux, процесите са свързани по два начина - 1. Като кръгов двойно свързан списък с "prev_task" като предния процес и "next_task" като следващия и 2. като hash таблица, като hash ключ е “pid”-а на дадения процес. Има още два списъка с процеси, в първия са всички процеси, а втория , които се казва "runqueue" са процесите, които са готови за изпълнение (т.е. са в състояние TASK_RUNNING, ще обясня състоянията, по
нататък). Тук алгоритъма за разпределяне на процесорното време също използва приоритети и разделяне на процесорното време. Тези приоритети се
сменят динамично според това, което се извършва от дадения процес. Например ако имаме един
текстови редактор вървящ и един филм, редактора ще е с по висок приоритет, защото е интерактивен процес. Все още в Linux 2.4 процес не може да бъде прекъсван докато се изпълнява в ядрото (както в 4.4BSD).
Всеки процес си има начален дял от времето, той може да се регулира от nice и setpriority. "nice" се използва най - вече да се намали приоритета на процеса (въпреки че се ползва доста рядко :), ако има стойност по
голяма от 40, тя става равна на 40, а ако е отрицателна (т.е. иска да се увеличи приоритета на процеса) се налага процеса да се пусне като супер потребител. Началния дял се изчислява по следната формула "20*HZ/100", където HZ е интервала на прекъсванията на таймер-а, които за x86 архитектура обикновено е 100 (в 2.6 e 1000).
Дяла, които се дава на процеса е много важен за бързината на цялата
система, ако например, за да се смени процес се изискват 10-15
милисекунди и дяла на процесите е малък, половината процесорно време, което иначе може да се
изразходва за изпълнение на някакъв процес, се изразходва за смяна между различните процеси, другия вариант е ако дяла е прекалено голям, тогава
тази илюзия за паралелна работа изчезва. Сега да разгледаме състоянията, които споменах по рано.
Тук състоянията на процесите могат да бъдат:
TASK_RUNNING - задача, която върви или е годна да бъде избрана.
TASK_INTERRUPTIBLE - задача, която спи, но може да бъде събудена от timer или сигнал
TASK_UNINTERRUPTIBLE - задача, която не може да бъде събудена.
TASL_ZOMBIE - задача, която е била спряна, но не е завършила все още.
TASK_STOPPED - задача, която е спряна от ptrace или от signal.
В Linux за разлика от 4.4BSD има възможност за стартиране на процеси изискващи изпълнение в реално време, тези процеси имат определен срок за
това, което вършат и се разделят на два вида - Hard real-time и Soft
real-time. Както говорят имената Hard real-time НЕ трябва да се
нарушават тези срокове, а на soft са позволени малки отклонения. В Linux
2.4 има три политики за разпределяне на процесорно време:
1. SCHED_FIFO
 First-in, First-out real-time политика.
2. SCHED_RR
 Round-robin real-time политика.
3. SCHED_OTHER
 Това е нормалната политика за всички останали процеси.
При real-time процесите приоритета варира между 0 и 99 и
е статичен, за разлика от нормалните процеси, на които се изчислява динамично. Една малка подробност, чрез "sched_yield", може да се освободи процесора доброволно, а процеса, които го извиква се слага
накрая на "runqueue" (и си остава в "TASK_RUNNING" състояние). Поради това, че Linux 2.4 е вече остарял като идеи, мисля, че това е достатъчно.
Сега ще ви запозная с алгоритмите за разпределяне на процесорното време в Linux ядро 2.6, най - новата стабилна серия на Linux. Тук наистина
ядрото е докарано до едно доста добро състояние, защото има доста оптимизации, които сега ще разгледаме.
В 2.6 отново I/O процеси са с по голям приоритет от тези използващи много  процесора. Отново има приоритети и “nice” стойност, която може да им въздейства. Тук има 2 приоритетни списъка – един активен и един неактивен. Отделно за всеки приоритет има списък с процеси, ако има повече от 1 процес на даден приоритет се изпълняват един след друг (както при BSD и Linux 2.4). Тук има един важен момент с двата приоритетни списъка, за да не се повтаря грешката на Linux 2.4, която обхожда всичките процеси и им преизчислява процесорното време, тук когато на даден процес му свърши времето (стане 0), то се преизчислява и тогава процеса се мести в списъка с неактивните процеси, което означава, че преизчисляването на процесите става с едно бързо действие – просто се сменят два указателя (на активния списък и на неактивния). Начина, по които се разбира дали даден процес е I/O или използва процесора много, е да се гледа колко време процеса отделя за “спане” (sleep), ако времето е много това означава, че процеса е I/O, ако е малко означава че е така наречена “процесорна хрътка”. Началното процесорно време е равно на половината на времето на процеса баща. Минимума време, което може да получи даден процес е 10 ms (до ядро 2.6.9, от 2.6.9 е 5 ms), нормално е 100 ms,а максимума е 200 ms(отново до ядро 2.6.9, от 2.6.9 е 800 ms), което означава, че процеса е много интерактивен. Една от новите и най – важни функции, която е имплементирана в 2.6 е възможността за прекъсване на даден процес докато се изпълнява код на ядрото (т.е. Процеса например е направил някакво системно извикване и така изпълнението навлиза в ядрото). Това е много важно и много малко Unix варианти могат да го правят, обикновено процесите се прекъсват само докато си изпълняват собствения код в потребителското пространство. Linux 2.6 също предлага real-time алгоритми. Те са същите като в Linux 2.4, т.е. един, които пуска Real-Time процесите един след друг и друг, който е First-In First-out (или FIFO). Real-time процесите са с по висок приоритет от нормалните процеси, техните приоритети варират от 0 до 99. Мисля, че това показва в съвсем малки части какво представлява политиката за разпределяне на процесорно време в тези ядра. Естествено по въпроса има още много информация, която може да бъде казана. Това е съвсем малка част от темата тъй като това е основна тема в разработването на ядра и много важна част за представянето на ядрото.

BOOKS (only in english):
“Operating Systems – Design and Implementation (part 2)” - Andrew Tanenbaum & Albert Woodhull (one of the best books)
“Linux Kernel Development” - Robert Love (kernel 2.6)
“4.4BSD – Design & Implementation” - Marshal Kirk McKusick, Keith Bostic, Michael Karels & John Quarterman
“Linux Device Drivers” - Alessandro Rubini & Jonathan Corbet (kernel 2.4)
“Understanding the Linux Kernel” - Daniel P. Bovet & Marco Cesatti (kernel 2.4)  

NOTES:
1.Съжалявам ако има проблеми с превода (lat -> cyr), правен е на уеб преводач, защото нямах възможност да я напиша на кирилица. Ако има неточности или искате повече информация можете да се свържете с мен на моят e-mail
2. Интерактивен процес е този, който си взаимодейства с потребителя.
3.I/O – Входно/изходен


<< Динамична промяна на работната честота на АМД К7 | Адаптивността като път към сигурността >>