Algoritmi de programare CPU în sistemele de operare

Ce este programarea procesorului?

CPU Scheduling este un proces de determinare a procesului care va deține CPU pentru execuție în timp ce un alt proces este în așteptare. Sarcina principală a programării procesorului este de a vă asigura că ori de câte ori CPU rămâne inactiv, sistemul de operare selectează cel puțin unul dintre procesele disponibile în coada pregătită pentru execuție. Procesul de selecție va fi realizat de programatorul CPU. Selectează unul dintre procesele din memorie care sunt pregătite pentru execuție.

În acest tutorial de planificare a procesorului, veți afla:

• Ce este programarea procesorului?
• Tipuri de programare CPU
• Terminologii importante de programare a procesorului
• Criterii de programare CPU
• Interval Timer
• Ce este Dispatcher?
• Tipuri de algoritm de planificare CPU
• Primul venit, primul servit
• Cel mai scurt timp rămas
• Programare bazată pe priorități
• Programare Round-Robin
• Cel mai scurt loc de muncă mai întâi
• Programarea cozilor pe mai multe niveluri
• Scopul unui algoritm de planificare

Tipuri de programare CPU

Iată două tipuri de metode de programare:

Programare preventivă

În programarea preventivă, sarcinile sunt atribuite în principal cu prioritățile lor. Uneori este important să rulați o sarcină cu o prioritate mai mare înainte de o altă sarcină cu prioritate mai mică, chiar dacă sarcina cu prioritate mai mică este încă în curs de executare. Sarcina cu prioritate inferioară se menține de ceva timp și se reia când sarcina cu prioritate superioară își termină executarea.

Programare non-preventivă

În acest tip de metodă de planificare, CPU-ul a fost alocat unui proces specific. Procesul care menține procesorul ocupat va elibera CPU fie prin schimbarea contextului, fie prin terminare. Este singura metodă care poate fi utilizată pentru diverse platforme hardware. Asta pentru că nu are nevoie de hardware special (de exemplu, un cronometru), cum ar fi planificarea preventivă.

Când programarea este preventivă sau non-preventivă?

Pentru a determina dacă planificarea este preventivă sau non-preventivă, luați în considerare acești patru parametri:

1. Un proces trece de la starea de funcționare la starea de așteptare.
2. Procesul specific trece de la starea de rulare la starea de pregătire.
3. Procesul specific trece de la starea de așteptare la starea de pregătire.
4. Procesul și-a încheiat execuția și sa încheiat.

Se aplică numai condițiile 1 și 4, programarea se numește nepreemptivă.

Toate celelalte planificări sunt preventive.

Terminologii importante de programare a procesorului

• Timp de rafală / Timp de execuție: este un timp necesar procesului pentru finalizarea executării. Se mai numește și timp de funcționare.
• Ora de sosire: când un proces intră într-o stare pregătită
• Timp de finalizare: când procesul este finalizat și iese dintr-un sistem
• Multiprogramare: Un număr de programe care pot fi prezente în memorie în același timp.
• Joburi: Este un tip de program fără niciun fel de interacțiune cu utilizatorul.
• Utilizator: este un fel de program cu interacțiune cu utilizatorul.
• Proces: este referința care este utilizată atât pentru job, cât și pentru utilizator.
• Ciclu de rafală CPU / IO: caracterizează execuția procesului, care alternează între activitatea CPU și I / O. Timpii procesorului sunt de obicei mai scurți decât timpul I / O.

Criterii de programare CPU

Un algoritm de planificare a procesorului încearcă să maximizeze și să minimizeze următoarele:

Maximizează:

Utilizarea CPU: utilizarea CPU este sarcina principală în care sistemul de operare trebuie să se asigure că CPU rămâne cât mai ocupat posibil. Poate varia de la 0 la 100%. Cu toate acestea, pentru RTOS, poate varia de la 40 la sută pentru nivelul scăzut și 90 la sută pentru sistemul de nivel înalt.

Transfer : Numărul de procese care își finalizează execuția pe unitate de timp este cunoscut. Deci, atunci când CPU-ul este ocupat cu executarea procesului, în acel moment, se lucrează, iar lucrarea finalizată pe unitate de timp se numește Transfer.

Minimizați:

Timp de așteptare: Timpul de așteptare este o sumă pe care procesul specific trebuie să o aștepte în coada pregătită.

Timpul de răspuns: este o cantitate de timp în care cererea a fost depusă până când se produce primul răspuns.

Timpul de răspuns: timpul de răspuns este o perioadă de timp pentru a executa un anumit proces. Este calculul timpului total petrecut în așteptare pentru a intra în memorie, așteptând în coadă și, executând pe CPU. Perioada dintre momentul depunerii procesului și timpul de finalizare este timpul de schimbare.

Interval Timer

Întreruperea temporizatorului este o metodă care este strâns legată de preempțiune. Când un anumit proces primește alocarea CPU, un temporizator poate fi setat la un interval specificat. Atât întreruperea temporizatorului, cât și preempțiunea forțează un proces să returneze procesorul înainte ca rafala acestuia să fie finalizată.

Majoritatea sistemului de operare multi-programat folosește o formă de cronometru pentru a împiedica un proces să lege sistemul pentru totdeauna.

Ce este Dispatcher?

Este un modul care asigură controlul procesorului procesului. Dispecerul ar trebui să fie rapid, astfel încât să poată rula pe fiecare comutator de context. Latența de expediere este cantitatea de timp necesară programatorului CPU pentru a opri un proces și a începe altul.

Funcții îndeplinite de Dispatcher:

• Comutarea contextului
• Trecerea la modul utilizator
• Trecerea la locația corectă din programul nou încărcat.

Tipuri de algoritm de planificare CPU

Există în principal șase tipuri de algoritmi de planificare a proceselor

1. First Come First Serve (FCFS)
2. Programare pentru cea mai scurtă slujbă (SJF)
3. Cel mai scurt timp rămas
4. Programare prioritară
5. Programare Round Robin
6. Programarea cozii pe mai multe niveluri

Primul venit, primul servit

First Come First Serve este forma completă a FCFS. Este cel mai simplu și mai simplu algoritm de planificare a procesorului. În acest tip de algoritm, procesul care solicită procesorului primește mai întâi alocarea procesorului. Această metodă de planificare poate fi gestionată cu o coadă FIFO.

Pe măsură ce procesul intră în coada gata, PCB-ul său (blocul de control al procesului) este legat de coada cozii. Deci, atunci când CPU devine liber, acesta ar trebui să fie atribuit procesului la începutul cozii.

Caracteristicile metodei FCFS:

• Oferă algoritm de planificare non-preventiv și preventiv.
• Locurile de muncă sunt executate întotdeauna pe principiul primul venit, primul servit
• Este ușor de implementat și de utilizat.
• Cu toate acestea, această metodă este slabă ca performanță, iar timpul general de așteptare este destul de ridicat.

Cel mai scurt timp rămas

Forma completă a SRT este cel mai scurt timp rămas. Este, de asemenea, cunoscut sub numele de programare preventivă SJF. În această metodă, procesul va fi alocat sarcinii, care este cea mai apropiată de finalizarea sa. Această metodă împiedică un proces de stare pregătit mai nou să rețină finalizarea unui proces mai vechi.

Caracteristicile metodei de planificare SRT:

• Această metodă este aplicată mai ales în medii discontinue în care este necesar să se acorde preferință lucrărilor scurte.
• Aceasta nu este o metodă ideală pentru a-l implementa într-un sistem partajat în care timpul CPU necesar nu este cunoscut.
• Asociați-vă cu fiecare proces pe măsură ce lungimea următorului său procesor se sparg. Astfel, sistemul de operare utilizează aceste lungimi, ceea ce ajută la programarea procesului cu cel mai scurt timp posibil.

Programare bazată pe priorități

Planificarea prioritară este o metodă de planificare a proceselor bazată pe prioritate. În această metodă, planificatorul selectează sarcinile pentru a lucra conform priorității.

Planificarea prioritară ajută, de asemenea, sistemul de operare să implice atribuții prioritare. Procesele cu prioritate mai mare ar trebui să se desfășoare mai întâi, în timp ce locurile de muncă cu priorități egale se desfășoară pe bază de round-robin sau FCFS. Prioritatea poate fi stabilită pe baza cerințelor de memorie, a cerințelor de timp etc.

Programare Round-Robin

Round robin este cel mai vechi și mai simplu algoritm de planificare. Numele acestui algoritm provine din principiul round-robin, în care fiecare persoană primește o cotă egală din ceva la rândul său. Este folosit mai ales pentru planificarea algoritmilor în multitasking. Această metodă algoritmică ajută la executarea proceselor fără foamete.

Caracteristicile programării Round-Robin

• Round robin este un model hibrid care este acționat de ceas
• Felia de timp trebuie să fie minimă, care este alocată pentru a fi procesată o anumită sarcină. Cu toate acestea, poate varia pentru diferite procese.
• Este un sistem în timp real care răspunde la eveniment într-o anumită limită de timp.

Cel mai scurt loc de muncă mai întâi

SJF este o formă completă de (Cel mai scurt job mai întâi) este un algoritm de planificare în care ar trebui selectat procesul cu cel mai scurt timp de execuție pentru a fi executat în continuare. Această metodă de planificare poate fi preventivă sau non-preventivă. Reduce semnificativ timpul mediu de așteptare pentru alte procese care așteaptă executarea.

Caracteristicile programării SJF

• Este asociat fiecărei lucrări ca o unitate de timp de finalizat.
• În această metodă, când CPU este disponibil, următorul proces sau lucrare cu cel mai scurt timp de finalizare va fi executat mai întâi.
• Este implementat cu o politică non-preventivă.
• Această metodă algoritmică este utilă pentru procesarea de tip batch, unde așteptarea finalizării lucrărilor nu este critică.
• Îmbunătățește producția de locuri de muncă oferind locuri de muncă mai scurte, care ar trebui executate mai întâi, care au cea mai mare parte un timp de răspuns mai scurt.

Programarea cozilor pe mai multe niveluri

Acest algoritm separă coada pregătită în diferite cozi separate. În această metodă, procesele sunt alocate unei cozi pe baza unei proprietăți specifice a procesului, cum ar fi prioritatea procesului, dimensiunea memoriei etc.

Cu toate acestea, acesta nu este un algoritm de programare independent al sistemului de operare, deoarece trebuie să utilizeze alte tipuri de algoritmi pentru a programa lucrările.

Caracteristica programării cozilor la mai multe niveluri:

• Ar trebui menținute cozi multiple pentru procesele cu anumite caracteristici.
• Fiecare coadă poate avea algoritmi de planificare separate.
• Prioritățile sunt date pentru fiecare coadă.

Scopul unui algoritm de planificare

Iată motivele utilizării unui algoritm de planificare:

• CPU utilizează programarea pentru a-și îmbunătăți eficiența.
• Vă ajută să alocați resurse între procesele concurente.
• Utilizarea maximă a procesorului poate fi obținută prin multi-programare.
• Procesele care urmează să fie executate sunt în coadă gata.

Rezumat:

• Programarea procesorului este un proces de determinare a procesului care va deține CPU pentru execuție în timp ce un alt proces este în așteptare.
• În programarea preventivă, sarcinile sunt atribuite în principal cu prioritățile lor.
• În metoda de planificare non-preventivă, CPU-ul a fost alocat unui proces specific.
• Timpul de rafală este timpul necesar procesului pentru finalizarea execuției. Se mai numește și timp de rulare.
• Utilizarea CPU este principala sarcină în care sistemul de operare trebuie să se asigure că CPU rămâne cât mai ocupat posibil
• Numărul de procese care își termină execuția pe unitate de timp este cunoscut.
• Timpul de așteptare este o sumă pe care procesul specific trebuie să o aștepte în coada pregătită.
• Este o perioadă de timp în care cererea a fost depusă până la primirea răspunsului.
• Timpul de răspuns este o cantitate de timp pentru a executa un anumit proces.
• Întreruperea temporizatorului este o metodă strâns legată de preempțiune,
• Un dispecer este un modul care asigură controlul procesorului procesului.
• Șase tipuri de algoritmi de planificare a proceselor sunt:
• First Come First Serve (FCFS), 2) Shortest-Job-First (SJF) Programare 3) Cel mai scurt timp rămas 4) Prioritate Programare 5) Round Robin Programare 6) Programare coadă pe mai multe niveluri
• În metoda First Come First Serve, procesul care solicită CPU primește mai întâi alocarea CPU.
• În cel mai scurt timp rămas, procesul va fi alocat sarcinii, care este cea mai apropiată de finalizarea sa.
• În, Planificarea prioritară a planificatorului selectează sarcinile pentru a lucra conform priorității.
• În, această programare Round Robin funcționează pe principiu, în care fiecare persoană primește o cotă egală din ceva la rândul său
• În cea mai scurtă lucrare, mai întâi trebuie selectat cel mai scurt timp de execuție pentru executarea următoare
• În programarea pe mai multe niveluri, metoda separă coada pregătită în diferite cozi separate. În această metodă, procesele sunt atribuite unei cozi pe baza unei proprietăți specifice
• CPU utilizează programarea pentru a-și îmbunătăți eficiența.