Tutti i processi alternano burst di I/O a Burst di CPU. Questo perché tutti i processi devono effettuare delle operazioni di I/O, altrimenti sarebbero inutili. Questo vuol dire che esiste un'alternanza di operazioni interne alla CPU ed esterne.

È quel modulo del sistema operativo che effettua lo switch tra due processi. Il dispatcher è rigorosamente scirtto in assembly, per permettergli di maneggiare i registri. La latenza di dispatch è il tempo necessario per effettuare lo switching tra due processi, ed esso dipende da diversi fattori come i registri da salvare, ecc.

I criteri che andremo a vedere, sono dei criteri che non vengono applicati ai sistemi da noi comunemente utilizzati, ma in generale fanno riferimento ad un processo che viene eseguito su un generico sistema di calcolo.

Sicuramente decidere qual è il processo che deve essere assegnato alla CPU, è un problema di ottimizzazione; bisogna infatti scegliere il processo che ci permette di ottenere i migliori risultati.

• Utilizzo della CPU: La CPU deve essere tenuta più occupata possibile.

• Throughput: lo scheduling deve consentire di massimizzare il numero di processi che vengono eseguiti per unità di tempo.

• Turnaround time: tempo necessario per eseguire un particolare processo, ovvero il tempo calcolato da quando un processo entra nel sistema a quando termina.

• Tempo di attesa: tempo in cui il processo è in attesa la coda ready, ovvero la coda dei processi che attendono il proprio turno di essere eseguiti dalla CPU.

• Tempo di risposta: Nei sistemi odierni, più che i quattro punti precedenti, si ha interesse nell'ottimizzare il tempo di risposta. Questo vuol dire che bisogna ottimizzare il tempo da quando viene sottomessa una richiesta, fino a quando questa richiesta viene effettivamente eseguita.

  In parole spicciole, all'utente non interessa quanto tempo impiegherà l'intera procedura, ma interessa essere servito nel minor tempo possibile, anche se la sua richiesta non viene soddisfatta interamente.

• Massimo utilizzo della CPU
• Massimo throughput
• Turnaround time minimo
• Tempo di attesa minimo
• Tempo di risposta minimo

È essenzialmente un coda: basti pensare alla coda di un supermercato, è irrilevante che una persona abbia il carrello più pieno di un'altra, verrà servita in ordine di arrivo.

Supponiamo che i processi P₁, P₂, P₃ arrivino in ordine. Il Diagramma di Gantt sarà il seguente (vedi immagine). Il diagramma di Gnatt è essenzialmente un diagramma unidimensionale, dove sull'asse delle X viene posto il tempo.

Se il processo P1 arriva per primo, vorrà dire che, rispettivamente, P2 e P3 attenderanno 24 e 27 unità di tempo, prima di essere eseguiti. Quindi il tempo di attesa per ogni processo sarà:

• P₁ : 0
• P₁ : 24
• P₁ : 27

Ed il tempo di attesa medio sarà: (0 + 24 + 27) / 3 = 17

Se invece eseguissimo i processi in un ordine diverso, ovvero eseguendo per primo il processo "più piccolo", potremmo velocizzare i tempi di attesa:

Eseguendo in ordine: P₂ , P₃ : , P₁ otteniamo un tempo di attesa:

• P₁ : 6
• P₂ : 0
• P₃ : 3

Con un tempo di attesa medio: (6 + 0 + 3) / 3 = 3

Il tipo di scheduling FCFS è uno scheduling completamente inefficace. Questo perchè se davanti a dei processi con un tempo di esecuzione bassa, viene posto un processo che impiega molto tempo, i diversi processi dovranno attendere molto tempo per essere eseguiti, e quindi la CPU si focalizzerà su un unico processo, invece che su molti.

Succede quando abbiamo dei processi "mischiati", tra CPU-bound e molti I/O-Bound.

Processi di tipo CPU bound: Sono dei processi che utilizzano la CPU con lunghi burst, ad esempio processi di tipo scientifico.

Processi di tipo I/O bound: Ad esempio processi interazioni su database, dove i tempi di calcolo sono molto bassi, ma il tempo di attesa per le operazioni di I/O è molto alto.

Che succede se con una tecnica FCFS si mischiano questi due tipi di processo? Abbiamo lo stesso effetto di camion su una strada ad una singola corsia: mi trovo un camion che mi precede molto lento, l'equivalente di un processo che utilizza la CPU per molto tempo.

Bisognerebbe, ad ogni scelta, eseguire sempre il processo che richiede un tempo di CPU più basso. Se in qualche modo riuscissi a sapere la lunghezza del prossimo burst di cpu, potrei utilizzare questa informazione per assegnare la CPU al processo che ha il CPU burst più corto.

Questa tecnica è ottimale, ma il problema è che non è molto semplice conoscere la lunghezza del prossimo burst di CPU, infatti non c'è nessuna informazione che possa darmi questo tempo di burst.

Facciamo finta di avere questa informazione, i processi P₁, P₂, P₃, P₄ hanno rispettivamente un tempo di burst pari a 6, 8, 7, 3.

Dovremmo quindi ordinare i processi nell'ordine: P4(3) -> P1(6+3) -> P3(6+3+7) -> P2(6+3+7+8). Abbiamo quindi un tempo di attesa medio pari a : (3 + 16 + 9 + 0) / 4 = 7

Non è possibile determinare al 100% il prossimo burst, ma i processi diventano prevedibili, ed a comportarsi sempre allo stesso modo. Serve quindi un modo semplice per stimare il burst di CPU in base al comportamento passato di un processo.

Questa stima deve essere fatta in maniera tale da tenere presente sia il comportamento passato, sia il comportamento presente, ovvero devo tenere presente maggiormente cosa è successo nell'immediato passato, ed un po meno cosa è successo nel passato remoto del processo.

Possiamo prevedere il tempo di burst utilizzando la media dell'esponenziale:

1. τ_n = reale lunghezza dell n^th CPU burst
2. τ_n+1 = valore previsto per il prossimo burst CPU
3. α, 0 < α < 1
4. Definiamo: τ_n+1 = α t_n + (1 - α) τ_n

Questo significa che ogni volta devo conservarmi la previsione precedente, la combino con la formula con ciò che è stato effettivamente misurato, e con questa tecnica trovo la lunghezza prevista per il reale tempo di burst.

• α = 0

  • τ_n+1 = τ_n
  • La storia recente non conta

• α = 1

  • τ_n+1 = αt_n
  • Solo l'ultimo burst di CPU conta.

• Se espandessimo la formula, otterremmo:

  τ_n+1 = αt_n+1 + (1 - α) t_n-1 + ...

  ​ (1 - α)^j t_n-j + ...

  ​ (1 - α)ⁿ⁺¹ t₀ + ...

  Guardando la formula, siccome 1 - α è un valore minore di 1, che viene elevato sempre ad un numero crescente, otteniamo che teniamo conto di ciò che è accaduto in un passato remoto via via sempre di meno.

Non è necessario usare la formula, infatti ad ogni passo devo semplicemente prendere t_n, moltiplicarlo per un numero (magari dividerlo per due visto che basta uno shift); a questo numero basta aggiungere il tempo precedente t_n e moltiplicarlo anche lui per un numero (sempre diviso due). Di conseguenza non serve una grande potenza di calcolo per eseguire questo calcolo.

In questa slide si può vedere come la previsione (in celeste) si adatta al tempo reale di CPU burst. È inevitabile che per qualche tempo la previsione sarà errata, come ad esempio nelle prime due sezioni del grafico (lungo il tempo).

Questo tipo di scheduling è non preemptive, infatti i processi vengono eseguiti interamente prima di passare ad un altro processo.

Nel momento in cui arriva un processo mentre la CPU è assegnata ad un dato processo, ma questo nuovo processo ha bisogno di un burst più piccolo rispetto a quello che il processo in esecuzione deve ancora fare, allora lo scheduler toglie la CPU al processo corrente, e la assegna al processo appena arrivato, tecnicamente più veloce da completare.

Risposta: assolutamente no.

Nei sistemi interattivi, come quelli che vengono utilizzati nei nostri personal computers, vogliamo avere l'illusione che tutti i processi vengano eseguiti allo stesso momento. Questo significa che a nessun processo deve essere permesso di utilizzare la CPU per un lungo periodo di tempo, proprio perchè lascerebbe tutti gli altri processi "bloccati".

Nei sistemi interattivi sorge spontanea la soluzione di utilizzare uno scheduling a suddivisione di tempo, ovvero ogni processo ha una fetta minima di tempo, detta time slice che è il tempo massimo che può trascorrere con la CPU; questo tempo varia dai 10 ai 100 millisecondi (ms).

Dopo che questo tempo è esaurito, al processo viene tolta la CPU (quindi questo è uno scheduling di tipo preemptive) ed essa viene attribuita ad un altro processo.

Significa che in condizioni ottimali, se ogni processo ha 10ms, ogni secondo ho l'esecuzione di 10 processi diversi; all'occhio umano si ha l'impressione che tutti i processi vengono eseguiti in contemporanea.

Bisogna notare che non tutti i tipi di processo vengono schedulati per la stessa quantità di tempo, infatti alcuni processi vengono eseguiti per una piccola fetta di tempo, mentre altri per più tempo; tuttosommato si parla dell'ordine di millisecondi.

Se abbiamo nella coda ready n processi, ed il time slice è q, allora ogni processo riceve 1/n del tempo della CPU in chunk di al massimo q time unità in una volta.

Questo vuol dire che nessun processo (nel caso peggiore) attende più di (n-1) q time units. In parole semplici, al massimo un processo deve attendere il completamento di tutti i processi (eseguiti al massimo per il time slice definito) che sono in coda prima di lui.

Se il time slice q è molto grande, essenzialmente ogni processo riesce a concludere il suo burst in un'unica esecuzione, e di conseguenza si ricade nella situazione FIFO, dove il primo processo che arriva è il primo ad essere servito.

Si ha quindi interesse a porre q abbastanza piccolo (ma non troppo perchè qualora q fosse davvero molto piccolo, aumenterebbe lo switching di contesto [context switch] e di conseguenza l'overhead).

Viene stabilito un meccanismo a priorità, si associa ad ogni processo un numero (intero) che esprime la priorità del processo, e la CPU viene assegnata al processo avente la priorità più alta.

Per motivi storici, la priorità più alta, significa numero effettivo più basso! Ovvero a numeri più bassi viene associata una priorità più alta.

In un sistema in cui c'è un arrivo costante di processi a media-alta priorità, un processo avente una bassa priorità non verrà mai eseguito. In qualche modo bisognerebbe fornire un qualche tipo di meccanismo che eviti questo fenomeno.

Come si supera questo problema? Tutti i sistemi reali prevedono una soluzione basata sul meccanismo di aging: le priorità non vengono più assegnate in maniera statica, ma via via che un processo attende, la sua priorità aumenta; in questo modo, prima o poi, il processo verrà eseguito.

Di questa tecnica, ovviamente, esiste sia la versione preemptive che nonpreemptive; nella versione preemptive, esiste si la priorità per ogni processo, ma comunque esiste un time slice dopo il quale un processo deve essere sostituito da un altro. Questo vuol dire che a priorità uguale, si procede con la tecnica del Round Robin.

Questo vuol dire che se abbiamo due processi con la stessa priorità, questi si alterneranno fino a quando uno (o entrambi) avranno terminato.

L'idea è quella di avere delle code di processi separati, aventi priorità diverse:

Scheduliamo i processi che si trovano nella coda a più alta priorità in preferenza rispetto ad altri.

Più tempo di CPU viene consumato da un processo, più il processo (o meglio la sua priorità) viene degradato, in modo che esso verrà eseguito meno spesso.

I thread all'interno di un processo potrebbero visti come un tutt'uno con il processo stesso, quindi ricevendo lo stesso time slice di quel particolare processo, oppure potrebbero essere schedulati separatamente.

In questo contesto viene assegnato un tempo di CPU al processo, e poi all'interno del processo il time slice viene suddiviso tra i vari thread.

Questa tecnica serve per evitare che un processo avente molti thread utilizzi tutto il tempo di CPU a discapito degli altri processi.

In questo caso il thread viene schedulato come se fosse un processo a se stante.

Tra i vari parametri che possiamo aggiungere al momento di attivazione di un thread, è possibile aggiungere anche un parametro che dice al sistema se il thread deve essere schedulato in PCS o in SCS.

🏁 05-13 01:03

Cosa succede in un sistema con più CPU?

Sono disponibili dei CPU Scheduler più complessi nel momento in cui più CPU sono disponibili. Possiamo avere una delle seguenti architetture:

• CPU multicore
• Core multithreaded: CPU singola che si riesce a dividere in più cores virtuali che vengono trattati come se fossero core reali della cpu.
• NUMA Systems
• Sistemi eterogenei

Sostanzialmente, lo scheduling su core multipli è una tecnica di scheduling nata con i sistemi SMP, ovvero i sistemi dove è presente un multiprocessing simmetrico.

Con questa tecnica lo scheduler pesca i thread/processi da mandare in esecuzione su diversi core da un'unica lista di ready, dove sono posti tutti i processi.

Pur essendo una soluzione semplice da implementare non è una grande soluzione; questo perchè una volta che un processo T0 è andato a finire sul core0, alla prossima operazione di scheduling potrebbe andare a finire su un core diverso.

Questo vuol dire che nel primo core utilizzato dal processo, è presente una cache con dati del processo, mentre se cambia core, nelle cache non troveremo dati del processo in esame.

Con questa tecnica, abbiamo diverse code dove sono presenti dei processi già suddivisi, ed ogni coda verrà eseguita su un unico core della CPU. In questo modo, la cache di un processo rimane presente nel core su cui il processo è già stato eseguito precedentemente.

È possibile che, con la tecnica per-core, ad un core vengano assegnati pochi processi rispetto agli altri core. La soluzione è quella di, ad intervalli di tempo, ridistribuire il carico.

Questo è un fenomeno che si verifica nel momento in cui effettuiamo una ridistribuizione di carico tra i vari core; poniamo il caso che il core0 abbia pochi processi in esecuzione, e che il core1 invece ne abbia molti. Il core0, però, ha molti processi in attesa (magari per operazioni I/O).

Di conseguenza, se ridistribuisco il carico dal core1 al core0, il core0 si vedrà dapprima un gran numero di processi provenienti dal core1, e poi, una volta che le operazioni I/O dei suoi processi in attesa hanno completato, si vedrà arrivare anche questi altri processi.

Quindi, dobbiamo effettuare ancora una volta la ridistribuizione di carico, e questo è noto come l'effetto di ping-ponging.

Tutti i sistemi moderni, tendono ad aumentare la frequenza quando è presente un unico core occupato, mentre gli altri core sono "scarichi". Almeno su alcuni tipi di sistemi, si potrebbe avere interesse nell'eseguire tutti i processi su un core, in modo da ridurre i consumi energetici.

In un sistema di questo tipo, abbiamo un processore con più cores (ad esempio un quadcore - 4CPU), che a loro volta vengono divisi in più hardware thread:

Il sistema, però, visualizza ogni thread come un processore fisico, andando quindi a visualizzare il doppio dei processori reali.

Quando un thread viene eseguito su un processore, nel contenuto della cache di quel processore specifico, viene salvata la memoria acceduta da quel thread. Ci riferiamo a questo concetto come affinità per un processore.

• Soft affinity: Il sistema operativo cerca di mantenere l'esecuzione di un processo sullo stesso processore, ma non garantisce nulla.
• Hard affinity: consente al processo di specificare un insieme di processore dove esso potrà essere eseguito.

Real-Time significa che in qualche modo devono essere rispettati dei vincoli di tempo. Esistono due tipi di sistemi:

• Soft real-time: questi sistemi cercano di eseguire i task real-time critici con la priorità maggiore, ma non garantiscono nulla.
• Hard real-time: i task devono essere serviti entro la loro deadline.

Per uno scheduling real-time, lo scheduler deve supportare il preemptive. I processi hanno una nuova caratteristica: quelli periodici richiedono la CPU ad intervalli costanti.

In questo tipo di scheduling, le priorità vengono assegnate a seconda delle deadlines:

Più la deadline è vicina, più la priorità del processo sarà alta.

Tutti i SO, prevedono code di processi ordinate secondo priorità, dalle quali deve essere estratto velocemente il prossimo processo per ridurre quanto più possibile il tempo di context switch (overhead).

Si ha interesse ad avere delle strutture dati che supportano al meglio questo tipo di operazione.

Il tempo di scheduling di linux > 2.5 è di ordine costante, ovvero O(1).

• n = lunghezza media della coda
• W = tempo di attesa medio in coda
• λ = ritmo medio di arrivo nella coda

Questa semplice legge, ci dice che in codizioni di regime, la lunghezza media di una coda è data dalla formula:

n = λ x W

Per esempio, se con una media di 7 processi in arrivo per secondo, e normalmente 14 processi in coda, il tempo di attesa medio per processo è 2 secondi.

FINE CAPITOLO 5

In questo capitolo parleremo di sincronizzazione di processi che lavorano in un ambiente di memoria comune; per il momento, quindi, non terremo conto dello scambio di messaggi, ne del sistema operativo.

Facciamo un'astrazione: Abbiamo più processi che vanno in esecuzione, questi hanno un'area di memoria in comune sulla quale essi vogliono lavorare.

Questo problema è stato risolto utilizzando un buffer circolare, che non viene mai riempito fino all'orlo, proprio perchè le variabili in e out ci segnalano la memoria restante nel buffer. Quando i due puntatori sono sovrapposti, il buffer è completamente vuoto; per questo motivo possiamo utilizzare solo BUFFER_SIZE-1 elementi, perchè se utilizzassimo tutto lo spazio, i due puntatori sarebbero nuovamente sovrapposti, ma indicherebbero che il buffer è pieno, e non vuoto.

Con questo metodo, il processo produttore legge dal puntatore in, e scrive sul puntatore out. In modo speculare, il processo consumatore, legge il puntatore in, e modifica out. I problemi nascono nel momento in cui entrambi i processi vogliono modificare la stessa variabile in memoria comune. Link al capitolo precedente.

while(true){
    /*produce un item n*/
    while(counter == BUFFER_SIZE)
        ;    //do nothing
  buffer[in] = next_produced;
  in = (in + i) % BUFFER_SIZE;
  counter++;
}

while(true){
    while(counter == 0)
        ;    //do nothing
    next_consumed = buffer[out];
  out = (out + i) % BUFFER_SIZE;
  counter--;
}

Questo tipo di codice, ha senso solo nel momento in cui abbiamo diversi processi. Questo perchè abbiamo il loop principale con all'interno un ulteriore loop, che viene eseguito finché counter non viene modificata. Counter può essere modificata solo perchè è una variabile allocata in un'area di memoria condivisa, e verrà quindi modificata da un altro processo!

Morale della favola: purtroppo, questo metodo, non funziona.

🏁 05-13 1:42

Ci sono due processi che condividono un'area di memoria. Uno dei processi tende ad incrementare il puntatore, mentre l'altro tenderà a decrementarlo.

In Assembly non abbiamo effettivamente un'istruzione per incrementare o decrementare una variabile in memoria. Questo vuol dire che per incrementare o decrementare sono costretto ad usare (a linguaggio macchina) una sequenza di istruzioni del tipo:

load    register    val
addi    register     1
save    register    memory

È quindi semplice capire che come minimo abbiamo bisogno di 3 istruzioni per incrementare una variabile; cosa succede se queste tre operazioni (per incrementare) si sovrappongono alle altre 3 operazioni dell'altro processo (per decrementare)?

La prima operazione (di addizione) potrebbe perdere la CPU nel mentre sta eseguendo l'addizione, e la seconda operazione (di sottrazione) utilizzerebbe i dati nei registri ancora "sporchi" dall'operazione precedente, andando ad invalidare il risultato.