Copia della pagina https://etherpad.wikimedia.org/p/so.cs.unibo.it (20190604)
Jump to navigation
Jump to search
Renzo Operating Systems 2018-19 The Semester
Esercizio 2: siano dati tre processi "stampa" come segue: stampa(x):(x=A,T,R) process while (true) { synchro(x); print(x); } scrivere la fuzione synchro() facendo uso di semafori che consenta di avere in output una sequenza infinita di TARATATA (i.e. TARATATATARATATATARATATATARATATATARATATA......)
sempplificazione 1:
stampa TARTARTARTAR
while(1) {
pre(x)
stampa(x)
post(x)
semaphore st(1), sa(0), sr(0)
case t: st.P(); break
case a: sa.P(); break
case r: sr.P(); break
post(x): switch(x)
case t: sa.V(); break
case r: sa.V(); break
case a: if (count % 4) st.V() else sr.V(); count ++; break
x].P()x].P()
#define T=0, A=1, R=2
semaphore S[3] = (1,0,0)
bool first[3] = (true, true, true)
int count = 0
synchro(x):
if (not first[x]):
if (x==A)
if (count % 4)
s[T].V()
else s[R].V();
count ++;
else s[A].V()
first([x]) = false
s[x].P()
-----------------------------------
Lezione di Mercoledi 15 Maggio 2019
-----------------------------------
esercizio 2018.05.28
proc[x]: x='b',...,'z'
while True:
(c, string) = arecv(*)
if c == None:
asend(proc['a'], (None, string))
else:
print(x)
if (len(string) > 1)
asend(proc[string[0]], (x, string[1:]))
else
asend(proc['a'], (x, None)
proc['a']:
busy = false
q = []
While True:
(c, string) = arecv(*)
if c == None:
if Busy:
q.add(string)
else:
busy = True
asend(proc[string[0]], ('a', string)
else if (string == None)
if len(q) > 0:
string = q.dequeue()
asend(proc[string[0]], ('a', string)
else
busy = False
else:
print(x)
if (len(string) > 1)
asend(proc[string[0]], (x, string[1:]))
else
asend(proc['a'], (x, None)
e i clienti che vogliono stampare una stringa (non vuota) usano la funzione:
def procstampa(s): asend(proc[s[0]], (None, s))
C1 - 12 Gennaio 2012
CONDITION: Stack<int, OK2EXIT> currentProcesses; // Quando un processo può uscire
PROCEDURE-ENTRY: void Enter(){
currentProcesses.Push(new struct (GetPID(), new OK2EXIT());
}
PROCEDURE-ENTRY: void Exit(){
int callerPID = GetPID();
// Il processo si blocca
if (callerPID != currentProcesses.Top().PID)
currentProcesses.FindByPID(callerPID).OK2EXIT.Wait();
currentProcesses.Pop();
// Il processo avverte il suo seguente di liberarsi
if (currentProcesses.Count() > 0)
currentProcesses.FindByPID(currentProcesses.Top().PID).OK2EXIT.Signal();
}
-----------
struct elem {pid_t pid, condition c}
S stack of struct elem
PROCEDURE-ENTRY: void Enter(){
S.push({getpid(), c})
}
//esce solo l'"ultimo" entrato
PROCEDURE-ENTRY: void Exit(){
mypid = getpid()
{pid, c} = S.top() //guarda chi è in cima allo stack (senza toglierlo)
if (pid != getpid()) {
myc = S.searchpid(mypid)
myc.wait();
}
S.pop()
if (! S.empty()) {
{pid, c} = S.top()
c.signal()
}
}
----------//altro modo
//con i vettori invece dello stack
current = 0
pid_t pid[]
condition c[]
PROCEDURE-ENTRY: void Enter(){
pid[current++]=getpid()
}
PROCEDURE-ENTRY: void Exit(){
int i;
mypid = getpid()
for (i = 0; i < current; i++)
if (pid[i] == mypid) break;
if (i != current-1)
c[i].wait()
current--;
if (current > 0)
c[current-1].signal()
}
Esercizio g1 9 feb 2017
Una partizione contiene un file systems ext2. Nella directory radice all’interno della partizione ci sono tre directory: una chiamata “lost+found” (quella standard per il controllo di coerenza), una seconda chiamata “dev” ed una terza “dir”. La directory “dev” contiene un file speciale a caratteri denominato “null” che ha major number 1 e minor number 3. La directory “dir” contiene: * “null.phy” che è un link fisico al file “null” della directory “dev”. * “null.sym” è un link simbolico che punta a “../dev/null”. La directory “lost+found” è vuota. Spiegare come funziona il file system di tipo ext2 e mostrare il contenuto di tutte le strutture dati relative al caso qui illustrato
Superblocco radice=inode 1, size... last mount... //informazioni di controllo
bitmap dei blocchi (block 0 is MSB) 01110011000000000....
bitmap i-node 010011111000000000.......
i-node
1 - tipo d, modo 0755, root/root, nlink=5 size= 37 aree dati 3
4 - tipo d, modo 0755, root/root, nlink=2 size= aree dati 2
5 - tipo d, modo 0755, root/root, nlink=2 size= aree dati 1
6 - tipo d, modo 0755, root/root, nlink=2 size= aree dati 7
7 - tipo l, modo 0777, root/root, nlink=1 size=10 aree dati 6
8 - tipo c, modo 0755, root/root, nlink=2 rdev=1/3 aree dati ---- //special file, /dev/null
blocchi dati
1 (.,5)(..,1) //lost+found
2 (.,4)(..,1)("null.phy",8)("null.sym",7) //dir
3 (.,1)(..,1)("dir",4)("lost+found",5)(dev,6)
6 ../dev/null //link simbolico
7 (.,6)(..,1)("null",8) //dev
//link fisico: più nomi allo stesso file
//link simbolico: stringa contente il path dell'altro file , si riferisce a quel file
-----------------------------------
Lezione di Mercoledi 8 Maggio 2019
-----------------------------------
es c1 11 sett 2017
monitor crossing
ok2dir[4]; //NESW
bool busy = false;
pe entra(int dir)
if (busy)
ok2dir[dir].wait();
busy = true;
pe esci(int dir)
busy = false;
ok2dir[(dir + 1) % 4].signal();
if (!busy)
ok2dir[(dir + 2) % 4].signal();
if (!busy)
ok2dir[(dir + 3) % 4].signal();
if (!busy)
ok2dir[(dir + 4) % 4].signal(); //dir
//alternativa più compatta
pe esci(int dir)
busy = false;
for (i = 0; i < 4; i++)
if (!busy)
ok2dir[(dir + i + 1) % 4].signal();
//Esercizio C1 - 28 Maggio 2018
#define MAXPROC n
Condition: Ok2Entrare; //Quando un processo può entrare: quando entriesStack.Count() < MAXPROC
Condition: Ok2Uscire; //Quando un processo può uscire: quando entriesStack.Top() == 1
Stack<int> entriesStack;
Procedure-entry: entra(int id)
{
if (entriesStack.Count() >= MAXPROC)
{
Ok2Entrare.Wait();
}
entriesStack.Push(id);
if (entriesStack.Count() == MAXPROC)
{
Ok2Uscire.Signal();
}
}
Procedure-entry: esci(int id)
{
while (entriesStack.Top() != id)
{
Ok2Uscire.Wait();
}
entriesStack.Pop();
Ok2Uscire.Signal();
if (entriesStack.Count() == 0)
{
Ok2Entrare.Signal();
}
}
Stack<int> entriesStack;
int vid[MAX];
condition ok2esci[MAX]
int in = 0; out = -1;
Procedure-entry: entra(int id){
if (in >= MAX)
ok2entra.wait()
vid[in++] = id;
if (in < MAX)
ok2entrai.signal()
else
out = MAX - 1;
}
Procedure-entry: esci(int id)
for (i = 0; i< in; i++)
if (vid[i] == id)
break; //cerco l'indice di id nelvettore vid
if (i != out)
ok2esci[i].wait();
if (out > 0) {
out--; ok2esci[out].signal();
} else {
out--; in = 0; ok2entra.signal();
}
#define fromDX 1
#define fromSX 0
monitor bridge {
int carsOnBridge = 0;
int shipping[2] = {0, 0}; //navi da entrambe le direzioni
int status = NONE; //UP DOWN NONE
int last2pass = 0; //ultimo che ha passato il ponte
int waitingC = 0; //coda delle macchine che aspettano
int waitingS[2] = {0,0}; //navi che stanno aspettando
condition ok2ship[2]
condition ok2drive
p.e. car_enter(int direction){
if(carsOnBridge >= MAX || status == UP || waitingS[0] + waitingS[1] > 0 ){
waitingC++;ok2drive.wait;waitingC--;}
status = DOWN;
carsOnBridge++
if (carsOnBridge < MAX)
ok2drive.signal(); //vanno tutte le MAX car che stanno aspettando
}
p.e. car_exit(int direction){
carsOnBridge--
if (waitingS[0] + waitingS[1] == 0)
ok2drive.signal();
if(carsOnBridge == 0){
ok2ship[0].signal(); ok2ship[1].signal();
}
if(carsOnBridge + waitingS[0] + waitingS[1] == 0)
status = NONE
}
p.e. ship_enter(int direction){
if (bridge = DOWN || shipping[direction] != 0 || waitingC > 0)
{waitingS[i]++; ok2ship[i].wait(); waitingS[i]--; }
isBridgeUp = false;
shipping[i] = 1;
p.e. ship_exit(int direction){
shipping[i] = 0;
if (waitingC == 0)
ok2ship[i].signal()
else if(shipping[1-i] == 0)
ok2drive.signal();
if(carsOnBridge + waitingS[0] + waitingS[1] == 0)
status = NONE
}
Proposta di soluzione:
Monitor riempisvuota {
Int MAXPROCESSI;
Stack s;
condition ok2enter;
condition ok2exit;
p.e void entra(getPid()){
if( s.size() >= MAXPROCESSI)
ok2enter.wait();
s.insert(getPid());
if(s.size() > MAXPROCESSI)
ok2exit.signal()
}
p.e void esci(getPid()){
if(s.size() > MAXPROCESSI && s.top == getPid()) {
s.pop();
ok2entra.signal()
}
else
ok2exit.wait();
}
//Esercizio C1 - 12 Febbraio 2018
#define MAXCAR n
#define UP 1
#define DOWN 0
Condition: Ok2TransitCars; //Quando una macchina può transitare: quando il ponte è giù e sopra ci sono meno di MAXCAR
Condition: Ok2TransitBoats[2]; //Quando una barca può transitare: quando il ponte è su e nessuna altra barca sta trasitando nella sua stessa direzione
Condition: Ok2BridgeGoUp; //Quando il ponte può alzarsi: quando non ho più auto che stanno transitando
Condition: Ok2BridgeGoDown; //Quando il ponte può abbassarsi: quando non ho più barche che stanno transitando
bool boatGoingUp = false;
bool boatGoingDown = false;
int carsOnBridgeCounter = 0;
enum BridgeStates
{
UP
DOWN
}
int bridgeState = BridgeStates.DOWN;
Procedure-entry: car_enter(int direction)
{
if (bridgeState != bridgeStates.DOWN || carsOnBridgeCounter >= MAXCAR)
{
Ok2TransitCar.Wait();
}
carsOnBridgeCounter++;
}
Procedure-entry: car_exit(int direction)
{
carsOnBridgeCounter--;
if (carsOnBridgeCounter == 0)
{
Ok2BridgeGoUp.Signal();
}
if (bridgeState == bridgeStates.DOWN && carsOnBridgeCounter < MAXCAR)
{
Ok2TransitCar.Signal();
}
}
Procedure-entry: boat_enter(int direction)
{
if (bridgeState != bridgeStates.UP || (direction == UP) ? /* 1 */ boatGoingUp : /* 0 */ boatGoingDown)
{
Ok2TransitBoats[direction].Wait();
}
if (direction == UP)
{
boatGoingUp = true;
}
else
{
boatGoingDown = true;
}
}
Procedure-entry: boat_exit(int direction)
{
if (direction == UP)
{
boatGoingUp = false;
}
else
{
boatGoingDown = false;
}
if (!boatGoingUp && !boatGoingDown)
{
Ok2BridgeGoDown.Signal();
}
if (bridgeState == BridgeStates.UP && (direction == UP) ? /* 1 */ !boatGoingUp : /* 0 */ !boatGoingDown)
{
Ok2TransitBoats[direction].Signal();
}
}
-----------------------------------
Lezione di Giovedi 2 Maggio 2019
-----------------------------------
link sol proposte: http://so.v2.cs.unibo.it/wiki/index.php?title=Prove_svolte_e_soluzioni_proposte
esercizio del giorno GG/MM/AAAA : http://www.cs.unibo.it/~renzo/so/compiti/AAAA.MM.GG.tot.pdf
Esame 21/06/2018
2018.06.21.tot.pdf
Esercizio c.1
/* Monitor tmon */
#define MAX n
#define TERRAFERMA 1
#define ISOLA 2
#define NONE 0
condition ok2unload;
condition ok2load[2];
condition ok2ship;
condition empty;
int onboard = 0;
int onramp = 0;
int current_port = NONE;
Procedure entry: al_porto(int location)
{
//arrivando
current_port = location;
ok2unload.signal();
if (onboard > 0)
empty.wait()
ok2load[location].signal()
if (onboard < MAX)
ok2ship.wait()
//partendo
current_port = NONE;
}
Procedure entry: imbarca(int location)
{
if (current_port != location || onramp > 0 || onboard >= MAX)
ok2load[location].wait()
onramp = 1;
}
Procedure entry: imbarcato(int location)
{
onramp = 0; onboard++;
if (onboard < MAX)
ok2load[location].signal();
else
ok2ship.signal();
}
Procedure entry: sbarca(int location)
{
if (current_port != location || onramp > 0)
ok2unload.wait()
onramp = 1;
}
Procedure entry: sbarcato(int location)
{
onramp = 0; onboard--;
if (onboard == 0)
empty.signal();
else
ok2unload.signal();
}
----------------------------
Esame 21/06/2018
2018.06.21.tot.pdf
Esercizio c.2 (da controllare)
#define N n // limite operazioni
semaphore mutex(1); // sezione critica
class lim_semaphore()
{
semaphore plus;
semaphore minus;
int value; //serve per significato
init(x) : { value=x; plus.init(N+x); minus.init(N-x);} //costruttore
P() : { plus.P(); value--; minus.V(); }
V() : { minus.P(); value++; plus.V(); }
}
class lim_semaphore()
{
semaphore mutex(1);
queue of semaphore okmin, okmax;
int value;
init(x) : { value=x; } // -N <= x <= N
P() {
mutex.P()
if (value <= -N) {
s=semaphore(0);
okmin.enqueue(s);
mutex.V();
s.P();
free(s); //dealloco il semaforo
mutex.V();
} else if (okmax.length() > 0) {
s = okmax.dequeue()
s.V();
} else {
value--;
mutex.V();
}
}
V() {
mutex.P()
if (value >= N) {
s=semaphore(0);
okmax.enqueue(s);
mutex.V();
s.P();
free(s); //dealloco il semaforo
mutex.V();
} else if (okmin.length() > 0) {
s = okmin.dequeue()
s.V();
} else {
value++;
mutex.V();
}
}
}
//soluzione proposta
#define N n // limite operazioni
semaphore mutex(1); // sezione critica
class unsigned_semaphore()
{
unsigned int value;
semaphore plus;
semaphore minus;
P()
{
mutex.P();
if(value < N)
{
if (value >= 0)
{
plus.P();
}
else
{
minus.V();
}
value--;
}
mutex.V();
}
V()
{
mutex.P();
if(value > -N)
{
if (value <= 0)
{
minus.P();
}
else
{
plus.V();
}
value++;
}
mutex.V();
}
}
------------------------------
Esame 21/06/2018
2018.06.21.tot.pdf
Esercizio g.1
//minimale
IC = 4,4,4 //massimo
COH = 1,1,1 //soldi in cassa
MAX ATT RES
P1 | 3,3,3 | 1,1,1 | 2,2,2
P2 | 3,3,3 | 1,1,1 | 2,2,2
P3 | 3,3,3 | 1,1,1 | 2,2,2
------------------------------
Esame 17/07/2018
2018.07.17.tot.pdf
Esercizio c.2
stack s;
semaphore mutex(1); // mutua esclusione
semaphore ok2consume(0);
Procedure entry: void push(int value){
mutex.P();
s.push(value)
mutex.V()
ok2consume.V()}
Procedure entry: int pop(){
int value;
ok2consume.P();
mutex.P();
value = s.pop();
mutex.V();
return value;}
-----------------------------------
Lezione di Mercoledi 17 Aprile 2019
-----------------------------------
NOTA: p.e. abbreviazione di procedure entry
2017.05.29.tot.pdf
Esercizio c.1:
condition okpartita
condition ok2chiama
condition ok2punteggio
condition ok2run[2][MAX]
int numpronti
int punteggio[2]
boolean partita=false, partitafinita=false
chiamati = []
contabandiera[2]
p.e. nuovapartita():
punteggio[A]=punteggio[B]=numpronti=0; partita=true; okpartita.signal(); chiamati = [];
p.e. chiama(l):
if numpronti<2*MAX ok2chiama.wait()
chiamati = l; contabandiera[A] = contabandiera[B] = 0; winner = None
for s in n:
ok2run[A][s].signal(), ok2run[B][s].signal()
ok2punteggio.wait()
punteggio[winner++]
if (max(punteggio) == 10)
if numpronti<2*MAX ok2chiama.wait()
partitafinita = true;
for s in A,B: for n in range(MAX): ok2run[s][n].signal()
return punteggio
p.e. pronto(s, n):
if !partita: okpartita.wait()
numpronti++
if numpronti>=2*MAX: ok2chiama.signal()
if partitafinita: return 1
else:
if not(n in chiamati) ok2run[s][n].wait()
numpronti--;
return 0
allabandiera(s, n):
contabandiera[s]++;
if (Winner == None and contabandiera[s] == len(chiamati)): winner = s
if (contabandiera[A] == len(chiamati) and contabandiera[B] == len(chiamati)):
ok2punteggio.signal()
casi da discutere:
se arrivano studenti a pronto prima che il prof dichiara nuovapartita succedono guai.
2018.09.19.tot.pdf
monitor dispatch
condition go_cart;
condition ok2station; //quando la stazione può caricare
current_station = None
//dizionario con chiave destinazione
luggages = {}
def countl(luggages):
n=0
for d in luggages:
n += len(luggages[d]);
p.e. cartat(code):
current_station = code //carrello arriva alla stazione
if (code == BLQ || len(luggages[code]) > 0):
ok2station[code].signal()
go_cart.wait()
current_station = None //il carrello sta viaggiando tra le stazioni
p.e. load(dst, owner):
if (current_station != BLQ || countl(luggages) >= MAX):
ok2station(BLQ).wait()
luggages[dst].append(owner)
if (countl(luggages) >= MAX)
go_cart.signal()
p.e. unload(dst):
if (current_station != dst || len(luggages[dst]) == 0)
//lunghezza lista dei bagagli con questa destinazione
ok2station(dst).wait()
owner = luggages[dst].pop()
if len(luggages[dst]) == 0)
go_cart.signal()
return owner
note:
se viene chiamata dispatch unload mentre il carrello non è lì deve bloccarsi.
2018.09.19.tot.pdf
Esercizio c.2:
dati asend/arecv devo implementare lssend lsrecv
lssend(dst, msg):
asend(dst, (MSG, myid(), msg))
arecv(dst)
lsrecv(snd):
asend(myid(), (TAG, myid(), NULL)) //mi mando un messaggio che riesco a riconoscere
while True:
(T, s, m) = arecv(ANY) //continua a ricevere finchè non ricevi il mio messaggio
if (T != TAG) data.push(s, m)
else break
while (((s,m) = data.pop(snd) == NULL): //cè il messaggio di src definito?
(T, s, m) = arecv(ANY)
data.push(s, m)
asend(s, (ACK, myid(), NULL)
return m
nota:
ls -> servizio di message passing sincrono e LIFO
2018.09.19.tot.pdf
Esercizio g.1:
P1(start=0): 5ms CPU, 5ms IO, 5ms CPU, 5ms IO, 2ms CPU
P2(start=4): 5ms CPU, 5ms IO, 5ms CPU, 5ms IO, 2ms CPU
P3(start=7): 5ms CPU, 5ms IO, 5ms CPU, 5ms IO, 2ms CPU
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
P|1 1 1|1 1|2 2 2|3 3 3|2 2|1 1 1|3 3|1 1|2 2 2*3 3 3|2 2|3 3|1 1|-|2 2|- - -|3 3|
I |1 1 1 1 1| |2 2 2 2 2|3 3 3 3 3|1 1 1 1 1|2 2 2 2 2|3 3 3 3 3|
r - - - - 2 - - 3 2 2 2 1 1 3 3 3 1 1 2 2 - - - 2 2 2 3 3 1 1
1 3 3
* 3 ha finito input output e 2 è ancora in esecuzione quindi cè da scegliere
----------------------------------
Lezione di Giovedi 11 Aprile 2019
----------------------------------
esame 16/07/2014 es c1:
BOUNDED BUFFER: (non richiesto dall'esercizio)
monitor bounded buffer
queue q;
condition oktoread; // q.length() > 0
condition oktowrite; // q.length() < MAX
procedure entry type read():
if (q.length() == 0) oktoread.wait(); //controllo
retval = q.dequeue(); //cambio lo stato
//abilito coloro che possono essere abilitati dal cambiamento di stato
oktowrite.signal()
return retval;
procedure entry void write(type elem):
if (q.length() >= MAX) oktowrite.wait(); //controllo
q.enqueue(elem); //cambio lo stato
oktoread.signal(); //abilito chi può essere abilitato
NOTE:
procedure entry ==> dichiarazione di funzioni (senza vedere l'implementazione dall'esterno)
Min-Max Monitor Bounded Buffer:
Queue Q;
//Condition: OKTOREAD: Q.Length > MIN
//Condition: OKTOWRITE: Q.Length < MAX
procedure entry: Type Read():
{
if (Q.Length <= MIN) OKTOREAD.Wait(); //Controllo
retval = Q.Dequeue(); //Cambio di stato
OKTOWRITE.Signal(); //Abilito chi vuole scrivere
return retval; //Qui sono sicuro perchè ne ho eliminato uno prima
}
procedure entry: void Write(Type elem):
{
if (Q.Length >= MAX) OKTOWRITE.Wait() //Controllo
Q.Enqueue(elem); //Cambio di stato
if (Q.Length > MIN) OKTOREAD.Signal(); //Abilito chi vuole leggere
}
esame 16/07/2014 es c2:
Semaphore mutex = 1;
struct Elem
{
Semaphore s;
int counter;
}
sturct Elem V[]; //Vettore a dimensione variabile. I nuovi elementi sono initializzati a s = 0, counter = 0.
void RendezVouz(int n)
{
mutex.P(); //Blocco, decremento di 1 (il processo si blocca se il semaforo vale 0)
V[n].counter++;
if (V[n].counter < n)
{
mutex.V(); //Rilascia, incrementa di 1
V[n].s.P();
}
V[n].counter--;
if (V[n].counter > 0)
V[n].s.V();
else
mutex.V();
}
esame 16/07/2014 es g1:
0241302
(0)2 2200
(1)3 1111
(2)4 4442
(3)0 0333
2 3 4 0 1 2 3 4 0 1 2 3
2 1 1 1 1 0 0 0 0
3 3 2 2 2 2 1 1 1
4 4 4 3 3 3 3 2 2
0 0 0 0 4 4 4 4 3
esame 17/07/2018 es c1:
monitor delirium {
condition ok2load;
condition ok2pour[]; //one element per type
int availablebeer[]; //one element per type
queue req[] // one element per type
queue reqt;
procedure entry void pour(type t, quantity c) {
if (c > availablebeer[t]) { //se non cè birra a sufficienza
c -= availablebeer[t]; //togli la richiesta
availablebeer[t] = 0; //bidone vuoto
req[t].enqueue(c); //richiesta per quel tipo di birra
if (req[t].length == 1) { //se è il primo che fa la richiesta
reqt.enqueue(t); //coda tipo di birra
ok2load.signal()};
ok2pour[t].wait(); //
req[t].dequeue();
availablebeer[t] -= c;
} else //se cè birra a sufficenza già all'inizio
availablebeer[t] -= c; // riempio il bicchiere
procedure entry type isempty() {
if (reqt.length() == 0)
ok2load.wait();
return reqt.dequeue();
procedure entry loaded(type t, capacity c) {
availablebeer[t] += c;
while (req[t].length > 0 && availablebeer[t] > req[t].head())
ok2pour[t].signal(); //ok, risveglio il barista
if (req[t].length > 0) { //se la coda si è riempita troppo rispetto alla capacità del fusto
reqt.enqueue(t);
ok2load.signal();
}
}
Monitor Delirum:
Condition: Ok2Load;
Condition: Ok2Pour[]; //Un elemento per Type
int availableBeer[]; //Un elemento per Type
Queue requests[]; //Un elemento per Type
Queue pendingRequests;
Procedure entry: void Pour(Type t, Quantity c)
{
if (c > availableBeer[t]) //Richiesta maggiore della birra disponibile
{
c -= availableBeer[t];
availableBeer[t] = 0;
requests[t].Enqueue(c);
if (requests[t].Length == 1) //Risveglio un magazziniere solo se è la prima richiesta di questo tipo di birra
{
pendingRequests.Enqueue(t);
Ok2Load().Signal();
}
Ok2Pour[t].Wait();
requests[t].Dequeue(); //Quando ho ottenuto la birra che voglio, elimino la mia richiesta
}
availableBeer[t] -= c;
}
Procedure entry: Type isEmpty()
{
if (pendingRequests.Length == 0)
{
Ok2Load.Wait();
}
return pendingRequests.Dequeue();
}
Procedure entry: Loaded(Type t, Capacity c)
{
availableBeer[t] += c;
while (requests[t].Length > 0 && availableBeer[t] > requests[t].head())
{
Ok2Pour[t].Signal();
}
if (requests[t].Length > 0) //serve per evitare che a causa di un magazziniere lento si accodino cosi tante richieste che mentre si sta caricando si svuota subito il fusto
{
pendingRequests.Enqueue(t);
Ok2Load.Signal();
}
}
----------------------------------
Lezione di Mercoledi 10 Aprile 2019
----------------------------------
Prima presentazione delle specifiche phase 2
----------------------------------
Lezione di Giovedi 04 Aprile 2019
----------------------------------
certificati per autenticazione
sa -> password
ha -> card (+ password) banca
è
autenticazione:
con password -> sapete
attaccata: tentativi, recuperare password, shoulder spying.
alcuni siti autenticano senza https ma con http.
come memorizziamo la password?
la macchina come riconosce che ho inserito la password?
si salva l'hash della password + salt il numero random in chiaro
il salt (sale) serve per non avere un dizionario che ha
come chiave la hash della password e come valore la password in chiaro.
https://haveibeenpwned.com/
challenge e response
nonce
Principi fondamentali della sicurezza:
accesso mediato, qualisasi tentativo di accesso deve avere un (unico) mediatore per l'accesso;
separazione dei privilegi, a particolari attività corrispondono particolari condizioni;
least privilege: le applicazioni devono avere il minimo insieme di privilegi possibile per "sopravvivere";
fail-safe defaults: nulla deve essere dato per automatico.
capability
diritti di accesso dati al soggetto
control list
posix access control list
----------------------------------
Lezione di Mercoledì 03 Aprile 2019
----------------------------------
errore: trap, fattori esterni: interrupt
non esiste security by obscurity (sicurezza per oscurità)
es. macchina Enigma, sicura la chiave non l'algoritmo.
se perdiamo solo una chiave verrà decifrato solo ciò che viene criptato con quella chiave
se perdiamo la sicurezza dell'algoritmo abbiamo perso tutto il sistema.
niente di peggio della falsa sensazione di sicurezza
trust: sicurezza PERCEPITA (può non c'entrare nulla con la reale sicurezza fornita)
hardware
es: stacco il filo
es: leggo la ram
es: guardo un bit vietato studiandone i suoi sideffect
firmware
bios
attacchi al sistema operativo
applicazioni
umani: attacchi di ingegneria sociale (es. phishing)
"l'utente è l'anello più debole di questa catena".
attacchi attivi e passivi
attacchi interni ed esterni.
crittografia chiave simmetrica e chiave doppia (pubblica privata)
encryption - decryption
DES:
L R
L' = R'
R' = XOR (L, owf ( K, R ) )
encryption ripetuta per 16 volte
2^64
2^10 circa 1k (1000)
2^64 sono circa 1k^6
per generare le chiavi due numeri primi si usa una "buona probabilità" che siano primi.
RSA:
pq = n
(p-1)(q-1) = phi
mcm (e, phi) = 1
d*e = 1 mod n
m^e mod phi = Q
Q^d mod phi -> m
p= 11 q= 13
pq=143
(p-1)(q-1) = 120
ecnription e= 7
primo con 120
d = 103
autenticazione
autorizzazione
problemi che possono causare attacchi
buffer overflow
Record di Attivazione
es. https://xkcd.com/1354/
Attacchi TOCTOU (Time of Check, Time of Usage): sostituendo l'entità in uso dal momento del controllo al momento dell'uso.
Uova di Pasqua (Easter Eggs): funzionalità nascoste all'interno dei programmi.
Cavallo di troia (Trojan Horse): uova di Pasqua maligni.
- Rootkit: programmi che servono per fare, o mantenere, privilege escalation. Per fare ciò sfrutta: codice con bug, amministratore poco accorto, cattive abituidini di uso.
- Logical bomb: porzione di codice inserito in un programma apparentemente innocuo e che resta latente fino al verificarsi di particolari condizioni che "attivano la bomba", ad esempio in un programma di gestione di un database una bomba logica può attivarsi al raggiungimento di un certo numero di recordsalvati oppure quando viene cancellato un preciso dato
- Backdoor: (vedere WarGames per cultura personale)
- Worm (vermi): sono interi programmi, non si diffondono come sideeffect di un operazione umana ma sono autonomi
nella loro diffusione (autoreplicanti)
primo warm esistito:
Morris
carmedy mellon
1. sendmail : mta (mail trasport agent) comando in pipe
2. rsh: (sun, solaris) carattere tilde ~
3. finger
Morris: "voglio fare un programma che fa in automatico questo tipo di attacco, se ci riesce copia se stesso
non faceva nessun danno volutamente, ma di fatto ha bloccato internet per un intera giornata
provare al mondo che era tutto molto fragile.
effetto a cascata saturata la rete
dai worms ci si difende anche aggiornando il sistema
- un virus non è un programma, modifica codice esistente, inserisce nel codice modalità non desiderate
similitudine con i virus biologici.
sicurezza assoluta non esiste
non bisogna nascondere un problema di sicurezza
aggiornamento continuativo e attento
CERT centro controllo incidenti
creato in risposta al worms di Morris
----------------------------------
Lezione di Giovedi 28 Marzo 2019
----------------------------------
prove scritte 28.05 18.06 15.07
prove pratiche 29.05 19.06 16.07
prova pratica:
testo di 3 esercizi
1 obbligatorio (da 20 punti) da svolgere in C
(coinvolge le SYSCALL) dialoga con il sistema
2 facoltativi (da 10 punti ciascuno), un ulteriore esercizio in C / Python / Bash
si può consultare lo scibile umano purchè non sia una persona... e ci sia licenza PENSATI LIBERA.
spiegare perchè abbiamo fatto quelle scelte.
---------------- da correggere:
grub capire struttura di ext2 ext3 ext4
con grub se cambiate il kernel e lo rimettete allo stesso path funziona
grub update
lilo (più silly) si teneva traccia di dove erano i blocchi dati del kernel
poteva non funzionare perché era messo in blocchi dati differenti
nuovi boot loader
ext2.backup
/usr/include/ext2_fs.h
ghex /tmp/e2/e2
hd
----- end
Quando il File System trova un i-node valido ma non raggiungibile, lo posiziona nella cartella /lost+found, contrassegnandolo con il relativo valore dell'iNode (es. #12).
SICUREZZA
Concetto, obiettivi teorici
Protezione
meccanismi
Trust
percezione di sicurezza
sicurezza, protezione, trust sono indipendenti tra loro
bisogna stare attenti che siano uguali per non avere allarmi esagerati o allarmi inesistenti.
principi chiave di sicurezza:
1. non esiste alcun sistema completamente sicuro
2. la sicurezza non è uno stato, ma un processo
per ottenere l'ideale di sicurezza è un attività che dura nel tempo, non è instantaneo
componenti della sicurezza
hardware
software
humanware
Keep
It
Simple
Stupid
teorema del Kiss : Keep It Simple Stupid
ogni programma ha una probabilità non nulla di contenere errori
per ogni misura la probabilità di contenere errori
es. 1x larghezza 2x sicura
semplice il meccanismo di protezione
La probabilità di errori in un programma cresce in maniera più che proporzionale con la dimensione dello stesso.
garanzie della sicurezza:
1. confidenzialità / riservatezza
2. integrità
3. continuità di servizio
ognuna di queste ha il suo tipo di errore
confidenzialità -> errore di disclosure, rivelate cose che non dovevano essere rivelate
continuità -> denial of service DOS
integrità -> alterazione
problemi pratici:
sniffing traffico di rete che viaggia in chiaro:
viola confidenzialità
man in the middle
integrità
kernel panic
DOS
licenze:
cosa è? un contratto che lega chi crea conoscenza con chi fruisce conoscenza
stabilisce cosa si può fare e cosa non si può fare con la conoscenza
per la conoscenza c'è un AUTORE
non ha le stesse regole della MATERIA
categorie di licenze:
licenze proprietarie
licenze libere
definizione di Richard Stallman
1. utilizzata per qualsiasi scopo
2. studiata
3. copiata
4. possibilità di divulgare la conoscenza modificata
General Public Licence
5. se la rilascia ulteriormente non può cambiare licenza
----------------------------------
Lezione di Mercoledì 27 Marzo 2019
----------------------------------
INODE: contiene tutte le informazioni del file.
il nome serve solo per identificarlo.
VNODE: copia dell'INODE estesa con le informazioni
di controllo per l'uso corrente.
esempio: quanti processi hanno quel file aperto.
VNODE condiviso con tutti i processi.
file system
come vengono realizzati?
come messi mem secondaria, partizionamenti nelle lezioni precedenti
e struttura interna
struttura dati globale (il super blocco)
struttura dati per gestione aree utilizzate e libere
aree dati dove mettere il "vero" contenuto
come realizzare il concetto di file
archivio
entità atomica gestita dal file system
memoria secondaria come vettore di blocchi
file - vettore di blocchi
file
certo numero di blocchi in sequenza
allocazione:
1o metodo:
contigua
pro:
comodo
consente accesso diretto molto rapido
contro:
scomodo per file system dinamico
visione teorica
2o metodo:
allocazione concatenata
il blocco punta al blocco successivo
pro:
non c'è limite al file
contro:
scandire per la lettura finchè non si arriva al punto desiderato
3o metodo: allocazione indicizzata
esempio: FAT File Allocation Table (MS-DOS)
usa un tipo di concatenata
gli indici non sono nel blocco ma fuori
una tabella che ha tanti elementi quanti sono i blocchi dati del disco
vettore di indici
guadagni:
c'è la potenza di 2
se bisogna scandire bisogna scandire un solo blocco di FAT
lo abbiamo mitigato nella ricerca
problema:
FAT è fragile, se si rompe la tabella non si riesce a ricostruire la trama
esempio 2: BFFS Back File System (UNIX)
usa un tipo di indicizzata
quantità limitata di puntatori
dopo i primi n (es. 10) ce ne sono altri 3
l'ultimo punta ad altri puntatori di altri dati
puntatore ai blocchi diretti
puntatore ai blocchi indiretti
puntatore ai blocchi 2 volte indiretti
puntatore ai blocchi 3 volte indiretti
diventa molto grande ma è limitata
larghe porzioni del file riescono a essere recuperate
lista aree libere
fat usa lo stesso fat per le aree libere
alberi
la directory contiene infomazioni sui file
FAT - nella directory
pro:
c
contro:
non si possono fare link simbolici
UNIX - lista di coppie, nome e numero di I-Node
pro:
più nomi che puntano allo stesso I-Node
contro:
c
FAT file system:
Superblocco
FAT (tabella)
blocchi dati (il primo e' la dir radice)
UNIX (BFFS):
superblocco
Bit map i-node liberi
Bit map blocchiliberi
inode
blocchi dati
----------------------------------
Lezione di Giovedì 21 Marzo 2019
----------------------------------
123415
111444
x22211
xx3335
123415
111115
x22222
xx3333
xxx444
----------------------------
kernel
|-----------------------|
| FILE SYSTEM |
|--------|-----|--------|
| CD-Rom | SSD | Dischi |
|--------|-----|--------|
----------------------------
HW (hardware)
file: ha contenuto e attributi
contenuti dei file:
data, payload
attributi:
nome, tipo, locazione, dimensione, tempi, proprietà
tipo: (pratiche diverse devono essere gestite in modo diverso)
locazione: (andare a recuperare il contenuto dei file, es. schedario biblioteca)
proprietà: permessi e privacy.
contenuto:
sapere l'"alfabeto" esempio ASCII, Unicode, UTF-8
file binari: contengono dei numeri espressi in forma binaria, esempio
tipo:
eseguibile, sorgente, oggetto, libreria, documento di testo, documento elettronico
come riconoscere il tipo di un file?
1. gestione appositamente fatta dal S.O.
indicazione nel tipo
2. associare delle estensioni
esempio .c
indicazione è nel nome
3. magic number
nel numero cè l'indicazione del tipo di file
indicazione è nel contenuto
potrebbe essere a byte o a record
blocchi contenenti diverse informazioni correlate tra loro. stesse informazioni di tante identità
esempio rubrica con nome, telefono ecc.
HFS e HFS+: il tipo è negli attributi del file. Due campi -- creatore e tipo
esempio: prima apro sull' editor e poi sul documento
oppure click sul documento e si apre direttamente il work processor
Estensione
MSDOS 8 caratteri + 3 caratteri per estensione
UNIX ha scelto una gestione minimale:
tutti i file sono stringhe di byte
riconosce solo gli eseguibili in maniera diversa
scelta per la semplicità del sistema
di fatto usa un mix tra suffissi e magic number
Approfondimento dal terminale:
file *
<ripasso su domanda relativa al trashing (ruscamento)>
1234156710
4 frame
12121232323
2 frame
Workingset fa il conto dei frame necessari per elaborare i processi
finestra di n riferimenti
</ripasso su domanda relativa al trashing>
Viene utilizzato per creare dei fake file utilizzati solo per dare nomi alle cose. Lo fa il mondo Unix, che ha file speciali , "icone", per qualcos'altro. Ad esempio:c(rwxrwxrwx) e b(rwxrwxrwx) non hanno contenuto ma solo nome.
Tipo di accesso ai file:
- accesso sequenziale: è normale leggerli dal primo all' ultimo carattere.
- accesso diretto: non ha nella struttura logica una sequenza.
- accesso a indici: per la locazione.
L'indice è una chiave quindi non è detto che sia numerica.
k ora in un certo senso abbiam visto la visione di cos'è un file e l' altra unità chiave sono le directory
------------------ visione dell'utente --> directory sono logicamente contenitori in grado di contenere file o directory per poter creare una visione gerarchica di tutto questo l'insieme dei documenti , quindi l'utente bene o male le vede anche se non è programmatore anche l' utente che nella vita scrive solo lettere con il word processor sa che una cosa è scrivere con il word processor una cosa e l' eseguibile, sa andiamo a vedere invece la visione del programmatore perche nel file system ci saranno 3 visioni utente programmatore e implementatore.
andiamo a vedere la visione del programmatore , vista nei file system che hanno a che fare con i file system (?)
quali sono le system call utilizzate per accedere ai file [open,read,write,close,seek,lseek] che consentono di aprire e leggere un file
poi ci sono s call relative alla directory cioè crea directory , cancella directory, lista i contenuti della directory mkdir mk Amir (?)
poi ci sono le system call che servono per la scritture del file system per le informazioni di controllo quell che servono per cambiare i permessi chmod per cambiare la proprietà, chown per limitare la lunghezza o cambiare l'ampiezza di un file ecc.. e cose del genere mmm anche per cancellare , alcune di queste sono ben collocate mentre altre invece a seconda delle implementazioni quando togliete l'ultimo nome cancellate il file
quando parliamo delle directory nella visione utente
le directory a seconda dell'implementazione del file system e anche nella visione utente possono essere a singolo livello, ad albero, a grafo aciclico o a grafo.
a singolo livello vuol dire che c'è un elenco di file nel file sys
directory:
sono contenitori di file o ulteriori directory per costruire una gestione gerarchica dei documenti.
- a singolo livello:
un elenco di file
fat16 prima versione
- ad albero
directory e sottodirectory
- a grafo aciclico
alcuni nodi (tipo foglie) comuni a più percorsi
usato da Unix
- a grafo
il più generale
pk non farla a grafo completo?
perchè le visite del grafo sono molto più "difficili" per evitare di entrare in loop nei nodi non visitati
le visite dell'albero basta una ricorsiva
-------visione dell' implementatore:
dal livello più basso, file system nelle unità di memorizzazione; un disco è visto al di sopra del livello di accesso, come una sequenza di blocchi. Questa visione è scomoda per andare ad implementare al di sopra la struttura del file system .
ESIGENZE:
1) non ci interessa vedere il disco come un'unica entità ma vorremmo vedere il disco come più file system esistenti
2) il disco può servire per memorizzare le cose, ma anche contenere il Master Boot Record(MBR), caricamento del kernel da un'unità di memorizzazione secondaria-
Metodi di partizionmento:
MBR, Master Boot Record---->creato per il ottenere dal nome stesso il Master Boot Record (Primo blocco), al cui interno conteneva, vettore di 4 elementi, con inizio, ampiezza, (alias, geometria del disco, settore , cilindro, e testina)
[blocco pensato da 512Byte] 446, per codice di prima partenza, rimane spazio per 4 elementi da 16Byte, e l'ultimo è un magic number.
GPT, GUID Partition Table---->quando si partiziona, se si perde la tabella delle partizioni, c'è una replica della tabella stessa in fondo. Esistono delle Magic Number per riconoscere che tipo di partizioni sono state caricate.
partizioni:
1. MBR MasterBootRecord: blocco inizio e ampiezza , geometria del disco 4 possibilità di mettere 4 partizioni
2. GPT la tabella delle partizioni è ripetuta alla fine del disco perchè critica
visione del programmatore
open close read write seek
^ livello file
crea directory, cancella directory, lista il contenuto della directory
mkdir, rmdir, getdents (non da usare)
^ livello directory
chmod, chown, truncate
^ livello struttura
visione implementatore:
livello basso
i file system vengono memorizzati in unità di memorizzazione secondaria
un disco è visto al livello driver come una sequenza di blocchi
è scomoda per
esigenze:
1. più file system
2. contenere non solo il filesystem ma anche altri elementi (es. master boot record)
Allocazione contigua: cominci da un file e continui con gli altri per trovarlo. Il problema sono le modifiche.
1.ISO9660
masterizzato in CD, non lo si può modificare
allocazione contigua, aspetto positivo: velocità di accesso, anche difetti
i CD sono intrinsecamente ad accesso sequenziale
2.Puntatori
dinamico, ma l'accesso diretto è scomodissimo
allocazione concatenata (puntatore al successivo)
effetto positivo: file lungo a piacere (unico vincolo n blocchi)
3. Allocazione indicizzata
file di 1 blocco contiene puntatori ai blocchi, non dati
esempio:
se i blocchi sono da 4KB se voglio accedere a un punto random lo calcolo
vincolo non riesco a memorizzare più di mille blocchi,
risolvo con allocazione indicizzata multipla
quindi: contigua, concatenata, indicizzata che può essere multipla
potenza di due salta non potendo fare shift, divisione le risk
----------------------------------
Lezione di Mercoledì 20 Marzo 2019
----------------------------------
un algoritmo è a stack se:
- per ogni stringa di riferimento dato
- per ogni memoria
la situazione della memoria che ne risulta è un sottoinsieme di una memoria più ampia.
esempio:
A A
B B
C C
D
se c'è page fault in ... indicato con [...]
[A,B,C] x x
[D] v x
[altro] v v
t-1 t
A A A A
B B
C C
D
[A,B,C] -> S_t = S_{t-1}
[D] ->
D A A A A A
B B D D B B
C C C C D C
D D D
E notin {A, B, C, D}
E A A A A A
B B E B B B
C C C C E C
E E E
Quanto posso contare sulla memoria virtuale?
Se ho una memoria reale di 1GB, posso avere una memoria virtuale di 100GB? la risposta è no.
continua sempre a fare richieste di pagine mancanti mentre altri processi gli tolgono altre pagine, fenomeno di trashing (circolo vizioso).
la memoria virtuale si può implementare con locazione globale o divisa per i processi
Trashing: Durante il periodo in cui sta aspettando una pagina perde le pagine a lui utili. Quando usano più tempo per la paginazione che per eseguire codice utile.
quando avviene? quando il processo durante il periodo per recuperare una pagina utile a se stesso perde altre pagine utili.
esempio:
se abbiamo un programma che deve fare la somma di due numeri (A, B) e mettere il risultato in C.
load A
load B
sum A B
store C
il tempo di recuperare la pagina è dell'ordine dei millisecondi.
va in trashing se nel frattempo viene cancellata una pagina utile.
come si fa a vedere e risolvere il problema?
(grafico a schiena di balena, se si chiede troppo crollano)
come si valuta se un sistema sta andando in trashing?
si guarda il motivo per cui va in trashing
occorre che le pagine utili rimangono da quando succede pagefault a quando si risveglia.
ripeterà accessi a vari programmi
working set
starvation
ritarda almeno un processo, altrimenti ritardi tutti, altrimenti vanno tutti così lenti che per l'occhio umano sembra tutto bloccato.
-------------------------------
gestione degli altri dispositivi di Input/Output
i dispositivi di I/O sono tanti, diversi ma li possiamo caratterizzare in classi omogenee
unità a caratteri
terminali
unità a blocchi
floppi disk (il disco è capace di accedere a settori interi non singoli caratteri)
accesso sequenziale
terminali, stampanti, cd (spirale, si cerca di arrivare al punto giusto)
accesso random
modalità di accesso sincrona o asincrona
masterizzatori hanno bisogno di accesso sincrono
il terminale è asincrono
condivisibile
non condivisibile
(dipende dalle unità)
come migliorare accesso a I/O?
tecniche generali
-buffering
memoria temporanea per ammortizzare diverse velocità di trasferimento della macchina e dell'unità di I/O
-caching
(ha molte cose in comune)
copia veloce di dati accessibili più lentamente
si accede alla copia veloce se possibile
doppia copia
dopo richiede l'aggiornamento della memoria ufficiale
-spooling
caso di buffering estremo
esempio: bufferizzo tutto il file da stampare e poi mando tutto insieme.
-scheduling
a turni, per condividere i dispositivi
algoritmi di scheduling dipendono dal tipo di dispositivo
disco rotazionale
ovvero magnetico
molto comune
chiamato disco ma è fatto da tanti dischi sovrapposti che ruotano all'unisono e cè un pettine delle testine, sul cui ci sono due testine magnetizzabili, a che velocità?
dipende da ciò che abbiamo preso.
questo pettine si muove e a seconda della posizione riesce a scrivere su tutti i dati che stanno a equal distanta su discord, per accedere ad altri le testine devono essere spostate.
leggere, scrivere, seek (spostare le testine, meccanica, molto costosa dal punto di vista temporale)
nel cilindro corrente, se si vuole cambiare un altro cilindro si può fare la seek
quanto ci metto a leggere? quanto a scrivere?
- ritardo rotazionale in media mezzo giro
se prendiamo un disco con 5400 giri al minuto farà 90 giri al secondo. 5ms per arrivare lì in media.
- tempo di trasferimento
quanto ci mette dal disco al bus
- tempo di seek
non si riescono a limare più di tanto perchè coinvolgono parti meccaniche
per migliorare di poco bisogna spendere molto di più
il sistema operativo può intervenire sui tempi di seek,
usando scheduling per minimizzare la seek
come le mettiamo in ordine?
in modo brutale fifo, proprietà fondamentale non dà starvation
algoritmo dell'ascensore
verso di percorrenza
le ordiniamo in ordine crescente
due code
Algoritmo look (algoritmo dell'ascensore), non applicato se non sugli ascensori reali
richiesta(c)
se direzione ^:
se c > currcyl => aggiungi alla coda corrente
altrimenti aggiungi alla coda dir opposta
se direzione v:
se c < currcyl => aggiungi alla coda corrente
altrimenti aggiungi alla coda dir opposta
ATTENZIONE!
la disuguaglianza è una disuguaglianza stretta perchè altrimenti c'è starvation.
Esempio: Se sono al 3' piano e mi arriva una richiesta per il 3' piano, la accodo altrimenti mi bloccherei lì.
=======
while 1:
se direzione ^:
se coda corrente vuota
inverti le code, direzione = v
altrimenti
scegli il minimo nella coda corrente e fai seek
se direzione v:
se coda corrente vuota
inverti le code, direzione = v
altrimenti
scegli il massimo nella coda corrente e fai seek
si può fare meglio?
non dà starvation
ma le richieste sono distribuite lungo tutti i cilindri
quelle centrali sono privilegiate
invertiamo le code ma facciamo la seek al numero più basso della coda
Algoritmo "Circular Look" (C LOOK)
RAID disco
se mi servono 10Tera e ho solo dischi da 1Tera con una velocità entro cui non riesco andare che faccio?
prendo 10 dischi
pro: più veloce complessivamente, restando fissa la tecnologia dei dischi.
contro: è più fragile (ho maggiori possibilità che uno dei 10 dischi si rompa)
ogni disco ha il suo mirroring (copia di riserva)
time between failure (dovrebbero rompersi 2 dischi, dà sicurezza)
tempi di accesso
lettura (metà in una metà nell'altra, migliora)
scrittura (devo aggiornare entrambe le copie, peggiora)
più sistemi di RAID (noi studiamo 4 teorico e 5, 6 reali)
tempi medi di guasto
bit di parità per decidere se il dato è corretto o meno
esempio
10 tera in 10 dischi da 1 tera
mettiamone un 11 esimo che contiene il bit di parità di tutti e 10 i dischi
esempio con meno dischi 3, invece di 1 tera 4 bit
1011, 1101, 0111 | 0001 (disco di parità)
se si rompe il disco di parità,
se se ne rompe un altro con la parità e tutti gli altri posso ottenere tutti gli altri
XOR: (in qualsiasi ordine) A xor B xor C = Parità, ma anche A xor C xor Parità = B
questo è RAID4
lettura:
scrittura: serve 1 lettura e 2 scritture
il disco di parità diventa il collo di bottiglia
Parita(n) = Parita(n-1) XOR NuoviBit
RAID5
è RAID4 con parità a rotazione tra tutti i dischi
i blocchi ciclano in modo che la parità sia distribuita
e possiamo permetterci di perderci un disco, il sistema riesce a recuperare.
serve per guasti hardware
RAID6
meno applicato più costoso, ha due dischi di parità
e tollera 2 dischi rotti
più pesante l'algoritmo
più costoso.
valido se quello che stiamo facendo è altamente critico
dischi allo stato solido
molti diffusi oggi
numero finito di cicli di scrittura
si scrivono a livello di blocco, si cancellano a livello di banco
possiamo scrivere solo in area vuota, blank
blocchi molto grandi nell'ordine delle 256 pagine
dovremmo riscriverle tutte per modificare anche solo una sola pagina...
trim: il sistema dice che quelle aree non gli servono
write amplification
--------------------------------
Lezione di Giovedì 14 Marzo 2019
--------------------------------
Cravatta di oggi: "Terrazza del caffè la sera, Place du Forum, Arles" di Vincent van Gogh, al limite tra creatività e pazzia.
Memoria virtuale:
paginazione su richiesta = usa la paginazione
due bit in più nell'indirizzo delle pagine
bit di validità
(nelle lezioni prossime) -> bit dirty (pagina è stata modificata)
Se un processo tenta di accedere a :
|00000000000000000010|000000000000| (pagina 2, offset 0)
la MMU cerca l'elemento 2 nella tabella delle pagine
2 casi:
bit V acceso: okay la MMU risolve l'indirizzo (hardware)
bit V spento: si genera un PAGE FAULT
.... e' una trap (interrupt software)
il kernel riconosce che manca la pagina, carica da disco la pagina in un frame libero, aggiorna la tabella delle pagine (l'elemento 2 ha ora indirizzo di frame valido e bit V=1) e riattiva il processo.
PAGER:
aspetta richiesta di pagine mancante P
cerca un frame libero F
se non c'e':
cerca il frame "meno utile" G (qua intervengono gli algoritmi di rimpiazzamento)
dichiara G invalido
se G e' dirty salva G su disco
F <- G
dichiara F occupato
carica la pagina nel frame F
metti F nella tabella delle pagine all'indice P
dichiara F valido
riattiva il processo
Algoritmi di rimpiazzamento: scelgono la pagina meno utile
stringa di riferimenti :
sequenza dei # pagina acceduti
[ # pagina : 20 bit | offset : 12 bit ]
hp scolastica pagine 256 byte
se fossero 8 bit per # pagina
dato un processo che acceda agli indirizzi
aa7e 3432 9053 aaff cc21 3442
la stringa dei riferimenti risulta essere:
aa 34 90 aa cc 34
prendiamo la stringa di riferimenti di accesso alle pagine:
5 2 1 0 2 4 2 3 0 4 2 4 0 1 0 2 1 5 2 1
FIFO
(5)5 5(0)0 0 0(3)3 3(2)2 2 2 2 2 2(5)5 5 (1o frame)
x(2)2 2 2(4)4 4(0)0 0 0 0(1)1 1 1 1(2)2 (2o frame)
x x(1)1 1 1(2)2 2(4)4 4 4 4(0)0 0 0 0(1) (3o frame)
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ (15 Page faults)
politica FIFO = la pagina vittima e' quella da piu' tempo in memoria
(anomalia di BELADY)
4 3 2 1 4 3 5 4 3 2 1 5
(4)4 4(1)1 1(5)5 5 5 5 5
x(3)3 4(4)4 4 4 4(2)2 2
x x(2)2 2(3)3 3 3 3(1)1
^ ^ ^ ^ ^ ^ ^ ^ ^ (9 page fault)
(4)4 4 4 4 4(5)5 5 5(1)1
x(3)3 3 3 3 3(4)4 4 4(5)
x x(2)2 2 2 2 2(3)3 3 3
x x x(1)1 1 1 1 1(2)2 2
^ ^ ^ ^ ^ ^ ^ ^ ^ ^(10 page fault)
non è detto che con una memoria abbiamo meno page fault
si chiama anomalia di Belady.
Least Recent Used (LRU) quella meno recentemente utilizzata
5 2 1 0 2 4 2 3 0 4 2 4 0 1 0 2 1 5 2 1
LRU
(5)5 5(0)0 0 0(3)3 3(2)2 2(1)1 1 1 1 1 1
x(2)2 2 2 2 2 2 2(4)4 4 4 4 4(2)2 2 2 2
x x(1)1 1(4)4 4(0)0 0 0 0 0 0 0 0(5)5 5
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ (12 Page faults)
MIN = la pagina vittima e' quella acceduta in un futuro piu' remoto
fatta a posteriori per calcolare quanti sono i page faults minimi.
5 2 1 0 2 4 2 3 0 4 2 4 0 1 0 2 1 5 2 1
MIN
(5)5 5(0)0 0 0 0 0 0 0 0 0 0 0 0 0(5)5 5
x(2)2 2 2 2 2(3)3 3(2)2 2 2 2 2 2 2 2 2
x x(1)1 1(4)4 4 4 4 4 4 4(1)1 1 1 1 1 1
^ ^ ^ ^ ^ ^ ^ ^ ^ (9 Page faults)
questo è "ideale", ma non è un algoritmo che si può usare durante l'esecuzione.
LRU e MIN non soffronto della anomalia di Belady.
(esempio di registro a scorrimento per LRU approssimata)
se modifico ogni 1ms
[10000000] = 128 1ms
[01000000] = 64 2ms
[00100000] = 32 3ms
[00010000] = 16 4ms
[10010000] = 144 5ms
.. questo e' solo un esempio e lo capirete solo se avete partecipato alla lezione.
Def: Un algoritmo di rimpiazzamento A e' a stack sse:
Per ogni sequenza s, per ogni istante di tempo t,
chiamato State(A,n,s,t) l'insieme delle pagine in memoria al tempo t
applicando l'algoritmo A alla stringa s data una memoria di n frame,
per ogni n,m | n < m State(A,n,s,t) ⊂ State(A,m,s,t)
Teorema:
Se un algoritmo è a stack non può soffrire dell'anomalia di Belady
Dim:
Per la anomalia di Belady dobbiamo avere un page fault nella memoria più grande che non c'è nella memoria più piccola. Non è nel complementare di quelle usate.
MIN e' a stack: induzione su t
caso base :
t=0 Stato(n,t) vuoto Stato(n+1,t) vuoto
caso induttivo :
caso in cui l'accesso fuori da entrambe
caso in cui si prende quello fuori dalla piccola ma dentro la grande
caso di intersezione
Algoritmo di second chance o dell'orologio.
Reference bit: un bit che la MMU accende quando accede a quella pagina
le pagine vengono pensate come in una struttura circolare (lista) e quando avviene un page fault si scandisce la lista circolare, se il reference bit è vero lo si azzera e si passa alla pagina alla successiva, la prima che ha il bit spento è la vittima.
quando trovo una pagina vittima mi trovo a scandire da quella dopo la vittima.
non è a stack
chiede solo un bit alla MMU
in casi normali si comporta bene
è equo, è pratico.
5 2 1 0 2 4 2 3 0 4 2 4 0 1 0 2 1 5 2 1
second chance
(5)5 5(0)0 0 0(3)
x(2)2 2 2 2 2 2
x x(1)1 1(4)4 4
^ ^ ^ ^ ^ ^ ( Page faults)
legenda:
sottolineato = la lancetta è qui
corsivo = il bit è a 1, la pagina è acceduta
/*alg di rimpiazzamento: cercano quale tra le pagine in memoria è la meno utile ep ossa essere scaricata
Stringa di riferimenti: sequenza dei # pagina acceduti
Esempio: pagine da 256byte, ovvero 8 bit
AA7E 3432 9053 AAFF CC21 3432
la stringa dei riferimenti sarà: AA 34 90 AA CC 34 (prendo solo il i primi 16 bit)
prendiamo la stringa di riferimenti: 5 2 1 0 2 4 2 3 0 4 2 4 0 1 0 2 1 5 2 1
t0 x x x
t1 5 x x
t2 5 2 x
t3 5 2 1
Politica FIFO: scarico la pagina che da più tempo è in memoria (nell'es tolgo)
Non è detto che aumentando la capienza della "cache" la probabilita di page fault diminuisca (anomalia di Belady)
Least Recenty Used: butto fuori la pagina che da più tempo non è utilizzata*/
----------------------------------
Lezione di Mercoledì 13 Marzo 2019
----------------------------------
GERARCHIA DELLE MEMORIE
Primaria: volatile, veloce (ordine del nanosecondo), solitamente poco capiente
Secondaria: non-volatile, lenta (ordine del millisecondo), solitamente molto capiente
Terziaria: non-volatile, molto lenta (tempi umani), solitamente molto capiente
Tutti e tre le tipologie danno accesso alla loro memoria attraverso una API composta da due istruzioni: load e store.
BINDING
Processo che lega gli indirizzi logici a quelli fisici. Come si può implementare?
Momento della compilazione:
Pro: non c'è bisogno di supporto hardware, valida opzione per sistemi embedded e kernel;
Contro: il compilatore deve sapere quali altri processi stiano attivi (cosa quasi mai possibile), non è possibile avere più istanze dello stesso programma.
Momento del caricamento: il compilatore genera un codice con indirizzi "relativi" ad un punto idale di caricamento, una volta caricato gli indirizzi fisici sono calcolati partendo dall'indirizzo relativo.
Pro: non c'è bisogno di supporto hardware, posso avere più istanze dello stesso programma;
Contro: poco flessibile, non gestisce processi che richiedono memoria a runtime.
Momento dell'esecuzione:
Pro: molto flessibile, permette di limitare il range degli indirizzi accessibili da un processo (restituendo un chiamata trap);
Contro: c'è bisogno di un support hardware (componente chiamamo MMU, che "trasforma" gli indirizzi logici in fisici).
MEMORY MANAGER
Componente interno al kernel che gestisce la memoria, ovvero si occupa di:
allocazione (fare spazio per...);
gestione degli spazi liberi.
Frammentazione interna: la differenza fra la memoria assegnata ad un processo e quella effettivamente richiesta da quest’ultimo.
Frammentazione esterna: quando lo spazio libero complessivo nella memoria è sufficiente per soddisfare una richiesta, ma non è contiguo.
COME ALLOCARE
Contigua, viene assegnato un singolo intervallo continuo di memoria;
Non contigua, vengono assegnati diversi intervalli di memoria.
L'allocazione non contigua è piu flessibile, ma richiede una MMU più complessa.
Binding statico
Binding dinamico
Partizionamento della memoria in blocchi fissi di varie dimensioni ("Allocazione a partizioni fisse").
Pro: facile da implementare;
Contro: limita il parallelismo, crea situazioni di frammentazione.
Quando muoiono i processi lasciano la parte vuota frammentata, è quindi necessario compattare di tanto in tanto la memoria per migliorare la località e risolvere la frammentazione esterna. Il costo di questa operazione è alto ed aumenta linearmente con la dimensione della memoria.
Per limitare la frammentazione esterna è possibile scegliere tra varie politiche per l'assegnazione di aree libere di memoria, quali:
Best fit, si sceglie la più piccola area di memoria in grado di contenere la pagina (costa O(n), genera aree libere man mano più piccole);
Worst fit, si sceglie la più grande area di memoria in grado di contenere la pagina (costa O(n));
First fit, si sceglie la prima area di memoria in grado di contenere la pagina, partendo dall'inizio della memoria;
Next fit, si sceglie la prima area di memoria in grado di contenere la pagina, partendo dall'ultima posizione precedentemente visitata (utilizzato in quanto distribuisce i blocchi su tutta la memoria, in modo più omogeneo del FF).
COME GESTIRE GLI SPAZI LIBERI
Esistono due modi per tenere la contabilità delle aree libere:
liste, quando allochiamo si estrae un elemento dalla lista, quando il processo termina e la memoria viene rilasciata posso avere un elemento in più (se aggiungo una area libera isolata), un elemento in meno (se due aree libere si fondono in un'unica);
mappe di bit, creaiamo aree di memoria (ad esempio 4K) e associamo un bit a 1 se sono occupate o un bit a 0 se sono libere.
PAGINAZIONE
Frame: area di memoria fisica grande come una pagina ed allineata
Pagina: area di memoria logica
queste unità hanno ampiezza 2-4KB, oggi più utilizzata è la 4KB, quindi servono 12 bit per indirizzarlo.
abbiamo 4095 byte buttati al massimo (?)
frame liberi a caso, presi da dove vuole
un processo ha bisogno di 10 pagine? bene può prendere 10 pagine dove vuole in memoria
Un indirizzo logico è formato da [ # pagina | offset ]
La MMU associa ad ogni processo un vettore degli indirizzi dei relativi frame, detto Tabella delle pagine.
Dove posizionamo le tabelle delle pagine?
Non in memoria centrale, sennò pago due volte il costo di una richiesta (uno per accedere alla TLB, una per accedere all'indirizzo).
Non nella MMU, che diventerebbe sì velocissima ma anche altrettanto costosa.
Soluzione:
cerchiamo una via di mezzo, introduciamo nella MMU una Translation Lookaside Buffer (TLB), che salva pochi elementi (32-64) in modo da accederci velocemente. Ogni volta che si vuole risolvere un indirizzo di una pagina si controlla prima nella TLB, altrimenti si genera una chiamata trap (di tipo TLBMiss) e il sistema operativo ricarica la TLB. Nel caso ottimo il costo è O(1), ma sfruttando il principio di località temporale ciò è molto probabile. Non soffriamo di frammentazione esterna e solo nei casi limite abbiamo frammentazione interna.
Codice reentrant: le istruzioni vengono condivise su istanze diverse, mentre lo stack e i dati sono diversi (es. aree condivise per il codice eseguibile, aree riservate per i dati).
SEGMENTAZIONE
Aree di memoria di dimensione variabile che contengono informazioni omogenee. Ogni segmento è visibile dal programma (a differenza della pagina) e ha assegnato un nome (es. dati, testo, ecc.).
Un indirizzo logico è formato da [ # segmento | # pagina (interna al segmento) | offset ]
Vista del programma: indirizzo logico [ # segmento | # pagina | offset ]
Vista della memoria: indirizzo fisico
Loading dinamico: i processi richiedono di caricare ulteriore codice/librerie esterne a runtime.
Linking dinamico: i programmi non hanno all'interno tutte le funzioni che sono richiamate, ma esse vengono linkate alle relative librerie a runtime. Ciò facilita la manutenzione e la condivisione di librerie tra più processi (caricando una sola istanza della libreria a runtime).
Le funzioni utilizzate per il caricamento dinamico di librerie sono:
dlopen(filename, flags), carica in memoria la libreria dinamica specificata;
dlclose(handle), rilascia la libreria dinamica specificata.
---------------------------------
Lezione di Giovedì 7 Marzo 2019
---------------------------------
Schedulazione in Sistemi in tempo reale: sistemi dove la correttazza del risultato dipende non solo dalla correttezza della computazione, ma anche dal tempo in cui il risultato è prodotto. Sistemi in tempo reale programmati con linguaggi ad hoc. Non vi sono fattori che potrebbero causare eventi probabili - solo determinismo.
Lo scheduler è calcolato in fase non critica, quindi non ne sono aggiunti altri in fase critica.
esempio: alettoni di aerei, tempo reale
video, soft real time (al massimo crea fastidio ma non danni)
- TIPI DI PROCESSI REAL TIME E NON:
1) PERIODICI: deadline dei processi = periodo pre-impostato (es termostato centrale nucleare)
2) APEPERIODICI: Silenti, reagisce dopo un certo tempo dal fenomeno (es. Sistema antincendio).
Scheduler rate-monotonic: periodo più basso ha priorità più alta
- regola (Liu & Layland - preemptive) : https://en.wikipedia.org/wiki/Rate-monotonic_scheduling
(nella regola, n: numero di processi)
Utilizzando il 70% della CPU, si permette che tutti i processi arrivino a deadline.
- Earliest deadline first (EDF) - Introdotta durante la lezione del 27/2/2019
- Deadlock avviene, come detto ieri, sse il sistema ha risorse: non condivisibili, non prerilasciabili, non richiesta bloccante, attesa circolare (deve avvenire l'and delle 4 (ovvero: non condivisibili, non prerilasciabile, non richiesta bloccante, attesa circolare; come nella lezione di ieri)).
- detection, grafo di Holt che fotografa lo stato delle risorse al tempo t, la **riducibilita'** avviene lavorando su una copia di tale grafo.
- prevection
- avoidance, il sistema non puo produrre deadlock anche se questo puo peggiorare l'uso delle risorse
- ignorare il deadlock
// vedere KNOT (insiemi non banali di nodi tali che l'insieme di raggiungibilità sia l'insieme stesso, (chiusura transitiva)).
sarebbe utile non avere deadlock bloccando una delle 4 (in modo opportuno)
------ DEADLOCK PREVENTION ------
- Attaccare la mutua esclusione:
**mutua esclusione**, la risorsa non puo essere usata contemporaneamente => l'uso puo essere virtualmente **bufferizzato** (aggiungendo delle attese)
Mutua esclusione per la stampante viene risolta con il meccanismo SPOOL di stampa crea stampanti virtuali sempre disponibili che bufferizzano le cose da stampare).
In questo modo la stampante diventa condivisibile, ma richiede tempo.
Non in tutti i sistemi è applicabile (es. stampanti banca che non hanno SPOOLER).
- Attaccare la richiesta bloccante: viene chiesto ai processi di fare allocazione globale.
- Attaccare attesa circolare: Utilizzare allocazione gerarchica.
Le risorse vengono divise in gruppi di priorità (più preziose, meno preziose).
Es. Se ho risorse di priorità 3, e richiedo priorità 4, posso farlo.
Se da priorità 4 richiedo priorità 2, rilascio la 4, la 3, e poi posso prenderla. Non vengono creati cicli?
- Attaccare preemption: o c'è o non c'è, è possibile o meno salvare lo stato.
allocazione gerarchica a
le frecce vanno solo a destra
proc1
^ \
| \
___ v___ ___
| | | | | |
| 1 | | 2 | | 3 |
|___| |___| |___|
| | ^
| v /
---------> proc2 -------
----DEADLOCK AVOIDANCE----
Algoritmo del banchiere: https://it.wikipedia.org/wiki/Algoritmo_del_banchiere
Dati:
N = numero di clienti
IC = initial cash €$¥£ (monovaluta)
c[i] = max credit to client i, credit (fido italiano)
l[i] = sum leased to client i, prestito attuale
COH = cash on hand (saldo di cassa) //COH = IC - SUM_{i=1,N} l[i]
COH >= 0
"Il denaro in cassa deve poter soddisfare almeno un cliente.
Con il denaro restituito, si vede se se ne può soddisfare un secondo. "
E così via con gli altri clienti.
Se ciò avviene lo stato è SAFE.
s[1]...s[N] permutazione di 1,..,N
AVAIL[1] = COH
AVAIL[i+1] = AVAIL[i] + l[s[i]] (somma disponibile per ciascun cliente/processo) (con i = 1,...,N-1)
si ha: per ogni i: AVAIL[i] >= (c[s[i]] - l[s[i]])
in altre parole se definiamo n[i] = c[i] - l[i] (c - l = il massimo ancora richiedibile)
si ha: per ogni i: AVAIL[i] >= n[i]
Ogni processo può chiedere: c[i]-n[i]
C=Credito massimo richiedibile, c[p1], ...
L=Credito richiesto, l[p1], ...
N=Rimamente: n[p1], n[p2], n[p3]
N = C - L
-------------------------------------------
COH = 0
C L N AVAIL
p1 10 5 5
p2 8 2 6
p3 4 4 0
p3 4 4 0 0 //posso soddisfare p3 perchè mi chiede 0
//ma ha già chiesto il suo massimo richiedibile
4 //la banca ha solo 4, non può consegnare 6 a p2 se lo richiedesse
^unsafe
-------------------------------------------
COH = 0
C L N AVAIL
p1 10 5 5
p2 8 6 2
p3 4 4 0
p3 4 4 0 0
p2 8 6 2 4
p1 10 5 5 10
^safe
// AVAIL = AVAIL del processo che ha rilasciato + L del processo
-------------------------------------------
1° problema) Non si può pensare che esista un solo tipo di risorsa in un sistema (banchiere monovaluta, come negli esempi precedenti);
2° problema) Limite dell'algoritmo
"i greci chiamavano ADE l'inferno perchè Agenzia Delle Entrate era troppo lungo" cit.unknown
Banchiera Multivaluta:
Dati:
(I valori in grassetto non sono scalari ma vettori)
valute non convertibili
N = numero di clienti
IC = initial cash [¥,€,$] //vettore con elemento in yen, in euro ed in dollaro
c[i] = max credit to client i, credit (fido italiano) //al cliente io concedo al massimo tot di ogni valuta
l[i] = sum leased to client i, prestito attuale //al cliente i concedo tot di ogni valuta, in l[i] c'è la somma
//(somma prestata al cliente in ogni valuta)
COH = cash on hand (saldo di cassa) //COH = IC - SUM_{i=1,N} l[i] (differenza vettoriale, tra stesse valute)
COH >= 0 //per ogni valuta deve essere maggiore-uguale di 0 (ovvero, ogni componente del vettore COH deve essere >= 0)
n[i] = c[i] - l[i]
s[1]...s[N] permutazione di 1,..,N
AVAIL[1] = COH
AVAIL[i+1] = AVAIL[i] + l[s[i]] (somma disponibile per ciascun cliente/processo) (con i = 1,...,N-1)
si ha: per ogni i: AVAIL[i] >= n[i]
//non è più una relazione di ordine totale, esistono elementi inconfrontabili (es. vettore [2,3] e vettore [3,2])
//multibanchiere diverso da applicare separatamente per ogni valuta
//complessità ((n^2)/2)
COH = 0,2 // esempio 0 euro e 2 dollari
C L N AVAIL
p1 10,5 5,3 5,2
p2 8,4 6,2 2,2
p3 4,4 4,2 0,2
Controllo se AVAIL (a quel passo) >= N(p1)|N(p2)|N(p3)
C L N AVAIL
p3 4,4 4,2 0,2 0,2
p2 8,4 6,2 2,2 4,4 //AVAIL(p2) = (L(p3)+AVAIL(p3))
p1 10,5 5,3 5,2 10,6
//SAFE
Esercizio g.1, http://www.cs.unibo.it/~renzo/so/compiti/2018.09.19.tot.pdf
Pa: (start t=0) cpu 5ms, io 5ms, cpu 5ms, io 5ms, cpu 2ms
Pb: (start t=4) cpu 5ms, io 5ms, cpu 5ms, io 5ms, cpu 2ms
Pc: (start t=7) cpu 5ms, io 5ms, cpu 5ms, io 5ms, cpu 2ms
tempo:
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
CPU *
a a a|a a|b b b|c c c|b b|a a a|c c|a a|b b b|c c c|b b|a a|c c|x|b b|x x x|c c|
RQ
b c b ba ac c a
IO
|a a a a a| |b b b b b|c c c c c|a a a a a|b b b b b|c c c c c|
Nota * : qui potevamo scegliere sia c che b
x = RQ (Ready Queue) vuota quindi lo scheduler lancia idle
---------------------------------
Lezione di Mercoledì 6 Marzo 2019
---------------------------------
"Non tutti i processi sono uguali: alcuni processi sono più uguali degli altri." cit. La fattoria di Renzo Davoli.
Esempio:
(M) processo per la gestione della mail
(V) processo per la riproduzione video
V è più intensivo e quindi avra una priorità maggiore rispetto a M nell'ordine di esecuzione.
SCHEDULER PREEMPTIVE
Tipo di implementazione nella quale lo scheduler sceglie il processo a priorità maggiore, estraendolo da un readyQueue. Ciò però crea starvation.
AGING
Ho due valori:
priorità nominale
priorità attuale
Allo stato iniziale la priorità attuale del processo equivale alla priorità nominale. Ogni volta che si attende la sua priorità attuale aumenta finchè non arriva il suo momento di gloria, quindi viene eseguito. Una volta terminato la sua priorità ritorna al valore nominale.
La readyQueue può essere vuota? Sì.
Se lo scheduler non deve gestire nulla:
Opzione 1: si lancia un (finto) processo (che non viene accodato alla readyQueue) che genera un ciclo infinito, il quale termina quando si riceve un interrupt;
Opzione 2: si mette la CPU in stato di WAIT (disponibile solo nei processori moderni).
SCHEDULER CON CLASSI DI PRIORITA
Tipo di implementazione nella quale lo scheduler sceglie la readyQueue con priorità più alta. Ogni funzionalità (es. multimedia, server, ecc.) ha una readyQueue associata.
SCHEDULER MULTILIVELLO
Tipo di implementazione nella quale si uniscono le caratteristiche degli scheduler precedenti. Ha classi di priorità per ogni tipo di processo, ed ognuna di queste classi è gestita utilizzando algoritmi specifici, in base alle esigenze.
Esempio:
Priorità massima: multimedia (priorità statica);
Priorità alta: demoni/server (FCFS);
Priorità media: interattivi (RR);
Priorità minima: batch (SRTF);
Priorità infima: IDLE.
NICE
nice(int _inc)
nice(20)
System call che cambia la priorità del processo chiamante settandola al valore _inc. La priorità massima per processi utente é 0,la priorità massima per processi root é -20. Ogni valore di _inc fuori dal range {19(min), -20(max)} verrà clampato.
Maggiori informazioni: http://man7.org/linux/man-pages/man2/nice.2.html
----------------------------------------------
GESTIONE delle RISORSE
Problema: evitare che il sistema vada in deadlock.
Risorse possono essere:
- Fisiche (CPU, RAM, I/O, ...)
- Logiche (descrittori di processi, ...)
Classificazione delle risorse:
- Fungibili: risorse possono essere intercambiali, una vale l'altra. (es. banconote da 10 euro)
- Non fungibili: risorse specifiche che non possono essere sostituite da altre. (es. bambino all'uscita della scuola)
Le risorse possono essere divise in classi. Due risorse appartenenti alla stessa classe sono equivalenti per il processo.
Le risorse possono essere assegnate
- Staticamente: il processo mantiene quella risorsa (es. descrittore del processo, a cui non si toglie il processo finché non è finito);
- Dinamicamente: i processi richiedono le risorse durante la loro esistenza, le usano una volte ottenute e le rilasciano una volta una volta che non sono più necessarie
- L'assegnazione delle risorse ai processi può essere bloccante o non bloccante
- La richiesta di risorse può essere singola o multipla: fa una richiesta alla volta per classe, o ne fa per classi multiple;
- Condivisibili (non seriali, utilizzabili insieme) o non condivisibili (seriali)
- Preemptable (es. allocazioni di memoria): se la posso salvare in modo da ripristinarla successivamente
- non preemptable: l'opposto della preentable.
Tutto ciò dipende dalla natura della risorsa.
Quando non c'è deadlock?
- Quando non c'è contesa nell'accesso, ovvero se la risorsa è condivisibile, altrimenti può esserci deadlock.
- Se la risorsa è prerilasciabile non c'è deadlock.
- se la richiesta non è bloccante non c'è deadlock.
esempio: processo P e processo Q
processo P: get A, get B.
processo Q: get B, get A.
se la richiesta è bloccante c'è deadlock.
per deadlock quindi avremo almeno: non condivisibili, non prerilasciabile, non richiesta bloccante, attesa circolare.
necessarie e/o sufficenti
- Come si può gestire/trattare il deadlock.
1. deadlock detection: vogliamo scoprire se c'è il deadlock
2. "gestire" deadlock prevention (strutturalmente non si presenta) e deadlock avoidance (mantiene l'attribuizione di risorse in stato SAFE, nel quale abbiamo garanzia che in futuro non possa avvenire deadlock).
3. Algoritmo "Ostrich" (mettere la testa sotto la sabbia): l'algoritmo opera come se il deadlock non esistesse.
Come capire se il sistema è in deadlock:
- Tenere contabilità dell'attribuzione delle risorse. Visione complessiva.
- Tenere traccia delle richieste tramite struttura dati creata per gestire le richieste del tipo: Grafo di Holt (è un grafo diretto bipartito)
Grafo di Holt presenta -> due partizioni di nodi: sottoinsieme dei nodi-processo e sottoinsieme nodi-risorse.
-> archi che vanno da processo a risorsa e viceversa.
Direzione archi:
processo -> risorsa: il processo sta richiedendo quella risorsa.
risorsa -> processo: il processo sta utilizzando la risorsa.
\
1° Teorema: se il grafo di Holt ha un ciclo (attesa circolare), allora c'è deadlock (in multirisorse è falso).
- Tramite il grafo di Holt si può vedere se c'è deadlock:
1° metodo: "processo di riduzione di un grafo di Holt": dato un grafo di Holt multirisorsa, si avrà deadlock sse il grafo di Holt non è completamente riducibile.
- Riducibilità del grafo di Holt: si dice Riducibile se esiste almeno un nodo processo che ha soli archi entranti, ed allora si può fare un passo di riduzione: si prende il processo con i soli archi entranti, si cancellano gli archi entranti, e le risorse liberate vengono assegnate agli altri processi richiedenti tali risorse;
- Un grafo si dice "Completamente Riducibile" se, dopo n passi di riduzione, si ottiene un grafo privo di archi;
esempio:
legenda: ● processo □ risorsa
A□ -> P● -> B□ -> Q● -> A□ è deadlock
1● <- A□ -> 2● -> B□ -> 3● -> A□ non è deadlock
(in questo caso 1, 2, 3 rappresentano l'ordine in cui si sbloccano con passi di riduzione)
P● -> A□ -> Q● -> B□ -> R● -> A□ è deadlock e cambia solo il verso della freccia
- Gli archi possono anche essere pesati: il peso rappresenta le risorse ancora disponibili.
KNOT: Tutti (processi E risorse) hanno lo stesso insieme di raggiungibilità; non è per forza tutto il grafo, anche un sottoinsieme del grafo.
2o Teorema: Dato un grafo di Holt multirisorsa, Deadlock c'è sse c'è un KNOT.
E ora che abbiamo scoperto il deadlock?
Si può utilizzare un Checkpoint: si riprende dal punto di salvataggio del processo.
Non sempre però è possibile/utile (esempio banca, in cui si ritira ma il sistema non ha processato il ritiro).
-----------------------------------
Lezione di Giovedì 28 Febbraio 2019
-----------------------------------
SCHEDULER
Lo scheduler organizza le risorse del sistema (es. memoria, file system, ecc.).
L'astrazione di processo che egli fornisce è realizzata attraverso l'uso di descrittori (ovvero strutture dati) detti Process Control Block (o PCB in breve), i quali racchiudono tutte le informazioni necessarie a descrivere un processo, quali:
identificazione, che permette di referenziare il processo univocamente (utile per il debugging);
stato, che può assumere valori "Ready", "Running" o "Blocked";
controllo, che racchiude tutte le informazioni necessarie al controllo (identità, processo padre, processi figli, privilegi, ecc.).
STATO DEI PROCESSI
.............
. Nascita .
.............
|
v
|---------| <--- |---------|
| Ready | ---> | Running |
|---------| |---------|
^ |
| |
| v
|-------------|
| Blocked |
|-------------|
Ready -> Running, se il processo viene scelto dallo scheduler.
Running -> Blocked, se il processo chiede di fare un'operazione bloccante.
Running -> Ready, dipende dal tipo di scheduler (es. processi con limite di tempo).
Blocked -> Ready, quando l'operazione bloccante viene completata.
Se un processo da Ready passa a Blocked (e quindi non termina completamente) è necessario salvare all'interno del relativo descrittore una "fotografia" della CPU e dei registri, in modo da poter continuare la computazione in un secondo momento.
COME FUNZIONA IL KERNEL
Esistono due principali modalità in cui un processo può essere eseguito:
kernel mode: modalità nella quale le istruzioni eseguite hanno completo accesso all'hardware sottostante e qualsiasi area di memoria.
user mode: modalità nella quale le istruzioni eseguite non hanno accesso all'hardware sottostante ed a specifiche aree di memoria.
Se il processo in user mode richiede una SysCall, l'Interrupt handler, riconoscendo la richiesta di SysCall, esegue il relativo frammento di codice in kernel mode. Terminata poi l'esecuzione il controllo ritorna al processo in user mode.
Il cambiamento della modalità di esecuzione di un processo (da kernel a user mode, e viceversa) crea mode switch.
La gestione delle modalità kernel mode e user mode viene implementata attraverso un componente hardware detto MMU (ovvero Memory Managment Unit), istruito dalla CPU, il quale mappa indirizzo logici ad indirizzi fisici (quando possibile).
MMU(IL) = IF
IL: indirizzo logico
IF: indirizzo fisico
In user mode gli IF non consentiti non fanno parte del codominio della funzione e quindi non sono raggiungibili.
(Kernel mode) ¦ (User mode)
¦
|-----------------| ¦
| init | ¦
|-----------------| ¦
| Creazione del | ¦
| processo init | (1) ¦
|-----------------| ¦
| ¦
_________|_________________________________¦_______________________________________ (punto del non ritorno)
| ¦
| |---------------------|<------¦--------------------------------|
| | interrupt handler | ¦ |
| |---------------------|<------¦----------| | (3)
| | ¦ | (3) |
| | ¦ | |
v v ¦ | |
|-----------------| ¦ |------------| |------------|
| scheduler | ¦ | processo | | processo |
|-----------------| ¦ |------------| |------------|
| ¦ ^ ^
| (2) ¦ | |
----------------------------------¦---------------------------------
(1) Viene generato un processo radice, detto init, che sarà il primo processo ad essere dato in pasto allo scheduler. La generazione del suddetto processo è unica durante tutto il ciclo vitale del kernel (ovvero fino al successivo avvio).
(2) Lo scheduler decide quale dei processi nelle ReadyQueue (ovvero la coda dei processi pronti per essere eseguiti) verrà eseguito, in base alle specifiche politiche ed implementazioni.
(3) I processi comunicano e mandano segnali allo scheduler attraverso uno specifico componente, l'Interrupt handler.
Nella maggior parte dei sistemi operativi i processi sono organizzati in forma gerarchica ad albero (vi è quindi una relazione di tipo padre-figlio tra i processi). Questa scelta implementativa porta diversi vantaggi, quali:
semplificazione del procedimento di creazione di processi;
le caratteristiche e i parametri non specificati vengono ereditati dal padre.
MULTITHREADING
La nozione di processo discussa in precedenza assume che ogni processo abbia una singola linea di controllo, ovvero esegua una singola sequenza di istruzioni alla volta.
Tutti i sistemi operativi moderni supportano l’esistenza di processi multithreaded in cui esistono molte linee di controllo, ognuna delle quali può eseguire un diverso insieme di istruzioni. Questa specifica architettura richiede l'introduzione di due nuovi campi all'interno del descrittore:
PID, process identifier;
TID, thread identifier.
Un PID può avere più TID associati (?).
| |
v |
|-----| v
| PCB |----------- | TCB
|-----| | TCB
| TCB
| TCB
Esempi:
In un web browser, lo scaricamento di due differenti pagine;
in un word processor, l'inserimento di nuovo testo in un wordprocessor mentre viene eseguito il correttore ortografico.
TIPOLOGIE DI SCHEDULER
Il diagramma di Gantt è uno strumento di supporto alla gestione dei processi.
|-----------------|-----------------|-----------------|
| P1 | P2 | P3 | Processi
|-----------------|-----------------|-----------------|
T0 T1 T2
Questo diagramma mostra che la risorsa (in questo caso il processore) e' usato dal processo P1 dal tempo T0 al tempo T1 poi da P2 dal tempo T1 al tempo T2,e cosi' via...
La terminazione/sospensione di un processo a favore di un'altro (arbitrato dall'Interrupt handler e scheduler) crea un content switch.
La terminazione/sospensione di un processo può essere causata da:
syscall bloccante;
terminazione "naturale";
passaggio di esso da Running a Ready;
passaggio di un altro processo da Blocked a Ready (es. quando termina l'I/O).
Scheduler non preemptive: scheduler che non permette al kernel di avere autorità sui processi (compatibile con i casi 1-2);
Scheduler preemptive: scheduler che permette al kernel di avere autorità sui processi (compatibile con i casi 1-2-3-4).
COME VALUTARE UNO SCHEDULER
La valutazione di uno scheduler dipende dall'uso che si fa di esso, a seconda delle necessità. Alcuni parametri sono:
utilizzo della CPU;
quantità di processi completati per quanto tempo (throughtput);
tempo di risposta.
CPU burst: utilizzo della CPU da parte di un processo.
I processi possono essere:
CPU bound, quanto utilizzano intensivamente la CPU e poi richiedono I/O (es. raytracing);
I/O bound, quando utilizzano brevemente la CPU ma richiedono un intenso I/O (es. lettura di dati dal disco).
CPU burst lunghi causano CPU bound.
CPU burst corti causano I/O bound.
MEDIA ESPONENZIALE
Tau(i) = a * Real(i-1) + (1-a) * Tau(i-1)
Tau(i): tempo stimato per l'i-esimo burst;
Real(i): tempo effettivo dell'i-esimo burst.
'a' e' il peso della predizione, ed e' un numero compreso tra 0 ed 1.
Un valore di a alto caratterizza poca inerzia e cambiamento repentino;
Un valore di a basso caratterizza molta inerzia e cambiamento graduale.
COME IMPLEMENTARE UNO SCHEDULER
Esistono varie tecniche, quali:
FCFS (First Come First Served): non preemptive, può causare l'effetto convoglio (processi con CPU burst lunghi possono essere privilegiati, creando una coda di processi con CPU burst corti) e la monopolizzazione della CPU da parte di pochi processi;
SJF (Shortest Job First): non preemptive, usa la media esponenziale (spiegata sopra) per stimare la durata del prossimo CPU burst;
SRTF (Shortest Remaining Time First): funziona come SJF ma e' preemptive... un processo che viene riattivato da un interrupt (quindi passa da stato blocked a stato ready) e ha una stima di durata del CPU burst inferiore al tempo rimanente per il processo ora running viene sostituito a quest'ultimo nel controllo del processore
RR Robin): basato sull'Interval Timer (componente hardware capace di inviare un segnale all'Interrupt handler dopo un determinato lasso di tempo), garantisce un time slice per ogni processo (in quanto un segnale interrupt viene generato se il processo richiede I/O o se l'IT interviene), risultando però troppo democratico. Indicato per sistemi interattivi.
(___) /¯¯¯¯¯\
(oo) < MOOO |
/------\_/ \_____/
/ | ||
* /\---/\
~~ ~~
SUPER COW POWERS
-------------------------------------
Lezione di Mercoledì 27 Febbraio 2019
-------------------------------------
COME SVILUPPARE UN SISTEMA
Per sviluppare il kernel (nucleo) di un sistema operativo occorrono diversi componenti.
Necessari:
scheduler, realizza l'astrazione sui processi;
gestione dei processi, consente la gestione dei processi (inizializzazione, terminazione, ecc);
gestione della mem. principale, allocazione e deallocazione di aree di memoria per i processi richiedenti;
gestione della mem. secondaria, gestione efficace delle unità di memorizzazione;
gestione del file system, realizza l'astrazione che rende accessibile la memoria secondaria;
gestione del networking, gestore dello stack TCP/IP e dei suoi vari protocolli;
gestione della sicurezza, supporti per il controllo dei diritti/accesso (es. evitare accessi non autorizzati);
gestione dispositivi di I/O, per il controllo delle periferiche.
Opzionali:
sistemi di virtualizzazione dell'hardware, che permettono la gestione di spazi di nomi separati (instruction set), permettendo il funzionamento di ambienti separati sullo stesso kernel;
shell, ovvero un'interfaccia che permette la comunicazion con il kernel (disponibile in macOS, non in Unix).
COME IMPLEMENTARE UN SISTEMA
Struttura semplice: agglomerato di singole librerie compilate insieme per ottenere il kernel (es. FreeDos (già MSDos)).
Pros:
efficienza, ogni funzionalità viene chiamata come chiamata di funzione.
Cons:
compatibilità, ogni dispositivo utilizza device diversi e necessita di librerie specifiche;
manutenzione, ogni modifica (a qualsiasi libreria) richiede la ricompilazione completa;
debugging, ogni errore causa sempre kernel_panic().
Struttura a strati: gerarchia di astrazioni successive in cui ogni strato parla un proprio linguaggio interno (es-. VFS per il fileSystem), si occupa di uno specifico task e offre serivizi all'esterno tramite una interfaccia/API.
La complessita è distruibuta sui vari livelli.
A livello più alto l'hardware non è nient'altro che un linguaggio con cui si puo interagire.
Pros:
trasparenza delle interfacce;
intercambiabilità, possibilità di caricare alcuni strati come librerie dinamiche;
modularità, possibilità di creare sistemi complessi "componendo" le varie librerie.
Cons:
minore efficenza.
Kernel monolitico: comprende tutte le funzionalità disponibili in un unico eseguibile (analogo all'architettura CISC nei processori).
Esempio: Linux ha linguaggi interni per ognuno dei suoi strati (stack di rete, file system, ecc.).
Microkernel: comprende un insieme ridotto di funzionalita (e.g. send, receive), le quali possono essere integrate caricando moduli aggiuntivi (analogo all'architettura RISC nei processori).
Esempio: MacOS si inizializza e lancia un unico processo che crea un'astrazione di FreeBSD.
Kernel flessibili (già proposti da Renzo Davoli(?)): kernel ibridi che posso avere parti di microkernel (per flessibilità) congiunte a parti monolitiche (per le performance).
E' sempre possibile "snellire" il kernel eliminandone le funzionalità superflue? Dipende dalle situazioni e dall'uso che si vuole fare del sistema.
Bisogona inoltre essere in grado di separare:
politica, cosa si deve fare;
meccanismi, come lo si fa.
MACCHINA VIRTUALE
Cosa si intende per "virtuale"? Data A una generica entità, B si dice A-virtuale se riesce a sostituire in modo efficiente e trasparente A.
L'hardware, come già visto, parla un linguaggio quindi se scrivo un SO che parli lo stesso linguaggio dell'HW, posso creare astrazioni su di esso (ovvero l'HW).
Instruction set processore + chiamate di accesso a bus, dove realmente esiste una corrispondente fisica al dispositivo.
Casi di utilizzo:
sandboxing, ovvero creazione di un ambiente sicuro ed isolato nel quale l'utente possa testare gli applicativi;
vendita di servizi a terzi (?)
architetture hardware diverse: es. sviluppo di applicazioni ARM su architetture x86.
QEMU: è un software che implementa un particolare sistema di emulazione (traduzione dinamica) il quale permette di ottenere un'architettura informatica nuova e disgiunta in un'altra che si occuperà di ospitarla.
1) Cross-emulation platform
2) Dynamic Translation
VirtualBox: è un software che supporta vari sistemi di virtualizzazione hardware (VT-x per Intel, AMD-V per AMD). Al generarsi di eccezioni, si richiama la hypervisor per il controllo.
File presenti nel percorso /boot:
system map, symbol table relativa al kernel;
config, file di configurazione usato per la creazione del kernel;
vmlinuz, immagine compressa del kernel.
'EDF': https://en.wikipedia.org/wiki/Eliest_deadline_first_scheduling (not a quote)
is a programming policy for periodic real-time processes.
the process with the closest expiry is chosen each time
is called "a dynamic priority" because the relative priority of two different processes at different times
It uses 100% of the CPU but despite the rule you look great, for security you prefer to stay on the simple and you prefer to use the rule of static forecast for real-time processes.
Scheduler rate-monotonic: lowest period has highest priority