CORSO DI
INFORMATICA GENERALE
Daniele Gunetti
E-Mail:
Indirizzo:
[email protected]
Dipartimento di Informatica,
corso Svizzera 185, Torino
Tel. Ufficio: 011 - 6706768 / 6706711
PROGRAMMA DEL CORSO
 Rappresentazione
delle Informazioni
 Architettura del computer (hardware)
 Il software (Sist. Operativi, I programmi)
 Reti di Calcolatori (Reti Locali, Internet)
LABORATORIO DEL CORSO
Uso del computer (windows95/98)
 Word
 PowerPoint
 Excel
 Access
 Internet

ESAME:
• Scritto + con prova pratica
RAPPRESENTAZIONE
DELLE INFORMAZIONI
Idea di fondo: Usare
presenza/assenza di carica elettrica
passaggio/non passaggio di corrente/luce

BInary digiT (cifra binaria): il BIT
Usiamo cioe’ una rappresentazione binaria
(a due valori) dell’informazione
INFORMAZIONI COMPLESSE
Con 1 bit rappresentiamo solo 2 diverse
informazioni:
si/no - on/off - 0/1
Mettendo insieme piu’ bit possiamo
rappresentare piu’ informazioni:
00 - 01 - 10 - 11
INFORMAZIONI COMPLESSE
In generale, con N bit, ognuno dei quali puo’
assumere 2 valori, possiamo rappresentare
2N informazioni diverse
viceversa:
Per rappresentare M informazioni dobbiamo
usare N bit, in modo che: 2N >= M
ESEMPIO:
Per rappresentare 57 informazioni diverse
dobbiamo usare gruppi di almeno 6 bit.
Infatti:
26 = 64 > 57
Cioe’ un gruppo di 6 bit puo’ assumere 64
configurazioni diverse:
000000 / 000001 / 000010 …/ 111110 / 111111
IL BYTE:
In informatica ha assunto particolare
importanza il concetto di:
byte = 8 bit = 28 = 256 inf. diverse
Il byte e’ usato come unita’ di misura per
indicare le dimensioni della memoria, la
velocita’ di trasmissione, la potenza di un
elaboratore
Usando sequenze di byte (e quindi di bit)
si possono rappresentare caratteri, numeri
immagini, suoni.
LA CODIFICA DEI CARATTERI
E’ necessario convenire un codice per
rappresentare i caratteri.
Il codice ASCII (American Standard Code
for Interchange Code) usa i primi 7 bit di
ogni byte:
27 = 128 caratteri diversi
Sufficienti per l’alfabeto anglosassone
ALTRI CODICI DI CODIFICA
 ASCII
ESTESO
– Usa anche il primo bit di ogni byte
– 256 caratteri diversi
– non e’ standard (cambia con la lingua usata)
 UNICODE
– standard proposto a 16 bit (65.536 caratteri)
 EBCDIC
– altro codice a 8 bit della IBM (quasi in disuso)
LA CODIFICA DEI NUMERI
Le cifre 0..9 rappresentate in Ascii sono
simboli o caratteri NON quantita’ numeriche
Non possiamo usarle per indicare quantita’
e per le operazioni aritmetiche. (Anche nella
vita di tutti giorni usiamo i numeri come
simboli e non come quantita’: i n. telefonici)
E poi i carat. Ascii occupano troppo spazio
IL SISTEMA DECIMALE
 10
cifre di base: 0, 1, 2, …, 9
 Notazione posizionale: la posizione di
una cifra in un numero indica il suo peso
in potenze di 10. I pesi sono:
– unita’
– decine
– centinaia
– migliaia
– …
= 100 = 1
= 101 = 10
= 102 = 100
= 103 = 1000
..
..
..
(posiz. 0-esima)
(posiz. 1-esima)
(posiz. 2-esima)
(posiz. 3-esima)
..
..
...
ES. DI NUMERO RAPPR. IN
NOTAZIONE DECIMALE
Il numerale 2304 in notazione decimale
(o in base 10) rappresenta la quantita’:
2304 = 2*103 + 3*102 +0*101 + 4*100 =
2000 + 300 + 0 + 4 = 2304 (numero)
Nota: numero e numerale qui coincidono,
perche’ il sistema decimale e quello adottato
come sistema di riferimento.
IL SISTEMA BINARIO
2
Cifre di base: 0 e 1.
 Notazione posizionale: la posizione di
una cifra in un numero binario indica il suo
peso in potenze di 2. I pesi sono:
– 20 = 1
(posiz. 0-esima)
– 21 = 2
(posiz. 1-esima)
– 22 = 4
(posiz. 2-esima)
– 23=8; 24=16; 25=32; 26=64; 27=128; 28=256;
29=512; 210 = 1024; 211=2048, 212=4096;...
ES. DI NUMERO RAPPR. IN
NOTAZIONE BINARIA
Il numerale 10100101 in notazione binaria
(o in base 2) rappresenta la quantita’:
10100101
1*27+0*26+1*25+0*24+0*23+1*22+0*21+1*20
128 + 0 + 32 + 0 + 0 + 4 + 0 + 1 =
165 (numero)
IL NUMERO PIU’ GRANDE
RAPPRESENT. CON N CIFRE
 Sist.
Decimale = 99…99 = 10N - 1
 Sist.
Binario= 11..11 = 2N - 1
 Esempio:
11111111 (8 bit binari) = 28 -1 =
255. Per rappresentare il n. 256 ci vuole
un bit in piu’: 100000000 = 1*28 = 256.
QUINDI:
Fissate quante cifre (bit) sono usate per
rappresentare i numeri, si fissa anche il
numero piu’ grande che si puo’ rappresent.:
– con 16 bit: 216 - 1 = 65.535
– con 32 bit: 232 - 1 = 4.294.967.295
– con 64 bit: 264 - 1 = circa 1,84 * 1019
Pero’: si possono rappresentare numeri piu’
grandi se si tollera un certo grado di
imprecisione.
CONVERSIONE DA BASE 2 A 10
Basta moltiplicare ogni bit per il suo peso e
sommare il tutto:
Esempio:
10100
1*24 + 0*23 + 1*22 + 0*21 + 0*20 =
16 + 4 = 20
la conversione e’ una somma di potenze
(N.B. se il numero binario termina per 1 e’ dispari
altrimenti e’ pari).
CONVERSIONE DA BASE 10 A 2
Idea di fondo: usare le potenze di 2 che,
sommate, danno il numero N da convertire:
– Prendere le potenze di 2 <= di N nell’ordine
dalla piu’ grande alla piu’ piccola (cioe’ 20)
– Associare il bit 1 alle potenze che vengono
usate nella somma per ricostruire N
– Associare il bit 0 alle potenze non usate.
ESISTONO ANCHE ALTRE BASI
DI NUMERAZIONE:

CODICE OTTALE
– cifre: 0, 1, 2, 3, 4, 5, 6, 7
– 10 (ottale) = 8 (decimale)

CODICE ESADECIMALE
– cifre: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
– 10 (esadecimale) = 16 (decimale); B = 11;
2B=2*161+B*160 = 32+11 = 43
NUMERI A VIRGOLA MOBILE
(NUMERI FLOATING POINT)
Idea: 12,52 = 1252/100 = 1252 * 10-2
Un numero decimale e’ rappresentato come
un intero moltiplicato per una opportuna
potenza di 10, cioe’ con una coppia:
<1252; -2>
mantissa
esponente
NUMERI FLOATING POINT
E’ necessario stabilire quanti bit assegnare
alla mantissa e all’esponente.
Ad esempio, con 16 bit a disposizione
possiamo usarne 12 per la mantissa e 4
per l’esponente
(in realta’ dovremmo anche tener conto dei
segni)
NUMERI FLOATING POINT
Con lo stesso metodo possiamo rappresent.
Numeri molto grandi. Ad esempio, con 8 bit:
5 bit di mantissa: 11111 = 31
3 bit di esponente: 111 = 3
11111111 = 31 * 107 = 310 milioni
Mentre, con la notazione classica, con 8 bit
rappresentiamo al massimo il n. 255
NUMERI FLOATING POINT
Ma allora, perche; non usare sempre la
notazione floating point?
Perche’ si perde in precisione
Esempio: 5 cifre (decimali) : 4 per la
mantissa, 1 per l’esponente. Rappresentare
312,45
<3124; -1> = [312,4 .. 312,5]???
NUMERI FLOATING POINT
Quindi: possiamo rappresentare numeri
molto grandi o con molti decimali al costo di
una perdita di precisione
Perche’? Perche’ i computer permettono
solo rappresentazioni finite, e cosi’
dobbiamo approssimare alcuni numeri (ad
esempio gli irrazionali), ma anche immagini
e suoni
CODIFICA DELLE IMMAGINI B/N

Dividere l’immagine in una griglia a righe
orizzontali e verticali

Ogni quadratino della griglia e’ un pixel

Codificare ogni pixel con:
– 0 se il pixel e’ bianco
– 1 se il pixel e’ nero

Convenire un ordinamento per i bit usati
nella codifica
CODIFICA DELLE IMMAGINI B/N
originale
imm. digitale
CODIFICA DELLE IMMAGINI
Quindi: le immagini sono rappresentate
con un certo livello di approssimazione, o
meglio, di risoluzione, ossia il numero di
pixel usati per riprodurre l’immagine:
– 640 x 480 pixel; 800 x 600 pixel
– 1024 x 768 pixel; 1280 x 1024 pixel
N.B. Ha importanza anche il dot pitch, il grado
di definizione del pixel: 0,25 - 0,28)
CODIFICA DELLE IMMAGINI
- Anche il colore e’ approssimato. Per il bianco e
nero, con 8 bit si codificano 256 livelli di grigio.
(ottenuti regolando la luminosita’ del pixel)
- Per i video a colori, con 8 bit si rappresent. 256
colori, con 16 bit 64.000 colori, con 24 bit 16
milioni di colori diversi per pixel
- BITMAP: la rappresentazione di una immagine
con codifica dei pixel. Porta via molto spazio:
(immagine a 640 x 480 x 256 c.=307.200 Byte)
CODIFICA DELLE IMMAGINI
- E’ possibile risparmiare spazio nella
rappr. delle immagini: Aree dello stesso
colore si rappresentano in modo
“abbreviato”.
- Esistono vari formati di codifica:
(bmp, gif, jpg, pict, tiff)
- E’ in genere possibile passare da un
formato ad un altro.
CODIFICA DEI SUONI
L’onda sonora viene misurata (campionata)
ad intervalli regolari
Minore e l’intervallo di campionamento e
maggiore e la qualita’ del suono
CD musicali: 44000 campionamenti al
secondo, 16 bit per campione.
CODIFICA DEI SUONI
Alcuni formati:
• ---.mov
• ---.wav
• ---.mpeg, ---.avi,
• formato midi usato per l’elaborazione
della musica al computer
CODIFICA DEI FILMATI
 Sono
sequenze di immagini compresse:
(ad esempio si possono registrare solo le
variazioni tra un fotogramma e l’altro)
 Esistono vari formati (compresi i suoni):
– mpeg (il piu’ usato), e' il formato DVD
– avi (microsoft)
– quicktime (apple)
– mov
 E’
possibile ritoccare i singoli fotogrammi
IL CONCETTO DI FILE
FILE: sequenza di byte conosciuta nel
computer con un certo nome.
TIPI DI FILE:
– file di dati (es: immagini o suoni)
– programmi (es: word o explorer)
– file di testo (cioe’ caratteri ascii)
ESTENSIONI DI UN FILE (windows95/98)
– nome.gif, nome.exe, nome.doc, ...
LA STRUTTURA DEI FILE (?)
E’ meglio vedere un file come una
sequenza di byte. E’ il programa che usa
il file a gestirne il contenuto in modo
corretto.
Ad esempio, nei file di testo quando viene
incontrato il byte = <new line> si devono
visualizzare i caratteri successivi nella
riga sottostante.
ARCHITETTURA DEI COMPUTER
(L’HARDWARE!!!)
 Processore
 Memoria
(CPU)
Principale (o Primaria o RAM)
 Memoria
di Massa (o secondaria, il
famoso hard disk, ma anche nastri, CD)
 Dispositivi
di Input/Output (video,
tastiera, stampanti,…)
FUNZIONAMENTO
 Programmi
e dati risiedono in file
memorizzati in memoria secondaria.
 Per essere eseguiti (i programmi) e usati
(i dati) vengono copiati nella memoria
primaria.
 La cpu e’ in grado di eseguire le istruzioni
di cui sono composti i programmi
FUNZIONAMENTO
copia il programma in RAM
programma
CPU
programma
RAM
hard disk
esegui le istruzioni del programma
LA MEMORIA PRINCIPALE
 Sequenza
di celle di memoria
 Ogni cella memorizza un byte
 Fisicamente e’ fatta di componenti
elettronici (transistors) miniaturizzati
 Ogni unita’ elementare puo’ trovarsi a
due diversi livelli di tensione elettrica:
ecco il corrispettivo fisico del bit
LA MEMORIA PRINCIPALE
 Le
celle sono numerate in sequenza: il
numero di ogni cella costituisce il suo
indirizzo
 Specificando l’indirizzo di una cella, la cpu
e’ in grado di leggere e/o modificare il
valore del byte memorizzato in quella cella
 Random Access Memory (RAM), perche’
ogni cella e’ indirizzabile direttamente.
LA MEMORIA PRINCIPALE
(LA RAM)
0
1
2
3
...
65.536
00101111
11001101
01010100
11111101
…………..
10000110
DIMENSIONI DELLA RAM
 Spazio
di indirizzamento: insieme o
numero delle celle indirizzabili direttam.
 Il numero di celle indirizzabili e’ una
potenza di due. Con:
– 16 bit si indirizzano 216 celle = 65.536 celle
– 32 bit si indirizzano 232 = 4.294.967.296 celle
– …..
UNITA’ DI MISURA DELLA MEMORIA
 Si
usano delle unita’ di misura per indicare
la dimensione della memoria:
– kilobyte (KB) = 1024 byte (210 byte)
– megabyte (MB) = 1000 KB (220 B)
– gigabyte (GB) = 1 miliardo di byte
 Quindi:
– con 16 bit si indirizzano 64KB di memoria
– con 32 bit si indirizzano 4GB di memoria
DIMENSIONI TIPICHE DELLA RAM
 Nei
Personal computer:
– 8, 16, 32, 64, 128 Megabyte
– una volta era un lusso avere 64 KB
 Nei
Mainframe/Workstations:
– 32, 64, 128, 256, …., Megabyte
 Ricordatevi
che la memoria e’
espandibile (fino ad un certo limite)
ALTRE INFO. SULLA RAM: LA
PAROLA O WORD
 La
parola (word) di un computer:
quanti bit possono essere letti/scritti/usati
dalla cpu con un unico accesso alla memoria
(16, 32, 64, 128 bit)
 Piu’
grande e la parola, maggiore e’ la
potenza del computer (vedasi le
playstations)
ALTRE PROPRIETA’ DELLA RAM
 La
ram e’ veloce: per leggere/scrivere
una cella ci vogliono, in media 5--30
nanosecondi (millesimi di milionesimi di
secondo = 30 * 10-9)
 la ram e’ volatile: e’ fatta di componenti
elettronici, e se togliete l’alimentazione
perdete tutto
 La ram e’ costosa (relativamente)
LA MEMORIA SECONDARIA
(L’HARD DISK)

Programmi e dati risiedono normalmente in
memoria secondaria.

Quando si lancia un programma questo viene
copiato dalla memoria secondaria (di solito un
hard disk) in memoria primaria. Questa
operazione si chiama caricamento (eseguita
dal sistema operativo).
L’HARD DISK:
 E’
fatto di supporti magnetici permamenti,
gestiti mediante dispositivi meccanici.
 Tempi di accesso dell’ordine dei
100 x micro/millisecondi.
 Spazio disponibile:
– Hard disk: 6, 8, 10, 20, 30 Gigabyte
(una volta era un lusso avere 20 Megabyte)
– Floppy disk (3.5”): 1.44 Megabyte
(obsoleto ma, incredibilmente, ancora in uso)
I BLOCCHI DELL’HARD DISK
 Nell’hard
disk la memoria e’ organizzata
in blocchi di dimensione fissa (512B,
1KB,2KB,..) indirizzabili direttamente
 La lettura/scrittura del disco avviene
sempre in blocchi, per risparmiare tempo
(pensate al tempo perso se si dovesse
leggere un byte per volta!)
 Il disco e’ quindi formattato in blocchi
MEMORIA PRIMARIA
VS
MEMORIA SECONDARIA
RAM
veloce (nanosec)
piccola (Megabyte)
volatile
HARD DISK
lenta (microsec)
grande (Gigabyte)
permanente
Notate che, in teoria, il computer potrebbe
funzionare con la sola ram o il solo harddisk
NASTRI MAGNETICI, CD, DVD
 Nastri:
accesso sequenziale, cioe' molto
lento. Usati per i backup, economici
 CD: 650 MB; Lettore CD 24X? Legge 24
volte piu' veloce di un lettore musicale
 DVD: circa 6 GB; stesso supporto fisico
dei CD, ma i dati sono rappresentati in
modo diverso.
IL PROCESSORE - CPU
(CENTRAL PROCESSING UNIT)
 Si
occupa di eseguire i programmi che
sono scritti in linguaggio macchina
I
programmi sono fatti di istruzioni
 le
istruzioni sono operazioni elementari:
– somma due numeri, confronta due numeri,
LE ISTRUZIONI MACCHINA
Codice istruzione | argom. 1 | argom. 2
•16 o 32 o 64 bit di lunghezza
• esempio: "add 6523 6450"
IL SET DI ISTRUZIONI MACCHINA

Ogni tipo di processore e’ in grado di eseguire
un numero limitato (40/100) di istruzioni

Istruzioni aritmetiche, logiche, di spostamento,
di lettura/scrittura in memoria, di salto.

Combinando in modo diverso sequenze anche
molto lunghe di istruzioni (i programmi) si
possono far fare al computer tantissime cose
completamente diverse
COSA FA LA CPU:
 Esegue
in modo ciclico:
– preleva dalla memoria centrale la prossima
istruzione da eseguire;
– esegui l’istruzione
– ripeti tutto
 Alla
velocita’ del clock (700, 800,... MHz)
(es.: 800 milioni di cicli al secondo)
LE COMPONENTI DELLA CPU:
I REGISTRI
 piccole
unita’ di memoria (2, 4, 8 byte) con
tempi di accesso molto piu’ bassi delle
celle della memoria primaria
 Ospitano le informazioni necessarie per
eseguire l’istruzione corrente
 In numero molto limitato perche' molto
costosi da realizzare
LE COMPONENTI DELLA CPU:
Il Program Counter (PC)
– contiene l’indirizzo in memoria centrale della
prossima istruzione da eseguire.
– All’inizio dell’esecuzione di un programma
viene caricato con l’indirizzo della prima
istruzione di quel programma.
– Ad ogni struzione eseguita viene il PC viene
modificato per contenere l’indirizzo della
istruzione successiva
LE COMPONENTI DELLA CPU:
I REGISTRI GENERALI
I
registri generali: R1, R2, R3,...
–in numero di 8, 16, 64
–sono usati come memorie temporanee
per contenere gli operandi delle
istruzioni e i risultati parziali durante
l’esecuzione delle istruzioni.
UN PROGRAMMA IN LINGUAGGIO
MACCHINA (ASSEMBLER)
1000
1004
1008
1012
1016
LOAD 3568 R1
LOAD 3574 R2
ADD R1 R2
STORE R1 3568
JUMP 1000
…….
PROBLEMA:
La RAM e' molto piu' lenta della CPU
 La RAM e' un collo di bottiglia
 A che serve spendere soldi per una
CPU molto veloce se poi non
possiamo sfruttarla?

SOLUZIONE:
LA MEMORIA CACHE
livello di memoria intermedio tra i registri
e la ram.
 per memorizzare i dati usati piu’ spesso
senza doverli recuperare RAM
 64KB, 128KB, 256KB, 512KB
 interna o esterna alla CPU
 Influisce moltissimo sulle prestazioni e il
costo della CPU (e quindi del computer)

LA MEMORIA CACHE
copia il programma in RAM
per l'esecuzione
copia un pezzettino di programma
e dei dati in cache
programma
gram
CPU
programma
RAM
hard disk
cache
esegui le istruzioni del programma
MEMORIE DI UN COMPUTER
Registri
16/64 Byte
100 * picosec.
Cache
128/512 KB nanosecondi
RAM
16/256 MB
10 * nanosec
Hard disk
2/10 GB
10 * microsec.
Nastri
> 10 GB
millisecondi
DISPOSITIVI DI INPUT/OUTPUT
(I/O, PERIFERICHE)
 Terminali.
Tastiera + Video:
– risoluzione, dimensione in pollici,…
 Stampanti:
– ad aghi, a getto, d’inchiostro, laser,…
 Modem:
per collegarsi in rete
 Scanner: per digitalizzare le immagini
 lettori CD, CDrw, DVD, ...
I PROGRAMMI (IL SOFTWARE!!!)
 Qualcosa
di assolutamente immateriale,
memorizzato mediante supporti
magnetici ed elettronici che dice al
computer cosa fare
 Il computer e’ programmabile. Usando
programmi (sequenze di istruzioni)
diversi, gli facciamo fare cose diverse
IL SOFTWARE DI BASE
 Si
ma: dobbiamo impartire ordini al
computer usando solo il codice binario???
 Ovviamente no: il computer e’ dotato di
alcuni programmi (il software di base)
che rendono il computer facile da usare
 Questi programmi trasformano il computer
in una macchina virtuale, piu’ vicina alle
esigenze dell’utente che puo’ cosi’
ignorare i dettagli implementativi.
IL SOFTWARE DI BASE
 Il
sistema operativo: che permette di
– sfruttare le risorse del computer in modo
semplice e (si spera) intuitivo (si pensi ad
esempio alle interfacce grafiche)
– usare i programmi che ci interessano (di
scrittura, di studio, i videogames) senza
preoccuparci di come questo avvenga
all’interno del computer
IL SOFTWARE DI BASE
I
Linguaggi di programmazione ad alto
livello, che permettono di:
–scrivere i propri programmi, cioe’ di
usare il computer come vogliamo noi
–di poter usare questi programmi su
qualsiasi (beh, quasi) computer (questa
si chiama portabilita’)
IL SISTEMA OPERATIVO
 E’
di gran lunga il programma piu’
importante che gira su un qualsiasi
computer
 Senza il Sistema Operativo (SO) il
computer sarebbe scomodissimo e
complicatissimo da usare.
COSA FA IL SIST. OPERATIVO?
 Gestisce
in modo efficiente le risorse del
computer: cpu, memoria, periferiche.
 "Capisce"
i comandi dell’utente: mouse e
clicks, esecuzione di programmi,…
all’utente tutti i problemi di
gestione delle varie parti del computer
 Nasconde
LA CIPOLLA DEL SISTEMA
OPERATIVO
INTERFACCIA con L'utente
GESTIONE MEMORIA/RISORSE
dove si eseguono i programmi
LE FUNZIONI PRINCIPALI DEI SO
 Gestione
del processore
 gestione
della memoria principale
 gestione
della memoria virtuale
 gestione
della memoria secondaria (il
file system)
L’ESECUZIONE DEI PROGRAMMI
Quando clicckate 2 volte sull’icona di un
programma, il S.O.:
 cerca il programma sull’hard disk
 copia il programma in memoria centrale
 imposta il Progr. Counter con l’indirizzo
in memoria centrale della prima
istruzione del programma
LA GESTIONE DEI PROCESSI
 Il
ruolo del processore e’ di eseguire i
programmi
 Un
processo e’ un programma in
esecuzione
SISTEMI MONO-USER/TASKING
 Un
solo utente puo’ eseguire un
programma per volta.
 Il
programma viene lanciato, esegue le
proprie funzioni e termina.
 Ma
la CPU viene sfruttata al meglio?
NEI SIST. MONO-USER/TASKING SI
SPRECA UN SACCO DI TEMPO!
 La
CPU e’ molto piu’ veloce dei dischi e
delle periferiche, e passa la maggior
parte del suo tempo in attesa del
completamento delle operazioni di questi
devices
 durante l’attesa si dice che la CPU e’ in
uno stato inattivo detto idle
ESEMPIO (1):
 Un
processo richiede l’esecuzione di
1000 istruzioni. Ogni istruzione richiede 1
microsec. di CPU. (tempo tot. = 1millisec.)
 A meta’
esecuzione e’ richiesta la lettura
di un dato su hard disk. Tempo di lettura =
1 millisec.
 Durata
 Idle
totale dell’esecuzione = 2 millisec.
time = 1millisec = 50% del tempo
di esecuzione = TEMPO SPRECATO!
ESEMPIO (2):
 Processo
= 1000 istruzioni. Ogni istr. =1
microsec. (tempo tot. = 1millisec.)
 A meta’
esecuz. e’ richiesto un dato
all’utente. Tempo di reazione = 1 sec.
 Durata
 Idle
totale = 1001 millisecondi
time = 1sec = 99,9% del tempo di
esecuzione = TEMPO SPRECATO!!!!!!!!
SOLUZIONE:
 Quando
la CPU e’ idle (insomma, quando
non ha nulla da fare) la si puo’ sfruttare
per eseguire (parte di) un altro processo.
 Quando un processo si ferma (e.g., in
attesa di un dato dall’utente) la CPU puo’
eseguire le istruzioni di un altro processo
 Chi si occupa di realizzare questa
alternanza di processi? Il S.O. (ci
risparmiamo il come).
IL MULTI-TASKING:
 Piu’
programmi possono essere eseguiti
contemporaneamente
 In realta’ in esecuzione c’e’ sempre un
solo processo, ma se l’alternanza e’ molto
frequente, si ha un’idea di simultaneita’
 si dice che il sistema e’
multi-programmato.
GLI STATI DI UN PROCESSO in un
S.O. MULTI-TASKING
terminazione
In esecuzione
Richiesta di
I/O o risorsa
pronto
I/O terminato o
risorsa disponibile
creazione
In attesa
SI, MA CHE SUCCEDE SE…:
 Un
processo non si ferma mai in attesa
di I/O o di una risorsa?
 Piu’ utenti vogliono usare il computer?
 E’ necessario far si che la risorsa piu’
importante del computer - la CPU - sia
distribuita equamente tra i processi
(dello stesso utente e di utenti diversi)
IL TIME SHARING:
 Ad
ogni processo viene assegnato un
quanto di tempo (e.g., 10 millisec). Nel
quale puo’ usare la CPU.
 Terminato il quanto di un processo, il
processo viene sospeso e la CPU viene
assegnata ad un altro processo.
 Un processo puo’ usare meno del quanto
che gli spetta: deve eseguire operazioni di
I/O oppure ha terminato la sua computaz.
EFFETTI DEL TIME SHARING:
 L’esecuzione
di piu’ processi appare
avvenire realmente in parallelo (questo
parallelismo, pero’, e’ solo virtuale).
 Piu’ utenti possono usare allo stesso
tempo il computer, perche’ la CPU viene
assegnata periodicamente ai processi dei
vari utenti (e.g., ogni 10 o 100 millisec.)
 Ovviamente, piu’ processi e piu’ utenti ci
sono e piu’ le prestazioni si degradano
GLI STATI DI UN PROCESSO in un
S.O. TIME SHARING
terminazione
E’ finito il quanto
di tempo
In esecuzione
Richiesta di
I/O o risorsa
pronto
I/O terminato o
risorsa disponibile
creazione
In attesa
I
p3
p3
p2
p1
p2
p1
GESTIONE DELLA
MEMORIA PRINCIPALE
 Il
problema e’: data la memoria primaria
del computer, come dobbiamo usarla per
far “girare” i processi in esecuzione?
SISTEMI MONO-PROGRAMMATI
 Una
porzione di memoria per il S.O., una
porzione per caricare il programma da
eseguire.
Sistema operativo
Processo
utente
SISTEMI MULTI-PROGRAMMATI
 Pero',
se si vogliono eseguire
"contemporaneamente" piu' programmi,
dobbiamo prevedere un'area per ognuno
di essi.
 Nel caso piu' semplice, il S.O. assegna un
pezzo di memoria a ciascun programma.
PARTIZIONI MULTIPLE:
ALLOCAZIONE CONTIGUA FISSA
 E’
fissato a priori il numero e le dimensioni
delle partizioni:
Sistema operativo
200 KB
100KB
100KB
PARTIZIONI MULTIPLE:
ALLOCAZIONE CONTIGUA FISSA
La strategia e’ facile da implementare, ma:
 Si spreca spazio all’interno delle partizioni
perche’ un processo non ha sempre le
dimensioni esatte della partizione in cui e’
allocato. Questo problema si chiama:
FRAMMENTAZIONE INTERNA
PARTIZIONI MULTIPLE:
ALLOCAZIONE CONTIGUA FISSA
 Una
partizione libera puo’ rimanere
inutilizzata se ha una dimensione inferiore
a quella di un processo che deve essere
eseguito. Questo problema si chiama:
FRAMMENTAZIONE ESTERNA
PARTIZIONI MULTIPLE:
ALLOCAZIONE CONTIGUA FISSA
I
processi con dimensione maggiore
della partizione piu’ grande non
possono mai essere eseguiti
 Del resto, se si prevedono partizioni
troppo grandi si ha una eccessiva
frammentazione interna. Se sono troppo
piccole si ha troppa framment. esterna.
PARTIZIONI MULTIPLE:
ALLOC.CONT. VARIABILE
 Principio:
allocare quando richiesto la
quantita’ di memoria necessaria.
S.O.
S.O.
Area libera
400KB
50 KB
Area libera
350KB
 Scompare
la frammentazione interna
MEMORIA VIRTUALE
Problema:
– Memoria principale = 1MB
– Dimensione del Processo 1 (P1) = 800KB
– Dimensione del Processo 2 (P2) = 700KB
Possiamo eseguirli contemporaneamente?
Con le tecniche che abbiamo visto finora, no?
MEMORIA VIRTUALE: SWAPPING
Quando il processo in esecuzione si ferma, la
sua immagine e’ copiata in un’area riservata al
S.O. in memoria secondaria (swap area)
 L’immagine del nuovo proc. in esecuzione puo’
ora essere copiata in memoria primaria
 Quando un proc. esce dallo stato di attesa,
prima che possa diventare pronto, la sua
immagine deve essere ricaricata in memoria
primaria

MEMORIA VIRTUALE: SWAPPING
di memoria virtuale, perche’ di
fatto, sono in esecuzione
contemporaneamente due processi la cui
dimensione totale e’ maggiore delle
dimensioni della memoria reale.
 Parliamo
MEMORIA VIRTUALE:
Segmentazione
Nello swapping, l’immagine di un processo sta
tutta in memoria primaria o in mem. Secondaria
 Se un processo e’ troppo grande non si puo’
comunque eseguire.
 Ma allora, perche’ non tenere in mem. Primaria
solo la parte di un processo che serve in quel
momento?

MEMORIA VIRTUALE:
segmentazione
 Ad
esempio, nel programma WORD:
– Un utente esperto non usera’ mai il manuale
in linea. Serve caricarlo in memoria?
– La scrittura di una lettera non richiede la
produzione di disegni. Serve caricare in
memoria il codice per disegnare, che non
verra’ mai usato (cioe’ eseguito dalla cpu)?
MEMORIA VIRTUALE:
segmentazione
Nella gestione della memoria a segmenti,
vengono effettivamente caricati in mem.
Primaria solo i pezzi del programma in
esecuzione che servono in quel momento.
 Ma che succede se il processo deve usare un
pezzo di programma che manca?

MEMORIA VIRTUALE:
segmentazione
Si verifica un segment fault: il S.O. si accorge
che il segmento manca. Sospende il processo
relativo e fa partire le operazioni per recuperare
dalla memoria secondaria il segmento
mancante e copiarlo in memoria primaria
 Intanto, un altro processo puo’ usare la cpu.
 Quando la segmento mancante e’ disponibile, il
processo sospeso puo’ ripartire (e’ pronto)

GESTIONE DELLA MEMORIA
SECONDARIA:IL FILE SYSTEM
I file di un computer sono memorizzati in
maniera permanente sull’hard disk.
 Fisicamente, i file sono memorizzati in blocchi
(o record fisici) di dimensione fissa variabile
tra 512 a 4kB
 Logicamente, i file sono organizzati in una
struttura ad albero detta File System

IL FILE SYSTEM
Non ha senso tenere tutti i file insieme.
Conviene raggrupparli a seconda dell’uso.
 Il S.O. mette a disposizione dei file particolari:
le cartelle (o folder, o directory) che sono
usati per contere file e altre altre cartelle.
 Per mezzo delle cartelle e’ quindi possibile dare
una struttura al file system. In particolare una
struttura gerarchica ad albero

IL PATHNAME DI UN FILE
All’interno del file system, il percorso che si
deve compiere per raggiungere quel file.
 Ossia: la successione di cartelle che si deve
attraversare per raggiungere il file, a partire
dalla radice del file system
 Nella stessa cartella non ci possono essere due
file con lo stesso nome, quindi il pathname di
un determinato file e’ sempre unico.

OPERAZIONI SUI FILE
Il S.O. fornisce vari supporti per:
 Operare sui file (leggere, modificare, rimuovere,
rinominare, stampare,…)
 Usare il file system (creare, (ri)nominare,
rimuovere, copiare, spostare, leggere il
contenuto delle cartelle)
 Proteggere i file (ad esempio si puo’ proibire la
modifica, o la lettura, o la rimozione di (gruppi
di) file.
RETI DI COMPUTER
Colleghiamo piu’ computer in rete per:
 scambiare informazioni (scambio di
documenti, e-mail, mailing-list, newsgroups,
web, …)
 condividere risorse (periferiche e hard disk in
comune, computazioni distribuite, …)
 aumentare la tolleranza ai guasti (se un
computer si rompe, un altro puo’ sostituirlo)
TIPI DI RETI ( dal punto di
vista della loro estensione)
Rete locale (LAN - Local Area Network):
collega due o piu’ computer in un area non piu’
grande di un palazzo. Collega i computer di un
laboratorio, gruppo di lavoro, ufficio, ditta.
 Internet: la rete delle reti. Collega fra loro reti
locali e singoli computer di tutto il mondo
 Rete metropolitana: concettualmente simile ad
una rete locale, collega computer di una singola
organizzazione (es.: Banca con filiali cittadine).

TIPI DI RETI LOCALI: LINEARI
(ETHERNET, APPLETALK)
PC1
PC2
PC3
PC4
Ethernet e’ il tipo di rete locale piu’ diffuso.
 Qualsiasi computer di qualsiasi tipo prevede la
possibilita’ di usare una scheda Ethernet per
connettersi alla rete locale

TIPI DI RETI LOCALI: AD ANELLO
(IBM)
PC1
PC2
PC4
PC3
TIPI DI RETI LOCALI:
A STELLA
PC1
PC3

PC2
hub
PC4
HUB: dispositivo hardware specializzato
che smista le comunicazioni dei computer
TIPI DI RETI LOCALI:
A TOPOLOGIA MISTA
hub
SISTEMI OPERATIVI DI
RETE (LOCALE)
In una LAN si vogliono condividere le risorse, di
solito, come minimo, stampanti e hard disk.
 Il S.O. deve permettere anche l’uso di quelle
risorse che non sono fisicamente collegate al
computer su cui si sta lavorando.
 I S.O. dei compuer in rete devono quindi
dialogare fra loro per permettere la condivisione
delle risorse.

FILE SYSTEM DISTRIBUITO
Parliamo di file system distribuito quando
l’utente del file system vede un’unica struttura
ad albero, e non si accorge che alcune parti
dell’albero (sub-tree) risiedono in realta’
sull’hard disk di un altro computer della rete.
 Il S.O. maschera completamente la situazione.
(in Unix, nel S.O. Windows un po’ meno)
 E’ possibile configurare in file system distribuito
in molti modi diversi, prendendone “pezzi” dalle
varie macchine in rete

SISTEMI OPERATIVI DISTRIBUITI
Versione piu’ sofisticata dei S.O. di rete
 Quando l’utente di un computer esegue un
programma, non e’ detto che questo venga
fatto girare sulla CPU locale: il S.O. si occupa di
selezionare il computer (e quindi la CPU) piu’
scarica su cui il processo deve girare.
 I S.O. distribuiti sono ancora in fase di studio.
Non esiste nulla a livello commerciale

TRASMISSIONE
SERIALE O PARALLELA
Si supponga di dover trasmettere un byte:
 Se il canale di comunicazione e’ fatto di un solo
filo, dobbiamo trasmetterlo serialmente, un bit
dopo l’altro.
 Se il canale di comunicazione‘ fatto di 8 fili,
possiamo trasmettere il byte in un colpo solo.
Gli otto bit sono trasmessi in parallelo.
TRASMISSIONE
SERIALE O PARALLELA
La trasmissione parallela e’ piu’ veloce, ma piu’
costosa da implementare, e viene usata di
solito solo per collegamenti punto a punto e
molto corti (es.: computer - stampante)
 La trasmissione seriale e’ quella normalmente
usata nelle reti, locali e non locali.
 In una LAN Ethernet, la trasmissione avviene a
10 o 100Mbit/sec (cioe’ almeno 1MByte/sec)

PROTOCOLLO DI
COMUNICAZIONE
I computer di una rete, per comunicare si
scambiano dei messaggi. Ogni messaggio deve
contenere:
– l’indirizzo del mittente e del destinatario
– il tipo di servizio richiesto ed eventuali dati
 Ad esempio, il PC A puo’ richiedere al PC B la
stampa di un file sulla stampante connessa a B
 Il protocollo deve essere anche in grado di
gestire gli errori di comunicazione

PROTOCOLLO DI
COMUNICAZIONE
TCP/IP (Transmission Control Protocol/Internet
Protocol) e’ il protocollo di comunicazione usato
in internet e anche nella maggior parte delle
altre reti.
 Praticamente tutti i servizi offerti da Internet,
compreso il web, sono costruiti usando TCP/IP

TRASMISSIONE
DIGITALE O ANALOGICA
Nelle reti locali, la comunicazione tra due
computer passa di solito su cavi dedicati,
installati esplicitamente per la rete, e adatti per
la trasmissione digitale delle informazioni.
 (Semplificando un po’) su questi cavi si ha una
variazione del livello di tensione fra due valori,
che corrisponde alla trsmissione di bit di valore
zero oppure 1.

TRASMISSIONE
DIGITALE O ANALOGICA
Per le comunicazioni su lunga distanza, si
cerca di sfruttare le reti di comunicazione
esistenti, come ad esempio la rete telefonica.
 La rete telefonica e’ pero’ fatta per comunicare
la voce, cioe’ un segnale analogico che varia in
maniera continua in una banda di frequenze.
 Sono necessari dei dispositivi per poter usare la
rete telefonica come mezzo di comunicazione
tra computer

IL MODEM
COMPUTER
Segnale
digitale
MODEM
Segnale
analogico
linea telef.
COMPUTER
Segnale
digitale
MODEM
IL MODEM
I modem attuali hanno velocita’ di trasmissione
di 14.400, 28.800, 38.400, 56.600 bit/sec. Ossia
una velocita’ massima di non piu’ di 6 kByte/sec
 Se due computer comunicano con un modem,
la velocita’ di comunicazione e’ sempre quella
del modem piu’ lento.
 Il modem e’ usato soprattutto per le
comunicazioni private (ad esempio un utente
che si collega ad internet tramite il suo provider)

COMUNICAZIONE SU LINEA
DEDICATA O COMMUTATA
Quando due computer sono connessi
direttamente da un cavo di comunicazione, si
parla di linea dedicata di trasmiss./comunic.
 Nel caso piu’ generale, e soprattutto su internet,
la comunicazione tra due computer avviene
attraverso computer intermedi, che fanno da
tramite tra i due che devono comunicare,
ritrasmettendo i loro messaggi. Si parla allora di
comunicazione su linea commutata

LINEE COMMUTATE :
IL TELEFONO
I telefoni di un distretto telefonico fanno capo ad
una centrale di smistamento, che comunica con
le centrali degli altri distretti.
 Quando telefoniamo, la chiamata viene fatta
passare attraverso una o piu’ centrali, fino a
raggiungere il numero chiamato.
 Comunicando fra loro, le centrali costruiscono
una connessione diretta fra i due telefoni, che
dura tutto (e solo) il tempo della telefonata.

UNA SEMPLICE RETE A
LINEA COMMUTATA
A
B
D
C
Con le linee commutate si risparmiano soldi
TRASMISSIONE A
COMMUTAZIONE DI CIRCUITO
Quando due telefoni comunicano, la linea e’
occupata: nessuno puo’ chiamare quei telefoni.
 Che succede se usiamo una comunicazione a
commutazione di circuito su internet?
 DISASTRO: qualsiasi servizio offerto sarebbe
disponibile ad un solo utente per volta.
 Ad esempio, chi riesce a connettersi ad un sito
web lo puo’ usare in esclusiva per tutto il tempo
che vuole. DISASTRO

TRASMISSIONE A
COMMUTAZIONE DI PACCHETTO
Ogni messaggio e’ diviso in tanti pacchetti
numerati di dimensione fissa.
 Ogni pacchetto contiene l’indirizzo del computer
destinatario e del mittente.
 Ogni pacchetto e’ trasmesso separatamente.
Una volta inviato, il mittente se ne disinteressa
 Ogni pacchetto fa (virtualmente) una strada
diversa per arrivare al destinatario

TRASMISSIONE A
COMMUTAZIONE DI PACCHETTO
I pacchetti non arrivano necessariamente nello
stesso ordine con cui sono stati inviati
 Il destinatario aspetta di aver ricevuto tutti i
pacchetti per ricomporli e ricostruire il msg.
 Ogni pacchetto occupa il mezzo di trasmissione
e la scheda di rete per un tempo molto breve
 Si ha un effetto di parallelismo: ogni computer
puo’ essere coinvolto contemporaneamente in
piu’ comunicazioni

INSTRADAMENTO DEI
PACCHETTI (ROUTING)
Come far arrivare i pacchetti a destinazione?
 Ogni nodo della rete mantiene una tabella che
indica a quale/quali vicini ritrasmettere un
pacchetto non destinato a lui, in base
all’indirizzo di destinazione del pacchetto.
 La scelta del nodo a cui inoltrare il pacchetto
dipende anche da situazioni temporanee di
carico della rete, guasti, ecc.

COMMUTAZIONE DI PACCHETTO
(PACKET SWITCHING)
W
1
1
A
1
X
2
2
Y
B
2
2
Z
QUINDI, QUANDO VI COLLEGATE AD
INTERNET CHIAMANDO IL VOSTRO
PROVIDER COL TELEFONO:
Dal telefono di casa vostra al provider e’ in
corso una comunicazione a commutazione di
circuito (la vostra linea e’ occupata, perche’
state effettuando una chiamata telefonica)
 dal provider verso qualsiasi punto di internet al
quale decidete di collegarvi, la comunicazione
e’ a commutazione di pacchetto.

NAMING
Ogni computer di una rete deve avere un nome
logico unico. Il nome logico e’ usato dagli utenti
della rete per comunicare con quel computer
 Il computer ha anche un indirizzo fisico:
l’indirizzo con il quale il software che gestisce le
comunicazioni in rete localizza e gestisce la
comunicazione con quel computer.
 Deve essere gestita una corrispondenza tra il
nome logico e l’indirizzo fisico del computer

INTERNET
Collega fra loro reti locali e metropolitane di
tutto il mondo.
 La comunicazione tra le sottoreti avviene
sfruttando canali di comunicazione dedicati ad
alta tecnologia (ISDN, ATM, fibre ottiche) che
consentono velocita’ di trasmissione dell’ordine
di decine o centinaia di Megabit/sec
 Ovviamente non avrebbe senso usare la rete
telefonica, che e’ troppo lenta

INTERNET
Ogni rete locale “si affaccia su Internet”
attraverso un dispositivo (un vero e proprio
computer ) detto router. Il router si occupa di
smistare il traffico dei pacchetti in uscita ed in
entrata nella rete locale rispetto a internet
 Al router e’ spesso associato anche un
dispositivo detto firewall. Il firewall protegge la
rete locale da accessi indesiderati dall’esterno
(e in alcuni casi, viceversa)

INTERNET
I vari servizi offerti da internet sono costruiti col
protocollo di comunicazione TCP/IP. Oltre al
Web, i piu’ importanti sono:
 E-MAIL (Electronic Mail)
 FTP (File Transfer Protocol) Permette di
trasferire file tra computer
 TELNET Permette di collegarsi a qualsiasi
computer, e usarne le risorse (cpu e hard disk)
come se fosse sulla nostra scrivania
 Win95 non ha tutte le funzionalita’ di UNIX

INDIRIZZAMENTO IN INTERNET

Gli indirizzi logici Internet hanno la forma:
aaa.bbb.ccc
e sono organizzati in domini e sotto domini
 I domini possono essere geografici:

xxx.yyy.it aaa.bbb.uk
jjj.kkk.ca
o di altro tipo:
aaa.com bbb.ccc.ddd.net xxx.gov
INDIRIZZAMENTO IN INTERNET

All’interno dei domini vi sono i sotto-domini,
sotto-sotto-domini, e cosi’ via, fino
eventualmente a raggiungere lo specifico
computer della rete locale relativa:
– xxx.unito.it (sotto-dominio dell’univ. di Torino)
– di.unito.it (sotto-sotto-dominio del Dip. Di Informat.,
a cui corrisponde fisicamente la rete locale del Dip.
– Pianeta.di.unito.it (uno dei computer della rete
locale del Dipartimento di Informatica dell’Univ. Di
Torino, Italia)
INDIRIZZAMENTO IN INTERNET

Gli indirizzi logici sono usati solo per comodita’
degli utenti. I veri indirizzi Internet, (detti indirizzi
fisici), sono numerici. Ad esempio:
– pianeta.di.unito.it = 130.192.239.1
130 = dominio .it
192 = sotto-dominio .unito
239 = rete locale del Dip. di Informatica
1 = il computer pianeta
IL DOMAIN NAME SERVICE (DNS)
Il meccanismo di gestione degli indirizzi internet
e’ chiamato Domain Name Service (DNS)
 Ogni dominio e’ gestito da un computer che
contiene l’associazione tra i nomi logici e gli
indirizzi fisici di ogni suo sotto-dominio
 Ogni sottodominio e’ gestito da un computer
che contiene l’associazione tra i nomi logici e gli
indirizzi fisici di ogni suo sotto-sotto-dominio
 In questo modo e’ facile localizzare qualsiasi
punto della rete usando solo nomi logici.

IL DOMAIN NAME SERVICE (DNS)
Ad esempio, se da un pc negli USA si vuole
comunicare con la macchina pianeta.di.unito.it.
 Viene contattato il gestore del dominio .it (130)
 che contatta il gestore del dominio .unito (192)
 che contatta il gestore del dominio .di (239)
 che sa che la macchina pianeta, all’interno
della rete locale .di (239) ha numero 1.
 Viene quindi restituito l’indirizzo fisico che sara’
usato nella comunicazione: 130.192.239.1

CENNI DI PROGRAMMAZIONE
Il computer esegue programmi
 Un programma eseguibile dal computer e’ una
sequenza di istruzioni macchina comprensibili
da quel computer.
 Usando sequenze diverse di istruzioni, e dati
diversi, possiamo far fare al computer le cose
piu’ disparate

CENNI DI PROGRAMMAZIONE

Pero’ scrivere programmi in linguaggio
macchina (in assembler) e’ scomodo, perche’ il
linguaggio e’ molto distante da quello umano.

Inoltre, un programma in assembler gira solo su
un tipo di cpu, e sarebbe comodo poter usare lo
stesso programma su cpu e con S.O. diversi
senza doverlo riscrivere ogni volta (portabilita’)
LING.DI PROGRAMMAZIONE AD
ALTO LIVELLO
I linguaggi di programmazione ad alto livello
permettono di scrivere programmi con una
notazione adatta agli esseri umani, e in alcuni
casi molto intuitiva.
 Usando degli opportuni traduttori (compilatori
ed interpreti) lo stesso programma puo’ essere
usato su macchine diverse
 Fortran, Cobol, Pascal, Ada, C, C++, Java,
Lisp, ML, Prolog,...

IL COMPILATORE
Un programma scritto in un linguaggio ad alto
livello e’ detto programma sorgente.
 Per essere eseguito su un computer , va
tradotto nel linguaggio macchina del computer.
 Il compilatore e’ un programma che esegue la
traduzione, producendo il programma oggetto,
ossia una sequenza di istruzioni macchina
 Il compilatore segnala anche eventuali errori di
sintassi nella scrittura del programma sorgente

IL COMPILATORE
Programma P
scritto nel
linguaggio L
Compilatore per P
sul computer M
Programma P’ nel
linguag. macchina di M
Esecuzione
di P’ su M
L’INTERPRETE
In alternativa alla compilazione, un programma
sorgente puo’ essere interpretato.
 Un interprete e’ un programma che non
produce alcun programma oggetto, ma legge il
ogni istruzione del programma sorgente e
genera le istruzioni macchina corrispondenti,
che vengono passate all’hardware per
l’esecuzione.

COMPILATORI VS INTERPRETI
In un programma compilato, la traduzione
avviene una sola volta, e poi il programma
oggetto puo’ essere eseguito quanto si vuole
 In un programma interpretato, la traduzione
avviene tutte le volte che si esegue il progr.
 Molti linguaggi permettono entrambe le scelte
 Attualmente, i computer sono cosi’ potenti che
anche la compilazione di lunghi programmi non
richiede molto tempo.

IL CONCETTO DI ALGORITMO
Un algoritmo e’ una sequenza di passi
necessari per risolvere un problema o eseguire
una computazione
 In alcuni casi, lo stesso problema/computazione
puo’ essere risolto in modi diversi, ai cui
corrispondono diversi algoritmi
 Un programma non e’ altro che la descrizione
di un algoritmo scritta nel linguaggio di
programmazione scelto.

IL CONCETTO DI VARIABILE
Per eseguire una qualsiasi computazione,
abbiamo bisogno di poter immagazzinare i
risultati temporanei e finali della computazione
stessa.
 Ogni linguaggio ad alto livello mette a
disposizione le variabili: “contenitori” in cui
immagazzinare i dati della computazione
 Concettualmente, le variabili sono come pezzi
di carta su cui si possono annotare/modificare i
valori di un calcolo che si sta facendo

IL CONCETTO DI VARIABILE
Ogni variabile ha un nome mnemonico, che si
usa nel programma per riferirsi alla var. stessa.
 Una variabile contiene un valore che puo’
essere modificato a piacimento
 Durante l’esecuzione di un programma, il
sistema operativo mantiene una associazione
tra il nome di ogni var. e l’indirizzo della cella di
memoria in cui e’ memorizzato il suo valore
 Quindi una variabile e’ semplicemente una
astrazione della cella di memoria fisica.

IL CONCETTO DI VARIABILE
Quando si scrive un programma e’ necessario
dichiarare quali variabili vogliamo usare.
 Le variabili possono essere di tipo diverso, per
indicare che le usiamo per memorizzare dati di
tipo diverso:
– Variabile LETTERA, tipo: carattere;
– Variabile SOMMA, tipo: intero;

L’IMPORTANZA DELLE VARIABILI
Le variabili sono lo strumento fondamentale per
assicurare la flessibilita’ dei programmi.
 Lo stesso programma, eseguito con variabili di
valore diverso da risultati diversi. Lo stesso
programma si adatta cioe’ alle esigenze del
momento, senza dover essere riscritto

ESEMPIO D’USO DI VARIABILI
Program SILLY
begin
Variables: YEARS,DAYS, type integer;
read YEARS from input;
DAYS := YEARS * 365;
print DAYS;
end
COSTRUTTI DI BASE DI UN
LINGUAGGIO DI PROGR.

Definizione delle variabili che verranno usate
nel programma, e del loro tipo:
int PIPPO, PLUTO;
char NOME;
float RISULTATO;
COSTRUTTI DI BASE DI UN
LINGUAGGIO DI PROGR.

Istruzioni elementari: assegnamento di un
valore ad una variabile:
PIPPO := 5;
PLUTO := 7;
RISULTATO := PIPPO/PLUTO
COSTRUTTI DI BASE DI UN
LINGUAGGIO DI PROGR.

Azioni condizionali:
if (NOME = daniele)
then RISULTATO = 0;
else {
PIPPO := 5;
PLUTO := 7;
}
COSTRUTTI DI BASE DI UN
LINGUAGGIO DI PROGR.

Azioni ripetute:
while (PIPPO * PLUTO < 100)
repeat {
PIPPO := PIPPO+1;
PLUTO := PLUTO+1;
}
DIAGRAMMI DI FLUSSO
Notazione grafica usata per descrivere in modo
intuitivo le azioni di cui e’ fatto un algoritmo.
 Viene usata per descrivere i passi salienti di un
algoritmo, senza doversi preoccupare dei
dettagli sintattici del programma corrispondente
 Una volta che l’algoritmo e’ stato descritto con
un diagramma di flusso, deve pero’ essere
trasformato nel programma corrispondente.
 Ogni azione e’ rappresentata da un blocco

BLOCCHI DI FLUSSO:
INIZIO E FINE ALGORITMO
START
STOP
BLOCCHI DI FLUSSO:
UNA O PIU AZIONI ELEMENTARI
PIPPO := PIPPO + 1;
PLUTO := 0
BLOCCHI DI FLUSSO:
BLOCCO CONDIZIONALE
F
T
condizione
Diagramma 1
Diagramma 2
BLOCCHI DI FLUSSO:
BLOCCO DI RIPETIZIONE
F
condizione
T
Diagramma 1
BLOCCHI DI FLUSSO:
INPUT/OUTPUT
Input/output
THE SILLY PROGRAM
start
Read YEARS
DAYS:= YEARS * 365
print DAYS
stop
ESEMPIO DI TRADUZIONE
variables A, B, X, type integer
…….
If (A = B) then X := 1 else X := 2
…….
A: locazione 1000
4726
4730
4734
4738
4342
4346
4350
4354
4358
B: 1002
…….
LOAD 1000,R1
LOAD 1002,R2
LOAD 1004,R3
JNE R1,R2,4354
SET R3,1
JUMP 4358
SET R3,2
……..
X: 1004
IL CONCETTO DI RECORD

Vogliamo mantenere in un file informazioni di
tipo anagrafico su un insieme di persone. Per
ogni persona vogliamo memorizzare i seguenti
attributi:
– Nome, Cognome, Data di nascita, Residenza
Ogni attributo prende il nome di campo
 L’insieme dei campi prende il nome di record

IL CONCETTO DI RECORD
Possiamo assegnare una dimensione fissa ad
ogni campo del record. Ad esempio:
– Nome : 20 byte
– Cognome: 30 byte
– Residenza: 40 byte
– Data di nascita: 8 byte
 E memorizzare un gruppo di record in un file.
Il file e’ visto come diviso in tanti record di
dimensione fissa

IL CONCETTO DI RECORD
R0
NOME
R1
NOME
R2
NOME
R3
NOME
COGNOME
RESIDENZA
DATA
COGNOME
RESIDENZA
DATA
COGNOME
RESIDENZA
DATA
COGNOME
RESIDENZA
DATA
CAMPI A DIMEN. VARIABILE
Usando campi a dimensione fissa e’ piu’ facile
gestire le informazioni nel file, cioe’ inserire,
cancellare e cercare un record specifico.
 Pero’ i campi a dimensione fissa sprecano
spazio, oppure possono essere di dimensione
insufficiente.
 Si usano allora anche record i cui campi hanno
dimensione variabile, in modo da adattarsi
esattamente alla lunghezza della informazione
da memorizzare

IL CAMPO “CHIAVE”
Ogni record contiene di solito un campo in piu’
che contiene un valore progressivo assegnato
ai record man mano che sono aggiunti nel file.
 Questo campo, detto chiave del record puo’
essere usato per compiere ricerche in modo
veloce all’interno del file stesso.
 La chiave puo’ avere un significato specifico:
numero di CC, codice fiscale, partita IVA.
 Il valore della chiave e’ unico: in un file non ci
sono due record con lo stesso valore di chiave.

IL CAMPO CHIAVE
0
NOME
COGNOME
RESIDENZA
1
NOME
COGNOME
RESIDENZA
2
NOME
NOME
NOME
DATA
COGNOME
RESIDENZA
4
DATA
COGNOME
RESIDENZA
3
DATA
DATA
COGNOME
RESIDENZA
DATA
SITUAZIONE PIU’ REALISTICA
NOME
6
COGNOME
RESIDENZA
13
NOME
COGNOME
RESIDENZA
14
NOME
NOME
NOME
DATA
COGNOME
RESIDENZA

DATA
COGNOME
RESIDENZA
20
DATA
COGNOME
RESIDENZA
18
DATA
DATA
Notate che i record sono ordinati per la chiave
RICERCA SEQUENZIALE DI
UN RECORD NEL FILE
Input: valore della chiave da cercare.
 While c’e’ un record la leggere
– leggi record corrente
– if chiave-corrente = chiave da cercare
then STOP

RICERCA SEQUENZIALE DI
UN RECORD NEL FILE
Quante letture/confronti dobbiamo fare in media
per trovare il record voluto se ce ne sono N nel
file?
 Se il record cercato e’ il primo, 1 lettura/confr.
 Se il record cercato e’ il secondo, 2 letture/conf.
 …..
 Se il record cercato e’ l’ultimo, N letture/confr.
 In media: (1+2+…+N)/N = (N+1)/2 ~ N/2

RICERCA DICOTOMICA DI
UN RECORD NEL FILE
Input: valore della chiave da cercare.
 While c’e’ ancora un record da selezionare

– Seleziona il record a meta’ del file
– if chiave selezionata = chiave da cercare
then STOP
else if chiave selezionata > chiave da cercare
then ripeti tutto usando la prima meta’ del file
else ripeti tutto usando la 2a meta’ del file
RICERCA DICOTOMICA DI
UN RECORD NEL FILE
Quante letture/confronti dobbiamo fare al
massimo con una ricerca dicotomica?
 Ad ogni record selezionato, se questo non e’
quello voluto, la porzione di file in cui cercare si
dimezza.
 Dato un elenco di N elementi, quante volte
possiamo dividerlo per 2? Log2N

RICERCA DICOTOMICA DI
UN RECORD NEL FILE
Quindi la ricerca dicotomica e’ piu’ efficiente di
quella sequenziale, perche’ dobbiamo fare
meno letture/confronti per trovare il record
desiderato.
 Pero’ la ricerca dicotomica funziona solo se i
record del file sono ordinati secondo la chiave

4 7 9 18 24 32 57 58 88 97 101 103 125