Tributo a Edsger Wybe Dijkstra

Edsger Wybe Dijkstra

Rotterdam, 11 maggio 1930 – Nuenen, 6 agosto 2002

Biografia

• Madre matematico, padre chimico.

• Istruzione:

• Gymnasium Erasmianum a Rotterdam.

• Università di Leiden - Matematica e Fisica Teorica.

Informatica Teorica Cristian Semperboni & Giovanni NavaA.A 2013-2014

“

”

Oh, no! Impara le formule e ricordati sempre chesei sulla strada sbagliata se hai bisogno dipiu’ di cinque righe.

Brechtje Cornelia Kluyver

… il suo stile sarà sempre caratterizzato da

SEMPLICITA’ ed ELEGANZA (qualità e correttezza)…


EDSAC

E’ il terzo computer della storia

a programma memorizzato

basato sull’ architettura di von Neumann.

Note tecniche:

• Composto da 3.000 valvole termoioniche;

• Input « schede perforate »;

• Output « telescrivente »;

• Superfice di 20 m2;

• Capacita di elaborazione 650 [istruzioni/secondo];

Settembre 1951 Cambridge - Corso programmazione

(Electronic Delay Storage Automatic Calculator)


1952…

• Assunzione presso il dipartimento di calcolo al Centro Matematico di

Amsterdam.

• Contributo nella progettazione di:

• ARRA

• ARRA II

• FERTA

• ARMAC

Collaborazione con:

Scholten

Loopstra

Blaauw


“

”

Nel 1955 ho preso la decisione di non diventare un fisico teorico, ma unprogrammatore [...] perche’ la programmazione rappresentava una sfidaintellettuale piu’ grande.

Edsger Dijkstra


“

”

Nessuno di noi era stato formato come matematico [...] credo fermamente che questo quadro, che comprendeva una solida formazione in 5 lingue straniere,

abbia avuto una grande influenza sul modo in cui abbiamo lavorato.

Edsger Dijkstra


ARRA I…

• Non funzionò mai correttamente…

alla sua presentazione si ruppe e da li non fu più riparato.

Note tecniche:

• 4 anni di sviluppo

• Composto da 1.200 relè connessi alla macchina

• Tempo di switch inaffidabile

• Input « nastro di carta perforata »

• Output « telescrivente »

• Memoria a tamburo

• 3 registri gestivano parole da 30 bit

• Assenza del Clock (segnale di « end-operation »)


ARRA II…

Una copia della macchina (FERTA) fu realizzata con qualche piccola

modifica per la Fokker (avionica).

Note tecniche:

• Non fu un evoluzione di ARRA I, ma una

macchina innovativa

• Introduzione del Clock di sistema

• Input « nastro di carta perforata »

• Output « telescrivente »

• Memoria a tamburo

(1024 parole – 2 istruzione per ogni parola)

• 2 registri

• Routine di controllo introdotte da Dijkstra

(inaffidabilità delle memorie a tamburo)


ARMAC…

• Successore ARRA II (50 volte più veloce)

• Ultima macchina del centro –

– poi società spin-off (Electrologica Nv)

• Coesistenza di memoria a tamburo e memoria

magnetica

• Registro di Jump (implementazione di subroutine

di «salto»)

• Completa divisione tra:

Progettazione e

Costruzione

Programmazione


“

”

La prima cosa che abbiamo fatto è stata quella di scrivere un manuale di programmazioneper la prossima macchina, compresa la sua completa descrizione funzionale […] Questodocumento e’ servito da contratto tra me e loro: essi sapevano quello che avrebberodovuto costruire e io sapevo quello che avrei dovuto sviluppare.

…basi dell’analisi delle specifiche funzionali del Software…


Edsger Dijkstra

“A note on two problems in connection with graphs”

(1959)

Consideriamo n nodi, alcuni o tutti accoppiati, i quali sono connessi

da un ramo. Ogni ramo ha una lunghezza nota. Ci limitiamo al caso

in cui esiste almeno un percorso tra due nodi qualsiasi.

• Algoritmo dell’albero ricoprente minimo (o Minimum Spanning

Tree, MST).

• L’algoritmo dei cammini minimi (o Shortest Paths, SP), passato

poi alla storia come « L’ Algoritmo di Dijkstra ».


Algoritmo dell’albero ricoprente minimo

Problema 1: Costruire l’albero della lunghezza minima totale tra n nodi.

Definiamo

• « I » rami definitivamente assegnati all’albero in costruzione.

• « II » rami tra i quali il prossimo ramo sarà aggiunto a I.

• « III » rami scartati o non ancora considerati.

• « A » nodi connessi dai rami I.

• « B » nodi rimanenti tali che uno ed uno solo ramo II porterà ad essi.


Algoritmo dell’albero ricoprente minimo

Poniamo:

• Arbitrariamente un solo nodo come unico nodo A.

• Tutti i rami che terminano nel nodo A come rami di tipo II.

Step 1: Il più breve ramo II è promosso a I, quindi il nodo collegato è promosso ad A.

Step 2: Consideriamo i rami che vanno dal nuovo A ad ogni B. Se il ramo considerato è

più breve del rispettivo II, allora il primo rimpiazza il secondo (che viene scartato),

altrimenti viene scartato.

Ripetere: fino a quando non abbiamo più rami di tipo II e i nodi di tipo B.



III

III

III

IIIIII

III

IIIIIIIII

IIIIII


III

II

III

IIIIII

III

IIIIIIII

IIII


II

I

III

IIIIII

III

IIIIIIII

IIIII


II

I

III

IIIIII

II

IIIIII

IIIIII


I

I

II

IIIII

II

IIIIIII

IIIIII


I

I

III

III

III

IIIIII

IIIIII


I

I

III

II

III

IIIIII

IIIIII


I

I

III

II

III

IIIII

IIIIII

Algoritmo dei cammini minimi

Problema 2: Trovare il cammino della lunghezza minima totale tra due nodi dati P e Q,

costruito in modo incrementale.

Definiamo

• « A » nodi per i quali il cammino minimo da P è noto.

• « B » nodi connessi ad almeno un A, tra i quali il prossimo nodo sarà aggiunto ad A.

• « C » nodi rimanenti.



Definiamo:

• « I » rami che si trovano sul cammino minimo tra P e i nodi A.

• « II » rami tali che uno ed un solo ramo II porterà a ciascun B, tra i quali il prossimo

ramo sarà aggiunto a I.

• « III » rami scartati o non ancora considerati.

Poniamo:

• Tutti i nodi come C, tutti i rami come III.

• P come unico nodo A.



Step 1:

• Ogni ramo che collega il nuovo A ad un B viene confrontato con i rispettivi II: se il

cammino è minore allora il primo sostituisce il secondo, altrimenti viene scartato.

• I nodi C collegati al nuovo A vengono promossi a B, i rispettivi rami a II.

Step 2:

• Ogni B può essere connesso a P in un solo modo: usando rami I ed un solo ramo II.

Il nodo B alla distanza minima da P è promosso ad A, il corrispondente ramo a I.

Ripetere: Fino a quando il nodo Q è promosso a tipo A.


P

Q

1415

7

9

11

10

9

62

G

H

E

F


III

III

III

IIIIII

III

III

III

III

P

Q

1415

7

9

11

10

9

62

G

H

E

F


II

III

III

IIIII

II

III

III

III

P

Q

1415

7

9

11

10

9

62

G

H

E

F


III

III

III

IIIII

I

III

III

II

P

Q

1415

7

9

11

10

9

62

G

H

E

F


III

III

II

IIII

I

III

II

III

P

Q

1415

7

9

11

10

9

62

G

H

E

F


III

II

I

IIII

I

III

III

III

P

Q

1415

7

9

11

10

9

62

E

F

G

H


III

I

I

IIII

I

III

III

III

Linguaggio «ALGOL 60» & «Compilatore»

Sviluppato congiuntamente da un comitato di informatici statunitense ed europeo

o Per quasi 30 anni considerato lo standard nella rappresentazione di algoritmi.

o Blocchi di istruzione delimitati da BEGIN END;

o Introdusse il concetto di Stack;

o Celebre la frase di Tony Hoare (inventore del quick sort);

« Qui c’è un linguaggio cosi avanzato che non è solo un

miglioramento rispetto ai suoi predecessori, ma anche rispetto ai suoi

successori »


“

”

Abbiamo scritto il compilatore in doppia copia, pienamenteconsapevoli che stavamo facendo la storia.

Apporto significativo di due grandi menti:

John Backus

Peter Naur

Edsger Dijkstra

Grammatiche

BNF


“Recursive programming”

Definiamo:

• Subroutine (o funzione) un particolare costrutto sintattico che permette

di raggruppare, all'interno di programma « main » , una sequenza

di istruzioni in un unico blocco espletando così una determinata

operazione o elaborazione sui dati del programma, in modo tale che a

partire da determinati input restituisca determinati output.

«Stack, vettore e mutua esclusione» attribuiti a Dijkstra dall’Oxford Dictionary


(1960)

Considerazione iniziale:

• Ogni subroutine ha il proprio spazio di memoria privato.

Conseguenze:

• Spreco di memoria: Lo spazio allocato per tutte le subroutine è

generalmente maggiore di quello di cui hanno simultaneamente bisogno.

• Terminazione incorretta: impossibilità di chiamare una subroutine

mentre una o più precedenti attivazioni della stessa non sono ancora

terminate, senza perdere la possibilità di terminare correttamente in seguito.


“Recursive programming”(1960)

Stack

Idea: memorizzare una sequenza di unità informative, che cresce e decresce

da una sola estremità. Quando un’unità non interessa più viene rimossa.

n locazioni di memoria consecutiveStack pointer: quantità amministrativa

che punta alla prima locazione di

memoria libera


Analogia con le espressioni algebriche

Associando parentesi tonde alla operazioni di push e pop, si ottiene una

struttura nidificata corretta di parentesi tonde.

Lo stack è usato per memorizzare i risultati intermedi delle operazioni

elementari richieste nella valutazione di un’espressione algebrica.


Stack reservations

All’interno di una subroutine distinguiamo:

• Parametri: argomenti della funzione.

• Variabili locali: introdotte dalla subroutine.

• Risultati intermedi: analoghi a quelli del main.

L’esecuzione di una subroutine richiede:

• Link: indirizzo dove salvare i dati dell’unità aritmetica nello stack.

• Return address: indirizzo per il ripristino dei dati dallo stack all’unità aritmetica.


“

”

Le subroutine devono comparire solo una volta nella memoria, ma possonoavere piu’ « incarnazioni » da un punto di vista dinamico: l’attivazione « piu’interna » provoca la stessa porzione di testo in una parte superiore dello stack.Quindi la subroutine e’ sviluppata in un elemento definito che puo’ essere usatoin maniera completamente ricorsiva.

Edsger Dijkstra


• 1962 – nominato prof. di matematica presso l’Università

Technische Hogeschool di Eindhoven, (corso di Analisi numerica).

• Forma un piccolo gruppo di studenti (scienziati del computer)

che insieme a lui daranno i natali ad una serie di progetti

riguardanti:

Operating system T.H.E.

GoTo Statement & Programmazione strutturata

Risoluzione di problematiche relative alla

« programmazione concorrente ».

Introduzione a concetto di semaforo.

“Hierarchical ordering of sequential processes” (1971)

Problema dei 5 filosofi


• I filosofi condividono un tavolo rotondo con 5 posti.

• Passano la vita pensando e mangiando

Problema

• Gli spaghetti sono difficili da mangiare; un filosofo

per mangiare deve usare due bacchette (risorse)

Conseguenza

• Due filosofi consecutivi, non potranno mai mangiare

contemporaneamente

Begin

think;

eat;

end


Semafori (Mutex)

Sezione critica

• è una porzione di codice che accede a

una risorsa condivisa, tra più processi in

esecuzione in un sistema concorrente

• Variabile intera non negativa «di scopo

speciale» ovvero garantire l’accesso in

mutua esclusione alla sezione critica


• Problema: «è necessario caratterizzare un processo in attesa»

• Soluzione: «tratteremo la variabile « s » non come un semplice valore integer,

ma con un significato particolare… quello di semaforo… e per far ciò essa

dovrà essere sempre non-negativa»

• Dijkstra definisce due operazioni atomiche complementari:

"prolagen" (testare & decrementare) P(s) : s : = s-1

"verhogen" (incrementare) V(S) : s : = s+1

1 0


• Ciò impone che:

• Sempre eseguita => incremento

• Se « S = 0 » => fase di verifica

operazione rigettata (vincolo violato).

processo in esecuzione passa in stato wait e viene posto in un buffer (di

processi relativi allo specifico semaforo) nell’attesa che un altro processo

esegua una V su di esso e risvegli un «dormiente» (FIFO) che potrà cosi

completarsi.

• Se « S = 1 » => decremento

V

P


Rischio

«deadlock»

repeat

P(bacchetta[i]);

P(bacchetta[i+1 mod 5]);

eat();

V(bacchetta[i]);

V(bacchetta[i+1 mod 5]);

think();

until false;

Soluzione

«banale»

« Se tutti i filosofi avranno fame contemporaneamente, essi prenderanno la

forchetta alla propria sinistra… e nell’attesa che qualcuno lasci la

forchetta… moriranno di fame… »


Soluzione « strutture condivise »

• state [5] Vettore dello stato di ciascun filosofo

(valori possibili: PENSA {0}, AFFAMATO {1}, MANGIA{2})

• Mutex = 1 Semaforo per mutua esclusione in Sezione critica

- inizializzato a 1 - ( libero )

• prisem[5] = 0 Vettore di semafori mutex (uno per ogni risorsa -

forchetta-) inizializzato a 0 ( occupato )


while (TRUE) {

think();

take_forks(i);

eat();

put_forks(i);

}

Soluzione « definitiva »

Se le forchette non sono

libere si blocca

Segnala che le forchette

sono libere

Ogni filosofo [i] esegue questo pezzo di codice « concorrentemente »

con gli altri filosofi per tutta la durata della sua vita


{

P (mutex);

state[i] = AFFAMATO;

test(i);

V (mutex);

P (prisem[i]);

}

« take_fork(i) »

L’ i-esimo filosofo

segnala di essere affamato

L’i-esimo filosofo verifica se ha la

disponibilità delle due forchette

L’ i-esimo filosofo si blocca se le

forchette non sono libere; egli è

affamato ma deve aspettare che l’

(i-1)-esimo o (i+1)-esimo finisca


{

if (state[i] == AFFAMATO &&

state[(i+5-1) mod 5] != MANGIA &&

state[(i + 1) mod 5)] != MANGIA)

state[i] = MANGIA;

V(prisem[i]);

}

« test (i) »

sem[i] va a 1 solo se l’ i-esimo

filosofo può mangiare; altrimenti

esso si blocca dopo la test(i) nella

take_forks(i)

Forchetta a SX dell’

i-esimo filosofo

L’ i-esimo filosofo può mangiare

Forchetta a DX dell’

i-esimo filosofo


P (mutex);

state[i] = PENSA;

test ((i + 1) mod 5);

test ((i + 5 - 1) mod 5);

V (mutex);

« put_forks(i) »

Esso deve quindi allertare i vicini di

posto (DX e SX) che le sue forchette

sono libere

Se il filosofo i-esimo decide di

smettere di mangiare e tornare a

pensare

Se i filosofi DX e/o SX sono affamati (e quindi in attesa sul relativo semaforo

della risorsa ove hanno invocato la P in precedenza) e le loro forchette sono

libere, allora vengono sbloccati dalla test


• L’ algoritmo di Dijkstra « I 5 filosofi » risolve quindi 2 problematiche

critiche nella programmazione concorrente:

Il deadlock che può verificarsi se ciascuno dei filosofi tiene in mano una

forchetta senza mai riuscire a prendere l'altra

Come??? Con questo algoritmo, un filosofo prende le forchette solo se

sono entrambe libere…

La starvation che può verificarsi indipendentemente dal deadlock se uno dei

filosofi non riesce mai a prendere entrambe le forchette.

Come??? Utilizzando come meccanismo di mutua esclusione le code di

attesa, assicurando cosi un equo accesso alle risorse


Sistema Operativo <<THE >>

• 1° SO a strati della storia (6 ma in realtà solo una convenzione progettuale,

poiché tutte le parti del sistema venivano alla fine collegate insieme in un unico

programma oggetto).

• Sistema di tipo Batch

• Multi-programming System: processi concorrenti sequenziali cooperavano

mediante l’impiego di semafori per la sincronizzazione.

• Utilizzo di un algoritmo di schedulazione della CPU basato su priorità,

che venivano ricalcolate ogni 2 secondi ed erano inversamente proporzionali al

tempo in cui la CPU era stata usata recentemente (negli ultimi 8-10 secondi).


Sistema Operativo <<THE >>

<< Go to statement considered harmful 1968>>

<< Notes on Structured Programming 1969 >>

Problema Soluzione


“

”

La qualità dei programmi e’ una funzione decrescente della densitàdi dichiarazioni GOTO […] sono sempre piu’ convinto che la struttura inquestione debba essere abolita da tutti i linguaggi di programmazione ad altolivello.

Edsger Dijkstra

…The go to statement as it stands is just too primitive, it is too

much an invitation to make a mess of one's program…


• Un qualunque algoritmo puòessere implementato in codicesorgente, pseudocodice odiagramma di flusso,utilizzando tre sole strutturedette strutture di controllo:

I. la sequenza;

II. la selezione;

III. il ciclo (iterazione);

• Applicare ricorsiva ad istruzioni elementari (ad es. di istruzioni eseguibili con ilmodello di base della macchina di Turing).

Teorema di Böhm-Jacopini

Operazioni I/O

Operazioni di

Assegnazione


“Notes on structured programming”

COMPUTAZIONE

• « Dimensionamento » in termini di

quantità di informazioni ed operazioni

coinvolte.

EFFICACIA

• « Organizzazione » delle risorse HW.

MASSIMA RESA


(1969)

“

”

Non si puo’ considerare la programmazione come la minimizzazione delcosto di una performance. L’arte di programmare e’ l’arte di organizzarela complessità, di gestire il caos bastardo nel modo più efficace possibile.


Edsger Dijkstra

PROGRAMMAZIONE

• Costrutti e diagrammi di flusso:

• If-Then-Else;

• Case Of;

• While-Do;

• Repeat-Until;

• (In)affidabilità del Testing.

• « Linguaggio ad alto livello » ed astrazione dall’hardware sottostante.



(1969)

CORRETTEZZA DI UN PROGRAMMA

• Programma ha senso solo durante l’esecuzione, un teorema ha senso di per sé.

• Programmazione ben strutturata attraverso successive scomposizioni.

dimostrazione di correttezza senza ricorrere a dispendioso processo intellettuale

Induzione per enumerazione Principio di induzione Astrazione



(1969)

“

”

Il programma e la prova di correttezza andrebbero sviluppati in parallelo.Inizialmente ci si chiede quale struttura dovrebbe avere la dimostrazione, poi sicostruisce un programma per soddisfare i requisiti della stessa, infine lo si usa in

senso euristico. In questo modo il programma risulta corretto per costruzione.

Edsger Dijkstra

• Utilizzo di strutture ben conosciute e/o familiari.

• Scelta di programmi intellettualmente gestibili (soluzione algoritmica).

• Lunghezza delle dimostrazioni: a « misura d’uomo ».


• I grandi sistemi devono essere costruiti partendo da molti piccoli componenti;

• Ogni componente deve essere definito solo dalla sua interfaccia e non dalla sua

implementazione;

• La progettazione dovrebbe iniziare dalla “separazione degli interessi”, cioè

separando i diversi aspetti del problema e concentrando l’attenzione su

ciascuno di essi;



(1969)Filosofia

Algoritmo del banchiere“Een algorithme ter voorkoming van de dodelijke omarming” (EWD-108)

• Indica se un sistema, in cui operano processi concorrenti su

istanze di risorse disponibili, si troverebbe in uno stato sicuro o

meno, nel caso soddisfacesse una specifica richiesta di risorse da

parte di un determinato processo evitando una situazione di

deadlock.

• Il deadlock (o stallo) è una situazione in cui due o più processi si

bloccano a vicenda, aspettando che uno esegua una certa azione.


…

Clienti Processi

……


• Fissata una situazione di allocazione di k-istanze di

m-risorse ad n-processi al tempo « t0 »


• Il processo P1 richiede l’allocazione di risorse (1,0,2)

• Ricavo il vettore Necessità (Max - Assegnate)


R ≤ N

R ≤ D

Simulazione

allocazione

risorse per Pj

D = D – RA = A + RN = N – R

Verifica:

Stato

SICURO

Assegnazione effettiva delle

risorse

D = D – RA = A + RN = N – R

• Pj deve attendere.• Ripristino vecchio

stato di allocazione risorse

ERRORE.

Superato

Max n

richieste

• Pj deve

attendere.

• Risorse non

disponibili

si

si

sino

no

no


Sicuro


“Simulazione”

• Il processo P1 richiede l’allocazione di risorse (1,0,2)

STATO SICURO

• Concetto introdotto da Dijkstra tra il 1965 e 1966 quando sviluppò il suo

sistema operativo multiprogrammabile THE.

• E’ uno stato in cui è possibile allocare tutte le risorse richieste

da un processo senza che quest'ultimo comporti

un deadlock con un altro processo.

• Osservazioni:

Uno stato sicuro non implica che tutte le allocazioni di risorse avverranno con

successo, MA solo che esiste almeno un modo sicuro per allocare tutte le risorse.


Valutazione SICUREZZA



<P1>


• L’esecuzione dell’algoritmo di sicurezza mostra che la

sequenza < P1, P3, P4, P0, P2 >soddisfa i requisiti di sicurezza.

• La Richiesta (1,0,2) può essere

soddisfatta senza rischiare un deadlock.


… Oggi …

• Difficile applicazione

• costoso in termini economici.

• allocazione delle risorse non deterministica (concetto richiesto dall’Algoritmo

del Banchiere).

• la maggior parte dei S.O. non considera il problema di eventuali deadlock, in

quanto evento raro, data l'abbondanza delle risorse a disposizione.

• oggigiorno la gestione dei deadlock è sicuramente più critica nei database che

non nei sistemi operativi.


“

”

L’induzione matematica puo’ portare ad argomentazioni molto compatte edefficaci – in breve: Belle! – e, quando riconosciamo la battaglia contro ilcaos, il disordine e l’indomita complessita’, come una delle principalivocazioni dell’informatica, dobbiamo ammettere che…

Edsger Dijkstra


Beauty is our Business

“The humble programmer” – Turing Award (1972)

La nostra metodologia di programmazione migliorerà se:

• Avremo apprezzamento della sua tremenda difficoltà.

• Utilizzeremo linguaggi di programmazione modesti ma

eleganti.

• Rispetteremo le intrinseche limitazioni della mente umana.

avvicinarsi alla programmazione UMILMENTE


A.C.M. – Association for Computing Machinery

«…un oceano tra me ed il mio capo…»

• Ingresso nel mondo dell’industria (ricercatore presso la Burroughs

Corporation) – il grosso del lavoro nel suo studio a casa (Olanda).

• Fonda l’ETAC noto come il « Club del martedì pomeriggio ».

• Periodo florido per gli articoli.

• Forte attaccamento al mondo dell’ Università.


“

”

Ventotto anni fa (1959) ho scritto EWD 0 […] dopo che ebbi mischiato le pagine tra imanoscritti per la seconda volta, decisi che sarebbe stato meglio mettere fine allaconfusione e li numerai (Ewd0, Ewd1, Ewd3…).

Questo è il modo in cui e’ iniziata.

Edsger Dijkstra

Le relazioni EWDUn informale ma efficace veicolo di diffusione delle idee

Scritti con la macchina da scrivere o con la penna stilografica

L’ultimo (Ewd1318) risale all’ aprile 2002


Università del Texas – Austin –

• Cattedra di Informatica in cui ripercorre tutti gli argomenti

affrontati nella sua vita.

• La sua semplicità si nota anche dal suo stile di insegnamento:

tutto alla lavagna, senza proiettore e senza seguire un libro di

testo.

• Fonda l’ETAC noto come il « Club del martedì pomeriggio ».


Conclusioni

• Dijkstra lavorò tutta la vita alla professionalizzazione

accademica della programmazione ed all’autonomia

dell’informatica come scienza.


Computer inteso come strumento

In Memorium Edsger W. Dijkstra

« Semplicità, bellezza ed eloquenza sono state le sue caratteristiche distintive, e la sua insistenza senza compromessi sull’eleganza nella

programmazione e sulla matematica e’ stata una fonte d’ispirazione per migliaia »

A.C.M. – Association for Computing Machinery

Grazie per la cortese attenzione…

Presentazione a cura di Nava Giovanni & Semperboni Cristian


Tributo a Edsger Wybe Dijkstra

Engineering

Transcript of Tributo a Edsger Wybe Dijkstra