Macchine Astratte
(anche dette Macchine Virtuali)
Corso: Architettura degli Elaboratori
Docente: Franco Barbanera
Lucidi by G.Bella (modificati by F.Barbanera)
UNIVERSITA’ DI CATANIA
Dip. di Matematica e Informatica
Cosa significa “computare”?
3+5
F. Barbanera, G. Bella
computazione
2
8
Macchine Astratte v.2.2
Genericamente:
output
input
procedimento effettivo
Computazione e’ una trasformazione di informazione da
una forma implicita ad una esplicita,
mediante una sequenza di passi computazionali unitari.
Buono, ma troppo generico
F. Barbanera, G. Bella
3
Macchine Astratte v.2.2
Modello Computazionale
Un modello computazionale fornisce
una formalizzazione delle nozioni di
• informazione
• passo computazionale unitario
Un modello computazionale e’ quindi una
definizione piu’ concreta di computazione.
F. Barbanera, G. Bella
4
Macchine Astratte v.2.2
Alcuni modelli computazionali
Gödel, basato sulla logica
Church, basato sul calcolo di funzioni
Post, basato sulla manipolazione di
stringhe di caratteri
Turing, basato su una macchina con un
nastro e una testina
…
F. Barbanera, G. Bella
5
Macchine Astratte v.2.2
Il modello computazionale
di Alan Turing (1936):
La Macchina di Turing (TM)
composta da
un nastro infinito, suddiviso in celle, ciascuna capace di
contenere un qualunque simbolo di un alfabeto
una testina movibile, capace di leggere e/o scrivere un simbolo in
una cella
un controllo finito, che memorizza lo stato corrente
un insieme di quintuple
Una quintupla (istruzione) descrive cosa deve scrivere la testina e
dove spostarsi (dx o sx) quando la testina legge un certo simbolo
e si è in un certo stato corrente .
F. Barbanera, G. Bella
6
Macchine Astratte v.2.2
Modello Computazionale
di Turing
• informazione rappresentata da una lista di
simboli (contenuti nel nastro)
• passo unitario di computazione come
“esecuzione” di una quintupla.
F. Barbanera, G. Bella
7
Macchine Astratte v.2.2
TM alla base della
programmazione imperativa
La Macchina di Turing introduce gli elementi essenziali
della moderna programmazione imperativa:
locazione –
assegnamento –
memoria –
stato –
iterazione –
F. Barbanera, G. Bella
8
Macchine Astratte v.2.2
Church: Il Lambda-calcolo
Il lambda calcolo è un altro modello
computazionale, basato sui concetti di
- Variabile (in senso matematico)
- Applicazione
- Astrazione funzionale
- Ricorsione
E’ alla base della
Programmazione Funzionale (Lisp, Haskell, ML)
F. Barbanera, G. Bella
9
Macchine Astratte v.2.2
Verso una definizione di
macchina basata sui concetti
introdotti dalle TM, ma non
eccessivamente essenziale.
F. Barbanera, G. Bella
10
Macchine Astratte v.2.2
Macchina Astratta (Imperativa)
E’ un insieme di algoritmi e strutture dati in grado
di memorizzare ed eseguire programmi.
memoria
operazioni primitive
operazioni e strutture dati per gestire il
trasferimento dati, ossia leggere gli operandi e
memorizzare i risultati delle istruzioni
operazioni e strutture dati per gestire il
controllo di sequenza, ossia l’ordine di
esecuzione delle operazioni del programma
interprete per l’esecuzione del programma
F. Barbanera, G. Bella
11
Macchine Astratte v.2.2
Osservazioni
Precisa corrispondenza fra macchine astratte
(imperative) e linguaggi di programmazione
(imperativi). IMPORTANTE!!!
Modelli computazionali diversi conducono a
nozioni diverse di macchine astratte
La maggioranza delle architetture concrete
sono realizzazioni di macchine astratte
imperative (per ragioni tecnologiche)
F. Barbanera, G. Bella
12
Macchine Astratte v.2.2
Struttura di una
Macchina Astratta
F. Barbanera, G. Bella
13
Macchine Astratte v.2.2
Architettura di Van Neumann
E’ la struttura delle realizzazioni fisiche
di Macchine astratte imperative
La CPU (Central Processing Unit) interpreta il Programma
e legge i Dati dalla RAM (Random Access Memory).
F. Barbanera, G. Bella
14
Macchine Astratte v.2.2
L’ Interprete
E’ preposto all’esecuzione dei
programmi
Coordina il funzionamento delle altre
componenti, allo scopo di eseguire un
ciclo FETCH/EXECUTE continuamente
fino all’esecuzione dell’istruzione
primitiva HALT
F. Barbanera, G. Bella
15
Macchine Astratte v.2.2
mediante operazioni e
strutture dati per gestire
il controllo di sequenza
mediante operazioni e
strutture dati per gestire il
trasferimento dati
operazioni primitive
L’algoritmo
Interprete
F. Barbanera, G. Bella
16
Macchine Astratte v.2.2
Esempio di Macchina Astratta
- macchina tradizionale -
memoria: vettore indicizzato di stringhe
binarie
operazioni primitive: aritmetico-logiche su
stringhe di bit
trasferimento dati: modalita’ per indirizzare la
memoria
controllo di sequenza: registro contatore
istruzioni (PC) ecc.
F. Barbanera, G. Bella
17
Macchine Astratte v.2.2
Esempi di macchine astratte
lavatrice
calcolatrice
JVM (Java Virtual Machine)
ristorante
…
F. Barbanera, G. Bella
18
Macchine Astratte v.2.2
Esempio di Macchina Astratta
- ristorante -
memoria: taccuini dei camerieri (input),
dispensa (dati), tavole imbandite (output)
operazioni primitive: varie capacita’ culinarie
dell’insieme dei cuochi
trasferimento dati: regole per trasferimento
ingredienti dalla dispensa ai cuochi
controllo di sequenza: ordine di arrivo delle
ordinazioni ai cuochi, ordine di utilizzo degli
ingredienti di una ricetta
interprete: camerieri
F. Barbanera, G. Bella
19
Macchine Astratte v.2.2
E l’ Input/Output ?
Fra le componenti di una Macchina Astratta, non abbiamo
incluso le strutture dati e gli algoritmi per la gestione
dell’ Input/Output.
Difficilmente esse possono essere generalizzate,
ma volendo, si potrebbe.
F. Barbanera, G. Bella
20
Macchine Astratte v.2.2
Il Linguaggio Macchina
Si consideri una Macchina Astratta M
LM, il linguaggio macchina di M, e’ il
linguaggio in cui si esprimono tutti i
programmi eseguibili da M
LMEST, il linguaggio macchina esteso di M,
e’ un linguaggio di stringhe di caratteri
direttamente traducibili in LM
Esempio: un programma in LM e’ una sequenza
di vari livelli di tensione per i bit di una memoria
fisica; l’equivalente in LMEST e’ un insieme di
stringhe di 0 e di 1.
F. Barbanera, G. Bella
21
Macchine Astratte v.2.2
Il Linguaggio Macchina
LM e’ il linguaggio in cui i programmi eseguibili da
M vengono rappresentati internamente
LMEST e’ il linguaggio in cui i programmi eseguibili
da M vengono rappresentati esternamente
Il medesimo oggetto programma astratto puo’
essere rappresentato in ambedue i linguaggi.
Quindi non faremo differenza fra i due linguaggi.
Il LOADER carica un programma in LMEST, lo traduce in LM e lo carica nella memoria della macchina.
F. Barbanera, G. Bella
22
Macchine Astratte v.2.2
Un binomio inscindibile
Data una macchina astratta,
resta definito il linguaggio di
programmazione che e’ il suo
linguaggio macchina
Dato un linguaggio di
programmazione, resta definita
la macchina astratta che lo
cuoco
abbia come suo
linguaggio macchina
spaghetti,
insalata, …
F. Barbanera, G. Bella
23
Macchina
astratta M
Linguaggio
LM
lavabiancheria
delicato,
colori,forte…
Macchine Astratte v.2.2
Complessita’
In virtu’ del binomio visto, si puo’ affermare che
la complessita’ di una macchina dipende dalla
complessita’ del suo linguaggio, e viceversa.
Esempio 1.
Si supponga che LM preveda il tipo astratto LISTA.
Allora, M deve contenere operazioni elementari per
realizzare Head, Tail, Length, …
ed algoritmi per l’allocazione dinamica della memoria
per le liste.
Esempio 2. Si pensi a un moderno HLL (high-level language)
F. Barbanera, G. Bella
24
Macchine Astratte v.2.2
L’hardware:
la realizzazione fisica di una MA
Oggi, e’ tecnicamente possibile realizzare una
macchina astratta associata ad un linguaggio di
alto livello.
Due degli inconvenienti derivanti sarebbero:
- costi della realizzazione
- scarsa flessibilita’ della macchina ottenuta
Quindi, in pratica, solo macchine astratte piuttosto
semplici vengono realizzate in hardware.
F. Barbanera, G. Bella
25
Macchine Astratte v.2.2
Alternative?
In generale, come implementare una Macchina
Astratta M ?
Esistono 3 realizzazioni:
• hardware : realizzare M fisicamente
• interpretativa : emulare M mediante una
macchina gia’ realizzata
• compilativa : tradurre il linguaggio di M in
quello di una macchina gia’ realizzata
F. Barbanera, G. Bella
26
Macchine Astratte v.2.2
Realizzazione Interpretativa
Sia M la Macchina Astratta da realizzare.
Sia M’ una MA gia’ realizzata.
(M’ e’ detta macchina ospite)
Si realizzano tutti gli algoritmi e le strutture dati
che definiscono le componenti di M mediante
programmi e strutture dati di LM’.
Se questi ultimi sono memorizzati in una memoria
ad alta velocita’, di sola lettura, sullo stesso chip
contenente le altre componenti di M’, si parla di
interpretazione via firmware.
F. Barbanera, G. Bella
27
Macchine Astratte v.2.2
Realizzazione Compilativa
Come nel caso precedente, sia M la Macchina
Astratta da realizzare, e sia M’ la macchina ospite.
Si traduce l’intero programma scritto in LM in un
programma funzionalmente equivalente scritto in
LM’.
Tale traduzione e’ eseguita dal compilatore.
Le componenti di M in realta’ non vengono
realizzate, ma l’utente ugualmente godra’ delle
funzionalita’ di M.
F. Barbanera, G. Bella
28
Macchine Astratte v.2.2
Nasce un problema…
Come calcolare 3+5
mentre si dispone di una macchina fisica che
puo’ solo incrementare un numero binario?
C’e’ una differenza di potenza espressiva fra le
due macchine (tra i due linguaggi).
In generale, la differenza di potenza espressiva
fra la Macchina Astratta da realizzare e la
macchina ospite esistente, e’ detta semantic gap.
F. Barbanera, G. Bella
29
Macchine Astratte v.2.2
Efficienza della realizzazione
Spesso il semantic gap e’ cosi’ ampio che sia
l’interpretazione che la compilazione potrebbero
risultare inefficienti (M sarebbe lenta).
Con l’interpretazione, l’interprete di M e’
realizzato da un programma in LM’, eseguito
dall’interprete di M’
Con la compilazione, il programma in LM’
potrebbe avere dimensioni enormi, e quindi
essere lento; il compilatore stesso e’ molto
complicato se LM ed LM’ sono molto diversi
Pertanto, si e’ pensato a delle macchine intermedie…
F. Barbanera, G. Bella
30
Macchine Astratte v.2.2
Singola macchina
intermedia
M
programma
in LM
compilazione
Mi
interpretazione
programma
in LMi
Mi va progettata in modo da massimizzare
• compattezza del codice in LMi prodotto
• velocita d’interpretazione di Mi su M’
F. Barbanera, G. Bella
31
M’
programma
in LM’
Macchine Astratte v.2.2
Esperienze pratiche
Mi e’ tipicamente solo un’estensione di M’ poiche’ ne
usa il medesimo interprete, potenziato con un
insieme di routine dedicate dette run-time system
Java si basa sullo schema appena visto: Mi e’ la JVM
(Java Virtual Machine); LMi e’ detto Bytecode; il runtime system e’ detto Java RunTime Environment
Tutte le combinazioni
compilazione/interpretazione sono possibili!!!
La singola macchina viene generalizzata a piu’
macchine intermedie all’uopo di maggior flessibilita’
del sistema
F. Barbanera, G. Bella
32
Macchine Astratte v.2.2
Una gerarchia di macchine
F. Barbanera, G. Bella
33
Macchine Astratte v.2.2
Osservazione
Alcune componenti di una macchina possono
essere identiche ad altrettante della macchina
ospite.
Esempio. Si immagini di poter utilizzare in C alcune
routine per l’aritmetica binaria.
Esempio schematico. Ciascun
linguaggio ha componenti precipue
(interpretate o compilate nei livelli
inferiori) ed altre ereditate immutate.
F. Barbanera, G. Bella
34
Macchine Astratte v.2.2
Tipica gerarchia di macchine
in un moderno calcolatore
Il
passaggio
a ciascun
livello
intermedio
colma una
parte del
semantic
gap.
F. Barbanera, G. Bella
35
Macchine Astratte v.2.2
Livello 0 – logica digitale
Componenti fondamentali sono le porte logiche
(GATES ).
Le porte logiche sono dispositivi analogici, ma fanno
da tramite verso quelli binari (e quindi digitali)
perche’ realizzano funzionalita’ (Not, And, Or, …)
formalizzabili mediante una teoria binaria detta
Algebra di Boole.
Combinando variamente le porte logiche, si
otterranno i registri, le memorie, le ALU.
F. Barbanera, G. Bella
36
Macchine Astratte v.2.2
Livello 1 - microprogrammazione
Componenti fondamentali sono registri e circuiti
digitali che realizzano varie funzionalita’
aritmetico-logiche.
Troviamo anche il datapath, le memorie, l’IFU
(Instruction-Fetch Unit).
Nasce il concetto di flusso di informazione poiche’
sequenze di bit viaggiano da una componente
all’altra della Macchina Astratta di questo livello,
venendo eventualmente elaborate.
F. Barbanera, G. Bella
37
Macchine Astratte v.2.2
Livello 2 – istruzioni macchina
Livello cui ci si riferisce quando si parla di
linguaggio macchina.
Istruzioni tipiche sono: ADD, MOVE, SUB, etc…
Tale livello e’ direttamente implementato in
hardware nel caso delle architetture RISC, mentre
e’ realizzato mediante interpretazione firmware
nelle architetture CISC.
F. Barbanera, G. Bella
38
Macchine Astratte v.2.2
Livello 3 – sistema operativo
Esso non copre del tutto il livello sottostante.
Molte istruzioni del 2 sono disponibili insieme a
nuove, piu’ evolute funzionalita’:
• FILE e FILE SYSTEM – la prima organizzazione
strutturata e gerarchica delle informazioni
• MEMORIA VIRTUALE – la macchina offre
un’enorme quantita’ di memoria in piu’ rispetto
a quella fisica
• PROCESSI e MULTITASKING – piu’ pezzi di
programma in esecuzione indipendente e
pseudo-parallela
F. Barbanera, G. Bella
39
Macchine Astratte v.2.2
Livello 4 – assembly
E’ il primo a presentare alcune caratteristiche
elementari di un linguaggio di programmazione
(etichette, variabili globali, procedure,…)
E’ realizzato mediante compilazione. Il
compilatore si chiama assembler.
L’assembler e’ tipicamente scritto in istruzioni
macchina (di livello 2).
F. Barbanera, G. Bella
40
Macchine Astratte v.2.2
Livello 5 – HLL
I moderni linguaggi di programmazione si
posizionano a questo livello.
Esistono varianti sia interpretative che compilate
di certe macchine di questo livello.
(Ad esempio, quella il cui linguaggio e’ il BASIC)
Osservazione 1. La JVM si sta consolidando fra i
livelli 4 e 5.
Osservazione 2. I livelli descritti sono solo una
possibile strutturazione gerarchica di un sistema.
F. Barbanera, G. Bella
41
Macchine Astratte v.2.2
Al di sotto della logica digitale
Possiamo individuare almeno 2 livelli:
• livello -1 – elettronica circuitale; si combinano i
dispositivi di base (transistor, diodi, etc…) per
ottenere le porte logiche
• livello -2 – fisica dello stato solido; si sfrutta la
struttura fisica dei solidi e le proprieta’ dei
semiconduttori per realizzare dispositivi di base
Servono da tramite fra i fenomeni fisici e le
tecniche per l’automazione del calcolo.
Immaginare delle Macchine Astratte a tali livelli
sarebbe pura speculazione.
F. Barbanera, G. Bella
42
Macchine Astratte v.2.2
Programmazione
e livelli di astrazione
Un programma scritto in un HLL aggiunge un livello
alla gerarchia.
Esso estende la Macchina Astratta associata all’HLL
con nuove strutture dati e nuove operazioni.
Quindi, la potenza di un HLL si puo’ misurare coi
meccanismi di astrazione che esso offre.
Nessun linguaggio al momento estende il controllo
di sequenza, del trasferimento dei dati, o la gestione
della memoria.
F. Barbanera, G. Bella
43
Macchine Astratte v.2.2
ATTENZIONE!!!
In un sistema di calcolo non c’e’ limite
ai livelli di MA presenti.
Non tutti i sistemi di calcolo hanno il
livello microprogrammato (CISC con,
RISC senza)
F. Barbanera, G. Bella
44
Macchine Astratte v.2.2