Col·lecció d'exercicis resolts: Fonaments de Sistemes Operatius

Exercici 1. Conceptes bàsics: programa, executable i procés

Proporcioneu una definició clara i precisa dels conceptes següents en l'àmbit dels sistemes operatius:

a)

b)

c)

Exercici 2. Seqüència d'accions i canvis d'estat de dos processos

Considerant dos processos, A i B, que arriben/es creen en l'instant $t = 0$ i que s'executen d'acord amb el diagrama temporal següent:

Completeu els termes o conceptes indicats entre parèntesis (...) a la llista d'esdeveniments que es detallen tot seguit per tal de reconstruir la seqüència vàlida d'execució:

1.

El (SO) crea el (Procés A)

2.

El (SO) crea el (Procés B)

3.

El (SO) planifica l'execució del (Procés A)...

4.

El (procés A) passa de l'estat a l'estat

5.

Canvia la modalitat del processador a

6.

El (procés A) s'executa en el processador

7.

El (procés A) invoca una crida al sistema

8.

Canvia la modalitat del processador a

9.

El (procés A) passa de l'estat a l'estat

10.

El (SO) planifica l'execució del (procés B)

11.

El (procés B) passa de l'estat a l'estat

12.

Canvia la modalitat del processador a

13.

El (procés B) s'executa en el processador

14.

El (SO) rep una interrupció HW indicant final esdeveniment.

15.

Canvia la modalitat del processador a

16.

El (procés A) passa de l'estat a l'estat

17.

Canvia la modalitat del processador a

18.

El (procés B) s'executa en el processador

19.

El (procés B) finalitza

20.

Canvia la modalitat del processador a

21.

El (procés A) passa de l'estat a l'estat

22.

Canvia la modalitat del processador a

23.

El (procés A) s'executa en el processador

24.

El (procés A) finalitza

Exercici 3. Correlació d'accions en instants temporals concrets

A partir de la seqüència detallada d'accions de l'exercici anterior, associeu quin interval d'accions numèriques té lloc en cadascun dels instants de temps indicats a la taula:

Temps ($t$) · Núm. d'accions

2

4

5

Exercici 4. Traça d'execució i canvis de mode amb dos processos

Dos processos, $A$ i $B$, es creen en el temps $t = 0$ i tenen uns temps totals de servei de CPU de 13 i 3 unitats temporals, respectivament. El seu comportament s'indica en el diagrama:

Relleneu els camps entre parèntesis (...) de la seqüència completa d'execució per reflectir el flux del sistema:

1. El (SO) crea el (Procés A) i el (Procés B)

2. El (SO) planifica l'execució del (Procés A)

3. El (procés A) passa de l'estat

a l'estat

4. Canvia la modalitat del processador a

5. El (procés A) s'executa en el processador

6. El (procés A) invoca una crida al sistema

7. Canvia la modalitat del processador a

8. El (procés A) passa de l'estat

a l'estat

9. El (SO) planifica l'execució del (procés B)

10. El (procés B) passa de l'estat

a l'estat

11. Canvia la modalitat del processador a

12. El (procés B) s'executa en el processador

13. El (SO) rep una interrupció HW indicant final esdeveniment.

14. Canvia la modalitat del processador a

15. El (procés A) passa de l'estat

a l'estat

16. Canvia la modalitat del processador a

17. El (procés B) s'executa en el processador

18. El (procés B) finalitza

19. Canvia la modalitat del processador a

20. El (SO) planifica l'execució del (procés A)

21. Canvia la modalitat del processador a

22. El (procés A) s'executa en el processador

23. El (procés A) finalitza

Exercici 5. Qüestions de vertader o fals sobre gestió de processos i memòria

Indiqueu raonadament si cadascuna de les asseveracions següents és vertadera o falsa:

Vertader

Fals

Exercici 6. Estats de tres processos a partir d'un cronograma

Considereu el cronograma d'execució mostrat a continuació per a tres processos ($A$, $B$ i $C$). Tingueu en compte que el procés $A$ ingressa al sistema a $t = 0$, $B$ arriba a $t = 3$ i $C$ a $t = 8$, i que tots tres completen la seva tasca de manera satisfactòria.

Notació per als estats: Ll (Llest), Ex (Execució), Blq (Bloquejat), Fin (Finalitzat).

A partir del cronograma d'execució mostrat, determineu els estats pels quals travessa cadascun dels tres processos ( A, B i C) al llarg de l'eix temporal. Tingueu en compte que el procés A ingressa al sistema a $t = 0$, B arriba a $t = 3$ i C a $t = 8$, i que tots tres completen la seva tasca de manera satisfactòria.

Notació per als estats: Ll (Llest), Ex (Execució), Blq (Bloquejat), Fin (Finalitzat), o transicions com Ll–Ex, Ex–Blq, Blq–Llest, Ex–Fin, etc. Indiqueu «—» per als intervals en què el procés encara no ha arribat o ja ha finalitzat.

Procés · 0–1 · 1–2 · 2–3 · 3–4 · 4–5 · 5–6 · 6–7 · 7–8 · 8–9 · 9–10 · 10–11 · 11–12 · 12–13 · 13–14 · 14–15 · 15–16

Exercici 7. Evolució del nombre de Blocs de Control de Procés (BCP)

Considereu el cronograma d'execució mostrat a continuació per a tres processos ($A$, $B$ i $C$). Tingueu en compte que el procés $A$ ingressa al sistema a $t = 0$, $B$ arriba a $t = 3$ i $C$ a $t = 8$, i que tots tres completen la seva tasca de manera satisfactòria.

Notació per als estats: Ll (Llest), Ex (Execució), Blq (Bloquejat), Fin (Finalitzat).

Prenent com a referència l'escenari de l'exercici anterior (amb processos A, B i C):

a)

Quants BCP romanen actius a la memòria en l'instant de temps $t = 2$?

b)

I en l'instant de temps $t = 7$?

c)

I en l'instant de temps $t = 13$?

Exercici 8. Anàlisi de canvis de mode d'execució i estats del sistema

En un sistema multiprogramat s'executen tres processos ($A$, $B$ i $C$) segons l'evolució temporal de la figura. El procés $A$ arriba a $t = 0$ i finalitza a $t = 13$; el procés $B$ arriba a $t = 1$ i acaba a $t = 10$; i el procés $C$ arriba a $t = 2$ i acaba a $t = 14$.

a)

Indiqueu 2 instants de temps on es produeixi un canvi de modalitat del processador de mode usuari a mode supervisor (kernel), justificant cadascun.

b)

Indiqueu 2 instants de temps on es produeixi un canvi de modalitat de mode supervisor a mode usuari, justificant la resposta.

c)

Indiqueu l'estat de cadascun dels tres processos ($A$, $B$ i $C$) en els instants $t = 0$, $t = 3$, $t = 9$ i $t = 15$.

Instant ($t$)

Procés A

Procés B

Procés C

$t = 0$

$t = 3$

$t = 9$

$t = 15$

Exercici 9. Validesa de les transicions d'estat d'un procés

Indiqueu quina o quines de les transicions d'estat següents no són correctes i raoneu breument per què:

a.

Execució a Llest

b.

Bloquejat a Execució

c.

Llest a Execució

d.

Llest a Acabat (Finalitzat)

e.

Llest a Bloquejat

Exercici 10. Canvis de modalitat d'execució usuari i supervisor

Es considera un conjunt de tres processos, A, B i C, el diagrama d'execució dels quals és el següent:

Les característiques dels processos són:

Procés A: arriba a $t = 0$ amb un temps total de CPU de 6 unitats de temps.

Procés B: arriba a $t = 0$ amb un temps total de CPU de 4 unitats de temps.

Procés C: arriba a $t = 2$ amb un temps total de CPU de 5 unitats de temps.

Indiqueu dos instants temporals en què es produeixi una commutació de mode supervisor a mode usuari i dos instants en què es produeixi la commutació contrària ( d'usuari a supervisor), justificant breument cada cas.

1.

2.

Exercici 11. Planificació de CPU mitjançant FCFS i Round Robin (q=4)

Considereu un sistema multiprogramat amb els processos detallats a la taula:

Procés · Temps d'arribada · Temps de servei

A · 3 · 6

B · 1 · 10

C · 3 · 6

D · 0 · 10

Dibuixeu el diagrama de Gantt resultant d'aplicar les dues polítiques de planificació de CPU següents:

a.

FCFS (First-Come, First-Served)

b.

RR (Round Robin) amb un quàntum de temps $q = 4$

Exercici 12. Planificació mitjançant FCFS i Round Robin (q=2)

Donada la taula de processos següent:

Procés · Temps d'arribada · Temps de servei

A · 2 · 18

B · 6 · 12

C · 4 · 9

D · 0 · 9

Dibuixeu el diagrama de Gantt corresponent a les polítiques:

a.

FCFS

b.

Round Robin amb $q = 2$

Exercici 13. Mètriques de planificació amb FCFS i Round Robin (q=4)

Considerant els quatre processos següents:

Procés · Temps d'arribada ($T_a$) · Temps de servei ($T_s$)

A · 0 · 6

B · 1 · 4

C · 7 · 3

D · 4 · 5

a.

Genereu el diagrama de Gantt i calculeu el temps de retorn mitjà ($\bar{T}_q$) i d'espera mitjà ($\bar{T}_w$) per a FCFS.

b.

Genereu el diagrama de Gantt i calculeu les mateixes mètriques per a Round Robin ($q = 4$).

Exercici 14. Comparativa de Round Robin (q=3) i Shortest Process Next (SPN)

Siguin els quatre processos a planificar descrits a la taula:

Procés · Temps d'arribada · Temps de servei

A · 1 · 8

B · 2 · 5

C · 3 · 2

D · 4 · 7

a)

Dibuixeu el diagrama de Gantt corresponent a les polítiques Round Robin (q=3) i SPN (Shortest Process Next).

b)

Determineu quin dels dos algorismes obté un millor temps mitjà d'espera ($T_{w,\text{mitjà}}$).

Round Robin

SPN

Exercici 15. Temps de finalització i retorn mitjà per a FCFS i SPN

Es presenten tres processos per ser executats amb les següents propietats:

Procés · Temps d'arribada ($T_a$) · Temps de servei ($T_s$)

P1 · 0 · 9

P2 · 5 · 4

P3 · 6 · 2

Calculeu el temps de finalització ($T_f$), el temps de retorn individual ($T_q$) i el temps de retorn mitjà ($T_{q,\text{mitjà}}$) per a cadascuna de les polítiques de planificació següents:

a)

FCFS

Procés · $T_f$ · $T_q$

P1

P2

P3

b)

SPN (no apropiatiu)

Procés · $T_f$ · $T_q$

P1

P2

P3

Exercici 16. Impacte de l'ordre d'arribada a la cua sobre l'algorisme FCFS

Un sistema operatiu gestiona els processos següents, presents a la cua de llests en un instant determinat:

Procés · Temps de servei

P1 · 13

P2 · 10

P3 · 5

P4 · 3

Suposant que tots es consideren disponibles en l'instant d'arribada base $t = 0$, calculeu el temps d'espera i de retorn per a cadascun, així com el temps d'espera mitjà ($T_{w,\text{mitjà}}$) i de retorn mitjà ($T_{q,\text{mitjà}}$) sota l'algorisme FCFS en els dos supòsits següents:

a.

Els treballs arriben a la cua ordenats com: P1, P2, P3, P4.

Procés · $T_w$ · $T_q$

P1

P2

P3

P4

b.

Els treballs arriben a la cua ordenats en sentit invers: P4, P3, P2, P1.

Procés · $T_w$ · $T_q$

P4

P3

P2

P1

Exercici 17. Avaluació de Round Robin segons diferents valors de quàntum

Es disposa dels següents processos a planificar mitjançant l'algorisme Round Robin:

Procés · Temps d'arribada · Temps de servei

P1 · 0 · 6

P2 · 1 · 8

P3 · 2 · 5

P4 · 3 · 9

P5 · 4 · 10

Per a cadascun dels següents valors de quàntum de temps ($q = 2$, $q = 3$ i $q = 7$), calculeu el temps de retorn de cada procés, el temps de retorn mitjà ($T_{q,\text{mitjà}}$) i el nombre total de canvis de procés (canvis de context):

a)

Quàntum $q = 2$:

b)

Quàntum $q = 3$:

c)

Quàntum $q = 7$: