Newsgroup: it.scienza.informatica
Titolo: [SISTEMI OPERATIVI] Principio di località

ciao.
Qualcuno mi potrebbe spiegare bene il principio di località ? studiandolo
sul libro non sono sicuro di averlo capito perfettamente...
In pratica i dati tendono ad ammassarsi ? In che senso ? Cioè nella memoria
principale si intende ?
Grazie a chi mi risponde.
Fly


Molto in breve:
mi pare ragionevole assumere che, se un programma sta in memoria, le sue
istruzioni siano effettivamente contigue, ovvero esso occupi (almeno in
generale, semplificando) un unico pezzo di memoria. Analogamente se in
memoria il nostro programma tiene dei dati, anche qui è ragionevole
l'assunzione che questi dati siano tra loro vicini (pensa ad esempio alla
memorizzazione di un vettore.. se v[0] sta in una certa cella, v[1] starà a
quella dopo, no?!?).
Il principio di località (spaziale) dice quindi che se un programma accede
ad una certa cella di memoria, è molto probabile che acceda anche a quelle
vicine... banale conseguenza delle osservazioni di sopra.
Il principio di località temporale, invece, dice che se un programma accede
ad una certa area di memoria al tempo t, molto probabilmente vi accederà
anche ad un tempo t' prossimo a t.
Quando parlo di memoria si intende, primariamente, la RAM, ma *credo* che il
principio valga analogamente anche per la memoria secondaria o, d'altro
verso, per la cache.. insomma per una memoria generica, ad un qualunque
livello di gerarchia.
Spero di essere stato d'aiuto (e di non aver detto 'zzate..;)
-Bura-

 principale si intende ?
Ti parlo sulle conoscenze che ho acquisito al corso di 
Calcolatori Elettronici II. In pratica è statisticamente molto 
probabile che due dati consecutivi si piazzino in regioni di 
memoria consecutive, e seguendo questo principio sono state 
ideate le cache, che incamerano la famosa "linea di cache", 
ovvero un blocco di dati consecutivi, proprio perché è molto 
facile che la richiesta di una dato successiva sia riferita a 
un'informazione contenuta nello stesso blocco che conteneva il 
dato richiesto precedentemente.
-- 
Lord Gas, the Waxen - Blasfemo di IFTMDG - Penguin's Enemy #1 
[ICQ: 57483751][the Waxen Pith: 
http://www.snipp.org/gas
]
... "Goddamn, there's always such a big temptation to be good"
... (Tom Waits - God's Away on Business)

 principale si intende ?
Durante l'esecuzione di un programma, per periodi di tempo relativamente
lunghi, si tende ad eseguire un certo sottoinsieme di istruzioni.
Prova a pensare ad un ciclo di un programma...

 ha scritto nel messaggio
news:bk6mao$10fd$1...@newsreader2.mclink.it...

Esempio: un programma che scansiona un vettore con un classico ciclo "for",
tende ad accedere a dati posti in indirizzi contigui di memoria (questo
perche' tutti i compilatori e interpreti utilizzano aree contigue per questo
tipo di struttura dati).
Un caso interessante si verifica quando si scansiona una matrice: e'
importante sapere se il linguaggio utilizzato (o meglio il compilatore o
l'interprete) memorizza la matrice "per righe" o "per colonne". Se non si
asseconda la scelta del compilatore si rischia di mandare in crisi i
meccanismi di paginazione e memoria virtuale del processore.
Scusa per la breita' ed il disordine...
Ciao. Federico.

 senso ? Cioè nella memoria principale si intende ?
Memoria 'principale' o disco non cambia molto (almeno sui concetti):
[localita' spaziale] supponiamo che tu stia leggendo un libro e sia arrivata
a pagina 25 , probabilmente dopo leggerai la pagina 26.
[localita' temporale] a volte capitera' che leggendo il tuo libro tu abbia
necessita' di rivederne alcune frasi parti piu' volte di seguito.
Su tali principi si basano le i sistemi di caching.
scusa per la spiegazione scherzosa, in altro momento con po' di sforzo
potrei recuperare quella seria da qualche parte  ;-)
saluti L

principale si intende ?
In pratica per un programma i riferimenti alle zone di memoria
virtuale tendono a concentrarsi ad una porzione di memoria limitata,
questo e' appunto la conseguenza della funzione Q(t) definita sopra:
anche per t--->infinito la porzione di memoria referenziata sara'
praticamente sempre la stessa.
-- 
Linux Registered User #181013
[Exokernels] Although one approach to eliminating bloated, buggy,
unreliable operating systems is to make them smaller, a more radical
one is to eliminate the operating system altogether.

...oops sorry piccola correzione:
praticamente la funzione e' simile a
Q(t) = l(1 - e^(-kt))
dove l e' il limite e k>0


 ha scritto nel messaggio
news:nsF9b.106340$sj6.1...@tornado.fastwebnet.it...

Rispondo a te , ma ringrazio tutti coloro che mi hanno risposto !
Penso di avere le idee un po' piu` chiare ma mi sorge spontanea una domanda
: la progettazione degli algoritmi di sostituzione di pagine nella memoria
virtuale si basano quindi su un principio di località spaziale o temporale ?
Forse entrambi ?
In pratica grazie a questo principio si tende a formare il working e/o
resident set di un processo  ?
ciao
Fly

 Prova a pensare ad un ciclo di un programma...
Infatti, se non ricordo male il principio (sia spaziale che temporale)
dovrebbe valere, oltre che per i dati, anche per le istruzioni del
programma.
ciao
sherpa

 temporale ? Forse entrambi ?
entrambi, volendo accedere ad un dato copy in chache tutta la 'pagina'
(sfrutti quindi la localita' spaziale) e mantieni i dati in chache fino a
che quella locazione di cache non ti e' necessaria per altri dati piu'
recenti (localita' temporale). E' quasi piu' diffcile a dirsi che a farsi
... cercati un esempio di progettazione di chache e capisci al volo..
L.

 ha scritto nel messaggio
news:bk9qoq$r03$1...@e3k.asi.ansaldo.it...

si infatti mi riferivo proprio al secondo caso, addirittura vale anche a
livello di microistruzioni, vedi per esempio il funzionamento della cache
del Pentium 4

Sostanzialmente da un'analisi statistica del funzionamento dei programmi si
nota che: se un programma accede ad una locazione di memoria ad un certo
istante è probabile che vi riaccederà a breve termine (località temporale) e
che a breve termine accederà a locazioni di memoria vicine (località
spaziale).
La località temporale nell'accesso ai dati è provocata dal fatto che spesso
i programmi usano alcune variabili molto frequentemente (es. contatori per
l'accesso agli array).
La località spaziale nell'accesso ai dati è provocata dall'uso degli array.
La località spaziale nell'accesso alle istruzioni è provocata dal fatto che
i programmi spesso eseguono le istruzioni sequenzialmente o facendo brevi
salti, mentre quella temporale è provocata dall'uso dei cicli e di
subroutine chiamate frequentemente.
Ciao.

 Forse entrambi ?
Da entrambi, visto che l'obiettivo è minimizzare il miss rate e questi
principi contribuiscono
entrambi alla causa.
Per quanto riguarda il progetto di una cache, ad esempio, utilizzare dei
blocchi di grandi
dimensioni migliora la località spaziale (più dati contigui staranno nello
stesso blocco in cache),
ma contemporaneamente peggiora quella temporale (man mano che ci saranno dei
miss
dei blocchi saranno sostituiti, e visto che più sono grandi i blocchi =>
meno ce ne stanno
in memoria, sarà più probabile che il blocco che hai usato da poco sarà
stato sostituito
da un altro). Insomma le due cose vanno a braccetto.
Salutoni.