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

Kas ir CPU plānošana?

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

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

CPU plānošanas veidi

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

Preventīva plānošana

Preventīvajā plānošanā uzdevumi lielākoties 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ākās prioritātes uzdevums joprojām darbojas. Zemākas prioritātes uzdevums tiek turēts kādu laiku un tiek atsākts, kad augstākās prioritātes uzdevums pabeidz tā izpildi.

Nepreventīva plānošana

Šāda veida plānošanas metodē CPU ir piešķirts konkrētam procesam. Process, kas notur centrālo procesoru, atbrīvos CPU, 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, iepriekšēja plānošana.

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

Lai noteiktu, vai plānošana ir pirmstermiņa vai neierobežota, ņemiet vērā šos četrus parametrus:

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

Piemērojami tikai 1. un 4. nosacījumi, plānošanu sauc par nenoteiktu.

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

Svarīga CPU plānošanas terminoloģija

  • Sērijas/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āju mijiedarbības.
  • Lietotājs: Tā ir sava veida programma ar lietotāju mijiedarbību.
  • Process: Tā ir atsauce, ko izmanto gan darbam, gan lietotājam.
  • CPU/IO pārraušanas cikls: Raksturo procesa izpildi, kas mainās starp CPU un I/O darbību. CPU procesori parasti ir īsāki par I/O laiku.

CPU plānošanas kritēriji

CPU plānošanas algoritms cenšas maksimāli palielināt un samazināt:

Maksimizēt:

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

Caurlaidība: Procesu skaits, kas pabeidz to izpildi laika vienībā, ir zināms caurlaidspēja. Tātad, kad centrālais procesors ir aizņemts ar procesa izpildi, tajā laikā tiek veikts darbs, un darbu, kas pabeigts laika vienībā, sauc par caurlaidspēju.

Samazināt:

Gaidīšanas laiks: Gaidīšanas laiks ir summa, kas īpašam procesam jāgaida gatavajā rindā.

Reakcijas laiks: Tas ir laiks, kurā pieprasījums tika iesniegts līdz pirmās atbildes sniegšanai.

Apgrozījuma laiks: Apgrozījuma laiks ir laiks, kas nepieciešams konkrēta procesa izpildei. Tas ir kopējā laika aprēķins, kas tiek gaidīts, lai iekļūtu atmiņā, gaidot rindā un izpildot CPU. Laika posms no procesa iesniegšanas brīža līdz pabeigšanas laikam ir izpildes laiks.

Intervāla taimeris

Taimera pārtraukšana ir metode, kas ir cieši saistīta ar priekšpirkšanu. Kad kāds process saņem CPU sadalījumu, taimeris var tikt iestatīts uz noteiktu intervālu. Gan taimera pārtraukšana, gan priekšlaicīga izmantošana liek procesam atgriezt centrālo procesoru pirms tā pārsprāgšanas pabeigšanas.

Lielākā daļa daudzprogrammētās operētājsistēmas izmanto kāda veida taimeri, lai process neatkārtotu sistēmu uz visiem laikiem.

Kas ir dispečers?

Tas ir modulis, kas nodrošina procesa kontroli CPU. Dispečeram jābūt ātram, lai tas varētu darboties ar katru konteksta slēdzi. Nosūtīšanas latentums ir laiks, kas nepieciešams CPU plānotājam, lai apturētu vienu procesu un sāktu citu.

Dispečera veiktās funkcijas:

  • Konteksta maiņa
  • Pārslēgšanās uz lietotāja režīmu
  • Pārvietošanās uz pareizo 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, kas pirmais pasniedz (FCFS)
  2. Īsākā darba pirmā (SJF) plānošana
  3. Īsākais atlikušais laiks
  4. Prioritāšu plānošana
  5. Round Robin plānošana
  6. Daudzlīmeņu rindu plānošana

Plānošanas algoritmi



Pasniedz vispirms

First Come First Serve ir pilna FCFS forma. Tas ir vienkāršākais un vienkāršākais CPU plānošanas algoritms. Šāda veida algoritmā process, kas pieprasa CPU, vispirms saņem CPU sadalījumu. Šo plānošanas metodi var pārvaldīt ar FIFO rindu.

Kad process nonāk gatavā rindā, tā PCB (procesa kontroles bloks) ir saistīts ar rindas asti. Tātad, kad CPU kļūst brīvs, tas jāpiešķir procesam rindas sākumā.

FCFS metodes raksturojums:

  • Tas piedāvā neierobežotu un preventīvu plānošanas algoritmu.
  • Darbi vienmēr tiek veikti pēc rindas principa
  • To ir viegli ieviest un lietot.
  • Tomēr šai metodei ir slikta veiktspēja, un vispārējais gaidīšanas laiks ir diezgan augsts.

Īsākais atlikušais laiks

SRT pilna forma ir īsākais atlikušais laiks. To sauc arī par SJF preventīvo plānošanu. Izmantojot šo metodi, process tiks piešķirts uzdevumam, kas ir vistuvāk tā pabeigšanai. Šī metode neļauj jaunākam gatavam stāvokļa procesam aizkavē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 nepieciešamais CPU laiks nav zināms.
  • Saistiet ar katru procesu kā nākamā CPU pārsprāgšanas ilgumu. Tā ka operētājsistēma izmanto šos garumus, kas palīdz ieplānot procesu pēc iespējas īsākā laikā.

Plānošana, pamatojoties uz prioritātēm

Prioritāšu plānošana ir procesu plānošanas metode, kuras pamatā ir prioritāte. Izmantojot šo metodi, plānotājs izvēlas veicamos uzdevumus atbilstoši prioritātei.

Prioritāšu plānošana arī palīdz OS iekļaut prioritāšu piešķiršanu. Vispirms būtu jāveic procesi ar augstāku prioritāti, turpretim darbus ar vienādām prioritātēm veic, pamatojoties uz apriti vai FCFS. Par prioritāti var lemt, pamatojoties uz atmiņas prasībām, laika prasībām utt.

Round-Robin plānošana

Apaļais apraksts ir vecākais, vienkāršākais plānošanas algoritms. Šī algoritma nosaukums cēlies no apļa principa, kurā katra persona pēc kārtas iegūst vienādu daļu no kaut kā. To galvenokārt izmanto algoritmu plānošanai daudzuzdevumu veikšanai. Šī algoritma metode palīdz bez bada procesa izpildi.

Round-Robin plānošanas raksturojums

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

Vispirms īsākais darbs

SJF ir pilna formāta (Vispirms visīsākais darbs) 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 pirmstermiņa vai neierobežota. 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ība, kas jāpabeidz.
  • Izmantojot šo metodi, kad CPU ir pieejams, vispirms tiks izpildīts nākamais process vai darbs ar īsāko pabeigšanas laiku.
  • Tas tiek īstenots ar politiku, kas nav preventīva.
  • Šī algoritma metode ir noderīga sērijveida apstrādei, kur darbu gaidīšanas gaidīšana nav kritiska.
  • Tas uzlabo darba rezultātus, piedāvājot īsākus darbus, kas vispirms jāizpilda un kuriem pārsvarā ir īsāks apgrozījuma 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 plānošanas OS algoritms, jo tam ir jāizmanto cita veida algoritmi, lai ieplānotu darbus.

Daudzlīmeņu rindu plānošanas raksturojums:

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

Plānošanas algoritma mērķis

Plānošanas algoritma izmantošanas iemesli ir šādi:

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

Kopsavilkums:

  • CPU plānošana ir process, kurā tiek noteikts, kuram procesam pieder CPU izpildei, kamēr cits process ir aizturēts.
  • Preventīvajā plānošanā uzdevumi lielākoties tiek piešķirti atbilstoši to prioritātēm.
  • Nepabeigtās plānošanas metodē CPU ir piešķirts konkrētam procesam.
  • Sērijveida laiks ir laiks, kas nepieciešams procesa pabeigšanai. To sauc arī par skriešanas laiku.
  • CPU izmantošana ir galvenais uzdevums, kurā operētājsistēmai jāpārliecinās, ka centrālais procesors paliek pēc iespējas aizņemts
  • Procesu skaits, kas pabeidz to izpildi laika vienībā, ir zināms caurlaidspēja.
  • Gaidīšanas laiks ir summa, kas īpašam procesam jāgaida gatavajā rindā.
  • Tas ir laiks, kurā pieprasījums tika iesniegts līdz pirmās atbildes sniegšanai.
  • Apgrozījuma laiks ir laiks, kas nepieciešams konkrēta procesa izpildei.
  • Taimera pārtraukšana ir metode, kas ir cieši saistīta ar priekšpirkšanu,
  • Dispečers ir modulis, kas nodrošina procesa kontroli.
  • Ir seši procesu plānošanas algoritmu veidi:
  • Pirmais, kas pirmais pasniedz (FCFS), 2) īsākā darba pirmais (SJF) plānošana
  • Izmantojot metodi, kas nāk vispirms, process, kas pieprasa CPU, vispirms saņem CPU sadalījumu.
  • Visīsākajā atlikušajā laikā process tiks piešķirts uzdevumam, kas ir vistuvāk tā pabeigšanai.
  • In, prioritāšu plānošana, plānotājs izvēlas uzdevumus, kas jāstrādā atbilstoši prioritātei.
  • Šajā kārtā apļa plānošana darbojas pēc principa, kur katra persona pēc kārtas saņem vienādu daļu
  • Vispirms īsākajā darbā jāizvēlas īsākais izpildes laiks
  • Daudzlīmeņu plānošanā metode gatavo rindu sadala dažādās atsevišķās rindās. Šajā metodē procesi tiek piešķirti rindai, pamatojoties uz konkrētu īpašumu
  • CPU izmanto plānošanu, lai uzlabotu tā efektivitāti.