實(shí)驗(yàn)材料與規(guī)則
官網(wǎng)的實(shí)習(xí)手冊(cè)是缺了測(cè)試材料的,所以我建議你直接從這里下載吧:
https://github.com/happysnaker/CSAPPLabs/tree/CSAPP/molloc-Lab
實(shí)驗(yàn)僅要求我們修改mm.c文件,要求完成init, molloc, free, recalloc 四個(gè)函數(shù)肚医,其中部分與系統(tǒng)接口的函數(shù)已在memlib.c文件中給出赡鲜。
完成之后巩趁,我們需要鍵入以下三條命令來(lái)跑分:
make clean
make mdriver
./mdriver
這個(gè)實(shí)驗(yàn)難度特別大亦歉,其中非常容易碰到段錯(cuò)誤,以至于我最后一個(gè)分離式的鏈表仍然沒(méi)有實(shí)現(xiàn)劲腿,實(shí)乃一個(gè)遺憾。立個(gè)flag鸟妙,2021年一定要實(shí)現(xiàn)它焦人!
實(shí)驗(yàn)部分
隱式空閑鏈表加首次適配
首次適配從頭遍歷鏈表,找到空閑塊重父。這個(gè)跑分不是很理想花椭,甚至還不及格,只有56分房午。這個(gè)就是書(shū)上的思路个从,其中要自己完善兩個(gè)函數(shù)。
代碼:隱式空閑鏈表加首次適配實(shí)現(xiàn)
隱式空閑鏈表加下一次次適配
下一次適配從上次操作的時(shí)候開(kāi)始遍歷歪沃。這種方式竟然出奇的理想嗦锐,跑了82分:
/*
Team Name:happysnaker
Member 1 :qwewqewqqe:qwewqewqqe
Using default tracefiles in traces/
Perf index = 42 (util) + 40 (thru) = 82/100
*/
我們留下一個(gè)bookstr來(lái)表示上一次操作時(shí)的指針,由于我們每一次釋放空閑塊都讓這個(gè)指針指向了空閑塊沪曙,所以下一次分配時(shí)速度非常塊奕污,可以看到效率部分拿了滿分(40),但利用率卻不理想液走。
代碼:
/*
Team Name:happysnaker
Member 1 :qwewqewqqe:qwewqewqqe
Using default tracefiles in traces/
Perf index = 42 (util) + 40 (thru) = 82/100
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"
team_t team = {
/* Team name */
"ateam",
/* First member's full name */
"Harry Bovik",
/* First member's email address */
"bovik@cs.cmu.edu",
/* Second member's full name (leave blank if none) */
"",
/* Second member's email address (leave blank if none) */
""
};
/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1 << 12)
#define MAX(X, Y) ((X) > (Y) ? (X) : (Y))
#define PACK(size, alloc) ((size) | (alloc)) /*設(shè)置頭部或腳部*/
#define GET(p) (*(unsigned int*)(p))
#define PUT(p, val) (*(unsigned int*)(p) = (val))
#define GET_SIZE(P) (GET(P) & ~0X7)
#define GET_ALLOC(P) (GET(P) & 0X1)
#define HDRP(bp) ((char*)(bp) - WSIZE) /*獲取頭部指針*/
#define FTRP(bp) ((char*)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) /*根據(jù)頭部獲取腳部指針*/
#define NEXT_BLKP(bp) ((char*)(bp) + GET_SIZE(((char*)(bp) - WSIZE))) /*下一個(gè)指向有效載荷的指針*/
#define PREV_BLKP(bp) ((char*)(bp) - GET_SIZE(((char*)(bp) - DSIZE)))
static void* extend_heap(size_t words);
static void* coalesce(void* bp);
static void *find_fit(size_t size);
static void place(void *bp,size_t asize);
static char *heap_listp = 0;
static void* bookptr;
/*
* mm_init - initialize the malloc package.
*/
int mm_init(void)
{
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void*)-1)
return -1;
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1));
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1));
PUT(heap_listp + (3 * WSIZE), PACK(0, 1));
heap_listp += (2 * WSIZE);
bookptr = (unsigned int)heap_listp + DSIZE; /*初始化*/
if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}
static void* extend_heap(size_t words){
char* bp;
size_t size;
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL;
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
bookptr = coalesce(bp); /*讓它指向空閑指針*/
return bookptr;
}
static void* coalesce(void* bp){
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
if (prev_alloc && next_alloc)
return bp;
else if (prev_alloc && !next_alloc){
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
PUT(HDRP(bp), PACK(size, 0));
}
else if (!prev_alloc && next_alloc){
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
else{
size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
return bp;
}
/*
* mm_malloc - Allocate a block by incrementing the brk pointer.
* Always allocate a block whose size is a multiple of the alignment.
*/
void *mm_malloc(size_t size)
{
char *bp;
size_t asize;
size_t extendsize;
if (size <= 0)
return NULL;
if (size <= DSIZE)
asize = 2 * DSIZE;
else
asize = DSIZE * ((size + DSIZE + (DSIZE - 1)) / DSIZE);
if ((bp = find_fit(asize)) != NULL){
place(bp, asize);
bookptr = bp;
return bp;
}
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
return NULL;
place(bp, asize);
bookptr = bp; /*指向上一個(gè)分配的塊*/
return bp;
}
/*
* mm_free - Freeing a block does nothing.
*/
void mm_free(void *ptr)
{
size_t size = GET_SIZE(HDRP(ptr));
PUT(HDRP(ptr), PACK(size, 0));
PUT(FTRP(ptr), PACK(size, 0));
bookptr = coalesce(ptr); /*指向空閑塊*/
return;
}
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
static void *find_fit(size_t size){
while (GET_SIZE(HDRP(bookptr)) > 0){
if (GET_SIZE(HDRP(bookptr)) >= size && GET_ALLOC(HDRP(bookptr)) == 0)
return bookptr;
bookptr = NEXT_BLKP(bookptr); /*別忘了更新它*/
}
return NULL;
}
static void place(void *bp,size_t asize){
size_t nowsize = GET_SIZE(HDRP(bp));
if (nowsize - asize < 2 * DSIZE){
PUT(HDRP(bp), PACK(nowsize, 1));
PUT(FTRP(bp), PACK(nowsize, 1));
}
else{
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
PUT(HDRP(NEXT_BLKP(bp)), PACK(nowsize - asize, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(nowsize - asize, 0));
}
return;
}
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *ptr, size_t size)
{
size_t oldsize = GET_SIZE(HDRP(ptr));
void* newptr = mm_malloc(size);
if (!newptr)
return 0;
bookptr = newptr; /*指向空閑塊*/
if (!ptr)
return newptr;
memcpy(newptr, ptr, (size < oldsize ? size : oldsize));
mm_free(ptr);
return newptr;
}
隱式空閑鏈表加最佳適配
找到最小適合的塊碳默,提高利用率贾陷,這個(gè)跑分不是很理想,只有56分嘱根。代碼:
隱式空閑鏈表加最佳適配
顯式空閑鏈表加FIFO
這一次采用雙向鏈表髓废,塊的大小至少需要16字節(jié),當(dāng)前塊指針bp指向的四字節(jié)保存著上一空閑塊的指針该抒,bp + 4保存著下一空閑塊的指針慌洪。當(dāng)我們有空閑塊時(shí),我們簡(jiǎn)單的插入到根節(jié)點(diǎn)處凑保。
/*
Team Name:happysnaker
Member 1 :qwewqewqqe:qwewqewqqe
Using default tracefiles in traces/
Perf index = 45 (util) + 40 (thru) = 85/100
*/
代碼:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"
/*********************************************************
* NOTE TO STUDENTS: Before you do anything else, please
* provide your team information in the following struct.
********************************************************/
team_t team =
{
/* Team name */
"Xwqe",
/* First member's full name */
"qewqe",
/* First member's email address */
"sadsa",
/* Second member's full name (leave blank if none) */
"",
/* Second member's email address (leave blank if none) */
""
};
/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
#define WSIZE 4
#define DSIZE 8 /*Double word size*/
#define CHUNKSIZE (1<<12) /*the page size in bytes is 4K*/
#define MAX(x,y) ((x)>(y)?(x):(y))
#define PACK(size,alloc) ((size) | (alloc))
#define GET(p) (*(unsigned int *)(p))
#define PUT(p,val) (*(unsigned int *)(p) = (val))
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
#define HDRP(bp) ((char *)(bp)-WSIZE)
#define FTRP(bp) ((char *)(bp)+GET_SIZE(HDRP(bp))-DSIZE)
#define PREV_BLKP(bp) ((char *)(bp)-GET_SIZE(((char *)(bp)-DSIZE)))
#define NEXT_BLKP(bp) ((char *)(bp)+GET_SIZE(((char *)(bp)-WSIZE)))
#define NEXT_RP(bp) ((unsigned int)(bp)+WSIZE) /*指向下一空閑塊指針*/
int mm_check(char *function);
static void *extend_heap(size_t dwords);
static void *coalesce(void *bp);
static void *find_fit(size_t size);
static void place(void *bp,size_t asize);
void __insert(char *p);
void __remove(char *p);
static char *heap_listp = NULL;
static char *root = NULL; /*這是我們的根節(jié)點(diǎn)*/
/*
* mm_init - initialize the malloc package.
* The return value should be -1 if there was a problem in performing the initialization, 0 otherwise
*/
int mm_init(void){
if((heap_listp = mem_sbrk(6*WSIZE))==(void *)-1) return -1;
PUT(heap_listp,0);
PUT(heap_listp+(1*WSIZE),0);
PUT(heap_listp+(2*WSIZE),0); /*內(nèi)存對(duì)齊*/
PUT(heap_listp+(3*WSIZE),PACK(DSIZE,1));
PUT(heap_listp+(4*WSIZE),PACK(DSIZE,1)); /*內(nèi)存對(duì)齊*/
PUT(heap_listp+(5*WSIZE),PACK(0,1)); /*尾巴*/
root = heap_listp + (1*WSIZE);/*初始化根節(jié)點(diǎn)*/
heap_listp += (4*WSIZE);
if((extend_heap(CHUNKSIZE/DSIZE)) == NULL)
return -1;
return 0;
}
/*
* mm_malloc - Allocate a block by incrementing the brk pointer.
* Always allocate a block whose size is a multiple of the alignment.
*/
void *mm_malloc(size_t size){
size_t asize;
size_t extendsize;
char *bp;
if(size ==0)
return NULL;
if(size <= DSIZE)
asize = 2*(DSIZE);
else
asize = (DSIZE) * ((size + DSIZE + (DSIZE-1)) / (DSIZE));
if((bp = find_fit(asize))!= NULL){
place(bp,asize);
return bp;
}
extendsize = MAX(asize,CHUNKSIZE);
if((bp = extend_heap(extendsize/DSIZE))==NULL)
return NULL;
place(bp,asize);
return bp;
}
/*
* mm_free - Freeing a block does nothing.
*/
void mm_free(void *bp){
if(bp == NULL)
return;
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
PUT(NEXT_RP(bp),0); /*剛釋放的塊冈爹,設(shè)置前后指針為null*/
PUT(bp,0);
coalesce(bp);
}
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *ptr, size_t size){
void *newptr = mm_malloc(size);
if(!newptr){
return 0;
}
if(ptr == NULL){
return newptr;
}
size_t oldsize = GET_SIZE(HDRP(ptr));
memcpy(newptr, ptr, oldsize < size ? oldsize : size);
mm_free(ptr);
return newptr;
}
static void *find_fit(size_t size){
/*first fit*/
char *bp = GET(root);
while(bp != NULL){
if(GET_SIZE(HDRP(bp)) >= size)
return bp;
bp = GET(NEXT_RP(bp));
}
return NULL;
}
static void place(void *bp,size_t asize)
{
size_t csize = GET_SIZE(HDRP(bp));
__remove(bp); /*使用了這個(gè)塊,切記移除它*/
if(csize-asize >= 2 *DSIZE){
PUT(HDRP(bp),PACK(asize,1));
PUT(FTRP(bp),PACK(asize,1));
PUT(HDRP(NEXT_BLKP(bp)),PACK(csize-asize,0));
PUT(FTRP(NEXT_BLKP(bp)),PACK(csize-asize,0));
PUT(NEXT_RP(bp),0);
PUT((NEXT_BLKP(bp)),0);
coalesce(NEXT_BLKP(bp));
}
else{
PUT(HDRP(bp),PACK(csize,1));
PUT(FTRP(bp),PACK(csize,1));
}
}
static void *extend_heap(size_t words)
{
char *bp;
size_t size;
size = (words % 2) ? (words+1) * DSIZE : words * DSIZE;
if((long)(bp = mem_sbrk(size))==(void *)-1)
return NULL;
PUT(HDRP(bp),PACK(size,0));
PUT(FTRP(bp),PACK(size,0));
PUT(HDRP(NEXT_BLKP(bp)),PACK(0,1));
PUT(NEXT_RP(bp),0);
PUT(bp,0);
return coalesce(bp);
}
/*coalesce the empty block*/
static void *coalesce(void *bp)
{
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
/*coalesce the block and change the point*/
if(prev_alloc && !next_alloc){
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
__remove(NEXT_BLKP(bp)); /*使用了這個(gè)塊欧引,切記移除它*/
PUT(HDRP(bp), PACK(size,0));
PUT(FTRP(bp), PACK(size,0));
}
else if(!prev_alloc && next_alloc){
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
__remove(PREV_BLKP(bp));/*使用了這個(gè)塊频伤,切記移除它*/
PUT(FTRP(bp),PACK(size,0));
PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));
bp = PREV_BLKP(bp);
}
else if (!prev_alloc && !next_alloc){
size +=GET_SIZE(FTRP(NEXT_BLKP(bp)))+ GET_SIZE(HDRP(PREV_BLKP(bp)));
__remove(PREV_BLKP(bp));/*使用了這個(gè)塊,切記移除它*/
__remove(NEXT_BLKP(bp));/*使用了這個(gè)塊芝此,切記移除它*/
PUT(FTRP(NEXT_BLKP(bp)),PACK(size,0));
PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));
bp = PREV_BLKP(bp);
}
__insert(bp);/*新的空閑塊憋肖,記住插入*/
return bp;
}
inline void __insert(char *bp)
{
//PUT(bp, root); 這個(gè)操作有段錯(cuò)誤,挺離譜的
char *next = GET(root);
if(next != NULL)
PUT(next, bp);
PUT(NEXT_RP(bp), next);
PUT(root,bp);
}
inline void __remove(char *bp){
char *pre = GET((bp));
char *next = GET(NEXT_RP(bp));
/*因?yàn)樯厦娌迦氩僮鞑荒苤胋p的前驅(qū)為root,所以這個(gè)是必須考慮的婚苹,這個(gè)代表前面就是根節(jié)點(diǎn)了 */
if(pre == NULL){
if(next != NULL)
PUT(next,0);
PUT(root,next);
}
else{
if(next != NULL)
PUT((next),pre);
PUT(NEXT_RP(pre),next);
}
PUT(NEXT_RP(bp),0);
PUT(bp,0);
}
插入操作設(shè)置前驅(qū)為root竟然有段錯(cuò)誤瞬哼,真是折殺我也,也許是因?yàn)椴唤?jīng)意間會(huì)訪問(wèn)NEXT_RP(root)吧租副,這個(gè)值被我們?cè)O(shè)置成了NULL坐慰。哎,由衷敬佩操作系統(tǒng)開(kāi)發(fā)者用僧,和內(nèi)存打交道太不容易了结胀。
其實(shí)這個(gè)在插入時(shí)我覺(jué)得還可以以升序的方式插入,這樣可以提高利用率责循≡愀郏可惜了,還是我們的老朋友段錯(cuò)誤院仿,哎秸抚。
看來(lái)想要滿績(jī)(90)必須要采用分離適配了,最近被段錯(cuò)誤弄的有點(diǎn)暈歹垫,不過(guò)立個(gè)flag剥汤,2021年一定要完成它!