Coadă de intrare - Input queue

În informatică , o coadă de intrare este o colecție de procese în stoc care așteaptă să fie aduse în memorie pentru a rula un program. Cozile de intrare sunt utilizate în principal în Planificarea sistemului de operare, care este o tehnică pentru distribuirea resurselor între procese. Cozi de intrare , nu se aplică numai sistemelor de operare (OS), dar pot fi aplicate și la programarea în interiorul dispozitivelor de rețea. Scopul programării este de a asigura distribuirea resurselor în mod echitabil și eficient; prin urmare, îmbunătățește performanțele sistemului.

În esență, o coadă este o colecție care are date adăugate în poziția din spate și eliminate din poziția din față. Există multe tipuri diferite de cozi, iar modul în care funcționează poate fi total diferit.

Sistemele de operare folosesc cozi First-Come, First-Served, Cel mai scurt timp rămas, Programare prioritară cu prioritate fixă, programare rotin -rotin și programare coadă pe mai multe niveluri.

Dispozitivele din rețea folosesc coada First-In-First-Out, coada corectă ponderată, Coada prioritară și Coada personalizată.

Sistem de operare

În sistemele de operare, procesele sunt încărcate în memorie și așteaptă ca rândul lor să fie executat de unitatea centrală de procesare (CPU). Programarea CPU gestionează stările procesului și decide când va fi executat un proces următor folosind coada de intrare.

Primul venit, primul servit

Procesele First-Come, First-Served sunt scoase din coadă în ordine consecutivă pentru a fi introduse în coadă. Cu această metodă, fiecare proces este tratat în mod egal. Dacă există două procese cu prioritate diferită și procesul de prioritate inferioară intră mai întâi în coadă, acesta va fi executat mai întâi. Această abordare poate să nu fie ideală dacă procesele diferite au priorități diferite, mai ales dacă procesele sunt de lungă durată.

Cel mai scurt timp rămas

Cea mai scurtă metodă de timp rămasă încearcă să prezice timpul de procesare a evoluțiilor și le plasează în coadă de la cel mai mic până la cel mai mare timp de procesare. Această metodă estimează și prezice pe baza înregistrărilor istorice anterioare. Pe termen lung, performanța sa nu este stabilă, dar îmbunătățește mai bine timpul de așteptare al procesului decât First-Come, First-Served.

Programare prioritară cu prioritate fixă

Metoda de planificare a priorităților cu prioritate fixă ​​atribuie priorități diferite proceselor în funcție de timpul lor de procesare și le aranjează în coadă în ordinea priorităților lor. Procesele serverului CPU de la prioritate mai mare la cea mai mică și procesele care au aceeași prioritate sunt servite ca First-Come, First-Servit. CPU va opri temporar difuzarea procesului cu prioritate scăzută atunci când procesul de prioritate mai mare va intra în coadă.

Programare rotundă

Metoda de planificare rotunjită va oferi aceeași perioadă de timp pentru fiecare proces și ciclu prin acestea. Această metodă se bazează puternic pe timpul acordat fiecărui proces. Timpul de alocare prea scurt va fragmenta procesele, iar timpul de alocare prea lung va crește timpul de așteptare pentru fiecare proces. Alegerea timpului corect alocat este baza acestei metode.

Planificarea cozii pe mai multe niveluri

Multe cozi sunt utilizate în metoda de planificare a cozii pe mai multe niveluri și fiecare coadă are propriul algoritm de planificare. Planificarea mai multor niveluri de coadă este mai complexă în comparație cu alte metode, dar oferă flexibilitate pentru sistemul de operare pentru a servi date diferite în situații complicate.

Rețele

În rețea, pachetele sunt fundamentul cheie pentru programare. Există multe tipuri diferite de pachete care călătoresc în jurul miezului de rețea în fiecare zi și sunt tratate total diferit. De exemplu, pachetele vocale și video au prioritate mai mare decât pachetele normale. Pentru a gestiona și distribui pachetul în mod eficient, dispozitivele de rețea folosesc, de asemenea, coada de intrare pentru a determina ce pachet va fi transmis mai întâi.

În primul rând, prima coadă la ieșire (FIFO)

În acest mod, pachetele sunt scoase din coadă în ordinea în care provin din coadă. Fiecare pachet este tratat cu aceeași prioritate. Dacă un pachet mare A vine înaintea unui pachet mic B, B trebuie să aștepte până când A este complet servit. Dacă un sistem tratează fiecare pachet la fel, utilizatorii pot experimenta întârzierea în transmitere, cum ar fi: pachete vocale.

Coada corectă ponderată (WFQ)

Coada corectă ponderată utilizează algoritmul min-max-fair-share pentru a distribui pachetele. Partajarea corectă minimă înseamnă că sistemul de operare al rețelei va distribui la fel de mult resursa minimă pentru fiecare tip de pachet. Partajarea corectă maximă înseamnă că sistemul de operare al rețelei va oferi mai multe resurse pentru pachetele care trebuie să transfere o cantitate mare de date în acel moment, dar va lua resursa înapoi după transfer. „Ponderați” înseamnă că programatorul va atribui greutate pentru fiecare tip de pachet. Pe baza greutății, va determina modul de a pune pachetul în coadă și de a le servi. De obicei, fiecare pachet va fi ponderat pe baza câmpului Precedență IP din antetul IP al fiecărui pachet.

Alocare echitabilă = (capacitatea resursei - resursă deja alocată) / numărul de pachete

Coadă de prioritate (PQ)

Coada de priorități este împărțită în 4 sub-cozi cu priorități diferite. Datele din fiecare coadă sunt furnizate numai atunci când cozile cu prioritate mai mare sunt goale. Dacă datele intră în coada goală cu prioritate mai mare în timp ce sistemul de operare de rețea transferă date de coadă cu prioritate inferioară, sistemul de operare de rețea va păstra datele din coada cu prioritate inferioară și va prelucra mai întâi datele din coada cu prioritate mai mare. Sistemul de operare al rețelei nu-i pasă de cât timp trebuie să aștepte rândul lor de prioritate mai mică, deoarece întotdeauna termină fiecare coadă de la cea mai mare la cea mai mică prioritate, înainte de a trece la următoarea coadă. În cadrul fiecărei cozi, pachetele sunt redirecționate pe baza bazei First-In-First-Out.

Coadă personalizată (CQ)

Coada personalizată este împărțită în 17 cozi secundare diferite. Prima coadă, coada 0, este rezervată sistemului de operare din rețea pentru a transmite pachetul de sistem, celelalte 16 cozi sunt destinate pachetelor definite de utilizator. Utilizatorul poate defini diverse pachete importante și le poate atribui în fiecare coadă. Fiecare coadă are dimensiuni limitate și va scăpa toate pachetele care vin dacă atinge această limită. Fiecare coadă este deservită în funcție de cât de multe pachete sunt servite în fiecare coadă. Dacă respectiva limită este respectată, sistemul de operare al rețelei va conține pachete de coadă curente și va servi următoarea coadă până când acea coadă este goală sau va ajunge la limita de pachete. Dacă o coadă este goală, sistemul de operare al rețelei va omite acea coadă și va servi următoarea coadă.

Referințe