Okay, now that we know how implicit free lists work, let's look at explicit free lists. So in implicit free lists the reason we call it implicit was because we had the, a list we could you know, traverse entire heap and we, we knew implicitly. In obeys in the bit that was a bit that tells whether it's allocated or not, whether the block is free or not. So it was implicit because it had to traverse it to figure it out. Now with explicit free lists we're going to link free blocks to get explicitly. How do we do that? Well, instead of just having the size and a bit saying it's allocated or not, like we had an implicit free list for each block. What we're going to do is, since in free blocks, we do not have the payload and the padding. We're going to use pointers. We're going to use, we're going to put pointers there. One that points to the next free block. And one that points to the previous one. 'Kay? So and by the way, we still going to need boundary texts for coalescing. 'Kay? We'll see, we'll see examples of that. now, and logically it's a doubly-linked list, as I said. And we have pointed to it previous, we going to point it to the next one. So, logically, it feels like, you know, organizing some order here. But physically you know, when you look at how it's in memory, it could be really in any order, okay? So you have one and then the other and so on. So let's see how allocating from, from explicit lists look like, okay? So, for instance, here we have, this is before the allocation and we have a pointer to the next block. And these are all free blocks, okay? These are all free blocks. And this is pointing in one direction, and pointing in the other direction. And when we allocate. Say that we finally choose this one. So we choose this one. So, now, that's what we going to return to malloc. And this part's allocated, and whatever is free is going to be split and now we going to insert this block back into this. We going to update the pointers here so we include this one here in the, in the explicit free lists. 'Kay, that's how we allocate it. It's pretty simple right? Well freeing is a little bit more complicated because now there's an insertion policy, right? Remember that the blocks should actually be mainly actual order in this list, alright? So thinking, where are we going to put the block once we free something? Is very, very important, 'kay? So so to summarize, the insertion policy's where in the free list you put a newly freed block. And there's two basic policies. The first one is called LIFO, last-in-first-out. Policy. So did we insert a free block at the beginning of the free list always, okay? The pro is that it's pretty simple is constant time because you always have a pointer at the beginning of the list. But the con is that studies suggest that fragmentation is worse than just ordering by address which is the other policy. Address order, what it does is just links them in a way such that addresses of the previous block, is lower than the others, the current one and slower than the next one and so on, so it's just address order. The con is that requires linear time search when blocks are free because it has to find the way the timing goes, but, studies suggest that fragmentation is lower. And that's an interesting question. And by the way, memory location in general is just full of heuristics. Okay? It's just very hard to make sure that, very hard to make a provably best allocator. It's nearly impossible, potentially even impossible. So, this is just full of of heuristics. Okay, so let's see how the LIFO policy works. Okay? So we have the first case here. So the first case is we have a free block, and there's nothing. It's a, a, we free a block in the middle of something allocated, and what we're going to do is we're just going to free it and up. And since we're doing LIFO, last in first out, it's going to be. There's, there's going to be sort of the beginning of the list. So now the root points to this new free block. And then we update the pointers accordingly. The, the old one, now, the old first one, just points backs to the one that was just inserted. Pretty simple, right? Okay. So let's see the other case. The other case here is that we are freeing something, and right before it we have, right before it we have a block that's free. So what are we going to do? Well, we're going to merge it, okay? And but now note that the resulting block, the resulting block here is the one that gets inserted in the beginning of the list. So now the root points here, okay? Because we just got this old block here and extended it with the one that we just freed. Simple, right? Great. Let's see one more case here. Now suppose that what we could, what we do, we're going to free a block and right next to it, after it, we have a free block. We're going to the same what we did, as, as we did before. We're going to merge into a larger block. Okay? We're going to merge this whole thing into a larger free block. And then we're going to update the links accordingly, such accordingly, such that the root now points to this newly formed larger block. We removed the older block here because it really, it's just part of a larger one now. And we're going to update the pointers accordingly. Okay? Good. So like the, the fourth and last case here is when you say that you free a block, and then there's ac-, there's two blocks that, on either side, and on both sides of it, that are now can be coalesced into one large block. So we're going to, we're going to remove the old ones from the list. We're going to create a new large block and we're going to search this large block at the beginning of the list so the root points there now. Pretty cool right? Okay, so now we created a big block. Hopefully this happens a lot so we can have more lots of large blocks. So to, to summarize, comparing explicit free list to implicit free list, the allocate is linear in the number of free blocks, instead of all blocks like what we had in implicit, in implicit free list, and this is much faster, when most of the memory is full. Well, why is that? Because when most of the memory is full in the implicit case, we're going to have to traverse in time memory. Okay? So we have, we might have to traverse not the entire memory, but most of memory until we find one. It's likely that we're going to do that. With explicit free lists you know, it's just, we just know it, okay? It's slightly more complicated to allocate in free because it needs to splice blocks in and out of their lists, okay? We also need some extra space for the links, so two extra words needed for each block. So that means that the minimal free block size has to be, mine has to be a little bit larger so it leads to more internal fragmentation. Such is life but I think it's worth it. And so in most common use of explicit list is with what we call segregated free lists. With the idea is to keep multiple link lists of different sizes. Of free blocks and even possible for different types of objects, okay. That's what we are going to see now, that's a method three. Okay, so the concept is very very simple, we are going to have bunch of size classes and for each size class we are going to have eight free explicit free lists. So here's for size one and two, you have one, for size three I have another one and so on. 'Kay? And often we have separate classes for each small size. 'Kay? And then we have one, you see this, you know, this, those are the small ones. And then we have nine in the, in the big, big one. 'Kay? So, and for larger size we have one for each two power size, a power is two size. So how, how does that work in a little bit more detail here's how we going to allocate it. OK, so given this array of free lists and each one of some class sizes if you allocate a block of size n, what you are going to do first is, you are going to find a lesser size m that's larger than the size n that you want, if, if it finds a block that's appropriate we just allocate it. If no block is found, we just try the next larger class, and we repeat until a block is found. And of course if no block is found, you have to go and increase the size of the heap using this a system called sbrk that I had mentioned before as well, 'kay? So and then when we do that we're going to allocate a block of n sizes. of size n from this new memory, and place the remainders as a single free block in the largest class. 'Kay. We want to keep things in large blocks and then start splitting them. 'Kay? Great. So when you free a block, you want to free the block, look at the resulting freed block, coalesce it as much as you can, and then reinsert the block into the appropriate list. Okay? So that's pretty cool right? So now we might have, and when we free it, we might actually change the category and have to insert it in a different in a different list. So the advantage of seglist segregators, segregator list allocators is higher throughput. And we have log time for power of two size classes, right? There'd be logarithmic time to, to, to find an appropriate one, and also it has a better memory utilization because the first fit search on this allocated on the segregated free list really approximates the best fits that we had, that of the entire heap. Okay, really it's an approx, not exactly but some an approximate. Okay. So in an extreme case, if you give each block its own size class, you know, in the array of lists. That's going to be equivalent to best fit. Okay. All right. So to summarize the summary of the key allocator properties allocator policies are the placement policy. We have first fit, next fit, and best fit. Okay. [INAUDIBLE]. So and this trades off throughput for last, for fragmentation, okay. So the observation I just told you is that segregated free lists approximate a best fit placement without having to search the entire free list. And so we have a splitting policy, when do we go ahead and split free blocks? Okay, so that depends on how much internal fragmentation are we willing to tolerate. Okay? So you might to and so there's also coalescing policy. You could do coalescing as soon as you do free, okay? When you call free, just do it right away. So that might have some throughput implications because you do more work at free. Or it can just delay it as long as you can. So you don't pay the throughput but then you might be paying more for fragmentation okay. See you soon.