Constraints Allocators Must align blocks so they satisfy all alignment requirements usually 8 byte alignment Can only manipulate and modify free memory Can't move the allocated blocks once they are allocated i. e, compaction is not allowe
16 Constraints • Allocators – Must align blocks so they satisfy all alignment requirements • usually 8 byte alignment – Can only manipulate and modify free memory – Can’t move the allocated blocks once they are allocated • i.e., compaction is not allowed
Goals P735 Given some sequence of malloc and free requests Ro. R R k,…;n-1 Want to maximize throughput and peak memory utilization These goals are often conf licting
17 Goals P735 • Given some sequence of malloc and free requests: – R0 , R1 , ..., Rk , ... , Rn-1 • Want to maximize throughput and peak memory utilization. – These goals are often conflicting
Performance goals: throughput Number of completed requests per unit time Example: 5.00 malloc calls and 5.00 free calls in 1 seconds throughput is 1,000 operations second
18 Performance goals: throughput • Number of completed requests per unit time • Example: – 5,00 malloc calls and 5,00 free calls in 1 seconds – throughput is 1,000 operations/second
Performance goals: peak memory utilization Given some sequence of malloc and free requests Ro,R1,…,Rk, n-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 ggregate:合计,累计
19 Performance goals: 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. Aggregate: 合计，累计
Performance goals: peak memory utilization Given some sequence of malloc and free requests Ro. R R Def: current heap size is denoted by Hk Note that Hk is monotonically nondecreasing Def: peak memory utilization After k requests peak memory utilization is: Uk = maxick Pi)/
20 Performance goals: peak memory utilization • Given some sequence of malloc and free requests: – R0 , R1 , ..., Rk , ... , Rn-1 • Def: current heap size is denoted by Hk – Note that Hk is monotonically nondecreasing • Def: peak memory utilization: – After k requests, peak memory utilization is: • Uk = ( maxi<k Pi ) / Hk