精华内容
下载资源
问答
  • linux内存管理数据结构

    千次阅读 2016-04-21 23:46:31
    linux内存管理数据结构linux内存管理数据结构 一物理空间管理 1 页表项 2 物理页面管理对象page 二内存分区 1 过去的分区 2 当下的分区情况 三 虚拟空间管理 1 进程虚存区域 2 进程地址空间 3 进程地址空间和...

    linux内存管理之数据结构


    一、物理空间管理

    1.1 页表项

    [include /asm-i386/page.h: 39]

     39 #if CONFIG_X86_PAE
     40 typedef struct { unsigned long pte_low, pte_high; } pte_t;
     41 typedef struct { unsigned long long pmd; } pmd_t;
     42 typedef struct { unsigned long long pgd; } pgd_t;
     43 #define pte_val(x)  ((x).pte_low | ((unsigned long long)(x).pte_high << 32))
     44 #else
     45 typedef struct { unsigned long pte_low; } pte_t;
     46 typedef struct { unsigned long pmd; } pmd_t;
     47 typedef struct { unsigned long pgd; } pgd_t;
     48 #define pte_val(x)  ((x).pte_low)
     49 #endif

    其中pte_t为页表项,在i386当中,一个页的大小为4K,这意味着也表项的低12位是0,高20位是物理页的起始地址。所以低12位可以用来保存页面保护和访问权限信息,页面保护和访问权限信息被定义在pgprot_t中
    [include/asm-i386/page.h : 52]

     52 typedef struct { unsigned long pgprot; } pgprot_t;

    pgprot_t的低12位定义如下:
    [include/asm-i386/pgtable.h : 152]

    152 #define _PAGE_BIT_PRESENT   0
    153 #define _PAGE_BIT_RW        1
    154 #define _PAGE_BIT_USER      2
    155 #define _PAGE_BIT_PWT       3
    156 #define _PAGE_BIT_PCD       4
    157 #define _PAGE_BIT_ACCESSED  5
    158 #define _PAGE_BIT_DIRTY     6
    159 #define _PAGE_BIT_PSE       7   /* 4 MB (or 2MB) page, Pentium+, if present.. */
    160 #define _PAGE_BIT_GLOBAL    8   /* Global TLB entry PPro+ */
    161     
    162 #define _PAGE_PRESENT   0x001
    163 #define _PAGE_RW    0x002
    164 #define _PAGE_USER  0x004
    165 #define _PAGE_PWT   0x008
    166 #define _PAGE_PCD   0x010
    167 #define _PAGE_ACCESSED  0x020
    168 #define _PAGE_DIRTY 0x040
    169 #define _PAGE_PSE   0x080   /* 4 MB (or 2MB) page, Pentium+, if present.. */
    170 #define _PAGE_GLOBAL    0x100   /* Global TLB entry PPro+ */

    将pgprot_t和pte_t的高20位合并即可得到真正的页表项,该操作有宏__make_pte来完成
    [include/asm-i386/pgtable-2level.h : 61]

     61 #define __mk_pte(page_nr,pgprot) __pte(((page_nr) << PAGE_SHIFT) | pgprot_val(pgprot))

    当MMU进行映射的时候,会首先检查P位,也就是_PAGE_BIT_PRESENT(BIT0)位,如果该位为1,则进行映射,否则就产生一个缺页中断。

    1.2 物理页面管理对象page

    内核维护一个全局的mem_page的page数组,每个page代表着一个物理页面,整个数组内的page就代表了全部物理页面。在内核定义中,可以用pte_t高20位当成索引去访问mem_page数组,从而得到该物理页的page结构。page结构定义如下:
    [include/linux/mm.h : 134]

    126 /*
    127  * Try to keep the most commonly accessed fields in single cache lines
    128  * here (16 bytes or greater).  This ordering should be particularly
    129  * beneficial on 32-bit processors.
    130  *
    131  * The first line is data used in page cache lookup, the second line
    132  * is used for linear searches (eg. clock algorithm scans). 
    133  */
    134 typedef struct page {
    135     struct list_head list;
    136     struct address_space *mapping;
    137     unsigned long index;
    138     struct page *next_hash;
    139     atomic_t count;
    140     unsigned long flags;    /* atomic flags, some possibly updated asynchronously */
    141     struct list_head lru;
    142     unsigned long age;
    143     wait_queue_head_t wait;
    144     struct page **pprev_hash;
    145     struct buffer_head * buffers;
    146     void *virtual; /* non-NULL if kmapped */
    147     struct zone_struct *zone;
    148 } mem_map_t;

    如果页面的内容来自一个文件,index代表该页面在文件中的序号,当页面被交换出内存,但还保留内容作为缓冲时,index指名了页面的去向。
    系统中的每一个物理页面都对应了一个page结构,也就是说一个page结构是物理页面的“登记信息”,或者说“管理信息”。在系统初始化时,所有page结构被建立,并且page作为一个物理页面的管理结构,当一个page结构被分配出去的时候,就表示了一个物理页面被分配使用。

    二、内存分区

    2.1 过去的分区

    系统内存被分为两个区:

    • ZONE_DMA
    • ZONE_NORMAL

    (根据系统配置,还可以增加第三个区给ZONE_HIGHMEN,内核访问超过1G的物理空间)
    这意味着mem_page数组中的page也被相应分为ZONE_DMA和ZONE_NORMAL两组,而既然已经分组了,就会有分组管理信息,故而每个内存区域具有一个区域管理结构:zone_struct。定义如下:
    [include/linux/mmzone.h : 24]

     24 typedef struct zone_struct {
     25     /*
     26      * Commonly accessed fields:
     27      */
     28     spinlock_t      lock;
     29     unsigned long       offset;
     30     unsigned long       free_pages;
     31     unsigned long       inactive_clean_pages;
     32     unsigned long       inactive_dirty_pages;
     33     unsigned long       pages_min, pages_low, pages_high;
     34 
     35     /*
     36      * free areas of different sizes
     37      */
     38     struct list_head    inactive_clean_list;
     39     free_area_t     free_area[MAX_ORDER];
     40 
     41     /*
     42      * rarely used fields:
     43      */
     44     char            *name;
     45     unsigned long       size;
     46     /*
     47      * Discontig memory support fields.
     48      */
     49     struct pglist_data  *zone_pgdat;
     50     unsigned long       zone_start_paddr;
     51     unsigned long       zone_start_mapnr;
     52     struct page     *zone_mem_map;

    其中39行的free_area为一组空闲区块队列,组内有“连续的空闲物理页面”和“离散的空闲物理页面”两种队列。因为分配内存的时候有可能要求分配连续的物理页,所以将连续的物理页和离散的物理页分开管理。而offset则表示该分区在mem_map中的起始号。

    2.2 当下的分区情况

    但随着NUMA*(非均质储存结构)的引入,分区发生了变化。NUMA指的是,在当下多处理器结构中,每个CPU都具有本地储存,称之为内存节点,而多个CPU之间又有共享的内存。CPU访问本地储存的速度要快于访问共享储存的速度,也就是说,在一个连续的物理地址上,储存器的访问速度不一致,这就叫做NUMA。在NUMA结构中,如果要分配几个连续的物理页,一般要求分配在质地相同的储存器内。为此,内核定义了一个pglist_data结构,每个pglist_data代表这一个内存节点,每个内存节点都可以拥有ZONE_DMA和ZONE_NORMAL(根据配置还可能有ZONE_HIGHMEN)两个区,也就意味这每个内存节点都有一个page数组和一个zone_t数组,用于管理该节点上两个区的所有page。总的来说,原来将整个物理空间分为三个区来管理的模式,现在变成了将整个物理空间分为若干内存节点,各个内存节点将节点上的所有物理空间进行分区管理*。pglist_data定义如下:
    [include/linux/mmzone.h : 79]

     79 typedef struct pglist_data {
     80     zone_t node_zones[MAX_NR_ZONES];
     81     zonelist_t node_zonelists[NR_GFPINDEX];
     82     struct page *node_mem_map;
     83     unsigned long *valid_addr_bitmap;
     84     struct bootmem_data *bdata;
     85     unsigned long node_start_paddr;
     86     unsigned long node_start_mapnr;
     87     unsigned long node_size;
     88     int node_id;
     89     struct pglist_data *node_next;
     90 } pg_data_t;

    80: node_zones为该内存节点上的三个分区管理结构。
    81: node_zonelists为一个指向zone_t指针数组链表(链表的每个节点上都挂着一个数组),链表上的每个节点包含一个指针数组,该数组的元素按照待定的次序指向每个储存节点的node_zones的数组。前面说过,在NUMA中分配物理页,往往要求在同一内存节点上分配,如果这时当前节点的空闲连续物理页无法满足分配,则可以通过这个指针数组按照0、1、2、3、4……的次序查找其它储存节点上的node_zones,直到找到一个可以满足分配的储存节点。指针数组中的元素排列次序,就称为一种分配策略。比如说有储存节点A、B、C、D、E。而node_zoneslist某节点上的指针数组元素排列次序为pA、pC、pD、pB。这个策略就规定了:要分配物理页的时候首先尝试从A分配,如果A不能满足,就查找B,如果B不能满足就查找C….而如果该点的指针数组为pC、pA、pD、pB,则这个策略规定:要分配物理页的时候首先尝试从C分配,如果C不能满足,就查找A,如果A不能满足就查找D….
    所以把node_zonelists称为分配策略链表也不为过。
    82: node_mem_map数组包含了该内存节点上的所有page结构。

    三、 虚拟空间管理

    3.1 进程虚存区域

    每一个进程都拥有自己的3G进程空间和1G共享的内核空间。很少会有进程占用到3G的空间,往往是占用多个离的虚存区域。虚存区域的抽象数据结构定义如下:
    [include/linux/mm.h : 41]

     41 struct vm_area_struct {
     42     struct mm_struct * vm_mm;   /* VM area parameters */
     43     unsigned long vm_start;
     44     unsigned long vm_end;
     45 
     46     /* linked list of VM areas per task, sorted by address */
     47     struct vm_area_struct *vm_next;
     48 
     49     pgprot_t vm_page_prot;
     50     unsigned long vm_flags;
     51 
     52     /* AVL tree of VM areas per task, sorted by address */
     53     short vm_avl_height;
     54     struct vm_area_struct * vm_avl_left;
     55     struct vm_area_struct * vm_avl_right;
     56 
     57     /* For areas with an address space and backing store,
     58      * one of the address_space->i_mmap{,shared} lists,
     59      * for shm areas, the list of attaches, otherwise unused.
     60      */
     61     struct vm_area_struct *vm_next_share;
     62     struct vm_area_struct **vm_pprev_share;
     63 
     64     struct vm_operations_struct * vm_ops;
     65     unsigned long vm_pgoff;     /* offset in PAGE_SIZE units, *not* PAGE_CACHE_SIZE */
     66     struct file * vm_file;
     67     unsigned long vm_raend;
     68     void * vm_private_data;     /* was vm_pte (shared mem) */
     69 };

    43: vm_start 该虚存区域的开始地址
    44: vm_end 该虚存区域的结束地址
    47: vm_next 用于将进程空间内所有的内存区域组成一个单项链表进行管理
    49: pgprot_t 页面保护权限,因为一个内存区域中只有一个用于描述页面访问权限pgprot_t这意味这在同意个区域中的所有页面访问权限是一致的。
    54~55:

     53     short vm_avl_height;
     54     struct vm_area_struct * vm_avl_left;
     55     struct vm_area_struct * vm_avl_right;

    这三个成员用于将内存区域组成一棵AVL树,因为常常需要在进程空间中查找某个内存区域。如果用线性链表查找的方式,会影响效率。
    61: vm_next_share ????
    62 vm_pprev_share ???
    64 vm_ops指向一个struct ,实际上是一个跳转表:

    120 struct vm_operations_struct {
    121     void (*open)(struct vm_area_struct * area);
    122     void (*close)(struct vm_area_struct * area);
    123     struct page * (*nopage)(struct vm_area_struct * area, unsigned long address, int write_access);
    124 }; 

    该跳转表用于虚存区间的打开,关闭和建立,其中nopage在发生缺页中断的时候会被调用。

    3.2 进程地址空间

    在vm_area_struct结构中有一个成员vm_mm指向了mm_struct结构,这个结构是整个进程虚存空间的数据抽象,它管理这进程中的所有vm_area_struct抽象,换句话mm_struct是一个更高层的数据结构。定义如下:
    [include/linux/mm.h : 203]

    203 struct mm_struct {
    204     struct vm_area_struct * mmap;       /* list of VMAs */
    205     struct vm_area_struct * mmap_avl;   /* tree of VMAs */
    206     struct vm_area_struct * mmap_cache; /* last find_vma result */
    207     pgd_t * pgd;
    208     atomic_t mm_users;          /* How many users with user space? */
    209     atomic_t mm_count;          /* How many references to "struct mm_struct" (users count as 1) */
    210     int map_count;              /* number of VMAs */
    211     struct semaphore mmap_sem;
    212     spinlock_t page_table_lock;
    213 
    214     struct list_head mmlist;        /* List of all active mm's */
    215 
    216     unsigned long start_code, end_code, start_data, end_data;
    217     unsigned long start_brk, brk, start_stack;
    218     unsigned long arg_start, arg_end, env_start, env_end;
    219     unsigned long rss, total_vm, locked_vm;
    220     unsigned long def_flags;
    221     unsigned long cpu_vm_mask;
    222     unsigned long swap_cnt; /* number of pages to swap on next pass */
    223     unsigned long swap_address;
    224 
    225     /* Architecture-specific MM context */
    226     mm_context_t context;
    227 };

    204: mmap作为进程的所虚存区域构成的链表的链表头。
    205: mmap_avl指向进程所有虚存区域构成的AVL树的根节点。
    206: mmap_cache指向最近一次使用的虚存空间。由于程序具有局部性,常常连续访问同一片区域的空间,所以这里记录了最近一次使用的虚存区域,是一种缓存机制。
    207: pgd指向了进程的页目录
    208~212:
    虽然每个进程只能拥有一个mm_struct,但是一个mm_struct却能为多个进程所用,最显著的例子就是父进程使用vfork创建子进程。这样就会涉及到资源进程和引用计数的问题,其中mm_users、mm_count、map_count作为引用计数,而mmap_sem、page_table_lock则用来保证访问的互斥。
    216~219:用于说明整个进程地址空间中各个段的起始和结束地址,比如代码段,数据段,栈段,环境变量段等等。(注,这里的段是指镜像段,不能与段页管理中的段相混淆)

    3.3 进程地址空间和进程虚存区域的关系

    每个进程都拥有一份mm_struct,它是整个3G进程空间的数据抽象,而由于进程往往不会整个3G空间都使用,而是使用不同的离散虚存区域,并且每个离散区域的使用都不一样,比如说栈所在的区域和代码段所在的区域的使用就不一样,从而导致各个区域的属性、需要的管理操作都不一致,所以就将各个虚存区域提炼出来单独管理,然后就再将所有虚存区域组成一颗AVL树交由mm_struct统一管理。这中设计思想属于提炼差异,或者说提炼子类的思想。

    展开全文
  • 收集的两本有关算法的电子书,一本是C++内存管理的,另外一本是数据结构的,感兴趣的可以看看。
  • 记笔记的过程,写出自己的问题,感想,边看边总结. 在看视频时,或者书籍学习时,有什么感想,疑问,可以停...程序为什么需要内存 程序运行的目的是 的到一定结果,这个结果可以解决实际需求问题,新问题不断产生,程序也需
    • 记笔记的过程,写出自己的问题,感想,边看边总结.

      在看视频时,或者书籍学习时,有什么感想,疑问,可以停下来,记录好,或者有什么理解,什么启示,收获都可以记下来,笔记看不看不重要,重要的是记笔记的过程,眼过千遍不如手过一遍.

      让学习以理解为主,而不是以记忆为主!

       

       

      1. 程序为什么需要内存

      程序运行的目的是

      的到一定结果,这个结果可以解决实际需求问题,新问题不断产生,程序也需要不断重新编写.得到不同结果.

       

      计算机就是在计算数据那么 数据 的重要性不言而喻.

       

       

      计算机程序 = 代码 + 数据

       

      代码用来加工数据,改变数据得到我们想要的结果.

       

       

       

      程序 运行的目的:    结果        过程(不在乎结果,主要是过程是否运行,凡是C语言函数返回值是Void的都不在乎结果)

       

      函数:

      int  add( int a, int b)

      {

      return  a + b;

       

      }

       

      void add(int a, int b)

      {

      int c;

      c = a + b;

      printf("c = %d.\n", c);

      }//这个函数的执行重在过程(printf),返回值不重要。

       

      问题 函数的返回问题

       

      计算机程序运行其实就是很多函数的运行,程序的本质就是函数,函数的本质就是加工数据的动作。

       

       

       

      冯诺依曼机构是数据和代码放在一起、

      哈佛结构是数据和代码分开存放

       

      什么是代码:  函数

      什么是数据: 全局变量、局部变量。

       

      S5PV210中运行的linux系统上,运行程序时,应用程序的代码和数据都在DRAM,所以这种机构就是冯诺依曼机构;在单片机中,程序代码放在FlsahNorflash)中,然后程序在Flash原地运行,程序中的数据(全局变量、局部变量)不能放在RAM,这种就叫哈佛结构

       

       

      问题 DRAM 动态内存  ||  SRAM是静态内存

       

       

       

      为什么需要内存?

      内存用来存储可变数据,数据在程序中表现为全局变量、局部变量等(特殊的:gcc中,其实常量也是存储在内存中的)(大部分单片机中,常量是存储在flash中的,也就是代码段),  

       

      问题 GCC编译

      编程的关键几乎在于 内存管理     譬如  数据结构,数据如何组织、算法,为了更优秀的方法来加工数据,既然与数据有关就里离不开内存

       

      那么如何管理内存?

       

      问题在于 写程序时,如何对内存进行管理,尤其是在程序运行时,内存的消耗量,内存对程序来说是一种的资源,

       

      操作系统掌握多有的硬件系统,因为内存很大,所以操作系统把内存分成一个个的页面(一块,4KB),然后以页面为单位管理。再细分到页里里面 以字节为单位管理。

      操作系统管理内存的原理分厂复杂,但是我们不需要了解这些细节。操作系统给我们提供了内存管理的一些接口,我们只需要用API即可管理内存。

      譬如C语言中使用 malloc free 这些接口 管理内存

       

       

      没有操作系统时,其实就是裸机程序,程序需要操作内存,编程者需要自己计算内存使用和安排

       

      从语言角度: 不同语言提供了不同的操作内存的接口。

      譬如汇编 根本没有任何内存管理,内存管理全靠自己,汇编中操作内存时直接使用内存地址譬如0xd0020010),很麻烦;

      譬如C语言中,通过APImalloc free)来访问系统内存

      譬如C++,用new来创建对象(其实就是为对象分配内存),如果此对象用完后忘记Delete,就会造成这个对象的内存不能释放,这就是内存泄露。

       

       

       

       

      1. 位、字节、半字、字的概念和内存位宽

       

      什么是内存?

      从逻辑角度:内存可以随机访问(给一个地址,就可以访问这个内存地址)、并且可以读写(在裸机上可限制读写,但是一般都是可读写的);内存在编程中天然用来存放变量的。一个变量对应内存中的一个单元。

       

      内存位宽

      从硬件角度讲:硬件内存实现本身是有宽度(内存芯片的实际数据总线数)的,也就是说有些内存条是8位的,而有些就是16位的,那么需要强调的是内存芯片之间是可以并联的。

       

      位和字节

       

      内存单元的大小:

      位(1bit

      字节(8bit

      半字(一般是16bit

      字(一般是32bit

       

      bit就是计算机中信息的最基础单元,

       

      字和半字

       

      历史上曾经出现过16位、32位、64位系统三种,

      平台不一样,子和半字的bit定义不一样,这些单位就提有多少bit 是依赖平台的

       

       

       

       

      问题 有没有8位系统

       

       

      1. 内存编址和寻址、内存对齐

      内存编址方法:

       

      内存地址(一个数字)指向一个空间,一对一且永久不变

       

      在程序运行时,计算机中CPU实际只通过内存地址,不需要找到这个空间在哪里?  

      这个设定由硬件设计保证。

       

      关键:内存编址是以字节为单位的

       

      随便给个内存地址,这个内存地址对应的空间的大小是固定的,就是一个字节(8bit

      如果把内存比为一栋大楼,楼里的一个个房间就是一个个内存空间,这个空间是固定大小 8bit

       

      内存和数据类型的关系:

       

      C语言中基本数据类型:  char short int long float double   

       

      int 整形   (整数类型,整个整体现在它和CPU本身的数据位宽是一样的)譬如32位的CPU,整形就是32位,int就是32位(4个字节)的

      数据类型和内存的关系:

      数据类型是用来定义变量的,而这些变量需要存储、运算在内存中。所以数据类型必须和内存相匹配才能获得做好的性能,否则可能不工作或者效率低下。

       

      32位系统中定义变量做好用int,因为这样效率高。原因在于32位的系统本身配合内存等也是32位,这样的硬件配置天生适合定义32位的int类型变量,效率最高。也能定义8位的char类型变量或者16位的short类型变量,但是实际上访问效率不高。

       

      在很多32位环境下,我们实际定义bool类型变量(实际只需要一个bit就够了)都是用int来实现bool的。

       

      譬如   定义  bool b1;时,编译器实际帮我们32的内存来存储这个bool变量b1,编译器这个做实际浪费了31位的内存,但是好处是效率高

       

      问题:省内存和运行效率,二者需具体情况解决。

       

       

      内存对齐

       

      C int a;   定义哟个int 类型变量,在内存中必须分配4个字节来存储这个a  两种方式:

      第一种:0 1 2 3       

      对齐访问

      第二种 1 2 3 4     或者 2 3 4 5 或者 3 4 5 6

      非对齐访问

       

       

      内存的对齐方式不是逻辑的问题,是硬件的问题。 从硬件角度,32位的内存它 0 1 2 3 四个单元本身裸机就有相关性,这四个字节组合起来当做一个int 硬件上就是合适的,效率就高。

       

      对齐访问很配合硬件,所以效率很高;非对齐访问因为硬件本身不搭配,所以效率不高。

       

       

       

      从内存编址看数组的意义

       

      1. C语言如何操作内存

       

       

      C语言对内存地址的封装

      譬如C语言中   int a;   a = 5;  a += 4;       //  a == 9;

       

       

      结合内存来解析C语言语句的本质:

      int a;     // 编译器帮我们申请了 1 int 类型 的内存格子(长度是4 字节。地址只有编译器知道。我们是不知道的,也不需要知道。)并且把符号 a 和这个格子绑定。

       

      a = 5; // 编译器会把 5 放到 a 这个格子

       

      C语言中数据类型的本质含义是: 表示一个内存格子的长度和解析方法。

      数据类型决定长度的含义:以一个内存地址(一个字节的长度单位(固定的))开始,长度是多少,一次往后面延生多少连续长度

      数据类型决定解析方法: 通过内存地址不同的类型指定这个内存地址(包括整个长度)指向的内存单元格子中二进制数的解析方法。

      问题 强制类型转换

       

       

      int   *0;

       

      C语言中,函数就是一段代码的封装。函数名的实质就是这一段代码的首地址。所以说函数名的本质也是一个内存地址。

       

      用指针来间接访问内存

       

      关于类型(不管是普通变量类型int float 等,还是 指针类型int * float * 等),只要记住:

      类型只是对后面数字或者符号(代表的是内存地址)  所表征的内存的一种长度规定和解析方法而已。

       

      C语言中的指针,全名叫指针变量,指针变量其实很普通没有任何区别。譬如 int a int *p 其实没有任何区别,a p 都代表一个内存地址 (譬如是0x20000000,但是这个内存地址(0x20000000)的长度和解析方法不同。a int 型所以a 的长度是4字节,解析方法是按照int 的规定的;pint * 规定的(0x2000000开头的连续4字节中存储了1个地址,这个地址所代表的内存单元中存放的是一个int类型的数)

       

       

      用数组来管理内存

      数组管理内存和变量其实没有本质区别,只是符号的解析方法不同。 (普通变量、数组、指针变量其实都没有本质差别,都是对内存地址的解析,只是解析方法不一样)

      int a;        //编译器分配4字节长度,并且把首地址和符号a绑定起来

      int b[10];  //编译器分配40字节长度,并且把首元素首地址和符号b 绑定起来

      int *c;       //编译器分配4字节长度,并且把首地址和符号c绑定起来,而与c地址绑定的首地址开始,存放了一个地址,地址的内存单元存放的是一个int 类型的数

       

      数组中第一个元素(a[0])就称为首元素;每一个元素类型都是int,所以长度都是4,其中第一个字节的地址

      就称为首地址;首元素a[0]的首地址就称为首元素首地址。

       

       

       

      1. 内存管理之结构体
        1. 数据结构这门学问的意义
          1. 数据结构就是研究数据如何组织(在内存中排布),如何加工的学问
        2. 最简单的数据结构:数组
          1. 为什么要有数组?
            1. 因为程序中有好多个类型相同、意义相关的变量需要管理,这时候需要管理,这时候如果用单独的变量来做程序看起来比较乱,用数组来管理会更好管理。

      譬如: int ages[20];

      1. 数组的优势和缺陷
        1. 优势:数组比较简单,访问用下标,可以随机访问。
        2. 缺陷:
          1. 数组所有元素类型必须相同
          2. 数组的大小必须在定义时给出,而且一旦确定不能再改
      2. 结构体隆重登场
        1. 结构体发明出来就是为了解决数组的第一个缺陷:数组中多有元素类型必须相同

      譬如:我们要管理三个学生的年龄(int 类型),怎么办?

      第一种解法:用数组   int age[3];

      第二种解法:用结构体  

      struct ages

      {

      int age1;

      int age2;

      int gae3;

      };

      struct ages age;

      分析总结:在这个示例中,数组要比结构体好。但是不能得出结论说数组就比结构体好,在包中元素类型不同时就只能用结构体而不能用数组了;

      struct people

      {

      int age;

      char name[20];

      int height;

      };

      struct people people;

      1. 题外话:结构体内嵌指针实现面向对象
        1. 总的来说:C语言是面向过程的,但是C语言写出的linux系统是面向对象的。
        1. 非面向对象的语言,不一定不能实现面向对象的代码。只是说用面向对象的语言来实现面向对象要更加简单一些、直观一些、无脑一些。
        2. C++java等面向对象的语言来实现面向对象简单一些,因为语言本身帮我们做了很多事情;但是用C来实现面向对象很麻烦,看起来也不容易理解,这就是为什么大多数人学过C语言却看不懂linux代码的原因。

      struct s

      {

      int age;                                 //普通变量

      void (*pFunc)(void);          //函数指针,指向void func(void)这类的函数

      }

      这样包含了函数指针的结构体就类似于面向对象的class,结构体中变量类似与class中的成员变量,结构体中的函数指针类似与class中的成员方法

      1. 内存管理之栈
        1. 什么是栈
          1. 栈是一种数据结构,C语言中使用栈来保存局部变量。
          2. 栈是被发明出来管理内存的
        2. 栈管理内存的特点
          1. 先进后出   FILO    first in last out   
          2. 先进先出   FIFO    first in first put    队列
          3. 栈的特点是入口即出口,只有一个口,另一个是堵死的,所以先进去的必须后出来。
        3. 栈的应用举例:局部变量
          1. 我们在C中定义一个局部变量时(int a,编译器会在栈中分配一段空间(4字节)给这个局部变量用(分配时栈顶指针会移动给出空间,给局部变量a用的意思就是,将这4字节的占的内存地址和我们定义的局部变量名a给关联起来 ),对应栈的操作是入栈。
          1. 注意这里栈指针的移动和内存分配是自动(栈自己完成,不用我们写代码去操作)。
          2. 然后等我们函数退出的时候,局部变量要灭亡。对应栈的操作时弹栈(出栈)。出栈时也是栈顶指针移动将栈空间中与a关联的那4个字节空间释放。这个动作也是自动的,也不用人写代码。

      栈的优点:栈管理内存,好处是方便,分配和最后回收都不用程序员操心,C语言自动完成。

      定义局部变量,其实就是在栈中通过移动栈指针来给程序提供一个内存空间和这个局部变量名绑定。因为这段内存空间在栈上,而栈内存是反复使用的(脏的,上次用完没清零的),所以说使用栈来实现的局部变量定义时如果不显示初始化,值就是脏的。如果你显式初始化怎么样?

      C语言是通过一个小手段来实现 局部变量 的初始化的。

      int a = 15;//局部变量定义时初始化

      //C语言编译器会自动把这行转为:

      int a;                 //局部变量定义

      a = 15;                    //普通的赋值语句

      1. 栈的约束(预定栈大小不灵活,怕溢出)
        1. 栈是有大小的,所以栈内存大小不好设置,如果太小怕溢出,太大怕浪费内存。 (这个缺点有点像数组)
        2. 其次,栈的溢出危害很大,一定要避免。所以我们在C语言中定义局部变量时不能定义太多或者太大(譬如不能定义局部变量时int a[10000];使用递归来解决问题时一定要注意递归收敛)      
      1. 内存管理之堆
        1. 什么是堆?
          1. 堆(heap)是一种内存管理方式。 内存管理对操作系统来说是一件非常复杂的事情
            1. 内存容量很大
            2. 内存需求在时间和大小块上没有规律(操作系统上运行着大量的进程随时都会申请或者释放内存,申请或者释放的内存块大小随意)
          2. 内存管理方式特点就是自由(随时申请、释放;大小块随意)。堆内存是操作系统划归给堆管理器(操作系统中的一段代码,属于操作系统中的一段代码,属于操作系统的内存管理单元)来管理的,然后向使用者(用户进程)提供APImalloc free)来使用堆内存
          3. 什么时候使用堆内存?    需要内存容量比较大时,需要反复使用及释放时;很多数据结构(譬如链表,二叉树)的实现都要使用堆内存。
        2. 堆内存的特点
          1. 容量不限,常规使用的需求容量都能满足
          2. 申请及释放都需要手工进行,需要程序员写代码明确进项申请malloc及释放free,如果程序员申请内存并使用后未释放,这段内存就丢失了(在对管理器的记录中,这段内存仍然属于你这个进程,但是进程自己又以为内存已经不用了,再用的时候又回去申请新的内存块,这就叫吃内存),称为内存泄露。在C/C++ 语言中,内存泄露是最严重的程序bug,这也是别人认为Java/C#优秀的地方。
        3. C语言操作堆内存的接口(malloc   free
          1. 堆内存释放时最简单,直接调用free释放即可。    void free(void *ptr)
          2. 堆内存申请时,有3个可选择的类似功能的函数:malloccalloc, realloc
            1. void *malloc(size_t size);
            2. void *calloc(size_t nmemb,size_t size);  //nmemb 个单元,每个单元size 个字节
            3. void *realloc (void *ptr, size_t size);  //改变原来申请的空间的大小的

      譬如要申请10int 元素的内存:

      malloc(40);                    malloc(10*sizeof(int));

      calloc(10,4);                  calloc(10, sizeof(int));

      1. 数组定义时必须同时给出数组元素个数(数组大小),而且一旦定义再无法更改。

      语法技巧可以更改数组大小,但其实这只是一种障眼法。他的工作原理是:先重新创建一个新的数组大小为要更改后的数组,然后将原数组的所有元素复制进新的数组,然后释放原数组,最后返回新的数组给用户;

      堆内存申请时给定大小,然后一旦申请完成大小不变,如果要变只能通过realloc接口(原理与上述语法技巧一致)

      1. 优势与劣势(管理大块内存、灵活、容易内存泄露)

      优势:灵活

      劣势:需要程序员去处理各种细节,所以容易出错,严重依赖程序员的水水平。

      1. 复杂数据结构
        1. 链表、哈希表、二叉树、图等
          1. 链表是最简单且最重要的,链表在linux内核中使用非常多,驱动、应用编程很多时候都需要使用链表。所以对链表必须掌握,掌握到:  会自己定义结构体实现链表、会写链表的节点插入(前插、后插)、节点删除、节点查找、节点遍历等。
          2. 哈希表不是很常用,一般不需要自己学实现,而直接使用别人实现的哈希表比较多。对我们来说最重要的是要明白哈希表的原理、从而知道哈希表的特点,从而知道什么时候该用哈希表,当看到别人用了哈希表的时候要明白别人为什么要用哈希表。合不合适?有没有好的选择?
            1. 哈希表类似于数组,但是在索引节点时是利用某种映射方式的
          3. 二叉树、图等。在嵌入式开发中这些数据结构用的很少很少,且这些数据结构一般用来解决特定问题的。
        2. 为什么需要更复杂的数据结构?
          1. 因为现实中的实际问题是多种多样的,问题的复杂度不同,所以需要解决问题的算法和数据结构也不同。
          2. 所以在处理不同复杂度的问题,就去针对性解决的数据结构和算法
        3. 数据结构和算法的关系
          1. 数据结构的发明都是为了配合一定的算法
          2. 算法是为了处理具体问题,算法的实现依赖于相应的数据结构。
          3. 当前我们所的算法和纯数学是不同的(算法是基于数学的),因为计算机算法要求以数学算法为指导,并且结合计算机本身的特点来改进,最终实现一个在计算机上可以运行的算法(即代码可以表示的算法)。
        4. 应该怎样学习这部分?
          1. 数据结构和算法是相辅相成的,要一起研究。
          2. 数据结构和算法对嵌入式来说不全是重点,不要盲目去研究这个。
          3. 一般在实际应用中实现数据结构和算法的人和使用数据结构和算法的人是分开的。实际中有一部分人的工作就是研究数据结构和算法,并且试图用代码来实现这些算法(表现为库);其他真正做工作的人要做的就是理解明白这些算法和数据结构的意义、优劣、特征,然后在合适的时候选择合适的数据结构和算法来解决自己碰到的实际问题。

      举个例子:linux内核在字符设备驱动管理时,使用了哈希表(hash table,散列表)。所以字符驱动的很多特点都和哈希表的特点有关。

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

    展开全文
  • 支持文件写入内存内存数据写文件 ,内存数据排序,数据快速查找,数据筛选,数据节点添加数据 内存结构数组数据管理
  • Linux内存管理数据结构之间的关系

    千次阅读 2016-03-21 22:04:07
    linux内存管理是一个相当复杂的机制,这里只是基础的内存管理知识结构,不包括页面换出换入。 可以从以下角度思考问题 用户地址空间: 用户内存请求被认为是不紧迫的 用户访问是危险的 权限控制用户程序典型应用...

    linux内存管理是一个相当复杂的机制,这里只是基础的内存管理知识结构,不包括页面换出换入。
    可以从以下角度思考问题
    用户地址空间:
    用户内存请求被认为是不紧迫的
    用户访问是危险的 权限控制

    用户程序典型应用:
    shell中运行个命令,全新的地址空间
    正在运行的程序装入了别一个程序exec,进程标识不变,线性区变了
    用户程对文件作内存映射
    用户malloc
    用户栈增长
    IPC共享内存
    多线程共享

    内存管理数据结构设计原因,其考虑的问题。
    UMA 与 NUMA

    DMA
    NORMAL
    HIGHMEM

    可阻塞路径中分配内存 永久内存映射
    不可阻塞路径中分配内存 保留页池 try… 临时内核映射

    碎片:
    内:
    外:1 2 4 8 16 …1024

    memzone中:
    申请内存要考虑NUMA,从本CPU结点到其他CPU结点,从HIGHMEM到NORMAL到DMA的优先级

    伙伴系统
    内核经常请求和释放单个页框,定义每CPU页框高速缓存。 一个页可能是热的,在CPU缓存中。
    从伙系统到每CPU高速缓存
    从每CPU高速缓存到伙伴系统
    每次申请和释放都是批量的,因此有上限、下限、批量值。

    slab分配器
    对象构造与析构
    对象缓存
    内核反复申请一些固定大小对象
    对象对齐
    不同slab中有相同偏移量的对象可能放在高速缓存到同一行中。通过着色避免。

    每CPU本地高速缓存 降低自旋锁的竞争

    非连续内存区 vmalloc
    对内存请求不是很频繁。
    没有外碎片

    缺页异常处理程序考虑:
    是编程错误导致?
    是无效线性地址 进程地址空间,介有待分配
    写时复制?

    内存页面换入换出。算法。
    内存管理知识体系

    **

    linux内存管理数据结构之间的关系

    **
    内存管理数据结构之间的关系

    SLAB经典图

    这里写图片描述

    展开全文
  • 数据结构:八大数据结构分类

    万次阅读 多人点赞 2018-09-05 18:23:28
    数据结构分类 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。 常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示: 每一种数据结构都...

    本文目录:

    数据结构分类

    数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。
    常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示:
    这里写图片描述
    每一种数据结构都有着独特的数据存储方式,下面为大家介绍它们的结构和优缺点。

    1、数组

    数组是可以再内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为 1。

    int[] data = new int[100];data[0]  = 1;
    

    优点:
    1、按照索引查询元素速度快
    2、按照索引遍历数组方便

    缺点:
    1、数组的大小固定后就无法扩容了
    2、数组只能存储一种类型的数据
    3、添加,删除的操作慢,因为要移动其他的元素。

    适用场景:
    频繁查询,对存储空间要求不大,很少增加和删除的情况。

    2、栈

    栈是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作。 栈的特点是:先进后出,或者说是后进先出,从栈顶放入元素的操作叫入栈,取出元素叫出栈。
    这里写图片描述
    栈的结构就像一个集装箱,越先放进去的东西越晚才能拿出来,所以,栈常应用于实现递归功能方面的场景,例如斐波那契数列。

    3、队列

    队列与栈一样,也是一种线性表,不同的是,队列可以在一端添加元素,在另一端取出元素,也就是:先进先出。从一端放入元素的操作称为入队,取出元素为出队,示例图如下:
    这里写图片描述
    使用场景:因为队列先进先出的特点,在多线程阻塞队列管理中非常适用。

    4、链表

    链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,每个元素包含两个结点,一个是存储元素的数据域 (内存空间),另一个是指向下一个结点地址的指针域。根据指针的指向,链表能形成不同的结构,例如单链表,双向链表,循环链表等。
    这里写图片描述
    链表的优点:
    链表是很常用的一种数据结构,不需要初始化容量,可以任意加减元素;
    添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可,所以添加,删除很快;

    缺点:
    因为含有大量的指针域,占用空间较大;
    查找元素需要遍历链表来查找,非常耗时。

    适用场景:
    数据量较小,需要频繁增加,删除操作的场景

    5、树

    是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

    • 每个节点有零个或多个子节点;
    • 没有父节点的节点称为根节点;
    • 每一个非根节点有且只有一个父节点;
    • 除了根节点外,每个子节点可以分为多个不相交的子树;

    在日常的应用中,我们讨论和用的更多的是树的其中一种结构,就是二叉树
    这里写图片描述
    二叉树是树的特殊一种,具有如下特点:

    1、每个结点最多有两颗子树,结点的度最大为2。
    2、左子树和右子树是有顺序的,次序不能颠倒。
    3、即使某结点只有一个子树,也要区分左右子树。

    二叉树是一种比较有用的折中方案,它添加,删除元素都很快,并且在查找方面也有很多的算法优化,所以,二叉树既有链表的好处,也有数组的好处,是两者的优化方案,在处理大批量的动态数据方面非常有用。

    扩展:
    二叉树有很多扩展的数据结构,包括平衡二叉树、红黑树、B+树等,这些数据结构二叉树的基础上衍生了很多的功能,在实际应用中广泛用到,例如mysql的数据库索引结构用的就是B+树,还有HashMap的底层源码中用到了红黑树。这些二叉树的功能强大,但算法上比较复杂,想学习的话还是需要花时间去深入的。

    6、散列表

    散列表,也叫哈希表,是根据关键码和值 (key和value) 直接进行访问的数据结构,通过key和value来映射到集合中的一个位置,这样就可以很快找到集合中的对应元素。

    记录的存储位置=f(key)

    这里的对应关系 f 成为散列函数,又称为哈希 (hash函数),而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里,这种存储空间可以充分利用数组的查找优势来查找元素,所以查找的速度很快。

    哈希表在应用中也是比较常见的,就如Java中有些集合类就是借鉴了哈希原理构造的,例如HashMap,HashTable等,利用hash表的优势,对于集合的查找元素时非常方便的,然而,因为哈希表是基于数组衍生的数据结构,在添加删除元素方面是比较慢的,所以很多时候需要用到一种数组链表来做,也就是拉链法。拉链法是数组结合链表的一种结构,较早前的hashMap底层的存储就是采用这种结构,直到jdk1.8之后才换成了数组加红黑树的结构,其示例图如下:
    这里写图片描述
    从图中可以看出,左边很明显是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。

    哈希表的应用场景很多,当然也有很多问题要考虑,比如哈希冲突的问题,如果处理的不好会浪费大量的时间,导致应用崩溃。

    7、堆

    堆是一种比较特殊的数据结构,可以被看做一棵树的数组对象,具有以下的性质:

    • 堆中某个节点的值总是不大于或不小于其父节点的值;

    • 堆总是一棵完全二叉树。

    将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

    堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆。
    (ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2),满足前者的表达式的成为小顶堆,满足后者表达式的为大顶堆,这两者的结构图可以用完全二叉树排列出来,示例图如下:
    这里写图片描述
    因为堆有序的特点,一般用来做数组中的排序,称为堆排序。

    8、图

    图是由结点的有穷集合V和边的集合E组成。其中,为了与树形结构加以区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。

    按照顶点指向的方向可分为无向图和有向图:
    这里写图片描述
    这里写图片描述
    图是一种比较复杂的数据结构,在存储数据上有着比较复杂和高效的算法,分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构,这里不做展开,读者有兴趣可以自己学习深入。

    展开全文
  • linux内存管理重要的数据结构

    千次阅读 2009-10-16 14:47:00
    } //linux通用的双向链队列,下面多处用到,这里列出源代码 linux对内存再用页式管理,对于页,就有个数据结构page加以描述。在内核中有个全局量mem-map指向的是一个page的数组,整个数组描述了整个物理内存,大家...
  • linux进程/内存管理数据结构之u区

    千次阅读 2012-08-05 12:06:05
    一个进程的上下文包括:用户级上下文,寄存器上下文和系统级上下文。 ...用户级上下文:正文,...系统级上下文:进程表项(proc结构)和U区,在Linux系统中,这两部分被合成task_struct,区表及页表,核心栈等。
  • None
  • 程序员面试笔试合集,包括FAQ,内存管理数据结构和算法、字符串操作等常见题,绝对能在笔试面试中加分!chm格式,方便阅读!
  • 管理系统 用纯C语言加链表实现 可模拟系统的内存分配 与回收 代码耦合性自认为可以
  • 通过对原来的内存块管理链表的结构改进,提出了一种新的链表结构,该数据结构描述了已分配块链表和空 闲块链表的结构关系,从而能够提高动态内存管理的效率. 来自于:倪西钩,汤可夫,吴大为 (大连理工大学应用数学...
  • Flink内存管理源码解读之基础数据结构

    千次阅读 热门讨论 2016-03-24 23:18:10
    概述在分布式实时计算领域,如何让框架...在应对这一问题上Flink无疑是做得非常杰出的,Flink的自主内存管理设计也许比它自身的知名度更高一些。正好最近在研读Flink的源码,所以开两篇文章来谈谈Flink的内存管理设计。
  • windows内存堆的数据结构

    千次阅读 2012-10-16 19:52:21
    还是紧接着昨天的问题,很想明白到底在内存中堆的数据结构到底是怎么样的?究竟是不是别人回答的红黑树的结构? 在网上搜索了一番好像也鲜有答案。后来在《0day 安全 软件漏洞分析技术》一书里面找到了这个问题的...
  • 内存数据库的数据结构

    千次阅读 2009-05-22 06:54:00
    内存容量的快速增长对数据库管理系统有着深刻的影响。在某些场合,将整个数据库放进内存是可能的,正常的查询处理可以完全脱离硬盘。另外,和传统的数据库应用相比,有大量的新兴应用,目前的内存大小已经足够了。 ...
  •   前面聊过内存的表示由 node -&gt;...内核把物理页作为内存管理的基本单位. 尽管处理器的最小可寻址单位通常是字, 但是, 内存管理单元MMU通常以页为单位进行处理. 因此,从虚拟内存的上...
  • 内存数据结构之栈和堆的区别?

    千次阅读 多人点赞 2018-01-15 15:56:37
    网上有一篇很好的文章,我差不多直接搬运...数据结构的堆栈我想很多同学学习过,今天介绍下数据结构的堆栈,但是重点是内存的堆栈整理。 数据结构的栈和堆 首先在数据结构上要知道堆栈,尽管我们这么称呼它,但实际上

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 680,882
精华内容 272,352
关键字:

内存管理相关的数据结构

数据结构 订阅