teoria 3 procesos so
DESCRIPTION
UABTRANSCRIPT
-
1SISTEMES OPERATIUS
Tema 3: Gesti de Processos
-
2ndex
Model de Procs Crides al sistema (creaci i
finalitzaci) Model de Thread Planificaci de CPU (curt termini) Concurrncia Deadlock
-
3De programa a procs
llenguatge dalt nivell -> llenguatge mquinaFase 1
editar
.asm
.c
fitxersfont
Compilaci:traducci de llenguatge dalt nivell a codi objecte
.o
.o
.a
Fitxers objectei llibreries
-
4De programa a procs
llenguatge dalt nivell -> llenguatge mquinaFase 1
editar
.asm
.c
.o
.o
.a
A.exem
o
n
t
a
r
Fictxersfont
fitxers objectei llibreries
Fitxersexecutables
Montatge: creaci dun fitxerexecutable a partir de diversos fitxers objete i llibreras
-
5Fase 1
editar
.asm
.c
.o
.o
.a
A.exem
o
n
t
a
r
Fitxersfont
Fitxers objectei llibreries
Fitxersexecutables
Programa:entitat esttica, codiemmagatzemat a disc
De programa a procs
llenguatge dalt nivell -> llenguatge mquinaFase 1
-
6De programa a procs
llenguatge dalt nivell -> llenguatge mquinaFase 1 Fase 2
execuci
editar
.asm
.c
.o
.o
.a
A.exem
o
n
t
a
r
carregar i executar
SOMemria CPU
CPA
A
carregar un fitxer executable a memria i donar control a la primera instrucci del
programa
-
7SOMemria CPU
CPA
A
Procs
Un procs s un programa en execuci
no existeix una relacin un-a-un entre programa i procs ats que es pot tenirdiversos processos dun mateix programa
main(){...foo(5);
...}
Programa
main(){...foo(5);
...}
Procs
pila
registresCPU
A
-
8 Estat del processador: contingut delsregistres del modelo de programaci.
Imatge de memria: contingut delssegments de memria en els que resideixel codi i les dades del procs
Informaci de control, identificaci
Informaci dun procs
-
9 Informaci didentificaci PID del procs, PID del pare ID dusuari real (uid real) ID de grup real (gid real) ID dusuari efectiu (uid efectiu) ID de grup efectiu (gid efectiu)
Estat del processador Informaci de control del procs
Informaci de planificaci i estat Descripci dels segments de memria del procs Recursos assignats (fitxers oberts, ...) Comunicaci entre processos. Apuntadors per estructurar els processos en llistes o cues.
Bloc de Control del Procs
-
10
Memria P.
Mapa de memriadel procs A
Taules SO
CP
SP
PSW
Registresespecials
Taules del sistema operatiuTaula de processos
- Taula de memria- Taula dE/S- Taula de Fitxers
BCP Procs BBCP Procs A BCP Procs C
Informaci dun procs
Mapa de memriadel procs B
Mapa de memriadel procs C
Registresgenerals Estat (regt.)
Identificaci Control
Estat (regt.) Identificaci Control
Estat (regt.) Identificaci Control
Quants processos pot controlar un SO?
-
11
Procs
Grau de multiprogramaci: nombre de processos actius
Sistema on tots els processos resideixentotalment a Memria Principal.
SOMemria P.
A
CB
Grau de multiprogramaci
U
t
i
l
i
t
z
a
c
i
d
e
l
p
r
o
c
e
s
s
a
d
o
r
100%
0%
-
12
Canvi de context
Procs A Procs BSO
interrupciE/S
interrupcirellotge
A : canvi de mode usuari a supervisor
B : canvi de mode supervisor a usuari
A
A
B
B
A
B
Temps
-
13
Estats dun procsC
B
A0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
llest execuci
bloquejat
planificat
expira temps
entra al sistema finalitzaci
-
14
Diagrama destats
finalnou
suspsllest
suspsbloquejat
llest execuci
bloquejat processos actiusa Memria Principal
processos inactiusa Memria Secundria
(disc)
swap outswap in
final q
planificat
entra al sistemafinalitzaci
swap in
-
15
ndex
Model de Procs crides al sistema (creaci i
finalitzaci) Model de Thread Planificaci de CPU (curt termini) Concurrncia Deadlock
-
16
Crides al sistema: gesti de processos
int fork()Retorna: -1 si error 0 al procs fill Valor ms gran que zero en el pare.Correspon a lidentificador del procs fill (PID).
crea un procs clon (fill) del procs que executa la crida (pare)
void exit(int status) finalitzaci de procs
int getpid()Retorna: -1 si error Valor ms gran que zero. Correspon a lidentificador de procs (PID).
Obtenir lidentificador de procs
-
17
Crides al sistema: gesti de processos
Qu fa el SO quan es sollicita la creaci dun procs?
Assigna una entrada a la taula de processos per al procs nou Assigna un ID nic de procs al procs nou Fa una cpia de la imatge del procs pare (excepte la mem.
comp.) Incrementa els comptadors dels fitxers que sn propietat del
pare Posa el procs fill a lestat Llest per a executar
-
18
Crides al sistema: gesti de processos
SO
main(){printf(Hola\n);fork();printf(Adeu\n);
}
Memria Principal
Hola
main(){printf(Hola\n);fork();printf(Adeu\n);
}
Quin procs escriu cada Adeu?
No es pot fer suposicions de velocitatsrelatives dexecuci dels processos cm discriminem un codi de laltre?
?AdeuAdeu
-
19
Crides al sistema: gesti de processos
SO
main(){int pid;printf(Hola\n);pid = fork();if (pid==0) /* fill */
printf(Adeu del fill\n);else /* pare */
printf(Adl padre\n);}
main(){int pid;printf(Hola\n);pid = fork();if (pid==0) /* fill */
printf(Adis del hijo\n);else /* pare */
printf(Adeu del pare\n);}
Ja sabem quin codi executa cada procs, per seguim sense poder saber lordre dexecucin.
HolaAdeu del pareAdeu del fill
o
HolaAdeu Adeu del filldel pare
........
o
o
Adeu del fillAdeu del pare
Hola
printf(Adeu del fill\n);
printf(Adeu del pare\n);
-
20
Crides al sistema: gesti de processos
int wait(int *status)Retorna: -1 si error Valor ms gran zero. Correspon a lidentificador de procs fill (PID).
Espera la finalitzaci dun procs fillqualsevol
pid_t waitpid(pid_t pid, int *stat_loc, int options)Retorna: -1 si error Valor ms gran que zero. Correspon a lidentificador del procs fill (PID). 0 lestat del procs fill a quisest fent referncia no estdisponible.
Espera la finalitzaci dunprocs fill en concret
-
21
Crides al sistema: gesti de processos
SOmain(){int pid,st;printf(Hola\n);pid = fork();if (pid==0) /* fill */{printf(Adeu del fill\n);}
else /* pare */{wait(&st);printf(Adeu del pare\n);}
}
main(){int pid,st;printf(Hola\n);pid = fork();if (pid==0) /* fill */
{printf(Adeu del fill\n);}else /* pare */
{wait(&st);printf(Adeu del pare\n);}
}
Ara ja sabem quin codi executa cada procs i lordre en qu sexecutaran.
HolaAdeu del fillAdeu del pare
-
22
Crides al sistema: gesti de processos
Cm aconseguir que un procs executi un altre programa diferent al que ja te carregat
cargado a memria?
-
23
Crides al sistema: gesti de processos
int execlp(char *file, char *arg0,...)Retorna: -1 si error si correcte mai torna.
Canviar la imatgeexecutable dun procs(codi, dades, pila)
int execl(char *path, char *file, char *arg0,...)int execle(char *path, char *file, char *arg0,..., char *envp[])int execv(char *path, char *argv[])int execvp(char *file, char *argv[])int execve(char *file, char *argv[], char *envp[])
-
24
Crides al sistema: gesti de processosSO
main(){int pid,st;printf(Hola\n);pid = fork();if (pid==0) /* fill */{printf(Adeu del fill\n);
execlp(ls,ls,-l,NULL);exit(1);}
else /* pare */{wait(&st);printf(Adeu del pare\n);}
}main(){int pid,st;printf(Hola\n);pid = fork();if (pid==0) /* fill */
{printf(Adeu del fill\n);execlp(ls,ls,-l,NULL);exit(1);}
else /* pare */{wait(&st);printf(Adeu del pare\n);}
}
/bin/ls
-
25
Crides al sistema: gesti de processosSO
main(){int pid,st;printf(Hola\n);pid = fork();if (pid==0) /* fill */{printf(Adeu del fill\n);
execlp(ls,ls,-l,NULL);exit(1);}
else /* pare */{wait(&st);printf(Adeu del pare\n);}
}main(){int pid,st;printf(Hola\n);pid = fork();if (pid==0) /* hijo */
{printf(Adis del hijo\n);execlp(ls,ls,-l,NULL);exit(1);}
else /* padre */{wait(&st);printf(Adis del padre\n);}
}
/bin/ls
Canviar el programa del procspel de ls -l,
codi del ls
-
26
fork()
exec() exit()
wait()pid P
padre
pid H
padre
pid P
padre
zombie
pid P
hijohijopid H
hijopid H
pid P pid P pid P pid Ppid Hpid H
texto
pila
datos
Ficheros, tuberas, ...
Crides al sistema: gesti de processos
-
27
ndex
Model de Procs Crides al sistema (creaci i finalitzaci) Model de Thread Planificaci de CPU (curt termini) Concurrncia Deadlock
-
28
Model de Procs
-
29
Procs versus fluxA cada part del programa (codi) que es pot executar de forma independent se li associa un flux (thread, fil, procslleuger).
main(){...foo(5);
...}
Procs
pila
registresCPU
un procs (o procs pesat) s lamo dels recursos
main(){...foo(5);
...}
Flux
pila
registresCPU
pila
registresCPU
poden existir mltiples fluxos dexecuci en un mateix procs
-
30
Informaci prpia/privada dun flux: Comptador de Programa (CP) Pila Registres Estat del flux (ejecuci, llest o
bloquejat)
Tots els fluxos dun mateix procscomparteixen:
Espai de memria Variables globals Arxius aberts Temporitzadors Senyals i semforos
Flux (thread)
Flux 1Registres
Pila
Proceso
Flux nRegistres
Pila
....
Codi
Dades
Recursos (fitxers, ...)
Entorn del procs
-
31
Creaci Threads vs. Procs
Nota: Els temps reflecteixen la creaci de 50.000 processos/thread, mesurat amb la utilitat time, les unitats sn en segons.
-
32
Exemple utilitzaci de Threads
-
33
Serveis POSIX per a la gesti de processos lleugers
int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*func)(void *), void *arg)
Crea un procs lleuger que executa "func" amb argument "arg" i atributs "attr".
Els atributs permeten especificar: Mida de la pila, prioritat, poltica de planificaci, etc.
Existeixen diverses crides per modificar els atributs. int pthread_join(pthread_t thid, void **value)
Suspn lexecuci dun procs lleuger fins que acabi el procslleuger amb lidentificador "thid".
Retorna lestat de finalitzaci del procs lleuger. int pthread_exit(void *value)
Permet a un Thread finalitzar la seva execuci, indicant lestat de la seva finalitzaci.
pthread_t pthread_self(void) Retorna lidentificador del thread que executa la crida.
-
34
34
Futur previst en 5 anys
128 cores per socket
32 sockets per node
128 nodes per sistema
Sistema = 128*32*128= 524,288 Cores!
4 threads per core 2M threads a gestionar
-
35
ndex
Model de Procs Crides al sistema (creaci i finalitzaci) Model de Thread Planificaci de CPU (curt termini) Concurrncia Deadlock
-
36
Comportament dels Processos
E/SCPU CPUCPUE/S
Processos amb Ms Crrega de CPU
CPU CPUCPU
Processos amb Ms Crrega dE/S
E/S E/S
-
37
finalnou
suspsllest
suspsbloquejat
llest execuci
bloquejat
swap out
swap in
final q
planificat
entra al sistemafinalitzaci
swap in
Pl. mitj termini: Decisi dafegir processos al conjunt de processos que hi ha a memria
Pl. Curt termini: Decisi sobrequin procs ser executat en el processador
Pl. Llarg termini: Decisi dafegri processos a la reserva de processos a executar. Grau de Multiprogramaci.
-
38
Proyecto Docente
Tipus de Planificador
FinalitzaciProcessosCPU
Planificador a llarg termini Planificador a
curt termini
Bloquejats
Llestos suspesos
Listos
Time-out
Bloquejats suspesos
Planificador a mitj termini
Planificador a mitj termini
Planificaci: Gesti de les cues que minimitzilespera i optimitzi el rendiment del sistema.
-
39
Planificador a Curt TerminiConsisteix en assignar processador alsprocessos llestos per ser executats, de manera que es complixin els objetivos:
Baix temps de resposta Baix temps despera Alt throughput (nombre de processos
acabats per unitat de temps) Baix tempsde retorn
-
40
Definici de les Poltiquesde Planificaci
Funci de Selecci: Quin procs sexecutar? Prioritats Necesitats de recursos Caracterstiques dels processosMode de selecci: Quan? No apropiatiu Apropiatiu
-
41
Exemple Poltiques de Planificaci a Curt Termini
Proceso Llegada Ts
P1 0 3
P2 2 6P3 4 4P4 6 5P5 8 2
Temps dEspera (Tw)
Temps de Retorn. (Tq)
Temps de Retorn Normalitzat (Tqn) Tqn = Tq/Ts
Temps de Resposta (Tr)
-
42
First Come First Served (FCFS)
Funci de selecci: max [Tespera], elsprocessos satenen per ordre darribada.
Mode de decisi: No apropiatiu
-
43
First Come First ServedProceso Llegada Ts
P1 0 3
P2 2 6P3 4 4P4 6 5P5 8 2
P5P4P3P2P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Tw(P1) = 0
Tw(P2) = 3-2 = 1
Tw(P3) = 9-4 = 5
Tw(P4) = 13-6 = 7
Tw(P5) = 18-8 = 10
Tw = 23/5 = 4,6
P1 P2 P5P3 P4
-
44
First Come First ServedProceso Llegada Ts
P1 0 3
P2 2 6P3 4 4P4 6 5P5 8 2
P5P4P3P2P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Tq(P1) = 3
Tq(P2) = 9-2 = 7
Tq(P3) = 13-4 = 9
Tq(P4) = 18-6 = 12
Tq(P5) = 20-8 = 12
Tq = 43/5 = 8,6
-
45
First Come First Served (FCFS)
Caracterstiques: Senzill Temps despera de mitjana elevat Penalitza als processos curts i als que tenen
molta E/S Inanici: no
-
46
Shortest Process Next(SPN)
Funci de selecci: min [Tservei], sasigna primer el procs amb menor temps dexecuci.
Mode de decisi: No apropiatiu Problema:
Problema: conixer Ts abans de lexecuci
-
47
Shortest Process Next (SPN) Predicci del Temps de Servei:
Mitjana exponencial dels temps dexecuci / rfegues de CPU anteriors.tn = durada del n-ssim temps dexecuci / rfega de CPUTn+1 = Predicci per a la prxima
execuci / rfega de CPU0 1
Tn+1 = .tn + (1-).Tn Problema: Estimar T0
Informaci msrecent Histria
-
48
Shortest Process Next (SPN) Predicci del Temps de Servei:
Tn+1 = .tn + (1-).Tn
Tn+1 = .tn + (1-)..tn-1 + ... + (1-)j .tn-j+...+ (1-)n+1.T0
Cada terme successiute menys pes que el predecessor
T4 = .t3 + (1-)..t2 + (1-)2 .t1+(1-)3 .t0 + (1-)4.T0
-
49
Shortest Process NextProceso Llegada Ts
P1 0 3
P2 2 6P3 4 4P4 6 5P5 8 2
P5P4P3P2P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Tw(P1) = 0Tw(P2) = 3-2 = 1Tw(P3) = 11-4 = 7Tw(P4) = 15-6 = 9Tw(P5) = 9-8 = 1Tw = 18/5 = 3,6
FCFS: Tw = 4,6
P1 P2 P3 P4 P5
-
50
Shortest Process NextProceso Llegada Ts
P1 0 3
P2 2 6P3 4 4P4 6 5P5 8 2
Tq(P1) = 3Tq(P2) = 9-2 = 7Tq(P3) = 15-4 = 11Tq(P4) = 20-6 = 14Tq(P5) = 11-8 = 3Tq = 38/5 = 7,6
P5P4P3P2P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
FCFS: Tqn = 2,56
-
51
Shortest Process Next(SPN)
Caracterstiques: Minimitza el temps despera (Tw) Bon temps de resposta Inanici: possible Penalitza als processos llargs Productivitat: alta
-
52
Round Robin Cada procs sexecuta durant una
fracci de temps abans de ser expulsat(Quantum)
Mod de decisi: Apropiatiu (basat en el quantum)
-
53
P5P4P3P2P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Round RobinProceso L legada Ts
P 1 0 3
P 2 2 6P 3 4 4P 4 6 5P 5 8 2
P2 P3 P4 P5P1
Quantum = 4
P1 P2 P3 P4 P5P2 P4
Sobrecarga
-
54
Round Robin
Caracterstiques: Rendiment en funci del quantum
q petit => nombre alt de canvis de context q petit => temps de retorn alt q gran => utilitzaci alta de la CPU, per tamb temps
de resposta alt q petit => productivitat baixa q ideal => el 80% de les rfegues de CPU han de ser
ms petites que el quantum q molt ms gran que el canvi de context
Quantum: entre 100 i 200 milisegons. El quantum s sintonitzable!.
-
55
Round Robin Caracterstiques:
Redueix la penalitzaci que pateixen els treballscurts amb FCFS
Inanici: No, per temps despera alt Bon temps de resposta Penalitza als processos amb E/S.
-
56
Prioritats
Caracterstiques: Inanici: Possible Penalitza als processos de baixa prioritat Soluci: Envelliment
-
57
Cues Multinivell
Alta Prioritat Processos del Sistema
Baixa Prioritat
Processos Interactius
Processos Batch
-
58
Cues amb Retroalimentaci
Preferncia als treballs ms curts. Es penalitza als treballs que han estat executan-
se durant ms temps. Es fa una planificaci apropiativa i es fa servir
un mecanisme dinmic de prioritats.
-
59
Cues amb Retroalimentaci
EntradaCPU
alliberarCua 0
CPUalliberarCua 1
CPUalliberarCua N
-
60
Cues amb Retroalimentaci. Parmetres
Nombre de cues. Algoritme de planificacions per a cada cua. Mtode utilitzat per determinar quan promocionar
un procs a una cua de major prioritat. Mtode utilitzat per a determinar quan moure un
procs a una cua de menor prioritat. Mtode utilitzat per a determinar a quina cua ser
assignat inicialmente un procs.
-
61
Exemple: Planificaci en UNIX
Beneficia als processos interactius. Retroalimentaci multinivell amb un Round
Robin a cada una de les cues de prioritat. Prioritat calculada cada segon en funci de la
classe de procs i el seu historial dexecuci. En usar ms CPU disminueix la prioritat. Envelliment per evitar inanici.
-
62
Ejemple: Planificaci en Win NT Planificaci cclica amb prioritats i expulsi. 32 nivells de prioritat:
16 nivells amb prioritats de temps real (16-31) 16 nivells amb prioritats variables (0-15)
Tots els processos en el mateix nivell: Round Robin(quantum per procs).
Prioritat Variable: Decrementa la prioritat si acaba el seu quantum. Incrementa la prioridad si es bloqueja (E/S).
Bon temps de resposta dels threads interactius.
-
63
ndex
Model de Procs Crides al sistema (creaci i finalitzaci) Model de Thread Planificaci de CPU (curt termini) Concurrncia Deadlock
-
64
Model de Procs
-
65
Procs versus fluxA cada part del programa (codi) que es pot executar de forma independent se li associa un flux (thread, fil, procslleuger).
main(){...foo(5);
...}
Procs
pila
registresCPU
un procs (o procs pesat) s lamo dels recursos
main(){...foo(5);
...}
Flux
pila
registresCPU
pila
registresCPU
poden existir mltiples fluxos dexecuci en un mateix procs
-
66
Informaci prpia/privada dun flux: Comptador de Programa (CP) Pila Registres Estat del flux (ejecuci, llest o
bloquejat)
Tots els fluxos dun mateix procscomparteixen:
Espai de memria Variables globals Arxius aberts Temporitzadors Senyals i semforos
Flux (thread)
Flux 1Registres
Pila
Procs
Flux nRegistres
Pila
....
Codi
Dades
Recursos (fitxers, ...)
Entorn del procs
-
67
Exemple utilitzaci de Threads
-
68
Qu es la concurrncia? Parallelisme: existeix simultaneitat en lexecuci
ats que disposem de ms dun processador.
C
B
A0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Processador 2
Processador 1
Lexecuci de processos / fluxos en processadors / cores diferentesSI es solapa en el temps.
-
69
Qu s la concurrncia?
IMPORTANT:
Recordeu que NO existeix cap garantia en lordredexecuci dels processos / fluxos.
Per aconseguir un ordre explcit shaur dinclourealgun mtode de sincronitzaci que ens ho asseguri.
-
70
Qu s la concurrencia? Instruccions senzilles de llenguatges dalt nivell (C,
Java, etc...) normalment es tradueixen en ms duna instrucci de llenguatge mquina.
Exemple:.....comp++;.....
mov al,compadd al, 1mov comp, al
En acabar qualsevol de las tres instruccions anteriors es pot atendre una interrupci o produir-se un canvi de context.
La majoria de les instruccions dalt nivell NO sn atmiques.
-
71
Operaci AtmicaUna operaci atmica s aquella que no pot interrumpir-
se durant la seva execuci.
Les instruccions mquina sn atmiques.mov al, comp
Aquesta instrucci no pot trencar-se en donar-se alguna interrupci.
Les instruccions dalt nivell NO sn atmiquescomp++;
Aquesta instrucci s realment 3instruccions mquina.Es pot produir una interrupci durantlexecuci de la instrucci.
-
72
Problema ! Suposem 2 fluxos (processos) accedint a una variable compartida.
int comp=2;main(){
crear_flux (flux0);crear_flux (flux1);esperaFinalFluxos();
}
void flux0(){
...comp++;...
}
void flux1(){
...comp--;...
}
Recordeu que comp++ i comp- sn en realitat 3 instruccions mquina. Un possible interleaving dels fluxos flux0 i flux1 s:
flux0 mov al,compflux1 mov al,compflux0 add al,1flux1 sub al,1flux0 mov comp, alflux1 mov comp, al
El resultat s que comp val 1
Depenent de l interleaving comppodra valer 1, 2 o 3
-
73
Condici de carrera(race condition)
Lexemple anterior s un cas on es produeix la condici de carrera:
dos fluxos competeixen (carrera) per posar un valor en una posici de la memria
no existeix cap manera de saber qui guanyar
Bug molt problemtic.s complicat de reproduir (execuci no deterministica)
ats que lordre de les instruccions pot variar dunaexecuci a una altra.
Sense una sortida consistent, s molt complex determinar els errors.
-
74
Secci Crtica Si existeixen diversos fluxos / processos que accedeixen a dades
compartides les quals sn modificables, aleshores laccs a aquestes dades per cada flux / procs ha de ser controlat.
La part de codi que ha de ser controlada en cada flux / procs sel que es coneix com a SECCI CRTICA.
int comp=2;main(){
crear_flux (flux0);crear_flux (flux1);esperaFinalFluxos();
}
void flux0(){
...comp++;...
}
void flux1(){
...comp--;...
}
SECCI CRITICA
-
75
Secci Crticavoid flux0(){
...entrarSeccioCritica();comp++;sortirSeccioCritica();...
}
void flux1(){
...entrarSeccioCritica();comp--;sortirSeccioCritica();...
}
entrarSeccioCritica() i sortirSeccioCritica() sn dos requeriments per protegir de forma correcta la SC. Es pot veure com un protocol daccs i sortida de la SC.
Aquesta parella de funcions han de complir: Exclusi mtua Progrs Espera limitada No es pot fer cap hiptesi ni suposici sobre el nombre de
processadors, ni la velocitat relativa dexecuci.
-
76
Secci CrticaentrarSeccionCritica();SeccionCritica();sortirSeccionCritica();
Mtodes/protocols de protecci de la SC
Software: implementaci de algoritmes en llenguatge dalt nivell (Peterson, Dekker, Lamport....).
Hardware: utilitzant instruccions de baix nivell (habilitar/deshabilitar int., test&set, swap).
SOware: utilitzant eines suportades i gestionades pel SO (semfors).
-
77
Secci CrticaProtecci hardware
Habilitar/deshabilitar interrupcions. Test&set Swap
Aquest mtode de protecci utilitza instruccions mquina, s per aix que se sanomenen mtodes hardware.
Nota: recordar que les instruccions mquina sn atmiques
-
78
Secci CrticaProtecci hardware: test&set
Testeja i modifica una posici de memria: Inicialitzar un registre al valor actual de la posici de memria Desprs inicialitzar la posici de memria a un valor
predeterminat.
Tot aix es fa en un sol cicle dinstrucci: test&set i
Lequivalent en llenguatge dalt nivell seria:
int test&set(int *i){int a = *i;*i = 1;return(a);
}
-
79
Secci CrticaProteccin hardware: test&set
int lock = 0 // variable compartida inicialitzada en el main()
entrarSeccionCritica();SeccionCritica();sortirSeccionCritica();
void fluxei(){
while(test&set(&lock));SeccionCritica();lock = 0;
}
Un exemple: M68000 TAS operando1
0xxxxxxx1xxxxxxx
llegir modificar escriure
xxx
N Z001
010
100000001xxxxxxx
1xxxxxxx
-
80
Secci CrticaProtecci hardware: test&set
void fluxei(){
while(test&set(&lock));SeccionCritica();lock = 0;
}
TAS lock.......MOVE 0,lock
Un exemple: M68000 TAS operando1
-
81
Secci CrticaProtecci SOware
El SO ens proporciona les eines per s el programador qui les ha de fer servir adequadament.
Semfor: s una estructura de dades del SO que t associada un comptador i una cua de processosbloquejats.
Serveix per protegir laccs a recursos. El comptador indica la quantitat daccessos simultanis que
permetem al recurs protegit pel semforo. Noms s accessible mitjanant dues primitives: wait() i
signal().
-
82
Secci CrticaProtecci SOware: semfors
void wait(semafor s){while(s
-
83
Secci CrticaProtecci SOware: semfors
Veiem com solucionem el problema de laccs a la SC utilitzant semfors.
entrarSeccioCritica();SeccioCritica();sortirSeccioCritica();
void flux0(){
???comp++;???
}
void flux1(){
???comp--;???
}
int comp=2;semafor s;main(){
sem_init(s,?? );crear_flux (flux0);crear_flux (flux1);esperaFinalFluxos();
}
compartit
Quants accessossimultanis volempermetre sobre comp?
Volem assegurarExMut, Aleshoresnoms 1 accssimultani.
1
-
84
Secci CrticaProtecci SOware: semfors
Veiem com solucionem el problema de laccs a la SC utilitzant semfors..
Com assegurar que flux0 entra a la seva SC impedint que flux1 pugui, a partir de llavors, entrar a la seva SC?
int comp=2;semafor s;main(){
sem_init(s,1);crear_flux (flux0);crear_flux (flux1);esperaFinalFluxos();
}
entrarSeccioCritica();SeccioCritica();sortirSeccioCritica();
void flux0(){
???comp++;???
}
void flux1(){
???comp--;???
}
Com assegurar que lexecuci del flux1 s atura si el flux0 sestexecutant a la seva SC?
-
85
Secci CrticaProtecci SOware: semfors
Veiem com solucionem el problema de laccs a la SC utilitzant semfors.
int comp=2;semafor s;main(){
sem_init(s,1);crear_flux (flux0);crear_flux (flux1);esperaFinalFluxos();
}
entrarSeccioCritica();SeccioCritica();sortirSeccioCritica();
void flux0(){
wait(s);comp++;???
}
void flux1(){wait(s);comp--;???
}
Com assegurar que lexecuci del flux1 s atura si el flux0 sestexecutant a la seva SC?
Com assegurar que flux0 entra a la seva SC impedint que flux1 pugui, a partir de llavors, entrar a la seva SC?
-
86
Secci CrticaProtecci SOware: semfors
Veiem com solucionem el problema de laccs a la SC utilitzant semfors.
int comp=2;semafor s;main(){
sem_init(s,1);crear_flux (flux0);crear_flux (flux1);esperaFinalFluxos();
}
entrarSeccioCritica();SeccioCritica();sortirSeccioCritica();
void flux0(){
wait(s);comp++;???
}
void flux1(){wait(s);comp--;???
}
Com assegurar que el flux0 en sortir de la seva SC allibera laccsal recurso comp ?
-
87
Secci CrticaProtecci SOware: semfors
Veiem com solucionem el problema de laccs a la SC utilitzant semfors.
int comp=2;semafor s;main(){
sem_init(s,1);crear_flux (flux0);crear_flux (flux1);esperaFinalFluxos();
}
entrarSeccioCritica();SeccioCritica();sortirSeccioCritica();
void flux0(){
wait(s);comp++;signal(s);
}
void flux1(){wait(s);comp--;
signal(s);}
Com assegurar que el flux0 en sortir de la seva SC allibera laccsal recurso comp ?
-
88
Secci CrticaProtecci SOware: semfors
Amb un semfor inicialitzat a 1 podem controlar laccs a la SC de N fluxes assegurant lExclusi Mtua.
void flux0(){
wait(s);SeccioCritica();signal(s);
}
void fluxN(){wait(s);SeccioCritica();signal(s);
}
int comp=2;semafor s;main(){
int i;sem_init(s,1);for (i=0;i
-
89
Secci CrticaProtecci SOware: semfors
Problema dels semfors
void wait(semafor s){
while(s
-
90
Secci CrticaProtecci SOware: semfors
void wait(semafor s){
s--;if (s < 0) bloquejar-me();
}
void signal(semafor s){
s++; if (s
-
91
Secci Crticawait() i signal() com seccions crtiques
void flujoi(){
wait(s);SeccionCritica();signal(s);
}
lock = 0;int i, cont=2;semaforo s;main(){
sem_init(s,1);for (i=0;i
-
92
Secci Crticawait() i signal() com seccions crtiques
void flujoi(){
wait(s);SeccionCritica();signal(s);
}
lock = 0;int i, cont=2;semaforo s;main(){
sem_init(s,1);for (i=0;i
-
93
Semfors ++ En funci del valor inicial del comptador associat al semfor,
lutilitzarem per a diferents funcions: sem_init (s, 1): ja hem vist la seva utilitat per aconseguir
que N processos accedeixin en Exclusi Mtua a les seves respectives SC.
sem_init (s, 0): sincronitzaci; marcar lordre de precedncia
sem_init (s, N): sincronitzaci; restricci de recursos (semfor comptador, genric)
Exemples de sincronitzaci: Productor / consumidor Sopar dels filsofs Lectors / escriptors
-
94
Marcar lordre de precednciamain(){crear_flux (flux0);crear_flux (flux1);esperaFinalfluxos();
}
void flux0(){acci 01;....acci 02;
}
void flux1(){acci 11;....acci 12;
}
Suposem que sha de complir el segent ordre en lexecuci de les diferentsaccions (ordre de precedncia):
- acci 01 i acci 11 poden fer-se concurrentement,- acci 02 sempre desprs de haver-se fet lacci 11 (i
evidentement desprs de lacci 01).
Com aconseguir-ho?
-
95
Marcar lordre de precedenciamain(){
Sem_init (s,..);crear_flux (flux0);crear_flux (flux1);esperaFinalfluxos();
}
void flux0(){
acci 01;......acci 02;
}
void flux 1(){
acci 11;......acci 12;
}
accio01
accio02
accio11
accio12
fluxprincipal
Graf de precedncies
signal(s);wait(s);
Sem_init (s, 0);
fluxprincipal
-
96
Productor/ConsumidorBuffer circular de mida limitada (N posicions)
inoutint buffer[N],in,out;main(){
crearflux(consumidor);crearflux(productor);esperarFinalfluxos();
}int buffer[N],
void consumidor(){
accedir_buffer_treure(ele); consumir_element();
}
Ha dexistir com a mnim 1 element en el buffer, si no, esperar.
void productor(){
ele = produir_element();accedir_buffer_introduir(ele);
}
Ha dexistir com a mnim 1 espai buit en el buffer, si no, esperar.
-
97
Productor/Consumidor
void consumidor(){
wait(hi_ha_ele);wait(mutex);accedir_buffer_treure(ele); signal(mutex);signal(hi_ha_esp);consumir_element();
}
void productor(){
ele = produir_element();wait(hi_ha_esp);wait(mutex);accedir_buffer_introduir(ele);signal(mutex);signal(hi_ha_ele);
}
int buffer[N],in,out;semafors hi_ha_ele, hi_ha_esp, mutex;main(){ sem_init(hi_ha_ele,0);
sem_init(hi_ha_esp,N);sem_init(mutex,1);.....
}
-
98
Productor/Consumidor
void consumidor(){
wait(hi_ha_ele);wait(mutex);accedir_buffer_treure(ele); signal(mutex);signal(hi_ha_esp);consumir_element();
}
void productor(){
ele = produir_element();wait(hi_ha_esp);wait(mutex);accedir_buffer_introduir(ele);signal(mutex);signal(hi_ha_ele);
}
int buffer[N],in,out;semafors hi_ha_ele, hi_ha_esp, mutex;main(){ sem_init(hi_ha_ele,0);
sem_init(hi_ha_esp,N);sem_init(mutex,1);.....
}
-
99
Sopar dels Filsofsmain(){
for (i=0;i
-
100
Sopar dels Filsofs
semaforo forquilla[5]; main(){
for (i=0;i
-
101
Sopar dels Filsofs
semaforo forquilla[5]; main(){
for (i=0;i
-
102
Sopar dels Filsofsvoid filosofo(i){
while(true) {PENSAR();agafar_forquilla(i);MENJAR ();deixar_forquilla(i);}
}
agafar_forquilla(i){wait(mutex);state(i):= hungry;test (i);signal(mutex);wait(s(i));
}
deixar_forquilla(i){wait(mutex);state(i):= thinking;test (left);test (right);signal(mutex);
}
test (i){if (state(i) == hungry && state(left) != eating && state(right) != eating
signal(s(i));}
-
103
Lectors/Escriptorslector 1
lector 2lector n
escritor 1escriptor iescriptor i
lector i
Escriptor accedeix a dades: Noms un escriptor
simultaniament Altres escriptors sesperen lectors sesperen
Lector accedeix a dades: poden accedir simultaniament n
lectors Els escriptores sesperen
-
104
Lectors/Escriptors(prioritat lectors)
Mentre existeixin lectors que vulguin accedir, els escriptors sesperaran, independentement de lordre en que es solliciti laccs
int comp_lect;semafors esc, mutex;main(){ sem_init(esc,1);
sem_init(mutex,1);cont_lect = 0;.....
}
void escriptor(){
wait(esc);escriure();signal(esc);
}
void lector(){
wait(mutex);comp_lect = comp_lect + 1;if (comp_lect == 1 ) wait(esc);signal(mutex);llegir();wait(mutex);comp_lect = comp_lect 1;if (comp_lect == 0) signal(esc);signal(mutex);
}
-
105
Lectors/Escriptors(prioritat lectors)
Mentre existeixin lectors que vulguin accedir, els escriptors sesperaran, independentement de lordre en que es solliciti laccs
int comp_lect;semafors esc, mutex;main(){ sem_init(esc,1);
sem_init(mutex,1);cont_lect = 0;.....
}
void escriptor(){
wait(esc);escriure();signal(esc);
}
void lector(){
wait(mutex);comp_lect = comp_lect + 1;if (comp_lect == 1 ) wait(esc);signal(mutex);llegir();wait(mutex);comp_lect = comp_lect 1;if (comp_lect == 0) signal(esc);signal(mutex);
}
-
106
Pedro, Pablo y el cartero Pedro y Pablo son dos amigos que comparten un buzn para las cartas que
reciben. Adems, tienen la suerte de conocer al cartero, por lo que l mismo les avisa cuando reciben una carta (cada vez que deja una carta en el buzn avisa al destinatario: Pedro o Pablo). La capacidad del buzn es de una nica carta. Entonces, si el buzn est vaco el cartero deposita la carta y avisa al destinatario (Pedro o Pablo) que tiene una carta. ste, retira la carta del buzn y de esta forma, el buzn queda vaco y listo para que el cartero pueda depositar otra carta. Si el cartero se encuentra con el buzn ocupado, debe esperar a que se retire la carta anterior.
Los tres procesos se repiten infinitamente. Se puede suponer que slo existen cartas para Pedro o Pablo. Suponed las funcionesobtener_nombre(); utilizada por el cartero para determinar el destinatario y la funcin recoger_carta(); utilizada por Pedro y Pablo para sacar la carta del buzn.
Implementad dicho proceso de recepcin de cartas utilizando semforos. Definid los semforos que se necesitan con su respectiva inicializacin y la implementacin de dicho proceso de recepcin.
-
107
Pedro, Pablo y el carterosemaforo pedro; semaforo pablo; semaforo buzonVacio;main() {
sem_init(pedro,0);sem_init(pablo,0);sem_init(buzonVacio,1);
create_thread(pedro());create_thread(pablo());create_thread(cartero());
}
Semaforo para avisarPedro-Pablo
Semforo acceso recurso crtico buzon
Inicialmente a 0 porque no hay ninguna carta en el buzn
Inicialmente a 1 porque el buzon est vaci
-
108
proceso cartero() {while true {
wait(buzonVacio);persona = obtener_nombre();if (persona == pedro)
signal(pedro);else
signal(pablo);}
}
proceso pedro() {
while true {
wait(pedro);
recoge_carta();
signal(buzonVacio);
}
}
proceso pablo() {
while true {
wait(pablo);
recoge_carta();
signal(buzonVacio);
}
}
-
109
4) Problema barbera Dispone de 3 asientos de
espera. Dispone de 2 asientos de
corte de pelo. Si todos los asientos estn
llenos, los clientes esperan afuera.
Un cliente primero se sienta en los asientos de espera y despus pasa a uno de los asientos de corte de pelo.
-
110
Problema barbera
Clientes
Problema parecido al problema del productor/consumidor con distintas colas
BarberoRecursos crticos(colas de espera)
-
111
Problema barbera
Cliente
main(){semaforo silla_af;semaforo silla_esp;semaforo hay_clientes;
sem_init(hay_clientes, 0),sem_init(silla_af,2); sem_init(silla_esp,3);
barbero();for (x=0;x
-
112
Problema del barber dormilega Problema: 1 barber i N cadires despera Si un client entra i no hi ha cadires, sen va Semfors:
clients: nombre de clients en espera sense comptar el que est a la cadira del barber.
barbers: nombre de barbers inactius exmut: exclusi mtua
Variable compartida: Cadires_lliures: nombre de cadires despera
disponibles
Inicialment:clients=0 barbers=0 exmut=1 esperant=0
-
113
Barber Client
wait(mutex);if (Cadires_lliures > 0){
Cadires_lliures --;signal(client);signal(mutex);wait(barber);/* Tallar cabells */}else{signal(mutex); MARXAR
wait(client);wait(mutex);Cadires_lliures ++;signal(barber);signal(mutex);
/* Tallar cabells */
-
114
ndex
Model de Procs Crides al sistema (creaci i finalitzaci) Model de Thread Planificaci de CPU (curt termini) Concurrncia Deadlock
-
115
Interbloquejos Bloqueig permanent dun conjunt de processos
que competeixen pels recursos del sistema o es comuniquen entre s.
Exemple: Si P i Q amb semfors amb valor inicial 1
P1 P2wait(P) wait(Q)wait(Q) wait(P)... ...
signal(P) signal(Q)signal(Q) signal(P)
-
116
Exemple dinterbloqueig
Q
P
BA