tailieunhanh - data structures and algorithms in C PHẦN 10

Phương pháp tiếp cận của ông là rất thực tế, ví dụ bằng cách sử dụng các bài kiểm tra thời gian hơn so với phân tích Big O để so sánh hiệu suất của các cấu trúc dữ liệu và các thuật toán. Cuốn sách này có thể được sử dụng trong cả hai bắt đầu và tiên tiến | Section The Nonsequential-Fit Methods c 58 7 Figure 12. J Block structure in the binary buddy system. This block is too large since roundedsize availsize so the block is divided into two buddies. The first buddy is marked as reserved and returned and the second is included in a list Figure . Finally a block of 16 locations is requested. After two iterations of the while loop of reserve the configuration pictured in Figure emerges there are two available blocks of 16 locations and both are linked up together in list avail 4 . To be sure blocks of memory are not only claimed but they are returned hence they have to be included in the pool of available blocks. Before they are included the status of each block s buddy is checked. If the buddy is available the block is combined with its buddy to create a block twice as large as before the combination. If the buddy of the new block is available it is also combined with its buddy resulting in a still larger block of memory. This process continues until the entire memory is combined into one block or a buddy is not available. This coalescing creates blocks of available memory as large as possible. The algorithm of including a block in the pool of available blocks is as follows include block blocksize size block buddy address block withbit blocksize l set to its complement while statusị buddy is 0 buddy has not and size buddy blocksize been claimed and blocksize lg size of memory buddy exists detach buddy from list avail blocksize block block plus body coalesce block and its buddy setstatMS block to 0 blocksize buddy address now extended block with bit blocksize l set to its complement include block in list avail blocksize Figure illustrates this process. A block previously claimed is now released Figure and because the buddy of this block is free it is combined with the D Chapter 12 Memory Management Figure Reserving three blocks of memory using the binary buddy system. 0_ 07W I b 18 .