V tej vadnici se bomo naučili pomembnega koncepta algoritmov za načrtovanje procesov CPU. Pomembno ime koncepta je First Come First Serve. To je osnovni algoritem, ki se ga mora naučiti vsak učenec, da razume vse osnove algoritmov za načrtovanje procesov CPU.
First Come First Serve utira pot razumevanju drugih algoritmov. Ta algoritem ima lahko številne pomanjkljivosti. Toda te pomanjkljivosti so ustvarile zelo nove in učinkovite algoritme. Naša odgovornost je torej, da spoznamo algoritme za načrtovanje procesov procesorja, ki prvi pridejo, prvi dobijo.
Pomembne okrajšave
- CPE - - - > Centralna procesna enota
- FCFS - - - > Prvi pride, prvi melje
- V - - - > Čas prihoda
- BT - - - > Burst Time
- WT - - - > Čakalna doba
- TAT - - - > Turn Around Time
- CT - - - > Čas zaključka
- FIFO - - - > First In First Out
Prvi pride, prvi postreže
Algoritem za razporejanje CPE-ja, ki prvi pride, prvi dobi, na kratko znan kot FCFS, je prvi algoritem algoritma za razporejanje procesov CPE. Pri algoritmu prvi pride, prvi melje omogočamo, da se postopek izvaja linearno.
To pomeni, da kateri koli proces, ki prvi vstopi v pripravljeno čakalno vrsto, se prvi izvede. To kaže, da algoritem prvi pride, prvi melje sledi načelu FIFO (First In First Out).
Algoritem »prvi pride, prvi melje« se lahko izvede na vnaprejšnji in nepredhodni način. Preden preidemo na primere, poglejmo, kaj je vnaprejšnji in nepredhodni pristop pri načrtovanju procesov procesorja.
Predhodni pristop
V tem primeru vnaprejšnjega razporejanja procesa OS dodeli sredstva procesu za vnaprej določeno časovno obdobje. Proces med dodeljevanjem virov preide iz stanja izvajanja v stanje pripravljenosti ali iz stanja čakanja v stanje pripravljenosti. Do tega preklopa pride, ker lahko CPE drugim procesom dodeli prednost in trenutno aktivni proces nadomesti s procesom z višjo prednostjo.
Nepredhodni pristop
V tem primeru razporejanja procesov brez vnaprejšnjega izčrpavanja vira ni mogoče umakniti iz procesa, preden se proces ne zaključi. Ko se tekoči proces konča in preide v stanje čakanja, se sredstva preklopijo.
Učinek konvoja v prvi prispe prvi melje (FCFS)
Učinek konvoja je pojav, ki se pojavi v algoritmu za razporejanje, imenovanem First Come First Serve (FCFS). Algoritem za razporejanje prvi pride prvi se pojavi na način, ki ni preventiven.
Nepreventivni način pomeni, da če se proces ali opravilo začne izvajati, mora operacijski sistem dokončati svoj proces ali opravilo. Dokler proces ali opravilo ni nič, se nov ali naslednji proces ali opravilo ne začne izvajati. Definicija nepreventivnega razporejanja v smislu operacijskega sistema pomeni, da bo centralna procesna enota (CPE) popolnoma posvečena do konca procesa ali opravila, ki se je začelo prvo, nov proces ali opravilo pa se izvede šele po zaključku starejšega procesa oz. služba.
Obstaja nekaj primerov, ki lahko povzročijo, da centralna procesna enota (CPE) dodeli preveč časa. To je zato, ker so v algoritmu načrtovanja prvi pride, prvi vročen brez vnaprejšnjega pristopa procesi ali opravila izbrani v zaporednem vrstnem redu. Zaradi tega krajša opravila ali procesi za večjimi procesi ali opravili zahtevajo preveč časa, da se dokončajo. Zaradi tega je čakalna doba, čas obračanja in čas dokončanja zelo visok.
Torej, tukaj, ko je prvi proces velik ali je čas dokončanja previsok, se pojavi ta učinek konvoja v algoritmu prvi pride prvi.
Predpostavimo, da daljše delo traja neskončno dolgo. Nato morajo preostali procesi čakati enako neskončno dolgo. Zaradi tega konvojskega učinka, ki ga ustvari daljše delo, se stradanje čakajočih procesov zelo hitro poveča. To je največja pomanjkljivost FCFS CPE Process Scheduling.
Značilnosti razporejanja procesov CPU FCFS
Značilnosti razporejanja procesov CPU FCFS so:
- Izvedba je preprosta.
- Med uporabo ne povzroča nobenih vzročnih posledic
- Sprejema nepreventivno in preventivno strategijo.
- Vsak postopek zažene v vrstnem redu, v katerem so prejeti.
- Čas prihoda se uporablja kot izbirno merilo za postopke.
Prednosti razporejanja procesov CPU FCFS
Prednosti razporejanja procesov CPU FCFS so:
- Za dodelitev procesov uporablja čakalno vrsto First In First Out.
- Proces razporejanja procesorja FCFS je preprost in enostaven za implementacijo.
- Pri predhodnem razporejanju situacije FCFS ni možnosti, da bi proces izginil.
- Ker ni upoštevanja prioritete procesa, je pravičen algoritem.
Slabosti razporejanja procesov CPU FCFS
Slabosti razporejanja procesov CPU FCFS so:
- Algoritem za razporejanje procesorja FCFS ima dolgo čakalno dobo
- FCFS CPE Scheduling daje prednost CPU pred vhodnimi ali izhodnimi operacijami
- Pri FCFS obstaja možnost pojava učinka konvoja
- Ker je FCFS tako preprost, pogosto ni zelo učinkovit. Z roko v roki gredo podaljšane čakalne dobe. Vsa druga naročila ostanejo nedejavna, če je CPE zaposlen z obdelavo enega zamudnega naročila.
Težave v algoritmu za razporejanje procesorja prvi pride, prvi dobi
Primer
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
Nepredhodni pristop
Zdaj pa rešimo to težavo s pomočjo algoritma za razporejanje z imenom First Come First Serve v pristopu brez prednosti.
Ganttov grafikon za zgornji primer 1 je:
Čas obračanja = čas dokončanja - čas prihoda
Čakalna doba = Čas obračanja - Čas porušitve
Rešitev zgornjega vprašanja Primer 1
| da ne | ID procesa | Čas prihoda | Burst Time | Čas dokončanja | Turn Around Time | Čas čakanja | |
|---|---|---|---|---|---|---|---|
| 1 | P 1 | A | 0 | 9 | 9 | 9 | 0 |
| 2 | P 2 | B | 1 | 3 | 12 | enajst | 8 |
| 3 | P 3 | C | 1 | 2 | 14 | 13 | enajst |
| 4 | P 4 | D | 1 | 4 | 18 | 17 | 13 |
| 5 | P 5 | IN | 2 | 3 | enaindvajset | 19 | 16 |
| 6 | P 6 | F | 3 | 2 | 23 | dvajset | 18 |
Povprečni čas dokončanja je:
Povprečni CT = (9 + 12 + 14 + 18 + 21 + 23) / 6
kako seznaniti slušalke beats
Povprečni CT = 97 / 6
Povprečni CT = 16,16667
Povprečna čakalna doba je:
Povprečna WT = (0 + 8 + 11 + 13 + 16 + 18) /6
Povprečna WT = 66 / 6
Povprečna WT = 11
Povprečni čas obračanja je:
Povprečni TAT = (9 + 11 + 13 + 17 + 19 +20) / 6
Povprečni TAT = 89 / 6
Povprečni TAT = 14,83334
Tako je FCFS rešen v pristopu brez vnaprejšnje izjeme.
Zdaj pa poglejmo, kako jih je mogoče rešiti v vnaprejšnjem pristopu
Predhodni pristop
Zdaj pa rešimo to težavo s pomočjo algoritma za razporejanje z imenom First Come First Serve v vnaprejšnjem pristopu.
V Pre Emptive Approach iščemo najboljši postopek, ki je na voljo
Ganttov grafikon za zgornji primer 1 je:
| da ne | ID procesa | Čas prihoda | Burst Time | Čas dokončanja | Turn Around Time | Čas čakanja | |
|---|---|---|---|---|---|---|---|
| 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 | petnajst | 14 | 10 |
| 5 | P 5 | IN | 2 | 3 | enajst | 9 | 7 |
| 6 | P 6 | F | 3 | 2 | 5 | 2 | 0 |
| naslednji → ← prejšnja Da bi se rešil problema zapravljanja signalov za bujenje, je Dijkstra predlagal pristop, ki vključuje shranjevanje vseh klicev za bujenje. Dijkstra navaja, da lahko proizvajalec, namesto da klice za bujenje posreduje neposredno potrošniku, shrani klic za bujenje v spremenljivko. Vsak od potrošnikov ga lahko prebere, kadar koli to potrebuje. Semafor je spremenljivka, ki shranjuje celotne klice bujenja, ki se prenašajo od proizvajalca do potrošnika. To je spremenljivka, katere branje, spreminjanje in posodabljanje poteka samodejno v načinu jedra. Semaforja ni mogoče implementirati v uporabniškem načinu, ker se lahko vedno pojavi stanje tekmovanja, ko poskušata dva ali več procesov hkrati dostopati do spremenljivke. Za implementacijo vedno potrebuje podporo operacijskega sistema. Glede na povpraševanje po razmerah lahko Semaphore razdelimo v dve kategoriji.
O vsakem bomo podrobno razpravljali. |