Insegnamento di AbilitàInformatiche

A.A. 2007/8

Lezione2Prof.ssa Raffaella Folgieri

folgieri@dico.unimi.itfolgieri@mtcube.com

Link addestrativo interattivo: http://www.caspur.it/formazione/mais/

BASI E NUMERI• In un elaboratore ogni comando, parola, lettera

o cifra sono composti da una stringa(sequenza) di 0 e 1 (ovvero un bit = BinaryDigit)

• Siamo abituati ad usare il sistema decimale perché impariamo a contare usando le nostre 10 dita, ma il sistema binario è più semplice e piùveloce: ho solo due simboli da imparare e da usare!

• Anche se il sistema decimale ci sembra ovvio, non si è contato sempre così!

Curiosità

• Babilonesi, Cinesi e Maya già furono capaci di rappresentarequalsiasi numero con una limitata quantità di cifre di base

• Non si è contato sempre allo stesso modo, il sistemanotazionale o di calcolo che abbiamo è il risultato di una lungaevoluzione.

• Ancora oggi ci sono popoli che non contano come noi, ovveronon concepiscono numeri astratti e sono perplessi di fronte ad operazioni del tipo 2+2=4.I Boscimani non vanno oltre il cinque.I Pigmei in Africa, i Botocudos in Brasile, gli Aranda in Australia computano 1, 2, massimo 3 e oltre il 3 parlano in termini di "molti" ("tanti quanto i capelli in testa"). Nell'apprendimento i bimbi di queste tribù hanno comunque un'evoluzione la cui rapidità è simile a quella dei nostri bambini.

• Per approfondimenti: http://it.wikipedia.org/wiki/Sistema_numerico

1 centinaio 1 decina

1 unità

• Il sistema decimale adotta una notazione posizionale: i numeri hanno un “peso” diverso a seconda della posizione che occupano

• Es. 111, ovvero 111

• Il numero di cifre usate da un sistema numerico si dice BASE. Nel nostro caso usiamo 10 cifre (da 0 a 9), per cui la base è 10.

• Ogni cifra, a seconda della sua posizione, indica quanti multipli della base dobbiamo utilizzare (si usano le potenze):

Es. 111 = 1x102+1x101+1x100 = 1x100 + 1x10 + 1x1Es. 215 = 2x102+1x101+5x100 = 2x100 + 1x10 + 5x1

• La posizione è data dall’esponente. La più bassa (la posizione zero) è quella più a destra.

• RICORDATE: qualunque numero, elevato a zero, vale 1!!

IL SISTEMA DECIMALE

“1” ha un diverso valore a seconda della posizione che occupa!

IL SISTEMA BINARIOe la conversione binario decimale

• Abbiamo detto che l’elaboratore usa gruppi (stringhe) di bit8 bit = 1 byte

• Per quanto riguarda i numeri, ogni posizione rappresenta una potenza di 2, a partire da quelle più basse, poste a destra:

27 26 25 24 23 22 21 20 (ricordate che qualunque numero0 0 0 1 0 1 0 1 elevato a 0 ha come risultato 1)

• Per calcolare il valore decimale del numero binario scritto sopra, si procede così (partendo da destra):

1x20 + 0x21 + 1x22 + 0x23 + 1x24 + 0x25 + 0x26 + 0x27 =1x1 + 0x2 + 1x4 + 0x8 + 1x16 + 0x32 + 0x64 + 0x128 =

ovvero 21 in base decimale

IL SISTEMA BINARIOe la conversione decimale binario

• Un modo semplice per ricavare il corrispondente numero binario a partire dal decimale è quello detto “per divisioni successive”. Consideriamo il numero 21

• Si effettuano divisioni successive per 2 ed ogni volta il resto della divisione fornisce il numero binario (0 o 1) da porre nella cifra binaria, partendo da destra:21:2=10 resto 1 110:2=5 resto 0 015:2=2 resto 1 1012:2=1 resto 0 01011:2=0 resto 1 10101

• Ora si “riempie” di zeri a sinistra, per completare gli 8 bit.• Otteniamo così 00010101 che è il numero 21 in binario• Se si desidera, si indica la base in basso a destra• Es. 000101012 e 2110

ALTRE NOTAZIONI• Altre notazioni utilizzate in Informatica sono la notazione

ottale (cifre da 0 a 8) e quella esadecimale (da 0 a 9, piùle lettere da A a F).

• Esiste una regola generale per effettuare un cambiamento di base:– Scelta una base B, ogni numero è rappresentato da una sequenza

di simboli di valore compreso fra 0 e B-1– A ogni posizione corrisponde una potenza della base, crescente da

ds a sin– Valore del numero = somma dei prodotti di ogni cifra per la potenza

associata alla sua posizione

Es. aN-1aN-2...a1a0=aN-1*BN-1+aN-2*BN-2+...+a1*B1+a0*B0

CONVERSIONE binario ottale• Consideriamo un numero binario. Per ottenere la codifica

ottale si procede così:– Si considerano gruppi di 3 bit (a partire dalla cifra meno

significativa, cioé quella più a destra, di posizione 0).– Si sostituisce al valore rappresentato da questi bit la

cifra ottale equivalente• Es. 1100011001011011

1/100/011/001/011/011 = 1 4 3 1 3 3Ovvero, partndo da ds, si ha:011:8=1 resto 3.... Fino a 100:8=12 resto 4 e 1:8=0 resto 1. Come vedete, i resti forniscono il numero ottale, secondo la regola generale vista nella slide precedente

CONVERSIONE binario esadecimale• Analogamente, se consideriamo un numero binario, la codifica in

esadecimale segue lo stesso procedimento, ma stavolta divideremole cifre in gruppi di 4, prima di procedere a dividere per 16:

• Es. 11000110010110111100/0110/0101/1011 = C 6 5 B

Ovvero, partendo da ds, si ha:1011:16=63 resto 3, che corrisponde alla B (abbiamo 1 nella cifra piùsignificativa del gruppo di 4, quindi utilizziamo le lettere)....In pratica, la lettera «A» nelle unità corrisponde al numero 10 e la lettera «F» nelle unità corrisponde al numero 15 Fino a 1100:16=68 resto 12 che corrisponde alla lettera C. Come vedete, i resti forniscono il numero ottale, secondo la regola generale vista nella slide precedente

Perché?• Perché per la conversione binario ottale e

binario esadecimale, suddividiamo i bit in gruppi, rispettivamente, di 3 e di 4?

• Vale la regola: con k bit posso rappresentare 2k caratteri distinti, dunque:

• Con 3 bit posso rappresentare 23=8 caratteri distinti

• Con 4 bit posso rappresentare 24=16 caratteri distinti

• Guarda caso, proprio i valori delle due basi!

Conversione decimale ottale

• Es. 12710 =1778

Infatti: 127:8 = 15 resto 715:8 = 1 resto 71:8 = 0 resto 1

• Se facciamo la verifica:7*80 + 7*81 + 1*82 = 7 + 56 + 64 = 127

Conversione decimaleesadecimale

• Es. 12710 =7E16

Infatti: 127:16 = 7 resto 157:16 = 0 resto 7

• Se facciamo la verifica:15*160 + 7*161 = 15 + 112 = 127(ricordiamo che E vale 15)

Riassumendo...• Ci interessa comprendere cosa significa

“trattare l’informazione” e il perché della rapidità di risposta di un elaboratore

• ...e capire lo schema generale di rappresentazione dell’informazione e i modi di “ragionamento” di un elaboratore

• Dobbiamo dunque avere dimestichezza con:• Differenza tra digitale e analogico• Conversioni tra basi (decimale, binaria,

ottale, esadecimale)

OPERAZIONI BINARIE

• Vedremo l’addizione e la sottrazione (riflettete sul fatto che tutte le operazioni di base si riconducono alla somma algebrica)

• Basta ricordare che:0 + 0 = 0 con riporto 00 + 1 = 1 con riporto 01 + 0 = 1 con riporto 01 + 1 = 0 con riporto 1

LA SOMMA

Secondo le regole di riportoEs. 00010101 + verifica:

00001101 = 00010101 = 21---------------- 00001101 = 13 00100010 00100010 = 34

infatti 21 + 13 = 34

0 + 0 = 0 con riporto 00 + 1 = 1 con riporto 01 + 0 = 1 con riporto 01 + 1 = 0 con riporto 1

LA SOTTRAZIONE

Secondo le regole di fiancoEs. 00010101 - verifica:

00001101 = 00010101 = 21---------------- 00001101 = 13 00001000 00001000 = 8

infatti 21 - 13 = 8

0 - 0 = 0 0 - 1 = 1 con prestito1 - 0 = 11 - 1 = 0

Valgono le regole seguentiMOLTIPLICAZIONE:

DIVISIONE: segue le stesse regole della divisione decimaleEs. 1100 10

10 110=1010== 0

Provate da soli ad eseguire:000101000 * 00000010000101000 / 00000010 e verificate il risultato, convertendo in sistema binario

MOLTIPLICAZIONE E DIVISIONE

0 * 0 = 0 0 * 1 = 01 * 0 = 01 * 1 = 1

RAPPRESENTAZIONE DEI TESTI

• Si utilizzano 52 lettere alfabetiche (maiuscole e minuscole)

• 10 cifre (0..9)• Segni di interpunzione (,.;:!”?’^\ /…)• Operatori matematici + - + [ -+ / > < ecc…• Caratteri tipici (à è ì ò ù …• Altri simboli @ # | £ $ % &• In totale sono circa 220 caratteri. Abbiamo visto

che per i numeri si utilizzano 8 bit. Lo stesso vale per gli altri simboli.

I SIMBOLI ALFABETICI

• Sono anch’essi codificati da un codice binario (8 bit)

• Vi sono codifiche standard. Le più famose:– ASCII (American Standard Code for Information Interchange)

8 bit per carattere. Codifica 256 caratteri

– ANSI (American National Standard Institute)

– UNICODE 16 bit per ogni carattere, rappresenta ASCII e caratteri di qualsiasi lingua (può rappresentare 34168 caratteri)

• Altre codifiche proprietarie:

• MSWindows 16 bit per carattere (simile a unicode)

TAVOLA ASCII

ESEMPIO DI CODIFICA ASCII

01110000 01101111 01101100

• Dividendo la stringa in gruppi di byte si risale alla parola (con riferimento alla tavola):

01110000 01101111 01101100P O I

ALGEBRA DI BOOLE• Abbiamo detto che un elaboratore opera confronti semplici.

Introduciamo l’algebra booleana.

• Si deve a Boole (matematico inglese, XIX sec.)

• Si basa su 2 stati:– ON – acceso

– OFF – spento

• Le variabili booleane possono assumere solo 2 valori:

0 e 1

• Con le variabili booleane si costruiscono funzioni booleane che possono assumere solo 2 stati:

TRUE e FALSE

TABELLE DI VERITA’ E OPERATORI

• Gli operatori logici che esprimono le relazioni tra le variabili sono:

• NOT, AND, OR, XOR• Esistono poi NAND e NOR (operatori

universali) che permettono di esprimere qualsiasi altra delle precedenti espressioni, utilizzando un solo tipo di operatori

• Ogni funzione booleana ha una sua tabella della verità

Tabelle di verità: NOT

Tabelle di verità: AND

Tabelle di verità: OR

Tabelle di verità: XOR

Tabelle di verità: NAND

Tabelle di verità: NOR

Algebra booleana ed elaboratore

• Abbiamo detto che l’elaboratore rappresenta l’informazione in modo digitale (intervalli finiti)…

• … e che traduce molte informazioni in binario(informazioni analogiche, numeri, lettere, comandi…)

• Inoltre svolge operazioni utilizzando l’aritmetica binaria

• L’elaboratore “ragiona” mediante confronti semplici, poiché quel che comprende con facilità è la differenza tra 0 e 1 (vero-falso, “passa corrente” – “non passa corrente” nei circuiti)

• Dunque i confronti vengono effettuati grazie all’algebra booleana

Archittettura di un elaboratoreIl modello di Von Neumann - 1

• 1946 – John Von Neumann• Modello teorico ancora valido e molto

utilizzato (eccezione macchine ad elaborazione parallela)

• Schematizza in modo omogeneo situazioni diverse

Il modello di Von Neumann - 2

Concettualmente si identificano i componenti:• Memoria (per procedura, dati iniziali, risultati

intermedi e finali)• Funzione aritmetica (operazioni, non solo

aritmetiche, sui dati)• Ingresso/Uscita (dispositivi per

ricevere/inviare dati)• Controllo (per eseguire passi procedure

coordinando flusso dati tra i preceenticomponenti)È la filosofia alla base dei calcolatori digitali

Il modello di Von Neumann - 3Si suole schematizzare così l’architettura di Von Neumann:• Quattro blocchi comunicanti tra loro mediante il bus• Bus: canale di scambio informazioni (e segnali di

controllo)

CPU Memoriaprincipale

Memoriasecondaria

DispositiviINPUT

OUTPUT

BUS

Il modello di Von Neumann - 4Corrispondentemente ai concetti visti, si ha:• CPU (Central Processing Unit)• Memorie• Dispositivi I/O• Bus: nel modello di Von Neumann è costituito da

3 bus distinti:– Bus dei dati: i dati viaggiano da e verso la

CPU– Bus degli indirizzi: dati solo da CPU– Bus dei segnali di controllo: dati solo da

CPU

Il bus• Scambio informazioni• Fisicamente: conduttori elettrici (linee)• Tre gruppi:

– Linee dati– Linee indirizzi (identificano unità da usare durante

trasferimento)– Linee di controllo (segnali temporizzazione,

read/write, tipo dati)

• Si possono avere conflitti• Dispositivi attivi: master (padroni)• Dispositivi passivi: slave (schiavi)

Ricordiamo: FASI DI SVILUPPO DI UN SOFTWARE

• Analisi (si raccolgono le esigenze cui deve rispondere il programma)

• Rappresentazione simbolica (di quanto evidenziato in fase di analisi)

• Programmazione (traduzione in linguaggio).• Test (si verificano tutte le funzionalità• Messa in esercizio (il programma va all’utente

finale)

Programma• Insieme di istruzioni che il computer

deve eseguire, connesse ad un compito specifico

• Tipologia programmi:• Interattivo: intervento operatore

(necessario o voluto). Es. browser• Batch: nessun intervento

Algoritmi• Nascita espressione simbolica di un problema (Al

Waritzsmi, matematico arabo)• Flusso risolutivo = algoritmo• Varie rappresentazioni simboliche:• Schema a blocchi (diagramma di flusso)• Top-down, down-top• UML• Def algoritmo: sequenza finita, non ambigua, di

passi eseguibili e ripetibili un numero finito di volte per portare a soluzione un dato problema (generale)

Proprietà di un algoritmo• finitezza: istruzioni in numero finito eseguite un

numero finito di volte• non ambiguità: ogni istruzione deterministica e

univocamente interpretabile• realizzabilità: istruzione deve essere realmente

eseguibile da parte del processore• Gli algoritmi si distinguono in:• Numerici (problemi di tipo matematico)• Non numerici (tutti gli altri algoritmi)

Flusso esecuzione istruzioniPuò procedere in tre modi diversi:• Sequenziale, istruzioni eseguite una dopo l’altra• Iterativo (ciclico), una sequenza di istruzioni è

ripetuta un certo numero di volte• Condizionale, istruzione o gruppo di istruzioni

eseguite solo se si verifica condizione

• La sequenza di istruzioni eseguibili su un elaboratore è detta modulo eseguibile oapplicativo

Evoluzione programmazione

• GOTO: istruzioni di salto (spaghetti code)

• GOSUB: programmazione sequenziale strutturata, da cui:

• Funzioni e procedure• Programmazione ad eventi• Programmazione ad oggetti

(modularità e riusabilità)

I processi

• Il termine processo fa riferimento all’esecuzione di un programma

• Il processo è un oggetto dinamico che evolve nel tempo; il programma èstatico

• Def. Processo: insieme di tutti i valori contenuti nella memoria centrale e neri registri della CPU durante l’esecuzione di un programma

Terminazione e stati di un processo3 motivi:• Termina il quanto a sua disposizione• Gli occorre una risorsa già in uso• Termina regolarmenteGestore dei processi (nucleo): responsabile dell’esecuzione

dei programmi (quasi contemporanea) da parte dell’unità di elaborazione.

Stati di un processo:• Attivato: appena stato creato• Pronto: ha tutte le risorse per procedere, è nella ready list• Esecuzione: è assegnato al processore (avviato)• Attesa (blocco): risorsa che chiede già impegnata• Terminato: è concluso e rilascia risorse

SchedulingLo scheduling (schedulatore) decide quale tra i processi

presenti nella ready list mandare in esecuzione.3 tipi di processo schedulatore:• Scheduling di basso livello (dispatcher): metodo

con cui il nucleo fa passare un processo (in ready list) da pronto a esecuzione

• Scheduling di livello intermedio: si inoltrano al nucleo solo quelli che assicurano il miglior utilizzo di tutte le risorse (con analisi statistiche)

• Scheduling di alto livello (scheduler): ordina ed estrae dalla lista i processi tenendo presente le prioritàe le caratteristiche statistiche

Lo stalloSi ha stallo quando un processo è nella situazione di

attesa perché non è possibile assegnargli risorse.Condizioni che si verificano quando c’è stallo:• Le risorse sono ad accesso esclusivo• Esiste la condizione di attesa• Non utilizzato prerilascio (togliere una risorsa ad un

processo dal momento in cui comincia ad utilizzarla)• Vi è lista circolare di processi in attesa di risorse in

uso ad altri• Def. Risorsa: qualsiasi elemento sw o hw condiviso

dai processi, necessario alla loro creazione ed al loro avanzamento.

Prevenzione e soluzione stalloUn metodo per evitare stallo è prevenirlo (es.

numerazione risorse e accesso in ordine crescente).

Riconoscere possibilità di stallo prima di assegnare le risorse: si perde molto tempo

• Si usa round robin:• Basata sul time sharing (suddivisione di tempo)• A ogni processo è assegnato quanto di tempo

(time slice), al termine del quale:– Processo passa da esecuzione a pronto– Viene messo in fondo alla lista e rilasciate risorse– Viene preso primo processo della lista

Schema round robin

Evoluzione round robinRound robin semplice da elementare e garantisce che

ogni processo prima o poi avrà processore assegnato• Svantaggio: tutti i processi hanno uguale priorità: si

può assegnare più tempo a processi con maggior priorità.

• Round robin penalizza processi che richiedono piùrisorse (appena ne ricevono una vengono messi in coda in attesa di un’altra)

Evoluzione due liste a priorità diversa:• Una per processi che terminano perché finito il quanto

di tempo• Una per quelli in attesa di risorse

Schema evoluzione round robin

• Si possono avere anche più liste.• Effetto globale: far terminare prima i processi che

richiedono minor tempo di esecuzione.

Gestore di risorseSvolge due compiti fondamentali:• Verifica dell’accesso alle risorse• Schedula richieste da inoltrare al controllore

che fisicamente manipola la risorsa (spesso su essa stessa)

Il gestore delle risorse comunica con il controllore della risorsa richiamando specifici driver.

Driver• E’ un programma o una raccolta di

sottoprogrammi, scritto in linguaggio di basso livello, che accede direttamente ai registri del controllore della risorsa

• A volte i driver sono inclusi nelle operazioni svolte dai gestori delle risorse.

La tecnica del buffer

• Primo problema di gestione I/O: notevole differenza di velocità delle varie risorse

• Spesso utilizzato metodo del buffer: interporre tra il processo che la utilizza e la risorsa un’area di memoria (buffer) della stessa tecnologia della CPU, nella quale il processore effettua le sue operazioni

Lo spooling• Evoluzione del buffer che risolve il problema

dell’occupazione di memoria (del buffer)• Simultaneous Peripherical Operation On Line• Il buffer in memoria centrale è sostituito da un file in

memoria secondaria. Es. stampa:• Il gestore scrive l’insieme dei caratteri da stampare, poi un

processo interno (spooler), se il file è completo, preleva ordinatamente i file (con politica Short Job First) e ne esegue la stampa. Al termine il file viene cancellato

• Scrittura su memoria massa più lenta, ma consente maggiore disponibilità di memoria e possibilità di ripetere stampa se cade il sistema.

• Tecnica adottata per tutte le periferiche molto lente