În acest tutorial, vom învăța un concept important în algoritmii de programare a procesului CPU. Numele conceptului important este primul venit, primul servit. Acesta este algoritmul de bază pe care fiecare student trebuie să învețe pentru a înțelege toate elementele de bază ale algoritmilor de planificare a proceselor CPU.
First Come First Serve deschide calea pentru înțelegerea altor algoritmi. Acest algoritm poate avea multe dezavantaje. Dar aceste dezavantaje au creat algoritmi foarte noi și eficienți. Deci, este responsabilitatea noastră să învățăm despre algoritmii de planificare a proceselor CPU, primul venit, primul servit.
Abrevieri importante
- CPU - - - > Unitate centrală de procesare
- FCFS - - - > Primul venit, primul servit
- AT - - - > Ora sosirii
- BT - - - > Timp de explozie
- WT - - - > Timp de așteptare
- TAT - - - > Ora de întoarcere
- CT - - - > Timp de finalizare
- FIFO - - - > First In First Out
Primul venit, primul servit
Primul venit, primul servit Algoritmul de programare CPU, cunoscut pe scurt sub numele de FCFS, este primul algoritm al algoritmului de programare a procesului CPU. În algoritmul First Come First Serve ceea ce facem este să permitem procesului să se execute într-o manieră liniară.
dateformat.format
Aceasta înseamnă că orice proces care intră în procesul intră mai întâi în coada gata este executat primul. Acest lucru arată că algoritmul primul venit, primul servit urmează principiul First In First Out (FIFO).
Algoritmul primul venit, primul servit poate fi executat în mod pre-emptiv și non-pre-emptive. Înainte de a trece la exemple, să înțelegem ce este abordarea preemptivă și non-preemptivă în planificarea procesului CPU.
Abordare preemptivă
În acest caz de planificare pre-emptivă a procesului, sistemul de operare alocă resursele unui proces pentru o perioadă de timp predeterminată. Procesul trece de la starea de rulare la starea de pregătire sau de la starea de așteptare la starea de pregătire în timpul alocării resurselor. Această comutare are loc deoarece CPU-ul poate atribui prioritate altor procese și poate înlocui procesul activ în prezent cu procesul cu prioritate mai mare.
Abordare non-preemptivă
În acest caz de planificare non-preemptivă a procesului, resursa nu poate fi retrasă dintr-un proces înainte ca procesul să se încheie. Când un proces care rulează se termină și trece la starea de așteptare, resursele sunt schimbate.
Efectul convoiului în primul venit, primul servit (FCFS)
Efectul Convoi este un fenomen care are loc în algoritmul de programare numit First Come First Serve (FCFS). Algoritmul de programare primul venit, primul servit are loc într-un mod nepreemptiv.
Modul non-preemptive înseamnă că, dacă un proces sau un job este pornit de execuție, atunci sistemul de operare trebuie să își finalizeze procesul sau jobul. Până când procesul sau jobul este zero, procesul sau jobul nou sau următorul nu începe execuția. Definiția Planificării Non Preemptive în ceea ce privește Sistemul de Operare înseamnă că Unitatea Centrală de Procesare (CPU) va fi complet dedicată până la sfârșitul procesului sau jobului început prima și noul proces sau job este executat numai după terminarea procesului mai vechi sau loc de munca.
Pot exista câteva cazuri, care ar putea face ca Unitatea Centrală de Procesare (CPU) să aloce prea mult timp. Acest lucru se datorează faptului că în Abordarea non-preemptivă a algoritmului de planificare primul venit, primul servit, procesele sau locurile de muncă sunt alese în ordine serială. Datorită acestui fapt, joburile sau procesele mai scurte din spatele proceselor sau joburilor mai mari necesită prea mult timp pentru a finaliza execuția. Din acest motiv, timpul de așteptare, timpul de întoarcere, timpul de finalizare este foarte mare.
Deci, aici, deoarece primul proces este mare sau timpul de finalizare este prea mare, atunci are loc acest efect de Convoi în algoritmul First Come First Serve.
Să presupunem că Jobul mai lung necesită timp infinit pentru a fi finalizat. Apoi, procesele rămase trebuie să aștepte același timp infinit. Datorită acestui efect de convoi creat de Jobul mai lung, înfometarea proceselor de așteptare crește foarte rapid. Acesta este cel mai mare dezavantaj al programării procesului CPU FCFS.
Caracteristicile programării procesului CPU FCFS
Caracteristicile programării procesului CPU FCFS sunt:
- Implementarea este simplă.
- Nu provoacă nicio cauzalitate în timpul utilizării
- Adoptă o strategie non-preemptivă și preventivă.
- Ea rulează fiecare procedură în ordinea în care sunt primite.
- Ora sosirii este folosită ca criteriu de selecție pentru proceduri.
Avantajele programării procesului CPU FCFS
Avantajele programării procesului CPU FCFS sunt:
- Pentru a aloca procesele, folosește coada First In First Out.
- Procesul de programare a procesorului FCFS este simplu și ușor de implementat.
- În situația FCFS de programare preventivă, nu există nicio șansă de înfometare a procesului.
- Deoarece nu se ia în considerare prioritatea procesului, este un algoritm echitabil.
Dezavantajele programării procesului CPU FCFS
Dezavantajele programării procesului FCFS CPU sunt:
- Algoritmul de programare a procesorului FCFS are un timp lung de așteptare
- Programarea procesorului FCFS favorizează CPU-ul față de operațiunile de intrare sau de ieșire
- În FCFS există șansa de apariție a Efectului Convoiului
- Deoarece FCFS este atât de simplu, adesea nu este foarte eficient. Perioadele de așteptare prelungite merg mână în mână cu acest lucru. Toate celelalte comenzi sunt lăsate inactiv dacă procesorul este ocupat cu procesarea unei comenzi consumatoare de timp.
Probleme în algoritmul de programare a procesorului primul venit, primul servit
Exemplu
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
Abordare non-preemptivă
Acum, să rezolvăm această problemă cu ajutorul algoritmului de planificare numit Primul venit, primul servit într-o abordare non-preemptivă.
Diagrama Gantt pentru exemplul 1 de mai sus este:
Ora de întoarcere = Ora de finalizare - Ora de sosire
Timp de așteptare = Timp de întoarcere - Timp de explozie
Soluția la întrebarea de mai sus Exemplul 1
| Da nu | ID proces | Timpul sosirii | Timp de explozie | Timp de finalizare | Întoarceți Timpul | Timp de asteptare | |
|---|---|---|---|---|---|---|---|
| 1 | P 1 | A | 0 | 9 | 9 | 9 | 0 |
| 2 | P 2 | B | 1 | 3 | 12 | unsprezece | 8 |
| 3 | P 3 | C | 1 | 2 | 14 | 13 | unsprezece |
| 4 | P 4 | D | 1 | 4 | 18 | 17 | 13 |
| 5 | P 5 | ȘI | 2 | 3 | douăzeci și unu | 19 | 16 |
| 6 | P 6 | F | 3 | 2 | 23 | douăzeci | 18 |
Timpul mediu de finalizare este:
CT mediu = ( 9 + 12 + 14 + 18 + 21 + 23 ) / 6
CT mediu = 97 / 6
CT mediu = 16,16667
Timpul mediu de așteptare este:
întrebări de interviu în limba java
WT mediu = ( 0 + 8 + 11 + 13 + 16 + 18 ) /6
WT mediu = 66 / 6
WT mediu = 11
Timpul mediu de întoarcere este:
TAT mediu = ( 9 + 11 + 13 + 17 + 19 +20 ) / 6
TAT mediu = 89 / 6
TAT mediu = 14,83334
Așa se rezolvă FCFS în Abordarea Non Pre Emptive.
Acum, să înțelegem cum pot fi rezolvate în Abordarea Pre Emptive
Abordare preemptivă
Acum, să rezolvăm această problemă cu ajutorul algoritmului de planificare numit Primul venit, primul servit într-o abordare preemptivă.
În Pre Emptive Approach căutăm cel mai bun proces disponibil
Diagrama Gantt pentru exemplul 1 de mai sus este:
| Da nu | ID proces | Timpul sosirii | Timp de explozie | Timp de finalizare | Întoarceți Timpul | Timp de asteptare | |
|---|---|---|---|---|---|---|---|
| 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 | cincisprezece | 14 | 10 |
| 5 | P 5 | ȘI | 2 | 3 | unsprezece | 9 | 7 |
| 6 | P 6 | F | 3 | 2 | 5 | 2 | 0 |
| următorul → ← prev Pentru a scăpa de problema risipei semnalelor de trezire, Dijkstra a propus o abordare care presupune stocarea tuturor apelurilor de trezire. Dijkstra afirmă că, în loc să dea semnalul de trezire direct consumatorului, producătorul poate stoca semnalul de trezire într-o variabilă. Oricare dintre consumatori îl poate citi oricând trebuie să facă acest lucru. Semaforul este variabilele care stochează toate apelurile de trezire care sunt transferate de la producător la consumator. Este o variabilă pe care citirea, modificarea și actualizarea au loc automat în modul kernel. Semaforul nu poate fi implementat în modul utilizator, deoarece condiția de cursă poate apărea întotdeauna atunci când două sau mai multe procese încearcă să acceseze variabila simultan. Întotdeauna are nevoie de suport din partea sistemului de operare pentru a fi implementat. În funcție de cererea situației, Semaphore poate fi împărțit în două categorii.
Vom discuta pe fiecare în detaliu. |