CPU plānošanas algoritmi operētājsistēmās

Kas ir CPU plānošana?

CPU plānošana ir process, ar kuru nosaka, kuram procesam pieder CPU izpildei, kamēr cits process ir aizturēts. Galvenais CPU plānošanas uzdevums ir pārliecināties, ka ikreiz, kad CPU paliek dīkstāvē, OS vismaz izvēlas vienu no procesiem, kas pieejami izpildei gatavajā rindā. Atlases procesu veiks CPU plānotājs. Tas izvēlas vienu no atmiņā esošajiem procesiem, kas ir gatavi izpildei.

Šajā CPU plānošanas apmācībā jūs uzzināsiet:

• Kas ir CPU plānošana?
• CPU plānošanas veidi
• Svarīgas procesora plānošanas terminoloģijas
• Procesora plānošanas kritēriji
• Intervāla taimeris
• Kas ir dispečers?
• CPU plānošanas algoritma veidi
• Pirmais nāc pirmais kalpo
• Īsākais atlikušais laiks
• Prioritārā plānošana
• Apaļā Robina plānošana
• Vispirms īsākais darbs
• Daudzlīmeņu rindu plānošana
• Plānošanas algoritma mērķis

CPU plānošanas veidi

Šeit ir divu veidu plānošanas metodes:

Iepriekšēja plānošana

Programmā Preemptive Scheduling uzdevumi galvenokārt tiek piešķirti atbilstoši to prioritātēm. Dažreiz ir svarīgi izpildīt uzdevumu ar augstāku prioritāti pirms cita zemākas prioritātes uzdevuma, pat ja zemākas prioritātes uzdevums joprojām darbojas. Zemākas prioritātes uzdevums tiek turēts kādu laiku un tiek atsākts, kad augstākas prioritātes uzdevums pabeidz izpildi.

Neplānojoša plānošana

Šāda veida plānošanas metodē CPU ir piešķirts noteiktam procesam. Process, kas uztur procesoru aizņemtu, atbrīvos CPU vai nu, pārslēdzot kontekstu vai pārtraucot darbību. Tā ir vienīgā metode, ko var izmantot dažādām aparatūras platformām. Tas ir tāpēc, ka tam nav nepieciešama īpaša aparatūra (piemēram, taimeris), piemēram, preventīva plānošana.

Kad plānošana ir preventīva vai nepreferatīva?

Lai noteiktu, vai plānošana ir preventīva vai nepieņemama, ņemiet vērā šos četrus parametrus:

1. Process tiek pārslēgts no skriešanas uz gaidīšanas stāvokli.
2. Konkrēts process tiek pārslēgts no darbības stāvokļa uz gatavu stāvokli.
3. Konkrēts process tiek pārslēgts no gaidīšanas stāvokļa uz gatavību.
4. Process pabeidza izpildi un tika pārtraukts.

Piemēro tikai 1. un 4. nosacījumu, plānošanu sauc par nepreferenciālu.

Visa pārējā plānošana ir preventīva.

Svarīgas procesora plānošanas terminoloģijas

• Saraksta laiks / izpildes laiks: Tas ir laiks, kas nepieciešams procesam, lai pabeigtu izpildi. To sauc arī par skriešanas laiku.
• Ierašanās laiks: kad process nonāk gatavā stāvoklī
• Pabeigšanas laiks: kad process ir pabeigts un iziet no sistēmas
• Daudzprogrammēšana: vairākas programmas, kuras vienlaikus var būt atmiņā.
• Darbs: Tas ir programmas veids bez jebkādas lietotāja mijiedarbības.
• Lietotājs: Tā ir sava veida programma, kurai ir lietotāja mijiedarbība.
• Process: tā ir atsauce, kas tiek izmantota gan darbam, gan lietotājam.
• CPU / IO pārsprāgt cikls: Raksturo procesa izpildi, kas mijas starp CPU un I / O darbību. Procesora laiki parasti ir īsāki par I / O laiku.

Procesora plānošanas kritēriji

Centrālā procesora plānošanas algoritms mēģina maksimizēt un samazināt sekojošo:

Palielināt:

Procesora izmantošana: CPU izmantošana ir galvenais uzdevums, kurā operētājsistēmai jāpārliecinās, ka CPU paliek pēc iespējas aizņemts. Tas var svārstīties no 0 līdz 100 procentiem. Tomēr attiecībā uz RTOS tas var svārstīties no 40 procentiem zema līmeņa un 90 procentiem augsta līmeņa sistēmai.

Caurlaide: To procesu skaits, kas pabeidz to izpildi laika vienībā, ir zināms. Tātad, kad centrālais procesors ir aizņemts, veicot procesu, tajā laikā tiek veikts darbs, un laika vienībā pabeigto darbu sauc par caurlaidi.

Samazināt:

Gaidīšanas laiks: Gaidīšanas laiks ir summa, kas konkrētajam procesam jāgaida gatavajā rindā.

Atbildes laiks: tas ir laiks, kurā pieprasījums tika iesniegts, līdz tiek sagatavota pirmā atbilde.

Apgrozījuma laiks: Apgrozījuma laiks ir laika daudzums, lai veiktu noteiktu procesu. Tas ir aprēķināt kopējo laiku, kas pavadīts, gaidot iekļūšanu atmiņā, gaidīšanu rindā un izpildi CPU. Laiks starp procesa iesniegšanas laiku līdz pabeigšanas laikam ir apgrozījuma laiks.

Intervāla taimeris

Taimera pārtraukums ir metode, kas ir cieši saistīta ar pirmstermiņu. Kad noteikts process iegūst CPU piešķiršanu, taimeri var iestatīt uz noteiktu intervālu. Gan taimera pārtraukšana, gan pirmstermiņa piespiešana atdod CPU, pirms tā ir pabeigta.

Lielākā daļa daudzprogrammēto operētājsistēmu izmanto kādu taimera formu, lai process netiktu sasiets uz visiem laikiem.

Kas ir dispečers?

Tas ir modulis, kas nodrošina procesora kontroli procesam. Dispečeram jābūt ātram, lai tas darbotos visos konteksta slēdžos. Nosūtīšanas latentums ir laiks, kas nepieciešams CPU plānotājam, lai apturētu vienu procesu un sāktu citu procesu.

Dispečera veiktās funkcijas:

• Konteksta pārslēgšana
• Pārslēgšanās uz lietotāja režīmu
• Pāreja uz pareizo atrašanās vietu tikko ielādētajā programmā.

CPU plānošanas algoritma veidi

Galvenokārt ir seši procesu plānošanas algoritmu veidi

1. Pirmais nāk pirmais kalpojums (FCFS)
2. Īsākais darbs vispirms (SJF) plānošana
3. Īsākais atlikušais laiks
4. Prioritārā plānošana
5. Apaļā Robina plānošana
6. Daudzlīmeņu rindas plānošana

Pirmais nāc pirmais kalpo

First Come First Serve ir pilna FCFS forma. Tas ir vienkāršākais un vienkāršākais procesora plānošanas algoritms. Šāda veida algoritmos process, kas pieprasa CPU, vispirms iegūst CPU piešķiršanu. Šo plānošanas metodi var pārvaldīt ar FIFO rindu.

Kad process nonāk gatavajā rindā, tā PCB (Process Control Block) ir saistīts ar rindas asti. Tātad, kad centrālais procesors kļūst brīvs, tas jāpiešķir procesam rindas sākumā.

FCFS metodes raksturojums:

• Tas piedāvā neplānojošu un preventīvu plānošanas algoritmu.
• Darbi vienmēr tiek izpildīti, vadoties pēc rindas principa
• To ir viegli ieviest un izmantot.
• Tomēr šai metodei ir slikta veiktspēja, un vispārējais gaidīšanas laiks ir diezgan augsts.

Īsākais atlikušais laiks

Pilna SRT forma ir īsākais atlikušais laiks. To sauc arī par SJF preventīvu plānošanu. Šajā metodē process tiks piešķirts uzdevumam, kas ir vistuvāk tā izpildei. Šī metode neļauj jaunākam gatavā stāvokļa procesam noturēt vecāka procesa pabeigšanu.

SRT plānošanas metodes raksturojums:

• Šo metodi galvenokārt izmanto sērijveida vidēs, kur priekšroka jādod īsiem darbiem.
• Šī nav ideāla metode, kā to ieviest koplietotā sistēmā, kur nav zināms nepieciešamais procesora laiks.
• Saistiet ar katru procesu, jo tā nākamā CPU pārsprāgt. Šī operētājsistēma izmanto šos garumus, kas palīdz ieplānot procesu pēc iespējas īsākā laikā.

Prioritārā plānošana

Prioritātes plānošana ir procesu plānošanas metode, kuras pamatā ir prioritāte. Šajā metodē plānotājs atlasa uzdevumus darbam atbilstoši prioritātei.

Prioritātes plānošana palīdz OS arī iesaistīt prioritāros uzdevumus. Vispirms būtu jāveic procesi ar augstāku prioritāti, turpretī darbavietas ar vienādām prioritātēm tiek veiktas pēc apļa vai FCFS principa. Prioritāti var izlemt, ņemot vērā atmiņas prasības, laika prasības utt.

Apaļā Robina plānošana

Apaļš robins ir vecākais, vienkāršākais plānošanas algoritms. Šī algoritma nosaukums nāk no apļa principa, kad katrs cilvēks pēc kārtas iegūst vienādu daļu no kaut kā. To galvenokārt izmanto algoritmu plānošanai daudzuzdevumu veikšanā. Šī algoritma metode palīdz bez bada procesus izpildīt.

Round-Robin plānošanas raksturojums

• Round robin ir hibrīds modelis, kas darbojas ar pulksteni
• Laika daļai jābūt minimālai, kas tiek piešķirta konkrētam apstrādājamam uzdevumam. Tomēr tas var atšķirties dažādiem procesiem.
• Tā ir reālā laika sistēma, kas reaģē uz notikumu noteiktā termiņā.

Vispirms īsākais darbs

SJF ir pilna veidlapa (Visīsākais darbs vispirms) ir plānošanas algoritms, kurā nākamajai izpildei jāizvēlas process ar īsāko izpildes laiku. Šī plānošanas metode var būt preventīva vai nepieļauta. Tas ievērojami samazina vidējo gaidīšanas laiku citiem procesiem, kas gaida izpildi.

SJF plānošanas raksturojums

• Tas ir saistīts ar katru darbu kā laika vienību, kas jāpaveic.
• Šajā metodē, kad ir pieejams centrālais procesors, vispirms tiks izpildīts nākamais process vai darbs ar īsāko pabeigšanas laiku.
• Tas tiek īstenots ar nepreferenciālu politiku.
• Šī algoritma metode ir noderīga sērijveida apstrādei, kur darbu pabeigšanas gaidīšana nav kritiska.
• Tas uzlabo darba piedāvājumu, piedāvājot īsākus darbus, kuri būtu jāizpilda vispirms, kuriem pārsvarā ir īsāks darba laiks.

Daudzlīmeņu rindu plānošana

Šis algoritms atdala gatavo rindu dažādās atsevišķās rindās. Šajā metodē procesi tiek piešķirti rindai, pamatojoties uz konkrētu procesa īpašību, piemēram, procesa prioritāti, atmiņas lielumu utt.

Tomēr tas nav neatkarīgs OS plānošanas algoritms, jo, lai ieplānotu darbus, ir jāizmanto cita veida algoritmi.

Raksturīga daudzlīmeņu rindu plānošanai:

• Procesiem ar dažām īpašībām būtu jāuztur vairākas rindas.
• Katrai rindai var būt atsevišķi plānošanas algoritmi.
• Prioritātes tiek noteiktas katrai rindai.

Plānošanas algoritma mērķis

Šeit ir plānošanas algoritma izmantošanas iemesli:

• CPU izmanto plānošanu, lai uzlabotu tā efektivitāti.
• Tas palīdz jums sadalīt resursus starp konkurējošiem procesiem.
• Maksimālo CPU izmantošanu var iegūt, izmantojot daudzprogrammēšanu.
• Izpildāmie procesi ir gatavā rindā.

Kopsavilkums:

• Procesora plānošana ir process, ar kuru nosaka, kuram procesam pieder CPU izpildei, kamēr cits process ir aizturēts.
• Programmā Preemptive Scheduling uzdevumi galvenokārt tiek piešķirti atbilstoši to prioritātēm.
• Neplānošanas plānošanas metodē CPU ir piešķirts konkrētam procesam.
• Burst laiks ir laiks, kas nepieciešams procesa pabeigšanai. To sauc arī par skriešanas laiku.
• Procesora izmantošana ir galvenais uzdevums, kurā operētājsistēmai jāpārliecinās, ka procesors paliek pēc iespējas aizņemts
• Procesu skaits, kas pabeidz to izpildi laika vienībā, ir zināms caurlaide.
• Gaidīšanas laiks ir summa, kas konkrētajam procesam jāgaida gatavajā rindā.
• Tas ir laiks, kurā pieprasījums tika iesniegts līdz pirmās atbildes sniegšanai.
• Apgrozījuma laiks ir laika daudzums, lai veiktu noteiktu procesu.
• Taimera pārtraukums ir metode, kas ir cieši saistīta ar pirmstermiņa
• Dispečers ir modulis, kas nodrošina procesora kontroli procesam.
• Seši procesu plānošanas algoritmu veidi ir:
• Pirmā atnākšanas pirmā pasniegšana (FCFS), 2) Visīsākā darba sākumā (SJF) plānošana 3) Īsākais atlikušais laiks 4) Prioritārā plānošana 5) Plānošanas apļa plānošana 6) Daudzlīmeņu rindas plānošana
• Metodē First Come First Serve process, kas pieprasa CPU, vispirms iegūst CPU piešķiršanu.
• Īsākajā atlikušajā laikā process tiks piešķirts uzdevumam, kas ir vistuvāk tā izpildei.
• Sadaļā Prioritātes plānošana plānotājam izvēlas uzdevumus, kas jāstrādā atbilstoši prioritātei.
• Šajā kārtā plānošana pēc kārtas darbojas principā, kad katrs cilvēks pēc kārtas iegūst vienādu daļu no kaut kā
• Īsākajā darbā vispirms izpildei jāizvēlas īsākais izpildes laiks
• Daudzlīmeņu plānošanā metode gatavo rindu atdala dažādās atsevišķās rindās. Šajā metodē procesi tiek piešķirti rindai, pamatojoties uz noteiktu īpašību
• CPU izmanto plānošanu, lai uzlabotu tā efektivitāti.