U ovom tutorijalu naučit ćemo važan koncept algoritama za raspoređivanje CPU procesa. Važan naziv koncepta je First Come First Serve. Ovo je osnovni algoritam koji svaki učenik mora naučiti kako bi razumio sve osnove CPU algoritama za raspoređivanje procesa.
First Come First Serve utire put razumijevanju drugih algoritama. Ovaj algoritam može imati mnoge nedostatke. Ali ti su nedostaci stvorili vrlo nove i učinkovite algoritme. Dakle, naša je odgovornost naučiti o algoritmima za planiranje CPU procesa koji prvi dolaze prvi služe.
Važne kratice
- CPU - - - > Središnja procesorska jedinica
- FCFS - - - > First Come First Serve
- AT - - - > Vrijeme dolaska
- BT - - - > Burst Time
- WT - - - > Vrijeme čekanja
- TAT - - - > Vrijeme preokreta
- CT - - - > Vrijeme završetka
- FIFO - - - > Prvi ušao prvi izašao
First Come First Serve
First Come First Serve CPU Scheduling Algorithm kratko poznat kao FCFS prvi je algoritam CPU Process Scheduling Algorithm. U algoritmu First Come First Serve ono što činimo je omogućiti procesu da se izvršava na linearan način.
To znači da koji god proces uđe proces koji prvi uđe u red čekanja spreman prvi se izvršava. Ovo pokazuje da algoritam 'prvi došao prvi poslužen' slijedi načelo 'prvi ušao prvi izašao' (FIFO).
Algoritam First Come First Serve može se izvršiti na Pre Emptive i Non Pre Emptive način. Prije nego što pređemo na primjere, shvatit ćemo što je pristup unaprijed i bez unaprijed u planiranju CPU procesa.
Pristup unaprijed
U ovom primjeru prethodnog planiranja procesa, OS dodjeljuje resurse procesu za unaprijed određeno vremensko razdoblje. Proces prelazi iz stanja rada u stanje spremnosti ili iz stanja čekanja u stanje spremnosti tijekom dodjele resursa. Ovo prebacivanje događa se jer CPU može drugim procesima dodijeliti prvenstvo i zamijeniti trenutno aktivni proces procesom višeg prioriteta.
Neprethodni pristup
U ovom slučaju Non-Emptive Process Scheduling, resurs se ne može povući iz procesa prije nego što se proces završi. Kada proces koji se izvodi završi i prijeđe u stanje čekanja, resursi se prebacuju.
Učinak konvoja u igri tko prvi dođe, prvi posluži (FCFS)
Učinak konvoja je fenomen koji se javlja u algoritmu raspoređivanja pod nazivom First Come First Serve (FCFS). Algoritam rasporeda 'prvi dođe prvi posluži' pojavljuje se na način koji nije preemptivan.
Nepreventivni način znači da ako se proces ili posao započne izvršavati, tada operativni sustav mora dovršiti svoj proces ili posao. Sve dok proces ili posao ne bude nula, novi ili sljedeći proces ili posao ne započinje svoje izvršenje. Definicija Non-Preemptive Scheduling u smislu operativnog sustava znači da će središnja procesorska jedinica (CPU) biti potpuno posvećena do kraja procesa ili posla koji je prvi započeo, a novi proces ili posao se izvršava tek nakon završetka starijeg procesa ili posao.
Može postojati nekoliko slučajeva koji mogu uzrokovati da središnja procesorska jedinica (CPU) odvoji previše vremena. To je zato što se u algoritmu raspoređivanja koji prvi dolazi, prvi služi pristupu bez preuzimanja, procesi ili poslovi biraju serijski. Zbog toga je kraćim poslovima ili procesima koji stoje iza većih procesa ili poslova potrebno previše vremena za dovršetak izvršenja. Zbog toga je vrijeme čekanja, vrijeme obrade i vrijeme završetka vrlo visoko.
Dakle, ovdje kako je prvi proces velik ili je vrijeme dovršetka previsoko, tada dolazi do ovog efekta konvoja u algoritmu First Come First Serve.
Pretpostavimo da Duljem poslu treba beskonačno vrijeme da se dovrši. Zatim, preostali procesi moraju čekati isto beskonačno vrijeme. Zbog ovog efekta konvoja stvorenog dužim poslom, izgladnjivanje procesa čekanja raste vrlo brzo. Ovo je najveći nedostatak FCFS CPU Process Scheduling.
Karakteristike raspoređivanja procesa FCFS CPU
Karakteristike FCFS CPU Process Scheduling su:
- Implementacija je jednostavna.
- Ne uzrokuje uzročne posljedice tijekom korištenja
- Usvaja ne-preventivnu i preventivnu strategiju.
- Pokreće svaku proceduru redoslijedom kojim su primljene.
- Vrijeme dolaska koristi se kao kriterij odabira za postupke.
Prednosti FCFS CPU Process Scheduling
Prednosti FCFS CPU Process Scheduling su:
- Kako bi se alocirali procesi, koristi se red čekanja First In First Out.
- FCFS CPU Scheduling Process je jasan i jednostavan za implementaciju.
- U FCFS situaciji s preventivnim planiranjem, nema šanse da proces zastane.
- Budući da se ne uzima u obzir prioritet procesa, to je pravičan algoritam.
Nedostaci FCFS CPU Process Scheduling
Nedostaci FCFS CPU Process Scheduling su:
- Algoritam za raspoređivanje procesora FCFS ima dugo vrijeme čekanja
- FCFS CPU Scheduling daje prednost CPU-u nad ulaznim ili izlaznim operacijama
- U FCFS-u postoji mogućnost pojave efekta konvoja
- Budući da je FCFS tako jasan, često nije baš učinkovit. Uz to idu i produljena razdoblja čekanja. Sve ostale narudžbe ostaju u stanju mirovanja ako je CPU zauzet obradom jedne narudžbe koja oduzima puno vremena.
Problemi u CPU algoritmu za raspored 'prvi dođe prvi posluži'.
Primjer
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
Neprethodni pristup
Sada riješimo ovaj problem uz pomoć algoritma za raspoređivanje nazvanog First Come First Serve u pristupu bez prevencije.
Gantogram za gornji primjer 1 je:
Vrijeme okretanja = Vrijeme završetka - Vrijeme dolaska
Vrijeme čekanja = vrijeme preokreta - vrijeme pucanja
Rješenje gornjeg pitanja Primjer 1
| Da ne | ID procesa | Vrijeme dolaska | Vrijeme pucanja | Vrijeme završetka | Vrijeme obrade | Vrijeme čekanja | |
|---|---|---|---|---|---|---|---|
| 1 | P 1 | A | 0 | 9 | 9 | 9 | 0 |
| 2 | P 2 | B | 1 | 3 | 12 | jedanaest | 8 |
| 3 | P 3 | C | 1 | 2 | 14 | 13 | jedanaest |
| 4 | P 4 | D | 1 | 4 | 18 | 17 | 13 |
| 5 | P 5 | I | 2 | 3 | dvadeset i jedan | 19 | 16 |
| 6 | P 6 | F | 3 | 2 | 23 | dvadeset | 18 |
Prosječno vrijeme završetka je:
Prosječni CT = ( 9 + 12 + 14 + 18 + 21 + 23 ) / 6
Prosječni CT = 97 / 6
Prosječni CT = 16,16667
Prosječno vrijeme čekanja je:
Prosječna WT = (0 + 8 + 11 + 13 + 16 + 18) /6
Prosječna WT = 66 / 6
Prosječna WT = 11
Prosječno vrijeme obrade je:
Prosječni TAT = ( 9 + 11 + 13 + 17 + 19 +20 ) / 6
Prosječni TAT = 89 / 6
Prosječni TAT = 14,83334
Ovako je FCFS riješen u pristupu bez prevencije.
Hajde sada da shvatimo kako se oni mogu riješiti u Pre-Emptivnom pristupu
Pristup unaprijed
Sada riješimo ovaj problem uz pomoć algoritma za raspoređivanje pod nazivom First Come First Serve u pristupu unaprijed.
U Pre Emptive Approach tražimo najbolji dostupni proces
Gantogram za gornji primjer 1 je:
| Da ne | ID procesa | Vrijeme dolaska | Vrijeme pucanja | Vrijeme završetka | Vrijeme obrade | Vrijeme čekanja | |
|---|---|---|---|---|---|---|---|
| 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 | petnaest | 14 | 10 |
| 5 | P 5 | I | 2 | 3 | jedanaest | 9 | 7 |
| 6 | P 6 | F | 3 | 2 | 5 | 2 | 0 |
| sljedeći → ← prethodna Kako bi se riješio problema rasipanja signala za buđenje, Dijkstra je predložio pristup koji uključuje pohranjivanje svih poziva za buđenje. Dijkstra navodi da, umjesto da pozive za buđenje daje izravno potrošaču, proizvođač može pohraniti poziv za buđenje u varijablu. Bilo koji od potrošača može ga pročitati kad god to zatreba. Semafor je varijabla koja pohranjuje cjelokupne pozive za buđenje koji se prenose od proizvođača do potrošača. To je varijabla na kojoj se čitanje, izmjena i ažuriranje događa automatski u kernel modu. pretvoriti string datum Semafor se ne može implementirati u korisničkom načinu jer se stanje utrke uvijek može pojaviti kada dva ili više procesa pokušavaju istovremeno pristupiti varijabli. Uvijek je potrebna podrška operativnog sustava za implementaciju. Prema zahtjevima situacije, Semaphore se može podijeliti u dvije kategorije.
Detaljno ćemo razgovarati o svakom. |