Skip to main content

Prioritats, SJF/SRTF, cues multinivell, MLFQ

Author

Jordi Mateo Fornés

Objectius d'Aprenentatge
  • Planificar amb prioritats, SJF, SRTF i cues multinivell, amb i sense E/S.
  • Reconèixer i resoldre inanició (envelliment) i inversió de prioritats (herència).
  • Predir ràfegues amb la mitjana exponencial i entendre el paper d’\(\alpha\).
  • Aplicar les regles de l’MLFQ, el boost i la comptabilitat del temps acumulat.
  • Calcular el repartiment de CPU de CFS a partir del nice.

Convenis

Són els mateixos que al full anterior, amb tres afegits per a les polítiques noves.

Concepte — Model d'execució
  1. Temps discret: la columna \(t\) és l’interval \([t, t+1)\).
  2. Ràfegues de CPU i d’E/S alternades; tot procés comença i acaba amb CPU.
  3. Cada procés té el seu dispositiu: les E/S no fan cua. Un procés que acaba l’E/S a \(t\) és preparat a \(t\).
  4. Una sola CPU (llevat que es digui el contrari) i canvi de context de cost zero.
Pista d'Examen — Desempat i expulsions
  • Entrades simultànies a una cua (arribades i retorns d’E/S): per prioritat (1 és la més alta).
  • Un procés expulsat (per quantum o per un procés més prioritari) torna al final de la seva cua, darrere dels que entren en aquell instant, amb el quantum reiniciat. Excepció: a l’MLFQ (Problemes 10 i 11), un procés expulsat per un nivell superior conserva el quantum restant.
  • SJF/SRTF treballen amb la ràfega actual (o el que en queda), no amb el total del procés. Amb SRTF només hi ha expulsió si el nou és estrictament més curt; en cas d’empat, per prioritat.
  • Prioritats: un procés només n’expulsa un altre si té prioritat estrictament més alta.

Mètriques

Mètrica Definició
\(T_{espera}\) Temps a la cua de preparats (caselles P). No inclou E/S ni el temps bloquejat esperant un lock.
\(T_{resposta}\) \(T_{inici} - T_a\)
\(T_{retorn}\) \(T_f - T_a\)
\(T_N\) \(T_{retorn} / (T_{cpu} + T_{E/S})\)
Utilització CPU ocupada / (\(n_{CPU} \cdot T_{final}\))
Productivitat processos acabats / \(T_{final}\)

Llegenda: E execució · W E/S · P preparat · B bloquejat esperant un lock · C execució dins d’una secció crítica · F finalitzat. A l’MLFQ, el número que acompanya E o P és el nivell del procés (0 = el més alt).

Podeu utiltizar plantilla

Problema 3 · Cues multinivell sense retroalimentació

En un sistema amb 1 CPU s’executen els processos següents:

Procés Tipus Cua \(T_a\) Prioritat Ràfegues
A Temps real crític 1 5 1 \(1_{CPU},\ 1_{E/S},\ 2_{CPU},\ 3_{E/S},\ 1_{CPU}\)
B Temps real 2 0 2 \(2_{CPU},\ 3_{E/S},\ 1_{CPU},\ 3_{E/S},\ 1_{CPU}\)
C Interactiu 3 2 3 \(4_{CPU},\ 4_{E/S},\ 2_{CPU},\ 2_{E/S},\ 1_{CPU}\)
D Interactiu 3 3 4 \(1_{CPU},\ 4_{E/S},\ 3_{CPU},\ 4_{E/S},\ 2_{CPU}\)
E Batch 4 4 5 \(2_{CPU},\ 2_{E/S},\ 4_{CPU},\ 1_{E/S},\ 2_{CPU}\)
F Batch 4 4 6 \(4_{CPU},\ 1_{E/S},\ 2_{CPU}\)

El planificador a curt termini té 4 cues. Cada procés hi és assignat de manera fixa:

Cua Processos Algorisme
1 (la més prioritària) Temps real crític FCFS
2 Temps real Round Robin, \(q = 1\)
3 Interactius Round Robin, \(q = 3\)
4 (la menys prioritària) Batch SRTF
  • Entre cues hi ha prioritat estricta: una cua només s’atén si totes les més prioritàries són buides.
  • L’apropiació entre cues és immediata: quan un procés d’una cua més prioritària passa a preparat, expulsa el que s’executa.
  • Els empats dins una mateixa cua es desfan per prioritat (1 la més alta, 6 la més baixa).
  1. Dibuixa el diagrama de Gantt.
  2. Calcula totes les mètriques per a cada procés.
  3. Analitza l’impacte de la planificació multinivell sobre cada classe de procés i sobre el rendiment del sistema.
Solució: planificació multinivell
Solució — planificació multinivell
Procés 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
A E W E E W W W E F
B E E W W W P E W W W E F
C E E E P P P P P P E W W W W P E E W W E F
D P P P P P P E W W W W E E E W W W W P E E F
E P P P P P P P P P E P P P P P E W W P P P P P E P P E E E W E E F
F P P P P P P P P P P P P P P P P E P P P E E E W E E F
CPU B B C C C A B A A D B C A E D D D C C E F C D D F F F E F F E E E – E E
Mètrica A B C D E F Mitjana
\(T_f\) 13 11 22 24 36 30 –
\(T_{espera}\) 0 1 7 7 21 19 9.17
\(T_{resposta}\) 0 0 0 6 9 16 5.17
\(T_{retorn}\) 8 11 20 21 32 26 19.67
\(T_N\) 8/8 = 1 11/10 = 1.1 20/13 = 1.54 21/14 = 1.5 32/11 = 2.91 26/7 = 3.71 1.96

Utilització de la CPU \(= 35/36 \approx 97\,\%\) · Productivitat \(= 6/36 \approx 0.17\) processos/u.t. · Final: \(t = 36\).

Instants clau:

  • \(t=5\): C esgota el quantum alhora que A arriba (cua 1) i B torna d’E/S (cua 2). S’executa A; C passa al final de la cua 3, darrere de D.
  • \(t=13\): les cues 1–3 són buides. SRTF tria E (ràfega 2) davant de F (4).
  • \(t=14\): D torna d’E/S (cua 3) i expulsa E (cua 4).
  • \(t=21\): C i D tornen d’E/S alhora; entra primer C per prioritat. F és expulsat.
  • \(t=28\): F torna d’E/S amb una ràfega de 2, menys que les 3 que li queden a E: F expulsa E dins la cua 4.
  • \(t=33\): CPU ociosa. E fa E/S i tots els altres han acabat.
Solució: anàlisi
Solució — anàlisi
Classe Processos \(\bar{T}_{espera}\) \(\bar{T}_{resposta}\) \(\bar{T}_N\)
Temps real A, B 0.5 0 1.05
Interactius C, D 7 3 1.52
Batch E, F 20 12.5 3.31
  • La planificació multinivell fa exactament el que promet: A i B no esperen gairebé mai i C i D tenen resposta acceptable. Tot el cost el paguen E i F: F no s’executa fins a \(t=20\), 16 unitats després d’arribar, i el seu \(T_N\) és 3.71.
  • El sistema en conjunt va bé: utilització del 97 % i una sola unitat ociosa. La prioritat estricta no malbarata CPU; només decideix qui espera.
  • Risc: amb una mica més de càrrega a les cues 1–3, els batch patirien inanició. La cua 4 no té cap garantia. Solucions: repartir la CPU per percentatges entre cues (p. ex. 60/25/10/5), envellir els processos que esperen o fer servir una MLFQ.
  • Atenció a la cua 1: és FCFS sense expulsió interna. Si A tingués una ràfega llarga, bloquejaria tot el sistema. Una cua de màxima prioritat només és segura si els seus processos tenen ràfegues curtes i acotades.

Problema 4 · Prioritats amb E/S: apropiativa o no?

Procés \(T_a\) Prioritat Ràfegues
A 0 3 \(3_{CPU},\ 2_{E/S},\ 2_{CPU}\)
B 1 1 \(2_{CPU},\ 3_{E/S},\ 1_{CPU}\)
C 2 4 \(4_{CPU}\)
D 3 2 \(1_{CPU},\ 2_{E/S},\ 2_{CPU}\)
  1. Planifica per prioritats a) no apropiatives i b) apropiatives.
  2. Calcula totes les mètriques.
  3. Quin procés guanya més amb l’apropiació? Quin no hi guanya res? Per què?
Solució: a) prioritats no apropiatives
Solució — a) prioritats no apropiatives
Procés 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A E E E W W P E E F
B P P E E W W W E F
C P P P P P P P P P E E E E F
D P P E W W P E E F
CPU A A A B B D A A B D D C C C C
Mètrica A B C D Mitjana
\(T_f\) 8 9 15 11 –
\(T_{espera}\) 1 2 9 3 3.75
\(T_{resposta}\) 0 2 9 2 3.25
\(T_{retorn}\) 8 8 13 8 9.25
\(T_N\) 8/7 = 1.14 8/6 = 1.33 13/4 = 3.25 8/5 = 1.6 1.83

Utilització de la CPU \(= 15/15 \approx 100\,\%\) · Productivitat \(= 4/15 \approx 0.27\) processos/u.t. · Final: \(t = 15\).

A \(t=1\) arriba B (prioritat 1), però A no deixa la CPU fins que es bloqueja a \(t=3\).

Solució: b) prioritats apropiatives
Solució — b) prioritats apropiatives
Procés 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A E P P P E E W W P E E F
B E E W W W E F
C P P P P P P P P P E E E E F
D E W W P E E F
CPU A B B D A A B D D A A C C C C
Mètrica A B C D Mitjana
\(T_f\) 11 7 15 9 –
\(T_{espera}\) 4 0 9 1 3.5
\(T_{resposta}\) 0 0 9 0 2.25
\(T_{retorn}\) 11 6 13 6 9
\(T_N\) 11/7 = 1.57 6/6 = 1 13/4 = 3.25 6/5 = 1.2 1.76

Utilització de la CPU \(= 15/15 \approx 100\,\%\) · Productivitat \(= 4/15 \approx 0.27\) processos/u.t. · Final: \(t = 15\).

B expulsa A a \(t=1\). A \(t=3\) B es bloqueja i D (2) passa davant d’A (3). A \(t=6\) B i D tornen d’E/S alhora: primer B i després D. A torna a \(t=8\), però D encara s’executa i és més prioritari.

Solució: discussió
Solució — discussió
  • Guanyen B i D, els més prioritaris: amb apropiació, el seu \(T_{resposta}\) passa de 2 a 0 i el \(T_{retorn}\) de 8 a 6.
  • A hi perd (de 8 a 11): és expulsat a \(t=1\) i, en tornar d’E/S, ha d’esperar D.
  • C no hi guanya res: en tots dos casos espera 9 unitats i acaba a \(t=15\). Té la prioritat més baixa i només s’executa quan tots els altres han acabat. Amb uns quants processos prioritaris més, patiria inanició (Problema 7).
  • La mitjana millora poc (9.25 → 9). L’apropiació redistribueix l’espera cap als menys prioritaris; no la redueix gaire.

Problema 5 · SJF, SRTF i l’optimalitat

Procés \(T_a\) \(T_{cpu}\)
A 0 8
B 1 4
C 2 9
D 3 5
E 5 2
  1. Planifica amb a) FCFS, b) SJF, c) SRTF i d) RR \(q=2\). Els empats es desfan per ordre alfabètic.
  2. Calcula \(\bar{T}_{espera}\), \(\bar{T}_{resposta}\) i \(\bar{T}_{retorn}\).
  3. Comprova que SRTF dona el mínim \(\bar{T}_{retorn}\). Dona també el mínim \(\bar{T}_{resposta}\)?
  4. Quin procés surt més perjudicat amb SRTF respecte de FCFS? Què passaria si arribessin processos curts contínuament?
Solució: a) FCFS
Solució — a) FCFS
Procés 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
A E E E E E E E E F
B P P P P P P P E E E E F
C P P P P P P P P P P E E E E E E E E E F
D P P P P P P P P P P P P P P P P P P E E E E E F
E P P P P P P P P P P P P P P P P P P P P P E E F
CPU A A A A A A A A B B B B C C C C C C C C C D D D D D E E
Mètrica A B C D E Mitjana
\(T_f\) 8 12 21 26 28 –
\(T_{espera}\) 0 7 10 18 21 11.2
\(T_{resposta}\) 0 7 10 18 21 11.2
\(T_{retorn}\) 8 11 19 23 23 16.8
\(T_N\) 8/8 = 1 11/4 = 2.75 19/9 = 2.11 23/5 = 4.6 23/2 = 11.5 4.39

Utilització de la CPU \(= 28/28 \approx 100\,\%\) · Productivitat \(= 5/28 \approx 0.18\) processos/u.t. · Final: \(t = 28\).

E necessita 2 unitats i n’espera 21: és el \(T_N\) més alt de tot el problema (11.5).

Solució: b) SJF
Solució — b) SJF
Procés 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
A E E E E E E E E F
B P P P P P P P P P E E E E F
C P P P P P P P P P P P P P P P P P E E E E E E E E E F
D P P P P P P P P P P P E E E E E F
E P P P E E F
CPU A A A A A A A A E E B B B B D D D D D C C C C C C C C C
Mètrica A B C D E Mitjana
\(T_f\) 8 14 28 19 10 –
\(T_{espera}\) 0 9 17 11 3 8
\(T_{resposta}\) 0 9 17 11 3 8
\(T_{retorn}\) 8 13 26 16 5 13.6
\(T_N\) 8/8 = 1 13/4 = 3.25 26/9 = 2.89 16/5 = 3.2 5/2 = 2.5 2.57

Utilització de la CPU \(= 28/28 \approx 100\,\%\) · Productivitat \(= 5/28 \approx 0.18\) processos/u.t. · Final: \(t = 28\).

A \(t=1\) arriba B, més curt, però SJF no expulsa A. A \(t=8\) s’escull E (2), després B (4) i després D (5).

Solució: c) SRTF
Solució — c) SRTF
Procés 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
A E P P P P P P P P P P P E E E E E E E F
B E E E E F
C P P P P P P P P P P P P P P P P P E E E E E E E E E F
D P P P P E E E E E F
E E E F
CPU A B B B B E E D D D D D A A A A A A A C C C C C C C C C
Mètrica A B C D E Mitjana
\(T_f\) 19 5 28 12 7 –
\(T_{espera}\) 11 0 17 4 0 6.4
\(T_{resposta}\) 0 0 17 4 0 4.2
\(T_{retorn}\) 19 4 26 9 2 12
\(T_N\) 19/8 = 2.38 4/4 = 1 26/9 = 2.89 9/5 = 1.8 2/2 = 1 1.81

Utilització de la CPU \(= 28/28 \approx 100\,\%\) · Productivitat \(= 5/28 \approx 0.18\) processos/u.t. · Final: \(t = 28\).

B expulsa A a \(t=1\) (4 < 7). A \(t=5\) acaba B i arriba E (2), que passa per davant de tothom. D no expulsa B a \(t=3\) perquè a B només li queden 2.

Solució: d) RR \(q = 2\)
Solució — d) RR $q = 2$
Procés 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
A E E P P P P E E P P P P P P P P E E P P P P E E F
B P E E P P P P P P E E F
C P P E E P P P P P P P P E E P P P P E E P P P E E E F
D P P P P P E E P P P P P P P P E E P P P P E F
E P P P P P P P E E F
CPU A A B B C C A A D D B B E E C C A A D D C C A A D C C C
Mètrica A B C D E Mitjana
\(T_f\) 24 12 28 25 14 –
\(T_{espera}\) 16 7 17 17 7 12.8
\(T_{resposta}\) 0 1 2 5 7 3
\(T_{retorn}\) 24 11 26 22 9 18.4
\(T_N\) 24/8 = 3 11/4 = 2.75 26/9 = 2.89 22/5 = 4.4 9/2 = 4.5 3.51

Utilització de la CPU \(= 28/28 \approx 100\,\%\) · Productivitat \(= 5/28 \approx 0.18\) processos/u.t. · Final: \(t = 28\).

Cap procés espera més de 7 unitats abans de la primera execució.

Solució: discussió
Solució — discussió
Política \(\bar{T}_{espera}\) \(\bar{T}_{resposta}\) \(\bar{T}_{retorn}\)
FCFS 11.2 11.2 16.8
SJF 8 8 13.6
SRTF 6.4 4.2 12
RR \(q=2\) 12.8 3 18.4
  • SRTF dona el mínim \(\bar{T}_{retorn}\) i \(\bar{T}_{espera}\), com diu la teoria.
  • No dona el mínim \(\bar{T}_{resposta}\): RR, amb 3, el millora. L’optimalitat de SRTF és respecte del retorn.
  • Qui més perd respecte de FCFS és A: l’espera li passa de 0 a 11 i el retorn de 8 a 19. A comença primer, SRTF l’expulsa a \(t=1\) i no torna a la CPU fins a \(t=12\): B, E i D, més curts, li passen davant. El seu \(T_{resposta}\), en canvi, no empitjora: continua sent 0.
Procés \(T_{espera}\) FCFS \(T_{espera}\) SRTF Diferència
A 0 11 +11
B 7 0 −7
C 10 17 +7
D 18 4 −14
E 21 0 −21
  • Qui té risc d’inanició és C, el més llarg: si arribessin processos curts contínuament, no s’executaria mai.
  • RR és el pitjor en retorn i el millor en resposta: és la mateixa tensió que a la sessió 04a.

Problema 6 · SRTF amb E/S: per a qui és bo?

Procés \(T_a\) Ràfegues
A 0 \(6_{CPU},\ 2_{E/S},\ 1_{CPU}\)
B 1 \(1_{CPU},\ 3_{E/S},\ 1_{CPU},\ 3_{E/S},\ 1_{CPU}\)
C 2 \(3_{CPU},\ 1_{E/S},\ 3_{CPU}\)

Empats: A > B > C.

  1. Planifica amb a) FCFS, b) RR \(q=2\) i c) SRTF (per ràfega).
  2. Calcula totes les mètriques.
  3. B és un procés limitat per E/S (com el procés C de l’exemple de Berkeley a la sessió 04b). Quan acaba B en cada cas? Què li passa al dispositiu de B?
  4. SRTF té el millor \(\bar{T}_{retorn}\) però el \(T_{final}\) més gran. Per què?
Solució: a) FCFS
Solució — a) FCFS
Procés 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
A E E E E E E W W P P E F
B P P P P P E W W W P E W W W E F
C P P P P P E E E W P E E E F
CPU A A A A A A B C C C A B C C C B
Mètrica A B C Mitjana
\(T_f\) 11 16 15 –
\(T_{espera}\) 2 6 6 4.67
\(T_{resposta}\) 0 5 5 3.33
\(T_{retorn}\) 11 15 13 13
\(T_N\) 11/9 = 1.22 15/9 = 1.67 13/7 = 1.86 1.58

Utilització de la CPU \(= 16/16 \approx 100\,\%\) · Productivitat \(= 3/16 \approx 0.19\) processos/u.t. · Final: \(t = 16\).

B arriba a \(t=1\) i no pot fer la seva ràfega d’1 unitat fins a \(t=6\), darrere de les 6 d’A.

Solució: b) RR \(q = 2\)
Solució — b) RR $q = 2$
Procés 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
A E E P P P E E P P E E W W P E F
B P E W W W P P E W W W P E F
C P E E P P E W P P E E P P E F
CPU A A B C C A A C B A A C C B A C
Mètrica A B C Mitjana
\(T_f\) 15 14 16 –
\(T_{espera}\) 6 4 7 5.67
\(T_{resposta}\) 0 1 1 0.67
\(T_{retorn}\) 15 13 14 14
\(T_N\) 15/9 = 1.67 13/9 = 1.44 14/7 = 2 1.7

Utilització de la CPU \(= 16/16 \approx 100\,\%\) · Productivitat \(= 3/16 \approx 0.19\) processos/u.t. · Final: \(t = 16\).

A \(t=2\) arriba C i A és expulsat: C entra abans que A.

Solució: c) SRTF
Solució — c) SRTF
Procés 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
A E P P P P P P P P P E E E E E W W E F
B E W W W E W W W E F
C E E E W E E E F
CPU A B C C C B C C C B A A A A A – – A
Mètrica A B C Mitjana
\(T_f\) 18 10 9 –
\(T_{espera}\) 9 0 0 3
\(T_{resposta}\) 0 0 0 0
\(T_{retorn}\) 18 9 7 11.33
\(T_N\) 18/9 = 2 9/9 = 1 7/7 = 1 1.33

Utilització de la CPU \(= 16/18 \approx 89\,\%\) · Productivitat \(= 3/18 \approx 0.17\) processos/u.t. · Final: \(t = 18\).

B i C expulsen A sempre que estan preparats. A no torna a la CPU fins a \(t=10\) i acaba la seva E/S quan ja no queda ningú: la CPU està ociosa a \(t=15\)–\(16\).

Solució: discussió
Solució — discussió
  • B acaba a \(t=16\) (FCFS), \(t=14\) (RR) i \(t=10\) (SRTF). Amb SRTF, B no espera mai (\(T_N = 1\)) i el seu dispositiu treballa sense interrupcions: és el comportament que volíem a l’exemple de Berkeley.
  • SRTF té el millor \(\bar{T}_{retorn}\) (11.33 contra 13 i 14) i \(\bar{T}_{resposta} = 0\).
  • El \(T_{final}\) és el més gran (18 contra 16) perquè A, el procés llarg, queda per al final. Quan fa l’E/S ja no hi ha ningú amb qui solapar-la i la CPU queda ociosa. SRTF optimitza la mitjana, no el temps total de la càrrega.
  • A és qui ho paga: espera 9 unitats amb SRTF, contra 2 amb FCFS.

Problema 7 · Inanició i envelliment

Planificació per prioritats apropiativa, sense E/S. Vuit processos \(J_1, \dots, J_8\) de prioritat 2 i ràfega 2 arriben a \(t = 0, 2, 4, \dots, 14\). El procés L, de prioritat 5 i ràfega 2, arriba a \(t=0\). A prioritat igual, s’executa el que fa més temps que espera.

Envelliment: cada \(K\) unitats consecutives a la cua de preparats, la prioritat d’un procés millora en 1 (fins a 1). Un procés conserva la prioritat envellida fins que acaba la seva ràfega.

  1. Planifica a) sense envelliment, b) amb \(K=2\) i c) amb \(K=4\).
  2. Calcula el \(T_{espera}\) de L i dels \(J_i\) en cada cas.
  3. Quin és el cost de l’envelliment? Qui el paga?
Solució: a) sense envelliment
Solució — a) sense envelliment
\(t\) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
CPU J1 J1 J2 J2 J3 J3 J4 J4 J5 J5 J6 J6 J7 J7 J8 J8 L L
Prioritat de L 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
J1 J2 J3 J4 J5 J6 J7 J8 L
\(T_f\) 2 4 6 8 10 12 14 16 18
\(T_{espera}\) 0 0 0 0 0 0 0 0 16

L només s’executa quan ja no queda cap \(J_i\): espera 16 unitats. Si els \(J_i\) no s’aturessin, L no s’executaria mai.

Solució: b) \(K = 2\)
Solució — b) $K = 2$
\(t\) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
CPU J1 J1 J2 J2 J3 J3 L L J4 J4 J5 J5 J6 J6 J7 J7 J8 J8
Prioritat de L 5 5 4 4 3 3 2 2
J1 J2 J3 J4 J5 J6 J7 J8 L
\(T_f\) 2 4 6 10 12 14 16 18 8
\(T_{espera}\) 0 0 0 2 2 2 2 2 6

A \(t=6\) la prioritat de L ha arribat a 2, la mateixa que \(J_4\), que acaba d’arribar. Com que L fa més temps que espera, guanya.

Solució: c) \(K = 4\)
Solució — c) $K = 4$
\(t\) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
CPU J1 J1 J2 J2 J3 J3 J4 J4 J5 J5 J6 J6 L L J7 J7 J8 J8
Prioritat de L 5 5 5 5 4 4 4 4 3 3 3 3 2 2
J1 J2 J3 J4 J5 J6 J7 J8 L
\(T_f\) 2 4 6 8 10 12 16 18 14
\(T_{espera}\) 0 0 0 0 0 0 2 2 12

L arriba a prioritat 2 a \(t=12\) i passa davant de \(J_7\).

Solució: discussió
Solució — discussió
  • L passa d’esperar 16 a esperar 6 (\(K=2\)) o 12 (\(K=4\)). Amb envelliment, el temps d’espera de L queda acotat independentment de quants processos prioritaris arribin.
  • El cost el paguen els \(J_i\) posteriors: cadascun espera 2 unitats que abans no esperava. El temps total no canvia (18): l’envelliment redistribueix l’espera.
  • Triar \(K\) és un compromís: un \(K\) petit desvirtua les prioritats; un \(K\) gran deixa esperar molt els processos poc prioritaris.

Problema 8 · Inversió de prioritats

Planificació per prioritats apropiativa, sense E/S. H i L comparteixen un lock \(S\); M no l’utilitza.

Procés \(T_a\) Prioritat Comportament
L 0 3 1 de CPU; agafa \(S\); 3 dins la secció crítica; allibera \(S\); 1 de CPU
H 2 1 1 de CPU; agafa \(S\); 2 dins la secció crítica; allibera \(S\); 1 de CPU
M 3 2 4 de CPU

Si un procés demana \(S\) i està ocupat, es bloqueja (no consumeix CPU) fins que s’allibera.

  1. Dibuixa el Gantt a) sense i b) amb herència de prioritat.
  2. Calcula \(T_{retorn}\) de cada procés en tots dos casos.
  3. Per què es diu que, sense herència, el bloqueig de H és no acotat? Hi hauria inversió de prioritats si M no existís?
Solució: a) sense herència
Solució — a) sense herència
Procés 0 1 2 3 4 5 6 7 8 9 10 11 12 13
H E B B B B B B C C E F
M E E E E F
L E C P P P P P C C P P P E F
CPU L L H M M M M L L H H H L

A \(t=3\) H demana \(S\), que té L, i es bloqueja. M arriba i, com que és més prioritari que L, s’executa durant 4 unitats. H espera M, un procés menys prioritari que ni tan sols usa \(S\).

\(T_{retorn}\): H = 10, M = 4, L = 13.

Solució: b) amb herència
Solució — b) amb herència
Procés 0 1 2 3 4 5 6 7 8 9 10 11 12 13
H E B B C C E F
M P P P P P E E E E F
L E C P C C P P P P P P P E F
CPU L L H L L H H H M M M M L

A \(t=3\) H es bloqueja a \(S\) i L hereta la prioritat 1. M arriba però no pot expulsar L. L acaba la secció crítica a \(t=5\), allibera \(S\) i recupera la prioritat 3. H continua.

\(T_{retorn}\): H = 6, M = 9, L = 13.

Solució: discussió
Solució — discussió
  • Sense herència, el temps que H passa bloquejat depèn de quanta feina tinguin els processos de prioritat intermèdia. Amb deu processos com M, H esperaria deu vegades més: el bloqueig no té cota.
  • Amb herència, H espera com a màxim el que queda de la secció crítica de L (aquí, 2 unitats). El bloqueig queda acotat per la durada de la secció crítica.
  • Sense M, H també esperaria L (2 unitats), però això és inevitable i acotat: és el preu d’una exclusió mútua, no una inversió. La inversió és que un procés de prioritat intermèdia retardi H.
  • M ho paga (de 4 a 9) i és correcte: M és menys prioritari que H.

Problema 9 · Mitjana exponencial

\[\tau_{n+1} = \alpha\, t_n + (1-\alpha)\,\tau_n\]

Prenem \(\tau_0 = 6\) i dues sèries de ràfegues reals:

  • Sèrie 1 (canvi de fase): \(4, 4, 4, 10, 10, 10\)
  • Sèrie 2 (soroll): \(8, 4, 8, 4, 8, 4\)
  1. Calcula les prediccions \(\tau_1, \dots, \tau_6\) amb \(\alpha = 1/2\) i amb \(\alpha = 1\) per a cada sèrie.
  2. Calcula l’error total \(\sum_n |\tau_n - t_n|\) (per a \(n = 0, \dots, 5\)) en cada cas.
  3. Quin \(\alpha\) és millor per a cada sèrie? Què en dedueixes?
Solució: prediccions i error
Solució — prediccions i error

Sèrie 1: \(t = 4, 4, 4, 10, 10, 10\)

\(n\) 0 1 2 3 4 5 6 Error total
\(t_n\) 4 4 4 10 10 10 –
\(\tau_n\), \(\alpha = 1/2\) 6 5 4.5 4.25 7.125 8.5625 9.28 13.56
\(\tau_n\), \(\alpha = 1\) 6 4 4 4 10 10 10 8

Sèrie 2: \(t = 8, 4, 8, 4, 8, 4\)

\(n\) 0 1 2 3 4 5 6 Error total
\(t_n\) 8 4 8 4 8 4 –
\(\tau_n\), \(\alpha = 1/2\) 6 7 5.5 6.75 5.375 6.6875 5.34 15.56
\(\tau_n\), \(\alpha = 1\) 6 8 4 8 4 8 4 22
  • Amb un canvi de fase (sèrie 1), \(\alpha = 1\) s’adapta de seguida i guanya.
  • Amb soroll (sèrie 2), \(\alpha = 1\) sempre prediu la ràfega anterior, que és justament la contrària. La mitjana amb \(\alpha = 1/2\) filtra el soroll i s’acosta a la mitjana real (6).
  • No hi ha un \(\alpha\) òptim universal: \(\alpha\) fixa el compromís entre rapidesa d’adaptació i robustesa al soroll. Valors habituals: \(\alpha \approx 1/2\).

Problema 10 · MLFQ

MLFQ amb 3 nivells: nivell 0 RR \(q=2\), nivell 1 RR \(q=4\), nivell 2 FCFS. Prioritat estricta entre nivells i apropiació immediata.

Concepte — Regles d'aquesta MLFQ
  1. Un procés nou entra al nivell 0.
  2. Si esgota el quantum en una tornada a la CPU, baixa un nivell i rep un quantum nou.
  3. Si es bloqueja abans d’esgotar-lo, es queda al mateix nivell. Quan torna d’E/S, rep un quantum nou.
  4. Si un procés d’un nivell superior l’expulsa, torna al final de la cua del seu nivell i conserva el quantum que li quedava: quan torni a la CPU, només podrà executar-se durant aquest restant.
  5. Boost (només a l’apartat b): en l’instant del boost, tots els processos no acabats passen al nivell 0 amb un quantum nou. Això inclou els preparats (en l’ordre en què eren a les cues), el que s’està executant i els bloquejats, que hi entraran quan tornin d’E/S.
Error Comú — Aquesta regla 4 és diferent de la resta del full

A la resta de problemes, un procés expulsat rep un quantum nou. Aquí el conserva. Amb l’altre conveni, la solució de l’apartat a canvia: A acabaria a \(t=14\) en lloc de \(t=18\).

Procés \(T_a\) Ràfegues
A 0 \(8_{CPU}\)
B 1 \(1_{CPU},\ 2_{E/S},\ 1_{CPU},\ 2_{E/S},\ 1_{CPU}\)
C 2 \(3_{CPU},\ 1_{E/S},\ 5_{CPU}\)

Empats: A > B > C.

  1. Planifica a) amb les regles 1–4 i b) afegint un boost a \(t=10\).
  2. Calcula les mètriques i indica en quin nivell és cada procés a cada instant.
  3. En aquest cas, el boost millora o empitjora? Quan és imprescindible?
Solució: a) regles 1–4
Solució — a) regles 1–4
Procés 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
A E0 E0 P1 P1 P1 P1 E1 E1 P1 P1 E1 E1 P2 P2 P2 P2 E2 E2 F
B P0 E0 W W E0 W W E0 F
C P0 E0 E0 P1 P1 P1 P1 E1 W P1 E1 E1 E1 E1 P2 P2 E2 F
CPU A A B C C B A A B C A A C C C C A A C
Mètrica A B C Mitjana
\(T_f\) 18 9 19 –
\(T_{espera}\) 10 1 8 6.33
\(T_{resposta}\) 0 1 1 0.67
\(T_{retorn}\) 18 8 17 14.33
\(T_N\) 18/8 = 2.25 8/7 = 1.14 17/9 = 1.89 1.76

Utilització de la CPU \(= 19/19 \approx 100\,\%\) · Productivitat \(= 3/19 \approx 0.16\) processos/u.t. · Final: \(t = 19\).

  • A i C baixen al nivell 1 en esgotar el primer quantum de 2.
  • B, que sempre es bloqueja abans, es queda al nivell 0 i expulsa A a \(t=8\). En aquell moment A ha gastat 2 dels 4 del seu quantum de nivell 1: en conserva 2.
  • A \(t=9\), C executa la unitat que li quedava de la primera ràfega i es bloqueja: es queda al nivell 1.
  • A \(t=10\), A reprèn amb el restant de 2. L’esgota a \(t=12\) i baixa al nivell 2.
  • C torna a \(t=11\) al nivell 1, s’executa a \(t=12\)–\(15\), esgota el quantum de 4 i també baixa al nivell 2, darrere d’A.
Solució: b) boost a \(t=10\)
Solució — b) *boost* a $t=10$
Procés 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
A E0 E0 P1 P1 P1 P1 E1 E1 P1 P1 E0 E0 P1 P1 E1 E1 F
B P0 E0 W W E0 W W E0 F
C P0 E0 E0 P1 P1 P1 P1 E1 W P0 E0 E0 P1 P1 E1 E1 E1 F
CPU A A B C C B A A B C A A C C A A C C C
Mètrica A B C Mitjana
\(T_f\) 16 9 19 –
\(T_{espera}\) 8 1 8 5.67
\(T_{resposta}\) 0 1 1 0.67
\(T_{retorn}\) 16 8 17 13.67
\(T_N\) 16/8 = 2 8/7 = 1.14 17/9 = 1.89 1.68

Utilització de la CPU \(= 19/19 \approx 100\,\%\) · Productivitat \(= 3/19 \approx 0.16\) processos/u.t. · Final: \(t = 19\).

  • Fins a \(t=10\) és idèntic a l’apartat a.
  • A \(t=10\), A (que era preparat al nivell 1 amb 2 de quantum restant) i C (que fa E/S) passen al nivell 0 amb quantum nou.
  • A gasta un quantum de 2 al nivell 0 i torna al nivell 1. C torna d’E/S a \(t=11\) directament al nivell 0, gasta el quantum de 2 a \(t=12\)–\(13\) i també baixa al nivell 1.
  • A acaba els 2 que li queden a \(t=14\)–\(15\), abans que C.
Solució: discussió
Solució — discussió
\(T_{retorn}\) A \(T_{retorn}\) B \(T_{retorn}\) C \(\bar{T}_{retorn}\)
Regles 1–4 18 8 17 14.33
Amb boost 16 8 17 13.67
  • Regles 1–4: B, l’interactiu, té \(T_N = 1.14\) i \(T_{resposta} = 1\). L’MLFQ l’ha identificat sense saber res d’ell. A i C, limitats per CPU, baixen de nivell: l’MLFQ aproxima SRTF.
  • Amb boost, A millora (18 → 16) i els altres no hi perden. Sense boost, A acaba al nivell 2, darrere de la tanda de 4 de C al nivell 1. El boost li dona una segona oportunitat als nivells alts, just quan li queda poca feina.
  • El boost és imprescindible quan hi ha prou processos interactius per ocupar sempre els nivells alts: sense boost, els dels nivells baixos no s’executarien mai. També permet que un procés que ha canviat de comportament (de càlcul a interactiu) recuperi la prioritat.
  • El boost no és gratuït: si es fa massa sovint, els processos de càlcul tornen a competir amb els interactius i l’MLFQ s’assembla a un RR.

Problema 11 · MLFQ: fer trampa

MLFQ amb 2 nivells: nivell 0 RR \(q=3\), nivell 1 FCFS. Expulsions entre nivells com al Problema 10 (regla 4). No hi ha boost.

Definició — Quantum i allotment
  • Quantum: temps màxim d’execució consecutiva en una tornada a la CPU. Quan s’esgota, el procés deixa la CPU.
  • Allotment: pressupost acumulat de CPU que un procés pot gastar en un nivell, sumant totes les seves tornades. Quan s’esgota, el procés baixa de nivell.

Amb les regles bàsiques, l’allotment és, de fet, el quantum d’una sola tornada: com que cada bloqueig el posa a zero, un procés que es bloqueja sovint no baixa mai. Aquí és on hi ha la trampa.

Procés \(T_a\) Ràfegues
N (honest) 0 \(8_{CPU}\)
T (tramposo) 0 \(2_{CPU},\ 1_{E/S},\ 2_{CPU},\ 1_{E/S},\ 2_{CPU},\ 1_{E/S},\ 2_{CPU}\)

T fa una E/S inútil just abans d’esgotar el quantum, com el programa d’Othello de la sessió 04b. Empats: N > T.

  1. a) Regles bàsiques. Un procés baixa de nivell si esgota el quantum de 3 en una sola tornada.
  2. b) Comptabilitat acumulada. Quantum de 3 i allotment de 5 al nivell 0.
    • Si esgota el quantum però no l’allotment, torna al final del nivell 0.
    • Si esgota l’allotment, baixa al nivell 1 immediatament, encara que sigui a mitja ràfega. També si l’esgota just en acabar una ràfega.
    • L’allotment no es posa a zero quan el procés es bloqueja.
  3. Compara \(T_{retorn}\) de N i de T en tots dos casos.
  4. Compara-ho amb el cas en què T és honest: una sola ràfega de 8 unitats de CPU i cap E/S. La trampa li surt a compte?
Solució: a) regles bàsiques
Solució — a) regles bàsiques
Procés 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
N E0 E0 E0 P1 P1 E1 P1 P1 E1 P1 P1 E1 P1 P1 E1 E1 F
T P0 P0 P0 E0 E0 W E0 E0 W E0 E0 W E0 E0 F
CPU N N N T T N T T N T T N T T N N
Mètrica N T Mitjana
\(T_f\) 16 14 –
\(T_{espera}\) 8 3 5.5
\(T_{resposta}\) 0 3 1.5
\(T_{retorn}\) 16 14 15
\(T_N\) 16/8 = 2 14/11 = 1.27 1.64

Utilització de la CPU \(= 16/16 \approx 100\,\%\) · Productivitat \(= 2/16 \approx 0.12\) processos/u.t. · Final: \(t = 16\).

N esgota el quantum a \(t=3\) i baixa al nivell 1. T es bloqueja sempre després de 2 unitats, no esgota mai el quantum i no baixa mai: cada vegada que torna d’E/S expulsa N.

Solució: b) comptabilitat acumulada (allotment 5)
Solució — b) comptabilitat acumulada (allotment 5)
Procés 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
N E0 E0 E0 P0 P0 E0 E0 P1 P1 E1 P1 E1 E1 F
T P0 P0 P0 E0 E0 W P0 E0 E0 W E0 P1 P1 E1 W E1 E1 F
CPU N N N T T N N T T N T N N T – T T
Mètrica N T Mitjana
\(T_f\) 13 17 –
\(T_{espera}\) 5 6 5.5
\(T_{resposta}\) 0 3 1.5
\(T_{retorn}\) 13 17 15
\(T_N\) 13/8 = 1.62 17/11 = 1.55 1.59

Utilització de la CPU \(= 16/17 \approx 94\,\%\) · Productivitat \(= 2/17 \approx 0.12\) processos/u.t. · Final: \(t = 17\).

  • N esgota el quantum a \(t=3\) amb 3 unitats d’allotment gastades: es queda al nivell 0, al final de la cua.
  • N acumula 5 unitats a \(t=7\) (3 + 2) i baixa al nivell 1.
  • T arriba a 5 a \(t=11\) (2 + 2 + 1) sense haver esgotat mai el quantum: baixa al nivell 1 a mitja ràfega, darrere de N.
  • A partir d’aquí, tots dos són al nivell 1 (FCFS) i competeixen en igualtat de condicions.
Solució: discussió
Solució — discussió
Cas \(T_{retorn}\) N \(T_{retorn}\) T
Regles bàsiques, T tramposo 16 14
Regles bàsiques, T honest 11 16
Allotment 5, T tramposo 13 17
Allotment 5, T honest 13 16
  • Amb les regles bàsiques, la trampa funciona. T passa de 16 a 14 tot i fer 3 unitats d’E/S de més, i ho paga N, que passa d’11 a 16.
  • Amb allotment, la trampa no funciona. N obté 13 tant si T fa trampa com si no: el comportament de T ja no l’afecta. T tramposo acaba a 17, pitjor que T honest (16), perquè les E/S inútils ara només li fan perdre temps.
  • La clau és la diferència entre els dos conceptes. El quantum limita una tornada i un bloqueig el reinicia: es pot esquivar. L’allotment suma totes les tornades: no es pot esquivar bloquejant-se.
  • És la regla que proposa OSTEP (cap. 8) per tancar aquest forat.
Error Comú — Errors freqüents
  • SJF sobre el total: SJF i SRTF comparen la ràfega actual (o el que en queda), no la suma de totes les ràfegues del procés.
  • SRTF amb empats: un procés que arriba amb el mateix temps restant no expulsa l’actual.
  • Comptar el bloqueig per un lock com a espera: les caselles B no són temps a la cua de preparats.
  • MLFQ: baixar de nivell en bloquejar-se. Amb les regles bàsiques només es baixa en esgotar el quantum.
  • Multinivell sense retroalimentació: canviar un procés de cua. A les cues fixes, cada procés es queda sempre a la seva.