CSAPP–第九章–虚拟内存–动态内存分配原理（上）

动态内存分配、

动态内存分配器维护着一个进程的虚拟内存区域，称为堆。比如说 malloc，我们用malloc来申请一段虚拟内存的时候，操作系统分配给我们的是一段 block ，但这个block和之前提到的page、cache中的block是不一样的，这边每个block的大小是不一样的。

分配过来的blocks，有两种。

一种是allocated也就是被分配的，已分配的块显式地保留 供应用程序使用
- 一个已分配的块保持已分配状态，直到它被释放，这种释放要么是应用程序显式执行的，要么是内存分配器自身隐式执行的。
还有一种是free，也就是没有被分配的，因此可以用来分配。

分配器也有两种：显式的分配器和隐式的分配器

显式分配器：比如说 C语言中的malloc和free，C++当中的new和delete
隐式分配器：比如说 Java语言中的垃圾回收系统。

显式分配器、

malloc函数：

#include<stdlib.h>
void* malloc(size_t size);

//参数是字节大小。执行完需要进行判断，因为不一定每次申请分配内存都能成功。并没有初始化。
//申请一个内存块，并返回一个指向内存块的指针，该内存块至少包含所声明的大小的字节，该内存块以16个字节对齐（64位系统），因为给我们的块会为可能包含在这个块内的任何数据对象类型做对齐，在64位模式中，malloc返回的块的地址总是16的倍数。
//失败返回nullptr或者出现error

calloc函数：

void* calloc（unsigned int num，unsigned int size）；

//calloc函数使用方式与malloc几乎相同,也是在堆区申请动态内存空间。size_t num为元素个数，size_t size为每个元素的字节大小。calloc会在返回起始地址之前，把在堆区申请的动态内存空间的每个字节都初始化为0。

//下面的代码申请了一个int数组，并全部初始化为0

        int* ptr = static_cast<int*>(calloc(10, sizeof(int)));

	if (ptr == nullptr)
	{
		exit(0);
	}

	for (int i = 0; i < 10; ++i)
	{
		if (ptr[i])
		{
			print(ptr[i], "\n");
		}
	}

	free(ptr);

realloc函数：

void *realloc(void *ptr, size_t size)；

//尝试重新调整之前调用 malloc 或 calloc 所分配的 ptr 所指向的内存块的大小。且ptr指向的内存块的保存的数据前后一致。
/* ptr -- 指针指向一个要重新分配内存的内存块，该内存块之前是通过调用 malloc、calloc 或 realloc 进行分配内存的。如果为空指针，则会分配一个新的内存块，且函数返回一个指向它的指针。
size -- 内存块的新的大小，以字节为单位。如果大小为 0，且 ptr 指向一个已存在的内存块，则 ptr 所指向的内存块会被释放，并返回一个空指针。*/

        //分配40个字节
	int* ptr = static_cast<int*>(calloc(10, sizeof(int)));
   
        //重新分配80个字节
	int* pp = static_cast<int*>(realloc(ptr, 80));


        //初始化40个字节
	for (int i = 0; i < 10; ++i)
	{
		ptr[i] = i;
	}


        //打印出80个字节的信息，发现前40个字节初始化了，后40个没有初始化
	for (int i = 0; i < 20; ++i)
	{
		cout << pp[i] << endl;
	}

	free(pp);

free函数：

void free(void* ptr);

//free适合malloc对应的，我们可以利用这个函数来回收之前分配的内存块。注意，这个  p 一定要是 malloc，calloc和realloc这三个函数的返回值，否则会报错。

sbrk函数：

#include <unistd.h>
void *sbrk(intptr_t incr);

//sbrk 函数通过将内核的brk 指针增加incr 来扩展和收缩堆。
//所以当分配器需要更多虚拟内存时，会调用sbrk来获得更多的虚拟内存，然后那个部分会添加到堆中，这会使堆增长

malloc 和free 实现管理堆、

假设下面是一个堆的模型，我们定义两条规则：

Show 8-byte words as squares 每一格子代表了一个 word（字），8字节
Allocations are double-word aligned. 双字对齐，也就是分配的块数只能是2的倍数

#define SIZ sizeof(size_t) 8个字节

我们一开始申请4倍的SIZ ,于是就有了黄色的4个格子
紧接着我们申请5倍的SIZ，因为要双字对齐，因此我们要划出6个格子来。
我们申请6倍的SIZ,malloc 就从空闲块的前部切出一个6字的块
调用free后，会释放掉第二部申请的5*SIZ 的块。
程序请求一个2字的块。在这种情况中，malloc分配在前一步中被释放的那个块的一部分并返回一个指向这个新块的指针。

一些分配和回收时的约束、

处理任意请求序列。一个应用可以有任意的分配请求和释放请求序列，只要满足约束条件：每个释放请求必须对应于一个当前已分配块，这个块是由一个以前的分配请求获得的。因此，分配器不可以假设分配和释放请求的顺序。例如，分配器不能假设所有的分配请求都有相匹配的释放请求，或者有相匹配的分配和空闲请求是嵌套的。
立即响应请求。分配器必须立即响应分配请求。因此，不允许分配器为了提髙性能重新排列或者缓冲请求。不能是异步的
只使用堆。为了使分配器是可扩展的，分配器使用的任何非标量数据结构都必须保存在堆里。
对齐块（对齐要求）。分配器必须对齐块，使得它们可以保存任何类型的数据对象。
不修改已分配的块。分配器只能操作或者改变空闲块。特别是，一旦块被分配了，就不允许修改或者移动它了。因此，诸如压缩已分配块这样的技术是不允许使用的。(就是把中间的空的blocks压出来，这种是不可以的)

衡量分配器性能的一些指数、

吞吐率：

现在我们假设假定n 个分配和释放请求的某种序列 $R0,R_1,\cdots,R_k,\cdots ,R{n-1}$；我们希望一个分配器的吞吐率最大化,吞吐率的定义就是每个单位时间里完成的请求数。

例如，如果一个分配器在1 秒内完成500 个分配请求和500 个释放请求，那么它的吞吐率就是每秒1000 次操作

内存利用率：

我们要知道内存虚拟内存是一个有限的空间，我们不能一直向他申请blocks，因此我们必须高效地使用虚拟内存。对于可能被要求分配和释放大块内存的动态内存分配器来说，尤其如此。

峰值利用率：

对于n 个分配和释放请求的某种序列 $R0,R_1,\cdots,R_k,\cdots ,R{n-1}$

如果说一个应用程序请求一个 p 字节的块，那么得到的已分配块地payload 是 p字节。

在请求 Rk 完成之后，aggregate payload(聚集有效载荷) 表示为 Pk，即当前已分配的块地有效载荷之和。

Hk表示堆地当前的大小(单调非递减)。那么，前面 k+1 个请求得峰值利用率，表示为 $Uk,,U_k = \frac{max{i\leq k}P_i}{H_k}$

我们看到，分配器的目标就是在整个序列中使 Un−1 最大化。但是最大化吞吐率和最大化利用率之间是相互牵制的。

当我们以堆利用率为代价时 ，很容易编写出吞吐率最大化的分配器。

Fragmentation（碎片）、

碎片即分配内存时产生的额外开销，它也是造成堆利用率很低的主要原因。有两种形式的碎片：内部碎片(internal fragmentation)和外部碎片（external fragmentation)

internal fragmentation（内部碎片）：

内部碎片就是已经被分配出去（能明确指出属于哪个进程）却不能被利用的内存空间

占有这些区域或页面的进程并不使用这个存储块。而在进程占有这块存储块时，系统无法利用它。直到进程释放它，或进程结束时，系统才有可能利用这个存储块。

当一个已分配块(allocated block) 比有效载荷(payload) 大的时候，内部碎片就会发生。

例如我需要分配11个字节，但是由于内存块大小和内存块对齐原则，分配给了我2个8字节的内存块，这样就造成了5个字节的浪费。

external fragmentation（外部碎片）：

外部碎片是位于任何两个 操作系统分配的用于装载进程的内存区域 或页面之间的空闲区域

外部碎片指的是还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。

外部碎片是处于任何两个已分配区域或页面之间的空闲存储块。这些存储块的总和可以满足当前申请的长度要求，但是由于它们的地址不连续或其他原因，使得系统无法满足当前申请。

比如说对于第五个请求，heap中明明有8个格子，但是却无法给7*SIZ分配空间

实现一个分配器、

要实现一个分配器，我们必须要解决这样几个问题

How do we know how much memory to free given just a pointer?
- 给free一个指针，那么分配器要怎么知道释放多少大小的内存空间？
空闲块组织：How do we keep track of the free blocks?
- 我们怎么知道那些blocks是空的呢？怎么知道这一块空的区域的大小呢？
分割：What do we do with the extra space when allocating a structure that is smaller than the free block it is placed in?
- 当分配一个比它所在的空闲块还小的结构时，我们如何处理额外的空间 (比如说6块空的分配掉4块，那么剩下两块怎么标记？)
放置：How do we pick a block to use for allocation — many might fit?
- 如果我有多个满足条件的空间，我应该选择哪一个进行分配
合并：How do we reuse a block that has been freed?
- 释放出来后的内存空间我怎么重新利用？比如前面也是空的，后面也是空的，我要不要将他们合并在一起？

CSAPP–第九章–虚拟内存（中）

反码，原码，补码再复习

Comments NOTHING

取消回复