Domande di teoria informatica

Domande di teoria informatica

Elaborazione e strutturazione dell'informazione

Calcolatori ed esecutori

Un esecutore è caratterizzabile in base alle sue capacità di interpretazione ed esecuzione: la soluzione deve essere interpretata in modo tale che il soggetto esecutore sia in grado di interpretarla in modo corretto e deve fare riferimento ad azioni che il soggetto esecutore sia in grado di attuare (sintattica, pragmatica e semantica).

Un calcolatore è uno strumento (esecutore) per l'elaborazione di dati caratterizzato da un linguaggio che è in grado di comprendere, capace di acquisire i dati, da delle azioni che è in grado di svolgere, cioè il processo che include elaborazione, archiviazione e comunicazione, ed è in grado di attuare soluzioni.

Il processo che porta alla soluzione di un problema è di natura logico-linguistico e possiede due aspetti: aspetto descrittivo, in cui il soggetto descrittore scompone il problema in sottoproblemi, fino ad arrivare a problemi elementari a cui corrispondono istruzioni elementari; aspetto esecutivo in cui il soggetto esecutore attua le azioni elementari, associate alle rispettive istruzioni elementari. È importante l'ordine in cui vengono eseguite le azioni.

Descrizione ed elaborazione di algoritmi

Un algoritmo è la descrizione della soluzione di un problema espressa in forma di un insieme di istruzioni che, operando sui dati iniziali, consentono di ottenere dei risultati che costituiscono la soluzione del problema; tali istruzioni sono determinate tramite la scomposizione iterativa del problema di partenza in sottoproblemi elementari, la soluzione di ogni sottoproblema è detta step, o passo, dell'algoritmo.

L'algoritmo può essere formulato per essere comunicato tra esseri umani, in questo caso si usa un linguaggio sintetico ed intuitivo, informale o semi-formale; oppure può essere formulato per essere eseguito direttamente, in questo caso deve essere preciso ed eseguibile, quindi scritto in un linguaggio formale, ossia comprensibile da esecutori automatici.

Un algoritmo deve essere corretto, cioè non deve difettare di alcun passo fondamentale, e deve essere efficiente, cioè deve pervenire alla soluzione del problema usando la minima quantità di risorse fisiche (tempo di esecuzione, memoria). Gli algoritmi sono parametrici, cioè il risultato dipende da una serie di dati di partenza.

Sviluppo di un programma

• Analisi del problema e identificazione di una soluzione
• Formalizzazione della soluzione e definizione dell'algoritmo risolutivo
• Programmazione, ossia scrittura della soluzione in linguaggio di programmazione ad alto livello
• Traduzione del programma in linguaggio macchina, ossia un linguaggio direttamente comprensibile dal calcolatore; vengono usati compilatori o interpreti

Le infrastrutture hardware

Calcolatore: definizione e funzione

Un calcolatore è costituito da un numero elevato di componenti, strutturato in forma gerarchica, cioè come un insieme di elementi che interagiscono tra di loro, ognuno dei quali a sua volta è costituito da elementi più semplici: ogni livello è caratterizzato dalla sua struttura e ogni componente è contraddistinto da una funzione, cioè dal compito da esso svolto nell'ambito della struttura complessiva del sistema.

Il calcolatore è un dispositivo polivalente cioè adattabile a diverse funzioni:

• Elaborazione dei dati: varia in base al tipo di applicazione e al tipo di dati da trattare
• Memorizzazione dei dati: sia per periodi brevi che per periodi lunghi
• Trasferimento dei dati da/verso l'esterno: un calcolatore deve essere in grado di comunicare con l'esterno sia per acquisire dati di input, sia per trasferire i risultati dell'elaborazione; questi compiti sono svolti da periferiche, rispettivamente di ingresso (input) e di uscite (output)
• Controllo: le operazioni dell'elaborazione, memorizzazione e trasferimento dati devono essere sottoposte a controllo, o da parte dell'utente, che attua operazioni di controllo esplicite, o in maniera automatica dall'unità di controllo del calcolatore.

Il calcolatore: modello di Von Neumann

Lo schema della macchina di Von Neumann è utilizzata per la progettazione e la realizzazione dei computer che usiamo tutti i giorni. Essa è costituita da più unità, strutturate in maniera gerarchica: la CPU, unità centrale, si occupa dell'elaborazione e del controllo; i microprocessori o i processori sono realizzati da tecnologie microelettroniche; la memoria centrale, ospita i dati necessari alla CPU per l'elaborazione di dati, può essere vista come un insieme di celle adiacenti, ognuna caratterizzata da un proprio indirizzo; le interfacce di input/output attraverso le quali il calcolatore interagisce con l'esterno; i BUS, responsabile del collegamento tra queste diverse unità, è una linea alla quale sono connesse contemporaneamente le unità del calcolatore, e che interagiscono tra loro sfruttando il concetto di master-slave: si tratta di un metodo di gestione efficace, che lascia alla CPU il ruolo di master, che gestisce l'intero sistema ed ha accesso al BUS, e tutte le altre unità sono “slave”, non possono accedere autonomamente al BUS.

Il BUS

Il BUS consente il collegamento tra le varie unità della CPU e fa parte dell'architettura di Von Neumann; le varie unità del calcolatore interagiscono tra loro sfruttando il concetto di master-slave.

Il Bus è caratterizzato da semplicità, estendibilità, tuttavia è lento, ha una limitata capacità che tende a far sovraccaricare la CPU. Il Bus può essere suddiviso in: BUS DATI, utilizzato per trasferire dati tra memoria e CPU o tra CPU e interfacce di I/O; BUS INDIRIZZI, identifica la posizione delle celle in memoria in cui la CPU legge o scrive; BUS DI CONTROLLO, in cui transitano segnali di controllo che consentono di selezionare di volta in volta le unità coinvolte nel trasferimento dati.

Struttura e funzionamento della CPU

La CPU è l'unità centrale di elaborazione, un dispositivo di tipo elettronico, lavora se ha a disposizione memoria da cui prendere i dati.

La CPU è a sua volta diviso in due unità fondamentali:

• Data Path: comprende dispositivi in grado di elaborazione effettivamente i dati; l'ALU, ossia l'unità aritmetico-logica, e alcuni registri, cioè unità di memorizzazione temporanea, in cui i dati vengono mantenuti per rendere più agevole la gestione (Data Register e Adress Register).
• Unità di controllo: coordina le operazioni di tutto il processore, anche quelle del data path; regola il flusso dei dati e indica quali registri debbano essere collegati agli ingressi e all'uscita dell'ALU; comprende registri di uso specifico che provvedono al prelievo dalla memoria di istruzioni da eseguire, come il PC (Program Counter) che conserva l'indirizzo dell'istruzione corrente, l'IR (Instruction Register) che conserva l'istruzione in esecuzione, e il PSW (Program Status Word), che si occupa della conservazione dei risultati delle operazioni svolte dall'ALU.

Funzioni della CPU

La CPU è in grado di eseguire istruzioni codificate in linguaggio macchina, seguendo un ciclo che segue questa sequenza di azioni:

• FETCH: prelevamento, consente di prelevare l'istruzione corrente dalla memoria, individuata dal PC, e spostarla nell'IR, incrementando contemporaneamente il PC, in modo che contenga l'indirizzo dell'istruzione successiva.
• DECODE: decodifica, determina il tipo di istruzione da eseguire e carica i dati, se necessario, in uno dei registri della CPU.
• EXECUTE: esecuzione, cioè esegue l'istruzione e torna al punto di partenza ed esegue l'istruzione successiva.

Architettura LOAD/STORE

L'architettura di riferimento della CPU è il LOAD/STORE, semplice, che si basa su alcuni principi: sia le operazioni possono essere eseguite solo su dati già caricati nei registri (load), sia l'operazione di archiviazione dei risultati dai registri alla memoria (store) devono essere previste esplicitamente.

Un processore con questo tipo di architettura deve essere in grado di svolgere tali operazioni: istruzioni aritmetico logiche, somma, sottrazione, maggiore, minore, uguale, and, or; controllo del flusso delle istruzioni, sequenza, salto condizionato (il salto dipende dal verificarsi di una condizione), o non condizionato (il salto non dipende dal verificarsi di una condizione); trasferimento di informazioni, da registri a memoria, e tra registri e dispositivi di ingresso e di uscita.

Esecuzione delle istruzioni

I primi due passi dell'esecuzione sono sempre gli stessi, cioè non dipendono dal tipo di istruzione:

• L'invio del contenuto del PC alla memoria che contiene le istruzione per prelevare quella corrente e trasferirla nell'IR, incrementando nel frattempo il PC, consiste nella fase di fetch.
• La lettura del contenuto di uno o due registri utilizzando pezzi dell'istruzione registrata nell'IR per selezionare i registri ai quali accedere.

Dopo questi due passi, le istruzioni comprese nelle diverse categorie completano l'esecuzione.

La memoria

La memoria fa parte dell'architettura di Von Neumann, svolge diverse funzioni: è di supporto alla CPU, cioè fornisce dati e istruzioni alla CPU il più rapidamente possibile; funge da archivio di dati e programmi, garantendo la conservazione e la reperibilità anche dopo lunghi periodi di tempo.

Per realizzare memorie si tiene conto delle varie esigenze, cioè elevate prestazioni a costi bassi, per questo la memoria è divisa in: memoria centrale, veloce e volatile, molto costosa, contiene solo programmi in esecuzione con i relativi dati, agisce principalmente in supporto della CPU; e la memoria di massa, lenta e non volatile, destinata a contenere dati e programmi, come archivio, meno costosa, memorizza i dati in modo permanente.

I parametri per la descrizione di una memoria sono:

• Volatilità: necessità o meno di alimentazione per memorizzare i dati
• Velocità di accesso: rapidità della memorizzazione di operazioni di lettura e scrittura
• Velocità di trasferimento dei dati: quantità di dati che la memoria riesce a trasferire nell'unità di tempo
• Capacità: numero di bit che possono essere memorizzati (misurati in multipli di Byte)
• Costo per bit: rapporto tra il costo dell'unità di memoria e la sua capacità espressa in bit.

Realizzazione di unità di memoria

La realizzazione delle unità di memoria si basa su tecnologie differenti:

• Memorie elettroniche: ad alta velocità, necessità di alimentazione, buona capacità, costo per bit elevato.
• Memorie magnetiche: bassa velocità, non necessità di alimentazione, basso costo per bit.
• Memorie ottiche: proprietà analoghe alle memorie magnetiche, utilizzano supporti riscrivibili, adatte alla distribuzione di grandi quantità di dati.

Memoria centrale

L'unità di memoria centrale fa parte dell'architettura di Von Neumann; per favorire elevate prestazioni a costi contenuti, la memoria è stata divisa in due categorie che svolgono funzioni diverse: la memoria centrale e la memoria di massa.

La memoria centrale usa una tecnologia elettronica ed è collocata esternamente alla CPU, anche se ha accesso diretto ad esso: è una memoria veloce, di supporto alla CPU, è in grado di mantenere i dati e le istruzioni al suo interno solo durante l'esecuzione dei programmi, è una memoria ad accesso casuale.

La memoria centrale è costituita da una successione ordinata di elementi binari, ciascuno capace di assumere uno stato tra due possibili, convenzionalmente 0 e 1; ciascun elemento di memoria è in grado di memorizzare un singolo bit, cioè elementi di memoria binari organizzabili in unità minime dette celle (tutte formate dallo stesso numero di bit).

Ogni cella ha un suo indirizzo che corrisponde alla sua posizione rispetto alla prima cella (che ha indirizzo 0), in una memoria di N celle gli indirizzi vanno da 0 a N-1.

La memoria centrale è costituita da due unità: RAM (Random Access Memory) memoria ad accesso casuale; ROM (Read Only Memory), memoria di sola lettura, utilizzata per contenere le informazioni di inizializzazione del calcolatore, usate ad ogni accensione.

La memoria centrale, dal punto di vista dell'esecuzione delle istruzioni, è monolitica, cioè vi si accede tramite la linea Bus: il bus indirizzi trasferisce gli indirizzi delle celle cui si vuole accedere, sulle linee del bus dati vengono trasmessi i dati, il bus di controllo specifica il tipo di operazioni richieste, di lettura o scrittura.

Criteri per la valutazione delle memorie

I criteri per la valutazione delle prestazioni delle unità di memoria sono:

• Tempo di accesso: intervallo tra il momento in cui una richiesta di acceso viene presentata alla memoria della CPU e l'istante in cui la memoria termina il compito rendendo disponibile il dato da leggere o garantendo la stabilità del dato scritto.
• Ciclo di memoria: somma del tempo di accesso e dell'intervallo di tempo che deve trascorrere prima che possa iniziare un successivo accesso alla memoria; generalmente viene espresso in numero di accessi possibili dalla CPU in unità di tempo.
• Velocità di trasferimento: corrisponde alla quantità di dati trasferiti nell'unità di tempo da o verso la memoria.

Metodo di accesso delle memorie

• Sequenziale: le celle, dette record in questo caso, sono poste una accanto all'altra e l'accesso ad un dato comporta la lettura di tutti quelli che lo precedono (CD, DVD)
• Diretta o casuale: consente di selezionare un dato indipendentemente dagli altri; la memoria centrale è una memoria ad accesso casuale (RAM)
• Accesso misto: l'accesso al dato viene portato a termine compiendo diversi accessi per giungere in prossimità del dato, e poi viene effettuata una ricerca sequenziale (DISCHI MAGNETICI)
• Associativa: è un metodo di accesso casuale che permette di effettuare un confronto tra alcuni bit in posizioni specifiche all'interno di una parola di memoria per verificare l'uguaglianza con una parola di riferimento (MEMORIE CACHE)

Organizzazione gerarchica della memoria

Il sistema complessivo di memorizzazione sfrutta le caratteristiche delle diverse tecnologie disponibili combinando le varie unità di memoria in una gerarchia, per ottimizzare le prestazioni e, contemporaneamente, riducendo i costi.

Abbiamo dunque due livelli adiacenti di memoria: la MPV, memoria piccola e veloce, e MGL, memoria grande e lenta. La MPV contiene una copia di alcune celle di memoria della MGL, i dati sono memorizzati in blocchi di dimensioni prefissate, che vengono trasferiti nelle diverse unità di memoria come se fossero delle unità indivisibili.

Quando la CPU richiede una particola cella di memoria la richiesta va ad entrambe: se il dato si trova nella MPV, va direttamente nella CPU, se si trova nella MGL, viene caricato anche nella MPV. La gerarchia di memoria sfrutta il principio di località: afferma che le informazioni usate più recentemente e quelle in posizioni contigue verranno probabilmente usate nel prossimo futuro, favorendo l'accesso a tali informazioni si migliorano le prestazioni complessive del sistema; vi sono diversi tipi di approcci a seconda della località: la località spaziale, quando vengono copiati dati dalla MGL alla MPV, si copiano anche i dati vicini (cache line o blocco); località temporale, quando vengono prelevati i dati dalla MGL vengono conservati nella MPV il più a lungo possibile.

La frequenza di successo (hit ratio – h) è tale da superare in certi casi il 90%, in effetti essa dipende da due caratteristiche contrastanti: la dimensione dei blocchi, poiché un blocco grande sfrutta meglio la località spaziale, e il numero di blocchi in memoria, più blocchi ci sono, un dato resta in memoria più a lungo sfruttando il principio di località.

Memoria di massa

I dispositivi di memoria di massa sono dispositivi ausiliari, non utilizzabili direttamente per l'esecuzione di programmi da parte della CPU, ma utilizzati per la memorizzazione di dati in modo permanente. Sono caratterizzati dalla non volatilità, grande capacità e un costo per bit ridotto.