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

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

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

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

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

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

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

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

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

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

Прилагат се само условия 1 и 4, планирането се нарича непредварително.

Всички останали планове са изпреварващи.

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

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

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

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

Увеличете

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Характеристика на многостепенното планиране на опашки

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

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

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

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

Oбобщение

• Планирането на CPU е процес на определяне кой процес ще притежава CPU за изпълнение, докато друг процес е задържан.
• При предварителното планиране задачите се присвояват предимно с техните приоритети.
• При метода за планиране без изпреварване процесорът е разпределен за конкретен процес.
• Времето за избухване е времето, необходимо на процеса да завърши изпълнението. Нарича се още време на работа.
• Използването на процесора е основната задача, при която операционната система трябва да гарантира, че процесорът остава възможно най-натоварен.
• Броят на процесите, които завършват своето изпълнение за единица време, е известна пропускателна способност.
• Времето за изчакване е количеството, което конкретен процес трябва да изчака в опашката за готовност.
• Това е времето, през което е изпратена заявката до получаване на първия отговор.
• Времето за изпълнение е количеството време за изпълнение на конкретен процес.
• Прекъсването на таймера е метод, който е тясно свързан с изпреварването.
• Диспечерът е модул, който осигурява контрол на процесора на процеса.
• Шест вида алгоритми за планиране на процеси са: First Come First Serve (FCFS), 2) Shortest-Job-First (SJF) Scheduling, 3) Shortest Remaining Time, 4) Priority Scheduling, 5) Round Robin Scheduling, 6) Многостепенно планиране на опашката .
• в Метод First Come First Serve, процесът, който иска CPU, получава първо разпределението на CPU.
• В най-краткото оставащо време процесът ще бъде разпределен към задачата, която е най-близо до нейното завършване.
• В приоритетното планиране планировчикът избира задачите, които да работят според приоритета.
• График за двупосочна система работи на принципа, при който всеки човек получава равен дял от нещо на свой ред.
• В Първо най-кратката задача трябва да се избере най-краткото време за изпълнение за следващо изпълнение.
• Методът на многостепенно планиране разделя готовата опашка на различни отделни опашки. При този метод процесите се присвояват на опашка въз основа на конкретно свойство.
• Централният процесор използва планиране, за да подобри своята ефективност.