Università degli Studi di Perugia

LAUREA SPECIALISTICA IN INFORMATICA

Anno Accademico 2007/2008

SimulazioneProgetto:

Sistema elaboratore in multiprogrammazione

Studenti:

Manfucci Andrea

Ciambelli Davide

1

Introduzione

Il problema

In un sistema elaboratore in multiprogrammazione ogni programma è inizialmente caricato nel sistema da un lettore di schede, riceve poi una o più iterazioni di CPU e operazioni su nastro o disco e alla fine esce dal sistema stampando i risultati. Ogni lavoro riceve un numero di iterazioni distribuito geometricamente con media 4 iterazioni prima di uscire dal sistema attraverso la stampante. Terminato un servizio di CPU, se non esce ha 0,875 probabilità di richiedere un servizio disco e 0,125 di richiedere nastro. Il servizio CPU è esponenziale di media 0,8 s; quello di disco uniforme tra 0,5 e 2,5 s, e quello di nastro ancora uniforme tra 2 e 16 s. La coda Q1 è a due livelli A e B con prelazione e priorità a favore di A. All'interno di ciascun livello il servizio è FIFO. Le code Q2 e Q3 siano invece servite SPTF. Il 20% dei lavori in arrivo dall'esterno siano diretti alla categoria A e i rimanenti a B. Nel corso delle iterazioni i lavori conservano la propria classificazione. Il sistema può ospitare soltanto un numero limitato di programmi (Q1 + Q2 + Q3 <= 20). Nell'ipotesi che il sistema funzioni al massimo della capacità (20) determinare media e varianza del numero di lavori espletati per unità di tempo, al 90% del livello di confidenza.

Analisi del modello

Il sistema elaboratore in multiprogrammazione è un sistema chiuso formato da 3 nodi principali: una CPU che accetta programmi di tipo A e B ed altri due nodi DISCO e NASTRO che attendono i programmi processati dalla CPU stessa. Come detto precedentemente i programmi ricevono un numero di iterazioni distribuito geometricamente con media 4 prima di uscire dal sistema attraverso la stampante. Il 12,5% dei programmi che esce dalla CPU richiede un servizio NASTRO mentre il restante 87,5% richiede un servizio DISCO. Una volta terminate le operazioni in DISCO e NASTRO i programmi ritornano in CPU. Un programma esce quando il numero di iterazioni corrisponde a zero. Per mantenere costante il numero di programmi nel sistema (20) si genera un nuovo programma ogni volta che uno esce. Avremo quindi un andamento come quello rappresentato in figura:

Le code del NASTRO e del DISCO sono disciplinate con politica SPTF (Shortest Processing Time First) dove ha priorità massima il job che richiede minor tempo di servizio. La coda della CPU invece è disciplinata con politica FIFO. Il lettore di schede inizialmente carica nel sistema un numero di programmi pari a 20 che viene mantenuto costante per tutto il tempo della simulazione. In queste condizioni, assumendo per ipotesi che il sistema funzioni al massimo della capacità, è

2

nostro compito determinare media e varianza del numero di lavori completati per unità di tempo, al 90% del livello di confidenza.

Studio teorico

Per rendere più chiara l’analisi del sistema, è necessario spiegare alcuni aspetti essenziali del modello e l'uso di determinate variabili, comprese quelle caratterizzanti le code. Il Tempo medio di Interarrivo (Ta) indica l’intervallo medio di tempo che intercorre tra l’arrivo di un programma alla CPU e il successivo mentre il Tempo medio di Servizio (Ts) mediamente indica quanto tempo spende un programma nel sistema. Considerando che il numero di programmi nella rete è fisso e non sono ammessi arrivi da e partenze per l'esterno, possiamo affermare che questo è un sistema a rete di code chiuso. Reti di questo tipo sono dette reti di Gordon-Newell. Questo modello è analogo al modello di Jackson se non per l'ipotesi che λi = 0, ∀ i ; non si verificano arrivi dall'esterno, tutti gli arrivi provengono da nodi della rete. Ciò significa che il numero di clienti nel sistema è costante e che quando un cliente completa il suo ciclo complessivo di servizi, viene sostituito da un nuovo cliente che inizia il ciclo di servizio. Tale modello è stato introdotto per rappresentare la competizione dei programmi per il processore e per le periferiche di I/O in un sistema di calcolo multiprogrammato. I programmi sono rappresentati dagli utenti e K è il livello di multiprogrammazione. L'esecuzione di un programma sul processore è rappresentata dal servizio al nodo uno, mentre l'attività sulle periferiche è modellata dal servizio negli altri nodi. In particolare si assume che l'esecuzione del programma sia costituita da una successione di segmenti di esecuzioni sul processore e sulle periferiche. Assumendo che il livello di multiprogrammazione sia costante e che vi siano sempre nuovi programmi da elaborare, la terminazione di un programma non cambia il modello se si ipotizza che immediatamente un nuovo programma inizi il suo ciclo di elaborazione.

Sia K il numero totale di utenti presenti nella rete. Il vincolo di rete chiusa porta ad una limitazione dello spazio degli stati, che è definito da

S={k=k 1, k 2, ... , k N ∣k 1k 2...k N=K }

La cardinalità dello spazio degli stati |S| è dunque finita e può essere valutata con un semplice ragionamento di matematica combinatoria. Essa coincide con il numero di possibili suddivisioni dei K clienti in N gruppi, che rappresentano i nodi. Quindi, se si immagina di allineare i clienti lungo una retta, la suddivisione equivale ad inserire N-1 separatori tra i K utenti. Si ottiene così un totale di K+N-1 oggetti, di cui K sono clienti e N-1 separatori. Quindi, il numero delle possibili disposizioni di clienti e separatori è pari al numero di combinazioni di N-1 oggetti su un totale di K+N-1, e quindi si ha

S=KN −1N−1

Anche nel caso di reti chiuse si definisce la generica probabilità di instradamento nella rete rij come la probabilità che un cliente che termina il servizio nel nodo i entri nel nodo j. Venendo meno il contributo dall’esterno, per ogni nodo j, l'equazione di traffico diventa

λ j=∑i=1

N

r ij λi , j=1, 2, ... , N

Supponendo di conoscere le probabilità di instradamento, il sistema è un sistema omogeneo di N equazioni in N incognite, per cui esso ammette infinite soluzioni. È quindi possibile calcolare solo i

3

valori relativi delle frequenze di arrivo, cioè ad esempio

λ j=b j λ1 , j=1,2, ... , N

per cui, dividendo per λ1, le equazioni di traffico diventano

V j=∑i=1

N

r ij b i=r 1j∑i=2

N

r ij bi , j=1, 2,... , N

che si riduce ad un sistema non omogeneo di N-1 equazioni indipendenti in N-1 incognite e che, quindi, ha soluzione unica.

Come già per le reti aperte, anche ora il problema è quello di calcolare le probabilità (stazionarie) di ciascuno stato n + (n1,n2,...,nN). Prima di fare ciò, è necessario definire, per ogni stazione i, cosa intendiamo adesso per valore atteso del numero di volte che ciascun programma passerà per la stazione i (che chiameremo visit count). Infatti, essendo la rete chiusa, occorrerà specificare convenzionalmente l'ingresso e l'uscita di un programma dal sistema. Denotiamo quindi Vi come il visit count del nodo i con Vi > 0. Da ciò possiamo enunciare che

∑i=1

N

Vi=1

Se vi(t) è il numero di volte che un programma passa nel nodo i nell'intervallo [0,t] allora

limt∞

vi

v j=

V i

V j

Un altro importante parametro associato a ciascuna stazione in una rete di code chiusa è la quantità di tempo che, mediamente, un programma trascorre in servizio in un centro i. Tale quantità viene indicata con ai ed è ovviamente legata a μj e al numero di volte che il centro i viene visitato. Una volta noti i valori delle Vj, è possibile calcolare il traffico offerto a ciascun nodo a meno di una costante moltiplicativa

a j=V j

μ j

Adesso siamo in grado di calcolare la probabilità che uno dei nodi sia occupato, con K che corrisponde al numero dei programmi nel sistema (nel nostro caso 20) e con μj = μ, con i = 1,2,3.

Se per esempio vogliamo calcolare la probabilità che il nodo 3 sia occupato denotiamo

a=V 1

μe b=

V 2

μ

mentreG=3a22abb2

sapendo poi cheP nodo3occupato=1−P nodo 3 libero

4

abbiamo

P nodo3 libero=a2abb2

G

da cui

P nodo3 occupato= 2a2ab3a22abb2

La soluzione del problema di analisi di una rete di code chiusa, nelle ipotesi viste, richiede dunque il calcolo della costante di normalizzazione G(N). Questa costante è data da

G= ∑n1...n N=K

∏i=1

N

a ini

Analisi matematica

Analizziamo ora alcuni parametri che poi verranno confrontati con i risultati delle simulazioni.

Stima del tempo di servizio ts

Da testo sappiamo che ci sono 20 programmi che girano costantemente nel sistema finché non esauriscono il loro numero di iterazioni. Un programma, dopo essere stato processato dalla CPU, ha il 12,5% di probabilità di richiedere un servizio NASTRO e il restante 87,5% di richiedere un servizio DISCO per poi tornare nuovamente alla CPU. Sapendo ciò possiamo stimare che su 20 programmi, 2,5 richiederanno un servizio NASTRO mentre 17,5 richiederanno un servizio DISCO. Inoltre è importante ricordare che il numero medio di iterazioni che riceve un programma è pari a 4. Quindi possiamo calcolare il tempo medio di servizio come:

● 20 ∙ (0,8 ∙ 4) + 2,5 ∙ (9 ∙ 3) = 131,5: tempo medio di permanenza di un programma passando per NASTRO;

● 20 ∙ (0,8 ∙ 4) + 17,5 ∙ (1,5 ∙ 3) = 142,75: tempo medio di permanenza di un programma passando per DISCO.

Allora

t s=131,5142,75

20=13,71

Stima del tempo di interarrivo

Il nostro sistema è rappresentato da una rete di Gordon-Newell perciò il tempo di interarrivo è stato calcolato singolarmente per ciascun nodo. Sapendo che N corrisponde a 20 programmi e K corrisponde a 3 nodi abbiamo calcolato la cardinalità dell'insieme degli stati S che rappresenta il modo in cui i programmi si distribuiscono nel sistema

[S ]=2022 =231

Poi siamo passati alla creazione della matrice di diramazione r

5

r ij=0 78

18

1 0 01 0 0

dove all'elemento rij corrisponde la probabilità che un programma ha nel raggiungere il nodo j dal nodo i. Dalla matrice r abbiamo risolto il sistema che ne deriva

{λ1= λ2λ3

λ2=78

λ1

λ3=18

λ1

La soluzione di questo sistema è indeterminata in quanto λ1 = λ1, infatti ammette infinite soluzioni. Vista l'impossibilità di procedere in questo senso è stato necessario calcolare i visit count.

Il visit count della CPU èV 1=1V 21V 3

Il visit count del DISCO èV 2=0,875V 10V 3

Il visit count del NASTRO èV 3=0,125V 10V 2

dove i coefficienti rappresentano le probabilità viste nella tabella di diramazione. Risolvendo il sistema che deriva da queste equazioni abbiamo trovato i seguenti valori

V 1=1V 2=0,875V 3=0,125

A questo punto abbiamo calcolato il throughput (traffico offerto) per ciascun nodo:

6

a1=V 1

μ1= 1

0,8=1,25

a2=V 2

μ2=0,875

1,5=0,583

a3=V 3

μ3=0,125

9=0,014

Questi sono i valori relativi al throughput di ciascun nodo (ad esempio per il nodo CPU il traffico offerto ad ogni istante di tempo è pari ad 1,25 programmi). Dopodiché abbiamo calcolato le probabilità che, ad un certo istante di tempo, un nodo sia libero oppure occupato. Qui a e b rappresentano i Vj/μj. Visto che a e b sono parametri associati al nodo di cui si vuol calcolare la probabilità, per semplicità prenderemo in esame solo il nodo CPU (per gli altri nodi il ragionamento è lo stesso).

a=0,8751,5

=0,583

b=0,1259

=0,014

Da questi valori ci calcoliamo il coefficiente di normalizzazione G

G=1.0170.0160,00019=1.037

Ora abbiamo tutti i valori che ci permettono di calcolare la probabilità

P CPU libera= 0.3390.0080.000191.037

=0.336

La probabilità che la CPU sia occupata è

1−P CPU libera =1−0.336=0.663

Progettazione

Vediamo in questa sezione i passi che abbiamo fatto per progettare il simulatore.

Meccanismo di avanzamento del tempo

Una delle più importanti considerazioni nella formulazione del modello è il metodo usato per l'avanzamento del tempo. Prima di tutto va fatta una distinzione fra tre concetti di tempo:

● Tempo reale: è quello proprio del sistema reale da simulare (in genere una variabile continua);

● Tempo simulato: è la rappresentazione del tempo reale nel modello. Il funzionamento del modello è rappresentato da una sequenza di cambiamenti di stato (eventi) discreti che si assume avvengano istantaneamente, senza consumo di tempo. Il tempo simulato è una variabile che assume valori discreti a istanti detti istanti critici. Questi istanti possono

7

coincidere oppure no con l'occorrenza di eventi. Nel primo caso si parla di avanzamento per eventi (next-event, o event-oriented), mentre nel secondo si parla di avanzamento per intervalli (fixed-time-step, o interval oriented). L’avanzamento del tempo simulato è registrato da una variabile interna il cui valore istantaneo è detto tempo di clock;

● Tempo di esecuzione: è il tempo consumato dall'elaboratore per l'esperimento di simulazione. Dipende dal numero e dalla complessità dei cambiamenti di stato che hanno luogo nel sistema e non dalla scala degli intervalli di tempo simulati. La scelta relativa all'avanzamento del tempo simulato è stata di tipo event-oriented e adottando questa “politica” il tempo di clock viene fatto avanzare ogni volta fino al tempo di occorrenza del prossimo evento in calendario. In tal modo si scavalcano tutti i periodi di tempo durante i quali non hanno luogo cambiamenti nel sistema.

Schema della simulazione

Effettuate tutte le scelte per la simulazione, si è stabilito lo schema generale, da cui poi è scaturito l'algoritmo. Come possiamo notare la simulazione è suddivisa nei seguenti blocchi

Inizializzazione

In questa parte vengono:

● caricati i 20 programmi;● costruite tutte le strutture utilizzate dal simulatore;● creati gli oggetti delle classi che permetteranno la generazione dei numeri random;● creati gli eventi iniziali che consentiranno lo START del sistema e l'evento FINE che

permetterà la terminazione della simulazione;● stabiliti i numeri random.

8

Clock e switch event

È in questo blocco che viene schedulato il tempo per eventi ovvero il current_time=ev.tempo dell'evento ev estratto, che poi verrà gestito in base al tipo dello stesso.

Terminazione

Questo avverrà nel momento in cui verrà estratto l'evento FINE generato in fase di inizializzazione. Da questo momento in poi, sarà possibile calcolare le statistiche della simulazione.

La gestione degli eventi

Vediamo ora come si è pensato di muoversi al verificarsi di un certo evento.

PROG_A

Notiamo in figura cosa avviene quando viene estratto un evento di tipo PROG_A. Possiamo vedere che, una volta riconosciuto l'evento e aggiornato il current_time, viene verificato il valore del flag cpu_libera; nel caso in cui sia false l'elemento viene inserito nella coda Q1 al livello A altrimenti se è true viene generato un nuovo evento uscita_cpu che rappresenta il completamento del programma.

9

PROG_B

Notiamo figura cosa avviene quando viene estratto un evento di tipo PROG_B. Possiamo vedere che, una volta riconosciuto l'evento e aggiornato il current_time, viene verificato il valore del flag cpu_libera; nel caso in cui sia false l'elemento viene inserito nella coda Q1 al livello B altrimenti se è true viene generato un nuovo evento uscita_cpu che rappresenta il completamento del programma.

10

USCITA_CPU

Notiamo in figura cosa avviene quando viene estratto un evento di tipo USCITA_CPU. Possiamo vedere che, una volta riconosciuto l'evento e aggiornato il current_time, viene settato il valore del flag cpu_libera a true in quanto a questo evento corrisponde il completamento del lavoro della CPU e viene preso in esame il numero di iterazioni del programma. Se ev.n_iter=0 il programma esce dal sistema attraverso la stampante e ne viene creato immediatamente uno nuovo; se invece ev.n_iter>0 viene decrementato di un'unità questo numero e viene creato un nuovo evento (uscita_d o uscita_n) a seconda della probabilità. Nel caso in cui il nodo di destinazione fosse occupato, il programma viene messo nella rispettiva coda (Q2 o Q3). Prima che la routine termini il programma esamina le code della CPU (ricordando che A ha priorità su B).

11

USCITA_D

Notiamo in figura cosa avviene quando viene estratto un evento di tipo USCITA_D. Possiamo vedere che, una volta riconosciuto l'evento e aggiornato il current_time, viene settato il valore del flag disco_libera a true in quanto a questo evento corrisponde il completamento del lavoro del DISCO e viene verificato il valore del flag cpu_libera; se è true viene generato un nuovo evento uscita_cpu mentre se è false il programma viene inserito nella coda Q1 al livello A o B a seconda della sua priorità. Prima che la routine termini il nodo esamina la propria coda Q2.

12

USCITA_N

Notiamo in figura cosa avviene quando viene estratto un evento di tipo USCITA_N. Possiamo vedere che, una volta riconosciuto l'evento e aggiornato il current_time, viene settato il valore del flag nastro_libera a true in quanto a questo evento corrisponde il completamento del lavoro del NASTRO e viene verificato il valore del flag cpu_libera; se è true viene generato un nuovo evento uscita_cpu mentre se è false il programma viene inserito nella coda Q1 al livello A o B a seconda della sua priorità. Prima che la routine termini il nodo esamina la propria coda Q3.

FINE

All'estrazione dell'evento FINE la simulazione volge al termine e da questo momento in poi sarà possibile iniziare ad effettuare i calcoli per le statistiche in base ai dati via via accumulati.

Il metodo delle prove ripetute

Il nostro scopo sarà quello di andare a determinare, assumendo N = 20 programmi, i valori di media e varianza dei lavori espletati per unità di tempo, al 90% del livello di confidenza. Innanzi tutto partiamo col dire che l'accumulo delle statistiche parte dopo 1000 secondi in quanto in questo lasso di tempo il sistema si deve ancora stabilizzare. È importante sottolineare che il tempo di stabilizzazione del simulatore può variare col seme per le imperfette proprietà aleatorie dei generatori pseudocasuali. Successivamente abbiamo diviso l'intervallo di tempo totale in 200 parti da 40 secondi ciascuna in modo da ottenere un numero significativo di programmi completati per unità di tempo. Ora andiamo a vedere come sarà lo schema che ci permetterà di effettuare più

13

esperimenti e da questi stimare i valori richiesti dal problema. Lo schema in questione è raffigurato in figura

Sia xij la i-esima osservazione fatta nel j-esimo esperimento, e sia nj il numero di osservazioni fatte nel j-esimo esperimento. Per ciascun esperimento si sceglierà una durata atta a garantire un nj

sufficientemente grande ma casuale e finito. Quindi avremo la serie di p campioni ciascuno formato da una serie di nj osservazioni autocorrelate. Essi sono

1 x11 x21 ⋯ xn1 1

2 x12 x22 ⋯ xn2 2

⋮j x1j x2j xn j j

⋮p x1p x2p xn p p

Per j = 1, 2, . . . , p, introduciamo le variabili

y j=∑i=1

N j

x ij

z j=∑i=1

N j

x ij2

14

Se il sistema ha raggiunto la stazionarietà ed i p esperimenti sono condotti con numeri random indipendenti, ciascuna delle tre serie

y1 y2 y j y p

z1 z2 z j z p

n1 n2 n j n p

può considerarsi formata da osservazioni di tipo i.i.d. (indipendenti e identicamente distribuite). Per quanto riguarda il livello di confidenza, esso ci servirà a determinare gli intervalli nei quali dovrà cadere il 90% dei nostri esperimenti. Vediamo ora come si fa a trovare il parametro uα/2 che ci permetterà di determinare gli intervalli interessati:

1−α=0,90 α=0,10 α2=0,05 1−α

2=0,95

Dalle tavole della distribuzione cumulativa si ricava per F( uα/2 ) = 0.95 il valore uα/2= 1.645, come possiamo vedere dalla tabella a pagina 188 del libro

A questo punto andiamo a calcolare il seguente valore

x= p−1 ∙∑j=1

p

x j

che consiste nella media verticale di tutti i nostri esperimenti; andiamo poi a calcolare la varianza

s2= 1n−1

∙∑i=1

n

x i−x 2

A questo punto siamo pronti a calcolare gli intervalli di confidenza

inferiore=x− snuα /2

superiore=x sn uα /2

dove s è la radice della varianza, n è il numero di prove effettuate e uα/2 è il valore proveniente dalla tabella vista in precedenza. Il 90% del livello di confidenza significa che sulle 100 prove da noi effettuate, 90 di queste hanno il valore medio interno a tale intervallo. Di seguito vengono mostrati due grafici relativi all'andamento nel tempo dei programmi completati.

15

In questo grafico viene mostrata l'area in cui il simulatore non è ancora stabile e perciò non viene considerata nelle statistiche.

In questo secondo grafico invece viene mostrato l'andamento dell'esperimento. Le tre linee mostrano rispettivamente l'intervallo inferiore (linea rossa), la media (linea nera) e l'intervallo superiore (linea verde). Come si può vedere, su 100 prove, all'incirca 90 valori cadono nell'intervallo mentre i restanti cadono all'esterno.

Convalida

Dopo la simulazione, e la successiva rilevazione dei dati, bisogna controllare se questi sono coerenti oppure no con il modello adottato. Bisogna far vedere infatti che, dopo un certo numero di esperimenti, i tempi che il simulatore mostra in output, siano effettivamente veritieri con i tempi calcolati matematicamente in precedenza.

Le statistiche

Confrontiamo ora i risultati calcolati su carta con quelli calcolati dal simulatore. Per fare ciò ci basta prendere in considerazione i risultati di un semplice esperimento con un tempo simulato elevato (8000 nel caso specifico). Di seguito viene mostrato un output del simulatore dove vengono

16

confrontati i valori teorici con quelli del simulatore.

Possiamo quindi notare che tutti i tempi, le probabilità e le percentuali calcolate matematicamente hanno un riscontro reale con il simulatore. I dati non sono effettivamente precisi ma hanno un margine di errore molto basso. Peraltro il modello risulta accettato.

17