基于C语言实现的Dynamic Storage Allocator动态内存分配器

深藏阁楼爱情的钟 2023-10-15 21:06 46阅读 0赞

目 录

第1章 实验基本信息 - 4 -  
1.1 实验目的 - 4 -  
1.2 实验环境与工具 - 4 -  
1.2.1 硬件环境 - 4 -  
1.2.2 软件环境 - 4 -  
1.2.3 开发工具 - 4 -  
1.3 实验预习 - 4 -  
第2章 实验预习 - 5 -  
2.1 进程的概念、创建和回收方法（5分） - 5 -  
2.2信号的机制、种类（5分） - 6 -  
2.3 信号的发送方法、阻塞方法、处理程序的设置方法（5分） - 5 -  
2.4 什么是shell，功能和处理流程（5分） - 5 -  
第3章 TinyShell测试 - 9 -  
3.1 TinyShell设计 - 9 -  
第4章 总结 - 14 -  
4.1 请总结本次实验的收获 - 14 -  
4.2 请给出对本次实验内容的建议 - 14 -  
参考文献 - 16 -  
2.1 动态内存分配器的基本原理（5分）  
动态内存分配器维护者一个进程的虚拟内存区域堆，每个块就是一个连续的虚拟内存片，已分配的块显式的保留为供应用程序使用，空闲块可用来分配。空闲块保持空闲，直到它显示的被应用所分配。一个已分配的块保持已分配的状态，直到它被释放，这种释放要么是应用程序显式执行的，要么是内存分配器自身隐式执行的。

2.2 带边界标签的隐式空闲链表分配器原理（5分）  
一个块是由一个字的头部、有效载荷，以及可能的一些额外的填充组成的，头部编码了这个快的大小，以及这个块是已分配的还是空闲的。每进行一个操作，就需要链表进行一次搜索，如果要分配内存，就找到大小符合的块进行分配，，如果要释放，就将头部和尾部的信息修改为空闲，然后搜索相邻的块进行合并成一个大块。

2.3 显示空间链表的基本原理（5分）  
在每个空闲块里都包含一个pred(前驱)和后继指针，形成一个双向链表，是的首次适配的分配时间从块总数的线性时间减少到了空闲块数量的线性时间。

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include "mm.h"
    #include "memlib.h"
    
    /* Team structure */
    team_t team = {
        
            "NULL",
            "NULL", "public",
            "", ""
    };
    
    /* $begin mallocmacros */
    /* Basic constants and macros */
    #define WSIZE       4       /* word size (bytes) */
    #define DSIZE       8       /* doubleword size (bytes) */
    #define CHUNKSIZE  (1<<12)  /* initial heap size (bytes) */
    #define OVERHEAD    8       /* overhead of header and footer (bytes) */
    
    #define MAX(x, y) ((x) > (y)? (x) : (y))
    
    /* Pack a size and allocated bit into a word */
    #define PACK(size, alloc)  ((size) | (alloc))
    
    /* Read and write a word at address p */
    #define GET(p)       (*(size_t *)(p))
    #define PUT(p, val)  (*(size_t *)(p) = (val))
    
    /* Read 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 bp, compute address of its header and footer */
    #define HDRP(bp)       ((char *)(bp) - WSIZE)
    #define FTRP(bp)       ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
    
    /* Given block ptr bp, compute address of next and previous blocks */
    #define NEXT_BLKP(bp)  ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
    #define PREV_BLKP(bp)  ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
    
    /* Given block ptr bp, compute address of next and previous free blocks */
    #define NEXT_FREE_BLKP(bp)  (char *)(GET((bp)))
    #define PREV_FREE_BLKP(bp)  (char *)(GET((bp) + WSIZE))
    
    /* set explicit freelist pointers of bp */
    #define SET_NEXTP(bp, p) PUT((bp), (size_t)(p))
    #define SET_PREVP(bp, p) PUT((bp)+WSIZE, (size_t)(p))
    
    /* $end mallocmacros */
    
    /* Global variables */
    static char *heap_listp;  /* pointer to first block */
    static char *heap_listr;  /* pointer to root of list */
    
    /* function prototypes for internal helper routines */
    static void *extend_heap(size_t words);
    
    static void place(void *bp, size_t asize);
    
    static void *find_fit(size_t asize);
    
    static void *coalesce(void *bp);
    
    static void checkblock(void *bp);
    
    static void mm_check(void);
    
    /*
     * mm_init - Initialize the memory manager
     */
    int mm_init(void) {
        
        /* create the initial empty heap */
        if ((heap_listp = mem_sbrk(4 * WSIZE)) == NULL)
            return -1;
        PUT(heap_listp, 0);                        /* alignment padding */
        PUT(heap_listp + WSIZE, PACK(OVERHEAD, 1));  /* prologue header */
        PUT(heap_listp + DSIZE, PACK(OVERHEAD, 1));  /* prologue footer */
        PUT(heap_listp + DSIZE + WSIZE, PACK(0, 1));   /* epilogue header */
    
        heap_listp += DSIZE;
        heap_listr = 0;
    
        /* Extend the empty heap with a free block of CHUNKSIZE bytes */
        if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
            return -1;
        return 0;
    }
    
    /*
     * mm_malloc - Allocate a block with at least size bytes of payload
     */
    void *mm_malloc(size_t size) {
        
        size_t asize;      /* adjusted block size */
        size_t extendsize; /* amount to extend heap if no fit */
        char *bp;
    
        /* Ignore spurious requests */
        if (size <= 0)
            return NULL;
    
        /* Adjust block size to include overhead and alignment reqs. */
        if (size <= DSIZE)
            asize = DSIZE + OVERHEAD;
        else
            asize = DSIZE * ((size + (OVERHEAD) + (DSIZE - 1)) / DSIZE);
    
        /* Search the free list for a fit */
        if ((bp = find_fit(asize)) != NULL) {
        
            place(bp, asize);
            return bp;
        }
    
        /* No fit found. Get more memory and place the block */
        extendsize = MAX(asize, CHUNKSIZE);
        if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
            return NULL;
        place(bp, asize);
        return bp;
    }
    
    /*
     * mm_free - Free a block
     */
    void mm_free(void *bp) {
        
        size_t size = GET_SIZE(HDRP(bp));
    
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
        coalesce(bp);
    }
    
    /*
     * mm_realloc - naive implementation of mm_realloc
     */
    void *mm_realloc(void *ptr, size_t size) {
        
        void *newp;
        size_t copySize;
    
        if ((newp = mm_malloc(size)) == NULL) {
        
            printf("ERROR: mm_malloc failed in mm_realloc\n");
            exit(1);
        }
        copySize = GET_SIZE(HDRP(ptr));
        if (size < copySize)
            copySize = size;
        memcpy(newp, ptr, copySize);
        mm_free(ptr);
        return newp;
    }
    
    
    /*
     * extend_heap - Extend heap with free block and return its block pointer
     */
    static void *extend_heap(size_t words) {
        
        char *bp;
        size_t size;
    
        /* Allocate an even number of words to maintain alignment */
        size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
        if ((bp = mem_sbrk((int) size)) == (void *) -1)
            return NULL;
    
        /* Initialize free block header/footer and the epilogue header */
        PUT(HDRP(bp), PACK(size, 0));         /* free block header */
        PUT(FTRP(bp), PACK(size, 0));         /* free block footer */
        PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* new epilogue header */
    
        /* Coalesce if the previous block was free */
        return coalesce(bp); /* coalesce will set next and prev pointers */
    }
    
    /*
     * place - Place block of asize bytes at start of free block bp
     *         and split if remainder would be at least minimum block size
     */
    static void place(void *bp, size_t asize)
    {
        
        size_t csize = GET_SIZE(HDRP(bp));
    
        /* remove block from free list */
        if (PREV_FREE_BLKP(bp))
            SET_NEXTP(PREV_FREE_BLKP(bp), NEXT_FREE_BLKP(bp));
        else
            heap_listr = NEXT_FREE_BLKP(bp);
        if (NEXT_FREE_BLKP(bp))
            SET_PREVP(NEXT_FREE_BLKP(bp), PREV_FREE_BLKP(bp));
    
        /* if the rest block is big enough,cut them,else,just place all*/
        if ((csize - asize) >= (DSIZE + OVERHEAD)) {
        
            PUT(HDRP(bp), PACK(asize, 1));
            PUT(FTRP(bp), PACK(asize, 1));
    
            bp = NEXT_BLKP(bp);
            PUT(HDRP(bp), PACK(csize - asize, 0));
            PUT(FTRP(bp), PACK(csize - asize, 0));
            coalesce(bp);
        } else {
        
            PUT(HDRP(bp), PACK(csize, 1));
            PUT(FTRP(bp), PACK(csize, 1));
        }
    }
    
    /*
     * find_fit - Find a fit for a block with asize bytes
     */
    static void *find_fit(size_t asize) {
        
        void *bp;
    
        for (bp = heap_listr; bp != 0; bp = NEXT_FREE_BLKP(bp)) {
        
            if (asize <= GET_SIZE(HDRP(bp))) {
        
                return bp;
            }
        }
        return NULL;
    }
    
    /*
     * coalesce - boundary tag coalescing. Return ptr to coalesced 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));
    
        if (prev_alloc && next_alloc) {
                    /* Case pre and next both used */
            /* set new head */
            SET_NEXTP(bp, heap_listr);
            if (heap_listr != 0)
                SET_PREVP(heap_listr, bp);
            SET_PREVP(bp, 0);
            heap_listr = bp;
        } else if (prev_alloc) {
              /* Case only pre used */
            bp = NEXT_BLKP(bp);
            /* remove block from free list */
            if (PREV_FREE_BLKP(bp))
                SET_NEXTP(PREV_FREE_BLKP(bp), NEXT_FREE_BLKP(bp));
            else
                heap_listr = NEXT_FREE_BLKP(bp);
            if (NEXT_FREE_BLKP(bp))
                SET_PREVP(NEXT_FREE_BLKP(bp), PREV_FREE_BLKP(bp));
            bp = PREV_BLKP(bp);
    
            /* set up new header & footer for current block */
            size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
            PUT(HDRP(bp), PACK(size, 0));
            PUT(FTRP(bp), PACK(size, 0));
    
            /* set new head */
            SET_NEXTP(bp, heap_listr);
            if (heap_listr != 0)
                SET_PREVP(heap_listr, bp);
            SET_PREVP(bp, 0);
            heap_listr = bp;
        } else if (next_alloc) {
              /* Case only next used */
            size += GET_SIZE(HDRP(PREV_BLKP(bp)));
            bp = PREV_BLKP(bp);
    
            /* remove block from free list */
            if (PREV_FREE_BLKP(bp))
                SET_NEXTP(PREV_FREE_BLKP(bp), NEXT_FREE_BLKP(bp));
            else
                heap_listr = NEXT_FREE_BLKP(bp);
            if (NEXT_FREE_BLKP(bp))
                SET_PREVP(NEXT_FREE_BLKP(bp), PREV_FREE_BLKP(bp));
    
            /* set up new header & footer for current block */
            PUT(HDRP(bp), PACK(size, 0));
            PUT(FTRP(bp), PACK(size, 0));
    
            /* set new head */
            SET_NEXTP(bp, heap_listr);
            if (heap_listr != 0)
                SET_PREVP(heap_listr, bp);
            SET_PREVP(bp, 0);
            heap_listr = bp;
        } else {
                                             /* Case pre and next both used */
            size += GET_SIZE(HDRP(PREV_BLKP(bp))) +
                    GET_SIZE(FTRP(NEXT_BLKP(bp)));
    
            bp = NEXT_BLKP(bp);
            /* remove block from free list */
            if (PREV_FREE_BLKP(bp))
                SET_NEXTP(PREV_FREE_BLKP(bp), NEXT_FREE_BLKP(bp));
            else
                heap_listr = NEXT_FREE_BLKP(bp);
            if (NEXT_FREE_BLKP(bp))
                SET_PREVP(NEXT_FREE_BLKP(bp), PREV_FREE_BLKP(bp));
    
            bp = PREV_BLKP(PREV_BLKP(bp));
            /* remove block from free list */
            if (PREV_FREE_BLKP(bp))
                SET_NEXTP(PREV_FREE_BLKP(bp), NEXT_FREE_BLKP(bp));
            else
                heap_listr = NEXT_FREE_BLKP(bp);
            if (NEXT_FREE_BLKP(bp))
                SET_PREVP(NEXT_FREE_BLKP(bp), PREV_FREE_BLKP(bp));
    
            /* set up header & footer for current block */
            PUT(HDRP(bp), PACK(size, 0));
            PUT(FTRP(bp), PACK(size, 0));
    
            /* set new head */
            SET_NEXTP(bp, heap_listr);
            if (heap_listr != 0)
                SET_PREVP(heap_listr, bp);
            SET_PREVP(bp, 0);
            heap_listr = bp;
        }
        return bp;
    }
    
    /*
     * mm_check - Check the heap for consistency
     */
    void mm_check(void) {
        
        char *bp = heap_listp;
    
        if ((GET_SIZE(HDRP(heap_listp)) != DSIZE) || !GET_ALLOC(HDRP(heap_listp)))
            printf("Bad prologue header\n");
        checkblock(heap_listp);
    
        for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
        
            checkblock(bp);   /* check if the block place align to 8*/
        }
    
        if ((GET_SIZE(HDRP(bp)) != 0) || !(GET_ALLOC(HDRP(bp))))
            printf("Bad epilogue header\n");
    }
    
    /*
     * checkblock - Check if the block place has aligned to 8
     */
    void checkblock(void *bp) {
        
        if ((size_t) bp % 8)
            printf("Error: %p is not doubleword aligned\n", bp);
        if (GET(HDRP(bp)) != GET(FTRP(bp)))
            printf("Error: header does not match footer\n");
    }

![在这里插入图片描述][d17baf0de99b49018a5efe008dae63c2.png_pic_center]  
![在这里插入图片描述][81bec679050340598698a08680f56515.png_pic_center]  
![在这里插入图片描述][9646d5a26e8a462abd5f16d422571048.png_pic_center]  
![在这里插入图片描述][d73dc5c2b2ac42ddb5fb86e8ab8053ca.png_pic_center]  
![在这里插入图片描述][6928531f60ea44ed8671a0cb2a811086.png_pic_center]  
![在这里插入图片描述][c2b39d3259db40d28d24a1787bbf3911.png_pic_center]  
![在这里插入图片描述][b4f35bc9864147e6a0e2bf3a19fcc4d5.png_pic_center]  
![在这里插入图片描述][e9cae8bc5fcd4a968b4a8b7501c48993.png_pic_center]

[d17baf0de99b49018a5efe008dae63c2.png_pic_center]: https://img-blog.csdnimg.cn/d17baf0de99b49018a5efe008dae63c2.png#pic_center
[81bec679050340598698a08680f56515.png_pic_center]: https://img-blog.csdnimg.cn/81bec679050340598698a08680f56515.png#pic_center
[9646d5a26e8a462abd5f16d422571048.png_pic_center]: https://img-blog.csdnimg.cn/9646d5a26e8a462abd5f16d422571048.png#pic_center
[d73dc5c2b2ac42ddb5fb86e8ab8053ca.png_pic_center]: https://img-blog.csdnimg.cn/d73dc5c2b2ac42ddb5fb86e8ab8053ca.png#pic_center
[6928531f60ea44ed8671a0cb2a811086.png_pic_center]: https://img-blog.csdnimg.cn/6928531f60ea44ed8671a0cb2a811086.png#pic_center
[c2b39d3259db40d28d24a1787bbf3911.png_pic_center]: https://img-blog.csdnimg.cn/c2b39d3259db40d28d24a1787bbf3911.png#pic_center
[b4f35bc9864147e6a0e2bf3a19fcc4d5.png_pic_center]: https://img-blog.csdnimg.cn/b4f35bc9864147e6a0e2bf3a19fcc4d5.png#pic_center
[e9cae8bc5fcd4a968b4a8b7501c48993.png_pic_center]: https://img-blog.csdnimg.cn/e9cae8bc5fcd4a968b4a8b7501c48993.png#pic_center