Fondamenti di InformaticaAppunti dalle lezioni

Stefano Marrone

October 11, 2016

Questa dispensa ha lo scopo di fornire allo studente una trattazione sintetica degliargomenti teorici relativi all’insegnamento di Fondamenti di Informatica per il corsodi Laurea in Matematica presso il Dipartimento di Matematica e Fisica della SecondaUniversita di Napoli.

1 Introduzione

1.1 Studio dell’informatica

L’informatica riveste un ruolo essenziale nella vita di tutti i giorni diventando uno deglistrumenti principali nell’analisi e nella manipolazione del mondo contemporaneo. Lapreparazione di uno studente in materie scientifiche non puo, pertanto, prescinderedallo studio di tale materia.La nostra vita e ormai permeata in tutte le sue forme dalla presenza del calcolatore:

non esiste nessun aspetto in cui il calcolatore non abbia fatto sentire il suo peso cam-biando non solo il modo in cui i prodotti ed i servizi sono realizzati ed offerti, ma anchel’interazione tra l’uomo e gli oggetti stessi. Basti pensare ad ambiti quali il diverti-mento (cinema, videogiochi, intrattenimento, ...) oppure le comunicazioni (Internet,telefonia mobile e fissa, email, ...) fino ad arrivare a settori vitali come la medicina conla presenza di dispositivi come i pacemaker. Questo fenomeno e ormai cosı irreversibileche l’immagine stessa di alcuni prodotti e servizi e totalmente cambiata da quando ilcalcolatore e entrato in essi (es. l’auto).L’informatica ed i calcolatori sono ormai diventati essenziali anche nello studio delle

scienze. Intuitivamente le scienze di tipo sperimentale traggono grande giovamentodalla presenza del calcolatore: il computer e diventato ormai il centro di tutti i labora-tori poiche unisce alla possibilita di ricreare i piu disparati ambienti attraverso simu-lazioni software, la capacita di calcolare funzioni estremamente complesse con grandeprecisione ed affidabilita. Inoltre la sua grande velocita lo rende strumento indispens-abile nell’acquisizione, memorizzazione ed analisi di grandi quantita di dati, al centrodi ogni esperimento di scienza applicata (fisica sperimentale, biologia, ...). Oltre a talidiscipline, il calcolatore sta diventando uno strumento sempre piu importante anchenella matematica dato il suo utilizzo per risolvere problemi difficilmente risolvibili pervia analitica. Tali problemi includono non solo equazioni differenziali spesso risolti invia numerica ma anche teoremi dimostrati solo dopo l’avvento del calcolatore (comead esempio il teorema dei quattro colori).

1.2 Concetti fondamentali

Alla base dello studio dei calcolatori e della programmazione c’e il concetto di elabo-razione:

Y = F (X)

dove:

3

• X: insieme degli ingressi;

• Y: insieme delle uscite;

• F: funzione che esegue in modo automatico (non necessariamente in un solopasso) la corrispondenza tra gli ingressi e le uscite.

Il fulcro e costituito dalla caratteristica di automazione del calcolo della funzione:non basta che la funzione sia calcolabile, che un uomo possa fare la computazione nelmodo piu naturale possibile: e necessario che il calcolo possa essere effettuato senzal’ausilio dell’uomo affinche si possa parlare di calcolo automatico, ossia di argomenti diinteresse per l’informatica. Esempi di elaborazione sono il calcolo della primalita di unnumero intero, l’arrangiamento crescente vettore di numeri reali oppure l’elaborazionegrafica di disegni complessi.Una ulteriore importante caratteristica che esce fuori dalla definizione sopra descritta

e legata alla natura degli insiemi di ingresso e di uscita della funzione, ossia ad X edY. Siamo interessati ad insimi di natura discreta.Questa funzione viene in genere costruita attraverso la definizione di un algoritmo.

Si definisce algoritmo una sequenza finita di passi che risolve automaticamente unproblema. Esempi di algoritmi si possono trovare nella vita di tutti i giorni: conside-riamo come esempio quello di fare la spesa al supermercato (vedi Fig. 1.1).In che senso l’esempio ricalca la definizione data? Innanzitutto vediamo che :

• sequenza: le azioni vengono svolte una alla volta (non c’e parallelismo);

• finita: la lista della spesa e un qualcosa di finito ed inoltre il numero di azioni chesi svolgono e sempre finito (non si rischia di stare in eterno nel supermercato!);

• passi : ogni singolo passo (riempire il carrello, cercare sullo scaffale, ...) non im-plica per se il concetto di spesa: e solo nella sequenza (ossia nella concatenazioneintelligente di tali passi) che il problema viene risolto;

• automaticamente: una volta scritto e lanciato l’algoritmo, non c’e bisogno diintervento esterno; l’esecutore ha tutti gli elementi per poter risolvere il problema.

Un programma invece e l’implementazione di un algoritmo in un ben definitolinguaggio di programmazione.Chi esegue un algoritmo? Qualsiasi entita in grado di eseguire un algoritmo viene

detta esecutore di quell’algoritmo. Relativamente all’esempio precedente, il clientedel supermercato e l’esecutore dell’algoritmo della spesa. Tra i possibili esecutori di unalgoritmo annoveriamo il calcolatore e l’uomo. Quali sono le differenze fondamentalitra i due (quando ovviamente li vediamo come esecutori)? Il computer ha dalla suauna grande precisione e velocita che fa di lui l’esecutore ideale per algoritmi dove erichiesta una grande quantita di calcoli con requisiti di precisione molto spinti. D’altrocanto il piu grande difetto di un calcolatore e il fatto che non e cosciente di se e quindinon e cosciente delle cose che fa. Un calcolatore, anche il piu potente e sofisticato,potrebbe calcolare la primalita di migliaia di numeri interi senza sapere il significato dei

4

Leggi dalla lista

Cerca prodotto

Metti prodottonel carrello

è sullo scaffale?

lista vuota?

Cancella prodottodalla lista

Vai alla cassa

NO

SI

INIZIO

FINE

SINO

Figure 1.1: Esempio di algoritmo

test che sta eseguendo. Inoltre un calcolatore esegue solo cio per cui e programmato:non improvvisa e non inventa (se non nei limiti di quanto e programmato appunto!).Un concetto fondamentale e quello di sequenza statica e dinamica. La sequenza stat-

ica definisce le azioni da svolgere indipendentemente dai dati specifici che ritroviamoin ingresso: le azioni che un esecutore del nostro algortimo di esempio deve svolgerein modo del tutto indipendente da quanti (e quali) elementi sono presenti nella lista.Questa e una sequenza “astratta”, nel senso che non tiene conto di attivita che possonoripetersi (considerando ad esempio una lista con due o piu prodotti presenti sullo scaf-fale, l’azione Metti prodotto nel carrello verra eseguita piu volte). Di natura contrariae la sequenza dinamica che fotografa la sequenza esatta di azioni considerando anchele ripetizioni: ovviamente tale sequenza e dipendente dai dati in ingresso. Facciamoun esempio sulla base dell’algoritmo prima descritto:Caso 1; Lista=(petto di pollo, vino bianco, insalata):Sequenza dinamica

1. INIZIO;

2. leggi dalla lista (petto di pollo);

5

3. cerca prodotto;

4. (e sullo scaffale?: SI) metti prodotto nel carrello;

5. cancella prodotto dalla lista;

6. (lista vuota?: NO) leggi dalla lista (vino bianco);

7. cerca prodotto;

8. (e sullo scaffale?: SI) metti prodotto nel carrello;

9. cancella prodotto dalla lista;

10. (lista vuota?: NO) leggi dalla lista (insalata);

11. cerca prodotto;

12. (e sullo scaffale?: SI) metti prodotto nel carrello;

13. cancella prodotto dalla lista;

14. (lista vuota?: SI) Vai alla cassa;

15. FINE.

Alternativamente presentiamo un secondo esempio che, sulla base dello stesso algo-ritmo (e quindi della stessa sequenza statica di istruzioni) genera una lista dinamicadiversa.Caso 2: Lista=(caffe, filetto di tricheco)Sequenza dinamica

1. INIZIO;

2. leggi dalla lista (caffe);

3. cerca prodotto;

4. (e sullo scaffale?: SI) metti prodotto nel carrello;

5. cancella prodotto dalla lista;

6. (lista vuota?: NO) leggi dalla lista (filetto di tricheco);

7. cerca prodotto;

8. (e sullo scaffale?: NO) cancella prodotto dalla lista;

9. (lista vuota?: SI) Vai alla cassa;

10. FINE.

6

1.3 Informazione, dato e valore

Cosa e e da dove viene l’informazione? Cerchiamo di spiegare questo concetto a partireda esempi concreti. Analizziamo le seguenti frasi: π vale 3,14159...; oggi non piove;questo e il corso di Fondamenti di Informatica. Queste sono chiaramente frasi cheportano una qualche informazione: ma cosa hanno in comune? Scorgiamo quelli chesono i fattori unificatori: ognuna delle frasi d’esempio determina una risposta (val-ore) rispetto ad un insieme di risposte possibili (tipo) all’interno di un contesto benpreciso (attributo). L’informazione puo essere dunque formalizzata come una tripla di(attributo,tipo,valore). Rispetto ai nostri esempi:

• (il numero π, insieme dei numeri reali, 3,14159...);

• (stato delle precipitazioni odierne, {vero,falso}, falso);

• (nome del corso, insieme delle stringhe, “Fondamenti di Informatica”).

Il tipo di un’informazione e dunque l’insieme dei possibili valori che quell’informazionepuo assumere. Un attributo e invece il contesto dell’informazione e da il significatoall’informazione stessa: senza l’attributo, il valore non avrebbe significato; senza iltipo, non si capirebbe in quale intervallo varia il valore.Non dobbiamo adesso confondere il valore di un’informazione con la sua rappre-

sentazione. Questo concetto viene chiaramente definito dalla nozione di dato ossia ilmodo in cui un valore viene rappresentato. A seconda del tipo di rappresentazioneche utilizziamo possiamo notare in modo differente anche valori uguali. Considerandoun valore di tipo intero pari a tre, questo puo essere rappresentato sia dalla notazionedecimale “3” sia attraverso la notazione numerale romana “III”. Le funzioni che trasfor-mano un valore in dato e un dato in valore si chiamano rispettivamente funzioni dicodifica e decodifica.Tutti i concetti sopra esposti sono raffigurati in Fig. 1.2.Cerchiamo di formalizzare adesso i concetti di codifica e decodifica.Consideriamo un tipo T con i suoi valori:

T = {x1, . . . , xn}

e sia E un insieme di simboli:

E = {e1, . . . , ek}

Su tale insieme definiamo l’insieme E+ come l’insieme di tutte le stringhe di lunghezzaarbitraria ottenute concatenando i simboli di E. Ad esempio, considerandoE = {α, β},avremo che E+ = {α, β, αα, αβ, βα, ββ, ααα, ααβ, . . .}.Definiamo come codifica, la funzione C:

C : T −→ E+

dove si dice li lunghezza della codifica di xi il numero dei simboli contenuti in C(xi)ossia |C(xi)|. La funzione inversa a quella di codifica sui dice decodifica:

7

VALORE

DATO

INFORMAZIONE

TIPO ATTRIBUTO

CODIFICADECODIFICA

Figure 1.2: Informazione

D : E+ −→ T

tale che ∀xi ∈ T, D(C(xi)) = xi. Una delle prime classificazioni che e possibilefare in tale ambito e quella tra codifiche a lunghezza fissa e variabile. Una codificasi dice di lunghezza fissa se e solo se ∀xi ∈ T, |C(xi)| = m, ossia se tutte le stringhecodificanti i valori di T hanno la stessa lunghezza; in caso contrario si parla di codificaa lunghezza variabile. Ecco alcuni esempi: supposti T = {a, b, c, d} e E = {α, β}, unapossibile codifica a lunghezza fissa e quella per cui:

• C(a) = αα,

• C(b) = αβ,

• C(c) = βα,

• C(d) = ββ

mentre una possibile codifica a lunghezza variabile puo essere:

• C(a) = α,

• C(b) = βββ,

• C(c) = βα,

• C(d) = βαβ

Senza entrare troppo nel dettaglio di una trattazione formale, enucleiamo alcunecaratteristiche che distinguono le codifiche fisse e quelle variabili: quelle a lunghezzafissa sono di per certo piu facili da interpretare in quanto sappiamo a priori la lunghezzadelle stringhe di dato e quindi riusciamo facilmente a dire quando finisce la codifica di

8

un valore dell’insieme di partenza e quando comincia il successivo; tale semplicita fa sıche la codifica e decodifica a lunghezza fissa siano facilmente implementabili attraversocircuiti elettronici. Una codifica a lunghezza variabile invece puo essere piu efficientese consideriamo che i simboli non sono equiprobabili, ad esempio se nel nostro casoil valore a si presenta nella stragrande maggioranza dei casi, assegnando ad esso unastringa di lunghezza minore (anche minore di quella che avremmo nella codifica dilunghezza fissa), avremmo un risparmio nella lunghezza media delle stringhe di dato.Introduciamo adesso l’alfabeto binario B = {0, 1} avente due simboli detti BIT (BI-

nary digiT); esso e l’alfabeto di simboli per la codifica piu usato nella programmazionee nel mondo di calcolatori data la sua estrema semplicita e versatilita. I Bit sono ilfondamento dei calcolatori elettronici.

1.3.1 Sistemi di numerazione

In questa sezione parleremo piu nello specifico di sistemi di rappresentazione numericae dei concetti di base della numerazione.Cosı come la conosciamo noi, la numerazione si basa sul concetto di notazione po-

sizionale dove, a dispetto di un numero finito di simboli (le cifre di un alfabeto), epossibile rappresentare un insieme infinito di valori (numerici). Cio viene realizzatodando un valore diverso ad ogni simbolo a seconda della posizione che occupa all’internodella stringa di dato. Un esempio e dato dalla rappresentazione decimale del numerotrenta:

30 = 3 · 101 + 0 · 100

oppure centosettantadue e quindici centesimi che viene codificato secondo la no-tazione decimale in:

172, 15 = 1 · 102 + 7 · 101 + 2 · 100 + 1 · 10−1 + 5 · 10−2

Questo principio non si applica esclusivamente alla rappresentazione decimale: es-istono ulteriori sistemi di numerazione caratterizzati dalla loro base, ossia dal numerodi simboli che sono ivi contenuti. Abbiamo:

• sistema binario (base 2): {0, 1};

• sistema ottale (base 8): {0, 1, 2, 3, 4, 5, 6, 7};

• sistema decimale (base 10): {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

• sistema esadecimale (base 16): {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A,B,C,D,E, F}.

In generale quindi possiamo scrivere una famiglia di funzioni di decodifica (dal datoal valore) relativamente ad un sistema di rappresentazione posizionale in base b.Data una stringa xn−1xn−2 . . . x1x0, x−1x−2 . . . x−m+1x−m, tale che:

∀i ∈ {−m, . . . , n− 1} 0 ≤ xi ≤ b− 1

9

il valore di tale numerale e dato da:

∑n−1

i=−mxi · b

i

Applichiamo tale concetto dunque anche a sistemi di numerazione non decimale;

1001B = 1 · 23 + 0 · 22 + 0 · 21 + 1 · 20 = 9

oppure

F4H = 15 · 161 + 4 · 160 = 244

Per quanto riguarda invece la codifica evidenziamo una procedura di passaggio dauna notazione decimale a quella binaria. Questa procedura e descritta dall’algoritmoillustrato in Figura 1.3.

assegna il valore din a q

q/b

Prendi il resto e fanne lacifra meno significativa

il quoziente è nullo?

NO

INIZIO

FINE

SI

assegna a q ilquoziente di q/b

Figure 1.3: Algoritmo per la codifica nei sistemi di numerazione

Innanzitutto si prende il numero da codificare e si divide per la base: il resto di taledivisione diventa la cifra meno significativa dela stringa codificante il nostro numero.Successivamente si testa se il quoziente di tale divisione e nullo, in tal caso, l’algoritmo

10

si arresta, altrimenti si ripete l’operazione sul quoziente finche esso non si annulla.Facciamo l’esempio del numero 123: in pratica basta scrivere il numero 123 su unfoglio e tracciare accanto ad esso una linea verticale verso il basso che ci aiutera nelcalcolo. A questo punto dividiamo il numero 123 per 2 (ottenendo 61) e scriviamo ilresto (1) alla destra della riga. Il 61 ottenuto lo scriveremo invece sotto al numeroprecedente (123) e ripeteremo l’operazione fino a che il numero alla sinistra della riganon diventi 1. A questo punto basta leggere la serie di 1 e 0 ottenuta (dal basso versol’alto) per ottenere il corrispondente binario del nostro 123.Un caso particolare e dato dalla conversione tra le basi 16 e 2. Infatti essendo 16

una potenza di 2 (secondo l’esponente 4) e possibile passare da binario a esadecimale(e viceversa) in modo semplice. Data una stringa di n bit possiamo raggrupparli apartire dalla cifra meno significativa a quella piu significativa in gruppi da 4 e farcorrispondere ad ogni gruppo una cifra esadecimale: in altre parole volendo convertireil numero binario 101100101001 possiamo scrivere:

1011︸︷︷︸

B

0010︸︷︷︸

2

1001︸︷︷︸

9

oppure verso il sistema ottale:

101︸︷︷︸

5

100︸︷︷︸

4

101︸︷︷︸

5

001︸︷︷︸

1

Dualmente possibile passare dall’esadecimale (ottale) al binario decodificando ognicifra in quattro (tre) cifre binarie. Esempio:

F︸︷︷︸

1111

8︸︷︷︸

1000

C︸︷︷︸

1100

1︸︷︷︸

0001

1.4 Algebra di Boole (cenni)

Consideriamo l’insieme K={0,1} e siano su di esso definite le seguenti operazioni:

• + : K ×K → K OR

• · : K ×K → K AND

• · : K → K NOT

Tali funzioni sono definite cosı come illustrato nelle tabelle di verita espresse:Definiamo Algebra di Boole < K,+, ·, · >. In tale algebra si puo dimostrare che

valgono le seguenti proprieta:

∀x ∈ K

x+ 0 = x

x · 1 = x

x+ 1 = 1

11

Table 1.1: Tabella di verita della OR

A B A+B

0 0 00 1 11 0 11 1 1

Table 1.2: Tabella di verita della AND

A B A ·B0 0 00 1 01 0 01 1 1

x · 0 = 0x+ x = x

x · x = x

x+ x = 1x · x = 0x = x

Valgono inoltre le proprieta commutative ed associative di somma e prodotto nonchele proprieta distributive di somma e prodotto. Vale inoltre il teorema di De Morgan:

∀x, y ∈ K,x+ y = x · y e x · y = x+ y.

E’ ulteriormente dimostrabile che l’insiemde delle operazioni AND, NOT e OR costi-tuiscono un’insieme funzionalmente completo, ossia e possibile a partire da tali funzionicostruire una qualsivoglia operazione logica sull’insieme K in un qualsiasi numero divariabili.

1.5 Automi

Altro concetto cardine dell’informativa e quello di automa a stati finiti. Si definisceautoma a stati finiti la sestupla:

Table 1.3: Tabella di verita della NOT

A A

0 11 0

12

< Q, I,O, q0, δ, ε > dove:Q: insieme non nullo degli stati,I: insieme dei simboli (alfabeto) in ingresso,O: insieme dei simboli (alfabeto) in uscita,q0: stato iniziale dell’automa,δ: funzione di transizione di stato tale che δ : Q× I → Q,ε: funzione di uscita tale che ε : Q× I → O.

Esistono essenzialmente due tipi di automi a stati finiti: gli automi di Mealy e quellidi Moore. La differenza sostanziale tra questi due tipi di automi risiede nel fatto che,in sostanza, negli automi di Moore l’uscita e funzione del solo stato e non degli ingressi.Formalmente:AMoore < Q, I,O, q0, δ, ε > dove:

Q: insieme non nullo degli stati,I: insieme dei simboli (alfabeto) in ingresso,O: insieme dei simboli (alfabeto) in uscita,q0: stato iniziale dell’automa,δ: funzione di transizione di stato tale che δ : Q× I → Q,ε: funzione di uscita tale che ε : Q → O.

Di particolare interesse risultano le notazioni attraverso le quali specificare le duefunzioni (δ e ε): ve ne sono due principali, quella grafica e quella tabellare del tuttoequivalenti nella loro capacita espressiva. Al fine di essere chiaro nella trattazione sifara l’esempio del riconoscitore di sequenze binarie 1101.

1.5.1 Notazione grafica

Il riconoscitore di sequenze 1101 e descritto dalle Fig. 1.4 e Fig. 1.5. In tali figuresono descritti gli stati come cerchi e gli archi come le possibili transizioni da uno statoall’altro. Lo stato iniziale e notato come un doppio cerchio concentrico. La Fig. 1.4descrive l’automa di Mealy dove la funzione di transizione δ e espressa attraverso unarco orientato (dal vecchio al nuovo stato) mentre la funzione di uscita ε e espressanell’etichetta dell’arco (ingresso/uscita).L’automa di Moore in Fig. 1.5 invece esprime l’uscita direttamente nello stato

(nome/uscita).

1.5.2 Notazione tabellare

Accanto alle notazioni grafiche sopra illustrate esistono notazioni tabellare meno in-tuitive ma piu chiare da schematizzare e quindi di piu facile implementazione in uncalcolatore. Per quanto riguarda la macchina di Mealy otteniamo che la Tab. 1.4 rapp-resenta la macchina sopra illustrata mentre le Tab. 1.5 e Tab. 1.6 illustrano la analogadi Moore.

13

Table 1.4: Versione tabellare della macchina di Mealy in Fig.1.4

0 1S0 S0/0 S1/0S1 S0/0 S2/0S2 S3/0 S2/0S3 S0/0 S0/1

Table 1.5: Versione tabellare (funzione δ) della macchina di Moore in Fig.1.5

0 1S0 S0 S1S1 S0 S2S2 S2 S3S3 S0 S4S4 S0 S1

Table 1.6: Versione tabellare (funzione ε) della macchina di Moore in Fig.1.5

S0 0S1 0S2 0S3 0S4 1

14

S0 S1

S2S3

0/0

1/0

0/0

0/0

1/0

1/0

0/0

1/1

Figure 1.4: Automa di Mealy del riconoscitore di sequenze 1101

1.6 Macchina di Turing

Nel 1936 Alan Turing formulo un modello matematico di una macchina poi rivelatasidi fondamentale importanza per il calcolo automatico tutto: la macchina di Turing.Essenzialmente immaginiamo di avere un nastro di lunghezza infinita, diviso in celle,ognuna delle quali in grado di memorizzare due simboli (0 ed 1 per comodita) oppurela loro assenza (simbolo di blank β). Sia inoltre presente una testina in grado dilegger/scrivere su una cella del nastro e di muoversi lungo esso (sia verso destra cheverso sinistra) (vedi Fig. 1.6).Piu formalmente una macchina di Turing e costituita dalla seguente: < S,F, s0, A, δ, β >

dove:S: insieme non nullo degli stati,F : insieme degli stati finali della macchina (S ⊃ F ),s0: stato iniziale della macchina (s0 ∈ S),A: alfabeto di ingresso/uscita della macchina (anche detto insieme dei simboli delnastro),δ: funzione di transizione della macchina tale che δ : S ×A → S ×A× {−1, 0, 1}1

β: simbolo di blank.Si voglia fare l’esempio di una macchina di Turing che controlli se il numero di uno

su un nastro e pari o dispari e che scriva, all’occorrenza del primo blank, 1 se talevalore e dispari, zero altrimenti. La Tab. 1.7 illustra tale esempio.

1-1,0,1 sono tre simboli convenzionali che stanno per muovi di uno step a destra, stai fermo e muovidi una posizione a sinistra

15

S0/0 S1/0

S2/0

S3/0

0

1

0

0 1

1

0

1S4/1

0 1

Figure 1.5: Automa di Moore del riconoscitore di sequenze 1101

Table 1.7: Esempio di macchina di Turing

0 1 β

S0 S0/0/1 S1/1/1 SSTOP/0/0S1 S1/0/1 S0/1/1 SSTOP/1/0

SSTOP - - -

Si S0 lo stato iniziale e SSTOP quello finale.Si riportano adesso alcuni risultati teorici molto importanti. Tutto cio che e com-

putabile puo essere realizzato attraverso una macchina di Turing. Tutto cio che nonpuo essere realizzato attraverso una macchina di Turing non e calcolabile, ossia non eesprimibile mediante una funzione automatica.

1.7 Modello di Von Neumann

Introduciamo in questa sezione il modello teorico di esecutore che sta alla base deimoderni calcolatori elettronici.In Fig. 1.7 sono raffigurati i componenti di questo modello. Tali elementi rappre-

sentano le funzionalita di un esecutore nel modello di Von Neumann e sono collegatiattraverso due tipologie di flussi. Il primo e il flusso dei dati (tratto grigio continuo)che rappresenta il passaggio di dati da un elemento all’altro del modello; il secondo

16

Figure 1.6: Schema di principio della macchina di Turing

UNITA’ DI INGRESSO UNITA’ DI

USCITA

MEMORIA

UNITA’ DI CONTROLLO

UNITA’ LOGICO-ARITMETICA

PROGRAMMI

DATI

Figure 1.7: Modello di Von Neumann

e relativo al flusso di controllo (linea nera tratteggiata) che indica invece che unelemento controlla un altro, ossia determina cosa il secondo componente deve fare. Cisono cinque elementi nel modello: l’unita di ingresso, responsabile dell’acquisizione deidati di ingresso dal mondo esterno, la memoria, responsabile della memorizzazione deidati in attesa di una loro elaborazione, l’unita logico-aritmetica, in grado di svolgere leoperazioni logiche ed aritmetiche necessarie alla trasformazione dei dati memorizzati;l’unita di uscita, in grado di interfacciarsi con le periferiche di uscita del nostro calcola-tore e l’unita di controllo avente la responsabilita di controllare l’intero procedimentodi elaborazione.Una delle caratteristiche piu importanti del modello di Von Neumann e che sia i

programmi che i dati sono memorizzati in modo indifferenziato nella stessa memoriae solo lo stato dell’elaborazione determina se si sta leggendo dalla memoria un dato oun’istruzione del programma.Per comprendere fino in fondo il modello di Von Neumann occorre introdurre il mod-

ello comportamentale del processore, anche detto ciclo del processore (vedi Fig.1.8).All’accensione del calcolatore il processore avvia la fase di bootstrap (avvio). Quandoil processore si e avviato, ad ogni ciclo vengono svolte le seguenti attivita:

• fetch: il processore preleva una nuova istruzione dalla memoria;

17

Fetch

Decode

Operand Assembly

Execute

BOOTSTRAP

Figure 1.8: Ciclo del processore

• decode: l’istruzione viene interpretata: a questo punto si comprende cosa si deveeseguire in questo ciclo;

• operand assembly: vengono prelevati dalla memoria (o da registri) i dati chedevono essere computati (ad esempio gli addendi di un’addizione);

• execute: l’operazione prelevata, decodifica e preparata viene effettivamente ese-guita.

18

2 Il calcolatore

In questo capitolo analizzeremo i principali elementi dell’architettura di un calcola-tore al fine di comprendere le motivazioni di diverse caratteristiche dei linguaggi diprogrammazione.

2.1 Architettura di un calcolatore

Nella Sezione 1.7 abbiamo visto il modello funzionale di un calcolatore attraverso ilmodello di Von Neumann.

CPUPeriferica 1

BUS

MemoriaPeriferica N

Figure 2.1: Architettura di un calcolatore

La Fig. 2.1 rappresenta un modello di riferimento di architettura di un calcolatore;in essa sono evidenziati i seguenti componenti:

• CPU: cervello del calcolatore contenente la circuiteria che presiede a tutte leattivita decisionali del sistema;

• Memoria: elemento che si occupa della memorizzazione temporanea dei dati1;

• Periferiche: sistemi di collegamento tra la parte interna del calcolatore e leunita periferiche di Ingresso/Uscita (I/O). Tra esse annoveriamo: lettore floppy,lettore CD-DVD, dischi rigidi, periferiche USB, tastiera, mouse, schede di rete,schermo, ...;

• Bus: sistema di comunicazione che collega su un unico canale condiviso tutte leunita sopra descritte.

1Si dice che la memoria e volatile in quanto, allo spegnimento del computer, perde i dati che avevain esso memorizzati. Esistono altri tipi di memorie non volatili (memorie secondarie): hard disks,drives usb, ...

19

Analizziamo nel dettaglio alcuni di questi elementi.

2.1.1 La memoria

Possiamo considerare la memoria come una grande matrice di celle ognuna capace dimemorizzare un bit. Le celle sono organizzate in righe e colonne come raffigurato inFig.2.2: ad esse e possibile accedere in lettura o scrittura.

K

2^N

Figure 2.2: Organizzazione della memoria

Vi sono dunque K celle di memoria ogni riga: questo numero viene detto parallelismodella memoria e rappresenta il numero di bit presenti in ogni riga. Ci sono invece unnumero di righe pari a una potenza di due, nella fattispecie 2N . La minima quantitadi memoria accessibile in memoria (sia in lettura che in scrittura) e la parola (ossia lariga); per potervi accedere viene fornito quello che si definisce indirizzo di memoria.L’indirizzo della parola i-esima non e altro dunque che la codifica binaria del numeroi-12. Ad esempio supponendo di avere 8 parole di memoria, esse saranno indirizzatedai seguenti: 000, 001, 010, 011, 100, 101, 110 e 111.

2.1.2 La CPU

La CPU (Central Processing Unit) rappresenta il centro delle attivita del calcolatoree presiede e a tutte le attivita di controllo nonche a quelle di elaborazione e trasfor-mazione dei dati. Rispetto al modello di Von Neumann (vedi Figura1.7) il processoreimplementa le funzionalita di unita di controllo e di unita logico-aritmetico.

2Per convenzione la prima parola di memoria e 0, quindi l’indirizzo della i-esima riga corrisponde al

20

PC

IR

MAR

MDR

R1

RN

ALU

Figure 2.3: Architettura di un processore

Gli elementi evidenti nel modello di Fig.2.3 (ad esclusione dell’ALU) sono registri.Un registro e una piccola porzione di memoria all’interno del processore che il pro-cessore stesso utilizza sia per operazioni di carattere generale (ossia per i dati) con iregistri R1...RN , sia per operazioni di tipo dedicato. Tra questi annoveriamo:

• MAR: Memory Address Register, contiene l’indirizzo di memoria del dato che sivuole leggere/scrivere dalla memoria;

• MDR: Memory Data Register, contiene il dato da leggere/scrivere in memoria;

• IR: Instruction Register, contiene l’istruzione di linguaggio macchina che il pro-cessore sta correntemente eseguendo;

• PC : Program Counter, contiene l’indirizzo della prossima istruzione che dovraessere eseguita dal processore.

In fine all’interno del processore e presente la ALU (Unita Logico-Artimetico) cos-tituita dai circuiti elettronici capaci di svolgere le operazioni aritmetiche (somma,differenza, prodotto, ...) e quelle logiche (negazione, and, or, ...). Tutti questi compo-nenti sono collegati ad un Bus interno alla CPU attraverso cui i dati possono passareda una parte all’altra della CPU e verso l’esterno.

2.1.3 Il bus

Il bus collega dunque la memoria, il processore e le altre periferiche del calcolatore.Esso e strutturato in tre parti distinte ognuna della quali specifica per alcuni tipi diinformazioni:

numero i-1

21

• dati : ivi viaggiano i dati che vengono scambiati tra gli elementi collegati al bus;

• indirizzi : vi viaggiano gli indirizzi di memoria che il processore richiede (letturae/o scrittura);

• controllo: linee speciali che servono per comunicare i tipi di operazioni richiesteagli elementi dal processore (ad esempio se un indirizzo di memoria deve essereletto o scritto dalla memoria).

2.1.4 Accesso alla memoria

Riassumiamo i concetti sopra espressi attraverso l’esempio di funzionamento della let-tura e della scrittura di un dato da processore a memoria.

Lettura dalla memoria

Memoria

MARMDR

MARMDR

CPU

BUS CONTROLLO

BUS INDIRIZZI

BUS DATI

(1)

(2)

(3)(4)

(5)(6)(7)

(9)

(8)

(10)

Figure 2.4: Lettura di dati dalla memoria

Facendo riferimento alla Fig.2.4, illustriamo il processo di lettura di una dato dallamemoria. Innanzitutto quando il processore stabilisce di voler leggere un dato dallamemoria, scrive nel suo registro MAR l’indirizzo (ad N bit) relativo a quale parola sivuole leggere (1), tale valore viene trasferito sul bus all’analogo registro presente neicircuiti di memoria (2). Successivamente il processore dice (sul bus dei controlli) divoler leggere il dato (3) e tale comando arriva alla memoria (4). A questo punto icircuiti della memoria leggono il MAR (5) ed estraggono tra le parole quella relativaall’indirizzo selezionato copiando il contenuto di tale parola (k bits) nel registro MDR(6) ed attivano un segnale di risposta verso il processore appena l’operazione si e

22

conclusa (7), comando che, arrivato al processore (8), permette il trasferimento deldato dalla memoria al processore sul bus dei dati (9) e (10).

Scrittura in memoria

Memoria

MARMDR

MARMDR

CPU

BUS CONTROLLO

BUS INDIRIZZI

BUS DATI

(1)(2)

(3)

(4)

(5)

(6)(7)

(9)

(8)

(10)

Figure 2.5: Scrittura di dati in memoria

Un processo del tutto analogo avviene per la scrittura di un dato in memoria (vediFig.2.5). In questo contesto, il processore stabilisce quale dato deve essere scrittoe dove; innanzitutto dunque scrive nel suo registro MAR l’indirizzo relativo a qualeparola si vuole scrivere (1), tale valore viene trasferito sul bus all’analogo registropresente nei circuiti di memoria (2). Ugualmente si procede per il dato da scrivere (3)e (4). Successivamente il processore dice (sul bus dei controlli) di voler scrivere il dato(5) e tale comando arriva alla memoria (6). A questo punto i circuiti della memorialeggono il MAR (7) ed il MDR (8) e scrivono il contenuto di quest’ultimo nella parolaindividuata dal primo. Alla fine di questa operazione, la memoria attiva un comandodi risposta verso il processore (9) e (10).

2.2 Memoria cache

Le prestazioni dei calcolatori basati sul modello di Von Neumann sono fortementeinfluenzate dagli accessi alla memoria; infatti, dato che ad ogni ciclo ci possono esserediversi accessi alla memoria (sia in lettura con le istruzioni ed i dati, sia in scrittura con idati), occorre velocizzare tale attivita al fine di migliorare globalmente le prestazioni delcalcolatore. Migliorare le prestazioni di una memoria non e pero semplicissimo: infatti

23

le memorie sono caratterizzate da costi, velocita e capacita. Ebbene non possiamopensare di avere contemporaneamente memoria poco costose, molto veloci e moltocapienti. In genere se scegliamo due di queste caratteristiche (ad esempio grandivelocita e bassi costi), dobbiamo accontentarci di memorie poco capienti.Occorre enucleare adesso due regole empiriche nate dall’osservazione statistica dei

programmi di maggior uso:

• principio di localita spaziale: afferma che se ad un certo istante di tempo sifa la richiesta di un dato dalla memoria e molto probabile che negli istanti ditempo successivi si fara la richiesta di un dato “vicino” (in termini di indirizzidi memoria) a quello richiesto in precedenza;

• principio di localita temporale: afferma che se ad un certo istante di tempo si fala richiesta di un dato dalla memoria e molto probabile che negli istanti di temposuccessivi si rifara la richiesta dello stesso dato.

Diciamo memoria cache quella memoria che viene frapposta tra il processore e lamemoria principale e che conserva una copia dei dati. La caratteristica principaledella memoria cache e una maggiore velocita (altrimenti sarebbe inutile averla!). Loschema architetturale del calcolatore con la presenza della cache diventa dunque quelladescritto in Fig.2.6.

CPU

Periferica 1

BUS

MemoriaPeriferica N

CACHE

Figure 2.6: Schema di memoria cache

Vediamo che la cache viene posta tra il processore ed il bus. Il suo funzionamento eil seguente: inizialmente la cache e vuota e quindi quando il processore chiede il datoalla cache, quest’ultima lo richiede alla memoria. A questo punto il trasferimento didati dalla memoria alla cache non interessa solo la parola che il processore ha richiestoma un blocco di dati relativo a quella locazione di memoria ed a quelle adiacenti.Appena il dato viene letto, la cache non viene svuotata ma il blocco trasferito dallamemoria resta nella cache. Quando invece il processore richiede un dato alla cache edesso si trova gia in cache, allora la cache non passa per la memoria. In questo caso sidice che si e avuto un cache hit: diciamo PHIT la probabilita di avere un tale evento.Questi due accorgimenti permettono un notevole miglioramento delle prestazioni:

24

• innanzitutto il fatto che si trasferisce un blocco di dati dalla memoria alla cacheinvece della singola parola permette di sfruttare a pieno il principio della localitaspaziale in quanto se un dato adiacente viene chiesto c’e un’alta probabilita cheesso si trovi gia in cache;

• in secondo luogo, il fatto che si conserva il dato in cache anche dopo che lo si eusato, permette di sfruttare il principio della localita temporale in quanto se ildato in questione viene richiesto gia si trova in cache.

Quando viene rimosso un blocco dalla cache? Quando ne viene chiesto un altro nonpresente e non c’e piu spazio libero in cache: in questo caso si prende uno dei blocchi“vecchi” e lo si elimina dalla cache (scrivendo in memoria quanto era stato scrittoprecedentemente in cache).Quali sono dunque le prestazione di un sistema in presenza della memoria cache?

Supponendo TM il tempo di accesso di un dato dalla memoria principale e TC il tempodi accesso alla memoria cache abbiamo che ogni accesso in assenza di cache e dunqueTM , mentre in presenza di cache abbiamo:

TTOT = PHIT · TC + (1 − PHIT ) · TM

Considerando che PHIT ≃ 0.8 e che TM ≃ 50 · TC possiamo capire quanto buono eil guadagno che si ottiene in presenza di cache.Le limitazioni della cache sono legate soprattutto alle sue dimensioni. Infatti essendo

una memoria molto veloce, e necessario, al fine di contenere i costi, di limitarne ledimensioni; infatti se le cache fossero veloci e grandi il loro costo renderebbe impossibile(dal punto di vista economico) la loro esistenza.

25

3 La programmazione dei calcolatori

3.1 Linguaggio macchina

Nel capitolo precedente abbiamo illustrato quelli che sono gli elementi fondamentalidell’architettura di un calcolatore elettronico. Il grande potere di un calcolatore e cheil limite delle cose che puo fare e dettato esclusivamente da come e stato programmato,dai programmi che su di esso vengono eseguiti. Qui evidenzieremo gli aspetti legatialla programmazione dei calcolatori parlando innanzitutto dei linguaggi in cui i taliprogrammi sono espressi.Cosa esprime una istruzione all’interno del calcolatore? Abbiamo visto nel modello

di Von Neumann diverse tipologie di controllo che l’unita di controllo stessa effettuasulle diverse unita del processore. Questa diversita riflettono un’analoga diversita trale possibili categorie di istruzioni:

• ingresso/uscita: istruzioni legate al trasferimento di dati tra la memoria ed unaperiferica;

• memorizzazione: a questa categoria appartengono le istruzioni legate alla letturae alla scrittura di dati da e verso la memoria da parte del processore (ossiaistruzioni di trasferimento dati tra registri interni al processore e la memoria);

• calcolo logico/aritmetico: istruzioni che permettono di utilizzare l’ALU nell’esecuzionedi operazioni quali la somma, la differenza o altro tra registri o tra un registroed una locazione di memoria.

A queste si aggiunge una categoria legata alla gestione del flusso di controllo stesso(istruzioni effettuate su altre istruzioni ossia legate all’individuazione della prossimaistruzione all’interno di un programma).Tipicamente la forma di un’istruzione e la seguente:

CodOp Op1 Op2

dove CodOp e detto codice operativo e rappresenta la tipologia di istruzione (esempioLeggi da memoria), Op1 rappresenta il primo operando (l’indirizzo della parola dimemoria da accedere) e Op2 il secondo operando (esempio il registro in cui conservateil dato letto dalla memoria)1.Continuiamo considerando che la macchina di Von Neumann tratta le istruzioni

come dati e che in memoria sono conservate in modo indifferenziato sia istruzioni che

1Nota che non tutte le istruzione hanno due operandi, alcune ne hanno solo una (ad esempio lanegazione di un valore) mentre alcune possono non avere affatto operandi.

26

dati. Detto questo risulta naturale pensare che anche per quanto riguarda le istruzioniesista una codifica verso il codice binario: tale codice viene detto linguaggio macchina.Questo e infatti l’unico metodo attraverso cui il calcolatore puo interpretare ed eseguirele istruzioni.Il linguaggio macchina presenta pero due grandissime limitazioni che ne rendono

l’uso (dal punto di vista della programmazione) pressocche limitato a pochi casi spo-radici. Il primo di questi problemi e quello della complessita: essendo il linguaggiomacchina di un livello di astrazione estremamente basso, specificare anche il piu sem-plice programma richiede diverse righe di codice. Pertanto scrivere programmi comp-lessi risulta pressocche impossibile. La seconda limitazione riguarda la portabilita ossiala possibilita di scrivere un programma una sola volta e di eseguirlo su quanti piu tipidi macchine possibile. Il linguaggio macchina e, per sua stessa definizione, dipendentefortemente dalla macchina e pertanto un programma scritto in tale linguaggio non puoessere eseguito (portato) su un computer di tipo diverso (che monti cioe un processorediverso).Per ovviare parzialmente a tali inconvenienti si sono diffusi velocemente i linguaggi

assemblativi (assembler) che sostituiscono ai codici binari condici simbolici: ad esempiol’istruzione di esempio mentre se scritta in linguaggio macchina apparirebbe come:

000101 110100010 1101001

in assembler potrebbe apparire come:

MOV E A R0

ossia sposta il dato dalla locazione A al registro R0. Un programma scritto inassembler deve poi esser trasformato in linguaggio macchina attraverso un appositoprogramma (l’assemblatore). L’assembler per quanto migliori la leggibilita di un pro-gramma non risolve totalmente i problemi di portabilita e complessita primi descritti.

3.2 Linguaggi di alto livello

Divenne presto ben chiaro sin dai primi tempi dell’informatica, che il basso livello diastrazione del linguaggio macchina (ed anche di quello assemblativo) era un fattoremolto limitante allo sviluppo di programmi complessi e corretti. Sorse subito l’esigenzadi avere a disposizione strumenti linguistici (linguaggi di programmazione e meccanismiper l’esecuzione dei programmi) che consentissero ai programmatori di elevare il livellodi astrazione dei loro programmi permettendo di non pensare piu a dettagli specificidella macchina considerata. Inoltre il fatto che ogni calcolatore avesse il suo linguaggiomacchina (e di conseguenza il suo linguaggio assemblativo) limitava la portabilita diprogrammi ossia la capacita si spostare un programma da una macchina all’altra senzadover riscrivere tutto. A tal fine sono stati introdotti fin dai primi anni dell’informaticai linguaggi di terza generazione (3GL) anche detti linguaggi di alto livello.A questa categoria appartengono diversi linguaggi quasi tutti basati su parole-chiave

riferite alla lingua inglese. Cio facilita molto sia la stesura che la rilettura di un pro-gramma, ma non mette il computer in condizione di capire direttamente cosa vogliamo

27

in quanto un calcolatore, sulla base di quanto gia detto alla Sez.3.1, comprende esclu-sivamente il linguaggio macchina. Sono dunque necessari degli strumenti in grado dicolmare il divario tra i linguaggi 3GL ed il linguaggio macchina.Generalmente si tende a suddividere i linguaggi ad alto livello in 3 categorie2:

• imperativi: sono composti da una sequenza di istruzioni in grado di modificare ilcontenuto della memoria del computer o di determinare le modalita di esecuzionedi altre istruzioni. Tipici linguaggi imperativi sono: Pascal, Basic, Fortran, C,...;

• dichiarativi: il programma e considerato come un’affermazione (teorema) dadimostrare e la dimostrazione e la sua esecuzione. Tipici linguaggi dichiarativisono il Prolog e il SQL3;

• funzionali: calcolano il valore di una funzione (molto piu vicini alla formaliz-zazione matematica rispetto a tutti gli altri). Tipici linguaggi funzionali sonoML e Lisp.

3.2.1 Compilatori ed interpreti

Esistono due tecniche per colmare il divario tra i linguaggi 3GL e quello macchina:la compilazione e l’interpretazione. Alla base di entrambi c’e il concetto che leespressioni del linguaggio di alto livello (piu sintetiche e quindi in minor numero)debbano essere tradotte in una piu lunga lista di istruzioni elementari. Il programma3GL che si vuole tradurre viene detto programma sorgente (o codice sorgente) mentre ilprogramma in linguaggio macchina risultato della compilazione/interpretazione vienedetto programma target (codice oggetto o eseguibile). Questo secondo programma vienepoi eseguito sulla macchina al fine di ottenerne l’elaborazione (si dice che viene lanciatala sua esecuzione).Nella compilazione, la traduzione e l’esecuzione sono due fasi distinte dello sviluppo

del programma. Innanzitutto viene scritto dal programmatore il programma sorgente.Successivamente viene eseguito un programma esterno (il compilatore) che esegue lacompilazione e genera tutto il codice oggetto relativo all’intero programma sorgente.Fatto questo l’eseguibile puo essere poi successivamente lanciato sulla macchina senzadover essere necessariamente compilato.Diversamente lavora l’interpretazione. In questo processo le fasi di traduzione ed

esecuzione sono contemporanee: in altre parole l’interprete scandisce il programmasorgente riga per riga e ad ogni istruzione di tale programma, provvede una traduzionesimultanea e l’esecuzione di tali righe di codice oggetto.Questi due schemi di ragionamento diversi presentano ovviamente delle differenze.

Per quanto riguarda la compilazione, questo processo permette di individuare gli er-rori presenti nel programma prima che esso venga eseguito permettendo che alcunicontrolli di correttezza del programma possano essere eseguiti prima dell’esecuzione.

2Esistono in realta tante altre categorie di linguaggi di programmazione relative alle piu diversecaratteristiche.

3All’interno di tale categoria distinguiamo la sottocategoria dei linguaggi logici tra cui il Prolog.

28

La compilazione inoltre traduce il programma nella sua interezza permettendo quindidi ottimizzare il codice oggetto ossia di renderlo (a parita di funzionalita svolte) piuveloce oppure occupante meno spazio. Durante l’esecuzione inoltre si ha gia a dispo-sizione tutte le istruzioni che verranno eseguite facendo sı dunque che il codice prodottosia molto piu veloce dell’analogo interpretato. D’altro canto l’interpretazione permetteuno sviluppo piu interattivo del programma in quanto le istruzioni vengono tradotte edeseguite una alla volta. Gli interpreti, inoltre, mancando di tutta una serie di controlliche il compilatore fa e mancando del tutto della fase di ottimizzazione del codice, hannouna struttura piu semplice (a parita del linguaggio) rispetto agli analoghi compilatori.Una cosa che accomuna interpreti e compilatori e la dipendenza dall’architettura.

Abbiamo visto nella sezione precedente che il linguaggio macchina e caratteristico diun’architettura e quindi i programmi scritti in linguaggio macchina (e possiamo direanche assembler) funzionano solo sull’architettura per la quale sono stati sviluppatirisultati dunque scarsamente portabili. I linguaggi di alto livello invece si astraggonodall’architettura considerata: infatti quando si scrive un programma in C, ad esempio,e lo si compila su una certa macchina, si produce un codice che funzionera su tuttele macchine di quel tipo. Per poter portare il codice su un’altra architettura, saranecessario cambiare compilatore scegliendone uno che riesca a tradurre il linguaggioC nel linguaggio macchina della nuova architettura mantenendo inalterato il codicesorgente. Analoghe considerazioni valgono per gli interpreti.Occorre pero precisare che e possibile l’esistenza, per un qualsiasi linguaggio di

programmazione, sia di compilatori che di interpreti. Non solo, esistono modalitaibride che prevedono l’uso combinato (unendo i vantaggi di entrambi) sia della fasecompilativa che di quella interpretativa. In questi casi la compilazione avviene sempreprima dell’interpretazione ed ha come linguaggio target non il linguaggio macchina mauna sorta di linguaggio intermedio (come avviene ad esempio nel bytecode di Java).

29

4 Sistemi operativi

I calcolatori elettronici, nella loro complessita, vengono schematizzati, studiati e pro-gettati secondo modelli che riescono a dominare quanto piu possibile tale complessita.Uno dei modelli piu utilizzati in tale ambito descrive il calcolatore attraverso l’astrazionedei livelli. In tale modello, raffigurato in Fig 4.1, possiamo vedere diversi livelli ognunodei quali si poggia su altri. Verso il livello superiore, ogni livello fornisce dei servizimentre allo stesso momento richiede servizi al livello inferiore.

Sw Applicativo

Sw di base

Hardware

ServiziEsportati

Servizirichiesti

Figure 4.1: Modello hw/sw a livelli

Nel nostro modello in particolare vediamo tre livelli:

1. hardware: il livello piu basso, e quello della macchina fisica cosı come visto nelCap. 2: es. server dual-core piuttosto che netbook di fascia bassa;

2. sw di base: su tale livello si poggia quello hardware ed ha lo scopo di forniretutta quella serie di programmi in grado di far funzionare la macchina hardwaree di fornire inoltre un’interfaccia unica che nasconda i dettagli della macchinastessa: es. Windows, Linux, Mac;

3. sw applicativo: software in grado di fornire funzionalita ben specifiche e creatiper scopi particolari: es. word processor, multimedia player, browsers. Gliapplicativi sono realizzati attraverso la stesura di un apposito programma scrittocon le tecniche ed i linguaggi evidenziati in Cap. 3.

30

4.1 Funzionalita

Un sistema operativo e un sistema complesso in se dato il suo duplice compito di gestireda una parte hardware sempre piu complessi e dall’altra di fornire funzionalita semprepiu sofisticate ed interfacce utente intuitive e gradevoli. A tal fine si preferisce iniziarea descrivere i sistemi operativi attraverso un ulteriore modello a livelli (raffigurato intermini concentrici) che prende anche il nome di schema a cipolla (vedi Fig. 4.2).

Shell ed Interpreti

File System

Gestione periferiche

Gestione Memoria

Kernel

Hardware

Figure 4.2: Modello a cipolla

Rispetto al modello a livelli come visto in Fig. 4.1, si deve considerare qui lo stratopiu interno come quello piu basso. Partendo dall’interno vediamo che il sistema oper-ativo si appoggia sull’hardware (e sui servizi direttamente offerti da questo). Il primolivello del sistema operativo vero e proprio e il nucleo (kernel) che offre funzionalitadi gestione dei processi e di gestione della risorsa piu importante della macchina, os-sia il processore. Successivamente troviamo quelle routine che si occupano di gestirela memoria ossia di stabilire quanta memoria ed a chi viene stata allocata (il ge-

store della memoria). Successivamente incontriamo il livello di gestione delle

periferiche che si occupa di interfacciarsi con le periferiche del calcolatore al fine diavere delle interfacce e dei modi di comunicazione con tali elementi unici. Ancora piusu troviamo il livello del file system, ossia di gestione dei file e delle informazionipersistenti del sistema. All’ultimo livello troviamo l’interprete dei comandi, os-sia l’insieme di software deputato all’interfacciamento verso l’utente e la gestione deicomandi da questi ricevuti.

31

4.1.1 Il kernel

Alla base della gestione di un sistema operativo c’e il concetto di processo. Abbiamovisto nei Capitoli 1 e 3 che i programmi sono costituiti dal codice oggetto generatodalla compilazione del codice sorgente e che rappresentano quindi concetti statici. Di-versamente, il processo e l’entita utilizzata dal sistema operativo per rappresentareuna specifica esecuzione di un programma (concetto dunque dinamico): oltre al codicesorgente (il programma), un processo contiene anche i dati relativi alla specifica es-ecuzione nonche tutte le informazioni che ne definiscono lo stato, come il contenutodella memoria indirizzata, i file e le periferiche in uso, etc...In un sistema operativo moderno, ci sono piu processi attivi contemporaneamente.

Uno dei compiti piu importanti di tali sistemi e appunto quello di gestire opportuna-mente tutti questi processi rendendoli attivi uno per volta. I primi sistemi operativierano monoprocesso ossia riuscivano a gestire solo un processo alla volta: i vari processiprocedevano in batch (lotti) ossia l’i-esimo non poteva iniziare prima che l’(i-1)-esimoavesse finito (vedi Fig. 4.3): questo prende il nome di schedulazione FIFO.

processo A

processo B

processo C

tempo

Figure 4.3: Schedulazione FIFO

Questo modo di schedulare, ossia di pianificare nel tempo l’esecuzione di tali processi,ha come inconveniente il permettere che alcuni processi monopolizzino il processoreper troppo tempo. Infatti come si evince dalla figura il processo C, che e il piu piccolo,deve aspettare che tutti gli altri finiscano. Obiettivo diverso ha invece la secondamodalita di schedulazione (Round Robin) che permette, attraverso la suddivisione deltempo in quanti (time slice) di eseguire un po di processo per volta, facendo insomma“un po di processore per uno” tra i processi permettendo dunque a quelli piu velocidi non dover aspettare troppo tempo prima di poter essere eseguito (vedi Fig. 4.4).Questa si chiama schedulazione Round-Robin ed ha come vantaggio tangibile quello

32

di una diminuzione media della durata del tempo di esecuzione dei processi.

processo A

processo B

processo C

tempo

Figure 4.4: Schedulazione Round-Robin

Un processo vive diverse fasi: richiede dati alle periferiche e quindi “perde tempo” inattesa di dati che vengono dall’esterno. In un sistema monoprocesso in questa perditadi tempo viene subita anche dal processore in quanto, in questo tempo, il processocontinua a detenere la CPU.Facendo dunque riferimento alla Fig. 4.5, quando viene attivato un processo si trova

in modalita READY dove viene inserito in una coda di processi pronti per essereeseguiti e che aspettano solo il processore. Quando il processore non ha nulla da fare,viene scelto un processo dalla coda (in genere quello che ci sta da piu tempo) e lo sifa diventare RUNNING ossia viene allocato a lui il processore e gli viene permessodi essere eseguito. Quando il tempo a disposizione del processo finisce (si esaurisce ilquanto di tempo precedentemente descritto) l’esecuzione del processo viene interrottaed il processo viene riaccodato ai READY . Quando invece, dallo stato di RUNNING

un processo fa una richiesta di I/O (ad esempio richiede dei dati ad una periferica)esso viene messo della coda dei WAIT , dalla quale si esce solo in caso di avvenutotrasferimento dati di I/O. A questo punto il processo viene rimesso nella coda deiREADY .

4.1.2 Gestione della memoria

Il gestore della memoria e il componente del sistema operativo dedito alla gestione dellamemoria disponibile sul computer. Esso si occupa di allocare, deallocare e gestire lamemoria che viene assegnata agli applicativi e allo stesso sistema operativo. Tutti imoderni sistemi operativi sono dotati di memoria virtuale. Il gestore della memoriasi preoccupa di decidere quali blocchi di memoria sono poco utilizzati dal sistema e

33

READY

RUNNING

WAIT

Nascita

Primo incoda

Tempo scaduto

Richiestaperiferica

Evento esterno

Fine

Figure 4.5: Modalita di un esecuzione di un processo

possono essere spostati sull’unita a disco senza deprimere eccessivamente le prestazionidel sistema.

4.1.3 File Systems

Un file system e la parte del Sistema Operativo attraverso cui i file sono immagazzinatie organizzati su un dispositivo di archiviazione, come un disco rigido o un CD-ROM.L’astrazione piu comunemente usata e quella di albero. Quasi tutti i file system mod-erni gestiscono le risorse memorizzate attraverso una struttura ad albero. In questoalbero si scorgono due elementi strutturali: i file e le directory. I primi sono collezionidi dati (sequenze) che vengono memorizzati in modo permanente sulla memoria sec-ondaria, le directory invece sono cartelle che possono contenere directory o altri file1.Uno schema di esempio e raffigurato in Fig. 4.6.Un concetto fondamentale nei file system e quello dei path. Un path e un percorso,

ossia una sequenza di directory che identifica una risorsa (file o directory). Un pathpu essere relativo (se fa riferimento alla directory corrente) o assoluto (se parte da unadirectory di riferimento). Ad esempio a partire dalla Fig. 4.7: il path relativo di F4 daD3 e D2-D1-F4 mentre il suo path assoluto e F4 (si assume come riferimento il nodoradice dell’albero).Il sistema operativo gestisce in questo contesto la struttura nonche fornisce all’esterno

(utente) primitive per la manipolazione del file system stesso: operazioni di creazione,cancellazione, spostamento di file e directory.

1Possiamo dire che mentre le directory sono i nodi non terminali dell’albero del file system, i file nesono i nodi terminali.

34

DIR

DIR

DIR

FIle

FIle

FIle FIleDIR

Figure 4.6: File system

D1

D2

D3

F4

F1

F2 F3D4

Figure 4.7: Paths

35