Informatica Appunti Test PDF

Preview

Summary

Download Informatica Appunti Test PDF

Description

- THREAD - CONCETTO DI THREAD Multithreading → possibilità di far eseguire più applicazioni contemporaneamente ad un computer. Multithreading Java → possibilità di eseguire più attività contemporaneamente alla JVM. Thread → frammento, flusso di programma eseguito concorrentemente all’interno di un processo. Thread Java → oggetto che porta avanti una singola computazione sequenziale, idealmente è associato ad un processore virtuale che utilizza parte della memoria condivisa tra i thread della JVM. Multiprocessore → più processi condividono la memoria centrale. Thread della JVM al lancio di un’applicazione standalone: - thread main del programma - thread garbage collector (recupera la memoria inaccessibile e la mette a disposizione dei thread) Classe Thread → ogni thread è visto come un’istanza di questa classe, che possiede il metodo statico currentThread() che restituisce il thread associato al codice in esecuzione. - CREAZIONE DI THREAD Thread main → creato implicitamente quando diamo il comando java. Class extend Thread: public class MyThread extends Thread{ //attributi //costruttore public void run(){ //operazione che MyThread deve svolgere } } public class Main{ public static void main(String[] args){ MyThread t1 = new MyThread(); t1.start(); } } Class implements Runnable: public class MyThread implements Runnable{ //attributi //costruttore @Override public void run(){ //operazione che MyThread deve svolgere } } public class Main{ public static void main(String[] args){ MyThread mt1 = new MyThread(); Thread t1 = new Thread(mt1); t1.start(); } } ● Metodo start() → viene invocato per far partire .un Thread, richiama il metodo run() della classe che estende Thread o implementa Runnable. Quando viene invocato si avvia il

processore virtuale distinto da quello che porta avanti il thread contenente la chiamata start(). La chiamata a start() viene definita asincrona: chi la effettua non deve attendere la sua terminazione e può essere effettuata solo oggetti attivi. - SINCRONIZZAZIONE DEI THREAD E ATOMICITÀ Sincronizzazione delle attività concorrenti → imporre delle pause ai processori virtuali per il tempo necessario a far sì che le operazioni vengano eseguite senza interferenze, producendo gli stessi risultati che sarebbero prodotti se le attività fossero eseguite sequenzialmente. Atomicità → caratteristica che permette di vedere una successione di operazioni come un’unica istruzione che deve essere eseguita del tutto o non deve essere eseguita per niente. Sequenza di interleaving → sequenza di azioni elementari. Sincronizzare metodi o istruzioni → permette di risolvere la problematica che si presenta quando due o più thread sono in competizione per l’utilizzo di una risorsa. Synchronized istruzione: synchronized (oggetto) istruzione; //es. synchronized (ogg) ogg.metodo(); Synchronized metodo: synchronized tipo nomeMetodo(){ //operazioni metodo } //es. synchronized void metodo(){...} Monitor → oggetto che contiene metodi sincronizzati e quindi concentra in un’unica classe tutte le operazioni che devono essere eseguite in modo atomico. Ad ogni monitor è associato un semaforo che garantisce la mutua esclusione. Solo un thread alla volta può possedere il monitor fino al termine dell’esecuzione del metodo. - SINCRONIZZAZIONE SU CONDIZIONI: wait e notify Attesa su una condizione → concetto che esiste nella programmazione concorrente, richiede un’attesa fino al verificarsi di una determinata condizione. In Java si traduce con: while(!condizione){ try{ wait(); }catch(InterruptedException e){e.printStackTrace();} } Comandi della classe Object per la sincronizzazione tra thread: wait()

attende che qualche altro thread, che usa questo stesso oggetto condiviso, esegua una notify() o una notifyAll()

notify()

risveglia uno dei thread messi in attesa, su questo stesso oggetto condiviso, con una wait()

notifyAll()

risveglia tutti i thread messi in attesa, su questo stesso oggetto condiviso, con una wait()

Priorità di un thread → può essere cambiata con il comando setPriority() che consente di alzare o abbassare la priorità di default (normale). Thread dispone di tre livelli di priorità: - MIN_PRIORITY - NORM_PRIORITY - MAX_PRIORITY Metodo yield() → permette di variare la priorità di un thread, fa abbandonare la CPU al

thread corrente e la assegna ad un altro thread avente la stessa priorità. //es. Thread.yield(); - STATI DI UN THREAD schedulatore a seguito di una notify() notifyAll() PRONT O new

start( )

schedulator e yield() preemptio n

NUOV O

TERMINAT O

● ● ● ●

SOSPES O wait() sleep(n ) t.join( )

ESECUZION E

terminazione run()

Thread creato → stato di NUOVO Thread invoca il metodo start() avvia il metodo run() → stato PRONTO Lo schedulatore decide di assegnare la CPU all’esecuzione del thread → stato ESECUZIONE Il thread può abbandonare la CPU in vari modi: ○ termina il metodo run() il thread risulta !isAlive() → stato TERMINATO ○

si porta nello stato SOSPESO per i seguenti motivi: ■ per effetto di una wait() ■ per effetto di una sleep(tempo) ■ per effetto di una t.join(), operazione che consente di attendere la terminazione di un altro thread t ■ eseguendo il metodo yield()

per preemption, la JVM forza l’abbandono della CPU da parte del thread in esecuzione a favore di un thread con priorità più alta o uguale Dallo stato di BLOCCATO il thread attende un risveglio che lo riporti in stato di PRONTO: ○ una notify() o una notifyAll() ○ terminazione del tempo di sleep(tempo) ■

●

○

terminazione del thread t su cui era stata invocata una t.join()

- STALLO E STARVATION Stallo e starvation → problemi caratteristici della programmazione concorrente. Stallo → stato in cui nessun thread può avanzare a causa degli altri. Starvation → un thread attende indefinitamente una risorsa che gli viene sottratta dagli altri thread. Può capitare in presenza dell’assegnazione di diverse priorità ai thread.

- DESIGN PATTERN- CONCETTO DI DESIGN PATTERN Design pattern→ soluzione ad un problema di progettazione, traccia risolutiva per un problema ricorrente nella progettazione ad oggetti. Si tratta di schemi da adattare ai casi concreti che si presentano. - CATEGORIE DI DESIGN PATTERN Design pattern per la CREAZIONE → (creational patterns) offrono soluzioni a problemi relativi alla creazione degli oggetti. Si occupa di rendere un’applicazione indipendente da come i suoi oggetti vengono creati, composti e rappresentati. Esempio: Singleton. Design pattern per la STRUTTURAZIONE → (structural patterns) offrono soluzioni a problemi di strutturazione degli oggetti e delle classi. Si occupa di come costruire da oggetti piccoli, oggetti più grandi o inglobati da altri. Esempio: Composite. Design pattern per il COMPORTAMENTO → (behavioral patterns) offrono soluzioni relative agli aspetti algoritmici e di attribuzione delle responsabilità degli oggetti. Esempio: Iterator.

- ITERATOR- CONCETTO DI ITERATORE Iteratore → soluzione ad un problema di progettazione per non violare il principio di information hiding della programmazione ad oggetti. Un iteratore è un oggetto che consente di attraversare un contenitore (visitare tutti gli elementi di un contenitore con un ciclo) senza fare alcun riferimento alla rappresentazione del contenitore né alle operazioni del contenitore. Ciclo base di un iteratore: it //iteratore per attraversare il contenitore while(it.inside()){ //se ci sono ancora elementi da visitare it.current(); //visita dell’elemento puntato it.goNext(); //rendi corrente il prossimo dato }

Attributi nascosti dell’iteratore: - un puntatore al contenitore che sta attraversando - un cursore che dipende dalla rappresentazione del contenitore e che serve per identificare ed accedere ad un particolare elemento del contenitore. Interfaccia Iteratore: public interface Iteratore{ boolean inside(); //verifica se il cursore è nel contenitore /*presenta all’interno una condizione che verifica inside()*/ Object current(); //ritorna l’elemento indicato dal cursore void goFirst(); //porta il cursore sul primo elemento /*presenta all’interno una condizione che verifica inside()*/ void goNext(); //porta il cursore sul prossimo elemento }

-

-

le operazioni current() e goNext() - hanno inside() come precondizione - non sono lecite se il contenitore è vuoto o se il cursore si trova fuori dal contenitore per effetto di un goNext() per usufruire dell’interfaccia Iteratore è necessario implementare una classe IteratoreConcreto

Classe IteratoreConctreto → implementa l’interfaccia Iteratore

Classe ContenitoreConcreto → implementa il metodo newIterator() per creare e restituire un’istanza di IteratoreConcreto Esempio attraversamento con while utilizzando queste strutture: Iteratore it = contenitore.newIterator(); it.goFirst(); //chiamata non necessaria se il costruttore posiziona //il cursore sul primo elemento del contenitore while(it.inside()){ it.current(); it.goNext(); }

Esempio attraversamento con for utilizzando queste strutture: for(Iteratore it = contenitore.newIterator(); it.inside(); it.goNext()){ it.current(); }

Interfaccia Attraversabile: public interface Attraversabile(){ Iteratore newIterator(); }

-

ha lo scopo di obbligare tutti i contenitori ad usare lo stesso nome per creare l’istanza di un iteratore il grado di generalità raggiunto è notevole grazie al polimorfismo per sapere se esiste un elemento x in un contenitore a che implementa l'interfaccia Attraversabile si potrà utilizzare sempre la seguente funzione: public boolean esisteInfo(Attraversabile a, Object x){ boolean trovato = false; for(Iteratore it = a.newIterator(); !trovato && !inside(); it.goNext()){ trovato = x.equals(it.current()); } return trovato; }

Esercizio di esempio con l’utilizzo delle interfacce Iteratore e Attraversabile: public class PilaAttraversabile extends Pila implements Attraversabile{ public PilaAttraversabile(){} public IteratorePila newIterator(){ return new IteratorePila (this); } } public class IteratorePila implements Iteratore{ Pila pilaDaAttraversare; NodoConc cursore; public IteratorePila(Pila p){ pilaDaAttraversare = p; goFirst(); } public boolean inside(){ return cursore != null; public Object current(){ if(!inside) throw new RuntimeException(“cursore fuori”); return cursore.info; } public void goNext(){ if(!inside) throw new RuntimeException(“cursore fuori”); cursore = cursore.next; } public void goFirst(){ cursore = pilaDaAttraversare.ultimo; } }

- ATTRAVERSAMENTI MULTIPLI Attraversamenti multipli→ utilizzando due o più iteratori contemporaneamente per scorrere

un unico contenitore, non si ottengono i risultati sperati. Non è quindi possibile fare più attraversamenti indipendenti e contemporanei sperando di ottenere i risultati corretti. - PROBLEMI DEGLI ITERATORI Non modificare un contenitore durante un attraversamento → gli effetti causati da una modifica al contenitore in fase di attraversamento sono imprevedibili e pericolosi per il funzionamento del programma. Altre problematiche: - inserimento di elementi in fase di scorrimento - effetti più gravi se due thread condividono lo stesso contenitore - ITERATORI DELLA LIBRERIA STANDARD DI JAVA Interfacce Java a supporto del concetto di iteratore → messe a disposizione dal package java.util - java.util.Enumeration: interface Enumeration → soluzione obsoleta - java.util.Iterator: - interface Iterator → soluzione migliore offerta da Java Interfaccia Iterator di Java: interface Iterator{ boolean hasNext(); //vero se esiste il successivo Object next(); //restituisce elemento corrente e va a successivo void remove() throws UnsupportedOperationException; }

Esempio utilizzo Iterator di Java: Iterator it = contenitore.iterator(); while(it.hasNext()){ Object x = it.next(); }

Interfaccia ListIterator di Java → più estesa della Iterator, può essere implementata per qualsiasi contenitore e non solo per le liste, utile quando si presenta la necessità di attraversare un contenitore in entrambe le direzioni. operazioni di java.util.ListIterator boolean hasNext() Object next() int nextIndex() boolean hasPrevious() Object previous()

vero se esiste un elemento successivo restituisce il corrente e scorre avanti indice dell’elemento successivo vero se esiste un elemento precedente restituisce il corrente e scorre indietro

int previousIndex()

indice dell’elemento precedente

void add(Object x)

(opzionale) inserisce x nella lista

void remove()

void set(Object x)

(opzionale) cancella l’ultimo elemento restituito da una next() o da una previous() (opzionale) sostituisce con x l’ultimo elemento restituito da una next() o da una previous()

- ITERATORI IMPLICITI E IL FOREACH Foreach → dà la possibilità di eseguire una elaborazione su tutti gli elementi di un

contenitore senza fare uso esplicito degli iteratori → necessario implementare l’interfaccia java.util.Iterable. Foreach di Java: for( : ) ; Esempio utilizzo foreach di Java: // c è un contenitore di interi int somma = 0; for (int x : c) somma += x;

- LISTE - LISTE ASTRATTE E CONCRETE Lista → è una lista vuota o una coppia informazione, detta testa della lista, e una lista, detta coda della lista. Liste astratte → si accede unicamente con le operazioni permesse: testa, coda… Liste concrete → rappresentazioni delle liste astratte, le più significative sono le liste concatenate. - LISTE CONCATENATE Liste concatenate → il legame tra un elemento ed il suo successivo viene realizzato attraverso un puntatore. E’ composta da tanti nodi concatenabili. Nodi concatenabili: class NodoConc{ Object info; NodoConc next; NodoConc(Object info, NodoConc next){ this.info = info; this.next = next; } }

- VISITA ITERATIVA DI UNA LISTA CONCATENATA While: NodoConc n = a; // a è il puntatore di accesso alla lista while(n != null){ n.info; n = n.next; }

For: for(NodoConc n = a; n != null; n = n.next){ n.info; }

Ricorsione: static void elaboraListaConc(NodoConc x){ if(x!null){ x.info; elaboraListaConc(x.next); } }

- NODI SENTINELLA Nodo sentinella → nodo inserito in testa il cui campo informazione non viene utilizzato. L’utilizzo di questi nodi rende più semplice l’implementazione di alcune soluzioni. - LISTE CIRCOLARI Liste circolari → non esiste un ultimo elemento, il campo next dell’ultimo elemento della lista

punta al primo elemento della lista. - LISTE DOPPIAMENTE CONCATENATE Liste doppiamente concatenate → utilizza due puntatori: uno all’elemento successivo, uno all’elemento precedente. Si possono utilizzare se è necessario poter scorrere la liste in tutti e due i versi.

- PILA ● ●

Politica LIFO → Last In First Out Operazioni: ○ push (x) → inserisci x nella pila ○ top () → restituisce l’elemento in cima alla pila senza rimuoverlo ○ pop () → toglie l’elemento in cima alla pila ○ isEmpty () → true se la pila è vuota

● ●

Politica FIFO → First In First Out Operazioni: ○ enqueue(x) → inserisci x nella coda ○ front() → restituisce l’elemento in testa alla coda senza rimuoverlo ○ dequeue() → toglie l’elemento in testa alla coda ○ isEmpty () → true se la coda è vuota

●

Coda doppia → è una struttura in cui è possibile inserire ed estrarre gli elementi da entrambe gli estremi della pila → viene fuori una struttura che può svolgere le funzioni di pila e di coda. LinkedList → Java mette a disposizione java.util.LinkedList che permette di svolgere le funzioni di pila e di coda. Ha i seguenti metodi: ○ addFirst(x) → come la push(x) ○ getFirst() → come la top() ○ removeFirst() → come la pop() ○ addLast() → come la enqueue(x) ○ getFirst() → come la front() ○ removeFirst() → come la dequeue() ○ isEmpty() → come la isEmpty() di pila e coda ■ add(int i, Object x): void → inserisce x in posizione i ■ add(Object x): boolean → appende x ■ remove(int i): Object → rimuove l’elemento in posizione i ■ clear(): void → cancella tutti gli elementi ■ set(int i, Object x): Object → imposta a x l’elemento in posizione i ■ get(int i): Object → restituisce l’elemento in posizione i ■ size(): int → ritorna il numero degli elementi

- CODA -

●...