5

CAPITO L

CPU
Programare

Exerciț ii de practică

5.1AAlgoritmul de planificare a CPU-ului determină un ordin pentru execuț ia acestuia

procese programate. Procesele date trebuie programate pe un proces-
sora, câte programe diferite sunt posibile? Dă o formulă în termeni
ofn.
Răspuns:
n!(nfactorial =n× n– 1× n – 2× ... × 2× 1).
5.2 Explica ț i diferen ț a dintre programarea preemptivă ș i cea non-preemptivă
ing.
Răspuns:
Planificarea preventivă permite unui proces să fie întrerupt în mijlocul
executarea sa, luând CPU-ul ș i alocându-l unei alte procese.
Programarea non-preemptivă asigură că un proces renunț ă la control
al CPU-ului doar atunci când îș i finalizează actuala explozie de CPU.

5.3 Să presupunem că următoarele procese sosesc pentru execu ț ie la momentele

indicat. Fiecare proces va rula pentru perioada de timp listată. Ca răspuns-
folosind programarea non-preemptivă ș i bazând toate deciziile
pe informaț iile pe care le ai în momentul în care trebuie luată decizia.

Proces Arrival Time Burst Time

P1 0.0 8
P2 0.4 4
P3 1.0 1

a. Care este timpul mediu de rota ț ie pentru aceste procese cu

Algoritmul de programare FCFS?

b. Care este timpul mediu de întoarcere pentru aceste procese cu

Algoritmul de programare SJF
c. Algoritmul SJF este destinat îmbunătă ț irii performan ț ei, dar observă
că am ales să rulăm processP1la timpul 0 pentru că nu ș tiau
115
116 Capitolul 5 Programarea CPU

cele două procese mai scurte vor sosi în curând. Calculează ce

timpul mediu de răspuns va fi dacă CPU-ul este lăsat inactiv pentru prima
1 unit ș i apoi programarea SJF este folosită. Amintiț i-vă că procesele
P1ș iP2aș teaptă în acest timp liber, aș a că timpul lor de aș teptare
ar putea creș te. Acest algoritm ar putea fi cunoscut sub numele de cunoș tinț e viitoare
planificare.

Răspuns:
a. 10.53
b. 9.53
c. 6.86
Amintiț i-vă că timpul de răsturnare este timpul de finalizare minus timpul de sosire, aș a că
trebuie să scazi timpul de sosire pentru a calcula timpii de întoarcere.
FCFS este 11 dacă uiț i să scazi timpul de sosire.

5.4 Considera ț i următorul set de procese, cu lungimea burst-ului CPU

timpul dat în milisecunde:

Proces Burst Time Priority

P1 2 2
P2 1 1
P3 8 4
P4 4 2
P5 5 3

Procesele se presupune că au sosit în ordine P1 ,P2 ,P3 ,P4 ,P5 ,

toate la timpul 0.

a. Desena ț i patru diagrame Gantt care ilustrează execu ț ia acestor pro-

procese utilizând următoarele algoritmi de planificare: FCFS, SJF, non-
prioritate preventivă (un număr de prioritate mai mare implică o prioritate mai mare)
prioritate), ș i RR(quantum = 2).
b. Care este timpul de întoarcere pentru fiecare proces pentru fiecare dintre
algoritmii de programare în partea a?
c. Care este timpul de a ș teptare pentru fiecare proces pentru fiecare dintre aceste programări
algoritmi de învăț are?

d. Care dintre algoritmi rezultă în timpul mediu minim de a ș teptare

time (over all processes)?

Răspuns:
a. Cele patru diagrame Gantt:

P1 P2 2 P3 3 P4 4 P5 5
0 2 3 2 3 11 11 15 15 20
 Exerciț ii de practică 117

P2 P1 P4 P5 P3
0 1 3 7 12 20

P3 P5 P1 P4 P2
0 8 13 15 19 20

P1 P2 P3 P4 P5 P3 P4 P5 P3 P5 P3
0 2 3 5 7 9 11 13 15 17 18 20

b. Turnaround time:

FCFS SJF Prioritate RR

P1 2 3 15 2
P2 3 1 20 3
P3 11 20 8 20
P4 15 7 19 13
P5 20 12 13 18
[Link] time (turnaround time minus burst time):

FCFS SJF Prioritate RR

P1 0 1 13 0
P2 2 0 19 2
P3 3 12 0 12
P4 11 3 15 9
P5 15 7 8 13
d. SJF are cel mai scurt timp de a ș teptare.

5.5 Urcătoarele următoare sunt programate folosind o metodă preemptivă, rotativă.

algoritmul de planificare Robin

Proces Priority Explozie Sosire

P1 40 20 0
P2 30 25 25
P3 30 25 30
P4 35 15 60
P5 5 10 100
P6 10 10 105

Fiecare proces este asignat o prioritate numerică, cu un număr mai mare indicând
Acordând o prioritate relativă mai mare. Pe lângă procesele enumerate mai sus,
sistemul are, de asemenea, o sarcină inactivă (care nu consumă resurse CPU ș i
118 Chapter 5 CPU Scheduling

este identificat caPinactiv). This task has priority 0 and is scheduled when-
oricând sistemul nu are alte procese disponibile pentru a fi rulate. Lungimea unui
timpul cuantic este de 10 unităț i. Dacă un proces este suspendat de o prioritate mai mare
procesul, procesul preemptat este plasat la sfârș itul cozii.
a. Arată ordinea de planificare a proceselor folosind un grafic Gantt.
b. Care este timpul de răspuns pentru fiecare proces?
c. Care este timpul de a ș teptare pentru fiecare proces?

d. Care este rata de utilizare a CPU-ului?

Answer:
a. Diagrama Gantt:

P1 inactiv P2 P3 P2 P3 P4 P2 P3 inactiv P5 P6 P5

0 20 25 35 45 55 60 75 80 90 100 105 115 120

b. P1: 20-0 - 20, P2: 80-25 = 55, P3: 90 - 30 = 60, P4: 75-60 = 15, P5:
120-100 = 20, P6: 115-105 = 10
c. P1: 0, p2: 40, P3: 35, P4: 0, P5: 10, P6: 0
d. 105/120 = 87,5 procente.
5.6 Ce avantaj există în a avea dimensiuni diferite ale timpului cuantificat în diferite
niveluri diferite ale unui sistem de coadă multilevel?
Răspuns:
Procesele care necesită o întreț inere mai frecventă - de exemplu, interactive
procese precum editorii - pot fi într-o coadă cu un mic cuantum de timp.
Procesele care nu necesită întreț inere frecventă pot fi într-o coadă cu
un quantum mai mare, care necesită mai puț ine comutări de context pentru a finaliza
procesarea ș i astfel utilizarea mai eficientă a computerului.
5.7 Multe algoritmi de planificare a CPU-ului sunt parametriza ț i. De exemplu,
Algoritmul RR necesită un parametru pentru a indica fereastra de timp. Multilevel
cozile de feedback necesită parametrii pentru a defini numărul de cozi,
algoritmii de programare pentru fiecare coadă, criteriile folosite pentru a muta
procese între cozi, ș i aș a mai departe.
Aceste algoritmi sunt, prin urmare, de fapt seturi de algoritmi (de exemplu, setul
de algoritmi pentru toate intervalele de timp ș i aș a mai departe). Un set de algoritmi poate
includeti un altul (de exemplu, algoritmul FCFS este algoritmul RR)
cu un cuantum de timp infinit). Ce (dacă există) relaț ie există între
următoarele perechi de seturi de algoritmi?

a. Prioritate ș i SJF
b. Cozi de feedback multilaterale ș i FCFS
c. Prioritate ș i FCFS
[Link]
 Exerciț ii de practică 119

Răspuns:
a. Cea mai scurtă muncă are cea mai mare prioritate.
b. Cel mai scăzut nivel al MLFQ este FCFS.

[Link] acordă cea mai mare prioritate locului de muncă care a existat
cel mai lung.
d. Niciunul.

5.8 Să presupunem că un algoritm de planificare a CPU-ului favorizează procesele care

au folosit cel mai puț in timp al procesorului în trecutul recent. De ce va fi aceasta
algoritm favorizează programele I/O-bound ș i totuș i să nu sufere niciodată de foamete permanentă
Programe legate de CPU?
Answer:
Va favoriza programele legate de I/O datorită duratei relativ scurte
CPU-urile solicitate de ei; totuș i, programele legate de CPU vor
nu înfometeze, deoarece programele limitate de I/O vor ceda CPU-ul
relativ frecvent să facă I/O-ul lor.
5.9 Distinge între programarea PCS ș i SCS.
Răspuns:
Planificarea PC este locală procesului. Este modul în care biblioteca de thread-uri planifică
se înfăș oară firele pe LWP-uri disponibile. Programarea SCS este folosită atunci când oper-
sistemul de operare programează firele de kernel. Pe sistemele care folosesc fie...
modelul mulț i-la-unu sau modelul mulț i-la-mulț i, cele două modele de planificare
sunt fundamental diferite. Pe sistemele care utilizează modelul unu-la-unu,
PCSandSCS sunt aceleaș i.

5.10 Planificatorul UNIX tradi ț ional impune o rela ț ie inversă între

numere de prioritate ș i priorităț i: cu cât numărul este mai mare, cu atât mai mic este
[Link] recalculează priorităț ile proceselor o dată pe secundă
folosind următoarea funcț ie:
Prioritate = (utilizarea recentă a CPU-ului / 2) + bază

unde baza = 60 andrecentutilizarea CPUse referă la o valoare care indică modul în care
adesea un proces a folosit CPU-ul din ultima dată când priorităț ile au fost recalculate.
Presupuneț i că recentCPUusage pentru processP1este 40, pentru procesP2are 18,
ș i pentru processP3Este 10. Care vor fi noile priorităț i pentru aceste trei?
procese când priorităț ile sunt recalculte? Pe baza acestei informaț ii,
schedulerul UNIX tradiț ional măreș te sau micș orează prioritatea relativă
al unui proces legat de CPU?
Răspuns:
Priorităț ile atribuite proceselor vor fi 80, 69 ș i 65.
Scheduler-ul scade prioritatea relativă a proceselor legate de CPU.
procese.