allocation (n x m) VS n x allocation (m)

Version imprimable

13/02/2012, 18h40
plxpy

allocation (n x m) VS n x allocation (m)

Bonjour,

Ces derniers jours, il y a eu plusieurs messages concernant des listes triées/à trier quelquefois "monstrueuses" (plusieurs millions d'éléments). Souvent, l'utilisation de tableaux a aussi été évoquée comme palliatif.

En y réfléchissant, je me suis posé la question suivante à laquelle je n'ai pas de réponse.

Peut-on se retrouver dans la situation où une allocation dynamique de (n x m) octets échouera tandis que, dans le même contexte, n allocations de m octets réussiront ? (pour une histoire de place, pas de syntaxe ou un truc dans le genre).

(n x m) octets contigus sont plus rares et difficiles à trouver que n blocs de m octets contigus, non ?

Est-ce que le système (l'OS) peut alors être amené à faire une espèce de "défragmentation" de la mémoire ou pas ? (en respectant, bien évidemment, les autres allocations faites et les adresses retournées précédemment).

Merci d'avance pour vos éclaircissements

ps : 1 allocation impose de mémoriser 1 adresse. N allocations imposent d'en mémoriser N mais ce n'est pas sur cela que ça porte, bien évidemment.
13/02/2012, 19h35
Neckara

L'avantage d'utiliser plusieurs malloc permet de faciliter les realloc futurs.

Après, quand on a beaucoup de données on utilisera surtout des Listes pour faciliter l'insertion, la suppression d'éléments.

Ensuite, un OS est très bien capable d'écrire sur la ROM quand la RAM ne suffit pas, donc pour "défragmenter" la RAM, c'est peut être possible en effet.

Mais en général, trouver un espace contigu est plus difficile de trouver n petits espaces.
Si il y a de la place pour le grand espace contigu, c'est qu'il y a en a pour les petits espaces, mais la réciproque n'est pas vraie.
13/02/2012, 20h53
anacharsis

@ Neckara

Citation:

un OS est très bien capable d'écrire sur la ROM

fais attention! pour les gens de ma génération ça craint un max ;=)

A+
13/02/2012, 21h10
Neckara

Le fait que l'OS soit capable d'écrire sur la ROM suggère bien que l'OS peut déplacer des segment de RAM en fonction de l'utilisation de la RAM.

Donc si un OS est capable de gérer cela, il est probable qu'il puisse aussi "arranger" la RAM pour avoir plus d'espace contigu.

Mais je n'ai jamais dit qu'utiliser de la ROM en tant que RAM était bien.
La ROM est beaucoup trop lente et n'est pas faite pour se substituer à la RAM.

Sinon, il me semble que les OS ont une technique bien particulière pour gérer la RAM, il faudrait se renseigner là-dessus.
13/02/2012, 21h32
Derek Corgan

Comme l'indique anacharsis écrire sur la ROM cela risque d'être difficile.;)

malloc reserve un espace vu comme contigüe dans le "tas".

Le tas peu être de la RAM (c'est préférable) ou de la mémoire de masse s'il n'y plus de place.
n allocation de (m) octets peut être intéressant si :
- risque d'avoir une allocation qui échoue (c'est rare) car n*m est très très élevé.
- si l'on souhaite faire des tris sur ces blocs.
Dans le cas de liste chainée l'on modifie uniquement les liens sans déplacer les valeurs.

Merci pour vos réponses, même si j'avoue avoir un peu de mal à suivre quand ça descend trop bas, coté hard.

Sinon - j'aurais pu y penser avant ! - il suffit d'essayer :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
 
#define MEGA        (1024*1024)
#define MEGA_500    (500*MEGA)
#define MEGA_10     (10*MEGA)
 
int main(int argc,char *argv[])
{
    char    *m500[8];   // 4 Go de mémoire
    int      i,j;
 
    for (i=0;;i++)
    {
        if ((m500[i] = malloc(MEGA_500)) == NULL)
            break;       
        // Sans remplissage, la mémoire utilisée qui est affichée dans le
        // moniteur système ne bouge pas (même si je sors de la boucle
        // au bout du meme nombre d'iterations). Avec remplissage, j'assure
        memset(m500[i],i,MEGA_500);
    }
 
    fprintf(stderr,"%d x 500 Moctets alloues\n",i);
    fprintf(stderr,"echec pour les 500 Mo suivants\n");
 
    for (i=0;;i++) 
    {
        char *m10 = malloc(MEGA_10);
        if (m10 == NULL) break;
        memset(m10,'X',MEGA_10);
    }
 
    fprintf(stderr,"%d x 10 Mo alloués en plus\n",i);
 
    // les blocs de 500Mo sont ils toujours dans le même état ?
    for (i=0;i<8;i++)
        if (m500[i])
        {
            fprintf(stderr,"verif bloc 500 Mo no %d\n",i);
            for (j=0;j<MEGA_500;j++)
                assert(m500[i][j] == i);
        }
 
}

Sous Linux (Ubuntu 11.04, 32 bits), l'exécution donne ça (avant le lancement, environ 600Mo sont déjà utilisés) :

Code:

1
2
3
4
5
6
7
8
9
plx@sony:~$ ./memory
5 x 500 Moctets alloues
echec pour les 500 Mo suivants
54 x 10 Mo alloués en plus
verif bloc 500 Mo no 0
verif bloc 500 Mo no 1
verif bloc 500 Mo no 2
verif bloc 500 Mo no 3
verif bloc 500 Mo no 4

500 Mo, ça plante mais, par paquets de 10Mo, on en passe 540.

Ca peut parfois, selon le contexte, la taille des données qu'on manipule et la façon dont on s'y prend, être important.

14/02/2012, 08h59
mala92

Citation:

Envoyé par anacharsis

Citation:

un OS est très bien capable d'écrire sur la ROM

fais attention! pour les gens de ma génération ça craint un max ;=)

A+

Ca fait un bail que je ne fais pas du très bas niveau, mais ROM ne veut plus dire ReadOnly Memory ?
14/02/2012, 09h55
Bktero

Pour moi cela veut bien dire Read Only Memory :)

Plxpy, la question originale est intéressante. Je pense d'ailleurs que ton code exemple répond à la question.
14/02/2012, 10h08
plxpy

Citation:

Envoyé par Bktero

Je pense d'ailleurs que ton code exemple répond à la question

C'est ce que je pense aussi d'où le passage en "Résolu" dans la foulée de mon dernier message.

Sinon, pendant que j'y suis ...

Citation:

Envoyé par plxpy

(n x m) octets contigus sont plus rares et difficiles à trouver que n blocs de m octets contigus, non ?

n'était pas vraiment une question que je me posais. C'est au niveau du hard que j'atteins très vite mes limites, mais pour ça, pas de problème !
14/02/2012, 10h47
plxpy

... "tant qu'à faire" et "pendant qu'on y est", épuisons le sujet !

Je me posais la question suivante :

Citation:

Envoyé par plxpy

Est-ce que le système (l'OS) peut alors être amené à faire une espèce de "défragmentation" de la mémoire ou pas ? (en respectant, bien évidemment, les autres allocations faites et les adresses retournées précédemment).

Au moins, sur mon système (rappel : Ubuntu 11.04 32 bits), la réponse est non. J'arrive à allouer, par petits bouts, 540 Mo alors qu'une allocation unitaire de 500 Mo échoue.
14/02/2012, 18h25
Neckara

http://fr.wikipedia.org/wiki/M%C3%A9moire_morte

Le terme anglais ROM prête à confusion car il désigne deux choses :
- Une mémoire qui ne s'efface pas même hors-tension.
- Une mémoire qui ne peut être ni programmée ni effacée par les utilisateurs.

Je parlais évidement du disque dur quand je parlais de mémoire ROM.
14/02/2012, 19h30
Obsidian

Citation:

Envoyé par Neckara

http://fr.wikipedia.org/wiki/M%C3%A9moire_morte

Le terme anglais ROM prête à confusion car il désigne deux choses :
- Une mémoire qui ne s'efface pas même hors-tension.
- Une mémoire qui ne peut être ni programmée ni effacée par les utilisateurs.

La page Wikipédia est trop imprécise : « ROM » signifie bien Read Only Memory et désigne bien une mémoire électronique qui ne peut être modifiée. En informatique élémentaire, on commence souvent par dire que le contenu de la RAM peut être modifié mais qu'il a perdu dès la mise hors tension et que celui de la ROM ne peut être altéré mais perdure en l'absence d'alimentation.

C'est techniquement vrai mais c'est un dogme qui a été établi à une époque où on n'utilisait pas les mémoires flash ou similaires. En outre, Il est tout-à-fait possible de disposer de mémoire RAM non volatile si elle est alimentée par une pile, par exemple. C'est important parce que les termes ROM et RAM sont liés à certaines technologies de circuits mémoire.

Les termes de « mémoire vive » et de « mémoire morte » ont été choisis pour imiter les notions de planète vive ou de planète morte. La première est versatile, la seconde ne changera plus jamais mais gardera ses derniers traits pendant des millions d'années.

Ensuite, on ne peut pas utiliser les acronymes RAM et ROM dans un sens général car ils sont associés à certains types de technologies. une EEPROM, par exemple, n'a rien à voir avec une RAM. Les temps de réponses sont complètement différents et la manière de les programmer l'est encore plus : même si elle est purement électrique, une EEPROM s'efface entièrement et se programme dans des conditions de tension spécifiques.

Citation:

Je parlais évidement du disque dur quand je parlais de mémoire ROM.

En aucun cas, tu ne peux utiliser le terme ROM pour parler du disque dur. On parle parfois de « mémoire de masse » pour regrouper tous les supports de stockage. Il en reste qu'un disque dur est un périphérique, qui s'exploite logiciellement et qui nécessite une certaine quantité de mémoire vive libre pour pouvoir être utilisé.

Les systèmes de mémoire virtuelle, même s'ils mettent en place une couche d'abstraction d'assez bas niveau, ne font que masquer une procédure de sauvegarde et de chargement qui était jadis menée directement par le programmeur.