Šajā apmācībā mēs apgūsim svarīgu jēdzienu CPU procesu plānošanas algoritmos. Svarīgais jēdziena nosaukums ir Serve First Come First. Šis ir pamata algoritms, kas katram studentam jāiemācās, lai saprastu visus CPU procesu plānošanas algoritmu pamatus.
Serve “Pirmais nāk pirmais” paver ceļu citu algoritmu izpratnei. Šim algoritmam var būt daudz trūkumu. Taču šie trūkumi radīja ļoti jaunus un efektīvus algoritmus. Tāpēc mūsu pienākums ir uzzināt par CPU procesa plānošanas algoritmiem “Pirmais nāk pirmais”.
Svarīgi saīsinājumi
- CPU - - - > Centrālā procesora bloks
- FCFS - - - > Servēšana pirmais brauc pirmais
- AT - - - > Ierašanās laiks
- BT - - - > Pārraides laiks
- WT - - - > Gaidīšanas laiks
- TAT - - - > Pagrieziena laiks
- CT - - - > Pabeigšanas laiks
- FIFO - - - > First In First Out
Pasniedz pirmais, kas pirmais brauc
CPU plānošanas algoritms, kas īsi pazīstams kā FCFS, ir pirmais CPU procesu plānošanas algoritma algoritms. Algoritmā “Vispirms nāk, pirmais kalpo” tas, ko mēs darām, ir ļaut procesam izpildīt lineāri.
Tas nozīmē, ka tas, kurš process ievada process, pirmais nonāk gatavības rindā, tiek izpildīts pirmais. Tas parāda, ka algoritms “Pirmais nāk pirmais ārā” atbilst FIFO principam.
Algoritmu “Pirmais nāc pirmais” var izpildīt gan pirmstermiņa, gan beztermiņa režīmā. Pirms iedziļināties piemēros, ļaujiet mums saprast, kas CPU procesu plānošanā ir iepriekšēja un neapsteidzoša pieeja.
Preventīvā pieeja
Šajā iepriekšējas procesa plānošanas gadījumā OS piešķir resursus procesam uz iepriekš noteiktu laika periodu. Resursu piešķiršanas laikā process pāriet no darbības stāvokļa uz gatavības stāvokli vai no gaidīšanas stāvokļa uz gatavības stāvokli. Šī pārslēgšana notiek tāpēc, ka centrālais procesors var piešķirt prioritāti citiem procesiem un aizstāt pašlaik aktīvo procesu ar augstākas prioritātes procesu.
Nepreventīva pieeja
Šajā nepreventīvā procesa plānošanas gadījumā resursu nevar izņemt no procesa, pirms process nav beidzies. Kad darbības process beidzas un pāriet uz gaidīšanas stāvokli, resursi tiek pārslēgti.
Konvoja efekts servēšanas kārtībā (FCFS)
Konvoja efekts ir parādība, kas rodas plānošanas algoritmā ar nosaukumu First Come First Serve (FCFS). Plānošanas algoritms “Pirmais nāk pirmais” tiek izmantots nepreventīvā veidā.
Nepreventīvs veids nozīmē, ka, ja process vai darbs tiek sākts izpildīt, operētājsistēmai ir jāpabeidz savs process vai darbs. Kamēr procesa vai uzdevuma vērtība ir nulle, jaunais vai nākamais process vai darbs nesāk tā izpildi. Nepreventīvas plānošanas definīcija attiecībā uz operētājsistēmu nozīmē, ka centrālais procesors (CPU) būs pilnībā veltīts līdz procesa vai darba beigām, kas sākts pirmais, un jaunais process vai darbs tiek izpildīts tikai pēc vecā procesa pabeigšanas vai darbs.
Var būt daži gadījumi, kuru dēļ centrālais procesors (CPU) var atvēlēt pārāk daudz laika. Tas ir tāpēc, ka nepreventīvā plānošanas algoritma “Pirmais nāk pirmais, kas pirmais piedāvā” pieejā procesi vai darbi tiek izvēlēti sērijas secībā. Šī iemesla dēļ īsāki darbi vai procesi aiz lielākiem procesiem vai darbiem aizņem pārāk daudz laika, lai pabeigtu tā izpildi. Sakarā ar to gaidīšanas laiks, apgriešanās laiks, pabeigšanas laiks ir ļoti augsts.
Tātad šeit, tā kā pirmais process ir liels vai pabeigšanas laiks ir pārāk ilgs, parādās šis konvoja efekts algoritmā “Pirmais nāk pirmais”.
Pieņemsim, ka ilgākam darbam ir vajadzīgs bezgalīgs laiks. Pēc tam atlikušajiem procesiem jāgaida tāds pats bezgalīgs laiks. Pateicoties garāka darba radītajam konvoja efektam, ļoti strauji palielinās gaidīšanas procesu badošanās. Tas ir lielākais FCFS CPU procesu plānošanas trūkums.
FCFS CPU procesu plānošanas raksturojums
FCFS CPU procesu plānošanas īpašības ir šādas:
- Īstenošana ir vienkārša.
- Lietošanas laikā neizraisa cēloņsakarības
- Tā pieņem nepreventīvu un preventīvu stratēģiju.
- Tā veic katru procedūru to saņemšanas secībā.
- Ierašanās laiks tiek izmantots kā procedūru izvēles kritērijs.
FCFS CPU procesu plānošanas priekšrocības
FCFS CPU procesu plānošanas priekšrocības ir:
- Lai piešķirtu procesus, tas izmanto rindu First In First Out.
- FCFS CPU plānošanas process ir vienkāršs un viegli īstenojams.
- FCFS situācijā, veicot iepriekšēju plānošanu, process nepastāv izsalkums.
- Tā kā procesa prioritāte netiek ņemta vērā, tas ir taisnīgs algoritms.
FCFS CPU procesu plānošanas trūkumi
FCFS CPU procesu plānošanas trūkumi ir šādi:
- FCFS CPU plānošanas algoritmam ir ilgs gaidīšanas laiks
- FCFS CPU plānošana dod priekšroku CPU, nevis ievades vai izvades operācijām
- FCFS gadījumā pastāv konvoja efekta rašanās iespēja
- Tā kā FCFS ir tik vienkārša, tā bieži vien nav ļoti efektīva. Pagarināti gaidīšanas periodi iet roku rokā ar to. Visi pārējie pasūtījumi tiek atstāti dīkstāvē, ja centrālais procesors ir aizņemts ar viena laikietilpīga pasūtījuma apstrādi.
Problēmas, kas saistītas ar CPU plānošanas algoritmu
Piemērs
S. No Process ID Process Name Arrival Time Burst Time _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 P 1 A 0 9 2 P 2 B 1 3 3 P 3 C 1 2 4 P 4 D 1 4 5 P 5 E 2 3 6 P 6 F 3 2
Nepreventīva pieeja
Tagad atrisināsim šo problēmu, izmantojot plānošanas algoritmu, kas nosaukts pirmais, kas pirmais, apkalpojot nepreventīvā pieejā.
Ganta diagramma iepriekšminētajam 1. piemēram ir:
Apgriešanas laiks = pabeigšanas laiks — ierašanās laiks
Gaidīšanas laiks = aprites laiks — sērijveida uzņemšanas laiks
Iepriekšējā jautājuma risinājums 1. piemērs
| Jā nē | Procesa ID | Ierašanās laiks | Pārraušanas laiks | Pabeigšanas laiks | Pagrieziena laiks | Gaidīšanas laiks | |
|---|---|---|---|---|---|---|---|
| 1 | P 1 | A | 0 | 9 | 9 | 9 | 0 |
| 2 | P 2 | B | 1 | 3 | 12 | vienpadsmit | 8 |
| 3 | P 3 | C | 1 | 2 | 14 | 13 | vienpadsmit |
| 4 | P 4 | D | 1 | 4 | 18 | 17 | 13 |
| 5 | P 5 | UN | 2 | 3 | divdesmitviens | 19 | 16 |
| 6 | P 6 | F | 3 | 2 | 23 | divdesmit | 18 |
Vidējais pabeigšanas laiks ir:
Vidējais CT = ( 9 + 12 + 14 + 18 + 21 + 23 ) / 6
Vidējais CT = 97/6
Vidējais CT = 16,16667
Vidējais gaidīšanas laiks ir:
Vidējais WT = ( 0 + 8 + 11 + 13 + 16 + 18 ) /6
Vidējais WT = 66/6
Pīta Deividsona pilsonība
Vidējais WT = 11
Vidējais apgrozījuma laiks ir:
Vidējais TAT = ( 9 + 11 + 13 + 17 + 19 + 20 ) / 6
Vidējais TAT = 89/6
Vidējais TAT = 14,83334
Šādi tiek atrisināta FCFS, izmantojot nepreventīvo pieeju.
Tagad sapratīsim, kā tos var atrisināt, izmantojot preventīvo pieeju
Preventīvā pieeja
Tagad atrisināsim šo problēmu, izmantojot plānošanas algoritmu, kas nosaukts pirmais, kas pirmais apkalpo, izmantojot iepriekšēju pieeju.
Izmantojot iepriekšēju pieeju, mēs meklējam labāko pieejamo procesu
Ganta diagramma iepriekšminētajam 1. piemēram ir:
| Jā nē | Procesa ID | Ierašanās laiks | Pārraušanas laiks | Pabeigšanas laiks | Pagrieziena laiks | Gaidīšanas laiks | |
|---|---|---|---|---|---|---|---|
| 1 | P 1 | A | 0 | 9 | 23 | 23 | 14 |
| 2 | P 2 | B | 1 | 3 | 8 | 7 | 4 |
| 3 | P 3 | C | 1 | 2 | 3 | 2 | 0 |
| 4 | P 4 | D | 1 | 4 | piecpadsmit | 14 | 10 |
| 5 | P 5 | UN | 2 | 3 | vienpadsmit | 9 | 7 |
| 6 | P 6 | F | 3 | 2 | 5 | 2 | 0 |
| nākamais → ← iepriekš Lai atbrīvotos no modināšanas signālu izšķērdēšanas problēmas, Dijkstra ierosināja pieeju, kas ietver visu modināšanas zvanu saglabāšanu. Dijkstra norāda, ka tā vietā, lai modināšanas zvanus sniegtu tieši patērētājam, ražotājs modināšanas zvanu var saglabāt mainīgā. Jebkurš patērētājs to var izlasīt, kad vien tas ir nepieciešams. Semafors ir mainīgie, kas saglabā visus modināšanas zvanus, kas tiek pārsūtīti no ražotāja patērētājam. Tas ir mainīgais, kura lasīšana, modificēšana un atjaunināšana notiek automātiski kodola režīmā. Semaforu nevar ieviest lietotāja režīmā, jo sacensību nosacījums vienmēr var rasties, kad divi vai vairāki procesi mēģina piekļūt mainīgajam vienlaikus. Lai to ieviestu, vienmēr ir nepieciešams atbalsts no operētājsistēmas. Atbilstoši situācijas pieprasījumam Semaforu var iedalīt divās kategorijās.
Mēs apspriedīsim katru sīkāk. |