按『个人 Wiki』风格整理的学习笔记
| 之前 | 之后 |
|---|---|
页面故障 (page fault)：假设 VP[3] 不在物理内存中，需从硬盘读取。步骤如下：
VP[4] 作为受害者 (victim)。VP[4] 被修改过，则将其写入硬盘。VP[3]，写入 PP[3]，即替换 VP[4]。其中 SUP 表示以监管者模式 (SUPervisor mode) 即内核模式 (kernel mode) 运行。
写时复制 (Copy-On-Write, COW)：
| 两个进程共享数据 | 进程 2 在私有 COW 页面写入数据 |
|---|---|
fork() 再探evecve() 再探mmap()#include <unistd.h>
#include <sys/mman.h>
void *mmap(void *start/* 建议起始位置，可以是 NULL */, size_t length/* 读取长度 */,
int prot/* 权限：PROT_EXEC | PROT_READ | PROT_WRITE | PROT_NONE */,
int flags/* 映射类型：MAP_ANON | MAP_PRIVATE | MAP_SHARED */,
int fd/* 文件描述符 */, off_t offset/* 文件偏移量 */);
// Returns: pointer to mapped area if OK, MAP_FAILED (−1) on error
int munmap(void *start, size_t length);
// Returns: 0 if OK, −1 on error
此函数从文件 fd 读取始于 offset 字节、长度为 length 字节的数据区块，映射到（可能）始于 start 的虚拟内存空间。
堆 (heap)：虚拟内存中紧跟在“未初始化数据”后面的一区块连续区域
brk：指向堆顶（堆内最后一个字节的下一子节）动态内存分配器 (dynamic memory allocator)：维护堆内存的软件接口
malloc() 与 free()C 语言标准库提供了以下动态内存接口：
#include <stdlib.h>
void* malloc(size_t n); // 不初始化
void* calloc(size_t k, size_t s); // 初始化为零
void* realloc(void* p, size_t n); // 改变已分配区块的大小
这组函数请求动态内存。若成功，则返回长度至少为 n 或 k*s 字节、满足对齐要求的可用区块的地址；否则，返回 NULL。
#include <stdlib.h>
void free(void* ptr);
此函数释放动态内存。其中 ptr 必须指向 malloc() 等函数返回的地址；否则，其行为未定义。
实现上述接口，需要用到管理堆内存的系统调用：
#include <unistd.h>
void* sbrk(intptr_t incr);
它（通过其他系统调用）改变堆的大小。若成功，则返回旧的 brk；否则，返回 (void*)(-1)，并将 errno 置为 ENOMEM。
主要原因：程序运行前，不知道所需空间大小。
⚠️ 用“足够大”的静态数组，有指标越界的风险。
需求：
目标：使以下指标最大化
static void *find_fit(size_t alloc_size) {
char *block = first_block;
size_t block_size; /* Size of current block */
do { /* First-hit */
block = NEXT(block);
block_size = GET_SIZE(HEADER(block));
if (block_size == 0) {
block = NULL;
break;
}
} while (block_size < alloc_size || GET_ALLOC(HEADER(block)));
return block;
}
static void place(void *block, size_t alloc_size) {
size_t block_size = GET_SIZE(HEADER(block));
int split = (block_size > alloc_size + QSIZE);
if (split) {
/* The remaining of current block can hold a min-sized block. */
PUT(HEADER(block), PACK(alloc_size, 1));
PUT(FOOTER(block), PACK(alloc_size, 1));
block = NEXT(block);
block_size -= alloc_size;
}
PUT(HEADER(block), PACK(block_size, !split));
PUT(FOOTER(block), PACK(block_size, !split));
}
static void *extend_heap(size_t words) {
char *block;
size_t size;
/* Allocate an even number of words to maintain alignment */
size = ((words % 2) + words) * WSIZE;
if ((block = mem_sbrk(size)) == (void *)-1)
return NULL;
/* Initialize free block header/footer and the epilogue header */
PUT(HEADER(block), PACK(size, 0)); /* Free block header */
PUT(FOOTER(block), PACK(size, 0)); /* Free block footer */
PUT(HEADER(NEXT(block)), PACK(0, 1)); /* New epilogue header */
/* Coalesce if the previous block was free */
return coalesce(block);
}
| Case 1 | Case 2 |
|---|---|
| Case 3 | Case 4 |
|---|---|
static void *coalesce(void *block) {
size_t prev_alloc = GET_ALLOC(FOOTER(PREV(block)));
size_t next_alloc = GET_ALLOC(HEADER(NEXT(block)));
size_t size = GET_SIZE(HEADER(block));
if (prev_alloc && next_alloc) { /* Case 1 */
}
else if (prev_alloc && !next_alloc) { /* Case 2 */
size += GET_SIZE(HEADER(NEXT(block)));
PUT(HEADER(block), PACK(size, 0));
PUT(FOOTER(block), PACK(size,0));
}
else if (!prev_alloc && next_alloc) { /* Case 3 */
size += GET_SIZE(HEADER(PREV(block)));
PUT(FOOTER(block), PACK(size, 0));
PUT(HEADER(PREV(block)), PACK(size, 0));
block = PREV(block);
}
else { /* Case 4 */
size += GET_SIZE(HEADER(PREV(block)))
+ GET_SIZE(FOOTER(NEXT(block)));
PUT(HEADER(PREV(block)), PACK(size, 0));
PUT(FOOTER(NEXT(block)), PACK(size, 0));
block = PREV(block);
}
return block;
}
memlib.c 实现了一个简易的虚拟内存系统：
#define MAX_HEAP (20*(1<<20)) /* 20 MB */
static char *mem_head; /* 堆首字节的地址 */
static char *mem_tail; /* 堆尾字节的地址 + 1 */
static char *mem_max_addr; /* 最大合法堆地址 + 1 */
void mem_init(void) {
mem_head = (char *)Malloc(MAX_HEAP);
mem_tail = (char *)mem_head;
mem_max_addr = (char *)(mem_head + MAX_HEAP);
}
void *mem_sbrk(int incr) {
char *old_brk = mem_tail;
if ((incr < 0) || ((mem_tail + incr) > mem_max_addr)) {
errno = ENOMEM;
fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\n");
return (void *)-1;
}
mem_tail += incr;
return (void *)old_brk;
}
mm.c 实现了一个基于“隐式链表”的分配器：
extern int mm_init(void);
extern void *mm_malloc(size_t size);
extern void mm_free(void *ptr);
为简化合并相邻的空闲区块，在链表两端引入一对辅助区块：
#define WSIZE 4 /* word size (bytes) */
#define DSIZE 8 /* double word size (bytes) */
#define CHUNK (1<<12) /* extend heap by this amount (bytes) */
#define MAX(x, y) ((x) > (y) ? (x) : (y))
/* PACK a size and allocated bit into a word */
#define PACK(size, alloc) ((size) | (alloc))
/* GET and PUT a word at address p */
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))
/* GET the SIZE and ALLOCated fields from address p */
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
/* Given block ptr block, compute address of its HEADER and FOOTER */
#define HEADER(block) ((char *)(block) - WSIZE)
#define FOOTER(block) ((char *)(block) + GET_SIZE(HEADER(block)) - DSIZE)
/* Given block ptr block, compute address of NEXT and PREVious blocks */
#define NEXT(block) ((char *)(block) + GET_SIZE(((char *)(block) - WSIZE)))
#define PREV(block) ((char *)(block) - GET_SIZE(((char *)(block) - DSIZE)))
/* e.g. get the size of the next block */
size_t size = GET_SIZE(HEADER(NEXT(block)));
/* Global variables */
static char *first_block = NULL; /* Pointer to first block */
int mm_init(void) {
/* Create the initial empty heap */
if ((first_block = mem_sbrk(4*WSIZE)) == (void *)-1)
return -1;
PUT(first_block, 0); /* Padding on head */
PUT(first_block + (1*WSIZE), PACK(DSIZE, 1)); /* Prologue header */
PUT(first_block + (2*WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
PUT(first_block + (3*WSIZE), PACK(0, 1)); /* Epilogue header */
first_block += (2*WSIZE);
/* Extend the empty heap with a free block of CHUNK bytes */
if (extend_heap(CHUNK / WSIZE) == NULL)
return -1;
return 0;
}
void mm_free(void *block) {
if (block == NULL)
return;
size_t size = GET_SIZE(HEADER(block));
if (first_block == NULL)
mm_init();
PUT(HEADER(block), PACK(size, 0));
PUT(FOOTER(block), PACK(size, 0));
coalesce(block);
}
void *mm_malloc(size_t size) {
size_t alloc_size; /* Adjusted block size */
size_t chunk_size; /* Amount to extend heap if no fit */
char *block;
if (first_block == NULL)
mm_init();
/* Ignore spurious requests */
if (size == 0)
return NULL;
/* Adjust block size to include overhead and alignment reqs. */
if (size <= DSIZE)
alloc_size = DSIZE + DSIZE; /* payload + overhead */
else
alloc_size = DSIZE * (((size + DSIZE) + (DSIZE-1)) / DSIZE);
/* Search the free list for a fit */
if ((block = find_fit(alloc_size)) == NULL) {
/* No fit found. Get more memory. */
chunk_size = MAX(alloc_size, CHUNK);
if ((block = extend_heap(chunk_size/WSIZE)) == NULL)
return NULL;
}
place(block, alloc_size);
return block;
}
空闲区块的有效载荷部分可用于存储指针，以便构造出链表等数据结构。
新空闲区块安置策略
Malloc Lab 中的 mm_explicit.c 给出了一种实现基于 LIFO 的实现。
分离链表 (segregated lists)：
简易分离存储 (simple segregated storage)：每条链表中的空闲区块具有相同的尺寸；不分裂或合并空闲区块。
sbrk() 除外）；无需区块首部、区块尾部；用单向链表即可实现。分离匹配 (segregated fits)：GCC 的实现方案。
/* Create an nxm array */
int **makeArray1(int n, int m) {
int i;
int **A = (int **)Malloc(n * sizeof(int/* 应为 `int*` */));
for (i = 0; i < n; i++)
A[i] = (int *)Malloc(m * sizeof(int));
return A;
}
*(p++);
(*p)++;