Планиране в интерактивни системи, fkn antitotal
Основни раздели
Циклично планиране.
Един от най-старите, най-простите, най-справедливите и най-често използваните е алгоритъмът за циклично планиране.На всеки процес е дадено определено време на процесора, така нареченият отрязък от време. Ако процесът все още работи в края на отрязъка от време, той се прекратява и управлението се прехвърля към друг процес. Разбира се, ако процесът блокира или прекрати преждевременно, преходът се извършва в този момент. Внедряването на кръговия график е просто. Планировчикът трябва само да поддържа списъка с процеси в състояние на готовност. Когато даден процес изчерпи своето времево ограничение, той отива в края на списъка.Единственото интересно нещо за този алгоритъм е дължината на кванта. Превключването от един процес към друг отнема известно време - трябва да запазите и заредите регистри и карти на паметта, да актуализирате таблици и списъци, да запазите и презаредите кеша на паметта и т.н. Заключението може да се формулира по следния начин:твърде малкият квант ще доведе до често превключване на процеси и ниска ефективност, но твърде големият квант може да доведе до бавен отговор на кратки интерактивни заявки. Квантова стойност от около 2 0 -5 0 ms често е причина способен на компромис.
Приоритетно планиране.
Има важно предположение в алгоритъма за кръгово планиране, че всички процеси са еквивалентни. В компютърна ситуация с голям брой потребители това може да не е така. Например в университета трябва да се обслужват на първо място деканите, след това професорите, секретарките, чистачките и чак след това студентите (не е ясно само защо деканите са преди студентите - университетът е за студенти!!).Необходимостта да се вземат предвид такива външни фактори води до приоритетно планиране. Основната идея е проста: на всеки процес се присвоява приоритет и контролът се прехвърля към процеса с най-висок приоритет, който е готов за изпълнение.
Множество опашки.
Един от първите приоритетни програмисти беше внедрен в CTSS (съвместима система със споделено време).Основният проблем със системата CTSS беше, че превключването на процеси беше твърде бавно, тъй като само един процес можеше да бъде в паметта на IBM 7094 компютър. Всяко превключване означава размяна на текущия процес на диск и четене на нов процес от диска. Разработчиците на CTSS бързо разбраха, чеефективността ще бъде по-добра, ако процесите, обвързани с процесора, получат по-голям времеви отрязък отколкото ако им бъдат дадени малки отрязъци, но често. От една страна, това ще намали броя на суапове от памет към диск, а от друга ще доведе до по-лошо време за реакция, както вече видяхме.
В резултат на това беше разработенорешение с приоритетни класове. На процесите в класа с най-висок приоритет беше даден един квант, на процесите в следващия клас бяха дадени два кванта, на процесите в следващия клас бяха дадени четири кванта и т.н.
Като пример, разгледайте процес, който трябва да извърши изчисления за 100 кванта. Първо ще му бъде даден един квант, след което ще бъде изпомпван на диск. Следващият път, когато получи 2 кванта, след това 4, 8.16, 32, 64, въпреки че от 64 той използва само 37. В този случай ще са необходими само 7 помпи (включително първоначалното натоварване) вместо 100, които биха били необходими, ако се използва кръгов алгоритъм.Освен това, докато се гмурнете в опашката с приоритети, процесът ще се изпълнява по-рядко, оставяйки процесора на по-кратки процеси.
„Най-краткият процес е следващият“
Тъй като алгоритъмът Shortest Task First минимизира средното време за изпълнение в системите за пакетна обработка, бихме искали да го използваме и в интерактивни системи. До известна степен това е възможно.Интерактивните процеси най-често следват модела „изчакване на команда, изпълнение на команда, изчакване на команда, изпълнение на команда“. » Като третирате всяка команда като отделна задача, можете да минимизирате общото средно време за реакция, като изпълните първо най-кратката задача.Единственият проблем е да разберете кой процес на изчакване е най-кратък.
Един метод разчита на оценка на продължителността на процес въз основа на предишното поведение на процеса. Това стартира процеса с най-краткото очаквано време. Да приемем, че очакваното време за изпълнение на командата е T0, а очакваното време на следващото изпълнение е T1. Човек може да подобри оценката на времето, като вземе претеглената сума на тези времена aT0 + (1 - a)T1. Избирайки подходяща стойност на a, можем да накараме алгоритъма за оценка бързо да забрави за предишни изпълнения или, обратно, да ги помни за дълго време. Като вземем a = 1/2, получаваме поредица от оценки:
След три изпълнения теглото на T0 в оценката ще намалее до 1/8.
Методът за оценяване на следващата стойност в серия чрез среднопретеглената стойност на предишната стойност и предишната оценка често се нарича стареене. Този метод е приложим в много ситуации, когато е необходимо да се направи оценка от предишни стойности. Най-лесният начин за прилагане на стареене е, когато a = 1/2. На всяка стъпка просто трябва да добавите нова към текущата оценкастойност и разделете сумата наполовина (преместване надясно с 1 бит).
Гарантирано планиране.
Принципно различен подход към планирането е да се дадат реални обещания на потребителите и след това да се изпълнят. Ето едно обещание, което е лесно да се каже и лесно да се спази:Ако n потребители споделят процесора с вас, ще ви бъде дадена 1/n мощност на процесора.
А в система с един потребител и n работещи процесора, всеки получава 1/n процесорни цикъла. За да изпълни това обещание, системата трябва да следи разпределението на процесора между процесите от момента на създаването на всеки процес. След това системата изчислява количеството CPU ресурси, на които процесът има право, като например времето от създаването, разделено на n. Сега можем да изчислим съотношението на времето, предоставено на процеса, към времето, на което той има право. Получената стойност от 0,5 означава, че на процеса е разпределена само половината от това, което е трябвало, а 2,0 означава, че процесът е получил два пъти повече, отколкото е трябвало. След това процесът, който има най-малко съотношение, се стартира, докато стане по-голямо от това на най-близкия му съсед.
планиране на лотария.
Алгоритъмът се основава наразпределяне на лотарийни билети на процеси за достъп до различни ресурси, включително процесора. Когато планировчикът трябва да вземе решение, лотариен билет се избира на случаен принцип и собственикът му получава достъп до ресурса. По отношение на достъпа до процесора, „лотарията“ може да се случи 50 пъти в секунда, а победителят получава 20 ms процесорно време.
По-важните процеси могат да получат допълнителни билети, за да се увеличи шансът за печалба. Ако има общо 100 билета и 20 от тях са ведин процес, тогава той ще получи 20% от процесорното време. За разлика от приоритетното планиране, където е много трудно да се прецени какво означава, да речем, приоритет 40, при планирането на лотарията всичко е ясно. Всеки процес ще получи процент от ресурсите, приблизително равен на процента билети, които има.
Планирането на лотарията има няколко интересни свойства.Например, ако даден процес получи няколко билета по време на създаването, тогава в следващата лотария шансовете му за печалба са пропорционални на броя на билетите.
Коопериращите се процеси могат да обменят билети, ако е необходимо. Така, ако клиентски процес изпрати съобщение до сървърен процес и след това блокира, той може да предаде всичките си билети на сървърния процес, за да увеличи шанса за стартиране на сървъра. Когато процесът на сървъра приключи, той може да върне всички билети обратно.
Справедливо планиране.
Досега приемахме, че всеки процес се управлява, независимо кой е собственикът му. Следователно, ако потребител 1 създаде 9 процеса и потребител 2 създаде 1 процес, тогава с помощта на кръгов режим или в случай на равни приоритети, потребител 1 ще получи 90% от процесора, а потребител 2 само 10.
За да се избегнат подобни ситуации,някои системи обръщат внимание на собственика на процеса преди планиране. В този модел всеки потребител получава дял от процесора и планировчикът избира процеса според този факт.Ако в нашия пример на всеки от потребителите беше обещано 50% от процесора, тогава те ще получат 50% от процесора, независимо от броя на процесите.