[SOLVED] CS代考计算机代写 Carnegie Mellon

Carnegie Mellon
Heap assumptions for lecture
 Memory is word addressed (each word can hold a pointer)
Allocated block (4 words)
Free block (3 words)
Free word Allocated word
1

Carnegie Mellon
Allocation Example
p1 = malloc(4)
p2 = malloc(5)
p3 = malloc(6)
free(p2)
p4 = malloc(2)
2

Carnegie Mellon
Constraints
 Applications
 Can issue arbitrary sequence of malloc and free requests freerequestmustbetoamalloc’d block
 Allocators
 Can’t control number or size of allocated blocks  Must respond immediately to malloc requests
 i.e., can’t reorder or buffer requests  Must allocate blocks from free memory
 i.e., can only place allocated blocks in free memory
 Must align blocks so they satisfy all alignment requirements
 8 byte alignment for GNU malloc (libc malloc) on Linux boxes  Can manipulate and modify only free memory
 Can’t move the allocated blocks once they are malloc’d
 i.e., compaction is not allowed
3

Carnegie Mellon
Performance Goal: Throughput
 Given some sequence of malloc and free requests:
 R0, R1, …, Rk, … , Rn-1
 Goals: maximize throughput and peak memory utilization
 These goals are often conflicting
 Throughput:
 Number of completed requests per unit time  Example:
 5,000 malloc calls and 5,000 free calls in 10 seconds  Throughput is 1,000 operations/second
4

Carnegie Mellon
Performance Goal: Peak Memory Utilization  Given some sequence of malloc and free requests:
 R0, R1, …, Rk, … , Rn-1
 Def: Aggregate payload Pk
 malloc(p) results in a block with a payload of p bytes
 After request Rk has completed, the aggregate payload Pk is the sum of currently allocated payloads
 Def: Current heap size Hk
 Assume Hk is monotonically nondecreasing
 i.e., heap only grows when allocator uses sbrk
 Def: Peak memory utilization after k requests Uk =(maxi