[C] Raddoppiamento ricorsivo con swapping sui dati

[k_mishima]

Ciao a tutti, devo fare quest'esercizio per un esame a settembre ma mi sono bloccato sulla seconda richiesta.

Scrivere function C per calcolare una somma di molti addendi mediante raddoppiamento ricorsivo:
• (a) [liv.1] usando un array in memoria;
• (b) [liv.2] usando un array in un file solo parzialmente in memoria (con swapping di dati).

Per ora ho scritto questo codice, funzionante.

#include<stdio.h>
int somma_ric(int array[],int primo,int ultimo);
main()
{
//Dichiarazione
	int array[100];
	int primo,ultimo;
	int n,i, somma;

//Input
	printf("Digita quanti sono i valori da sommare ");
	scanf("%d",&n);

//Ciclo in input, legge n dati
	for(i=0;i<n;i++)
	{
		printf("Digita il %d valore da sommare ", i+1);
		scanf("%d",&array[i]);
	}
	
	primo=0;
	ultimo=n-1;

//Chiamata function ricorsiva    
	somma=somma_ric(array,primo,ultimo);	

//Output
	printf("\nLa somma e' %d\n",somma);
	
	system("pause");
}


/*Function che effettua la somma tramite raddoppiamento ricorsivo di n valori dell'array
In input prende l'array, il primo elemento della porzione di array desiderata e l'ultimo*/
int somma_ric(int array[],int primo,int ultimo)
{
	int mediano;
	int somma;

//Nell'istanza banale il primo e l'ultimo sono adiacenti e la somma è data dalla somma di questi due
	if((ultimo-primo)==1)
	{
		somma=array[primo]+array[ultimo];
		
		return somma;
	}

//Negli altri casi si effettua la ricorsione
	else
	{
        
/*Se l'ultimo e il primo sono però lo stesso elemento si restituisce semplicemente
 l'elemento stesso */

		if(ultimo==primo)
			return array[primo];

///Negli altri casi si trova l'elemento mediano e si effettua il raddoppiamento ricorsivo
		else
		{
			mediano=(primo+ultimo)/2;
			
			somma=somma_ric(array,primo,mediano)+somma_ric(array,mediano+1,ultimo);
			
			return somma;
		}
	}	
}

Le mie domande sono
1 Cos'è uno swapping di dati e come si fa?
2 Il termine "raddoppiamento ricorsivo", l'ho cercato su internet ma non ho trovato una definizione, me la dareste voi? Nell'esercizio sono andato un po' a intuito, ho fatto 2 ricorsioni. Si intende questo per raddoppiamento?

Vi ringrazio anticipatamente per le vostre risposte

[cionci]

Mi dispiace, ma anche io non ho idea cosa significhi "raddoppiamento ricorsivo". "Swapping di dati" forse si riferisce al classico swap con variabile di appoggio.

[sottovento]

In effetti e' davvero curioso.
Lavorando di fantasia, potrebbe essere che ti chiede di dividere un array in due array piu' piccoli e via dicendo? "Raddoppiamento ricorsivo" potrebbe significare semplicemente questo, no?

Swapping di dati immagino semplicemente che si tratta di caricare/scaricare la porzione di array su cui ti interessa lavorare dal file che la contiene...

[71104]

Originariamente inviato da sottovento

In effetti e' davvero curioso.
Lavorando di fantasia, potrebbe essere che ti chiede di dividere un array in due array piu' piccoli e via dicendo? "Raddoppiamento ricorsivo" potrebbe significare semplicemente questo, no?

si, anche perché la seconda funzione mi sembra uno sconquassato tentativo di somma tramite divide et impera (credo che volesse dire quello il "raddoppiamento ricorsivo").

[k_mishima]

Grazie per le risposte.

Allora per il raddoppiamento ricorsivo ci ho preso? Che fortuna

Per lo swapping, non ho capito, perchè non ho proprio idea di cosa sia, è la prima volta che sento questo termine, me lo spieghereste in maniera semplice?
Devo forse mettere l'array in un file c a parte e caricarlo? (Non so come)

[k_mishima]

up

[AngeL)]

che io sappia, uno swapping è questo:

int a = 10;
int b = 20;
int temp = a;
a = b;
b = temp;

ma non penso sia questociò che s'intende

[nuovoUtente86]

Originariamente inviato da AngeL)

che io sappia, uno swapping è questo:

int a = 10;
int b = 20;
int temp = a;
a = b;
b = temp;

ma non penso sia questociò che s'intende

Non penso intenda questo ma piuttosto lo swap derivante dall' utilizzo nei sistemi operativi di aumentare la capacità della memoria volatile attraverso altri supporti(esempio fare swap su disco quando la Ram non basta).Per cui leggendo la traccia ipotizzo una cosa del genere:
memorizzare un array su un file e caricarne in una variabile solo una porzione per volta.
Una cosa del genere

ipotizziamo che nel file c sia un array di dimensione 100.
Ne carico 10 celle per volte in un array e lavoro..finche ho utilizzato tutto l' array...

[71104]

Originariamente inviato da nuovoUtente86

Non penso intenda questo ma piuttosto lo swap derivante dall' utilizzo nei sistemi operativi di aumentare la capacità della memoria volatile attraverso altri supporti(esempio fare swap su disco quando la Ram non basta).Per cui leggendo la traccia ipotizzo una cosa del genere:
memorizzare un array su un file e caricarne in una variabile solo una porzione per volta.
Una cosa del genere

ipotizziamo che nel file c sia un array di dimensione 100.
Ne carico 10 celle per volte in un array e lavoro..finche ho utilizzato tutto l' array...

si ma abbi pazienza, è una vera e propria idiozia, è inutile fare tutto sto lavoro se poi tanto ci pensa già il sistema operativo che tra l'altro non è neanche detto che metta i dati fisicamente sul disco visto che è lui a decidere quali pagine devono restare in memoria fisica e quali devono essere swappate su disco... su Windows la cosa è programmabile ma dubito fortemente che un esercizio di quella portata richieda l'uso di API Win32...

diciamo piuttosto che a scrivere il testo di quell'esercizio dev'essere stata una donna

[nuovoUtente86]

Originariamente inviato da 71104

si ma abbi pazienza, è una vera e propria idiozia, è inutile fare tutto sto lavoro se poi tanto ci pensa già il sistema operativo che tra l'altro non è neanche detto che metta i dati fisicamente sul disco visto che è lui a decidere quali pagine devono restare in memoria fisica e quali devono essere swappate su disco... su Windows la cosa è programmabile ma dubito fortemente che un esercizio di quella portata richieda l'uso di API Win32...

diciamo piuttosto che a scrivere il testo di quell'esercizio dev'essere stata una donna

si l' esercizio non ha molto senso.Quello che dicevo io però non prevede l' interagire con le api native del sistema,ma in modo piu banale deve essere lui a simulare uno swap sulla grandezza dell' array.

Tanto per curiosità,su che livello in windows è programmabile lo swap?

[71104]

Originariamente inviato da nuovoUtente86

si l' esercizio non ha molto senso.Quello che dicevo io però non prevede l' interagire con le api native del sistema,ma in modo piu banale deve essere lui a simulare uno swap sulla grandezza dell' array.

Tanto per curiosità,su che livello in windows è programmabile lo swap?

stavo parlando molto in generale. di fattori che influenzano lo swap su disco in Windows per ora mi vengono in mente i seguenti:
- le pagine possono essere bloccate in memoria fisica con VirtualLock e poi sbloccate con VirtualUnlock
- è possibile regolare la quota per il "working set" di ciascun processo, cioè la quantità massima di memoria allocata che può stare in memoria fisica
- i drivers spesso necessitano di allocare memoria residente per vari motivi, per esempio perché devono accedervi in dei momenti in cui l'interrupt del page fault è mascherata (IRQL <= DISPATCH_LEVEL), o perché le routines che vi accedono potrebbero essere richiamate indirettamente dall'algoritmo stesso di swap; di conseguenza esiste il pool non paginato.

ma non è detto che non ce ne siano altri. per esempio se il testo dell'esercizio si riferisse realmente allo swap come lo effettua il sistema operativo, e se fosse assennato usare API Win32 per risolverlo, io aprirei il file utilizzando i flag FILE_FLAG_NO_BUFFERING e FILE_FLAG_WRITE_THROUGH (vedi CreateFile) in maniera tale da rendere effettiva qualsiasi scrittura sul file (così avrei la certezza di provocare uno swap effettivo, anche se come ho detto è una discreta idiozia).

[nuovoUtente86]

Originariamente inviato da 71104

stavo parlando molto in generale. di fattori che influenzano lo swap su disco in Windows per ora mi vengono in mente i seguenti:
- le pagine possono essere bloccate in memoria fisica con VirtualLock e poi sbloccate con VirtualUnlock
- è possibile regolare la quota per il "working set" di ciascun processo, cioè la quantità massima di memoria allocata che può stare in memoria fisica
- i drivers spesso necessitano di allocare memoria residente per vari motivi, per esempio perché devono accedervi in dei momenti in cui l'interrupt del page fault è mascherata (IRQL <= DISPATCH_LEVEL), o perché le routines che vi accedono potrebbero essere richiamate indirettamente dall'algoritmo stesso di swap; di conseguenza esiste il pool non paginato.).

cos' è un pool non paginato?

ma non è detto che non ce ne siano altri. per esempio se il testo dell'esercizio si riferisse realmente allo swap come lo effettua il sistema operativo, e se fosse assennato usare API Win32 per risolverlo, io aprirei il file utilizzando i flag FILE_FLAG_NO_BUFFERING e FILE_FLAG_WRITE_THROUGH (vedi CreateFile) in maniera tale da rendere effettiva qualsiasi scrittura sul file (così avrei la certezza di provocare uno swap effettivo, anche se come ho detto è una discreta idiozia).

tempo fa mi ponevo una domanda del genere,forse mi h indirettamente risposto,in questo caso intendi che se un file in ram viene modificato la scrittura avviene subito sul disco?

[71104]

Originariamente inviato da nuovoUtente86

cos' è un pool non paginato?

il pool non paginato. ce n'è uno solo in tutto il sistema, anche se il Task Manager indica una quota per ogni processo (i drivers spesso agiscono nel contesto di processi arbitrari e quindi per ciascun processo risulta una quantità di memoria allocata nel nonpaged pool).

il pool non paginato è il monnezzaio dove i drivers e i componenti kernel-mode allocano memoria perennemente residente; è un heap i cui frames fisici non vengono mai swappati. è chiaramente una risorsa di sistema piuttosto esigua, percui i drivers devono farne un uso limitato ed utilizzare il pool paginato ogni volta che sia possibile.
per allocare un blocco di memoria nel pool non paginato bisogna chiamare la funzione ExAllocatePoolWithTag passandole il valore NonPagedPool.

tempo fa mi ponevo una domanda del genere,forse mi h indirettamente risposto,in questo caso intendi che se un file in ram viene modificato la scrittura avviene subito sul disco?

intendo che chiamando WriteFile su un HANDLE creato dalla CreateFile con quei due flag la scrittura ha effetto immediato sul disco, cioè di fatto in runtime vedrai il disco lavorare e il led accendersi. infatti mi pare anche che in questi casi la WriteFile fallisce se la dimensione del buffer da scrivere non è un multiplo della dimensione di un settore del disco.