График на процесора Algorithms in Operaтинг системи

Какво е CPU планиране?

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

Видове планиране на процесора

Ето два вида методи за планиране:

Превантивно планиране

При превантивното планиране задачите най-често се присвояват с техните приоритети. Понякога е важно да се изпълни задача с по-висок приоритет преди друга задача с по-нисък приоритет, дори ако задачата с по-нисък приоритет все още се изпълнява. Задачата с по-нисък приоритет се задържа известно време и се възобновява, когато задачата с по-висок приоритет завърши изпълнението си.

Планиране без изпреварване

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

Кога планирането е превантивно или непревантивно?

За да определите дали планирането е превантивно или не, вземете предвид тези четири параметъра:

1. Процесът превключва от работещо в състояние на изчакване.
2. Конкретен процес превключва от състояние на изпълнение в състояние на готовност.
3. Специфичен процес превключва от състояние на изчакване в състояние на готовност.
4. Процесът завършва изпълнението си и се прекратява.

Ако са изпълнени само условия 1 и 4, планирането се нарича непревантивно. Всички останали ситуации на планиране са превантивни.

Важни термини за планиране на процесора

• Време за избухване/време за изпълнение: Времето, необходимо на даден процес за завършване на изпълнението му. Нарича се още време за изпълнение.
• Час на пристигане: Моментът, в който даден процес влиза в състояние на готовност.
• Крайно време: Моментът, в който даден процес завършва и излиза от системата.
• Мултипрограмиране: Редица програми, които могат да присъстват в паметта едновременно.
• Работни места: Вид програма без никаква намеса от страна на потребителя.
• Потребител: Вид програма, която има взаимодействие с потребителя.
• Процес: Референцията, която се използва както за задача, така и за потребител.
• CPU/IO пакетен цикъл: Характеризира изпълнението на процеса, което се редува между активност на процесора и входно/изходна активност. Времената за процесора обикновено са по-кратки от времената за входно/изходна активност.

Критерии за планиране на процесора

Алгоритъмът за планиране на процесора се опитва да максимизира и минимизира следното:

Увеличете

Използване на процесора: Използването на процесора е основната задача, при която операционната система трябва да се увери, че процесорът остава максимално зает. То може да варира от 0 до 100 процента. За RTOS обаче то може да варира от 40 процента за система от ниско ниво до 90 процента за система от високо ниво.

Пропускателна: Броят на процесите, които завършват изпълнението си за единица време, е известен като пропускателна способност. Така че, когато процесорът е зает с изпълнението на процес, се извършва работа и работата, завършена за единица време, се нарича пропускателна способност.

Минимизиране

Време за чакане: Времето за изчакване е времето, през което даден процес трябва да чака в опашката за готовност.

Време за реакция: Това е времето от момента на подаване на заявката до момента на получаване на първия отговор.

Време за изпълнение: Времето за изпълнение е времето, необходимо за изпълнение на конкретен процес. Това е общото време, прекарано в чакане за влизане в паметта, чакане в опашката и изпълнение на процесора. Периодът между момента на подаване на процеса и времето за завършване е времето за изпълнение.

Интервален таймер

Прекъсването на таймера е метод, който е тясно свързан с изпреварването. Когато определен процес получи разпределението на процесора, таймерът може да бъде настроен на определен интервал. Както прекъсването на таймера, така и изпреварването принуждават процеса да върне процесора, преди неговият CPU пакет да е завършен.

Повечето многопрограмни операционни системи използват някаква форма на таймер, за да предотвратят завинаги блокиране на системата от даден процес.

Какво е Диспечер?

Диспечерът е модул, който осигурява контрол над процесора на процеса. Диспечерът трябва да е бърз, за ​​да може да работи при всяко превключване на контекста. Латентността на диспечера е времето, необходимо на планировчика на процесора, за да спре един процес и да стартира друг.

Функции, изпълнявани от диспечера:

• Превключване на контекста.
• Преминаване към потребителски режим.
• Преместване на правилното място в новозаредената програма.

Видове планиране на процесора Algorithms

Има основно шест вида алгоритми за планиране на процеси:

1. Първи дойде първи обслужен (FCFS)
2. Планиране на най-кратката работа (SJF).
3. Най-краткото оставащо време
4. Приоритетно планиране
5. График за кръгъл робот
6. Многостепенно планиране на опашка

Scheduling Algorithms

Първи дойде, първи обслужи

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

Когато даден процес влезе в опашката за готовност, неговият PCB (блок за управление на процеса) се свързва с края на опашката. Така че, когато процесорът се освободи, той трябва да бъде присвоен на процеса в началото на опашката.

Характеристики на метода FCFS

• Това е алгоритъм за планиране без превантивни действия.
• Задачите винаги се изпълняват на принципа „първи дошъл, първи обслужен“.
• Той е лесен за изпълнение и използване.
• Този метод обаче е с ниска производителност и общото време за изчакване е доста дълго.

Най-краткото оставащо време

Пълната форма на SRT е Shortest Remaining Time (най-кратко оставащо време). Известно е още като SJF превантивно планиране. При този метод процесът ще бъде разпределен на задачата, която е най-близо до завършването си. Този метод предотвратява по-нов процес в състояние на готовност да забави завършването на по-стар процес.

Характеристики на метода за планиране на SRT

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

Приоритетно базирано планиране

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

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

График по кръгов режим

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

Характеристики на Round-Robin Scheduling

• Кръговият модел е хибриден модел, който се управлява от часовник.
• Времевият интервал, определен за обработката на конкретна задача, трябва да бъде минимален. Той обаче може да варира за различните процеси.
• Тя се държи като система за споделяне на време, която реагира на всеки процес в рамките на определен период от време.

Първо най-кратката работа

SJF (Shortest Job First - Най-кратко изпълнение) е алгоритъм за планиране, при който процесът с най-кратко време за изпълнение се избира за следващо изпълнение. Този метод на планиране може да бъде превантивен или непревантивен. Той значително намалява средното време на изчакване за други процеси, чакащи изпълнение.

Характеристики на планирането на SJF

• Всяка задача е свързана с единица време за изпълнение.
• При този метод, когато процесорът е наличен, първо се изпълнява следващият процес или задача с най-кратко време за завършване.
• Прилага се с политика без превантивни мерки.
• Този алгоритъм е полезен за пакетна обработка, където изчакването за завършване на задачите не е критично.
• Подобрява производителността на задачите, като първо изпълнява по-кратки задачи, които обикновено имат по-кратко време за изпълнение.

Планиране на опашки на няколко нива

Този алгоритъм разделя опашката за готовност на няколко отделни опашки. При този метод процесите се присвояват на опашка въз основа на специфично свойство на процеса, като например приоритет на процеса, размер на паметта и т.н.

Това обаче не е независим алгоритъм за планиране, тъй като е необходимо да се използват други видове алгоритми, за да се планират задачите.

Характеристики на планирането на опашки на няколко нива

• За процеси със споделени характеристики трябва да се поддържат множество опашки.
• Всяка опашка може да има свой собствен отделен алгоритъм за планиране.
• На всяка опашка се задават приоритети.

Целта на алгоритъма за планиране

Ето причините за използването на алгоритъм за планиране:

• Централният процесор използва планиране, за да подобри своята ефективност.
• Това ви помага да разпределите ресурси между конкуриращи се процеси.
• Максималното използване на процесора може да се постигне с мултипрограмиране.
• Процесите, които трябва да бъдат изпълнени, се съхраняват в опашката за готовност.

Въпроси и Отговори