[科普中国]-存储分配程序和编码-

存储分配程序

存储分配程序是指计算机系统中依照一定的算法实现内存分配的程序。主要是为了解决内存分配问题。一般分为直接方式、静态分配、动态分配。

直接方式直接方式是早期的计算机所使用的一种方式。当时多道程序技术还没出现，存储器的可用空间一般是给定的。那时程序员在编程序时或编译程序对源程序进行编译时，使用实际的存储器地址，这种分配方式使用户与计算机内存直接打交道；系统资源在某一时刻为一个用户所独占。当多道程序出现时就使用户感到极不方便，因为用户要自己做主存的分配工作，而且内存不止存放一个作业，这要求用户必须知道每一个作业放在主存的什么地方，这无疑增加了用户的负担，况且存储空间的利用率也相当低1。

动态分配所谓动态分配(Dynamic Memory Allocation)就是指在程序执行的过程中动态地分配或者回收存储空间的分配内存的方法。动态内存分配不象数组等静态内存分配方法那样需要预先分配存储空间，而是由系统根据程序的需要即时分配，且分配的大小就是程序要求的大小。分配过程包括寻找一块足够大未被使用的内存。分配过程当中的问题，内部和外部碎片。减少碎片需要特别处理，从而导致更复杂的实现。分配器的元数据需要占用额外的空间。尝试组块来减轻这个效应。

通常，内存是从一个被称为堆的内存池中分配出来的。高级语言封装了内存地址的概念，内存通常是通过指针来间接访问的。分配算法经常将组织分配释放组块等操作封装成抽象的接口供上层函数调用。

静态分配所谓的静态分配，即在编译期间为数据对象分配存储空间。这要求在编译期间就可以确定数据对象的大小，同时还可以确定数据对象的数目。

现状

多数（现代）语言只实施部分静态存储分配。可静态分配的数据对象包括大小固定且在程序执行期间可全称访问的全局变量、静态变量、程序中的常量以及class的虚函数表等，如C语言中的static和extern变量，以及C++中的static变量，这些数据对象的存储将被分配在静态数据区。

常见做法

从道理上讲，或许可以将静态数据对象与某个绝对存储地址绑定，然而，通常的做法是将静态数据对象的存取地址对应到偶对（DataArerStart，Offset）。Offset是在编译时刻确定的固定偏移量，而DataArerStart则可以推迟到链接或运行时刻才确定。有时，DataArerStart的地址也可以装入某个基地址寄存器Register，此时数据对象的存取地址对应到偶对（DataArerStart，Offset），即所谓的寄存器偏址寻址方式。

优点

采用这种方式，存储分配极其简单。

缺点

（1）采用这种方式会带来存储空间的浪费。为解决存储空间浪费问题，人们设计了变量的重叠布局机制，如FORTRAN语言的equivalence语句。重叠布局带来的问题是使得程序难写难读。

（2）完全静态分配的语言还有另外一个缺陷，就是无法支持递归过程或函数。

（3）对于一些动态的数据结构，例如动态数据（C++中使用new关键字来分配内存）以及递归函数的局部变量等最终空间大小必须在运行时才能确定的场合，静态存储分配就无能为力了。

分配算法最佳适应算法

最佳适应算法，即选择空间浪费最少的存储块2。

最先适应算法

最先适应算法，即选择最先找到的足够大的存储块。

循环最先适应算法

循环最先适应算法，，即起始点不同的最先适应算法。

哈希算法

哈希算法就是利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。

编码概述用规定的一组代码表示计算机程序的指令或信息的过程，即为计算机编写程序。用一组明确的规则表示某种信息，使得以后能进行译码，这种过程亦称为编码。

在电子计算机上，对指令及数据编码后，就可以进行操作或运算。

有时，编码与代码同义。在通讯中，表示信息组成、传送、接受及处理的一组规则与约定，称为编码或代码;为执行一个程序或解一个问题，把所要进行的操作步骤，按顺序用计算机代码编成的表，也称为编码3。

常见编码

字符编码（Character encoding）是一套法则，使用该法则能够对自然语言的字符的一个集合（如字母表或音节表），与其他东西的一个集合（如号码或电脉冲）进行配对。

文字编码（Text encoding）使用一种标记语言来标记一篇文字的结构和其他特征，以方便计算机进行处理。

语义编码（Semantics encoding），以正式语言乙对正式语言甲进行语义编码，即是使用语言乙表达语言甲所有的词汇（如程序或说明）的一种方法。

电子编码（Electronic encoding）是将一个信号转换成为一个代码，这种代码是被优化过的以利于传输或存储。转换工作通常由一个编解码器完成。

神经编码（Neural encoding）是指信息在神经元中被如何描绘的方法。

记忆编码（Memory encoding）是把感觉转换成记忆的过程。