78
Corso di Sistemi di Elaborazione delle Informazioni Dott. Francesco Rossi a.a. 2019/2020 SCUOLA DI MEDICINA E CHIRURGIA Università degli Studi di Napoli Federico II 1
Corso di
Sistemi di Elaborazione delle Informazioni
Dott. Francesco Rossia.a. 2019/2020
SCUOLA DI MEDICINA E CHIRURGIA
Università degli Studi di Napoli Federico II
1
Il sistema operativo
2
Gestione dei processi
• Processo
• Si definisce processo (o anche job, task) una istanza di un certo Programma. Un processo è composto da una parte statica (le istruzioni) e da una parte dinamica (i dati)
3
Monotasking
Il sistema operativo permette l'esecuzione di un unico processo alla volta
Multitasking
Il sistema operativo permette l'esecuzione contemporanea di più processi
Gestione della memoria
• La memoria è una risorsa generalmente scarsa e va quindi suddivisa tra i vari processi in competizione
• Nella realtà, i sistemi operativi:
– fanno vedere ai processi una quantità di memoria maggiore (memoria virtuale) di quella centrale
– tengono in memoria centrale solo porzioni dei processi in competizione, mentre le restanti parti restano sulla memoria di massa 4
Gestione della memoria
• La gestione della memoria avviene utilizzando la tecnica della segmentazione o della paginazione
– segmentazione, la memoria è assegnata in segmenti
uguali alla parte di programma da caricare
– paginazione, la memoria è suddivisa in pagine di
dimensioni fisse
5
Gestione delle periferiche
• Per gestire una periferica, il sistema operativo utilizza i driver
– Deve esistere quindi un determinato driver per ogni
periferica da gestire
6
Gestione delle periferiche
• La gestione delle periferiche in un sistema multitasking è una attività «insidiosa» perché
– E’ necessario gestire correttamente errori di I/O
– E’ indispensabile adottare corrette politiche di
utilizzo affinché non si acceda a risorse attualmente
in uso da un altro processo
– non si verifichino situazioni di blocco irreversibile
7
Il file system
• Per organizzare la grande quantità di dati che possono essere stoccati nella memoria di massa, si ricorre a
– una unità astratta di memorizzazione detta file
– un contenitore di file detta directory
8
Il file system
• Il file system si occupa della gestione della memoria di massa.
– Il file system è strutturato ad albero
– Il percorso di un file è dato dalla concatenazione
delle varie directory (partendo dalla radice,
discendendo l'albero) e il nome del file
9
Il file system
10
L’interprete dei comandi
11
• L'interprete dei comandi è lo strumento più spartano per dialogare con il sistema operativo
– In Windows, l'interprete dei comandi è richiamabile lanciando il programma «COMMAND» o «CMD»
– In Linux/Unix, esistono vari interpreti dei comandi dotati di funzioni più o meno potenti (e.g., BASH)
Interfaccia grafica
12
• L'interfaccia grafica l'interazione con il sistema operativo.
• Attualmente, la metafora usata per la gestione dei processi è la finestra, le icone identificano i file e/o le directory, mentre è usato il desktop (la scrivania) per organizzare i file
Interfaccia grafica
13
• Vantaggi di una interfaccia grafica
– Semplicità di utilizzo
– Rapidità di esecuzione di compiti complessi
• Vantaggi dell'interprete dei comandi
– E’ possibile eseguire anche compiti non disponibili sull'interfaccia grafica
Le reti
14
Divide et impera
• In molti ambiti informatici si affrontano problemi complessi:
– troppo difficili da risolvere “in un unico passaggio”
• In questi casi si adotta la strategia “divide et impera”:
– dividi il problema in tanti sottoproblemi più semplici
– risolvi tutti i sottoproblemi
– sfrutta le soluzioni dei sottoproblemi per trovare la soluzione del problema iniziale
15
Problema (esempio)
• Voglio inviare una mail
• Soluzione → scrivi un programma che si occupi di:
– permettere all’utente di scrivere le mail
– comunicare l’informazione
• inviare il segnale, indipendentemente dalla connessione fisica utilizzata (cavo, etere, ecc.)
• assicurarsi che l’informazione sia stata ricevuta
• ecc.
→ troppo difficile!16
Soluzione “divide et impera”
• Dividiamo il problema in sottoproblemi:
– come si invia l’informazione su un mezzo fisico (cavo, etere, ecc.)?
– come ci si può assicurare che l’informazione sia stata ricevuta?
– ...
– scrivi un programma che permetta all’utente di scrivere mail
17
Vantaggi della soluzione “divide et impera”
• Le componenti sono specializzate:
– ognuna svolge un compito specifico, quindi:
• saranno meglio ottimizzate
• avranno meno errori
• Se volessimo scrivere un’applicazione diversa (es: un browser)?
– potremmo utilizzare buona parte del lavoro fatto, senza cambiare nulla
18
Seconda parte:Lo stack ISO/OSI
19
“E adesso cos’è sta roba?!!... Non venirmi a dire che serve
sapere queste cose per usare internet!”
Applicazione
Presentazione
Sessione
Trasporto
Rete
Collegamento
Fisico
Lo stack ISO/OSI
20
Applicazione
Presentazione
Sessione
Trasporto
Rete
Collegamento
Fisico
• Utilizzato per suddividere il problema della comunicazione in rete in tanti sottoproblemi
• Ogni livello ha un compito specifico e diverso da quello degli altri livelli
– OSI = Open Systems Interconnection
– ISO = International Organization for Standardization
Il livello fisico
• Stabilisce come deve avvenire la comunicazione sul canale di comunicazione:
– nella comunicazione su cavo:
• a quanti volt corrisponde il valore 1 e a quanti volt corrisponde il valore 0?
– nella comunicazione su onde radio:
• quale deve essere la frequenza utilizzata?
21
Applicazione
Presentazione
Sessione
Trasporto
Rete
Collegamento
Fisico
Il livello di collegamento
• Il problema: su un canale può scrivere un solo computer per volta
• se due computer scrivono sul canale nello stesso momento, nessuno dei due riesce a leggere dal canale
• Come possono fare i computer di una rete a sincronizzarsi in modo da parlare uno alla volta?
22
Applicazione
Presentazione
Sessione
Trasporto
Rete
Collegamento
Fisico
Ethernet
• E’ un protocollo che definisce come devono essere risolti i problemi al livello di collegamento:
– è adatto a funzionare con diverse soluzioni a livello fisico:
• con cavo
• senza cavo (Wi-Fi=Wireless Fidelity)
• Non è l’unico protocollo per questo livello:
– esempio: bluetooth (frequenza radio a corto raggio)
23
Il livello di rete
24
Applicazione
Presentazione
Sessione
Trasporto
Rete
Collegamento
Fisico
• Come conviene dividerel’informazione che deveessere inviata?
– suddivisione in pacchetti, cioè in piccole componenti di informazione
Il livello di rete
• Come faccio a mandare un messaggio destinato a un determinato computer?
• Protocollo IP (=Internet protocol):
– assegno un numero univoco a ogni computer
– quando mando un messaggio, scrivo il numero del destinatario
– i computer che non sono i destinatari, ignorano il messaggio
25
Gli indirizzi IP
• Sono formati da 4 numeri compresi tra 0 e 255:
– di solito si indicano separati da un “.”
– es: 159.149.200.150
• Perché proprio 255?
• Ogni computer connesso alla rete deve avere un IP differente dagli altri:
– quanti computer al massimo possono essere connessi? 26
“Le reti” e “la rete”
• I computer connessi direttamente tra loro formano una rete locale (LAN = Local Area Network)
• Le reti locali sono organizzate in reti geografiche (WAN = Wide Area Network)
– reti progettate per inviare informazioni a località distanti
– i computer non sono tutti collegati tra loro
• La rete (Internet) è composta da più reti WAN collegate tra loro 27
La rete
• Quando mando un messaggio per un computer che non è nella stessa rete locale:
– indico l’indirizzo IP del destinatario
– un componente nella mia rete (router) si accorge che il messaggio non è per un computer della mia LAN, e lo inoltra ad un’altra rete
– quando la comunicazione arriva alla rete corretta, il computer destinatario riceve il messaggio
28
“Ma questo non è quello che faccio tutti i giorni!”
“Se sto capendo bene, mi stai dicendo che ogni macchina ha un indirizzo IP e che se voglio comunicare con questa macchina, devo conoscere il suo l’indirizzo.
Quando voglio leggere una pagina web, devo dare il nome della macchina dove si trova la pagina, giusto? Ecco, appunto, ma io non ho mai scritto un indirizzo
IP: ho sempre usato nomi più semplici, come www.google.com. Come è possibile allora che funzioni lo stesso?”
29
Il DNS
• DNS = Domain Name System
• E’ difficile, per l’uomo, memorizzare gli indirizzi IP:
– ad ogni indirizzo IP si associa un nome più semplice da ricordare (es: it.wikipedia.org)
• Quando si scrive il nome, si richiede ad un server DNS di risolvere quel nome:
– cioè di dire a quale indirizzo IP quel nome corrisponde
– per fare questo, il server DNS mantiene sempre aggiornata una lista di nomi e dei relativi indirizzi IP
30
Il livello trasporto
• Se invio tanti pacchetti:
– come posso essere sicuro che arrivino tutti ?
– come posso sapere in che ordine arrivano?
• pacchetti diversi possono prendere strade diverse, alcune più rapide, altre più lente
31
Applicazione
Presentazione
Sessione
Trasporto
Rete
Collegamento
Fisico
Una soluzione: il protocollo TCP
• TCP = Transmission Control Protocol (TCP/IP)
• Con il protocollo TCP ogni pacchetto viene numerato in ordine sequenziale:
– quando i pacchetti vengono ricevuti, è possibile ricostruire l’ordine di tutti i pacchetti
• I pacchetti sono inviati uno alla volta usando diversi percorsi tra quelli disponibili• dato che ogni pacchetto può essere instradato su un
cammino diverso, interruzioni di servizio o congestioni non rappresentano un problema insormontabile
32
Il protocollo TCP
33
I livelli sessione, presentazione e applicazione
• Sessione: serve per stabilire, mantenere o terminare una connessione (sessione) fra applicazioni
– Mantiene le connessioni (continue) tra due macchine
– Controlla il flusso di dati trasmessi • es: punti di controllo permettono di
riprendere dall’ultimo pacchetto inviato in caso di errori o malfunzionamenti
34
Applicazione
Presentazione
Sessione
Trasporto
Rete
Collegamento
Fisico
35
Applicazione
Presentazione
Sessione
Trasporto
Rete
Collegamento
Fisico
I livelli sessione, presentazione e applicazione
• Presentazione: gestisce la trasformazione dei dati in formati standardizzati
– Come vengono codificati i dati durante la trasmissione?
– Come è possibile offrire servizi comuni come, ad esempio, la compressione?
• Applicazione: si occupa di interfacciare l’utente con la macchina
Terza parte:Le applicazioni Internet
36
Il web
• Si richiede ad una macchina (il server) di darci alcune informazioni:
– queste informazioni vengono visualizzate all’interno del browser (es: Internet Explorer, Mozilla Firefox, Google Chrome, ecc.)
• Non confondete il web con Internet:
– il web è una delle possibili applicazioni che si possono usare in Internet
37
Architettura client/server
• Il server è il computer che memorizza la pagina web, il clientè il computer che accede alla pagina web
– Quando cliccate su un link, il vostro computer comincia un’interazione con il server
– Una volta che il server vi ha inviato la pagina, l’interazione client/server termina
– Il server è in grado di gestire più client contemporaneamente38
Caratteristiche della comunicazione
• Sincrona:
– mittente e destinatario devono agire contemporaneamente nella comunicazione
– es: telefono, fax
• Asincrona:
– mittente e destinatario possono agire in tempi diversi nel processo di comunicazione
– es: posta cartacea, email
39
L’instant messaging
• Permette di scambiare messaggi (di solito in forma scritta) in tempo reale
• Esempi:
– MSN, Google talk, Skype, facebook
40
Il voice over IP (VoIP)
• E’ una evoluzione dell’instant messaging:
– perché scrivere quando si può parlare?
• La voce viene digitalizzata e spedita
• In pratica è come il telefono:
– e con il telefono può interagire: con il VoIP si possono anche fare o ricevere chiamate su telefoni tradizionali
• Alcune compagnie telefoniche usano esclusivamente VoIP (ma voi non lo vedete perché vi permettono di usare il telefono classico):
– ES: Fastweb
41
Condivisione di file
• Ogni utente rende disponibile dei file che gli altri possono scaricare
• E’ basato su un modello di comunicazione diverso da quello classico delle altre applicazioni: il peer-to-peer (P2P)
– ogni macchina svolge sia lavoro di client (quando richiede un file) sia lavoro di server (quando fornisce un file)
42
Condivisione di file
43
La posta elettronica:come funziona?
44
Utente(mittente)
Server di
posta(1) Invio
Messaggio
Utente(destinatario)
Server di
posta
(2) Ricezione
Messaggio
“Ci sono messaggiper me?”
I protocolli di comunicazione
• Qual è il problema:
– In tutte le applicazioni Internet due (o più) componenti comunicano tra loro
– Per capirsi devono definire quali messaggi vengono scambiati
• I protocolli di comunicazione definiscono l’ordine e il significato dei messaggi:
– esistono numerosi protocolli definiti per ogni livello dello stack OSI
• es: protocolli IMAP, POP e SMTP per posta elettronica e newsgroup
• es: protocolli HTTP e FTP per trasmissione dati
45
I protocolli di comunicazione
46
Quarta parte:Gli algoritmi distribuiti e
il calcolo parallelo
47
Algoritmi distribuiti
• Sono particolari tipi di algoritmi che coinvolgono almeno due macchine per il calcolo.
• Hanno problemi teorici maggiori rispetto agli algoritmi classici
– esempio: è necessario garantire che le macchine possano sincronizzarsi
48
Vantaggi degli algoritmi distribuiti
• Sfruttano informazioni che non risiedono su una sola macchina
• Permettono di calcolare risultati più velocemente rispetto agli algoritmi eseguiti su una singola macchina:
– il calcolo in questo caso viene detto parallelo
– avviene in contemporanea su diverse macchine
49
Calcolo distribuito: un esempio (curioso)
• Il progetto “SETI@home”:
– progetto di calcolo distribuito per personal computer
– analizza i segnali captati dal radiotelescopio di Arecibo alla ricerca di eventuali trasmissioni radio provenienti da intelligenza extraterrestre
• SETI = Search for Extraterrestrial Intelligence
– andate a curiosare: http://setiathome.berkeley.edu/index.php
50
Calcolo distribuito: un altro esempio
• Il progetto “Folding@home”:
– progetto di calcolo distribuito per personal computer
– analizza il corretto/errato avvolgimento delle proteine, in relazione ad alcune patologie:
• morbo di Alzheimer, di Parkinson, della “mucca pazza”
• sclerosi laterale amiotrofica
• molti tipi di cancro
– andate a curiosare: http://folding.stanford.edu/Italian/Main
51
Calcolo parallelo: esempio
• Vogliamo verificare se 10 numeri dati sono tutti primi
• Prendiamo 10 computer, facciamo verificare ad ognuno se 1 dei numeri è primo e poi mettiamo assieme il risultato
• Il tempo per comporre il risultato è trascurabile rispetto al tempo per calcolare se un numero è primo
• Tempo totale di calcolo: 1/10 del tempo che servirebbe per eseguire lo stesso algoritmo su un solo computer
52
Calcolo parallelo: limiti
53
Calcolo parallelo: limiti
• In molti casi il tempo di coordinamento tra vari computer non è trascurabile.
– Non tutti gli algoritmi si possono rendere paralleli in modo efficiente.
54
Calcolo parallelo e complessità computazionale
• Dunque
– il calcolo parallelo può servire per calcolare più rapidamente un risultato di una computazione particolarmente complessa
• Tuttavia
– il tempo di calcolo diminuisce “solo” linearmente con il numero di computer
– ci sono alcuni algoritmi che hanno complessità computazionale talmente alta che, nonostante siano resi distribuiti, richiedono tempi lunghissimi
• o, addirittura, non sono praticamente calcolabili
55
Quinta parte:I motori di ricerca
56
Quanto è grande Internet
• Quanto è grande Internet?
– quante pagine ci sono?
– quanti link?
• Difficile da valutare esattamente
– perché in continua crescita
• Per avere un’idea:
– 4 miliardi di pagine
– 100 miliardi di link
57
Problema
• C’è troppa informazione!
• Come facciamo a trovare quello che cerchiamo?
58
Le directory
• Si costruisce manualmente una gerarchia di argomenti con i relativi link
59
60
http://www.google.it/dirhp
Le directory. I problemi
• Non tutte le pagine vengono linkate
• La struttura della directory è arbitraria:
– quante categorie ci devono essere?
• Le risorse in Internet sono dinamiche (variano molto in fretta):
– è necessario aggiornare la directory molto spesso
• Il lavoro è manuale:
– lento, soggetto ad errori, costoso
61
Ricerca automatica. Una soluzione naive
• Supponiamo di voler trovare una procedura per ricercare una parola all’interno del web
• Scriviamo un programma che, automaticamente, cerchi “il più possibile” nel web per trovare la parola cercata
62
Soluzione naive. Idea
• Visitiamo tutte le pagine, partendo da una (che abbia tanti link in uscita) e seguiamo i link
• Quando visitiamo una nuova pagina (se non la abbiamo già visitata), cerchiamo il contenuto della parola anche in quella pagina:
– se lo troviamo, aggiungiamo la pagina appena visitata ad un elenco (il risultato della ricerca)
63
Soluzione naive. Idea
64
Prima pagina visitata
pagina 1
pagina 2
Link
Link Link
Soluzione naive
• Input: una parola, una pagina da cui iniziare
• Output: l’elenco delle pagine che contengono quella parola
• E’ troppo complesso specificare un algoritmo
– presentiamo solo una procedura, in cui alcuni passi non sono ben specificati
65
Soluzione naive: procedura1. Chiamiamo “alfa” la pagina con cui cominciare
2. Chiamiamo “beta” l’elenco (inizialmente vuoto) di pagine
3. Se la pagina alfa non è già stata visitata, allora:
A. Se la parola in input è presente in alfa, aggiungi alfa a beta
B. Aggiungi tutti i link in uscita da alfa alle pagine da visitare
C. Segna alfa come pagina già visitata
4. Se ci sono altre pagine da visitare, chiama alfa una di queste pagine, rimuovi la pagina alfa dalle pagine ancora da visitare, e vai al passo 3
5. Termina restituendo in output l’elenco beta66
Soluzione naive: problemi
1. Tempo (fisico) richiesto:
– assumiamo 10ms per percorrere un link
– trascuriamo molti altri problemi
– 10ms per 100 miliardi di link = 32 anni
2. Ordine delle pagine:
– le pagine dell’output non hanno un ordine
3. Non ricerco in tutte le pagine:
– ma solo nelle pagine raggiungibili
67
Soluzione al problema delle prestazioni
• In realtà, i motori di ricerca impiegano pochi decimi di secondo per fare una ricerca
– rispetto ai 32 anni (stimati) del nostro algoritmo!
• Idea: visitare il web una volta sola e fare un indice
– memorizza tutte le parole in modo ordinato
– le successive ricerche devono essere fatte all’interno dell’indice e non nel web
• Un programma detto crawler si occupa di questa operazione
68
L’indice. L’idea
• Supponete che una certa pagina X contenga il testo: “Il corso di informatica è bellissimo!”
• Il crawler memorizza, all’interno dell’indice, che le parole “corso”, “informatica” e “bellissimo” compaiono nella pagina X
– le parole troppo brevi o comuni non vengono memorizzate
• Quando devo fare una ricerca, basta scorrere l’indice:
– è ordinato, quindi posso fare molto in fretta
69
Problema dell’ordine delle pagine
• Se cerchiamo “Università degli Studi di Napoli Federico II” otteniamo circa 3 milioni di risultati
– ci sono 3 milioni di pagine che contengono le parole “università” “studi” “Napoli”
• Se cercassimo la “home page” dell’Università e usassimo il nostro algoritmo naive, dopo aver aspettato 32 anni, dovremmo ancora scorrere tutti i 3 milioni di risultati per trovare quello che ci interessa
– perché non sono ordinati!70
Soluzione al problema dell’ordine delle pagine
• Soluzione: diamo un peso alle pagine
– il termine tecnico è page ranking
• Idea: più grande è il numero di link in ingresso, più una pagina è importante:
– perché sono in tanti che la puntano
– mostriamo le pagine all’utente in ordine di importanza
• Tante altre tecniche
– che possono variare tra diversi motori di ricerca71
Problema delle pagine non raggiungibili
• Pagine raggiungibili
– le pagine che possono essere raggiunte, seguendo i link, dalla pagina iniziale
• Non tutte le pagine sono raggiungibili. Es:
– pagine senza link in ingresso
– pagine create temporaneamente
– pagine ad accesso limitato
• es: serve una password
72
Problema delle pagine non raggiungibili: soluzione?
• I motori di ricerca attuali non risolvono questo problema
• Inoltre, introducono un altro tipo di pagine sulle quali non viene svolta la ricerca:
– le pagine non ancora indicizzate
– se una pagina viene creata (o modificata), non verrà trovata dal motore di ricerca fino a quando il crawler non la visita
• Google ci mette qualche settimana per fare il crawling di tutto il web
73
Sesta parte:Conclusioni
74
“Accidenti se è lunga questa lezione!”
Le reti
• Problema difficile, che coinvolge diversi aspetti:
– da quello “fisico” alla gestione della comunicazione
75
La rete
• Viene chiamata con il termine Internet:
– uno dei protocolli utilizzati nelle reti → Internet Protocol
• da cui deriva il termine “IP address”
– la rete è composta da tante reti WAN collegate tra loro
• Internet è una rete sulla quale possono essere eseguite diverse applicazioni:
– web, posta elettronica, ecc.
76
Il calcolo parallelo
• Utilizzato per velocizzare l’esecuzione di programmi i cui algoritmi hanno complessità computazionale molto alta
• Soluzione spesso usata per ottenere risultati di ricerca:
– per esempio in bioinformatica
77
I motori di ricerca
• Organizzazione delle pagine
• Ricerca di parole all’interno delle pagine
– Metodo naive
– Indicizzazione delle pagine
– Page Rank
78
